Method and apparatus for distance vector routing on datagram point-to-point links

Claim 4

A method as defined in claim 2, wherein the step of transmitting the information packet includes: scanning the distance vector for update items that have not yet been transmitted; storing each located update item in the information packet; and when the packet is full, initiating its transmission.

Claim 5

A method as defined in claim 3, wherein the step of transmitting the information packet includes the additional step of: checking to determine whether a selected number of destination items in the distance vector have been scanned; and if so, initiating transmission of the packet even if it is not full.

Claim 6

A method as defined in claim 3, wherein: the step of scanning the distance vector is performed on a round-robin basis, wherein scanning begins, for a particular neighboring router, at a destination item following the one last scanned prior to initiating transmission of the last information packet to the same neighboring router.

Claim 7

A method as defined in claim 2, and further comprising the steps of: receiving at a neighboring router a distance vector update packet; updating a distance vector at the receiving router in accordance with the information received in the distance vector update packet; and transmitting an acknowledgment message to the router from which distance vector the update packet was received, wherein the acknowledgment message includes the same unique sequence number that was contained in the received distance vector update packet.

Claim 8

A method as defined in claim 2, and further comprising the steps of: periodically saving the sequence number of the last information packet transmitted by the router; periodically retrieving the sequence number of the last information packet transmitted a selected time period earlier; scanning the distance vector for the sequence numbers equal to or less than the retrieved sequence number, whereby these numbers indicate distance vector update items that have been transmitted but not acknowledged for more than the selected time period; clearing any located sequence numbers located in the preceding step; and setting the Send Flags corresponding to the sequence numbers cleared in the preceding step, whereby the distance vector update items corresponding to the unacknowledged transmissions are flagged for retransmission.

Claim 9

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.

Claim 10

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.

Claim 11

Apparatus as defined in claim 8, wherein: the apparatus further comprises means for scanning for the availability of links to other neighboring routers; and the means for 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, are all operable to transmit distance vector updates to the other neighboring routers.

Claim 12

Apparatus as defined in claim 9, wherein the means for transmitting the information packet includes: means for scanning the distance vector for update items that have not yet been transmitted; means for storing each located update item in the information packet; and means activated when the packet is full, for initiating its transmission.

Claim 13

Apparatus as defined in claim 10, wherein the means for transmitting the information packet includes: means for checking to determine whether a selected number of destination items in the distance vector have been scanned; and means responsive to the last-recited means, for initiating transmission of the packet even if it is not full.

Claim 14

Apparatus as defined in claim 10, wherein: the means for scanning the distance vector operates on a round-robin basis, wherein scanning begins, for a particular neighboring router, at a destination item following the one last scanned prior to initiating transmission of the last information packet to the same neighboring router.

Claim 15

Apparatus as defined in claim 9, and further comprising: means for receiving at a neighboring router a distance vector update packet; means for updating a distance vector at the receiving router in accordance with the information received in the distance vector update packet; and means for transmitting, an acknowledgment message to the router from which the distance vector update packet was received, wherein the acknowledgment message includes the same unique sequence number that was contained in the received distance vector update packet.

Claim 16

Apparatus as defined in claim 9, and further comprising the steps of: means for periodically saving the sequence number of the last information packet transmitted by the router; means for periodically retrieving the sequence number of the last information packet transmitted a selected time period earlier; means for scanning the distance vector for the sequence numbers equal to or less than the retrieved sequence number, whereby these numbers indicate distance vector update items that have been transmitted but not acknowledged for more than the selected time period; means for clearing any located sequence numbers located in the preceding step; and means for setting the Send Flags corresponding to the sequence numbers cleared by the last-recited step, whereby the distance vector update items corresponding to the unacknowledged transmissions are flagged for retransmission.