SWEB Towards
`
`Scalable World Wide Web Server 011
`
`Multicomputers
`
`Daniel Andresen
`
`Vegard Holmedahl Oscar
`Tao Yang
`Department of Computer Science
`University of California
`Santa Barbara CA 93106
`dandrese tyang veho ibarra Ocs ucsb .edu
`
`Ibarra
`
`Abstract
`
`scalable World Wide Web WWW server
`We investigate the issues involved in developing
`on
`cluster of workstations and parallel machines using the Hypertext Transport Protocol
`HTTP The main objective is to strengthen the processing capabilities of such
`server by
`to match huge demands in simultaneous access requests
`utilizing the power of multicomputers
`system called SWEB on
`distributed memory ma
`from the Internet We have implemented
`chine the Meiko CS-2 and networked SUN and DEC workstations
`The scheduling component
`of the system actively monitors the usages of CPU I/O channels and the interconnection net
`work to effectively distribute HTTP requests across processing units to exploit
`task and I/O
`parallelism We present
`this system Our
`results on the performance of
`the experimental
`and obtains
`the system delivers good performance on multi-computers
`results indicate that
`improvements over other approaches
`
`significant
`
`Motivation
`
`Digital
`
`The Scalable Web server SWEB project grew out of the needs of the Alexandria Digital Library
`ADL project at UCSB
`library systems which provide the on-line retrieval and
`processing of digitized documents through Internet have increasingly turned into
`The Alexandria Project
`
`importance
`
`of
`
`distributed digital
`
`library for spatially-indexed information
`
`is focused on the design implementation and deployment
`The collections of the library
`
`topic of national
`
`currently involve geographically-referenced materials such as maps satellite images digitized aerial
`photographs and associated metadata The fundamental goal of the Alexandria Project is to permit
`users who are distributed over the Internet
`
`to access broad classes of spatially-indexed materials
`
`that may themselves be distributed over
`
`the Internet and to derive useful
`
`information from such
`
`materials
`
`rapid prototype system for the Alexandria digital
`
`library has already been developed
`
`which allows users to browse spatially-indexed maps and images
`
`To expose the system to
`
`Petitioner IBM – Ex. 1009, p. 1
`
`

`
`broad user community the next version of the system available at
`
`the end of 1995 will be
`
`that
`
`the Alexandria digital
`
`connected to the World Wide Web WWW using the Hypertext Transport Protocol HTTP
`library WWW server has
`over high-speed Internet
`
`Our work is motivated by the fact
`to become the bottleneck
`in delivering digitized documents
`WWW sites such as the Lycos and Yahoo
`day For
`receive over one million accesses
`rate for NCSAs HTTP server at UIUC increased from
`example in 1993 alone the weekly access
`91K to L5M The peak request arrival
`rate at NCSA exceeds more than 20 requests/second
`The
`limited number of requests per second
`single high-end workstation can handle only
`requests to the NCSA server typically involve only simple file retrieval operations For WWW-based
`libraries the servers involve much more intensive I/O
`network information systems such as digital
`and heterogeneous CPU activities This is because such systems process
`images And content-based searching and multi-resolution image browsing
`
`potential
`
`Popular
`
`but
`
`large amount of digitized
`
`have large demands
`
`in computation speed disk storage and network bandwidth in the server To meet such demands
`the SWEB project makes use of existing networked computers and inexpensive disk resources to
`strengthen the processing and storage capabilities of WWW servers During the last few years it has
`become commonplace that
`local networks span large numbers of powerful workstations connected
`with inexpensive disks Those machines are idle much of time Also the price/performance ratio of
`parallel machines has dropped rapidly We expect
`
`recycling the idle cycles of those processing
`
`that
`
`of the server in response to
`
`We have developed the preliminary version of
`
`from inexpensive disks can significantly improve the scalability
`units and retrieving files in parallel
`large amount of simultaneous HTTP requests
`scalable WWW server SWEB
`running on
`network of workstations NOW such as SUN and
`following the HTTP
`
`Meiko CS-2 distributed memory machine and
`DEC machines Each processing unit
`is capable of handling
`user request
`protocol The distinguishing feature of SWEB is effective resource utilization by
`processor eg SUN SPARC or Meiko
`CS-2 node possibly linked to
`local disk Several
`the performance of
`resource constraints affect
`the CPU speed and memory size of one processing unit the existing system load the
`transmission bandwidth between the processing unit and its local disk the network latency and
`
`of multiple processing units Each processing unit is
`
`the server
`
`close collaboration
`
`bandwidth between
`
`processing unit and
`the local disk and disk contention when multiple I/O requests access
`the same disk can all affect
`the performance Server scalability is achieved by actively monitoring the run-time CPU disk I/O
`and network loads of system resource units and dynamically scheduling user HTTP requests to
`proper node for efficient processing
`
`remote disk when the accessed files are not stored in
`
`The paper
`ground and problem definition Section
`
`is organized as follows Section
`
`discusses
`
`the related work Section
`
`gives the back
`
`discusses
`
`the possible approaches for building
`
`scalable
`
`Petitioner IBM – Ex. 1009, p. 2
`
`

`
`WEB server and the SWEB organization and load balancing
`presents the
`strategies Section
`results showing the performance of SWEB and compares our approach with others
`performance bound of SWEB and verifies it with the actual
`provides analytic results on
`
`experimental
`
`Section
`
`experiment results Section
`
`discusses conclusions and future work
`
`Related Work
`
`has built
`
`Numerous other initiatives to create high-performance HTTP servers have been reported NCSA
`multi-workstation HTTP server based on round-robin domain name resolution DNS
`The round-robin technique is effective when HTTP requests
`to assign requests to workstations
`access HTML information of relatively-uniform size chunks and the load and computing powers of
`workstations are relatively comparable Our assumption is that
`the computing powers of worksta
`They can be used for other computing
`
`tions and parallel machine resources can be heterogeneous
`
`needs and can leave and join the system resource pool at any time Thus scheduling techniques
`The
`which are adaptive to the dynamic change of system load and configuration are desirable
`domain name resolution in
`
`round-robin fashion cannot predict
`
`those changes Another weakness
`local DNS
`DNS caching enables
`
`of the technique is the degree of name caching which occurs
`
`system to cache the name-to-IP address mapping so that most recently accessed hosts can quickly
`period of time from DNS servers domain
`The downside is that all
`the requests from UCSB might go to server S2
`IP address For example all
`will go to
`particular
`its IP address happened to be cached in some previous lookup even though server Si might be
`
`be mapped
`
`if
`
`requests for
`
`relatively idle
`
`Recently NCSA has come out with version L4 of their httpd software which in many cases doubles
`This technique
`
`the performance of previous versions by utilizing
`
`pre-forking strategy
`can be incorporated in our system and will be beneficial However we have not done so at
`stage and in this paper we focus on alternative means of achieving the scalability through dynamic
`
`this
`
`scheduling and request redirection
`
`The
`Other projects have focused on improving the performance of
`single-workstation server
`to the early versions of NCSA httpd to make
`Apache project has programmed
`set of changes
`the server more efficient The CERN server has achieved significant
`improvements The Harvest
`HTTP cache which can be major accelerator
`
`project
`
`has introduced
`
`for pages without
`
`dynamically created component All
`
`these efforts are concentrating
`
`on the single workstation
`
`server level and can be embodied in our system while our work focuses on
`
`collaborating multi
`
`workstation server
`
`It should be noted that WWW applications only represent
`
`special class of Internet
`
`information
`
`Petitioner IBM – Ex. 1009, p. 3
`
`

