Load balancing routing algorithm based upon predefined criteria

• US 6,650,621 B1
• Filed: 10/05/1999
• Issued: 11/18/2003
• Est. Priority Date: 06/28/1999
• Status: Expired due to Term

• Current Assignee: Forcepoint LLC
• Original Assignee: Stonesoft Oy (Rtx Corporation)
• Inventors: Maki-Kullas, Jukka
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): HYUN, SOON D
• Application Number:
  US09/412,867
• Time in Patent Office: 1,505 Days
• Field of Search: 370/400, 370/389, 370/392, 370/252, 370/401, 370/465, 370/254, 370/255, 370/351, 370/238, 370/238.1, 370/237, 370/229, 370/230, 370/235, 370/236.1, 709/102, 709/104, 709/105, 709/236
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/121 by minimising delays
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/243 using M+N parallel active paths
• CPC Class Codes: H04L 45/80 Ingress point selection by the source endpoint, e.g. selection of ISP or POP

Abstract

The invention relates to distribution of IP traffic between more than one route between a node and an IP network. The invention is concerned with a new method for distribution of connections between a plurality of possible routes for transmission of IP packet traffic between a source node and end nodes, each of the routes being associated with a plurality of IP addresse. According to the invention, a route is selected for a new connection to be established between the source node and an end node for transmission of packet traffic, the selected route is taken into use by translating source IP addresses of packets transmitted from the source node to said end node to an IP address associated with the selected route, and said selection of a route is performed on the basis of predefined criteria. Preferably, the selection of the route is performed on the basis of round trip times measured by a new method using packet replication.

Claims

1. Method for distribution of connections between a plurality of possible routes for transmission of IP packet traffic between a source node and end nodes, each of the routes being associated with a plurality of IP addresses, wherein

a route is selected for a new connection to be established between the source node and an end node for transmission of packet traffic,

the selected route is taken into use by translating source IP addresses of packets transmitted from the source node to said end node to an IP address associated with the selected route, and

said selection of a route is performed on the basis of predefined criteria so that the route having fastest response time is selected as the route to be used.

2. Method according to claim 1, wherein

the source node is connected to a first IP network,

said end node is connected to a second IP network,

said first and second networks are connected via a plurality of paths, and

each path of said plurality of paths corresponds to one route of the plurality of possible routes.

10. A method according to claim 1, wherein said IP protocol is IP version 4 protocol.

11. A method according to claim 1, wherein said IP protocol is IP version 6 protocol.

18. Method according to claim 1, wherein said selection of a route includes the steps:

(i) replicating a connection setup packet through each of said plurality of possible routes to be tested,

(ii) receiving a reply packet relating to the connection setup packet through at least one of the plurality of possible routes to be tested,

(iii) selecting the one of the plurality of routes having the fastest reply time to the connection setup packet.

3. A Method for distribution of connections between a plurality of possible routes for transmission of IP packet traffic between a source node and end nodes, each of the routes being associated with a plurality of IP addresses, the connections using the Internet Protocol (IP) and at least one second protocol, the method comprising at least steps, in which

a route is selected for a new connection to be established between the source node and an end node for transmission of packet traffic,

the selected route is taken into use by translating source IP addresses of packets transmitted from the source node to said end node to an IP address associated with the selected route, and

said selection of a route including the steps

a first IP datagram comprising a setup message of a second protocol is created for initiating a new connection to an end node using said second protocol,

said first IP datagram is sent through a first route of the routes between the source node and said end node,

said first IP datagram is copied for creating a second IP datagram for sending through a second route of the routes between the source node and said end node,

the source IP address of said second IP datagram is translated to an IP address selected from the plurality of IP addresses associated with said second route,

said second IP datagram is transmitted via said second route to said end node,

first datagram comprising information of a predefined type is received from said end node via one of the routes, and

the route from which said first datagram comprising information of said predefined type is received is selected as the route to be used.

4. Method according to claim 3, wherein said selection of a route is performed to balance the load of new connections between the plurality of possible routes.

5. A method according to claim 3, wherein the method comprises a step, in which the source IP address of said first IP datagram is translated to an IP address selected from the plurality of IP addresses associated with said first route.

