Arrangement for preventing count-to-infinity in flooding distance vector routing protocols

• US 20060007865A1
• Filed: 07/12/2004
• Published: 01/12/2006
• Est. Priority Date: 07/12/2004
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Retana, Alvaro Enrique, Cook, David Anthony, White, Russell Ivan
• Granted Patent: US 7,924,726 B2
• Time in Patent Office: Days
• US Class Current: 370/238
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/32 Flooding denial of service attacks H04L63/1458
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks

Abstract

Each router in a network is configured for generating router advertisement messages according to a flooding distance vector routing protocol. Each router advertisement message output according to the flooding distance vector routing protocol includes reachability information for at least one destination, and an originating router identifier indicating a router having originated the reachability information. If any router receiving the router advertisement message detects a match between the originating router identifier and the corresponding assigned router identifier, the received router advertisement message is disregarded during calculation of the best paths from the network. If the originating router identifier identifies another router, the router floods the received router advertisement message to other ports, and output its own router advertisement message based on the received router advertisement message and that specifies the originating router identifier from the received router advertisement message.

Claims

1. A method in a router, the method comprising:

generating a router advertisement message according to a flooding distance vector routing protocol, the router advertisement message including reachability information specifying at least one reachable destination and a corresponding cost, and an originating router identifier indicating a router having originated the reachability information; and

outputting the router advertisement message to adjacent routers according to the flooding distance vector protocol.

2. The method of claim 1, further comprising:

detecting the adjacent routers in response to detecting respective unsolicited router messages from the adjacent routers;

connecting to the adjacent routers via respective interface links; and

updating a local link state table, configured for identifying connected adjacent routers, to specify the adjacent routers, the respective interface links, and respective link status.

3. The method of claim 2, further comprising outputting to one of the adjacent routers the local link state table based on determining the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

4. The method of claim 2, wherein the generating includes originating the reachability information based on the local link state table, the originating router identifier identifying the router.

5. The method of claim 1, further comprising:

receiving from one of the adjacent routers a second router advertisement message that specifies the at least one reachable destination and a corresponding second cost, and the originating router identifier;

the generating including;

(1) disregarding the second router advertisement message based on determining the originating router identifier specified in the second router advertisement message corresponds to the router, and

(2) based on determining the originating router identifier specified in the second router advertisement message does not correspond to the router, determining the cost for the reachable destination specified in the router advertisement message based on the second cost specified in the second router advertisement message, and storing in a routing table entry the reachable destination, the corresponding cost, and the originating router identifer.

6. The method of claim 1, further comprising outputting the second router advertisement to others of the adjacent routers according to the flooding distance vector routing protocol.

7. The method of claim 1, wherein the router is a mobile router configured for attaching to a mobile ad hoc network.

8. A method in a router, the method comprising:

receiving a router advertisement message that includes reachability information specifying at least one reachable destination and a corresponding first cost, and an originating router identifier indicating a router having originated the reachability information;

determining for said at least one reachable destination a corresponding second cost for reaching the reachable destination by the router, based on the corresponding first cost;

generating a second router advertisement message, based on the router advertisement message, that includes second reachability information specifying said at least one reachable destination and the corresponding second cost, and the originating router identifier; and

outputting the router advertisement message and the second router advertisement message to an adjacent router.

9. The method of claim 8, further comprising:

detecting the adjacent router in response to detecting an unsolicited router message from the adjacent router;

connecting to the adjacent router via an interface link; and

updating a local link state table, configured for identifying connected adjacent routers, to specify the adjacent router, the corresponding interface link, and a corresponding link status.

10. The method of claim 9, further comprising outputting to the adjacent router the local link state table based on determining the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

11. The method of claim 9, further comprising:

originating third reachability information based on the local link state table;

generating a third router advertisement message that includes the third reachability information for a prescribed destination, the originating router identifier for the third router advertisement message identifying said router as the router having originated the reachability information; and

outputting the third router advertisement message to the adjacent router.

12. The method of claim 11, wherein the third reachability information specifies that the prescribed destination is unreachable.

13. The method of claim 11, wherein the router advertisement message, the second router advertisement message, and the third router advertisement message each are output according to a flooding distance vector routing protocol.

14. The method of claim 8, wherein the router is a mobile router configured for attaching to a mobile ad hoc network.

15. A router comprising:

means for generating a router advertisement message according to a flooding distance vector routing protocol, the router advertisement message including reachability information specifying at least one reachable destination and a corresponding cost, and an originating router identifier indicating a router having originated the reachability information; and

means for outputting the router advertisement message to adjacent routers according to the flooding distance vector protocol.

16. The router of claim 15, further comprising:

means for detecting the adjacent routers in response to detecting respective unsolicited router messages from the adjacent routers, the means for detecting further configured for connecting to the adjacent routers via respective interface links, and

a local link state table configured for identifying connected adjacent routers, the means for detecting configured for updating the local link state table to specify the adjacent routers, the respective interface links, and respective link status.

