Apparatus and method of selecting next hops for a session

• US 10,205,651 B2
• Filed: 05/13/2016
• Issued: 02/12/2019
• Est. Priority Date: 05/13/2016
• Status: Active Grant

• Current Assignee: 128 Technology, Inc. (Juniper Networks Incorporated)
• Original Assignee: 128 Technology, Inc. (Juniper Networks Incorporated)
• Inventors: Piecuch, Michael T.
• Primary Examiner(s): Pancholi, Rina C
• Application Number:
  US15/154,134
• Publication Number:
  US 20170331721A1
• Time in Patent Office: 1,005 Days
• CPC Class Codes: H04L 43/0882 Utilisation of link capacity
• CPC Class Codes: H04L 43/20 the monitoring system or the monitored elements being virtualised, abstracted or software-defined entities, e.g. SDN or NFV
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 47/125 by balancing the load, e.g. traffic engineering
• CPC Class Codes: H04L 67/142 Managing session states for stateless protocols; Signalling session states; State transitions; Keeping-state mechanisms

Abstract

A method establishes a session across a plurality of nodes in a computer network using a load balancing technique. The plurality of nodes includes a current node and a plurality of next nodes, and each next hop node is coupled with the current node via a link. To determine the next hop node from the current node, the method determines the residual capacity of the links between the current node and the next nodes, and generates a random number. Next, the method selects one of the next nodes as a function of the random number and the respective residual capacities of the links between the current node and the next nodes. After selecting the one next hop node, the method directs packets for the session from the current node to the one selected next hop node.

Claims

1. A method of establishing a session across a plurality of nodes in a computer network, the plurality of nodes including a current node and a plurality of next nodes, each one of the plurality of next nodes being coupled with the current node via a link, the method comprising:

determining residual capacities of the links between the current node and the plurality of next nodes, wherein residual capacity corresponds to amount of network flow capacity remaining in a respective link, at a given point in time, not in use or otherwise reserved;

determining a sum of the residual capacities of the links between the current node and the plurality of next nodes;

generating a random number from a range of numbers, the range of numbers being a function of the sum of the residual capacities of the links between the current node and the plurality of next nodes;

selecting one of the plurality of next nodes as a function of the random number and the residual capacities of the links between the current node and the plurality of next nodes, the selected next node being a next hop node; and

directing packets for the session from the current node to the next hop node.

2. The method as defined by claim 1 wherein each one of the plurality of next nodes is assigned a set of zero or more unique node values, each unique node value being a function of at least one number from the range of numbers, the total number of unique node values in the sets being a function of the residual capacities in the links between the current node and the plurality of next nodes,

further wherein selecting comprises selecting the next hop node as a function of the unique node values of the plurality of next nodes.

3. The method as defined by claim 1 further comprising determining cost of the plurality of links between the current node and the plurality of next nodes, further wherein selecting comprises selecting one of the plurality of next nodes as a function of the cost.

4. The method as defined by claim 1 wherein determining the residual capacities comprises using a maximum flow algorithm that determines the residual capacities of the links between the current node and the plurality of next nodes.

5. The method as defined by claim 1 wherein selecting comprises applying a weight to each one of the plurality of next nodes as a function of the residual capacities, and selecting one of the plurality of next nodes as a function of the weights of each one of the plurality of next nodes.

6. The method as defined by claim 1 wherein the plurality of nodes comprise a router.

7. The method as defined by claim 1 wherein determining the residual capacities comprises forming a network graph wherein the current node and the plurality of next nodes form vertices and the links comprise edges.

8. The method as defined by claim 1 wherein the next hop node is a new current node, the method repeating the acts of determining, generating, and selecting for a plurality of new current nodes in the computer network to a destination node, the method forming a network path through the computer network to the destination node for a given session, the method forwarding packets of the given session along the selected nodes to the destination node.

9. The method as defined by claim 1 wherein the current node receives a lead packet of a plurality of packets in the session, the method modifying the lead packet to identify the current node, and forwarding the lead packet toward a destination node, via the next hop node, to establish a stateful session.

10. The method as defined by claim 9 further wherein the current node receives a backward message from the next hop node, the current node storing information relating to the next hop node in memory to maintain state information for the stateful session.

11. The method as defined by claim 9 wherein the stateful session comprises packets traversing from the current node to the designation node via the next hop node, and packets traversing from the destination node to the current node via the next hop node.

