`Exhibit  1006  
`  
`
`Exhibit 1006
`
`

`

`(12) United States Patent
`Smith et al.
`
`US006341311B1
`US 6,341,311 B1
`(10) Patent N0.:
`Jan. 22, 2002
`(45) Date of Patent:
`
`(54)
`
`(75)
`
`(73)
`
`(*)
`
`(21)
`(22)
`(51)
`(52)
`(58)
`
`(56)
`
`DIRECTING DATA OBJECT ACCESS
`REQUESTS IN A DISTRIBUTED CACHE
`Inventors: Brian J. Smith, Seattle; Vinod V.
`Valloppillil, Redmond, both of WA
`(US); Hans Hurvig, Copenhagen (DK)
`Assignee: Microsoft Corporation, Redmond, WA
`(Us)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`Appl. No.: 09/087,330
`Filed:
`May 29, 1998
`
`Notice:
`
`Int. Cl.7 .............................................. .. G06F 13/00
`US. Cl. ..................................................... .. 709/226
`Field of Search ............................... .. 709/201, 203,
`709/217, 218, 219, 223, 224, 225, 226,
`227
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,341,499 A
`8/1994 Doragh ..................... .. 709/321
`5,539,883 A
`7/1996 Allon et a1.
`709/105
`5,603,029 A
`2/1997 Aman et a1.
`709/105
`
`. . . . . .. 364/184
`3/1997 Dasgupta . . . . . .
`5,612,865 A
`.. 395/182.04
`4/1997 Bailey ........ ..
`5,623,585 A
`7/1997 Hanko et a1. ........ .. 395/182.04
`5,649,093 A
`5,740,371 A * 4/1998 Wallis ...................... .. 709/229
`5,774,660 A * 6/1998 Brendel et a1.
`709/201
`5,787,470 A
`7/1998 DiSimone et a1.
`711/124
`5,805,824 A * 9/1998 Kappe ............... ..
`709/242
`5,826,270 A * 10/1998 Rutkowski et a1. ..
`707/10
`5,864,852 A
`1/1999 Luotonen ................... .. 707/10
`8,918,013
`6/1999 Mighdoll et a1. .... .. 395/200.47
`5,924,116 A
`7/1999 Aggarwal et a1. ........ .. 711/122
`5,933,606 A
`8/1999 MayheW ......... ..
`.. 395/20069
`5,933,849 A
`8/1999 Srbljic et a1. . . . . .
`. . . . .. 711/118
`5,935,207 A
`8/1999 Logue et a1. ..
`..... .. 709/219
`5,940,594 A
`8/1999 Ali et a1. ............. .. 395/200.33
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`Valloppillil, Vinod and Ross, Keith W. Cache Array Routing
`Protocol v1.0. World Wide Web. pp. 1—9.
`Microsoft Corporation. Cache Array Routing Protocol and
`Microsoft Proxy Server 2.0. World Wide Web: WWW.mi
`crosoft.com. pp. 1—15.
`Valloppillil, Vinod and Cohen, Josh. Hierarchal HTTP Rout
`ing Protocol. World Wide Web. pp. 1—7.
`HoW to Make Distributed Proxy Server by URL Hasing,
`(last modi?ed Apr. 1999, http://naragW.sharp.co.jp/sps/.
`Brie?ng on Super Proxy Script, (last modi?ed Aug. 1998),
`http/naragW.sharp.co.jp/sps/sps—e.html.
`Primary Examiner—Moustafa M. Meky
`(74) Attorney, Agent, or Firm—Workman, Nydegger &
`Seeley
`ABSTRACT
`(57)
`A method, computer program product, and system for rout
`ing URL data object requests in a proxy server array. A URL
`data object request is received at one proxy server of the
`array While the desired URL data object resides in the local
`cache of another proxy server in the array. The receiving
`proxy server Will deterministically identify the residing
`proxy server based on information residing thereon Without
`resorting to expensive query-response transactions, such as
`those that occur in proxy server arrays using ICP. An array
`membership list containing array membership information is
`available at each and every proxy server and is used in
`conjunction With the URL as the information for identifying
`the correct proxy server Where the URL data object resides.
`First, a deterministic hash value is computed for each proxy
`server name and the URL. Next, a combined hash value is
`computed that combines the URL hash value With each
`proxy server hash value. Finally, the proxy server With the
`highest “score” or combined hash value is identi?ed as the
`proxy server Where the desired URL data object should
`reside in local cache storage. Since the array membership
`list, the URL, and the hashing algorithm are the same at each
`proxy server, the same proxy server Will be identi?ed as
`having the URL data object regardless of Which proxy server
`originally receives the URL data object request.
`24 Claims, 11 Drawing Sheets
`
`(so
`WENT
`
`:
`i
`a4
`HTTP I‘ PS2
`REQUEST;
`
`LATERAL ACCESS
`PROXY SERVER ARRAY
`(DISTRIBUTED CACHE)
`(e0
`ifaz
`‘:
`(as
`i
`,2
`’
`5
`GET
`EOBJECT
`. (Mi
`'
`I
`'
`I
`El 5
`
`PSN
`
`l
`1
`a
`
`94
`
`OBJECT
`COPY
`4
`
`TOTAL MESSAGES = 2
`
`Petitioner Ex. 1006 Page 1
`
`

`

`US 6,341,311 B1
`Page 2
`
`US. PATENT DOCUMENTS
`
`5,987,233 A 11/1999 Humphrey ----------- -- 395/20047
`5,991,804 A 11/1999 Bolosky et a1.
`709/221
`5,991,809 A 11/1999 Kriegsman ----- --
`709/226
`6,006,251 A * 12/1999 Toyouchi er a1-
`709/203
`6,006,264 A 12/1999 Colby et a1. ..
`.. 709/226
`6,014,667 A
`1/2000 Jenkins et a1. .............. .. 707/10
`
`6,026,405 A * 2/2000 Arda et a1. ................. .. 707/10
`6,029,168 A
`2/2000 Frey .......................... .. 707/10
`6,029,195 A * 2/2000 HerZ ........................ .. 725/116
`6,052,718 A * 4/2000 Gifford
`' 709/219
`6,112,228 A * 8/2000 Earl et a1.
`709/205
`6,122,666 A * 9/2000 Beurket et a1. ........... .. 709/226
`
`* cited by examiner
`
`Petitioner Ex. 1006 Page 2
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 1 0f 11
`
`US 6,341,311 B1
`
`21
`,1
`(2o
`I ——\ SPERRQIXEYR
`CLIENT —" (CACHE)
`
`22
`
`FIG. 1
`
`PROXY SERVER ARRAY
`(DISTRIBUTED CACHE)
`
`PROXY
`SERVER
`
`2 g 3
`CLIENT
`
`Petitioner Ex. 1006 Page 3
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 2 0f 11
`
`US 6,341,311 B1
`
`52.3
`
`Q23
`
`3
`
`52.3
`:5 8%
`
`2: 53a :2;
`
`5
`
`w j i: f:
`2:2 " $22; is
`
`m .0:
`
`Petitioner Ex. 1006 Page 4
`
`

`

`US. Patent
`
`Jan. 22, 2002
`
`Sheet 3 0f 11
`
`US 6,341,311 B1
`
`3
`
`Sofia
`
`ON:2:
`
`Esmsoo
`
`s:we;
`
`:22;
`
`2530:
`
`583.52<32.53_.235.2250:32522:V3522:
`._|vo:_g2252:
`“9:3:__$223
`3:320:32:aa38:
`_a$522
`_I_Fm”“4200:"gaE8:Es
`__g20:52:W299%
`_3E23:553
`mxoxdfiwq52ma::2was
`228E/
`32:2.32:;E2.355::
`
`fl__
`
`ozawmooi
`
`a$38:
`
`mwm=<x¢oxm
`
`s<mw0mmmeHo
`zoz<osmm<
`
`mm=wpw>w
`
`ez:<xm¢o
`
`2%:
`
`Petitioner Ex. 1006 Page 5
`
`Petitioner Ex. 1006 Page 5
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 4 0f 11
`
`US 6,341,311 B1
`
`(a0
`’
`
`s4
`HTTP L
`
`SEND 94
`01mm>
`COPY
`
`LATERAL ACCESS
`PROXY SERVER ARRAY
`(DISTRIBUTED CACHE)
`PS1
`)(go
`V82
`(as
`W92
`J
`L
`GET
`
`L
`5
`i , PS2
`
`. 484i
`I
`i
`5
`AMLI
`5
`
`PSN
`
`g
`i
`5
`
`TOTAL MESSAGES = 2
`
`FIG. 5
`
`Petitioner Ex. 1006 Page 6
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 5 0f 11
`
`US 6,341,311 B1
`
`DETERMINISTICALLY
`DERIVE MOST LIKELY
`ARRAY MEMBER BASED r120
`0N URL AND ARRAY
`MEMBERSHIP LIST
`
`FORWARD REQUEST fm
`T0 ARRAY MEMBER
`
`v gwe
`RETURN
`
`CACHE
`
`\
`
`(DO NOT
`CACHE URLY
`
`UPDATE ARRAY
`MEMBERSHIP LIST
`TXMWMEFR'BLEAD
`+
`130
`DETERMINE NEXT
`MOST LIKELY f
`ARRAY MEMBER
`
`
`
`v AccEss URL f 114
`
`OVER 'NTERNET
`*
`PLACE URL INTO
`LOCAL CACHE f 116
`+
`RETURN
`URL
`
`_r118
`
`108
`
`FIG. 6
`
`Petitioner Ex. 1006 Page 7
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 6 0f 11
`
`US 6,341,311 B1
`
`ESDIU RVl-DIH
`IVA
`
`ATMEU
`CED AVE
`
`RT
`
`“RC
`
`EAA C CR
`MB,
`RH
`
`R DlmmP
`
`AML
`
`TOTAL MESSAGES = 0
`
`FIG. 7
`
`Petitioner Ex. 1006 Page 8
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 7 0f 11
`
`US 6,341,311 B1
`
`DETERMINISTICALLY
`152
`DERIVE MOST LIKELY
`ARRAY MEMBER BASED —/_
`0N DESIRED URL AND
`ARRAY MEMBERSHIP LIST
`
`REQUEST URL
`FROM ARRAY MEMBER
`
`f1s4
`
`156
`
`N @ “8
`UPDATE ARRAY
`MEMBERSHIP LIST
`_/~160
`TO REMOVE FAILED
`ARRAY MEMBER
`
`i
`
`DETERMINE NEXT
`MOST LIKELY
`ARRAY MEMBER
`
`_/“162
`
`FIG. 8
`
`Petitioner Ex. 1006 Page 9
`
`

`

`U.S. Patent
`US. Patent
`
`Jan. 22, 2002
`
`Jan. 22, 2002
`
`Sheet 8 0f 11
`
`Sheet 8 0f 11
`
`US 6,341,311 B1
`US 6,341,311 B1
`
`N:
`
`a:
`
`11 :2
`N2
`m2
`
`PT 5
`m2 N2
`
`
`3
`F
`
`v
`2
`
`2
`F
`
`:2
`N2
`m2
`
`m2
`
`F
`we
`
`v
`2
`
`S
`F
`
`F
`3
`
`v
`3
`
`F2
`
`8.;
`
`g.o:
`
`2 .6:
`g.0:
`
`8 .6:
`3.0:
`
`3.o:
`
`Petitioner Ex. 1006 Page 10
`
`Petitioner Ex. 1006 Page 10
`
`
`
`
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 9 0f 11
`
`US 6,341,311 B1
`
`180
`
`194
`
`ADD NEW PS TO
`196
`THE PROXY SERVER
`ARRAY
`-f
`
`GIVE NEW PS ACCESS
`TO AN EXISTING
`/-198
`ARRAY MEMBER
`'
`
`W PS REQUESTS
`AML ERoM EXISTING x200
`ARRAY MEMBER
`
`W PS owns 202
`AML f
`
`I
`I
`I
`I
`I
`
`TTI. TIMER
`
`EXPIRES I
`I
`I
`
`184
`RANDOMLY SELECT
`AN ARRAY MEMBER J‘
`FROM THE AMI.
`
`REQUEST THE AML
`FROM THE SELECTED _/—1B6
`ARRAY MEMBER
`
`UPDATE AML
`188
`WITH INFORMATION
`mm THE f
`REQUESTED AML
`
`I
`
`ma TTL
`TIMER f 190
`
`NEW PS NOTIFIES
`ALL OTHER EXISTING PSs
`
`OTHER PSs UPDATE
`RESPECTIVE AMLs
`TO INCLUDE NEW PS
`
`fzos
`_
`
`f2o4
`
`FIG. 10
`
`206
`
`FIG. 11
`
`Petitioner Ex. 1006 Page 11
`
`

`

`U.S. Patent
`
`Jan. 22, 2002
`
`Sheet 10 0f 11
`
`US 6,341,311 B1
`
`REMOVE PS
`r210
`FROM PROXY —
`SERVER ARRAY
`
`EACH REMAINING PS
`UPDATES AML
`T0 REFLECT REMOVAL “
`
`REMOVED PS
`NOTIFIES ALL PS5
`IN ITS AML 0F _
`REMOVAL
`
`l
`
`l
`
`Petitioner Ex. 1006 Page 12
`
`

`

`U.S. Patent
`US. Patent
`
`Jan. 22, 2002
`
`Jan. 22, 2002
`
`Sheet 11 0f 11
`
`Sheet 11 0f 11
`
`US 6,341,311 B1
`US 6,341,311 B1
`
`m2 .5
`
`33 m2
`
`
`
`Petitioner Ex. 1006 Page 13
`
`Petitioner Ex. 1006 Page 13
`
`

`

`1
`DIRECTING DATA OBJECT ACCESS
`REQUESTS IN A DISTRIBUTED CACHE
`BACKGROUND OF THE INVENTION
`1. The Field of the Invention
`The ?eld of the present invention is that of the proxy
`servers used in connection With accessing data over the
`World Wide Web (“WWW”) through the Internet or other
`Wide Area NetWork (“WAN”). More particularly, the
`present invention involves an array of multiple proxy servers
`con?gured together to act as a single distributed cache of
`information identi?ed through the use of Uniform Resource
`Locators (“URL”). Speci?cally, the invention treats the
`routing of a URL request received by one array member to
`the array member having the cached information associated
`With the URL.
`2. Present State of the Art
`Generally speaking, the concept of a “cache” or “caching”
`as used in computer terminology and applications typically
`means making a more accessible copy of some piece of data
`for a performance advantage. For example, information that
`is cached is in many instances more accessible than it
`otherWise Would be so that processing speed is increased
`since accessing the cached information is quicker.
`Since having excess copies of data can create its oWn sort
`of overhead and because cache siZe is limited, data is not
`typically retained in a cache inde?nitely and Will eventually
`be overWritten after a certain amount of time if the cache is
`being fully utiliZed. This may occur according to a Leased
`Recently Used (“LRU”) algorithm, an expiration time, or
`any other relevant criteria for a particular application. Cach
`ing commonly exists at the microprocessor level With
`instruction and data caches so as to avoid excessive access
`ing of system RAM and may also exist elseWhere in a
`computer system or in a netWork of computer systems.
`Another form of caching is commonly used in relation to
`accessing data or information over the WWW. Auser having
`Internet access can directly receive a URL identi?ed data
`object, such as a Web page, and then display it locally on a
`broWser. Each time the user receives such a data object, there
`is a delay as the Hyper Text Transport Protocol (“HTTP”)
`request travels across the Internet to the location identi?ed
`by the URL and the destination server processing the URL
`request responds With the requested data object. Because the
`data object can be quite large, the time to access the data
`objects With the HTTP request and response creates a
`signi?cant amount of information traveling over the Internet
`connection causing delays and excess overhead.
`In some organiZations, many of the same data objects are
`requested by the various users Within the organiZation. It is
`therefore common to introduce a proxy server that Will
`receive user access requests from a client application, such
`as a Web broWser. Referring to FIG. 1, the use of a proxy
`server acting as a cache is shoWn. Aclient application 20 Will
`direct all URL requests to a proxy server 21 that Will serve
`as a cache for any information (i.e., URL data objects)
`associated With the URL. Should the proxy server 21 not
`have the URL data object Within its cache, it Will, in turn,
`make access over the Internet 22 to the destination server
`found Within the URL in order to place the data object into
`its cache and then respond to the client 20 URL request.
`Thereafter, should another client make a request to the proxy
`server 21, it can be serviced directly from the cache Without
`necessary access over the Internet to the destination server
`found in the URL itself.
`Note that the client 20 can be any softWare application
`capable of communicating or directing requests to the proxy
`
`45
`
`55
`
`65
`
`US 6,341,311 B1
`
`15
`
`25
`
`35
`
`2
`server 21 using the HTTP protocol and Would include other
`proxy servers, Web broWsers, Internet “enabled”
`applications, etc. Furthermore, HTTP requests contain a
`variety of information that can be used to “force” the proxy
`server 21 to access the URL data object over the Internet in
`order to assure that the “freshest” copy has been accessed.
`Such operation of proxy servers and their use as caches are
`generally knoW in the art for use in servicing IITTP requests.
`It should be noted that the term URL may indicate either
`the address of Where a data object is originally located and
`accessed, or the data object itself. To distinguish, a URL
`itself Would be an address or location of the data object
`Whereas a URL data object Would be the actual Web page ?le
`that is transmitted across the Internet to the client applica
`tion. Though the appropriate usage is readily identi?able by
`context, efforts Will be made throughout this application to
`distinguish betWeen the tWo.
`There are bene?ts of having a proxy server acting as a
`cache for URL data objects. One bene?t is that for cached
`items, the total access time for a user is generally reduced
`since the connection betWeen the client 20 and the proxy
`server 21 is typically over a Local Area NetWork (“LAN”)
`rather than having to access the data object over the Internet
`or other Wide Area NetWork (“WAN”). Another bene?t is
`for security purposes so that an organiZation may have a
`“?reWall” to protect itself from unWanted outside penetra
`tion.
`Larger corporations and other organiZations may have
`many proxy servers servicing their needs. It becomes desir
`able in such situations to harness many proxy servers
`together as a single, logical distributed cache. Ideally, such
`a single distributed cache Would have no duplication of URL
`data objects contained therein. Furthermore, a single dis
`tributed cache should have as little overhead as possible in
`servicing any given URL request that arrives at a member of
`the distributed cache. In other Words, the actual URL data
`object may not be residing at the same server that originally
`receives the URL request and some form of forWarding,
`routing, or acquisition of the desired URL data object must
`occur in order to service that original URL request.
`One attempt at creating a such a distributed cache is the
`Internet Cache Protocol (“ICP”) that coordinates the activity
`of an “array” of proxy servers. Though ICP alloWs an array
`of proxy servers to function as a distributed cache, it also has
`some draWbacks as Will be explained hereafter.
`Referring noW to FIG. 2, the interaction of a client With
`a proxy server array is shoWn. In such an arrangement, a
`client 23 Will contact one of the proxy servers in the array
`24 in order to access URL data objects that are available over
`the Internet 25. Typically, a client 23 is assigned to a
`particular proxy server Within the proxy server array 24 and
`may itself be a proxy server. Since the URL data object
`requested by a client may exist in a different proxy server
`than the one contacted, a mechanism or protocol is necessary
`for routing the URL request from the receiving proxy server
`to the appropriate proxy server, or in some other Way service
`that URL request.
`Referring noW to FIG. 3, proxy server array that is
`organiZed and con?gured according to the ICP protocol is
`shoWn. In the example shoWn in FIG. 3, a client 26 Will
`direct HTTP requests to an assigned proxy server 27 that is
`part of an ICP proxy server array 28. Assuming that a desired
`URL data object is contained in the distributed cache created
`by the ICP proxy server array 28 and located at the proxy
`server 29, a scenario illustrating the operation of ICP is noW
`shoWn. This scenario Will also illustrate a number of prob
`
`Petitioner Ex. 1006 Page 14
`
`

`

`US 6,341,311 B1
`
`10
`
`15
`
`3
`lems that make ICP a less than optimal Way of creating a
`distributed cache.
`The URL request Will originate at the client 26 and be
`received by the proxy server 27 as indicated by arroW 30.
`After determining that the desired URL object does not
`reside at the proxy server 27 in its local cache storage, a
`query Will be sent out to all proxy servers in the ICP proxy
`server array 28 as indicated by the query messages path 32.
`In turn, every other proxy server that receives the query Will
`give a response back to the proxy server 27 as indicated by
`the response message path 34. Each individual response Will
`indicate Whether or not the speci?ed URL data object resides
`at that particular responding proxy server. Note that more
`than one of the proxy servers in the ICP proxy server array
`28 may contain a given URL data object.
`For purposes of this example, it is assumed that only the
`proxy server 29 actually contains the data object and there
`fore the response from proxy server 29 to proxy server 27
`Would be the only response having an indication that the
`desired or requested URL data object exists thereon. Note
`that for an ICP proxy server array 28 of N proxy servers, that
`N-1 messages Were sent out by the proxy server 27 querying
`for the existence of the URL data object and N-1 messages
`Were sent back to or received by the proxy server 27 in
`response, thus creating a fair amount of netWork message
`25
`traf?c and usage of the overall netWork bandWidth.
`Once the proxy server 27 knoWs Where the desired URL
`data object is located, it Will issue a request to get the object
`as indicated by the get path 36. Naturally, the proxy server
`Will respond by sending the desired URL data object from
`the proxy server 29 to the proxy server 27 as indicated by the
`send object path 38. NoW that the proxy server 27 has the
`desired URL data object, it can respond to the original URL
`request and return that data object to the client 26.
`Cache storage redundancy can be seen since the proxy
`server 27 Will also place the URL data object into its local
`cache such that the same URL data object noW exists in both
`proxy server 27 and proxy server 29. Also, netWork usage
`overhead is signi?cant since the total number of messages to
`alloW the proxy server 27 the ability to service the original
`URL request for an ICP proxy server array 28 of N proxy
`servers is 2(N-1)+2 total data messages across the netWork.
`Given the above scenario, a number of undesirable prob
`lems exhibit themselves almost immediately. First, by using
`a query-response scenario to contact all of the proxy servers
`in the ICP proxy server array, a signi?cant amount of
`netWork resources may be consumed. Additionally, a natural
`consequence of the query-response scenario is that the larger
`the ICP proxy server array 28 becomes the greater the
`netWork overhead for each non-resident URL request, there
`fore adding a negative scalability component to operating an
`ICP server array. This means that each addition of another
`proxy server onto the array Will in fact increase the amount
`of communication betWeen the different proxy servers for all
`array members and for each request in order to resolve the
`correct location of a desired URL data object. Theoretically,
`there may exist an upper limit to the number of proxy servers
`that may be comfortably used in an ICP proxy server array
`28.
`Another problem is that multiple copies of the distributed
`cache URL data objects exist across the various proxy
`servers. In an extreme case, each proxy server of the ICP
`proxy server array 28 could become a redundant mirror of
`the other array members. It Would be desirable to have only
`one copy of a URL data object existing in the entire
`distributed cache so that the distributed cache may be used
`to its full capacity.
`
`35
`
`4
`Finally, adding or deleting proxy servers from the ICP
`proxy server array 28 may totally disrupt the distribution of
`URL data objects across the entire logical cache. In an
`extreme case, the distributed cache may be “emptied” upon
`any addition or removal of a proxy server from a proxy
`server array.
`What is needed is a truly distributed logical cache across
`an array of proxy servers Where a given URL data object is
`contained therein at only one location so as to maximiZe
`cache capacity. Furthermore, What is needed is a Way to
`access the correct proxy server Within the logical distributed
`cache or array of proxy servers Without making a query to
`each and every proxy server making up the array thereby
`alloWing a request received at one proxy server to be directly
`routed to the correct proxy server, or alternatively, an
`acquisition of the desired URL data object from the correct
`proxy server quickly attained. Finally, What is needed is a
`Way of gracefully migrating cached URL data objects
`betWeen the different proxy servers as a result of additions
`or removals of proxy servers from the proxy server array
`making up the distributed cache that Will not require the
`reorientation of all URL data objects in the cache.
`SUMMARY AND OBJECTS OF THE
`INVENTION
`It is an object of the present invention to alloW a URL data
`object request made to a proxy server array to be laterally
`routed to the proxy server having the desired URL data
`object in one hop Without making expensive query-response
`transactions With each and every proxy server in the array.
`It is another object of the present invention to share array
`membership information betWeen the array members so that
`such array member ship information may be deterministi
`cally processed, along With a requested URL, to indicate a
`particular proxy server assigned to have the desired URL
`data object and do so from any proxy server.
`It is a further object of the present invention to provide a
`proxy server array having positive scalability so that very
`large numbers of proxy servers may be used to create the
`array.
`It is another object of the present invention to utiliZe
`deterministic hashing algorithms to alloW consistent and
`predictable identi?cation of a proxy server to be assigned or
`have residing thereon a particular URL data object.
`It is yet another object of the present invention to provide
`a proxy server array that has a minimal amount of cached
`URL data object redundancy amongst the local caches of the
`individual proxy servers making up the array.
`Additional objects and advantages of the invention Will be
`set forth in the description Which folloWs, and in part Will be
`obvious from the description, or may be learned by the
`practice of the invention. The objects and advantages of the
`invention may be realiZed and obtained by means of the
`instruments and combinations particularly pointed out in the
`appended claims.
`To achieve the foregoing objects, and in accordance With
`the invention as embodied and broadly described herein a
`method, computer program product, and system for lateral
`URL lookup Within a distributed cache of URLs are pro
`vided. Aproxy server array according to the present inven
`tion makes up a form of queryless distributed caching that
`reduces the extraneous netWork traf?c associated With other
`forms of distributed caching, such as a ICP proxy server
`array.
`Each proxy server has access to the entire array member
`ship information stored in array membership list. This array
`
`45
`
`55
`
`65
`
`Petitioner Ex. 1006 Page 15
`
`

`

`10
`
`15
`
`25
`
`US 6,341,311 B1
`5
`membership list is periodically updated and re?ects changes
`in array membership due to additions, removals, or tempo
`rary unavailability of the various proxy servers that make up
`the array. When changes have propagated through the proxy
`server array, all array membership lists at each proxy server
`Will contain identical information.
`When a proxy server receives a URL data object request,
`it uses the array membership list, the URL itself, and a
`deterministic hashing function to identify Which array mem
`ber should actually hold the URL data object in its local
`cache. The request may then be serviced by laterally access
`ing the desired data object from the correct proxy server
`Without making expensive query-response transactions over
`the netWork. The hashing function operates so as to distrib
`ute the cached URL data objects evenly over the entire proxy
`server array Without redundancy so as to more ef?ciently use
`the array capacity.
`The proxy server identi?cation mechanism Works by
`computing a hash value for each server name found in the
`array membership list and a hash value for the requested
`URL. The URL hash value is combined With each member
`proxy server hash value to form a combined value. The
`proxy server associated With the highest of the combined
`values is identi?ed as Where the desired URL should reside
`in local cache. Aload factor that assigns some proxy servers
`proportionately more URL data objects for the local cache is
`also incorporated in the creation of the combined hash
`values.
`All information for making a determination as to the
`correct proxy server is completely available at a single proxy
`server receiving the URL request so that no external infor
`mation is necessary. Furthermore, because of the propaga
`tion of array membership information betWeen the proxy
`servers, it is the exact same information and Will identify the
`exact same proxy server regardless of Which proxy server
`originally receives the URL request.
`These and other objects and features of the present
`invention Will become more fully apparent from the folloW
`ing description and appended claims, or may be learned by
`the practice of the invention as set forth hereinafter.
`BRIEF DESCRIPTION OF THE DRAWINGS
`In order that the manner in Which the above-recited and
`other advantages and objects of the invention are obtained a
`more particular description of the invention brie?y described
`above Will be rendered by reference to speci?c embodiments
`thereof Which are illustrated in the appended draWings.
`Understanding that these draWings depict only typical
`embodiments of the invention and are not therefore to be
`considered limiting of its scope, the invention Will be
`described and explained With additional speci?city and
`detail through the use of the accompanying draWings in
`Which:
`FIG. 1 is a logical diagram shoWing the use of a proxy
`server that serves as a cache from Which a client may access
`desired URL data objects.
`FIG. 2 is a logical diagram illustrating hoW an array of
`proxy servers may be logically con?gured to be a single
`distributed cache having a greater capacity.
`FIG. 3 is a logical diagram shoWing an array of proxy
`servers that coordinate using the Internet cache protocol or
`ICP With an illustration of hoW a request directed into the
`cache at one proxy server may query all other proxy servers
`in the cache and eventually receive the data object laterally
`from another proxy server in order to service the original
`request.
`
`6
`FIG. 4 is a block diagram of an exemplary system for
`implementing the present invention that includes a general
`purpose computing device in the form of a conventional
`personal computer.
`FIG. 5 is a logical diagram shoWing the operation of a
`proxy server array con?gured to form a distributed cache
`Where requests are serviced according to the present inven
`tion and an example is given Where a request received by
`one proxy server of the array may laterally access the proxy
`server having the desired URL data object Without making
`queries to all proxy servers in the array.
`FIG. 6 is a How chart shoWing the processing steps taken
`by a proxy server according to the present invention When
`receiving a URL data object request.
`FIG. 7 is a logical diagram shoWing an array of proxy
`servers con?gured to form a distributed cache according to
`the present invention and an enabled client according to the
`present invention Wherein the client may make the original
`URL data object request directly to the proxy server Within
`the array that is most likely to contain the desired URL data
`object.
`FIG. 8 is a How chart shoWing the processing steps taken
`by an enabled client for directly assessing the proxy server
`in a proxy server array that is most likely to contain the
`desired URL data object.
`FIGS. 9A—9D shoW a logical sequence of events that may
`occur in the life of a proxy server array according to the
`present invention. FIG. 9A shoWs the initial state of the
`proxy server array having tWo proxy servers and each Array
`Membership list (“AML”) shoWing the tWo active members.
`In FIG. 9B, a third proxy server is added to the array and the
`array membership list for all three proxy servers is updated
`to include the neWly added proxy server. In FIG. 9C, one
`proxy server is temporarily unavailable due to mechanical
`failure or other event and the array membership list of the
`remaining proxy servers in the array have been marked to
`indicate that the designated proxy server is temporarily
`unavailable. In FIG. 9D, the same proxy server as Was
`unavailable in FIG. 9C is actually removed from the array
`and the array membership lists from the remaining proxy
`servers are updated to indicate the removal of the proxy
`server from the list.
`FIG. 10 is a How chart shoWing the processing steps taken
`by a proxy server or enabled client for randomly accessing
`an array membership list from another member of the proxy
`server array that represents one form of communicating
`array membership information betWeen the different proxy
`servers and enabled clients.
`FIG. 11 is a How chart shoWing the steps taken in order
`to add a neW proxy server to the proxy server array.
`FIG. 12 is a How chart shoWing the steps taken for
`removing a proxy server from the array.
`FIG. 13 is a logical diagram shoWing hoW a proxy server
`array according to the present invention may be used With
`legacy clients and enabled clients.
`FIG. 14 is a logical diagram shoWing tWo levels of proxy
`server arrays according to the present invention may be used
`in a realistic environment Where both lateral access and
`direct access are accomplished. A ?rst proxy array uses
`lateral access Within the array in order to service non
`enabled or legacy clients, but in turn may directly access the
`proxy server array of an Internet service provider.
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`As used herein, the term “hashing function” refers to
`those functions knoWn in the art that systematically covert
`
`55
`
`65
`
`Petitioner Ex. 1006 Page 16
`
`

`

`US 6,341,311 B1
`
`10
`
`15
`
`25
`
`7
`one multi-bit representation into another, usually smaller,
`single or multi-bit representation. Ahashing function is said
`to be deterministic if it generates the same results from the
`same input.
`As used herein, the term “data object” refers to any data
`that may be accessed from a distributed store and singularly
`identi?ed. Examples of data objects Would include, but not
`be limited to, ?les, database records, graphic images, pro
`gramming “objects,” etc. One particular data object that Will
`be used throughout the application is a URL data object that
`is any resource that can be identi?ed and accessed using a
`URL according to the HTTP protocol. Typically, this Would
`be a Hyper Text Markup Language (“HTML”) ?le that is
`located on a server of the World Wide Web and accessed
`using a URL. Those skilled in the art Will appreciate that the
`invention as explained using URL data objects accessed over
`the Internet Will apply to many other environments having a
`distributed store of data objects.
`As used herein, the term “array membership information”
`refers to information regarding all the servers making up an
`array of servers that can be con?gured into a distributed
`cache. As used more particularly throughout With one
`embodiment of the present invention, this Would be infor
`mation regarding proxy servers in a proxy server array that
`is used to cache URL data objects. Note that such array
`membership information may be incorporated into a ?le or
`data structure that may be shared or updated betWeen the
`different array members, such as an array membership list.
`Array membersh