Stateful load balancing in a stateless network

Abstract

A packet routing method for directing packets of a session in an IP network causes an intermediate node to obtain a lead packet of a plurality of packets in a given session. The intermediate node has an electronic interface in communication with the IP network and obtains the lead packet through that same interface. The method maintains, in a routing database, state information relating to a plurality of sessions in the IP network. Each session includes a single stateful session path formed by an ordered plurality of nodes in the IP network, and the state information includes information about the ordered plurality of nodes in the sessions. The method further accesses the routing database to determine the state of a plurality of sessions, and forms a stateful given path for packets of the given session across the IP network as a function of the state information in the routing database.

What is claimed is: 
     
         1 . A packet routing method for directing packets of a session between an originating node and a destination node in an IP network, the method comprising an intermediate node that includes a processor configured to perform the following acts:
 obtaining a lead packet of a plurality of packets in a given session, the intermediate node having an electronic interface in communication with the IP network, the intermediate node obtaining the lead packet through the electronic interface;   maintaining, in a routing database, state information relating to a plurality of sessions in the IP network, each session including a single stateful session path formed by an ordered plurality of nodes in the IP network, the state information including information relating to the ordered plurality of nodes in each of the sessions;   accessing the routing database to determine the state of a plurality of the sessions;   forming a stateful given path for packets of the given session across the IP network between the intermediate node and destination node, forming being a function of the state information in the routing database;   storing state information relating to the stateful given path and the given session in the routing database; and   forwarding the lead packet via the electronic interface toward the destination along the stateful given path.   
     
     
         2 . The packet routing method as defined by  claim 1  wherein the intermediate node includes a routing device or a switching device. 
     
     
         3 . The packet routing method as defined by  claim 1  wherein the ordered plurality of nodes in each session includes a plurality of nodes between two end nodes, the plurality of nodes between the two end nodes in each session being configured to transmit each packet in its session in the same node order between the two end nodes. 
     
     
         4 . The packet routing method as defined by  claim 1  wherein forming the stateful given path comprises accessing one or more of flow utilization and cost information relating to a plurality of nodes in the routing database. 
     
     
         5 . The packet routing method as defined by  claim 1  wherein the stateful given path comprises an ordered plurality of given nodes between the originating node and the destination node, the ordered plurality of given nodes having a first node next to the originating node, the first node being the intermediate node. 
     
     
         6 . The packet routing method as defined by  claim 1  further comprising:
 receiving a plurality of additional packets for the given session from the originating node; and 
 forwarding the plurality of additional packets for the given session toward the destination node along the stateful given path. 
 
     
     
         7 . The packet routing method as defined by  claim 1  wherein forming a stateful given path comprises determining utilization of the stateful session paths and bandwidth of the stateful session paths. 
     
     
         8 . The packet routing method as defined by  claim 1  further comprising:
 receiving a plurality of packets in a return session from the destination node, the packets in the return session being addressed toward the originating node; and 
 forwarding, through the electronic interface, substantially all of the packets in the return session toward the originating node along the stateful given path. 
 
     
     
         9 . The packet routing method as defined by  claim 1  wherein the destination node comprises an edge router for a data center network. 
     
     
         10 . The packet routing method as defined by  claim 1  wherein the stateful given path comprises an ordered plurality of given nodes between the originating node and the destination node, the ordered plurality of given nodes including the intermediate node and a next node next to and downstream of the intermediate node within the ordered plurality of given nodes, the method further comprising addressing the lead packet to the next node so that a plurality of network devices receive the lead packet after it is forwarded and before the next node receives the lead packet. 
     
     
         11 . A routing device for directing packets of a session between an originating node and a destination node in an IP network, the router comprising:
 an electronic interface configured to receive a lead packet of a plurality of packets in a given session, the electronic interface being configured to be connectable to the IP network;   a routing database operatively coupled with the electronic interface, the routing database being configured to store state information relating to a plurality of sessions in the IP network, each session including a single stateful session path formed by an ordered plurality of nodes in the IP network, the state information including information relating to the ordered plurality of nodes in each of the sessions;   a path generator operatively coupled with the routing database, the path generator being configured to access the routing database to determine the state of a plurality of the sessions, the path generator also being configured to form a stateful given path for packets of the given session across the IP network between the routing device and the destination node, the path generator forming the stateful given path as a function of the state information in the routing database, the state information relating to the stateful given path and the given session being stored in the routing database; and   a router operatively coupled with the path generator, the router being configured to forward the lead packet via the electronic interface toward the destination along the stateful given path.   
     
     
         12 . The routing device as defined by  claim 11  wherein the ordered plurality of nodes in each session includes a plurality of nodes between two end nodes, the plurality of nodes between the two end nodes in each session being configured to transmit each packet in its session in the same node order between the two end nodes. 
     
     
         13 . The routing device as defined by  claim 11  wherein the path generator is configured to form the stateful given path by accessing one or more of utilization and cost information relating to a plurality of nodes in the routing database. 
     
     
         14 . The routing device as defined by  claim 11  wherein the stateful given path comprises an ordered plurality of given nodes between the originating node and the destination node, the ordered plurality of given nodes having a first node next to the originating node, the first node being the routing device. 
     
     
         15 . The routing device as defined by  claim 11  wherein the router is configured to receive a plurality of additional packets for the given session from the originating node, and forward the plurality of additional packets for the given session toward the destination node along the stateful given path. 
     
     
         16 . The routing device as defined by  claim 11  wherein the information relating to the ordered plurality of nodes in each of the sessions includes utilization of the stateful session paths and bandwidth of the stateful session paths. 
     
     
         17 . The routing device as defined by  claim 11  wherein the router is configured to receive a plurality of packets in a return session from the destination node, the packets in the return session being addressed toward the originating node, the router also configured to forward, through the electronic interface, substantially all of the packets in the return session toward the originating node along the stateful given path. 
     
     
         18 . The routing device as defined by  claim 11  wherein the destination node comprises an edge router for a data center network. 
     
     
         19 . The routing device as defined by  claim 11  wherein the stateful given path comprises an ordered plurality of given nodes between the originating node and the destination node, the ordered plurality of given nodes including the routing device and a next node next to and downstream of the routing device within the ordered plurality of given nodes, the router further being configured to address the lead packet to the next node so that a plurality of network devices receive the lead packet after it is forwarded through the electronic interface and before the next node receives the lead packet. 
     
     
         20 . A computer program product for use on a computer system for directing packets of a session between an originating node and a destination node in an IP network, the computer program product comprising a tangible, non-transient computer usable medium having computer readable program code thereon, the computer readable program code comprising:
 program code for an electronic interface of a routing device to obtain a lead packet of a plurality of packets in a given session, the electronic interface being connectable with the IP network;   program code for maintaining, in a routing database, state information relating to a plurality of sessions in the IP network, each session including a single stateful session path formed by an ordered plurality of nodes in the IP network, the state information including information relating to the ordered plurality of nodes in each of the sessions;   program code for accessing the routing database to determine the state of a plurality of the sessions;   program code for forming a stateful given path for packets of the given session across the IP network between the routing device and destination node as a function of the state information in the routing database;   program code for storing state information relating to the stateful given path and the given session in the routing database; and   program code for forwarding the lead packet via the electronic interface toward the destination along the stateful given path.