@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix dc: . @prefix skos: . vivo:departmentOrSchool "Applied Science, Faculty of"@en, "Electrical and Computer Engineering, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Wang, Hao"@en ; dcterms:issued "2009-10-28T22:29:11Z"@en, "2003"@en ; vivo:relatedDegree "Master of Applied Science - MASc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description "Shortest Path First (SPF) routing protocols such as OSPF and IS-IS are the dominant intradomain Internet routing protocols nowadays, and are widely used in the Internet Service Provider (ISP) backbone networks. The weights, or the lengths, of the links in an OSPF/IS-IS network are set by the network operator and usually are not changed during the network operation. The packets are routed along the shortest paths from the sources to the destinations. The paths between the origin and destination pairs are fixed regardless of the traffic load changes, since the weights of the links are predetermined. The objective of this thesis is to investigate a way of adapting the weights in SPF routing, such as OSPF and IS-IS, in real-time dynamically according to the traffic loads of the links and to evaluate its performance over non-adaptive routing. The feedback effect and the stability issue of adaptive routing are studied from a control point of view, and the analysis shows why Minimal-Delay Adaptive Routing in the early ARPANET is not stable and what can be done to make adaptive routing stable. The thesis presents a routing algorithm, Load-Sensitive Adaptive Routing (LSAR), which keeps the traffic balancing ability of adaptive routing and avoids the undesirable unstable behavior at the same time. Finally, the performance of LSAR is tested in simulations. The simulation software used is Network Simulator 2 (ns2). The result shows that, compared with non-adaptive OSPF/IS-IS routing, LSAR improves the network throughput and reduces the packet drop rate significantly, and does not show unstable behavior under either light or heavy traffic load."@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/14233?expand=metadata"@en ; dcterms:extent "2560841 bytes"@en ; dc:format "application/pdf"@en ; skos:note "L O A D - S E N S I T I V E A D A P T I V E R O U T I N G ( L S A R ) F O R C O M P U T E R N E T W O R K S by Hao Wang B.Eng. , Harbin Institute of Technology, Harbin, China, 1998 M . E n g . , Harbin Institute of Technology, Harbin, China, 2000 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES DEPARTMENT OF ELECTRICAL AND COMPUTER ENGINEERING We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA April 2003 © Hao Wang, 2003 In presenting this thesis in partial fulfilment of the requirements for an advanced degree at the University of British Columbia, I agree that the Library shall make it freely available for reference and study. I further agree that permission for extensive copying of this thesis for scholarly purposes may be granted by the head of my department or by his or her representatives. It is understood that copying or publication of this thesis for financial gain shall not be allowed without my written permission. Department of LUc-trieM &*«r***^ £*J> Insertft^. The University of British Columbia Vancouver, Canada Date DE-6 (2/88) Abstract Shortest Path First (SPF) routing protocols such as O S P F and IS-IS are the dominant intradomain Internet routing protocols nowadays, and are widely used in the Internet Service Provider (ISP) backbone networks. The weights, or the lengths, of the links in an OSPF/IS-IS network are set by the network operator and usually are not changed during the network operation. The packets are routed along the shortest paths from the sources to the destinations. The paths between the origin and destination pairs are fixed regardless of the traffic load changes, since the weights of the links are predetermined. The objective of this thesis is to investigate a way of adapting the weights in SPF routing, such as O S P F and IS-IS, in real-time dynamically according to the traffic loads of the links and to evaluate its performance over non-adaptive routing. The feedback effect and the stability issue of adaptive routing are studied from a control point of view, and the analysis shows why Minimal-Delay Adaptive Routing in the early A R P A N E T is not stable and what can be done to make adaptive routing stable. The thesis presents a routing algorithm, Load-Sensitive Adaptive Routing ( L S A R ) , which keeps the traffic balancing ability of adaptive routing and avoids the undesirable unstable behavior at the same time. Finally, the performance of L S A R is tested in simulations. The simulation software used is Network Simulator 2 (ns2). The result shows that, compared with non-adaptive OSPF/IS-IS routing, L S A R improves the network throughput and reduces the packet drop rate significantly, and does not show unstable behavior under either light or heavy traffic load. Table of Contents Abstract ii Table of Contents iii List of Tables vi List of Figures vii Acknowledgement viii Chapter 1. Introduction 1 1.1 Introduction to Internet Protocol (IP) and IP Routing 1 1.1.1 The OSI Reference Model 1 1.1.2 IP and IP Routing 2 1.1.3 Classification of IP Routing Protocols 3 1.2 Motivation and Objective 8 1.2.1 Limitation of Current Link-State Routing Protocols 8 1.2.2 Related Work 9 1.2.3 Objective 9 1.3 Thesis Outline 10 Chapter 2. A Review of Adaptive Routing 11 2.1 A Brief Historical Review of IP Routing 11 2.2 Minimal-Delay Adaptive Routing 12 2.2.1 The Bertsekas's Analysis 12 2.2.2 The Dynamic Behavior Analysis 15 2.3 Summary 17 Chapter 3. Load-Sensitive Adaptive Routing (LSAR) 18 3.1 Weight Mapping in L S A R 18 3.1.1 Weight Mapping Function in M D A R 19 3.1.2 Weight Mapping Function in L S A R 20 3.2 Damping by Averaging 22 3.2.1 The Dynamic Behavior Graph of Adaptive Routing 22 3.2.2 The Effect of Adding Bias in M D A R 24 3.2.3 Damping by Averaging in L S A R 25 3.3 The Minimal Weight Update Limit 26 3.3.1 Two Types of Equilibrium Points 26 3.3.2 The Minimal Weight Update Limit 27 3.4 Summary 28 Chapter 4. Simulation in ns2 30 4.1 The Simulation Software 30 4.1.1 Network Simulator 2 (nsl) 30 4.1.2 Routing in nsl • 30 4.2 Network Topologies Generator 32 4.3 Static Traffic Test 33 4.3.1 Traffic Generation 33 4.3.2 Simulation Results 33 4.3.3 Discussion 37 4.4 Dynamic Traffic Test 38 4.4.1 Traffic Generation 38 4.4.2 Simulation Results 40 4.4.3 Discussion • 43 4.5 Summary 43 Chapter 5. Conclusions and Future Work 45 5.1 Conclusions 45 5.2 Future Work 47 Bibliography 50 Appendix A Simulation Topologies 54 iv A . 1 ns2 Codes for Random Topology Generation 54 A . 1.1 ns2 Code for Generating Topologies with 16 Nodes 54 A . 1.2 ns2 Code for Generating Topologies with 32 Nodes 55 A . 1.3 ns2 Code for Generating Topologies with 64 Nodes 56 A .2 Topology Samples -. 57 A.2.1 A Topology Sample with 16 Nodes 57 A.2.2 A Topology Sample with 32 Nodes 58 A.2.3 A Topology Sample with 64 Nodes 59 V List of Tables Table 1.1 Intradomain and Interdomain Routing Protocols 4 Table 1.2 Distance Vector and Link-State Protocols 6 Table 4.1 The Parameters of L S A R 31 Table 4.2 Network Topologies Used in Static Traffic Simulation 32 Table 4.3 Simulation Results For Dynamic Traffic Loads 41 List of Figures Figure 1.1 OSI Reference Model 1 Figure 1.2 Intradomain and Interdomain routing 5 Figure 2.1 A Simple Ring Topology 13 Figure 2.2 Routing Oscillation in Minimal-Delay Adaptive Routing 16 Figure 3.1 The System Block Diagram of M D A R 19 Figure 3.2 The Weight Mapping Function of L S A R 21 Figure 3.3 Dynamic Behavior Graph of a Weight-Changing Link in a M D A R Network 23 Figure 3.4 The Effect of Adding Bias to the Weight Mapping Function 24 Figure 3.5 The Two Types of Equilibrium Points in Adaptive Routing 26 Figure 3.6 The System Block Diagram of L S A R 29 Figure 4.1 Simulation Result for Static traffic on Topology 1(16 nodes, 23 links) 34 Figure 4.2 Simulation Result for Static traffic on Topology 2 (16 nodes, 22 links) 35 Figure 4.3 Simulation Result for Static traffic on Topology 3 (32 nodes, 55 links) 35 Figure 4.4 Simulation Result for Static traffic on Topology 4 (32 nodes, 57 links) 36 Figure 4.5 Simulation Result for Static traffic on Topology 5 (64 nodes, 210 links) 36 Figure 4.6 Simulation Result for Static traffic on Topology 6 (64 nodes, 194 links) 37 Figure 4.7 The Dynamic Traffic Load Over L i n k l in an OSPF/IS-IS Network 39 Figure 4.8 The Dynamic Traffic Load Over Link2 in an OSPF/IS-IS Network 39 Figure 4.9 The Dynamic Traffic Load Over L i n k l in a L S A R Network 42 Figure 4.10 The Dynamic Traffic Load Over Link2 in a L S A R Network 42 vii Acknowledgement I would like to express my sincerest gratitude to my thesis supervisor, Dr. Mabo R. Ito, for his continuous guidance and support throughout this thesis and my education at U B C . His critical reviews and many constructive suggestions were essential to the completion of this work. Without his guidance and support, this work could not have been accomplished. I would also like to thank Lechang Cheng, Sukhwinder S. Virk, Han W u , Xiul iu Huang, Mulong Gao, and other fellow students in the computer engineering research group for making my studies at U B C memorable and interesting. Finally, I would like to thank my family, especially my lovely wife Yuan Zhang, for their love, support and encouragement. Chapter 1. Introduction 1.1 Introduction to Internet Protocol (IP) and IP Routing 1.1.1 The OSI Reference Model The Open Systems Interconnection (OSI) reference model has served as one of the most basic, yet essential, elements of computer networking since its inception in 1984. OSI is an abstract model and offers a very practical structured introduction to many networking concepts. OSI divides the task of host-to-host networking into a vertical stack containing seven layers as shown in Figure 1.1. 7 Application 6 Presentation 5 Session 4 Transport 3 Network 2 Data Link 1 Physical Figure 1.1 OSI Reference Model. OSI designates the application, presentation, and session layers as \"upper layers.\" Generally 1 speaking, software in these layers performs application-specific functions like data formatting, encryption, and connection management. The remaining \"lower layers\" provide more primitive network-specific functions like routing, addressing, and flow control. 1.1.2 IP and IP Routing IP is the dominant Layer 3 protocol for connectionless data networking. IP is part of a suite of protocols referred to as the Transmission Control Protocol/Internet Protocol (TCP/IP) protocol suite. The TCP/ IP suite embraces many protocols, which continue to grow as new applications emerge. Some key IP protocols include Internet Protocol (IP), Transmission Control Protocol (TCP), User Datagram Protocol (UDP) and Internet Control Message Protocol ( ICMP) . T C P and U D P run over the IP layer and provide transport for applications. I C M P is a control protocol that works alongside IP at the network layer. Numerous applications use the transport services of T C P and U D P , such as Telnet, F i le Transfer Protocol (FTP), World Wide Web ( W W W ) and Domain Name Service (DNS) . IP is largely responsible for the continuing success of the T C P / I P suite, mainly because of its simplicity and high efficiency for transferring data. In connectionless networking, data is presented in self-contained routable units known as datagrams or packets. There is no need for prior setup of an end-to-end path between the source and destination before data transmission is initiated. Packets, which contain the data to be transferred over the network, are forwarded, or routed, independently along the path by routers located between the source and destination. Each packet contains information, such as source and destination addresses, which is used by routers when making routing decisions. A router is a network device that essentially consists of a collection of network interfaces linked 2 together by a high-speed bus or a complex interconnection system, such as a crossbar-switch or shared memory fabric. A router has two functional planes: data and control. Frequently, both functions are performed by an intelligent subsystem known as the route processor. Most modern high-speed routers are designed with a clear separation between the control and data planes. The control plane functions are centered on building the necessary intelligence about the state of the network and a router's interfaces. The data plane handles actual packet processing and forwarding by relying on the intelligence of the control plane. IP routing is the broader process of collecting routing information about the network. IP routing protocols process this information to determine the best paths to destinations in the network. The best paths are stored in the routing table. The routing table is then used for forwarding packets, moving them out of the router onto the best paths to the next hop and toward their intended destinations. The best path is usually the path with the lowest value of metric or cost to the destination. IP routing is primarily based on the destination address and is commonly referred as destination-based routing. 1.1.3 Classification of IP Routing Protocols Routing between the various segments of a network can be achieved by programming the routers with manual routing information, commonly referred to as static routing, or by using a dynamic protocol to automate the collection of routing information and intelligence. The applications or protocols used in the latter case are referred to as dynamic routing protocols. Static routing requires the network administrator to preprogram the routing table manually, and it does not have the ability to respond to the topology changes of the network. Although static routing could be very resource efficient, both in bandwidth and in C P U horsepower, and works well in simple and small networks, if carefully engineered, it is not suitable for working in today's large, 3 complex and dynamic networks. Some common dynamic IP routing protocols in use today are the Routing Information Protocol (RIP) version 1 [17] and version 2 [18], Interior Gateway Routing Protocol (IGRP) [19], Enhanced Interior Gateway Routing Protocol (EIGRP) [20], Integrated Intermediate System-to-Intermediate System Routing Protocol (IS-IS) [15], Open Shortest Path Routing Protocol (OSPF) [14], and the Border Gateway Protocol (BGP) [21]. These commonly used dynamic routing protocols can be differentiated using the following classifications: intradomain versus interdomain routing, and distance-vector versus link-state protocols. The different breeds of routing protocols have different capabilities related to both architectural design and embedded functionality. • Intradomain Versus Interdomain Routing Intradomain Routing Interdomain Routing R I P v l RIP v2 IGRP B G P E I G R P O S P F IS-IS Table 1.1 Intradomain and Interdomain Routing Protocols A network of interconnected routers and related systems managed and maintained together by a common administration is often referred to as a network domain, or sometimes called an autonomous system (AS). The Internet consists of several interconnected network domains spanning the whole world. Routing protocols are designed and optimized for use within a domain (intradomain) or between domains (interdomain). Figure 1.2 Intradomain and Interdomain routing. Figure 1.2 shows three network domains (AS1, AS2 , and AS3) interconnected into a global routing system. Also depicted in the diagram are instances of intradomain and interdomain routing. A l l the routing protocols we mentioned earlier, with the exception of B G P , are optimized for intradomain functionality. Because autonomous systems, or domains, are owned and administered by different owners, it is obvious that interdomain routing requires more complex policies to control the exchange of routing information than intradomain routing does. Because of the vastness of the global Internet, the number of routes that need to be handled globally is very large and is growing continuously. Therefore, an interdomain routing protocol must handle a large number of routes under both stable and unstable conditions. A n interdomain routing protocol also must support configuration of complex policies, such as route filtering, tagging and so on, respond reasonably fast to network changes, and handle multiple peers, with each peer presenting a different view of the same large tables. Currently, only B G P can deliver on all these requirements, and it remains the de facto interdomain routing protocol on the Internet. The B G P , as an interdomain routing protocol, focuses mainly on the aspect of policy 5 implementation among the different ASs , instead of finding the best route from an origin to a destination. It uses the hop-counting criteria for the route selection, which is not very efficient. It also does not have the ability to cope with congestion, because the information exchanged by B G P routers contains only the connectivity information. B G P also has instability problem, on which some research had been done [22] [23]. In fact, because of the problems of B G P , the routing of Internet does not perform very well. Some people are even doing routing over Internet in order to get satisfying performance [24]. But interdomain routing is out of the context of this thesis. The subject of this thesis is intradomain routing. • Distance-Vector Versus Link-State Protocols This classification of routing protocols is based on architectural design. Essentially, this categorization applies to intradomain protocols, also known as Interior Gateway Protocols (IGPs). The only surviving interdomain protocol, B G P , was discussed earlier. Protocol Category Metric Algorithm R I P v l Distance Vector Hop count Bellman-Ford RIP v2 Distance Vector Hop count Bellman-Ford IGRP Distance Vector Composite Bellman-Ford E I G R P Distance Vector Composite Diffusing Update Algorithm O S P F Link State Bandwidth-based cost Shortest Path First IS-IS L ink State Manual cost Shortest Path First Table 1.2 Distance Vector and Link-State Protocols Table 1.1 shows the classification of IGPs into distance-vector and link-state protocols. IGPs are easily placed into these two categories. The primary difference between these two types of routing lies in the way they discover and calculate routes to destinations. The algorithms used in distance-vector routing are called Bellman-Ford algorithms. The routers periodically pass copies of their routing tables, consisting of distance vectors to destinations, to their immediate network neighbors. Each recipient router updates its own distance vectors in its routing table according to the information received and forwards the routing table to its immediate neighbors. This process occurs in an omnidirectional manner among immediately neighboring routers. Each router in this algorithms only has the knowledge of the distances to networked resources of its immediate neighbors. It does not know anything specific about other routers, or the network's actual topology. The routers in link-state routing algorithms maintain a complete database of the network's topology, so they have full knowledge of the network's routers as well as how they are interconnected. This is achieved by the broadcasting of link-state advertisement (LSAs) within the network. The routers originate L S A s , and broadcast them throughout the network. Each router in the network constructs an identical topological database using all received L S A s . A Shortest Path First (SPF) algorithm, also called Dijkstra's Algorithm, is then used to compute the routes to networked destinations, and the routing table is updated according to the routes calculated. Since the routers have complete knowledge of the network, link-state algorithms have better performance in finding the optimal routes and converge quicker than the distance-vector algorithms. Distance-vector protocols are simpler in design, but they use periodic update mechanisms that consume a lot of bandwidth resources. Link-state protocols send only incremental updates for any network changes. In general, link-state protocols require a lot more processing and memory resources than distance-vector protocols. However, they do not have some of the inherent problems associated with distance-vector protocols such as periodic updates, transient loops, count to infinity, and slow convergence issues. 7 Because of the advantages of link-state routing over distance-vector routing, OSPF and IS-IS have become the dominant intradomain routing protocols running over the IP networks. They are both effective, and, for the most part, are functionally identical. The original design of IS-IS was optimized for large LANs and SPF computation performance. OSPF was optimized for efficient bandwidth utilization and reliability. High-speed routing technology has significantly evolved since inception of these protocols, obsoleting most of the original design criteria. Yet, both protocols have withstood the test of time and have emerged as the only viable IGP options for large scale routing. OSPF has a large number of vendor implementations but there are few mature and stable IS-IS implementations. OSPF is more of a full Internet standard, better documented and more widely understood. Most IP-based enterprise networks have deployed OSPF whereas IS-IS remains largely deployed in the service provider space for both practical and historical reasons. IS-IS has recently attracted a lot of interest in the IEFT, and there is considerable ongoing effort for its advancement. Many vendors and large ISPs are backing IS-IS efforts in the IETF. 1.2 Motivation and Objective 1.2.1 Limitation of Current Link-State Routing Protocols OSPF and IS-IS, the only current implementations of link-state routing, are the dominant intradomain IP routing protocols today, and are widely used in the Internet Service Provider (ISP) backbone networks. The weights, or the lengths, of the links in an OSPF/IS-IS network are set by the network operator and usually are not changed during the network operation. The traffic is routed along the shortest paths from sources to destinations based on the link weights. Because the link weights are fixed, the paths between the origin and destination pairs are also fixed regardless of the traffic load changes. In OSPF the link weights are set using the formula of 8 W = l x l 0 8 / W [13], where BW is the bandwidth of the corresponding link. While in IS-IS, the weights of all links are set to the same default value of 10 [16]. One problem of OSPF and IS-IS is that they do not have the ability to do traffic engineering, because the cost of each link in an OSPF/IS-IS network is fixed. Although OSPF and IS-IS can cope with some network topology changes, like link up and down, they do not have the ability to adapt to the dynamic traffic running over the network. 1.2.2 Related Work One way of solving the traffic engineering problem is by introducing the Multi-Protocol Label Switching (MPLS) protocol [27] [28]. In principle, MPLS would allow arbitrary routing in the network, but it is not yet widely deployed, let alone tested. Another way of doing traffic engineering is to optimize the weights in OSPF/IS-IS networks [4] [5] [6] [7] [8] [9]. It has been shown that by properly setting the weights in an OSPF/IS-IS network, significantly better network throughput and performance can be achieved compared with the simple default weight settings recommended by vendors. The limitation of this research is that their optimizations were done offline based on static traffic loads on the network. Because the weight settings of the links are still static, the routing algorithms are not adaptive to real network traffic loads, which are very dynamic. Since the algorithms need the traffic statistics and will do the optimization offline, they are hard to implement in real networks. \" 1.2.3 Objective The objective of the thesis is to investigate a way of adaptively changing the link weights in an OSPF/IS-IS network in real-time according to the current traffic loads on the links and to evaluate 9 the performance of this adaptive routing algorithm by comparing it with conventional non-adaptive link-state routing algorithms. 1.3 Thesis Out l ine The thesis is organized as follows. Chapter 1 is the introduction. Chapter 2 gives a brief historical review about adaptive routing and also some previous research on the dynamics of Minimal-Delay Adaptive Routing. The proposed Load-Sensitive Adaptive Routing ( L S A R ) algorithm is presented in Chapter 3, which includes detailed implementation and the dynamics analysis of L S A R . In Chapter 4, the performance of L S A R is evaluated by simulations. Finally, Chapter 5 draws the conclusion and gives some discussion on future work. 10 Chapter 2. A Review of Adaptive Routing Before presenting the Load-Sensitive Adaptive Routing algorithm, it is necessary to have a brief review of the history of adaptive routing algorithms implemented in the past. 2.1 A Brief Historical Review of IP Routing The history of IP routing can be dated back as early as the late 1960's, when the A R P A N E T was first developed. The original routing algorithm for A R P A N E T was a truly adaptive routing algorithm. The delay of each link in the network was continuously estimated, and the weight of each link was set based on the estimated delay. The algorithm used the distributed Bellman-Ford algorithm and tried to route the packets along the minimum weight path, in other words the minimal delay path. This routing algorithm was a distance-vector routing algorithm. It served very well at the beginning of implementation and attracted considerable attentions. But in the late 1970's, people began to observe a number of problems with the original A R P A N E T routing algorithm. These problems include the formation of loops, heavy routing overhead, and slow convergence. The problems were so fatal that a complete redesign of the routing algorithm had to be done [25]. The new routing algorithm for the A R P A N E T was a link-state routing algorithm. It abandoned the distributed Bellman-Ford algorithms in its route calculation and replaced it with the Shortest Path First (SPF) algorithms, therefore solving some of the problems of the previous distance-vector routing algorithm. One thing in common between the original and new routing algorithm was that they both associate the weights of the links in the networks directly with the link delays. The new routing algorithm measured the average delay of each link instead of estimation as the original l l algorithm did, but it still set the link weights according to the measured delays, therefore it was still a Minimal Delay Adaptive Routing algorithm. 2.2 Minimal-Delay Adaptive Routing The Minimal Delay Adaptive Routing (MDAR) algorithms had a fatal defect. They were prone to severe routing oscillations under high volume of traffic. In 1982, Bertsekas published his study of the dynamics of adaptive routing [1] and gave some theoretical analysis on the instability issue of Minimal Delay Adaptive Routing. His research was very discouraging to adaptive routing researchers. After Bertsekas, Wang and Crowcroft [2] also did research on the dynamics of adaptive routing, but they almost repeated the same result as Bertsekas. Little research has been done on adaptive routing since then, and almost all the current routing protocols use static link weight settings rather than changing them adaptively. Engineers and researchers are working hard to find out other ways of doing load balancing and congestion control over static routing, since the routing protocol itself does not have this capability. In this section, some previous theoretical analysis about the dynamics of Minimal-Delay Adaptive Routing is briefly reviewed. 2 . 2 . 1 The Bertsekas's Analysis Bertsekas's analysis starts from a simple ring topology, as shown in Figure 2.1. Consider a ring network with N nodes show in Figure 2.1 (a), where node N is the only destination node and all links are duplex links. The traffic originating for node i and destined for N is denoted as rt, which is a constant. The routing in this network is denoted as Rt (i = 1,..., N) , 12 for which all nodes j < i route their traffic in the clockwise direction and all nodes j > i route their traffic in the counterclockwise direction as shown in Figure 1 (b). Figure 2.1 A Simple Ring Topology. Given a routing Rt , the flows on each undirected link — in the clockwise and counterclockwise directions are denoted by / . (/) and fj+(i) respectively and are given by r c o = { ° ' i f l ~ j J 1 [r^+r^+.-. + rj, if i> j f+n-l °' i f i - j T i \\rt+rM+... + r}_x, if i 0 . In M D A R , such as the early routing algorithms in the A R P A N E T , the weights are associated directly with the delay, which means the function of d is defined as 13 d(fa) = Pu+Ta+Qtt(Jtt) (2.2) where Pu is the average processing plus propagation delay per message, Ttt is the average transmission delay per message, and Qit(fu) is average queuing delay per message when the average flow on link (/, /) is fn . While Pu and Tu are independent from the flow fu, the value of Qa (/,,) does depend on fu . If the queuing can be modeled as an MIM11 queue, then the Qa ( /„) can be expressed as Qa(fn)=-fTZT ( 2 - 3 ) where Ca is the capacity of the link. Later in [1], Bertsekas illustrated that in order to ensure stability, the bias d(0) should exceed a level that depends strongly on the traffic conditions. This level is proportional to the derivative d' along the ring. d(0)>^- (2.4) where fi = max d\\f) (2.5) R - max rt (2.6) From (2.2) and (2.3) we can see, the value of d' will be extremely high under heavy traffic load, when / —> C. This is because d\\f) = Q\\f) = -^—^ (2.7) 14 Therefore, in order to make the routing stable, a very large constant of d(0) is needed in the routing metric. In the early ARPANET, a substantial bias factor was added to the weight calculation. The equation 2.2 changes to the form of d(fll) = B + Pil+Til+Qil(fil) (2.8) where B is the large value of bias added into the weight calculation function. The purpose of adding a large bias into the weight calculation function is to damp the routing oscillation under heavy traffic load. But at the same time, the addition of this large bias made the routing less sensitive to the dynamic traffic load, and the routing algorithm performed close to minimal-hop routing. The detailed and completed analysis can be found in [1]. 2.2.2 The Dynamic Behavior Analysis Ramakrishnan and Rodrigues [6] used another approach to illustrate the routing oscillation problem of MDAR in their research. Let's consider an adaptive minimal delay network, where the weights are derived directly from the link delay. For the sake of simplicity, only the weight of one chosen link in the network is changing, while the weights of the other links are kept constant. It is also assumed that the traffic flows over the network are static. Figure 2.2 shows the dynamic behavior of a chosen link in such a network under relatively heavy traffic load. 15 Figure 2.2 Routing Oscillation in Minimal-Delay Adaptive Routing. In Figure 2.2, the horizontal axis denotes the utilization of the chosen link; the vertical axis denotes the weight assigned on this link; the curve increasing with link utilization indicates the delay of the link corresponding to the link utilization; the curve decreasing with link utilization shows the resulted link utilization corresponding to an assigned weight. Suppose the initial weight of the chosen link is 1.5. From the load curve it can be deduced that the link utilization resulted by this weight assignment is 0.75. Therefore, the delay of the link with such traffic load will be 4.3 from the delay curve. The M D A R will set the weight to 4.3 in the next update. From the load curve we can see that the updated weight of 4.3 will result in a link utilization of 0.15. As a consequence, the delay of the link will change to 1.2. Then, the algorithm will set the weight to 1.2 in the next update resulting in a link utilization of 0.8. After that, the 16 utilization of 0.8 will lead to a link delay of 5, which will cause the algorithm to set the weight to 5 in the next update. From then on, the system will enter a cycle where the link utilization will oscillate between 0.15 and 0.8, which means route flipping for many of the origin-destination pairs in the network. 2.3 Summary The previous analysis of the dynamics of M D A R shows that by deriving the weights directly from the delays of the links the adaptive routing algorithm may be unstable under heavy traffic load and will experience route flipping problem. The Bertsekas's analysis tells us that the reason for this instability is because the differential of the delay curve, d'(f), is too large under heavy traffic load, in other words the delay curve increases too dramatically. The similar conclusion can also be drawn from the dynamic behavior analysis. In the heavy load situation, the link utilization is high. This results in large value of link delay due to the queuing nature of the link. Consequently, a large value of weight is derived directly form the link delay, and most of the traffic through the link is shed. Therefore, the link utilization drops dramatically, and the delay of the link also reduces significantly. Then, a small value of weight is set according to the reduced link delay, and this causes the high link utilization again. Thus, the link falls into a circle, and the route flipping starts. 17 Chapter 3. Load-Sensitive Adaptive Routing (LSAR) In this chapter, a new routing algorithm is presented. Because in this algorithm the link weight is derived from the measured link utilization, which reflects the traffic load over the link, the routing algorithm is named Load-Sensitive Adaptive Routing (LSAR). Due to the extremely complex nature of the dynamics of packet switched data networks and the lack of an efficient mathematical tool to model such complex dynamic systems, it is difficult to build an accurate mathematical model. Therefore, the analysis in this chapter is more qualitative than quantitative. 3.1 Weight Mapping in LSAR An adaptive routing network can be looked upon as a feedback system, and the system block diagram of MDAR, which was implemented in the early ARPANET, can be drawn as shown in Figure 3.1. The input of this system is the changing traffic load, which changes the utilization of the links in the network. The routing algorithm changes the weights of the links according to the weight mapping between the link utilization and the weight. In MDAR, the weight is set proportional to the link delay, so the weight mapping curve has the shape of a queuing delay curve. The output of the weight mapping is the updated weights of the links, which become the input of the Shortest Path First (SPF) algorithm. The SPF algorithm calculates the shortest path for each origin destination pair in the network and updates the routing tables of the routers. The routers then reroute the traffic using the updated route tables, therefore the traffic load on each link of the 18 network changes because of the route update. The weight mapping, the SPF algorithm and the route update blocks form a feedback controller of the system. The feedback in the system is a negative feedback, because if the traffic load input increases, the weight mapping block will increase the link weight, and the increased weight will cause the traffic load over the link to decrease. Traffic Load Route Update Shortest Path First (SPF) A ; gorithm Link Link Utilization • 0.20.4 0.6 \" 0,8 Link\" UntilrBtiDn Weight Mapping Figure 3.1 The System Block Diagram of MDAR. We call an adaptive routing network a stable system, if given a static traffic load on the network, after some time the network converges to a steady state where the link utilizations in the network do not change, which means no routing oscillation occurs in the network. 3.1.1 Weight Mapping Function in MDAR The weight mapping function in MDAR can be expressed as 19 W=W0 +D = W0 + d(u) (3.1) where W is the output weight, W0 is a constant, and D is the link delay which is a function of link utilization u . Bertsekas gave the conclusion in [1] that the reason for the unstable oscillation of minimal-delay adaptive routing is that the value of the derivative d' is too high when the network is heavily loaded, in other words when u approaches 1. To put the same conclusion in the words of control theory, the reason for the instability of the system is because the gain of the feedback loop is too high when u —> 1, since W' = d' and W' represents the gain of the weight mapping block in the block diagram. The function d(u) is a nonlinear function, because of the queuing nature of link delay. The derivative d' is relatively small when the network is lightly loaded but increases dramatically when the load is heavy. In control theory, a small gain in the feedback loop usually means less sensitivity and more stability for the system; a large gain usually makes the system more sensitive and can lead the system to instability if the gain is too large. This matches the dynamic behavior of Minimal-Delay Adaptive Routing very well. When the network is lightly loaded, the routing is stable, but when it is heavily loaded, routing oscillation appears. 3.1.2 Weight Mapping Function in LSAR Given the above analysis, it is clear that the nonlinear weight mapping function in MDAR is the root of the routing oscillation problem. The nonlinear weight mapping function increases the gain in the feedback loop dramatically as the traffic load increases, and leads the system to instability. Therefore, a linear mapping function would be helpful to improve the stability of LSAR. The linear function means that the weight mapping block in the feedback loop has a constant gain. 20 If a link increases its weight and broadcasts this update to the whole network, the network responds to the increase by moving some of the routes and associated traffic off the link. The amount of traffic remaining on the link depends on the value of the reported weight relative to the surrounding link weights. In networks that are rich with alternate paths, on average, the normalized reported weight of 4 is big enough to shed all the traffic off a link [3]. Therefore, the maximal value of the weight mapping function in L S A R should not exceed the value of 4. Figure 3.2 shows a weight mapping function of L S A R , with maximal value of 4. The flat section of the mapping function from link utilization value 0 to 0.5 is called the non-adaptive area, within which the weight remains constant. The reason for having this non-adaptive area is that when the link is lightly utilized, the link performance in terms of delay and packet loss rate is good enough, so it is not necessary to change the weight. By doing so, we can also save routing overhead and router C P U consumption. Weight 5 4 3 2 1 0 0 0.2 0.4 0.6 0.8 1 Link utilization Figure 3.2 The Weight Mapping Function of L S A R . 21 The section after the non-adaptive area is a straight line increasing proportionally to the link utilization. The maximal value of the weight mapping function is usually set to be smaller than 4 because of the reason we just mentioned above. The bigger the value, the higher the constant gain of the weight mapping block is, and the more powerful the routing is when doing traffic balancing. But there is a trade off between the traffic balancing power and the stability of the routing algorithm. In the simulations in this thesis, the maximal weight is set to be 3. 3.2 Damping by Averaging Changing the nonlinear weight mapping function in the feedback loop does help improve the stability of the system, but it is not enough. In this section the dynamics of adaptive routing systems is analyzed by studying the dynamic behavior graphs. 3.2.1 The Dynamic Behavior Graph of Adaptive Routing For the sake of simplicity, let's consider an adaptive routing network where there is only one link changing its weight, while the rest of the links keep their weights constant. Let's also assume that the traffic flows over the network are static flows. Figure 3.3 shows the dynamic behavior of the weight-changing link in such a network. The horizontal axis in Figure 3.3 denotes the utilization of the link. The vertical axis denotes the normalized weight assigned on this link. The curve increasing with link utilization represents the weight mapping function, which can be written as w - f{u), where u is the link utilization and w is the recalculated weight based on the link utilization of u . The step-shaped decreasing curve represents the resulted link utilization corresponding to an assigned weight, and it can be written as 22 u = g(w). The shape of g(w) is determined by the discrete nature of network flows. The shape of f(u) does not affect our analysis, as long as it is a monotonically increasing function with d(0) > 0 . The point where f(u) and g(w) intersect is called the equilibrium point Pe. 0.2 0.4 0.6 0.8 1.0 Link utilization Figure 3.3 Dynamic Behavior Graph of a Weight-Changing Link in a MDAR Network. In Figure 3.3, the system starts with initial weight w0 - 2. From the load curve we can deduce that the link utilization resulted by this weight assignment ux = g(w0) is about 0.7. The routing algorithm calculates the weight of the link by checking the weight mapping curve, so w, = f(ux)-4.3. Then the link weight of 4.3 is updated, and the load over the link changes accordingly, u2 = g(w,) = 0.15 . As a consequence, the weight of the link changes again, 23 w2 = f(u2) -1.2. The routing algorithm sets the weight to 1.2 in the next update, and results the change of link utilization M 3 = g(w2) = 0.8 . Then the link utilization of 0.8 leads to a link weight update, vv3 = f(u3) = 5 . From then on, the system enters a cycle where the link utilization oscillates between 0.15 and 0.8, which means route flipping for many of the origin-destination pairs in the network. If a system changes its state and reaches the equilibrium point after some weight updates, it is called a stable system. For different network topologies and different traffic follows, the only shape of weight mapping curve that can guarantee the stability of the system is a flat straight line, which means the weight of the link remains constant and the routing is not adaptive at all. 3.2.2 The Effect of Adding Bias in MDAR i i i I I i > 0 0:2 0.4 0.6 0.8 1 Link Untilization Figure 3.4 The Effect of Adding Bias to the Weight Mapping Function. 24 In the M D A R algorithm of early A R P A N E T , the weight was updated based on the link delay, so the weight mapping curve had the same shape of a queuing delay. The routing is only stable when the link is lightly utilized, because when the link utilization is small the delay curve is approximately flat. One way to increase the stability of the routing algorithm under relatively heavy utilization, as suggested in [1], is to add a large value of bias to the weight mapping function. The effect of adding a bias can be shown in Figure 3.4. Figure 3.4 shows three normalized weight mapping curves with different biases, where 0, LSAR ' 0 6 L , . : : . . - . -0 51 1 1 -I ! H 1 50 60 70 80 SO 100 110 Trafic Loa