[ih] History question -- multi-homing

[Jack Haverty]

Re: the question of when these issues first surfaced...here's what I 
remember:

Issues such as multi-homing, naming, etc., have been around since before 
The Internet.  I've mentioned earlier on this list that the ICCB, circa 
1981-1983, maintained a list of things that needed to be done.  The more 
pragmatic of those were associated with the conversion of the ARPANET 
from NCP to TCP targeted for January 1983.   But there were also a lot 
of issues, many related to routing, that were judged to need further 
research, since the researchers had not yet reached consensus on the 
next set of algorithms, protocols, et al.

Many of the research issues related to routing had been already 
encountered in the ARPANET, which had been operating, evolving, and 
emerging into commercial use for more than a decade.  For example, 
issues of multi-homing and naming had been identified in the ARPANET, 
and a new mechanism had been developed, tested, and introduced -- for 
example, "logical addressing" as a tool for ARPANET users to address at 
least some of the problems they faced.  That mechanism was specified in 
an Appendix to the ARPANET user interface specification, BBN Report 
1822, in Appendix L (for Logical addressing...)

There was considerable effort to improve and evolve the internals of the 
ARPANET through the 1970s and 1980s as it grew into becoming an 
infrastructure.  Much of that was done by BBN under contract to ARPA and 
later DCA after ARPA transitioned operational responsibility to DCA.  
  Eventually, in the 1980s, the ARPANET evolved into the Defense Data 
