Abstract:
The present invention allows a server to delay allocating resources to a client&#39;s request. When the client requests a feature that requires server resources, the server accepts and acknowledges the client&#39;s request, but the client is prohibited from using the requested feature until further notice from the server. For example, during an authorization process, the server allocates only the minimum resources required to maintain the session and to authorize the client. Thereafter, the server allocates the resources necessary to support the client&#39;s request only when the resources become available. Until then, the server maintains the communications session without supporting the request. Thus, the server shepherds its resources rather than committing them at the whim of a client. Also, a client need not repeat its request if the server cannot immediately satisfy it; instead, the server accepts the request and then later begins to support it when adequate resources become available.

Description:
RELATED APPLICATION  
         [0001]    The present application claims the benefit of U.S. Provisional Patent Application 60/451,151, filed on Feb. 28, 2003, which is incorporated herein in its entirety by reference.  
         TECHNICAL FIELD  
         [0002]    The invention relates generally to network communications and, more particularly, to allocating resources among clients and servers on a network.  
         BACKGROUND OF THE INVENTION  
         [0003]    The rapid growth of computer networks, both public and private, in recent years has been spurred, in large part, by “client/server computing.” In this model, one computing device, the client, requests that another computing device, the server, provide services or features to it. Note that “client” and “server” are used solely to denote the parties in a request transaction. While some computing devices are implemented as dedicated servers that can serve multiple clients, a client and a server can switch roles from one transaction to another. In a “peer-to-peer” network (common, for example, among devices communicating via short range radio), every computing device has the potential to be both a client and a server, serially or simultaneously.  
           [0004]    Servers often have to allocate precious resources to fulfill a request for a feature or for a service. Upon receiving a request from a client, a server checks the availability of its resources. Traditionally, if the server does not have the resources to fulfill the request, then the server rejects the request. If the client can proceed without the requested feature or service, then it does so and resubmits the request later, at which time the server may have the necessary resources available to fulfill the request.  
           [0005]    In order to ensure that precious server resources are dedicated only to those clients authorized to use them, servers often check the identity of a client making a request. If the client cannot authenticate itself to the satisfaction of the server, then the server rejects the request.  
           [0006]    This protection against unauthorized clients is not perfect, however. Some types of requests are made before the authorization process is complete. Processing these requests, even if they are ultimately rejected, consumes some level of server resources. For example, a nefarious client could bring a “denial of service” (DOS) attack against a server by repeatedly making requests of the server. Although this client will fail to authenticate itself and its requests will ultimately be rejected, the server may in the mean time utilize so many resources attempting to authenticate the client during each request that the server exhausts its resource pool until the server is rendered incapable of fulfilling any requests, even those made by authorized clients.  
         SUMMARY OF THE INVENTION  
         [0007]    In view of the foregoing, the present invention allows a server to delay allocating resources to a client&#39;s request. When the client requests a service or a feature that requires server resources (such as, for example, encryption or compression of the messages between the client and the server), the server accepts and acknowledges the client&#39;s request, but the client is prohibited from using the requested feature until further notice from the server. For example, during an authorization process, the server allocates only the minimum resources required to maintain the session and to authorize the client. Thereafter, the server allocates the resources necessary to support the client&#39;s request only when the resources become available. Until then, the server maintains the communications session without supporting the request. Thus, the server shepherds its resources rather than committing them at the whim of a potentially malicious, malfunctioning, or misconfigured client. Also, a legitimate client need not repeat its request if the server cannot immediately satisfy it; instead, the server accepts the request and then later begins to support it when adequate resources become available.  
           [0008]    According to one embodiment, after receiving a request for data compression from a client, the server accepts and acknowledges the request but delays allocating the resources necessary to compress communications data. Indeed, the server might not even check to see whether resources are available until the client has successfully authenticated itself to the server. Even though the compression request has been accepted, the client and server communicate without compressing their data. This continues until, and if, the resources necessary for compression become available on the server. At that time, the server allocates the necessary resources and indicates to the client that compression is now supported. The server can signal this by, for example, sending compressed data to the client. Upon receiving the signal (e.g., the compressed data), the client realizes that it is now permitted to communicate with compression. The client responds by beginning to transmit compressed data to the server.  
           [0009]    Compression is just one example of a communications feature that can be requested by a client. Other examples include the wide range of features commonly called Quality of Service (QOS). QOS features include, generally, bandwidth, response time guarantees, immunity to error, integrity of message sequence and lack of duplication, maximum permissible loss rates, and the like. QOS features provide examples where, in keeping with one embodiment of the present invention, the server can allocate resources level by level rather than all at once. For example, the client requests a great amount of guaranteed bandwidth. The server initially accepts the request but allocates resources sufficient to support only a low amount of guaranteed bandwidth. The client recognizes this and uses only the low amount of bandwidth. Later, the server allocates more bandwidth to this client (in response, for example, to another client releasing bandwidth), and the client begins to use the greater bandwidth amount.  
           [0010]    Also in keeping with the invention, a server or a client (or both) maintains information about the requested feature and about the actual level of service being supported. The server monitors this information for each client and allocates additional resources to the clients as resources become available in order to more fully support the clients&#39; requests.  
           [0011]    A client can display to its user the status of requests as accepted and supported, accepted but not yet supported, and rejected. The server can provide similar information to an administrator or to a log file. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0012]    While the appended claims set forth the features of the present invention with particularity, the invention, together with its objects and advantages, may be best understood from the following detailed description taken in conjunction with the accompanying drawings of which:  
         [0013]    [0013]FIG. 1 is a block diagram of an exemplary computer networking environment within which the present invention can be practiced;  
         [0014]    [0014]FIG. 2 is a schematic diagram generally illustrating an exemplary computer system that supports the present invention;  
         [0015]    [0015]FIGS. 3 a  and  3   b  together form a data-flow diagram illustrating an exemplary message exchange between a client and a server during negotiation of the client&#39;s communications feature request;  
         [0016]    [0016]FIG. 4 is a data-structure diagram of an exemplary message exchanged between the client and the server during the scenario of FIGS. 3 a  and  3   b;    
         [0017]    [0017]FIGS. 5 a  and  5   b  together form a flowchart illustrating an exemplary resource allocation method performed by a server;  
         [0018]    [0018]FIG. 6 is a data-structure diagram of a request status list usable by a server; and  
         [0019]    [0019]FIGS. 7 a  and  7   b  together form a flowchart illustrating an exemplary feature request method performed by a client; and 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0020]    Turning to the drawings, wherein like reference numerals refer to like elements, the present invention is illustrated as being implemented in a suitable computing environment. The following description is based on embodiments of the invention and should not be taken as limiting the invention with regard to alternative embodiments that are not explicitly described herein.  
         [0021]    In the description that follows, the present invention is described with reference to acts and symbolic representations of operations that are performed by one or more computing devices, unless indicated otherwise. As such, it will be understood that such acts and operations, which are at times referred to as being computer-executed, include the manipulation by the processing unit of the computing device of electrical signals representing data in a structured form. This manipulation transforms the data or maintains them at locations in the memory system of the computing device, which reconfigures or otherwise alters the operation of the device in a manner well understood by those skilled in the art. The data structures, where data are maintained, are physical locations of the memory that have particular properties defined by the format of the data. However, while the invention is being described in the foregoing context, it is not meant to be limiting as those of skill in the art will appreciate that various of the acts and operations described hereinafter may also be implemented in hardware.  
         [0022]    The present invention allows a server to accept a client request but to delay allocating the resources necessary to support that request. FIG. 1 gives an example of a computer networking environment  100  in which the invention can be used. The example network  100  includes a server computing device  102  and three client computing devices  104 ,  106 , and  108 . The network  100  can be a corporate local area network (LAN), a wireless network, the Internet, or anything in between and can include many well known components, such as routers, gateways, hubs, etc. In an example transaction, the client  104  requests a service or a communications feature from the server  102 . The server  102  provisionally accepts the request but does not allocate resources to support the requested feature until, for example, the client  104  authenticates itself to the server  102  or until the resources become available. Until the resources are allocated and the server  102  informs the client  104  of that fact, the client  104  and the server  102  communicate without using the requested feature. Thus, the server  102  shepherds its resources rather than committing them at the whim of a potentially malicious, malfunctioning, or misconfigured client.  
         [0023]    In another transaction, the client  104  and the server  102  can switch roles with the “server”  102  requesting a service from the “client”  104 . In a peer-to-peer network, every computing device can be both a client and a server, serially or simultaneously. Accordingly, embodiments of the invention can be practiced on clients, servers, peers, or any combinations thereof.  
         [0024]    The computing device  110  is another server but one that only directly communicates with the server  102  to provide resources to it. Its presence illustrates that by following the methods of the present invention, the server  102  shepherds not just its own resources but the resources of the networking environment  100  generally.  
         [0025]    The computing devices  102  and  104  of FIG. 1 may be of any architecture. FIG. 2 is a block diagram generally illustrating an exemplary computer system that supports the present invention. The computer system of FIG. 2 is only one example of a suitable environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Nor should the computing device  102  be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in FIG. 2. The invention is operational with numerous other general-purpose or special-purpose computing environments or configurations. Examples of well known computing systems, environments, and configurations suitable for use with the invention include, but are not limited to, personal computers, servers, hand-held or laptop devices, tablet devices, multiprocessor systems, microprocessor-based systems, set-top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, and distributed computing environments that include any of the above systems or devices. In its most basic configuration, the computing device  102  typically includes at least one processing unit  200  and memory  202 . The memory  202  may be volatile (such as RAM), non-volatile (such as ROM or flash memory), or some combination of the two. This most basic configuration is illustrated in FIG. 2 by the dashed line  204 . The computing device  102  may have additional features and functionality. For example, the device  102  may contain additional storage (removable and non-removable) including, but not limited to, magnetic and optical disks and tape. Such additional storage is illustrated in FIG. 2 by removable storage  206  and by non-removable storage  208 . Computer-storage media include volatile and non-volatile, removable and non-removable, media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules, or other data. Memory  202 , removable storage  206 , and non-removable storage  208  are all examples of computer-storage media. Computer-storage media include, but are not limited to, RAM, ROM, EEPROM, flash memory, other memory technology, CD-ROM, digital versatile disks, other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage, other magnetic storage devices, and any other media that can be used to store the desired information and can be accessed by the computing device  102 . The device  102  may also contain communications channels  210  that allow the computer to communicate with other devices. Communications channels  210  are examples of communications media. Communications media typically embody computer-readable instructions, data structures, program modules, or other data in a modulated data signal such as a carrier wave or other transport mechanism and include any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communications media include wired media, such as wired networks and direct-wired connections, and wireless media such as acoustic, RF, infrared, and other wireless media. The term “computer-readable media” as used herein includes both storage media and communications media. The computing device  102  may also have input devices  212  such as a keyboard, mouse, pen, voice-input device, tablet, touch-input device, etc. Output devices  214  such as a display (which may be integrated with a touch-input device), speakers, and printer may also be included. All these devices are well known in the art and need not be discussed at length here.  
         [0026]    [0026]FIGS. 3 a  and  3   b  together show an exemplary exchange of messages when the client  104  requests a feature from the server  102 . FIGS. 5 a,    5   b,    7   a,  and  7   b,  below, present further details of possible message exchanges. The client  104  requests the feature in step  300  of FIG. 3 a.  The feature can be of any type including data compression, data encryption, and the numerous QOS features. The message protocol can also be of any type, such as, e.g., SIP (the Session Initiation Protocol). Note that the feature request in step  300  need not be explicit: It may instead be implied by the message protocol used between the client  104  and the server  102 .  
         [0027]    In step  302 , the server  102  receives the feature request and decides whether it will support that feature. If not, then the server  102  uses the methods defined in the protocol to reject the request (not shown). If the server  102  will support the requested feature and is ready to do so immediately, then the server  102  allocates the resources needed to support the feature and accepts the request (also not shown). The scenario depicted in FIGS. 3 a  and  3   b  concerns a third possibility for the server  102 : It may be willing to support the requested feature in the future but is not yet ready to do so. One example that leads to this scenario is the case where the server  102  currently does not have the resources available to support the feature but expects to acquire those resources soon. In another example, the server  102  does not yet trust the client  104  enough to allocate precious resources to its request. The server  102  does not yet allocate the resources but waits until the client  104  has successfully authenticated itself. (See the discussion of steps  310  and  312  of FIG. 3 b  below.) In the scenario of FIG. 3 a,  the server  102  in step  302  sends a message to the client  104  indicating that the request has been accepted but also indicating that the requested feature is not yet supported.  
         [0028]    There are numerous ways in which the server  102  can indicate that the requested feature is not yet supported. In SIP, for example, when data compression is allowed on a communications link, “tags” are added to the data fields. (See FIG. 4 and the accompanying discussion.) Not all data messages are compressed even when compression is enabled (for example, a given message may be too short to benefit from compression), so a flag in a tag indicates whether the accompanying data are compressed. Embodiments of the present invention can use this tag and flag in step  302 : The acceptance message is tagged indicating that the request for data compression has been allowed, but the data in that message are not compressed, as indicated by the flag. In step  304 , the client  104  receives the acceptance message and notes that the requested feature is not yet supported. In the data compression example, the tag indicates the acceptance of the request, but the lack of compression indicates that the server is not ready for compressed data.  
         [0029]    In steps  306  and  308 , the client  104  and the server  102  communicate without using the requested feature. Depending upon circumstances, these steps can continue for a long time (until, e.g., the server  102  acquires the necessary resources) or can be very short (e.g., only until the client  104  successfully authenticates itself to the server  102 ).  
         [0030]    Steps  310  and  312  of FIG. 3 b  are, in one sense, optional but are included because they illustrate a scenario in which the methods of the present invention are very useful. During these steps, the client  104  authenticates itself to the server  102  using the methods established by the protocol they are using. (Many such methods are known in the art.) The server  102  is understandably reluctant to allocate precious resources until these steps are complete. Although this scenario is not the only one in which delayed allocation of resources proves valuable, it is one scenario closely tied to preventing DOS attacks.  
         [0031]    Finally, in step  314  the server  102  decides to allocate the resources to support the client  104 &#39;s request. In step  316 , the server  102  indicates to the client  104  that the feature is now supported. Just as with the numerous possible indications discussed above with respect to step  302 , there are numerous ways in which the server  102  can indicate that the feature is now supported. Using the data compression example, the server  102  can simply send compressed data to the client  104 . Upon receiving the indication, whatever it is, the client  104  notes that the feature is now supported in step  318 . From that point on, the client  104  and the server  102  can communicate either using or not using the requested feature, as appropriate to the situation.  
         [0032]    [0032]FIG. 4 shows a message data structure  400  used for sending compressed or uncompressed data. The data structure  400  includes three tag fields. The first tag field  402  is designated for flags (herein “flags tag”). The flags tag field  402  is used for indicating the format of the data in field  408 , specifically whether the data are compressed. Under this implementation, the flag field includes mutually exclusive bits. As an example, a 0×80 bit is used to indicate that the data are uncompressed, and a 0×20 bit indicates that the data are compressed.  
         [0033]    In some embodiments, there are at least three types of data packets: (1) untagged data indicating that data compression is not available for the current connection; (2) data tagged indicating that compression is possible, but the data in field  408  are flagged as not compressed; and (3) data tagged indicating that compression is possible, and the data in field  408  are compressed. In steps  304  and  318  of FIGS. 3 a  and  3   b,  respectively, the client  104  determines the type of data packet it receives from the server  102  to know whether or not data compression is supported.  
         [0034]    A flowchart illustrating exemplary steps performed by the server  102  is shown in FIGS. 5 a  and  5   b.  In step  500 , the server  102  receives a request from the client  104  for a service or for a communications feature. As mentioned above, this request may be in the form of an explicit message sent by the client  104 , or it may be implicit in the communications protocol used between the client  104  and the server  102 . The server  102  checks, in step  502 , its own configuration to see whether it can support the requested feature. It could happen that the client  104  is requesting a feature that the server  102  is not configured to support. In that case, the method proceeds to step  510  where the server  102  rejects the request.  
         [0035]    If the server  102  could, at least theoretically, support the requested feature, then in step  504  it accepts the request but tells the client  104  that the client  104  may not yet use the feature.  
         [0036]    There are some features that the server  102  will only provide to authenticated clients. If the client  104  has requested such a feature, then in step  506  an authentication process is carried out. If the client  104  fails the authentication in step  508 , then the server  102  can reject the request in step  510 , even though it provisionally accepted the request earlier in step  504 . Note that an authentication failure does not necessarily imply that the client  104  must terminate its communications session with the server  102 . While that is a possible outcome, for the present discussion, the consequence of an authentication failure is the client  104 &#39;s inability to use the requested feature.  
         [0037]    If the client  104  successfully authenticates itself to the server  102  (or if such authentication is not necessary), then the client  104  and the server  102  begin to communicate with each other but without using the requested feature. If necessary, the server  102  checks for the availability of sufficient resources in step  512  and when, in step  514  of FIG. 5 b,  such resources become available, the server  102  allocates them to support the feature requested by the client  104 . As mentioned above in relation to FIG. 1, these resources need not reside on the server  102  itself. They may be provided by another server  110 . In some scenarios, the resources may become available in step  514  when another client gives them up. In other scenarios, the resources are always available, but the server  102  is reluctant to commit them to the client  104  until the client  104  successfully authenticates itself in step  508  of FIG. 5 a.    
         [0038]    In step  516  of FIG. 5 b,  the server  102  indicates that it is now ready to support the requested feature. Some features can be supported at different levels. For example, the client  104  requests a minimum bandwidth guarantee of 512 kbps. If the server  102  does not have the resources to fully support that request, it could simply reject it. Alternatively, the server  102  can accept the request but tell the client  104  that the server  102  can only support a 128 kbps bandwidth guarantee. The client  104  decides whether the lower guarantee is acceptable or not and reacts accordingly.  
         [0039]    Throughout this procedure, the server  102  tracks its resource levels and allocations, as indicated in step  518 . The server  102  uses this information when deciding whether it has sufficient resources to support a requested feature. System administrators use this information when deciding whether the server  102  is optimally configured.  
         [0040]    [0040]FIG. 6 gives an example of the server  102 &#39;s resource log. The resource allocation log  600  contains four entry rows, each one pertaining to a single feature request. In the log  600 , the client  104  (field  602 ) has requested data compression (field  604 ), and that request has been accepted (field  606 ). The client  106 &#39;s request for data compression was rejected, possibly because the client  106  failed to authenticate itself to the server  102 . The client  108 &#39;s request for data compression has been provisionally accepted, but that feature is not yet supported. The client  108  has made another request, this time for a guaranteed bandwidth of 512 kbps. The request has been accepted, but the feature is currently supported only at the lower level of 128 kbps.  
         [0041]    In step  520  of FIG. 5 b,  the client  104  and the server  102  can use the requested feature in their communications. However, they are not required to use the feature. For example, even when compression is supported, some messages are too short to benefit from being compressed.  
         [0042]    Another use of the server  102 &#39;s resource allocation log  600  is illustrated in step  522 . Here, some resources are freed up (probably from another client), and the server  102  checks its resource allocation log  600 . It notes, for example, that the client  108  requested 512 kbps of guaranteed bandwidth but was only granted 128 kbps. If the server  102  can and wishes to support the client  108 &#39;s request at a higher level, it can now do so. For some features, the server  102  can even use this method to reduce its level of support. Other features do not allow for this, and the level of support must be renegotiated.  
         [0043]    The client  104 &#39;s side of a feature request transaction is illustrated in the flowchart of FIGS. 7 a  and  7   b.  As the bulk of the client  104 &#39;s procedure is evident in light of the above discussion of the server  102 &#39;s procedure, only a few aspects need be discussed here. The client  104  can maintain a log of its own requests similar to the server  102 &#39;s resource allocation log  600  of FIG. 6. The status of feature requests, including their level of support if appropriate, can be displayed to a user of the client  104  as indicated in steps  716  and  720  of FIG. 7 b.    
         [0044]    The above discussion focuses on the expected course of an exchange between the server  102  and the client  104 . The following table illustrates some of the unexpected things that can occur and how the client  104  should react.  
                                             Potential Responses That the Client Should Be Prepared       to Handle When Requesting a Feature            Response   Meaning   Appropriate Handling               Transaction timeout.   Negotiation has failed.   Fall back to not using the       Invalid response.       requested feature on this       Response with no       link.       indication of the       requested feature.       Response with an       invalid indication of the       requested feature.       400   The server does not support   Fall back to not using the           the NEGOTIATE method at   requested feature on this           this point in time or fails to   link.           recognize the method as           valid.       405, 501   The server does not support   Fall back to not using the           the NEGOTIATE method.   requested feature on this               link.       488, 606   The server does not support   Fall back to not using the           the requested feature.   requested feature on this               link.       403   The server is denying the   Close the connection. Open           request.   a new connection and do               not request the feature. Do               not use the requested               feature on this link.       408, 480, 504   Timeout.   Retry after a suitable delay.               Multiple timeouts should               result in closing the               connection and raising an               appropriate alarm. This               indicates loss of               connectivity to the server.       1xx   Provisional response.   Ignore.       2xx   Success.   Enable the requested feature               for this link.       3xx   The server is redirecting the   Ignore. Fall back to not           request.   using the requested feature               on this link.       4xx, 5xx, 6xx   Other errors.   Ignore. Fall back to not               using the requested feature               on this link.                  
 
         [0045]    In view of the many possible embodiments to which the principles of the present invention may be applied, it should be recognized that the embodiments described herein with respect to the drawing figures are meant to be illustrative only and should not be taken as limiting the scope of the invention. For example, those of skill in the art will recognize that the illustrated embodiments can be modified in arrangement and detail without departing from the spirit of the invention. Although the invention is described in terms of software modules or components, those skilled in the art will recognize that such may be equivalently replaced by hardware components. Therefore, the invention as described herein contemplates all such embodiments as may come within the scope of the following claims and equivalents thereof.