Computer Science
`
`Implementing Distributed Server Groups for the
`World Wide Web
`
`Michael Garland Sebastian Grassia Robert Monroe Siddhartha Pun
`
`25 January 1995
`CMU-CS-95-1 14
`
`199O317 138
`
`Carnegie
`Mellon
`
`Approved for public ze1eae
`Dfatiibutjo Unlimited
`
`Petitioner IBM – Ex. 1012, p. 1
`
`

`
`Implementing Distributed Server Groups for the
`World Wide Web
`
`Michael Garland Sebastian Grassia Robert Monroe Siddhartha Pun
`
`25 January 1995
`CMU-CS-95-l 14
`
`School of Computer Science
`Carnegie Mellon University
`15213-3890
`
`Pittsburgh Pennsylvania
`
`Abstract
`
`very popular facility
`
`for the dissemination of
`
`The World Wide Web WWW has recently become
`information As
`load Single
`result of this popularity
`rapidly increasing traffic
`is experiencing
`load being placed upon them To alleviate this
`machine servers cannot keep pace with the ever greater
`distributed Web server group The server group can effectively bal
`problem we have implemented
`its members within about 10% of optimal and client response time is no
`load amongst
`ance request
`improved because the measured cli
`worse than in the single server case Client response time was not
`ent traffic consumed all available network throughput
`The distributed operation of the server groups is
`to standard Web clients
`
`it
`
`completely transparent
`
`in part by the Wright Laboratory Acronautical SystemsCenler Air Force Materiel Command USAF
`This research is sponsored
`and the Advanced Research Projects Agency ARPA under grant P33615-93-1-1330 Thc US Government
`is authorized to repro
`duce and distribute reprints for Government purposes notwithstanding any copyright notation thereon Support also came from the
`Air Force Materiel Command under contract number F19628-93-C-0171 Views and conclusions contained
`in this document arc
`those of the authors and should not be interpreted as representing the official policies either expressed or implied of Wright Labo
`ratory or the United States Government
`
`By
`
`Distribution
`
`Availability Codes
`
`Avail andfor
`Special
`
`DISTRIBufloN STATEMjr
`
`Approved
`for public 1dec50
`Distñbution Uulim.jte3
`
`Petitioner IBM – Ex. 1012, p. 2
`
`

