Hybrid and predictive admission control strategies for a server

BACKGROUND OF THE INVENTION

[0001] 1. Field of Invention

[0002] The present invention relates generally to the field of servers and pertains more particularly to a system for providing reliable client/server sessions by controlling the admission of arriving messages to a server.

[0003] 2. Discussion of the Prior Art

[0004] Servers are commonly employed for sharing of information among large numbers of computer systems or similar devices. A computer system or similar device that communicates with a server is usually referred to as a client of the server and the server is often part of a host system. A client and a host typically exchange messages via a communication network using a predetermined protocol. Such protocols are usually arranged in a client/host model in which a requesting client transfers a request message to a host and the host in turn takes an appropriate action depending on the content of the request message. Typically, the appropriate action for the request message includes the transfer of a response message to the requesting client.

[0005] Prior protocols typically do not allow for the establishment of a persistent session between the client and the host in the traditional sense in which a local terminal establishes a session on a computer system. Instead, any session-like information is usually implied in the content of the messages exchanged between the client and the host. Such a communication protocol may be referred to as a “stateless” protocol. Such stateless protocols include protocols associated with Internet communication including the Internet Protocol (IP), the User Datagram Protocol (UDP), the Simple Mail Transfer Protocol (SMTP), and the Hypertest Transfer Protocol (HTTP), as well as the Network File System (NFS) Protocol.

[0006] A client that accesses a host commonly engages in an extended transaction with the host. Such an extended transaction typically involves the exchange of multiple messages between the client and the host. For example, an NFS client typically issues multiple request messages to an NFS server while retrieving a file from the NFS server. Similarly, an HTTP client typically issues multiple request messages to an HTTP server while browsing through web pages contained on the HTTP server. Such transactions that involve the exchange of multiple messages between a client and a server are hereinafter referred to as sessions.

[0007] Servers commonly have a large pool of potential clients which may issue request messages. For example, an HTTP server connected to the world-wide-web has potentially millions of clients from which it may receive request messages. Prior servers that are adapted for stateless protocols typically respond to each request message in the order in which it is received, that is, on a first-come-first-served basis regardless of the source of the request message.

[0008] In the present context, the term “quality of service” refers both a host's ability to provide quick response to a message and to complete an entire session. As a particular host becomes more popular, and due to that popularity receives more messages, the host's processing resources can become stretched. For example, due to heavy traffic, a host may not be able to respond to a message at all, or the host may not provide a timely response which can cause a client to “time-out” and generate an error. Poor quality of service can have significant results, as users may become frustrated and simply give up trying to reach a particular host, or the sponsor of the host may lose sales or fail to communicate needed information to any or all clients.

[0009] Two techniques are generally used to alleviate quality of service problems. First, more processing capacity can be added to the host, typically by either replacing the host with another, more powerful computer, or by providing multiple computers in parallel and delegating new messages to different ones of the multiple computers. While this first technique presents an effective way of reducing some quality of service problems, it is not always practical. For example, sometimes, due to inadequate planning, budgetary constraints or space constraints, additional processing capacity simply cannot be added. Other times, if demand for a host is not properly forecast, there may be a long lead time before additional processing capacity can be purchased and implemented.

[0010] A second technique calls for applying “admission control,” where only a certain set number of client messages are processed (“admitted”) and the remainder are refused. Of the messages which are in fact admitted, all are ideally handled in an expedient manner without degradation of quality of service as to those admitted messages. An advantage of this technique is that admission control can be implemented in software, thus facilitating quick, inexpensive use with little advance notice. Unfortunately, typical admission control mechanisms operate by admitting messages on a message-by-message basis, and so, these typical admission control techniques do not provide an adequate solution for multiple-message sessions. Also, the messages which are not admitted to the host are generally not handled at all, such that a client is not informed that the request has been refused or the client, if informed, is simply asked to “try again later.” Typically, a refused client must try repeatedly to obtain service with no guarantee that future requests will be processed. For these reasons and others, techniques generally used to alleviate quality of service problems are not always successful.

