15-441 Computer NetworkingScaleSlide 3Problem 1 – Reconnecting LANsOutlineBuilding Larger LANs: BridgesTransparent BridgesFrame ForwardingLearning BridgesSpanning Tree BridgesProblem 2 – Bridging WeaknessesSlide 17What is an Internetwork?Logical Structure of InternetInternet Protocol (IP)Problem 3: Internetwork DesignGetting to a DestinationForwarding PacketsSimplified Virtual Circuits ExampleVirtual CircuitsSource Routing ExampleSlide 29Global Address ExampleGlobal AddressesComparisonProblem 3: Router Table SizeSlide 35Addressing in IPRouter Table SizeAddressing ConsiderationsIP AddressesIP Address Classes (Some are Obsolete)Original IP Route LookupSubnet Addressing RFC917 (1984)SubnettingSubnetting ExampleForwarding ExampleAside: Interaction with Link LayerIP Address Problem (1991)IP Address Utilization (‘97)Important ConceptsSome People Have Too Much Time…15-441 Computer NetworkingLecture 8 – Bridging, Addressing and Forwarding9-21-06 Lecture 8: Bridging/Addressing/Forwarding 2Scale•What breaks when we keep adding people to the same wire?yak yak…9-21-06 Lecture 8: Bridging/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-21-06 Lecture 8: Bridging/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-21-06 Lecture 8: Bridging/Addressing/Forwarding 5Outline •Bridging•Internetworks•Methods for packet forwarding•Traditional IP addressing9-21-06 Lecture 8: Bridging/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-21-06 Lecture 8: Bridging/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-21-06 Lecture 8: Bridging/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-21-06 Lecture 8: Bridging/Addressing/Forwarding 9Learning Bridges•Manually filling in bridge tables?•Time consuming, error-prone•Keep track of source address of packets arriving on every link, showing what segment hosts are on•Fill in the forwarding table based on this informationhost host host host hosthost host host host hosthosthostBridge9-21-06 Lecture 8: Bridging/Addressing/Forwarding 10Spanning 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-21-06 Lecture 8: Bridging/Addressing/Forwarding 16Problem 2 – Bridging Weaknesses•Doesn’t handle incompatible LAN technologies•How well does it scale?9-21-06 Lecture 8: Bridging/Addressing/Forwarding 17Outline •Bridging•Internetworks•Methods for packet forwarding•Traditional IP addressing9-21-06 Lecture 8: Bridging/Addressing/Forwarding 18What 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-21-06 Lecture 8: Bridging/Addressing/Forwarding 19Logical 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-21-06 Lecture 8: Bridging/Addressing/Forwarding 20Internet 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-21-06 Lecture 8: Bridging/Addressing/Forwarding 21Problem 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-21-06 Lecture 8: Bridging/Addressing/Forwarding 22Getting to a Destination•How do you get driving directions?•Intersectionsrouters•Roadslinks/networks•Roads change slowly9-21-06 Lecture 8: Bridging/Addressing/Forwarding 23Forwarding 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-21-06 Lecture 8: Bridging/Addressing/Forwarding 25Simplified Virtual CircuitsExampleReceiverPacketconn 5 3Sender2341conn 5 423412341conn 5 3R2R3R15 5559-21-06 Lecture 8: Bridging/Addressing/Forwarding 26Virtual Circuits•Advantages•Efficient lookup (simple table lookup)•Can reserve bandwidth at connection setup•Easier for hardware
View Full Document