Fragmentation Considered Harmful
`
`Christopher A. Kent
`Jeffrey C. Mogul
`
`Digital Equipment Corporation
`Western Research Lab
`
`(Originally published in Proc. SIGCOMM ‘87, Vol. 17, No. 5, October 1987)
`
`Abstract
`
`Internetworks can be built from many different kinds of networks, with varying limits on
`maximum packet size. Throughput is usually maximized when the largest possible packet is
`sent; unfortunately, some routes can carry only very small packets. The IP protocol allows a
`gateway to fragment a packetif it is too large to be transmitted. Fragmentation is at best a
`necessary evil; it can lead to poor performance or complete communication failure. There are a
`variety of ways to reduce the likelihood of fragmentation; some can be incorporated into exist-
`ing IP implementations without changes in protocol specifications. Others require new
`protocols, or modifications to existing protocols.
`
`1. Introduction
`
`Internetworks built of heterogeneous networks are
`valuable because they insulate higher-level protocols
`from changes in network technology, because they al-
`low universal communication without the expense of
`constructing a homogeneous universal
`infrastructure,
`and because they allow the use of different network
`technologies as appropriate to both local-area and long-
`haul
`links. Most datagram networks set a maximum
`limit on tile size of packets they carry,
`to simplify
`packet buffering in the nodes and to limit how long one
`packet can lie up the link. In a heterogeneous interned
`such as the DARPAIP Internet, these packet-size limits,
`known as MTUs(for maximum transmission unit) vary
`widely from 254 bytes for Packet Radio networks to
`2000 bytes for the Wideband Satellite Network [22];
`since nobody knows exactly what is connected to the
`Internet, the range in MTUs maybe even broader.
`
`In general, it is better to use a few large packets instead
`of many small packets to carry a given amount ofdata,
`because much ofthe cost of packetized communication
`is per-packet rather than per-byte. On a high-speed
`LAN,
`throughput can increase almost
`linearly with
`packet size over a wide range of sizes. Therefore, we
`prefer to make our packetsas large as possible.
`
`This desire for large packets conflicts with the variation
`in MTUsacross an internet. We want to send large
`
`packets but some network along the packets’ path may
`not be able to carry them. One approachto this dilemma
`is fragmentation when a node must transmit a packet
`that is larger than the MTU ofthe network.it breaks the
`packet into several smaller fragments and sends them
`instead.If the fragmentsare all sent along the same data
`link and are immediately reassembled at the next node,
`this is called transparent or intra-network fragmenta-
`tion. If the fragments are allowed to follow independent
`routes, and are reassembled only upon reaching their
`ultimate destination this is called inter-network frag-
`mentation. A good discussion of both methods, in more
`detail, may be found in Shoch [23].
`
`In this paper, drawing on experience with a large
`heterogeneous internetwork, we examine fragmentation
`in the context of the IP protocol [18]. IP supports the
`use
`of
`inter-network
`fragmentation.
`(Transparent
`fragmentation may be also be used as long asit is
`invisible to the IP layer.) Fragmentation appearsatfirst
`to be an elegant solution to the problem, but subtle
`complications arise in real networks that can result in
`poor performanceor even total communicationfailure.
`
`Experience with inter-network fragmentation in the IP
`Internet has convinced us that it is something to avoid.
`In section 2 we compare the advantages and dis-
`advantages of fragmentation,
`in order to justify this
`assertion. We then discuss,
`in section 3, a variety of
`schemesfor avoiding or recovering from fragmentation
`
`ACM SIGCOMM
`
`-75-
`
`Computer Communication Review
`
`INTEL EX. 1420.001
`
`INTEL EX. 1420.001
`
`