[0011] A definite need exists for an admission control system having an improved ability to alleviate quality of service problems. In particular, a need exists for an admission control system which responds to all messages, whether or not those messages are actually admitted. Ideally, such system would operate by admitting entire sessions, not just individual messages, such that messages relating to a session in-progress are generally admitted. With a system of this type, admission control would at least provide a reliable means of finishing each session with high quality of service. Finally, a need exists for a system that provides some level of service to all clients, including those which have been refused admission. The present invention solves these needs and provides further, related advantages.

SUMMARY OF THE INVENTION

[0012] An admission control system for a server is disclosed including an admission controller that receives a stream of messages from one or more clients targeted for the server. The admission controller relays to the server the messages in the stream that correspond to a number of sessions already underway between the clients and the server. The admission controller also relays to the server the messages in the stream that do not correspond to sessions already underway if a hybrid and predictive admission control strategy using information provided by a resource monitor indicates that additional sessions can be handled by the server. The admission controller defers the messages otherwise.

BRIEF DESCRIPTION OF THE DRAWING

[0013] The above and other objects and advantages of the present invention will be more readily appreciated from the following detailed description when read in conjunction with the accompanying drawing, wherein:

[0014]FIG. 1 is a block diagram of an admission control system that provides reliable sessions between clients and a server;

[0015]FIG. 2 is a flow diagram of the processing of arriving messages by the admission controller in one embodiment of the present invention;

[0016]FIG. 3 is a block diagram of example configurations of web servers that employ the admission control techniques of the present invention; and

[0017]FIG. 4 is a block diagram of the application of the admission control techniques of the present invention to a proxy server.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0018] A purpose of the present invention is to provide improved quality of service of a server through hybrid and predictive admission control strategies. Turning first to FIG. 1, a block diagram of an admission control system <b>10</b> that provides reliable sessions between clients (not shown) and a server <b>12</b> is shown. The admission control system <b>10</b> includes the server <b>12</b>, an admission controller <b>14</b>, a resource monitor <b>16</b>, and a deferral manager <b>18</b>. The admission controller <b>14</b> processes a stream of arriving messages <b>20</b> from clients into a stream of accepted messages <b>22</b> and a stream of unaccepted messages <b>24</b>. The accepted messages <b>22</b> are passed on to the server <b>12</b> and the unaccepted messages <b>24</b> are passed on to the deferral manager <b>18</b>. It is important to note that there is a practical linit to the number of messages in the stream of arriving messages <b>20</b> for a given time interval. That is, only a finite number of messages can be captured for processing by the admission control system <b>10</b>. Any messages that are sent by clients but do not become part of the stream of arriving messages <b>20</b> are referred to as refused connections. Refused connections often result in aborted sessions. Refused connections are handled according to the applicable protocol.

[0019] The server <b>12</b> represents any server that processes request messages using a stateless protocol in which clients do not establish persistent sessions with the server. In one embodiment, the server <b>12</b> is a web server that processes request messages from web clients using the HTTP. In another embodiment, the server <b>12</b> is a NFS server that processes request messages from NFS clients using the NFS protocol. In other embodiments, the server <b>12</b> may be adapted to the IP, the UDP, or the SMTP, to name a few examples.

[0020] The server <b>12</b> includes resources (not shown) that are involved in the servicing of the arriving messages <b>20</b>. These resources include, for example, one or more processors or central processing units (CPUs), various types of memory and storage subsystems, and network communication subsystems.

[0021] The resource monitor <b>16</b> monitors the utilization of the resources in the server <b>12</b> that are involved in the servicing of the accepted messages <b>22</b> and provides the admission controller <b>14</b> with indications of the utilization of the resources. These indications or metrics inform the admission controller of whether sufficient resources are available in the server to provide an adequate level of service to new sessions.

[0022] In one embodiment, the resource monitor <b>16</b> measures the CPU utilization in the server <b>12</b>. In another embodiment, the resource monitor measures the utilization of the network pathway for the accepted messages <b>22</b> to the server. In a further embodiment, the resource monitor measures the utilization of a storage subsystem, such as a disk drive, of the server. In still another embodiment, the resource monitor <b>16</b> measures the percentage of aborted client requests as an indication that the level of service is unsatisfactory. In an additional embodiment, the resource monitor measures the percentage of new sessions refused as an indication that the server <b>12</b> is overloaded. In yet another embodiment, the resource monitor generates a combined metric for use by the admission controller <b>14</b> that takes into account a number of the above metrics.

