Internet Routing Protocols and Architectures

15. Routing & Routing Algorithms Distance vector routing (Bellman-Ford) Link-state routing (Dijkstra) Hierarchical routing Roch Guerin (with adaptations from Jon Turner and John DeHart, and material from Kurose and Ross)

Routing vs Forwarding Routing automates the process of building forwarding tables Learns of reachable destinations Adapts to changes (destinations & topology) Computes best choices (next hop) for each route routing algorithm local forwarding table prefix out/nh 3/2.3.4.5 2/6.5.4.3 2/6.5.4.5 1.2.0.0/16 1.2.3.0/24 3.2.1.0/24 4.0.0.0/8 1/4.3.2.1 address in arriving packet s header Involves Communications with neighbors (routing protocols) Best paths computations ( shortest paths) 1 1.2.3.6 2 3 2

Design Constraints A single solution for the entire Internet is unlikely to work Not scalable Sheer size of global state Noise level associated with changes Not feasible Administrative and competitive limitations Not suitable Differences in selection criteria (different definitions of best path) Basic design approach: A two-level hierarchy Intra-domain and inter-domain protocols Ensures scalability Gateways connect domains together for an end-to-end solution Key features Fine-grain local information, coarse-grain remote information Optimize local resources, ensure global connectivity Control what information crosses domain boundaries 3

The Internet Abstraction The Internet topology A federation of inter- connected domains, i.e., Autonomous Systems (AS) Each domain identified by a number Domains have their own internal rules Domains collaborate to offer end-to-end connectivity AS 376 AS 441 AS 2 AS 168 AS 524 AS 3 AS 1 A multi-level hierarchy Big domains at the top Tier 1 Internet Service Providers (ISPs) provide global connectivity (full mesh) Smaller domains offer local connectivity and connect to tier 1 for global connectivity AS 321 AS 123 AS 121 AS 3411 4

Routing Protocols A two-level hierarchy for routing protocols Interior Gateway Protocols (IGP) control routing within an AS/domain Exterior Gateway Protocols (EGP) control routing betweenAS s AS 376 AS 441 AS 2 AS 168 Different goals and constraints for each family of protocols IGP: Ability to fine tune internal operation and shielding from outside noise EGP: Scalability and ability to accommodate a broad range of administrative policies AS 524 AS 3 AS 1 AS 321 AS 123 AS 121 AS 3411 5

Interior Gateway Protocols Routing protocols follow the two-level hierarchy of the Internet Interior Gateway Protocols (IGPs) control routing within an AS/domain Exterior Gateway Protocol(s) (EGP) control routing between AS s AS 376 AS 441 AS 2 AS 168 Different goals and constraints for each family of protocols IGP: Ability to fine tune internal operation and shielding from outside noise EGP: Scalability and ability accommodate a broad range of administrative policies AS 524 AS 3 AS 1 AS 321 AS 123 AS 121 AS 3411 6

Graph Abstraction 5 3 v w 1 2 u z 2 1 3 v w 2 1 x y 1 u z 5 3 v w x y 1 T2 2 T1 u z 3 2 1 Graph: G = (N,E) N = set of routers = { u, v, w, x, y, z } T = set of transit networks = { T1,T2 } more compact E = set of links (more accurately, adjacencies ) ={ (u,v), (u,x), (u,w), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } edges have costs costs may be uniform (hop), proportional to distance, inversely related to link capacity, or 0 (outgoing transit network edge), etc. path cost is (usually) sum of link costs or some variations thereof 1 2 x y 1 7

IGP Design Goals Design parameters 1. Network resources (bandwidth) 2. Router resources Memory (size of routing table and supporting data structures) Communication (number and frequency of control messages) Processing (handling messages & computing forwarding decisions) Design goals Correctness Avoid black holes (unable to reach reachable destination) Prevent or recover from loops (inconsistencies across routers) Stability Short reaction time to changes, but robustness to frequent changes Efficiency Best possible paths (according to some metric) 8