6. A method according to claim 3, wherein said first datagram comprising information of a predefined type is a first response datagram sent by said end node as a response to one of said first and second IP datagrams.

7. A method according to claim 3, wherein connection setup signalling according to said second protocol is continued via the selected route.

8. A method according to claim 3, wherein the method further comprises the steps:

after sending said first and second IP datagrams, connection setup signalling procedure is continued via said first and said second route, and said first datagram comprising information of a predefined type is a first IP datagram comprising payload data according to the second protocol sent by said end node.

9. A method according to claim 3, wherein said second protocol is the Transmission Control Protocol (TCP).

12. A method according to claim 3, wherein said second protocol is a protocol for carrying speech data.

13. System for distribution of connections between a plurality of possible routes for transmission of IP packet traffic between a source node and end nodes, each of the routes being associated with a plurality of IP addresses, comprising:

means for selecting a route for a new connection to be established between a source node and an end node for transmission of packet traffic,

means for translating source IP addresses of packets for transmission from said source node to said end node to an IP address associated with said selected route, said means for selecting a route being arranged to select a route on the basis of predefined criteria so that the route having fastest response time is selected as the route to be used.

14. System according to claim 13, characterized in that said means for selecting a route is arranged to perform the selection for balancing the load of new connections between the plurality of possible routes.

15. A System for distribution of connections between a plurality of possible routes for transmission of IP packet traffic between a source node and end nodes, each of the routes being associated with a plurality of IP addresses, the system comprising

means for selecting a route for a new connection to be established between the source node and an end node for transmission of packet traffic,

means for translating source IP addresses of packets for transmission from the source node to said end node to an IP address associated with the selected route, said means for selecting a route including

means for detecting an IP datagram destined to an end node comprising a setup message according to a second protocol,

means for sending said IP datagram to a first route of the plurality of routes for transmission to said end node,

means for copying said IP datagram for creating a second IP datagram for transmission to said end node via a second route of the plurality of routes,

means for translating the source IP address of said second IP datagram to an IP address belonging to the plurality of IP addresses associated with said second route, and

means for sending said second IP datagram to said second route for transmission to said end node.

16. A network element for distribution of connections between a plurality of possible routes for transmission of Internet Protocol (IP) packet traffic between a source node and end nodes, each of the routes being associated with a plurality of IP addresses, the network element comprises:

means for creating at least first and second datagrams, each constituting a setup message in a second protocol which runs over said IP protocol, said first and second datagrams being copies of each other and being attempts to establish a connection between said source node and said end node, said first datagram having a source IP address associated with a first route between said source node and said end node;

means for transmitting said first datagram via said first route;

means for translating said source IP address in said second datagram which was copied from said first datagram to an IP address associated with a second route between said source node and said end node;

means for transmitting said second datagram to said end node via said second route;

means for determining which of said first and second routes has the lowest load as judged by it having the fastest response time in transmitting back to said source node a datagram of a predetermined type transmitted from said end node;

means for selecting a route for subsequent transmissions between said source node and said end node on the basis of predefined criteria so that the route having fastest response time in transmitting said datagram of a predetermined type back to said source node is selected as the route to be used.

17. A network element for distribution of connections between a plurality of possible routes for transmission of IP packet traffic between a source node and end nodes, each of the routes being associated with a plurality of IP addresses, the system network element comprising:

means for selecting a route for a new connection to be established between the source node and an end node for transmission of packet traffic,

means for translating source IP addresses of packets for transmission from the source node to said end node to an IP address associated with the selected route, said means for selecting a route including

means for detecting an IP datagram destined to an end node comprising a setup message according to a second protocol,

means for sending said IP datagram to a first route of the plurality of routes for transmission to said end node,

means for copying said IP datagram for creating a second IP datagram for transmission to said end node via a second route of the plurality of routes,

means for translating the source IP address of said second IP datagram to an IP address belonging to the plurality of IP addresses associated with said second route, and

means for sending said second IP datagram to said second route for transmission to said end node; and

means for receiving a first-in-time reply datagram to said setup message sent via either said first route or said second route, and for selecting the route through said first-in-time reply datagram was received as the route to use for further transmissions between said source node and said end node.