System for determining reachablity of a neighboring node in a network

• US 7,720,006 B1
• Filed: 08/06/2003
• Issued: 05/18/2010
• Est. Priority Date: 08/06/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Yadav, Navindra
• Primary Examiner(s): Rao; Seema S
• Assistant Examiner(s): Davenport; Mon Cheri S
• Application Number:
  US10/636,347
• Time in Patent Office: 2,477 Days
• Field of Search: 370/400, 370/254, 370/255, 370/238, 370/392, 370/449, 370/432
• US Class Current: 370/255
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

A system for determining reachablity of a neighboring node from a node. A packet is received over a network by node. The packet has a destination address of a node other than the receiving node. The node reads a source address from the packet. The node then determines whether the source address is for a neighboring node in which the node has an interest. The node then determines whether the packet indicates a forward link from the node to the neighboring node. Reachablity information for the neighboring node is then stored in a memory responsive to a determination of the forward link.

Claims

1. A system for determining reachability of a neighboring node from a node in a network, comprising:

circuitry configured to receive a packet having a destination address for a node other than said node;

circuitry configured to read a source address from said packet responsive to receiving said packet;

circuitry configured to determine whether said source address is for a neighboring node for which said node needs to determine reachability;

circuitry configured to make a reachability determination for said neighboring node according to whether said packet indicates a forward link from said node to said neighboring node, with said reachability determination based on one or more of a destination address for the packet, a source port for the packet, a destination port for the packet, an acknowledgement number, or sequence numbers from the packet, wherein the node sends fewer solicitation and response messages over the network as a result of the reachability determination; and

circuitry configured to store reachability information for said neighboring node responsive to a determination of said forward link.

2. The system of claim 1 wherein said circuitry configured to determine whether said packet indicates a forward link comprises:

circuitry configured to determine whether said packet includes an advertisement.

3. The system of claim 2 wherein said circuitry configured to determine whether said packet indicates a forward link further comprises:

circuitry configured to read a solicitation bit from said packet responsive to a determination that said packet includes said advertisement; and

circuitry configured to determine whether said solicitation bit is set.

4. The system of claim 3 wherein said circuitry configured to store said reachability information comprises:

circuitry configured to add said source address of said packet to said neighbor cache in a memory.

5. The system of claim 4 wherein said circuitry configured to store said reachability information further comprise:

circuitry configured to determine whether said source address is stored in said neighbor cache wherein said source address is added to said neighbor cache responsive to a determination that said source address is not contained in said neighbor cache.

6. The system of claim 4 further comprising:

circuitry configured to determine whether said neighbor cache is full; and

circuitry configured to generate an interrupt for a software application responsive to a determination that said neighbor cache is full.

7. The system of claim 1 wherein said circuitry configured to determine whether said source address for a neighboring node comprises:

circuitry configured to determine whether said source address is included in an interest table.

8. The system of claim 7 wherein said circuitry configured to store said reachability information further comprises:

circuitry configured to read a destination address from said packet; and

circuitry configured to said store said destination address in an entry in said interest table for said source address.

9. The system of claim 7 wherein said circuitry configured to store said reachability information further comprises:

circuitry configured to determine a source port from said packet; and

circuitry configured to said store said source port in an entry in said interest table for said source address.

10. The system of claim 7 wherein said circuitry configured to store said reachability information further comprises:

circuitry configured to determine a destination port for said packet; and

circuitry configured to said store said destination port in an entry in said interest table for said source address.

11. The system of claim 7 wherein said circuitry configured to store said reachability information further comprises:

circuitry configured to read an acknowledgement for said packet; and

circuitry configured to said store said acknowledgement in an entry in said interest table for said source address.

12. The system of claim 7 wherein said circuitry configured to store said reachability information further comprises:

circuitry configured to read sequence numbers from said packet; and

circuitry configured to store said sequence numbers in an entry in said interest table for said source address.

13. The system of claim 7 wherein said circuitry configured to store said reachability information further comprises:

circuitry configured to determine whether said interest table is full; and

circuitry configured to generate an interrupt for a software application responsive to a determination that said interest table is full.

14. The system of claim 13 further comprising:

computer executable instructions of said software application for directing a processing unit to;

read said reachability information for an entry, and

store said reachability information in a neighbor reachability database; and

a media readable by said processing unit for storing said instructions.

15. The system of claim 14 wherein said instructions comprise:

instructions for directing said processing unit to;

determine whether said interest table includes at least one entry,

read a subsequent entry responsive to a determination that said interest table includes at least one entry, and

