(12) United States Patent
`Farber et al.
`
`USOO6185598B1
`(10) Patent No.:
`US 6,185,598 B1
`(45) Date of Patent:
`Feb. 6, 2001
`
`(54) OPTIMIZED NETWORK RESOURCE
`LOCATION
`
`(75) Inventors: David A. Farber, Oak View, CA (US);
`Richard E. Grier Red Lodge, MT
`(US); Andrew D. Swart, Westlake
`Village; James A. Balter, Santa
`Barbara, both of CA (US)
`(73) ASSignee: pital Island, Inc., San Francisco, CA
`
`(*) Notice:
`
`Under 35 U.S.C. 154(b), the term of this
`patent shall be extended for 0 days.
`
`(21) Appl. No.: 09/021,506
`
`(51) Int. Cl. ............................. G06F 15/16; G06F 13/00
`(52) U.S. Cl. .......................... 709/200; 709/203; 709/226;
`709/233; 709/234; 709/235; 709/236; 709/237;
`709/239; 709/240; 709/241
`(58) Field of Search ..................................... 709/200, 203,
`709/223, 224, 226, 233, 234, 235, 238,
`239, 240, 241
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`1/1985 Kitajima et al. ..................... 709/105
`4,495,570
`6/1986 Olivier ..........
`... 370/217
`4,594,704
`2/1988 Krum et al. ...
`... 370/449
`4,726,017
`6/1989 Eguchi et al. .
`... 709/105
`4,839,798
`4/1990 Eggers ................................... 386/96
`4,920,432
`8/1990 Cohen .................................... 386/69
`4,949,187
`8/1990 Caro .......
`... 709/203
`4,949.248
`12/1992 Bradley ...............................
`348/7
`5,172,413
`10/1993 Rozmanith ........................... 709/219
`5,253,341
`2/1994 Newmark et al. ..................... 712/29
`5,287,537
`3/1994 Morales .........
`so
`5,291,554
`5341. 477 * 8/1994 Pitkin et all
`709/226
`5,37,532
`12/1994 Gelman.
`... 3487
`5,410,343
`4/1995 Coddington .............................. 348/7
`5,414,455
`5/1995 Hooper ..................................... 348/7
`5,442,389
`8/1995 Blahut ...................................... 348/7
`
`Reflector 108
`
`8/1995 Hooper ..................................... 348/7
`5,442,390
`8/1995 Northcutt ............................. 709/219
`5,442,749
`11/1995 Eadline .................................... 707/3
`5,471,622
`52 1240. bon- - - - - -
`7.
`2- Y- a-2
`OllOnley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5,515,511
`5/1996 Nguyen ................................ 709/219
`5519.435
`5
`2- - - 2
`/1996 Anderson ................................. 348/8
`5,528,281
`6/1996 Grady ....................................... 348/7
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`2281793
`3/1995 (GB).
`WO 97/11429
`3/1997 (WO).
`OTHER PUBLICATIONS
`
`Andresen et al., “SWEB: Towards a Scalable World Wide
`Web Server on Multicomputers", Proceedings of IPPS, Apr.
`
`Mourad et al., “Scalable Web Server Architectures', Pro
`ceedings IEEE Symposium on Computers and Communi
`cations, Jul. 1, 1997, pp. 12-16.
`Adler, “Distributed Coordination Models for Client/Server
`Computing”, Computer, vol. 28, No. 4, Apr. 1, 1995, pp.
`14-22.
`International Search Report dated Jun. 8, 1999 for PCT/
`US99/01477.
`Primary Examiner Zarni Maung
`ASSistant Examiner Almari Romero
`(74) Attorney, Agent, or Firm-IP Group of Pillsbury
`Madison & Sutro LLP
`
`(57)
`ABSTRACT
`ReSource requests made by clients of origin Servers in a
`network are intercepted by reflector mechanisms and Selec
`tively reflected to other servers called repeaters. The reflec
`torS Select a best repeater from a set of possible repeaters and
`redirect the client to the selected best repeater. The client
`then makes the request of the Selected best repeater. The
`bl
`ittent
`1
`t least
`fth
`resource is possibly rewritten to replace at least some of ine
`resource identifiers contained therein with modified resource
`identifiers designating the repeater instead of the origin
`Server.
`
`27 Claims, 6 Drawing Sheets
`
`E.
`. Determine
`client's group
`
`Determine
`combined cost
`of each
`repeater
`
`Select Best Repeater
`
`a
`
`
`
`E3
`Select stall
`set of
`repeaters
`
`
`
`
`
`E4
`Select
`element from
`Set
`
`
`
`E2a
`Determine
`loads on
`repeater
`
`Determine link
`cost between
`repeater &
`client's group
`
`Determine
`combined
`cost
`
`HPE, Exh. 1009, p. 1
`
`

`

