US8971328B2 - Distributed routing architecture - Google Patents

Abstract

A hierarchical distributed routing architecture including at least three 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 that receiving a forwarded packet and identify a transit level router component based a second processing of at least a subset of the destination address associated with the received packet. The transit level router components receive the 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.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

This application is a continuation of U.S. patent application Ser. No. 12/641,260, entitled “DISTRIBUTED ROUTING ARCHITECTURE” and filed Dec. 17, 2009, now U.S. Pat. No. 8,331,371, the entirety of which is incorporated herein by reference.

BACKGROUND

Generally described, computing devices utilize a communication network, or a series of communication networks, to exchange data. In a common embodiment, data to be exchanged is divided into a series of packets that can be transmitted between a sending computing device and a recipient computing device. In general, each packet can be considered to include two primary components, namely, control information and payload data. The control information corresponds to information utilized by one or more communication networks to deliver the payload data. For example, control information can include source and destination network addresses, error detection codes, and packet sequencing identification, and the like. Typically, control information is found in packet headers and trailers included within the packet and adjacent to the payload data.

In practice, in a packet-switched communication network, packets are transmitted between multiple physical networks, or sub-networks. Generally, the physical networks include a number of hardware devices that receive packets from a source network component and forward the packet to a recipient network component. The packet routing hardware devices are typically referred to as routers. Generally described, routers can operate with two primary functions or planes. The first function corresponds to a control plane, in which the router learns the set of outgoing interfaces that are most appropriate for forwarding received packets to specific destinations. The second function is a forwarding plane, in which the router sends the received packet to an outbound interface.

To execute the control plane functionality, routers can maintain a forwarding information base (“FIB”) that identifies, among other packet attribute information, destination information for at least a subset of possible network addresses, such as Internet Protocol (“IP”) addresses. In a typical embodiment, the FIB corresponds to a table of values specifying network forwarding information for the router. In one aspect, commercial level routing hardware components can include customized chipsets, memory components, and software that allows a single router to support millions of entries in the FIB. However, such commercial level routing hardware components are typically very expensive and often require extensive customization. In another aspect, commodity-based routing hardware components are made of more generic components and can be less expensive than commercial level routing hardware components by a significant order of magnitude. However, such commodity-based routing hardware components typically only support FIBs on the order of thousands of entries.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing aspects and many of the attendant advantages of this invention will become more readily appreciated as the same become better understood by reference to the following detailed description, when taken in conjunction with the accompanying drawings, wherein:

FIG. 1A is a block diagram illustrative of one embodiment of a distributed routing environment including a router management component and a hierarchical, distributed routing component architecture;

FIG. 1B is a block diagram illustrative of components of a router component utilized in accordance with the distributed routing environment ofFIG. 1A;

FIGS. 2A-2C are block diagrams illustrative of the distributed routing environment ofFIG. 1A illustrating the routing of a received packet within the hierarchical distributed routing component architecture;

FIG. 3 is a flow diagram illustrative of a distributed router architecture routing routine implemented within a distributed routing environment; and

FIG. 4 is a flow diagram illustrative of a distributed router architecture routing routine implemented within a distributed routing environment

DETAILED DESCRIPTION

Generally described, the present disclosure corresponds to a distributed routing architecture. Specifically, the present disclosure corresponds to a hierarchical distributed routing architecture including at least three logical levels, or layers, for receiving, processing and forwarding data packets between network components. In one embodiment, the three logical levels can corresponds to a core level, a distribution level and a transit level. Illustratively, the core level corresponds to one or more router components that receive an incoming packet from a network component and processes the destination address information associated with the received packet. The core level router component then identifies a distribution level router component based on a subset of the destination address associated with the received packet. The distribution level corresponds to one or more router components that receive a forwarded packet from a core level router component and further processes the destination address information associated with the received packet. The distribution level router component identifies a transit level router component based on at least a subset of the destination address associated with the received packet. Each distribution level router component is associated with, or otherwise corresponds to, a subset of the FIB associated with the distributed routing architecture. Finally, the transit level router components correspond to one or more router components that receive the forwarded packet from a distribution level router component and forward the packet “upstream” to a respective network, or network node. The mapping, or other assignment, of portions of the FIB associated with the distributed routing environment is managed by a router management component.

