Stateful load balancing in a stateless network

Patent metadata

Field	Value
Publication number	US-10277506-B2
Application number	US-201414562917-A
Country	US
Kind code	B2
Filing date	Dec 8, 2014
Priority date	Dec 8, 2014
Publication date	Apr 30, 2019
Grant date	Apr 30, 2019

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.

First claim

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 steps of:
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;
after obtaining the lead packet, assigning a session identifier to the given session, the session identifier being sufficient to enable the intermediate node to identify subsequent packets of the given session;
storing the session identifier in a routing database;
forwarding the lead packet toward the destination node, there being no predetermined path the lead packet will take between the originating node and the destination node;
after the lead packet has been forwarded by the intermediate node and obtained by another node, receiving an identification of the other node;
storing the identification of the other node in the routing database, in association with the session identifier, thereby adding the other node to a respective stateful ordered path of nodes between the source node and the destination node;
receiving a plurality of additional packets;
accessing the routing database to identify, among the plurality of additional packets, subsequent packets that originated at the originating node and are of the given session;
for each identified packet of the given session:
accessing the routing database to determine the other node associated with the given session; and
forwarding the packet toward the destination node, along the stateful ordered path, via the other node.

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 stateful ordered path 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 storing the identification of the other node in the routing database, in association with the session identifier, thereby adding the other node to the stateful ordered path of nodes between the source node and the destination node 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 ordered path comprises an ordered plurality of nodes between the originating node and the destination node, the ordered plurality of 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 wherein storing the identification of the other node in the routing database, in association with the session identifier, thereby adding the other node to the stateful ordered path of nodes between the source node and the destination node comprises determining utilization of a plurality of stateful ordered paths and bandwidth of the plurality of stateful ordered paths.

7. The packet routing method as defined by claim 1 further comprising the intermediate node:
receiving an identification of a previous node that forwarded the lead packet toward the intermediate node;
storing the identification of the previous node in the routing database, in association with the session identifier, thereby adding the previous node to the stateful ordered path of nodes;
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
for each packet of the plurality of packets:
accessing the routing database to determine the previous node associated with the return session; and
forwarding, through the electronic interface, all of the packets in the return session toward the originating node, along the stateful ordered path, via the previous node.

8. The packet routing method as defined by claim 1 wherein the destination node comprises an edge router for a data center network.

9. The packet routing method as defined by claim 1 wherein forwarding the lead packet comprises the intermediate node addressing the lead packet so that, between the lead packet being forwarded by the intermediate node and the lead packet being obtained by the other node, the lead packet traverses a series of network devices.

10. The packet routing method as defined by claim 1 further comprising:
a previous node, that forwarded the lead packet toward the intermediate node, modifying the lead packet to indicate the lead packet has been handled by an augmented IP router; and
the intermediate node using a modification of the lead packet to identify the lead packet as a lead packet and to trigger assigning the session identifier to the given session and storing the session identifier in the routing database.

11. The packet routing method as defined by claim 10 further comprising, before forwarding the lead packet to the destination node, restoring the lead packet to remove the modification of the lead packet.

12. The packet routing method as defined by claim 1 further comprising, after the other node obtains the lead packet, the other node sending a packet to the intermediate node, the packet containing the identification of the other node.

13. 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 lead packet identifier configured to, after the electronic interface receives the lead packet, assign a session identifier to the given session, the session identifier being sufficient to enable the routing device to identify subsequent packets of the given session;
a routing database, the routing database being configured to store information relating to a plurality of sessions in the IP network, the information about each session including a session identifier and an identification of a next node in the stateful ordered path;
a packet series manager configured to store the session identifier in the routing database;
a router configured to forward the lead packet via the electronic interface toward the destination node, there being no predetermined path the lead packet will take between the originating node and the destination node;
a downstream controller identifier configured to, after the lead packet has been forwarded by the router and obtained by another node, receive an identification of the other node and store the identification of the other node in the routing database, in association with the session identifier, thereby adding the other node to a respective stateful ordered path of nodes between the source node and the destination node; and
a subsequent packet modifier configured to receive, via the electronic interface, a plurality of additional packets, access the routing database to identify, among the plurality of additional packets, subsequent packets that are of the given session and that originated at the originating node and, for each identified packet of the given session:
access the routing database to determine the ot

Assignees

• 128 Tech Inc

Inventors

• Timmons Patrick
• Baj Michael
• Kaplan Hadriel
• Melampy Patrick
• Kumar Prashant
• Penfield Robert

Classifications

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title

• H04L45/38

  Flow based routing · CPC title

• H04L45/70 Primary

  Routing based on monitoring results · CPC title

• H04L45/54

  Organization of routing tables · CPC title