Names Addresses Names EE 122 IP Forwarding and Transport Protocols Scott Shenker Addresses http inst eecs berkeley edu ee122 Materials with thanks to Vern Paxson Jennifer Rexford and colleagues at UC Berkeley Human readable No location semantics E g yahoo com sky cs berkeley edu 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 1 Names Addresses 2 Hop by Hop Packet Forwarding What is Leonardo da Vinci Each router has a forwarding table What is Seven of Nine Upon receiving a packet Depends on the context An address in one context can become a name in another context Maps destination addresses to outgoing interfaces links 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 3 Longest Prefix Match Forwarding 4 Longest Prefix Match Forwarding Forwarding Table prefix destination 192 0 0 0 4 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 7 17 11001001 00001010 00000111 00010001 Forwarding Table outgoing link prefix outgoing link 2 destination 192 0 0 0 4 2 1 3 201 10 7 17 4 83 128 0 17 201 10 0 0 21 1 3 201 10 7 17 201 10 6 0 23 2 126 255 103 0 24 3 11001001 00001010 00000111 00010001 201 10 6 0 23 2 126 255 103 0 24 3 192 11000000 5 6 1 Longest Prefix Match Forwarding Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 2 201 10 7 17 4 83 128 0 17 1 201 10 0 0 21 201 10 6 0 23 3 2 201 10 7 17 11001001 00001010 00000111 00010001 Forwarding Table prefix outgoing link destination 192 0 0 0 4 2 201 10 7 17 4 83 128 0 17 1 201 10 0 0 21 201 10 6 0 23 3 2 201 10 7 17 126 255 103 0 24 3 4 00000100 83 01010011 128 10000000 11001001 00001010 00000111 00010001 126 255 103 0 24 3 201 11001001 10 00001010 0 00000000 7 Longest Prefix Match Forwarding Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 2 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 1 3 2 201 10 7 17 11001001 00001010 00000111 00010001 Forwarding Table 126 255 103 0 24 3 1 3 2 11001001 00001010 00000111 00010001 126 255 103 0 24 3 Algorithmic problem how do we do this fast 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 Today that means 200 000 250 000 entries And the router may have just a few nanoseconds before the next packet arrives Better algorithms Hardware implementations 2 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 10 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 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 Need greater efficiency to keep up with line speed 192 0 0 0 4 201 10 7 17 Patricia Tree Overhead is linear in size of the forwarding table destination 9 Scan the forwarding table one entry at a time outgoing link 2 Simple Algorithms Are Too Slow prefix 201 10 7 17 201 11001001 10 00001010 6 00000110 8 11 0 00 1 0 0 0 1 1 11 12 2 How Does Sending End Host Forward What About Reaching the End Hosts 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 does the last router reach the destination 1 2 3 4 1 2 3 7 1 2 3 156 host host host LAN router Each interface has a persistent global identifier How this information is learned Static setting of address subnet mask and gateway Or Dynamic Host Configuration Protocol DHCP Constructing an address resolution table 13 MAC address Media Access Control Layer 2 Programmed into Network Interface Card NIC Usually flat address structure i e no hierarchy Mapping MAC address to from IP address Address Resolution Protocol ARP 14 Transport Protocols nd e application transport network data link physical 16 4 bit 8 bit 4 bit Version Header Type of Service Length TOS Datagram messaging service UDP No frills extension of best effort IP Multiplexing demultiplexing among processes Reliable in order delivery TCP 8 bit Time to Live TTL 16 bit Total Length Bytes 3 bit Flags 16 bit Identification network data link physical network data link physical 15 Internet Transport Protocols network data link physical t or sp an tr network data link physical network data link physical d en Transport Layer application transport network data link physical l ca gi lo 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 8 bit Protocol 13 bit Fragment Offset 16 bit Header Checksum 32 bit Source IP Address Connection set up tear down Discarding of corrupted packets Retransmission of lost packets Flow control Congestion control 32 bit Destination IP Address Options if any Services not available Delay guarantees Bandwidth guarantees Sessions that survive change of IP address Payload 17 3 4 bit 8 bit 4 bit Version Header Type of Service Length TOS 3 bit Flags 16 bit Identification 8 bit Time to Live TTL 8 bit Protocol 4 16 bit Total Length Bytes 5 8 bit Type of Service TOS 16 bit Identification 13 bit Fragment Offset 8 bit Time to Live TTL 16 bit Header Checksum 16 bit Total Length Bytes 3 bit Flags 8 bit Protocol 13 bit Fragment Offset 16 bit Header Checksum 32 bit Source IP Address 32 bit Source IP Address 32 bit Destination IP Address 32 bit Destination IP Address Options if any Payload Payload 4 5 8 bit Type of Service TOS 3 bit Flags 16 bit Identification 8 bit Time to Live TTL 6 TCP 17 UDP 4 16 bit Total Length Bytes 5 8 bit Type of Service TOS 3 bit Flags 16 bit Identification 13 bit …
View Full Document