Subject: Intentional Host Reordering of TCP Fragments

From: "Nabil Seddigh" <[email-masked]>
Date: Thu, 15 Jun 2000 22:04:05 -0400 (EDT)

Recent discussions on this list focused on network
devices reordering packets. How about an end-host
that intentionally reorders some TCP packets?

During testing of Packet Classification capability
on for Diffserv-capable routers, one of my colleagues
discovered that the Linux TCP sender intentionally
reorders fragments - the pkt containing the TCP port
number is the last pkt sent in a family (same ip_id)
of fragments.

The implication of such an implementation is that
Layer-4 packet classification of fragments 
is virtually impossible - unless routers try to 
cache packets....not a desirable solution.

Of course one could argue that most fragments on
the net are UDP and not TCP but nonetheless:
shouldn't end-hosts avoid intentional reordering?

We checked out various RFCs and didn't find explicit 
prohibitions on an end-host reordering the pkts 
that it sends out. 

Best,
---
Nabil Seddigh
[email-masked]

---

From: Charles Esson <[email-masked]>
Date: Fri, 16 Jun 2000 13:37:51 +1000

<rant>
Doesn't Defragmentation belongs in the IP layer; if you make that
assumption, then you could make life easier for that layer by sending
the last fragment first; the receiver then knows what resources are
required to reassemble.

As an outsider looking in; it would seem to me TCP/IP started out a very
elegant general purpose protocol. It allowed for out of order delivery;
multiple packet delivery and made no assumption on the packet size that
the underlying medium could handle. It has become more and more complex;
and less and less robust ( complexity brings bugs) as people try to get
additional speed out of systems that don't need a protocol that is as
robust as TCP/IP was.

Fast retransmit for example making assumptions that are just not valid
in the general case.

I am also a little confused as too why out of order packet delivery is
an issue with the ever decreasing cost of processors. It for example
costs very little to have a NIC reassemble fragmented IP packets before
delivery to the general purpose CPU.

Granted sorting out the IP order is a little more complex, but even
there if rules where made to have the IP identifier indicate the order
it would not have been a big deal; the NIC could have handled it; but
that was not to be.

If you have to move to the TCP sequence number to sort out packet order
then surely all is lost.
1) TCP is one of many possible protocols handled by IP.
2) You are using in a low layer something that has nothing to do with
that layer, more complexity more bugs.

If  you send packets in parallel surly it would be better to add a
sequence number  when dividing the input stream up, then use and remove
that sequence number when putting it back together, assuming you have
control over how the stream is put back together.

Given the way the US patent system is going it is probable something as
simple and obvious as this that is about to be patented. Perhaps this is
today's solution, but not tomorrow's.

If you haven't got control of reassemble, then I would have thought that
was the very application IP was initially designed to handle, and the
bits added as time has passed are the problem.
</rant>

---

From: "Jamal Hadi Salim" <[email-masked]>
Date: Fri, 16 Jun 2000 06:47:55 -0400 (EDT)

> shouldn't end-hosts avoid intentional reordering?

Fix your classifier.

Linux's "intentional packet re-ordering" of fragments is because that
is more efficient for Linux to do (and more natural thing to do for
network ordering of the bytes in the packet).

From a philosophical point of view, why should an end system care about
your classifier?

cheers,
jamal

---

From: Craig Partridge <[email-masked]>
Date: Fri, 16 Jun 2000 09:14:24 -0400

><rant>

A fun rant and it has lots of things we could argue about.  But there is
one point where I think I can shed some light (rather than just rant back :-)).

>control over how the stream is put back together.

The problem is more much more complex than simply ordering.  Suppose we
did this -- just put a sequence number on every packet at the link level
when we went parallel, and then put it back together at the next hop.  (You
can do this analysis for reordering at the end, too, just simpler this way).

OK, so consider the following situation:

Single link A -> Splitter -> 2 parallel links -> Ordering Node -> Single Link B

Further suppose that single link A is very fast (much much faster than the
downstream links).  This assumption just makes the analysis more clear (you
can have A be closer in speed).  Second, assume the rate of Link B is
R, and the rate of the 2 parallel links is R/2 each (so R in aggregate).

Now imagine that you receive a packet stream of the form, one maximum size
packet, called M, followed by 1 minimum size packet, called m.

Assume we put sequence numbers on each packet but that their cost is
negligible.

Now, look at the link performance.

At the splitter, we get M, and start sending it on one of the parallel lines.
Ignoring delay, M will take time (2M/R) to transmit.  Packet m arrives
almost immediately after M (recall link A is fast) and gets sent on the
second line.  Packet m takes time (2m/R).  So packet m arrives first.
Indeed, since m is the minimum packet size and M is the max, the last
bit of m arrives around the time the m-th bit of M arrives.

We want to put packets back in order before sending on link B.  So packet
m has to wait and link B is left idle.  The idle time is the remaining
time for packet M to arrive (which is roughly ((2M-m)/R)).  At that point
we have all of M, and can send M and then m along.

It is useful to figure out how long it takes to send packet m from the time
it enters the splitter until the time it leaves the ordering node.

If the parallel links were one single link, it would take time (M+m)/R to send
m, because it has to wait for M to serialize and then itself.    But because
we've gone parallel AND choose to delay m until M arrives to send in order,
the time is (3M+m)/R.  So it takes roughly THREE times as long to get m
from one end to the other, all because we put sequence numbers on.

The exact cost varies -- the key point here is not so much the time delay
as the fact that the splitter has data (packet m) which is not being sent
while it waits for packet M to arrive.  Unused bits are like unused
hotel room nights: you can't reuse them and they increase the overhead.

That's why most people don't like simple sequence numbers for maintaining
packet order.

Craig

---

From: Rick Jones <[email-masked]>
Date: Fri, 16 Jun 2000 10:28:39 -0700

I thought that end hosts were supposed to avoid fragmenting TCP
datagrams in the first place :)

Sending the first fragment last is not _that_ unknown. For example, it
is done for the HP-PB FDDI NIC from many years ago. In that case it was
done for UDP (thought I guess it would be done for TCP too if TCP
segments were fragmented) - the reason? The card basically had a
checksum accumulator - accumulate the checksum over the relevant
portions of the rest of the fragments and then insert them into the
header at the end. That way one does not have a need to DMA the entire
fragment chain into the NIC before the offloaded checksum can take
place.

Basically, it is a way to do a "trailer checksum" without actually doing
a trailer checksum.

rick jones

-- 
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to email, OR post, but please do NOT do BOTH...
my email address is raj in the cup.hp.com domain...