`
`Attorney’s Docket No. 02577.P001D
`
`m
`
`1N THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`.4
`C)
`N.4
`
`DC .
`
`‘I
`ZI"
`70
`
`OO3
`
`Examiner:
`
`Unassigned
`
`ArtUnit: 2755
`
`In Re Patent Application of:
`
`Keith Lowery et a].
`
`Application No.: 09/234,048
`
`Filed:
`
`January 19, 1999
`
`For:
`
`System and Method for Managing
`Dynamic Web Page Generation
`Requests (As Amended)
`
`Assistant Commissioner for Patents
`
`Washington, DC. 20231
`
`VVVVUVVVVV
`
`J
`
`Sir:
`
`INFO
`
`TION DIS
`
`STATEME
`
`Enclosed is a copy of Information Disclosure Citation Form PTO-1449 together
`
`with copies of the documents cited on that form. It is respectfully requested that the cited
`
`documents be considered and that the enclosed copy of Information Disclosure Citation
`Form PTO-1449 be initialed by the Examiner to indicate such consideration and a copy
`
`thereof returned to applicant(s).
`
`Pursuant to 37 C.F.R. § 1.97, the submission of this Information Disclosure
`
`Statement is not to be construed as a representation that a search has been made and is not
`
`to be construed as an admission that the information cited in this statement is material to
`
`patentability.
`
`Pursuant to 37 C.F.R. § 1.97. this Information Disclosme Statement is being
`
`submitted under one of the following (as indicated by an “X” to the lefi of
`
`the appropriate paragraph):
`
`XL 37 C.F.R. §l.97(b).
`
`37 C.F.R. §l.97(c). Ifso, then enclosed with this Infomation
`Disclosure Statement is on; of the following:
`
`A statement pursuant to 37 C.F.R. §l.97(e) or _
`
`A check for 32% for the fee under 37 C.F.R. § l.17(p).
`
`- 1 -
`
`LJV/cak (ca/23198)
`
`
`PN EXHIBIT 2004
`
`Microsoft Corp. V. Parallel Networks Licensing, LLC PN'00000348
`IPR2015—00483
`
`
`
`

`

`37 CPR. §1.97(d). If so, then enclosed with this Information
`Disclosure Statement are the following:
`
`(1)
`
`(2)
`
`(3)
`
`A statement pursuant to 37 C.F.R. §l.97(e);
`
`A petition requesting consideration of the Information Disclosure
`. Statement; and
`
`
`for the fee under 37 CPR. §1.17(i)
`A check for $
`for submission of the Information Disclosure Statement.
`
`If there are any additional charges, please charge Deposit Account No. 02-2666.
`
`Respectquy submitted,
`
`TAYLOR & ZAFMAN LLP
`
`
`
`Dated: ‘14?“ 1999
`
`12400 Wilshire Blvd.
`Seventh Floor
`
`fit”—
`
`James H. Sal r
`Reg. No.
`.668
`
`
`
`Los Angeles, CA 90025-1026
`(408) 720-8598
`
`. I
`
`hereby certify that this correspondence is belng deposited with the United States Postal Service as first class
`mail with sufficient postage in an envelope addressed to the Assistant Commissionet for Patents. Washington. D.
`C 20231 0" _1y1y_2._12£______—____.
`(Date of Deposit)
`AWL—.—
`(Typed or printed name of person mailing conespondence)
`
`(Signature of person mailing cor-res
`
`once)
`
`- 2 -
`
`LJVlcak (08/28/98)
`
`PN-00000349
`
`

`