`
`systems There are other information servers dealing with huge file sizes and large numbers of
`
`users for example multi-media servers
`
`Our situation has several differences
`
`First our
`
`current system has no real-time processing constraints for displaying digital movies or audio clips
`
`Secondly many of our users tend to browse different
`such as one film beginning to end Thirdly we assume lossless
`
`text and images information rather than
`
`focusing one particular document
`
`document delivery keeping consistency between the source library holding and what
`
`is sent
`
`to the
`
`client
`
`Our dynamic scheduling scheme is closely related to the previous work on load balancing
`on dis
`BCS95 WR93 In these studies tasks arrivals may temporarily be uneven
`is to adjust the imbalance between processors by
`among processors and the goal of load balancing
`
`tributed systems
`
`appropriately transferring tasks from overloaded processors to underloaded
`
`processors
`
`The most
`
`well known techniques are called receiver-initiated and sender-initiated strategies In those studies
`single system parameter Le the CPU load We call
`the criteria for task migration are based on
`them single-faceted scheduling strategies In the WWW applications there are multiple parameters
`that affect the system performance including CPU loads interconnection network performance and
`disk channel usages The optimal HTTP request assignment
`to processors does not only depend on
`CPU loads Thus we need to develop multi-faceted scheduling scheme that can effectively utilize
`
`the system resources by considering multiple performance parameters
`
`Background The World Wide Web
`
`The World Wide Web is based on three critical components the Uniform Resource Locator URL
`the HyperText Markup Language HTML and the HyperText Transfer Protocol HTTP The
`the HTML language allows the information
`URL defines which resource the user wishes to access
`platform-independent but still well-formatted manner and the HTTP protocol
`to be presented in
`BC95 BL95
`is the application-level mechanism for achieving the transfer of information
`
`HTML is derived from the Standard Generalized Markup Language SGML optimized for
`information It operates on the basis of tags where each piece of the text
`presenting hypertext
`is marked to indicate the format to be used HTML is similar to other markup languages such
`as LT and RTF HTML version LU contained little beyond hypertext
`links and standard
`
`formatting functions such as bold center etc Later versions have been extended to include
`
`the forcrns interface where users can fill
`
`in data and submit
`
`the form to
`
`server
`
`tables which
`
`spreadsheet and inline images In addition to the formal standard many
`mimic the layout of
`browser companies eg Netscape have added custom extensions to their implementations
`
`Petitioner IBM – Ex. 1009, p. 4
`
`

