Internet Protocol (IP)!2 basic functions!! Assigning unique addresses to each attachment point (router/host interface)!! Best effort packet delivery!" Fragmentation and re-assembly when needed!How does a router figure out where to forward each packet?!! Based on the information provided by network routing protocols!CS118!1!Where we are in the book!4.5 Routing algorithms (this lecture)!" Link state!" Distance Vector!" Hierarchical routing (FYI)!4.6 Routing in the Internet (next lecture)!" RIP: Routing Information Protocol!" OSPF: Open Shortest Path First Protocol!" BGP: Border Gateway Protocol!4.7 Broadcast and multicast routing (8th week)!CS118!2!Network Graph Abstraction!CS118!3!Graph: G = (N,E) N = set of routers = { A, B, C, D, E, F } E = set of links ={ (A,B), (A,C), (A,D), (B,C), (B,D), (C,D), (C,E), (C,F), (E,F) } A E D C B F 2 2 1 3 1 1 2 5 3 5 Cost of link (a, b) = c(a, b) – e.g. c(A, B) = 2 – link cost could always be 1, or inversely related to bandwidth, or inversely related to congestion Cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) Routing algorithm: given a graph, find least-cost path from a given node to all the other nodes in the graph Network Routing: algorithms vs. protocols!Route computation algorithms:!link-state (Dijkstra): each router!! has complete topology graph with all link costs!! computes shortest paths to all destinations!distance-vector (Bellman-Ford): a router!! knows its physically-connected neighbors and link costs to each!! computes its shortest paths based on the paths it learns from all neighbors!Routing protocols!! define the format of routing information exchanges!! define the computation upon receiving routing updates!! network topology changes over time # routing protocol must continuously update the routers with latest changes!CS118!4!A E D C B F 2 2 1 3 1 1 2 5 3 5Link-State algorithm: basic notations!! all nodes have identical info for network topology graph and link cost!! Each node computes least cost paths from itself to all other nodes!" builds forwarding table for next hop!! iterative: after k iterations, a node know the best path to k destinations!Notation:!! c(x,y): link cost from node x to y!" Initializes to " if (x, y) are not direct neighbors!! D(v): current value of cost of path from source to destination v!! p(v): predecessor node along path from source to v!! N': set of nodes whose least-cost paths are known!CS118!5!Link-State algorithm!CS118!6!1 Initialization: 2 N' = {A} 3 for all nodes v 4 if v adjacent to A 5 then D(v) = c(A,v) 6 else D(v) = ! 7 8 Loop 9 find w not in N' such that D(w) is minimum 10 add w to N' 11 update D(v) for all v adjacent to w and not in N': 12 D(v) = min( D(v), D(w) + c(w,v) ), p(v) = w 13 /* new cost to v is either the old cost, or the 14 shortest path cost to w plus the cost from w to v */ 15 until all nodes in N' A!E D C B F 2 2 1 3 1 1 2 5 3 5 (consider the computation done at node A)!Link-State algorithm: example!CS118!7!A E D C B F 2 2 1 3 1 1 2 5 3 5 Step 0 start N' A D(B),p(B) 2,A D(C),p(C) 5,A D(D),p(D) 1,A D(E),p(E) ! D(F),p(F) ! Link-State algorithm: example!CS118!8!A E D C B F 2 2 1 3 1 1 2 5 3 5 Step 0 1 start N' A AD D(B),p(B) 2,A 2,A D(C),p(C) 5,A 4,D D(D),p(D) 1,A D(E),p(E) ! 2,D D(F),p(F) !Link-State algorithm: example!CS118!9!A E D C B F 2 2 1 3 1 1 2 5 3 5 Step 0 1 2 start N' A AD ADE D(B),p(B) 2,A 2,A D(C),p(C) 5,A 4,D 3,E D(D),p(D) 1,A D(E),p(E) ! 2,D D(F),p(F) ! 4,E Link-State algorithm: example!CS118!10!A E D C B F 2 2 1 3 1 1 2 5 3 5 Step 0 1 2 3 start N’ A AD ADE ADEB D(B),p(B) 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) ! 2,D D(F),p(F) ! 4,E Link-State algorithm: example!CS118!11!A E D C B F 2 2 1 3 1 1 2 5 3 5 Step 0 1 2 3 4 start N’ A AD ADE ADEB ADEBC D(B),p(B) 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) ! 2,D D(F),p(F) ! 4,E 4,E Link-State algorithm: example!CS118!12!A E D C B F 2 2 1 3 1 1 2 5 3 5 Step 0 1 2 3 4 5 start N’ A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) ! 2,D D(F),p(F) ! 4,E 4,ELink-State algorithm: example!CS118!13!Step 0 1 2 3 4 5 start N’ A AD ADE ADEB ADEBC ADEBCF D(B),p(B) 2,A 2,A D(C),p(C) 5,A 4,D 3,E 3,E D(D),p(D) 1,A D(E),p(E) ! 2,D D(F),p(F) ! 4,E 4,E A E D C B F 2 2 1 3 1 1 2 5 3 5 B D E C F (A, B) (A, D) (A, D) (A, D) (A, D) destination Link/interface Resulting forwarding table at A: Resulting shortest-path tree for A: Link-State algorithm: discussion!Algorithm complexity: for a graph with n nodes!! each iteration: need to check all nodes, w, not in N'!! n(n+1)/2 comparisons: O(n^2)!" more efficient implementations possible: O(nlogn)!Oscillations possible:!! e.g., link cost = amount of carried traffic!CS118!14!A D C B 1 1+e e 0 e 1 1 0 0 A D C B 2+e 0 0 0 1+e 1 A D C B 0 2+e 1+e 1 0 0 A D C B 2+e 0 e 0 1+e 1 initially … recompute routing … recompute … recompute Distance Vector Algorithm!Recall Link-State algorithm:!! Each node knows the complete topology graph with link costs!! Each node calculate the shortest path to all other nodes!! (Each node floods its distance to neighbor nodes throughout the network – that’s how every node learns a complete map)!For Distance-Vector algorithm:!! each node communicates only with direct neighbors: send each neighbor a list of distances to all destinations!! Each node computes shortest path based on the input from all its neighbors !" If distance to any destination changes, send updated info to all neighbors again!!CS118!15!Distance Vector Equation!Define: Dx(y) := cost of best path from x to y!Then Dx(y) = min {c(x,v) + Dv(y) }!" where min is taken over all neighbors v of x!CS118!16!DA(F) = min {c(A,B) + DB(F), c(A,D) + DD(F), c(A,C) + DC(F) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Node leading to shortest path is next hop ߠ forwarding table A E D C B F 2 2 1 3 1 1 2 5 3 5Distance Vector: what a node does!! Node x knows cost to each neighbor v: c(x,v)!! Node x maintains Dx = [Dx(y): y є N ]!" Dx(y) = estimate of least cost from x to y!! Node x sends the distance vector, Dx, to all its neighbors!! Node x receives Dv from each neighbor v, then calculate D’x(y) = min {c(x,v) + Dv(y)}
View Full Document
Unlocking...