Patent Document

FIELD OF INVENTION 
     The invention relates generally to the field of communications. More specifically, but not by way of limitation, the invention relates to a system and method for load balancing a Session Initiation Protocol (SIP) network for applications such as Voice Over Internet Protocol (VoIP) communications and Instant Messaging (IM). 
     BACKGROUND 
     Systems and methods are generally known for effecting signaling (control) data on a communications network.  FIG. 1  is a block diagram of a functional architecture of a communications network, according to the prior art. As shown in  FIG. 1 , a SIP server  104  provides communications services such as routing SIP signaling messages between a source device  102  and a destination device  106 . Source device  102  and/or destination device  106  may be, for example, a SIP-enabled telephone, a SIP PC (Personal Computer) client, a SIP-enabled gateway, or other device configured to originate or terminate a SIP session.  FIG. 2  is a message sequence diagram of communications with a SIP server, according to the prior art. In particular,  FIG. 2  illustrates signaling between the functional blocks in  FIG. 1  using request and response message types: Invite and Bye are request messages; Ringing and OK are response messages. 
     In typical signaling applications, multiple SIP servers may be used (instead of a single SIP server  104 ) where the communications system also includes multiple sources and/or destination devices. But systems with multiple SIP servers have many disadvantages. For example, known systems may not be able to establish, modify, or terminate at least some SIP sessions where one or more SIP servers have failed. Moreover, requests may be received at SIP servers according to round-robin assignments or theoretical server capacity, resulting in inefficient processing of SIP messages. What is needed is a system and method for performance-based load balancing of SIP servers that can also adapt to one or more failed SIP servers in the system. 
     SUMMARY OF THE INVENTION 
     The invention relates to a system and method for load-balancing multiple servers in a communications network. SIP messages are forwarded to one of multiple SIP servers according to a performance score that is calculated from measured performance data from each of the multiple servers. 
     Embodiments of the invention provide a method for load-balancing a Session Initiation Protocol (SIP) network, including: receiving a SIP request from a source device; selecting one of a plurality of SIP servers based on a plurality of performance scores, each of the plurality of performance scores associated with a corresponding one of the plurality of SIP servers; and forwarding the SIP request to the selected SIP server. 
     Embodiments of the invention provide a method for polling a SIP server for performance data, including: receiving a data request for the performance data in a performance server; creating a persistent performance client in the performance server; opening a connection to an agent running on the SIP server; and issuing a request from the persistent performance client to the agent. 
     Embodiments of the invention provide a method responsive to a data request, including: creating a first controller, the first controller being configured to gather and cache performance data; and creating a server socket, the server socket being configured to determine whether a connection request has been received, the server socket being further configured to transmit the performance data. 
     Embodiments of the invention provide a method for load-balancing a Session Initiation Protocol (SIP) network, including: receiving a SIP request; generating a routing request based on the SIP request; generating a performance score request for each of a plurality of SIP servers based on the routing request; generating a performance data query to each of the plurality of SIP servers based on the performance score request; and receiving the performance data query in an agent in each of the plurality of SIP servers. 
     Embodiments of the invention provide a communication system, including: an interface to a source device; a load balancer coupled to the interface; a plurality of Session Initiation Server (SIP) servers coupled to the load balancer; and a performance server coupled to the load balancer and the plurality of SIP servers, the performance server configured to collect performance data from the plurality of SIP servers, the load balancer configured to calculate a performance score for each of the plurality of SIP servers based on the performance data, the load balancer further configured to direct a SIP request received from the first interface to a selected one of the plurality of SIP servers based on the performance score for each of the plurality of SIP servers. 
     Advantageously, the disclosed system and method decreases signaling latency, improving overall communications speed. Moreover, where performance data indicates that a SIP server has failed, the performance score for the failed SIP server is zero, and the load balancer will not forward SIP messages to the failed SIP server. So system uptime is also improved. 
     The features and advantages of the invention will become apparent from the following drawings and detailed description. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       Embodiments of the invention are described with reference to the following drawings, wherein: 
         FIG. 1  is a block diagram of a functional architecture of a communications network, according to the prior art; 
         FIG. 2  is a message sequence diagram of communications with a SIP server, according to the prior art; 
         FIG. 3  is a block diagram of a functional architecture of a communications network, according to an embodiment of the invention; 
         FIG. 4  is a block diagram of a functional architecture of the SIP load balancer in  FIG. 3 , according to an embodiment of the invention; 
         FIG. 5  is a flow diagram of a routing/forwarding process, according to an embodiment of the invention; 
         FIG. 6  is a flow diagram of a server selection process, according to an embodiment of the invention; 
         FIG. 7  is a graphical illustration of a server selection plot, according to an embodiment of the invention; 
         FIG. 8  is a flow diagram of a process for calculating server load, according to an embodiment of the invention; 
         FIG. 9  is a graphical illustration of server load scores, according to an embodiment of the invention; 
         FIG. 10  is a flow diagram of a server performance query process, according to an embodiment of the invention; 
         FIG. 11  is a block diagram of a functional architecture for collecting performance data, according to an embodiment of the invention; 
         FIG. 12  is a flow diagram of a polling process from the perspective of a performance server, according to an embodiment of the invention; 
         FIG. 13  is a flow diagram for a polling process from the perspective of a performance agent on a SIP server, according to an embodiment of the invention; 
         FIG. 14  is a block diagram of a test bed functional architecture, according to an embodiment of the invention; and 
         FIG. 15  is an illustration of a test results table, according to an embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     This section provides a top-level functional architecture, exemplary selection, routing and forwarding processes, a process for calculating a performance score, a process for collecting performance data, and a summary of empirical analysis. Sub-headings are used below for organizational convenience. The disclosure of any particular feature is not necessarily limited to any particular section, however. 
     Top Level Functional Architecture 
       FIG. 3  is a block diagram of a functional architecture of a communications network, according to an embodiment of the invention. As shown in  FIG. 4 , a functional architecture includes source device  102 , load balancer  302 , performance server  304 , SIP servers  306 A,  306 B,  306 C, and  306 D, a network  308 , and a destination device  106 . The load balancer  302  is coupled to the source device  102 , the performance server  304 , and each of the SIP servers  306 A,  306 B,  306 C, and  306 D. The performance server  405  is also coupled to each of the SIP servers  306 A,  306 B,  306 C, and  306 D. Further, network  308  is coupled to each of the SIP servers  306 A,  306 B,  306 C, and  306 D and the destination device  106 . 
     The load balancer  302 , performance server  304 , SIP servers  306 A,  306 B,  306 C, and  306 D may each include a processor, each of the processors being configured to read and execute instructions from a processor-readable storage medium. In one variation, the load balancer  302  and the performance server  304  share a processor. The storage medium may be or include, for instance, a hard drive, Random Access Memory (RAM), or a Computer Disc (CD) Read Only memory (ROM). The load balancer  302 , performance server  304 , SIP servers  306 A,  306 B,  306 C, and  306 D may each be configured, for example, with a server operating system, examples of which include Linux™ or Windows™ server operating systems. SIP servers  306 A,  306 B,  306 C and  306 D may each be configured as SIP proxy servers. 
     The load balancer  302  is configured to receive a SIP message from source device  102 . Informed by the performance server  304 , the load balancer  302  is configured to forward the SIP message from the source device  102  to a selected one of the SIP servers  306 A,  306 B,  306 C, and  306 D. In turn, the selected SIP server establishes a session between the source device  102  and the destination device  106 . 
     Variations of the functional architecture illustrated in  FIG. 3  are also contemplated. For example, although four SIP servers are illustrated in  FIG. 3 , a functional architecture may have two or more SIP servers. Further, in a general case, a functional architecture may include multiple source devices and/or multiple destination devices. Moreover, switches or servers configured for H.323 or other IP telephony or other communications protocol could be used in the alternative to, or in combination with, the illustrated SIP servers  306 A,  306 B,  306 C, and  306 D, according to design choice. 
       FIG. 4  is a block diagram of a functional architecture of the SIP load balancer in  FIG. 3 , according to an embodiment of the invention. As shown therein, an exemplary load balancer  302  includes SIP forwarding module  402 , SIP routing module  404 , server load computation module  406 , and server performance query module  408 . The SIP routing module  404  is coupled to the SIP forwarding module  402  and the server load computation module  406 . The server load computation module  406  is coupled to the SIP routing module  404  and the server performance query module  408 . The server performance query module  408  is coupled to the server load computation module  406 . In the illustrated embodiment, each of the couplings described above are two-way couplings. 
     The SIP forwarding module  402  is configured to receive a SIP request from the source device  102  and send an inquiry to the SIP routing module  404  to determine a SIP server recipient of the SIP message. Once the SIP forwarding module  402  receives the SIP server selection from the SIP routing module  404 , the SIP forwarding module  402  is configured to forward the SIP request to the selected SIP server (e.g., one of SIP servers  306 A,  306 B,  306 C, and  306 D). 
     In response to a routing inquiry from the SIP forwarding module  402 , the SIP routing module  404  is configured to request performance scores from the server load computation module  406 , to select a SIP server (e.g., one of SIP servers  306 A,  306 B,  306 C, and  306 D) based on the performance scores, and forward the selection to the SIP forwarding module  402 . 
     The server load computation module  406  is configured to receive a request for performance scores from the SIP routing module  404 , request performance data from the server performance query module  408 , calculate a performance score for each of the SIP servers  306 A,  306 B,  306 C, and  306 D based on the performance data, and provide the performance scores to the SIP routing module  404 . 
     The server performance query module  408  is configured to receive a request for performance data from the server load computation module  406 , solicit performance data from the performance server  304 , and forward the performance data to the server load computation module  406 . 
     Variations to the functional architecture illustrated in  FIG. 4  are possible. For example, any of the functional capability illustrated therein and described above may be combined in functional groupings different from that illustrated in  FIG. 4  and described above. 
     In operation, data may be cached or otherwise stored at various locations of the functional architecture. For instance, in response to a request for performance scores, server load computation module  406  may provide most recent performance scores to the SIP routing module  404  without having to first initiate a request for server performance data from the server performance query module  408 . Likewise, in response to a request from the server load computation module  406 , the server performance query module  408  may provide most recent server performance data to the server load computation module  406  prior to sending a request to the performance server  304 . 
     Embodiments of processes performed by the functional components of the load balancer  302  are further described with reference to  FIGS. 5-10  below. 
     Selection, Routing, and Forwarding Processes 
       FIG. 5  is a flow diagram of a routing/forwarding process, according to an embodiment of the invention. As shown therein, the process begins by receiving a SIP request in step  502 . The process then advances to conditional step  504  to determine whether the received request is a registration request. Where the result of conditional step  504  is in the affirmative, the process advances to step  506  to route the SIP request to all SIP servers. In an alternative embodiment, if the result of conditional step  504  is in the affirmative, the process routes the SIP request to a registrar server (step not shown). 
     On the other hand, where the result of conditional step  504  is in the negative, the process is promoted to step  508  to extract a session signature from the SIP request in step  508 . The execution of step  508  may vary according to proprietary SIP implementation schemes. Then, in conditional step  510 , the process determines whether a SIP session exists (e.g., based on the session signature). If it is determined in conditional step  510  that a SIP session exists (e.g., the SIP request is associated with an existing SIP session), then the process advances to step  512  to forward the SIP request to the (pre)selected SIP server associated with the existing SIP session. Accordingly, a SIP request associated with an active session is simply routed to the appropriate SIP server. 
     If it is determined in conditional step  510  that a SIP session does not exist (e.g., the request is associated with a new SIP session), then the process selects a SIP server in step  514  and advances to conditional step  516  to determine whether the selected SIP server has been found. Where the result of conditional step  516  is in the negative, the process advances to step  518  to drop (e.g., terminate processing of) the SIP request. Where the result of conditional step  516  is in the affirmative, the process advances to step  512  to forward the SIP request to the (newly) selected SIP server. Accordingly, a SIP request associated with a new session requires selection of a SIP server in step  514  before being forwarded to the selected SIP server in step  512 . The load balancer  302  preferably maintains a list of active SIP sessions to execute conditional step  510  described above. 
     Variations to the process illustrated in  FIG. 5  are contemplated. For example, conditional step  504  and associated step  506  are optional. In addition, conditional step  514  may be considered a portion of selection step  516 . 
       FIG. 6  is a flow diagram of a server selection process, according to an embodiment of the invention. In other words,  FIG. 6  is one embodiment of selection step  514 . As shown therein, the process begins in step  602 , then advances to step  604  to generate a random integer X, where 0&lt;X≦ΣS k . ΣS k  is the sum of performance scores for all SIP servers (shown graphically on integer axis  702  of  FIG. 7 ). 
     Next, j is set equal to zero in step  606 , and conditional step  608  tests whether (S 0 + . . . +S j−1 )&lt;X≦(S 0 + . . . S j ). S 0 , S j−1 , and S j  are the performance scores for servers  0  (S 0 ), j−1, and j, respectively. If the result of conditional step  608  is negative, then the value of j is incremented by 1 in step  610 , and the process returns to conditional step  608 . If the result of conditional step  608  is positive, then the process selects server j in step  612 . 
     Accordingly, the server selection process  514  illustrated in  FIG. 6  tests one or more servers in steps  606 ,  608 , and  610  to associate random integer X with a particular server j. The exemplary process illustrated in  FIG. 6  can be further understood with reference to the server selection plot illustrated in  FIG. 7 . 
       FIG. 7  is a graphical illustration of a server selection plot, according to an embodiment of the invention. As shown in  FIG. 7 , data for each of five servers, S 0 , S 1 , S 2 , S 3 , and S 4  are plotted on integer axis  702  and score axis  704 . The integer axis  702  is divided into N partitions sequentially assigned to servers S 0 , S 1 , S 2 , S 3 , and S 4 . For each server, the size of the partition along integer axis  702  is proportional to the performance score. 
       FIG. 7  further illustrates the position on the integer axis  702  for a random integer X generated in step  604 . It should be apparent that the larger the performance score for a server, the larger the partition size, and the more likely that the random integer X will be associated with a server having a relatively larger performance score. It would be determined in step  608  (with reference to integer axis  702 ) that (S 0 +S 1 )&lt;X≦(S 0 +S 1 +S 2 ). Thus, server S 2  would be selected. 
     The performance score S 3  associated with server S 3  is represented by a single point on the integer axis  702 . Note that the selection criteria in conditional step  608  prevents selection of a server having a performance score of zero. For example, if random integer X were equal to S 0 +S 1 +S 2 , the point where it is indicated in  FIG. 7  that the performance score for server S 3  is equal to zero, server S 2  would be selected by the process depicted in  FIG. 6 . 
     As described above, calculation of a performance score for each of the SIP servers is a prerequisite to selecting a SIP server in step  514 . 
     Calculating a Performance Score 
       FIG. 8  is a flow diagram of a process for calculating server load (or performance score), according to an embodiment of the invention. As shown therein, the process begins in step  802 , then advances to step  804  to read each of several parameters. For example, in step  804 , the process reads C i , which is the Computer Processing Unit (CPU) usage, expressed as a percentage, for the i th  SIP server. The process also reads C max , which is the maximum CPU usage, also expressed as a percentage. Also in step  804 , the process may read M i , which is the amount of available memory of the i th  SIP server, expressed as a percentage of total memory. Further, in step  804 , the process reads M min , which is the minimum required memory (again, expressed as a percentage of total memory). The process may also read or calculate ΣM k , which is the sum of the available memory for all SIP servers with a non-zero performance score. Finally, in step  804 , the process may read W 0  and W 1 , which are the predetermined weight of the CPU usage percentage parameter and the predetermined weight of the memory availability parameter, respectively. In one embodiment, C max  is 95%, M min  is 10 Mbytes, and W 0  and W 1  are both set equal to 1. 
     After reading the parameters in step  804 , the process advances to conditional step  806  where it is determined whether C i  is less than or equal to C max . Where the result of conditional step  806  is in the affirmative, the process advances to step  810  to determine whether M i  is greater or equal to M min . Where the result of either conditional step  806  or conditional step  810  are in the negative, the process terminates in step  808 , where a performance score S i  is set equal to zero. Where the result of conditional step  810  is in the affirmative, the process advances to step  812  to calculate the performance score S i  given by: S i =100(W 0 (1−C i )+W i M i /ΣM k )/W 0 +W 1 ). Advantageously, scoring sensitivity can be adjusted by varying the predetermined weights W 0  and W 1  according to application requirements. 
       FIG. 9  is a graphical illustration of server performance scores  902 , according to an embodiment of the invention. As shown, the highest performance score, 100%, is the case where CPU usage (C i ) is 0%, and memory availability (M i ) is 100%. As CPU and/or memory resources become less available, the performance score drops. Where the CPU usage (C i ) is 100%, and/or where the memory availability (M i ) is 0%, the performance score is equal to zero. In the illustrated embodiment, W 0  and W 1  are both set equal to 1. In alternative embodiments, the scoring solution can be made more sensitive to either memory availability or CPU utilization by changing the value of W 0  and/or W 1  either off-line or in-situ. 
     In alternative embodiments of the invention, the above calculation may be performed without a CPU usage parameter, or without a memory availability parameter. Moreover, in other embodiments, performance scores may be calculated based on network utilization, call volume, failure statistics (such as indications of server down status, or abnormal SIP session terminations), and/or other factors either separately or combined with CPU usage and/or memory availability so that multiple SIP servers can be load balanced based on one or more performance metrics, and/or so that fault tolerance can be provided to a SIP-based application. 
     Collecting Performance Data 
       FIG. 10  is a flow diagram of a server performance query process, according to an embodiment of the invention. As shown in  FIG. 10 , the process begins in step  1002 , and then advances to step  1004  to set a parameter N equal to 1. Next, the process advances to step  1006  to poll a server PSN (the Nth SIP server). Then, the process advances to conditional step  1008  to determine whether the data being polled in step  1006  has been received. Where the result of conditional step  1008  is in the affirmative, the process advances to step  1012  to determine whether the query process of  FIG. 10  is completed. If the result of conditional step  1012  is in the affirmative, the process terminates in step  1016 . 
     Where the result of conditional step  1008  is in the negative, the process associates PSN with a down condition, and the process continues at conditional step  1012 . Where the result of conditional step  1012  is in the negative, the process advances to step  1014  where the server number is incremented by a 1 and the process returns to polling step  1006 . 
     Accordingly, the process illustrated in  FIG. 10  can be executed by the server performance query module  408  to collect server performance data for each of N SIP servers.  FIGS. 11-13  illustrate one embodiment for retrieving the performance data being polled in step  1006 . 
       FIG. 11  is a block diagram of a functional architecture for collecting performance data, according to an embodiment of the invention. As shown in  FIG. 11 , performance server  304  is coupled to performance agent  1102  in SIP server  306 A and to performance agent  1104  in SIP server  306 B. 
       FIG. 12  is a flow diagram of a polling process from the perspective of a performance server, according to an embodiment of the invention. As shown in  FIG. 12 , the process begins in step  1202  where performance server  304  receives a SIP request from load balancer  302  for a specific SIP server (e.g., SIP server  306 A or SIP server  306 B) or other node. Next, the process advances to step  1204  where the performance server  304  creates a persistent performance client (PPC) for the specified node. Next, the process advances to step  1206  where the PPC opens a connection to an agent (e.g., performance agent  1102  or performance agent  1104 ) running on the specified node. Then, in step  1208 , the PPC issues a “get data” request to the agent. Next, in step  1210 , the PPC receives and processes a reply from the agent. Then, in step  1212 , the performance server  304  sends a performance statistics to the load balancer  302 . Finally, in step  1214  the performance server  304  caches the PPC. 
     Thus, in one embodiment of the invention, performance data is collected by one or more performance servers using agents that are embedded in each of the SIP servers. 
       FIG. 13  is a flow diagram for a polling process from the perspective of a performance agent on a SIP server, according to an embodiment of the invention. As illustrated in  FIG. 13 , upon receipt of an initiation in step  1302 , the process launches three separate and distinct processes: a create collection controller step  1304 , a create server socket step  1312 , and a create notification controller step  1322 . 
     In response to the create collection controller step  1304 , the process advances to gather performance data in step  1306 , then cache performance data in  1308 . After step  1308 , the process may advance to a delay step  1310  before returning to step  1306  to gather additional performance data. 
     Subsequent to creating the server socket in step  1312 , the process advances to conditional step  1314  to determine whether a connection request has been received from the performance server  304 . Where the result of conditional step  1314  is in the affirmative, the process advances to step  1316  to create a new worker object. Next, in step  1318 , the process receives a “get data” request from the performance server  304 . Then, in step  1320 , the process returns the performance data (which was gathered in step  1306  and cached in step  1308 ) to the performance server  304 . Where the result of conditional step  1314  is in the negative, the process returns to conditional step  1314 . 
     In response to the creation of a notification controller in step  1322 , the process advances to step  1324  to read the performance data cached in step  1308 . Next, the process advances to conditional step  1326  to determine whether the performance data exceeds a predetermined threshold. For example, a CPU utilization threshold may be set at 85%, and a memory availability threshold may be set at 10 MB. Where the result of step  1326  is in the affirmative, the process issues a notification to the performance server  304  in step  1328 . Where the data does not exceed a pre-determined threshold in conditional step  1326 , the process returns to step  1324  to read performance data. 
     Variations to the process illustrated in  FIG. 13  are contemplated. For example, the implementation of delay step  1310  is optional. In addition, where the result of conditional step  1314  is in the negative, an optional delay step could be inserted before returning to conditional step  1314 . 
     Empirical Analysis 
     Embodiments of the invention described above were tested using the architecture illustrated in  FIG. 14 . The test produced the results summarized in  FIG. 15 . 
       FIG. 14  is a block diagram of a test bed functional architecture, according to an embodiment of the invention. As shown, SIP telephones  1402  and  1404 , softphones  1406  and  1408 , Load balancer  1412 , and SIP proxy servers  1414  and  1416  were coupled via link  1410 . SIP telephones  1402  and  1404  were 3Com® SIP telephones, and softphones  1406  and  1408  were implemented with Microsoft Windows® Messenger running on laptop personal computers. 
     To initialize the test, SIP telephones  1402  and  1404 , and softphones  1406  and  1408  were each registered with SIP proxy servers  1414  and  1416 . Server  1414  was assigned address 10.10.1.213, and server  1416  was assigned address 10.10.1.208. In addition, phones  1402 ,  1404 ,  1406 , and  1408  were each configured with load balancer  1412  address 10.10.1.221 as the outbound proxy address. A software tool was used to generate a controlled load on each of the SIP proxy servers  1414  and  1416 , while signaling messages were generated using phones  1402 ,  1404 ,  1406 , and  1408 . Log messages in load balancer  1412  were later reviewed to determine the number of times that each SIP proxy server  1414  and  1416  were selected. 
       FIG. 15  is an illustration of a test results table, according to an embodiment of the invention. As shown therein, the test included four scenarios,  1 - 4 . 
     In scenario  1 , server  1414  and server  1416  were lightly loaded; the result was that the performance scores were similar, and load balancer  1412  selected servers  1414  and  1416  more or less equally. In scenario  2 , server  1414  was heavily loaded, and server  1416  was lightly loaded; the result was that server  1416  was selected 17 out of 20 times. In scenario  3 , server  1414  was lightly loaded, and server  1416  was heavily loaded; the result was that server  1414  was selected 15 out of 20 times. In scenario  4 , server  1414  and server  1416  were both heavily loaded; the result was that servers  1414  and  1416  were selected more or less equally. 
     CONCLUSION 
     The invention described above thus overcomes the disadvantages of known systems and methods by balancing signaling load amongst multiple servers based on performance scores calculated from measured performance data. While this invention has been described in various explanatory embodiments, other embodiments and variations can be effected by a person of ordinary skill in the art without departing from the scope of the invention. For example, the systems and methods described herein could be applied to different signaling protocols or communication environments.

Technology Category: h