115-441 Computer NetworkingLecture 9 – IP Packets, RoutersLecture 9: 2-8-05 2Overview• Last lecture• How does choice of address impact network architecture and scalability?• What do IP address look like?• How to get an IP address?• This lecture• What do IP packets look like?• How to handle some differences between LANs?• How do routers work?Lecture 9: 2-8-05 3Outline• IP Packet Format• Router Internals• Route LookupLecture 9: 2-8-05 4IP Service Model• Low-level communication model provided by Internet• Datagram• Each packet self-contained• All information needed to get to destination• No advance setup or connection maintenance• Analogous to letter or telegram0 4 8 12 1619 24 2831version HLen TOS LengthIdentifier Flag OffsetTTL Protocol ChecksumSource AddressDestination AddressOptions (if any)DataHeaderIPv4 PacketFormat2Lecture 9: 2-8-05 5IPv4 Header Fields• Version: IP Version• 4 for IPv4• HLen: Header Length• 32-bit words (typically 5)• TOS: Type of Service• Priority information• Length: Packet Length• Bytes (including header)• Header format can change with versions• First byte identifies version• Length field limits packets to 65,535 bytes• In practice, break into much smaller packets for network performance considerations048121619 242831ver-sionHLenTOS LengthIdentifierFlagsOffsetTTL Protocol ChecksumSource AddressDestination AddressOptions (if any)DataLecture 9: 2-8-05 6IPv4 Header Fields• Identifier, flags, fragment offset Æ used primarily for fragmentation• Time to live• Must be decremented at each router• Packets with TTL=0 are thrown away• Ensure packets exit the network• Protocol• Demultiplexing to higher layer protocols• TCP = 6, ICMP = 1, UDP = 17…• Header checksum• Ensures some degree of header integrity• Relatively weak – 16 bit• Options• E.g. Source routing, record route, etc.• Performance issues• Poorly supported048121619 242831ver-sionHLenTOS LengthIdentifierFlagsOffsetTTL Protocol ChecksumSource AddressDestination AddressOptions (if any)DataLecture 9: 2-8-05 7IPv4 Header Fields• Source Address• 32-bit IP address of sender• Destination Address• 32-bit IP address of destination• Like the addresses on an envelope• Globally unique identification of sender & receiver0 4 8 12 16 19 24 28 31ver-sionHLenTOS LengthIdentifierFlagsOffsetTTL Protocol ChecksumSource AddressDestination AddressOptions (if any)DataLecture 9: 2-8-05 8IP Delivery Model• Best effort service• Network will do its best to get packet to destination• Does NOT guarantee:• Any maximum latency or even ultimate success• Sender will be informed if packet doesn’t make it• Packets will arrive in same order sent• Just one copy of packet will arrive• Implications• Scales very well• Higher level protocols must make up for shortcomings• Reliably delivering ordered sequence of bytes Æ TCP• Some services not feasible• Latency or bandwidth guarantees3Lecture 9: 2-8-05 9IP Fragmentation• Every Network has Own Maximum Transmission Unit (MTU)• Largest IP datagram it can carry within its own packet frame• E.g., Ethernet is 1500 bytes• Don’t know MTUs of all intermediate networks in advance• IP Solution• When hit network with small MTU, fragment packets• Might get further fragmentation as proceed fartherhosthostrouterrouterMTU = 4000MTU = 1500MTU = 2000Lecture 9: 2-8-05 10Reassembly• Where to do reassembly?• End nodes or at routers?• End nodes• Avoids unnecessary work where large packets are fragmented multiple times • If any fragment missing, delete entire packet• Dangerous to do at intermediate nodes• How much buffer space required at routers?• What if routes in network change?• Multiple paths through network• All fragments only required to go through destinationLecture 9: 2-8-05 11Fragmentation Related Fields• Length• Length of IP fragment• Identification • To match up with other fragments• Flags• Don’t fragment flag• More fragments flag• Fragment offset• Where this fragment lies in entire IP datagram• Measured in 8 octet units (13 bit field)Lecture 9: 2-8-05 12IP Fragmentation Example #1hostrouterMTU = 4000IPHeaderIPDataLength = 3820, M=04Lecture 9: 2-8-05 13IP Fragmentation Example #2routerrouterMTU = 2000IPHeaderIPDataLength = 3820, M=03800 bytesIPHeaderIPDataLength = 2000, M=1, Offset = 01980 bytesIPDataIPHeaderLength = 1840, M=0, Offset = 19801820 bytesLecture 9: 2-8-05 14IP Fragmentation Example #3IPHeaderIPDataLength = 2000, M=1, Offset = 01980 bytesIPDataIPHeaderLength = 1840, M=0, Offset = 19801820 byteshostrouterMTU = 1500IPHeaderIPDataLength = 1500, M=1, Offset = 01480 bytesIPHeaderIPDataLength = 520, M=1, Offset = 1480500 bytesIPHeaderIPDataLength = 1500, M=1, Offset = 19801480 bytesIPHeaderIPDataLength = 360, M=0, Offset = 3460340 bytesLecture 9: 2-8-05 15IP Reassembly• Fragments might arrive out-of-order• Don’t know how much memory required until receive final fragment• Some fragments may be duplicated• Keep only one copy• Some fragments may never arrive• After a while, give up entire processIPHeaderIPDataLength = 1500, M=1, Offset = 0IPHeaderIPDataLength = 520, M=1, Offset = 1480IPHeaderIPDataLength = 1500, M=1, Offset = 1980IPHeaderIPDataLength = 360, M=0, Offset = 3460IPDataIPDataIPDataIPDataLecture 9: 2-8-05 16Fragmentation and Reassembly Concepts• Demonstrates many Internet concepts• Decentralized• Every network can choose MTU• Connectionless• Each (fragment of) packet contains full routing information• Fragments can proceed independently and along different routes• Best effort• Fail by dropping packet• Destination can give up on reassembly• No need to signal sender that failure occurred• Complex endpoints and simple routers• Reassembly at endpoints5Lecture 9: 2-8-05 17Fragmentation is Harmful• Uses resources poorly• Forwarding costs per packet• Best if we can send large chunks of data• Worst case: packet just bigger than MTU• Poor end-to-end performance• Loss of a fragment • Path MTU discovery protocol Æ determines minimum MTU along route• Uses ICMP error messages• Common theme in system design• Assure correctness by implementing complete protocol• Optimize common cases to avoid full complexityLecture 9: 2-8-05 18Internet Control Message Protocol (ICMP)• Short messages used to send error & other control information• Examples• Ping request /
View Full Document