1、Broadband Communication NetworkCh4: Routing in Data Networks10/1/20221Contents 10/1/20222Contents (cont.)10/1/20223Must choose routes for various origin destination pairs (O/D pairs) or for various sessions Datagram routing: route chosen on a packet by packet basis Using datagram routing is an easy

2、way to split paths Virtual circuit routing: route chosen a session by session basis Static routing: route chosen in a prearranged way based on O/D pairs 5.1.1 Routing10/1/20225.1.1 Complexity analysis of routingRouting requires coordination among all the nodes of the subnet rather than just a pair o

3、f modules;Routing system must cope with link and node failures, if so, then redirect the traffic and update the information databases;Routing must achieve high performance, for this, it must modify the routs when congested. For those mentioned reasons, routing has to do:Do with selecting routes to a

4、chieve high performance;Broadcast routing-related information to all network nodes.10/1/202255.1.1 Performance measures of RoutingMeasurements: Throughput (quantity of service) and Average delay (quality of service);Routing interacts with flow control in determining these measures by feedback mechan

5、ism shown here:10/1/202265.1.1 Routing Vs. Flow controlThroughput Vs. DelayIf offered load is low and moderate, routing is easy; (5;5)When load increasing, routing is getting important;(10; 1010;15)Static routing is not desirable ;The maximum total throughput a network can accommodate is depended on

6、 the routing scheme;(maximum traffic-minimum cut theory?)Datagam routing is a natural way to split the traffic How? 10/1/2022710105.1.1 Routing Vs. Flow controlThroughput Vs. Delay10/1/20228Delay-throughput operating curves for good and bad routing5.1.2 overview of routing in WAN To survey current p

7、ractice in WAN; to introduce classification of different schemes, to provide a context for the analysis.Routing schemes can be divided into centralized and distributed according to where the route choices are made at a central node or among network nodes. Routing schemes can also divided into static

8、 or adaptive according to the route is fixed forever or change occasionally in response to congestiong. 10/1/20229Route a packet from a source to all nodes in the network Possible solutions: Flooding: Each node sends packet on all outgoing links. How to limit the number of packet transmission? Disca

9、rd packets received a second time, how? 5.1.2 Broadcast Routing10/1/20225.1.2 Broadcast RoutingPossible solutions: Spanning Tree Routing: Send packet along a tree that includes all of the nodes in the network.A spanning tree is a connected subgraph of the network that includes all nodes and has no c

10、ycles.Broadcasting on a spanning tree is more communication-efficient than flooding. The price of this saving is the need to maintain and update the spanning tree in the face of topological changes. 10/1/2022115.1.2 Shortest Path routingEach link has a cost that reflects The length of the link Delay

11、 on the link Congestion $ cost Cost may change with time The length of the route is the sum of the costs along the route The shortest path is the path with minimum length Shortest Path algorithms Bellman-Ford: centralized and distributed versions Dijkstras algorithm Many others10/1/2022125.1.2 optim

12、al routing and hot potato routing 10/1/2022135.2 network algorithms and shortest path routing Routing methods involve the use of a number of simple graph theoretic problems such as shortest path problems.Start by introducing some basic graph-theoretic notions. 10/1/2022145.2 GraphsA graph G = (N,A)

13、is a finite nonempty set of nodes and a set of node pairs A called arcs (or links or edges) 10/1/2022155.2 Walks and pathsA walk is a sequence of nodes (n1, n2, .,nk) in which each adjacent node pair is an arc. A path is a walk with no repeated nodes. 10/1/2022165.2 CyclesA cycle is a walk (n1, n2,.

14、,nk) with n1 = nk, k3, and with no repeated nodes except n1 = nk 10/1/2022175.2 Connected graphA graph is connected if a path exists between each pair of nodes.An unconnected graph can be separated into two or more connected components. 10/1/2022185.2 Acyclic graphs and treesAn acyclic graph is a gr

15、aph with no cycles. A tree is an acyclic connected graph.The number of arcs in a tree is always one less than the number of nodes Proof: start with arbitrary node and each time you add an arc you add a node = N nodes and N-1 links. If you add an arc without adding a node, the arc must go to a node a

16、lready in the tree and hence form a cycle 10/1/2022195.2 SubgraphsG = (N,A) is a subgraph of G = (N,A) if 1) G is a graph 2) N is a subset of N 3) A is a subset of A One obtains a subgraph by deleting nodes and arcs from a graph Note: arcs adjacent to a deleted node must also be deleted10/1/2022205.

17、2 Spanning treesT = (N,A) is a spanning tree of G = (N,A) if T is a subgraph of Gwith N = N and T is a tree10/1/2022215.2 Spanning treesSpanning trees are useful for disseminating and collecting control information in networks; they are sometimes useful for routing To disseminate data from Node n: N

