Patent Description:
Current Internet architecture is built around layers of different functions, including a "network layer" which provides a technology-independent abstraction on top of a large set of autonomous, heterogeneous networks. The Internet Protocol (IP) is one mechanism for achieving such an abstraction. However, limitations of the Internet Protocol's "best-effort" service model have prevented the Internet from effectively scaling to meet new requirements, such as security, manageability, wireless networking, mobility, and others.

United States Patent Application Publication number <CIT>, <NPL>) discloses a method and apparatus for managing nodes of a network. In one embodiment, the invention is implemented as part of a computer based network management system. The system allows a network operator to Select, View and modify the configuration of a logical group node at any level of a network hierarchy. The configuration of a logical group node may include, without limitation, logical group node attributes, Summary addresses, and any other information that may be relevant to implementing the desired function of a logical group node. After a change is made to the configuration of a logical group node, the System automatically identifies all physical nodes that may potentially function as the logical group node whose configuration has changed, and causes the configurations of the logical group node to be updated on the identified physical nodes to reflect the change made to the logical group node. In this manner, modifications made to a logical group node are automatically propagated to all physical nodes, at lower levels of hierarchy therein, that might run the logical group node function, eliminating the need to manually update each physical node's configuration one physical node at a time. The invention may be used with any network that involves the aggregation of physical nodes into a hierarchy of logical group nodes, including, without limitation, networks using the PNNI and IP protocols.

European Patent number <CIT>,<NPL>) discloses extending the PNNI protocols to support hierarchical multicast routing and signaling for ATM networks. The invention utilizes an extension to a core-based tree algorithm. Instead of a single core node, core nodes are maintained in each peer group and at each level of the hierarchy. The advantage of this is that one single core node is not overloaded. Additionally, this increases fault-tolerance because there are no single points of failure.

European Patent number <CIT>, <NPL>) discloses methods and systems for rendezvousing resource requests with corresponding resources. Doubly linked sorted lists are traversed using modulo arithmetic in both directions. Sorted lists can be partitioned based on a multiple proximity metrics. Node routing tables provide a logarithmic index to nodes within the ID space of the federation infrastructure to facilitate more efficient routing. Messages can be routed to nodes within a ring and proximally routed to nodes in other partitioned rings.

One shortcoming of the current Internet architecture is that it exposes actual addresses to endpoint modules (e.g., endpoint devices such as servers or client devices; applications executing on endpoint devices, such as virtual machines; etc.) Exposing the actual addresses (e.g., IP addresses) of endpoint modules Internet-wide tends to inhibit the mobility of those modules. For example, a client using a voice-over-IP (VoIP) application that binds to an IP address provided by a cable operator A generally cannot move outside cable operator A's subnet (to which the IP address is assigned) without disrupting the network address registration and application connectivity.

Another issue with the current Internet architecture is that it artificially isolates functions of the same scope by splitting transport and routing/relaying into two separate layers, and artificially limiting the number of layers, which tends to cause growth of routing tables. This issue is especially problematic in datacenter and mobile networks, where large amounts of traffic are forwarded to network devices capable of holding such large routing tables, just to be sent back into the network via hairpin connections. This scenario, in which traffic comes from one source into the network device (e.g., router) and makes a U-turn and goes back the same way it came, is quite common and highly inefficient.

The inventors have recognized and appreciated that the performance of the Internet (or portions thereof, such as datacenters) can be enhanced by using hierarchical topological addressing and recursive routing in one or more layers encapsulated by (lower than) the "network layer" at which the Internet Protocol resides. Using hierarchical topological addressing and recursive routing below the network layer can lead to increased mobility of endpoint modules and reduced size of routing tables, while maintaining compatibility with other portions of the Internet that retain the current Internet architecture.

According to the present invention there are provided a system, method, and computer program according to the independent claims.

The foregoing Summary, including the description of motivations for some embodiments and/or advantages of some embodiments, is intended to assist the reader in understanding the present disclosure, and does not in any way limit the scope of any of the claims.

Certain advantages of some embodiments may be understood by referring to the following description taken in conjunction with the accompanying drawings. Also, the drawings are not necessarily to scale, emphasis instead generally being placed upon illustrating principles of some embodiments of the invention.

