Question? Leave a message!




Interdomain Routing Broadcast routing

Interdomain Routing Broadcast routing
Interdomain Routing Broadcast routing EECS 489 Computer Networks http://www.eecs.umich.edu/courses/eecs489/w07 Z. Morley Mao Monday Feb 12, 2007 1 Mao W07 Acknowledgement: Some slides taken from KuroseRoss and KatzStoicaƒƒ 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) BellmanFord Equation (dynamic programming) Define d (y) := cost of leastcost 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 W07BellmanFord example (2) 5 Clearly, d (z) = 5, d (z) = 3, d (z) = 3 v x w 3 v w 5 2 BF 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 BF 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 linkcost 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 counttoinfinity 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 “intraAS” routing protocol routers in different AS can run different intraAS 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 interAS routing algorithm IntraAS sets entries for IntraAS InterAS internal dests Routing Routing algorithm algorithm InterAS IntraAs sets entries for external dests Forwarding table 15 Mao W07ƒ InterAS 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 interAS 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 interAS protocol that subnet x is reachable from AS3 (gateway 1c) but not from AS2. InterAS protocol propagates reachability info to all internal routers. Router 1d determines from intraAS 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 interAS 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 interAS routing protocol Hot potato routing: send packet towards closest of two routers. Determine from Use routing info Learn from interAS Hot potato routing: forwarding table the from intraAS protocol that subnet Choose the gateway interface I that leads protocol to determine x is reachable via that has the to leastcost gateway. costs of leastcost multiple gateways smallest least cost Enter (x,I) in paths to each forwarding table of the gateways 18 Mao W07ƒƒ IntraAS Routing Also known as Interior Gateway Protocols (IGP) Most common IntraAS 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 BSDUNIX 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ƒƒ RIP advertisements Distance vectors: exchanged among neighbors every 30 sec via Response Message (also called advertisement) Each advertisement: list of up to 25 destination nets within AS 21 Mao W07RIP: Example z w xy A D B C Destination Network Next Router Num. of hops to dest. w A2 y B2 z B7 x 1 …. …. .... Routing table in D 22 Mao W07RIP: Example Dest Next hops Advertisement w from A to D x z C 4 z …. … ... w xy A D B C Destination Network Next Router Num. of hops to dest. w A2 y B2 z B A 7 5 x 1 …. …. .... Routing table in D 23 Mao W07RIP: Link Failure and Recovery If no advertisement heard after 180 sec neighbor/link declared dead routes via neighbor invalidated new advertisements sent to neighbors neighbors in turn send out new advertisements (if tables changed) link failure info quickly propagates to entire net poison reverse used to prevent pingpong loops (infinite distance = 16 hops) 24 Mao W07ƒƒ RIP Table processing RIP routing tables managed by applicationlevel process called routed (daemon) advertisements sent in UDP packets, periodically repeated routed routed Transprt Transprt (UDP) (UDP) network forwarding forwarding network (IP) table table (IP) link link physical physical 25 Mao W07ƒƒƒƒ OSPF (Open Shortest Path First) “open”: publicly available Uses Link State algorithm LS packet dissemination Topology map at each node Route computation using Dijkstra’s algorithm OSPF advertisement carries one entry per neighbor router Advertisements disseminated to entire AS (via flooding) Carried in OSPF messages directly over IP (rather than TCP or UDP 26 Mao W07ƒƒƒƒƒ OSPF “advanced” features (not in RIP) Security: all OSPF messages authenticated (to prevent malicious intrusion) Multiple samecost paths allowed (only one path in RIP) For each link, multiple cost metrics for different TOS (e.g., satellite link cost set “low” for best effort; high for real time) Integrated uni and multicast support: Multicast OSPF (MOSPF) uses same topology data base as OSPF Hierarchical OSPF in large domains. 27 Mao W07Hierarchical OSPF 28 Mao W07ƒƒƒƒ Hierarchical OSPF Twolevel hierarchy: local area, backbone. Linkstate advertisements only in area each nodes has detailed area topology; only know direction (shortest path) to nets in other areas. Area border routers: “summarize” distances to nets in own area, advertise to other Area Border routers. Backbone routers: run OSPF routing limited to backbone. Boundary routers: connect to other AS’s. 29 Mao W07ƒƒƒ Internet interAS routing: BGP BGP (Border Gateway Protocol): the de facto standard BGP provides each AS a means to: 1. Obtain subnet reachability information from neighboring ASs. 2. Propagate the reachability information to all routers internal to the AS. 3. Determine “good” routes to subnets based on reachability information and policy. Allows a subnet to advertise its existence to rest of the Internet: “I am here” 30 Mao W07ƒƒƒ BGP basics Pairs of routers (BGP peers) exchange routing info over semi permanent TCP conctns: BGP sessions Note that BGP sessions do not correspond to physical links. When AS2 advertises a prefix to AS1, AS2 is promising it will forward any datagrams destined to that prefix towards the prefix. AS2 can aggregate prefixes in its advertisement 3c 2c 3a 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 eBGP session iBGP session 31 Mao W07ƒƒƒƒ Distributing reachability info With eBGP session between 3a and 1c, AS3 sends prefix reachability info to AS1. 1c can then use iBGP do distribute this new prefix reach info to all routers in AS1 1b can then readvertise the new reach info to AS2 over the 1bto2a eBGP session When router learns about a new prefix, it creates an entry for the prefix in its forwarding table. 3c 2c 3a 3b 2a AS3 2b 1c AS2 1a 1b 1d AS1 eBGP session iBGP session 32 Mao W07ƒƒƒ Path attributes BGP routes When advertising a prefix, advert includes BGP attributes. prefix + attributes = “route” Two important attributes: ASPATH: contains the ASs through which the advert for the prefix passed: AS 67 AS 17 NEXTHOP: Indicates the specific internalAS router to nexthop AS. (There may be multiple links from current AS to nexthopAS.) When gateway router receives route advert, uses import policy to accept/decline. 33 Mao W07ƒƒ BGP route selection Router may learn about more than 1 route to some prefix. Router must select route. Elimination rules: 1. Local preference value attribute: policy decision 2. Shortest ASPATH 3. Closest NEXTHOP router: hot potato routing 4. Additional criteria 34 Mao W07ƒƒ BGP messages BGP messages exchanged using TCP. BGP messages: OPEN: opens TCP connection to peer and authenticates sender UPDATE: advertises new path (or withdraws old) KEEPALIVE keeps connection alive in absence of UPDATES; also ACKs OPEN request NOTIFICATION: reports errors in previous msg; also used to close connection 35 Mao W07BGP routing policy legend: provider B network X W A customer network: C Y Figure 4.5BGPnew: a simple BGP scenario A,B,C are provider networks X,W,Y are customer (of provider networks) X is dualhomed: attached to two networks X does not want to route from B via X to C .. so X will not advertise to B a route to C 36 Mao W07BGP routing policy (2) legend: provider B network X W A customer network: C Y Figure 4.5BGPnew: a simple BGP scenario A advertises to B the path AW B advertises to X the path BAW Should B advertise to C the path BAW No way B gets no “revenue” for routing CBAW since neither W nor C are B’s customers B wants to force C to route to w via A B wants to route only to/from its customers 37 Mao W07ƒƒƒƒƒ Why different Intra and InterAS routing Policy: InterAS: admin wants control over how its traffic routed, who routes through its net. IntraAS: single admin, so no policy decisions needed Scale: hierarchical routing saves table size, reduced update traffic Performance: IntraAS: can focus on performance InterAS: policy may dominate over performance 38 Mao W07Broadcast routing duplicate creation/transmission duplicate R1 duplicate R2 R2 R3 R4 R3 R4 (b) (a) Sourceduplication versus innetwork duplication. (a) source duplication, (b) innetwork duplication 39 Mao W07ƒƒ How to get rid of duplicates Sequencenumber A controlled flooding B Broadcast sequence c number Source node address D E F G Only forward if packet arrived on the link on Reverse path forwarding its own shortest unicast path back to source 40 Mao W07ƒ Spanning tree to the rescue Spanningtree broadcast A tree containing every node, no cycles A A B B c c D D F E E F G G (b) Broadcast initiated at D (a) Broadcast initiated at A Broadcast along a spanning tree 41 Mao W07ƒƒ How to construct a spanning tree A A 3 B B c c 4 2 D D F E E F 5 1 G G (a) Stepwise construction (b) Constructed spanning of spanning tree tree Centerbased construction of a spanning tree E is the center of the tree Is this a minimum spanning tree 42 Mao W07
Website URL
Comment