`
`The Uniform Resource Locator URL serves as an index to
`giving the hostname the access method and document/application path in
`format For example the URL http//wwwcsucsbedu/
`would fetch the default document
`or page from the www server at
`the Computer Science department at UCSB using the
`HTTP protocol
`uses the FTP protocol to fetch the document
`ftp//wwwcsucsbedu/myfile
`myffle from the same machine URLs are not
`
`particular service or document
`
`single concise
`
`limited to simply fetching files however but
`
`program to execute
`http//wwwcsucsbedu/cgi-bin/uptime
`can specify
`causes the
`uptime program to execute on the www server and return its results to the client This
`resource which might be the results of
`ability to transparently select
`dynamic execution
`number of internet services possible without adding complexity
`
`file fetch makes
`
`or simply
`
`for the user
`
`stateless connection-oriented
`
`application-level protocol
`
`servers
`
`sequence of events
`
`The HTTP protocol HTTP is
`number of WWW browsers and servers
`used for network hypermedia information systems
`the NCSA and CERN HTTP
`use such protocols for example NetComs NetScape browser
`simple HTTP request would typically activate
`from
`First the client determines the host name from
`initiation to completion as shown in figure
`the URL and uses the local Domain Name System DNS server to determine its IP address
`The local DNS may not know the IP address of the destination and may need to contact
`the DNS system on the destination side to complete the resolution After receiving the IP
`
`TCP/IP connection to well-known port on the server where
`then sets up
`address the client
`the HTTP process is listening The request
`
`parsing the request
`
`the server sends back
`
`is then passed in through the connection After
`response code eg 202 in the HTTP stands for
`OK File found and 404 is File not found followed by the results of the query The
`
`connection is then closed by either the client or the server
`
`Figure
`
`request
`
`simple HTTP transaction Client
`and receives response
`
`looks up the address of server
`
`sends over
`
`Petitioner IBM – Ex. 1009, p. 5
`
`

