15-744 Computer NetworksOutlineEthernet MAC (CSMA/CD)Ethernet Backoff CalculationCollisionsMinimum Packet SizeEthernet Collision DetectEthernet Frame StructureEthernet Frame Structure (cont.)4B/5B EncodingFramingDealing with Errors Stop and Wait CaseSummarySlide 14ScaleSlide 16Problem 1 – Reconnecting LANsTransparent Bridges / SwitchesFrame ForwardingSpanning Tree BridgesSlide 21Global Address ExampleSource Routing ExampleSimplified Virtual Circuits ExampleVirtual Circuit IDs/Switching: Label (“tag”) SwappingComparisonMPLS core, IP interfaceSlide 28IP AddressesIP Address Classes (Some are Obsolete)Original IP Route LookupSubnet Addressing RFC917 (1984)Aside: Interaction with Link LayerClassless Inter-Domain Routing (CIDR) – RFC1338Host Routing Table ExampleRouting to the NetworkRouting Within the SubnetSlide 38Slide 39IP Addresses: How to Get One?Slide 41IP Service ModelIP Fragmentation ExampleImportant ConceptsSlide 45Distance-Vector RoutingDistance-Vector UpdateDistance Vector: Link Cost ChangesDistance Vector: Split HorizonDistance Vector: Poison ReversePoison Reverse FailuresLink State Protocol ConceptSending Link States by FloodingComparison of LS and DV AlgorithmsRouting HierarchiesRouting HierarchyArea Hierarchy AddressingPath Sub-optimalitySlide 59NAT: Opening Client ConnectionNAT: Client RequestNAT: Server ResponseExtending Private NetworkSupporting VPN by TunnelingImplementing TunnelingSlide 6615-744 Computer NetworksBackground Material 1: Getting stuff from here to thereOrHow I learned to love OSI layers 1-3Outline•Link-Layer•Ethernet and CSMA/CD•Bridges/Switches•Network-Layer•Physical-Layer23Ethernet MAC (CSMA/CD)Packet?Sense CarrierDiscard PacketSendDetect CollisionJam channel b=CalcBackoff(); wait(b);attempts++;NoYesattempts < 16attempts == 16•Carrier Sense Multiple Access/Collision DetectionEthernet Backoff Calculation•Exponentially increasing random delay•Infer senders from # of collisions•More senders increase wait time•First collision: choose K from {0,1}; delay is K x 512 bit transmission times•After second collision: choose K from {0,1,2,3}…•After ten or more collisions, choose K from {0,1,2,3,4,…,1023}4CollisionsTimeA B C56Minimum Packet Size•What if two people sent really small packets•How do you find collision?•Consider:•Worst case RTT•How fast bits can be sentEthernet Collision Detect•Min packet length > 2x max prop delay•If A, B are at opposite sides of link, and B starts one link prop delay after A•Jam network for 32-48 bits after collision, then stop sending•Ensures that everyone notices collision78Ethernet Frame Structure•Sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame9Ethernet Frame Structure (cont.)•Addresses: 6 bytes•Each adapter is given a globally unique address at manufacturing time•Address space is allocated to manufacturers•24 bits identify manufacturer•E.g., 0:0:15:* 3com adapter•Frame is received by all adapters on a LAN and dropped if address does not match•Special addresses•Broadcast – FF:FF:FF:FF:FF:FF is “everybody”•Range of addresses allocated to multicast•Adapter maintains list of multicast groups node is interested in4B/5B Encoding•Data coded as symbols of 5 line bits 4 data bits, so 100 Mbps uses 125 MHz.•Uses less frequency space than Manchester encoding•Uses NRI to encode the 5 code bits•Each valid symbol has at least two 1s: get dense transitions.•16 data symbols, 8 control symbols •Data symbols: 4 data bits•Control symbols: idle, begin frame, etc.•Example: FDDI.10Framing•A link layer function, defining which bits have which function.•Minimal functionality: mark the beginning and end of packets (or frames).•Some techniques:•out of band delimiters (e.g. FDDI 4B/5B control symbols)•frame delimiter characters with character stuffing•frame delimiter codes with bit stuffing•synchronous transmission (e.g. SONET)11Dealing with ErrorsStop and Wait Case•Packets can get lost, corrupted, or duplicated. •Error detection or correction turns corrupted packet in lost or correct packet•Duplicate packet: use sequence numbers.•Lost packet: time outs and acknowledgements.•Positive versus negative acknowledgements•Sender side versus receiver side timeouts•Window based flow control: more aggressive use of sequence numbers (see transport lectures).12SenderReceiver13Summary•CSMA/CD carrier sense multiple access with collision detection•Why do we need exponential backoff?•Why does collision happen?•Why do we need a minimum packet size?•How does this scale with speed? (Related to HW)•Ethernet•What is the purpose of different header fields?•What do Ethernet addresses look like?•What are some alternatives to Ethernet design?Outline•Link-Layer•Ethernet and CSMA/CD•Bridges/Switches•Network-Layer•Physical-Layer14Scale•What breaks when we keep adding people to the same wire?yak yak…15Scale•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…16Problem 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…1718Transparent Bridges / Switches•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 algorithmFrame 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 entries198711C98900AA2MAC AddressPortA21032C9A591199A323C908422301B2369011C2695519001190315Age36011611Bridge132Spanning Tree Bridges•More complex topologies can provide redundancy.•But can also create loops.•What is the problem with loops?•Solution: spanning tree20host host host host hosthost host host host hosthosthostBridge BridgeOutline•Link-Layer•Network-Layer•Forwarding/MPLS•IP•IP Routing•Misc•Physical-Layer2122Global Address ExampleReceiverPacketRSender234123412341R2R3R1RRR 3R 4R 3R23Source Routing
View Full Document