Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!lll-lcc!ames!ucbcad!ucbvax!GATEWAY.MITRE.ORG!tsuchiya
From: tsuchiya@GATEWAY.MITRE.ORG.UUCP
Newsgroups: mod.protocols.tcp-ip
Subject: Re: Packet network reliability
Message-ID: <8704021229.AA15774@jupiter.mitre.org>
Date: Thu, 2-Apr-87 07:29:28 EST
Article-I.D.: jupiter.8704021229.AA15774
Posted: Thu Apr  2 07:29:28 1987
Date-Received: Sat, 4-Apr-87 13:49:37 EST
Sender: daemon@ucbvax.BERKELEY.EDU
Distribution: world
Organization: The ARPA Internet
Lines: 23
Approved: tcp-ip@sri-nic.arpa

> BBN gets around these two disadvantages at a cost.  The Milnet for instance
> is gettingvery large, very fast.   I don't know the formula for computing the
> amount of bandwidth required for the internal routing updates, but I would 
> suspect it would go up exponentially with the number of nodes(and connectivity
> of them).  If anybody knows the numbers I'd like to have them.

BBN C-30 based networks use an efficient flooding scheme to send routing
updates.  Each update crosses each link twice, the second time as a
robust acknowledgement.  Link overhead is therefore linear with the
number of nodes.

Better still, the algorithm they use to compute routes when a change
is received performs on the order of the average hop length of all
paths, estimated at log N/log(c-1) where N is number of nodes and
c is connectiviey.

See paper by John McQuillan, Ira Richer, and Eric Rosen, "The New
Routing Algorithm for the ARPANET," IEEE Transactions on Communications,
Vol. COM-28, No. 5, May 1980.


	Paul Tsuchiya		tsuchiya@gateway.mitre.org
	The MITRE Corp.		tsuchiya@mitre-gateway.arpa