[0023] The admission controller <b>14</b> receives the stream of arriving messages <b>20</b> which are targeted for the server <b>12</b>. Each of the arriving messages specifies a client request for the server. Each client request implies an action to be taken by the server in accordance with the predetermined communication protocol which the server processes.

[0024] The admission controller <b>14</b> processes individual ones of the arriving messages <b>20</b> based upon the indications provided by the resource monitor <b>16</b> and a determination of whether the arriving messages correspond to sessions already underway with the server <b>12</b>. In one embodiment, a transaction list <b>26</b> identifies any session underway between the server and a requesting client. The admission controller compares client source indications contained in the arriving messages to entries in the transaction list to determine whether the arriving messages correspond to sessions underway. In another embodiment, the admission controller determines whether the arriving messages correspond to sessions underway by determining whether valid transaction identifiers are contained in the arriving messages.

[0025] The admission controller <b>14</b> accepts the ones of the arriving messages <b>20</b> that correspond to sessions underway. In addition, the admission controller accepts the ones of the arriving messages that do not correspond to existing sessions if the resource monitor <b>16</b> indicates that there are sufficient resources in the server <b>12</b> to adequately process a new session.

[0026] The server <b>12</b> receives and processes each of the accepted messages <b>22</b> in the order received at the server. A stream of completed messages <b>28</b> represents the actions taken by the server in response to the accepted messages. For example, the completed messages may contain response information to be transported to the requesting clients that originated the corresponding accepted messages.

[0027] The deferral manager <b>18</b> handles the unaccepted messages <b>24</b> which were blocked by the admission controller <b>14</b>. In one embodiment, the deferral manager transfers the unaccepted messages as a stream of deferred messages <b>30</b> to another server (not shown) that replicates the functionality of the server <b>12</b>. For example, if the server is a web server then the deferral manager redirects the deferred messages to another web server, often called a mirror site, that performs the same function as the web server <b>12</b>.

[0028] In another embodiment wherein the server <b>12</b> is a web server, the deferral manager <b>18</b> transfers response messages back to the requesting web clients which indicate that a bonus or incentive is available if the deferred request is retried at a later time. For example, if the web server provides a sales transaction to requesting web clients, then the deferred messages <b>30</b> are targeted for the deferred requesting clients and may contain encoded information that provides the client with a discount on a later purchase.

[0029] In another embodiment, the deferral manager <b>18</b> directs the deferred messages <b>30</b> to another server that enables the deferred web client to reserve a future time interval for access to the server <b>12</b>. Alternatively, the server may provide a function that enables the deferred web client to reserve a future time. In addition, the deferral manager may transfer a response message to the deferred client that indicates that the request is being deferred.

[0030] Turning now to FIG. 2, a flow diagram of the processing of the arriving messages <b>20</b> by the admission controller <b>14</b> in one embodiment of the present invention is shown. The arriving messages include a new request message, and processing begins at block <b>32</b>. At decision block <b>34</b>, the admission controller <b>14</b> examines a client source indication in the new request message to determine whether the new request message corresponds to an entry in the transaction list <b>26</b>. If the new request message corresponds to a session that is identified in the transaction list, then processing proceeds to block <b>42</b> where the new request message is passed on to the server <b>12</b> as one of the accepted messages <b>22</b>.

[0031] In one embodiment, the client source indication is an IP address in the new request message that specifies its source. Correspondingly, the entries in the transaction list <b>26</b> contain the IP addresses of clients of the server <b>12</b> that are involved in sessions. The admission controller <b>14</b> compares the IP address contained in the new request message to the IP addresses stored in the transaction list <b>26</b> at decision block <b>34</b>. If a match is detected then processing proceeds to block <b>42</b>.

