15-441 Computer NetworkingInternet Protocol (IP)What is an Internetwork?Designing an InternetworkOutlineLogical Structure of InternetGetting to a DestinationForwarding PacketsSimplified Virtual CircuitsSimplified Virtual Circuits ExampleVirtual CircuitsSource RoutingSource Routing ExampleSlide 14Global Addresses (IP)Global Address ExampleGlobal AddressesRouter Table SizeComparisonSlide 20Addressing in IPAddressing ConsiderationsIP AddressesIP Address Classes (Some are Obsolete)Original IP Route LookupSubnet Addressing RFC917 (1984)SubnettingSubnetting ExampleForwarding ExampleAside: Interaction with Link LayerSlide 31IP Address Problem (1991)IP Address Utilization (‘97)Classless Inter-Domain Routing (CIDR) – RFC1338CIDR ExampleIP Addresses: How to Get One?Slide 37CIDR IllustrationCIDR ImplicationsImportant ConceptsSlide 41Host Routing Table ExampleRouting to the NetworkRouting Within the SubnetSlide 45Slide 46EXTRA SLIDES15-441 Computer NetworkingLecture 8 – IP Addressing and ForwardingLecture 8: 2-3-05 2Internet Protocol (IP)•Hour Glass Model•Create abstraction layer that hides underlying technology from network application software•Make as minimal as possible•Allows range of current & future technologies•Can support many different types of applicationsNetwork technologyNetwork applications email WWW phone...SMTP HTTP RTP...TCP UDP…IP ethernet PPP…CSMA async sonet... copper fiber radio...Lecture 8: 2-3-05 3What is an Internetwork?•Multiple incompatible LANs can be physically connected by specialized computers called routers•The connected networks are called an internetwork•The “Internet” is one (very big & successful) example of an internetworkhosthost hostLAN 1...hosthost hostLAN 2...router router routerWAN WANLAN 1 and LAN 2 might be completely different, totally incompatible LANs (e.g., Ethernet and ATM)Lecture 8: 2-3-05 4Designing an Internetwork•How do I designate a distant host?•Addressing / naming•How do I send information to a distant host?•Underlying service model•What gets sent?•How fast will it go?•What happens if it doesn’t get there?•Routing•Challenges•Heterogeneity•Assembly from variety of different networks•Scalability•Ensure ability to grow to worldwide scaleLecture 8: 2-3-05 5Outline•Methods for packet forwarding•Traditional IP addressing•CIDR IP addressing•Forwarding examplesLecture 8: 2-3-05 6Logical Structure of Internet•Ad hoc interconnection of networks•No particular topology•Vastly different router & link capacities•Send packets from source to destination by hopping through networks•Router forms bridge from one network to another•Different packets may take different routeshosthostrouterrouterrouterrouterrouterrouterLecture 8: 2-3-05 7Getting to a Destination•How do you get driving directions?•Intersections routers•Roads links/networks•Roads change slowly•Road signs•Detailed directions•MapsLecture 8: 2-3-05 8Forwarding Packets•Table of virtual circuits •Connection routed through network to setup state•Packets forwarded using connection state •Source routing•Packet carries path•Table of global addresses (IP) •Routers keep next hop for destination•Packets carry destination addressLecture 8: 2-3-05 9Simplified Virtual Circuits•Connection setup phase•Use other means to route setup request •Each router allocates flow ID on local link•Each packet carries connection ID•Sent from source with 1st hop connection ID•Router processing•Lookup flow ID – simple table lookup•Replace flow ID with outgoing flow ID•Forward to output portLecture 8: 2-3-05 10Simplified Virtual CircuitsExampleReceiverPacketconn 5 3Sender2341conn 5 423412341conn 5 3R2R3R15 555Lecture 8: 2-3-05 11Virtual Circuits•Advantages•Efficient lookup (simple table lookup)•More flexible (different path for each flow)•Can reserve bandwidth at connection setup•Easier for hardware implementations•Disadvantages•Still need to route connection setup request•More complex failure recovery – must recreate connection state•Typical use fast router implementations•ATM – combined with fix sized cells•MPLS – tag switching for IP networksLecture 8: 2-3-05 12Source Routing•List entire path in packet•Driving directions (north 3 hops, east, etc..)•Router processing•Strip first step from packet•Examine next step in directions•Forward to next stepLecture 8: 2-3-05 13Source Routing ExampleReceiverPacketR1, R2, R3, RSender234123412341R2R3R1R2, R3, RR3, RRLecture 8: 2-3-05 14Source Routing•Advantages•Switches can be very simple and fast•Disadvantages•Variable (unbounded) header size•Sources must know or discover topology (e.g., failures)•Typical uses•Ad-hoc networks (DSR)•Machine room networks (Myrinet)Lecture 8: 2-3-05 15Global Addresses (IP)•Each packet has destination address•Each router has forwarding table of destination next hop•At v and x: destination east•At w and y: destination south•At z: destination north•Distributed routing algorithm for calculating forwarding tablesLecture 8: 2-3-05 16Global Address ExampleReceiverPacketRSender234123412341R2R3R1RRR 3R 4R 3RLecture 8: 2-3-05 17Global Addresses•Advantages•Stateless – simple error recovery•Disadvantages•Every switch knows about every destination•Potentially large tables•All packets to destination take same route•Need routing protocol to fill tableLecture 8: 2-3-05 18Router Table Size•One entry for every host on the Internet•300M entries,doubling every 18 months•One entry for every LAN•Every host on LAN shares prefix•Still too many and growing quickly•One entry for every organization•Every host in organization shares prefix•Requires careful address allocationLecture 8: 2-3-05 19ComparisonSource Routing Global AddressesHeader Size Worst OK – Large addressRouter Table Size NoneNumber of hosts (prefixes)Forward Overhead Best Prefix matchingVirtual CircuitsBestNumber of circuitsPretty GoodSetup Overhead None NoneError Recovery Tell all hosts Tell all routersConnection SetupTell all routers and Tear down circuit and re-routeLecture 8: 2-3-05 20Outline•Methods for packet forwarding•Traditional IP addressing•CIDR IP addressing•Forwarding examplesLecture 8: 2-3-05 21Addressing in IP•IP addresses are names of interfaces•E.g., 128.2.1.1•Domain Name System (DNS) names are names
View Full Document