12. An apparatus for establishing a session across a plurality of nodes in a computer network, the plurality of nodes including a current node and a plurality of next nodes, each one of the plurality of next nodes being coupled with the current node via a link, the apparatus comprising:

a random number generator configured to generate a random number;

a capacity calculator operatively coupled with the random number generator, the capacity calculator being configured to determine residual capacities of the links between the current node and the plurality of next nodes, wherein residual capacity corresponds to amount of network flow capacity remaining in a respective link, at a given point in time, not in use or otherwise reserved;

the random number generator is configured to generate the random number from a range of numbers, the range of numbers being a function of a sum of the residual capacities of the links between the current node and the plurality of next nodes;

a link selector operatively coupled with the random number generator, the link selector being configured to select one of the plurality of next nodes as a function of the random number and the residual capacities of the links between the current node and the plurality of next nodes, the one selected next node being a next hop node; and

a router configured to direct packets for the session from the current node to the next hop node.

13. The apparatus as defined by claim 12 further comprising a routing database, the link selector associating, in the routing database, both the next hop node and the current node with the session.

14. The apparatus as defined by claim 12 the link selector is configured to assign each one of the plurality of next nodes a set of zero or more unique node values, each unique node value being a function of at least one number from the range of numbers, the total number of unique node values in the sets being a function of the residual capacities in the links between the current node and the next nodes,

further wherein the link selector also is configured to select the next hop node as a function of the unique node values of the plurality of next nodes.

15. The apparatus as defined by claim 12 wherein the capacity calculator is configured to use a maximum flow algorithm that determines the residual capacities of the links between the current node and the plurality of next nodes.

16. The apparatus as defined by claim 12 wherein the current node is configured to receive a lead packet of a plurality of packets in the session, the apparatus further comprising:

a lead packet modifier configured to modify the lead packet to identify the current node; and

wherein the router is configured to forward the modified lead packet toward a destination node, via the next hop node, to establish a stateful session.

17. The apparatus as defined by claim 16 wherein the stateful session comprises packets traversing from the current node to the designation node via the next hop node, and packets traversing from the destination node to the current node via the next hop node.

18. A computer program product for use on a computer system for establishing a session across a plurality of nodes in a computer network, the plurality of nodes including a current node and a plurality of next nodes, each one of the plurality of next nodes being coupled with the current node via a link, 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 determining residual capacities of the links between the current node and the plurality of next nodes, wherein residual capacity corresponds to amount of network flow capacity remaining in a respective link, at a given point in time, not in use or otherwise reserved;

program code for determining a sum of the residual capacities of the links between the current node and the plurality of next nodes; and

program code for generating a random number from a range of numbers, the range of numbers being a function of the sum of the residual capacities of the links between the current node and the plurality of next nodes;

program code for selecting one of the plurality of next nodes as a function of the random number and the residual capacities of the links between the current node and the plurality of next nodes, the selected next node being a next hop node; and

program code for directing packets for the session from the current node to the next hop node.

19. The computer program product as defined by claim 18 wherein each one of the plurality of next nodes is assigned a set of zero or more unique node values, each unique node value being a function of at least one number from the range of numbers, the total number of unique node values in the sets being a function of the residual capacities in the links between the current node and the plurality of next nodes,

further wherein the program code for selecting comprises program code for selecting the next hop node as a function of the unique node values of the plurality of next nodes.

20. The computer program product as defined by claim 18 further comprising program code for determining cost of the plurality of links between the current node and the plurality of next nodes, further wherein the program code for selecting comprises program code for selecting the next hop node as a function of the cost.

21. The computer program product as defined by claim 18 wherein the program code for determining the residual capacities comprises program code for executing a maximum flow algorithm that determines the residual capacities of the links between the current node and the plurality of next nodes.

22. The computer program product as defined by claim 18 wherein the program code for determining the residual capacities comprises program code for forming a network graph wherein the current node and the plurality of next nodes form vertices and the links comprise edges.

23. The computer program product as defined by claim 18 wherein the one selected node is a new current node, the computer program product comprises program code for repeating execution of the program code for determining, program code for generating, and program code for selecting for a plurality of new current nodes in the computer network to a destination node, the computer program product including program code for forming a network path through the computer network to the destination node for a given session, the computer program product including program code for forwarding packets of the given session along the selected nodes to the destination node.

24. The computer program product as defined by claim 18 wherein the current node receives a lead packet of a plurality of packets in the session, the computer program product comprising program code for modifying the lead packet to identify the current node, and program code for forwarding the lead packet toward a destination node, via the next hop node, to establish a stateful session.