115-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 applicationsemail WWW phone...SMTP HTTP RTP...TCP UDP…IPethernet 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 scale2Lecture 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 address3Lecture 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 1sthop 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 step4Lecture 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 3R5Lecture 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 examples6Lecture 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 of hosts• E.g., www.cmu.edu• DNS binds host names to interfaces• Routing binds interface names to pathsLecture 8: 2-3-05 22Addressing Considerations• Hierarchical vs. flat• Pennsylvania / Pittsburgh / Oakland / CMU / Seshanvs. Srinivasan Seshan:123-45-6789• What information would routers need to route to Ethernet addresses?• Need hierarchical structure for designing scalable binding from interface name to route!• What type of Hierarchy?• How many levels?• Same hierarchy depth for everyone?• Same segment size for similar partition?Lecture 8: 2-3-05 23IP Addresses• Fixed length: 32 bits• Initial classful structure (1981)• Total IP address size: 4 billion• Class A: 128 networks, 16M hosts• Class B: 16K networks, 64K hosts• Class C: 2M networks, 256 hostsHigh Order Bits0 10 110Format7
View Full Document
Unlocking...