1 1 EE 122: IP Forwarding and Transport Protocols Scott Shenker http://inst.eecs.berkeley.edu/~ee122/ (Materials with thanks to Vern Paxson, Jennifer Rexford, and colleagues at UC Berkeley) 2 Names & Addresses Names Human readable No location semantics E.g., “yahoo.com”, “sky.cs.berkeley.edu” Addresses Easy to manipulate in software (usually fixed length) Location semantics E.g., 206.190.60.37, 128.32.37.169.229 But sometimes not clear cut… 3 Names & Addresses What is “Leonardo da Vinci”? What is “Seven-of-Nine”? Depends on the context An address in one context can become a name in another context 4 Hop-by-Hop Packet Forwarding Each router has a forwarding table Maps destination addresses… … to outgoing interfaces (= links) Upon receiving a packet Inspect the destination IP address in the header Index into the table Find the longest prefix match Forward packet out interface associated with match Where does forwarding table come from? Routing algorithms (or static configs) 5 Longest-Prefix-Match Forwarding 201.10.7.17 destination Forwarding Table outgoing link 192.0.0.0/4 2 4.83.128.0/17 1 201.10.0.0/21 3 201.10.6.0/23 2 126.255.103.0/24 3 prefix 201: 11001001! 10: 00001010" 7: 00000111" 17: 00010001"6 Longest-Prefix-Match Forwarding 201.10.7.17 destination Forwarding Table outgoing link 192.0.0.0/4 2 4.83.128.0/17 1 201.10.0.0/21 3 201.10.6.0/23 2 126.255.103.0/24 3 prefix 201: 11001001! 10: 00001010" 7: 00000111" 17: 00010001"192: 11000000"201: 11001001! 10: 00001010" 7: 00000111" 17: 00010001"2 7 Longest-Prefix-Match Forwarding 201.10.7.17 destination Forwarding Table outgoing link 192.0.0.0/4 2 4.83.128.0/17 1 201.10.0.0/21 3 201.10.6.0/23 2 126.255.103.0/24 3 prefix 201: 11001001! 10: 00001010" 7: 00000111" 17: 00010001" 4: 00000100! 83: 01010011"128: 10000000"8 Longest-Prefix-Match Forwarding 201.10.7.17 destination Forwarding Table outgoing link 192.0.0.0/4 2 4.83.128.0/17 1 201.10.0.0/21 3 201.10.6.0/23 2 126.255.103.0/24 3 prefix 201: 11001001! 10: 00001010" 7: 00000111" 17: 00010001" 201: 11001001 !10: 00001010"0: 00000000"9 Longest-Prefix-Match Forwarding 201.10.7.17 destination Forwarding Table outgoing link 192.0.0.0/4 2 4.83.128.0/17 1 201.10.0.0/21 3 201.10.6.0/23 2 126.255.103.0/24 3 prefix 201: 11001001! 10: 00001010" 7: 00000111" 17: 00010001" 201: 11001001 !10: 00001010"6: 00000110"10 Longest-Prefix-Match Forwarding Algorithmic problem: how do we do this fast? 201.10.7.17 destination Forwarding Table 2 outgoing link 192.0.0.0/4 2 4.83.128.0/17 1 201.10.0.0/21 3 201.10.6.0/23 2 126.255.103.0/24 3 prefix 201: 11001001! 10: 00001010" 7: 00000111" 17: 00010001"11 Simple Algorithms Are Too Slow Scan the forwarding table one entry at a time See if the destination matches the entry If so, check the size of the mask for the prefix Keep track of the entry with longest-matching prefix Overhead is linear in size of the forwarding table Today, that means 200,000-250,000 entries! And, the router may have just a few nanoseconds … before the next packet arrives Need greater efficiency to keep up with line speed Better algorithms Hardware implementations 12 Patricia Tree Store the prefixes as a tree One bit for each level of the tree Some nodes correspond to valid prefixes (w/ next-hop interfaces) When a packet arrives Traverse the tree based on the destination address Stop upon reaching the longest matching prefix Running time: scales with # bits in address (but takes more memory) Lot of work on still-faster algorithms 0 1 0 0 1 0 1 00* 0* 11*3 13 How Does Sending End Host Forward? No need to run a routing protocol Packets to the host itself (e.g., 1.2.3.4/32) Delivered locally Packets to other hosts on the LAN (e.g., 1.2.3.0/25) Sent out the interface with LAN address Can tell they’re local using subnet mask (e.g., 255.255.255.128) Packets to external hosts (any others) Sent out interface to local gateway I.e., IP router on the LAN How this information is learned Static setting of address, subnet mask, and gateway Or: Dynamic Host Configuration Protocol (DHCP) 14 What About Reaching the End Hosts? How does the last router reach the destination? Each interface has a persistent, global identifier MAC address (Media Access Control) - Layer 2 Programmed into Network Interface Card (NIC) Usually flat address structure (i.e., no hierarchy) Constructing an address resolution table Mapping MAC address to/from IP address Address Resolution Protocol (ARP) host!host! host!LAN!...!router!1.2.3.4 1.2.3.7 1.2.3.156 15 Transport Layer 16 Transport Protocols Provide logical communication between application processes running on different hosts Run on end hosts Sender: breaks application messages into segments, and passes to network layer Receiver: reassembles segments into messages, passes to application layer Multiple transport protocol available to applications Internet: TCP and UDP (mainly) application transport network data link physical application transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical logical end-end transport 17 Internet Transport Protocols Datagram messaging service (UDP) No-frills extension of “best-effort” IP Multiplexing/demultiplexing among processes Reliable, in-order delivery (TCP) Connection set-up & tear-down Discarding of corrupted packets Retransmission of lost packets Flow control Congestion control Services not available Delay guarantees Bandwidth guarantees Sessions that survive change-of-IP-address 4-bit Version 4-bit Header Length 8-bit Type of Service (TOS) 16-bit Total Length (Bytes) 16-bit Identification 3-bit Flags 13-bit Fragment Offset 8-bit Time to Live (TTL) 8-bit Protocol 16-bit Header Checksum 32-bit Source IP Address 32-bit Destination IP Address Options (if any) Payload4 4-bit Version 4-bit
View Full Document
Unlocking...