Network layer:"control plane"roadmap ■introduction routing protocols ■link state ■distance vector intra-ISP routing:OSPF routing among ISPs:BGP network management, SDN control plane configuration Internet Control Message ·SNMP Protocol ·NETCONF/YANG Network Layer:5-11
Network layer: “control plane” roadmap ▪ network management, configuration • SNMP • NETCONF/YANG ▪ introduction ▪ routing protocols ▪ link state ▪ distance vector ▪ intra-ISP routing: OSPF ▪ routing among ISPs: BGP ▪ SDN control plane ▪ Internet Control Message Protocol Network Layer: 5-11
Dijkstra's link-state routing algorithm centralized:network topology,link notation costs known to all nodes accomplished via "link state Cxy:direct link cost from broadcast'” node x to y;if not direct neighbors all nodes have same info D(v):current estimate of cost computes least cost paths from one of least-cost-path from source node("source")to all other nodes to destination v gives forwarding table for that node p(v):predecessor node along path from source to v iterative:after k iterations,know least cost path to k destinations N':set of nodes whose least- cost-path definitively known Network Layer:5-12
Dijkstra’s link-state routing algorithm Network Layer: 5-12 ▪ centralized: network 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 destinations ▪ cx,y: direct link cost from node x to y; = ∞ if not direct neighbors ▪ D(v): current estimate of cost of least-cost-path from source to destination v ▪ p(v): predecessor node along path from source to v ▪ N': set of nodes whose leastcost-path definitively known notation
Dijkstra's link-state routing algorithm 1 Initialization: 2N'={u} /compute least cost path from u to all other nodes * 3 for all nodes v 4 if v adjacent to u /u initially knows direct-path-cost only to direct neighbors * 5 then D(v)=Cuv /but may not be minimum cost! */ 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 Dwl=min(DwD(wl+cwv】 13 /new least-path-cost to v is either old least-cost-path to v or known 14 least-cost-path to w plus direct-cost from w to v*/ 15 until all nodes in N' Network Layer:5-13
Dijkstra’s link-state routing algorithm Network Layer: 5-13 1 Initialization: 2 N' = {u} /* compute least cost path from u to all other nodes */ 3 for all nodes v 4 if v adjacent to u /* u initially knows direct-path-cost only to direct neighbors */ 5 then D(v) = cu,v /* but may not be minimum cost! */ 6 else D(v) = ∞ 7 8 Loop 9 10 11 12 13 14 15 until all nodes in N' find w not in N' such that D(w) is a minimum add w to N' update D(v) for all v adjacent to w and not in N' : D(v) = min ( D(v), D(w) + cw,v ) /* new least-path-cost to v is either old least-cost-path to v or known least-cost-path to w plus direct-cost from w to v */
Dijkstra's algorithm:an example (w Step N D(yip(）Dw1p叫Dp9Dyp(y)BrIp(z) 0 u 2 5u 1,U 1 ⑧ 2 2,X 2 u过 2,u 3.y 3 uxyv) ③yD 4 uxyww 4,y 5 uNy② Initialization(step0):For all a:if a adjacentto then D(a)=Cu 5 find a not in N'such that D(a)is a minimum add a to N' update D(b)for all b adjacent to a and not in N': D(b)=min (D(b),D(a)+ca,b) Network Layer:5-14
Dijkstra’s algorithm: an example Network Layer: 5-14 Step 0 1 2 3 4 5 N' D(v),p(v) D(x),p(x) D(y),p(y) D(z),p(z) u x y v w z 2 2 1 3 1 1 2 5 3 5 4,y D(w),p(w) 3,y 4,y 2,u 5,u 1,u ∞ ∞ 2,u 4,x 2,x ∞ 2,u 3,y 4,y uxyvwz uxyvw uxyv uxy ux u v w x y z find a not in N' such that D(a) is a minimum add a to N' update D(b) for all b adjacent to a and not in N' : D(b) = min ( D(b), D(a) + ca,b ) Initialization (step 0): For all a: if a adjacent to then D(a) = cu,a
Dijkstra's algorithm:an example 5 3 W resulting least-cost-path tree from u: resulting forwarding table in u: destination outgoing link V (u,) route from u to v directly X (u,X) y (u,x) route from u to all X W (u,x) other destinations (u,x) viax Network Layer:5-15
Dijkstra’s algorithm: an example Network Layer: 5-15 u x y v w z 2 2 1 3 1 1 2 5 3 5 u x y v w z resulting least-cost-path tree from u: resulting forwarding table in u: v x y w x (u,v) (u,x) (u,x) (u,x) (u,x) destination outgoing link route from u to v directly route from u to all other destinations via x