Re: Packet network reliability


tsuchiya@mitre-gateway.arpa
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 tsuchiya@gateway.mitre.org
        The MITRE Corp. tsuchiya@mitre-gateway.arpa



This archive was generated by hypermail 2.0b3 on Thu Mar 09 2000 - 14:37:47 GMT