DISTRIBUTED ROUTING ARCHITECTURE

• US 20130010788A1
• Filed: 09/14/2012
• Published: 01/10/2013
• Est. Priority Date: 12/17/2009
• Status: Active Grant

• Current Assignee: Alan M. Judge, David J. Mcgaugh, David J O'Meara, James R. Hamilton, Justin O. Pietsch
• Original Assignee: Alan M. Judge, David J. Mcgaugh, David J O'Meara, James R. Hamilton, Justin O. Pietsch
• Inventors: Hamilton, James R., Judge, Alan M., McGaugh, David J., Pietsch, Justin O., O'Meara, David J.
• Granted Patent: US 8,902,897 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/58 Association of routers
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering

Abstract

A hierarchical distributed routing architecture including at least two levels, or layers, for receiving, processing and forwarding data packets between network components is provided. The core level router components receive an incoming packet from a network component and identify a distribution level router component based on processing a subset of the destination address associated with the received packet. The distribution level router components receive a forwarded packet and forward the packet to a respective network. The mapping, or other assignment, of portions of the FIB associated with the distributed routing environment is managed by a router management component.

Claims

1. A system for routing packets, the system comprising:

a first level of a hierarchy of routing components comprising one or more first level routing components, wherein each of the one or more first level routing components is configured to;

receive a first packet for routing, wherein the first packet comprises at least a destination address, and wherein the destination address comprises a first subset of the destination address and a second subset of the destination address;

identify at least one second level routing component based at least in part on the first subset of the destination address; and

transmit the first packet to the identified at least one second level routing component; and

a second level of the hierarchy of routing components comprising one or more second level routing components, wherein each of the one or more second level routing components is configured to;

receive a second packet from a first level routing component;

identify an outgoing transit path based at least in part on the second subset of the destination address; and

transmit the second packet to the identified outgoing transit path.

2. The system of claim 1, wherein the destination address corresponds to an IP address.

3. The system of claim 2, wherein the first subset of the destination address corresponds to the eight most significant bits of the IP address.

4. The system of claim 1, wherein at least two routing components corresponding to at least one of the first level or the second level of the hierarchy of routing components are implemented in a physical router device.

5. The system of claim 1, wherein each routing component corresponding to at least one of the first level or the second level of the hierarchy of routing components is allocated a portion of destination addresses of packets based at least in part on traffic volume associated with one or more destination addresses of the packets.

6. The system of claim 1 further comprising a router management device configured to assign one or more router components of at least one of the first level or the second level of the hierarchy of routing components to a portion of packets based at least in part on one or more destination addresses of the packets.

7. The system of claim 1, wherein the first packet and the second packet are the same packet.

8. A computer-implemented method for routing packets, the method comprising:

receiving, at a router component of a first level of a routing component hierarchy, a packet comprising a first subset of a destination address and a second subset of the destination address;

identifying a second level routing component of a second level of the routing component hierarchy based at least in part on the first subset of the destination address;

causing the packet to be routed to the second level routing component;

identifying, at the second level router component, an outgoing transit path based at least in part on the second subset of the destination address; and

causing the packet to be routed to the outgoing transit path.

9. The computer-implemented method of claim 8, wherein the destination address corresponds to an IP address.

10. The computer-implemented method of claim 9, wherein the second subset of the destination address corresponds to at least one of the sixteen or twenty four most significant bits of the IP address.

11. The computer-implemented method of claim 8, wherein each routing component corresponding to at least one of the first level of the routing component hierarchy or the second level of the routing component hierarchy is allocated a portion of destination addresses of packets based at least in part on traffic volume associated with one or more destination addresses of the packets.

12. The computer-implemented method of claim 8, wherein each routing component corresponding to at least one of the first level of the routing component hierarchy or the second level of the routing component hierarchy is allocated approximately equal portions of packets based at least in part on a first subset of destination addresses of the packets.

13. The computer-implemented method of claim 8, wherein each routing component corresponding to at least one of the first level of the routing component hierarchy or the second level of the routing component hierarchy is allocated portions of packets based on at least one of random selection, round robin selection, hashing or load balancing.

14. The computer-implemented method of claim 8, wherein identifying a second level routing component of a second level of the routing component hierarchy comprises;

attempting to identify the second level routing component from address information persisted in a first memory, and

if the address information is not available in the first memory component, attempting to identify the second level routing component from address information persisted in a second memory;

wherein the first memory is associated with a faster access time than the second memory.

15. A system for routing packets, the system comprising:

a first level of a routing component hierarchy comprising one or more first level routing components, wherein the first level of the routing component hierarchy is configured to;

in response to reception of a packet comprising a destination address, identify a second level routing component based at least in part on a first subset of the destination address; and

transmit the packet to the identified second level routing component;

a second level of the routing component hierarchy comprising one or more second level routing components, wherein the second level of the routing component hierarchy is configured to;

in response to reception of the packet from the first level of the routing component hierarchy, identify an external routing path based at least in part on a second subset of the destination address; and

transmit the packet to the identified external routing path.

16. The system of claim 15, wherein the destination address corresponds to an IP address.

17. The system of claim 16, wherein the first subset of the destination address corresponds to at least one of the eight, the sixteen, or the twenty four most significant bits of the IP address.

18. The system of claim 15, wherein each of the second level routing components comprises a first memory and a second memory for storing destination address information, and wherein the first memory is associated with a faster access time than the second memory.

19. The system of claim 18, wherein each of the second level routing components are further configured to:

attempt to identify the third level routing component from address information persisted in the first memory, and

if the address information is not available in the first memory, attempt to identify the third level routing component from address information persisted in the second memory component.

20. The system of claim 15, wherein each routing component corresponding to at least one of the first level or the second level is allocated approximately equal portions of packets based at least in part on the destination addresses of the packets.

21. The system of claim 15, wherein each routing component corresponding to at least one of the first level or the second level is allocated portions of packets based on at least one of random selection, round robin selection, hashing or load balancing.

22. The system of claim 15, wherein each routing component corresponding to at least one of the first level or the second level is allocated a portion of destination addresses of packets based at least in part on traffic volume associated with one or more destination addresses of the packets.

23. The system of claim 15 further comprising a router management device configured to assign router components of at least one of the first level or the second level to a portion of packets based at least in part on a destination address of each packet.