In one embodiment, each of the router components associated with the core level, distribution level and transit level can correspond more closely to commodity based router components/hardware. In another embodiment, the core level, distribution level and transit level router components correspond to logical router components that do no necessarily have a corresponding hardware router component. For example, one or more logical router components within each level may be implemented in the same hardware router component. Likewise, the logical router components associated with different levels of the distributed routing architecture may be implemented in the same hardware router component. In both embodiments, however, because responsibility for maintaining the FIB associated with the distributed routing environment is divided among several router components, the processing and memory restraints associated with commodity based router components/hardware can be mitigated. Various implementations, combination, and applications for dividing the FIB associated with the distributed routing environment will be described in accordance with the distributed routing environment. However, one skilled in the relevant art will appreciate that such embodiment and examples are illustrative in nature and should not be construed as limiting.

Turning now toFIG. 1A, adistributed routing environment100 for implemented a hierarchical distributed routing architecture will be described. Thedistributed routing environment100 includes arouter management component102 for controlling the routing information utilized by thedistributed routing environment100. Specifically, the router managedcomponent102 can receive all upstream routing information to be used by thedistributed routing environment100 and allocate the assignment of the upstream routing information among the components of thedistributed routing environment100 as will be described. In one embodiment, therouter management component102 can correspond to a computing device in communication with one or more components of thedistributed routing environment100. Illustrative computing devices can include server computing devices, personal computing devices or other computing devices that include a processor, memory and other components for executing instructions associated with the function of therouter management component102. In another embodiment, therouter management component102 may be implemented as a software component that is executed on one or more of the router components described below. Illustratively, therouter management component102 maintains and updates the FIB associated with thedistributed routing environment100. Additionally, therouter management component102 can allocate responsibility for portions of the FIB entries to the various layers of thedistributed routing environment100, as will be described below. In one embodiment, therouter management component102 can partition the FIB according to the distribution to the various router components of thedistributed routing environment100 and distribute respective portions of the FIB to be maintained in a memory associated with the various router components.

With continued reference toFIG. 1A, thedistributed routing environment100 includes afirst communication network104 that transmits data packets to thedistributed routing environment100. Thefirst communication network104 may encompass any suitable combination of networking hardware and protocols necessary to establish packet-based communications to the distributedrouting environment100. For example, thecommunication network104 may include private networks such as local area networks (LANs) or wide area networks (WANs) as well as public or private wireless networks. In such an embodiment, thecommunication network104 may include the hardware (e.g., modems, routers, switches, load balancers, proxy servers, etc.) and software (e.g., protocol stacks, accounting software, firewall/security software, etc.) necessary to establish a networking link with the distributedrouting environment100. Additionally, thecommunication network104 may implement one of various communication protocols for transmitting data between computing devices. As will be explained in greater detail below, the communication protocols can include protocols that define packet flow information, such as network address information corresponding to the Internet Protocol version 4 (IPv4) and the Internet Protocol version 6 (IPv6) Internet Layer communication network protocols. One skilled in the relevant art will appreciate, however, that present disclosure may be applicable with additional or alternative protocols and that the illustrated examples should not be construed as limiting.

In communication with thefirst communication network104 is a first level of the distributedrouting environment100, generally referred to as the core layer or core level. In one embodiment, the core level corresponds to one or more logical router components, generally referred to ascore level routers106A,106B, and106C. As previously described, within the distributedrouting environment100, thecore level routers106A,106B,106C receive an incoming packet from a component from thenetwork104 and process the destination address by identifying a distribution level router component based on a subset of the destination address associated with the received packet. Illustratively, the subset of the destination address can correspond to less than the entire destination IP address, such as the highest most values of the IP address. As previously described, thecore level routers106A,106B,106C can correspond to logical router components implemented on one or more hardware components. In one embodiment, each logical router component can correspond with a dedicated physical router component. In another embodiment, each logical router component can correspond to a physical router component shared by at least one other logical router component in the distributedrouter environment100. In an alternative embodiment, at least some portion of the core layer may be implemented by components outside the distributedrouting environment100. In such an embodiment, such external components would directly address a distribution level router component (described below) of the distributedrouting environment100.

