DOC PREVIEW
Berkeley ELENG 122 - IP Forwarding & Transport Protocols

This preview shows page 1-2-23-24 out of 24 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 24 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

11IP Forwarding & Transport ProtocolsEE 122: Intro to Communication NetworksFall 2007 (WF 4-5:30 in Cory 277)Vern PaxsonTAs: Lisa Fowler, Daniel Killebrew & Jorge Ortizhttp://inst.eecs.berkeley.edu/~ee122/Materials with thanks to Jennifer Rexford, Ion Stoica,and colleagues at Princeton and UC Berkeley2Announcements• Some of the Tuesday section students wouldprefer to keep it open– Does it work to instead close the Monday section?– Let us know• Please take the poll (see the announcementspage) regarding lecture scheduling forThanksgiving week• Homework #1 due next Friday before lecture23Goals of Today’s Lecture• Summary of IP addressing structure• How IP packet forwarding works• Principles underlying transport-layerservices–Service models (UDP vs. TCP)–(De)multiplexing via port numbers–Reliable delivery–Performance issues:o Stop-and-Wait vs. Sliding Windowo Flow control–Non-goal: details of TCP’s operations4Are 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)35Summary 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)6Packet Forwarding47Hop-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 withmatch• Where does forwarding table come from?–Routing algorithms (or static configs)8Longest-Prefix-Match Forwarding201.10.7.17destinationForwarding Tableoutgoing linkSerial1/1.1126.255.103.0/24Serial0/0.1201.10.6.0/23Serial2/2.3201.10.0.0/21Serial0/0.14.83.128.0/17Serial3/0.2192.0.0.0/4prefix201: 11001001 10: 00001010 7: 00000111 17: 0001000159Longest-Prefix-Match Forwarding201.10.7.17destinationForwarding Tableoutgoing linkSerial1/1.1126.255.103.0/24Serial0/0.1201.10.6.0/23Serial2/2.3201.10.0.0/21Serial0/0.14.83.128.0/17Serial3/0.2192.0.0.0/4prefix201: 11001001 10: 00001010 7: 00000111 17: 00010001192: 11000000201: 11001001 10: 00001010 7: 00000111 17: 0001000110Longest-Prefix-Match Forwarding201.10.7.17destinationForwarding Tableoutgoing linkSerial1/1.1126.255.103.0/24Serial0/0.1201.10.6.0/23Serial2/2.3201.10.0.0/21Serial0/0.14.83.128.0/17Serial3/0.2192.0.0.0/4prefix201: 11001001 10: 00001010 7: 00000111 17: 00010001 4: 00000100 83: 01010011128: 10000000611Longest-Prefix-Match Forwarding201.10.7.17destinationForwarding Tableoutgoing linkSerial1/1.1126.255.103.0/24Serial0/0.1201.10.6.0/23Serial2/2.3201.10.0.0/21Serial0/0.14.83.128.0/17Serial3/0.2192.0.0.0/4prefix201: 11001001 10: 00001010 7: 00000111 17: 0001000112Longest-Prefix-Match Forwarding201.10.7.17destinationForwarding Tableoutgoing linkSerial1/1.1126.255.103.0/24Serial0/0.1201.10.6.0/23Serial2/2.3201.10.0.0/21Serial0/0.14.83.128.0/17Serial3/0.2192.0.0.0/4prefix201: 11001001 10: 00001010 7: 00000111 17: 00010001713Longest-Prefix-Match Forwarding• Algorithmic problem: how do we do this fast?201.10.7.17destinationForwarding TableSerial0/0.1outgoing linkSerial1/1.1126.255.103.0/24Serial0/0.1201.10.6.0/23Serial2/2.3201.10.0.0/21Serial0/0.14.83.128.0/17Serial3/0.2192.0.0.0/4prefix201: 11001001 10: 00001010 7: 00000111 17: 0001000114Simple 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 implementations815Patricia 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 algorithms0 100 10 11100 10100*0*11*16How 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 gatewayo 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)917What 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 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)hosthost hostLAN...router1.2.3.41.2.3.7 1.2.3.15618Role of Transport Layer• Application layer– Communication for specific applications– E.g., HyperText Transfer Protocol (HTTP), File TransferProtocol (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


View Full Document

Berkeley ELENG 122 - IP Forwarding & Transport Protocols

Documents in this Course
Lecture 6

Lecture 6

22 pages

Wireless

Wireless

16 pages

Links

Links

21 pages

Ethernet

Ethernet

10 pages

routing

routing

11 pages

Links

Links

7 pages

Switches

Switches

30 pages

Multicast

Multicast

36 pages

Switches

Switches

18 pages

Security

Security

16 pages

Switches

Switches

18 pages

Lecture 1

Lecture 1

56 pages

OPNET

OPNET

5 pages

Lecture 4

Lecture 4

16 pages

Ethernet

Ethernet

65 pages

Models

Models

30 pages

TCP

TCP

16 pages

Wireless

Wireless

48 pages

Load more
Download IP Forwarding & Transport Protocols
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view IP Forwarding & Transport Protocols and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view IP Forwarding & Transport Protocols 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?