a2) United States Patent
`US 6,351,775 B1
`(10) Patent No.:
`
`Feb. 26, 2002(45) Date of Patent:
`Yu
`
`US006351775B1
`
`(54)
`
`(75)
`
`LOADING BALANCING ACROSS SERVERS
`IN A COMPUTER NETWORK
`
`Inventor: Philip Shi-Lung Yu, Chappaqua, NY
`(US)
`
`(*) Notice:
`
`(73) Assignee:
`
`International Business Machines
`Corporation, Armonk, NY (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(6) by 0 days.
`(21) Appl. No.: 08/866,461
`.
`(22)
`Filed:
`May30, 1997
`(SL)
`Tint. C1. cece cece eseeeeeseeeeeeneneeeees G06F 15/173
`(52) US. Ch eee 709/238; 709/239; 709/240;
`709/241; 709/242; 370/237; 370/400
`(58) Field of Search oo... 709/242, 239,
`709/240, 241, 238; 370/237, 400
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,371,852 A
`12/1994 Attanasioet al.
`5,517,620 A *
`5/1996 Hashimotoet al.
`......... 709/242
`5,526,414 A *
`6/1996 Bedard et al.
`.......
`... 379/221
`
`8/1996 Shachnaietal.
`........... 709/219
`5,544,313 A *
`
`ve 709/239
`.......
`5,828,847 A * 10/1998 Gehret al.
`. 370/231
`5,864,535 A“ 1/1999 Basilico.....
`
`7/1999 Regnier et al.
`vee 379/221
`5,930,348 A :
`001790 A * ooo x“dadetal™ aes,
`FOREIGN PATENT DOCUMENTS
`8-214063
`8/1996
`
`OTHER PUBLICATIONS
`
`JP
`
`M. Colajannict al., “Scheduling Algorithms for Distributed
`Web Servers”, RC 20680 (91683) Jan. 6, 1997, Computer
`Science/Mathematics, Research Report, 29 pages.
`
`T. Brisco, “DNS Support for Load Balancing”, Apr. 1995, 6
`pages, Network Working Group, Rutgers University.
`Daniel M.Diaset al., “A Scalable and Highly Available Web
`Server”, (not dated), 8 pages, IBM Research Division,T.J.
`Watson Research Center, Yorktown Heights, N. Y. 10598.
`Eri D. Katz et al., “A scalable HTTP server: The NCSA
`prototype”, 1994, pp. 155-164, vol. 27, Computer Networks
`and ISDN Systems.
`* cited by examiner
`Primary Examiner—Krisna Lim
`(74) Attorney, Agent, or Firm—F. Chau & Associates, LLP
`67
`ABSTRACT
`Adynamic routing of object requests among
`a collection or
`cluster ofservers Factors the caching oificiency of the servers
`and the load balance or just the load balance. The routing
`information onserver location can be dynamically updated
`by piggybacking meta information with the request
`response. To improve the cachehit at the server, the server
`selection factors the identifier (e.g. URL) of the object
`requested. A partitioning method can map object identifiers
`into classes; and requester nodes maintain a server assign-
`ment table to map each class into a server selection. The
`class-to-server assignment table can change dynamically as
`the workload varies and also factors the server capacity. The
`requester node need only be informed on an “on-demand”
`basis on the dynamic change of the class-to-server assign-
`ment (and thus reduce communication traffic).
`In the
`Internet, the collection of servers can be either a proxy or
`Web server cluster and can include a DNS and/or TCP-
`router. The PICS protocol can be used by the server to
`provide the meta information on the “new” class-to-server
`mapping whena request is directed to a server based on an
`invalid or obsolete class-to-server mapping. DNS based
`routing for load balancing of a server cluster can also
`benefit. By piggybacking meta data with the returned object
`to reassign the requester to another server for
`future
`requests, adverse effects of the TTL on the load balance are
`overcome without increasing traffic.
`
`75 Claims, 15 Drawing Sheets
`
`
`203
`267,
`Requestor K ~
`“T|object request
`generation
`
`
`assignment
`table
`270
`
`202
`Requestor 1
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`)
`205 servercluster,1
`
`
`208 server M>
`235 Arbitrator ~
`
`
`212
`
`N} object request
`i
`=
`Q
`248s,
`DAS.|
`
`handler
`208
`mappingrequest}
`
`
`2A
`Server 1]
`hander
`
`
`object handler
`250.
`240
`statistics &
`v
`
`statistics
`©
`
`
`
`a8
`A reporting
`evaluation
`220,
`A 1225.
`230
`cache manager
`assignment
`7
`= 242||table
`
`assignment
`table
`228
`
`210.4
`
`27
`
`201
`Network
`
`<4,
`
`Data Co Exhibit 1036
`Data Co Exhibit 1036
`Data Co v. Bright Data
`
`Data Co v. Bright Data
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 1 of 15
`
`US 6,351,775 B1
`
`105 Network
`
`
`110
`Requestor1
`
`
`
` 103 server cluster
`
`Requestor K
`
`OO
`
`5
`
`OO
`
`127
`
`Fig.1
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 2 of 15
`
`US 6,351,775 B1
`
`203
`Requestor K~
`
`267.
`
`object request
`generation
`
`assignment
`
`table
`
`202
`Requestor 1
`970
`
`
`
`201
`Network
`
`
`
`205 server cluster ~
`208 server M
`
`235 Arbitrator
`
`12
`
`object request
`handler
`
`assignment
`table
`
`S
`mapping request
`handler
`
`250
`
`statistics &
`evaluation
`
`225
`
`assignment
`table
`
`
`
`

