Method and apparatus for distance vector routing on datagram point-to-point links
First Claim
1. A method for updating distance vectors in a network topology that includes multiple destinations and multiple routers, some of which are connected by datagram point-to-point links, the method comprising the steps of:
- detecting changes in a distance vector stored in a router;
upon the detection of a distance change for a destination d in the distance vector, setting a Send Flag corresponding to that destination d and corresponding to every neighboring router to provide distance vector update items;
detecting the availability of a link to a selected neighboring router n;
transmitting an information packet to the neighboring router n over the available link, the information packet containing as many as possible of the distance vector update items that are flagged by Send Flags associated with router n;
prior to transmitting the packet, selecting a unique sequence number for transmission with the packet;
storing the sequence number in a sequence number field SN(d,n) for each distance vector update item transmitted with the packet;
receiving an acknowledgment message from the neighboring router n, containing the same unique sequence number that was transmitted with the information packet; and
clearing the sequence number field in every location of the distance vector in which the unique sequence number is stored, to indicate successful transmission of the corresponding distance vector update item.
5 Assignments
0 Petitions
Accused Products
Abstract
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.
132 Citations
14 Claims
-
1. A method for updating distance vectors in a network topology that includes multiple destinations and multiple routers, some of which are connected by datagram point-to-point links, the method comprising the steps of:
-
detecting changes in a distance vector stored in a router; upon the detection of a distance change for a destination d in the distance vector, setting a Send Flag corresponding to that destination d and corresponding to every neighboring router to provide distance vector update items; detecting the availability of a link to a selected neighboring router n; transmitting an information packet to the neighboring router n over the available link, the information packet containing as many as possible of the distance vector update items that are flagged by Send Flags associated with router n; prior to transmitting the packet, selecting a unique sequence number for transmission with the packet; storing the sequence number in a sequence number field SN(d,n) for each distance vector update item transmitted with the packet; receiving an acknowledgment message from the neighboring router n, containing the same unique sequence number that was transmitted with the information packet; and clearing the sequence number field in every location of the distance vector in which the unique sequence number is stored, to indicate successful transmission of the corresponding distance vector update item.
-
-
2. A method as defined in claim and further comprising the steps of:
-
scanning for the availability of links to other neighboring routers; and repeating, for each available link, the steps of transmitting an information packet, selecting a unique sequence number, storing the sequence number in the distance vector, receiving an acknowledgment message, and clearing the appropriate sequence number fields in the distance vector, whereby distance vector updates are transmitted to all of the neighboring routers. - View Dependent Claims (3, 4, 5, 6, 7)
-
-
8. Apparatus for updating distance vectors in a network topology that includes multiple destinations and multiple routers, some of which are connected by datagram point-to-point links, the apparatus comprising:
-
means for detecting changes in a distance vector stored in a router; means responsive to the detection of a distance change for a destination d in the distance vector, for setting a Send Flag corresponding to that destination d and corresponding to every neighboring router to provide distance vector update items; means for detecting the availability of a link to a selected neighboring router n; means for transmitting an information packet to the neighboring router n over the available link, the information packet containing as many as possible of the distance vector update items that are flagged by Send Flags associated with router n; means operable prior to transmitting the packet, for selecting a unique sequence number for transmission with the packet; means for storing the sequence number in a sequence number field SN(d,n) for each distance vector update item transmitted with the packet; means for receiving an acknowledgment message from the neighboring router n, containing the same unique sequence number that was transmitted with the information packet; and means for clearing the sequence number field in every location of the distance vector in which the unique sequence number is stored, to indicate successful transmission of the corresponding distance vector update item. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
Specification