Determining a route advertisement in a reactive routing environment

• US 8,705,539 B2
• Filed: 01/06/2012
• Issued: 04/22/2014
• 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:
  US13/345,003
• Publication Number:
  US 20120106395A1
• Time in Patent Office: 837 Days
• Field of Search: 370/395.54, 370/390, 370/401, 370/389, 709/238, 709/220, 709/247
• US Class Current: 370/395.54
• 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 reactive routing environment, receiving a network address query with respect to a destination address;

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

identifying from a local routing table of the routing device one or more addresses which are within the range of network addresses and for which the routing device does not have reachability information that indicates reachability of the respective addresses via the routing device, and

sending one or more queries from the routing device with respect to the one or more addresses, to determine reachability of the one or more addresses via the routing device; and

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

2. The method of claim 1, wherein the determining of the aggregate value further comprises receiving one or more responses to the one or more queries.

3. The method of claim 1, wherein the determining of the aggregate value further comprises determining that a percentage of addresses within the range of network addresses that can be reached via the routing device satisfies a predefined minimal coverage value.

4. The method of claim 3, wherein the determining of the aggregate value further comprises:

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

determining that a percentage of addresses within the larger range of network addresses that can be reached via the routing device does not satisfy the predefined minimal coverage value.

5. The method of claim 4, wherein the determining of the aggregate value further comprises identifying a plurality of addresses which are within the larger range of network addresses and for which the routing device does not have reachability information, and sending one or more further queries from the routing device with respect to the plurality of addresses.

6. The method of claim 4, wherein the aggregate values are respective network address prefixes, the method comprising recursively determining whether or not progressively shorter prefixes corresponding to progressively larger network address ranges satisfy the minimal coverage value.

7. The method of claim 6, further comprising identifying a shortest prefix that satisfies the minimal coverage value as the aggregate value to be advertised in reply to the network address query.

8. The method of claim 3, wherein the minimal coverage value is 100%.

9. The method of claim 3, wherein the minimal coverage value is less than 100%.

17. The routing device of claim 3, wherein the minimal coverage value is 100%.

10. A routing device comprising:

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

a calculation engine to determine an aggregate value representing a range of network addresses that includes the destination address, the calculation engine being configured to determine the aggregate value by an operation comprising identifying from a local routing table of the routing device one or more addresses which are within the range of network addresses and for which the routing device does not have reachability information that indicates reachability of the respective addresses via the routing device,

a transmitter to send one or more queries with respect to the one or more addresses, to determine reachability of the one or more addresses via the routing device; and

an advertising engine to reply to the network address where he by advertising the aggregate value.

11. The routing device of claim 10, further comprising a second receiver to receive one or more responses to the one or more queries.

12. The routing device of claim 10, wherein the calculation engine is further configured to determine that a percentage of addresses within the range of network addresses that can be reached via the routing device satisfies a predefined minimal coverage value.

13. The routing device of claim 12, wherein the calculation engine is further configured to:

identify a broader aggregate value representing a larger range of network addresses than the range of network addresses corresponding to the aggregate value, the larger range of network addresses including the destination address; and

determine that a percentage of addresses within the larger range of network addresses that can be reached via the routing device does not satisfy the predefined minimal coverage value.

14. The routing device of claim 13, wherein the calculation engine is further configured to identify a plurality of addresses which are within the larger range of network addresses and for which the routing device does not have reachability information, the transmitter being configured to send one or more further queries from the routing device with respect to the plurality of addresses.

15. The routing device of claim 13, wherein the aggregate values are respective network address prefixes, the calculation engine being configured recursively to determine whether or not progressively shorter prefixes corresponding to progressively larger network address ranges satisfy the minimal coverage value.

16. The routing device of claim 15, wherein the calculation engine is further configured to identify a shortest prefix that satisfies the minimal coverage value as the aggregate value to be advertised in reply to the network address query.

18. An apparatus comprising:

means for receiving, at the apparatus in a reactive routing environment, a network address query with respect to a destination address;

means for determining an aggregate value representing a range of network addresses that includes the destination address, the determining of the aggregate value comprising

identifying from a local routing table of the routing device one or more addresses which are within the range of network addresses and for which the routing device does not have reachability information that indicates reachability of the respective addresses via the routing device, and

sending one or more queries from the routing device with respect to the one or more addresses, to determine reachability of the one or more addresses via the routing device; and

means for replying to the network address query by advertising the aggregate value.

19. Logic encoded in one or more tangible media for execution and when executed operable to:

at a routing device in a reactive routing environment, receive a network address query with respect to a destination address;

at the routing device, determine an aggregate value representing a range of network addresses that includes the destination address, the determining of the aggregate value comprising

identifying from a local routing table of the routing device one or more addresses which are within the range of network addresses and for which the routing device does not have reachability information that indicates reachability of the respective addresses via the routing device, and

sending one or more queries from the routing device with respect to the one or more addresses, to determine reachability of the one or more addresses via the routing device; and

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