Attorney's Docket No. 02577.P00lD
`
`D
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`In Re Patent Application of:
`
`Keith Lowery et al.
`
`Application No.: 09/234,048
`
`Filed:
`
`January l9, 1999
`
`For:
`
`System and Method for Managing
`Dynamic Web Page Generation
`Requests (As Amended)
`
`Assistant Commissioner for Patents
`
`Washington, D.C. 20231
`
`\l\/\/\/i%/%/\l\.#\.#
`
`)
`
`Sir:
`
`INFO
`
`TION DIS
`
`STATEME
`
`Enclosed is a copy of Information Disclosure Citation Fonn 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 Infonnation Disclosure 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(e). Ifso, then enclosed with this Infomiation
`Disclosure Statement is 9_n_e of the following:
`
`A statement pursuant to 37 C.F.R. §l.97(e) or _
`
`A check for 352% for the fee under 37 C.F.R. § l.17(p).
`
`- 1 -
`
`LJV!cak (oa/23198)
`
`
`
`Microsoft Corp. V. Parallel Networks Licensing, LLC PN'°°°°°348
`IPR2015-00483
`
`PN EXHIBIT 2004
`
`Examiner:
`
`Unassigned
`
`ArtUnit: 2755
`
`--t
`c:
`ro-ul
`:2
`ca
`
`3 Zr
`
`"
`:3
`
`o:
`
`93
`
`

