Methods and apparatus for sharing computational resources

[0001] Not Applicable

[0002] (Provisional Applications Filing: 60/173,604 Filing date: Dec. 29, 1999 and 60/174,697 Filing date: Jan. 6, 2000)

[0003] Not Applicable

[0004] A computer listing, 17 pages in length is attached in paper form. A microfiche version will be submitted within 10 days.

[0005] 1. Field of the Invention

[0006] This present invention relates to the field of client-server communications and more specifically to regulating use of a server by a client or clients.

[0007] 2. Description of Prior Art

[0008] Servers attached to a public data network such as the internet are capable of providing to Clients dynamically computed or selected data in addition to static graphics and textual material. Servers are a limited resource and their owners and managers often desire to limit or apportion their use among Clients.

[0009] A common mechanism is to require that each User of a Client be associated with a User ID which is mapped to a Client-User Account which has associated limits on resource utilization. Association with the Account may be established by Client-User submission of an identifier and password, or by other means such as completing a registration form, or clicking on a personalized link in an email, or simply using the Client-User's unique internet email address. The account information is usually kept in a database or file associated with the Server and not under control of the Client. This scheme has the following limitations.

• • [0010] 1. Additional disk and CPU resources are required to maintain a User Account Database.
  • [0011] 2. The User Account Database may become a performance bottleneck, particularly when multiple Servers are added to support a number of Clients, or when the Servers are geographically distributed or otherwise remote from the User Account Database.

[0012] As an alternative, User Account information can be stored in the Client (Client Storage). However, even if this account information is encrypted or obfuscated to inhibit manual editing, a User may be able to prevent it from being updated and so prevent the account information from accurately reflecting resource use.

[0013] Additional problems are created when Server resources are publicly usable (as is the case with a web server available on the public internet) or semi-publicly usable (as is the case with a web server attached to a corporate WAN or internet with large numbers of users). Without some kind of unforgeable identifier, resource management is easily evaded.

[0014] The following books/documents provide relevant background and are incorporated by reference:

• • [0015] “CGI Programming on the World Wide Web”, Shishir Gundavaram, © 1996 O'Reilly & Associales, Inc.
  • [0016] “The Essential Client/Server Survival Guide, Second Edition”, Orfali, Harkey and Edwards, © 1996 John Wiley and Sons
  • [0017] “Programming Perl”, Larry Wall & Randal L Schwartz, © 1991 O'Reilly & Associates, Inc. and 2^nd edition, Larry Wall, Tom Christiansen & Randal L. Schwartz, © 1996 O'Reilly & Associates, Inc.
  • [0018] “Java in a Nutshell, A Desktop Quick Reference for Java Programmers”, David Flanagan, © 1996 O'Reilly & Associates, Inc. and 2^nd edition © 1997 O'Reilly & Associates, Inc.
  • [0019] “HTML: The Definitive Guide”, Musciano & Kennedy, © 1996 O'Reilly & Associates, Inc.
  • [0020] “JavaScript: The Definitive Guide, 2^nd edition”, David Flanagan, © 1996-7 O'Reilly & Associates, Inc.
  • [0021] “Dynamic HTML: The Definitive Reference”, Danny Goodman, © 1998 O'Reilly & Associates, Inc.
  • [0022] RFC 1945 (HTTP 1.0)/2048 (HTTP 1.1)/etc., IETF (Internet Engineering Task Force)
  • [0023] RFC 1866 (HTML 2.0), IETF
  • [0024] HTML 3.2 and 4.0, W3C (World-Wide Web Consortium)
  • [0025] Perl MD5 library

[0026] As used in this document, the following words with capitalized first letters have special meanings:

• • [0027] A Computer includes any number and organization (cluster, array, etc.) of CPUs, memory/storage/communication devices, etc. and whose function includes the processing of information.
  • [0028] A Client is a Computer that is capable of accepting input from and providing output to a User. A Client may also be a Server.
  • [0029] A Server is a Computer that provides computational, data storage, communication or other services for at least one (and usually more than one) Client. A Server may also be a Client.
  • [0030] A User is an individual or process in control of an application or process executing on a Client (Client-User).
  • [0031] One Client can have multiple Users.
  • [0032] A Network includes all proxy servers, gateways, routers, communication channels, cabling, etc. that comprise a communication medium between two Computers, such as a private, local network or a public network such as the internet.
  • [0033] A Unique Identifier is a token (a collection of letters, digits and other symbols) that with high probability (>99%) is uniquely associated with a single User. For example, a uniformly-chosen 64-bit random number is considered a Unique Identifier for the purposes of this definition, because the probability is very small (<1%) that two users could be assigned the same number. A Unique identifier does not necessarily contain or point to personal information about the user, i.e., an anonymous user can be assigned a Unique Identifier.
  • [0034] A Browser is a Client program that at least a) accepts data in the form of a display list (e.g. HTML, XML, etc.) and b) wherein at least one of the interpretable display list elements is a “hyperlink” having the capability to “link” to display list data on Servers other than (and in addition to) that which provide the list containing the link. c) uses an intrinsically stateless, file-oriented protocol (e.g. HTTP, FTP, etc.) to retrieve objects named in the display list (e.g. GIF, JPG). Typical Browsers have many other capabilities in addition to these. The words “link” and “hyperlink” are standard terms of art within the field of HTML, HTTP and the WWW.
  • [0035] Form Structure Data are those elements of a fetched Browser display list (e.g. <FORM> tag and associated elements) that create corresponding form elements in which data can be entered and submitted to a Server (such submitted data is Form Data)

[0036] Related inventions: Montulli, Pat. No. 5,774,670 and White Pat. No. 6,049,877.

[0037] Systems, methods and computer media instructions are disclosed that enable the storage or caching of server account information on a client by clients that have a mechanism for the storage and modification of named or enumerated server data. An example of such an application and mechanism would be a web browser with the ability to store “cookies”. Another example might be a web browser with the ability to install public-key encryption certificates (or both cookies and certificates). A less common example might be a graphical browser coupled with a second application that can save data at server instigation, such as an FTP server. The account information is used to limit user access to server resources. Storing account information on the client implies it need not be stored on the server (or, in some cases, that a smaller “auditing” database be used), thereby conserving server resources and scaling more easily to a multi-server system.

[0038] The account information may be stored on the client in an encrypted or obfuscated form to discourage user modification. To process a server operation subject to account limitations, the server first reads and validates the existing account information from the client, then updates it with an (worst-case) estimate of the resources to be used. It again reads and validates the updated account information to verify the account information was successfully updated. If this second verification is successful AND the verified updated account information indicates completion of the operation will not exceed usage limits the operation is performed. The account information may be checked against limits before the cookie is updated. Optionally, failed or cancelled operations can credit the user account. To prevent reuse of the account information, a timestamp may be updated along with account information and server operations not performed unless the timestamp indicates the account information has been freshly updated. The mechanism may be thought of as “pay in advance”.

[0039] Though the methods of the previous paragraph are highly inconvenient for a user to circumvent, they can be circumvented. Consequently, additional methods are disclosed for the optional use of a “sampling” database and/or for periodic multi-server usage log comparison to deter abuse of these systems, methods and instructions.

[0040] Further methods are disclosed for initializing The account information in such a way that is time-consuming and/or inconvenient so that a user cannot just delete the stored account information and start over. A simple delay is demonstrated, in conjunction with the (optional) presentation of a disclaimer. A registration form requiring significant data entry or even a quiz would be obvious alternatives to the preferred embodiment and within the scope of the attached claims.

[0041] It is therefore an object of the present invention to store information about Client-User use of Server resources on the Client (in Client Storage) so to be accessible to a single or multiplicity of Servers without requiring a central database.

[0042] It is a further object of the present invention to provide methods that use Client Storage in a manner that helps ensure the said Client-User usage information is up-to-date.