[0032] In another embodiment, the client source indication is a transaction identifier in the new request message. Correspondingly, the entries in the transaction list <b>26</b> contain transaction identifiers. At decision block <b>34</b>, the admission controller <b>14</b> determines whether a transaction identifier is contained in the new request message and compares that transaction identifier, if present, to the transaction identifiers stored in the transaction list <b>26</b> and processing proceeds to block <b>42</b> if a match is detected.

[0033] Returning to decision block <b>34</b>, if the new request message does not correspond to a transaction identified in the transaction list <b>26</b> then processing proceeds to decision block <b>36</b>. At decision block <b>36</b>, the admission controller <b>14</b> determines whether sufficient resources are available in the server <b>12</b> to adequately service a new session. The determination at decision block <b>36</b> is made based upon indications provided by the resource monitor <b>16</b> and will be discussed in further detail below. In general, utilization of the resources of the server <b>12</b> are measured at regular intervals. If the utilization rises above a specified threshold, then for the next time interval, the admission controller <b>14</b> will reject all new sessions and service only existing sessions. Once the utilization falls below the given threshold, then for the next time interval, the admission controller <b>14</b> will admit new sessions again while continuing to service existing sessions.

[0034] If there are insufficient resources to adequately sustain a new session at decision block <b>36</b>, then at block <b>38</b> the admission controller <b>14</b> passes the new request message to the deferral manager <b>18</b> as one of the unaccepted messages <b>24</b>. Otherwise at block <b>40</b>, the admission controller creates a new entry in the transaction list <b>26</b>. Thereafter, at block <b>42</b>, the admission controller passes the new request message on to the server <b>12</b> as one of the accepted messages <b>22</b>.

[0035] In one embodiment at block <b>40</b>, the admission controller <b>14</b> creates a new entry in the transaction list <b>26</b> and writes the IP address of the new request message into the new entry of the transaction list. In another embodiment, the admission controller creates a new entry and writes a new transaction identifier into the new entry of the transaction list <b>26</b>. The new transaction identifier may be returned to the requesting client that originated the request message as a “cookie” or may be returned to the requesting client in a hidden field of an HTTP form.

[0036] The entries in the transaction list <b>26</b> identifying sessions remain valid until the end of the corresponding session. A session ends and the corresponding entry in the transaction list is cleared when a new client request message corresponding to that session is not received by the admission controller <b>14</b> during a predetermined time-out interval. In addition, a session ends at a point in the session defined by the server <b>12</b>. For example, if the server <b>12</b> is a web server which provides an item purchase function then the session ends and its entry is cleared from the transaction list <b>26</b> when a message is received from the client indicating the confirmation of the purchase.

[0037] There are two desirable properties for the processing of the arriving messages <b>20</b> by the admission controller <b>14</b>. The first is that the admission control process be responsive, that is, that the process aims to minimize the number of aborted sessions and to achieve higher levels of service at the expense of slightly lower session throughput. A responsive process leads to a more restrictive admission controller <b>14</b>. The second is that the admission control process be stable, that is, that the process aims to minimize the overreaction to utilization changes with the benefit of slightly higher session throughput. A stable process leads to a less restrictive admission controller <b>14</b>. If the utilization of the resources of the server <b>12</b> during the previous time intervals is consistently high and exceeds the threshold, then a responsive admission control process is very desirable to reject newly arriving messages <b>20</b> as soon as possible. However, if the utilization of the resources of the server <b>12</b> during the previous time intervals is consistently below the threshold with occasional brief bursts of utilization, then a stable admission control process is very desirable to maximize session throughput. As one can see, these two properties are somewhat contradictory and a hybrid admission control process is a desirable achievement.

[0038] Formally, the admission control process is defined by a number of parameters including the admission control utilization threshold Uth which establishes the critical server utilization level at which the admission control process becomes more restrictive. The server utilization is measured at regular intervals where the intervals are T<b>1</b>, T<b>2</b>, . . . , Ti, . . . and their length is the admission control interval length ACil. For example, ACil might be one second so the server utilization is measured every second. The server utilization measured during the i-th interval Ti is Umea_i. An admission control function ƒ_acis used to evaluate the observed server utilization Uobs_i+1where