`
`37 C.F.R. §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. §1.97(e);
`
`A petition requesting consideration of the Information Disclosure
`_ Statement; and
`
`
`for the fee under 37 C.F.R. §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.
`
`Respectfully submitted,
`
`
`
`12400 Wilshire Blvd.
`Seventh Floor
`
`Los Angeles, CA 90025-1026
`(408) 720-8598
`
`. I
`
`hereby certify that this correspondence is being deposited with the United States Postal Service as firs: class
`mail with sufficient postage in an envelope addressed to the Assistant Commissioner for Patents. Washington. D.
`C. 20231 on .
`(Date of Deposit)
`
`(Typed or printed name of person mailing correspondence)
`
`(Signature of person mailing cor-res
`
`cnce)
`
`- 2 -
`
`LJVIcak (08/28/98)
`
`PN-00000349
`
`

`
`.
`
`Q
`
`. Scalability Issues for High Performance Digital Libraries on the World Wide Web
`s
`
`Daniel Andresen. Tao Yang. Omer Egccioglu. Oscar H. Ibarra. and Terence R. Smith
`Department of Computer Science
`University of California
`Santa Barbara, CA 93106
`, {dandrese, tyang, omcr, ibarra, srnithtr},'@cs.ucsb.edu
`
`
`
`We Investigate scalability issues involved in developing high
`performance digital library systems. Our observations and so-
`lutions are based on our e.t.perIerIce with the Alexandria Digital
`Library (ADL) testbed under development at UCSB. The current
`ADL system provides ort-line browsing andprocessing cfdigitired
`mapsand othergeo-spdglally mapped data via the World Wide Web
`{Wlrl-’l'V). A primary activity ofthe ADL system involves computa-
`tion anddisk I/Ofor accessing compressedrnulti-resolution images
`with hierarchical data structures. as well as other duties such as
`supporting database queries and on-the-fly HTML page genera-
`tion. Providing rnulti-resolution image browsing services can re~
`duce network trofic but impose some additional cost at the server:
`We discuss the necessity ofhaving a multiprocessor DL server to
`match potentially huge demands in sin-tultaneotts access requests
`from the Internet. We have developed a distributed scheduling
`system firr processing DL requests. which actively ntanltars the
`usages of CPU. I/O channels and the interconnection network to
`efectively distribute worl: across processing units to exploit task
`and 1/0 parallelism. We present an ea-perirnental study on the per-
`fonnance oforu-scheme in addressing the scalability issues arising
`In ADL wavelet processing ondfile retrieval. Our results indicate
`that the system delivers goodperfortnance on these types oftasks.
`
`1. Introduction
`
`The notnbcrofdigital librtuy (DL) projects is incraslng 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 Internet.
`
`Performance and scalability issues are especially important for
`the Alexandria Digital Library (ADL) project [2, I4]. The fun-
`damental goal or this project Is to provide users with the ability to
`access and process broad classes of spatially-tctctcnccd materials
`from the Internet. Materials that are currently in the collections of
`ADL and accessible through the ADL World Wide Web (WWW)
`
`server include geographically-referenced items such as digitized
`maps. satellite images. digitized aerial photographs. and associated
`tnctadata. When fully developed. ADL will comprise a set ofnodes
`disu-ibutcd 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 others rcquirc extensive process-
`ing to be of value in certain applications. The catalog component
`alone contains a rnctadatabasc of significant size.
`
`Before SllCl'l_gDlIl8 can be achieved. however. major issues of
`pcrfarm'..tnce and scalability must be rcsolvod. particularly for DI..s
`supporting extensive collections or collections with large ‘data'
`Items. Critical pcrlomtance bottlenecks that must be overcome
`to assure adequate access over the Internet lnvolve server process-
`ing capability and network bandwidth. While we expect network
`communication technology to improve steadily. particularly with
`the advent of ATM and B-ISDN. we still need to consider the min-
`imization or network tralfic in the design of the current system.-
`Additionully. the scrvcrpcrtormancc 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 t.hc
`subregion retrieval. to avoid unnecessary large image transtttissiott.
`1'hc trade-ofl". 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
`server Involves much more intensive 1/0 and heterogeneous CPU
`activities. a multi-processorscrvcr becomes indispensable [2].
`
`In this paper. we investigate the network bandwidthrequircrnent
`in the ADL system using progressive image browsing retrieval and
`the computational and no demands for supporting such activities.
`We study the use of networks olcxlsting. inexpensive workstations
`anddisks to augment the processing and storage cnpabggles of DL
`servers. In particular. we have investigated toiirhat cxtcagrccycling
`the idle cycles of processing units in networks of-workstations.
`as well as retrieving files in parallel from ll|¢Xp$l‘I5l}@l$li‘;-Call Cr‘;
`significantly improve the scalability of a Di.‘ server responding to "1
`many simultaneous requests.
`3,
`0" 2-
`!" § [-11
`3 an O
`§
`3:
`
`;'.1.,-
`
`.
`
`PN-00000350
`
`-3-
`
`

`
`'
`
`1
`
`o
`
`we have implemented our scheme on rt cluster of SUN SPARC
`- nodes connected by a Meilto CS-2 Elan network. and clusters of
`' S-UN and DEC workstations connected by Ethernet. Each process-
`ing unit (e.g. a SUN SPARC node) is linked to rt 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 disk
`contention when multiple I/O requests access the same dislt. By
`understanding these effects. we can achieve server scalability. In
`particular. by actively monitoring the run-time CPU. disk I10. and
`network loads of system resource 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 ourworlc 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-II 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
`time.
`
`The paper is organized as follows: Section 2 briefly describes
`the ADL Project. Section 3 discusses the scalability issues ad-
`dressed in the ADL system for ameliorating network and server
`boltlenecics. Section 4 discusses scheduling and resource moni-
`toring strategies in our multi-processor system. Section 5 presents
`experimental studies concerning multi-node performance and an-
`alyzing overhead and the effectiveness of resource scheduling.
`Section 6 discusses related work. Section 1 discusses conclusions
`and future worlt.
`a
`
`2. The Alexandria Digital Library on the
`WWW
`
`Key aspects of the development strategy for ADI. involve:
`
`a developing a library whose components are distributed over
`the Internet and are accessible to many classes of users:
`
`I lollowing an evolutionary and incremental approach to both
`design and implementation:
`
`a focusing on the design ofdiglrally supportable extensions to
`tratfttional library functionality. and making ADI. consistent
`with requirements oi‘ the library community;
`
`a providing the user with access to the implicit information
`available in the DL collections. as well as to the explicit
`infonmtion;
`
`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 from WWW browsers cort-
`. nected to the ADL WWW server: 239.50 clients are also able to
`connect with the ADL SQLJZ39.50 query engines. The WWW
`is based on three critical components: the Uniform Resource Lo-
`cator (URL). the l{yperTcxt Marlcup Language (HTML). and the
`I-lyperText Transfer Protocol (HTTP). The URL defines which
`resource the user wishes to access. the HTML language allows
`the information to be presented in a platforrn-independent but still
`well-formatted manner. while the l-lTl'P protocol is the application-
`level mechanism for achieving the transfer of information [8]. The
`W supports general types of multimedia info:-tnation 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 commotion of a
`stand-alone “rapid prototype” (RP) system [5]. A second. and
`now completed. increment provided an augmented version of the
`functionality oi the RP over WWW.'l'he third increment is focused
`on developing a greedy enhanced catalog component based on a
`general model oi rnetadara 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 l. Each of these components may be_d.is-
`tributetl 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.
`
`_
`
`o The storage component of ADL 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. andimages 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 l00 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 malte a
`mapping between their requirements for information and
`the most appropriate set of infon-nation that can be accessed
`from the library‘: 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 rporiolfoorprlnr, which is a pointset characterizing the
`spatial extent of the item in the space over which it is de-
`fined. Footprints are represented in an extensible metsdata
`model for spatial Iy-referenced infonnation (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 pre-
`selected image "textures features". Both the gazetteer and
`the image texture feature_s are used to support content-based
`search.
`
`0 The ingest component involves the digitization of non-
`dlgital items: the extraction of catalog rnctadata from items
`that are admitted to the collections (which initially may
`be in either digital or rtort-digital tom): and the applica-
`tion of transformations. such as wavelet decompositions. to
`ingested iterns.- The mctadata extraction is in accordance
`with the metadata model of the catalog Currently available
`tnetadata includesapproximately 450K frame-level records
`for a NASAIAmes database; approximately 350K sheet-
`levcl records for Geodex topographic series: approximately
`IDOK USMARC map records front 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
`
`I 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-l'l"l'PIl-ITML to support user access via the WWW. Current
`implementations of I-FITPII-i'I'ML impose significant limi-
`tations on browsers. such as statelessness and the general
`reliance on small. fast transactions.
`in particular. HTML
`laclts mechanisms for presenting spatial data in vector form.
`and provides weak support for the entry of spatially-indexed
`infomtation. 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 cttrrertt 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 l00 MB will take
`about 8.5 minutes over a full Tl (l.5tl4MbIsec) connection. For
`the next generation of lntemet. e.g. T3 (45MbIset:). TV set-top
`
`boxes (lohlblsec). ATM and VBNS (l55MbIsec). 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 lntemet. The AOL has adopted progressive multi-
`resolutlon and subreglon browsing strategies to reduce lntemet
`traffic in accessing map images.
`‘This approach is based on the
`following 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, theyinltially need infonnationonly
`at coarse levels of resolution. Delivering images at coarse
`grain resolution substantially reduces the size of data unna-
`ferred hetween 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 st
`5I2. or at most lK| st IX to fit a screen. Compressed
`5 l2 3: 5 I2 color images have size of 100K-300KBytes and
`take around ten seconds to transfer over a‘l'l link.
`
`e Users should be able to rapidly view higher-resolution ver-
`sions of those images already being viewed to assist their
`selection. I: is desirable to have a method that can con-
`stntet 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-'
`ference data is usually small. taking less than 1 second to '
`deliver in a Tl link.
`
`0 Satellite map images usually have high resolutions (e.g.
`2Kl at 2K| and 10K 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 st 512. ‘thus supporting subregion
`browsing can also significantly reduce network bandwidth
`requiremenu.
`
`To support these features. the ADI. system is using a wavelet-
`based hierarchical data representation for tnulti-resolution decom-
`position of images. images and their snbregions can be browsed in
`different levels of resolution and can be delivered in it 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 ts "thumbnail". and three
`additional coefiicient data sets. More fomtally. for the given quan-
`tized lmage I; of resolution R x R‘. we specify the input and
`output of the forward wavelet transfon-n as follows.
`
`(I3, (I4, 0;, G3] I: Fo1=ttmrd.W'.nuele£e1‘.t).
`
`I; is the thumbnail of resolution -"5! at -§. (31.0: rind G; are of
`
`resolution § at Fig. 2 depicts the resultof wavelet transform.
`
`‘Rectangular shapes can also be supported while square images are
`used here for demonstration.
`
`PN-00000352
`
`-5-
`
`

`
`resolutions. the server retrieves compressed image cocl’ii~
`cient data from permanent storage and delivers it to the
`client as the client rnncltine performs the inverse wavelet
`to construct images of higher resolutions from the existing
`thumbnail and new cocflicieat data. If the client machine
`does not have such a capability. the server performs the
`image reconstruction.
`o Retrieval oflmage srtbregions: after a client identities an
`interesting point in an image. the request is made for an
`enhanced resolution view of the subregion surrounding that
`point. The appropriate image data is then retrieved and sent
`to the client.
`
`
`
`
`:._‘!;,E
`
`
`‘y: “L.
`,- 1".-'.-‘ .‘ 3+
`;;_ ,r.._-1 rt.~..
`.
`, .
`
`
`,_
`
`.
`
`.
`
`'-V
`..s;= g.-,.¢
`
`left A map image l’..(right) The
`Figure 2.
`I; after applying the torwar
`thumbnail
`wavelet translorm.(lelt)
`-
`
`The inverse wavelet transfonn can be performed to re-construct
`the original image on-the-fly from the coeificient data sets and the
`thumbnail.
`
`Ir = Inttcr.s_e-Wm:elerl(lh. 63,01. 0:).
`lfimage thumbnail 1; is available at the client site. then by request-
`ing that ADI. sends Ci, 03,03. image I. can be reconstructed at
`the client site. The image reconstruction is not time consuming.
`taking about 1.5 seconds for a 5l2 x 512 image on a SUN SPARC
`5. The size of compressed data 0;, 65,61; to be transferred is in
`the range of to to lO0KBytes. which takes less than i second over
`a T1 link.
`
`if a user wishes to access subregions of an image It. then
`the corresponding subrcgions in thumbnail Iz,C|.C'1.C-'3 can be
`retrieved and the reconstruction perforated accordingly. We model
`such a process as follows.
`
`:elei(sub'reglon(i'z),
`Inuor-sc.l-’
`2:
`:u5rc9lan(Ir)
`srrbr-eglon(C:). sttlu-egictn(C:), attbre_qs'ms(C)]].
`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
`further to produce smaller thumbnail: 1;. 15,- - -. The ingest com-
`ponent of the ADI. perfonrts the forward transformation to decom-
`pose dara images into thumbnails and the cociiicient data set.
`
`The ADL 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 filer and rhuntbnail intagcsr when a
`client requests a thumbnail for the initial browsing. the
`server retrieves the corresponding file from the ADL stor-
`age.
`
`0 Retrieval of Image coefiicient data for progressive image
`browsing: when a client further requests images with higher
`
`if a user tinds it necessary to access the original large image.
`e.g.. for scientific applications. the ADI. will direct this request to a
`large storage server (currently at ITB robotic tape storage device at
`the San Diego Supercomputer Center). 'i1'tis file will be delivered
`via ftp since large images (With size to-IOOMB). take along time
`to transfer over the Internet. We do not address the issue of ftp .
`delivery of large documents in this paper.
`
`It should be noted that there are other operations perfonned 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 onthe problemofdelivering
`data, whether simple tiles or wavelet data. to the user as quickly.
`as possible over the Net. We also focus on scalability issues in
`supponing the rnultl-resolution and subregion browsing of images.
`
`While we have addressed issues relating to the network band-
`width bottlcncclt. the ADL server itself can be another bottleneck
`in document delivery. For example. the computation and disk IIO
`pcriorrnedin the ADLfor decompressing and accessing subregions
`” of images involve a substantial amount of time and occupy disk
`IIO 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 Iapperbound for the numberof
`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 IMB-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 infonnation arrives at the client for that transaction.
`Another perfonnance goal is to have the RPS limit of the system
`as large as possible since the access activities of current popular
`WWW sires already indicate that 2 20 requests persccond can be
`expected.
`
`We performed an experiment to determine the network band-
`width requirements after adopting the progressive image browsing
`strategy. and examine the ADL server reqttircrrtenLs. Table 1 gives
`the compressed size for a number of greyscale Images. Each image
`
`PN-00000353
`
`-6-
`
`

`
`'\
`1
`
`~
`
`-
`
`'-
`
`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 90%. The compressed full images are still sizeable.
`Using progressive image delivery can reduce nctworlt demands
`_ since full resolution images are not always required. For example.
`with the "pentagon" image (rt satellite photo of the Pentagon}. the
`I28 3! I28 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-tesolutionlsubrcgion browsing
`strategy significantly reduces network bandwidth requirements.
`But retrieving sulsregions 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 ct’
`compressed coefticicnt data from a 2K 1 2K pixel greyscale image.
`To support 20 users per second. at least 40 high-end workstations
`need to be employed.
`
`
`
` lfl£l
`lmfllffil
`7K
`1K EEK!
`[commits 47K|
`3.3KI
`6K In}!
`
`
`lmlllltfiafiflillflala
`
`
`[Emil 13K
`271-:
`
`
`
`
`
`Figure 3. ADL multl-node server architecture.
`
`Table 1. Wavelet compressed data size for
`progressive delivery.
`"Full" is the com-
`pressed fuli 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 Utilising multiple netvrorlted commodity workstations and
`dislts to build a scalable server. The computing environment
`can be heterogeneous and worlrstationlproeessor units with
`-different speeds and difierent loads at any time.
`c Developing sophisticated dynamic scheduling algorithms
`for exploiting task and I/O parallelism adaptive to the run-
`time change ofsystemrcsourcc 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-
`qumts toa properunitforeflicient processing. The overhead
`involved for current resource load assessment and schedul-
`lng should be minimized.
`
`network resources. ‘the load of a processing unit must be moni-
`tored so that requests can be distributed to relatively lightly loaded
`processors. An ADL request following the I-l'l'i'P protocol is han-
`dled through a TCPIIP connection and then subsequently through
`a forked subprocess. This subprocess may retrieve a tile or invoke
`a Computational Gateway Interface (CGI) program implementing
`an ADL-specific operation. In processing most ADI. requests. im-
`age data needs to be retrieved from dislrs. so dislt channel usage '
`must be observed. Simultaneous user requests accessing different
`dislts can utilize parallel V0 to achieve higher throughput. ‘Ihe
`l_ocal interconnection rtetworlt bandwidth afiects the perfortnartee
`olllle retrlevalslnce many filesrnay notreside luthe local disltofa
`processor. Therefore remote file retrieval through the network tile
`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 networlr
`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 re-
`sources. introduce the functional modules ofourscheduier. and we
`then present an algorithm fordeterrnining the processor assignment
`of a given ADI. 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 inlorrnation. 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. malszing the enti.re
`system vulnerable.
`
`The current version of our system uses a distributed scheduler.
`The user requests are first evenly routed to processors via Domain
`Name System (DNS) rotation. DNS rotation provides the initial
`
`PN-00000354
`
`-7-
`
`

`
`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-oi?
`control rnodificationcan be made within a WWW server. whercthe
`main complexity lies in the routines to determine the optimal server
`for a particular request. Furthermore. the approach lies well within
`our design parameters: it does not require a modification of the
`l-tT1'P 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 of an additional
`connectlpitss requestlparselrespond 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 (ii. 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 (e.g. [13]). 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 su-ategy reduces unnecessary
`overhead. In our problem context. it is hard to classify a processor
`as heavily orlighted loaded since there are several load par'a'meters.
`A processor could have a light CPU load but its local dislr may
`receive many access requests from the network file systctn.
`
`IIIIIIIIIIIIlII
`
`:..------...._..--..--- ..t
`
`Qouw-u
`
` AnII¢InlwrIrurI¢¢otIpIflIIIIbIf6°OI4|flB|l|Cl|'||-
`
`o
`
`- a
`
`ssignment of l~lT'l’P requests and is used in the NCSA multi-
`woritstation server [[0]. In this scheme. multiple realmacitirtcs are
`' mapped to the same ii’ name. When a client requests the networtt
`ID of the machine name (e.g.. www.cs.uesb.cdu). 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 ID: is in a round-robin fashion. This functionality is
`available in current DNS systems. The major advantages of this
`technique are simplicity and ease ofimplcmentation [10].
`
`N1’'
`
`The DNS is subject to caching problems when attempting to
`do dynamic load balancing. and it assigns requests without eon-
`sulting dynamically-changing system load information. Titus 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 infonnation.
`After a request is routed to_a processor via DNS. the scheduler in
`that processor makes a decision regarding whether to process this
`request or redirect it to another processor. An I-i'l"i'P 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 Hg. 4. It contains a daemon based on NCSA httpd code
`for handling httpd requests. with a broker module that determines
`the best possible processor to handle a given request. The broker
`consults with two other modules. the oracle and the iocrciri. 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 iondd daemon is responsible for updating the system
`CPU. network and disk toad 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
`or join: the resource pool. the iortdd daemon will be aware of tire
`change.
`
`Flodinctton