[0043] It is a still further object of the present invention to encode said Client-User usage information in such a manner that it cannot be forged or easily reused by the client.

[0044] It is still further object of the invention to disclose optional methods of auditing (sampling).Client-User usage information to help thwart sophisticated attacks on the integrity of the foregoing methods.

[0057] Program listings for the methods here described are attached in the attached Listings, pages 1-17. These listings and the following description of the preferred embodiment may be phrased in terms of HTML, Java, Perl and HTTP, but straightforward conversion to other markup languages (including, but not limited to XHTML, XML, MathML, VRML, etc.) and programming languages is anticipated.

[0058] The present invention principally achieves its objective of semi-securely storing account information on the client by a mechanism that may be summarized as “pay-in-advance”: In the preferred embodiment, an account “cookie” is maintained in the browser which is modified in advance of performing an action subject to account limit(s), rather than afterwards. To prevent the same cookie from being resubmitted, a timestamp is encoded in the cookie data that will expire within a few seconds of when the cookie is first sent to the browser (the few second limit is to allow for network congestion and possible user interaction in accepting the cookie. The (simplified) normal sequence is 1) request operation, 2) update account cookie as if operation had been completed, 3) redirect browser to new URL (which causes retransmission of cookie) 4) compare newly updated cookie against account and staleness limits, 5) if OK, process operation. It is possible that the operation could fail through no fault of the user, and in such case the account information could be credited to reflect such failure. Though this feature is not implemented in the attached listings, what is required is to simply decrement “usage” and send the adjusted cookie along with the failure notification page.

[0059] An example client user interface demonstrating the disclosed methods in the simplest case (Single Server, FIG. 0A) and using an HTTP and Java-compatible web browser is attached in the drawings (FIG. 1-5) and described below. The user interface happens to be that of a PCB impedance extractor, but the particulars of the computation to be performed and the user interface are irrelevant. The user interface appears essentially the same for all four illustrated embodiments (FIG. 0a-0d), although the underlying methods vary.

• • [0060] 1) If the user has never visited before (i.e., has no valid account information), they are presented with a disclaimers/term of use page.
    • [0061] See FIG. 1 and FIG. 0A, step 0
  • [0062] 2) If the user clicks “DECLINE” a regrets page is shown. See FIG. 2A (declined.html).
    • [0063] If the user clicks “ACCEPT”, account information is initialized (in this example, such information is stored in a “cookie”) on the client machine. See FIG. 0A, steps 1&2. If storage of the account information is not successful, the interface returns to 1).
    • [0064] If the account information is successfully initialized, the full user interface is shown. See FIG. 2B and FIG. 0A, step 3. The example interface uses a Java applet for user input with HTML output but which could be just as easily implemented using a purely Java, HTML or XML interface. This interface is composed of normal browser/applet elements (pull-down menus, buttons, text fields, etc.) and capabilities.
  • [0065] 3) After the user has selected appropriate input settings, server computation is initiated. See FIG. 0A, step 4. In this example, “Execute” is clicked.
    • [0066] Data is saved on the server. An optional message, or messages is/are displayed while the data is saved. In this example, “Saving data . . . ” is displayed in a dialog box and in the browser status line until the data has been successfully saved. See FIG. 3.
  • [0067] 4) After the data is saved, a new page is displayed (in the preferred embodiment, this page is displayed/opened in a separate window) indicating that “Processing . . . ” is taking place, accompanied by updated account information (in a “cookie”) and an implicit (“refresh”) request to direct the Client-User application to fetch a new page. See FIG. 4B and FIG. 0A, step 5.
  • [0068] 5) The browser automatically fetches the new page implicitly communicated in the previous step while echoing the updated account information (“cookie”) it received in the previous step. See FIG. 0A, step 6.
    • [0069] If the user's account information is invalid (missing, corrupt, inauthentic or obsolete), or the user has exceeded his quota for use of this resource, an error message (../../htmlStackup/overuse.html) is displayed and computation does not proceed. See FIG. 4A and FIG. 0A, step 7.
    • [0070] If the user's account information is present, complete, authentic and timely and the requested operation is within the limits allowed in the user's account information, the operation is actually performed. During this time, a message such as FIG. 4A may be displayed.
  • [0071] 6) The results of the computation are saved in a local file and formatted for return and display to the Client-User. The results window is refreshable by the user without reinitiating computation, because the results have been saved in a file. See FIG. 5.