ƒ_ac(1)=U_ac,  Eq. 1

ƒ_ac(<i>i+</i>1)=(1−<i>k</i>)*ƒ_ac(<i>i</i>)+<i>k*Umea</i>_i,  Eq. 2

[0039] and k is a damping coefficient between 0 and 1 and is called the admission control weight coefficient.

[0040] The observed server utilization is used to determine the admission control process of the admission controller <b>14</b>. If Uobs_i+1is greater than Uth, then for the next time interval Ti+1, the admission controller <b>14</b> will reject all new sessions and service only existing sessions. If Uobs_i+1is less than or equal to Uth, then for the next time interval Ti+1, the admission controller <b>14</b> will admit new sessions again while continuing to service existing sessions.

[0041] The value of the admission control weight coefficient k in Eq. 2 creates a range of admission control processes which cover the spectrum from responsive to stable. If k is equal to one, then the admission control process is based entirely on the server utilization measured during the last interval and is called responsive. If k is equal to one tenth (0.1), then the admission control process is influenced by server utilization measured over all of the prior intervals and the influence of the last interval is limited. This is called stable. As expected, a responsive admission control process leads to more restrictive admissions and achieves a better level of service but at the price of a higher percentage of new sessions refused as an result of the server being overloaded. Likewise, a stable admission control process achieves better throughput in the utilization range of eighty five to one hundred and twenty percent but at the price of a higher percentage of aborted client requests as a result of the unsatisfactory level of service. Based on these observations, a self-tunable admission control process called a hybrid was developed.

[0042] Further parameters that define the admission control process include the number of refused connections Re(i) and the number of aborted requests Ab(i) accumulated during the interval Ti. It is assumed that Ab(i) is directly related to server service levels and not to external factors on the client end such as a computer crash. External factors should be discounted from Ab(i). If the sum of Re(i) and Ab(i) is greater then zero then the process needs to be made more responsive. If the sum of Re(i) and Ab(i) is equal to zero then either the system is not overloaded or the process is perfectly balanced between responsive and stable during server overload. This balance is the ideal state for the system to operate in and results in the best quality of service.

[0043] The preferred hybrid process begins with k equal to one. Then for any time interval Ti where the sum of Re(i) and Ab(i) is greater than zero, k is made equal to one for the next time interval Ti+1. Recall that this results in the most responsive admission control process. However, this may not be the most balanced process and so at intervals the process is evaluated for possible adjustment to a less responsive process. At an evaluation interval, if the sum of Re(i) and Ab(i) was equal to zero for all of the previous time intervals since the previous evaluation interval, then k is reduced by a predetermined amount, for example 0.1. Recall that k is limited to having a value greater than or equal to zero so k cannot be reduced below zero. It is preferred that the evaluation intervals be separated by the number of time intervals that it takes to complete an average session known as an admission control cycle. The admission control cycle can be approximated by measuring an inter request time. that is the time it takes for the system to respond in addition to the time it takes for the client to evaluate the response and place a new request, multiplied by an average session length in number of requests.

[0044] An alternative to the hybrid process would be for the process not to return immediately to k equal to one upon the first sign of overload. Instead, for any time interval Ti where the sum of Re(i) and Ab(i) is greater than zero, k is increased by a predetermined amount, for example 0.1, for the next time interval Ti+1. Recall that k is limited to having a value less than or equal to one so k cannot be increased above one.

[0045] A further alternative to the hybrid process would be for the process not to consider the summation of Re(i) and Ab(i) but to consider one or the other parameter individually. This may however result in a less accurate picture of the utilization levels of the server depending on the circumstances.

[0046] The hybrid admission control process outlined above has a potential problem that one might want to address. The problem is that if the hybrid process determines that it can handle new sessions then it allows all new sessions presented to it in the next time interval. If the server is near full resource utilization, then it is possible that too many new sessions may be presented in the next time interval for the amount of resources that remain. The result is that the hybrid process allows the server to become overloaded when that is exactly what it is supposed to prevent. One way to address this problem is to allow something less than all of the new sessions presented. This may be a fixed maximum number, for example up to 10. or a fixed percentage, for example one-half. A further refinement would be to estimate the number of new sessions that the server can handle with the remaining resources and only admit that many new sessions in the next time interval. Based on this observation, an alternative to the hybrid admission control process, called predictive was developed and is presented below.

