Two-hop Relay for Reducing Distance Vector Routing Information

• US 20100091823A1
• Filed: 10/13/2008
• Published: 04/15/2010
• Est. Priority Date: 10/13/2008
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Savage, Donnie Van, Retana, Alvaro, White, Russell, Sichitiu, Mihail L., Ratliff, Stanley
• Granted Patent: US 7,978,612 B2
• Time in Patent Office: Days
• US Class Current: 375/211
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04Q 2213/13098 Mobile subscriber
• CPC Class Codes: H04Q 2213/13141 Hunting for free outlet, circuit or channel
• CPC Class Codes: H04Q 2213/13196 Connection circuit/link/trunk/junction, bridge, router, gateway
• CPC Class Codes: H04Q 2213/13352 Self-routing networks, real-time routing
• CPC Class Codes: H04Q 2213/13353 Routing table, map memory
• CPC Class Codes: H04Q 2213/13389 LAN, internet
• CPC Class Codes: H04Q 3/66 Traffic distributors
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

In one embodiment, a method for using a two-hop relay includes receiving an update message for a distance vector routing protocol from a first neighbor. The update message is sent to a different neighbor. Often, it is first determined whether the receiving node is a relay node for the first neighbor in the protocol. The relay node is a node preferred to update a particular node two hops from the first neighbor. In another embodiment, a method for serving as the two-hop relay includes receiving from each neighbor a first message that includes neighbor data that indicates nodes that are in direct communication with the neighbor. A relay set of fewer than all neighbors is determined. Every node two hops from the first node is updated using only the relay set of neighbors. The relay set is sent in a second message for the protocol.

Claims

1. A method comprising:

receiving, at a node in a communications network, an update message for a distance vector routing protocol from a first neighbor of a plurality of neighbors in direct communication with the node, wherein the update message indicates a destination in the communications network and a least total cost of reaching that destination from the first neighbor; and

sending, to a different neighbor of the plurality of neighbors, the update message.

2. The method as recited in claim 1 further comprising:

determining whether the node is a relay node for the first neighbor in the distance vector routing protocol; and

if the node is the relay node for the first neighbor, then substantively immediately sending the update message to the different neighbor of the plurality of neighbors,

wherein the relay node is a node preferred by the first neighbor to update a particular node two hops from the first neighbor.

3. The method as recited in claim 2 wherein:

the method further comprises receiving filter data that indicates a filtered node address in the communications network for which data packets are not forwarded by the node; and

sending the update message to the different neighbor of the plurality of neighbors even if the update message is for the filtered node address.

4. The method as recited in claim 3 further comprising:

determining whether the update message is for the filtered node; and

if the update message is for the filtered node, then sending to the different neighbor a poison update message that indicates a prohibitive cost to reach the filtered node through the node.

5. The method as recited in claim 2 wherein sending the update message to the different neighbor further comprises sending the update message as a multicast to the plurality of neighbors.

6. The method as recited in claim 2 wherein determining whether the node is the relay node for the first neighbor further comprises:

receiving from the first neighbor a first message for the distance vector routing protocol, wherein the first message includes relay identification data that indicates the relay node; and

,

determining that the node is the relay node if the relay identification data indicates the node.

7. The method as recited in claim 6 wherein the first message is a type of neighbor discovery message for the distance vector routing protocol.

8. The method as recited in claim 6 further comprising, sending a different second message for the distance vector routing protocol to the plurality of neighbors, wherein the different message includes neighbor data that indicates the plurality of neighbors.

9. The method as recited in claim 8 wherein the relay identification data is based on the neighbor data.

10. The method as recited in claim 8 wherein the neighbor data also indicates a corresponding plurality of costs to reach the plurality of neighbors and the relay identification data is also based on the plurality of costs.

11. The method as recited in claim 8 wherein:

the second message includes willingness data that indicates a relative capacity of the node to serve as a relay node; and

,

the relay identification data is also based on the willingness data.

12. The method as recited in claim 8 wherein the second message is a type of neighbor discovery message for the distance vector routing protocol.

13. The method as recited in claim 2 further comprising, if it is determined that the node is not the relay node for the first neighbor, then,

determining whether an acknowledgement message is received for the update message within a retransmission time;

and

only sending the update message to the plurality of neighbors if it is determined that the acknowledgment message is not received within the retransmission time.

14. The method as recited in claim 2 further comprising, if it is determined that the node is not the relay node for the first neighbor, then, updating the local routing information based on the update message without sending an update message reflecting the updates to the local routing information.

15. A method comprising:

receiving, at a first node in a communications network, a first message for a distance vector routing protocol from each neighbor of a plurality of neighbors in direct communication with the first node, wherein the first message from each neighbor of the plurality of neighbors includes neighbor data that indicates a set of one or more nodes that are in direct communication with the neighbor;

