Route prefix aggregation using reachable and non-reachable addresses in a computer network

• US 9,008,092 B2
• Filed: 10/07/2011
• Issued: 04/14/2015
• Est. Priority Date: 10/07/2011
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Thubert, Pascal, Wetterwald, Patrick, Vasseur, Jean-Philippe
• Primary Examiner(s): Yao, Kwang B
• Assistant Examiner(s): CHOWDHURY, HARUN UR R
• Application Number:
  US13/269,203
• Publication Number:
  US 20130088999A1
• Time in Patent Office: 1,285 Days
• Field of Search: 370/252, 370/254, 370/389, 370/392, 370/393, 370/401, 370/466, 370255-258, 370/351, 709/221, 709/238
• US Class Current: 370/392
• CPC Class Codes: H04L 2101/695 using masks or ranges of addresses
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/245 Link aggregation, e.g. trunking
• CPC Class Codes: H04L 45/74 Address processing for routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 40/248 Connectivity information update

Abstract

In one embodiment, a network device determines a set of routes to one or more reachable addresses and also a set of no-routes to one or more non-reachable addresses in a computer network. The routes and no-routes may then be aggregated into one or more reachable route prefixes with one or more corresponding non-reachable no-route prefix exceptions. As such, the aggregated combination of route prefixes and no-route prefix exceptions may be utilized by the network device.

Claims

1. A method, comprising:

determining, at a network device, a set of routes to one or more reachable addresses in a computer network;

determining a set of no-routes to one or more non-reachable addresses in the computer network;

recursively aggregating the routes and no-routes into one or more reachable route prefixes within which there are one or more corresponding non-reachable no-route prefix exceptions to exceptions, wherein aggregating includes;

creating a bitmap with bits corresponding to each address within a given range, wherein based on the routes and no-routes, the bits of the bitmap are populated with a first bit value for addresses corresponding to a route, and with a second bit value for addresses corresponding to a no-route, and

recursively merging each even prefix with its adjacently corresponding odd prefix for each decremented prefix length in a range of available prefix lengths; and

utilizing the route prefixes and no-route prefix exceptions.

2. The method as in claim 1, wherein utilizing comprises:

advertising the route prefixes and no-route prefix exceptions into the computer network.

3. The method as in claim 2, wherein the network device is a node within a directed acyclic graph (DAG), and wherein advertising comprises:

notifying a DAG parent node of the route prefixes and no-route prefix exceptions.

4. The method as in claim 1, wherein utilizing comprises:

storing the route prefixes and no-route prefix exceptions in one or more routing tables at the network device.

5. The method as in claim 4, wherein the network device is a node within a directed acyclic graph (DAG), and wherein storing comprises:

storing one or more routing tables for each DAG child of the network device.

6. The method as in claim 4, wherein storing comprises:

storing a first table for routes and a second table for no-routes, wherein reachability is determined based on a longest match lookup between the first and second tables.

7. The method as in claim 1, wherein determining no-routes comprises:

identifying addresses within a given address range that are not the reachable addresses.

8. The method as in claim 1, wherein determining routes and no-routes comprises:

receiving an advertisement from one or more neighbors with associated aggregated route prefixes and no-route prefix exceptions.

9. The method as in claim 1, wherein aggregation is performed in response to expiration of a configurable timer.

10. The method as in claim 1, wherein the one or more reachable route prefixes are a plurality of reachable route prefixes in response to corresponding routes being separated by at least a threshold range of no-routes.

11. The method as in claim 1, wherein at least one of the non-reachable no-route prefix exceptions has within it one or more reachable route prefix exceptions to the associated no-route prefix exception.

12. The method as in claim 1, wherein:

i) when the even prefix and odd prefix are different bit values selected from the first and second bit values, a corresponding bit value at a next recursively decremented prefix length is equal to a third bit value;

ii) when both the even prefix and odd prefix are a same bit value, a corresponding bit value at a next recursively decremented prefix length is equal to that same bit value;

iii) when the even prefix and odd prefix are different bit values selected from the first and third bit values, any bits that were the second value in a previous prefix length recursion become no-route prefixes at that previous prefix length; and

iv) when the even prefix and odd prefix are different bit values selected from the second and third bit values, any bits that were the first value in the previous prefix length recursion become route prefixes at that previous prefix length.