`

`Feb. 26, 2002
`
`Sheet 3 of 15
`
`US 6,351,775 B1
`
`Ta €=IN‘9L=N
`
`Toran
`oy
`
`ol
`
`e
`
`U.S. Patent
`
`
`
`giqe,juawubissy
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 4 of 15
`
`US 6,351,775 B1
`
`Wait for input
`
`410
`
`
`
`request
`?
`
` Object
`
`
`
`Object
`
`request
`
`handler
`
`
` statistics
`Collection
`
`
`Object
`handler
`
`Statistics
`reporting
`routine
`
`
`
`
`
`assignment
`
`table
`
` Miscellaneous
`
`
`routine
`
`Fig. 4
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 5 of 15
`
`US 6,351,775 B1
`
`Object Handler
`
`Object class
`assigned to
`this server
`
`515
`
`Cache
`
`manager
`
`Dynamic
`reassign
`
`
`
`routine
`
`
`
`
`
`
`
`Return object
`to requester
`
`
`
`Fig. 5
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 6 of 15
`
`US 6,351,775 B1
`
`Dynamic Reassign Routine
`
`610
`
`Determine the server id
`to handle the object
`class from assignment
`table
`
`in the object header
`
`Insert "reassign"
`label with category
`value equal to the
`appropriate serverid
`
`Fig. 6
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 7 of 15
`
`US 6,351,775 B1
`
`Object Request Handler
`
`
`
`
`
`
`local buffer
`?
`
`Send request
`to get
`object
`
`720
`
`Object class
`assigned to
`this server,
`
`Dynamic
`reassign
`routine
`
`Return object
`to requester
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 8 of 15
`
`US 6,351,775 B1
`
`Statistics Reporting Routine
`
`Send CS(j,i)
`i=1,...,N
`to arbitrator
`
`i=1,...,N
`
`Reset CS(j,/) to zero
`
`Fig. 8
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 9 of 15
`
`US 6,351,775 B1
`
`910
`
`Arbitrator
`
`
`920
`
`240
`
`Class-to-server
`mapping
`
`
`request
`
`
`
`
`
`request
`handler
`
`930
`
`Timer
`Statistics
`
`expires
`&
`
`evaluation
`
`
`
`
`Wait for input
`
`
` Mapping
`
`
`routine
`
` Send assignment
`
`
`table update
`requestto all
`servers
`
`Fig. 9
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 10 of 15
`
`US 6,351,775 B1
`
`Statistics & Evaluation Routine
`
`1010
`
`Send statistics collection requests
`to get CS(/,/), for i=/,...,N
`
`1020
`
`1030
`
`1040
`
`j=
`
`Calculate
`SA(j)<——>__ CA(i)
`
`from server j, j=/,...,!M
` Calculate
`
`CA(i)~<— 2 CS(j,i),/<isN
`for isjsM OCA)
`
`1060
`im
`
`1050
`
`Yes
`Reassignmentroutine
`
`1070
`
`Fig. 10
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 11 of 15
`
`US 6,351,775 B1
`
`Reassignment Routine
`
`1110,
`
`
`
`\\
`1115
`‘S
`
`TOo~=«— {| SA() > TH}
`y
`Let A be the index of the most loaded
`server in TO
`
`
`
`7
`
`K
`
`
`
`
`
`
`
`
`1120
`\
`
`TU=<— {j| SAG) <TH}
`
`1165
`1125
`\
`
`Yes
`
`
`\\
`
`
`Let / be the index of the least loaded
`server in TU
`
`
`
`Let i be the class assigned to server k
`with the smallest class load
`
`
`
`Reassign class 7 to server /
`from server k
`
`1145
`
`* Update SA(7) and SA(&)
`
`1155
`
`Fig. 11
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 12 of 15
`
`US 6,351,775 B1
`
`Mapping Request Handler
`
`1210
`
`1230
`
`Map objectid to class
`
`
`
`mapping from assignment
`table
`
`1220 Determine class-to-server
`
`
`
`Send class to server
`mapping to requester
`
`Fig. 12
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 13 of 15
`
`US 6,351,775 B1
`
`Requester
`
`1310
`\h
`
`
`Wait for input
`
`
`
`
`
`
`
`Object
`
`
`request
`
`
`
`
`Object
`
`
`
`request
`Object
`
`
`
`generation
`returned
`
`
`
`
`
`\ M
`
`
`iscellaneous
`
`
`handler
`Reassign
`
`label Send object
`
`
`request to
`
`
`specified server|1365
`
`
`
`
`
`Update
`
`
`assignment
`
`table
`
`
`Process object
`Fig. 13
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 14 of 15
`
`US 6,351,775 B1
`
`Object Request Generation
`
`1410
`
`Mapobjectid to class
`to arbitrator Send object
`
`
`
`
`
`Class to server
`Issue
`assignment
`mapping
`
`
`request
`available
`
`
`
`
`
`request to
`specified server
`
`Fig. 14
`
`

`