`
`
`Abstract
`
`We investigate scalability issues involved in developing high.
`performance digital library systems. Our observation: and so-
`lutions are based on our experience with the Alexandria Digital
`Library (ADL) testbed under development at UCSB. The current
`ADL system provides art-line brawsing andprocessing ofdigitized
`mpsand othergeo-spt'tgialiy mapped data via the World Mole Web
`(WWW). A primary activity ofthe ADL system involves computa-
`tion anddr‘sk l/Ofor accessing compressedmulti-resolutr'on images
`with hierarchical data structures. as well as other duties such as
`supporting database queries and ort-tlre-fly HTML page genera.
`tlorg. Providing multi-resolutlon image browsurg services can res
`duce network trafic but impose some additional cost at the server:
`We discuss the necessity ofhoving a mum-processor DL server to
`match potentially huge demands in simultaneous access requests
`from the lntemet. We have developed a distributed scheduling
`system fitr processing DL requests. which actively monitors the
`usages of CPU. [/0 channels and the interconnection network to
`efl'ectively distribute worl: across processing units to exploit task
`and 1/0 parallelism. We present an esperimental study on the per-
`former:ce ofourscheme in addressing the scalability issues arising
`In ADL wavelet processing undfile retrieval. Our results Indicate
`that the system delivers goodperformance on these types oftasks.
`
`1. Introduction
`
`The numbcrofdigital library (DL) projects is increasing rapidly
`at both the national and the international levels (sec. for example.
`[6. 2]). Many of the current projects are moving rapidly towards
`their goals of supporting on-lino retrieval and processing of major
`collections of digitized documents over the inter-net.
`
`Performance and scalability issues are especially important for
`the Alexandria Digital Library (ADL) project [2. l4]. Thc fun-
`damental goal of this project Is to provide users with the ability to
`access and process broad classes of spatially-referenced materials
`from the Internet. Materials that are Currently in the collections of
`ADI. and accessible through the ADL World Wide Web (WWW)
`
`s
`
`O
`
`.
`
`Q
`
`u
`
`Scalability Issues for High Performance Digital Libraries on the World Wide Web
`
`Daniel Andresen. Tao Yang. Omer Egccioglu. Oscar H. Ibarra. and Terence R. Smith
`Department of Computer Science
`University of California
`Santa Barbara, CA 93106
`, {dandresc. tyang, omcr. ibarra, smilhtr}@cs.ucsb.cdu
`
`server include geographically-referenced items such as digitized
`maps. satellite images. digitized aerial photographs. and associated
`metadata. When fully developed. ADL will comprise a set ofnodes
`distributed over the Internet supporting such library components
`as collections. catalogs. interfaces. and ingest facilities. ADI. is
`currently building collections that will involve millions of items
`requiring terabyte levels of storage. Many collection items have
`sizes in the glgtbytc range while other: require extensive process-
`ing to be of value in certain applications. The catalog component
`alone contains a. metadatabasc of significant size.
`
`Before suchgoals can be achieved. however. major issues of
`performance rind scalability must be resolved. particularly for DI..s
`supporting extensive collections or collections with large data'
`Items. Critical performance bottlenecks that must be overcome
`to assure adequate access over the Internet involve server process-
`ing capability and network bandwidth. Whilc we expect network
`conununication technology to improve steadily. particularly with
`the advent ofATM and B-ISDN. we still need to consider the min-
`imization of network traffic in the design of the current system.-
`Additionully. the scrvcrpcrfannancc must scale to match expected
`demands.
`
`A strategy used in the ADLsystcm for reducing network u-affic
`is to provide the service of progressive Image browsing and thc
`subregion retrieval. to avoid unnecessary large image transmission.
`The trade-0&2 however. is that more processing is required at the
`server site. Considering that popular WWW sites such as Alta
`Vista. Lycos and Yahoo have been receiving over two million
`accesses per day (or 20-30 requests per second). and the ADL
`sctvcr Involves much more intensive 110 and heterogeneous CPU
`activities. a multi-proccssorscrvcr becomes indispensable [2].
`
`In this paper. we investigate the network bandwidthrcquirctncnt
`in the ADL system using progressive image browsing retrieval and
`the computational and U0 demands for supporting such activities.
`We study the use of networks ol'cxisting. inexpensive workstations
`anddisks to augment the processing and storage capubflics of DL
`servers. In particular. we have investigated to'iirhat extcfitccycllng
`the idle cycles of processing units in networks of'mtgns.
`as well as retrieving files ln parallel from lnexpcnsiygdisliflan
`CD
`significantly improve the scalability of a Dl.‘ server tfiondiog to
`many simultaneous rcqucsrs.
`z,
`:5
`7‘"
`w :2
`C.)
`o
`3:
`
`'
`
`GBAIHOEH
`
`.
`
`PN-00000350
`
`-3-
`
`

`