[0047] It is important for one to realize that in order to correctly estimate the number of sessions that a server is able to process per time interval, one must take into consideration the session rejection overhead. Even though a session may be rejected, this act takes up some fractional portion of the resources of the system. Under certain conditions this can add up to a significant amount and will reduce the number of sessions that can be completed. Under the most extreme conditions, the session rejection overhead may theoretically be so great so as to prevent any sessions from being completed.

[0048] In order to account for the session rejection overhead, a number of parameters that define the admission control process need to be measured or calculated. Among these is a server capacity in requests Sr which is the number of requests per time interval that a server can sustain. Next is the length, in requests rather then time, of an average completed session SesLength which is the average number of requests for a session. These values can be measured directly. Calculated from these two as the result of Sr divided by SesLength is a server capacity in sessions Ss which is the maximum number of sessions per time interval that a server can complete. The actual number of sessions applied to the server per time interval is equal to the product of Ss and Load where, for example, Load would be equal to two if the applied number of sessions was twice the server capacity in sessions. The actual number of sessions applied to the server per time interval is also equal to the sum of the number of rejected sessions per time interval x and the number of completed sessions per time interval y. These values can be measured directly. Based on these parameters, the session rejection overhead can be calculated.

[0049] One should realize that from the perspective of the admission control system there are two types of sessions. The first is the completed session which has an average length of SesLength. The second is the rejected session which is equivalent to processing one request. Thus the number of requests per time interval handled by the system is defined in the following way:

<i>y*SesLength+x=Sr .</i>  Eq. 3

[0050] Using the relationships described above, y can be expressed in the following way: <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>y</mi><mo>=</mo><mrow><mfrac><mrow><mi>Load</mi><mo>*</mo><mi>Sr</mi></mrow><mi>SesLength</mi></mfrac><mo>-</mo><mrow><mi>x</mi><mo>.</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>4</mn></mrow></mtd></mtr></mtable></math><img file="US20020052962A1-20020502-M00001.TIF" id="EMI-M00001" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00001" attachment-type="nb" file="US20020052962A1-20020502-M00001.NB" /></attachments></maths>