`
`KeywordsWorld Wide Web distributed computing hypertext
`uted information systems
`
`transfer protocol HYTP load balancing server groups distrib
`
`Petitioner IBM – Ex. 1012, p. 3
`
`

`
`Introduction
`
`growth of the World \Vide Web continues with no near-term end in sight the load placed on pop
`As the exponential
`single server machine to handle When the volume of requests to
`ular Web servers is often too great
`server
`for
`becomes prohibitively high the server tends to drop requests and eventually crashes The service provider needs more
`the service One solution is to simply buy
`the demands of the clients
`computing power to meet
`bigger
`requesting
`machine that can handle the large load of service requests This solution is however unacceptable
`it provides only
`to grow rapidly even the more powerful server will
`temporary relief from server overload If server usage continues
`few years as the number
`eventually be overwhelmed This problem is likely to become more significant over
`the next
`of commercial service providers and the size of the data objects being exchanged are likely to increase dramatically
`
`distributed Web server which will spread incoming
`solution to this problem is to implement
`fairly obvious
`significant problem with this approach The HyperText
`load among several machines There is however
`request
`resource on the Web using
`Transfer Protocol HTTP/l.0 used by Web clients and servers identifies
`valid host-
`single hostname to maintain compatibility with existing
`distributed server needs
`name Consequently
`to present
`Web clients We can alleviate this problem by extending the concept of distributed process groups to the Web server
`single logical name and address to the outside world From the viewpoint
`level
`distributed server group exports
`single server that will handle the HTTP request
`client sending an HTTP request the server group is
`in the same
`of
`way that any other Web server would Once the server group receives
`transparently allocates
`appropriate member of the group for processing
`
`request
`
`it
`
`it
`
`to an
`
`By supporting distributed Web server groups we can provide
`mechanism for smoothly scaling the server capacity
`request provided there is suf
`of Web service providers The use of server groups can reduce the latency of servicing
`throughput Our Web server group implementa
`ficient available network bandwidth to accommodate
`higher request
`the HTTP/l
`to Web clients which support
`load and is transparent
`.0 protocol
`
`tion can effectively balance request
`
`The World Wide Web
`
`2.1 The HTTP Protocol
`
`The fundamental mechanism underlying the Web is the HTTP protocol The protocol
`complete description of the current protocol can be found on-line at
`interested in the basic structure of the protocol
`
`textual
`
`is stateless object-oriented and
`For our purposes we are only
`
`HTTP is an RPC-like protocol
`is
`
`request
`
`clients make requests of servers and receive responses
`
`The general
`
`format of
`
`method
`
`URL
`
`protocol version
`
`optional header information
`
`/doc .html HTTP/1 .0 CrLf
`CrLf
`GET
`CrLf CrLf
`end
`
`Body
`
`Figure HTTP request format
`
`Figure
`
`Example HTTP request
`
`name for an object
`URL is simply
`typically the hierarchical naming scheme
`This figure needs some explanation
`is method to be invoked on the object named by the
`of the Unix file system is used The method given in the request
`given URL The CrLf tag represent
`the pair of characters carriage return and line feed The optional header
`infornza
`series of MIME headers which can be used to specify
`variety of things including client name user name
`
`tion is
`
`Petitioner IBM – Ex. 1012, p. 4
`
`

`
`encoding type date authorization information etc The body of the request
`for the method
`is in essence the argument
`
`invoked it
`
`list
`
`page
`
`is interpreted
`
`by the method which is
`
`Once the server receives
`
`request
`
`from client
`
`it processes the request and returns
`
`response
`
`reply from the
`
`server has the following structure
`
`protocol version
`
`status code
`
`reason CrLf
`
`optional header information
`
`CrLf
`
`Body
`
`200 OK CrLf
`HTTP
`Server NOSA/1.3
`Content-te text/html CrLf
`HTML document
`end
`
`Figure
`
`HTTP response format
`
`Figure
`
`Example HTTP response
`
`humanreadable textual explanation of
`The status code indicates
`the result of the request the reason field provides
`the status code The rest of the fields of the response fulfill similar roles to their counterparts
`in the request
`
`frequently used In fact Web sessions typically
`In current patterns of Web use the GET method is by far the most
`consist exclusively of GETS This reflects the fact
`that the Web is currently used primarily as means of fetching files
`albeit in many formats including hypertext
`
`2.2 Web Servers and Clients
`
`Servers and clients use the HTTP protocol described above to exchange information The general model of the Web
`by documents
`file space to clients This file space is populated
`hierarchical
`currently in use is this servers export
`of various types The primary function of Web clients is to acquire documents from this file space in response to user
`format which is acceptable to them both Web servers
`document
`actions The client and server must also negotiate
`and clients communicate with each other over TCP/IP streams The general model of an HTTP transaction
`is
`
`The client opens
`
`TCP/IP connection
`
`to the server
`
`The client sends its request over
`
`this stream
`
`The server sends its response back
`
`And the connection
`In the case of the most widely used Web server NCSAs httpd the server forks
`new process for each connection
`That process receives the request
`from the client processes it sends back
`response and exits
`
`is closed
`
`Distributed Web Server Group
`
`Since its inception the Web has experienced
`very rapid growth in usage and amount of data being provided The
`demand for data and the raw amount of data has also
`growth of the user community has generated increasing
`increased due to the proliferation of large multimedia resources The result has been continually increasing stress on
`Web servers
`
`single server group The server group would provide
`natural solution is to group several server machines
`into
`its member machines The need for this
`single logical service but would physically share incoming requests amongst
`is indeed real NCSA has implemented
`similar scheme for their server after
`able to cope with the heavy load
`
`single server machine was no longer
`
`In order for Web server group to be useful
`
`it must operate transparently within the existing Web In other words it
`
`Petitioner IBM – Ex. 1012, p. 5
`
`

`
`page
`
`load
`
`inform
`
`Web
`Client
`
`Web
`
`Client
`
`Web
`Client
`
`Architecture
`
`Client sends an i-il
`and Protocol for the IJistributed Web Server Uroup
`Figure
`least-loaded server and sends forwarding address
`Client resends
`calculates
`Dispatcher
`request
`Member server satisfies request
`IITTP request to forwarding address member server
`
`must be implemented within the framework of the HTTP protocol and it must be completely compatible with existing
`by the current URL specification
`Web clients The server group implementation is also constrained
`server group
`In addition to all this we also want
`the server group to perform well
`unique Internet address
`must be identified by
`new overhead as possible
`load effectively and introduce
`it must balance request
`
`as little
`
`3.1 System Architecture
`
`We have chosen the following general architecture for our Web server groups
`
`There is
`
`the dispatcher which
`server
`special
`intended for the server group are received by the dispatcher
`
`coordinates
`
`and controls the server group Requests
`
`Attached
`
`collection of member servers These servers are the actual repository of
`to the dispatcher
`requests made of the group
`data and fulfill
`
`is
`
`the group to the outside world Incoming requests are received by the
`The dispatcher
`is the single entity representing
`to one of the member servers for actual processing It
`is also the task of the dis
`dispatcher and they are redirected
`to balance the load placed upon the various members under
`tries to always dispatch
`In essence it
`its control
`patcher
`loaded member Each member exports an identical copy of some data repository In our
`incoming requests to the least
`and communi
`common AFS directory Figure
`diagrams both the system architecture
`case this data is shared via
`
`cation protocol
`
`server httpd This server has several
`to the NCSA Web
`We have implemented our new servers as extensions
`is quite portable One major consequence of this
`is in wide use and it
`is well supported it
`attractive properties it
`new process for every connection
`choice has affected our design since the httpd server
`process handling
`forks
`an incoming request cannot modify the global server state
`
`like the standard httpd server it only forks when
`We have decided that
`the dispatcher should not fork on connection
`sending messages to its members This lowers the latency of request dispatching
`and allows the global server state to
`the design process we felt
`the dispatcher was likely to be
`be modified during request processing Throughout
`single point through which all
`requests flow Processing each request serially before accepting
`bottleneck since it
`bottleneck Therefore we have tried to keep the
`an even greater danger of creating
`to minimum Fortunately in our experience the load on the dis
`amount of processing performed by the dispatcher
`critical point It remained only marginally loaded
`patcher never reached
`
`the next connection
`
`introduced
`
`is
`
`that
`
`Petitioner IBM – Ex. 1012, p. 6
`
`

`
`3.2 Interfacing to Web Clients
`
`In order to make the server group work there needs to be some mechanism for the dispatcher
`to redirect
`clicnts
`by all major Web clients
`to another server Fortunately such mechanism already exists and is supported
`including Mosaic Lynx and W3
`
`request
`
`page
`
`Recall
`
`included
`
`that every response from server
`status code The status code of particular interest to us
`is Found 302 It
`the requested object has been found on another server whose address is
`in the body of the response The client is expected to re-request
`from the given alternative server
`that object
`This process of redirection is completely invisible to the user
`
`to
`
`client includes
`
`instructs
`
`client that
`
`3.3 Protocol Extensions
`
`server groups we needed some means for communication between the dispatcher and its members One
`To support
`for this purpose possibly using UDP instead of TCP However we
`possibility would be to build
`dedicated protocol
`this communication through extensions to the HTTP protocol As
`the intragroup com
`decided to implement
`result
`munication fits smoothly within the overall structure of the server This has
`the chief advan
`number of advantages
`tage being that our code should be easily portable to future server versions as well as other servers
`
`The extensions we have made to the HTTP protocol are fairly minor Most of these changes involve simply adding
`new methods and they oniy affect
`the dialog between the dispatcher and its members These extensions are com
`pletely invisible to clients The first
`adding methods
`set of extensions
`involves
`for administering server groups In
`server and member is communicating with it
`client The new
`in the role of
`
`is acting as
`
`these cases the dispatcher
`methods are as follows
`
`Method GROUP-ADD
`Body URL of member server
`This method adds the specified member server to the server group administered by the dispatcher
`
`Method GROUP-EXIT
`Body URL of member server
`This method removes the specified member server from the dispatchers server group
`
`Method GROUP-QUERY
`Body None
`Returns
`status information about
`
`debugging purposes
`
`the server group and its mcmbers Currently this is meant only for
`real system might choose to ignore this request
`
`from the H1TP specification It
`The next extension actually diverges
`is implemented as
`request
`The format of the message is
`response is neither required nor expected
`
`message rather than as
`
`Method LOAD-INFORM
`Body Load value arid time stamp
`load information from member to the dispatcher This information is then
`This message communicates
`used by the dispatcher
`in its load balancing decisions
`
`Our final extension
`
`is also message rather than
`
`request
`
`Method LOAD-QUERY
`Body None
`to query load information from member The member is expected
`This message is used by the dispatcher
`LOAD-INFORM message
`to respond later with
`
`Petitioner IBM – Ex. 1012, p. 7
`
`

`
`LOAD-QUERY message
`This last requirement may seem slightly strange the member is required to respond to
`response The reason for this is related to the structure of the dispatcher
`direct
`with another message rather than
`forks when sending messages any response would be unable to affect
`the global state To get
`Since the dispatcher
`around this difficulty we require the member to send LOAD-INFORM back to the parent process
`
`page
`
`3.4 Load Balancing
`
`is to distribute incoming requests to members of the server group However simply doing
`The task of the dispatcher
`this without making informed decisions about where to send requests would not be very desirable We want
`the dis
`to distribute requests in such way as to balance the load placed on the various member servers This requires
`patcher
`of the load on members and there must be some scheduling
`two things the dispatcher must have some knowledge
`policy used to select which member to dispatch the next
`
`request to
`
`The first
`
`issue that needs to be addressed is how to measure the load on member server At first glance you might
`should have enough information to compute the load on member After all every request
`that
`the dispatcher
`suspect
`true When examining actual
`that arrives at member was directed
`there by the dispatcher In reality this is not
`HTML documents
`remote
`that many links are either relative to the current server or point
`it becomes evident
`to
`server This has the following consequence when first contacting
`client will be dispatched
`par
`server group
`ticular member Subsequently all relative links will be resolved by going directly to that member This property actu
`In addition since each client connection
`ally has the desirable effect of helping to balance the load
`single request there is no way of predicting how long
`particular client will continue making requests of the server
`cannot know the load on member so it must be informed of the members load using the LOAD
`The dispatcher
`INFORM message described above
`
`to
`
`is for
`
`traffic
`
`well
`
`for two sources of load the traffic of requests and the general
`good load measure for the members should account
`is an important source of load Including the load on the machine as
`load on the machine Obviously request
`is necessary because there might easily be other active processes on the same machine In particular
`there might
`be multiple members per machine The formula we use to compute the load on member is Load
`10
`rn
`is the number of requests per second being received by the member and
`is the machine load as measured
`where
`by the number of processes in the run queue The scaling factor of 10 is used to allow the load to be represented as an
`direct correlation between requests being pro
`for faster processing Note that with our servers there is
`integer
`cessed and number of processes This load information is transmitted periodically to the dispatcher every 15 sec in
`our experimental configuration
`
`the members in doubly-linked priority queue sorted by
`The dispatcher uses
`simple scheduling policy It keeps all
`looking at the head of the queue and returning that mem
`load Thus dispatching
`request simply involves
`increasing
`ber address to the requesting client The dispatcher also attempts to estimate the change of member load over
`time by
`to that member If
`does not
`the dispatcher
`to the load every time
`adding
`constant
`factor
`is dispatched
`request
`LOAD-QUERY mes
`LOAD-INFORM query from member after some long amount of time it will send
`this fails for some reason the member is assumed to have failed and is removed from the server pool
`If
`
`receive
`
`sage to it
`
`Performance Analysis
`
`4.1 Experimental Overview
`
`for our distributed Web
`The most appropriate test
`server would involve observing
`its performance in
`period of months However practical
`obviously preclude this type of testing
`accessed
`considerations
`location over
`to simulate heavy localized load on the servers and
`Instead we have attempted
`from the scope of this project
`variety of file access patterns We have attempted to use file access patterns which
`observe how they perform under
`we feel are fairly representative of common Web usage patterns Our testing has focused on the latency for satisfying
`
`heavily
`
`Petitioner IBM – Ex. 1012, p. 8
`
`

`
`50
`
`50
`
`40
`
`3Q
`
`20
`
`10
`
`-.
`
`p..
`
`Server Number
`
`page
`
`Dsrveri
`
`DServer2
`
`100%
`
`90%
`
`80%
`
`70%
`
`60%
`
`50%
`
`40%
`
`30%
`
`20%
`
`10%
`
`0%
`
`10
`
`Test Number
`
`Figure
`
`Total Load Balance
`
`servers
`
`Figure
`
`Instantaneous Load Balance
`
`the group members These metrics
`from the users perspective
`and on the balancing
`of load amongst
`request
`user browsing the Web and server hardware utilization respectively
`the perception of
`
`reflect
`
`4.2 Experimental Procedure
`
`We developed
`test suite of 125 tests to observe how the server groups performed as various aspects of the system
`were stressed As
`control test we performed each of the test series on
`vanilla httpd server To measure server
`performance the member servers were instrumented to periodically dump their load information into log files
`
`programmable HTTP client using Tel that measured
`latency as seen by clients we constructed
`To measure request
`the time required to satisfy an HTTP request The phases timed by the client were connection
`to the dispatcher redi
`recting to the member server and finally receiving the requested data All timing measurements were made in
`code
`to avoid Tel overhead and the data read by the client was not interpreted
`in any way Many machines were required to
`test suite was performed in Carnegie Mellons computing labs early in the morning
`test system performance the final
`over Thanksgiving break 1994 The campus network was very lightly loaded We used 10 Sun Sparc-5 machines
`SGI Indigo2 machines
`clients and
`as servers The entire test suite took about
`five hours to complete External
`remained consistently negligible but present throughout the duration of the test
`
`as
`
`load
`
`on the network
`
`4.3 Test Cases
`
`The three parameters which were varied during our tests were the number of member servers the number of concur
`rent clients and the file access pattern Specifically we looked at
`and member servers
`vanilla httpd server
`and 10 clients and ten different file access patterns The file access patterns were designed to simulate common
`Web access patterns All of the file access patterns were some combination of small 4KB medium 100KB and
`large 2MB files These file sizes were designed to represent
`small HTML home page medium JPEG image and
`short MPEG video clip respectively We ran test cases
`for each possible conthination of server count client count
`and file access pattern
`
`4.4 Experimental Results
`
`ures6 and
`
`Server Performance Observations
`The long term load balancing
`performance of the servers is displayed in Fig
`among the member scr
`As you can see the dispatcher was able to maintain reasonable load balancing
`the optimal case As the graphs show the actual
`ers The dashed line on each graph indicates
`load observed was
`within 7% of optimal with
`servers and within 9% of optimal with
`servers We consider
`this performance to be
`Figure7 shows more fine grained load balancing
`quite acceptable
`ten consecutive
`analysis over
`test cases with
`
`Petitioner IBM – Ex. 1012, p. 9
`
`