The distributedrouting environment100 can further include a second level of logical router components, generally referred to as the distribution layer or distribution level. In one embodiment, the distribution level corresponds to one or more router components, generally referred to asdistribution level routers108A,108B, and108C. As previously described, within the distributedrouting environment100 thedistribution level routers108A,108B and108C receiving an incoming packet from acore routing component102 and process the destination address by identifying a transit level router component based on at least a subset of the destination address associated with the received packet. Illustratively, the subset of the destination address can correspond to a larger subset of the destination IP address used by thecore level routers106A,106B,106C. In this embodiment, the routing preformed by the distribution level can correspond to a more refined routing of the received packet relative to the core level routing. As described above with thecore level routers106A,106B,106C, thedistribution level routers108A,108B, and108C can correspond to logical router components implemented on one or more hardware components. In one embodiment, each logical router component can correspond with a dedicated physical router component. In another embodiment, each logical router component can correspond to a physical router component shared by at least one other logical router component in the distributedrouter environment100.

In communication with the distribution level router components is a third level of router components, generally referred to as the transmit layer or transit level. In one embodiment, the transit level corresponds to one or more router components, generally referred to astransit level routers110A,110B, and110C. As previously described, thetransit level routers110A,110B,110C receive the forwarded packet from a distributionlevel router component108A,108B,108C and forward the packet “upstream” to anothercommunication network112 node. Illustratively, eachtransit level router110A,110B,110C can be configured to communicate with one or more upstream peers such that all packets destined for an associated peer network component will be transmitted through the assignedtransit level router110A,110B,110C (or a redundant router). As described above with thecore level routers106A,106B,106C and thedistribution level routers108A,108B and108C, thetransit level routers110A,110B, and110C can correspond to logical router components implemented on one or more hardware components. In one embodiment, each logical router component can correspond with a dedicated physical router component. In another embodiment, each logical router component can correspond to a physical router component shared by at least one other logical router component in the distributedrouter environment100

Similar tocommunication network102,communication network112 may encompass any suitable combination of networking hardware and protocols necessary to establish packet-based communications to the distributedrouting environment100. For example, thecommunication network112 may include private networks such as local area networks (LANs) or wide area networks (WANs) as well as public or private wireless networks. In such an embodiment, thecommunication network112 may include the hardware (e.g., modems, routers, switches, load balancers, proxy servers, etc.) and software (e.g., protocol stacks, accounting software, firewall/security software, etc.) necessary to establish a networking link with the distributedrouting environment100. As described above with regard to thecommunication network104, thecommunication network112 may implement one of various communication protocols for transmitting data between computing devices. One skilled in the relevant art will appreciate, however, that present disclosure may be applicable with additional or alternative protocols and that the illustrated examples should not be construed as limiting.

In an illustrative embodiment, the logical router components (106,108,110) inFIG. 1A may correspond to a computing device having processing resources, memory resources, networking interfaces, and other hardware/software for carrying the described functionality for each of the logical router components. With reference now toFIG. 1B, a block diagram illustrative of components of arouter component150 utilized in accordance with the distributedrouting environment100 ofFIG. 1A will be described. The general architecture of therouter component150 depicted inFIG. 1B includes an arrangement of computer hardware and software components that may be used to implement one or morelogical router components106,108,110. Those skilled in the art will appreciate that therouter component150 may include many more (or fewer) components than those shown inFIG. 1B. It is not necessary, however, that all of these generally conventional components be shown in order to provide an enabling disclosure.

As illustrated inFIG. 1B, therouter component150 includes aprocessing unit152, at least onenetwork interface156, and at least one computerreadable medium drive158, all of which may communicate with one another by way of a communication bus. Theprocessing unit152 may thus receive information and instructions from other computing systems or services via a network. Theprocessing unit152 may also be associated with afirst memory component154 for recalling information utilized in the processing of destination address information, such as at least a portion of a FIB associated with the distributedrouting environment100. Thememory154 generally includes RAM, ROM and/or other persistent memory. Theprocessing unit152 may also communicate to and frommemory160. Thenetwork interface156 may provide connectivity to one or more networks or computing systems. The at least one computerreadable medium drive158 can also correspond to RAM, ROM, optical memory, and/or other persistent memory that may persists at least a portion of the FIB associated with the distributedrouting environment100. In an illustrative embodiment, the access time associated with thememory component154 may be faster than the access time associated with the computer readablemedium driver158. Still further, the computerreadable medium drive158 may be implemented in a networked environment in whichmultiple router components150 share access to the information persisted on the computerreadable medium drive158.