`
`SWEB
`
`scalable WWW server
`
`We call WWW server scalable if the system response time for individual
`requests remains relatively
`constant when the the number of simultaneous HTTP requests increases We define the response
`request as the length of the time period from when
`time for
`is initiated until all
`the
`
`request
`
`requested information arrives at
`
`the client
`
`For
`
`single-workstation server
`
`there is an upper bound for the number of requests per second
`The NCSA has performed
`number of tests using high-end
`the server can handle
`workstations and discovered in their working environment approximately 5-10 rps could be dealt
`which cannot match the current and future loads eg
`with using the NCSA httpd server
`library server Thus multiple servers are needed for achieving scalable performance
`
`rps that
`
`digital
`
`We assume that
`set of networked workstations Some of
`the architecture of our system contains
`the workstations are connected to SCSI disks or mass storage RAID subsystems in which HTML
`The disks are included in
`shared file system among all processing units Our
`files are stored
`current implementation runs on NOWs using Ethernet we will use ATM in the future and Meiko
`set of distributed memory SPARC processors connected by
`CS-2 machine which contains
`based communication network All files are available to each processor via NFS mounts The NOW
`set of SUN Sparc stations with Solaris operating systems and DEC Alpha-based
`version runs on
`depicts the architecture assumptions of SWEB In this paper
`workstations with OSF1 Fig
`the
`term workstation unit and processor are interchangeable We also assume that each CPU unit may
`be used by other applications and it could leave and join the resource pool at any time
`
`fat tree
`
`nt
`
`IiIs7
`
`.lIit Flu
`
`\l
`
`\\ oiI.ll
`
`ioii
`
`DODD
`DODD 11
`
`E1
`
`\l
`
`II
`
`\l
`
`iIA S2
`
`Figure
`
`The computing and storage architecture of SWEB
`
`The overall objective of the system is to reduce and sustain the response time under large numbers
`
`Petitioner IBM – Ex. 1009, p. 6
`
`

`
`of simultaneous requests Goals considered in designing this system are
`
`disk resources to build
`
`To demonstrate how to utilize existing inexpensive
`commodity network workstation
`scalable WWW server The computing environment could be het
`erogeneous and workstation/processor units with different speeds and different
`loads at any
`time
`
`and
`
`To develop sophisticated dynamic scheduling algorithms for exploiting task and I/O paral
`lelism adaptive to the run-time change of system resource loads and availabilities The system
`needs to provide good system resource estimation to assist the scheduler The scheduler needs
`to incorporate multiple system performance parameters to assign user HTTP requests to
`proper unit for efficient processing The overhead involved for current resource load assessment
`
`and scheduling decision making should be minimized
`
`In this subsection we will
`first discuss factors that affect scalability of the system introduce the
`functional modules of SWEB and discuss the approaches for routing HTTP request to
`routing scheme affects the design of the scheduling
`based on the scheduling decision since such
`heuristic Then we will present our scheduling algorithm for determining the processor assignment
`given HTTP request
`
`processor
`
`of
`
`4.1
`
`Performance factors
`
`There are several performance factors that affect
`We discuss them in more detail as follows
`
`the response time in processing HTTP requests
`
`Processor
`
`load
`
`HTTP request
`
`is handled through
`
`TCP/IP connection
`
`and then subsequently
`through
`CGI program which
`processing unit can also be used for
`
`This subprocess may retrieve
`forked subprocess
`requires varying amounts of CPU time Notice that
`applications other than WWW The load of
`processing unit must be monitored so that
`HTTP requests can be distributed to relatively lightly loaded processors
`
`file or invoke
`
`Disk I/O
`
`Since most HTTP requests retrieve files from disks the I/O requirements can present
`local network
`bottlenecks For instance whether
`can affect performance substantially The raw data transfer rate of disks is in the range of 2-3
`MByte per second while the RAID subsystems can achieve substantially faster performance
`
`the files are on local disk or fetched over
`
`further
`
`Petitioner IBM – Ex. 1009, p. 7
`
`

`
`20MB or more per second If many requests are accessing
`the I/O performance can degrade significantly due to disk channel contention If simultaneous
`
`the same disk at
`
`the same time
`
`user requests are accessing different disks then parallel
`
`I/O leads to
`
`higher throughput
`
`in
`
`delivering documents
`
`Interconnection network
`
`reside in the local disk of
`
`in some cases given
`
`HTTP requests usually access HTML files but they could activate the execution of program
`The local
`interconnection network bandwidth affects the performance of file retrieval since
`processor Remote file retrieval
`many files may not
`through the
`network file system will be involved The network traffic congestion could dramatically slow
`the HTTP request processing However
`very fast network and NFS
`remote access
`
`server
`
`it
`
`is possible that
`
`can actually be faster than pulling data from the
`
`local disk if the local disk has
`
`high channel contention
`
`Internet
`
`The Internet speed significantly affects the performance
`in information delivery Currently
`Internet bandwidth is increasing rapidly with the advent of ATM BISDN and other WAN
`the NCSA work
`technologies However
`and our experiment show that
`
`the Internet
`
`is
`
`not necessarily the bottleneck
`
`in
`
`high traffic system and the server is another bottleneck
`
`for document delivery
`
`Our goal
`
`is to get
`
`the requested information out of the server as fast as possible Thus our scheduler
`
`primarily monitors the above first
`
`three performance factors The Internet bandwidth information
`
`is used partially in request re-direction Our scheduling algorithm is multi-faceted in the sense that
`the proper decision on routing HTTP requests needs to aggregate the impact of the above multiple
`system parameters on the overall system response time
`
`4.2 Distributed vs centralized scheduler
`
`There are two approaches in designing the scheduler One is to have
`centralized scheduler running
`one processor such that all HTTP requests go through this processor The scheduler monitors the
`usages of all system resources makes assignment decisions based on this information and routes
`requests to appropriate processors We did not
`
`take this approach mainly because the single central
`
`distributor becomes
`
`single point of failure making the entire system more vulnerable
`
`The current version of SWEB uses
`distributed scheduler The user requests are first evenly routed
`to SWEB processors via the DNS scheme as shown in Fig
`The use of DNS rotation to provide
`
`Petitioner IBM – Ex. 1009, p. 8
`
`

`
`Clients
`
`ID
`
`Collaborative
`Servers
`
`Figure
`
`Distributed collaborative scheduler
`
`the initial assignment of HTTP requests is used in the NCSA multi-workstation
`this scheme multiple real machines are mapped to the same IP name As shown in Fig
`requests the network ID of the machine name eg wwwcsucsbedu
`the DNS at
`rotate the network IDs pick up one eg 1111 and send back to the client The
`round-robin fashion
`rotation on available workstation network IDs is in
`This functionality
`available in current DNS systems The major advantages of this technique are simplicity ease of
`
`server
`
`In
`
`when
`
`the
`
`is
`
`client
`
`server site will
`
`implementation and reliability
`
`1.1.1.1
`
`1.1.1.2
`
`II
`
`DNS Rotation The DNS server returns differing IP addresses
`Figure
`round-robin fashion from list of servers
`
`for
`
`given name in
`
`The DNS assigns the requests without consulting dynamically-changing system load information
`Thus the SWEB conducts
`in SWEB contains
`
`re-direction of requests Each processor
`
`further
`
`scheduler and those processors collaborate with each others to exchange
`processor via DNS the scheduler
`in that processor makes
`to another processor Any HTTP request
`to process this request or redirect
`is not allowed to be re-routed more than once to avoid the ping-pong effect This architecture is
`
`After
`
`request
`
`is routed to
`
`regarding whether
`
`it
`
`system load information
`
`decision
`
`substantially less prone to single-point-of-failure breakdowns is more distributed and the overhead
`
`of load balancing is distributed across
`
`number of nodes
`
`The functional structure of the scheduler at each processor
`in Fig
`is depicted
`httpd daemon based on NCSA httpd code for handling httpd requests with
`The broker consults with two
`to handle
`determines the best possible processor
`
`It contains
`
`broker module which
`
`given request
`
`Petitioner IBM – Ex. 1009, p. 9
`
`

`
`The oracle is miniature expert system which uses
`other modules the oracle and the loadd
`user-supplied table to characterize the CPU and disk demands for
`particular task The loadd
`daemon is responsible for updating the system CPU network and disk load information periodically
`every 2-3 seconds and marking those processors which have not
`time as unavailable When
`
`processor
`
`leaves or joins the resource pool
`
`the loadd daemon will be
`
`responded in
`
`preset period of
`
`aware of the change
`
`SWEB
`
`Broker
`
`manage
`servers
`choose server
`
`for request
`
`accept requestr
`choose servers
`me
`ifs
`reroute_requests
`
`else
`
`handle
`
`requestr
`
`___________________
`Oracle
`
`characterize
`
`requests
`
`_______________________________
`loadd
`
`manage distributed load info
`
`httpd
`
`loadd
`
`Figure
`
`The functional modules of
`
`SWEB scheduler
`
`in
`
`processor
`
`4.3 Routing HTTP requests
`
`After
`
`processor accepts
`
`HTTP request
`
`request
`
`to
`
`through TCP connection and
`particular processor this request needs to be transparently routed to this processor
`
`system decides to assign
`
`The best situation would be to modify the UNIX sockets package
`system call Currently the http daemon at
`
`to change
`
`the semantics of the
`
`the server sits listening on
`
`pre-defined port
`
`then negotiates another port over which to conduct
`client wishes to connect
`the transaction while continuing to listen on the original port Setting this new port
`substantial modification of the UNIX operating
`
`the server
`
`to be on
`
`separate machine is difficult
`
`since it
`
`requires
`
`accept
`When
`
`system kernel
`
`allows for
`
`the HTTP protocol
`
`when client
`
`sends
`
`request to
`
`The approach that we eventually decided to implement
`is based on the fact that
`response called URL Redirection As shown in Fig
`rewritten URL
`server SO SO returns
`and
`response code indicating the information is located
`then follows
`
`at
`
`Most Net browsers and clients automatically
`to retrieve the resulting file
`to the user The SWEB algorithm
`query the new location so redirection is virtually transparent
`incorporates the URL redirection with the scheduler
`
`that
`
`is shown in Fig
`
`The primary advantages of URL redirection are the simplicity of implementation and universal
`compatibility An simple control program can be set up within modified WWW server where
`the main complexity lies in the routines to determine the optimal server
`
`particular request
`
`for
`
`10
`
`Petitioner IBM – Ex. 1009, p. 10
`
`