`
`page
`
`35
`
`15
`
`10
`
`40
`
`.20
`15
`
`10
`
`Server Number
`
`Number of concurrent
`
`clients
`
`10
`
`Figure
`
`Total Load Balance
`
`servers
`
`Figure
`
`Dispatch time with increasing client load
`
`3-5
`
`2.5
`
`1.5
`
`0.5
`
`60
`
`140
`
`120
`
`100
`
`80
`
`60
`
`client
`
`clients
`
`IC clients
`
`ce-- client
`
`clients
`
`10 clients
`
`vonille
`
`Servers
`
`venillo
`
`Servers
`
`Figure 10 Time to access
`
`10 4K files
`
`Figure 11 Time to access
`
`2Mb files
`
`load balance varies somewhat This could be improved by reducing
`servers As you can see the instantaneous
`granularity of LOAD-INFORM messages from the members but
`this would probably lower total throughput
`client has members address it can contact
`load balancing Once
`practically impossible to ensure optimal
`cannot possibly be accurately predicted by the servers
`member any number of times these accesses
`
`the
`
`It
`
`is
`
`that
`
`User Performance Perception Unfortunately the performance witnessed by the clients was not as promising as the
`the bandwidth of the Ethernet was
`the tests it became rapidly apparent
`results While conducting
`that
`load balancing
`barrage from four servers and ten
`small number of clients and servers let alone
`to keep up with even
`insufficient
`to exceed
`clients Throughout the tests it was not uncommon for the number of Ethernet collisions in the server pool
`the client latency figures are fairly erratic and show only
`the number of successful outgoing packets As
`result
`latency for very small and very large file
`slight improvement as servers are added FigureslO and 11 show request
`access patterns The curves are somewhat erratic Adding servers to the group did not generally improve request
`it was also generally no worse than that of the stand-alone vanilla server It would certainly seem that
`in
`latency but
`the server machines was the chief limiting factor on performance
`our experimental setup the network and not
`
`that
`
`Dispatcher Server Performance One of the promising results of our experiments was the performance of the dis
`patcher We had anticipated
`in our experiments however
`the dispatcher would be the primary bottleneck
`turned out to be remarkably fast and scalable We attempted to determine where the dispatcher would break by having
`barrage of requests to the dispatcher the forwarding responses were merely discarded With the
`ito 10 clients send
`server configuration that rapidly saturated the Ethernet when data was actually transferred we
`same 10 client and
`to refuse any connections or dramatically increase the time required to process
`were unable to force the dispatcher
`at around 30 milliseconds
`shows the time required to process
`request stays fairly constant
`request As Figure
`is increased from to 10 This was
`surprising result With the 10 client and
`server
`even as the number of clients
`machines we had at our disposal we were unable to significantly degrade the dispatchers performance Furthermore
`human user Obviously the
`the 30 msec overhead induced by the redirection is small enough to be imperceptible to
`
`it
`
`Petitioner IBM – Ex. 1012, p. 10
`
`