17. The router of claim 16, wherein the means for outputting is configured for outputting to one of the adjacent routers the local link state table based on the means for generating having determined that the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

18. The router of claim 16, wherein the means for generating is configured for originating the reachability information based on the local link state table, the originating router identifier identifying the router.

19. The router of claim 15, wherein:

the means for outputting is configured for receiving from one of the adjacent routers a second router advertisement message that specifies the at least one reachable destination and a corresponding second cost, and the originating router identifier;

the means for generating is configured for;

(1) disregarding the second router advertisement message based on determining the originating router identifier specified in the second router advertisement message corresponds to the router, and

(2) based on determining the originating router identifier specified in the second router advertisement message does not correspond to the router, determining the cost for the reachable destination specified in the router advertisement message based on the second cost specified in the second router advertisement message, and storing in a routing table entry the reachable destination, the corresponding cost, and the originating router identifer.

20. The router of claim 19, wherein the means for outputting is configured for outputting the second router advertisement to others of the adjacent routers according to the flooding distance vector routing protocol.

21. The router of claim 15, wherein the router is a mobile router configured for attaching to a mobile ad hoc network.

22. A router comprising:

means for receiving a router advertisement message that includes reachability information specifying at least one reachable destination and a corresponding first cost, and an originating router identifier indicating a router having originated the reachability information;

means for determining for said at least one reachable destination a corresponding second cost for reaching the reachable destination by the router, based on the corresponding first cost, the means for determining configured for generating a second router advertisement message, based on the router advertisement message, that includes second reachability information specifying said at least one reachable destination and the corresponding second cost, and the originating router identifier;

the means for receiving further configured for outputting the router advertisement message and the second router advertisement message to an adjacent router.

23. The router of claim 22, further comprising:

means for detecting the adjacent router in response to detecting an unsolicited router message from the adjacent router, the means for detecting further configured for connecting to the adjacent router via an interface link; and

a local link state table configured for identifying connected adjacent routers, the means for detecting configured for updating the local link state table to specify the adjacent router, the corresponding interface link, and a corresponding link status.

24. The router of claim 23, wherein the means for receiving is configured for outputting to the adjacent router the local link state table based on determining the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

25. The router of claim 23, wherein:

the means for determining is configured for originating third reachability information based on the local link state table, and generating a third router advertisement message that includes the third reachability information for a prescribed destination, the originating router identifier for the third router advertisement message identifying said router as the router having originated the reachability information;

the means for receiving configured for outputting the third router advertisement message to the adjacent router.

26. The router of claim 25, wherein the third reachability information specifies that the prescribed destination is unreachable.

27. The router of claim 25, wherein the means for receiving is configured for outputting the router advertisement message, the second router advertisement message, and the third router advertisement message according to a flooding distance vector routing protocol.

28. The router of claim 22, wherein the router is a mobile router configured for attaching to a mobile ad hoc network.

29. A computer readable medium having stored thereon sequences of instructions for causing a router to output a router advertisement message, the sequences of instructions including instructions for:

generating a router advertisement message according to a flooding distance vector routing protocol, the router advertisement message including reachability information specifying at least one reachable destination and a corresponding cost, and an originating router identifier indicating a router having originated the reachability information; and

outputting the router advertisement message to adjacent routers according to the flooding distance vector protocol.

30. The medium of claim 29, further comprising instructions for:

detecting the adjacent routers in response to detecting respective unsolicited router messages from the adjacent routers;

connecting to the adjacent routers via respective interface links; and

updating a local link state table, configured for identifying connected adjacent routers, to specify the adjacent routers, the respective interface links, and respective link status.

31. The medium of claim 30, further comprising instructions for outputting to one of the adjacent routers the local link state table based on determining the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

32. The medium of claim 30, wherein the generating includes originating the reachability information based on the local link state table, the originating router identifier identifying the router.

33. The medium of claim 29, further comprising instructions for:

receiving from one of the adjacent routers a second router advertisement message that specifies the at least one reachable destination and a corresponding second cost, and the originating router identifier;

the generating including;

(1) disregarding the second router advertisement message based on determining the originating router identifier specified in the second router advertisement message corresponds to the router, and

(2) based on determining the originating router identifier specified in the second router advertisement message does not correspond to the router, determining the cost for the reachable destination specified in the router advertisement message based on the second cost specified in the second router advertisement message, and storing in a routing table entry the reachable destination, the corresponding cost, and the originating router identifer.

34. The medium of claim 33, further comprising instructions for outputting the second router advertisement to others of the adjacent routers according to the flooding distance vector routing protocol.

35. The medium of claim 29, wherein the router is a mobile router configured for attaching to a mobile ad hoc network.

36. A computer readable medium having stored thereon sequences of instructions for causing a router to output a router advertisement message, the sequences of instructions including instructions for:

receiving a router advertisement message that includes reachability information specifying at least one reachable destination and a corresponding first cost, and an originating router identifier indicating a router having originated the reachability information;

determining for said at least one reachable destination a corresponding second cost for reaching the reachable destination by the router, based on the corresponding first cost;