[0051] Replacing y in Eq. 3 with Eq. 4 and solving for x, one finds the following: <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>x</mi><mo>=</mo><mrow><mfrac><mrow><mi>Sr</mi><mo>*</mo><mrow><mo>(</mo><mrow><mi>Load</mi><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow><mrow><mi>SesLength</mi><mo>-</mo><mn>1</mn></mrow></mfrac><mo>.</mo></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>5</mn></mrow></mtd></mtr></mtable></math><img file="US20020052962A1-20020502-M00002.TIF" id="EMI-M00002" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00002" attachment-type="nb" file="US20020052962A1-20020502-M00002.NB" /></attachments></maths>

[0052] Finally, the number of rejected sessions x divided by the server capacity in requests Sr is the fractional number of rejections per time interval and can be expressed as a percentage in the following way: <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>RejectionPercentage</mi><mo>=</mo><mrow><mn>100</mn><mo>*</mo><mrow><mfrac><mrow><mi>Load</mi><mo>-</mo><mn>1</mn></mrow><mrow><mi>SesLength</mi><mo>-</mo><mn>1</mn></mrow></mfrac><mo>.</mo></mrow></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>6</mn></mrow></mtd></mtr></mtable></math><img file="US20020052962A1-20020502-M00003.TIF" id="EMI-M00003" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00003" attachment-type="nb" file="US20020052962A1-20020502-M00003.NB" /></attachments></maths>

[0053] As reflected in Eq. 6, the rejection overhead depends on the average session length and the applied load. As a result, the shorter the average session length and the higher the applied load, the greater the rejection overhead.

[0054] Once the rejection overhead is calculated, one is able to predict the number of sessions that the server is able to handle per time interval. The relationship is derived by replacing x in Eq. 4 with Eq. 5 and rearranging, resulting in the following: <maths id="MATH-US-00004" num="4"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>y</mi><mo>=</mo><mrow><mfrac><mrow><mi>Sr</mi><mo>*</mo><mrow><mo>(</mo><mrow><mi>SesLength</mi><mo>-</mo><mi>Load</mi></mrow><mo>)</mo></mrow></mrow><mrow><mi>SesLength</mi><mo>*</mo><mrow><mo>(</mo><mrow><mi>SesLength</mi><mo>-</mo><mn>1</mn></mrow><mo>)</mo></mrow></mrow></mfrac><mo>.</mo></mrow></mrow></mtd><mtd><mrow><mi>Eq</mi><mo>.</mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>7</mn></mrow></mtd></mtr></mtable></math><img file="US20020052962A1-20020502-M00004.TIF" id="EMI-M00004" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00004" attachment-type="nb" file="US20020052962A1-20020502-M00004.NB" /></attachments></maths>

[0055] Based on the calculation of the number of sessions that the server is able to complete per time interval, a predictive admission control system will only process new sessions for the amount of resources that it has available. One will realize that this prediction is not without risk because the prediction for the next time interval is based on data from the current time interval including the applied load and a running average of the session length. Either or both of these may not prove true for the next time interval. Under certain conditions the admission control system may still allow too many new sessions in the next time interval and allow the server to become overloaded. Nevertheless, the prediction should usually be better than simply allowing all new sessions in the next time interval.

[0056] Turning now to FIG. 3, a block diagram of example configurations of web servers that employ the admission control techniques of the present invention are shown. A set of web browsers <b>44</b>, <b>46</b>, and <b>48</b>, and a pair of web servers <b>50</b> and <b>52</b> are shown coupled for communication via a network <b>54</b>. In addition, a pair of web servers <b>56</b> and <b>58</b> are shown coupled for communication over a local network <b>60</b>. A gateway <b>62</b> enables communication between the network <b>54</b> and the local network <b>60</b>.

[0057] The web browsers <b>44</b>, <b>46</b>, and <b>48</b> transfer HTTP requests via the network <b>54</b> and are potential web clients to the web servers <b>50</b>, <b>52</b>, <b>56</b>, and <b>58</b>. Each HTTP request from the web browsers <b>44</b>, <b>46</b>, and <b>48</b> contains a Universal Resource Locator (URL), referred to as an “address,” that targets one of the web servers <b>50</b>, <b>52</b>, <b>56</b>, and <b>58</b>. The network <b>54</b> routes each HTTP request to either the web server <b>50</b> or <b>52</b>. or the gateway <b>62</b>, depending on the particular URL contained in the request.

[0058] The web server <b>50</b> is augmented with software elements that provide functionality of the admission controller <b>14</b>, the resource monitor <b>16</b>, and the deferral manager <b>18</b>. The deferral manager <b>18</b> in the web server <b>50</b> redirects deferred client request messages to the web server <b>52</b>. The web server <b>52</b> may be a mirror site to the web server <b>50</b> or may implement special web server software for handling the deferred client requests as previously described. The resource monitor <b>16</b> in the web server <b>50</b> may employ the services of an operating system under which it executes to obtain metrics such as CPU. network, or storage subsystem utilization.

[0059] In one embodiment, the web server <b>50</b> generates transaction identifiers to identify any of the web browsers <b>44</b>, <b>46</b>, and <b>48</b> to which sessions are underway. The web server <b>50</b> may transfer the transaction identifiers to the web browsers <b>44</b>, <b>46</b>, and <b>48</b> as cookies in response messages to the web browsers. The cookies may be encoded and may have an expiration date and time. The web browsers <b>44</b>, <b>46</b>, and <b>48</b> include the cookies which they were allocated in subsequent request messages to the web server <b>50</b> and the admission controller <b>14</b> in subsequent request messages when determining whether to admit the subsequent request messages.

[0060] Alternatively, the web server <b>50</b> may transfer transaction identifiers to the web browsers <b>44</b>, <b>46</b>, and <b>48</b> as hidden fields in forms contained in response messages to the web browsers. The web browsers submit the forms including hidden transaction identifiers with subsequent request messages to the web server <b>50</b> and the admission controller <b>14</b> compares the transaction identifiers contained in submitted forms when deciding whether to admit the subsequent request messages.

[0061] The gateway <b>62</b> functions as a communication gateway between the network <b>54</b> and the local network <b>60</b> that connects to the web servers <b>56</b> and <b>58</b>. The web servers <b>56</b> and <b>58</b> each may provide a different web server function. Alternatively, the web servers <b>56</b> and <b>58</b> taken together may provide a single web server function.

[0062] The gateway <b>62</b> is augmented with software elements that provide the functionality of the admission controller <b>14</b>, the resource monitor <b>16</b>, and the deferral manager <b>18</b>. The resource monitor <b>16</b> in the gateway <b>62</b> monitors the resources of both of the web servers <b>56</b> and <b>58</b> via the local network <b>60</b>. The admission controller <b>14</b> in the gateway <b>62</b> receives arriving messages targeted for the web servers <b>56</b> and <b>58</b> from the web browsers <b>44</b>, <b>46</b>, and <b>48</b>. The admission controller <b>14</b> in the gateway <b>62</b> relays the arriving messages that correspond to sessions already underway onto the appropriate one of the web servers <b>56</b> and <b>58</b> if the resource monitor <b>16</b> indicates that sufficient resources are available in the appropriate web server <b>56</b> and <b>58</b> to adequately handle additional sessions.

[0063] The web browsers <b>44</b>, <b>46</b>, and <b>48</b> may be embodied as separate computer systems that execute web browser software or as one computer system executing multiple web browser applications or any combination thereof. The web browsers may be also be embodied as network computers with web browser capability or television components with web browsing capability.

[0064] Turning now to FIG. 4, a block diagram of the application of the admission control techniques of the present invention to a proxy server is shown. The proxy server <b>64</b> enables access to a network <b>66</b> by a set of computer systems <b>68</b>, <b>70</b>, and <b>72</b> coupled to a local network <b>74</b>. For example, the network <b>66</b> may represent the world-wide-web of the Internet that enables access to a web server <b>76</b> and the computer systems <b>68</b>, <b>70</b>, and <b>72</b> may belong to a large organization and be connected via an internal organization network or local area network.

[0065] The proxy server <b>64</b> receives a stream of client request messages from the computer systems <b>68</b>, <b>70</b>, and <b>72</b> which are targeted for destinations on the network <b>66</b> such as the web server <b>76</b>.

[0066] The proxy server <b>64</b> maintains a transaction list <b>26</b> that identifies which of the computer systems <b>68</b>, <b>70</b>, and <b>72</b> have sessions underway with a destination on the network <b>66</b>. In one embodiment, the transaction list <b>26</b> in the proxy server <b>64</b> records network addresses on the local network <b>74</b> for the computer systems <b>68</b>, <b>70</b>, and <b>72</b>.

[0067] The proxy server <b>64</b> also contains a resource monitor <b>16</b> for monitoring the CPU and storage subsystem utilization in the proxy server, the network utilization in the proxy server, and the network utilization on both the network <b>66</b> side and the local network <b>74</b> side. The proxy server also contains an admission controller <b>14</b> that passes request messages from the computer systems <b>68</b>, <b>70</b>, and <b>72</b> onto the network <b>66</b> if the client request messages correspond to sessions identified in the transaction list <b>26</b> of the proxy server. In addition, the admission controller <b>14</b> in the proxy server passes client request messages from computer systems <b>68</b>, <b>70</b>, and <b>72</b> not identified in the transaction list <b>26</b> if the resource monitor <b>16</b> in the proxy server indicate that sufficient resources are available to allow another session to be established.

[0068] While the invention has been illustrated and described by means of specific embodiments, it is to be understood that numerous changes and modifications may be made therein without departing from the spirit and scope of the invention as defined in the appended claims.