Network routing systems and techniques

Abstract

A system for hierarchical topological addressing and hierarchical recursive routing in a network includes routing devices organized in a hierarchical topology forming a routing layer including levels. The levels include first and second levels including first and second subsets of the routing devices, respectively. Each routing device in the first level is directly connected to endpoint modules and to routing devices in the second level. Each routing device has a hierarchical address based on a location of the routing device within the hierarchical topology. Each routing device performs recursive one-hop routing to route packets through the network. Performing recursive one-hop routing on a particular packet includes: selecting a network port based on 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 network port.

What is claimed is: 
     
         1 . A system for hierarchical topological addressing and hierarchical recursive routing in a network, the system comprising:
 a plurality of routing devices organized in a hierarchical topology, the topology forming a routing layer including a plurality of levels, the levels including a first level and a second level, the first level including a first subset of the routing devices, the second level including a second subset of the routing devices, each routing device in the first level being directly connected to one or more endpoint modules and 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 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 network port. 
   
     
     
         2 . The system of  claim 1 , wherein the routing layer is below a network layer in a network protocol stack. 
     
     
         3 . The system of  claim 2 , wherein the network layer is an Internet Protocol (IP) layer. 
     
     
         4 . The system of  claim 2 , wherein the endpoint modules include a first endpoint module operable to establish a network connection with a second endpoint module in the network layer, and packets routed between the first and second endpoint modules are routed through the network via the recursive one-hop routing. 
     
     
         5 . The system of  claim 4 , wherein the first and second endpoint modules establish the network connection in the network layer using a first unique network identifier (ID) of the first endpoint module and a second unique network identifier (ID) of the second endpoint module. 
     
     
         6 . The system of  claim 5 , wherein a particular routing device R 1  in the first level is directly connected to the first endpoint module prior to the network connection being established, wherein the particular routing device R 1  assigns a hierarchical address to the first endpoint module prior to the network connection being established, wherein a particular routing device R 2  changes the hierarchical address of the first endpoint module after the network connection is established, and wherein the network maintains the network connection without interruption before and after the change in the hierarchical address of the first endpoint module. 
     
     
         7 . The system of  claim 2 , further comprising a gateway device operable to route packets between the network and one or more external networks, wherein the gateway device uses unique network identifiers (IDs) in the network layer to route the packets. 
     
     
         8 . The system of  claim 7 , wherein the unique network IDs are Internet Protocol (IP) addresses and/or media access control (MAC) addresses. 
     
     
         9 . The system of  claim 1 , wherein each routing device in the hierarchical topology implements a network forwarding plane and communicates with one or more remote network routing planes. 
     
     
         10 . The system of  claim 9 , wherein each routing device further communicates with one or more remote network service planes. 
     
     
         11 . The system of  claim 1 , wherein the routing devices in the hierarchical topology autonomically reassign the hierarchical addresses to themselves in response to a change in the hierarchical topology of the routing devices. 
     
     
         12 . A method for hierarchical topological addressing and hierarchical recursive routing in a network including a plurality of routing devices organized in a hierarchical topology, the topology forming a routing layer including a plurality of levels, the levels including a first level and a second level, the first level including a first subset of the routing devices, the second level including a second subset of the routing devices, each routing device in the first level being directly connected to one or more endpoint modules and 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, each of the routing devices in the hierarchical topology being operable to perform recursive one-hop routing to route packets through the network, the method comprising:
 performing, by a first routing device, recursive one-hop routing on a particular packet, including:
 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 network port. 
   
     
     
         13 . The method of  claim 12 , wherein the routing layer is below a network layer in a network protocol stack. 
     
     
         14 . The method of  claim 13 , wherein the network layer is an Internet Protocol (IP) layer. 
     
     
         15 . The method of  claim 13 , wherein the endpoint modules include a first endpoint module operable to establish a network connection with a second endpoint module in the network layer, and wherein packets routed between the first and second endpoint modules are routed through the network via the recursive one-hop routing. 
     
     
         16 . The method of  claim 15 , wherein the first and second endpoint modules establish the network connection in the network layer using a first unique network identifier (ID) of the first endpoint module and a second unique network identifier (ID) of the second endpoint module. 
     
     
         17 . The method of  claim 16 , wherein a particular routing device R 1  in the first level is directly connected to the first endpoint module prior to the network connection being established, wherein the particular routing device R 1  assigns a hierarchical address to the first endpoint module prior to the network connection being established, wherein a particular routing device R 2  changes the hierarchical address of the first endpoint module after the network connection is established, and wherein the network maintains the network connection without interruption before and after the change in the hierarchical address of the first endpoint module. 
     
     
         18 . The method of  claim 13 , wherein the network further includes a gateway device operable to route packets between the network and one or more external networks, wherein the gateway device uses unique network identifiers (IDs) in the network layer to route the packets. 
     
     
         19 . The method of  claim 18 , wherein the unique network IDs are Internet Protocol (IP) addresses and/or media access control (MAC) addresses. 
     
     
         20 . The method of  claim 12 , wherein each routing device in the hierarchical topology implements a network forwarding plane and communicates with one or more remote network routing planes. 
     
     
         21 . The method of  claim 20 , wherein each routing device further communicates with one or more remote network service planes. 
     
     
         22 . The method of  claim 12 , wherein the routing devices in the hierarchical topology autonomically reassign the hierarchical addresses to themselves in response to a change in the hierarchical topology of the routing devices.