15-441 Computer NetworkingScaleSlide 3Problem 1 – Reconnecting LANsOutlineBuilding Larger LANs: BridgesTransparent BridgesFrame ForwardingSpanning Tree BridgesProblem 2 – Bridging WeaknessesSlide 11What is an Internetwork?Logical Structure of InternetInternet Protocol (IP)Problem 3: Internetwork DesignGetting to a DestinationForwarding PacketsSimplified Virtual Circuits ExampleVirtual CircuitsSource Routing ExampleSlide 23Global Address ExampleGlobal AddressesComparisonProblem 3: Router Table SizeSlide 29Addressing in IPRouter Table SizeAddressing ConsiderationsIP AddressesIP Address Classes (Some are Obsolete)Original IP Route LookupSubnet Addressing RFC917 (1984)SubnettingSubnetting ExampleForwarding ExampleAside: Interaction with Link LayerCaching ARP EntriesARP Cache ExampleIP Address Problem (1991)IP Address Utilization (‘97)Important ConceptsARP Cache SurpriseCMU’s Internal Network StructureProxy ARPMonitoring Packet TrafficSlide 5015-441 Computer NetworkingLecture 7 – IP Addressing and Forwarding9-20-07Lecture 7: Addressing/Forwarding 2Scale•What breaks when we keep adding people to the same wire?yak yak…9-20-07Lecture 7: Addressing/Forwarding 3Scale•What breaks when we keep adding people to the same wire?•Only solution: split up the people onto multiple wires•But how can they talk to each other?yak yak…9-20-07Lecture 7: Addressing/Forwarding 4Problem 1 – Reconnecting LANs•When should these boxes forward packets between wires?•How do you specify a destination?•How does your packet find its way?yak yak…9-20-07Lecture 7: Addressing/Forwarding 5Outline •Bridging•Internetworks•Methods for packet forwarding•Traditional IP addressing9-20-07Lecture 7: Addressing/Forwarding 6Building Larger LANs: Bridges•Extend reach of a single shared medium•Connect two or more “segments” by copying data frames between them•Only copy data when needed key difference from repeaters/hubs•Reduce collision domain compared with single LAN•Separate segments can send at once much greater bandwidth•Challenge: learning which packets to copy across linksLAN 1 LAN 29-20-07Lecture 7: Addressing/Forwarding 7Transparent Bridges•Design goals:•Self-configuring without hardware or software changes•Bridge do not impact the operation of the individual LANs•Three parts to making bridges transparent:1) Forwarding frames2) Learning addresses/host locations3) Spanning tree algorithm9-20-07Lecture 7: Addressing/Forwarding 8Frame Forwarding•A machine with MAC Address lies in the direction of number port of the bridge•For every packet, the bridge “looks up” the entry for the packets destination MAC address and forwards the packet on that port.•Other packets are broadcast – why?•Timer is used to flush old entries8711C98900AA2MAC AddressPortA21032C9A591199A323C908422301B2369011C2695519001190315Age36011611Bridge1329-20-07Lecture 7: Addressing/Forwarding 9Spanning Tree Bridges•More complex topologies can provide redundancy.•But can also create loops.•What is the problem with loops?•Solution: spanning tree (see HW)host host host host hosthost host host host hosthosthostBridge Bridge9-20-07Lecture 7: Addressing/Forwarding 10Problem 2 – Bridging Weaknesses•Doesn’t handle incompatible LAN technologies•How well does it scale?9-20-07Lecture 7: Addressing/Forwarding 11Outline •Bridging•Internetworks•Methods for packet forwarding•Traditional IP addressing9-20-07Lecture 7: Addressing/Forwarding 12What 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)9-20-07Lecture 7: Addressing/Forwarding 13Logical 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 connect one network to another•Different paths to destination may existhosthostrouterrouterrouterrouterrouterrouter9-20-07Lecture 7: Addressing/Forwarding 14Internet 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...9-20-07Lecture 7: Addressing/Forwarding 15Problem 3: Internetwork Design•How do I designate a distant host?•Addressing / naming•How do I send information to a distant host?•What gets sent?•What route should it take?•Must support:•Heterogeneity LAN technologies•Scalability ensure ability to grow to worldwide scalehosthost hostLAN 1...hosthost hostLAN 2...router router routerWAN WAN9-20-07Lecture 7: Addressing/Forwarding 16Getting to a Destination•How do you get driving directions?•Intersections routers•Roadslinks/networks•Roads change slowly9-20-07Lecture 7: Addressing/Forwarding 17Forwarding Packets•Table of virtual circuits •Connection routed through network to set up 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 address9-20-07Lecture 7: Addressing/Forwarding 19Simplified Virtual CircuitsExampleReceiverPacketconn 5 3Sender2341conn 5 423412341conn 5 3R2R3R15 5559-20-07Lecture 7: Addressing/Forwarding 20Virtual Circuits•Advantages•Efficient lookup (simple table lookup)•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 networks9-20-07Lecture 7: Addressing/Forwarding 22Source Routing ExampleReceiverPacketR1, R2, R3, RSender234123412341R2R3R1R2, R3, RR3, RR9-20-07Lecture 7: Addressing/Forwarding 23Source Routing•Advantages•Switches
View Full Document