General Design Choices How are routes learned and forwarding decisions computed? Centralized vs. distributed - Centralized is simpler but may not scale and more prone to failure Not just server failure, but more importantly failure to learn about changes - Distributed requires collaboration between routers and has more complex transient behavior (not everyone decides or knows the same thing at the same time) More complex ways for things to break, but more options to fix broken things - - Assuming a distributed solution: Who computes what and how? - Distance vector protocols Everyone computes partial results and exchange them to obtain a full answer Efficiency and scalability benefits, but dependencies on other lengthens reactions - Link state protocols - Everyone individually computes the full answer - Greater overhead, but inherent parallelism of computation yields faster reactions What is a good path? What metrics to optimize (hop count, bandwidth, delay, etc.)? Static vs. dynamic metrics? 9

IGP Summary Main responsibilities 1) Discover reachable destinations 2) Determine best way to get to reachable destinations shortest path computation 3) Detect changes to 1) and 2) and update local state Changes to reachability affect best matches for packets Changes to network topology affect where packets are forwarded, and can affect reachability as well IGP protocols differ primarily in the type of shortest path computations they perform Distance vector (distribute network information and shortest path computations) Routing Information Protocol V2 (RIP2) Obsolete Cisco s Enhanced Interior Gateway Router Protocol (EIGRP) Link state (distribute network information, perform parallel centralized shortest path computations) Open Shortest Path First (OSPF) Intermediate System Intermediate System (IS-IS) 10

Distance Vector Protocols Iterative procedure to build and update routing tables Neighbors exchange what they can reach and at what cost Progressive discovery of reachable destinations Shortest (lowest cost) path computation based on a distributed (distance vector) computation model Pros (and cons) of distributed computations Routers only store routes and associated costs Routers benefit from each others work (computations) Routers are only notified of (remote) changes that affect them But routing convergence can be slow Serialization of notification and computations Inconsistencies in knowledge and, therefore, decisions can result in not so transient routing loops or black-holes 11

Distance Vector Algorithm Bellman-Ford Equation (dynamic programming) Define dx(y) := cost of least-cost path from x to y Then dx(y) = minv { c(x,v) + dv(y) } where min is taken over all neighbors v of x Forms the basis of a simple distributed algorithm for computing shortest paths 12

Distributed Distance-Vector Algorithm Each node x maintains a distance vector containing best distances to known destinations Dx = [ y, dx(y) = shortest known distance from x to y ] initially dx(y)=c(x,y) for local destinations only Node x sends its initial distance vector to its neighbors and re-sends it (or part of it) after every change When a node x receives a distance vector from a neighbor, it stores a copy and updates its own (Dx) for all destinations y, dx(y) = minvc(x,v) + dv(y) where the minimum is taken over all neighbors v of x the node does the same update if the cost of one of its links changes When link costs are stable, distance vectors eventually converge to the actual shortest path distances 13

Benefiting From Others Computations C2(r) R2 d12 C3(r) d13 r R1 R3 d14 C4(r) R4 R1 only computes c1(r)=min{d12+c2(r),d13+c3(r),d14+c4(r)} In other words, it takes advantage of the work done by R2, R3, R4 to compute c2(r), c3(r), and c4(r) But it has to wait for them to perform those computations before it can produce its own answer 14

Shielded from Irrelevant Changes C2(r) R2 d12 C3(r) d13 r R1 R3 d14 C4(r) R4 R1 unaffected by change/failure of path from R2 to r Update from R2 is received and processed, but does not result in changes, i.e., R1 does not propagate further updates 15

Responding to Link Cost Reductions Link cost changes: node detects local link cost change updates routing info, recalculates distance vector if DV changes, notify neighbors 1 y 4 1 x z 4 t0: x, y detect link-cost change, recompute their DVs, and send copies to neighbors good news travels fast t1: all receive updates and recompute DV; z sends copy to neighbors t2: x, y receive z s update, recompute own DV; since DVs do not change further, no additional updates 16

