Internet ProtocolLayer reminderIP service modelIP addressingIP Addressing: introductionIP networksIPv4 Address ModelSlide 8CIDRClassless DomainsIP forwardingHierarchical RoutingHierarchical NetworksSubnettingForwarding TablesSlide 16Interconnected ASesInter-AS tasksExample: Setting forwarding table in router 1dExample: Choosing among multiple ASesIntra-AS RoutingInternet inter-AS routing: BGPBGP basicsDistributing reachability infoPath attributes & BGP routesBGP route selectionBGP messagesBGP routing policyBGP routing policy (2)Why different Intra- and Inter-AS routing ?Slide 31RIP ( Routing Information Protocol)RIP advertisementsRIP: ExampleRIP: Link Failure and RecoveryRIP Table processingOSPF (Open Shortest Path First)OSPF “advanced” features (not in RIP)Hierarchical OSPFSlide 40IPv4 Address Translation supportIP to Physical Address TranslationAddress Resolution Protocol (ARP)ARP snoopingARP exampleARP PacketHost ConfigurationSlide 48Dynamic Host Configuration Protocol (DHCP)Slide 50DHCPInternet ProtocolLayer reminderBridges - emulate single linkEverything broadcastSame collision domainSwitches - emulate single networkFlat addressingBroadcast supportedInternet - connect multiple networksHierarchical addressingNo broadcastHighly scalableIP service modelService provided to transport layer (TCP, UDP)Global name spaceHost-to-host connectivity (connectionless)Best-effort packet deliveryNot in IP service modelDelivery guarantees on bandwidth, delay or lossDelivery failure modesPacket delayed for a very long timePacket lossPacket delivered more than oncePackets delivered out of orderIP addressingEthernet address spaceFlatAssigned at manufacture timeIP address spaceHierarchicalAssigned at configuration timeIP Addressing: introductionIP address: 32-bit identifier for host, router interface interface: connection between host/router and physical linkrouters typically have multiple interfaceshost typically has one interfaceIP addresses associated with each interface223.1.1.1223.1.1.2223.1.1.3223.1.1.4 223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.1.1 = 11011111 00000001 00000001 000000012231 11IP networksAddress has 2 componentsNetwork (high-order bits)Host (low-order bits)223.1.1.1223.1.1.2223.1.1.3223.1.1.4 223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27IPv4 Address ModelClass Network ID Host ID # of Addresses# of NetworksA 0 + 7 bit 24 bit 224-2 126B 10 + 14 bit 16 bit 65,536 - 2 214C 110 + 21 bit 8 bit 256 - 2 221D 1110 + Multicast Address IP MulticastE Future Use0 Network (7 bits)Network (14 bits)1 1 01 0Network (21 bits)Host (24 bits)Host (16 bits)Host (8 bits)Class A:Class B:Class C:IP networksClass A network: 18.0.0.0 (MIT)www.mit.edu has address 18.7.22.83Class B network: 128.174.0.0 (UIUC)www.cs.uiuc.edu has address 128.174.252.84Class C network: 216.125.249.0 (Parkland)www.parkland.edu has address 216.125.249.97CIDR3-class model too inflexibleCIDR: Classless InterDomain RoutingArbitrary number of bits to specify networkAddress format: a.b.c.d/x, where x is # bits in network portion11001000 00010111 00010000 00000000subnetparthostpart200.23.16.0/23Classless DomainsInternet Archive - 207.241.224.0/204K hosts207.241.224.0 - 207.241.239.255AT&T - 204.127.128.0/1816K hosts204.127.128.0 - 204.127.191.255UUNET - 63.64.0.0/104M hosts63.64.0.0 - 63.127.255.255IP forwardingForwarding table has:Network numberInterfaceAvoid having to store 4 billion entriesBut there are still 2 million class C’s…and perhaps more CIDR networksHierarchical Routingscale: with 200 million destinations:can’t store all dest’s in routing tables!routing table exchange would swamp links! administrative autonomyinternet = network of networkseach network admin may want to control routing in its own networkOur routing study thus far - idealization all routers identicalnetwork “flat”… not true in practiceHierarchical Networks“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......SubnettingUIUC - 130.126.0.0/16130.126.0.0 - 130.126.255.255CRHC - 130.126.136.0/21130.126.136.0 - 130.126.143.255EWS - 130.126.160.0/21130.126.160.0 - 130.126.167.255Forwarding Tables130.126.136.0/21 if1130.126.160.0/21 if2130.126.0.0/16 if30.0.0.0/0 if4Most specific rule is usedMost hosts outside of the core have default rulesCRHCEWSUIUCInternetif1if2if4if3Hierarchical Routingaggregate routers into regions, “autonomous systems” (AS)routers in same AS run same routing protocol“intra-AS” routing protocolrouters in different AS can run different intra-AS routing protocolGateway routerDirect link to router in another AS3b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cInterconnected ASesForwarding table is configured by both intra- and inter-AS routing algorithmIntra-AS sets entries for internal destsInter-AS & Intra-As sets entries for external dests3b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS tasksSuppose router in AS1 receives datagram for which dest is outside of AS1Router should forward packet towards on 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!Example: Setting forwarding table in router 1dSuppose AS1 learns from the inter-AS protocol that subnet x is reachable from AS3 (gateway 1c) but not from AS2.Inter-AS protocol propagates reachability info to all internal routers.Router 1d determines from intra-AS routing info that its interface I is on the least cost path to 1c.Puts in forwarding table entry (x,I).Learn 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 ASesNow suppose AS1 learns from the
View Full Document