generating a second router advertisement message, based on the router advertisement message, that includes second reachability information specifying said at least one reachable destination and the corresponding second cost, and the originating router identifier; and

outputting the router advertisement message and the second router advertisement message to an adjacent router.

37. The medium of claim 36, further comprising instructions for:

detecting the adjacent router in response to detecting an unsolicited router message from the adjacent router;

connecting to the adjacent router via an interface link; and

updating a local link state table, configured for identifying connected adjacent routers, to specify the adjacent router, the corresponding interface link, and a corresponding link status.

38. The medium of claim 37, further comprising instructions for outputting to the adjacent router the local link state table based on determining the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

39. The medium of claim 37, further comprising instructions for:

originating third reachability information based on the local link state table;

generating a third router advertisement message that includes the third reachability information for a prescribed destination, the originating router identifier for the third router advertisement message identifying said router as the router having originated the reachability information; and

outputting the third router advertisement message to the adjacent router.

40. The medium of claim 39, wherein the third reachability information specifies that the prescribed destination is unreachable.

41. The medium of claim 39, wherein the router advertisement message, the second router advertisement message, and the third router advertisement message each are output according to a flooding distance vector routing protocol.

42. The medium of claim 36, wherein the router is a mobile router configured for attaching to a mobile ad hoc network.

43. A network having a plurality of routers, each router configured for:

generating a router advertisement message according to a flooding distance vector routing protocol, the router advertisement message including reachability information specifying at least one reachable destination and a corresponding cost, and an originating router identifier indicating a router having originated the reachability information; and

outputting the router advertisement message to adjacent routers according to the flooding distance vector protocol.

44. The network of claim 43, each router further configured for:

detecting the adjacent routers in response to detecting respective unsolicited router messages from the adjacent routers;

connecting to the adjacent routers via respective interface links; and

updating a local link state table, configured for identifying connected adjacent routers, to specify the adjacent routers, the respective interface links, and respective link status.

45. The network of claim 44, each router further configured for outputting to one of the adjacent routers the local link state table based on determining the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

46. The network of claim 44, wherein the generating includes originating the reachability information based on the local link state table, the originating router identifier identifying the router.

47. The network of claim 43, each router further configured for:

receiving from one of the adjacent routers a second router advertisement message that specifies the at least one reachable destination and a corresponding second cost, and the originating router identifier;

the generating including;

(1) disregarding the second router advertisement message based on determining the originating router identifier specified in the second router advertisement message corresponds to the router, and

(2) based on determining the originating router identifier specified in the second router advertisement message does not correspond to the router, determining the cost for the reachable destination specified in the router advertisement message based on the second cost specified in the second router advertisement message, and storing in a routing table entry the reachable destination, the corresponding cost, and the originating router identifer.

48. The network of claim 47, each router further configured for outputting the second router advertisement to others of the adjacent routers according to the flooding distance vector routing protocol.

49. The network of claim 43, wherein at least one of the routers is a mobile router configured for attaching according to a mobile ad hoc network protocol.

50. A network having a plurality of routers, each router comprising:

means for generating a router advertisement message according to a flooding distance vector routing protocol, the router advertisement message including reachability information specifying at least one reachable destination and a corresponding cost, and an originating router identifier indicating a router having originated the reachability information; and

means for outputting the router advertisement message to adjacent routers according to the flooding distance vector protocol.

51. The network of claim 50, each router further comprising:

means for detecting the adjacent routers in response to detecting respective unsolicited router messages from the adjacent routers, the means for detecting further configured for connecting to the adjacent routers via respective interface links, and

a local link state table configured for identifying connected adjacent routers, the means for detecting configured for updating the local link state table to specify the adjacent routers, the respective interface links, and respective link status.

52. The network of claim 51, wherein the means for outputting is configured for outputting to one of the adjacent routers the local link state table based on the means for generating having determined that the corresponding interface link has maintained an active link status for at least a prescribed link stability interval.

53. The network of claim 51, wherein the means for generating is configured for originating the reachability information based on the local link state table, the originating router identifier identifying the router.

54. The network of claim 50, wherein:

the means for outputting is configured for receiving from one of the adjacent routers a second router advertisement message that specifies the at least one reachable destination and a corresponding second cost, and the originating router identifier;

the means for generating is configured for;

(1) disregarding the second router advertisement message based on determining the originating router identifier specified in the second router advertisement message corresponds to the router, and

(2) based on determining the originating router identifier specified in the second router advertisement message does not correspond to the router, determining the cost for the reachable destination specified in the router advertisement message based on the second cost specified in the second router advertisement message, and storing in a routing table entry the reachable destination, the corresponding cost, and the originating router identifer.

55. The network of claim 54, wherein the means for outputting is configured for outputting the second router advertisement to others of the adjacent routers according to the flooding distance vector routing protocol.

56. The network of claim 50, wherein at least one of the routers is a mobile router configured for attaching according to a mobile ad hoc network protocol.