Thu, 2 Apr 87 07:29:28 EST
> 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 email@example.com
The MITRE Corp. firstname.lastname@example.org
This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:37:47 GMT