Responding to Increase in Costs After link cost increase y thinks best path to x is through z (with cost of 6) z now thinks best path to x is through y (with cost of 7) y now thinks best path to x is through z (with cost of 8) and so forth eventually correct value is reached, but can take a while (need to count up to ) bad news travels slowly Can improve convergence by using poisoned reverse if node a thinks its best path to node c is through its neighbor b, it tells b that its distance to cis infinity this prevents b from trying to reach c through a this helps in simple cases, but is not a general solution General loop prevention solutions exist but add complexity 60 y 4 1 x z 50 17

Distance Vector Computation (1) From Routes ; Cost To 19.2.4.0/24 19.2.5.0/24 Stub R1 19.2.4.0/24 ; 1 19.2.5.0/24 ; 1 19.2.0.0/16 ; 6 R2, R3, R4 Stub 1 19.2.6.0/24 1 1 1 Stub R2 4 R1 3 R2 19.2.6.0/24 ; 1 R1, R4 6 6 2 Transit 19.2.0.0/16 R4 1 2 R3 19.2.0.0/16 ; 5 19.2.7.0/24 ; 3 R1, R4 5 3 R3 Stub 19.2.7.0/24 R4 19.2.6.0/24 ; 2 19.2.7.0/24 ; 2 19.2.0.0/16 ; 1 R1, R3, R2 18

Distance Vector Computation (2) 19.2.4.0/24 ; 1 (local) 19.2.5.0/24 ; 1 (local) 19.2.0.0/16 ; 6 (local) 19.2.6.0/24 ; 2 (R2) 19.2.7.0/24 ; 8 (R4) 19.2.6.0/24 ; 1 (local) 19.2.4.0/24 ; 5 (R1) 19.2.5.0/24 ; 5 (R1) 19.2.0.0/16 ; 4 (R4) 19.2.7.0/24 ; 5 (R4) 19.2.0.0/16 ; 5 (local) 19.2.7.0/24 ; 3 (local) 19.2.4.0/24 ; 6 (R1) 19.2.5.0/24 ; 6 (R1) 19.2.6.0/24 ; 7 (R4) 19.2.6.0/24 ; 2 (local) 19.2.7.0/24 ; 2 (local) 19.2.0.0/16 ; 1 (local) 19.2.4.0/24 ; 2 (R1) 19.2.5.0/24 ; 2 (R1) R1 19.2.4.0/24 19.2.5.0/24 Stub Stub 1 19.2.6.0/24 R2 1 1 1 Stub R2 4 R1 3 6 6 2 Transit 19.2.0.0/16 R4 1 R3 2 5 3 R3 Stub 19.2.7.0/24 R4 19

Distance Vector Computation (3) 19.2.4.0/24 ; 1 (local) 19.2.5.0/24 ; 1 (local) 19.2.0.0/16 ; 6 (local) 19.2.6.0/24 ; 2 (R2) 19.2.7.0/24 ; 6 (R2) 19.2.6.0/24 ; 1 (local) 19.2.4.0/24 ; 5* (R1, R4) 19.2.5.0/24 ; 5* (R1, R4) 19.2.0.0/16 ; 4 (R4) 19.2.7.0/24 ; 5 (R4) 19.2.0.0/16 ; 5 (local) 19.2.7.0/24 ; 3 (local) 19.2.4.0/24 ; 6 (R1) 19.2.5.0/24 ; 6 (R1) 19.2.6.0/24 ; 7* (R1, R4) 19.2.6.0/24 ; 2 (local) 19.2.7.0/24 ; 2 (local) 19.2.0.0/16 ; 1 (local) 19.2.4.0/24 ; 2 (R1) 19.2.5.0/24 ; 2 (R1) R1 19.2.4.0/24 19.2.5.0/24 Stub Stub 1 19.2.6.0/24 R2 1 1 1 Stub R2 4 R1 3 6 1+3+1=5<6 6 2 Transit 19.2.0.0/16 R4 R3 1 2 5 3 R3 Stub 19.2.7.0/24 R4 NH: Next Hop 20