`
`30 msec delay is very sensitive to network distance travelled but
`general cost of dispatching
`
`the results paint
`
`very encouraging picture of the
`
`page
`
`Related Work
`
`Distributed process groups have been explored in the ISIS system
`and the
`These two
`system
`forms of process groups neither of which are sufficient to completely solve our
`systems implement slightly different
`problem However
`they do establish the basic concepts of distributed process groups and hence distributed server
`
`groups
`
`can be broken down into two main categories those based on communication and those
`Load balancing methods
`based on dispatching patterns
`group of equal servers dispatches jobs to its members
`In the first category
`improve some performance
`trying to optimize or at
`criteria This requires that each server be kept
`informed of
`least
`the load on every other server The second approach views the problem as one of routing where
`central dispatcher
`jobs to servers based on
`routing policy which may involve optimization The critical difference for our
`routes all
`in this scheme the servers whose loads we are trying to balance need to communicate only with the
`purposes is that
`dispatcher Schemes for dynamically scheduling
`requests to balance load have proven successful
`in several applica
`WIK9I HSUS6 PAR92
`tion areas similar to our own
`
`The NCSA has also implemented
`distributed Web server mechanism
`Their server which is probably the
`most heavily loaded server on the Web was beginning to experience actual system failures due to extreme load They
`the system was incapable of handling more than 20 requests per second without crashing To solve this
`report that
`problem they extended the BIND name resolution server at their site It now allows them to specify multiple physical
`for the same logical name When HTTP connections
`are requested on the logical name the BIND server
`machines
`resolves that name to one of the physical machines Machines
`are scheduled in
`purely round-robin fashion They
`of their machines consistently got 50% of the load but
`load was not very well balanced
`their problem of server
`failure
`
`report that
`
`it did solve
`
`Future Directions
`
`There are several ways in which our work could be extended in the future To support active use in the Web at
`large
`few features which would make our servers more complete As with most experimental systems our code
`there are
`in state acceptable for widespread use There are also areas in which our servers could be extended or altered
`to improve functionality and performance
`
`is not
`
`As they are currently implemented our servers implement
`the basic server group functionality However
`there are
`that could be made The GROUP-ADD and GROUP-EXIT requests could be extended to allow
`several extensions
`single request We could also extend the dispatcher
`multiple servers to be added/removed
`in
`to support anonymous
`members It
`that some servers might not want
`is conceivable
`to advertise their location to the rest of the world In this
`for ano
`could serve as an intermediary between the client and the anonymous server
`case the dispatcher
`request
`nymity would be made in the GROUP-ADD request Currently every member exports
`identical data It would be
`nice to allow specific members to export data objects unique to themselves This would complicate the dispatcher
`it would have to actually interpret the URLs handed to it
`table and determine whether
`look them up in
`that
`they
`location or could be dispatched to anyone With the current non-forking architecture of the dispatcher
`special
`this name resolution would add unacceptable
`one would need to carefully consider whether
`overhead
`
`had
`
`in
`
`improvement which should be made to our servers and
`This point highlights what
`is probably the most important
`indeed to all Web servers They should be multithreaded Servers currently pay
`connec
`high price for accepting
`price particularly noticeable during small requests In addition the server process interacting with the client
`tion
`cannot modify the global server state
`multithreaded server should perform significantly better and obviate
`the
`contortions one must go through to maintain server global state
`
`Petitioner IBM – Ex. 1012, p. 11
`
`

