UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Load-sensitive adaptive routing (LSAR) for computer networks Wang, Hao 2003

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_2003-0320.pdf [ 2.44MB ]
Metadata
JSON: 831-1.0091004.json
JSON-LD: 831-1.0091004-ld.json
RDF/XML (Pretty): 831-1.0091004-rdf.xml
RDF/JSON: 831-1.0091004-rdf.json
Turtle: 831-1.0091004-turtle.txt
N-Triples: 831-1.0091004-rdf-ntriples.txt
Original Record: 831-1.0091004-source.json
Full Text
831-1.0091004-fulltext.txt
Citation
831-1.0091004.ris

Full Text

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 (LSAR) F O R COMPUTER  NETWORKS by  Hao Wang  B . E n g . , 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 E L E C T R I C A L 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  degree freely  at  this  the  available  copying  of  department publication  of  in  University  of  for reference  this or  thesis  thesis by  this  partial British  fulfilment Columbia,  and study.  for scholarly  his thesis  or  her  of  requirements  I agree  that  I further agree  purposes  may be  representatives.  for financial  the  gain  shall  It not  is  that  the  for  Library  permission  granted  by  understood be  allowed  of  LUc-trieM  The University of British Vancouver, Canada  Date  DE-6  (2/88)  Columbia  make  it  for extensive  the  without  &*«r***^ £*J> Insertft^.  advanced  shall  that  permission.  Department  an  head  of  my  copying  or  my written  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. T h e 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. T h e 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 S P F 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 o f view, and the analysis shows why M i n i m a l - D e l a y 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. 1.1  Introduction  1  Introduction to Internet Protocol (IP) and IP Routing  1  1.1.1  T h e O S I Reference M o d e l  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  Thesis Outline  10  1.3  Chapter 2.  A Review of Adaptive Routing  11  2.1  A Brief Historical Review of IP Routing  11  2.2  M i n i m a l - D e l a y Adaptive Routing  12  2.2.1  The Bertsekas's Analysis  12  2.2.2  T h e Dynamic Behavior Analysis  15  2.3  Summary  Chapter 3. 3.1  Load-Sensitive Adaptive Routing (LSAR) Weight Mapping in L S A R  17  18 18  3.1.1  Weight M a p p i n g 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 A d d i n g Bias in M D A R  24  3.2.3  Damping by Averaging in L S A R  25  3.3  T h e M i n i m a l Weight Update L i m i t  26  3.3.1  T w o Types of Equilibrium Points  26  3.3.2  The M i n i m a l Weight Update Limit  27  3.4  Summary  28  Simulation in ns2  30  T h e Simulation Software  30  Chapter 4. 4.1 4.1.1  Network Simulator 2 (nsl)  4.1.2  Routing in nsl  30 •  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  4.5  •  43  Summary  43  Conclusions and Future Work  45  5.1  Conclusions  45  5.2  Future Work  47  Chapter 5.  Bibliography  50  Appendix A Simulation Topologies  54  iv  A. 1  A.2  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  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 F o r Dynamic Traffic Loads  41  List of Figures Figure 1.1  O S I Reference M o d e l  1  Figure 1.2  Intradomain and Interdomain routing  5  Figure 2.1  A Simple R i n g Topology  13  Figure 2.2  Routing Oscillation in Minimal-Delay Adaptive Routing  16  Figure 3.1  T h e System B l o c k 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 L i n k in a M D A R Network  23  Figure 3.4  T h e Effect of A d d i n g Bias to the Weight Mapping Function  24  Figure 3.5  The T w o Types of Equilibrium Points in Adaptive Routing  26  Figure 3.6  T h e System B l o c k 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  T h e Dynamic Traffic L o a d Over L i n k l in an OSPF/IS-IS Network  39  Figure 4.8  The Dynamic Traffic L o a d Over L i n k 2 in an OSPF/IS-IS Network  39  Figure 4.9  The Dynamic Traffic L o a d Over L i n k l in a L S A R Network  42  Figure 4.10  T h e Dynamic Traffic L o a d Over L i n k 2 in a L S A R Network  42  vii  Acknowledgement I would like to express my sincerest gratitude to my thesis supervisor, Dr. M a b o R. Ito, for his continuous guidance and support throughout this thesis and my education at U B C . H i s 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, H a n W u , X i u l i u Huang, M u l o n g 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  1.1.1  Introduction to Internet Protocol (IP) and IP Routing  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 L a y e r 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 T C P / I P suite embraces many protocols, which continue to grow as new applications emerge. Some key IP protocols include Internet Protocol (IP), Transmission Control Protocol ( T C P ) , User Datagram Protocol ( U D P ) and Internet Control Message Protocol ( I C M P ) .  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 l e Transfer Protocol (FTP), World W i d e Web ( W W W ) and D o m a i n Name Service ( D N S ) .  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 ( O S P F ) [14], and the Border Gateway Protocol ( B G P ) [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. T h e different breeds of routing protocols have different capabilities related to both architectural design and embedded functionality.  •  Intradomain Versus Interdomain Routing  Intradomain Routing Interdomain Routing RIPvl RIP v2 IGRP BGP EIGRP OSPF 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  autonomous  referred to as a network domain, or sometimes called an  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 ( A S 1 , A S 2 , and A S 3 ) interconnected into a global routing system. A l s o 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 A S s , 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. T h e subject of this thesis is intradomain routing.  •  This  Distance-Vector Versus Link-State Protocols  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  RIPvl  Distance Vector  Hop count  Bellman-Ford  RIP v2  Distance Vector  H o p count  Bellman-Ford  IGRP  Distance Vector  Composite  Bellman-Ford  EIGRP  Distance Vector  Composite  Diffusing Update Algorithm  OSPF  L i n k State  Bandwidth-based cost  Shortest Path First  IS-IS  L i n k 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 ( L S A s ) within the network. The routers originate L S A s , and broadcast them throughout the network. E a c h 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  1.2.1  Motivation and Objective  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 = lxl0 /W 8  [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 O u t l i n e  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. T h e new routing algorithm measured the average delay of each link instead of estimation as the original  ll  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 r , which is a constant. The routing in this network is denoted as R (i = 1,..., N) , t  t  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  Given  a routing  R  t  , the flows  A Simple R i n g Topology.  on each  counterclockwise directions are denoted by  undirected link  / .  rco={ J  [r^+r^+.-.  1  f n-l \r +r +... t  The weight or the length of a link  °'  fj (i) +  and  i f  + rj,  °'  +  T i  (/)  (/, /)  M  —  }  x  clockwise  l  ~  j  if i> j  if  -  j  i<j  is given by an equation of the form  D =d(f ) u  where  f  u  is the flow  on link  (/, I)  (2.1)  u  during the preceding period and  d is a real valued,  continuously differentiable and monotonically increasing function of flow with d(0)  In M D A R ,  and  respectively and are given by  i f i  + r_,  in the  > 0 .  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(f )  = Pu+T +Q (J )  a  a  tt  (2.2)  tt  where P is the average processing plus propagation delay per message, T u  tt  transmission delay per message, and Q (f ) it  is the average  is average queuing delay per message when the  u  average flow on link (/, /) is f . n  While P and T u  u  are independent from the flow f , u  f . If the queuing can be modeled as an MIM11 u  a  a  queue, then the Q ( / „ ) can be expressed as  Qa(fn)=-fTZT  where C  the value of Q (/,,) does depend on a  ( 2  -  3 )  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)  fi = max d\f)  (2.5)  R - max r  (2.6)  where  t  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(f ) ll  = B + P +T +Q (f ) il  il  il  il  (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. F r o m 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. T h e M D A R will set the weight to 4.3 in the next update. F r o m the load curve we can see that the updated weight of 4.3 will result in a link utilization of 0.15. A s 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. F r o m 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 T h e 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. T h e 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.  T h e 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  Link Utilization •  Link  Route Update  Shortest Path First gorithm (SPF) A ;  0.20.4  06 .  "  08 ,  L n ik "U n r t l B it D in  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=W +D = W + d(u) 0  0  (3.1)  where W is the output weight, W is a constant, and D is the link delay which is a function of 0  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 o f 4 is big enough to shed all the traffic off a link [3]. Therefore, the maximal value o f 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. T h e 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. B y doing so, we can also save routing overhead and router C P U consumption.  Weight  5  4  3  2  1  0 0  0.2  Figure 3.2  0.4  0.6  0.8  1  Link utilization  T h e Weight Mapping Function of L S A R .  21  T h e 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 o f 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 o f the system, but it is not enough. In this section the dynamics o f 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.  T h e horizontal axis in Figure 3.3 denotes the utilization of the link. T h e 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  w - f{u),  where  u  is the link utilization and  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)  0.2  and g(w) intersect is called the equilibrium point P . e  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 w - 2. From the load curve we can deduce 0  that the link utilization resulted by this weight assignment u = g(w ) x  0  is about 0.7. The routing  algorithm calculates the weight of the link by checking the weight mapping curve, so w, = f(u )-4.3.  Then the link weight of 4.3 is updated, and the load over the link changes  x  accordingly, u = g(w,) = 0.15 . As a consequence, the weight of the link changes again, 2  23  w  2  = f(u )  -1.2.  2  T h e routing algorithm sets the weight to 1.2 in the next update, and results the  change of link utilization  update,  vv = f(u ) 3  3  = 5.  M = g(w ) 3  2  = 0.8 . Then the link utilization of 0.8 leads to a link weight  F r o m 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. F o r 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  0  i  0:2  i  0.4  I  I  0.6  0.8  i  1  >  Link Untilization  Figure 3.4  The Effect of A d d i n g Bias to the Weight M a p p i n g 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. T h e 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 < B < B < B . W e can see that by increasing the bias value, the curve is compressed along the 1  2  3  vertical direction, and the flat region of the curve is extended, therefore the stability of the routing under heavy utilization is improved. But the routing is stable only when the link utilization varies within the flat section of the weight mapping curve. Out of this region, the routing oscillates very easily. E v e n when the routing is stable, the performance of such routing algorithm is not much better than minimal hop routing, because the weight remains almost constant.  3.2.3  Damping by Averaging in LSAR  In L S A R , a different approach is used rather than simply adding a bias. B y observing the dynamic behavior of unstable adaptive routing algorithms, such as the one shown in Figure 3.3, it can be noticed that the unstable oscillating routing behavior is the typical behavior of a system that lacks enough damping. This suggests that to improve the stability of the routing algorithm, damping factors should be added into the system. T h e way damping factor is added into L S A R is by averaging, which is a very common method in control theory to introduce damping into a system. The L S A R routing algorithm still calculates the weight of the link using the weight mapping function, but instead of updating the link weight by this calculated value and broadcasting it to the whole network, the L S A R algorithm uses the average of this value and the previous updated link  25  weights. The number of previous weights used in averaging determines the effect of damping. T h e more previous weights used, the more damping the system has, and the more stable the system can be. But there is a trade off between the stability and the response speed of the system. In the simulations, 3 previous weights are used in the averaging process.  3.3  The M i n i m a l Weight Update L i m i t  B y adding damping factors into the feedback system, it is likely that the system will not fall into routing oscillations but gradually approaches the equilibrium point and remains there. But by taking a close look at the equilibrium point in the dynamic behavior graphs, it can be noticed that there are actually two types of equilibrium points.  3.3.1  Two Types of E q u i l i b r i u m Points  -mapping  (a) Unstable equilibrium point  Figure 3.5  (b) Stable equilibrium point  The T w o Types of Equilibrium Points in Adaptive Routing.  26  The two types of equilibrium points are shown in Figure 3.5. In Figure 3.5 (a), the equilibrium point is on a horizontal section o f the traffic load curve, and it is called an unstable equilibrium point. Suppose at time t , 0  the system is at the equilibrium point, where the link utilization u  After a period of time at time t , x  the link updates its weight according to u  e  results the link utilization changing to u". Then at t , 2  utilization changes to u'. A t t , 3  —u . e  and this update  the weight is updated again and the  the utilization changes back to u", and so on. T h e oscillation  starts.  The equilibrium point in Figure 3.5 (b) is on a vertical section of the traffic load curve, and it is stable, because once the system is within the area between  u'  and « " , it will move to the  equilibrium point after one link weight update and will remain there.  3.3.2  The Minimal Weight Update Limit  It is obvious that an adaptive routing system cannot be stable if the equilibrium point itself is not. But there is no way we can guarantee that the equilibrium point will always be on the vertical section of the traffic load curve, unless we make the weight mapping curve a flat straight line, which means no adaptive routing at all. In order to deal with the unstable equilibrium point problem, the minimal weight update limit is introduced into L S A R algorithm.  In L S A R , the link calculates its weight using the weight mapping curve and averages this value over previous updated weights. The result after averaging is the weight value to be update at the next update time. But i f the weight change between the current weight and the to-be-updated weight value is smaller than the minimal weight update limit, the weight value will not be changed at the update time, instead the link will keep its previous weight.  27  The step sizes of the traffic load curve depend on the traffic flow bandwidth consumption compared with the link capacity. G i v e n the fact that the bandwidth of the current ISP backbones is very high, it is not likely that there will be a single flow which consumes a large part of the bandwidth. Therefore the step sizes of the traffic load curve in Figure 3.5 (a) are not likely to be very large. Hence the routing oscillation around the unstable equilibrium point usually has small weight changes between each link updates, so by having a minimal weight update limit we can prevent oscillation around the unstable equilibrium point. It also helps to reduce the frequency of link weight updates in the network, therefore reduces routing overhead and saves the routers' C P U resource. The larger the minimal weight update limit, the more stable the system could be, but the less sensitive the routing algorithm is to traffic changes.  Considering the trade off and by  experimenting, the value used in simulations is set to be 20%  of previous update link weight. The  advantage of using a percentage instead of a fixed absolute value is that we can have a variable sensitivity system. W h e n the traffic load increases, the network is more likely to oscillate. The minimal update limit increases because the weight increases with the traffic load, so the routing decreases its sensitivity and therefore improves its stability.  3.4  Summary  Figure 3.6 shows the system block diagram of L S A R , which have new features such as changing the weight mapping function, adding damping factor and limiting the minimal weight update.  The nonlinear weight mapping function in M D A R yields too much gain under heavy traffic and leads the feedback system to instability. Therefore it is changed to a linear function in L S A R to provide constant gain. The mapping function also has a non-adaptive section to save routing overhead and router C P U resource.  Damping factor is added into L S A R by averaging the output of the weight mapping block. This  28  will prevent the system falling into oscillation and make it approaching the equilibrium point.  Traffic L o a d  L i n k Utilization •  Link  WiigM 5  Route Update  Shortest Path First (SPF)  A: gorithm 0  0.2  0.4  0.6  0.8  M i n i m a l Weight Update Limit  1 Link utilization  Weight Mapping  Averaging  Figure 3.6  The System B l o c k Diagram of L S A R .  Because of the existence of unstable equilibrium point, a minimal weight update limit block is also added into the system block diagram of L S A R .  29  Chapter 4. Simulation in ns2  4.1 The Simulation Software 4.1.1  Network Simulator 2 (ns2)  The software used for the simulations is Network Simulator 2 (nsT) [30] [31], which is a discrete event simulator targeted at networking research and is widely utilized among academic researchers. It is an object oriented open source simulator written in O T c l and C++. Because it is open source, new functions and new algorithms can be added by modifying the source files. Ns2 provides substantial support for simulations of T C P , U D P , IP routing, and multicast protocols over wired and wireless networks, and it is supported by several research organizations, including D A R P A .  4.1.2  Routing in ns2  There are two dynamic unicast routing protocols  in ns2, D V and L S . D V routing is the  implementation of Distributed Bellman-Ford (or Distance Vector) routing in ns2. The routing agent for D V routing is named Agent/rtProto/DV and is defined in file ns-2/tcl/rtglib/route-proto.tcl. T h e C++ files for D V routing are ns-2/rtProtoDV.{cc, h}. T h e D V routing agents send periodic route updates, and each agent also sends triggered updates whenever the routing table in the node changes. T h e routing table change occurs either due to changes in the topology, or because the routing agent at the node received a route update and recomputed and installed new routes.  30  L S routing in nsl implements an OSPF/IS-IS like fixed weight Link-State routing protocol. T h e routing algorithm is the same as in O S P F and IS-IS, but it is not implement in every detail of O S P F or  IS-IS.  T h e L S routing  agent  is  named  Agent/rtProto/LS,  and it  is  defined  in  file  ns-2/tcl/rtglib/ns-rtProtoLS.tcl. The C++ files for L S routing agent are ns-2/linkstate/hdr-ls.{cc, h), ns-2AinkstateAs.{cc, h} and ns-2Ainkstate/rtProtoLS.{cc, hj. T h e routing agents also send both periodic route updates and triggered updates.  The L S A R is implemented based on the embedded L S routing in ns2. A switch, L S A R _ S W I T C H , is added into L S routing. W h e n L S A R _ S W I T C H is set to O F F , the routing agents send out fixed weight periodic link-state advertisements  ( L S A s ) , just like normal OSPF/IS-IS routing. W h e n  L S A R _ S W I T C H is set to O N , the weight values in the L S A s sent out by routing agents are no longer fixed. T h e routing agents get the link utilization information from object QueueMonitor, calculate the weights using the weight mapping function, average this weight with previous updated weight values, check the results with the minimal weight update limit, and put the final weight updates in the L S A s .  Meaning  Default Value  The range of non-adaptive area  0.5  Parameter STATIC_AREA  on the weight mapping curve. MAX_WEIGHT  The maximal weight value.  3  NUMBER_OF_AVERAGE  The number of weights used in  4  averaging. MIN_CHANGE  The  minimal  weight  change  0.2  between updates. Table 4.1  The Parameters of L S A R .  There are some parameters for L S A R that can be adjusted, such as the range of non-adaptive area on the weight mapping curve, the maximal weight value, the number of weights used in averaging, and the minimal weight change limit. B y changing these parameters, the dynamic behavior of  31  L S A R can be adjusted to suit different network conditions.  The functions of these parameters have been discussed in the previous analysis, and the behavior of L S A R observed from experimental tests consists with the analysis. After considering the trade offs mentioned in the previous discussion and doing experiments, the default values of the parameters are set as shown in Table 4.1.  4.2  Network Topologies Generator  The topologies used in our simulation are randomly generated by G T - I T M Topology Generator software [32].  Topology Number  Number of Nodes  Number of Links  1  16  23  2  16  22  3  32  55  4  32  57  5  64  210  6  64  194  Table 4.2  Network Topologies Used in Static Traffic Simulation.  Six different random topologies of various sizes are used, as listed in Table 4.2. Based on these topologies, the performance of L S A R is tested for both static traffic load and dynamic traffic load.  32  4.3  Static Traffic Test  4.3.1  Traffic Generation  In static traffic simulation, the flow between each origin destination pair is implemented by a constant bit rate U D P flow. The rates of the traffic flows are determined using a method similar to the one used in [5]. T w o random number, O , x  network, and another random number C  (x  x  T h e traffic rate from origin node  y)  DE X  e [0,1]  [ 0 , 1 ] , are assigned to each node x  is assigned to each pair of nodes  to destination node  y  Where  R  (x  y)  is the traffic rate, and a  Different values of O  x  and D  x  x  y  (x,  y).  is calculated as  R , =aO D C , lx y)  in the  (4.1)  lx y)  is the traffic load factor used to adjust the traffic flows.  can make node  x  a more or less active sender or receiver, and  this gives us the ability to simulate the hot spots on the network.  Because we have control of the seeding of the random number generator, the traffic flows on the comparing L S A R and OSPF/IS-IS routing networks are exactly the same. T h e traffic flow patterns for a set of simulations performed on the same network topology are also the same, except the variation of the traffic load factor.  4.3.2  Simulation Results  For each random topology listed in Table 4.2, we ran a set of simulations for different traffic loads. The traffic flows are generated using equation (4.1). F o r each topology, by keeping the seed of the random number generator constant and changing only the value of the traffic load factor, the traffic loads generated for this topology vary from light to heavy, but they all have the same pattern. Both  33  OSPF/IS-IS and L S A R routing algorithms are tested, and the simulation results are shown from Figure 4.1 to Figure 4.6.  Figure 4.1  Simulation Result for Static traffic on Topology 1 (16 nodes, 23 links).  34  1.1.1  '100  0SPF/1SLSAR '  1.1.0  120  130 140 150; Traffic Load Factor (Kbit/sec)  160  170  180  Figure 4.2  Simulation Result for Static traffic on Topology 2 (16 nodes, 22 links).  Figure 4.3  Simulation Result for Static traffic on Topology 3 (32 nodes, 55 links).  OA - 50  60  70  80  90 100 110, Traffic Load Factor.(Kbit/sec)  '120  .130  140  150  Figure 4.4  Simulation Result for Static traffic on Topology 4 (32 nodes, 57 links).  Figure 4.5  Simulation Result for Static traffic on Topology 5 (64 nodes, 210 links).  1.1  |  1  1  —T~  1  - —  I ;>,  0 6  1  OSPF/IS-IS LSAR '  L,.::..-.-  0 51  1  50  60  1 70  -I 80  !  H  S O  100  1 110  T r a f f i c L o a < l F a c t o r . ( K b i t s /e c j  Figure 4.6  Simulation Result for Static traffic on Topology 6 (64 nodes, 194 links).  4.3.3  Discussion  Figure 4.1  to Figure 4.6  show that for fixed weight OSPF/IS-IS routing, the maximum link  utilization in the network increases linearly as the traffic load increases, which is as expected because the routing is fixed. W h e n the maximum link utilization reaches 1, it means the traffic load over a link in the network exceeds its capacity, congestion occurs.  W h e n L S A R is used instead of OSPF/IS-IS in the same networks with the same traffic flows, we can see that L S A R performs the same as OSPF/IS-IS with linearly increasing maximum link utilization when the traffic load is light. This is because of the non-adaptive section in the weight mapping curve. But when the traffic load becomes heavier, the adaptive routing begins to reroute traffic away from the heavily utilized link to alternative routes as the result of increased weights on  37  these links. N o continuous routing oscillation is observed in the simulations. T h e routings became steady after several update periods. Under the same traffic load, the maximum link utilization with L S A R after routing to become steady is significantly smaller than the one with fixed weight OSPF/IS-IS routing. T h e traffic load needed to make the maximum link utilization reach 1 is larger. This means that by using L S A R , the network can accommodate more traffic load before congestion occurs, in other words the throughput of the network increases. F o r the simulations we run, the average throughput increase is about 40% when L S A R is used.  4.4  Dynamic Traffic Test  Although  the  performance  of  LSAR  has  been  tested  under  static  traffic  and  significant  improvement on the throughput of the network has been observed, Further testing under dynamic traffic is still needed, because the traffic flows on real networks are dynamic rather than static.  4.4.1  The  Traffic Generation  traffic generator used in simulation is developed by Yuksel [10], which can dynamically  generate T C P and U D P flows simulating F T P , W W W , Telnet and S M T P applications. We use this traffic generator to randomly generate one hour of dynamic traffic load. Figure 4.7 and Figure 4.8 show the dynamic traffic load generated by this traffic generator over two links, l i n k l and link2, in an OSPF/IS-IS network for one-hour period. F r o m the graphs we can see that the traffic generated by the traffic generator is fairly dynamic. The dashed lines in these two graphs are the averaged link utilizations for the two links. The link in Figure 4.7 is heavily loaded with average link utilization of about 0.79. The traffic load on the link in Figure 4.8 is not so heavy, and average link utilization is about 0.55.  38  0.2 h  0.  Figure 4.7  500  1000  1.500 2000 Time (second)  2500  3000'  3500  The Dynamic Traffic Load Over Linkl in an OSPF/IS-IS Network.  4.4.2  Simulation Results  Both OSPF/IS-IS and L S A R routing are used in each contrast pair of simulations, with the same network topology and the same dynamic traffic load. The overall packet drop ratio is chosen as the metric to evaluate the routing performance. The performance of L S A R is tested over different topologies and under various traffic loads, both light and heavy. The detailed simulation results are listed in Table 4.3.  The more frequently the routers in the network send out link weight updates, the better the routing performs adapting to the traffic. But since it takes time for the network to distribute the updated weight to the whole network, usually in O S P F routing this update interval is set at least 5 seconds. The routing update period in the simulations is set to be 5 seconds.  The two links shown in Figure 4.9 and Figure 4.10 are the same links in Figure 4.7 and Figure 4.8 respectively. The network topologies and the dynamic traffic loads are the same too. T h e only difference is that the routing protocol in Figure 4.7 and Figure 4.8 is OSPF/IS-IS, while the routing protocol in Figure 4.9 and Figure 4.10 is L S A R .  40  Number of Nodes  Average Link Utilization OSPF/IS-IS  LSAR  Overall Packet Drop Ratio OSPF/IS-IS  LSAR  Improvement  0. 054298  0.054435  0. 000111  5. 86E-05  0. 47426  32  0.07113  0.070507  0. 000337  0.000122  0. 639418  32  0. 088704  0.088524  0. 000432  0.000203  0. 53026  4  32  0. 093402  0.093386  0. 000438  0.000192  0. 561724  5  32  0. 099716  0.100037  0. 000648  0. 000325  0. 49825  6  32  0. 108379  0. 10865  0. 000789  0. 000363  0. 540234  7  32  0. 113273  0. 113659  0. 00083  0.000334  0. 597993  8  32  0. 136472  0.138943  0. 001264  0. 000756  0.401697  9  32  0.153823  0. 15341  0.001281  0.000839  0. 345148  10  32  0.163726  0. 163858  0.001507  0. 000898  0. 403946  11  32  0. 204806  0. 204506  0. 002015  0. 001387  0. 311564  12  32  0.216938  0. 219393  0.002383  0.001622  0. 31922  13  32  0. 225076  0. 225901  0.002559  0. 001771  0. 307991  14  32  0. 258233  0. 260057  0.003726  0. 002921  0. 215959  15  32  0. 284058  0. 284595  0. 004182  0. 003036  0.274071  16  32  0. 29229  0. 294673  0. 004518  0. 003154  0. 30202  17  32  0. 093733  0. 096982  0. 001112  0. 000837  0.247852  18  32  0. 151593  0.159804  0. 001261  0. 000662  0.475171  1  32  2 3  19  32  0. 156436  0.160036  0. 001284  0.000994  0. 226406  20  32  0. 157047  0. 162772  0. 001397  0. 00099  0. 291569  21  32  0.182578  0. 203879  0. 001797  0. 001264  0. 296793  22  32  0. 195253  0. 222696  0. 001746  0. 001103  0. 368129  23  32  0. 199  0. 223487  0. 001807  0. 001156  0. 360062  24  32  0. 222689  0. 25005  0. 00239  0. 001545  0. 353609  25  64  0. 075069  0. 076092  0. 000141  0. 000125  0. 108318  26  64  0.090333  0. 091332  0.000394  0. 000408  -0. 03454  27  64  0.097635  0. 097687  7.32E-05  9. 96E-05  -0.35995  28  64  0. 13538  0. 136746  0. 000763  0. 000577  0.243867  29  64  0. 146428  0. 148532  0. 000848  0. 000557  0. 342847  30  64  0. 159578  0. 160812  0. 000919  0.000724  0.212261  31  64  0. 180999  0. 186352  0.001095  0. 000747  0. 317403  32  64  0. 18627  0. 188472  0.001163  0. 000952  0. 181157  33  64  0. 187757  0. 18891  0. 00048  0. 000309  0. 357162  34  64  0. 196355  0. 199459  0. 000479  0. 000277  0.421882  35  64  0. 21766  0. 215362  0.0006  0. 000302  0. 497091  36  64  0. 231209  0.234086  0. 000801  0. 00048  0. 400413  37  64  0. 240467  0.240527  0. 000916  0.000589  0. 35677  38  64  0. 250256  0. 251201  0. 001  0.000585  0. 41501  39  64  0. 259539  0. 263444  0. 001185  0. 000746  0.370282  40  64  0. 152648  0. 1523  0. 000464  0. 000487  -0. 04962  41  64  0. 246715  0. 25112  0. 001266  0. 000944  0. 253889  Table 4.3  Simulation Results For Dynamic Traffic Loads.  41  1500 2000 Time (second)  Figure 4.9  T h e Dynamic Traffic L o a d Over L i n k l in a L S A R Network.  1500. 2000 time, (second)  Figure  4.10  The Dynamic Traffic L o a d Over  Link2 in  a L S A R Network.  42  4.4.3  The  Discussion  simulation results in Table 4.3 show that in most cases, L S A R can improve the network  performance significantly. The average overall packet drop rate improvement we achieve from the simulations is 32.6%.  Only in some exceptional cases when the network is lightly loaded and the packet drop ratio is already very low, the packet drop ratio increases when L S A R is deployed, but the amount of increase is really small and the performance of the network is still very satisfying.  Figure 4.7 to Figure 4.10 give two examples on how L S A R affect the traffic load on the links in a network. The link shown in Figure 4.7 is very heavily loaded when OSPF/IS-IS routing is used, as we can see that the average utilization o f this link is about 0.79. W h i l e in Figure 4.9, when L S A R routing is used, the traffic load over the same link dropped significantly. The average link utilization in the latter case is only about 0.25. The reason for such a dramatic change is because of the link weight changes on this link and other links in the network, part of the traffic flows that used to go through this link in OSPF/IS-IS routing are shed to alternative routes.  But not every link in the network experiences the same dramatic change in traffic load. The average link utilization for the link in Figure 4.8, in which OSPF/IS-IS routing is used, is about 0.55, and in Figure 4.10, the average link utilization for the same link when L S A R is used is about 0.38.  4.5  Summary  The simulation of L S A R is discussed in this chapter. The simulation software used is ns2, which is an open source software designed for networking research. T h e topologies in the simulations are randomly generated by G T - L T M Topology Generator software. T h e performance of L S A R is tested  43  under both static and dynamic traffics. T h e static traffic test shows the throughput of the network improves significantly when L S A R is used. In our simulations, the network throughput increases by about 40% on average. T h e performance of L S A R is also tested under dynamic traffic flows. It is shown that L A S R is able to balance the traffic loads in the network by shedding some of the traffic flows away from heavily utilized links. In the dynamic traffic simulations, the average over all packet drop ratio decreases by 32.6%. During the simulations no continuous routing oscillation is observed.  44  Chapter 5. Conclusions and Future Work  5.1  Conclusions  The main contribution o f this thesis is that it presents an insight view of the dynamics o f adaptive routing by looking at adaptive routing networks  as feedback  systems. The cause of routing  oscillations in M D A R in the early A R P A N E T is investigated from control theory point of view, and it is shown that the reason for the instability of M D A R under heavy traffic load is because of the nonlinear weight mapping function and the lack of damping factor in the system. Therefore, a new routing algorithm called L o a d Sensitive Adaptive Routing ( L S A R ) is presented,  which has a  peicewise linear weight mapping function and is added with damping factor by averaging. Because of the existence of unstable equilibrium point in the system, a minimal weight update limit block is also added into the system block diagram of L S A R .  The  analysis of the dynamics of L S A R shows that by changing the nonlinear weight mapping  function to a linear function and by adding dumping factor and minimal weight update limit into the feedback system the stability of adaptive routing can be improved. B y setting the parameters of L S A R properly, the new routing algorithm could be stable while keep the ability of balancing the traffic loads on the network, and these characters of L S A R are confirmed in simulations latter in the thesis. The performance of L S A R is tested under both static and dynamic traffics in the simulations, and the network topologies used in simulations are random topologies generated by G T - I T M  [32]  software.  In static traffic simulations, the traffic flows are constant bit rate U D P flows randomly generated  45  between the nodes in the network. The purpose of the static traffic test is to show the traffic load balancing ability o f L S A R and also to test the stability o f L S A R . T h e simulation results show that LSAR  improves the throughput of the network significantly, compared with OSPF/IS-IS, by  shedding traffic away from heavily utilized links. It is also observed that there is no continuous routing oscillation happening in the simulations. The routing of the networks always become steady after several routing update intervals, even under heavy traffic loads.  To further test the performance of L S A R under more realistic network condition, simulations with dynamic traffic loads are performed. T h e dynamic traffic loads are generated using Yuksel's  [10]  traffic generator. T w o links are randomly picked, and the traffic loads over these two links with OSPF/IS-IS and L S A R routing algorithms respectively are compared to show the traffic load balancing effect of L S A R .  The dynamic traffic simulation results show that compared with  OSPF/IS-IS, L S A R reduces the overall packet drop ratio in the networks by 32.6% on average.  B y analysis and simulations, the thesis shows that by looking at an adaptive routing network as a feedback dynamic system and by applying techniques from control theory, adaptive routing can be made stable and yet still keeps its traffic load balancing feature at the same time. L S A R is not supposed to be a routing algorithm trying to achieve minimal end-to-end delay, because the weight mapping function of L S A R is based on link utilization instead of delay. Although L S A R does not give a routing solution that is optimal in delay, link utilization or network throughput, it provides traffic balancing ability that current dominant link-state routings, such as O S P F and IS-IS, do not have, and more importantly it is stable and does not have the routing oscillation problem as the previous adaptive routing did. Therefore, it can achieve better network performance.  It is possible that a particular traffic flow does not see better network performance with L S A R , in terms o f end-to-end delay or packet drop rate of this flow, especially i f the flow has a large bandwidth consumption and lasts only for a short period of time. Because the duration of such flow  46  is too short, the routing algorithm does not have enough time to adapt the routing decisions accordingly before it ends. In fact, L S A R is not designed to adapt to such short-lived flows. Because the trade off between sensitivity  and stability in the adaptive routing system,  it is  impossible to make the routing stable and sensitive enough to adapt to short-lived flows at the same time. Since stability is a much more important factor in affecting the network performance, and because of the fact that the dominant traffic on the Internet are long-lived flows [12], the L S A R is designed to achieve stability and to improve the overall network performance.  The implementation o f L S A R is relatively easy. It requires only minor modifications to the current link-state routing protocols. L S A R is also very flexible to deploy in the network. It is possible to have only part of the routers in the network running L S A R while the rest routers use conventional fixed weight O S P F or IS-IS. The parameters of L S A R can be adjusted to tune the dynamics of L S A R in order to suit a particular network topology or a particular traffic load pattern. It is also possible to configure the parameters of L S A R differently on different routers in the network.  In conclusion, L S A R is a very promising new routing algorithm for computer communication networks to improve network efficiency and performance.  5.2  Future Work  Despite the analysis and simulations being done in this thesis, there are still many further works could be done to further investigate on L S A R .  Because there is no mathematic model for the network dynamics available yet, the analysis of L S A R in this thesis is rather qualitative than quantitive. If a mathematic model for the dynamics of the network could be established in the future, more accurate quantitive analysis about L S A R would be possible to do.  47  Since we are looking at adaptive routing as feedback control system, new control algorithms could be tried on the system to evaluate their performance. Such new control algorithms may include: system identification, adaptive control and fuzzy logic.  Because of the existence of one routing update period delay in the feedback loop of the adaptive routing system, the dynamics of the system is susceptible to instability and response of the system can not be designed to be fast enough to cope with short-lived traffic flows. Feedforward technique could be used in order to improve the performance of L S A R . F r o m control theories and control engineering practices we know that feedforward technique usually can be used to improve the responsiveness of a system. The details of how to implement a feedforward mechanism in computer networks and how feedforward will affect the performance of L S A R need to be investigated in the future, and hopefully the investigation can bring some positive results.  The  application of L S A R is intended to be in the ISP backbones, but because of Intellectual  Property issue and other commercial reasons, most ISPs are not willing to give out the details of the topology of their backbones. Therefore, the simulations in this thesis are base on randomly generated network topologies using G T - I T M [32]. Although the author is very optimistic that the same or similar results can be achieved based on real network topologies, it has not been tested yet. Some possible sources of getting real backbone network topologies include industry university cooperation and research programs such as Rocketfuel in University of Washington [33].  Similar to the network topology problem, the traffic flows, both static and dynamic, are randomly generated instead of based on real traffic data. H o w to get real traffic data or at least generate more realistic traffic flows for simulations still needs to be further investigated.  The metric of measuring the performance of L S A R under dynamic traffic in this thesis is over-all  48  packet drop ratio in the network. Other metrics such as the average packets end-to-end delay could also be used in future simulations.  One thing that is not mentioned in the thesis is the router C P U horsepower consumption in L S A R routing. Because each time a link changes its weight, every router in the network will need to re-compute the routing table accordingly. H o w much C P U computation power will be consumed because of such routing table re-computation and how, if needed, to reduce the computation power requirement needs to be studied in later research.  49  Bibliography [1] Dimitri  P. Bertsekas,  "Dynamic Behavior of  Shortest Path Routing Algorithms for  Communication Networks", I E E E Transactions on Automatic Control, Vol. A C - 2 7 , pp. 60-74, 1982. [2]  Z . Wang and J . Crowcroft, "Analysis of Shortest-Path Routing Algorithms in a Dynamic Network Environment", A C M Computer Communication Review, V o l . 22, pp. 63-71, 1992.  [3]  Atul Khanna and John Zinky, "The Revised ARPANET Routing Metric", Proceedings o f A C M S I G C O M M , pp. 45-56, 1989.  [4]  Bernard Fortz and M i k k e l Thorup, "Internet Traffic Engineering by Optimizing OSPF Weights", Proceedings of the I N F O C O M 2000, pp. 519-528, 2000.  [5]  T. Y e , D . Harrison, B . M o , B . Sikdar, H . T. Kaur, S. Kalyanaraman, B . Szymanski and K . S. Vastola,  "Network Management and Control Using Collaborative On-line Simulation,"  Proceedings of I E E E ICC2001, Volume 1, 11-14, June 2001. [6]  K . G Ramakrishnan and Manoel A . Rodrigues,  "Optimal Routing in Shortest-Path Data  Networks", B e l l Labs Technical Journal, V o l . 6, N o . 1, pp. 117-138, January - June 2001. (online documentation) http://lucent.netlabs.net/minds/techjournal/jan-jun2001/pdf/paper08.pdf [7]  J . Harmatos, "A Heuristic Algorithm for Solving the Static Weight Optimization Problem in OSPF  Networks", Global Telecommunications  Conference  2001, I E E E ,  Volume  3, pp.  1605-1609, 2001. [8] M . Ericsson, M . G C . Resende and P. M . Pardalos, "A Genetic Algorithm for the Weight Setting Problem in OSPF Routing", Journal of Combinatorial Optimization, Volume 6, N o . 3, pp. 299-333, 2002. [9] Bernard Fortz and M i k k e l Thorup, "Optimizing OSPF/IS-IS Weights in a Changing World", I E E E Journal on Selected Areas in Communications, V o l . 20, N o . 4, pp. 756-767, 2002. [10] M . Yuksel, B . Sikdar, K . S. Vastola and B . Szymanski,  "Workload Generation for ns  50  Simulations of Wide Area Networks and the Internet", Proc. Communication Networks and Distributed Systems Modeling and Simulation Conference, pp. 93-98, San Diego, C A , U S A , 2000. [11] Martin Heusse and Y v o n Kermarrec, "Adaptive Routing and Load Balancing of Ephemeral Connections", 1st European Conference on Universal Multiservice Networks, pp. 100-108, 2000. [12] Anees Shaikh, Jennifer Rexford and K a n g G Shin, "Load-Sensitive Routing of Long-Lived IP Flows", Proc. of A C M S I G C O M M ( S I G C O M M '99), pp. 215-226, September 1999. [13] Cisco, "Configuring OSPF", Cisco IOS LP and IP Routing Configuration Guide, Release 12.1. (online documentation) http://www.cisco.com/univercd/cc/td/doc/product/software/ios 121/121 cgcr/ip_c/ipcprt2/ lcdos pf.htm [14] J . M o y , "OSPF Version 2", Internet Engineering Task Force, R F C 2328, A p r i l 1998. (online documentation) http://www.ietf.org/rfc/rfc2328.txt [15] R. Callon, "Use  of OSI IS-IS for  Routing in TCP/IP and  Dual Environments", Internet  Engineering Task Force, R F C 1195, December 1990. (online documentation) http: //w w w. ietf. org/rfc/rfcll95.txt [16] Cisco, " Configuring Integrated IS-IS", Cisco IOS LP and IP Routing Configuration Guide, Release 12.1. (online documentation) http://www.cisco.conVunivercd/cc/td/doc/product/software/iosl21/121cgcr/ip_c/ipcprt2/lcdisi s.htm [17] C . Hedrick, "Routing Information Protocol", Internet Engineering Task Force, R F C 1 0 5 8 , June 1988. (online documentation) http://w w w. ietf. org/rfc/rfc 105 8. txt [18] G M a l k i n , "RIP Version 2", Internet Engineering Task Force, R F C 1 7 2 3 , November  1994.  (online documentation)  51  http://www.ietf.org/rfc/rfcl723.txt [19] Cisco, "Interior Gateway Routing Protocol (IGRP)", Internetworking Technology Handbook, (online documentation) http://www.cisco.corn/univercd/cc/td7doc/cisintwk/ito_doc/igrp.htm [20] Cisco, "Enhanced Interior Gateway Routing Protocol (EIGRP)", Internetworking Technology Handbook, (online documentation) http://www.cisco.com/univercd/cc/td/doc/cisintwk/ito_doc/en_igrp.htm [21] Y. Rekhter, "A Border Gateway Protocol 4 (BGP-4)", Internet Engineering Task Force, R F C 1771, M a r c h 1995. (online documentation) http://www.ietf.org/rfc/rfc 1771 .txt [22] Graig Labovitz, G Robert Malan  and Farnam Jahanian, "Internet Routing Instability",  L E E E / A C M Transactions on Networking, V o l . 6, N o . 5, pp. 515-527, October 1998. [23] Graig Labovitz, G Robert Malan  and Farnam Jahanian, "Origins of Internet Routing  Instability", Proceedings of the Conference on Computer Communications ( L E E E Infocom), New York, pp. 218-226, M a r c h 1999. [24] David Anderson, Hari Balakrishnan, Frans Kaashoek and Robert Morris, "Resilient Overlay Networks", Proceedings of the 18th A C M Symposium on Operating Systems Principles (SOSP), October 2001. [25] John M . M c Q u i l l a n , Ira Richer and Eric C . Rosen, "The New Routing Algorithm for the ARPANET', L E E E Transactions on Communications, pp. 711-719, 1980. [26] Gianni D i Caro and Marco Dorigo, "Ant Colonies for Adaptive Routing in Packet-Switched Communications Networks", Proceedings of the-Fifth International Conference on Parallel Problem Solving F r o m Nature ( P P S N V ) , September 1998. [27] D . Awduche, J. M a l c o l m , J. Agogbua, M . O'Dell and J. M c M a n u s , "Requirements for Traffic Engineering Over MPLS", Internet Engineering Task Force, R F C 2 7 0 2 , September 1999. (online documentation) http ://w w w. ietf. org/rfcl rfc2702. txt  52  [28] E . Rosen, A . Viswanathan and R. Callon, "Multiprotocol Label Switching Architecture", Internet Engineering Task Force, R F C 3 0 3 1 , January 2001. (online documentation) http://www.ietf.org/rfc/rfc3031 .txt [29] Dimitri Bertsekas and Robert Gallager, Data Networks (Second Edition), Prentice-Hall, 1992. [30] Network Simulator 2 (ns2), http://www.isi.edu/nsnam/ns/. [31] The ns Manual (online documentation), http://www.isi.edu/nsnam/ns/doc/. [32] G T - I T M :  Georgia  Tech  Internetwork  Topology  Models,  http://www.cc.gatech.edu/fac/  Ellen.Zegura/gt-itm/gt-itm.tar.gz [33] Rocketfuel: A n ISP Topology Mapping  Engine,  http://www.cs.washington.edu/research/  networking/rocketfuel/  53  Appendix A Simulation Topologies  A.1 ns2 Codes for Random Topology Generation A.l.l  ns2 Code for Generating Topologies with 16 Nodes  # make s u r e t h a t g t - i t m and ns c o n v e r s i o n p r o g are i n the p a t h # u n t i l the t h e s e two f i l e s become p a r t of the r e l e a s e , # need t o source source  !!!XXX  we  them  topo-gen.tcl  source t o p o - v i e w . t c l # the f i l e s t h a t w i l l c o n t a i n the t o p o l o g y s c r i p t s and nam dump f i l e s set  t o p o f i l e mysimu-l-topo  set  topoext  tcl  set o u t f i l e mysimu-l-topo-view s e t o u t e x t nam set  topology_number 3  set h i e r _ f l a g 0 # c r e a t e 3 f l a t random t o p o l o g i e s o f 16 nodes, # p r o b a b i l i t y of  with connection  0.16  # f o r more h e l p on the t o p o l o g y command type " t o p o l o g y - h " for  { set  i 0 } { $ i < $topology_number  } { incr i } {  topology - o u t f i l e $ t o p o f i l e - $ i . $ t o p o e x t  -nodes 16 - c o n n e c t i o n _ p r o b  0.16  }  # after  creation,  # to be a mess,  v i e w the t o p o l o g y ,  h i t re-layout  the f i r s t  l a y o u t i n nam i s g o i n g  to get a r e a s o n a b l e  layout. 54  # f o r now, sgb2ns and sgb2hierns a r e not combined  ; hence pass a f l a g t o  view-topology # for  { s e t i 0 } { $ i < $topology_number } { i n c r i } { view-topology puts  $topofile-$i.$topoext $outfile-$i.$outext  "Do you want t o view another t o p l o g y  $hier_flag  (Y/N) ?! \ [ N \ ] "  gets s t d i n x if  ![regexp  { (y|Y|yes|Yes|YES)} $x] { A  break }  }  A.1.2  nsl Code for Generating Topologies with 32 Nodes  # make sure t h a t g t - i t m and ns c o n v e r s i o n prog a r e i n the p a t h  !!!XXX  # u n t i l the these two f i l e s become p a r t of the r e l e a s e , we # need t o source  them  source t o p o - g e n . t c l source t o p o - v i e w . t c l # the f i l e s  t h a t w i l l c o n t a i n the t o p o l o g y s c r i p t s and nam dump  set  topofile  set  topoext t c l  set o u t f i l e  files  mysimu-O-topo mysimu-O-topo-view  s e t o u t e x t nam set  topology_number 3  set h i e r _ f l a g 0 # create 3 f l a t # probability  random t o p o l o g i e s of 32 nodes, w i t h c o n n e c t i o n  of 0.1  # f o r more h e l p on the t o p o l o g y command type for  "topology -h"  { s e t i 0 } { $ i < $topology_number } { i n c r i } { t o p o l o g y - o u t f i l e $ t o p o f i l e - $ i . $ t o p o e x t -nodes 32 -connection_prob  0.1  }  55  # after # to  creation,  be a m e s s ,  # f o r now,  view  hit  sgb2ns  the  topology,  re-layout  to  get  and s g b 2 h i e r n s  the  first  layout  a reasonable  are not  i n nam i s  going  layout.  combined ; hence  pass  a flag  to  view-topology  # for  { set  i  0 }  { $i  view-topology  < $topology_number  $topofile-$i.$topoext  puts  "Do y o u want  gets  stdin  if  to  view  }  { incr  i  } {  $outfile-$i.$outext  another  toplogy  (Y/N)  ?!  $hier_flag  \[N\]"  x  ![regexp  { (y|Y|yes|Yes|YES)}  $x]  A  {  break  } }  A.1.3  ns2 Code for Generating Topologies with 64 Nodes  # make s u r e  that  # until  these  the  two  # need  to  source  topo-gen.tcl  source  topo-view.tcl  # the  source  g t - i t m and ns  files  that  files  become p a r t o f  will  contain  topofile  set  topoext  tcl  set  outfile  mysimu-2-topo-view  set  outext  set  topology_number 3  set  hier_flag 0  in  the  release,  path  !!!XXX  we  the  topology  scripts  a n d nam dump  files  mysimu-2-topo  nam  3 flat  # p r o b a b i l i t y of  random t o p o l o g i e s  on t h e  for  { $i  i  topology  0 }  of  64 n o d e s ,  with  connection  0.1  # f o r more h e l p { set  the  are  them  set  # create  conversion prog  -outfile  topology  command t y p e  < $topology_number  }  $topofile-$i.$topoext  "topology  { incr -nodes  i  -h"  } { 64  -connection_prob  0.1  }  56  # after  creation,  # t o be a mess,  view  the topology,  h i t re-layout  # f o r now, sgb2ns  the f i r s t  layout  i n nam i s  to get a reasonable  layout.  a n d sgb2hierns a r e n o t combined  ; hence  pass  going  a flag  view-topology # for  { set  i  0 } { $ i < $topology_number  view-topology  $topofile-$i.$topoext  puts  "Do y o u want  gets  stdin  if  ![regexp  to view  another  { (y|Y|yes|Yes|YES)} A  } }  A.2.1  toplogy  x  break  A.2  } { incr  Topology Samples  A Topology Sample with 16 Nodes  i  } {  $outfile-$i.$outext  $x]  {  ( Y / N ) ?!  $hier_flag  \[N\]"  to  A.2.3  A Topology Sample with 64 Nodes  59  

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0091004/manifest

Comment

Related Items