`Exhibit  1001  
`  
`
`
`
`Exhibit 1001Exhibit 1001
`
`

`

`(12)
`
`United States Patent
`Lowery et a].
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,188,145 B2
`Mar. 6, 2007
`
`US007188145B2
`
`(54) METHOD AND SYSTEM FOR DYNAMIC
`DISTRIBUTED DATA CACHING
`
`(75) IIWBIIIOFSI Keith A- Lowery, Richardson, TX
`(Us); Bryan S- Chm, Plano, TX (Us);
`David A. Consolver, Arlington, TX
`(US); Gregg A. DeMasters, Plano, TX
`(Us)
`
`_
`(73) Assrgnee: EpicRealm Licensing LLC, Dallas, TX
`(Us)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`USC 154(b) by 875 days.
`
`(21) Appl. No.2 09/759,406
`
`(22) Filed:
`
`Jan. 12, 2001
`_
`_
`_
`PI‘IOI‘ Pllbllcatloll Data
`US 2002/0107934 A1
`Aug. 8, 2002
`
`(65)
`
`(51) Int Cl
`(2006.01)
`G06F 15/167
`(52) US. Cl. .................... .. 709/214; 709/203; 709/217;
`709/219; 709/226; 707/10; 707/200; 710/56;
`711/119; 711/126; 711/130; 711/135
`(58) Field Of Classi?cation Search .............. .. 709/213,
`709/217, 201, 212, 203, 205, 215, 216, 248;
`707/8,10; 711/151
`See application ?le for Complete Search history
`_
`References Clted
`U.S. PATENT DOCUMENTS
`
`(56)
`
`4,603,382 A *
`
`7/1986 Cole et a1. .................. .. 710/56
`
`5,522,045 A *
`
`5/1996 Sandberg . . . . . . . .
`
`. . . .. 709/215
`
`5,537,572 A *
`
`7/1996 Michelsen et a1.
`
`711/135
`
`5,701,427 A * 12/1997 Lathrop . . . . . . . . . .
`
`. . . .. 709/237
`
`709/226
`7/1998 Gregerson et a1.
`5,778,185 A *
`1/1999 Boyle .................... .. 707/10
`5,864,854 A *
`8/1999 Schmuck et a1. ......... .. 707/200
`5,940,838 A *
`5,968,176 A * 10/1999 Nessett et a1. ............ .. 713/201
`5,987,477 A * 11/1999 Schmuck et a1. ......... .. 707/201
`
`5,988,847 A * 11/1999 McLaughlin et a1. ........ .. 700/9
`6,006,254 A * 12/1999 Waters et a1. ............. .. 709/205
`
`6,026,474 A
`6,065,102 A *
`6,098,064 A *
`
`2/2000 Carter et a1. .............. .. 711/202
`5/2000 Peters et a1. .... ..
`711/151
`8/2000 P110111 et a1. ................. .. 707/2
`
`(Continued)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`0993 163 Al
`
`4/2000
`
`(Continued)
`OTHER PUBLICATIONS
`
`Author: John Borland, Article entitled “Net video not yet ready for
`prime time”, printed from Web site WWW.cnet.com on Aug. 15,
`2000'
`
`(Continued)
`Primary ExamineriSaleh Najjar
`Assistant ExamineriMichael Won
`(74) Attorney, Agent, or FirmiBaker Botts L.L.P.
`
`(57)
`
`ABSTRACT
`
`A method and system for dynamic distributed data caching
`is presented. The method includes providing a cache com
`munity (402) comprising at least one peer (413). Each peer
`has an associated ?rst content portion (511) indicating
`content to be cached by the respective peer. A client (404)
`may be allowed to join the cache community. A peer list
`(426) associated With the cache community is updated to
`include the client. The peer list indicates the peers in the
`cache community. Arespective second content portion (511)
`is associated With each peer based on the addition of the
`client.
`
`36 Claims, 11 Drawing Sheets
`
`UPDATE PEER LIST
`
`910
`
`SEND ALLOW MESSAGE
`
`UPDATE ALLOCATION TABLE
`
`914
`
`SEND UPDATE PEER LIST MESSAGE
`
`Petitioner Ex. 1001 Page 1
`
`

`