`e
`
`'
`
`C W
`
`..
`
`e have implemented our scheme on a cluster of SUN SPARC
`- nodes connected by a hleiko CS-2 Elan network. and clusters of
`' SUN and DEC workstations connected by Ethernet. Each process-
`ing unit (e.g. 3 SUN SPARC node) is linked to a local disk and is
`.capable of handling a user request. There are a variety of resource
`constraints that can affect the performance of the server. These
`constraints include: the CPU speed and memory size of a single
`processing unit: the current system load: the transmission band-
`width between the processing unit and its local disk; the network
`latency and bandWidth between a processing unit and a remote disk
`when the accessed tiles are not stored in the local disk; and dislt
`contention when multiple [/0 requests access the same dislt. By
`understanding these effects. we can achieve server scalability. in
`particular. by actively monitoring the run-time CPU. disk 1/0. and
`network loads of system resoutCe units. we can dynamically sched-
`ule user requests to nodes in a manner that provides the greatest
`Overall processing efficiency.
`. ‘
`
`Our strategies are based on ourworls for ascalable WWW server
`called SWEB [I]. We assume that the system contains a set of
`networked workstations (see Figure 3). Some of the workstations
`are connected to SCSI-ll disks or mass storage subsystems. In
`this paper. the terms workstation unit. node. and processor are
`interchangeable. We assume that each CPU unit may be used by
`other applications and can leave and join the resource pool at any
`tlme.
`
`The paper is organized as follows: Section I briefly describes
`the ADL Project. Section 3 discusses the scalability issues ad-
`dressed in the ADL system for ameliorating network and server
`bottlenecks. Section 4 discusses scheduling and resource moni-
`toring strategies in our mum-processor system. Section 5 presents
`experimental studies concerning multi-nodc performance and an-
`alyzing overhead and the effectiveness of resource scheduling.
`Section 6 discusses related work. Section 1 discusses conclusions
`and future work.
`a
`
`2. The Alexandria Digital Library on the
`WWW
`
`Key aspects of the development strategy for ADI. involve:
`
`o developing a library whose components are distributed over
`the Internet and are accessible to many classes of users;
`
`I following an evolutionary and incremental approach to both
`design and implementation:
`
`c focusing on the design ofdigitally supportable extensions to
`traditional library functionality. and making ADL consistent
`with requirements of the library community;
`
`a providing the user with access to the implicit information
`available in the DL collections. as well as to the explicit
`information;
`
`a developing collections of spatially-referenced materials.
`
`We comment briefly on these ltey strategic points.
`
`Since we are initially focusing on users who access ADI. from
`the WWW. primary access to ADI. is fromW browsers con-
`. nected to the ADL WWW server. 239.50 clients are also able to
`connect with the ADL SQLJZB9JO query engines. The W
`is based on three critical components: the Uniform Resource Lo-
`cator (URL). the Hyper-Text Markup Language (HTML). and the
`Hyper'l'ext Transfer Protocol (HTTP). The URL defines which
`resource the user Wishes to access. the HTML language allows
`the information to be presented in a platform-independent but still
`well-formatted n-tanncr. while the H11? protocol is the application-
`level mechanism for achieving the transfer of information [8]. The
`W supports general types of multimedia information systems
`while a DL system provides more advanced features for browsing.
`searching. and delivering digitized documents.
`
`A major reason for adopting an evolutionary and incremental
`approach to design and development stems from the rapidity of
`developments in Internet technology. The first increment in the
`development of AOL involved the design and construction of a
`stand-alone “rapid prototype” (RP) system [5]. A second. and
`now completed. increment provided an augmented version of the
`functionality of the RP over www.me third increment is focused
`0n developing a greatly enhanced catalog component based on a
`general model oi metadata and supporting catalog interoperability
`with other DLs.
`
`The approach of providing digitally-supportable extensions to
`traditional libraries is represented in the high-level architecture of
`ADi. shown in Figure 1. Each of these components may bedis-
`tributeri over the Internet. This architecture involves the four major
`
`
`
`Figure 1. The ADL architecture.
`
`components of traditional libraries, namely a catalog component.
`a collection component. an ingest component. and a user interface
`component.
`
`‘
`
`0 The storage component of Am. contains a collection of
`digital objects. The collections on which ADL is initially
`focused include spatially-referenced materials. such as dig-
`itized maps. digitized aerial photographs. andirnages from
`many domains of application [5]. An important aspect of
`the ADL collection is that individual items are typically
`very large. Satellite images are frequently 100 MB in size.
`and sizes of up to two 68 are not uncommon.
`
`PN-00000351
`
`-4-
`
`

`

`-
`
`.
`
`o The catalog component of AOL permits users to make a
`mapping between their requirements for information and
`the most appropriate set of information that can be accessed
`from the library's collection of items. Since it is important
`that spatially-referenced items be accessible by means of
`a spatial reference. each Item is represented in the catalog
`by a spatialfoaqarbtt, which is a pointset characterizing the
`spatial extent or the item in the space over which it is de-
`fined. Footprints arc represented in an extensible metadata
`model for spatial ly-rei’ercnced information (currently com-
`bining the FGDC and USMARC standards [5]) and are in-
`dexed to support efficient search over the catalog holdings.
`The metadata model also incorporates extensions involv-
`ing gazetteers (Le. mappings between named geographic
`features and the footprints of their spatial extent} and pro-
`selected image "textures features". Borh the gazetteer and
`the image texture features are used to support content-based
`search.
`
`a The ingest component involves the digitization of non-
`dlgiral items; the extraction of catalog metadata from items
`that are admitted to the collections (which initially may
`be in either digital or non-digital tom): and the applica-
`tion of transformations. such as wavelet decompositions. to
`ingested iterns.- The metadata extraction is in accordance
`with the metadata model of the catalog Currently available
`metadata includes'approxirnately 450K frame-level records
`for a NASA/Ames database; approximately 350K sheet-
`levcl records for Geodex topographic series: approximately
`100K USMARC map records from MELVYL: and catalog
`records for selected items. such as WWW sites for spatial .
`data in digital form and aerial photographs for four local
`counties in California
`
`a The goal of the interface component is to provide easy ac-
`cess to a core set of functionality for a heterogeneous user
`population. This component contains a browser based on
`l-i'r'l'Pfl-lTML to support user access via the WWW. Current
`implementations of HH'PIH'I'ML impose significant limi‘
`tations on browsers. such as statelessness and the general
`reliance on small. fast transactions.
`in particular. HTML
`lacks mechanisms for presenting spatial data in vector form.
`and provides weak support for the entry of spatially-indexed
`information. The development of the WWW interface com-
`ponent has involved attempts to overcome such limitations,
`and the system provides external viewers and “helper apps"
`for the display of spatially-indexed materials of both raster
`and vector type. These limitations are being overcome with
`the current generation of programmable browsers.
`
`3. Scalability of the ADL
`
`As noted above. digitized data objects in ADI. are typically
`very large. With current network speeds. it is quite infeasible to
`consider sending the full contents of an image file to users for the
`browsing purposes. An image data file of size 100 MB will take
`about 8.5 minutes over a full Tl (lidde/sec) connection. For
`the next generation of lntemet. e.g. T3 (45Mblsec). TV set-top
`
`boxes (lOMbIsee). am and VBNS (lSSMb/sec). the transmission
`time will significantly decrease but the demands for larger image
`files will continue increasing. especially when there are millions
`of users on the interact. The AOL has adopted progressive multi-
`rcsolution and subreglon browsing strategies to reduce lnterttet
`traffic in accessing map images. This approach is based on the
`fol iOWing ideas:
`
`0 Users often make the selection of materials of interest with-
`out browsing the image information at fine-grain levels of
`resolution: in particular, theylnitially need informationonly
`at coarse levels of resolution. Delivering images at coarse
`grain resolution substantially reduces the size of data trans-
`ferred between the client and the ADL server.
`For current computer monitors. it is reasonable to assume
`that one would usually view an image of resolution 512 x
`5I2. or at most ”(I at 1K to fit a screen. Compressed
`5 [2 x 5 l2 color images have size of IOOK-BOOKBytes and
`take around ten seconds to transfer over a‘l'l link.
`
`0 Users should be able to rapidly view higher-resolution ver-
`sions of those images already being viewed to assist their
`selection.
`it is desirable to have a method that can con-
`struct a higher resolution image from the lower resolution
`image with only a small amount of additional data. Ifsuch
`construction can be performed at the client site. then since
`the lower solution image is already available at the client
`site. only the difference data needs to be transferred from
`the ADL server over the Internet. Note that the size of dif-'
`fercrtce data is usually small. taking less than 1 second to '
`deliver in a Tl link.
`
`0 Satellite map images usually have high resolutions (cg.
`2KI x 2Kl and 10)? at 10K). and such high resolutions
`can not be viewed on a regular screen. A reasonable user
`requirement is to browse a subregion of an image to iden-
`tify details of interest. Popular subregion resolutions are
`likely to be around 512 at 512. Thus supporting subregion
`browsing can also significantly reduce network bandwidth
`rcquiremean.
`
`To support these features. the ADL system is using a wavelet~
`based hierarchical data representation for mum-resolution decom-
`position of images. Images and titelr subtcgions can be browsed in
`difl'erent levels of resolution and can be delivered in a progressive
`manner [2]. We briefly describe the techniques of wavelet image
`data retrieval and transformation below.
`
`Given an image. a forward wavelet transform produces a sub-
`sampled image of lower resolution called a "thumbnail". and three
`additional coefiicient data sets. More formally. for the given quart-
`tized image I; of resolution R x R'. we specify the input and
`output of the forward wavelet transform as follows.
`
`(I3. Gs, Ca. Ca] =- FonttmrLW'mmleieA).
`
`I; is the thumbnail of resolution 4}- x s. 01.0: and c. are or
`resolution § at 1}. Fig. 2 depicts the resultof wavelet transform.
`
`lRectangular shapes can also be supported while square images are
`used here for demonstration.
`
`PN-00000352
`
`-5-
`
`

`

`resolutions. the server retrieves compressed image coefli~
`cient data from permanent storage and delivers it to the
`client as the client machine performs the inverse wavelet
`to construct images of higher resolutions from the existing
`thumbnail and new coefficient data. If the client machine
`does not have such a capability. the server performs the
`image reconstnrction.
`o Retrieval ofimage subregions: after a client identifies an
`interesting point in an image. the request is made for an
`enhanced resolution view of the subregion surrourrding that
`point. The appropriate image data is then retrieved and sent
`to the client.
`
`if a user finds it necessary to access the original large image.
`e.g.. forseientiftc applications. the ADI. will direct this requestto a
`large storage server (currently a [TB robotic tape storage device at
`the San Diego Supercomputer Center). This file Will be delivered
`via ftp since large images (with size iO-lOOMB). take along time
`to transfer over the Internet. We do not address the issue of hp
`delivery of large documents in this paper.
`
`’
`
`it should be noted that there arelothcr operations performed in
`the ADI. server. For example. content-based database queries to
`find suitable images are important. so the speed of the database
`server and its supporting mass storage is vital [2. 12]. We assume
`that the database functionality is provided by a separate computer
`within ADL. and so focus ourattention ontheproblemofdelivering
`data. whether simple files or wavelet data. to the user as quickly.
`as possible over the Net. We also focus on scalability issues in
`supponing the mum-resolution and subregion browsing of images.
`
`While we have addressed issues relating to the network band-
`width bottleneck. the ADL server itself can be another bottleneck
`in document delivery. For example. the computation and disk IIO
`perfonnedirt the ADLfor decompressing and accessing subregiotts
`7 of images involve a substantial amount of time and occupy disk
`I10 channels for long periods.
`
`There are several aspects in assessing the scalability of 2: DL
`system. When there are many requests coming in. the typical
`situation (such as one in the current WWW servers) is that the
`server's response for an individual request becomes slow. For a
`single-workstation server. thereis an uppcrbound for the numberoi'
`requests per second (RPS) that the server can handle. For example.
`a SPARC 10 can handle 4 requests per second for delivering files
`of size [MB-2MB. When the system limit is reached. the requests
`fail due to congestion at the server. Our overall objective for
`the system is to reduce and sustain the response time under large
`numbers ofsimultaneous requests. We define the response time for
`a request as the length of time from when a request is initiated until
`all requested information anives at the client for that transaction.
`Another performance goal is to have the RPS limit of the system
`as large as possible since the access activities of cunent popular
`WWW sites already indicate that 2 20 requests per second can be
`expected.
`
`We perfumed an experiment to determine the network band-
`width requirements after adopting the progressive image browsing
`strategy. and examine the ADL server requirements Table 1 gives
`the compressed size for a number of greyscale images. Each'image
`
`
`
`
` .Z . o Lg': {"1925
`
`"#541312?“
`
`
`2511sign»
`
`
`left A map Image 1’. .(right) The
`Figure 2.
`I; after applying the forward
`thumbnail
`wavelet transform.(left)
`
`The inverse wavelet transform can be performed to re-construct
`the original image on-the-fly from the coefficient data sets and the
`thumbnail.
`
`Ir Inucr:e-Wm.eiedUh. Cr. 01.0))
`Ifimage thumbnail 1; is available at the client site. then by request-
`ing that ADI. sends (71.03.03. image I. can be reconstructed at
`the client site. The image reconstruction is not time consuming.
`raising about 1.5 seconds for a 5l2 x 512 image on 3 SUN SPARC
`5. The size of compressed data Cr, 05.61: to be transferred is in
`the range of 10 to lOOKBytes. which takes less than i second over
`a T1 link.
`
`if a user wishes to access subregions of an image 1'1. then
`the corresponding subrcgions in thumbnail 11.0.. 01.6; can be
`retrieved and the reconstruction perforated accordingly. We model
`such a process as follows.
`
`Inner-an’ :clei(sub'regian(!z),
`2:
`sttbregtlanur)
`:rrbregian(Cr). attbregionica). mtbregt'msccsn.
`A detailed definition of forward and inverse wavelet functions
`can be found in {4]. The time complexity of wavelet transforms
`is proportional to the image size. The wavelet transform can be
`applied recursively. namely the thumbnail 1: can be decomposed
`funher to produce smaller thumbnails 1;. f9. - - -. The ingest cont-
`ponent of the ADI. performs the forward transformation to decom-
`pose data images into thumbnails and the coefficient data set.
`
`The AOL system uses the above wavelet technique and at run-
`time. the following operations will be frequently invoked on the
`ADI. server.
`
`I Retrieval of regular files and thumbnail images: when a
`client requests a thumbnail for the initial browsing. the
`server retrieves the corresponding file from the ADL stor-
`age.
`
`- Retrieval of Image coeficr'ent data for progressive image
`browsing: when a client further requests images with higher
`
`PN-00000353
`
`-6-
`
`

`

`‘\
`l
`
`~ .
`
`s
`
`O
`was eight bits per pixel. and was a square image. We use the com-
`- pression algorithm developed in [l I] whose compression ratio is
`- approximately 9093. The compressed full images are still sizeabie.
`Using progressive image delivery can reduce network demands
`since full resolution images are not always required. For example.
`with the “pentagon" image (a satellite photo of the Pentagon}. the
`128 x in pixel thumbnail requires just 3.3K. and only 6.2K of
`additional data is needed to view this image at a 256 x 256 res
`olution. This indicates our multi-t'esolutionlsubrcglon browsing
`strategy significantly reduces network bandwidth requirements.
`But retrieving subregions from the compressed images imposes
`processing cost. On a Sun SPARC station 10. the current im-
`plementation takes 2 secondspf CPU time for extracting 8K3 of
`compressed coefficient data from a 2K rt 2K pixel greyscole image.
`To support 20 users per second. at least 40 high-end workstations
`need to be employed.
`
`
`
`—Wm-zu
`[mm 7K
`1K _EEX!
`mm 47K|
`3.3m an IE!
`
`
`—lmillmaiflil-Im3
`
`
`“Irma BK 271-:
`
`
`
`
`
`Figure 3. AOL multl-node server architecture.
`
`Table 1. Wavelet compressed data size for
`progressive delivery.
`"Full" is the com-
`pressed fuii image size. The thumbnail size
`is 1/8 of the original Image dimensions.
`
`To reduce and sustain the response time under large numbers
`of simultaneous requests, our strategies involve:
`
`a Utilizing multiple networked commodity workstations and
`disks to build a scalable server. The computing environment
`can be heterogeneous and workstation/processor units with
`different speeds and different loads at any time.
`c Developing sophisticated dynamic scheduling algorithms
`for exploiting task and I/O parallelism adaptive to the run-
`time change ofsystemrcsource 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 re-
`qusts toa properunitt‘orcfficient processing. The overhead
`involved for current resource load assessment and schedul-
`ing should be minimized.
`
`network resources. The load of a processing unit must be moni-
`tored so that requesLs can be distributed to relatively lightly loaded
`processors. An ADI. request following the HTTP protocol is han-
`dled through a TCPIIP connection and then subsequently through
`a forked subprocess. This subprocess may retrieve a file or invoke
`a Computational Gateway Interface (CGI) program implementing
`an ABL-spcciiic operation. In processing most ADL requests. im-
`age data needs to be retrieved from disks. so disk channel usage '
`must be observed. Simultaneous user requests accessing different
`disks can utilize parallel 1/0 to achieve higher throughput. The
`local interconnection network bandwidth afiects the performance
`of file retrieval since many filesmay not reside in the local diskofa
`processor. Therefore remote file retrieval through the network file
`system will be involved. Local network traffic congestion could
`dramatically slow the request processing.
`
`Thus a critical component of our system is a load daemon mn-
`ning at each processor to detect its own CPU. disk. and network
`load. and periodically broadcasts this information to other proces-
`sors. Our experiments show that such overhead is insignificant.
`
`4.1. Internal scheduler structure
`
`4. System Resource Monitoring and. Request
`- Scheduling
`
`in this section we first discuss the monitoring of system rc-
`sourccs. introduce the functional modules ol'ourschedulcr. and we
`then present an algorithm fordetermining the processor assignment
`of a given ADL request.
`
`There are several factors that affect the response time in pro-
`cessing ADL requests. These include loads on CPU. disk. and
`
`There are two approaches to designing the scheduler. One is
`to have a centralized scheduler running on one processor such that
`all 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.
`Our main reason for not adopting this approach is that the central
`distributor becomes a single point of failure. making the entire
`system vulnerable.
`
`The current version of our system uses a disu-ibuted scheduler.
`The user requests are first evenly routed to processors via Domain
`Name System (DNS) rotation. DNS rotation provides the initial
`
`PN-00000354
`
`-7-
`
`

`

`‘1'.
`
`assignment of HTTP requests and is used in the NCSA multi'
`workstation server [10]. In this scheme. multiple realmachines are
`mapped to the same ii" name. When a client requests the network
`ID of the machine name (e.g.. www.cs.ucsb.edu). the DNS at the
`server site rotates the network IDs. picking one (e.g.. l.l.l.l) to
`send back to the client. The rotation on available workstation
`network [Dr is in a roundorobin fashion. This functionality is
`available in current DNS systems. The major advantages of this
`technique are simplicity and ease ofimplementation [10].
`
`The DNS is subject to caching problems when attempting to
`do dynamic load balancing. and it assigns requests without eon-
`suiting dynamically-changing system load information. Thus our
`scheduler conducts a further redirection of requests. Each proces-
`sor in the ADL server contains a scheduler and those processors
`collaborate with each other to exchange system load information.
`After a request is routed tqa processor via DNS. the scheduler in
`that processor makes a decision regarding whether to process this
`request or redirect it to another processor. An HTTP request is
`not allowed to be re-routed more than once in order to avoid the
`ping-pong effect.
`
`The functional structure of the scheduler at each processor is
`depicted in Fig. 4. It contains a daemon based on NCSA httpd code
`for handling httpd requests. with a broker module mat determines
`the best possible processor to handle a given request. The broker
`consults with two other modules. the oracle and the loodd. The
`oracle is a miniature expert system. which uses a user~supplied
`table to characterize the CPU and disk demands for a particular
`task. The loodd 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 responded
`in a preset period of time as unavailable. When a processor leaves
`orjolas the resource pool. the loodd daemon will be aware of the
`change.
`RequestA
`
`Oreo
`Analyze the memo and 9° demand.
`
`Load oomon
`Ugo-Ito eyelet-n told hie.
`
`ladlehlromothcroodu
`
`
`
`
`
`
`
`Select a node to - cease.
`Reduction or procu- locally.
`
`
`
`the new location. so redirection is virtually transparent to the user.
`
`The primary advantages of URL redirection are the simplicity
`of implementation and universal compatibility. An simple flow-of-
`control modificationcan be made within a WWW server. whcrcthc
`main complexity lies in the routines to determine the optimal server
`{or a particular request. Furthermore. the approach lies \vell within
`our design parameters: it does not require a modification of the
`HTTP protocol. is reasonably efficient. and is able to support so-
`phisticated optimization algorithms. The primary disadvantage of
`URL redirection in practice is the added overhead or an additional
`connectlpirss requestlpatselreSpond cycle after the redirection oc-
`curs. We will show that such overhead is more than negated by
`improved performance overall.
`
`4.2. The processor assignment of ADL requests
`
`In (ll. we designed an algorithm that decides the routing for a
`general HTTP request. In this subsection, we discuss the strategies
`for the ADL system
`
`In the previous work on load balancing (oz. [i3]). usually one
`factor (CPU load) is considered. A processor can be classified as
`lightly loaded and heavily loaded based on the CPU load. One
`purpose of such a classification is to update load information only
`when a classification changes. Such a strategy reduces unnecessary
`overhead. In our problem context. it is hard to classll’y a processor
`as heavily orlighted loaded since there are several load parameters.
`A processor could have a light CPU load but its local disk may
`receive many access requests from the network file system.
`
`r------...._.._-..--- "I Queue-u
`
`
`
`MIICIHMDIHIF‘DWIM
`
`Figure 4. The functional modules at a sched-
`uler f