Apparatus, systems and methods for aggregate routes within a communications network

• US 8,615,015 B1
• Filed: 12/30/2010
• Issued: 12/24/2013
• Est. Priority Date: 12/30/2010
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Shekhar, Ravi
• Primary Examiner(s): Lai, Andrew
• Assistant Examiner(s): LEE, ANDREW CHUNG CHEUNG
• Application Number:
  US12/981,678
• Time in Patent Office: 1,090 Days
• Field of Search: 370/256, 370/389, 370/392, 370/395.31, 370/400, 370/401, 370/408
• US Class Current: 370/400
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 45/745 Address table lookup; Address filtering
• CPC Class Codes: H04L 49/00 Packet switching elements

Abstract

An apparatus includes a memory configured to store multiple route descriptors as a tree, a communications interface configured to be in communication with an access switch, and a processor operatively coupled to the memory and the communications interface. Each route descriptor is a node within the tree, and includes a next hop destination associated with a next hop destination of a route associated with that route descriptor and a next hop indicator associated with a quantity of routes represented by that route descriptor. A first route descriptor has a first child route descriptor and a second child route descriptor. The processor is configured to define, at a first time, a value of the next hop destination of the first route descriptor and to send, at a second time after the first time, the value of the next hop destination of the first route descriptor to the access switch.

Claims

1. An apparatus, comprising:

a memory, the memory configured to store a plurality of route descriptors as a tree, each route descriptor from the plurality of route descriptors including a next hop destination associated with a route associated with that route descriptor, each route descriptor including a next hop indicator having a value associated with a quantity of routes represented by that route descriptor, each route descriptor from the plurality of route descriptors being a node from a plurality of nodes of the tree;

a communications interface configured to be in communication with an access switch; and

a processor operatively coupled to the memory and the communications interface, the processor configured to access a first route descriptor from the plurality of route descriptors, the first route descriptor having a first child route descriptor from the plurality of route descriptors, the first route descriptor having a second child route descriptor from the plurality of route descriptors,

the processor configured to define, at a first time, a value of the next hop destination of the first route descriptor based on a value of the next hop destination of the first child route descriptor and a value of the next hop destination of the second child route descriptor,

the processor configured to send, at a second time after the first time, the value of the next hop destination of the first route descriptor to the access switch via the communications interface in response to a next hop identifier request from the access switch.

2. The method of claim 1, wherein the tree includes leaf nodes and internal nodes, the leaf nodes being associated with host routes, the internal nodes being associated with prefix routes.

3. The apparatus of claim 1, wherein the next hop identifier request is triggered by an Address Resolution Protocol request.

4. The apparatus of claim 1, wherein:

the first route descriptor has a parent route descriptor from the plurality of route descriptors;

the first route descriptor has a sibling route descriptor from the plurality of route descriptors; and

the processor is configured to define, at a third time after the first time and before the second time, the value of the next hop destination of the parent route descriptor based on the value of the next hop destination of the first route descriptor and the value of the next hop destination of the sibling route descriptor.

5. The apparatus of claim 1, wherein:

the next hop indicator of the first child route descriptor is from a plurality of next hop indicators of the first child route descriptor, each next hop indicator from the plurality of next hop indicators of the first child route descriptor is uniquely associated with a next hop destination; and

the value of the next hop indicator of the first child route descriptor being greater than a value of each remaining next hop indicator from the plurality of next hop indicators of the first child route descriptor.

6. The apparatus of claim 1, wherein:

the first child route descriptor is associated with a first host route;

the second child route descriptor is associated with a second host route; and

the first route descriptor is associated with a route prefix of the first host route and the second host route.

7. The apparatus of claim 1, wherein:

the first child route descriptor is associated with a first host route;

the first child route descriptor includes a plurality of next hop indicators of the first child route descriptor, each next hop indicator from the plurality of next hop indicators of the first child route descriptor is uniquely associated with a next hop destination and having a negative value;

the value of the next hop indicator of the first child route descriptor is greater than the negative value of each remaining next hop indicator from the plurality of next hop indicators of the first child route descriptor.

8. The apparatus of claim 1, wherein:

the first child route descriptor is associated with a first route prefix;