Network (DDN).   Since the work was no longer viewed as "research", it 
was much less likely to be published as an RFC.  But much documentation 
about the internal changes to the IMP mechanism was produced and 
submitted to DoD, and may still be accessible at DTIC (see 
http://discover.dtic.mil ).

One example is a series of documents concerning the "ARPANET Routing 
Algorithm Improvements".  You can find these on DTIC using the "ADA 
Number" or searching for the contract number involved.    For one such 
report that I am listed as the author, the contract was MDA90-78-C-0219 
and the ADA reference is ADA121350.  I doubt I actually wrote any of 
that report, but I was responsible for that contract at the time and for 
getting the report submitted, which I recall was often a task comparable 
to herding cats.

It's quite possible that similar issues had arisen in other network 
deployments of that era.   Perhaps IBM's systems, or other packet-based 
networks such as Cyclades.  Or even earlier "networks" such as 
railroads, ships, or other transportation technologies.

Many of the issues that had been encountered in the ARPANET were also 
relevant to the Internet, and were added to the ICCB's "to-do list".  In 
particular, various "routing" issues were considered to "require further 
research" before any new mechanism could be defined and released as a 
standard.

I'm not sure if that list was ever widely publicized back in the early 
1980s.   The ICCB was somewhat of a "stealth" activity and I don't 
recall that there were any minutes of the ICCB meetings.  For History's 
sake, here's what I remember about that list of issues from the "early 
Internet era" of the 1981-1983 timeframe, where we decided there were 
things needing a lot of further research.  Remember that it's been a 
long time since 1983; I probably should have written this years, or 
decades, ago:

TIME-BASED ROUTING

The ARPANET had extensive hardware and code to measure how long it took 
for packets to traverse the 'net.   This data was exchanged among all 
IMPs regularly.  Each IMP ran a routing algorithm on that data, to make 
a decision about which IMP it should send each packet to as the next 
step.   The algorithm was typically called SPF, for Shortest Path 
First.   Each IMP sent a packet to the next IMP based on its calculation 
of which choice would best to get the packet to its destination most 
quickly.

The gateways (now called routers) of the early Internet did not have the 
hardware necessary to measure time, either for packets waiting in queues 
or for packets in transit across some network.  So the metric used for 
routing in the early Internet was simply hops, basically counting the 
number of networks that had to be transited to get from source to 
destination.  This was obviously inferior even to the time-based routing 
being performed in the ARPANET, but it was appropriate for 
experimentation as the Internet started.  Routing based on actual 
measurements of time was an obvious next step, but had to wait until the 
required hardware was available - specifically appropriate real-time 
clocks in gateways, and Dave Mills efforts to create NTP as a method to 
synchronize clocks.

EXPRESSWAY ROUTING

Expressway Routing was named based on experiences we've all had when in 
urban environments.  In any large city, a source and destination might 
be on the same street, but miles away from each other.  A source at 1000 
Main Street might be several miles away from a destination at 12000 Main 
Street, with numerous traffic lights and other delays along the route.  
Drivers quickly learn that to get from one to the other it might be 
faster to "go the wrong way"  and head toward 100 Main Street, because 
there is an on-ramp there to the Expressway, which bypasses all the 
traffic lights.

In the early Internet, exactly this situation existed.  The WideBand Net 
(WBNET) was satellite-based and had much greater capacity than the 
ARPANET, so it could be considered as an "expressway" spanning the US, 
especially useful for transfers of large files.  But the gateways 
attached to the WBNET were also attached only to the ARPANET.    Traffic 
between two ARPANET hosts, e.g., at 1000 Main Street and 12000 Main 
Street would never be routed to the WBNET gateway at 100 Main Street, 
even though such a route would provide better service.  When source and 
destination were on the same networ, i.e., the ARPANET, the routing 
mechanisms did not have the capability to divert traffic towards another 
network.

CAPACITY ROUTING

Capacity Routing was another aspect of possible routing mechanisms, 
which simply used a metric other than Time (or Hops) as the basis for 
choosing a particular path from a source to a destination.  Some traffic 
on the Internet was expected to require fastest possible transit times.

In the ARPANET era, the network was fairly uniform with typical line 
speeds of 56 kilobits/second.  There was little chance for "excess 
capacity" to occur.  Traffic patterns were carefully monitored however, 
and the topology of the network itself was changed to reflect traffic 
patterns.  If you look at the ARPANET maps of the era, you might notice 
that one of the cross-country lines ran almost directly between the ARPA 
offices in DC and the computers that they used, in California.  That 
provided the quick response times expected of the era, when much of the 
usage involved using terminals on desks in Washington logged in to 
computers in California.  Changes to the topology of the ARPANET could 
take a long time to make, involving ordering new circuits from the phone 
company and waiting for the installation to complete.

Interactive voice was the example with considerable experimentation 
during the early Internet era.  Anything that required quick response 
times between a human user and some remote computer would likely require 
:shortest transit time" routes.  But some traffic across the Internet 
was not time sensitive, and could tolerate longer transit times.  A good 
example was file transfers, especially of large (for that era) files.

In the early Internet, the WBNET and ARPANET created such a 
configuration where routing based on available capacity could be 
beneficial.  ARPANET was based on primarily circuits running at 56 
kilobits/second (yes, not mega or giga).   The WBNET was based on a 
multi-megabit satellite channel.  So an obvious goal was to have a 
routing system that would send "bulk" traffic through the WBNET, and use 
the limited capacity of the ARPANET to handle time-sensitive traffic.

Capacity Routing would require some way to measure available capacity of 
paths through the Internet, and of course a mechanism to pass such 
information around the network so routing decisions could be made at 
every node.   It would also likely require some solution to the 
Expressway Routing issue as well.

REDUNDANCY ROUTING

In both military and commercial environments, there is often a desire 
for redundancy, for example as a way to keep some activity in operation 
even when some of the underlying technology has failed.  Within the 
ARPANET "subnet" of IMPs connected to each other by circuits, routing 
mechanisms automatically worked around such failures, usually without 
the human users even being aware of the situations.   But most computers 
attached to the ARPANET had just a single connection to a single IMP, 
which created a possibility of a single failure disrupting the users' work.

In the ARPANET era, some sites therefore desired to have their computers 
redundantly attached to the ARPANET, so that when one attachment failed 
the other one could still be used.   If, for example, a particular IMP 
failed, a computer with a connection to a different IMP could still 
communicate.  However, the ARPANET architecture did not support such 
usage well, requiring awareness and actions by the human users to detect 
such failures and switch to the alternate route to the computer they 
were using.  The Appendix L mechanisms of BBN 1822L implemented "Logical 
Addressing", which may have helped mitigate such problems.

In the case of the Internet, techniques implemented in the "switches", 
such as IMPs, seemed impractical.  Some networks, such as Ethernets, had 
no "switches" where such a mechanism could be implemented.   Any such 
mechanism would likely have to be implemented in the "gateways" that 
interconnected networks, integrated appropriately with the routing 
mechanisms.

TOS ROUTING

With many different metrics possible as a basis for routing decisions, a 
new routing mechanism would essentially involve multiple routing 
decisions being made, and the actual route chosen based on the kind of 
traffic involved for each individual datagram. Of course there had to be 
some way for a user computer to specify what its needs were.  Also, the 
different separate routing metrics and decisions would have to be 
somehow coordinated so that the available resources were allocated 
fairly -- and "fairly" itself would have to be defined and implemented 
in algorithms and protocols.

That was a formidable task requiring much further research and 
experimentation.   But it was clear that some kind of mechanism would be 
needed to permit the users' computers to specify what type(s) of service 
was desired.  So, when TCP 2 was being redefined as TCP 4, a TOS field 
was added to the IP headers to carry such information.  At the time, 
gateways (routers) couldn't behave any differently based on the contents 
of the TOS field, but at least it was there to be used when the next 
generation routing mechanisms were decided and ready to deploy.

MULTIPATH ROUTING

The classic "Shortest Path First" routing algorithm, as used in the 
ARPANET, finds the lowest-delay path between a source and destination 
and then sends all packets along that route until some new information 
triggers coice of a different path.   In the ARPANET, there were 
typically a few routes across the entire country, all based on similar 
capacity circuits operating at 56 kilobits/second.  So any particular 
path would work, but the performance would be limited to that circuit 
speed.   File transfers would take longer than they could if more than 
one cross-country path was used.  If there were 3 cross-country circuits 
in the network topology, a file transfer might be able to achieve over 
100 kilobits/second if multiple paths were used.

That situation led to a desire for MultiPath Routing in the ARPANET.  In 
such a scheme, not only would the shortest path be used, but all paths 
would be used to achieve faster file transfers. Any such scheme would of 
course also have to provide for some kind of "fair" allocation of 
resources to other traffic flows between other computers over the same 
paths.

As far as I remember, such a scheme was investigated but never 
implemented in the ARPANET.  However, a similar situation would exist in 
the more complex environment of the Internet, as another item on the 
wishlist for a next generation of routing mechanisms

POLICY ROUTING

Policy Routing refers to routing decisions that are made on metrics that 
can't be readily measured during network operations.  They are set 
instead by laws, regulations, and in general policies of the 
organizations who own and operate the underlying networks.   In a 
military context, a policy might be to avoid passing your traffic 
through any "territory" controlled by "the enemy", to avoid compromise 
of sensitive information.  In a commercial context, a similar policy 
might avoid sending your traffic through a route friendly to your 
competitors.

This situation did not exist in the ARPANET, since all of the 
infrastructure was owned and operated by ARPA and later DCA.

In the early Internet, such a situation did exist, in the part of the 
Internet which provided connecivity between the US and Europe.  ARPA 
owned and operated SATNET, which used a channel on the Intelsat IV-A 
satellite.  One of the "core gateways" that BBN operated for ARPA was 
modified to have the capability to interface to the public X.25 
network.  This was termed the "VAN Gateway" in the Internet 
discussions.   In Europe, a separate gateway was also configured to 
interface to the public X.25 network.

This topology created two possible routes across the Atlantic Ocean.  
Both of these were quite expensive to use.  The SATNET channel was a 
monthly expense, and X.25 usage was charged by the number of minutes 
used on a "call" just as was common at the time for the phone system.

ARPA desired, as a policy, that use of SATNET be limited to projects 
sponsored by ARPA.   Other projects could use the Internet, but only if 
they used the X.25 route to cross the Atlantic.

The Internet routing mechanisms did not support such routing decisions.  
Both routes were simply one additional "hop" to the routing algorithm 
and thus equivalent.  The policy was implemented in a Rube Goldberg 
method, by assigning two separate network numbers to one Ethernet.  A 
computer using one of its IP addresses would pass traffic across 
SATNET.  A computer using the "other" IP address would pass traffic over 
the public X.25 infrastructure.

Clearly a better scheme was needed for the next Internet routing mechanism.

======================

The recent discussions on the internet-history list reminded me of two 
other items on the ICCB's to-do list, requiring further research.  
Here's what I remember, after almost 50 years...

END-MIDDLE INTERACTIONS

End-Middle Interactions resulted from work we did at BBN in the early 
1980s to create some tools for diagnosing Internet problems.  I'm pretty 
sure that I was the one who added it to the ICCB to-do list.

End-middle interactions resulted from examination of lots of packet 
traces of traffic through gateways as part of problem solving 
activities.  At the time, there was a lot of attention on "end-to-end" 
interactions, and the mechanisms involved, such as the TCP windowing 
scheme, IP addressing, and the like.  But if you examine the full 
contents of packets flowing through the Internet, you can easily observe 
lots of other interactions involved in every TCP connection or IP 
datagram flow.

There are many examples of this behavior.  DNS interactions are one, 
converting host names into IP addresses.  DHCP interactions are another 
example.  On Ethernets, ARP is used to convert IP addresses into 
Ethernet addresses.   Higher level protocols are also involved, such as 
SMTP and even the voluminous "headers" that appear in every email.

Some of these interactions are end-to-end between the related clients 
and servers.  However, many of them are End-To-Middle.  A good example 
is the ICMP datagrams which are sent from a gateway somewhere along a 
route, directed back to the sender of a datagram which experienced some 
kind of failure in its travels.  Even in email, there are numerous 
"header fields" such as DKIM data, which is created by some software in 
the "middle" of the email travels and added to the email headers.

The gist of the End-Middle-Interactions issue is that every piece of 
data transiting the Internet is created by some program running in some 
device along the route, and that data is not necessarily created only by 
the end device computers.   Similarly, every piece of data is put into 
the traffic flow for some reason, and is used by some device(s) along 
the route, not necessarily the one at the destination IP address.

The consequence of this architecture is that every piece of data is 
produced by some program on some device, and subsequently used by some 
other program on some other device.   Such producing and consuming does 
not necessarily happen just at the endpoints of the datagram flow.

A related consequence is that every such piece of data must be protected 
in some way that is appropriate for its purpose.  Perhaps it must be 
verified as being actually created where it purports to have been 
created and survived intact until it reached the consumer.  Perhaps it 
should only be visible to legitimate consumers of that data.  
Appropriate techniques for protecting all data must be used, regardless 
of where they are produced and consumed - not just at the endpoints of a 
TCP (or HTTP, or SMTP...) connection.

In the early 1980s Internet, we used such end-middle traffic to create a 
diagnostic tool called a "Flakeway".  A Flakeway was a piece of software 
that typically ran on a Sun workstation.  At the time, the ARPANET was 
the backbone of the Internet.  But the ARPANET provided a "virtual 
circuit" service to its users.  So IP traffic never got dropped, 
reordered, duplicated, or corrupted as it traversed the ARPANET.   It 
was difficult to exercise and diagnose TCP behavior without some way of 
causing the problems that TCP should mitigate.

The Flakeway was used by putting it's computer on the same Ethernet as 
one of the computers along the route that the IP traffic would take - 
such as a gateway or even one of the user's computers. Flakeway could 
then intercept all of the IP traffic and do nasty things such as 
dropping, delaying, duplicating, corrupting, and reordering the IP 
datagrams.   This was useful for testing how TCP reacted to such 
situations out in the wild west of the early Internet.

It was also important that a Flakeway could accomplish this without the 
need to make any changes to, or even have access to, any of the users' 
computers involved in the Internet activity.   As long as the Flakeway 
machine was on an Ethernet along the route that IP datagrams would take, 
it could do its work.

This was accomplished by noticing how ARP functioned -- one of those 
End-Middle-Interactions.  When a computer needed to convert an IP 
address into an Ethernet address, it would send out an ARP request to 
get that information.  The computer assigned that IP address would 
respond, to say that it was the owner of that IP address.

The Flakeway simply watched for these ARP interactions.   When it saw a 
response from an IP address it was told to "flake", it would simply 
follow the real response with one of its own, saying that the Flakeway 
was actually the owner of that IP address.  Since most software just 
believed the last answer, a Flakeway could easily insert itself into any 
path on which IP datagrams traveled on that Ethernet, and do its magic.

This seemed like a problem and was quietly reported to the appropriate 
"standards" organizations, including the ICCB and probably IEEE so it 
could be fixed.  In the meanwhile, it provided a mechanism for a 
valuable diagnostic tool.

RELEASE DEPLOYMENT

The planning for the January 1983 cutover of the ARPANET from NCP to TCP 
surfaced a lot of pragmatic issues, many of which were solvable largely 
because the ARPANET was owned and operated by a single management by 
DCA.  The Internet was expected to grow, even in 1983.   NSF had also 
appeared as another player, and introduced the notion of independent 
ISPs each of whom would own part of the Internet.   The growth and 
fragmentation of the Internet seemed likely to complicate any changes to 
the algorithms and protocols involved.   The experience with the 1983 
cutover also indicated that there was an enormous amount of detail 
involved in planning any transition from a current system to a new one, 
as well as during its execution.

How would one introduce a new version of IP, TCP, or any of the 
ancillary mechanisms (DNS, DHCP, SMTP, ARP, etc.), while assuring that 
service remained always operational, and that the "old" technology was 
phased out on an appropriate schedule.  We didn't know how to do that yet.

The problem of Release Deployment, and the mechanisms, plans, programs, 
and techniques to accomplish it, would be much more complex in the 
Internet than was experienced in the ARPANET.  Much more research was 
required.

======================

THE PLAN

Bob Kahn collared me at one of the Internet meetings in Europe and told 
me it was important to make the Internet "open" so that all its 
components could be built by multiple vendors.   At the time, I was 
responsible for making the "core gateways" operate as a reliable 24x7 
service.  But there were lots of other people experimenting with all 
sorts of ideas for the next generation of the Internet.

Operations and Research don't mix well, and we had been experiencing 
outages of the "core" when some research project elsewhere on the 
Internet misbehaved.   I recruited Dr. Eric Rosen and we spent some time 
musing about this situation.  The result was the concept of "Autonomous 
Systems", and a definition of EGP - the Exterior Gateway Protocol.   EGP 
was a "firewall" protocol, which allowed one piece of the Internet (a 
particular autonomous system) to insulate itself from misbehaviors in 
the other autonomous systems.

That plan was intended to provide a structure for the Internet in which 
"service" parts (such as the core gateways) could coexist with multiple 
ongoing "research" parts of the Internet, so that each autonomous system 
could operate without disruption by the others.

When the research activities produced the next generation Internet 
architecture, solving at least some of the ICCB's "need further 
research" issues, EGP would be retired and the new scheme deployed.

Meanwhile, mechanisms such as Source Routing were added to IP, to 
provide a way to get the WBNET to actually be used even when the 
hop-based routing mechanism of the time would never choose such a route.

At least, that was the vision.   It didn't quite work out that way 
though.....

Thanks for getting this far, hope you enjoyed the History,
/Jack Haverty


-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature.asc
Type: application/pgp-signature
Size: 665 bytes
Desc: OpenPGP digital signature
URL: <http://elists.isoc.org/pipermail/internet-history/attachments/20260915/04e057bf/attachment.asc>