`
`1.1.1.1
`
`Figure
`
`The URL redirection
`
`while true
`listen_on_well_known_port
`
`accept_URL_request
`
`parse
`scheduler_determine_optimal_processorx
`me
`
`if
`fulfill_request
`else
`
`rewrite_URLsx
`return_as_redirection
`
`endif
`
`endwhile
`
`Figure
`
`the URL redirection algorithm
`
`Furthermore the approach lies well within our design parameters by not requiring modification of
`the HTTP protocol being reasonably efficient and being able to support sophisticated optimization
`
`algorithms
`
`The primary disadvantage of URL redirection in practice is the added overhead of an additional
`cycle after the redirection occurs We will show that such
`
`request/parse/respond
`
`connect/pass
`
`in situations where
`
`overhead is more than negated by improved performance overall especially
`common request
`to handle the request
`
`multi-megabyte files are
`
`better for
`
`processor
`
`If
`
`the request
`
`is for
`
`small document
`
`it
`
`is generally
`
`itself without
`
`redirection Our scheduler will consider
`
`such effects
`
`4.4
`
`The multi-faceted scheduling algorithm
`
`HTTP request should be routed
`In this subsection we discuss the algorithm that decides where
`As we discussed before several system load parameters affect such
`
`single-faceted
`
`decision In
`
`11
`
`Petitioner IBM – Ex. 1009, p. 11
`
`

