Lecture 4: IP, Forwarding, and Switch FabricsOverview• Internet Protocol (v4)- What it provides and its header- Fragmentation and assembly• IP Addresses- Format and assignment: class-A, class-B, CIDR- Mapping, translation, and DHCP• Packet forwarding, circuits, source routing• Switch fabrics• Bisection bandwidthInternet Protocol Goal• Glue lower-level networks togetherR2R1H4H5H3H2H1Network 2 (Ethernet)Network 1 (Ethernet)H6Network 4(point-to-point)H7R3H8Network 3 (FDDI)The Hourglass, Revisited…FTPTCPUDPIPNET1NET2NETnHTTP NV TFTPInternet Protocol• Connectionless (datagram-based)• Best-effort delivery (unreliable service)- packets are lost- packets are delivered out of order- duplicate copies of a packet are delivered- packets can be delayed for a long timeIPv4 packet format0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9 0 10 1 2 3hdr lenvers TOS Total LengthIdentification Fragment offsetDMTTL Protocol hdr checksumSource IP addressDestination IP addressOptions PaddingF0FDataIP header details• Routing is based on destination address• TTL (time to live) decremented at each hop (avoids loops)- TTL mostly saves from routing loops- But other cool uses. . .• Fragmentation possible for large packets- Fragmented in network if crosses link w. small frame size- MF bit means more fragments for this IP packet- DF bit says “don’t fragment” (returns error to sender)• Following IP header is “payload” data- Typically beginning with TCP or UDP headerExample EncapsulationApplication dataTransport headerIP headerLink layer headerSending ReceivingIPv4 packet format0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9 0 10 1 2 3hdr lenvers TOS Total LengthIdentification Fragment offsetDMTTL Protocol hdr checksumSource IP addressDestination IP addressOptions PaddingF0FTCP or UDP headerTCP or UDP payloadOther IP Fields• Version: 4 (IPv4) for most packets, there’s also IPv6(lecture 12)• Header length (in case of options)• Type of Service (diffserv, we won’t go into this)• Protocol identifier (UDP: 17, TCP: 6, ICMP:1, whyis TCP earlier?)• Checksum over the header• Let’s look at a packet with wiresharkFragmentation & Reassembly• Each network has some maximum transmissionunit (MTU)• Strategy- Fragment when necessary (MTU < size of Datagram)- Source host tries to avoid fragmentationWhen fragment is lost, whole packet must be retransmitted!- Re-fragmentation is possible- Fragments are self-contained datagrams- Delay reassembly until destination host- Do not recover from lost fragmentsFragmentation exampleH1R1 R2 R3H8ETH FDDIPPP IP (376)PPP IP (512)PPP IP (512)(512)ETH IPETH IP(512)ETH IP(376)IP (1400) IP (1400)R1 R2 R3• Ethernet MTU is 1,500 bytes• PPP MTU is 576 bytes- R2 Must fragment IP packets to forward themFragmentation example(continued)• IP addresses plus ident fieldidentify fragments belonging tosame packet• MF (more fragments) bit is 1 in allbut last fragment• Fragment size multiple of 8 bytes- Multiply offset field by 8 to get fragmentposition within original packet(a)Ident = xStart of headerRest of header1400 data bytesOffset = 00(b)Ident = xStart of headerRest of header512 data bytesOffset = 01Ident = xRest of header512 data bytesOffset = 641Start of headerIdent = xStart of headerRest of header376 data bytesOffset = 1280TCP Path MTU discovery• Problem: How does TCP know what MSS to use?- On local network, obvious, but for more distant machines?• Solution: Exploit ICMP—another protocol on IP- ICMP for control messages, not intended for buik data- IP supports DF (don’t fragment) bit in IP header- Set DF to get ICMP can’t fragment when segment too big• Can do binary search on packet sizes- But better: Base algorithm on most common MTUs- Common algorithm may underestimate slightly (betterthan overestimating and losing packet)- See RFC1191 for details• Is TCP a layer on top of IP?IP Address Format, Translation, and DHCPFormat of IP addresses• Globally unique (or made to seem that way)• Hierarchical: network + host- Aggregating addresses saves memory in routers, simplifiesrouting (as we will see next lecture)• Originally, routing prefix embedded in address:Network Host7 240(a)Network Host14 161 0(b)Network Host21 81 1 0(c)(Still hear “class A,” “class B,” “class C”)• Now, routing info on “CIDR” blocks, addr+prefix-len- E.g., 171.67.0.0/16Translating IP to lower-level addresses• Map IP addresses into physical addresses- E.g., Ethernet address of destination host- Or Ethernet address of next hop router• Techniques- Encode link layer address in host part of IP address(option is available, but only in IPv6)- Each network node maintains a lookup table (link→IP)• ARP – address resolution protocol- Table of IP to link layer address bindings- Broadcast request if IP address not in table- Everybody learns physical address of requesting node (broadcast)- Target machine responds with its link layer address- Table entries are discarded if not refreshedNeed for Address Translation• Layer 2 (link) address names a hardware interface- E.g., my wireless ethernet 00:26:b0:f9:25:cf• Layer 3 (network) address names a host- E.g., www06.stanford.edu is 171.67.216.19- (lecture 8 will explain mapping from name to IP)• Details:- A single host can have multiple hardware interfaces, somultiple link layer addresses for a single network address- A node is asked to forward a packet to another IP address:out which hardware interface does it send the packet?Arp Ethernet packet formatTargetHardwareAddr (bytes 2–5)TargetProtocolAddr (bytes 0–3)SourceProtocolAddr (bytes 2–3)Hardware type = 1 ProtocolType = 0x0800SourceHardwareAddr (bytes 4–5)TargetHardwareAddr (bytes 0–1)SourceProtocolAddr (bytes 0–1)HLen = 48 PLen = 32 OperationSourceHardwareAddr (bytes 0–3)0 8 16 31Internet Control Message Protocol (ICMP)• Echo (ping)• Redirect (from router to source host)• Destination unreachable (protocol, port, or host)• TTL exceeded (so datagrams don’t cycle forever)• Checksum failed• Reassembly failed• Cannot fragment• Many ICMP messages include part of packet thattriggered them- Example: TracerouteICMP message format0 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 9 0 10 1 2 320-byte IP headerChecksumCodeTypedepends on type/code(protocol = 1—ICMP)•Types include:- echo, echo reply, destination unreachable, time exceeded, . ..- See
View Full Document
Unlocking...