`US 6,185,598 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5,539,621
`5,544,313
`5,544,327
`5,550,577
`5,550,863
`5,550,982
`5,557,317
`5,572,643
`5,590,288
`5,592,611
`5,594,910
`5,603,026
`5,619,648
`5,623,656
`5,625,781
`5,627,829
`5,630,067
`5,633,999
`5,634,006
`5,644,714
`
`7/1996 Kikinis ................................. 361/803
`8/1996 Shachnai.
`... 709/219
`8/1996 Dan .........
`... 709/234
`8/1996 Verbiest .
`... 348/7
`8/1996 Yurt ......
`... 375/240
`8/1996 Long ...
`... 709/219
`9/1996 Nishio ...
`... 348/7
`11/1996 Judson .
`... 709/218
`12/1996 Castor .....
`... 709/201
`1/1997 Midgely ...
`... 714.f4
`1/1997 Filepp et al.
`712/28
`2/1997 Demers et al. .......................... 707/8
`4/1997 Canale .......
`... 709/206
`4/1997 Lyons ...
`... 707/10
`4/1997 Cline ...........
`... 345/335
`5/1997 Gleeson et al.
`... 370/230
`5/1997 Kindell ........
`... 709/231
`5/1997 Clowes ..................................... 714/6
`5/1997 Baugher et al.
`... 709/228
`7/1997 Kikinis ................................. 709/219
`
`7/1997 Ferguson ................................ 707/10
`5,649,186
`8/1997 Nielsen .................................... 707/3
`5,659,729
`9/1997 Chen .................................... 370/420
`5,666,362
`9/1997 Elgamai
`... 705/79
`5,671,279
`10/1997 Tetrick ...
`711/202
`5,682,512
`12/1997 Feigen et al.
`713/201
`5,699,513
`2/1998 Stewart ....
`707/104
`5,715,453
`2/1998 DeVries ...
`707/104
`5,721,914
`3/1998 Sanders .
`709/223
`5,734,831
`4/1998 Scholl ......
`709/200
`5,742,762
`5,761,663 * 6/1998 Largarde et al.
`709/203
`5,774,660 * 6/1998 Brendel et al. .
`... 709/239
`5,774,668
`6/1998 Choquier et al.
`709/223
`5,796,952
`8/1998 Davis .......
`709/224
`5,799,141
`8/1998 Galipeau et al.
`... 714/13
`5,828,847
`10/1998 Gehr .........
`709/239
`5,870,546 * 2/1999 Kirsch ...
`709/238
`5,956,716
`9/1999 Kenner .....
`... 707/10
`5.991,809
`11/1999 Kriegsman.
`709/226
`6,065,062 * 5/2000 Periasamy et al. .................. 709/242
`* cited by examiner
`
`
`
`HPE, Exh. 1009, p. 2
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 1 of 6
`
`US 6,185,598 B1
`
`Nilo
`
`JO}I9|j9y
` YSAYAS
`
`LN&IT9
`
`cOl
`
` gOL90l
`
`wrol
`
`19}SeW
`
`Jajeaday
`
`
`
`@YALVsdsadeyoes
`
`VdalvadaHy
`
`arol
`
`Erol
`
`Jajyeaday
`
`Obl
`
`270}
`
`°¥saLVadsay
`
`HPE, Exh. 1009, p. 3
`
`HPE, Exh. 1009, p. 3
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`JUSIID
`
`Feb. 6, 2001
`
`
`
`Aidayaalsooy
`
`
`
`ysanbey149
`
`dLLHPuss
`
`ysiqe}sg
`
`J9AI9SUM
`uolsauu0D
`
`ssaippeqd]dny0072THNWoyswueu
`THNSAl9994
`
`JBAIBSJO
`
`ysanbay
`
`gv90F
`
`vv
`
`Cv
`
`
`
`JBAIOSJOBI}XA
`
`ov
`
`LV
`
`Sheet 2 of 6
`
`LvovGV
`
`
`
`Ajdeypues410938907]:SulBUO
`
`aonoseyaa1nNoseaYyjsenboySOL40JV9/Jay10
`yyasoduiog@AleoouZOL4ansa
`
`
`
`
`
`
`US 6,185,598 B1
`
`Z‘bi-s
`
`POL4ajeaday10
`
`HPE, Exh. 1009, p. 4
`
`HPE, Exh. 1009, p. 4
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 3 of 6
`
`US 6,185,598 B1
`
` aounoseyysenbey
`
`
`Aideypues408)8907]
`uaasodwogenjeney
`
`avovsv
`
`aonosey
`
`
`
`ZO}40AL9$
`
`ujBuoO
`
`HPE, Exh. 1009, p. 5
`
`
`
`6o7]aepdh
`
`
`
`0)Ajdaypuas
`
`yayD
`
`
`
`AidoyUleIq0
`
`12907a242907]
`
`JoOeYeY
`
`$)dedsazU]
`
`ysanbey
`
`
`
`80}40}90/94
`
`yoeyed
`
`ysanbay
`
`9
`
`TNMauyu
`
`Hy93492g09
`
`S3A
`
`
`
`Aidayeapaoay
`
`ev
`
`diLHpues
`
`ysenbew149
`
`90}IUELD
`
`HPE, Exh. 1009, p. 5
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 4 of 6
`
`US 6,185,598 B1
`
`puÐS
`
`9-98
`
`10.ERICIER,
`
`Z-98
`
`80
`
`
`
`
`
`
`
`
`
`
`
`
`
`Quell'O
`
`90].
`
`HPE, Exh. 1009, p. 6
`
`

`

