15-16: Inter and intra AS, RIP, OSPF, BGP, Router ArchitectureGoals of Routing ProtocolsReal Internet Routing?Recall CIDRCIDRDynamic Routing Protocols?Routing in the InternetHierarchical RoutingInternet AS HierarchyIntra-AS and Inter-AS routingSlide 11Intra vs Inter AS Routing protcolsIntra-AS RoutingRIP ( Routing Information Protocol)RIP: Link Failure and RecoveryRIP Table processingRIP Table example: netstat -rnOSPF (Open Shortest Path First)OSPF “advanced” features (not in RIP)Hierarchical OSPF: Mini InternetHierarchical OSPFIGRP (Interior Gateway Routing Protocol)Now on to Inter-AS routingAutonomous systemsInternet inter-AS routing: BGPSlide 26Slide 27Internet MapThe Internet around 1990CAIDA: NSFNET growth until 1995NSF Networking Architecture of Late 1990sNetwork Access PointThe Internet in 1997A typical Network Access Point (NAP)CAIDA’s skitter plotRoadmapGetting a datagram from source to dest.Destination on same network as sourceDestination on different network than source, Step 1Destination on different network than source, Step 2Router Architecture OverviewInput Port FunctionsInput Port QueuingThree types of switching fabricsSwitching Via MemorySwitching Via BusSwitching Via An Interconnection NetworkOutput PortsOutput port queueingMiscRouter HardwareRouter ConfigurationOuttakesA small InternetWhy different Intra- and Inter-AS routing ?CAIDA: Layout showing Major ISPs4: Network Layer 4a-115-16: Inter and intra AS, RIP, OSPF, BGP, Router ArchitectureLast Modified: 01/14/19 07:07 AM4: Network Layer 4a-2Goals of Routing ProtocolsFind the “optimal route”Rapid Convergence Robustness Configurable to respond to changes in many variables (changes in bandwidth, delay, queue size, policy, etc.)Ease of configuration4: Network Layer 4a-3Real Internet Routing?CIDR?Dynamic routing protocols running between every router?4: Network Layer 4a-4Recall CIDR“Send me anythingwith addresses beginning 200.23.16.0/20”200.23.16.0/23200.23.18.0/23200.23.30.0/23Fly-By-Night-ISPOrganization 0Organization 7InternetOrganization 1ISPs-R-Us“Send me anythingwith addresses beginning 199.31.0.0/16”200.23.20.0/23Organization 2......We already talked about how routing based on hierarchical allocation of IP address space can allows efficient advertisement of routing information:4: Network Layer 4a-5CIDRCIDR by itself is a nice idea but..Hard to maintainWork around existing IP address space allocationsWhat about redundant paths?Dynamic routing protocols?They maintain/update themselvesAllow for redundant paths4: Network Layer 4a-6Dynamic Routing Protocols?scale: with 50 million destinations:can’t store all destinations in routing tables!routing table exchange would swamp links! Neither link state nor distance vector could handle the whole InternetOur study of dynamic routing protocols thus far = idealized graph problemall routers identicalnetwork “flat”… not true in practice4: Network Layer 4a-7Routing in the InternetAdministrative AutonomyInternet = network of networksEach network controls routing in its own networkGlobal routing system to route between Autonomous Systems (AS)Two-level routing: Intra-AS: administrator is responsible for choiceInter-AS: unique standard4: Network Layer 4a-8Hierarchical RoutingRouters in same AS run same routing protocol“intra-AS” routing protocolrouters in different AS can run different intra-AS routing protocolspecial routers in ASrun intra-AS routing protocol with all other routers in ASalso responsible for routing to destinations outside ASrun inter-AS routing protocol with other gateway routersgateway routers4: Network Layer 4a-9Internet AS HierarchyIntra-AS border (exterior gateway) routersInter-AS interior (gateway) routers4: Network Layer 4a-10Intra-AS and Inter-AS routingGateways:•perform inter-AS routing amongst themselves•perform intra-AS routers with other routers in their ASinter-AS, intra-AS routing in gateway A.cnetwork layerlink layerphysical layerabbaaCABdA.aA.cC.bB.acbc4: Network Layer 4a-11Intra-AS and Inter-AS routingHost h2abbaaCABdcA.aA.cC.bB.acbHosth1Intra-AS routingwithin AS AInter-AS routingbetween A and BIntra-AS routingwithin AS BSingle datagram is often routed over many hops via routes established by several intra-AS routing protocols and an inter-AS routing protocol4: Network Layer 4a-12Intra vs Inter AS Routing protcolsFor Intra AS routing protocols: many choices; For Inter AS routing protocols: standardWhy does this make sense?Intra AS routing protocols focus on performance optimization; Inter AS routing protocols focus on administrative issuesWhy does this make sense?Choice in Intra-ASIntra-AS often static routing based on CIDR, can also be dynamic (usually RIP or OSPF)Standard Inter-AS BGP is dynamic4: Network Layer 4a-13Intra-AS RoutingAlso known as Interior Gateway Protocols (IGP)Most common IGPs:RIP: Routing Information ProtocolOSPF: Open Shortest Path FirstIGRP: Interior Gateway Routing Protocol (Cisco proprietary)Can also be static (via CIDR) but that is not called an IGP4: Network Layer 4a-14RIP ( Routing Information Protocol)Distance vector algorithmIncluded in BSD-UNIX Distribution in 1982Single Distance metric: # of hops (max = 15 hops)Can you guess why? Count to infinity less painful if infinity = 16 But limits RIP to networks with a diameter of 15 hopsDistance vectors: exchanged every 30 sec via Response Message (also called advertisement)Each advertisement: route to up to 25 destination nets4: Network Layer 4a-15RIP: 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 ping-pong loops (infinite distance = 16 hops)4: Network Layer 4a-16RIP Table processingRIP routing tables managed by application-level process called route-d (daemon)advertisements sent in UDP packets, periodically repeatedPeriodically inform kernel of routing table to use4: Network Layer 4a-17RIP Table example: netstat -rn Three attached class C networks (LANs) Router only knows routes to attached LANs Default router used to “go up” Route multicast address: 224.0.0.0 Loopback