Determining a route advertisement in a reactive routing environment

• US 9,191,227 B2
• Filed: 03/24/2014
• Issued: 11/17/2015
• Est. Priority Date: 12/03/2007
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: White, Russell I., Moore, Steven Edward, Ng, James L., Retana, Alvaro Enrique
• Primary Examiner(s): Abelson, Ronald B
• Application Number:
  US14/223,873
• Publication Number:
  US 20140269734A1
• Time in Patent Office: 603 Days
• Field of Search: 370/395.54, 370/390, 370/401, 370/389, 709/238, 709/220, 709/247
• US Class Current: 1/1
• CPC Class Codes: H04L 12/28 characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks] wireless communication networks H04W ; arrangements for dividing the transmission path H04W40/00
• 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
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

In an example embodiment, a method and system is provided to determine and advertise a route advertisement in a reactive routing environment. In response to receiving a network address query with respect to a destination address at a routing device, an aggregate value, e.g. an address prefix, is determined and advertised in reply to the network address query. Determining of the aggregate value may comprise identifying within a range of network addresses represented by the aggregate value respective addresses for which the routing device does not have reachability information. The routing device may send address queries with respect to the identified addresses, to determine reachability via the routing device of those addresses. The aggregate value may be advertised conditional upon determining that a percentage of addresses within the corresponding range that can be reached via the routing device satisfies a predefined minimal coverage value.

Claims

1. A method comprising:

at a routing device in a computer network, receiving a network address query with respect to a destination address;

at the routing device, determining an advertisement value representing a network address range that includes the destination address, the determining of the advertisement value comprising;

calculating a coverage value that indicates a portion of addresses within the network address range that can be reached through the routing device, and

determining that the calculated coverage value meets or exceeds a predefined threshold coverage value; and

replying to the network address query by advertising the advertisement value.

2. The method of claim 1, further comprising:

at the routing device, receiving a second network address query with respect to a second destination address;

at the routing device, determining a candidate advertisement value representing a second network address range that includes the second destination address;

calculating a second coverage value that indicates a respective portion of addresses within the second network address range that can be reached through the routing device;

determining that the second coverage value is smaller than the predefined threshold coverage value; and

based on the determination that the second coverage value smaller than the predefined threshold coverage value, replying to the second network address query by advertising a value other than the candidate advertisement value.

3. The method of claim 1, wherein the determining of the advertisement value comprises identifying from a local routing table of the routing device one or more addresses which are within the network address range and for which the routing device does not have reachability information that indicates whether or not the respective addresses can be reached via the routing device.

4. The method of claim 3, further comprising, in response to the identifying of the one or more addresses, sending one or more queries from the routing device with respect to the one or more addresses, to determine whether or not the one or more addresses can be reached via a routing device.

5. The method of claim 1, wherein the determining of the advertisement value further comprises:

identifying a candidate aggregate value representing a larger range of network addresses than the network address range corresponding to the advertisement value, the larger range of network addresses including the destination address;

calculating a candidate coverage value that indicates a respective portion of addresses within the larger range of network addresses that can be reached through the routing device; and

determining that the candidate coverage value is smaller than the predefined threshold coverage value.

6. The method of claim 1, wherein the advertisement value is a network address prefix, the determining of the advertisement value comprising identifying a shortest network address prefix of which the corresponding coverage value meets or exceeds the predefined threshold coverage value.

7. The method of claim 6, wherein the determining of the advertisement value comprises recursively determining whether or not progressively shorter network address prefixes corresponding to progressively larger network address ranges have respective coverage values that meet or exceed the predefined threshold coverage value.

8. The method of claim 1, wherein the predefined threshold coverage value is a threshold proportion of addresses within the network address range that are reachable via the routing device.

9. The method of claim 8, wherein the threshold proportion is 100%.

10. The method of claim 8, wherein the threshold proportion is less than 100%.

11. A routing device comprising:

a first receiver configured to receive, in a reactive routing environment, a network address query with respect to a destination address;

a calculation engine configured to determine an advertisement value representing a network address range that includes the destination address the calculation engine being configured to determine the aggregate value by performing operations comprising;

calculating a coverage value that indicates a portion of addresses within the network address range that can be reached through the routing device, and

determining that the calculated coverage value meets or exceeds a predefined threshold coverage value; and

an advertising engine configured to reply to the network address query by advertising the advertisement value.

12. The routing device of claim 11, wherein:

the first receiver is further configured to receive a second network address query with respect to a second destination address;

the calculation engine is further configured to determine a candidate advertisement value representing a second network address range that includes the second destination address, the calculation engine being configured to determine the candidate advertisement value by performing operations comprising;

calculating a second coverage value that indicates a respective portion of addresses within the second network address range that can be reached through the routing device, and

determining that the second coverage value is smaller than the predefined threshold coverage value; and

the advertising engine is further configured to reply to the second network address query by advertising a value other than the candidate advertisement value, based on the determination that the second coverage value is smaller than the predefined threshold coverage value.

13. The routing device of claim 11, wherein the calculation engine is further configured such that the operations for determining the candidate advertisement value comprises identifying from a local routing table of the routing device one or more addresses which are within the network address range and for which the routing device does not have reachability information that indicates whether or not the respective addresses can be reached via the routing device.

14. The routing device of claim 13, further comprising a transmitter configured to send, in response to the identifying of the one or more addresses, one or more queries with respect to the one or more addresses, to determine whether or not the one or more addresses can be reached via a routing device.

15. The routing device of claim 11, wherein the calculation engine is configured such that the operations for determining the candidate advertisement value further comprises:

identifying a candidate aggregate value representing a larger range of network addresses than the network address range corresponding to the advertisement value, the larger range of network addresses including the destination address;

calculating a candidate coverage value that indicates a respective portion of addresses within the larger range of network addresses that can be reached through the routing device; and

determining that the candidate coverage value is smaller than the predefined threshold coverage value.

16. The routing device of claim 11, wherein the advertisement value is a network address prefix, the calculation engine being configured such that the operations for determining the advertisement value comprises identifying a shortest network address prefix of which the corresponding coverage value meets or exceeds the predefined threshold coverage value.

17. The routing device of claim 16, wherein the calculation engine is configured such that the operations for determining the advertisement value recursively determining whether or not progressively shorter network address prefixes corresponding to progressively larger network address ranges have respective coverage values that meet or exceed the predefined threshold coverage value.

18. The routing device of claim 11, wherein the predefined threshold coverage value is a threshold proportion of addresses within the network address range that are reachable via the routing device.

19. A non-transitory computer readable storage medium including instructions for causing a routing device, when the instructions are executed by the routing device, to perform operations comprising:

in a computer network, receive a network address query with respect to a destination address;

determine an advertisement value representing a network address range that includes the destination address, the determining of the advertisement value comprising;

calculating a coverage value that indicates a portion of addresses within the network address range that can be reached through the routing device, and

determining that the calculated coverage value meets or exceeds a predefined threshold coverage value; and

reply to the network address query by advertising the advertisement value.