Referring to <FIG>, a network <NUM> may include networks <NUM> and <NUM>, which are communicatively coupled via gateways <NUM> and <NUM>. The network <NUM> includes a hierarchical recursive network (HRN) <NUM> and endpoint modules <NUM> connected to the HRN <NUM>. In some embodiments, the network <NUM> also includes the gateway <NUM>. Features of some embodiments of the HRN <NUM> are described below, including suitable topologies of the HRN and routing techniques suitable for use within the HRN. In addition, endpoint modules <NUM> are coupled to network <NUM> and can communicate with the endpoint modules <NUM> via the network <NUM>, the gateways (<NUM>, <NUM>), and the HRN <NUM>.

An endpoint module (<NUM>, <NUM>) may be an endpoint device (e.g., a server computer, laptop computer, desktop computer, tablet computer, smartphone, etc.) or an application executing on an endpoint device (e.g., a virtual machine). Some embodiments of endpoint devices are described in further detail below. Each endpoint module may be assigned at least one unique network identifier ("network ID"), for example, an Internet Protocol (IP) address, a media access control (MAC) address, etc..

The network <NUM> may include one or more communication networks of any suitable type. Some examples of communication networks include a local area network ("LAN"), a wide area network ("WAN"), e.g., the Internet (or a portion thereof), etc. Communication networks may include wired and/or wireless networks. The network <NUM> may perform routing using any suitable routing techniques (e.g., link-state routing, distance vector routing, etc.). In some embodiments, the network <NUM> routes data packets based on the network IDs of the endpoint modules to which the data packets are addressed. As discussed above, performing routing based on the unique network IDs of the endpoint modules can lead to loss of connectivity when mobile endpoint modules (<NUM>, <NUM>) change locations, and can also lead to very large routing tables and associated routing inefficiencies.

The gateways (<NUM>, <NUM>) may route packets between networks (e.g., network <NUM> and network <NUM>) based on the network IDs of the endpoint modules to which the packets are addressed. When gateway <NUM> receives a packet addressed to the network ID of one of the endpoint modules <NUM>, the gateway <NUM> forwards the packet to the network <NUM> for routing to that endpoint module <NUM>. When gateway <NUM> receives a packet addressed to the network ID of one of the endpoint modules <NUM>, the gateway <NUM> forwards the packet to (or toward) the gateway <NUM> for routing to the endpoint module <NUM> via the hierarchical recursive network <NUM>.

When gateway <NUM> receives a packet addressed to the network ID of one of the endpoint modules <NUM>, the gateway <NUM> forwards the packet to the HRN <NUM> for routing to that endpoint module <NUM>. When gateway <NUM> receives a packet addressed to the network ID of one of the endpoint modules <NUM>, the gateway <NUM> forwards the packet to (or toward) the gateway <NUM> for routing to the endpoint module <NUM> via the network <NUM>. An example implementation of a gateway is described below with reference to <FIG> and <FIG>.

In the hierarchical recursive network <NUM>, network devices (e.g., routers) are physically organized in a hierarchical topology (e.g., a tree) and are assigned hierarchical addresses corresponding to their locations within the topology. The network devices may autonomically assign the hierarchical addresses to themselves, and/or the hierarchical addresses may be assigned to the network devices by users (e.g., network administrators). Within the HRN <NUM>, the network devices can use recursive routing protocols. In some embodiments, the routing protocol is implemented using an existing protocol, such as IS-IS. Using the recursive routing protocols, core routers (e.g., routers that are not directly connected to endpoint devices <NUM>) can determine how to forward packets within the HRN <NUM> based on prefixes of the packets' destination addresses, and edge routers (e.g., routers that are directly connected to endpoint devices <NUM>) can determine how to forward packets to core routers based on prefixes of the packets' destination addresses. When a recursive routing protocol is used, only the edge router connected to a particular endpoint module maintains a routing table entry for the address of that endpoint module. Thus, prefix-based recursive routing can greatly reduce the sizes of the routing tables maintained by the network devices in the HRN <NUM>.

In the hierarchical recursive network <NUM>, the edge routers can assign hierarchical addresses to the endpoint modules, and a network registrar can maintain a mapping between the unique network IDs of the endpoint modules and their corresponding hierarchical addresses. The network registrar can be centralized or distributed. When an endpoint module physically moves to a different location in the network, the module can maintain its unique network ID but receive a new hierarchical address from the network. Thus, connectivity in the network layer can be maintained as endpoint modules move, thereby facilitating increased mobility of the endpoint modules.