Reconciling Sources of Routing Information Routers often acquire routing information from multiple sources, e.g., local configuration, protocols with different/incompatible metrics How to compare and select? Administrative distance specifies the degree of preference of a protocol Smaller is better Default administrative distance is vendor specific Table to the right is for Cisco (Juniper s is slightly different) Protocol Connected interface (direct) Static route EIGRP eBGP OSPF IS-IS RIP EGP iBGP Unknown Distance 0 1 5 20 110 115 120 140 200 255 21

Link-State Routing Divides route computation into two parts 1. distributing link-state to all routers (link state advertisements, a.k.a. LSAs) network topology plus link costs Allows each router to build a complete map (graph) of the network 2. computing best routes using global link-state map centralized shortest path algorithm on the complete network graph Distributing link-state requires a dedicated mechanism uses a flooding technique to make sure that information reaches all routers (cannot depend on routing) important to stop flooding and minimize duplicate Route computation can use any efficient algorithm Dijkstra s algorithm is the usual choice can compute shortest paths in large networks in <1 second 22

Flooding Example My LSA1 Flooding Routers Forward new information (reliably) on all links except the one on which it was received (if applicable) Sequence numbers used to identify new information My LSA1 My LSA1 1 1 My LSA1 My LSA1 1 My LSA1 1 1 23

Flooding Example 2 2 4 3 4 2 4 24

Flooding Example 2 2 4 3 5 2 5 25

Dijsktras Algorithm (Refresher) 1 Initialization: 2 S = {s}; d(s) = 0 3 for all edges (s,v) 4 d(v) = c(s,v) 5 p(v) = s 6 for non-neighbors, d(v) = 7 8 Loop 9 select u not in S with smallest value of d(u) 10 add u to S 11 for all edges (u,v) where v is not in S 12 if d(u) + c(u,v) < d(v) then 13 d(v) = d(u) + c(u,v) 14 p(v) = u 15 until all nodes are in S u s finalized nodes (S) boundary remainder Use heap to efficiently find best u in S O(m log n) algorithm 26

Some Subtleties 1 B 1 A 1 The order in which nodes are added to Scan affect the number of paths discovered Once a node is added to S it is never revisited 1 2 0 1 E C 0 In cases of ties, nodes with outgoing costs of 0 must be added first to S Shortest path computation at A B and C have costs of 1 & 2 and E a cost of B is added to S E s cost is updated from to 2 E and C are in a tie to be added to S If E was added first to S, the path A-C-E of cost 2 would not be discovered Note: in link state protocols only outgoing transit network edges have a cost of 0. All other edges have a positive cost No cycles of length 0 27

Some More Subtleties r2 r1 Shortest path computations proceed in two phases 1. Dijkstra to all core nodes (routers and transit networks) 2. Add stub nodes (linear complexity) Stub Stub 1 r3 1 1 1 Stub R2 4 R1 3 6 6 2 T R4 1 2 5 3 R3 Stub r4 28

A 2-Step Shortest Path Computation 1 1 R2 1 Adding stub nodes Visit all core nodes and add local stub nodes Update distance of stub nodes accessible from multiple core nodes R1: r1(1),r2(1) R2: r3(1+1=2) R3: r4(12+3=15) R4: r4(6+1=7<15) r3 R1 5 4 6 r1 12 0 2 6 R4 r2 1 T 0 1 0 5 r4 R3 3 Shortest paths at R1 R2(1);R4(6), T(12),R3( ) R2(1),R4(6); T(12),R3( ) R2(1),R4(6),T(12);R3(12) R2(1),R4(6),T(12),R3(12) 29

