Two-hop relay for reducing distance vector routing information

• US 7,978,612 B2
• Filed: 10/13/2008
• Issued: 07/12/2011
• 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: Ratliff, Stanley, Savage, Donnie Van, Retana, Alvaro, White, Russell, Sichitiu, Mihail L.
• Primary Examiner(s): Sefcheck; Gregory B
• Application Number:
  US12/250,446
• Publication Number:
  US 20100091823A1
• Time in Patent Office: 1,002 Days
• Field of Search: None
• US Class Current: 370/238
• 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, wherein the update message indicates a destination in the communications network and a least total cost of reaching that destination from the first neighbor, wherein the node is configured to filter at least one change in cost for a selected network address such that it is not forwarded;

sending, to a different neighbor of the plurality of neighbors, the update message, wherein if the change in cost for the selected network address is for a sole address provided in the update message, then the update message is not forwarded by the node;

sending the update message to the different neighbor of the plurality of neighbors if the node is a relay node for the first neighbor, wherein the relay node is a node preferred by the first neighbor to update a particular node a certain number of hops from the first neighbor;

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

sending to the different neighbor a poison update message that indicates a prohibitive cost to reach the filtered node address through the node.

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

3. The method as recited in claim 1, 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.

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

5. The method as recited in claim 3 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.

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

7. The method as recited in claim 5 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.

8. The method as recited in claim 5 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.

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

10. The method as recited in claim 1, further comprising:

if it is determined that the node is not the relay node for the first neighbor, then,

determining whether an acknowledgment 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.

11. The method as recited in claim 1, 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.

12. 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, wherein the first message from each neighbor of the plurality of neighbors includes a 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, wherein the first node is configured to filter at least one change in cost associated with reaching a destination for a selected network address such that it is not forwarded; 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 the relay set of neighbors;

determining whether a particular message is for a filtered node address; and

sending to a particular neighbor a poison update message that indicates a prohibitive cost to reach the filtered node address through the first node.

13. The method as recited in claim 12, 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.

14. The method as recited in claim 12, 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.

15. The method as recited in claim 12, 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.

16. An apparatus comprising:

a network interface that is part of a node and 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, wherein the update message indicates a destination in a communications network and a least total cost of reaching that destination from the first neighbor, wherein the node is configured to filter at least one change in cost for a selected network address such that it is not forwarded as part of the update message;

send, to a different neighbor of the plurality of neighbors, the update message, wherein if the change in cost for the selected network address is for a sole address provided in the update message, then the update message is not forwarded by the node;

send the update message to the different neighbor of the plurality of neighbors if the node is a relay node for the first neighbor, wherein the relay node is a node preferred by the first neighbor to update a particular node two hops from the first neighbor;

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

send to the different neighbor a poison update message that indicates a prohibitive cost to reach the filtered node address.

17. The apparatus as recited in claim 16, 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.

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

19. The apparatus as recited in claim 17 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.

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

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

22. The apparatus as recited in claim 16, 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 acknowledgment 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.