fragmentation
Christopher A. Kent, Jeffrey C. Mogus, DECWRL, 1988
Summary. Fragmentation is widely known to be detrimental to performance
for 3 reasons:
- Wastes resources: more packet header overhead, more routing decisions,
reassembly at the end node.
- Loss of fragments leads to degraded performance: loss of one fragment
results in entire datagram being retransmitted; if fragment lost due to
congestion, re-transmit of entire datagram worsens congestion;
- Efficient reassembly is hard: it is not possible to pass a portion of the
datagram off to higher layer; if too large to fit in buffer space, no
progress is made; fragments from many medium sized datagrams can all arrive
and fill the buffers without an entire datagram being present; datagrams
with TTLs that are too long will stay in buffer too long.
The authors propose several ways to avoid fragmentation or recover from .fragmentation. Of these many proposals, they recommend the following:
- Do use a MTU of 576 bytes on any packet that will traverse a gateway.
- Do use transparent fragmentation on hops with small MTUs.
- Don't use intentional fragmentation because it has limited gains and can
cause protocol failure. Could use only on local nets.
- Don't use the ICMP ``fragment reassembly time exceeded'' message; most
protocol implementations ignore it so there would be no gain yet more
messages would be injected into traffic.
.
TTL and IP Id tuple. IP uses 4 fields to control fragmentation:
- 16-bit ID (unique per source/destination/protocol)
- TTL
- *
Fragment offset (for reassembly)
- More Fragments bit (to determine end of datagram)
The ID and TTL together put an upper limit on the maximum bandwidth. If the .TTL is 32, then the packet is limited to either 32 seconds or 32 hops. This
means that IP can send out only (2**16)/32 or 2048 datagrams per second.
This limit is approaching (in 1988) unacceptable. If fragmentation were
avoided, this limit would be meaningless.
Deterministic frament loss is a phenomenon whereby a certain ordering of
fragment arrival will cause loss deterministically. For example, a certain
network can't handle back-to-back arrivals (?) so it will drop the second
packet of a 2-fragment datagram every time. Deterministic fragment loss
can be detected with a high retransmission rate. However, since a high
retransmission rate also can indicate congestion, this can only be used when
congestion is detected via a separate mechanism (router based, for example).
Without protocol changes.
- Always send small datagrams; won't provide reasonable performance.
- Send 576-bytes datagram if route goes through gateway; provides max
performance local; could still have fragmentation; could unnecessarily limit
packet size; used in BSD 4.3.
- Same as above but examine network number.
With protocol changes..
- Probe for MINMTU once or over life of connection. Soft-state since gaps
in probe info not fatal. Use new ICMP message Probe Path that gets MINMTU
set by routers.
- Piggyback on IP header. Use new Probe MTU option in conjunction with
MTU Reply option. Could be a problem because you have to have a datagram
to send in the first place in order to piggyback.
.
- Use a Don't Fragment flag. If router needs to fragment, send back ICMP
message (appropriate message exists) and drops packet. Source tries again.
Problem: iteration makes cnxn setup time long.
- Passive detection of fragmentation. No packets are dropped (as in above).
Observe the retransmission rate (again, have to be careful about congestion
conflict).
- Use ``Time Exceeded'' ICMP message. When reassembly time times out on receiver,
can send message. Source reacts by reducing size of datagrams. This is
ignored by most IP implemtations so probably isn't useful.
- Router sends ``Fragmentation Warning'' ICMP message. Carries MTU for that link.
New message. Source is supposed to decrease to that size. Useless traffic
can be generated if source doesn't obey warning.
- Receiver sends ``Fragments received'' ICMP message. . Carries maximum
fragmentation size from the fragments received.
.
Transparent fragmentation is the reassembly of fragments on a hop-by-hop
level. The benefits are that it maximizes bw on higher links and
deterministic fragmentation unlikely. The drawbacks are that packets may be
reassembled/fragmented, gateways more complex, performance gains bounded
because the max TU will be the MTU of the first hop. Plus, the IP layer at
the destination may still have to perform reassembly if the last link had a
smaller MTU than the first link. Only use on links with unusually small MTUs.
Intentional fragmentation is sending such large datagrams that they must be
immediately fragmented. This can improve performance by minimizing the
amount of handling done before and after the network layer sends the data.
Vulnerable to deterministic fragmentation. Could use on local nets.