18、ode n broadcasts data on all adjacent tree arcs Other nodes relay data on other adjacent tree arcs To collect data at node n: All leaves of tree (other than n) send data Other nodes (other than n) wait to receive data on all but one adjacent arc, and then send received plus local data on remaining a

19、rc 10/1/2022225.2 General construction of a spanning treeAlgorithm to construct a spanning tree for a connected graph G= (N,A): 1) Select any node n in N; N = n; A = 2) If N = N, then stop (T=(N,A) is a spanning tree) 3) Choose (i,j) A, i N, j N N := Nj; A := A(i,j); go to step 2 Connectedness of G

20、assures that an arc can be chosen in step 3 as long as N N Is spanning tree unique?10/1/2022235.2 Spanning tree algorithmThe algorithm never forms a cycle, since each new arc goes to a new node. T = (N,A) is a tree at each step of the algorithm since T is always connected, and each time we add an ar

21、c we also add a node Theorem: If G is a connected graph of n nodes, then 1) G contains atleastn-1 arcs 2) G contains a spanning tree 3) If G contains exactly n-1 arcs, G is a spanning tree10/1/2022245.2 Distributed algorithms to find spanning trees1)A fixed node sends a start message on each adjacen

22、t arc of the graph 2) Each other node marks the first arc on which a start message was received as a spanning tree arc and then sends a start message on each other arc This is a distributed implementation of the general spanning tree algorithm It has several problems shared by many such algorithms:

23、a) who chooses the starting node? b) When does the algorithm terminate? c) The resulting tree is somewhat random 10/1/202225Min weight spanning treeGiven a graph with weights assigned to each arc, find a spanning tree of minimum total weight (MST) Define a fragment“ to be a subtree of a MST Theorem:

24、 Given a fragment F of an MST, Let a(i,j) be a minimum weight out going arc from F, where j is not in F. Then, F extended by arc a (i,j)& node j is a fragment. Proof: Let M be the MST that does not include a(i,j). Since a(i,j) is not part of M,then adding a (i,j) to M must cause a cycle. There must

25、be some link in the cycle b a which is outgoing from F. Deleting b and adding a creates a new spanning tree. Since weight of b cannot be less then weight of a , M must be a MST. If weight of a = weight of b, then both are MSTs otherwise M could not have been an MST 10/1/202226MST algorithmsGeneric M

26、ST algorithm steps: Given a collection of subtrees of an MST (called fragments) add a minimum weight outgoing edge to some fragment Prim-Dijkstra: Start with an arbitrary single node as a fragment Add minimum weight outgoing edge Kruskal: Start with each node as a fragment; Add the minimum weight ou

27、tgoing edge, minimized over all fragments10/1/202227Prim-Dijkstra Algorithm10/1/202228Kruskal AlgorithmSuppose the arcs of weight 1 and 3 are a fragment Consider any spanning tree using those arcs and the arc of weight 4, say, which is an outgoing arc from the fragment. Suppose that spanning tree do

28、es not use the arc of weight 2. Removing the arc of weight 4 and adding the arc of weight 2 yields another tree of smaller weight. Thus an outgoing arc of min weight from fragment must be in MST. 10/1/2022295.1.2 Directed graphs (digraphs)A directed graph (digraph) G= (N,A) is a finite nonempty set

29、of nodes N and a set of ordered node pairs A called directed arcs. Directed walk: (4,2,1,4,3,2) Directed path: (4,2,1) Directed cycle: (4,2,1,4) Data networks are best represented with digraphs, although typically links tend to be bi-directional (cost may differ in each direction) For simplicity we

30、will use bi-directional links of equal costs in our examples 10/1/2022305.1.2 Bellman-Ford algorithmFinds the shortest paths, from a given source node, say node 1, to all other nodes. General idea: First find the shortest single arc path, Then the shortest path of at most two arcs, etc. Let dij= if

31、(i,j) is not an arc. Let Di(h) be the shortest distance from 1 to i using at most h arcs. Di(1) = d1i ; i1 D1(1) = 0 Di(h+1) = min j Dj(h) + dji ;i1 D1(h+1) = 0 If all weights are positive, algorithm terminates in N-1 steps. 10/1/2022315.1.2 Distributed Bellman FordLink costs may change over time Ch

32、anges in traffic conditions Link failures MobilityEach node maintains its own routing table Need to update table regularly to reflect changes in networkLet Di be the shortest distance from node i to the destination Di = min j Dj + dij: update equationEach node (i) regularly updates the values of Di

