1 15-744 Computer Networks Background Material 1: Getting stuff from here to there Or How I learned to love OSI layers 1-3 Outline • Link-Layer • Ethernet and CSMA/CD • Bridges/Switches • Network-Layer • Physical-Layer 3 Ethernet MAC (CSMA/CD) Packet? Sense Carrier Discard Packet Send Detect Collision Jam channel b=CalcBackoff(); wait(b); attempts++; No Yes attempts < 16 attempts == 16 • Carrier Sense Multiple Access/Collision Detection Ethernet 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}2 Collisions Time A B C 6 Minimum Packet Size • What if two people sent really small packets • How do you find collision? • Consider: • Worst case RTT • How fast bits can be sent Ethernet 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 collision 8 Ethernet Frame Structure • Sending adapter encapsulates IP datagram (or other network layer protocol packet) in Ethernet frame3 9 Ethernet 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 in 4B/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. 10 Framing • 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) 11 Dealing with Errors Stop 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). 12 Sender Receiver4 13 Summary • 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-Layer Scale • What breaks when we keep adding people to the same wire? yak yak… Scale • 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…5 Problem 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… 18 Transparent 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 frames 2) Learning addresses/host locations 3) Spanning tree algorithm Frame 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 entries 19 8711C98900AA 2 MAC Address Port A21032C9A591 1 99A323C90842 2 301B2369011C 2 695519001190 3 15 Age 36 01 16 11 Bridge 1 3 2 Spanning Tree Bridges • More complex topologies can provide redundancy. • But can also create loops. • What is the problem with loops? • Solution: spanning tree 20 host host host host host host host host host host host host Bridge Bridge6 Outline • Link-Layer • Network-Layer • Forwarding/MPLS • IP • IP Routing • Misc • Physical-Layer 21 9-21-06 Lecture 8: Bridging/Addressing/Forwarding 22 Global Address Example Receiver Packet R Sender 234123412341R2 R3 R1 R R R 3 R 4 R 3 R 23 Virtual Circuit IDs/Switching: Label (“tag”) Swapping • Global VC ID allocation -- ICK! Solution: Per-link uniqueness. Change VCI each hop. Input Port Input VCI Output Port Output VCI R1: 1 5 3 9 R2: 2 9 4 2 R4: 1 2 3 5 A B R2 R1 R3 R4 Dst 1 2 3 4 3 3 3 1 1 1 2 2 4 4 4 2 9-21-06 Lecture 8: Bridging/Addressing/Forwarding 24 Simplified Virtual Circuits Example Receiver Packet conn 5 3 Sender 2341conn 5 4 23412341conn 5 3 R2 R3 R1 5 5 5 57 9-20-07 Lecture 7: Addressing/Forwarding 25 Comparison Source Routing Global Addresses Header Size Worst OK – Large address Router Table Size None
View Full Document