Some implementations of hierarchical recursive networks <NUM> are described below with reference to <FIG>. In the example of <FIG>, the network <NUM> has a hierarchical topology (in particular, a tree topology), with the network devices (e.g., routing devices) organized in three levels. The first (lowest) level includes the edge routers ("ER") <NUM>. Each edge router <NUM> may be connected to many endpoint modules <NUM>, though, in the example of <FIG>, only two endpoint modules 150a and 150b are shown. The second (intermediate) level includes the core routers ("CR") <NUM>. Each of the core routers <NUM> in the second level may be connected to one or more edge routers <NUM> in the first level. The third (highest) level includes the core routers ("CR") <NUM>. Each of the core routers <NUM> in the third level may be connected to one or more core routers <NUM> in the second level and to one or more gateways <NUM>.

In the example of <FIG>, the network devices (<NUM>, <NUM>, <NUM>) are not only organized in a hierarchical topology, but also assigned hierarchical addresses corresponding to their locations within the topology. For example, edge router 210c is assigned address <NUM>. <NUM>, and all the endpoint modules <NUM> connected to edge router 210c are assigned addresses with a prefix of <NUM>. <NUM>, matching the address of the edge router 210c. Likewise, core router 220a is assigned address <NUM>, and all edge routers <NUM> assigned addresses with a prefix of <NUM> (i.e., ERs 210a, 210b, and 210c) are connected to CR 220a. Furthermore, core router 230a is assigned address <NUM>, and all core routers <NUM> assigned addresses with a prefix of <NUM> (i.e., CRs 220a, 220b, and 220c) are connected to CR 230a. (in the example of <FIG>, some of the edge routers <NUM> in the first level are connected to more than one core router <NUM> in the second level, and some of the core routers <NUM> in the second level are connected to more than one core router <NUM> in the third level. These redundant links within the network <NUM> can facilitate fault tolerance and load balancing. In addition, these redundant links do not interfere with the hierarchical topology of the network <NUM>, nor do they interfere with the network's hierarchical addressing scheme.

With the network devices <NUM>-<NUM> and the endpoint modules <NUM> organized in a hierarchical topology with hierarchical addresses corresponding to their locations in the topology, the network devices can efficiently route data packets through the network <NUM> using recursive one-hop routing. Within the network <NUM>, a recursive routing protocol may be characterized by the following conditions:.

An example of a registration operation performed by the network <NUM> is now described. In one embodiment, the hierarchical address of an endpoint module <NUM> is maintained by a registrar of the network <NUM> as a temporary alias. To connect to the network <NUM>, the endpoint module <NUM> registers with the network registrar via the edge router <NUM> to which the endpoint module <NUM> is connected, and the registration information (e.g., the endpoint module's temporary alias (hierarchical address) and unique network ID) is distributed to other network devices that provide the same registration service. For example, to connect to the network <NUM>, the endpoint module 150a registers with the edge router 210c, which has an address of <NUM>. The registrar assigns the endpoint module 150a a temporary alias (hierarchical address) that complies with the hierarchical addressing scheme, i.e., a hierarchical address that includes the address of the edge router 210c as a prefix. In the example of <FIG>, the hierarchical address assigned to the endpoint module 150a is <NUM>.

In the foregoing example of registration, the endpoint module 150a registers with a single edge router 210c. In some embodiments, endpoint modules <NUM> can register with one or more edge routers <NUM>. Redundant registration and connection of the endpoint modules <NUM> to multiple edge routers can increase the network's resilience, and may also facilitate load balancing. In scenarios in which an endpoint module <NUM> registers with multiple edge routers <NUM>, the endpoint module may be assigned multiple unique network IDs (one for each registration) and multiple hierarchical addresses (one for each edge router).

An example of a routing operation performed by the network <NUM> is now described. Referring to <FIG>, endpoint module 150b has been assigned address N. <NUM> and is connected to edge router 210p, which has been assigned address N. To initiate the transmission of a packet to endpoint module 150a, endpoint module 150b addresses the network layer packet PNL to endpoint module 150a's unique network ID, and forwards the packet to edge router 210p at the network layer. Edge router 210p queries the registrar for the location of endpoint module 150a (e.g., the address of the edge router <NUM> to which the endpoint module 150a is connected). Edge router 210p receives a response from the registrar, indicating that endpoint module 150a is connected to the edge router (210c) with address <NUM>.

Continuing the routing example, the edge router 210p checks its routing table for entries matching the packet's destination address <NUM>. In this case, the only route from edge router 210p to any address beginning with the prefix "<NUM>" is through the core router 220i. Thus, the packet's destination address "<NUM>. <NUM>" matches an entry "<NUM>. x" in the edge router's routing table, and the edge router 210p forwards the packet to core router 220i via the port corresponding to the matching table entry.

Continuing the routing example, the core router 220i checks its routing table for entries matching the packet's destination address <NUM>. In this case, address <NUM>. <NUM> is reachable via core routers 220a, 220b, and 220c, so the routing table may include an entry "<NUM>. x" corresponding to core router 220a, an entry "<NUM>. x" corresponding to core router <NUM>, and another entry "<NUM>. x" corresponding to core router <NUM>. The core router 220i may use any suitable technique to select among the matching entries (e.g., a routing metric, equal cost multipath selection, etc.). For purposes of this example, the core router 220i selects the table entry "<NUM>. x" because it matches the longest prefix portion of the destination address <NUM>. <NUM>, and forwards the packet to core router 220a.

Continuing the routing example, the core router 220a checks its routing table for entries matching the packet's destination address <NUM>. In this case, address <NUM>. <NUM> is reachable via edge router 210c and via core router 230a. As discussed above, the core router 220i may use any suitable technique to select among the matching entries. For purposes of this example, the core router 220a selects the table entry "<NUM>. <NUM>" because it matches the entire destination address <NUM>. <NUM>, and forwards the packet to edge router 210c.

Continuing the routing example, the packet has reached the edge router (210c) to which the endpoint module 150a is connected. After determining that the destination address of the packet matches the address of the edge router 210c, the edge router 210c checks with the registrar to determine whether a temporal alias (hierarchical address) has already been assigned to the unique network ID of the endpoint module 150a. As described above, the registrar has assigned temporal alias <NUM>. <NUM> to the endpoint module 150a. Thus, the edge router checks its routing table for an entry matching the endpoint module's temporal alias, and forwards the packet to endpoint module 150a using the information in the matching table entry.

As the foregoing example demonstrates, within the network <NUM>, the unique network ID of each endpoint module has only local meaning to the edge router to which the endpoint module is connected. In addition, any response packet from endpoint module 150a to endpoint module 150b can be returned using the same recursive hop-by-hop routing as the received packet. Furthermore, none of the network devices need to have an entry for the full address of the endpoint module, only for the next hop. In addition, the number of layers in the network <NUM> is practically unlimited and can be artificially determined based on suitable criteria, thus providing flexibility in network design.

An example of a network reorganization operation performed by the network <NUM> is now described. When a new network device or routing layer is added to the network <NUM>, the network autonomically readdresses the network devices, as doing so does not disrupt any connectivity. This architecture provides mobility for endpoint modules (e.g., services, hosts, etc.) in the network, as the host connectivity is not bound by network layer addressing and enforces security, as different intents can be enforced at different points in the network without adding any specialized network devices such as firewalls, etc..

Some examples have been described in which all routing devices in the network <NUM> are in a single routing layer governed by the same routing protocol, even though the routing devices are organized in different levels of a hierarchical topology. In some embodiments, the different routing devices in the network <NUM> may be included in different routing layers, which may be governed by different routing protocols.

Referring to <FIG>, an edge router <NUM> may perform a routing method <NUM> to route packets in a hierarchical recursive network. At step <NUM>, the edge router receives a packet. The edge router may receive the packet from an endpoint module <NUM> connected to the edge router, or from a core router <NUM> connected to the edge router. In some embodiments, the edge router may determine whether it received the packet from an endpoint module <NUM> or from a core router, and may store data indicating which type of device provided the packet to facilitate further processing of the packet. For example, the edge router may determine which type of device provided the packet based on which port received the packet (e.g., because the edge router may have access to data indicating which of its ports are connected to endpoint modules and which of its ports are connected to core routers), based on the packet's type (e.g., because endpoint modules generally send network layer packets addressed to unique network IDs, whereas core routers generally send hierarchical recursive routing packets addressed to hierarchical addresses in the network.

At step <NUM>, the edge router determines whether the packet includes a hierarchical address of a destination device in the network. In some embodiments, the edge router makes this determination by examining the contents of the packet. For example, the packet's type may indicate whether the packet contains a hierarchical address. In some embodiments, the edge router makes this determination based on which type of device sent the packet. For example, the edge router may determine that packets received from core routers include hierarchical addresses of destination devices, and that packets received from endpoint modules do not include such addresses. At step <NUM>, having determined that the packet includes a hierarchical address of a destination device, the edge router determines whether it is the destination device (e.g., by looking up the hierarchical address of the destination device in a routing table and determining that the packet's destination address matches the table entry for the edge router's own address.

If the packet's destination address matches the address of the edge router, the edge router proceeds to step <NUM>. At step <NUM>, the edge router extracts the unique network ID of the destination endpoint module from the packet and determines the temporal alias (hierarchical address) of the destination endpoint module. Alternatively, if a valid temporal alias is not currently assigned to the unique network ID of the destination endpoint module, the edge router assigns the endpoint module's temporal alias, and the edge router adds an entry to its routing table, such that the entry maps the temporal alias of the endpoint module to an edge router port to which the endpoint module is connected.

At step <NUM>, the edge router forwards the packet to the endpoint module. To perform this forwarding operation, the edge router may look up the temporal alias of the endpoint module (or the suffix thereof) in the routing table, identify the edge router port connected to the endpoint module based on the data in the matching entry in the routing table, and forward the packet to the endpoint module via the identified port.

Returning to step <NUM>, if the packet does not include the hierarchical address of a destination device in the network, the edge router proceeds to step <NUM>. At step <NUM>, the edge router extracts a unique network ID of the destination device from the packet and determines whether an endpoint module having that network ID is in the network. In some embodiments, the edge router makes this determination by querying the network registrar to determine whether an endpoint module having that network ID has registered on the network.

If the destination endpoint module is not registered on the network, the edge router proceeds to step <NUM>. At step <NUM>, the edge router prepares to route the packet outside the hierarchical network. For example, the edge router may wrap the packet in a wrapper with a special hierarchical address ("X") indicating that destination endpoint module is outside the network. At step <NUM>, the edge router forwards the packet to the next hop for the packet's destination address, based on a prefix of the destination address. In the scenario in which the destination address is the special hierarchical address X, the edge router forwards the packet to a core router in the second routing level, and the core routers recursively forward the packet to a gateway <NUM> for routing outside the network. As described above, the edge router may use a routing table to identify one or more potential next hops along the packet's route, and may use any suitable criteria to select the next hop if the routing table identifies multiple potential next hops.

Returning to step <NUM>, if the destination endpoint module is registered on the network, the edge router proceeds to step <NUM>. In this scenario, the edge router has received the packet from an endpoint module connected to the edge router, and in steps <NUM>, <NUM>, and <NUM>, the edge router prepares the packet for routing through the hierarchical recursive network <NUM> and forwards the packet to the next hop on its route toward the destination endpoint module.

More specifically, at step <NUM>, the edge router determines the hierarchical address of the edge router to which the destination endpoint module is connected. In some embodiments, the edge router makes this determination by querying the network registrar for the address of the edge router with which the destination endpoint module is registered. At step <NUM>, the edge router wraps the packet in a wrapper with the address of the edge router to which the destination endpoint module is connected. At step <NUM>, the edge router forwards the packet to the next hop for the packet's destination address, based on a prefix of the destination address. In the scenario in which the destination address is the address of the edge router to which the destination endpoint module is connected, the source edge router forwards the packet to a core router in the second routing level, and the core routers recursively forward the packet to the destination edge router. As described above, the edge router may use a routing table to identify one or more potential next hops along the packet's route, and may use any suitable criteria to select the next hop if the routing table identifies multiple potential next hops.

Referring to <FIG>, a core router (<NUM>, <NUM>) may perform a routing method <NUM> to route packets in a hierarchical recursive network. At step <NUM>, the core router receives a packet. The core router may receive the packet from a gateway <NUM> connected to the network, from another core router, or from an edge router. In some embodiments, the core router may determine whether it received the packet from (<NUM>) a gateway, or (<NUM>) a core router or edge router.

In the latter case, the core router simply proceeds to step <NUM>. In the former case, the core router may extract the unique network ID of the destination endpoint module from the packet and query the network registrar to determine whether the unique network ID is registered on the network, and if so, to identify the hierarchical address of the edge router to which the destination endpoint module is connected. The core router may then wrap the packet in a wrapper having its destination address set to the hierarchical address of that edge router. The core router then proceeds to step <NUM>.

At step <NUM>, the core router determines whether destination address of the packet is the core router's address. If so, the core router processes the packet at step <NUM>. Otherwise, the core router proceeds to step <NUM>. At step <NUM>, the core router forwards the packet to the next hop on its route to the destination endpoint module based on the packet's hierarchical address. As described above, the core router may use a routing table to identify one or more potential next hops along the packet's route, and may use any suitable criteria to select the next hop if the routing table identifies multiple potential next hops.

In some embodiments, the hierarchical recursive network <NUM> can be used to perform packet routing in a datacenter. Referring to <FIG>, the edge routers <NUM> can be top-of-rack switches (TORs), the core routers <NUM> can be fabric switches, and the core routers <NUM> can be spines. The endpoint modules <NUM> can be servers or applications executing on servers (e.g., virtual machines). <FIG> further illustrates how logical network constructs that may be beneficial in the datacenter environment can be implemented using the hierarchical recursive network <NUM> of <FIG>.

In the example of <FIG>, the vertical structures in dashed lines represent routing devices. In particular, the edge router 210c is implemented using a TOR (which is connected to the endpoint module 150a), the core router 220a connected to the edge router 210c is implemented using a fabric switch, the core router 230a connected to the core router 220a is implemented using a spine, the core router 210i connected to the core router 230a is implemented using another fabric switch, and the edge router 210p connected to the core router 210i is implemented using another TOR (which is connected to the endpoint module 150b).

In the example of <FIG>, the horizontal structures <NUM>-<NUM> represent logical network constructs that may facilitate communication in the datacenter. In particular, the network constructs include multiple service / tenant inter-process communication (IPC) fabrics <NUM> (e.g., one service / tenant IPC fabric per service / tenant of the datacenter), an inter-datacenter IPC fabric <NUM> (connecting two or more datacenters), an intra-datacenter IPC fabric <NUM> (e.g., one intra-datacenter IPC fabric per physical datacenter), and multiple shim IPC data fabrics <NUM> (e.g., reduced broadcast domains within a physical datacenter).

Referring to <FIG>, a network system <NUM> is shown. The gateways (<NUM>, <NUM>), edge routers <NUM>, and/or core routers (<NUM>, <NUM>) of <FIG> and <FIG> may be implemented, using embodiments of the network system <NUM>.

The network system <NUM> provides a forwarding plane <NUM>, a routing component (routing plane <NUM>), and a servicing component (service plane <NUM>) to provide for packet servicing and forwarding by the network system. Network system <NUM> may be a high-end router capable of deployment within a service provider network or datacenter. Moreover, forwarding plane <NUM> may be provided by dedicated forwarding integrated circuits, may be distributed (e.g., over a multi-stage switch fabric, such a <NUM>-stage Clos switch fabric, or over a multi-chassis router), and may accommodate processing related to pure routing as well as other network services (e.g., firewall and deep packet inspection processing). Together, routing plane <NUM> and forwarding plane <NUM> may operate as a high-end router.

In some embodiments, the network system <NUM> is distributed, such that two or more of the forwarding plane <NUM>, servicing plane <NUM>, and routing plane <NUM> are implemented on using different devices, rather than being integrated in the same device. In some embodiments, each edge router <NUM> and core router (<NUM>, <NUM>) may implement a forwarding plane <NUM>, and the servicing plane and routing plane may be located remotely from the forwarding plane. In some embodiments, a network system <NUM> may include one or more routing planes <NUM> (or routing engines <NUM>) per forwarding plane <NUM> (or forwarding component <NUM>). Separating the planes in this manner may reduce the computational burden on the edge and core routers, thereby enhancing the speed and efficiency of the network.

Alternatively, the servicing plane <NUM> may be tightly integrated within the network device (e.g., by way of service cards) so as to use forwarding plane <NUM> of the routing components in a shared, cooperative manner. In some embodiments, the servicing plane may perform security operations on packets sent to the service plane <NUM> by the flow control unit <NUM>. For example, when a packet of an incoming packet flow is received by network device <NUM> (e.g., via an interface card <NUM> of the network device <NUM>) and injected into the forwarding plane <NUM> normally used for packet routing, the flow control unit <NUM> of forwarding plane <NUM> may analyzes the packet and determine based on the analysis whether to (<NUM>) send the packet through one or more service cards <NUM> of the service plane <NUM> or (<NUM>) send the packet directly to the forwarding component <NUM>.

Service cards <NUM> within security plane <NUM> may be installed along a backplane or other interconnect of network device <NUM> to perform a variety of types of processing to packets, such as Intrusion Detection and Prevention (IDP) analysis, virus scanning, deep packet inspection, or ciphering. In some embodiments, service cards <NUM> may provide application layer gateway (ALG) and protocol proxy software applications, e.g., for Voice over IP (VoIP) call setup.

A service card <NUM> may issue commands for dynamic installation of filters into a flow table / removal of filters from the flow table (not shown) within flow control unit <NUM> of forwarding plane <NUM>. When a packet is processed by forwarding component <NUM>, forwarding component <NUM> may apply an appropriate action according to a dynamic filter that matched the packet. Exemplary actions that network device <NUM> may apply in forwarding plane <NUM> as specified by filters include rate limiting, queuing, routing, firewalling (i.e., blocking or dropping the packet), counting, network address translation (NAT), quality of service (QoS), sequence number adjustment, or other types of actions.

In this manner, actions typically performed by a security device and actions typically performed by a router can be combined in an integrated manner within the shared forwarding plane <NUM> to streamline packet forwarding in network device <NUM>. Alternatively, in some embodiments, the service plane <NUM> may not be included in the network device <NUM>.

Network device <NUM> includes a routing engine <NUM> that provides a routing plane <NUM> and a downstream forwarding component <NUM> within forwarding plane <NUM>. Routing engine <NUM> is primarily responsible for maintaining a routing information base (RIB) <NUM> to reflect the current topology of the network (e.g., network <NUM>) and other network entities to which network device <NUM> is connected. For example, routing engine <NUM> may provide an operating environment for execution of routing protocols that communicate with peer routers and periodically update RIB <NUM> to accurately reflect the topology of the network and the other network entities.

In accordance with RIB <NUM>, forwarding component <NUM> maintains forwarding information base (FIB) <NUM> that associates network destinations (e.g., hierarchical network addresses or prefixes thereof) with specific next hops and corresponding interface ports of output interface cards of network device <NUM>. Routing engine <NUM> may process RIB <NUM> to perform route selection and generate FIB <NUM> based on selected routes. When forwarding a packet, forwarding component <NUM> traverses the routing table of the network device <NUM> based on information (e.g., a hierarchical network address of a destination endpoint module, or a prefix thereof) within a header of the packet to ultimately select a next hop and output interface to which to forward the packet.

Referring to <FIG>, logical components of the network device <NUM> are shown to illustrate the logical interaction between modules regardless of the underlying physical implementation. The network device <NUM> may include a control unit <NUM> that includes a routing engine <NUM> and a forwarding engine <NUM>. As described above, the routing engine <NUM> is primarily responsible for maintaining routing information base (RIB) <NUM>. Routing engine <NUM> also includes routing protocols <NUM> that perform routing operations. In accordance with RIB <NUM>, forwarding component <NUM> of forwarding engine <NUM> maintains forwarding information base (FIB) <NUM> that associates network destinations (e.g., hierarchical network addresses or prefixes thereof) with specific next hops and corresponding interface ports.

Network device <NUM> includes interface cards 794a-794n ("IFCs <NUM>") that receive and send packets via network links. IFCs <NUM> may be coupled to the network links via a number of interface ports. Generally, flow control unit <NUM> of forwarding engine <NUM> may relay certain packets received from IFCs <NUM> to service cards 624a-<NUM> ("service cards <NUM>") in accordance with filter settings. Service cards <NUM> may receive packets from flow control unit <NUM>, selectively provide services in accordance with information within the packet, and relay the packet or any response packets to control unit <NUM> for forwarding by forwarding component <NUM>.

In one embodiment, each of forwarding engine <NUM> and routing engine <NUM> may include one or more dedicated data processing apparatus and may be communicatively coupled by a data communication channel. The data communication channel may be a high-speed network connection, bus, shared-memory or other data communication mechanism. Forwarding engine <NUM>, routing engine <NUM>, or both, may make use of the data structures and organization described above with respect to <FIG>. For example, routing plane <NUM> of <FIG> may correspond to routing engine <NUM>, forwarding plane <NUM> of <FIG> may correspond to forwarding engine <NUM>, and interface cards <NUM> and service plane <NUM> of <FIG> may correspond to service cards <NUM>.

Network device <NUM> may further include a chassis (not shown) for housing control unit <NUM>. The chassis has a number of slots (not shown) for receiving a set of cards, including IFCs <NUM> and service cards <NUM>. Each card may be inserted into a corresponding slot of the chassis for electrically coupling the card to control unit <NUM> via a bus, backplane, or other electrical communication mechanism.

Service cards <NUM> may relay processed packets or reply packets to control unit <NUM>. Control unit <NUM> may forwards the packet in accordance with FIB <NUM>. The forwarding component <NUM> may apply one or more actions to packets relayed to the forwarding component <NUM> by control unit <NUM>, as specified by matching filters. For example, forwarding component <NUM> may perform rate limiting, queuing, packet mirroring, routing, firewalling (i.e., blocking or dropping the packet), counting, logging, network address translation (NAT), sequence number adjustment, quality of service (QoS), or other types of actions.

The functions of network device <NUM> may be implemented by executing, with one or more data processing apparatus, instructions fetched from a computer-readable storage medium. The term "data processing apparatus" encompasses all kinds of apparatus, devices, and machines for processing data, including by way of example a programmable processor (e.g., a general or special purpose microprocessor), a system on a chip, or multiple ones or combinations, of the foregoing. Generally, a processor will receive instructions and data a computer-readable storage medium. Examples of such media include random access memory (RAM), read-only memory (ROM), non-volatile random access memory (NVRAM), electrically erasable programmable read-only memory (EEPROM), flash memory, and the like.

An endpoint device (<NUM>, <NUM>) may include a computer, which may include one or more data processing apparatus for performing actions in accordance with instructions and one or more memory devices for storing instructions and data. Moreover, a computer can be embedded in an endpoint device, e.g., a mobile telephone, a personal digital assistant (PDA), a mobile audio or video player, a game console, a Global Positioning System (GPS) receiver, or a portable storage device (e.g., a universal serial bus (USB) flash drive), to name just a few.

The techniques described herein can be implemented in digital electronic circuitry, or in computer hardware, firmware, software, or in combinations of them. The techniques can be implemented as a computer program product, i.e., a computer program tangibly embodied in an information carrier, e.g., in a machine-readable storage device or other non-transitory storage medium, for execution by, or to control the operation of, data processing apparatus, e.g., a programmable processor, a computer, or multiple computers.

While operations are depicted in the drawings in a particular order, this should not be understood as requiring that such operations be performed in the particular order shown or in sequential order, or that all illustrated operations be performed, to achieve desirable results.

The term "approximately", the phrase "approximately equal to", and other similar phrases, as used in the specification and the claims (e.g., "X has a value of approximately Y" or "X is approximately equal to Y"), should be understood to mean that one value (X) is within a predetermined range of another value (Y). The predetermined range may be plus or minus <NUM>%, <NUM>%, <NUM>%, <NUM>%, <NUM>%, <NUM> %, or less than <NUM> %, unless otherwise indicated.

The indefinite articles "a" and "an," as used in the specification and in the claims, unless clearly indicated to the contrary, should be understood to mean "at least one. " The phrase "and/or," as used in the specification and in the claims, should be understood to mean "either or both" of the elements so conjoined, i.e., elements that are conjunctively present in some cases and disjunctively present in other cases. Thus, as a non-limiting example, a reference to "A and/or B", when used in conjunction with open- ended language such as "comprising" can refer, in one embodiment, to A only (optionally including elements other than B); in another embodiment, to B only (optionally including elements other than A); in yet another embodiment, to both A and B (optionally including other elements); etc..

As used in the specification and in the claims, "or" should be understood to have the same meaning as "and/or" as defined above. Only terms clearly indicated to the contrary, such as "only one of or "exactly one of," or, when used in the claims, "consisting of," will refer to the inclusion of exactly one element of a number or list of elements. In general, the term "or" as used shall only be interpreted as indicating exclusive alternatives (i.e. "one or the other but not both") when preceded by terms of exclusivity, such as "either," "one of," "only one of," or "exactly one of" "Consisting essentially of," when used in the claims, shall have its ordinary meaning as used in the field of patent law.

As used in the specification and in the claims, the phrase "at least one," in reference to a list of one or more elements, should be understood to mean at least one element selected from any one or more of the elements in the list of elements, but not necessarily including at least one of each and every element specifically listed within the list of elements and not excluding any combinations of elements in the list of elements.

Claim 1:
A system for hierarchical topological addressing and hierarchical recursive routing in a network (<NUM>), the system comprising:
a plurality of routing devices (<NUM>, <NUM>, <NUM>) operating in two or more routing layers below a network layer in a network protocol stack, wherein within each routing layer a respective group of the routing devices (<NUM>, <NUM>, <NUM>) are organized in a respective hierarchical topology, each topology including a plurality of levels, the levels including at least a first level and a second level, the first level including a first subset of the respective group of routing devices, the second level including a second subset of the respective group of routing devices, each routing device (<NUM>) in the first level being directly connected to one or more routing devices in the second level, each routing device in the hierarchical topology having a hierarchical address based on a location of the respective routing device within the hierarchical topology,
wherein, within the respective hierarchical topology corresponding to each routing layer, the hierarchical address of each routing device (<NUM>) in the first level includes the hierarchical address of a corresponding routing device (<NUM>) in the second level, and wherein each of the routing devices in the hierarchical topology is operable to perform recursive one-hop routing to route packets through the network, and wherein a first routing device performing the recursive one-hop routing on a particular packet includes:
selecting a network port of the first routing device based on at least a prefix of a destination address of the packet, wherein the destination address is a hierarchical address of a second routing device in the first level, and
forwarding the packet to a routing device directly connected to the selected port.