`U.S. Patent
`
`Feb. 26, 2002
`
`Sheet 15 of 15
`
`US 6,351,775 B1
`
`105 Network
`
`
`
`110
`Requestor 4
`
`
`103 server cluster
`C) 112
`
`
`
`164
`
`
`
`
`
`
`Requestor K
`
`
`162
`
`TCP-router >
`163
`VON)
`
`DNS
`
`Fig.15
`
`

`

`US 6,351,775 B1
`
`1
`LOADING BALANCING ACROSS SERVERS
`IN A COMPUTER NETWORK
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`The present invention is related to U.S. Pat. No. 6,078,
`943,filed Feb. 7, 1997 and issued on Jun. 20, 2000 entitled
`“A Method and Apparatus for Dynamic Interval-based Load
`Balancing,”by P. Yu, and (provisional) Ser. No. 60/031,849,
`filed provisionally on Dec. 5, 1996, entitled “A Computer
`System and Method for Load Balancing with Selective
`Control,” by Dias, et al. The above-identified U.S. Pat. No.
`6,078,943, the above-identified provisional application and
`the present invention are commonly assigned to the Inter-
`national Business Machines Corporation of Armonk, N-Y.
`The descriptions set forth in the above-identified issued
`patent and provisional application are hereby incorporated
`by reference in their entirety into the present application.
`
`FIELD OF THE INVENTION
`
`The present invention relates generally to providing load
`balancing across a collection (or cluster) of servers such as
`proxy servers and Webservers in the Internet environment.
`A more particular aspect of the present invention relates to
`a method of updating routing information using meta data
`piggybacked with the response to client
`requests. Yet
`another aspect is related to a load balancing method which
`also optimizes caching efficiency.
`GLOSSARY OF TERMS
`
`While dictionary meanings are also implied by certain
`terms used here, the following glossary of some terms may
`be useful.
`Internet
`
`The network of networks and gateways that use the
`TCP/IP suite of protocols.
`Client
`
`A client is a computer which issues commandsto the
`server which performs the task associated with the com-
`mand.
`Server
`
`Any computer that performs a task at the command of
`another computer is a server. A Web server typically sup-
`ports one or more clients.
`World Wide Web (WWW or Web)
`The Internet’s application that lets people seeking infor-
`mation on the Internet switch from server to server and
`
`database to database by clicking on highlighted words or
`phrases of interest (hyperlinks). An Internet WWW server
`supports clicnts and provides information. The Web can be
`consideredas the Internetwith all of the resources addressed
`
`as URLsand which uses HTMLto display the information
`corresponding to URLs and provide a point-and-clickinter-
`face to other URLs.
`Universal Resource Locator (URL)
`Away to uniquely identify or address information on the
`Internet. Can be considered to be a Web documentversion
`of an e-mail address or a fully-qualified network file name.
`They can be accessed with a Hyperlink. An example of a
`URLis “http://www.philipyu.com:80/table.huml”. Here, the
`URLhas four components. Starting from the left, the first
`specifies the protocol to use, separated from therest of the
`locator by a “:”. Next is the hostname or IP address of the
`target host; this is delimited bythe “//’ on the left and on the
`right by a “/” or optionally a “:”. The port number is
`optional, and is delimited on the left from the hostname by
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`ce pri
`66,99
`“/’. The fourth componentis the
`“:” and on the right by a
`a
`actual file name or program name. In this example, the
`“ html” extension meansthat this is an HTMLfile.
`HyperText Markup Language (HTML)
`HTMLis a language which can be used, among other
`things, by Web servers to create and connect documentsthat
`are viewed by Web clicnts. HTML uses Hypertext docu-
`ments.
`
`Hypertext Transfer Protocol (HTTP)
`HTTPis an example of a stateless protocol, which means
`that every request from a client
`to a server is treated
`independently. The server has no record of previous con-
`nections. At the beginning of a URL, “http:” indicates the
`file should be retrieved using http.
`Internet Browser or Web Browser
`A graphical interface tool that runs Internet protocols such
`as http, and display results on the user’s screen. The browser
`can act as an Internet tour guide, complete with pictorial
`desktops, directories and search tools used when a user
`“surfs” the Internet. In this application the Web browseris
`a client service which communicates with the World Wide
`Web.
`Client Cache
`Client caches are typically used as primary caches for
`objects accessed by the client. In a WWW environment,
`client caches are typically implemented by web browsers
`and may cache objects accessed during a current invocation,
`1e., a nonpersistent cache, ar may cache objects across
`invocations.
`
`Caching Proxies
`Specialized servers in a network which act as agents on
`the behalf of the client to locate a cached copy of an object.
`Caching proxies typically serve as secondary or higher level
`caches, because they are invoked as a result of cache-misses
`from client caches.
`HTTP Daemon (HTTPD)
`A server having Hypertext Markup Language and Com-
`mon GatewayInterface capability. The HTTPD is typically
`supported by an access agent which provides the hardware
`connections to machines on the intranet and access to the
`Internet, such as TCP/IP couplings.
`
`BACKGROUND
`
`The traffic on the World Wide Webis increasing expo-
`nentially. Proxy servers, especially at a gateway to a large
`organization or region, can comprise a collection of com-
`puting nodes. Similarly, at popular (hot) Web sites, a col-
`lection (or cluster) of computing nodesis used to support the
`access demand.
`
`To achieve good performance in a servercluster, the load
`should be balanced among the collection of nodes. This
`should be tempered by the need to optimize the cache hit
`ratio in a given serverin the cluster by localizing identical
`object requests.
`Previous work on load balancing in a multi-processor or
`multiple node environment, such as the IBM $/390 Sysplex,
`primarily focused on scheduling algorithms which select one
`of multiple generic resources for each incomingtask or user
`session. The scheduler controls the scheduling of every
`incoming task or session and there is no caching of the
`resource selection.
`
`One known method for balancing the load among geo-
`graphically distributed replicated sites is known as the
`Round-Robin Domain NameServer (RR-DNS)approach. In
`the paper by Katz., E., Butler, M., and McGrath, R., entitled
`“A Scaleable HTTP Server: The NCSA Prototype”, Com-
`
`