`

`2. Whatis wrong with fragmentation?
`
`The arguments in favor of fragmentation are straight-
`forward. Fragmentation allows higher level protocols to
`be
`unconcerned with
`the
`characteristics of
`the
`transmission channel, and to send data in conveniently
`sized pieces. Sending larger quantities of data in each IP
`datagram minimizes the bookkeeping overhead asso-
`ciated with managing the data. (See section 3.5 fowl
`specific example.)
`
`Fragmentation allows the source host to deal with routes
`having different MTUs without having to know what
`path packet are taking. The safest strategy is for the
`source to send very small datagrams, at a great loss of
`efficiency. Fragmentation allows the source to choose a
`size that is “reasonable” and, when that size proves to
`be too large, provides a mechanism that allows data to
`continueto get through.
`
`fragmentation allows protocols to optimize
`Finally,
`performance for high bandwidth connections. Emerging
`network technologies have larger and larger MTUs.
`Mostlocal networks have MTUslarge enough to send
`1024 bytes of user data plus associated overhead in a
`single packet; new technologies will allow ten times
`that. Fragmentation provides a mechanism for deciding
`the actual packet size as late as possible. It especially
`allows protocols to avoid choosing to send small
`datagrams until absolutely necessary. Protocols can
`choose large segment sizes to take advantage of the
`large MTU in a local network, and rely on fragmenta-
`tion at gateways to send the segments through networks
`with small MTUs when needed. If datagrams must
`traverse a route consisting of several high-MTU links
`followed by a low-MTUlink, by delaying the use of
`small packets until
`the low-MTU link is
`reached,
`fragmentation allows the use of large packets on the
`initial high MTU links, and thus uses those links more
`efficiently.
`
`The arguments against fragmentation fall
`categories
`
`into three
`
`e
`
`e
`
`of
`use
`inefficient
`causes
`Fragmentation
`resources: Poor choice of fragment sizes can
`greatly increase the cost of delivering a datagram.
`Additional bandwidth is used for the additional
`header information, intermediate gateways must
`expend computational resources to make addi-
`tional routing decisions, and the receiving host
`must reassemble the fragments.
`
`Loss of fragments leads to degraded per-
`formance: Reassembly of IP fragments is not
`very robust. Loss of a single fragment requires
`the higher level protocol to retransmit all of the
`
`data in the original datagram, even if most of the
`fragments were received correctly.
`
`e
`
`the
`reassembly is hard: Given
`Efficient
`likelihood of lost fragments and the information
`present in the IP header, there are manysituations
`in which the reassembly process, though straight-
`forward, yields lower than desired performance.
`
`2.1. An overview of fragmentation in IP
`
`IP is a protocol providing unreliable delivery of
`datagrams. IP datagrams are encapsulated in network-
`specific packets. Gateways may fragment an incoming
`packet if it will not fit in a single outgoing packet; in
`this case, each fragment is sent as a separate packet.
`The [P header contains several fields that are used to
`manage fragmentation [18]:
`
`e
`
`e
`
`e
`
`Identification: A 16-bit field assigned by the
`sender to aid in assembling the fragments of a
`datagram. The tuple (source, destination, proto-
`col, identification) for a given datagram must be
`unique over all existing datagrams. When a
`packet is fragmented, the value of the Identifica-
`tion field of the original packet is copied into
`each fragment.
`
`Timeto live (TTL): An8-bit field that specifies
`the maximum time, measured in seconds, that the
`packet may remain in the Internet system. If TTL
`contains the value zero,
`the packet must be
`discarded. The TTL must be decreased byat least
`one every time the packet passes through a
`gateway, even if the time required to process the
`packetis less than a second. Thus, the TTL field
`is an upper bound on packetlifetime.
`
`Fragmentoffset: A 13-bit field that identifies the
`fragmentlocation, relative to the beginning of the
`original, unfragmented datagram. Fragment off-
`sets are in units of 8 bytes.
`
`indicates
`field that
`e More fragments: A I-bit
`whether or not this is the last fragment of the
`datagram.
`
`The reassembly process consists of matching the
`protocol and identification fields of incoming fragments
`with those of fragments already held, and coalescing the
`data into complete datagrams. Fragments must be
`discarded if their TTL expires while they are held for
`reassembly.
`(For more details of
`the reassembly
`algorithm, see [5].)
`
`level protocols such as TCP (Transmission
`Higher
`Control Protocol) [19] use IP as a basis to implement a
`reliable connection between two client processes.
`Portions of the data stream known as segments are sent
`in individual IP datagrams, along with control informa-
`
`ACM SIGCOMM
`
`-76-
`
`Computer Communication Review
`
`INTEL EX. 1420.002
`
`INTEL EX. 1420.002
`
`

`

`tion used by the cooperating TCP processes to ensure
`reliable communication.
`In particular, TCP uses a
`sequence number that covers individual bytes in the
`data stream, and an acknowledgment mechanism that
`allows the receiving process to tell the sender “TI have
`correctly received all data up to and including sequence
`number 7.”
`
`2.2. Fragmentation causesinefficient resource usage
`
`Consider the costs associated with sending a packet.
`Each time it passes through a gateway, there is some
`constant computational overhead to make
`routing
`decisions, modify the packet header, compute the new
`checksum, and move the packet between the appropriate
`incoming and outgoing queues. In addition, a portion of
`the available bandwidth on the incoming and outgoing
`interfaces is consumed.
`In many cases,
`the constant
`computational overhead dominates the cost. Input and
`output may be overlapped using DMA devices;
`in a
`typical uniprocessor gateway,
`there is no way to
`parallelize the computational overhead.
`
`Fragmenting at an IP gateway, rather than having the
`host choose the appropriate segment size to avoid
`fragmentation, may lead to suboptimal use of gateway
`resources and network bandwidth. Consider a TCP
`processthat tries to send 1024 data bytes across a route
`that includes the ARPAnet, which has an MTU of 1006
`bytes. The IP and TCP headers are at least 40 bytes
`long, leading to a total unfragmented IP datagram 1064
`bytes in length. To cross the ARPAnet,
`this will be
`broken into a 1006 byte fragment, followed by a 78 byte
`fragment. These short fragments amortize the fixed
`overhead per ARPAnet packet over very few bytes of
`data, and the total packet count is much higher than
`needed. If the sending TCP instead chooses segments
`that fit in a 1006 byte ARPAnetpacket,the total packet
`count is minimized, and the total overhead is as low as
`possible.
`
`For example, consider sending 10 Kbytes of data.
`Sending 1024-byte TCP segments generates 10 IP
`datagrams, each 1064 bytes long. Each datagram is
`fragmented into two ARPAnet packets, one 1006 bytes
`long and the other 78 bytes, for a total of 20 packets.If
`the originating TCP instead sends 966 byte segments
`(the largest that will fit in a single ARPAnet packet),
`only 11 packets are sent.
`
`Anotherlimit to utilizing available bandwidth lies in the
`interaction of the TTL and Identification fields. Assume
`that a reasonable initial value for the TTL field is 32
`(the maximum hop count from edge to edge of the
`DARPA Internet is currently estimated to be between
`15 and 20). If we allow fragmentation, we must ensure
`that all datagrams in flight have unique values for the
`
`Identification field. Thus, the maximum datagram rate is
`216/32, or 2048 datagrams per
`second. Current
`gateways can forward nearly 1000 packets per second;
`high performance workstations
`and interfaces can
`generate packets much more rapidly, and can probably
`forward 4000 packets per second. We are certainly
`within five years of having commonly available
`processor and network technology that pushes against
`the limit imposed by the 16-bit Identification field.
`
`to increase bandwidth in the
`This limit implies that,
`presence of fragmentation, hosts should send larger
`datagrams, so as to carry more data per value of the
`Identification field. This is a bad idea, because large
`datagrams lead to more fragments, and we shall show
`that this increases the likelihood of a severe decrease in
`performance. If we simply avoid fragmented datagrams,
`values of the Identification field need not be unique,
`and there is no bandwidth limit imposedbyits size.
`
`2.3. Poor performance when fragments are lost
`
`When segmentsare sent that are large enough to require
`fragmentation,
`the loss of any fragment requires the
`entire segment to be retransmitted. This can lead to
`poorer performance than would have been achieved by
`originally sending segments that didn't require frag-
`mentation.
`
`Gateways in the Internet must drop packets when
`congested. If the gateways are congested, dropping
`fragments only makes the situation worse. Dropped
`fragments mean increased retransmissions, which leads
`to more fragments. As the loss rate goes up due to
`heavy
`congestion,
`the
`total
`throughput
`drops
`dramatically, since the loss of any one fragment means
`that
`the resources expended in sending the other
`fragments of that datagram are entirely wasted.
`
`Even when congestion is not the problem, retransmis-
`sion does not necessarily increase the likelihood thatall
`the fragments that make up the segment will arrive
`unscathed.
`In particular, network idiosyncrasies may
`conspire to cause the same fragment or fragments to be
`lost on successive retransmission. We call this deter-
`ministicfragmentloss.
`
`An example of deterministic fragment loss occurs in the
`4.2BSD Unix implementation of TCP when datagrams
`pass between a local network (typically an Ethernet or a
`Proteon ring, with MTUs of 1500 or 2046 bytes,
`respectively) and the ARPAnet. The TCP prefers to
`send 1024 byte data segments, which are transmitted in
`1064 byte IP datagrams. As seen earlier, this results in
`two fragments, 1006 and 78 bytes long.
`
`The receiving gateway receives both fragments and
`sends them out overthe local Proteon ring. The Proteon
`
`ACM SIGCOMM
`
`T7-
`
`Computer Communication Review
`
`INTEL EX. 1420.003
`
`INTEL EX. 1420.003
`
`

`

`Ting interface does not have sufficient buffering to
`receive back-to-back packets, so it consistently drops
`the second fragment. The sending TCP times out, and
`retransmits the 1024 byte segment, which will again be
`fragmented. The second fragment
`is again lost,
`the
`segment
`times out, and eventually the connection is
`broken.
`
`In addition, many of the gateways in the Internet today
`are derived from 4.2BSD Unix. This implementation of
`IP does not properly fragment a previously fragmented
`packet, preventing some fragments from ever reaching
`their destination, which might better be called guar-
`anteed fragmentloss.
`
`2.4. Efficient reassembly is difficult
`
`Reassembling fragments into datagrams at the IP layer
`is considerably less robust than constructing a reliable
`stream at the TCP layer. The window mechanism in
`TCP allows the reassembly process to accurately gauge
`how much buffer space to allocate for the current
`stream of unacknowledged data bytes. Also, because in
`TCP the data stream is covered by a sequence number
`for each data byte, once a contiguous sequence of bytes
`at the beginning of the outstanding data stream has been
`reassembled, it can be acknowledged and handed up to
`the next layer. Thus, progress can always be made, even
`if in small amounts.
`
`At the IP layer, there is no indication in the headerof a
`fragmented packet of how many other fragments follow,
`or of the length of the entire datagram. The More
`Fragments bit tells only if this the last fragment of the
`datagram, and the Fragment Offset field tells only the
`position of this fragment in the complete datagram. If
`the total size of the incoming datagram is too large to fit
`available buffer space, no progress can be made. The IP
`specification requires hosts to be able to reassemble
`datagrams at least 576 bytes in length; larger segment
`sizes must be explicitly negotiated by higher level
`protocols.
`
`Evenif there is sufficient buffer space to reassemble a
`very large datagram, conflicts can occur. In the Internet,
`it is possible for fragments of the same datagram to take
`different routes to their ultimate destination. Depending
`on queue managementstrategies at gateways along the
`way, a fragment of a small datagram may arrive
`intermixed with the fragments of a large datagram.
`More concretely, assume two datagrams, L (large) and
`S (small), are fragmented as L,L,L3LyL;L,L7L, and
`S)S2. If there are only eight buffers available, and the
`reception order is LjL2L3L4Ls5L¢L7S,L3S2, reassembly of
`L cannot succeed, despite adequate buffer space. Upon
`reception of S,, the reassembly process could discard L,
`through L;, which would leave six free buffers and
`
`allow S to be reassembled when S,arrives. Or, it could
`discard Lg (and subsequently S,), blocking reassembly
`of both L and S$; the buffers would be keptfull until the
`fragments expire.
`In either case,
`the work done to
`transport all the fragments of L is entirely wasted.It is
`not possible to coalesce a complete initial string of
`fragments and partially acknowledge receipt of the
`datagram in order to free some of the buffer space.
`(Dave Mills first pointed out this behaviorin [13].)
`
`It is difficult to decide how long to hold on to received
`fragments. The only firm limit
`is the TTL field;
`the
`reassembly process must discard fragments as their
`TTLs expire. Since each gateway decrements the TTL
`field, it must be set high enoughto traverse the longest
`possible route, and thus maystill be quite high when the
`packet arrives at
`its destination. Naive use of the
`received TTL as a reassembly timeout will cause some
`fragments to occupy buffer space for a much longer
`time than necessary. Use of too short a reassembly
`timeoutwill cause fragments to be dropped too quickly,
`leading to unnecessary retransmissions.
`
`Because IP is a datagram protocol, there is no guarantee
`that a given fragment will ever arrive. A higher level
`protocol may retransmit a lost IP datagram.If a retrans-
`mitted datagram does not have the same value for the IP
`Identification field,
`its data will not be recognized as
`being the sameas that in previously received fragments.
`The old fragments will occupy buffer space until timed
`out or forced out by incoming packets, and cannot fill
`holes left by fragments dropped from the second data-
`gram. This suggests that higher level protocols should
`attempt to use the same value for the IP Identification
`on both the original and retransmitted data. (This idea
`was proposed by John Shriver [24].)
`
`3. Avoiding fragmentation
`
`in most circumstances, the potential
`Webelieve that,
`fragmentation
`far outweigh the
`disadvantages of
`expected advantages. Thus, hosts should avoid sending
`datagrams that are so large that they will be fragmented.
`The length limit can be determined by a variety of
`general approaches:
`
`e Always send small datagrams: There is some
`datagram size that is small enough to fit without
`fragmentation on any network; we could simply
`send no datagramslarger than this limit.
`
`e Guess minimum MTU of path: Use a heuristic
`to guess the minimum MTUalong the path the
`datagram will follow.
`
`e Discover actual minimum MTU ofpath: Use a
`protocol to determine the actual minimum MTU
`along the path the datagram will follow.
`
`ACM SIGCOMM
`
`-78-
`
`Computer Communication Review
`
`INTEL EX. 1420.004
`
`INTEL EX. 1420.004
`
`

`

`e Guess or discover MTU and backtrack if
`wrong:Since an estimate might be wrong, and a
`discovered MTU may change if a route changes,
`sometimes we may have to adjust the length limit.
`This requires both a mechanism for detecting
`errors, and a mechanism for correcting them.
`
`Later in this section we will discuss more specific
`fragmentation avoidance schemes.
`
`All these strategies assume that the route the datagrams
`will follow is
`independently determined. If multiple
`routes are available between source and destination, one
`might
`instead try to avoid fragmentation by using
`source-routing to avoid data links with small MTUs.
`Suitable alternate routes seldom exist, however, and
`even when they do we see no efficient way for an IP
`host to obtain enough information to choose a good
`source-route.
`
`IP is a layered protocol architecture, and fragmentation
`avoidance mustbe doneatthe right layer. It makeslittle
`sense to build redundant mechanismsinto several layers
`if it is possible to do it once, This implies that the right
`place for fragmentation avoidanceis the layer common
`to all IP communication,
`the IP datagram layeritself
`(and its partner, the ICMP protocol). It would be a poor
`idea
`to
`put
`the
`entire
`fragmentation
`avoidance
`mechanism in, say, the TCP layer, because both the
`mechanism and any additional protocol would have to
`be duplicated in paralle]
`layers, such as UDP[17],
`NETBLT[6], and VMTP[3], and because it would be
`awkward for
`a TCP-based mechanism to
`share
`knowledge with other layers and across connections.
`
`layers above IP should be
`to say that
`This is not
`uninvolved in fragmentation avoidance. Architectural
`layering does not mean that higher layers must be kept
`ignorant of fragmentation issues. Optimal performance
`depends upon cooperation between layers for example,
`the TCP layer should not send huge segments if the IP
`layer knowsthat they will be fragmented.
`
`Most of the fragmentation-avoidance schemes we will
`propose depend on keeping some knowledge about the
`minimum MTU (MINMTU)onthe path a datagram will
`follow. A MINMTU value could be associated with a
`specific destination network, a specific destination host,
`a specific route (there may be several routes to one
`destination, with differing MINMTUs), or a specific
`connection (since for different applications, we may
`want
`to choose between optimizing for maximum
`bandwidth versus minimum delay, and thus might want
`to accept different risks of fragmentation for different
`connections to the same host). The MINMTUvalues
`could be kept in the IP routing database, or in a separate
`database, especially if per-connection MINMTUs are
`
`wanted. To support per-connection MINMTUs, the IP
`layer must obtain
`a
`connection
`identifier
`from
`connection-oriented higherlayers.
`
`scheme
`a per-connection
`that
`is our belief
`It
`(degenerating to a per-route-to-specific-host scheme for
`connectionless protocols)
`is the most
`flexible one.
`Whileit is true that by keeping per-destination-network
`information one might be able to pool
`information
`about several hosts, this is not necessarily safe. Because
`many networks are subnetted [15], because MTUs may
`vary amongthe subnets of a given network, and because
`one cannot tell whether a remote network is subnetted
`or not, it is not true that knowing the MINMTU for one
`host reliably gives you the MINMTUforall other hosts
`on the same network.
`
`Routes in a datagram network are not necessarily
`symmetric, the route a packet takes may not be the
`reverse of the route taken by a packet traveling in the
`opposite direction. Because of this, it is not safe for a
`host to assume that it can send a datagram as large as
`the one it has received from its peer. An independent
`MINMTU determination must be made for each
`direction, although the peer hosts may assist each other
`in doing so.
`
`Whenthe IP layer has determined the MINMTUfor a
`connection or destination, it can make this information
`available to higher
`layers,
`such as TCP,
`that are
`generating segments
`to be
`sent as
`IP datagrams
`Segment-generating layers should ask the IP layer for a
`MINMTUbefore sending a segment; connection-based
`layers
`should either
`check periodically that
`the
`MINMTUhas not changed,or should be able to handle
`asynchronousnotification of a change.
`
`3.1. Fragmentation avoidance without protocol
`changes
`
`fragmentation
`section we describe several
`In this
`avoidance schemes that can be implemented without
`changing existing protocol specifications or creating
`new protocols. There are obvious advantages to such
`approaches, since they can be taken immediately by
`individual sites or vendors; further, we have sufficient
`experience with one of them to believe that it works
`fairly well. On the other hand, none of these schemes
`can make use of exact knowledge of MINMTUs,and so
`may not provide optimal performance.
`
`3.1.1. Always send tiny datagrams
`
`If a host always sent datagrams no larger than the
`minimum MTU overthe entire internet, these datagrams
`would never be fragmented. In the IP Internet the limit
`is no higher than 254 bytes, and might be lower. Since
`almost all of the Internet supports larger MTUs, and
`
`ACM SIGCOMM
`
`-79-
`
`Computer Communication Review
`
`INTEL EX. 1420.005
`
`INTEL EX. 1420.005
`
`

`

`since performance depends so strongly on packet size,
`this approach can't provide reasonable performance.It
`is worth invoking only as a
`temporary diagnostic
`measure if performance actually increases when the
`datagram size is decreased, this is a clear indication that
`inappropriate fragmentation is taking place for larger
`datagrams.
`
`Alternatively, one might assume that using a 576-byte
`limit is small enough to avoid fragmentationin virtually
`all cases (we hope that in the future, all new LP network
`links would be capable of handling packets ofthissize).
`576 bytes is set forth in the IP specification [18] as the
`maximum size a host can send without explicit
`permission from the receiving host, so it is reasonable
`as an arbitrary value.
`
`3.1.2. Send 576-byte datagrams if the route goes via
`a gateway
`
`The IP layer can determine if the route for a connection
`or destination goes via a gateway. If it does, then the
`size limit is set to 576 (our favorite arbitrary value);
`otherwise, any size up to the MTU ofthe data-link layer
`may be used.
`
`This approach provides maximum performance for
`local connections, and reasonable assurance that on
`most non-local connections, datagrams will not be
`fragmented.It is not perfect, since
`1.
`Itdoes not avoid fragmentation on every path
`2.
`It may unnecessarily limit packet size, especially
`on subnetted collections of high-speed LANsthat
`all support large packets.
`
`3.
`
`If proxy ARPis used [14] then the IP layer may
`be fooled into believing that a non-local path is
`local, and thus use large datagrams whentheyare
`not necessarily safe.
`
`However, it is quite easy to implementand in general
`provides good performance. A variant of this scheme,
`implemented in the TCP layer, has been used for
`several years at many sites and is now incorporated in
`4.3BSD Unix [12]. This is the method we recommend
`in the absence of protocol changes.
`
`3.13. Send 576-byte datagrams if the route goes off-
`net
`
`Instead of checking whether a destination is behind a
`gateway,
`the IP layer can examine the destination's
`network numberto decideif it is local or non-local. In a
`subnetted environment,
`this trades a higher risk of
`guessing too high a MINMTUforhigher performance
`within the local collection of subnets.
`
`3.2. Fragmentation avoidance with protocol changes
`
`fragmentation
`section we describe several
`In this
`avoidance schemes that
`require changes to existing
`protocol specifications or the creation of new protocols.
`Mostly, these involve changes to gateways and some
`minor changes to IP-layer software; all are designed so
`as to coexist with unmodified gateways and hosts.
`
`3.2.1. Probe mechanisms
`
`Ideally, for a host to be able to send the largest possible
`datagrams that will not be fragmented,
`it must have
`perfect information as to the MINMTUalongthe path
`the datagrams will follow. Since most IP hosts do not
`even know whatthat route is, much less what the MTUs
`are
`along the
`route, we need a mechanism for
`discovering MINMTU.
`
`The moststraightforward kind of mechanism is to send
`a packet along the route, collecting MTU information as
`it goes; we call
`these probe mechanisms. Probe
`mechanisms require support from gateways each gate-
`way along the route must update the probe according to
`the MTU ofthe hopit is about to take. Probe mechan-
`isms also require support from peer hosts, since paths
`are asymmetric, once a probe reaches the end ofits
`route, the information it has collected must be returned
`to the source host.
`
`A probe may either gather a list of all the MTUsalong
`the path (somewhat analogousto the IP “Record Route”
`option), with which the host
`can determine
`the
`MINMTU,or the probe may simply carry only the
`lowest MTU value seen along the route. The former
`method provides a little more information;
`the latter
`method is easier to implement and results in shorter
`packets.
`
`A probe may be made only once,at the beginning of a
`connection or the use of a route, or it may be made
`periodically. Periodic probes are preferable if
`the
`MINMTU is kept per-destination or per-connection,
`since the route may change. If MINMTUinformationis
`kept per-route, then it will not change and consequently
`probes need notbe repeated.
`
`Probe mechanismsare useful for discovering other path
`characteristics besides MINMTU. As long as one is
`processing a probe,it makes sense to collect a variety of
`information, since it comesatlittle additional cost. This
`information could include:
`
`Minimum bandwidth
`Useful for determining appropriate transmission
`rates; if a host knowsthat a 9600-baud link is part
`of the path, it should behave differently than if the
`path is entirely via 100 Mbit fiber networks.
`
`ACM SIGCOMM
`
`Computer Communication Review
`
`INTEL EX. 1420.006
`
`INTEL EX. 1420.006
`
`

`

`Maximum delay
`Useful for determining realistic round-trip times;
`if a satellite channel
`is in use, with a delay of
`several hundred milliseconds, a host should not
`retransmit as quickly as if the end-to-end delay
`were several milliseconds.
`
`which both hosts will have the path information,
`including MINMTU.
`
`3.23. Probes piggybacked on IP headers
`
`It is not necessary to send a separate packet to probe the
`path. Instead, the probe information can be piggybacked
`on the actual data packets, as part of the IP header. In
`Maximum queue length
`appendix II we describe new IP header options for
`if measured
`A high value implies congestion;
`
`recording returning MINMTU_information.and
`
`using the
`“fair-queueing”
`algorithm [16]
`it
`(Additional options could be defined for recording other
`indicates to a host whetherit is sending too much.
`path characteristics.)
`Alternatively,
`a “congestion-encountered” flag
`could be set
`if any gateway along the path is
`experiencing congestion.
`
`Maximumerrorrate
`Whena link along the path is experiencing a high
`error rate, a host might choose to send shorter
`packets (so as to reduce the likelihood that an
`entire datagram is dropped because of a single
`error) or use error-correcting codes.
`
`Hop Count
`The total number of links traversed along the
`route may beof interest, for example, in choosing
`a value for the “Time To Live” field. (Collection
`of hop counts was proposed by Mike Karels [10].)
`
`It is not necessary for every gateway along the path to
`support probing, providing they all forward the probe.
`Gaps in the probe information are not fatal; at worst,
`host behavior is the same as if no probing is done. A
`gateway that does support probing can cover up for an
`occasional uncooperative gateway by looking at
`the
`incoming link as well as
`the outgoing link when
`determining the MINMTU.
`
`Since route choices may depend on the IP “Type of
`Service” and perhaps the IP “Security” option, probes
`should carry the same Type of Service and Security as
`the data packets will [4]; gateways should observe Type
`of Service and Security when updating values in probes.
`
`3.2.2. Probing with ICMP messages
`
`A probe can be done using a separate packet; in the IP
`architecture, we would do this using a new ICMP
`“Probe Path” message. This is described in detail
`in
`appendix I.
`
`Briefly, a host wishing to probe a path sets initial values
`for the fields of the Probe Path message, then sends it to
`the destination host. Each gateway along the route
`updates various
`fields of the message. When the
`destination host receives the message,
`it copies the
`recorded information into a different area of
`the
`message, reinitializes the recording fields, and returns
`the message to the original host. If the second host
`requests, the message may make one moretrip, after
`
`In this case, a host wishing to probe a path sets initial
`values for the “Probe MTU”option in the IP header of
`a datagram it is sending. Each gateway along the route
`may update the value carried in this option. When the
`destination host receives the datagram,
`it copies the
`recorded information into a “MTU Reply” option and
`attaches it to the next datagram going backto the source
`host. When this reply is received, the first host knows
`the MINMTU;the second host may pass its own Probe
`MTUoption along with the MTU Reply, so after one
`more datagram both hosts can know the MINMTU.
`
`involve