13. An apparatus, comprising:

one or more network interfaces to communicate in a computer network;

a processor coupled to the network interfaces and adapted to execute one or more processes; and

a memory configured to store a process executable by the processor, the process when executed operable to;

determine a set of routes to one or more reachable addresses in the computer network;

determine a set of no-routes to one or more non-reachable addresses in the computer network;

recursively aggregate the routes and no-routes into one or more reachable route prefixes within which there are one or more corresponding non-reachable no-route prefix exceptions to exceptions, wherein the process when executed to aggregate is further operable to;

create a bitmap with bits corresponding to each address within a given range, wherein based on the routes and no-routes, the bits of the bitmap are populated with a first bit value for addresses corresponding to a route, and with a second bit value for addresses corresponding to a no-route, and

recursively merge each even prefix with its adjacently corresponding odd prefix for each decremented prefix length in a range of available prefix lengths; and

utilize the route prefixes and no-route prefix exceptions.

14. The apparatus as in claim 13, wherein the process when executed to utilize the route prefixes and no-route prefix exceptions is further operable to:

advertise the route prefixes and no-route prefix exceptions into the computer network.

15. The apparatus as in claim 13, wherein the process when executed to utilize the route prefixes and no-route prefix exceptions is further operable to:

store the route prefixes and no-route prefix exceptions in one or more routing tables.

16. The apparatus as in claim 15, wherein the process when executed is further operable to:

store a first table for routes and a second table for no-routes; and

determine reachability based on a longest match lookup between the first and second tables.

17. The apparatus as in claim 13, wherein the process when executed to determine routes and no-routes is further operable to:

receive an advertisement from one or more neighbors with associated aggregated route prefixes and no-route prefix exceptions.

18. The apparatus as in claim 13, wherein:

i) when the even prefix and odd prefix are different bit values selected from the first and second bit values, a corresponding bit value at a next recursively decremented prefix length is equal to a third bit value;

ii) when both the even prefix and odd prefix are a same bit value, a corresponding bit value at a next recursively decremented prefix length is equal to that same bit value;

iii) when the even prefix and odd prefix are different bit values selected from the first and third bit values, any bits that were the second value in a previous prefix length recursion become no-route prefixes at that previous prefix length; and

iv) when the even prefix and odd prefix are different bit values selected from the second and third bit values, any bits that were the first value in the previous prefix length recursion become route prefixes at that previous prefix length.

19. A tangible, non-transitory, computer-readable media having software encoded thereon, the software when executed by a processor operable to:

determine a set of routes to one or more reachable addresses in the computer network;

determine a set of no-routes to one or more non-reachable addresses in the computer network;

recursively aggregate the routes and no-routes into one or more reachable route prefixes within which that are one or more corresponding non-reachable no-route prefix exceptions to exceptions, wherein the software when executed to aggregate is further operable to;

;

create a bitmap with bits corresponding to each address within a given range, wherein based on the routes and no-routes, the bits of the bitmap are populated with a first bit value for addresses corresponding to a route, and with a second bit value for addresses corresponding to a no-route, and

recursively merge each even prefix with its adjacently corresponding odd prefix for each decremented prefix length in a range of available prefix lengths; and

utilize the route prefixes and no-route prefix exceptions.

20. The computer-readable media as in claim 19, wherein the software when executed to utilize the route prefixes and no-route prefix exceptions is further operable to perform at least one of either advertisement of the route prefixes and no-route prefix exceptions into the computer network or storage of the route prefixes and no-route prefix exceptions in one or more routing tables.

21. The computer-readable media as in claim 19, wherein:

i) when the even prefix and odd prefix are different bit values selected from the first and second bit values, a corresponding bit value at a next recursively decremented prefix length is equal to a third bit value;

ii) when both the even prefix and odd prefix are a same bit value, a corresponding bit value at a next recursively decremented prefix length is equal to that same bit value;

iii) when the even prefix and odd prefix are different bit values selected from the first and third bit values, any bits that were the second value in a previous prefix length recursion become no-route prefixes at that previous prefix length; and

iv) when the even prefix and odd prefix are different bit values selected from the second and third bit values, any bits that were the first value in the previous prefix length recursion become route prefixes at that previous prefix length.