the second child route descriptor is associated with a second route prefix; and

the first route descriptor is associated with a third route prefix, the third route prefix being a route prefix of the first route prefix and the second route prefix.

9. The apparatus of claim 1, wherein:

the first child route descriptor is associated with an active host route;

the second child route descriptor is associated with an inactive host route, the value of the next hop destination of the first child route descriptor is associated with a destination, the value of the next hop destination of the second child route descriptor is associated with the destination.

10. The apparatus of claim 1, wherein the first route descriptor represents the quantity of routes represented by the first route descriptor using a single route prefix such that the access switch is configured to store a reduced number of routes.

11. A method, comprising:

storing a plurality of route descriptors at a memory, each route descriptor from the plurality of route descriptors including a next hop destination associated with a route associated with that route descriptor, each route descriptor including a next hop indicator having a value associated with a quantity of routes represented by that route descriptor, each route descriptor from the plurality of route descriptors being a node from a plurality of nodes of a tree;

accessing a first route descriptor from the plurality of route descriptors, the first route descriptor having a first child route descriptor from the plurality of route descriptors, the first route descriptor having a second child route descriptor from the plurality of route descriptors, the first route descriptor having a parent route descriptor from the plurality of route descriptors;

defining a value of the next hop destination of the first route descriptor based on at least one of a value of the next hop destination of the first child route descriptor and a value of the next hop destination of the second child route descriptor; and

defining the value of the next hop destination of the parent route descriptor based on at least the value of the next hop destination of the first route descriptor.

12. The method of claim 11, further comprising sending the value of the next hop destination of the parent route descriptor to an access switch.

13. The method of claim 11, wherein:

the first route descriptor has a sibling route descriptor from the plurality of route descriptors; and

the value of the next hop destination of the parent route descriptor is defined based on the value of the next hop destination of the first route descriptor and the value of the next hop destination of the sibling route descriptor.

14. The method of claim 11, wherein:

the value of the next hop destination of the first child route descriptor is the same as the value of the next hop destination of the second child route descriptor; and

the value of the next hop indicator of the first route descriptor is one more than a sum of value of the next hop indicator of the first child route descriptor and the value of the next hop indicator of the second child route descriptor.

15. The method of claim 11, wherein:

the value of the next hop destination of the first child route descriptor is different from the value of the next hop destination of the second child route descriptor; and

the value of the next hop indicator of the first route descriptor is a sum of the value of the next hop indicator of the first child route descriptor and the value of the next hop indicator of the second child route descriptor.

16. A system, comprising:

a first access switch including a first communications interface, a second communications interface and a processor, the first communications interface of the first access switch configured to be coupled to a first computing device, the first computing device associated with a first network address;

a second access switch including a first communications interface, a second communications interface and a processor, the first communications interface of the second access switch configured to be coupled to a second computing device, the second computing device associated with a second network address;

a third access switch including a communications interface and a processor; and

a switch fabric operatively coupled to the second communications interface of the first access switch, the communications interface of the third access switch and the second communications interface of the second access switch, the processor of the first access switch configured to receive a data packet including the second network address from the first computing device via the first communications interface of the first access switch,

the processor of the first access switch configured to select a first next hop destination associated with an address prefix of the second network address from a plurality of next hop destinations based on the second network address,

the processor of the first access switch configured to send the data packet to the third access switch via the switch fabric based on the first next hop destination without requesting a second next hop destination associated with the second network address,

the processor of the third access switch configured to request the second next hop destination associated with the second network address if the processor of the third access switch determines that the second computing device is not directly coupled to the third access switch, the second next hop destination different from the first next hop destination,

the processor of the third access switch configured to send the data packet to the second access switch based on the second next hop destination.

17. The system of claim 16, wherein the second network address is included in an aggregate route of the first next hop destination.

18. The system of claim 16, wherein the second network address includes the address prefix.

19. The system of claim 16, wherein the processor of the third access switch is configured to request the second next hop destination using an Address Resolution Protocol.

20. The system of claim 16, wherein the first next hop destination is associated with the second access switch and the third access switch such that the first access switch is configured to store a reduced number of next hop destinations.