11 – Inter/Intra-AS RoutingHierarchical RoutingSlide 3Interconnected ASesInter-AS tasksSlide 6Example: Choosing among multiple ASesIntra-AS RoutingRIP ( Routing Information Protocol)RIP advertisementsRIP: ExampleSlide 12RIP: Link Failure and RecoveryOSPF (Open Shortest Path First)OSPF “advanced” features (not in RIP)Hierarchical OSPFSlide 17Internet inter-AS routing: BGPBGP basicsDistributing reachability infoPath attributes & BGP routesBGP route selectionBGP routing policyBGP routing policy (2)Why different Intra- and Inter-AS routing ?Network Layer: summaryChapter 5: The Data Link LayerLink Layer: IntroductionLink layer: contextLink Layer ServicesLink Layer Services (more)Adaptors CommunicatingError DetectionParity CheckingInternet checksumChecksumming: Cyclic Redundancy CheckCRC ExampleCRC11 – Inter/Intra-AS RoutingNetwork Layer 4-1Network Layer 4-2Hierarchical Routingscale: with 200 million destinations:can’t store all dest’s in routing tables!routing table exchange would swamp links! administrative autonomyinternet = network of networkseach network admin may want to control routing in its own networkOur routing study thus far - idealization all routers identicalnetwork “flat”… not true in practiceNetwork Layer 4-3Hierarchical Routingaggregate routers into regions, “autonomous systems” (AS)routers in same AS run same routing protocol“intra-AS” routing protocolrouters in different AS can run different intra-AS routing protocolGateway routerDirect link to router in another ASNetwork Layer 4-43b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cInterconnected ASesForwarding table is configured by both intra- and inter-AS routing algorithmsIntra-AS sets entries for internal destsInter-AS & Intra-AS set entries for external destsNetwork Layer 4-53b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS tasksSuppose router in AS1 receives datagram for which dest is outside of AS1Router should forward packet towards one of the gateway routers, but which one?AS1 needs:1. to learn which dests are reachable through AS2 and which through AS32. to propagate this reachability info to all routers in AS1Job of inter-AS routing!Network Layer 4-6Problem 6Network Layer 4-7Learn from inter-AS protocol that subnet x is reachable via multiple gatewaysUse routing infofrom intra-AS protocol to determinecosts of least-cost paths to eachof the gatewaysHot potato routing:Choose the gatewaythat has the smallest least costDetermine fromforwarding table the interface I that leads to least-cost gateway. Enter (x,I) in forwarding tableExample: 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 of inter-AS routing protocol!Hot potato routing: send packet towards closest of two routers.Network Layer 4-8Intra-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)Network Layer 4-9RIP ( Routing Information Protocol)Distance vector algorithmDistance metric: # of hops (max = 15 hops)DCBAuvwxyzdestination hops u 1 v 2 w 2 x 3 y 3 z 2 At A:Network Layer 4-10RIP 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 ASNetwork Layer 4-11RIP: Example Destination Network Next Router Num. of hops to dest. w A 2y B 2 z B 7x -- 1…. …. ....wx yzACDBRouting table in DNetwork Layer 4-12RIP: Example Destination 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 - - x - - z C 4 …. … ...Advertisementfrom A to DNetwork Layer 4-13RIP: 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 netNetwork Layer 4-14OSPF (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Advertisements disseminated to entire AS (via flooding)Carried in OSPF messages directly over IPNetwork Layer 4-15OSPF “advanced” features (not in RIP)Security: all OSPF messages authenticated (to prevent malicious intrusion) Multiple same-cost paths allowed (only one path in RIP)Integrated uni- and multicast support: Multicast OSPF (MOSPF) uses same topology data base as OSPFHierarchical OSPF in large domains.Network Layer 4-16Hierarchical OSPFNetwork Layer 4-17Hierarchical OSPFTwo-level hierarchy: local area, backbone.Link-state advertisements only in area each node has detailed area topology; only know direction (shortest path) to nets in other areas.Area border routers: connect to the backbone and thus other areas.Backbone routers: route traffic between areas.Boundary routers: connect to other AS’s.Network Layer 4-18Internet inter-AS 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”Network Layer 4-19BGP basicsPairs of routers (BGP peers) exchange routing info over semi-permanent TCP connections: 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 advertisement3b1d3a1c2aAS3AS1AS21a2c2b1b3ceBGP sessioniBGP sessionNetwork Layer 4-20Distributing reachability infoWith eBGP session between 3a