Thememory160 contains computer program instructions that theprocessing unit152 executes in order to operate the dynamic classifier. Thememory160 generally includes RAM, ROM and/or other persistent memory. Thememory160 may store anoperating system162 that provides computer program instructions for use by theprocessing unit152 in the general administration and operation of therouter component150. Thememory160 may further include computer program instructions and other information for implementing one or more of the logical router components in the distributedrouting environment100. For example, in one embodiment, thememory160 includes arouter module164 that implements the functionality associated with any of therouters106,108,110. In the event that multiple logical routers are implemented by thesame router component150,memory160 may have each instance of arouter module164.

In an illustrative embodiment, eachrouter component150 may be embodied as an individual hardware component for implementing one or morelogical routers106,108,110. Alternatively,multiple router components150 may be grouped and implemented together. For example, eachrouter component150 may correspond to an application-specific integrated circuit (ASIC) having aprocessing unit152,memory154 and memory160 (or other components with similar functionality). Therouter components150 may share one or more components, such as thenetwork interface156 and computerreadable medium158, via a common communication bus.

With reference now toFIGS. 2A-2C, the processing of receiving packets by the distributedrouting environment100 will be described. With reference first toFIG. 2A, an incoming packet is received from thecommunication network104 to acore level router106. Thecore level router106 that receives the incoming packet may be selected according to a variety of techniques including, but not limited to, load balancing, random selection, round robin, hashing, and other packet distribution techniques. Upon receipt, thecore level router106 processes destination IP address and utilizes a subset of the destination IP address to identify a second level destination router component that will perform a second level of routing. In an illustrative embodiment, thecore level router106 utilizes the most significant bits of the IP address, such as the eight most significant bits of the destination address. The selection of the subset of IP addresses corresponding to a selection of the most significant bits is generally referred to as prefix. For example, selection of the eight most significant bits corresponds to a prefix length of “8.” Selection of the sixteen most significant bits corresponds to a prefix length of “16.” One skilled in the relevant art will appreciate that the number of bits utilized by thecore level router106 may vary. Additionally, in an alternative embodiment, thecore level router106 may use different methodologies to allocate, or otherwise subdivide, the address space serviced by the distributedrouting environment100.

Based on the processing of the first subset of the destination address, thecore level router106 forwards the packet to a distribution level router, in this case illustratively108A. As previously described, the receivingdistribution level router108A processes the destination address of the received packet and also utilizes a subset of the destination IP address to identify a third level router component that will forward the packet to a next network destination (outside of the distributed routing environment100). Similar to thecore level router106, the receiving distribution level router can be configured to utilize a selection of the most significant bits of the IP address (e.g., the prefix) to route the packet. In an illustrative embodiment, the prefix used by thedistribution level router108A is greater than the prefix used by thecore level router106. Based on the processing by thedistribution level router106A, thetransit level router110B receives the forwarded packet and forwards the packet to a designated designation associated with thecommunication network112.

Turning now toFIGS. 2B and 2C, the allocation of IP addresses or subsets of IP addresses within the distributedrouting environment100 will be described. With reference toFIG. 2B, thecore level router106 distributes some portion of the subset of destination IP addresses todistribution level router108A (illustrated at202).Distribution level router108A in turn further distributes the portions of the IP addresses totransit level routers110A,110B, and110C (illustrated at204,206, and208). With reference toFIG. 2C, thecore level router106 distributes a different portion of the subset of destination IP addresses todistribution level router108B (illustrated at210).Distribution level router108B in turn further distributes the portions of the IP addresses totransit level routers110A and110B (illustrated at212 and214).

In an illustrative embodiment, the router management component102 (FIG. 1) can allocate responsibility of subsets of IP addresses to the distribution level routers in a variety of manners. In one embodiment, therouter management component102 can allocate responsibility for the entire set of IP addresses in accordance with assignment of IP addresses equally, or substantially equally, among available routers. In this embodiment, each distribution level router108 becomes responsible for an equal subset of IP addresses or substantially equal if the IP addresses cannot be divided equally. In another embodiment, therouter management component102 can specify specific distribution level router108 to handle high traffic IP addresses or prefixes. In this example, the entire subset of IP addresses may be custom selected by therouter management component102. Alternatively, only the subset of IP addresses meeting a traffic threshold may be custom selected with the remaining portions of IP address automatically distributed.

In still a further embodiment, multiple distribution level routers108 may be selected for a subset of IP addresses. In this embodiment, eachcore level router106 can select from multiple distribution level routers108 based on an equal cost multi-path routing (ECMP) technique in which a specific distribution level router108 is selected based on a standard load sharing technique. Other factors that can be utilized to select from multiple assigned distribution level router108 include carrier preference, Internet weather, resource utilization/health reports, an allocated or determine routing cost, service level agreements (SLAs), or other criteria.