Combining Link-State and Distance Vector Computations Area 1 Area 2 Used to scale to larger networks Break large network into several smaller areas Routers know full network graph only in their local area Link-state (Dijkstra) to compute shortest paths in each area B 1 A 2 C D 3 E F 4 5 A & E compute shortest paths to B,C,D and F in area 2 A & E advertise their shortest path costs to B,C,D and F into area 1 1 computes its shortest paths to A & E and determines its shortest path costs to B,C,D and F based on a DV computation A: F(3); E: F(1) 1: A(1); E(2) F(3) through E Border routers leak (as distance vectors in LSAs) results of Dijkstra computations into other areas Internal router use DV computation to find shortest path to routes in remote area Minimum across border routers of cost to border router + cost advertised by border router 30

Exercises 1. Consider the graph on the right. Show the final distance vectors computed by the Bellman-Ford algorithm at nodes A, B, C and D (just show the final result) 1 1 B 1 5 r3 A 4 6 r1 12 2 0 6 C r2 1 T 0 1 0 5 r4 D 3 31

Exercises 1. Consider the graph on the right. Show the final distance vectors computed by the Bellman-Ford algorithm at nodes A, B, C and D (just show the final result) 1 1 B 1 5 r3 A 4 6 r1 12 2 0 A Route Cost + next hop 6 C r2 1 r1 1, local T 0 1 r2 1, local 0 r3 2, B 5 r4 D r4 7, B 3 Note: path through B also has a cost of 12 but is not used T 12, local Route Cost + next hop Route Cost + next hop Route Cost + next hop B C D r1 5, A r1 7, A/T r1 6, A/T r2 5, A r2 7, A/T r2 6, A/T r3 1, local r3 2, local r3 7, A/T, C/T r4 6, C r4 1, local r4 3, local T 11, C T 6, local T 5, local 32

Exercises 1 A 1 B 1 Consider the network on the right, where link B-D fails. Focusing on route r, show the distances that A, B, and C send to each other as a result of this change. Assume poisoned reverse is used. Show how each node updates its own distance after it receiving distances from its neighbors. 2. C 10 1 D 1 r 33

Exercises 1 A 1 B 1 Consider the network on the right, where link B-D fails. Focusing on route r, show the distances that A, B, and C send to each other as a result of this change. Assume poisoned reverse is used. Show how each node updates its own distance after it receiving distances from its neighbors. 2. C 10 1 D 1 r Column: Receiving node Row: Sending node t=0 t=1 t=2 t=3 t=4 t=5 A B C D A * 16 3 B 2 * 2 16 C 3 16 * 3 D 1 1 * t=6 A B C D A * 16 3 B 16 * 16 C 3 16 * 3 D 1 * t=7 A B C D A * 4 16 B 16 * 16 C 16 4 * D t=8 A B C D A * 16 16 B 6 * 5 C 11 1 * 6 D t=9 A B C D A * 12 16 B 12 * 16 C 6 16 * 6 D t=10 A B C D A * 7 16 B 16 * 16 C 16 7 * 7 D t=11 4 1 * 1 * 1 * 1 * A B C D A * 16 16 B 16 * 8 C 11 11 * 16 D A B C D A * 12 16 B 12 * 16 C 9 16 * 9 D A B C D A * 10 16 B 16 * 13 C 11 11 * 16 D A B C D A * 12 16 B 16 * 11 C 11 11 * 16 D 1 * A B C D A * 12 16 B 12 * 16 C 11 11 * 16 D A B C D A * 12 16 B 12 * 16 C 11 11 * 16 D 1 * 1 * 1 * 1 * 1 * 34

Exercises 3. What is the maximum number of times an LSA can traverse a bidirectional link (in either direction)? 4. What is the maximum number of copies of an LSA that a node can receive? 5. Assuming it takes on average t secs for an LSA to propagate between neighbors, give an estimate function of the network graph characteristics for how long it takes a new LSA to reach all nodes in the network? 35