[0072] Though the fundamental mechanisms and user interface appear similar across the four embodiments diagrammed in FIGS. 0A-0D, there are underlying differences. All embodiments show a Primary (web) Server (although in reality, there could easily be a plurality of such servers) that performs the following steps of account initialization and transmission of the user interface data:

• • [0073] 0) The Client-User directly retrieves the disclaimer/registration page, or attempts to retrieve a page containing an interface to a Computational Resource under control by disclosed Server methods, and is redirected to the disclaimer/registration page because of the lack of a valid account cookie.
    • [0074] Ordinarily, a disclaimer page serves only the legal function of informing a potential user of contractual obligations required to obtain access to the software used. In the preferred embodiment, however, such pages serve a second purpose as a “delay” page—a mechanism that requires the user to do something inconvenient in order to create a new account in those situations where Server access is not controlled by passwords or unique identification. If unique identification or passwords are used such delay may be unnecessary. The attached listings (acceptdecline.pl) demonstrate a mechanism of delaying 15 seconds, however, the delay is actually measured from when the disclaimer page was generated, rather than simply being fixed. To achieve this a timestamp (“token”) is generated and transmitted with the disclaimer page with said timeslamp being returned when the form is submitted. This allows the disclaimer page to hide the download time of the applet—so the delay effectively runs concurrently with any download time (such as a large jar file).
  • [0075] 1-3) If the Client-User submits the form via the Accept button, a new account cookie is created and transmitted in an HTTP header along with a Location: redirect to the user interface page (ci.pl, CrossSection.jar) for the controlled resource (in the attached diagrams, a 2D PCB Impedance Calculator). As mentioned above, a Client-User cannot directly access this page without a valid account cookie because said page is generated from a script that checks for the presence of a valid account cookie.
    • [0076] If the Client-User clicks Decline, they are forwarded to a regrets page and no account cookie is sent.

[0077] Once, an account cookie has been created and the user interface presented to the Client-User, subsequent steps differ between the 4 embodiments.

Embodiment 0A

[0078] In the preferred embodiment, a single web Server handles all transactions with the Client (although secondary graphics or advertising may be stored on Servers located elsewhere in the Internet). The Server contains methods to execute the following steps.

• • [0079] 4) Once the Client-User has access to the computational resource interface, they may use it as any ordinary interactive interface (HTML, Java, JavaScript, etc.) up to the point where an operation is requested that uses a Server resource subject to limits controlled by the methods of the present invention. In that case, the data needed to complete the operation may be separately submitted via a CGI/RMI HTTP (etc.) form and saved in a temporary file (save.pl), identified by the unique ID stored in the account cookie.
  • [0080] 5) A calculation using this saved data is then requested (calculate.pl). The Server returns a preliminary result page for this form submission that includes an updated account cookie and a redirection request (e.g. META REFRESH=) to the page that actually performs the calculation (getresults.pl). An “Operation in progress” message may optionally be part of this preliminary result page, and is, in fact, a reason this step is separate from the step that follows (getresults.pl).
    • [0081] Steps 4 and 5 (save.pl and calculate.pl) may be combined into a single step. In a pure HTML interface, this would be likely, however, the example interface uses a mixture of Java and HTML and so it is useful to separate file saving, for which access to cookies is not necessary, from computation, which requires that cookies be set. Java does not have a cookie mechanism, but some browsers have a connection between Java and JavaScript that allows Java applets to set cookies, and this is a possible alternative implementation.
  • [0082] 6-7)The Client-User application acts upon the redirection request and fetches the named page (getresults.pl). The request is normally accompanied by updated account information from the previous step. If a results file already exists that corresponds to the updated account information, that results file is processed into a form suitable for display to the Client-User.
    • [0083] If a results file is not present, but the account information is present, valid, fresh (good timestamp) and indicates that the operation is within account limits, the operation is performed and a results file is created. Then the results file is processed as returned to the Client-User (as in the previous paragraph).
    • [0084] If a results file is not present, and the account information is missing, invalid or stale (bad timestamp) the operation is not performed and an optional error message is returned. If the account information is otherwise valid but indicates the user has exceeded their account limits, an overuse page is returned.
      Embodiment 0B

