[ih] Anticipating network and internetwork scaling

[John Day]

Aren’t routing and forwarding tables state?

> On Feb 2, 2025, at 20:48, John Shoch via Internet-history <internet-history at elists.isoc.org> wrote:
> 
> In the last week there have been a number of interesting comments on
> stateless gateways, which led to a broader question -- if one could have
> predicted the eventual scaling of networks and the internet.
> 
> On Jan. 26 jnc wrote:
> "I don't think we could have been thinking 'this aspect of lack of state in
> the internet packet switches [m]eans it will scale indefinitely' because I
> don't think we had any idea, at that point, about how to do path selection
> in
> a global-scale internet - so global-scale internets could not have been in
> our thinking."
> 
> On Jan. 26 Vint Cerf responded, in part:
> "I don't know that we recognized the scalability aspect
> 
> but we definitely cared a lot about statelessness of the gateways"
> 
> On Jan. 28 Len Kleinrock commented on the scalability of packet networks.
> 
> On Jan. 28 Brian Carpenter noted:
> "I just glanced through Baran's 1964 paper, and it clearly recognized
> statelessness (and a standard packet header) as important for network
> survivability and adaptive routing. But although he mentions networks
> of intercontinental size, I didn't spot any discussion of scalability
> as such.
> Interestingly, exactly the same applies to Dave Clark's 1988 "Design
> Philosophy" paper.
> In RFC 1958 [published in 1996], we did note as principle 3.3 that "All
> designs must scale readily to very many nodes per site and to many millions
> of sites".
> I guess that by then (1996) this was too obvious to ignore, and it was
> written when IPv4 address exhaustion was considered inevitable.
> Maybe somebody who knows the early literature better than me can find
> something. But it's almost as if the intrinsic scalability of stateless
> packet switching was an unnoticed and accidental property."
> 
> I certainly don't know all "the early literature" but I would be remiss if
> I did not point out that there were people who foresaw the problems of
> internetwork scalability -- and actively worked on solutions.  In
> particular, 15 years before that RFC (in 1981) Yogen Dalal wrote about the
> migration from the first generation Xerox Ethernet and internet
> architecture, to the second generation of each -- and how the desire to
> scale led (at the suggestion of Will Crowther) to the need for a large,
> flat address space and associated routing techniques:
> 
> "We have described our reasons for choosing absolute host numbers in
> internet addresses, and for using them as station
> addresses on the Ethernet channel. The host number space should
> be large enough to allow the Xerox internet architecture to have a
> life span well into the twenty-first century. 48 bits allow for
> 140,737,488 million physical hosts and mulitcast IDs each. We
> chose this size based on marketing projections for computers and
> computer-based products, and to permit easy management of the
> host number space."
> "We expect that the production of microcomputer chips will
> increase in the decades that follow, and there will be
> microprocessors in typewriters, cars, telephones, kitchen appliances,
> games, etc."
>     https://dl.acm.org/doi/pdf/10.1145/1013879.802680
> 
> This was a really expansive vision about internet scaling and necessary
> routing techniques, written about 45 years ago.  Yet Yogen and his team
> didn't just think about a "global-scale internet" -- they were already
> building one.
> 
> John
> 
> PS:  While the paper was published in 1981, the actual work had been going
> on for some years.  It was unfortunate at the time that we could not share
> the detailed work, but in general discussions with the internetworking
> community we tried to leave a trail of early breadcrumbs, which an
> interested reader might have been able to follow.  See for example, from
> IEN 19 in 1978:
> "The Implications of Hierarchical vs. Flat Address Spaces
> It should be apparent that the structure of the address space is of central
> importance: it is the major element of commonality in such an
> [internetworking] environment, and can have a profound influence on the
> naming mechanism "above" and the routing mechanism "below".
> An address space can be partitioned in a hierarchical manner, or left as a
> single uniform space. Use of a flat address space implies that:
>    1. The address given to any resource must be unique over the whole
>    domain; and,
>    2. There is no structure to the address which might aid the routing
>    process; instead, the routing mechanism must be able to handle all
>    addresses, without segmenting them into parts (i.e., there is no
>    area code [network number])."
> -- 
> Internet-history mailing list
> Internet-history at elists.isoc.org
> https://elists.isoc.org/mailman/listinfo/internet-history