`
`scheduling system processor can be classified as lightly loaded and heavily loaded based on one
`parameter eg CPU load One purpose of such
`classification is to update load information only
`WR93 In our problem
`to reduce unnecessary overhead eg
`when
`classification changes
`processor as heavily or lighted loaded since there are several
`light CPU load but
`its local disk may receive many access
`in SWEB has
`load daemon to detect
`requests from the network file system Thus each processor
`own CPU disk and network load periodically broadcasting such information to other processors
`In our experiments we will show that such overhead is insignificant
`
`context
`
`it
`
`is hard to classify
`
`parameters
`
`processor could have
`
`load
`
`its
`
`Our initial algorithm took into account only the location of the file to be fetched and rerouted the
`to that processor We called this strategy file locality
`
`Initial
`
`results showed that under
`
`request
`
`many conditions an improvement over simple round-robin was apparent
`
`In some cases such as
`
`many requests for
`
`single file performance fell off drastically
`
`We then addressed how multiple system load parameters can be used together
`assignment of the HTTP requests Since our goal
`we design the heuristic based on the estimated cost
`
`is to minimize the response time for each request
`
`for processing each request using the following
`
`in deciding the
`
`formula
`
`tjjj
`
`tdata
`
`tcpu
`
`tmet
`
`tredjrectjom is the cost
`
`to redirect
`
`the request
`
`if required tdata is the time to
`to another processor
`local tp
`transfer the required data from the disk drive or from the remote disk if the file is not
`HTTP request plus any known
`
`is the cost
`
`for transferring the
`
`cost
`
`terms as follows
`
`data
`
`Requested file size
`Disk bandwidthxo1
`
`Requested file size
`mimDi5k bandwidthxo1 Local network bandwidthxo2
`
`if
`
`file is local
`
`if
`
`file is remote
`
`If
`
`the time required to fetch the data is simply the file size divided by the
`the file is local
`available bandwidth of the local storage system We also measure the disk channel
`
`load
`
`If
`
`there are many requests the disk transmission performance degrades accordingly
`
`If
`
`network
`
`the data is remote then the file must be retrieved through the interconnection
`The local network bandwidth and load 82 must be incorporated Experimentally we found
`NFS access and on the SUN workstations
`10% penalty for
`increases by 50%-70%
`
`on the Meiko approximately
`
`connected by Ethernet
`
`the cost
`
`12
`
`is the time to fork
`
`process perform disk reading to handle
`is CGI operation
`if the request
`associated computational cost
`processing results over the Internet We discuss and model these individual
`
`Petitioner IBM – Ex. 1009, p. 12
`
`

`
`CPU1Oad
`
`No of operations required
`CPU8d
`
`is based
`
`The tcpu term estimates the amount of processing time required to complete the task This
`destination node CPU1Oad
`on the speed of the server
`and the estimated number of operations required for the task The computation requirement
`
`the estimated load on
`
`for
`
`is estimated by the Oracle component of the system see Figure
`particular request
`Currently we mainly estimate the CPU cost
`file The parameters for
`configuration file It should be noted that some estimated
`are saved in
`different architectures
`CPU cycles may overlap with network and disk time and the overall cost may be overestimated
`slightly But such estimation still helps us determine the slowdown in file transfer when the
`CPU is shared by others
`
`involved in requesting
`
`One surprising aspect of our research to date is the experimental
`fetch from http server results in substantial CPU activity For
`SUN each concurrent
`or more to the running load average
`request adds
`more is considered heavy using the UNIX load estimate function uptimeQ In this paper we
`assume most requests are retrieving HTML or other files We will
`functions
`incorporate cost
`for CGI operations as accurately as possible as the system is further developed for specialized
`libraries where knowledge on special CGI operations are available
`
`result that
`
`simple file
`
`node on the Meiko or
`
`load of
`
`or
`
`applications such as digital
`
`It should be noted that an inaccurate estimate of computational
`
`cost
`
`is possible but
`
`the
`
`system tries to respond to such
`
`dynamic situation by accessing the current
`
`information on
`
`processor
`
`load as it
`
`is updated periodically and adjusting its scheduling decision accordingly
`
`The load estimation of remote processors is based on the periodic updating of information
`
`informed by those remote processors every 2-3 seconds
`
`It
`
`is possible that
`
`processor Ps
`
`is incorrectly believed to be lightly loaded by other processors
`
`To avoid this unsynchronized
`redirected
`to it
`CPU load of px by
`our system
`
`This strategy is found to be effective in
`
`and many requests will be
`overloading we conservatively
`We use
`
`increase the
`
`30% in
`
`_bytes_required
`met _bamdwzdth
`
`This term is used to estimate the time necessary to return the results back to the client over
`the network When the scheduler compares processors we assume all processors will have
`for this term Thus we do not estimate this term Our goal
`basically the same cost
`produce the query result for HTTP request as fast as possible in the server site
`
`is to
`
`tredirectiom
`
`latemcy
`
`13
`
`if
`
`task is executed locally
`
`if redirection is used
`
`Petitioner IBM – Ex. 1009, p. 13
`
`

`
`This term measures the time necessary to move the HTTP request from one server to another
`This is set
`
`to twice the estimated latency of the connection between the server and the client
`
`plus the time for
`
`server
`
`to set up
`short reply going back to the client browser who then automatically issues another request
`
`connection
`
`The conceptual model
`
`is that of
`
`very
`
`to the new server address The transfer time is zero if
`
`the task is already local
`
`to the target
`
`server The estimate of the link latency is available from the TCP/IP implementation but in
`
`the initial
`
`implementation is hand-coded into the server
`
`Given the arrival of HTTP request
`
`at processor
`
`the scheduler at processor
`
`goes through the
`
`following steps
`
`Preprocess
`
`request The server parses the HTTP commands and completes the pathname
`It also determines whether
`given determining appropriate permissions along the way
`the
`requested document exists has moved or is CGI program to execute
`
`Analyze request The server
`
`then determines whether
`
`itself or another server should fill
`
`the
`
`request
`
`It does so by checking
`
`the results from the preprocessing
`
`phase
`
`If
`
`is already
`
`determined to be
`
`redirection does not exist or is not
`
`retrieval of information then the
`
`is always completed at
`request
`SWEB it will always be accepted
`for analysis The broker
`then
`
`Additionally if
`
`the request has already been redirected by
`
`If
`
`this is not
`
`the case then the request
`
`is passed to the
`
`broker
`
`Determines the server on whose local disk the file resides if any
`
`Calculates
`
`an estimated time for each available server-node for request
`
`Having determined the estimated time for each server to fill
`the request
`its choice determined by the minimum time to completion to the main process
`
`the broker
`
`indicates
`
`Redirection If the chosen server is not
`
`the request
`
`is redirected appropriately
`
`is processed in the normal HTTP serv