determining a relay set of fewer than all neighbors of the plurality of neighbors based on the neighbor data received from every neighbor of the plurality of neighbors; and

sending to the plurality of neighbors a second message for the distance vector routing protocol, wherein the second message includes relay data that indicates the relay set,

wherein every node two hops from the first node is updated using only the relay set of neighbors.

16. The method as recited in claim 15, wherein at least one of the first message or the second message is a type of neighbor discovery message for the distance vector routing protocol.

17. The method as recited in claim 15, wherein the neighbor data also indicates a cost of reaching each node in the set of one or more nodes from the neighbor and determining a relay set is also based on the plurality of costs.

18. The method as recited in claim 15, wherein:

the first message from each neighbor of the plurality of neighbors includes willingness data that indicates a relative capacity of the neighbor to serve as a relay node; and

determining the relay set further comprises determining the relay set based on the willingness data.

19. The method as recited in claim 15, further comprising:

determining at the first node a change in nodes that can be reached from the first node; and

sending, to the plurality of neighbors, an update message that includes

node identification data that indicates the first node,

sequence data that distinguishes among multiple update messages sent by the first node for acknowledgement purposes, and

update data that indicates the change in nodes that can be reached from the first node,

wherein the update messages is forwarded substantively immediately only by the relay set of one or more neighbors.

20. An apparatus comprising:

a network interface that is configured for communicating a data packet with a packet-switched network;

logic encoded in one or more tangible media for execution and, when executed, operable to;

receive an update message for a distance vector routing protocol from a first neighbor of a plurality of neighbors in direct communication with the apparatus, wherein the update message indicates a destination in a communications network and a least total cost of reaching that destination from the first neighbor; and

send, to a different neighbor of the plurality of neighbors, the update message.

21. The apparatus as recited in claim 20, wherein the logic, when executed, is further operable to:

determine whether the apparatus is a relay node for the first neighbor in the distance vector routing protocol; and

if the apparatus is the relay node for the first neighbor, then substantively immediately send the update message to the different neighbor of the plurality of neighbors,

wherein the relay node is a node preferred by the first neighbor to update a particular node two hops from the first neighbor.

22. The apparatus as recited in claim 21 wherein:

the logic, when executed, is further operable to receive filter data that indicates a filtered node in the communications network for which data packets are not forwarded by the apparatus; and

the logic, when executed to send the update data is further operable to send the update message to the different neighbor of the plurality of neighbors even if the update message is for the filtered node.

23. The apparatus as recited in claim 22 wherein the logic, when executed, is further operable to:

determine whether the update message is for the filtered node; and

if the update message is for the filtered node, then sending to the different neighbor a poison update message that indicates a prohibitive cost to reach the filtered node through the node.

24. The apparatus as recited in claim 21 wherein the logic operable to determine whether the apparatus is the relay node for the first neighbor is further operable to:

receive from the first neighbor a first message for the distance vector routing protocol, wherein the first message includes relay identification data that indicates the relay node; and

,

determine that the apparatus is the relay node if the relay identification data indicates the apparatus.

25. The apparatus as recited in claim 24 wherein the first message is a type of neighbor discovery message for the distance vector routing protocol.

26. The apparatus as recited in claim 24 wherein the logic, when executed, is further operable to send a different second message for the distance vector routing protocol to the plurality of neighbors, wherein the different message includes neighbor data that indicates the plurality of neighbors.

27. The apparatus as recited in claim 26 wherein the relay identification data is based on the neighbor data.

28. The apparatus as recited in claim 26 wherein the second message is a type of neighbor discovery message for the distance vector routing protocol.

29. The apparatus as recited in claim 21 wherein, if it is determined that the apparatus is not the relay node for the first neighbor, the logic is further operable to then,

determine whether an acknowledgement message is received for the update message within a retransmission time;

and

only send the update message to the plurality of neighbors if it is determined that the acknowledgment message is not received within the retransmission time.

30. An apparatus comprising:

a network interface that is configured for communicating a data packet with a packet-switched network;

logic encoded in one or more tangible media for execution and, when executed, operable to;

receive a first message for a distance vector routing protocol from each neighbor of a plurality of neighbors in direct communication with the apparatus, wherein the first message from each neighbor of the plurality of neighbors includes neighbor data that indicates a set of one or more nodes that are in direct communication with the neighbor;

determine a relay set of fewer than all neighbors of the plurality of neighbors based on the neighbor data received from every neighbor of the plurality of neighbors; and

send to the plurality of neighbors a second message for the distance vector routing protocol, wherein the second message includes relay data that indicates the relay set,

wherein each neighbor in the relay set is a neighbor preferred to update a particular node two hops from the apparatus, and every node two hops from the apparatus is updated using only the relay set of neighbors.