Digital Equipment Corporation

George A Harvey

Radia Joy Perlman

Robert E Thomas

William R Hawe

Anthony G Lauck

George Varghese

John A Harper

David R Oran

Robert J Souza

Kevin Miles

Gerard Koning

A technique for distributing updated distance vectors used in routers, which are connected by point-to-point links having datagram service. Distance vectors are used by routers to route messages over the most desirable paths, but must be continually modified as a result of update messages passed between routers, to reflect changes in network topology. Datagram service does not normally ensure that such update messages will reach other routers, but the technique of the invention uses unique sequence numbers on all information packets containing distance vector update messages, and achieves efficient and timely distribution of updated distance vector information with only a modest storage requirements. Unlike reliable service, which requires each message to be delivered exactly once and in the order sent, the invention allows subsequent update messages to be delivered to the same neighboring router even if previous messages have not yet been received and processed. The invention also provides for retransmission of unacknowledged distance vector information, but without the burden of having to store all transmitted packets until they are acknowledged.

Method and apparatus for distance vector routing on datagram

A packet data communication network employs sequence numbers in message packets to identify the packets transmitted for a message, so that the order of packets can be checked, and so that the occurrence of lost or duplicated packets can be detected. A method of keeping track of these sequence numbers is provided. Any number below or above a bounded sequence number acceptance window is ignored (not accepted). Bit maps are established for the range of numbers within the bounded window, each bit representing a sequence number and the bit maps indexed by sequence number. One bit map is a received packet map, used to keep track of which sequence numbers have been received and thus to filter duplicate sequence numbers. An end-of-message bit map is used to record the positions of packets having end-of-message flags, and this is used with the received packet map to determine whether all packets of a message have been received, so that an end-of-message trigger can be generated. The sequence number and an end-of-message flag from an incoming packet are used to update these bit maps as each packet is received, then the updated bit maps used to determine the needed action. Two methods are described for tracking these sequence numbers. Both methods have good average-case performance. The first method uses an iterative loop and is more suited for software implementation. The second method uses table lookup to replace the iterative loop and is more suited for hardware implementation. This method has very good worst-case performance.

Tracking sequence numbers in packet data communication system

A distributed digital data processing system includes a plurality of nodes which communicate over a network. A node maintains one or more objects, each of which may be a file, that is, an addressable unit in the system, such as a program, database, text file, or the like, or a directory which may contain one or more files or other directories. One node maintains a naming service which associates each object in the system with one or more protocol towers. Each protocol tower identifies the object name and a series of entries each identifying a name for each of the protocol layers, along with the communications parameters and address information, to be used in communicating with the object. When a node requires access to an object maintained by another node, it first retrieves from the naming service the protocol towers for the object. The node also maintains a tower identifying the names of each of the protocols over which it can communicate. The node then compares the protocol names in the retrieved protocol towers with the protocol names over which it can communicate. If the protocol names in a retrieved tower match the protocol names in the node's tower, the node uses the communications parameters and address information in future communications with the object. If the node is unable to identify a retrieved protocol tower which matches its supported tower or towers, it is unable to communicate with the object.

Session control in network for digital data processing system which

Growing community of inventors

Maynard, MA, United States of America

George A Harvey