store said reachability information from said entry in said neighbor reachability database.

16. The system of claim 7 further comprising:

circuitry configured to determine reachability information for said neighboring node having an address that is stale; and

circuitry configured to insert said address into said interest table responsive to a determination that said reachability information for said neighboring node is stale.

17. The system of claim 7 wherein said circuitry configured to determine whether said source address is for a neighboring node comprises:

circuitry configured to perform a reverse path forwarding lookup for said packet responsive to a determination that said source address is in said interest table.

18. The system of claim 17 wherein said circuitry configured to store said reachability information comprises:

circuitry configured to update an entry for said source address in said interest table with data returned from said reverse path forwarding lookup.

19. The system of claim 1 further comprising:

circuitry configured to write said packet to a queue.

20. The system of claim 19 wherein said circuitry configured to determine whether said packet indicates a forward link comprises:

circuitry configured to read said packet from said queue;

circuitry configured to read a source address from said packet;

circuitry configured to perform a reverse path lookup for said packet responsive to reading said source address; and

circuitry configured to update a reachability module with information received from said performing of said reverse forward path lookup.

21. A method for determining reachability of a neighboring node from a node in a network, comprising:

receiving a packet over said network wherein said packet has a destination address of a node other than said node;

reading a source address from said packet responsive to receiving said packet;

determining whether said source address is for a neighboring node for which said node needs to determine reachability, the determining performed according to whether said source address is included in an interest table storing addresses of neighboring nodes for which the node requires reachability information;

making a reachability determination for said neighboring node according to whether said packet indicates a forward link from said node to said neighboring node, with said reachability determination based on one or more of a destination address from the packet, a source port for the packet, a destination port for the packet, an acknowledgement number, or sequence numbers from the packet; and

storing reachability information for said neighboring node in a memory responsive to a determination of said forward link wherein the node sends fewer solicitation and response messages over the network at a result of the reachability determination.

22. The method of claim 21 wherein said step for determining whether said packet indicates a forward link comprises:

determining whether said packet includes an advertisement.

23. The method of claim 22 wherein said step of determining whether said packet indicates a forward link further comprises:

reading a solicitation bit from said packet responsive to a determination that said packet includes said advertisement; and

determining whether said solicitation bit is set.

24. The method of claim 23 wherein said step of storing said reachability information comprises:

adding said source address of said packet to said neighbor cache in a memory.

25. The method of claim 24 wherein said step of storing said reachability information further comprise:

determining whether said source address is stored in said neighbor cache wherein said source address is added to said neighbor cache responsive to a determination that said source address is not contained in said neighbor cache.

26. The method of claim 24 further comprising:

determining whether said neighbor cache is full; and

generating an interrupt for a software application responsive to a determination that said neighbor cache is full.

27. The method of claim 21 wherein said step of storing said reachability information further comprises:

reading a destination address from said packet; and

storing said destination address in an entry in said interest table for said source address.

28. The method of claim 21 wherein said step of storing said reachability information further comprises:

determining a source port from said packet; and

storing said source port in an entry in said interest table for said source address.

29. The method of claim 21 wherein said step of storing said reachability information further comprises:

determining a destination port for said packet; and

storing said destination port in an entry in said interest table for said source address.

30. The method of claim 21 wherein said step of storing said reachability information further comprises:

determining an acknowledgement for said packet; and

storing said acknowledgement in an entry in said interest table for said source address.

31. The method of claim 21 wherein said step of storing said reachability information further comprises:

reading sequence numbers from said packet; and

storing said sequence numbers in an entry in said interest table for said source address.

32. The method of claim 21 wherein said step of storing said reachability information further comprises:

determining whether said interest table is full; and

generating an interrupt for a software application responsive to a determination that said interest table is full.

33. The method of claim 32 further comprising:

reading said reachability information from an entry of said interest table; and

storing said reachability information in a neighbor reachability database.

34. The method of claim 33 further comprising:

determining whether said interest table includes at least one entry;

reading a subsequent entry responsive to a determination that said interest table includes at least one entry; and

storing said reachability information from said entry in said neighbor reachability database.

35. The method of claim 21 further comprising:

determining reachability information for said neighboring node having an address that is stale; and

inserting said address into said interest table responsive to a determination that said reachability information for said neighboring node is stale.

36. The method of claim 21 wherein said step of determining whether said source address is for a neighboring node comprises:

performing a reverse path forwarding lookup for said packet responsive to a determination that said source address is in said interest table.

37. The method of claim 21 wherein said step of storing said reachability information comprises:

updating an entry for said source address in said interest table with data returned from said reverse path forwarding lookup.

38. The method of claim 21 further comprising:

writing said packet to a queue.

39. The method of claim 38 wherein said determining whether said packet indicates a forward link comprises:

reading said packet from said queue;

reading a source address from said packet;

performing a reverse path lookup for said packet responsive to reading said source address; and

updating a reachability module with information received from said performing of said reverse forward path lookup.

40. A computer readable medium carrying one or more sequences of one or more instructions for determining reachability of a neighboring node from a node in a network, the one or more sequences of instructions including instructions which, when executed by one or more processors, cause one or more processors to perform a method comprising:

receiving a packet transmitted over said network wherein said packet has a destination address of a node other said node;

reading a source address from said packet responsive to receiving said packet;

determining whether said source address is for a neighboring node for which said node needs to determine reachability, the determining performed according to whether said source address is included in an interest table storing addresses of neighboring nodes for which the node requires reachability information;

making a reachability determination for said neighboring node according to whether said packet indicates a forward link from said node to said neighboring node, with said reachability determination based on one or more of a destination address from the packet, a source port for the packet, a destination port for the packet, an acknowledgement number, or sequence numbers from the packet; and

storing reachability information for said neighboring node responsive to a determination of said forward link wherein the node sends fewer solicitation and response messages over the network at a result of the reachability determination.

41. The computer readable medium of claim 40 wherein said step of determining whether said packet indicates a forward link in said method comprises:

determining whether said packet includes an advertisement.

42. The computer readable medium of claim 41 wherein said step of determining whether said packet indicates a forward link further in said method comprises:

reading a solicitation bit from said packet responsive to a determination that said packet includes said advertisement, and determining whether said solicitation bit is set.

43. The computer readable medium of claim 42 wherein said step of storing said reachability information in said method comprises:

adding said source address of said packet to said neighbor cache in a memory.

44. The computer readable medium of claim 43 wherein said step of storing said reachability information in said method further comprises:

determining whether said source address is stored in said neighbor cache wherein said source address is added to said neighbor cache responsive to a determination that said source address is not contained in said neighbor cache.

45. The computer readable medium of claim 43 wherein said method further comprises:

determining whether said neighbor cache is full; and

generating an interrupt for a software application responsive to a determination that said neighbor cache is full.

46. The computer readable medium of claim 40 wherein said step of storing said reachability information in said method comprises:

reading a destination address from said packet, and

storing said destination address in an entry in said interest table for said source address.

47. The computer readable medium of claim 40 wherein said step of storing said reachability information in said method further comprises:

determining a source port from said packet, and

storing said source port in an entry in said interest table for said source address.

48. The computer readable medium of claim 40 wherein said step of storing said reachability information in said method further comprises:

determining a destination port for said packet; and

storing said destination port in an entry in said interest table for said source address.

49. The computer readable medium of claim 40 wherein said step of storing said reachability information in said method further comprises:

determining an acknowledgement for said packet; and

storing said acknowledgement in an entry in said interest table for said source address.

50. The computer readable medium of claim 40 wherein said step of storing said reachability information in said method further comprises:

reading sequence numbers from said packet; and

storing said sequence numbers in an entry in said interest table for said source address.

51. The computer readable medium of claim 40 wherein said step of storing said reachability information in said method further comprises:

determining whether said interest table is full; and

generating an interrupt for a software application responsive to a determination that said interest table is full.

52. The computer readable medium of claim 51 wherein said method further comprises:

reading said reachability information for an entry; and

storing said reachability information in a neighbor reachability database.

53. The computer readable medium of claim 52 wherein said method further comprises:

determining whether said interest table includes at least one entry;

reading a subsequent entry responsive to a determination that said interest table includes at least one entry, and storing said reachability information from said entry in said neighbor reachability database.

54. The computer readable medium of claim 40 wherein said method further comprises:

determining reachability information for said neighboring node having an address that is stale; and

inserting said address into said interest table responsive to a determination that said reachability information for said neighboring node is stale.

55. The computer readable medium of claim 40 wherein said step of determining whether said source address is of a neighboring node in said method comprises:

performing a reverse path forwarding lookup for said packet responsive to a determination that said source address is in said interest table.

56. The computer readable medium of claim 40 wherein said step of storing said reachability information in said method comprises:

updating an entry for said source address in said interest table with data returned from said reverse path forwarding lookup.

57. The computer readable medium of claim 40 wherein said method further comprises:

writing said packet to a queue.