`US 7,188,145 B2
`Page 2
`
`US. PATENT DOCUMENTS
`
`8/2000 Wang ....................... .. 711/119
`6,112,279 A *
`9/2000 Walker et al. .
`707/8
`6,122,629 A *
`6,167,438 A * 12/2000 Yates et al.
`709/216
`6,167,490 A * 12/2000 Levy et al. ..... ..
`711/148
`6,199,179 B1* 3/2001 Kaulfman et al.
`714/26
`6,205,481 B1* 3/2001 Heddaya et al.
`. 709/226
`6,263,302 B1 *
`7/2001 Hellestrand et al. ........ .. 703/17
`6,330,605 B1* 12/2001 Christensen et al. ...... .. 709/226
`6,477,150 B1* 11/2002 Maggenti et al.
`370/312
`6,487,583 B1* 11/2002 Harvey et al. ..... ..
`709/204
`6,542,926 B2* 4/2003 Zalewski et al.
`709/213
`6,725,261 B1* 4/2004 Novaes et al.
`709/220
`6,785,704 B1* 8/2004 McCanne .... ..
`718/105
`2002/0026560 A1* 2/2002 Jordan et al.
`711/120
`2002/0103972 A1* 8/2002 Satran et al. ............. .. 711/119
`
`FOREIGN PATENT DOCUMENTS
`
`W0
`
`WO 98/22891
`
`5/1998
`
`OTHER PUBLICATIONS
`
`Author: Corey Grice, Article entitled “Start-up taps swapping to
`ease Web bottlenecks”, printed from web site www.cnet.com on
`Aug, 15, 2000.
`Author: VTrails.com. Product information regarding company’s
`Full Duplex Packet Cascading technology printed from web site
`www.vtrails.com on Aug. 15, 2000.
`Author Vinod Valloppillil and Keith W. Ross, Internet-Draft docu
`ment entitled “Cache Array Routing Protocol v1.0”, printed from
`web site www.globecom.net on Nov. 14, 2000.
`Author: Microsoft Corporation. Information regarding the Cache
`Array Routing Protocol (CARP) and Microsoft ProXy Server 2.0,
`printed from web site www.msdn.microsoft.com on Oct. 9, 2000.
`
`Author: Geek.com. Information news article entitled “Cash for your
`unused CPU cycles”, printed from web site www.geek.com on Jun.
`30, 2000.
`Author: Dcypher.net. Answers to frequently answered questions
`v1.5, printed from web site www.dcypher.net on Jun. 30, 2000.
`Author: Popular Power. Information regarding the company’s Popu
`lar Power for Windows software, printed from web site www.
`popularpower.com on Jun. 30, 2000.
`Author: ProcessTree Network. Information regarding their “for
`pay” distributed processing network, printed from web site www.
`distributedscience.com on Jun. 30, 2000.
`Author: Keith Schultz, Article entitled “Pushing content to the
`Internet’s Edge”, printed from web site www.internetweek.com on
`Jan. 11, 2001.
`US. Appl. No. 09/759,392, ?led Jan. 12, 2001, entitled “Method
`And System For Community Data Caching” 78 total pages.
`Greg Barish, et al., “World Wide Web Caching: Trends and Tech
`niques,” XP-000949799, IEEE Communications Magazine, May
`2000, pp. 178-185.
`PCT/US 02-00886 Search Report, 6 pages, Oct. 2000.
`PCT/US 02-00886 Search Report, 10 pages, Mar. 27, 2003.
`Inohara, et al., “Self-Organizing Cooperative WWW Caching,” ©
`1998 IEEE (pp. 74-83).
`Zhang, et al., “Adaptive Web Caching,” Proceedings of the 1997
`NLANR Web Cache Workshop, Apr. 25, 1997 (9 pages).
`Michel, et al., “Adaptive Web Caching: Towards a New Global
`Caching Architecture,” © 1998 Elsevier Science B. V, Computer
`Networks and ISDN Systems 30 (1998) (pp. 2169-2177).
`Karger, et al., “Web Caching with Consistent Hashing,” © 1999
`Elsevier Science B. V, Computer Networks 31 (1999)(pp. 1203
`1213).
`
`* cited by examiner
`
`Petitioner Ex. 1001 Page 2
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 1 of 11
`
`US 7,188,145 B2
`
`M55
`
`5302
`
`9
`
`2520
`
`Ezam
`
`-5382
`M56
`
`:u»:»mmx/DE
`
`V‘
`
`LO
`
`_._.Z___.________
`
`Illllllll
`mm./mm_
`
`-52902
`
`was
`
`Petitioner Ex. 1001 Page 3
`
`Petitioner Ex. 1001 Page 3
`
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 2 0f 11
`
`US 7,188,145 B2
`
`I- _ _ _ _ _ - _ _ — _ _ _ _ _ _ — _ _ _ _ _ _ _ _ __"I
`
`I
`i
`|
`:
`|
`:
`{ 102\
`1
`I
`I
`l
`
`I :
`
`120 52
`150
`/
`\ F‘l
`CACHE
`BROWSER 124
`ON/OFF
`|
`\
`CACHE MODULE
`125\ LOCATION TABLE
`
`126
`
`122
`
`l
`I
`
`l
`|
`'
`I
`I
`{
`l 104/
`I
`I
`
`l
`I
`I
`i
`I
`I
`l
`:
`|
`:
`:
`:
`: 106
`I
`I
`I
`I
`l
`l
`L
`
`f
`
`140 32
`150
`/
`\ I1
`CACHE
`BROWSER 144
`ON/OFF
`l
`\
`CACHE MODULE
`148% LOCATION TABLE
`
`146
`
`142
`
`32
`
`170
`160
`/
`L
`CACHE
`BROWSER 164
`1 L ON/OFF
`CACHE MODULE
`168% LOCATION TABLE
`
`,___—___
`
`166
`
`162
`
`Petitioner Ex. 1001 Page 4
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 3 0f 11
`
`US 7,188,145 B2
`
`FIG. 3
`( START )
`
`200\ BROWSER OENERATES
`REQUEST
`
`CACHE MODULE
`INTERCEPTS REQUEST
`
`BROADCAST
`HEARTBEAT
`
`V230
`
`WAIT
`
`f232
`
`204\
`
`DETERMINE
`REQUEST URL
`
`205\
`
`‘
`DETERMINE LOCATION
`OF COMMUNITY
`CACHE FOR URL
`
`208x CHECK CACHE FOR
`CONTENT
`
`NO
`
`CACHED
`1)
`'
`
`21D
`
`YES
`212% RETRIEVE CACHED
`
`I
`RETRIEVE FROM
`ORIGIN SERVER
`
`“SEE
`
`I.
`TRANSMIT TO
`CACHE LOCATION \ZIB
`
`V
`CACHE
`
`CONTENT
`
`4
`
`IF
`DISPLAY IN BROWSER
`
`214/
`
`CID
`
`Petitioner Ex. 1001 Page 5
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 4 0f 11
`
`US 7,188,145 B2
`
`FIG. 4
`
`@
`
`INITIATE CACHE MODULE
`
`f500
`
`BROADCAST CACHE ON MESSACE f502
`1
`NECOTIATE PRIMARY DISTRIBUTION f503
`L
`NECOTIATE SECONDARY DISTRIBUTION /304
`1
`UPDATE LOCATION TABLES
`1
`RECEIVE DISTRIBUTION SHARE \506
`
`/505
`
`510
`
`COLLECT
`STATISTICS
`
`CHE
`DATA
`
`1
`
`BROADCAST CACHE OFF MESSAGE #512
`1
`CLEAR CACHE
`
`\514
`
`FIG. 5
`
`PRIMARY ?
`
`v
`
`"
`
`w
`
`J‘
`
`v
`
`'
`
`%ABCOEFCH1JKLMNOPQRSTUVWXYZ
`
`106
`104
`102
`ABCDEFGHlJKLMNOPQRSTUVWXYZ
`
`104
`
`100
`
`102
`
`106
`
`102
`
`104
`
`ALTERNATEgABCDyEFGHLJKLMNORQRSTUVWXY;
`
`SECONDARY
`
`106
`
`‘vi
`
`102
`
`v
`
`104
`
`Petitioner Ex. 1001 Page 6
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 5 0f 11
`
`US 7,188,145 B2
`
`400
`\
`
`FIG. 6
`
`4/06
`
`415
`\ COMMUNITY 410
`/
`
`MASTER
`
`420
`424\
`
`ALLOW
`MESSAGE
`
`422
`426) PEER LIST
`
`412
`VL
`430
`
`MEMBER
`
`452
`
`DYNAMIC
`CACHE APP
`/
`428
`
`I
`
`I
`
`/
`402
`
`440
`
`442
`
`428/
`
`470
`
`472
`
`CACHE sERvER
`
`ADMIN f474
`MODULE
`L
`COMMUNITY f476
`LIST
`
`478
`f
`
`EXPIRATION
`MOTLE
`EXPIRATION /480
`MESSAGE
`
`ORIOIN SERVER
`
`CONTENT \460
`
`\
`19
`
`INTERNET
`
`I6
`
`CLIENT
`
`DYNAMIC CACHE
`APPLICATION
`
`450
`
`COMMUNITY
`REQUEST
`
`JOIN
`452/ REQUEST
`
`\404
`
`f ADD
`454 mm
`
`PROBE
`456/ MESSAGE
`
`Petitioner Ex. 1001 Page 7
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 6 0f 11
`
`US 7,188,145 B2
`
`F
`
`51 1
`CONTENT
`PORTION f
`5T0
`500
`/
`\
`CACHE A ALLOCATION
`
`502
`/
`EXPIRATION
`
`428
`/
`
`HOLD
`530% ELECTION
`MESSAGE
`
`REMOVE
`528\ PEER
`MESSAGE
`
`424
`\
`M’ééLSi‘éE
`
`PEER LIST / 426
`
`COMMUNITY M450
`REQUEST
`
`FIG 7 I
`
`‘
`
`.
`
`REMOVE
`527\ MASTER
`REQUEST
`
`f MASTER
`526
`REQUEST
`
`DYNAMIC
`AFFILIATION
`PORTION
`Q0}.
`UPOATE / \ ADD
`
`REgOJEST f452
`
`MASTER \
`REQUEST
`454
`
`NOMINATE
`4% MASTER
`MESSAGE
`52
`
`PROBE
`MESSAGE
`
`\
`456
`
`MEMBER
`STATUS
`REQUEST
`/
`522
`
`UPOATE
`PEER LIST
`MESSAGE
`\
`520
`
`Petitioner Ex. 1001 Page 8
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 7 of 11
`
`US 7,188,145 B2
`
`fizmm2520
`
`20:53
`
`Q3
`
`M55
`
`zoEo.__
`
`zo:<8j<
`
`mi
`
`fimsomm
`
`m.
`
`on
`
`<3
`
`Petitioner Ex. 1001 Page 9
`
`Petitioner Ex. 1001 Page 9
`
`
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 8 0f 11
`
`US 7,188,145 B2
`
`@
`
`SEND COMMUNITY
`600
`\ REQUEST TO
`ADMIN MODULE
`
`602
`
`RECEIVE
`RESPONSE
`I?
`
`F I G. 9
`
`SEND PROBE
`622
`\ MESSAGE 0N
`KNOWN PORT
`
`/ 604
`
`EXAMINE
`COMMUNITY LIST
`I
`FIND "BEST FIT" /606
`COMMUNITY TO JOIN
`
`RECEIVE
`RESPONSE
`
`624
`
`DO ANY
`COMMUNITIES
`MATCH "BEST FIT"
`CRITERIA?
`
`NOMINATE SELF
`AS A MASTER
`I
`SEND A NUMBER TO
`ADMIN MODUL:
`620
`
`5
`END
`
`SEND JOIN REQUEST
`MESSAGE TO MASTER \610
`
`CLIENT ADDED
`TO COMMUNITY
`I
`
`614
`
`‘I—
`PICK NEXT "BEST
`FIT" COMMUNITY \616
`?_____
`
`Petitioner Ex. 1001 Page 10
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 9 0f 11
`
`US 7,188,145 B2
`
`( MASTER )
`AGTIvE
`I:
`9OO\ LISTEN FOR JOIN REQUEST
`I
`EVALUATE JOlN REQUEST
`
`902\
`
`FIG 70
`
`IGNORE JOIN REQUEST f906
`
`L
`
`_
`
`908A
`
`910
`
`UPDATE PEER LIST
`I
`SEND ALLOw MESSAGE
`I
`912/ UPDATE ALLOCATION TABLE
`I
`SEND UPDATE PEER LIST MESSAGE
`I
`
`914
`
`(
`
`)
`
`MASTER
`ACTIVE
`‘I’:
`SEND MEMBER
`STATUS REQUEST
`
`IOOO\
`
`REMOVE MEMBER
`1006/ FROM PEER LIST
`I__—
`
`FIG. 11
`
`SEND UPDATE PEER fIOOs
`LIST MESSAGE
`I
`UPDATE
`ALLOCATION TABLE
`
`\
`T010
`
`:1
`wAIT FOR NEXT
`\IOO4
`STATUS INTERVAL
`|____
`
`Petitioner Ex. 1001 Page 11
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 10 0f 11
`
`US 7,188,145 B2
`
`FIG. 13
`
`MASTER
`ACTIVE
`
`1200\
`
`MASTER TO BE
`SHUT DDwN
`
`(
`
`)
`
`FIG. 12
`MASTER
`ACTIVE
`C
`LISTEN FOR
`HOO\ DEPARTING
`MEMBERS
`T
`1102\ REcETvE REMovE
`PEER MESSAGE
`T
`1104/ REMOVE MEMBER
`FROM PEER LIST
`T
`
`UPDATE
`/ ALLOCATION
`H06
`TABLE
`l
`SEND UPDATE
`/ PEER LIST
`“08
`MESSAGE
`I
`
`1220
`j
`SEND REMovE
`MASTER REQUEST
`
`NO
`
`A
`v
`1202\ DETERMINE NEw
`MASTER
`M
`1204\ REMDvE SELF FROM
`PEER LIST
`SEND AiMTNATE
`1206\ MASTER To NEw
`MASTER
`
`RESPONSE?
`
`1210/ SHUT DOWN MASTER
`4
`SEND PEER LlST
`MESSAGE
`T
`1214A SEND UPDATE MASTER
`
`1212f
`
`CM:
`
`Petitioner Ex. 1001 Page 12
`
`

`

`U.S. Patent
`
`Mar. 6, 2007
`
`Sheet 11 0f 11
`
`US 7,188,145 B2
`
`FIG. 74
`
`MEMBER
`ACTIVE
`>11
`13()()\ DETERMINE TIME SINCE LAST
`MEMBER STATUS REQUEST
`
`EXCEED
`THRESHOLD
`9
`
`I304\
`
`SEND HOLD
`ELECTION MESSAGE
`
`I506\
`
`V
`RECEIVE RESPONSES
`
`1510/
`
`ABORT ELECTION
`I
`
`‘
`SELECT NEW MASTER
`
`\1514
`
`BUILD NEW PEER LIST
`
`\1312
`
`‘I
`SEND NOMINATE MASTER
`TO NEW MASTER
`
`\I5I6
`
`NEW MASTER SENDS
`UPDATE MASTER
`
`i)
`
`RT320
`
`Petitioner Ex. 1001 Page 13
`
`

`

`US 7,188,145 B2
`
`1
`METHOD AND SYSTEM FOR DYNAMIC
`DISTRIBUTED DATA CACHING
`
`TECHNICAL FIELD OF THE INVENTION
`
`This invention relates in general to the ?eld of data
`processing systems and, more particularly, to a method and
`system for dynamic distributed data caching.
`
`BACKGROUND OF THE INVENTION
`
`As computers have groWn increasingly important in
`today’s society, the importance of the Internet has also
`increased. As increasing numbers of users access the Inter
`net, the need for ef?cient use of bandwidth has also
`increased. The increasing numbers of requests handled by
`the Internet are increasing the delay experienced by a user
`betWeen generating a request and receiving a response to the
`request because of bandWidth limitations.
`One traditional solution to decreasing bandWidth usage
`and decreasing the delay experienced by the user has
`involved caching previously requested content at the user’s
`computer for faster retrieval. A related traditional solution
`has involved caching previously requested content for mul
`tiple users at a single cache server. Another traditional
`solution has involved increasing the bandWidth of the net
`Work connection betWeen the Internet, the user and the Web
`servers handling the requests. HoWever, traditional solutions
`have often failed as the number of requests continue to
`increase and overload single cache servers and because of
`the expense associated With maintaining large numbers of
`high speed connections to the Internet. In addition, the
`traditional solutions have not utiliZed the “alWays-on” nature
`of neWer broadband connections such as digital subscriber
`line and cable modems.
`
`SUMMARY OF THE INVENTION
`
`From the foregoing, it may be appreciated that a need has
`arisen for a method and system for dynamic distributed data
`caching to provide more ef?cient use of bandWidth.
`According to one embodiment of the present invention, a
`method for dynamic distributed data caching is provided.
`The method comprises providing a cache community com
`prising at least one peer. Each peer has an associated ?rst
`content portion indicating content to be cached by the
`respective peer. The method further comprises alloWing a
`client to join the cache community, updating a peer list
`associated With the cache community to include the client,
`the peer list indicating the peers in the cache community, and
`associating a respective second content portion With each
`peer based on the addition of the client. The second content
`portion is distinct from the ?rst content portion.
`According to another embodiment of the present inven
`tion, a system for dynamic distributed data caching is
`presented. The system comprises logic encoded on storage.
`The logic is operable to provide a cache community com
`prising at least one peer. Each peer has an associated ?rst
`content portion indicating content to be cached by the
`respective peer and alloW a client to join the cache commu
`nity. The logic is further operable to update a peer list
`associated With the cache community to include the client.
`The peer list indicates the peers in the cache community. The
`logic is further operable to associate a respective second
`content portion With each peer based on the addition of the
`client. The second content portion is distinct from the ?rst
`content portion.
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`According to a further embodiment of the present inven
`tion, a method for dynamic distributed data caching is
`presented. The method comprises determining that a ?rst
`master associated With a cache community is non-opera
`tional, electing a second master to replace the ?rst master in
`the cache community, and allocating at least one content
`portion based on the loss of the ?rst master.
`According to a yet another embodiment of the present
`invention, a system for dynamic distributed data caching is
`presented. The system comprises logic encoded on storage.
`The logic is operable to determine that a ?rst master asso
`ciated With a cache community is non-operational, elect a
`second master to replace the ?rst master in the cache
`community, and allocate at least one content portion based
`on the loss of the ?rst master.
`According to yet a further embodiment of the present
`invention, a method for dynamic distributed caching is
`presented. The method comprises requesting a list of cache
`communities from a cache server and determining Whether
`at least one existing cache community exists. The method
`further comprises attempting to join a one of the existing
`cache communities When the existing cache communities
`are found and generating a neW cache community When no
`existing cache communities are found.
`According to another embodiment of the present inven
`tion, a system for dynamic distributed caching is presented.
`The system comprises logic encoded on storage. The logic
`is operable to request a list of cache communities from a
`cache server and determine Whether at least one existing
`cache community exists. The logic is further operable to
`attempt to join a one of the existing cache communities
`When the existing cache communities are found and generate
`a neW cache community When no existing cache communi
`ties are found.
`According to a further embodiment of the present inven
`tion, a method for dynamic distributed data caching is
`presented. The method comprises generating a content
`request for requested content at a ?rst peer in a cache
`community, determining a second peer associated With the
`requested content, the second peer being associated With the
`cache community, and retrieving, by the ?rst peer, the
`requested content from the second peer.
`According to yet another embodiment of the present
`invention, a system for dynamic distributed data caching is
`presented. The system comprises logic encoded on storage.
`The logic is operable to generate a content request for
`requested content at a ?rst peer in a cache community,
`determine a second peer associated With the requested
`content, the second peer being associated With the cache
`community, and retrieve, by the ?rst peer, the requested
`content from the second peer.
`According to yet a further embodiment of the present
`invention, a method for dynamic distributed data caching is
`presented. The method comprises communicating a com
`munity request from a dynamic cache module to an admin
`istration module and receiving a community list from the
`administration module in response to the community
`request, the community list including a list of communities.
`The method further comprises generating a join request to
`attempt to join a one of the communities in the community
`list and receiving an alloW message associated With the one
`of the communities. The method further comprises receiving
`a peer list associated With the one of the communities,
`receiving a content request, and storing content associated
`With the content request.
`According to an additional embodiment of the present
`invention, a system for dynamic distributed data caching is
`
`Petitioner Ex. 1001 Page 14
`
`

`

`US 7,188,145 B2
`
`3
`presented. The system comprises logic encoded on storage.
`The logic is operable to communicate a community request
`from a dynamic cache module to an administration module
`and receive a community list from the administration mod
`ule in response to the community request. The community
`list includes a list of communities. The logic is further
`operable to generate a join request to attempt to join a one
`of the communities in the community list and receive an
`alloW message associated With the one of the communities.
`The logic is further operable to receive a peer list associated
`With the one of the communities, receive a content request,
`and store content associated With the content request.
`According to a further additional embodiment of the
`present invention, a system for dynamic distributed data
`caching is presented. The system comprises means for
`providing a cache community comprising at least one peer.
`Each peer has an associated ?rst content portion indicating
`content to be cached by the respective peer. The system
`further comprises means for alloWing a client to join the
`cache community and means for updating a peer list asso
`ciated With the cache community to include the client. The
`peer list indicates the peers in the cache community. The
`system further comprises means for associating a respective
`second content portion With each peer based on the addition
`of the client. The second content portion is distinct from the
`?rst content portion.
`According to yet a further additional embodiment of the
`present invention, a system for dynamic distributed data
`caching is presented. The system comprises means for
`determining that a ?rst master associated With a cache
`community is non-operational, means for electing a second
`master to replace the ?rst master in the cache community,
`and means for allocating at least one content portion based
`on the loss of the ?rst master.
`According to yet another further additional embodiment
`of the present invention, a system for dynamic distributed
`caching is presented. The system comprises means for
`requesting a list of cache communities from a cache server
`and means for determining Whether at least one existing
`cache community exists. The system further comprises
`means for attempting to join a one of the existing cache
`communities When the existing cache communities are
`found and means for generating a neW cache community
`When no existing cache communities are found. According
`to another additional embodiment of the present invention,
`a system for dynamic distributed data caching is presented.
`The system comprises means for generating a content
`request for requested content at a ?rst peer in a cache
`community and means for determining a second peer asso
`ciated With the requested content. The second peer is asso
`ciated With the cache community. The system further com
`prises means for retrieving, by the ?rst peer, the requested
`content from the second peer.
`According to yet a further additional embodiment of the
`present invention, a system for dynamic distributed data
`caching is presented. The system comprises means for
`communicating a community request from a dynamic cache
`module to an administration module and means for receiving
`a community list from the administration module in
`response to the community request. The community list
`includes a list of communities. The system further comprises
`means for generating a join request to attempt to join a one
`of the communities in the community list and means for
`receiving an alloW message associated With the one of the
`communities. The system further comprises means for
`receiving a peer list associated With the one of the commu
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`nities, means for receiving a content request, and means for
`storing content associated With the content request.
`The present invention provides a number of technical
`advantages. Various embodiments of the present invention
`may provide all, some or none of these advantages. One such
`technical advantage is the capability to support a dynamic
`distributed caching system. In addition, the distributed cach
`ing system is supportable Without the use of specialiZed
`hardWare as standard personal computers may be used to
`support the distributed caching system. A further technical
`advantage is decreased utilization of expensive connections
`to the Internet and increased utilization of cheaper local area
`netWork connections and broadband connections, such as
`digital subscriber line and cable modems. By caching con
`tent at local machines on a local area netWork or on
`broadband connections to an Internet Service Provider,
`response time to requests for content is decreased by retriev
`ing the content from local machines. Additional bene?ts
`may be realiZed by alloWing more client machines to utiliZe
`a single connection to the Internet by decreasing the amount
`of bandWidth needed by particular client machines.
`Another technical advantage is the capability to dynami
`cally add and remove members from a distributed cache
`community. In contrast to traditional distributed caching
`systems, Which have typically required a human adminis
`trator to add and remove members from the distributed
`caching system, the present invention provides the capabil
`ity to dynamically add and remove members from the
`distributed cache community. Also, members may be added
`or removed from the cache community Without the inter
`vention of a human administrator. The present invention also
`reallocates the data to be cached by particular members of
`the distributed cache community based on the addition and
`subtraction of members to the distributed cache community.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`A better understanding of the present invention Will be
`realiZed from the detailed description that folloWs, taken in
`conjunction With the accompanying draWings, in Which:
`FIG. 1 is a block diagram illustrating a community cache
`system;
`FIG. 2 is a block diagram illustrating an exemplary
`community cache constructed according to the teachings of
`the present invention;
`FIG. 3 is a ?owchart illustrating a method for community
`caching according to the teachings of the present invention;
`FIG. 4 is a ?owchart illustrating a method for generating
`a community cache according to the teachings of the present
`invention;
`FIG. 5 is a diagram illustrating an exemplary distribution
`of cache shares according to the teachings of the present
`invention;
`FIG. 6 is a block diagram illustrating a dynamic caching
`system according to one embodiment of the system of FIG.
`1;
`FIG. 7 is a block diagram illustrating details of the
`dynamic cache application according to one embodiment of
`the present invention;
`FIG. 8 is a How diagram illustrating a method for retriev
`ing and caching content Within a cache community accord
`ing to one embodiment of the present invention;
`FIG. 9 is a How chart illustrating a method for adding a
`client to the cache community according to one embodiment
`of the present invention;
`
`Petitioner Ex. 1001 Page 15
`
`

`

`US 7,188,145 B2
`
`5
`FIG. 10 is a How chart illustrating a method for allowing
`the client to join the cache community according to one
`embodiment of the present invention;
`FIG. 11 is a How chart illustrating a method for deter
`mining Whether a member of the cache community has
`unexpectedly departed the cache community according to
`one embodiment of the present invention;
`FIG. 12 is a How chart illustrating a method for gracefully
`removing the member from the cache community according
`to one embodiment of the present invention;
`FIG. 13 is a How chart illustrating a method for gracefully
`removing a master from the cache community according to
`one embodiment of the present invention; and
`FIG. 14 is a How chart illustrating a method for alloWing
`the master to unexpectedly depart the cache community
`according to one embodiment of the present invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`FIG. 1 is a block diagram illustrating a community cache
`system 10. System 10 comprises one or more Internet
`Service Provider (ISP) clients 12, an ISP 14, an ISP caching
`community 15, a network 16, an Intranet caching commu
`nity 18 and an origin server 19.
`Client 12 comprises a processor 20, a computer readable
`memory 22, a computer readable storage device 24, a cache
`module 26 and a broWser 30. Client 12 may be adapted to
`execute any of the Well-knoWn MS-DOS, PC-DOS, OS/2,
`UNIX, Linux, MAC-OS, mainframe, minicomputer and
`WindoWs operating systems or other operating systems.
`Processor 20 comprises any suitable general purpose or
`specialiZed electronic processing device, such as a central
`processing unit (CPU), operable to communicate With
`memory 22 and storage device 24, and further to execute
`cache module 26 and broWser 30. Memory 22 comprises any
`suitable combination of transient or persistent memory oper
`able to store cache module 26 and broWser 30, and to
`communicate With processor 20. Storage device 24 com
`prises any suitable combination of optical, magnetic or other
`computer readable storage medium such as a ?oppy disk
`drive, a hard disk drive, a CD-ROM drive, a CD-RW drive,
`a magnetic tape drive or an optical drive. Storage device 24
`may also represent multiple computer readable storage
`devices. Storage device 24 includes a cache portion 28.
`Cache portion 28 comprises a portion of storage device 24
`used by cache module 26 for caching data. Access to cache
`portion 28 may be controlled by cache module 26 so as to
`prevent user modi?cation of data stored in cache portion 28.
`Cache portion 28 may comprise one or more directories, one
`or more logical partitions, one or more distinct physical
`devices and other suitable physical and logical elements.
`Cache module 26 comprises a softWare application oper
`able to manage cache portion 28 of storage device 24. Cache
`module 26 is operable to monitor the activities of broWser 30
`and to cache content items retrieved by broWser 30. Cache
`module 26 is also operable to respond to content requests
`from broWser 30 using content cached in cache portions 28
`at clients 12 in community 15. In one embodiment, cache
`module 26 may use the Cache Array Routing Protocol
`(CARP) to determining the location of content Within com
`munity 15. Cache module 26 is con?gurable such that limits
`may be placed on the siZe of cache portion 28 and the
`amount of processor time used on processor 20 by cache
`module 26. For example, a user associated With a client 12
`may con?gure the cache module 26 associated With that
`client 12 to use only 5% of the storage space and no more
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`than 10% of the processor time. For another example, a user
`associated With a client 12 may con?gure the cache module
`26 associated With that client 12 to only provide caching
`services When the system is idle, such as When a screen saver
`is active or When processor usage by the user of the client 12
`is beloW a particular threshold. In general, resource limits
`may be associated With cache module 26 such that cache
`module 26 is prevented from consuming more than a pre
`determined amount of the resource. The resources may
`comprise any of an amount of processor time on processor
`20, an amount of bandWidth on link 13, an amount of storage
`space on storage 24, an amount of memory 22 and other
`computing resources associated With client 12. Cache mod
`ule 26 is further operable to collect statistical information
`associated With link 13, broWser 30, client 12, portion 28,
`cache module 26 and other elements in community 15.
`Cache module 26 is further operable to encrypt data
`stored in cache portion 28. Cache module 26 may use any
`suitable symmetric and/or asymmetric encryption system for
`encrypting data in cache portion 28. For example, cache
`module 26 may use public-key/private-key encryption, the
`US. Data Encryption Standard (DES), the TWo?sh algo
`rithm, the BloW?sh algorithm and other suitable encryption
`systems. Encrypting data stored in cache portion 28 prevents
`a user associated With client 12 from unrestrictedly access
`ing and modifying cached content. Encryption also provides
`privacy as the user of any particular client 12 in community
`15 is prevented from vieWing the data retrieved by other
`users in community 15.
`The increasing use of “alWays-on” Internet connections
`With large bandWidth capacities alloWs for the use of a
`distributed caching system using non-specialized equip
`ment. Note that as used herein, an “alWays-on” connection
`is de?ned as a data connection betWeen a client computer,
`such as a personal computer, and a netWork, such as the
`Internet, Which operates Without competing With other
`devices associated With a user of the client computer. In
`addition, an “alWays-on” connection as used herein may be
`oif and may cycle betWeen being on and olf at unpredictable
`intervals. Stated another Way, an “alWays-on” connection
`has the capability to be continuously active Without inter
`fering With other devices usable by the user associated With
`the client computer, but the “alWays-on” connection is not
`required to be literally “alWays-on”.