if space for the source route is a problem, you can set
up the source routes in advance (effectively, an ATM PVC), and then use
an index # to specify which source route to be used -- this can be
much shorter than O(log # of detour boxes) * path length.
Pushed a little farther, you can even encapsulate the destination address
into the PVC #. This means you need to find extra space in the
header of roughly log(# of connections through a Detour router).
As Stefan pointed out, lots of places you could put this.
I lectured about source routes on wednesday, and realized they
really aren't as bad as people think -- no extra space in
the common case (if you use #'s to indicate routes), it is
possible to make them scale (by using a hierarchical loose source
routing scheme that scales in the same way as hop-by-hop routing), etc.
Perhaps a paper on "the duality of source and hop by hop routing?"
tom
-----
Received: from june.cs.washington.edu (june.cs.washington.edu [128.95.2.4]) by emigrant.cs.washington.edu (8.8.8+CS/7.2ws+) with ESMTP id NAA26514 for <tom@emigrant.cs.washington.edu>; Thu, 29 Oct 1998 13:54:38 -0800 (PST)
Received: from exchsrv1.cs.washington.edu (exchsrv1.cs.washington.edu [128.95.3.128]) by june.cs.washington.edu (8.8.7+CS/7.2ju) with ESMTP id NAA27924; Thu, 29 Oct 1998 13:54:23 -0800
Received: by exchsrv1.cs.washington.edu with Internet Mail Service (5.5.1960.3)
id <46QHDNBD>; Thu, 29 Oct 1998 13:54:23 -0800
Message-ID: <055A195871E5D1119F8100A0C9499B5F044897@exchsrv1.cs.washington.edu>
From: Stefan Savage <savage@cs.washington.edu>
To: Andy Collins <acollins@cs.washington.edu>
Cc: "'syn@cs.washington.edu'" <syn@cs.washington.edu>
Subject: hack to avoid fragmentation
Date: Thu, 29 Oct 1998 13:54:22 -0800
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.1960.3)
Content-Type: text/plain
Status: R
Hi Andy,
As i promised.. here's the hack:
First, this is pretty ugly and I'm not saying it SHOULD be done... but
it is an option if we get burned by fragmentation.
Ok, so the problem is how to add an encapsulating header AND the source
route data without making the packet any bigger (assuming its already at
1460bytes on ethernet)
To make things simple, lets start assuming that this is a one hop route.
Now we don't need a source route header because the encapsulating header
holds all the information you need. However, you still have this 20
byte encapsulating header you need to get rid of. First, lets remind
ourselves why we need the encapsulating header. The only reason we need
it is to select the next hop in the virtual network. So, broadly
speaking, we only care about the destination IP address field... the
rest is superfluous. Ok, so lets eliminate the encapsulating header and
just overwrite the real destination IP address with the next hop
destination IP address. The packet is the same size... no
fragmentation. The only problem is that we've lost the real
destination... admittedly a problem for the egress node. However, if we
could stick the extra 32 bits somewhere in the packet, we'd be golden.
On UDP this is easy... we simply write over the 16 bit UDP length and
UDP checksum fields. On the egress end we put the dest ip address back
in place, and re-calculate the UDP fields (we can just write 0 in the
UDP checksum... this is an experiment after all. On TCP we have a
number of options.
1) we can take advantage of the fact that most TCP traffic isn't
"two-way" (ie doesn't have data and acks together) and overload the
acknowledgement number to hold the destination IP address. We could do
the same thing with the sequence number in the ACK direction, but its
unlikely that these packets will be MTU sized.
2) As with UDP, we can overwrite the checksum and urgent pointer
(generally, only small packets have the urgent pointer set anyway).
Then we use one of the unused flags in the IP header or TCP header to
indicate that this is a "special" packet with reduced encapsulation.
Now, what if we have a source route of size more than one? Do we need
another 32 bits for each one? No. Because Detour will have a small
number of nodes (10's) and those nodes are well known, its possible to
compress the source route into a detour router index number, whose IP
address can be regenerated on each hop. For 16 detour routers (more
than we'll have any time soon) you only need 4 bits per hop. These can
be stuck in any of these left over spaces:
8 bit TOS in ip header
16 bit length in ip header (can be computed from MAC layer)
16 bit header checksum in ip header
16 bit identification & 13 bit frag offset (if we ensure that
MSS=MTU-40)
6 bit reserved field in TCP header
So, it seems quite feasible that we can source route paths of length 1-5
without fragmenting maximum sized packets.
- Stefan