`
`page
`
`An important area of inquiry which was beyond the scope of our current project but which could be very informative
`under actual use Although we have tried to examine rea
`is the long term measurement of server group performance
`sonable server usage our experiments have used inherently artificial
`is nontrivial
`to predict just
`access patterns It
`how our measured performance would translate into actual performance With our fairly limited time and perfor
`mance data we were unable to seriously explore variations in the actual dispatching policy Such inquiry might lead
`to significant performance improvements
`
`overshadow the constraints of CPU load for our distributed
`Our tests show that
`the constraints of network bandwidth
`into our servers and the added
`server This suggests that we could incorporate more intelligent
`higher CPU load by provid
`impair performance We could also allow each server to accept
`computation would not
`ing more intensive services such as numerical computation or database lookup instead of simply sending files In this
`enhancement
`case we would expect our distributed servers to provide
`significant performance
`
`request processing
`
`they reside on
`The most obvious way to avoid
`network bottleneck
`is to distribute the servers geographically so that
`separate networks The dispatcher would then take network load and proximity into account when deciding which
`client to This gives rise to the paradigm of transparent mirrors which could be seen as extend
`server to transfer
`transparent centralized directory ser
`ing the current practice of geographically distributed mirror sites by providing
`this approach raises is determining proximity While some way of calculating
`vice The most difficult problem that
`distance metric based on network topol
`good heuristic what we would really like is
`distance may be
`geographical
`to dynamically keep track of the topology of the internet and the probable
`good way for the dispatcher
`ogy Finding
`available bandwidth at each link is wide open for further study
`
`Conclusion
`
`serious problem The NCSA has already become so over
`The increasing load placed upon Web servers is clearly
`distributed server mechanism While their method works it
`is not particu
`loaded that
`they were forced to deploy
`much nicer abstraction
`larly clean and it does not balance request
`load very well Server groups provide
`wider range of possible uses With our current architecture server groups
`distributed Web servers and they support
`could also be deployed without any changes to system software as required by the NCSA approach
`
`for
`
`that server groups are both feasible and effective Server group functionality can be
`Our implementation demonstrates
`added to existing HTTP servers without modifying the overall structure of the servers Our servers have also proven
`load fairly amongst group members For all
`this the server group does not
`incur any
`capable of distributing request
`in client response time
`
`significant cost
`
`Bibliography
`
`Process groups
`
`Birman Kenneth The Process Group Approach
`of the ACM December 1993 pp 36-53
`
`to Reliable Distributed Computing Communications
`
`tCHE85I
`
`and Zwaenepocl Willy Distributed Process Groups
`Cheriton David
`actions on Computer Systems May 1985 pp 77-107
`
`in the
`
`Kernel ACM Traits
`
`Load Balancing
`
`Alonso Rafael An Experimental Evaluation of Load Balancing Strategies Technical Report CS
`TR1 12-87 Department of Computer Science Princeton University
`
`Cheng William
`
`Muntz Richard
`
`Optimal
`
`routing for closed queueing networks Peiforenance
`
`Petitioner IBM – Ex. 1012, p. 12
`
`

`
`page 10
`
`Evaluation vol 13 no.1 Sept 1991 PP 3-15
`
`Hsu Chi-Yin Huang Liu Jane W.S Dynamic Load Balancing Algorithms in Homogenous Distributed
`Systems Technical Report UIUCDCS-R-86-1261
`of Illinois
`Department
`of Computer Science
`
`Urbana-Champaign
`
`Lin H-C Raghavendra CS dynamic load balancing policy with
`job dispatcher Proceed
`ings of 11th Intl Conf on Distributed Computi