1Internet ProtocolLayer reminder Bridges - emulate single link Everything broadcast Same collision domain Switches - emulate single network Flat addressing Broadcast supported Internet - connect multiple networks Hierarchical addressing No broadcast Highly scalableIP service model Service provided to transport layer (TCP, UDP) Global name space Host-to-host connectivity (connectionless) Best-effort packet delivery Not in IP service model Delivery guarantees on bandwidth, delay or loss Delivery failure modes Packet delayed for a very long time Packet loss Packet delivered more than once Packets delivered out of orderIP addressing Ethernet address space Flat Assigned at manufacture time IP address space Hierarchical Assigned at configuration timeIP Addressing: introduction IP address: 32-bitidentifier for host,router interface interface: connectionbetween host/routerand physical link routers typically havemultiple interfaces host typically has oneinterface IP addressesassociated with eachinterface223.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 networks Address has 2components Network (high-orderbits) 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.272IPv4 Address ModelIP MulticastFuture UseE1110 + Multicast AddressD221256 - 28 bit110 + 21 bitC21465,536 - 216 bit10 + 14 bitB126224-224 bit0 + 7 bitA# ofNetworks# ofAddressesHost IDNetwork IDClass0 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 networks Class A network: 18.0.0.0 (MIT) www.mit.edu has address 18.7.22.83 Class B network: 128.174.0.0 (UIUC) www.cs.uiuc.edu has address 128.174.252.84 Class C network: 216.125.249.0 (Parkland) www.parkland.edu has address 216.125.249.97CIDR 3-class model too inflexible CIDR: Classless InterDomain Routing Arbitrary number of bits to specifynetwork Address format: a.b.c.d/x, where x is #bits in network portion11001000 00010111 00010000 00000000subnetparthostpart200.23.16.0/23Classless Domains Internet Archive - 207.241.224.0/20 4K hosts 207.241.224.0 - 207.241.239.255 AT&T - 204.127.128.0/18 16K hosts 204.127.128.0 - 204.127.191.255 UUNET - 63.64.0.0/10 4M hosts 63.64.0.0 - 63.127.255.255IP forwarding Forwarding table has: Network number Interface Avoid having to store 4 billion entries But there are still 2 million class C’s …and perhaps more CIDR networksHierarchical Routingscale: with 200 milliondestinations: can’t store all dest’s inrouting tables! routing table exchangewould swamp links!administrative autonomy internet = network ofnetworks each network admin maywant to control routing in itsown networkOur routing study thus far - idealizationall routers identicalnetwork “flat”… not true in practice3Hierarchical 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......Subnetting UIUC - 130.126.0.0/16 130.126.0.0 - 130.126.255.255 CRHC - 130.126.136.0/21 130.126.136.0 - 130.126.143.255 EWS - 130.126.160.0/21 130.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 if4 Most specific rule is used Most hosts outside of the core havedefault rulesCRHCEWSUIUCInternetif1if2if4if3Hierarchical Routing aggregate routers intoregions, “autonomoussystems” (AS) routers in same AS runsame routing protocol “intra-AS” routing protocol routers in different AS canrun different intra-ASrouting protocolGateway router Direct link to routerin another AS3b1d3a1c2aAS3AS1AS21a2c2b1bIntra-ASRouting algorithmInter-ASRouting algorithmForwardingtable3cInterconnected ASes Forwarding table isconfigured by both intra-and inter-AS routingalgorithm Intra-AS sets entries forinternal dests Inter-AS & Intra-As setsentries for external dests3b1d3a1c2aAS3AS1AS21a2c2b1b3cInter-AS tasks Suppose router in AS1receives datagram for whichdest is outside of AS1 Router should forwardpacket towards on of thegateway routers, but whichone?AS1 needs:1. to learn which destsare reachable throughAS2 and which throughAS32. to propagate thisreachability info to allrouters in AS1Job of inter-AS routing!4Example: Setting forwardingtable in router 1d Suppose AS1 learns from the inter-ASprotocol that subnet x is reachable from AS3(gateway 1c) but not from AS2. Inter-AS protocol propagates reachabilityinfo to all internal routers. Router 1d determines from intra-AS routinginfo that its interface I is on the least costpath 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-ASprotocol to determinecosts of least-costpaths to eachof the gatewaysHot potato routing:Choose the gatewaythat has thesmallest least costDetermine fromforwarding table the interface I that leads to least-cost gateway. Enter (x,I) in forwarding tableExample: Choosing among multipleASes 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.Intra-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 ProtocolInternet inter-AS routing: BGP BGP (Border Gateway Protocol): the de factostandard BGP provides each AS a means to: Obtain subnet reachability information from neighboringASs. Propagate the reachability information to all routersinternal to the AS. Determine “good” routes to subnets based on reachabilityinformation and policy. Allows a subnet to advertise its existence to rest ofthe Internet: “I am here”BGP basics• Pairs of routers
View Full Document
Unlocking...