Exercises 3. What is the maximum number of times an LSA can traverse a bidirectional link (in either direction)? Twice, once in each direction 4. What is the maximum number of copies of an LSA that a node can receive? 5. Assuming it takes on average t secs for an LSA to propagate between neighbors, give an estimate function of the network graph characteristics for how long it takes a new LSA to reach all nodes in the network? 36

Exercises 3. What is the maximum number of times an LSA can traverse a bidirectional link (in either direction)? Twice, once in each direction 4. What is the maximum number of copies of an LSA that a node can receive? d, where d is the degree of the node 5. Assuming it takes on average t secs for an LSA to propagate between neighbors, give an estimate function of the network graph characteristics for how long it takes a new LSA to reach all nodes in the network? 37

Exercises 3. What is the maximum number of times an LSA can traverse a bidirectional link (in either direction)? Twice, once in each direction 4. What is the maximum number of copies of an LSA that a node can receive? d, where d is the degree of the node 5. Assuming it takes on average t secs for an LSA to propagate between neighbors, give an estimate function of the network graph characteristics for how long it takes a new LSA to reach all nodes in the network? D*t, where D is the diameter of the network 38

Exercises r1 1 1 1 Compute the routing table at router A using Dijkstra (identify both costs and next hop(s) for all entries). Link costs are all symmetric, except for transit network nodes (T1 and T2), for which outgoing costs are all 0 1 6. 10 A r2 B r3 10 5 5 1 10 T1 1 C 5 5 1 D 10 r4 10 1 E r5 1 F 5 5 T2 1 1 1 10 r6 5 r7 G 1 1 39

Exercises Compute the routing table at router A using Dijkstra (identify both costs and next hop(s) for all entries). Link costs are all symmetric, except for transit network nodes (T1 and T2), for which outgoing costs are all 0 Dijkstra s algorithm at A proceeds as follows: A(0);T1(5),B(10),C(10),D( ),E( ),F( ),T2( ),G( ) A(0),T1(5);B(5),C(5),D(5),E( ),F( ),T2( ),G( ) A(0),T1(5),B(5);C(5),D(5),E( ),F( ),T2( ),G( ) A(0),T1(5),B(5),C(5);D(5),E(15),F( ),T2( ),G( ) A(0),T1(5),B(5),C(5),D(5);E(15),F(15),T2( ),G( ) A(0),T1(5),B(5),C(5),D(5),E(15);F(15),T2(20),G( ) A(0),T1(5),B(5),C(5),D(5),E(15),F(15);T2(20),G(25) A(0),T1(5),B(5),C(5),D(5),E(15),F(15),T2(20);G(20) A(0),T1(5),B(5),C(5),D(5),E(15),F(15),T2(20),G(20); 6. 10 A B 10 5 5 10 T1 C 5 5 D 10 10 E F 5 5 T2 10 5 G T1 is the next hop for all entries 40

Exercises r1 1 1 1 Compute the routing table at router A using Dijkstra (identify both costs and next hop(s) for all entries). Link costs are all symmetric, except for transit network nodes (T1 and T2), for which outgoing costs are all 0 The second step of route computation adds stub networks based on the nodes they are attached to and the distances to those nodes computed in the first step: A(0),T1(5),B(5),C(5),D(5),E(15),F(15),T2(20),G(20) This produces the following routing table at A: r1: 1 (local 1) r2: 1 (local 2) r3: 6 (T1/B) r4: 6 (T1/C) r5: 6 (T1/D) r6: 16 (T1/C) r7: 16 (T1/D) T1: 5 (T1) T2: 20 (T1/C,D) 1 6. 10 A r2 B r3 10 5 5 1 10 T1 1 C 5 5 1 D 10 r4 10 1 E r5 1 F 5 5 T2 1 1 1 10 r6 5 r7 G 1 1 41

