Intradomain Topology and RoutingInternet Routing OverviewToday: Routing Inside an ASKey QuestionsPoint-of-Presence (PoP)Example: Abilene Network TopologyWhere’s Duke?Recent Development: NLR Packet NetProblem: RoutingDistance-Vector RoutingGood News Travels QuicklyProblem: Bad News Travels SlowlyIt Gets Worse“Solution”: Poison ReverseDoes Poison Reverse Always Work?Example: Routing Information ProtocolRIP UpdatesRIP: Staleness and Oscillation ControlLink-State RoutingLink-State vs. Distance-VectorOSPF: Salient FeaturesExample: Open Shortest Paths First (OSPF)Example: IS-ISHierarchical Routing in IS-ISLevel-1 vs. Level-2 RoutingCLNS Addressing: “NSAPs”ISIS on the Wire…IS-IS Configuration on Abilene (atlang)IS-IS vs. OSPFMonitoring OSPFChallenge #1: Capturing LSAsChallenge #2: Dealing with AreasToday’s Papers: Alternative Intradomain Routing MechanismsIntradomain Topology and Routing(Nick Feamster)January 30, 20082GeorgiaTechInternet Routing Overview•Today: Intradomain (i.e., “intra-AS”) routing•Monday: Interdomain routingComcastAbileneAT&TCogentAutonomous Systems (ASes)3Today: Routing Inside an AS•Intra-AS topology–Nodes and edges–Example: Abilene•Intradomain routing protocols–Distance Vector•Split-horizon/Poison-reverse•Example: RIP–Link State•Examples: OSPF, IS-IS4Key Questions•Where to place “nodes”?–Typically in dense population centers•Close to other providers (easier interconnection)•Close to customers (cheaper backhaul)–Note: A “node” may in fact be a group of routers, located in a single city. Called a “Point-of-Presence” (PoP)•Where to place “edges”?–Often constrained by location of fiber5Point-of-Presence (PoP)•A “cluster” of routers in a single physical location•Inter-PoP links–Long distances–High bandwidth•Intra-PoP links–Cables between racks or floorsPoP6Example: Abilene Network Topology•Problem Set 1 will have a problem dealing with Abilene router configurations/topology.7Where’s Duke?OC-48 (2.5GbpS uplink)NCREN Raleigh8Recent Development: NLR Packet Net9Problem: Routing•Routing: the process by which nodes discover where to forward traffic so that it reaches a certain node•Within an AS: there are two “styles”–Distance vector–Link State10Distance-Vector Routing•Routers send routing table copies to neighbors•Routers compute costs to destination based on shortest available path•Based on Bellman-Ford Algorithm–dx(y) = minv{ c(x,v) + dv(y) }–Solution to this equation is x’s forwarding tablex y zx 0 1 5yzx y zxy 1 0 2zx y zxyz 5 2 0yx z12511Good News Travels Quickly•When costs decrease, network converges quicklyx y zx 0 1 3y 1 0 2z 3 2 0x y zx 0 1 3y 1 0 2z 3 2 0x y zx 0 1 3y 1 0 2z 3 2 0yx z12512Problem: Bad News Travels Slowlyyx z125060x y zx 0 60 50y 5 0 2z 3 2 0x y zx 0 60 50y 5 0 2z 7 2 0Note also that there is a forwarding loop between y and z.13It Gets Worse•Question: How long does this continue?•Answer: Until z’s path cost to x via y is greater than 50.yx z125060x y zx 0 60 50y 5 0 2z 3 2 0x y zx 0 60 50y 5 0 2z 7 2 014“Solution”: Poison Reverse•If z routes through y to get to x, z advertises infinite cost for x to y•Does poison reverse always work?x y zx 0 1 3y 1 0 2z 3 2 0x y zx 0 1 Xy 1 0 2z X 2 0x y zx 0 1 3y 1 0 2z 3 2 0yx z12515Does Poison Reverse Always Work?yxz135060w1116Example: Routing Information Protocol •Earliest IP routing protocol (1982 BSD)–Version 1: RFC 1058 –Version 2: RFC 2453 •Features–Edges have unit cost–“Infinity” = 16•Sending Updates–Router listens for updates on UDP port 520–Message can contain up to 25 table entries17RIP Updates•Initial–When router first starts, asks for copy of table for every neighbor–Uses it to iteratively generate own table•Periodic–Table refresh every 30 seconds•Triggered–When ever an entry changes, send copy of entry to neighbors•Except for one causing update (split horizon rule)–Neighbors use to update their tables18RIP: Staleness and Oscillation Control•Small value for Infinity–Count to infinity doesn’t take very long•Route Timer–Every route has timeout limit of 180 seconds•Reached when haven’t received update from next hop for 6 periods–If not updated, set to infinity–Soft-state•Behavior–When router or link fails, can take minutes to stabilize19Link-State Routing•Idea: distribute a network map•Each node floods costs c(u,v) to its neighbors•Given all costs, each node performs shortest path (SPF) computation, e.g., using Dijkstra’s algorithm, between itself and all other nodes20Link-State vs. Distance-Vector•Convergence–DV has count-to-infinity–DV often converges slowly (minutes) –Odd timing dependencies in DV•Robustness–Route calculations a bit more robust under link-state. –DV algorithms can advertise incorrect least-cost paths•Bandwidth Consumption for Messages•Computation•Security21OSPF: Salient Features•Dijkstra, plus some additional features•Equal-cost multipath•Support for hierarchy: Inter-Area Routing22Example: Open Shortest Paths First (OSPF)•Key Feature: hierarchy•Network’s routers divided into areas•Backbone area is area 0•Area 0 routers perform SPF computation–All inter-area traffic travels through Area 0 routers (“border routers”)Area 023Example: IS-IS•Originally: ISO Connectionless Network Protocol (CLNP) . – CLNP: ISO equivalent to IP for datagram delivery services– ISO 10589 or RFC 1142•Later: Integrated or Dual IS-IS (RFC 1195)– IS-IS adapted for IP– Doesn’t use IP to carry routing messages•OSPF more widely used in enterprise, IS-IS in large service providers24Area 49.001Area 49.0002Level-1RoutingLevel-2RoutingLevel-1RoutingBackboneHierarchical Routing in IS-IS•Like OSPF, 2-level routing hierarchy –Within an area: level-1–Between areas: level-2–Level 1-2 Routers: Level-2 routers may also participate in L1 routing25Level-1 vs. Level-2 RoutingLevel 1 routing–Routing within an area –Level 1 routers track links, routers, and end systems within L1 area–L1 routers do not know the identity of destinations outside their area. –An L1 router forwards all traffic for destinations outside its area to the nearest L2 router within its area. Level 2 routing–Routing between areas –Level 2 routers know the level 2 topology and know which addresses are reachable via each level 2 router. –Level 2 routers track the location of each