In one embodiment, each distribution router108 can maintain the portion of the FIB that is associated with the subset of IP addresses assigned the respective distribution level router108. In another embodiment, each distribution level router108 can maintain the entire FIB associated with the distributedrouting environment100 in a memory component, such as computer readable medium158 (FIG. 1B). Once a subset of IP addresses are assigned to each respective distribution level router108 (or otherwise updated), the applicable portions of the FIB are loaded in a different memory components, such as memory component154 (FIG. 1B) utilized by the router (e.g., a routing chip level content addressable memory or a processor level cache memory). The maintenance of the applicable portions of the FIB in a memory component facilitates better router performance by faster memory access times for the applicable portion of the FIB. However, in this embodiment, the allocation of FIBs to each distribution level router108 can be modified by loading different portions of the stored FIB from a first memory component storing the entire FIB (e.g., the computer readable medium158) to the memory component maintaining the portion of the FIB allocated to the distribution level router108 (e.g., memory component154). Accordingly, this embodiment facilitates the dynamic allocation of distribution level routers108, the creation of redundant distribution level routers, and additional failover for distribution level routers. Additionally, one or morecore level routers106 can utilize a similar technique in performing the functions associated with the core level of the distributedrouting environment100.

In still a further embodiment, as a variation to the above embodiment, each distribution level router can be allocated a larger portion of the FIB associated with the distributedrouting environment100 than is capable of being maintained in a first memory component of the router, such as memory component154 (e.g., a processor level cache memory). If acore level router106 routes to a distribution level router108 and the corresponding prefixes of the destination IP address do not correspond to the FIB maintained in the first memory component of the distribution level router, the distribution level router can recall the necessary information from the larger subset of the FIB maintained in a different memory component (e.g., computer readable medium158 (FIG. 1B)). The FIB maintained in the first memory component (e.g., memory component152) may be updated to store the prefix in the primary memory component. Alternatively, the FIB in the first memory component may not be automatically updated based on a single request, but based on increases in traffic for a given prefix.

In yet another embodiment, lower traffic prefixes may be assigned to multiple distribution level routers108. In one example, each assigned distribution level router108 does not maintain the lower traffic routing portion of the assigned FIB in the primary memory component. Rather, routing requests for the lower traffic prefixes can be directed to a specific distribution level router based on selection techniques, such as ECMP, and can be processed by a selected distribution level router108 based on the larger FIB maintained in a different memory component within the selected distribution level router.

With reference now toFIG. 3, a routine300 for routing packets and implemented in a distributedrouting environment100 will be described. Atblock302, the distributedrouting environment100 obtains a routing request. As previously described, the routing request is received from a first network102 (FIG. 1) and includes information identifying a destination IP address. Atblock304, acore level router106 corresponding to a first level of the distributedrouting environment100 is selected and receives the routing request. In an illustrative embodiment, eachcore level router106 can perform the same function and can selected in accordance with standard selection techniques, including, but not limited to, random selection, round robin selection, load balancing selection and the like.

Atblock306, the selectedcore level router106 identifies a distribution level router108 corresponding to a second level of the distributedrouting environment100. The core level router108 selects the distribution level router108 based on processing the destination IP address and utilizing a subset of the destination IP addresses (e.g., the prefix) to determine the appropriate distribution level router108. Illustratively, in accordance with an embodiment corresponding to the IPv4 communication protocol, thecore level router106 processing can be based on consideration of a prefix of the eight most significant bits. Atblock308, the selected distribution level router108 identifies a transit level router110 based on processing the destination IP address and utilizing a subset of the destination IP address to determine the appropriate transit level router110. Illustratively, in accordance with an embodiment corresponding to the IPv4 communication protocol, the distribution level router108 processing can be based on a larger subset of IP address (e.g., a longer prefix such as 16 or 24 bits, as needed to select the appropriate transit level router110). One skilled in the relevant art will appreciate, however, theblocks306 and308 may be implemented in a manner such thecore level router106 and distribution level router108 may utilize additional or alternative attributes (including different portions of a destination IP address) of received packets in identifying the next router component to forward the received packet.

Atblock310, the selected transit level router110 transmits the receive packet to the destination recipient associated, or otherwise configured, with the transit level router110. Atblock312, the routine300 terminates.

