re: Source Routing

Ross Callon (rcallon@PARK-STREET.BBN.COM)
Tue, 17 Nov 87 14:07:03 EST


The possibility of having the first gateway compute a complete source
route and add the route to the packet is an interesting one, which
has been discussed for quite a while now. The biggest problem with
it is the computation involved with changing the IP header (at the
first gateway) and parsing the header (at other gateways). This
problem is a result of the way that the IP header is defined (and is
at least as bad for the ISO IP), but could be solved by alternate
encodings. The degree to which you care about processing depends
upon the processing power of the gateway, relative to the bandwidth
of its interfaces. In particular, do your gateways have processing
power to spare?

Inserting a source route at the first gateway requires recomputing
the checksum, which kills the end-to-end nature of the checksum
computation (I personally don't care that much about this). Also
note that the ISO IP, with 20 octet addresses (maximum size) and a
254 octet maximum header size, does not leave room for all that many
addresses in the source routing field (the exact number depends upon
the actual address size used, whether the segmentation part of the
header is there, and the presence of other options).

In the case of multiple-autonomous systems, assuming some future
inter-AS protocol, you probably don't want a gateway to have complete
knowledge of the internals of other ASs. This implies that you would
not be able to produce a complete source route (as you suggested),
but still may use a similar idea with partial source routes (which
may specify gateways, or may specify AS numbers or something else).

One obvious question is why would you want to do this? There are
several reasons that I can think of: (1) to avoid looping and other
routing problems; (2) to relax the requirement of SPF that different
gateways all have consistent databases; (3) to allow different
sources to have different routing policies; (4) to allow the source
to route different packets along different paths; or (5) for some
different encoding, to minimize the work required of intermediate
"transit" gateways along the path.

I'm not convinced that avoiding looping is really the reason for
using this scheme. Our experience is that, given well chosen
metrics, SPF routing really works pretty well. The degree to which
the NSF network is having trouble with routing is due to the
particular routing algorithm that they are using, not due to any need
for a previously unthought-of approach to routing. I think this is more
or less why there is the beginning of an effort in IETF to develop a
new (probably SPF-based) routing scheme that would be "public domain"
and well specified via future RFCs.

If you use source routing, you still must require that all gateways
have databases which are correct in the sense that any link that they
think is there really is. Thus link failures would still have to be
reported very quickly. However, it would be possible to report other
news (such as a new link coming up, or the change in "cost" of a
link) more slowly. I'm still not sure that this is such a big deal
because (1) I think that "costs" on operational links should not be
allowed to change rapidly in any case; and (2) when new links come
up, it should first be determined that the link is really stable up,
and then all nodes will probably want to hear about this quickly. On
the other hand, there may be some minor benefit in not needing to
propagate most routing updates at quite so high a priority.

The idea of allowing sources to have different routing policies is
an important one in inter-AS routing, but I don't see it as very
important in intra-AS routing.

We (at BBN) have plans to use a sort of source routing in the Arpanet
to allow multi-path routing for load splitting and congestion control
purposes. Note that in order to do anything that resembles optimal
multipath routing, you are required to do either (1) source and
destination based routing (i.e., each node calcualtes and maintains a
separate route for every source-destination pair, rather than just
for every destination); or (2) source routing. Since we build all of
the PSNs in the Arpanet, we are able to define a header encoding
which makes source routing very efficient (actually more efficient
than regular routing table lookups).

Similarly, Butterfly gateways do something that resembles partial
source routing in order to optimize the path lookup. As an IP
datagram passes through an AS consisting of Butterfly gateways, the
first gateway encodes the datagram in a "gateway to gateway header"
which specifies the last gateway in the AS. The transit gateways
only have to look at a very small exit gateway ID in the gateway to
gateway header in order to route the packet. The exit gateway (the
last gateway in the AS to deal with the packet) then removes the
gateway to gateway header. This approach minimizes the processing
required at intermediate gateways, and allows IP level routing to be
separated into two logically separate steps (i) determining the exit
gateway for a particular destination network or IP address; (2)
determining the route to that particular exit gateway. If we were to
extend routing to deal with partitioned networks, only step (1) would
be effected. This may potentially be useful for other purposes as well.
For example, the exit gateway may be chosen based on load sharing or
other criteria.

I think that if we are to use your suggestion and use source routing
(whether partial or complete), we would need to either redefine the
IP encoding, or do something similar and add a gateway to gateway
header with a more efficient encoding. This latter approach would
allow the hosts to remain unaffected by the change.


This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:39:56 GMT