`

`US 6,351,775 B1
`
`3
`puter Networks and ISDN Systems, Vol. 27, 1994, pp.
`68-74, the RR-DNS method is used to balance the node
`across a set of web server nodes. Here,the set of distributed
`sites is represented by one URL (e.g., www.hotsite.com); a
`cluster sub-domainfor this distributed site is defined withits
`sub-domain nameserver. The sub-domain name server maps
`the nameresolution requests to different IP addresses (in the
`distributed cluster) in a round-robin fashion. Thus, subsets
`of the clients will be assigned to each of the replicated sites.
`In order to reduce networktraffic, a mapping requestis not
`issued for each service request. Instead, the result of the
`mapping requestis saved for a “time-to-live” (TTL)interval.
`Subsequent requests issued during the ‘IIL interval retain
`the previous mapping and hence will be routed to the same
`server node.
`
`10
`
`15
`
`4
`approach lacks the flexibility to cope with dynamic load
`changes and moreover, is not scaleable.
`Thus,
`there is a need for an improved load balancing
`method and apparatus in a server cluster which not only
`balances the load across the cluster but also optimizes the
`cache hit ratio in a given server in the cluster by localizing
`identical object requests. The present invention addresses
`such a need.
`
`There is also a need for an improved routing method
`which assigns each server to handle a subset of the object
`space dynamically according to workload conditions and
`routes object requests to the server assigned to the subspace
`associated with the object. The present
`invention also
`addresses such a need.
`
`,,
`
`A problem with the RR-DNS method is that a load
`imbalance amongthe distributed sites may result (see e.g.,
`Dias, D. M., Kish, W., Mukherjee, R., and Tewari, R., in “A
`Scaleable and Highly Available Web Server”, Proc. 41st
`IEEE Computer Society Intl. Conf. (COMPCON) 1996,
`Technologies for the Information Superhighway, pp. 85-92,
`February 1996). The load imbalance can be caused by
`caching of the association between a name andIP addressat
`various gateways, fire-walls, and domain name-servers in
`the network. Thus, for the TTL period all newclient requests ,
`routed through these gateways,
`fire-walls, and domain
`name-servers will be assigned to the single site stored in the
`cache. Those skilled in the art will realize that a simple
`reduction in the TTL value will not solve the problem. In
`fact, low TTL values are frequently not accepted by many
`name servers. More importantly, a simple reduction of TTL
`value may not reduce a load skew caused by unevenly
`distributed client request rates.
`One method of load balancing within a local cluster of
`nodesis to use a so-called TCP router as described in: “A
`
`30
`
`35
`
`Virtual Multi-Processor Implemented by an Encapsulated
`Cluster of Loosely Coupled Computers,” by Attanasio,
`Clement R. and Smith, Stephen E., IBM Research Report
`RC 18442, 1992; and U.S. Pat. No. 5,371,852, entitled
`“Method and Apparatus for Making a Cluster of Computers
`Appear as a Single Host,” issued Dec. 6, 1994 which is
`hereby incorporated by reference in its entirety. Here, only
`the address of the TCProuteris given out to clients; the TCP
`router distributes incoming requests among the nodesin the
`cluster, either in a round-robin manner, or based on the load
`onthe nodes. It should be noted that this TCP router method
`is limited to a local cluster of nodes.
`
`Morerecently, in the paper by Colajanni, M., Yu, P., and
`Dias, D., entitled “Scheduling Algorithms for Distributed
`Web Servers,” IBM Research Report, RC 20680, January
`1997, which is hereby incorporated by reference in its
`entirety, a multi-tier round robin method is described which
`divides the gateways into multiple tiers based on their
`request rates. Requests from each tier are scheduled sepa-
`rately using a round robin algorithm. This method can also
`handle a homogeneousdistributed server architecture.
`In all of the above approaches, the goal is to balance the
`load among a collection of servers. The dynamic routing
`decision does not take into accountthe identity of the object
`being requested. In other words, multiple requests for the
`same object may be routedto different servers to balance the
`load. This will result in a poor cache hit ratio which is
`especially severe for proxy servers since the potential num-
`ber of distinct Web pages referenced can be very large.
`Although in a Web servercluster, a static partition can be
`made to the Web pages wherein eachpartition is assigned a
`different (virtual) host name or IP, a static partitioning
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`SUMMARY
`
`In accordance with the aforementioned needs, the present
`invention is directed to an improved method and apparatus
`for dynamic routing object requests among collection of
`servers that takes into account either: the caching efficiency
`of the servers and load balance; or just the load balance.
`The present
`invention also has features which can
`dynamically update server routing information by “piggy-
`backing” meta information with the response to the routing
`requests. The present invention has other features which can
`improve the cache hit ratio at a server by mapping a server
`based on the identifier (e.g., URL) of the object requested
`and dynamically updating this mapping if workload condi-
`tions change. In an Internet environment, the collection of
`servers can include, but is not limited to, a proxy server
`cluster or a Web servercluster.
`
`A method having features of the present invention for
`dynamically routing object requests among, a collection of
`server nodes,
`includes the steps of: piggybacking meta
`information with a requested object; and dynamically updat-
`ing routing informationfor a server assignment according to
`the meta information.
`
`A method having features of the present invention for
`dynamic routing object requests among a collection of
`server nodes while optimizing cache hits, further includes
`the steps of: mapping an object identifier to a class; and
`assigning a server based on the class and a class-to-server
`assignmenttable.
`The present invention has still other features which can
`inform the requester node in an “on-demand”basis of a
`dynamic change in a class-to-server assignment. The class-
`to-server assignment can change dynamically as the work-
`load varies. To avoid costly broadcasting of the changes to
`all potential requesters, or forcing requesters to first obtain
`a mapping each time an request is sent,
`the server can
`advantageously continue to serve an object request even if it
`is not the one assigned to process that class. However, the
`server can indicate in a header of the returned object (or
`response), the information onthe newclass-to-server assign-
`ment.
`
`Furthermore, the present invention’s features for piggy-
`backing meta information with requested objects can also be
`applied to a conventional DNS routing in the Internet to
`improve load balancing in a server cluster. This should be
`distinguished from the concept of using an object’s URL (or
`object class) to make a server assignment (to improve the
`cache hits). DNS routing has a valid interval (TTL) for
`address mapping. The present invention has features which
`allow server assignments to be generated at an interval
`smaller than the TTL and thus better reflect
`true load
`
`conditions. Changes in server assignment can be piggy-
`
`

`

`US 6,351,775 B1
`
`5
`backed with the returned object, avoiding added traffic, so
`that future requests can be sent to the new server.
`The present invention has still other features which can
`dynamically and incrementally change the class-to-server
`assignment based on the workload demand to balance the
`load.
`
`According to yet other features of the present invention,
`in an Internet environment, the PICS protocol may be used
`to communicate various types of information. PICS can be
`used by the server to piggyback the meta information on a
`new class-to-server mapping whena requestis directed to a
`server based on an obsolete class-to-server mapping entry.
`PICS can also be used by the requester to query the
`coordinator for the current class-to-server mapping.
`Those skilled in the art will appreciate that the present
`invention can be applied to general distributed environments
`as well as the World Wide Web.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`These, and further, objects, advantages, and features of
`the invention will be more apparent from the following
`detailed description of a preferred embodiment and the
`appended drawings wherein:
`FIG. 1 is a diagram ofan Internet environment applicable
`to the present invention;
`FIG. 2 is a more detailed example of a general environ-
`ment having features of the present invention;
`FIG. 3 is an example of the “class-to-server” assignment
`table;
`FIG. 4 is an example of the server logic of FIG. 2;
`FIG. 5 is an example of the object handler of the server;
`FIG. 6 is an example of the dynamic reassign routine of
`the object handler of the server;
`FIG. 7 is an example of the object request handler of the
`server;
`
`FIG. 8 is an example ofthe statistics reporting routine of
`the server;
`FIG. 9 is an example of the arbitrator logic of FIG. 2;
`FIG. 10 is an example of the statistics and evaluation
`routine of the arbitrator;
`TIG. 11 is an example of the reassignment routine of the
`statistics and evaluation routine of the arbitrator;
`FIG. 12 is an example of the mapping request handler of
`the arbitrator;
`FIG. 13 is an example of the requester logic of FIG. 2;
`FIG. 14 is an example of the object request generation of
`the requester logic; and
`FIG. 15 is an example of the server cluster of FIG. 1,
`including a domain name-server (DNS).
`DETAILED DESCRIPTION
`
`FIG. 1 is a diagram ofan Internet environment applicable
`to the present invention. As depicted, Requesters (110-153),
`which can be include any of conventional proxy server
`nodes (118, 125-127), client workstations and personal
`computers (also called PCs) (110, 112, 120, 150-153), are
`connected to a network (105). Proxy servers, workstations,
`and PCsare well knownin the art. An example of the proxy
`server node is the Internet Connection Server (ICS) sold by
`IBM. Requesters request services from the server cluster
`(103), via the network (105). Examples of the network
`include, but are not limited to, the Internet, the World Wide
`Web, an Intranet and local area networks (LANs). Theserver
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`cluster includes multiple server nodes (161-163) to handle
`high traffic demand.It can be either a proxy server or a Web
`server cluster. The servers in the cluster can include, but are
`not limited to, products such as are sold by IBM underthe
`trademarks $/390 SYSPLEX, SP2, or RS6000 workstations.
`As is conventional, each request can be handled by any
`serverin the cluster. Typical service requests include World-
`Wide-Web page accesses, remote file transfers, electronic
`mail, and transaction support.
`Although requests can in principle be processed by any of
`the server nodes, routing requests for the same object to a
`single server node will result in a better cache hit probability
`at the same server node, and hence better performance. As
`will be described below, the present invention has features
`which not only balance the load amongthe server nodes in
`the cluster, but which also achieve a high cache hit prob-
`ability.
`By way of overview, a routing method according to the
`present invention uses a logic identifier or symbolic name
`(e.g. URT,) ofthe object in selecting the server to handle the
`request. A partitioning methodis also provided to map object
`identifiers into classes; and a requester node preferably
`maintains a class-to-server assignment table (FIG. 3) to map
`each class into a server selection. A preferred partitioning
`method is to use a conventional hashing function to hash an
`object URL into a given numberof hash classes. This hash
`function will preferably be given and knownto all partici-
`pating servers and requester nodes by anarbitrator 235 (FIG.
`2).
`
`The arbitrator 235 monitors the load of each server and
`dynamically updates the class-to-server assignment
`to
`improve the load balancing. The present
`invention also
`provides a method to inform the requester node “on-
`demand”in the event of a dynamic changeof the class-to-
`server assignment by the servers 103.
`A request from a requester node may need to traverse
`several intermediate requester nodes (i.e. proxy servers)
`before reaching the server cluster 103. For example, node
`150 needs to traverse two levels of proxy nodes, 125 and
`118, before reaching the sever cluster 103. If the server
`cluster is a proxy server cluster,
`the server selection is
`preferably done by the requesters 110-120 closest to the
`proxyserver cluster 103. In the case of a Web servercluster,
`the Web server selection may be done at the intermediate
`requesters on the path.
`The present invention also has features for efficiently
`communicating routing information between requester and
`server nodes using “piggybacked” meta-data. In a HTTP
`implementation, the information exchange can be included
`as meta-data in an object header using cxisting web proto-
`cols. PICS (“Platform for Internet Content Selection”) speci-
`fies a method of sending meta-information concerning elec-
`tronic content. PICS is
`a Web Consortium Protocol
`Recommendation (see http://www.w3.org/PICS). PICS was
`first used for sending values-based rating labels, such as
`“How much nudity is associated with this content,” but the
`format and meaningof the meta-informationis fully general.
`In PICS, meta-information about electronic content
`is
`grouped according to the “rating service” or producer-and-
`intended-usage of the information, and within one such
`group, any number of categories or dimensions of informa-
`tion may be transmitted. Each category has a range of
`permitted values, and for a specific piece of content, a
`particular category may have a single value or multiple
`values. In addition, the meta-information group (knownas a
`“PICS label’) may contain expiration information. There are
`
`

`

`US 6,351,775 B1
`
`10
`
`15
`
`35
`
`40
`
`8
`7
`tion by CPU (240). The arbitrator logic is divided for clarity
`also facilities for permitting a PICS label to apply to more
`and by way of example only,
`into several components
`than one piece of electronic content. Each PICS label for a
`including: a mapping request handler (248), andastatistic
`specific piece of electronic content may be added or
`and evaluation routine (250). These components will be
`removed from the content independently.
`described in detail with reference to FIGS. 12 and 10,
`For example, an imagefile may be sent from a server with
`respectively. The main data structure maintained is the
`a single PICS label whose “rating service”field indicatesit
`class-to-proxy assignment table (225). The operations onthe
`contains values-based rating labels according to the “Safe-
`Surf” rating system. According to the present invention, as
`class-to-proxy assignmenttable (225)will be explained with
`it passes throughan enterprise proxy, the image file may also
`the various components.
`receive a second PICS label whose “rating service” field
`Servers 1... M (206-208) can comprise any conventional
`indicates it contains class-to-server assignmentinformation.
`computing node that can handle service requests such as
`As it passes through a departmental proxy, the second PICS
`providing data/object accesses and/orfile transfers requested
`label may bestripped. Thus, the client computer may only
`by the requester (203). The server node (208) includes CPU
`sees the first PICS label. The HTTP protocol has been
`(227), memory (210) and storage devices (230) such as
`augmented with request headers and response headers that
`DASD, and/or other stable magnetic, electrical or optical
`support PICS. The technical bodies which define other
`storage. The memory (210) stores the server logic of the
`commonapplication protocols, such as NNTP, are now also
`present invention (with details depicted in FIG. 4) preferably
`considering adding PICS support. As part of these protocols,
`embodied as computer executable code which is loaded
`a list of the types of PICS labels desired may be included
`from storage (230) into memory (210) for execution by CPU
`with a request. PICS also specifies a query format for
`(227). The server node logic is divided for clarity and by
`receiving PICS information from a central
`label bureau
`way of example only, into several components: an object
`server. A sample PICS label
`is:
`(PICS-1.1 “http://
`request handler (212); an object handler (214); and a statistic
`the.rating.service” label
`for “http://the.content” exp
`reporting routine (218). These components are explained in
`“1997.07.01 T08: 15-0500” 1(n 4 s 3 v 210)) where the ‘n’
`details in FIGS. 7, 5, and 8, respectively. It also includes a
`‘s’ ‘v’ ‘TV are transmit names for various meta-information
`cache manager (220) and maintains a copy of the class-to-
`types, and the applicable valuesfor this content are 4 (for n),
`server assignment table (225).
`3 (for s), 2 (for v) and O (for 1). Only software which
`FIG. 3 provides an example of the assignmenttable (225,
`recognizes the ID “http://the.rating.service” would know
`270) for N=16 and M=3, where N is preferably the number
`how to interpret these categories and values.
`of object classes, i.c., the size of the hash or assignment
`In a preferred embodiment, two different kinds of PICS
`table, and M is the number of servers. Let Co be the
`labels are used. The first kind of PICS label, referred to as
`assignment table (225, 270) that assigns class k to server
`a “reassign” label or (R-label), is used by the server node in
`Ck). Referring again to FIG. 2, notonly the arbitrator (235)
`the cluster to indicate the “current” server assignment for the
`and each server (206,208) node in the cluster, but also the
`object class of the returned object. The second kind of PICS
`requester nodes (202,203) can maintain a copy of the
`label, referred to as an “assignment” label or (A-label), is
`assignment table (225, 270). The table (270) at the request-
`used by the requester to determine the current server assign-
`ers are generally are not up-to-date, ie., not synchronized
`ment of the URL of an object from the arbitrator which
`with the server (208) or arbitrator (235) assignment tables
`provides the label bureau function in this case.
`(225). The present invention has features which eliminate
`T'IG. 2 depicts a more detailed example of a network (201)
`the need to send costly update