[0085] This embodiment differs from Embodiment 0A in that the actual restricted computation is performed on a different server from the server communicating with the Client, that is, the primary Server accepts data and then chooses one-of-N (at least one) Private Computation Servers to execute the actual core computation. The primary Server script forwards (and may modify) all Client-submitted information to the one-of-N Private Computation Servers and forwards (and may modify) any results from Computation Server to Client. This difference between 0A and 0B occurs at step 7.

[0086] The algorithm by which the one-of-N servers is chosen is a known art, and may be a simple round-robin selection, or a round-robin whereby busy servers are skipped over in favor of the next available server.

[0087] In the illustrated example, the original implementation consisted of two different Servers. The primary server was running just a web server, the other was running a web server plus a field extraction CAD package. Account management was performed by the Primary Server with the computationally intensive field extraction performed on the second server. The information was packaged by the Primary Server into a form and submitted via an HTTP POST mechanism to a CGI script running on the second (computation) Server. That second server script converted the form data into a batch job for the CAD package and returned (formatted) results to the Primary (web) Server. Additionally, because the second Server could only perform one extraction at a time, the Primary Server contained methods that used semaphores to sequentially process a multiplicity of simultaneous, independent Client-User requests.

Embodiment 0C

[0088] This embodiment also differs from Embodiment 0A in that the actual limited computation is performed on a different server from the primary Server, but also differs from Embodiment 0B in that both the Primary Server and each Computation Server are visible to, and communicate with the Client. Embodiment 0C differs from 0A and 0B at step 7.

[0089] In embodiment 0C, Client-User data is forwarded to one-of-N computation servers chosen by possibly similar means and possibly similar mechanisms as in 0B, but then the Client-User application is forwarded to retrieve results directly from the selection computation server. This requires that each computation server have methods for communicating with the Client (e.g. must be a web server), and must have methods to reformat computation results for display on Client . An additional method not present in 0A or 0B must exist—the Client is authenticated to the Computation Server by a match between the Client-User account information and the data that was separately forwarded from the Primary Server and stored on the selected Computation Server.

Embodiment 0D

[0090] The topology for this embodiment is identical to 0C and as with 0C the actual limited computations are performed on separate Computation Server(s) that are visible to, and communicate with, the Client. Embodiment 0D differs from 0A, 0B and 0C at step 4-7. More than just computation is offloaded to each Computation Server in embodiment 0D.

[0091] In embodiment 0D, when the client submits calculation data (step 4), the Primary Server forwards that request to one of the N Computation Servers, chosen by means (e.g. round-robin) similar to 0B and 0C. All further processing is performed by the Computation Server (as per 0A, steps 5-7), including methods for

• • [0092] 1) accepting and storing the Client data directly from Client
  • [0093] 2) authenticating and updating the Client-User account information.
  • [0094] 3) checking updated Client-User account information to make sure requested operation is within limits.
  • [0095] 4) (optionally) formatting Client data for processing and post-processing data for display by Client-User application.

[0096] A hybrid between 0C and 0D is possible in which steps 4 and 5 are identical to 0C, but then the Primary Server forwards the saved Client data to the chosen one-of-N Computation Servers, which authenticates the updated account information and performs the requested operation.