1 Computer)Networking)Rou1ng)Algorithms)Rou1ng)Algorithms Rou1ng)Algorithms 1 2 3 0111 value in arriving packet’s header routing algorithm local forwarding table header value output link 0100 0101 0111 1001 3 2 2 1 Interplay)between)rou1ng,)forwarding)2 Rou1ng)Algorithms u y x w v z 2 2 1 3 1 1 2 5 3 5 Graph: G = (N,E) N = set of routers = { u, v, w, x, y, z } E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Graph)abstrac1on)Remark: Graph abstraction is useful in other network contexts Example: P2P, where N is set of peers and E is set of TCP connections Rou1ng)Algorithms Graph)abstrac1on:)costs)u y x w v z 2 2 1 3 1 1 2 5 3 5 • c(x,x’) = cost of link (x,x’) - e.g., c(w,z) = 5 • 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) Question: What’s the least-cost path between u and z ? Routing algorithm: algorithm that finds least-cost path3 Rou1ng)Algorithms Rou1ng)Algorithm)classifica1on)Global)or)decentralized)informa1on?)Global:)❒ all)routers)have)complete)topology,)link)cost)info)❒ “link)state”)algorithms)Decentralized:))❒ router)knows)physicallyGconnected)neighbors,)link)costs)to)neighbors)❒ itera1ve)process)of)computa1on,)exchange)of)info)with)neighbors)❒ “distance)vector”)algorithms)Sta1c)or)dynamic?)Sta1c:))❒ routes)change)slowly)over)1me)Dynamic:))❒ routes)change)more)quickly)❍ periodic)update)❍ in)response)to)link)cost)changes)Rou1ng)Algorithms A)LinkGState)Rou1ng)Algorithm)Dijkstra’s)algorithm)❒ net)topology,)link)costs)known)to)all)nodes)❍ accomplished)via)“link)state)broadcast”))❍ all)nodes)have)same)info)❒ computes)least)cost)paths)from)one)node)(‘source”))to)all)other)nodes)❍ gives)forwarding)table)for)that)node)❒ itera1ve:)aQer)k)itera1ons,)know)least)cost)path)to)k)dest.’s)Nota1on:)❒ c(x,y):)link)cost)from)node)x)to)y;))=)∞)if)not)direct)neighbors)❒ D(v):)current)value)of)cost)of)path)from)source)to)dest.)v)❒ p(v):)predecessor)node)along)path)from)source)to)v)❒ N':)set)of)nodes)whose)least)cost)path)defini1vely)known)4 Rou1ng)Algorithms Dijsktra’s)Algorithm)1 Initialization: 2 N' = {u} 3 for all nodes v 4 if v adjacent to u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in N' such that D(w) is a 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) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N' Rou1ng)Algorithms Dijkstra’s)algorithm:)example)Step 0 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz D(v),p(v) 2,u 2,u 2,u D(w),p(w) 5,u 4,x 3,y 3,y D(x),p(x) 1,u D(y),p(y) ∞ 2,x D(z),p(z) ∞ ∞ 4,y 4,y 4,y u y x w v z 2 2 1 3 1 1 2 5 3 55 Rou1ng)Algorithms Dijkstra’s)algorithm:)example)(2)))u y x w v z Resulting shortest-path tree from u: v x y w z (u,v) (u,x) (u,x) (u,x) (u,x) destination link Resulting forwarding table in u: Rou1ng)Algorithms Dijkstra’s)algorithm,)discussion)Algorithm)complexity:)n)nodes)❒ each)itera1on:)need)to)check)all)nodes,)w,)not)in)N)❒ n(n+1)/2)comparisons:)O(n2))❒ more)efficient)implementa1ons)possible:)O(nlogn))Oscilla1ons)possible:)❒ e.g.,)link)cost)=)amount)of)carried)traffic)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 … recompute6 Rou1ng)Algorithms Distance)Vector)Algorithm))BellmanGFord)Equa1on)(dynamic)programming))Define)dx(y)):=)cost)of)leastGcost)path)from)x)to)y)Then)dx(y))=)min){c(x,v))+)dv(y))})where)min)is)taken)over)all)neighbors)v)of)x)v Rou1ng)Algorithms BellmanGFord)example))u y x w v z 2 2 1 3 1 1 2 5 3 5 Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Node that achieves minimum is next hop in shortest path ➜ forwarding table B-F equation says:7 Rou1ng)Algorithms Distance)Vector)Algorithm))❒ Dx(y))=)es1mate)of)least)cost)from)x)to)y)❒ Node)x)knows)cost)to)each)neighbor)v:)c(x,v))❒ Node)x)maintains))distance)vector)Dx)=)[Dx(y):)y)є)N)])❒ Node)x)also)maintains)its)neighbors’)distance)vectors)❍ For)each)neighbor)v,)x)maintains))Dv)=)[Dv(y):)y)є)N)])Rou1ng)Algorithms Distance)vector)algorithm)(4))Basic)idea:))❒ From)1meGtoG1me,)each)node)sends)its)own)distance)vector)es1mate)to)neighbors)❒ Asynchronous)❒ When)a)node)x)receives)new)DV)es1mate)from)neighbor,)it)updates)its)own)DV)using)BGF)equa1on:)Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N ❒ Under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y)8 Rou1ng)Algorithms Distance)Vector)Algorithm)(5))Itera1ve,)asynchronous:)each)local)itera1on)caused)by:))❒ local)link)cost)change))❒ DV)update)message)from)neighbor)Distributed:)❒ each)node)no1fies)neighbors)only)when)its)DV)changes)❍ neighbors)then)no1fy)their)neighbors)if)necessary)wait for (change in local link cost or msg from neighbor) recompute estimates if DV to any dest has changed, notify neighbors Each node: Rou1ng)Algorithms x y z x y z 0 2 7 ∞ ∞ ∞ ∞ ∞ ∞ from cost to from from x y z x y z 0 from cost to x y z x y z ∞ ∞ ∞ ∞ ∞ cost to x y z x y z ∞ ∞ ∞ 7 1 0 cost to ∞ 2 0 1 ∞ ∞ ∞ 2 0 1 7 1 0 time x z 1 2 7 y node x table node y table node z table Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+1 , 7+0} = 3 3 29 Rou1ng)Algorithms x y z x y z 0 2 7 ∞ ∞ ∞ ∞ ∞ ∞ from cost to from from x y z x y z 0 2 3 from cost to x y z x y z 0 2 3 from cost to x y z x y z ∞ ∞ ∞ ∞ ∞ cost to x y z x y z 0 2 7 from cost to x y z x y z 0 2 3 from cost to x y z x y z 0 2 3 from cost to x y z x y z 0 2 7 from cost to x y z x y z ∞ ∞ ∞ 7 1 0 cost to ∞ 2 0 1 ∞ ∞ ∞ 2 0 1 7 1 0 2 0 1 7 1 0 2 0 1 3 1 0 2 0 1 3 1 0 2 0 1 3 1 0 2 0