Routing algorithm classification Q:global or decentralized Q:static or dynamic? information? global: static routes change slowly over all routers have complete time topology,link cost info ■“link state”algorithms dynamic decentralized: routes change more quickly router knows physically- connected neighbors,link 。periodic update costs to neighbors ·in response to link ■iterative process of cost changes computation,exchange of info with neighbors “distance vector'”algorithms Network Layer:Control Plane 5-11
Routing algorithm classification Q: global or decentralized information? global: ▪ all routers have complete topology, link cost info ▪ “link state” algorithms decentralized: ▪ router knows physicallyconnected neighbors, link costs to neighbors ▪ iterative process of computation, exchange of info with neighbors ▪ “distance vector” algorithms Q: static or dynamic? static: ▪ routes change slowly over time dynamic: ▪ routes change more quickly • periodic update • in response to link cost changes Network Layer: Control Plane 5-11
Chapter 5:outline 5.I introduction 5.5 The SDN control plane 5.2 routing protocols 5.6 ICMP:The Internet ■link state Control Message ■distance vector Protocol 5.3 intra-AS routing in the 5.7 Network management Internet:OSPF and SNMP 5.4 routing among the ISPs: BGP Network Layer:Control Plane 5-12
5.1 introduction 5.2 routing protocols ▪ link state ▪ distance vector 5.3 intra-AS routing in the Internet: OSPF 5.4 routing among the ISPs: BGP 5.5 The SDN control plane 5.6 ICMP: The Internet Control Message Protocol 5.7 Network management and SNMP Chapter 5: outline Network Layer: Control Plane 5-12
A link-state routing algorithm Dijkstra's algorithm notation: net topology,link costs C(X,y):link cost from known to all nodes node x to y,=∞if not ·accomplished via“link state direct neighbors broadcast" D(v):current value of all nodes have same info cost of path from source computes least cost paths to dest.v from one node('source")p(V):predecessor node to all other nodes along path from source to gives forwarding table for that node N':set of nodes whose iterative:after k least cost path definitively iterations,know least cost known path to k dest.'s Network Layer:Control Plane 5-13
A link-state routing 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 ▪ iterative: after k iterations, know least cost path to k dest.’ s notation: ▪ 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 definitively known Network Layer: Control Plane 5-13
Dijsktra's algorithm 1 Initialization: 2N'={u} 3 for all nodes v 4 if v adjacent to u 5 then D(）=c(u,) 6 else D(W=∞ 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' Network Layer:Control Plane 5-14
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' Network Layer: Control Plane 5-14
Dijkstra's algorithm:example D(v)D(w)D(x)D(y)D(z) Step N' p(v)p(w) p(x)p(y)p(z) 0 U 7,u 3,U 5,u 0 1 uw 6,w (⑤，uD11,w 2 uwX 6,w 11,W14,X 3 uWXV (10,14,X 4 uwxvy 12, 5 uwxvyz X 9 notes: 5 construct shortest path tree by tracing predecessor nodes ties can exist (can be broken arbitrarily) Network Layer:Control Plane 5-15
3 w 4 v x u 5 3 7 4 y 8 z 2 7 9 Dijkstra’s algorithm: example Step N' D(v) p(v) 0 1 2 3 4 5 D(w) p(w) D(x) p(x) D(y) p(y) D(z) p(z) u 7,u 3,u 5,u ∞ ∞ uw 6,w 5,u 11,w ∞ uwx 6,w 11,w 14,x uwxv 10,v 14,x uwxvy 12,y notes: ❖ construct shortest path tree by tracing predecessor nodes ❖ ties can exist (can be broken arbitrarily) uwxvyz Network Layer: Control Plane 5-15