Network load balancing and overload control

• US 9,219,686 B2
• Filed: 03/31/2006
• Issued: 12/22/2015
• Est. Priority Date: 03/31/2006
• Status: Active Grant

• Current Assignee: WSOU Investments, LLC (WSOU Holdings, LLC)
• Original Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Inventors: Widjaja, Indra, Hilt, Volker
• Primary Examiner(s): Vostal, Ondrej C.
• Application Number:
  US11/395,455
• Publication Number:
  US 20070233896A1
• Time in Patent Office: 3,553 Days
• Field of Search: 709/223, 709/224, 709/204
• US Class Current: 1/1
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/12 Avoiding congestion; Recovering from congestion
• CPC Class Codes: H04L 47/122 by diverting traffic away from congested entities
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 65/1016 IP multimedia subsystem [IMS]
• CPC Class Codes: H04L 65/1104 Session initiation protocol [SIP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 69/40 for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection management of faults, events, alarms or notifications in data switching networks H04L41/06

Abstract

Load balancing and overload control techniques are disclosed for use in a SIP-based network or other type of network comprising a plurality of servers. In a load balancing technique, a first server receives feedback information from at least first and second downstream servers associated with respective first and second paths between the first server and a target server, the feedback information comprising congestion measures for the respective downstream servers. The first server dynamically adjusts a message routing process based on the received feedback information to compensate for imbalance among the congestion measures of the downstream servers. In an overload control technique, the first server utilizes feedback information received from at least one downstream server to generate a blocking message for delivery to a user agent.

Claims

1. A method of routing messages in a network comprising a plurality of servers, the method comprising the steps of:

receiving in a first server feedback information from downstream servers of the network, the downstream servers including at least first and second downstream servers associated with respective first and second paths between the first server and a target server, the feedback information comprising congestion measures for respective ones of the downstream servers; and

adjusting a message routing process in the first server based on the received feedback information to compensate for imbalance among the congestion measures;

wherein at least a given one of the downstream servers on one of the first and second paths receives a response from the target server to an invite request sent to the target server from the first server; and

wherein the given downstream server compares a congestion measure contained in the response from the target server with a congestion measure of the given downstream server and if the congestion measure of the given downstream server indicates a higher level of congestion than the congestion measure contained in the response from the target server, the given downstream server modifies the response from the target server to include the congestion measure of the given downstream server before forwarding the response upstream to the first server.

2. The method of claim 1 wherein the congestion measures comprise utilization measures for the respective downstream servers.

3. The method of claim 1 wherein the feedback information comprises a highest congestion measure among congestion measures of a plurality of servers in a same one of the first and second paths between the first server and the target server.

4. The method of claim 1 wherein one of the first and second downstream servers is the target server.

5. The method of claim 1 wherein at least one of the first and second downstream servers is a nearest neighboring server of the first server.

6. The method of claim 1 wherein the step of adjusting a message routing process in the first server based on the feedback information further comprises adjusting routing information which specifies relative percentages of a given set of messages to be routed on the first and second paths.

7. The method of claim 6 wherein the routing information comprises at least first and second routing probabilities for the respective first and second paths.

8. The method of claim 1 wherein the first server is an ingress/egress server of the network.

9. The method of claim 1 wherein at least one of the first and second downstream servers is an ingress/egress server of the network.

10. The method of claim 1 wherein at least one of the first and second downstream servers is a core server of the network.

11. The method of claim 1 wherein the messages comprise SIP messages.

12. An apparatus for use in routing messages in a network, comprising:

a first server of the network, configured to receive feedback information from downstream servers of the network, the downstream servers including at least first and second downstream servers associated with respective first and second paths between the first server and a target server, the feedback information comprising congestion measures for respective ones of the downstream servers;

wherein the first server is further configured to adjust a message routing process thereof based on the received feedback information to compensate for imbalance among the congestion measures;

wherein at least a given one of the downstream servers on one of the first and second paths receives a response from the target server to an invite request sent to the target server from the first server; and

wherein the given downstream server compares a congestion measure contained in the response from the target server with a congestion measure of the given downstream server and if the congestion measure of the given downstream server indicates a higher level of congestion than the congestion measure contained in the response from the target server, the given downstream server modifies the response from the target server to include the congestion measure of the given downstream server before forwarding the response upstream to the first server.

13. A method of routing messages in a network comprising a plurality of servers, the method comprising the steps of:

receiving in a first server feedback information from at least one downstream server of the network, the downstream server being associated with a path between the first server and a target server, the feedback information comprising a congestion measure and

generating a blocking message in the first server for delivery to a user agent based on the feedback information;

wherein the downstream server receives a response from the target server to an invite request sent to the target server from the first server; and

wherein the downstream server compares a congestion measure contained in the response from the target server with a congestion measure of the downstream server and if the congestion measure of the downstream server indicates a higher level of congestion than the congestion measure contained in the response from the target server, the downstream server modifies the response from the target server to include the congestion measure of the downstream server before forwarding the response upstream to the first server.

14. The method of claim 13 wherein the congestion measure comprises a utilization measure for the downstream server.

15. The method of claim 13 wherein the feedback information comprises a highest congestion measure among congestion measures of a plurality of servers in the path between the first server and the target server.

16. The method of claim 13 wherein the blocking message is generated based at least in part on a SIP 500 response message.

17. The method of claim 13 wherein the downstream server is the target server.

18. The method of claim 13 wherein the downstream server is a nearest neighboring server of the first server.

19. The method of claim 13 wherein the feedback information is transmitted from the downstream server to the first server in one or more SIP 100 response messages.

20. An apparatus for use in routing messages in a network, comprising:

a first server of the network, configured to receive feedback information from at least one downstream server of the network, the downstream server being associated with a path between the first server and a target server, the feedback information comprising a congestion measure;

wherein the first server is further configured to generate a blocking message for delivery to a user agent based on the feedback information;

wherein the downstream server receives a response from the target server to an invite request sent to the target server from the first server; and

wherein the downstream server compares a congestion measure contained in the response from the target server with a congestion measure of the downstream server and if the congestion measure of the downstream server indicates a higher level of congestion than the congestion measure contained in the response from the target server, the downstream server modifies the response from the target server to include the congestion measure of the downstream server before forwarding the response upstream to the first server.