`U.S. Patent
`
`US 6,185,598 B1
`
`G -61-I
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`| O
`
`ezÁIeuw
`
`?senbau
`
`
`
`LES) pueS
`
`Qua!!0
`
`90].
`
`HPE, Exh. 1009, p. 7
`
`

`

`U.S. Patent
`
`Feb. 6, 2001
`
`Sheet 6 of 6
`
`US 6,185,598 B1
`
`aUujWajagaujwie}ag
`
`
`
`
`
`Yul]SUILE}aQg
`
`oa|9geusjoe|egJSO9@UILWI9}9q|SUIWII}IGpaujquios
`
`
`va£3ba
`
`
`
`
`WoolJUBWUB]ajojas
`yessiajeadal
`
`yoraJodnoibs,juayo
`
`Jajeedal
`
`ca
`
`80}40}99/94
`
`qc3
`
`
`
`
`
`dajeadayjSagjIa/aS
`
`
`
`ugaMmjeq}SO9
`
`pauiquiosuOSpeOo}
`}so09Jajeedal9Jajeedal
`
`
`
`
`dnoibs,juayo
`
`9‘biz
`
`HPE, Exh. 1009, p. 8
`
`HPE, Exh. 1009, p. 8
`
`
`
`
`
`
`

`

`US 6,185,598 B1
`
`1
`OPTIMIZED NETWORK RESOURCE
`LOCATION
`
`FIELD OF THE INVENTION
`This invention relates to replication of resources in com
`puter networks.
`
`2
`balanced among those Servers. Domain name-Server-based
`round-robin address resolution causes different clients to be
`directed to different mirrors.
`Another Solution, load balancing, takes into account the
`load at each server (measured in a variety of ways) to Select
`which Server should handle a particular request.
`Load balancers use a variety of techniques to route the
`request to the appropriate Server. Most of those load
`balancing techniques require that each Server be an exact
`replica of the primary Web site. Load balancers do not take
`into account the “network distance” between the client and
`candidate mirror Servers.
`ASSuming that client protocols cannot easily change, there
`are two major problems in the deployment of replicated
`resources. The first is how to select which copy of the
`resource to use. That is, when a request for a resource is
`made to a single Server, how should the choice of a replica
`of the server (or of that data) be made. We call this problem
`the “rendezvous problem'. There are a number of ways to
`get clients to rendezvous at distant mirror Servers. These
`technologies, like load balancers, must route a request to an
`appropriate Server, but unlike load balancers, they take
`network performance and topology into account in making
`the determination.
`A number of companies offer products which improve
`network performance by prioritizing and filtering network
`traffic. Proxy caches provide a way for client aggregators to
`reduce network resource consumption by Storing copies of
`popular resources close to the end users. A client aggregator
`is an Internet Service provider or other organization that
`brings a large number of clients operating browsers to the
`Internet. Client aggregators may use proxy caches to reduce
`the bandwidth required to serve web content to these brows
`erS. However, traditional proxy caches are operated on
`behalf of Web clients rather than Web publishers.
`Proxy caches Store the most popular resources from all
`publishers, which means they must be very large to achieve
`reasonable cache efficiency. (The efficiency of a cache is
`defined as the number of requests for resources which are
`already cached divided by the total number of requests.)
`Proxy caches depend on cache control hints delivered
`with resources to determine when the resources should be
`replaced. These hints are predictive, and are necessarily
`often incorrect, So proxy caches frequently Serve Stale data.
`In many cases, proxy cache operators instruct their proxy to
`ignore hints in order to make the cache more efficient, even
`though this causes it to more frequently Serve Stale data.
`Proxy caches hide the activity of clients from publishers.
`Once a resource is cached, the publisher has no way of
`knowing how often it was accessed from the cache.
`SUMMARY OF THE INVENTION
`This invention provides a way for Servers in a computer
`network to off-load their processing of requests for Selected
`resources by determining a different Server (a "repeater) to
`process those requests. The Selection of the repeater can be
`made dynamically, based on information about possible
`repeaterS.
`If a requested resource contains references to other
`resources, Some or all of these references can be replaced by
`references to repeaters.
`Accordingly, in one aspect, this invention is a method of
`processing resource requests in a computer network. First a
`client makes a request for a particular resource from an
`origin Server, the request including a resource identifier for
`
`25
`
`35
`
`40
`
`BACKGROUND OF THE INVENTION
`The advent of global computer networks, Such as the
`Internet, have led to entirely new and different ways to
`obtain information. A user of the Internet can now acceSS
`information from anywhere in the world, with no regard for
`the actual location of either the user or the information. A
`user can obtain information Simply by knowing a network
`15
`address for the information and providing that address to an
`appropriate application program Such as a network browser.
`The rapid growth in popularity of the Internet has
`imposed a heavy traffic burden on the entire network.
`Solutions to problems of demand (e.g., better accessibility
`and faster communication links) only increase the Strain on
`the supply. Internet Web sites (referred to here as
`"publishers') must handle ever-increasing bandwidth needs,
`accommodate dynamic changes in load, and improve per
`formance for distant browsing clients, especially those over
`Seas. The adoption of content-rich applications, Such as live
`audio and Video, has further exacerbated the problem.
`To address basic bandwidth growth needs, a Web pub
`lisher typically subscribes to additional bandwidth from an
`Internet service provider (ISP), whether in the form of larger
`or additional “pipes” or channels from the ISP to the
`publisher's premises, or in the form of large bandwidth
`commitments in an ISP's remote hosting server collection.
`These increments are not always as fine-grained as the
`publisher needs, and quite often lead times can cause the
`publisher's Web site capacity to lag behind demand.
`To address more serious bandwidth growth problems,
`publishers may develop more complex and costly custom
`Solutions. The Solution to the most common need, increasing
`capacity, is generally based on replication of hardware
`resources and Site content (known as mirroring), and dupli
`cation of bandwidth resources. These Solutions, however,
`are difficult and expensive to deploy and operate. As a result,
`only the largest publishers can afford them, Since only those
`publishers can amortize the costs over many customers (and
`Web site hits).
`A number of Solutions have been developed to advance
`replication and mirroring. In general, these technologies are
`designed for use by a single Web Site and do not include
`features that allow their components to be shared by many
`Web sites simultaneously.
`Some Solution mechanisms offer replication Software that
`helps keep mirrored Servers up-to-date. These mechanisms
`generally operate by making a complete copy of a file
`System. One Such System operates by transparently keeping
`multiple copies of a file System in Synch. Another System
`provides mechanisms for explicitly and regularly copying
`files that have changed. Database Systems are particularly
`difficult to replicate, as they are continually changing. Sev
`eral mechanisms allow for replication of databases, although
`there are no Standard approaches for accomplishing it.
`Several companies offering proxy caches describe them as
`replication tools. However, proxy caches differ because they
`are operated on behalf of clients rather than publishers.
`Once a Web site is served by multiple servers, a challenge
`is to ensure that the load is appropriately distributed or
`
`65
`
`45
`
`50
`
`55
`
`60
`
`HPE, Exh. 1009, p. 9
`
`

`

`US 6,185,598 B1
`
`3
`the particular resource, the resource identifier Sometimes
`including an indication of the origin Server. Requests arriv
`ing at the origin Server do not always include an indication
`of the origin Server, Since they are Sent to the origin Server,
`they do not need to name it. A mechanism referred to as a
`reflector, co-located with the origin Server, intercepts the
`request from the client to the origin Server and decides
`whether to reflect the request or to handle it locally. If the
`reflector decides to handle the request locally, it forwards it
`to the origin Server, otherwise it Selects a “best” repeater to
`process the request. If the request is reflected, the client is
`provided with a modified resource identifier designating the
`repeater.
`The client gets the modified resource identifier from the
`reflector and makes a request for the particular resource
`from the repeater designated in the modified resource iden
`tifier.
`When the repeater gets the client's request, it responds by
`returning the requested resource to the client. If the repeater
`has a local copy of the resource then it returns that copy,
`otherwise it forwards the request to the origin Server to get
`the resource, and Saves a local copy of the resource in order
`to Serve Subsequent requests.
`The Selection by the reflector of an appropriate repeater to
`handle the request can be done in a number of ways. In the
`preferred embodiment, it is done by first pre-partitioning the
`network into “cost groups' and then determining which cost
`group the client is in. Next, from a plurality of repeaters in
`the network, a Set of repeaterS is Selected, the members of
`the Set having a low cost relative to the cost group which the
`client is in. In order to determine the lowest cost, a table is
`maintained and regularly updated to define the cost between
`each group and each repeater. Then one member of the set
`is Selected, preferably randomly, as the best repeater.
`If the particular requested resource itself can contain
`identifiers of other resources, then the resource may be
`rewritten (before being provided to the client). In particular,
`the resource is rewritten to replace at least Some of the
`resource identifiers contained therein with modified resource
`identifiers designating a repeater instead of the origin Server.
`AS a consequence of this rewriting process, when the client
`requests other resources based on identifiers in the particular
`requested resource, the client will make those requests
`directly to the Selected repeater, bypassing the reflector and
`origin Server entirely.
`Resource rewriting must be performed by reflectors. It
`may also be performed by repeaters, in the situation where
`repeaters "peer with one another and make copies of
`resources which include rewritten resource identifiers that
`designate a repeater.
`In a preferred embodiment, the network is the Internet and
`the resource identifier is a uniform resource locator (URL)
`for designating resources on the Internet, and the modified
`resource identifier is a URL designating the repeater and
`indicating the origin server (as described in Step B3 below),
`and the modified resource identifier is provided to the client
`using a REDIRECT message. Note, only when the reflector
`is “reflecting a request is the modified resource identifier
`provided using a REDIRECT message.
`In another aspect, this invention is a computer network
`comprising a plurality of origin Servers, at least Some of the
`origin Servers having reflectors associated there with, and a
`plurality of repeaters.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The above and other objects and advantages of the
`invention will be apparent upon consideration of the fol
`
`4
`lowing detailed description, taken in conjunction with the
`accompanying drawings, in which the reference characters
`refer to like parts throughout and in which:
`FIG. 1 depicts a portion of a network environment accord
`ing to the present invention; and
`FIGS. 2-6 are flow charts of the operation of the present
`invention.
`
`DETAILED DESCRIPTION OF THE
`PRESENTLY PREFERRED EXEMPLARY
`EMBODIMENTS
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Overview
`FIG. 1 shows a portion of a network environment 100
`according to the present invention, wherein a mechanism
`(reflector 108, described in detail below) at a server (herein
`origin server 102) maintains and keeps track of a number of
`partially replicated servers or repeaters 104a, 104b, and
`104c. Each repeater 104a, 104b, and 104c replicates some or
`all of the information available on the origin server 102 as
`well as information available on other origin Servers in the
`network 100. Reflector 108 is connected to a particular
`repeater known as its “contact” repeater (“Repeater B' 104b
`in the system depicted in FIG. 1). Preferably each reflector
`maintains a connection with a single repeater known as its
`contact, and each repeater maintains a connection with a
`Special repeater known as its master repeater (e.g., repeater
`104m for repeaters 104a, 104b and 104c in FIG. 1).
`Thus, a repeater can be considered as a dedicated proxy
`Server that maintains a partial or sparse mirror of the origin
`server 102, by implementing a distributed coherent cache of
`the origin server. A repeater may maintain a (partial) mirror
`of more than one origin server. In some embodiments, the
`network 100 is the Internet and repeaters mirror selected
`resources provided by origin Servers in response to clients
`HTTP hypertext transfer protocol) and FTP (file transfer
`protocol) requests.
`A client 106 connects, via the network 100, to origin
`server 102 and possibly to one or more repeaters 104a etc.
`Origin Server 102 is a Server at which resources originate.
`More generally, the origin Server 102 is any proceSS or
`collection of processes that provide resources in response to
`requests from a client 106. Origin server 102 can be any
`off-the-shelf Web server. In a preferred embodiment, origin
`server 102 is typically a Web server Such as the Apache
`Server or Netscape Communications Corporation's Enter
`prise TM server.
`Client 106 is a processor requesting resources from origin
`server 102 on behalf of an end user. The client 106 is
`typically a user agent (e.g., a Web browser Such as Netscape
`Communications Corporation's NavigatorTM) or a proxy for
`a user agent. Components other than the reflector 108 and
`the repeaters 104a, 104b, etc., may be implemented using
`commonly available Software programs. In particular, this
`invention works with any HTTP client (e.g., a Web browser),
`proxy cache, and Web server. In addition, the reflector 108
`might be fully integrated into the data server 112 (for
`instance, in a Web Server). These components might be
`loosely integrated based on the use of extension mechanisms
`(Such as So-called add-in modules) or tightly integrated by
`modifying the Service component Specifically to Support the
`repeaterS.
`ReSources originating at the origin Server 102 may be
`Static or dynamic. That is, the resources may be fixed or they
`may be created by the origin server 102 specifically in
`response to a request. Note that the terms "static' and
`
`HPE, Exh. 1009, p. 10
`
`

`

`S
`“dynamic' are relative, Since a Static resource may change
`at Some regular, albeit long, interval.
`Resource requests from the client 106 to the origin server
`102 are intercepted by reflector 108 which for a given
`request either forwards the request on to the origin Server
`102 or conditionally reflects it to some repeater 104a, 104b,
`etc. in the network 100. That is, depending on the nature of
`the request by the client 106 to the origin server 102, the
`reflector 108 either serves the request locally (at the origin
`server 102), or selects one of the repeaters (preferably the
`best repeater for the job) and reflects the request to the
`selected repeater. In other words, the reflector 108 causes
`requests for resources from origin Server 102, made by client
`106, to be either served locally by the origin server 102 or
`transparently reflected to the best repeater 104a, 104b, etc.
`The notion of a best repeater and the manner in which the
`best repeater is Selected are described in detail below.
`Repeaters 104a, 104b, etc. are intermediate processors
`used to Service client requests thereby improving perfor
`mance and reducing costs in the manner described herein.
`Within repeaters 104a, 104b, etc., are any processes or
`collections of processes that deliver resources to the client
`106 on behalf of the origin server 102. A repeater may
`include a repeater cache 110, used to avoid unnecessary
`transactions with the origin server 102.
`The reflector 108 is a mechanism, preferably a software
`program, that intercepts requests that would normally be
`sent directly to the origin server 102. While shown in the
`drawings as Separate components, the reflector 108 and the
`origin Server 102 are typically co-located, e.g., on a particu
`lar System Such as data server 112. (AS discussed below, the
`reflector 108 may even be a “plug in module that becomes
`part of the origin server 102.
`FIG. 1 shows only a part of a network 100 according to
`this invention. A complete operating network consists of any
`number of clients, repeaters, reflectors, and origin Servers.
`Reflectors communicate with the repeater network, and
`repeaters in the network communicate with one another.
`Uniform Resource Locators
`Each location in a computer network has an address
`which can generally be specified as a Series of names or
`numbers. In order to acceSS information, an address for that
`information must be known. For example, on the World
`Wide Web (“the Web’) which is a subset of the Internet, the
`manner in which information address locations are provided
`has been Standardized into Uniform Resource Locators
`(URLs). URLs specify the location of resources
`(information, data files, etc.) on the network.
`The notion of URLs becomes even more useful when
`hypertext documents are used. A hypertext document is one
`which includes, within the document itself, links (pointers or
`references) to the document itself or to other documents. For
`example, in an on-line legal research System, each case may
`be presented as a hypertext document. When other cases are
`cited, links to those cases can be provided. In this way, when
`a perSon is reading a case, they can follow cite links to read
`the appropriate parts of cited cases.
`In the case of the Internet in general and the World Wide
`Web Specifically, documents can be created using a stan
`dardized form known as the Hypertext Markup Language
`(HTML). In HTML, a document consists of data (text,
`images, Sounds, and the like), including links to other
`Sections of the same document or to other documents. The
`links are generally provided as URLS, and can be in relative
`or absolute form. Relative URLs simply omit the parts of the
`URL which are the same as for the document including the
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`US 6,185,598 B1
`
`6
`link, Such as the address of the document (when linking to
`the same document), etc. In general, a browser program will
`fill in missing parts of a URL using the corresponding parts
`from the current document, thereby forming a fully formed
`URL including a fully qualified domain name, etc.
`A hypertext document may contain any number of links to
`other documents, and each of those other documents may be
`on a different server in a different part of the world. For
`example, a document may contain links to documents in
`Russia, Africa, China and Australia. A user Viewing that
`document at a particular client can follow any of the links
`transparently (i.e., without knowing where the document
`being linked to actually resides). Accordingly, the cost (in
`terms of time or money or resource allocation) of following
`one link versus another may be quite Significant.
`URLs generally have the following form (defined in detail
`in T. Berners-Lee et al., Uniform Resource Locators (URL),
`Network Working Group, Request for Comments: 1738,
`Category: Standards Track, December 1994, located at
`“http://ds.internic.net/rfc/rfc1738.txt”, which is hereby
`incorporated herein by reference):
`scheme://hostport/url-path
`where “scheme” can be a symbol such as “file” (for a file on
`the local system), “ftp” (for a file on an anonymous FTP file
`server), “http” (for a file on a file on a Web server), and
`“telnet” (for a connection to a Telnet-based service). Other
`Schemes, can also be used and new Schemes are added every
`now and then. The port number is optional, the System
`Substituting a default port number (depending on the
`scheme) if none is provided. The “host” field maps to a
`particular network address for a particular computer. The
`“url-path’ is relative to the computer specified in the "host”
`field. A url-path is typically, but not necessarily, the path
`name of a file in a Web Server directory.
`For example, the following is a URL identifying a file “F”
`in the path “A/B/C” on a computer at “www.uspto.gov”:
`http://www.uspto.gov/A/B/C/F
`In order to access the file “F” (the resource) specified by
`the above URL, a program (e.g., a browser) running on a
`user's computer (i.e., a client computer) would have to first
`locate the computer (i.e., a server computer) specified by the
`host name. I.e., the program would have to locate the Server
`“www.uspto.gov. To do this, it would access a Domain
`Name Server (DNS), providing the DNS with the host name
`(“www.uspto.gov). The DNS acts as a kind of centralized
`directory for resolving addresses from names. If the DNS
`determines that there is a (remote server) computer corre
`sponding to the name "www.upSto.gov, it will provide the
`program with an actual computer network address for that
`Server computer. On the Internet this is called an Internet
`Protocol (or IP) address and it has the form
`“123.345.456.678”. The program on the user's (client) com
`puter would then use the actual address to access the remote
`(server) computer.
`The program opens a connection to the HTTP server (Web
`Server) on the remote computer "www.uspto.gov and uses
`the connection to Send a request message to the remote
`computer (using the HTTP Scheme). The message is typi
`cally an HTTP GET request which includes the url-path of
`the requested resource, “A/B/C/F". The HTTP server
`receives the request and uses it to access the resource
`specified by the url-path “A/B/C/F. The server returns the
`resource over the same connection.
`Thus, conventionally HTTP client requests for Web
`resources at an origin Server 102 are processed as follows
`
`HPE, Exh. 1009, p. 11
`
`

`

`7
`(see FIG. 2) (This is a description of the process when no
`reflector 108 is installed.):
`A1. A browser (e.g., Netscape's Navigator) at the client
`receives a resource identifier (i.e., a URL) from a user.
`A2. The browser extracts the host (origin server) name
`from the resource identifier, and uses a domain name
`server (DNS) to look up the network (IP) address of the
`corresponding Server. The browser also extracts a port
`number, if one is present, or uses a default port number
`(the default port number for http requests is 80).
`A3. The browser uses the server's network address and
`port number to establish a connection between the
`client 106 and the host or origin server 102.
`A4. The client 106 then sends a (GET) request over the
`connection identifying the requested resource.
`A5. The origin server 102 receives the request and
`A6. locates or composes the corresponding resource.
`A7. The origin server 102 then sends back to the client
`106 a reply containing the requested resource (or Some
`form of error indicator if the resource is unavailable).
`The reply is sent to the client over the same connection
`as that on which the request was received from the
`client.
`A8. The client 106 receives the reply from the origin
`server 102.
`There are many variations of this basic model. For
`example, in one variation, instead of providing the client
`with the resource, the origin Server can tell the client to
`re-request the resource by another name. To do So, in A7 the
`server 102 sends back to the client 106 a reply called a
`“REDIRECT" which contains a new URL indicating the
`other name. The client 106 then repeats the entire sequence,
`normally without any user intervention, this time requesting
`the resource identified by the new URL.
`System Operation
`In this invention reflector 108 effectively takes the place
`of an ordinary Web server or origin server 102. The reflector
`108 does this by taking over the origin server's IP address
`and port number. In this way, when a client tries to connect
`to the origin server 102, it will actually connect to the
`reflector 108. The original Web server (or origin server 102)
`must then accept requests at a different network (IP) address,
`or at the same IP address but on a different port number.
`Thus, using this invention, the server referred to in A3-A7
`above is actually a reflector 108.
`Note that it is also possible to leave the origin server's
`network address as it is and to let the reflector run at a
`different address or on a different port. In this way the
`reflector does not intercept requests Sent to the origin Server,
`but can Still be sent requests addressed specifically to the
`reflector. Thus the System can be tested and configured
`without interrupting its normal operation. The reflector 108
`Supports the processing as follows (see FIG. 3): upon receipt
`of a request,
`B1. The re