Broadcast routing algorithm

Interdomain Routing Broadcast routing
Dr.GriffinWood Profile Pic
Dr.GriffinWood,United Kingdom,Teacher
Published Date:23-07-2017
Your Website URL(Optional)
Interdomain Routing Broadcast routing EECS 489 Computer Networks Z. Morley Mao Monday Feb 12, 2007 1 Mao W07 Acknowledgement: Some slides taken from Kurose&Ross and Katz&Stoicaƒƒ Adminstrivia Homework 2 will be posted this afternoon - Due date: next Monday Midterm 1 is in class next Wednesday 2 Mao W07ƒƒƒƒ Dijkstra’s algorithm, discussion Algorithm complexity: n nodes each iteration: need to check all nodes, w, not in N 2 n(n+1)/2 comparisons: O(n ) more efficient implementations possible: O(nlogn) Oscillations possible: e.g., link cost = amount of carried traffic A A A A 1 1+e 2+e 0 2+e 0 2+e 0 D B D B D 0 B D B 0 1 1+e 0 0 1 1+e e 0 0 0 e 1 1+e 0 C C C C 1 1 e …recompute …recompute …recompute initially routing 3 Mao W07Distance Vector Algorithm (1) Bellman-Ford Equation (dynamic programming) Define d (y) := cost of least-cost path from x to y x Then d (y) = min c(x,v) + d (y) x v where min is taken over all neighbors of x 4 Mao W07Bellman-Ford example (2) 5 Clearly, d (z) = 5, d (z) = 3, d (z) = 3 v x w 3 v w 5 2 B-F equation says: u 2 1 z 3 1 d (z) = min c(u,v) + d (z), 2 u v x y 1 c(u,x) + d (z), x c(u,w) + d (z) w = min 2 + 5, 1 + 3, 5 + 3 = 4 Node that achieves minimum is next hop in shortest path ➜ forwarding table 5 Mao W07ƒƒƒƒƒ Distance Vector Algorithm (3) D (y) = estimate of least cost from x to y x Distance vector: D = D (y): y є N x x Node x knows cost to each neighbor v: c(x,v) Node x maintains D = D (y): y є N x x Node x also maintains its neighbors’ distance vectors - For each neighbor v, x maintains D = D (y): y є N v v 6 Mao W07ƒƒ Distance vector algorithm (4) Basic idea: Each node periodically sends its own distance vector estimate to neighbors When node a node x receives new DV estimate from neighbor, it updates its own DV using B-F equation: D (y) ← min c(x,v) + D (y) for each node y ∊ N x v v Under minor, natural conditions, the estimate D (y) x converge the actual least cost d (y) x 7 Mao W07ƒƒƒ Distance Vector Algorithm (5) Iterative, asynchronous: Each node: each local iteration caused by: local link cost change wait for (change in local link DV update message from cost of msg from neighbor) neighbor Distributed: recompute estimates each node notifies neighbors only when its DV changes - neighbors then notify their if DV to any dest has neighbors if necessary changed, notify neighbors 8 Mao W07D (z) = minc(x,y) + x D (y) = minc(x,y) + D (y), c(x,z) + D (y) x y z D (z), c(x,z) + D (z) y z = min2+0 , 7+1 = 2 = min2+1 , 7+0 = 3 node x table cost to cost to cost to x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3 y y 2 0 1 ∞∞ ∞ y 2 0 1 z z 7 1 0 ∞∞ ∞ z 3 1 0 node y table cost to cost to cost to x y z x y z y x y z 2 1 x ∞∞ x 0 2 7 ∞ x 0 2 3 x z y y 7 2 0 1 2 0 1 y 2 0 1 z z ∞∞ ∞ 7 1 0 z 3 1 0 node z table cost to cost to cost to x y z x y z x y z x 0 2 7 x 0 2 3 x ∞∞ ∞ y y 2 0 1 y 2 0 1 ∞∞ ∞ z z z 3 1 0 3 1 0 71 0 time 9 Mao W07 from from from from from from from from fromDistance Vector: link cost changes Link cost changes: 1 node detects local link cost change y 4 1 updates routing info, recalculates x z 50 distance vector if DV changes, notify neighbors At time t , y detects the link-cost change, updates its DV, 0 “good and informs its neighbors. news At time t , z receives the update from y and updates its table. 1 travels It computes a new least cost to x and sends its neighbors its DV. fast” At time t , y receives z’s update and updates its distance table. 2 y’s least costs do not change and hence y does not send any message to z. 10 Mao W07Distance Vector: link cost changes Link cost changes: 60 good news travels fast y 4 1 bad news travels slow - “count to x infinity” problem z 50 44 iterations before algorithm stabilizes: see text X NH X - - Poisoned reverse: X NH Y 4 X X - - If Z routes through Y to get to X : Z 5 Y Y 51 Z Z tells Y its (Z’s) distance to X is Z 50 Y X NH infinite (so Y won’t route to X via X - - Z) Y 5 Z will this completely solve count to Z 5 Y infinity problem? X NH X - - Y 5 Z Z 6 Y 11 Mao W07ƒƒƒƒ Comparison of LS and DV algorithms Robustness: what happens if Message complexity router malfunctions? LS: with n nodes, E links, O(nE) msgs sent LS: DV: exchange between - node can advertise incorrect neighbors only link cost - convergence time varies - each node computes only its own table Speed of Convergence DV: 2 LS: O(n ) algorithm requires - DV node can advertise O(nE) msgs incorrect path cost - may have oscillations - each node’s table used by DV: convergence time varies others - may be routing loops • error propagate thru network - count-to-infinity problem 12 Mao W07ƒƒ ƒƒ Hierarchical Routing Our routing study thus far - idealization all routers identical network “flat” … not true in practice administrative autonomy scale: with 200 million internet = network of destinations: networks can’t store all dest’s in routing tables each network admin may want to control routing in its routing table exchange own network would swamp links 13 Mao W07ƒ ƒƒ Hierarchical Routing aggregate routers into Gateway router regions, “autonomous systems” (AS) Direct link to router in another AS routers in same AS run same routing protocol - “intra-AS” routing protocol - routers in different AS can run different intra-AS routing protocol 14 Mao W07ƒ Interconnected ASes 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d Forwarding table is configured by both intra- and inter-AS routing algorithm - Intra-AS sets entries for Intra-AS Inter-AS internal dests Routing Routing algorithm algorithm - Inter-AS & Intra-As sets entries for external dests Forwarding table 15 Mao W07ƒ Inter-AS tasks Suppose router in AS1 AS1 needs: receives datagram for which 1. to learn which dests are dest is outside of AS1 reachable through AS2 and - Router should forward which through AS3 packet towards on of the 2. to propagate this gateway routers, but which reachability info to all one? routers in AS1 Job of inter-AS routing 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 1d 16 Mao W07ƒƒƒƒ Example: Setting forwarding table in router 1d Suppose AS1 learns from the inter-AS protocol that subnet x is reachable from AS3 (gateway 1c) but not from AS2. Inter-AS protocol propagates reachability info to all internal routers. Router 1d determines from intra-AS routing info that its interface I is on the least cost path to 1c. Puts in forwarding table entry (x,I). 3c 3a 2c 3b 2a AS3 2b 1c AS2 1a 1b AS1 17 1d Mao W07ƒƒƒƒ Example: Choosing among multiple ASes Now suppose AS1 learns from the inter-AS protocol that subnet x is reachable from AS3 and from AS2. To configure forwarding table, router 1d must determine towards which gateway it should forward packets for dest x. This is also the job on inter-AS routing protocol Hot potato routing: send packet towards closest of two routers. Determine from Use routing info Learn from inter-AS Hot potato routing: forwarding table the from intra-AS protocol that subnet Choose the gateway interface I that leads protocol to determine x is reachable via that has the to least-cost gateway. costs of least-cost multiple gateways smallest least cost Enter (x,I) in paths to each forwarding table of the gateways 18 Mao W07ƒƒ Intra-AS Routing Also known as Interior Gateway Protocols (IGP) Most common Intra-AS routing protocols: - RIP: Routing Information Protocol - OSPF: Open Shortest Path First - IGRP: Interior Gateway Routing Protocol (Cisco proprietary) 19 Mao W07ƒƒƒ RIP ( Routing Information Protocol) Distance vector algorithm Included in BSD-UNIX Distribution in 1982 Distance metric: of hops (max = 15 hops) destination hops u v u 1 w v 2 A B w 2 x 3 y 3 x z 2 C D z y 20 Mao W07