通信网理论基础（工程硕士）：Ch5 Routing in Data Networks

1、Broadband Communication NetworkCh5: 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 routes when congested. For those mentioned reasons, routing has to:Do with selecting routes to ach

4、ieve 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 mechanis

5、m 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 t

6、he 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 pra

7、ctice 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 o

8、r adaptive according to the route is fixed forever or change occasionally in response to congestion. 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? Discard

9、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 cycl

10、es.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 on

11、 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 optimal

12、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 Graphsgraph G = (N,A) is a

13、finite nonempty set N of nodes and a set of node pairs A called arcs (or links or edges) 10/1/202215Disallow the arc with both ends incident on the same node or multiple arcs between the same pair of nodes. 5.2 Walks and pathsA walk is a sequence of nodes (n1, n2, .,nk) in which each adjacent node p

14、air is an arc. A path is a walk with no repeated nodes. 10/1/2022165.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/2022175.2 CyclesA cycle is a walk (n1, n2,.,nk) with n1 = nk, k3, a

15、nd with no repeated nodes except n1 = nk 10/1/2022185.2 Acyclic graphs and treesAn acyclic graph is a graph 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

16、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 already 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 dele

17、ting nodes and arcs from a graph Note: arcs adjacent to a deleted node must also be deleted10/1/2022205.2 Spanning treesT = (N,A) is a spanning tree of G = (N,A) if T is a subgraph of G with N = N and T is a tree10/1/2022215.2 Spanning treesSpanning trees are useful for disseminating and collecting

18、control information in networks; they are sometimes useful for routing To disseminate data from Node n: Node 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

19、) wait to receive data on all but one adjacent arc, and then send received plus local data on remaining arc 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,

20、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 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.

21、T = (N,A) is a tree at each step of the algorithm since T is always connected, and each time we add an arc we also add a node Theorem: If G is a connected graph of n nodes, then 1) G contains at least n-1 arcs 2) G contains a spanning tree 3) If G contains exactly n-1 arcs, G is a spanning tree10/1/

22、2022245.2 Distributed algorithms to find spanning trees1)A fixed node sends a start message on each adjacent 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 imp

23、lementation of the general spanning tree algorithm It has several problems shared by many such algorithms: a) who chooses the starting node? b) When does the algorithm terminate? c) The resulting tree is somewhat random 10/1/202225Min weight spanning tree(MST)Given a graph with weights assigned to e

24、ach arc, find a spanning tree of minimum total weight (MST) Define a fragment“ to be a subtree of a MST Theorem: 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

25、 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 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

26、 of a = weight of b, then both are MSTs otherwise M could not have been an MST 10/1/202226Proof of theorem 10/1/202227MST algorithmsGeneric MST 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 a

27、n arbitrary single node as a fragment Add minimum weight outgoing edge Kruskal: Start with each node as a fragment; Add the minimum weight outgoing edge, minimized over all fragments10/1/202228MST constructions Graph with arc weights as indicated10/1/202229Successive iterations with the starting fra

28、gment consists of the single node S. The fragment extends by adding a minimum weight outgoing arc. Prim-Dijkstra algorithm. MST constructions Graph with arc weights as indicated10/1/202230The algorithm starts with all nodes as fragments. At each iteration, we add an arc that has minimum weight out o

29、f all arcs that are outgoing from one of the fragments. Kruskal algorithmsPrim-Dijkstra Algorithm10/1/202231Kruskal 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

30、 that spanning tree does 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/202232Directed graphs (digraphs)A directed graph (digraph) G= (N,A) is a fini

31、te nonempty set 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) Fo

32、r simplicity we will use bi-directional links of equal costs in our examples 10/1/202233Bellman-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. Le

33、t dij= if (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) 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/202234Bellman-Ford algorithm10/1/202235Shortest path using at mo

34、st 1 ARCShortest path using at most 2 ARCBellman-Ford algorithmThe effect of negative length cycles10/1/202236Shortest path using at most 3 ARCFinal tree of shortest pathDistributed Bellman FordLink costs may change over time Changes in traffic conditions Link failures MobilityEach node maintains it

35、s 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 using the update equation Each node maintains the values of dij to its n

36、eighbors, 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 steps10/1/202237Slow reaction to link failuresStart with D3=1 and D2=100 Af

37、ter 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 2 will update: D2 = d23+D3 = 4 It will take nearly 100 iterations before node

38、 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 prevent loops10/1/202238Dijkstras algorithmThe detail algorithm is shown as 1

39、0/1/202239Dijkstras 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

40、path to the k+1st 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 dista

41、nce to the source 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/202240Dijkstras algo

42、rithm10/1/202241Dijkstras algorithm implementationCentralized 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

43、shortest paths to each other node Open Shortest Path First (OSPF) protocol used in the internet10/1/202242Example using the Bellman-Ford and Dijkstra algorithmUsing the Bellman-Ford 10/1/202243Example using the Bellman-Ford and Dijkstra algorithmUsing the Dijkstra10/1/202244The floyd-warshall algori

44、thmAiming to solve All-Pairs Shortest Path ProblemSuppose we are given a directed graph G=(V,E) and a weight function w: E-R.We assume that G does not contain cycles of weight 0 or less. The All-Pairs Shortest Path Problem asks to find the length of the shortest path between any pair of vertices in

45、G. 10/1/202245The floyd-warshall algorithmIf the weight function is nonnegative for all edges, then we can use Dijkstras single source shortest path algorithm for all vertices to solve the problem. For arbitrary weight functions, we can use the Bellman-Ford algorithm applied to all vertices. 10/1/20

46、2246The floyd-warshall algorithmRepresentation of the InputWe assume that the input is represented by a weight matrix W= (wij)i,j in E that is defined by wij= 0 if i=jwij= w(i,j) if ij and (i,j) in Ewij= if ij and (i,j) not in EFormat of the OutputIf the graph has n vertices, we return a distance ma

47、trix (dij), where dij the length of the path from i to j. 10/1/202247The floyd-warshall algorithmIntermediate VerticesWithout loss of generality, we will assume that V=1,2,n, i.e., that the vertices of the graph are numbered from 1 to n. Given a path p=(v1, v2, vm) in the graph, we will call the ver

48、tices vk with index k in 2,m-1 the intermediate vertices of p.10/1/202248The floyd-warshall algorithmThe key to the Floyd-Warshall algorithm is the following definition: Let dij(k) denote the length of the shortest path from i to j such that all intermediate vertices are contained in the set 1,k. Co

49、nsider a shortest path p from i to j such that the intermediate vertices are from the set 1,k. If the vertex k is not an intermediate vertex on p, then dij(k) = dij(k-1) If the vertex k is an intermediate vertex on p, then dij(k) = dik(k-1) + dkj(k-1)Therefore, dij(k) = mindij(k-1) , dik(k-1) + dkj(

50、k-1)10/1/202249The floyd-warshall algorithm- ExampleConsider Vertex 3: Nothing changes.Consider Vertex 2: D(1,3) = D(1,2) + D(2,3)Consider Vertex 1: D(3,2) = D(3,1) + D(1,2)Original weights.The floyd-warshall algorithmLooking at this example, we can come up with the following algorithm:Let D store t

51、he matrix with the initial graph edge information initially, and update D with the calculated shortest paths.For k=1 to n For i=1 to n For j=1 to nDi,j = min(Di,j,Di,k+Dk,j)The final D matrix will store all the shortest paths.The floyd-warshall Path ReconstructionThe path matrix will store the last vertex visited on the path from i to j.So pathij = k means that in the shortest path from vertex i to vertex j, the LAST vertex on that path before you get to vert