IP Forwarding Transport Protocols EE 122 Intro to Communication Networks Fall 2007 WF 4 5 30 in Cory 277 Vern Paxson TAs Lisa Fowler Daniel Killebrew Jorge Ortiz http inst eecs berkeley edu ee122 Materials with thanks to Jennifer Rexford Ion Stoica and colleagues at Princeton and UC Berkeley 1 Announcements Some of the Tuesday section students would prefer to keep it open Does it work to instead close the Monday section Let us know Please take the poll see the announcements page regarding lecture scheduling for Thanksgiving week Homework 1 due next Friday before lecture 2 1 Goals of Today s Lecture Summary of IP addressing structure How IP packet forwarding works Principles underlying transport layer services Service models UDP vs TCP De multiplexing via port numbers Reliable delivery Performance issues o Stop and Wait vs Sliding Window o Flow control Non goal details of TCP s operations 3 Are 32 bit Addresses Enough Not all that many unique addresses 232 4 294 967 296 just over four billion Plus some many reserved for special purposes And addresses are allocated in larger blocks And many devices need IP addresses Computers PDAs routers tanks toasters Long term solution perhaps larger address space IPv6 has 128 bit addresses 2128 3 403 1038 Short term solutions limping along with IPv4 Private addresses Net 10 etc Network address translation NAT Dynamically assigned addresses DHCP 4 2 Summary of IP Addressing 32 bit numbers identify interfaces Allocated in prefixes Non uniform hierarchy for scalability and flexibility Routing is based on CIDR A number of special purpose blocks reserved Address allocation ICANN RIR ISP customer network host Issues to be covered later How hosts get their addresses DHCP How to map from an IP address to a link address ARP 5 Packet Forwarding 6 3 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 7 Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 Serial3 0 2 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 126 255 103 0 24 Serial0 0 1 Serial2 2 3 Serial0 0 1 Serial1 1 1 201 10 7 17 11001001 00001010 00000111 00010001 8 4 Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 Serial3 0 2 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 126 255 103 0 24 Serial0 0 1 Serial2 2 3 Serial0 0 1 Serial1 1 1 201 10 7 17 11001001 00001010 00000111 00010001 192 11000000 9 Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 Serial3 0 2 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 126 255 103 0 24 Serial0 0 1 Serial2 2 3 Serial0 0 1 Serial1 1 1 201 10 7 17 11001001 00001010 00000111 00010001 4 00000100 83 01010011 128 10000000 10 5 Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 Serial3 0 2 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 126 255 103 0 24 Serial0 0 1 Serial2 2 3 Serial0 0 1 Serial1 1 1 201 10 7 17 11001001 00001010 00000111 00010001 11 Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 Serial3 0 2 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 126 255 103 0 24 Serial0 0 1 Serial2 2 3 Serial0 0 1 Serial1 1 1 201 10 7 17 11001001 00001010 00000111 00010001 12 6 Longest Prefix Match Forwarding Forwarding Table prefix outgoing link destination 192 0 0 0 4 Serial3 0 2 201 10 7 17 4 83 128 0 17 201 10 0 0 21 201 10 6 0 23 126 255 103 0 24 Serial0 0 1 Serial2 2 3 Serial0 0 1 Serial1 1 1 201 10 7 17 11001001 00001010 00000111 00010001 Serial0 0 1 Algorithmic problem how do we do this fast 13 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 150 000 200 000 entries And the router may have just a few nanoseconds before the next packet arrives Need greater efficiency to keep up with line rate Better algorithms Hardware implementations 14 7 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 00 10 0 00 1 100 11 101 11 15 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 o Delivered locally Packets to other hosts on the LAN e g 1 2 3 0 25 o Sent out the interface with LAN address ARP o Can tell they re local using subnet mask e g 255 255 255 128 Packets to external hosts any others o Sent out interface to local gateway o 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 16 8 What About Reaching the End Hosts 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 MAC address Media Access Control Layer 2 Programmed into 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 17 Role of Transport Layer Application layer Communication for specific applications E g HyperText Transfer Protocol HTTP File Transfer Protocol FTP Network News Transfer Protocol NNTP Transport layer Communication between processes e g socket Relies on network layer serves the application layer E g TCP and UDP Network layer Logical communication between nodes Hides details of the link technology E g IP 18 9 Transport Protocols Provide logical communication between application processes running on different hosts application transport network data link physical network data link physical network data link physical lo gi ca le nd e nd an network data link …
View Full Document
Unlocking...