Exercises r1 1 1 1 The link A-B goes down How are routers notified of this event? 1 7. a. 10 A r2 B r3 10 5 5 1 10 T1 1 C 5 5 1 D 10 r4 10 1 How does the failure affect the routing table at A? b. E r5 1 F 5 5 T2 1 1 1 10 r6 5 r7 G 1 1 42

Exercises r1 1 1 1 The link A-B goes down How are routers notified of this event? After routers A and B detect the failure (routers run a Hello protocol to detect such issues), they originate new LSAs and flood them to their neighbors that will propagate them to their own neighbors (the LSA has a newer sequence number) until the information reaches all routers 1 7. a. 10 A r2 B r3 10 5 5 1 10 T1 1 C 5 5 1 D 10 r4 10 1 How does the failure affect the routing table at A? b. E r5 1 F 5 5 T2 1 1 1 10 r6 5 r7 G 1 1 43

Exercises r1 1 1 1 The link A-B goes down How are routers notified of this event? After routers A and B detect the failure (routers run a Hello protocol to detect such issues), they originate new LSAs and flood them to their neighbors that will propagate them to their own neighbors (the LSA has a newer sequence number) until the information reaches all routers 1 7. a. 10 A r2 B r3 10 5 5 1 10 T1 1 C 5 5 1 D 10 r4 10 1 How does the failure affect the routing table at A? The routing table at A is unchanged since the link A- B was not used on any shortest path. b. E r5 1 F 5 5 T2 1 1 1 10 r6 5 r7 G 1 1 44

Exercise Consider the two area network below with routers B and D serving as border routers between areas. Compute the routing table at router A (identify both costs and next hop(s) for all entries). Link costs are again symmetric, except for transit network nodes (T1, T2, T 1, and T 2), for which outgoing costs are all 0 8. r'1 1 r1 1 1 1 10 10 A A r'2 r2 B 10 10 5 5 1 5 1 5 10 T1 T 1 C C 5 5 5 5 1 D 1 10 10 Area 2 Area 1 r 3 r3 10 10 E r 4 1 E r4 1 F F 5 5 5 5 1 1 T2 T 2 1 1 1 1 10 10 r'6 r5 5 5 r 5 r6 G G 1 1 1 1 45

Exercise Consider the two area network below with routers B and D serving as border routers between areas. Compute the routing table at router A (identify both costs and next hop(s) for all entries). Link costs are again symmetric, except for transit network nodes (T1, T2, T 1, and T 2), for which outgoing costs are all 0 8. Reusing mostly the same computations as before, the routing table for Area1 at A is of the form r1: 1 (local 1) r2: 2 (local 2) r3: 6 (T1/C) r4: 16 (T1/D) r5: 16 (T1/C) r6: 16 (T1/D) T1: 5 (T1) T2: 20 (T1/C,D) Similarly, the distance vector that B and D advertise into area 1 based on the distances they compute d for routes in area 2 is of the form B r'1: 6 r'2: 6 r'3: 6 r'4: 16 r'5: 16 r'6: 16 T 1: 5 T 2: 20 The distances of the shortest path from A to B and D are both 5 with a next hop of T1. Hence the complete routing table at A is of the form Area 1 r1: 1 (local 1) r2: 2 (local 2) r3: 6 (T1/C) r4: 16 (T1/D) r5: 16 (T1/C) r6: 16 (T1/D) T1: 5 (T1) T2: 20 (T1/C,D) T 2: 20 (T1/D) Area 2 r 1: 11 (T1/B,D) r 2: 11 (T1/B,D) r 3: 11 (T1/B,D) r 4: 16 (T1/D) r 5: 16 (T1/D) r 6: 21 (T1/B,D) T 1: 10 (T1/B,D) D r 1: 6 r 2: 6 r 3: 6 r 4: 11 r 5: 11 r 6: 16 T 1: 5 T 2: 15 46