58. The computer readable medium of claim 57 wherein said step of determining whether said packet indicates a forward link in said method comprises:

reading said packet from said queue;

reading a source address from said packet;

performing a reverse path lookup for said packet responsive to reading said source address; and

updating a reachability module with information received from said performing of said reverse forward path lookup.

59. An apparatus for determining reachability of a neighboring node from a node in a network, comprising:

means for receiving a packet over said network wherein said packet has a destination address of a node other than said node;

means for reading a source address from said packet responsive to receiving said packet;

means for determining whether said source address is for a neighboring node for which said node needs to determine reachability, wherein said neighboring node comprises a switch, a desktop computer system, a laptop computer, a workstation, or a server computer;

means for making a reachability determination for said neighboring node according to whether said packet indicates a forward link from said node to said neighboring node, with said reachability determination based solely on information in said packet, wherein the node sends fewer solicitation and response messages over the network as a result of the reachability determination; and

means for storing reachability information for said neighboring node in a memory responsive to a determination of said forward link.

60. The apparatus of claim 59 wherein said means for determining whether said packet indicates a forward link comprises:

means for determining whether said packet includes an advertisement.

61. The apparatus of claim 60 wherein said means for determining whether said packet indicates a forward link further comprises:

means for reading a solicitation bit from said packet responsive to a determination that said packet includes said advertisement; and

means for determining whether said solicitation bit is set.

62. The apparatus of claim 61 wherein said means for storing said reachability information comprises:

means for adding said source address of said packet to said neighbor cache in a memory.

63. The apparatus of claim 62 wherein said means for storing said reachability information further comprise:

means for determining whether said source address is stored in said neighbor cache wherein said source address is added to said neighbor cache responsive to a determination that said source address is not contained in said neighbor cache.

64. The apparatus of claim 62 further comprising:

means for determining whether said neighbor cache is full; and

means for generating an interrupt for a software application responsive to a determination that said neighbor cache is full.

65. The apparatus of claim 59 wherein said means for determining whether said source address is for a neighboring node comprises:

means for determining whether said source address is included in an interest table.

66. The apparatus of claim 65 wherein said means for storing said reachability information further comprises:

means for reading a destination address from said packet; and

means for storing said destination address in an entry in said interest table for said source address.

67. The apparatus of claim 65 wherein said means for storing said reachability information further comprises:

means for determining a source port from said packet; and

means for storing said source port in an entry in said interest table for said source address.

68. The apparatus of claim 65 wherein said means for storing said reachability information further comprises:

means for determining a destination port for said packet; and

means for storing said destination port in an entry in said interest table for said source address.

69. The apparatus of claim 65 wherein said means for storing said reachability information further comprises:

means for determining an acknowledgement for said packet; and

means for storing said acknowledgement in an entry in said interest table for said source address.

70. The apparatus of claim 65 wherein said means for storing said reachability information further comprises:

means for reading sequence numbers from said packet; and

means for storing said sequence numbers in an entry in said interest table for said source address.

71. The apparatus of claim 65 wherein said means for storing said reachability information further comprises:

means for determining whether said interest table is full; and

means for generating an interrupt for a software application responsive to a determination that said interest table is full.

72. The apparatus of claim 71 further comprising:

means for reading said reachability information from an entry of said interest table; and

means for storing said reachability information in a neighbor reachability database.

73. The apparatus of claim 72 further comprising:

means for determining whether said interest table includes at least one entry;

means for reading a subsequent entry responsive to a determination that said interest table includes at least one entry; and

means for storing said reachability information from said entry in said neighbor reachability database.

74. The apparatus of claim 65 further comprising:

means for determining reachability information for said neighboring node having an address that is stale; and

means for inserting said address into said interest table responsive to a determination that said reachability information for said neighboring node is stale.

75. The apparatus of claim 65 wherein said means for determining whether said source address is for a neighboring node comprises:

means for performing a reverse path forwarding lookup for said packet responsive to a determination that said source address is in said interest table.

76. The apparatus of claim 65 wherein said means for storing said reachability information comprises:

means for updating an entry for said source address in said interest table with data returned from said reverse path forwarding lookup.

77. The apparatus of claim 59 further comprising:

means for writing said packet to a queue.

78. The apparatus of claim 77 wherein said means for determining whether said packet indicates a forward link comprises:

means for reading said packet from said queue;

means for reading a source address from said packet;

means for performing a reverse path lookup for said packet responsive to reading said source address; and

means for updating a reachability module with information received from said performing of said reverse forward path lookup.