With reference now toFIG. 4, another routine400 for routing packets and implemented in a distributedrouting environment100 will be described. In an illustrative embodiment, routine400 may be implemented in embodiments in which less than all the FIB associated with a particular distribution router108 is maintained in a primary memory component. Atblock402, a routing request is received at a distribution level router108. The selection and routing to a distribution level router108 was previously described above. Although routine400 will be described with regard to implementation by a distribution level router108, one skilled in the relevant art will appreciate that at least portions of routine400 may be implemented by other components of the distributedrouting environment100, such ascore level routers106 or transit level router110. Atdecision block404, a test is conducted to determine whether the subset of the destination IP address associated with the routing request is in the portion of the FIB table maintained in the primary memory of the selected distribution level router108. If so, atblock406, the distribution level router108 obtains the transit layer routing information from the FIB maintained in the first memory component (e.g., memory component152 (FIG. 1B)). Atblock408, the distribution level router108 forwards the packet to the selected transit level router110.

Alternatively, if atdecision block404 the subset of the destination IP address associated with the routing request is not maintained in the portion of the FIB table maintained in the primary memory of the selected distribution level router108, atblock410, distribution level router108 attempts to obtain additional transit routing information from a separate memory component associated with the distribution level router. Atblock410, the distribution level router108 can update the forwarding table information maintained in the primary memory component with the information obtained from the other memory component. Alternatively, block410 can be omitted or is otherwise optional. Atblock412, the routine terminates.

While illustrative embodiments have been disclosed and discussed, one skilled in the relevant art will appreciate that additional or alternative embodiments may be implemented within the spirit and scope of the present disclosure. Additionally, although many embodiments have been indicated as illustrative, one skilled in the relevant art will appreciate that the illustrative embodiments do not need to be combined or implemented together. As such, some illustrative embodiments do not need to be utilized or implemented in accordance with the scope of variations to the present disclosure.

Conditional language, such as, among others, “can,” “could,” “might,” or “may,” unless specifically stated otherwise, or otherwise understood within the context as used, is generally intended to convey that certain embodiments include, while other embodiments do not include, certain features, elements, or steps. Thus, such conditional language is not generally intended to imply that features, elements or steps are in any way required for one or more embodiments or that one or more embodiments necessarily include logic for deciding, with or without user input or prompting, whether these features, elements or steps are included or are to be performed in any particular embodiment. Moreover, unless specifically stated otherwise, or otherwise understood within the context as used, is generally intended to convey utilization of the conjunction “or” in enumerating a list of elements does not limit the selection of only a single element and can include the combination of two or more elements.

Any process descriptions, elements, or blocks in the flow diagrams described herein and/or depicted in the attached figures should be understood as potentially representing modules, segments, or portions of code which include one or more executable instructions for implementing specific logical functions or steps in the process. Alternate implementations are included within the scope of the embodiments described herein in which elements or functions may be deleted, executed out of order from that shown or discussed, including substantially concurrently or in reverse order, depending on the functionality involved, as would be understood by those skilled in the art. It will further be appreciated that the data and/or components described above may be stored on a computer-readable medium and loaded into memory of the computing device using a drive mechanism associated with a computer-readable medium storing the computer executable components, such as a CD-ROM, DVD-ROM, or network interface. Further, the component and/or data can be included in a single device or distributed in any manner. Accordingly, general purpose computing devices may be configured to implement the processes, algorithms, and methodology of the present disclosure with the processing and/or execution of the various data and/or components described above. Alternatively, some or all of the methods described herein may alternatively be embodied in specialized computer hardware. In addition, the components referred to herein may be implemented in hardware, software, firmware or a combination thereof.

It should be emphasized that many variations and modifications may be made to the above-described embodiments, the elements of which are to be understood as being among other acceptable examples. All such modifications and variations are intended to be included herein within the scope of this disclosure and protected by the following claims.

Claims (22)

What is claimed is:

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

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

receive a packet for routing, wherein the 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 a second level physical routing component based at least in part on an association of the first subset of the destination address with the identified second level physical routing component, wherein the identified second level physical routing component is associated with the first subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of destination addresses to individual second level physical routing components of the second level of the physical routing component hierarchy; and

transmit the packet to the identified second level routing component;

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

receive the packet from a first level physical routing component;

