[ih] Source routing, IEN 80, and IEN 95 (in use)

[jfh]

Hi Mike!  I was going to reply to Matthias' message by saying that the
best source would be someone who actually wrote the code - like Mike
Brescia.

TWIMC, Mike was the guy who had the interesting job of keeping the "core
internet" running back in the late 70s/early 80s timeframe.  So his
comments about the use of source routing as a debugging tool can be
taken as gospel.  We had had a lot of experience from operating the
ARPANet at BBN, and so the idiosyncracies of routing algorithms were
well known, especially their tendencies to behave in unexpected ways.
So tools were very important in that experimental period, and that need
motivated the implementation of source routing, traceroute, SNMP, TCP
ports like sources and sinks, etc.

As I recall, there were a bunch of other motivations for source routing.
Remember, it was a very experimental time - the whole Internet was
officially an experiment.  At the "IP level" there were quite a few
projects which were also building gateways/routers, which were typically
(at that time) attached as "branches" hanging off the core.  Source
routing in the core allowed people to force packets to go a certain way,
so that they would go into the appropriate "other internet" rather than
taking what might be a more direct route through the normal core routes.
I think Dave Mills used this in some of his work.

Also, people were experimenting with things like packet voice.  The core
routing scheme was pretty simple, based purely on hops, with no concern
for delay, available bandwidth, cost, etc.  The Wideband Net was roughly
parallel to the core internet system, and had much higher bandwidth (but
of course much higher delay, being satellite based).  

So it was desirable to route non-interactive packet voice/video through
the WBNet, e.g., between east and west coast US.  But with normal core
internet routing, packets arriving into the core from a site on the east
coast would be sent directly to the site on the west coast through
low-speed terrestrial circuits - when it would be preferable to "detour"
them to the high-speed east coast satellite connection, across the
satellite, and back into the core on the west coast.  

The "shortest hop" route was not the right answer.  The normal core
routing would never choose a longer route (unless the core internet was
partitioned, making the satellite route shorter).  So source routing was
a way to get packets to go the way you wanted.  This particular scenario
was called "Expressway Routing".

There were a handful of such "not yet solved issues" that Jon Postel
used to write on the board at every ICCB/IAB/TCPIPWG meeting.  

E.G., the "VAN gateway" (connected ARPANet with Telenet (sic)) enabled
the use of the public X.25 network to get packets from the US to UK.
SATNET could also provide that transatlantic connection.  However,
SATNET was only to be used for research projects that funded it.
Conversely, the X.25 net was open for anyone - but it cost real money -
for each packet - to use it, which came out of DARPA's budget.  So there
was a desire to make sure that various projects sent their traffic
through the appropriate paths, which source routing could help
accomplish.  An interesting quirk was that the X.25 costs were charged
to the end which opened the X.25 connection.  If the UK end opened the
connection, the UK got the bill, and converse for US.  This asymmetry
motivated some interesting algorithms in the VAN gateway thinking -
implementing the old Manager's Mantra "Move your expenses into someone
else's budget".   AFAIK, this was the beginning of the "Policy Routing"
issue.

The "grand scheme" was that all of these scenarios would be explored by
experimentation, and then the lessons learned would be used to design
and implement a routing protocol which handled everyone's needs - the
Grand Unified Routing Protocol, aka GURP (don't google that, I just made
it up).  Not an easy task.  I don't think there was ever an intent that
source routing be used as an end-user tool.  After the experimentation
phase ended and the "real" routing mechanism was in place, source route
et al would be simply internal tools for network management and
operations (like ping, traceroute, etc.).

In effect, there would be multiple, possibly many, independent routing
algorithms running on the same physical Internet, each concerned with
figuring out the "least cost" path for packet flow based on independent
criteria about what "cost" meant - actual money, lowest delay,
achievable throughput, available unused capacity, ownership of circuits,
time of day, etc.  For any given packet, the TOS (type of service) field
would be used to select which routing service to use for that packet.

This would also permit the operation of independent congruent internets
with different behaviors.  E.G., the "premium" network would route
packets with little regard for cost.  The "bulk cargo" internet would
route packets only through paths that would otherwise be idle.  No one
at the time cared much about pricing policies, but premium service would
obviously be more valuable than bulk.

You'll have to ask someone else how far today's Internet has gotten in
terms of that 80s-era grand scheme.  That was about the time that
routers started popping up like dandelions all over the place and I
think we lost control of the experiment.

I get this sense of deja vu when I read today about the "net neutrality"
debates.  It seems to me like a new name for the same problem from that
80s white-board list.

Hope this helps,
/Jack
Point Arena, CA


On Thu, 2010-08-05 at 21:25 -0400, Mike Brescia wrote:
> John,
> 
> You got it exactly right.  You cannot "stop and ask for directions" from normal routing when something may have broken it.
> 
> In the early days of SATNET (1978..), when the routing or the SATNET or ARPANET network infrastructure failed between the U.S. either the U.K. or Europe, fallback source routes configured in the monitoring and control program were used to get around the failure.  On ARPANET and SATNET, failure of one of the satellite links would isolate parts of one net and a set of configured source-routes via other nets would be tried as the way to reach nodes which were not normally responding, bypassing the break.  The only programs I saw using this approach was the IMP monitor/control program NU and before that, U.  Oh, and later, monitoring for the "Wideband" net also at BBN.
> 
> While a user tool (e.g. telnet, ftp) may have had a source-route command line option to force a bypass in extreme cases, I cannot recall those tools having a configuration file setup for trying fallback routes.
> 
> network example: (forgive the ASCII "art")
> 
> NOC ..2................>
>  |       ARPANET(10)    .
>  +-------+=========+-------+ 
>   ..1..  |         |    .
>       .  R1        R2   .
>       .  |         |    .
>       v  +         +    v
>           \       /
>   SATNET(4) XXXXX
>           /       \
>          +         +
> 
> NOC = network ops center
>  +  = network node (IMP, SATNET IMP)
> === = ARPANET satellite link
>  R  = gateway(router)
> XXX = break in SATNET isolating parts of net 4
> .1. = normal path to net 4 via R1
> .2. = source-routed path to isolated part of net 4 via R2
> 
> 
>  -- Mike Brescia (BBN &seq. '78-'02)
> 
> 
> On Aug 5, 2010, at 7:10 PM, John Day wrote:
> > Source routing is a male thing  -  the packets don't want to stop and ask for directions.
> > 
> > ;-)  Sorry, couldn't resist.
> > 
> > 
> > At 0:40 +0200 2010/08/06, Matthias Bärwolff wrote:
> >> -----BEGIN PGP SIGNED MESSAGE-----
> >> Hash: SHA1
> >> 
> >> Hi everyone out there. I am wondering (mainly just out of curiosity)
> >> about the implementation and usage record of source routing in the early
> >> Internet. The IPv4 spec (starting with IEN 80) came to include it
> >> eventually, but my impression is that while people *thought* it would be
> >> important, in reality no one cared too much and it wasn't used much.
> >> 
> >> My question: have people actually been using it for purposes other than
> >> spoofing attacks? What about routing debugging? And, load balancing?
> >> 
> >> Plus, how widespread did it become in gateways/routers before security
> >> concerns rendered it a complete no-go?
> >> 
> >> Thanks for your recounts and takes.
> >> 
> >> - --
> >> Matthias Bärwolff
> >> www.bärwolff.de
> >> ----- elided PGP SIGNATURE-----
> 
>