33、using the update equation Each node maintains the values of dij to its neighbors, as well as values of Dj received from its neighbors Uses those to compute Di and send new value of Di to its neighbors If no changes occur in the network, algorithm will converge to shortest paths in no more than N ste

34、ps10/1/2022325.1.2 Slow reaction to link failuresStart with D3=1 and D2=100 After one iteration node 2 receives D3=1 and D2 = min 1+1, 100 = 2In practice, link lengths occasionally change Suppose link between 3 and 1fails (I.e., d31=infinity) Node 3 will update D3= d32 + D2 = 3 In the next step node

35、 2 will update: D2 = d23+D3 = 4 It will take nearly 100 iterations before node 2 converges on the correct route to node 1Possible solutions: Propagate route information as well Wait before rerouting along a path with increasing costNode next to failed link should announce D=infinity for some time to

36、 prevent loops10/1/202233InstabilityAs routes change due to traffic conditions, they affect the Loadings on the links, hence routes may oscillate10/1/202234InstabilityHaving a bias independent of flow in the arc distances helps to prevent this problem.Asynchronous updates also helps.10/1/202235Dijks

37、tras algorithmFind the shortest path from a given source node to all other nodes Requires non-negative arc weightsAlgorithm works in stages: Stage k: the k closest nodes to the source have been found Stage k+1: Given k closest nodes to the source node, find k+1st.Key observation: the path to the k+1

38、st closest nodes includes only nodes from among the k closest nodesLet M be the set of nodes already incorporated by the algorithm Start with Dn = dsn for all n (Dn = shortest path distance from node n to the source node Repeat until M=NFind node wM which has the next least cost distance to the sour

39、ce node Add w to MUpdate distances: Dn = min Dn, Dw + dwn (for all nodes n M) Notice that the update of Dn need only be done for nodes not already in M and that the update only requires the computation of a new distance by going through the newly added node w.10/1/202236Dijkstras algorithm implement

40、ationCentralized version: Single node gets topology information and computes the routes Routes can then be broadcast to the rest of the networkDistributed version: each node i broadcasts dij all j to all nodes of the network; all nodes can then calculate shortest paths to each other node Open Shorte

41、st Path First (OSPF) protocol used in the internet10/1/202237Routing in the InternetAutonomous systems (AS) Internet is divided into ASs each under the control of a single authorityRouting protocol can be classified in two categories Interior protocols - operate within an AS Exterior protocols - ope

42、rate between ASsInterior protocols Typically use shortest path algorithmsDistance vector - based on distributed Bellman-ford link state protocols - Based on “distributed” Dijkstras10/1/202238Distance vector protocolsBased on distributed Bellman-Ford Nodes exchange routing table information with thei

43、r neighborsExamples: Routing information protocols (RIP)Metric used is hop-count (dij=1)Routing information exchanged every 30 seconds Interior Gateway Routing Protocol (IGRP)CISCO proprietaryMetric takes load into accountDij 1/() (estimate delay through link)Update every 90 secondsMulti-path routin

44、g capability10/1/202239Link State ProtocolsBased on Dijkstras Shortest path algorithm Avoids loops Routers monitor the state of their outgoing links Routers broadcast the state of their links within the AS Every node knows the status of all links and can calculate all routes using dijkstras algorith

45、mNonetheless, nodes only send packet to the next node along the route with the packets destination address. The next node will look-up the address in the routing tableExample: Open Shortest Path First (OSPF) commonly used in the internetLink State protocols typically generate less “control” traffic

46、than Distance-vector10/1/202240Inter-Domain routingUsed to route packets across different ASsOptions: Static routing - manually configured routes Distance-vector routingExterior Gateway Protocol (EGP)Border Gateway Protocol (BGP)Issues What cost “metric” to use for Distance-Vector routingPolicy issu

47、es: Network provider A may not want Bs packets routed through its network or two network providers may have an agreementCost issues: Network providers may charge each other for dlivery of packets10/1/202241Bridges, Routers and GatewaysA Bridge is used to connect multiple LAN segments Layer 2 routing

48、 (Ethernet) Does not know IP address Varying levels of sophistication Simple bridges just forward packetssmart bridges start looking like routersA Router is used to route connect between different networks using network layer address Within or between Autonomous Systems Using same protocol (e.g., IP

49、, ATM)A Gateway connects between networks using different protocols Protocol conversion Address resolutionThese definitions are often mixed and seem to evolve!10/1/202242Bridges, routers and gateways10/1/202243View routing as a “global” optimization problem Assumptions: The cost of using a link is a function of the flow on that link The total network cost is the sum of the link costs The required traffic rate between each source-destination pair is known