identify a third level physical routing component based at least in part on an association of the second subset of the destination address with the identified third level physical routing component, wherein the identified third level physical routing component is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of the set of destination addresses to individual third level physical routing components of the third level of the physical routing component hierarchy; and

transmit the packet to the identified third level physical routing component; and

a third level of the hierarchy of physical routing components comprising one or more third level physical routing components, wherein each of the one or more third level physical routing components is configured to:

receive the packet from a second level physical routing component;

identify an additional component to which to transmit the packet; and

transmit the packet to the identified additional component.

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

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

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

5. The system ofclaim 1, wherein each physical routing component corresponding to at least one of the first level, the second level, or the third 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.

6. The system ofclaim 1 further comprising a router management device configured to dynamically allocate the individual portions of the set of destination addresses to the individual second level routing components of the second level of the routing component hierarchy.

7. 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 an association of the first subset of the destination address with the identified second level physical routing component, wherein the identified second level physical routing component is associated with the first subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of destination addresses to individual second level physical routing components of the second level of the physical routing component hierarchy;

transmitting the packet to the second level routing component;

identifying, at the second level router component, a third level routing component of a third level of the routing component hierarchy based at least in part on an association of the second subset of the destination address with the identified third level physical routing component, wherein the identified third level physical routing component is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of the set of destination addresses to individual third level physical routing components of the third level of the physical routing component hierarchy;

transmitting the packet to the third level routing component;

identifying, at the third level router component, an additional component to which to transmit the packet; and

transmitting the packet to the additional component.

8. The computer-implemented method ofclaim 7, wherein the destination address corresponds to an IP address.

9. The computer-implemented method ofclaim 8, 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.

10. The computer-implemented method ofclaim 7, wherein at least one routing component of the first level of the routing component hierarchy, the second level of the routing component hierarchy, and the third level of the routing component hierarchy are dynamically allocated individual portions of the set of destination addresses of packets based at least in part on traffic volume associated with the allocated portions of the set of destination addresses of the packets.

11. The computer-implemented method ofclaim 10, wherein remaining routing components of the first level of the routing component hierarchy, the second level of the routing component hierarchy, and the third level of the routing component hierarchy are allocated approximately equal portions of the set of destination addresses of the packets.

12. The computer-implemented method ofclaim 10, wherein remaining routing components of the first level of the routing component hierarchy, the second level of the routing component hierarchy, and the third level of the routing component hierarchy are allocated portions of the set of destination addresses of packets based on at least one of random selection, round robin selection, hashing and load balancing.

13. The computer-implemented method ofclaim 7, 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.

14. A system for routing packets, the system comprising one or more physical routing devices configured with specific computer-executable instructions that, when executed by the physical routing devices, cause the physical routing devices to implement at least:

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 an association of a first subset of the destination address with the identified second level physical routing component, wherein the identified second level physical routing component is associated with the first subset of the destination address based at least in part on a dynamic allocation of individual portions of a set of destination addresses to individual second level physical routing components of the second level of the physical routing component hierarchy; 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 a third level routing component based at least in part on an association of a second subset of the destination address with the identified third level physical routing component, wherein the identified third level physical routing component is associated with the second subset of the destination address based at least in part on a dynamic allocation of individual portions of the set of destination addresses to individual third level physical routing components of the third level of the physical routing component hierarchy; and

transmit the packet to the identified third level routing component;

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

in response to reception of the packet from the second level of the routing component hierarchy, identify an additional component to which to transmit the packet; and

transmit the packet to the identified additional component.

15. The system ofclaim 14, wherein the destination address corresponds to an IP address.

16. The system ofclaim 15, 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.

17. The system ofclaim 14, 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.

18. The system ofclaim 17, 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.

19. The system ofclaim 14, wherein at least one routing component of the first level, the second level, and the third level are dynamically allocated individual portions of the set of destination addresses of packets based at least in part on traffic volume associated with the allocated portions of the set of destination addresses of the packets.

20. The system ofclaim 19, wherein remaining routing component of the first level, the second level, and the third level are allocated portions of the set of destination addresses of packets based on at least one of random selection, round robin selection, hashing and load balancing.

21. The system ofclaim 19, wherein remaining routing component of the first level, the second level, and the third level are allocated approximately equal portions of the set of destination addresses of the packets.

22. The system ofclaim 14 further comprising a router management device configured to dynamically allocate the individual portions of the set of destination addresses to the individual second level routing components of the second level of the routing component hierarchy.

Images