1RoutingintheInternetLast Time Link-State routing protocol Broadcast all link state to all routers Run Dijkstra’s algorithm to find best paths Distance Vector routing protocol Distribute vector of current distances toall neighbors Update current distances based onneighbors’ inputsMP3 Implement LS and DV routingalgorithms Write a node that: Connects to some neighbors Monitors link quality Exchanges routing state information Computes (outputs) best routesTroll Network “troll” simulates an unreliablelink Drops packets Delays packets Reorders packets Garbles packets One troll per direction of a (logical) linkExample Topology123T1T2T3T4T5T6Setting Up Topology Node i on port 500i Troll i on port 600itroll -h localhost -i 5002 6001troll -h localhost -i 5001 6002troll -h localhost -i 5003 6003troll -h localhost -i 5001 6004troll -h localhost -i 5002 6005troll -h localhost -i 5003 6006node DV 5001 localhost 6001 L1 localhost 6003 L2node DV 5002 localhost 6002 L1 localhost 6006 L3node DV 5003 localhost 6004 L2 localhost 6005 L32Things to Keep in Mind Find a partner Teams of 1-2, suggest 2 Ask in class, on newsgroup Start early! Deal with loss, errors, dead links How do you detect dead links? Watch out for runaway broadcast Solve the count-to-infinity problemThis class Routing in the Internet Hierarchical routing RIP OSPF BGP Broadcast techniquesHierarchical Routingscale: with 200 milliondestinations: can’t store all dest’s inrouting tables! routing table exchangewould swamp links!administrative autonomy internet = network of networks each network admin maywant to control routing in itsown networkOur routing study thus far - idealization all routers identical network “flat”… not true in practiceHierarchical Routing aggregate routers intoregions, “autonomoussystems” (AS) routers in same ASrun same routingprotocol “intra-AS” routingprotocol routers in different AScan run different intra-AS routing protocolGateway router Direct link to routerin another AS3b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cInterconnected ASes Forwarding table isconfigured by bothintra- and inter-ASrouting algorithm Intra-AS sets entriesfor internal dests Inter-AS & Intra-Assets entries for externaldests3b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS tasks Suppose router in AS1receives datagram forwhich dest is outsideof AS1 Router should forwardpacket towards one ofthe gateway routers,but which one?AS1 needs:1. to learn which destsare reachable throughAS2 and whichthrough AS32. to propagate thisreachability info to allrouters in AS1Job of inter-AS routing!3Example: Setting forwarding table in router 1d Suppose AS1 learns (via inter-AS protocol) that subnet xis reachable via AS3 (gateway 1c) but not via AS2. Inter-AS protocol propagates reachability info to allinternal routers. Router 1d determines from intra-AS routing info that itsinterface I is on the least cost path to 1c. Puts in forwarding table entry (x,I).3b1d3a1c2aAS3AS1AS21a2c2b1b3cChoosing among multiple ASes Now suppose AS1 learns from the inter-AS protocolthat subnet x is reachable from AS3 and from AS2. To configure forwarding table, router 1d mustdetermine towards which gateway it should forwardpackets for dest x. This is also the job on inter-AS routing protocol!3b1d3a1c2aAS3AS1AS21a2c2b1b3cLearn from inter-AS protocol that subnet x is reachable via multiple gatewaysUse routing infofrom intra-ASprotocol todeterminecosts of least-costpaths to eachof the gatewaysHot potato routing:Choose thegatewaythat has thesmallest least costDetermine fromforwarding table the interface I that leads to least-cost gateway. Enter (x,I) in forwarding tableChoosing among multiple ASes Now suppose AS1 learns from the inter-AS protocolthat subnet x is reachable from AS3 and from AS2. To configure forwarding table, router 1d mustdetermine towards which gateway it should forwardpackets for dest x. This is also the job on inter-AS routing protocol! Hot potato routing: send packet towards closest of tworouters.Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit anddatagram networks 4.3 What’s inside arouter 4.4 IP: InternetProtocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in theInternet RIP OSPF BGP 4.7 Broadcast andmulticast routingIntra-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)Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit anddatagram networks 4.3 What’s inside arouter 4.4 IP: InternetProtocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in theInternet RIP OSPF BGP 4.7 Broadcast andmulticast routing4RIP ( Routing Information Protocol) Distance vector algorithm Included in BSD-UNIX Distribution in 1982 Distance metric: # of hops (max = 15 hops)DCBAuvwxyzdestination hops u 1 v 2 w 2 x 3 y 3 z 2 From router A to subsets:RIP advertisements Distance vectors: exchanged amongneighbors every 30 sec via ResponseMessage (also called advertisement) Each advertisement: list of up to 25destination nets within ASRIP: ExampleDestination Network Next Router Num. of hops to dest. w A 2y B 2 z B 7x -- 1…. …. ....wx yzACDBRouting table in DRIP: ExampleDestination Network Next Router Num. of hops to dest. w A 2y B 2 z B A 7 5x -- 1…. …. ....Routing table in Dwx yzACDB Dest Next hops w - 1 x - 1 z C 4 …. … ...Advertisementfrom A to DRIP: Link Failure and RecoveryIf no advertisement heard after 180 sec -->neighbor/link declared dead routes via neighbor invalidated new advertisements sent to neighbors neighbors in turn send out newadvertisements (if tables changed) link failure info quickly (?) propagates toentire net poison reverse used to prevent
View Full Document