(12) INTERNATIONAL APPLICATION PUBLISHED UNDER THE PATENT COOPERATION TREATY (PCT)
`
`(19) World Intellectual Property Organization
`International Bureau
`
`1111111111111111 IIIIII 111111111111111 lllll 111111111111111111111111111111111111111 IIII
`
`(43) International Publication Date
`21 August 2003 (21.08.2003)
`
`PCT
`
`(10) International Publication Number
`WO 03/069437 A2
`
`(51) International Patent Classification 7:
`
`G06F
`
`(21) International Application Number: PCT/US03/04108
`
`(22) International Filing Date: 11 February 2003 (11.02.2003)
`
`(25) Filing Language:
`
`(26) Publication Language:
`
`English
`
`English
`
`(30) Priority Data:
`10/073,938
`
`14 February 2002 (14.02.2002) US
`
`(71) Applicant (for all designated States except US): CABLE
`& WIRELESS INTERNET SERVICES, INC. [US/US];
`12th Floor, 45 Fremont Street, San Francisco, CA 94105
`(US).
`
`(72) Inventors; and
`(75) Inventors/Applicants (for US only): SEED, Steven,
`L. [US/US]; 5617 Sale Avenue, Woodland Hills, CA
`91367 (US). HOBBS, Kevin [US/US]; 324 Skyline Drive,
`Vista, CA 92084 (US). GLYNN, Shane, M. [US/US];
`
`4023 Lincoln Avenue, #2, Culver City, CA 90232 (US).
`FORAKER, Isaac, W. [US/US]; 20320 Valerio Street,
`Winnetka, CA 91306 (US). JONES, Peter, J. [US/US];
`1750-L Via Petirrojo, Thousand Oaks, CA 91320 (US).
`CHEN, Homer, H. [US/US]; 1616 Oakcottage Court,
`Thousand Oaks, CA 91361 (US).
`
`(74) Agents: SIRITZKY, BRIAN et al.; Heller, Ehrman,
`White & Mcauliffe, LLP, 1666 K Street, N.W., Suite 300,
`Washington, DC 20006-1228 (US).
`
`(81) Designated States (national): AE, AG, AL, AM, AT, AU,
`AZ, BA, BB, BG, BR, BY, BZ, CA, CH, CN, CO, CR, CU,
`CZ, DE, DK, DM, DZ, EC, EE, ES, Fl, GB, GD, GE, GH,
`GM, HR, HU, ID, IL, IN, IS, JP, KE, KG, KP, KR, KZ, LC,
`LK, LR, LS, LT, LU, LV, MA, MD, MG, MK, MN, MW,
`MX, MZ, NO, NZ, OM, PH, PL, PT, RO, RU, SC, SD, SE,
`SG, SK, SL, TJ, TM, TN, TR, TT, TZ, UA, UG, US, UZ,
`VC, VN, YU, ZA, ZM, ZW.
`
`(84) Designated States (regional): ARIPO patent (GH, GM,
`KE, LS, MW, MZ, SD, SL, SZ, TZ, UG, ZM, ZW),
`Eurasian patent (AM, AZ, BY, KG, KZ, MD, RU, TJ, TM),
`
`[Continued on next page]
`
`(54) Title: MANAGED OBJECT REPLICATION AND DELIVERY
`
`Network 100
`
`120
`
`Parent
`Server
`
`I 10 Origin
`Server
`
`l20 Parent
`\
`Server
`
`iiiiiiii
`
`---iiiiiiii
`-----iiiiiiii --
`---iiiiiiii
`
`iiiiiiii
`
`t---.
`~
`"'1'
`~ (57) Abstract: A method, system and computer program product for managed object replication and delivery redirects, directly or
`Q
`indirectly, a client's request for an object that is not available at a best or optimal handling edge server of a network to a parent
`-.... server that has the requested object. So, where the requested object is not available at the handling edge server, the client's request is
`~ redirected directly to the parent server that can provide the requested object to the client or indirectly via one or more parent servers
`to a parent server that can provide the requested object to the client. The method, system and computer program product further
`0 intelligently replicates the object to the edge server if the object is popular enough. Likewise, an object is removed from an edge
`> server when it is no longer popular. All redirection and replication operations are preferably transparent to the end-user and not
`
`;;, degrade the quality of service.
`
`Client
`
`' 140
`
`130
`Edge
`Server
`
`130
`130
`Edge
`Edge
`Server Server
`
`[tiii
`1111
`
`(
`130
`Edge
`Server
`
`/~fi//\
`• ( I\ ••
`
`110 Origin
`Server
`
`I 10 Origin
`Server
`
`,
`
`130
`Edge
`Server
`
`130
`Edge
`Server
`
`130
`Edge
`Server
`
`-i-
`
`Amazon v. Audio Pod
`US Patent 10,735,488
`Amazon EX-1011
`
`

`

`WO 03/069437 A2
`
`1111111111111111 IIIIII 111111111111111 lllll 111111111111111111111111111111111111111 IIII
`
`European patent (AT, BE, BG, CH, CY, CZ, DE, DK, EE,
`ES, Fl, FR, GB, GR, HU, IE, IT, LU, MC, NL, PT, SE, SI,
`SK, TR), OAPI patent (BF, BJ, CF, CG, CI, CM, GA, GN,
`GQ, GW, ML, MR, NE, SN, TD, TG).
`
`Declarations under Rule 4.17:
`as to the identity of the inventor (Rule 4.17 (i)) for the fol(cid:173)
`lowing designations AE, AG, AL, AM, AT, AU, AZ, BA, BB,
`BG, BR, BY, BZ, CA, CH, CN, CO, CR, CU, CZ, DE, DK,
`DM, DZ, EC, EE, ES, Fl, GB, GD, GE, GH, GM, HR, HU,
`ID, IL, IN, IS, JP, KE, KG, KP, KR, KZ, LC, LK, LR, LS, LT,
`LU, LV: MA, MD, MG, MK, MN, MW, MX, MZ, NO, NZ,
`OM, PH, PL, PT, RO, RU, SC, SD, SE, SG, SK, SL, TJ, TM,
`TN, TR, TT, TZ, UA, UG, UZ, VC, VN, YU, ZA, ZM, ZW,
`AR/PO patent (GH, GM, KE, LS, MW, MZ, SD, SL, SZ, TZ,
`UG, ZM, Zrf;, Eurasian patent (AM, AZ, BY, KG, KZ, MD,
`RU, TJ, TM), European patent (AT, BE, BG, CH, CY, CZ,
`DE, DK, EE, ES, Fl, FR, GB, GR, HU, IE, IT, LU, MC, NL,
`PT, SE, SI, SK, TR), OAP/ patent (BF, BJ, CF, CG, CI, CM,
`GA, GN, GQ, GW, ML, MR, NE, SN, TD, TG)
`as to applicant's entitlement to apply for and be granted
`a patent (Rule 4.17 (ii)) for the following designations AE,
`AG, AL, AM, AT, AU, AZ, BA, BB, BG, BR, BY, BZ, CA, CH,
`
`CN, CO, CR, CU, CZ, DE, DK, DM, DZ, EC, EE, ES, FI,
`GB, GD, GE, GH, GM, HR, HU, ID, IL, IN, IS, JP, KE, KG,
`KP, KR, KZ, LC, LK, LR, LS, LT, LU, LV: MA, MD, MG, MK,
`MN, MW, MX, MZ, NO, NZ, OM, PH, PL, PT, RO, RU, SC,
`SD, SE, SG, SK, SL, TJ, TM, TN, TR, TT, TZ, UA, UG, UZ,
`VC, VN, YU, ZA, ZM, ZW, AR/PO patent (GH, GM, KE, LS,
`MW, MZ, SD, SL, SZ, TZ, UG, ZM, Zrf;, Eurasian patent
`(AM, AZ, BY, KG, KZ, MD, RU, TJ, TM), European patent
`(AT, BE, BG, CH, CY, CZ, DE, DK, EE, ES, FI, FR, GB,
`GR, HU, IE, IT, LU, MC, NL, PT, SE, SI, SK, TR), OAP/
`patent (BF, BJ, CF, CG, CI, CM, GA, GN, GQ, GW, ML,
`MR, NE, SN, TD, TG)
`as to the applicant's entitlement to claim the priority of the
`earlier application (Rule 4. l 7(iii)) for all designations
`
`Published:
`without international search report and to be republished
`upon receipt of that report
`
`For two-letter codes and other abbreviations, refer to the "Guid(cid:173)
`ance Notes on Codes and Abbreviations" appearing at the begin(cid:173)
`ning of each regular issue of the PCT Gazette.
`
`-ii-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`MANAGED OBJECT REPLICATION AND DELIVERY
`
`BACKGROUND
`
`(0001]
`
`This invention relates in general to the field of computer networks.
`
`Particularly, aspects of this invention pertain to managed object replication and delivery
`
`over a network.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`(0002]
`
`Exemplary embodiments of the invention are illustrated in the
`
`accompanying drawings in which like references indicate similar or corresponding
`
`elements and in which:
`
`[0003]
`
`FIG. 1 is a high-level block diagram of a topology of the n;ianaged object
`
`replication and delivery method and system according to embodiments of the invention;
`
`(0004]
`
`FIG. 2 is a high-level block diagram illustrating the data flows of managed
`
`object replication and delivery method according to embodiments of the invention;
`
`[0005]
`
`FIGS. 3(a), 3(b) and 3(c) are a flow chart of the managed object replication
`
`and delivery method and the object purging method according to embodiments of the
`
`invention;
`
`(0006]
`
`FIG. 4 is a flow chart of a popularity computation according to
`
`embodiments of the invention;
`
`[0007]
`
`FIG. 5 is a flow chart of a replication scheme according to embodiments of
`
`I
`
`the invention;
`
`-1-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`[0008)
`
`FIG. 6 is a flow chart of a purge scheme according to embodiments of the
`
`invention; and
`
`[0009)
`
`FIG. 7 is a block diagram of the managed object replication and delivery
`
`system according to embodiments of the invention.
`
`DETAILED DESCRIPTION
`
`(0010]
`
`A typical content delivery network (CDN) operator deploys one or more
`
`parent servers, hosting a plurality of objects, in a network and one or more edge servers at
`
`the edge of the network to facilitate more cost-effective and efficient delivery of such
`
`objects to an end-user (client). End-users or client proxies that access customers' objects
`
`are called clients. Content provider companies, organizations, etc. that subscribe to the
`
`CDN service are referred to as customers. As used herein, an object includes, without
`
`limitation, an audio file (such as, e.g., an MP3 (Motion Picture Experts Group-I Layer 3)
`
`file and a RealNetworks, Inc. Real format file), a video file (such as an MPEG file), an
`
`image file (such as, e.g., a BMP (bitmap) file or JPEG (Joint Photographic Experts) file)
`
`and any other software or data file or object. It is typically desirable to serve objects from
`
`edge servers because the edge servers are typically closer (by various measures of
`
`distance) to end-users. For example, streaming content data from edge servers saves
`
`parent-to-edge bandwidth. Furthermore, the less the distance objects must travel can also
`
`mean reduced network congestion and packet losses, which can lead to a better experience
`
`for the end-user through faster response times and better quality of service.
`
`(0011)
`
`It is typically not feasible to store all objects on the edge servers. The main
`
`difficulty is due to the fact that many such objects are very large (typically on the order of
`
`2
`
`-2-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`10 MB (10,000,000 bytes) - - in the neighborhood of 500 MB for movies). The storage
`
`and rack space required to accommodate often large and sometimes rarely requested
`
`objects at every edge server can be cost prohibitive as the number of customers grows and
`
`the number of their objects increases. It may not even be possible to store a good working
`
`set of objects, for example a set of objects thought to be requested often and/or better
`
`suited to be served from an edge server, because of the size and changing demand for
`
`objects in the working set.
`
`(0012]
`
`One obvious solution is to pre-populate edge servers with objects for which
`
`there will likely be a significant or high demand. However, it is difficult to predict
`
`popularity and difficult to manage pre-populating. A related solution is to associate objects
`
`with two or more domains depending on popularity of the object, e.g., one domain for
`
`popular objects (served from edge servers) and another domain for less popular objects
`
`(served from parent servers). However, this requires some way to pre-determine what
`
`objects are popular and what objects are less popular statically, and build that popularity
`
`into the domain name of the object. As with pre-populating, it is difficult to predict
`
`popularity and to manage assignment of domains based on such popularity determinations.
`
`[0013]
`
`Other solutions fetch objects on demand. In such schemes, when a
`
`requested object is not available on a handling edge server, a connection is made between
`
`a parent server having the requested object and the handling edge server to fetch the
`
`requested object from the parent server. Such fetching suffers however from having to go
`
`through the parent path (the network path between the handling edge server and the parent
`
`server with the object) whenever a client requests an object that is not already at the
`
`particular edge server.
`
`3
`
`-3-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`[0014)
`
`Fetching a large object to the handling edge server through a parent path
`
`can be slow. For example, there may be limited available bandwidth from the parent
`
`server to the handling_edge server, i.e., sometimes the parent path has less bandwidth than
`
`even the network path from the edge server to the client ( e.g., the "last mile" in a
`
`broadband network). If a parent server uses too much bandwidth copying an object to an
`
`edge server, this can create congestion at that parent server. If storage fill bandwidth is
`
`matched to client bandwidth, it is difficult to handle a second, faster client and if fetch is
`
`done using a streaming protocol (for instance, the Real-Time Streaming Protocol (RTSP)
`
`and Real-Time Transport Protocol (RTP) standards), the quality of the copy made can be
`
`hurt due to lost packets ("thinning").
`
`[0015]
`
`Moreover, there may be an unreliable end-to-end parent path due to
`
`network congestion. And, if a parent server has to preprocess an object ( e.g., to generate
`
`an image at a specific bit rate) or is otherwise busy with other tasks, this may further slow
`
`its ability to serve the request for the object fast enough. For example, if a client requests a
`
`bit rate higher than the parent-to-edge bit rate, delays will likely occur. Under such
`
`conditions;- the parent server may fail, for example, to stream the object in time or to
`
`maintain the stream of an object at a requested bit rate thereby causing a thinned object,
`
`i.e., an object with lower quality due to lost packets in its transmission, to be populated at
`
`the edge server and delivered to subsequent clients requesting the same object.
`
`[0016]
`
`Thus, it would be advantageous to populate edge servers with the most
`
`popular objects yet somehow serve the rest from parent servers with a goal to maximize
`
`the amount of object bits served from edge servers of the network. It would also be
`
`advantageous to populate edge servers by, for example, storage fill on demand when an
`
`4
`
`-4-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`object is popular enough, without having to make the end-user wait for such population.
`
`Therefore, it would be advantageous to provide a method and system for managed object
`
`replication and delivery over a network.
`
`(0017]
`
`According to embodiments of the invention, a method and system for
`
`managed object replication and delivery over a network redirects, directly or indirectly, a
`
`client's request for an object that is not available at a best or optimal handling edge server
`
`of the network to a parent server of the network that has the requested object. So, where
`
`the requested object is not available at the handling edge server, the client's request is
`
`redirected directly to the parent server that can provide the requested object to the client or
`
`indirectly via one or more parent servers to a parent server that can provide the requested
`
`object to the client. The method and system further intelligently replicates the object to the
`
`edge server if the object is popular enough. Likewise, an object is removed from an edge
`
`server when the object is no longer popular. All redirection and replication operations are
`
`preferably transparent to the end-user and do not degrade the quality of service. Other
`
`embodiments of the invention are possible and some are described hereafter.
`
`(0018]
`
`So, for example, under the framework described herein, a request for a
`
`streaming object will be served by a handling edge server if that handling edge server has
`
`a copy of that object. Otherwise, the request is redirected, directly or indirectly, to a parent
`
`server for service of the requested streaming object to the client. If the requested streaming
`
`object is popular, the object is replicated from a parent server that has the requested
`
`streaming object to the handling edge server so that the handling edge server will serve the
`
`object from the edge of the network when the object is requested in the future. If a
`
`streaming object is no longer popular, the object is removed from an edge server.
`
`5
`
`-5-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`(0019]
`
`As used herein, replication generally refers to the permanent and/or volatile
`
`storage of an object in a server, particularly an edge server and if applicable, a parent
`
`server. Accordingly, the term replication will be considered synonymous to storing,
`
`caching and copying. In typical embodiments, replication of an object will usually refer to
`
`temporary storage of the object in an edge server and/or a parent server for an undefined
`
`duration.
`
`[0020]
`
`A typical network for the managed object replication and delivery method
`
`according to embodiments of the invention is illustrated in FIG. 1. The network 100
`
`comprises one or more parent server sites 120 and one or more edge server sites 130. The
`
`network also optionally has access to one or more origin server sites 110. The origin
`
`server sites are typically owned and/or maintained by the network provider's customers
`
`for storing and serving one or more objects. Each customer (content provider) may have
`
`its own origin server site. Furthermore, one or more clients 140 access the network to
`
`request one or more objects. A parent server site (or simply parent site or parent server)
`
`may comprise one parent server or a cluster of parent servers. Likewise, an edge server
`
`site ( or simply edge site or edge server) may comprise one edge server or a cluster of edge
`
`servers and an origin server site (or simply origin site or origin server) may comprise one
`
`origin server or a cluster of origin servers. Typically, the network 100 is configured such
`
`that servers in a cluster share a common storage. In any event, configuration details of the
`
`parent server site, edge server site, and the origin server site are not important to the
`
`present invention.
`
`[0021]
`
`In the typical network, the parent servers and edge servers are maintained
`
`by a network provider, wherein the parent servers are primarily used for storing and
`
`6
`
`-6-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`managing one or more objects and edge servers are primarily used for serving objects to
`
`clients. In some embodiments, all the objects are retrieved from origin servers and stored
`
`over one or more parent servers before any end-users can access each such object as the
`
`object is stored on the parent servers. Accordingly, in these embodiments, the origin
`
`servers play no significant role in the managed object replication and delivery method
`
`except to supply new and/or updated objects for storage on the parent servers. Moreover,
`
`only the parent servers communicate with the origin servers. In other embodiments, each
`
`requested object is replicated from one or more origin servers to one or more parent
`
`servers (and/or one or more edge servers) when the requested object becomes popular (as
`
`described in more detail below). In these embodiments, the origin servers play a more
`
`significant role in the managed object replication and delivery method to supply objects to
`
`parent and/or edge servers when requested. So, in these embodiments, the origin servers
`
`and parent servers communicate between each other and the origin servers and clients may
`
`also communicate between each other. In all of these embodiments, the communications
`
`relationships between origin servers and parent servers may be one-to-one, one-to-many or
`
`many-to-many.
`
`[0022]
`
`Further, as shown in FIG. 1, the parent servers and edge servers
`
`communicate between each other, edge servers and clients communicate between each
`
`other and parent servers and clients communicate between each other. While in
`
`embodiments, as shown in FIG. 1, the edge servers have a one-to-one or one-to-many
`
`communications relationship with parent servers, edge servers may also have many-to(cid:173)
`
`many communications relationships with parent servers. As discussed in more detail
`
`below, the edge servers act as the primary source of serving objects but if a requested
`
`object is not available at the edge server a parent server that has the requested object will
`
`7
`
`-7-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`serve the requested object to the clients. Also, FIG. 1 shows a single layer or level of
`
`parent servers and origin servers. As will be apparent to those skilled in the art, more than
`
`one layer or level of parent servers and/or origin servers may be used.
`
`[0023]
`
`According to embodiments of the invention and referring to FIGS. 2, 3(a),
`
`3(b) and 3(c), the method of managed object replication and delivery and the method of
`
`object purging is depicted. FIG. 2 depicts embodiments of the method in relation to a
`
`portion of the network 100, an origin server 110 and a client 140 as shown in FIG. 1.
`
`FIGS. 3(a), 3(b) and 3(c) depict embodiments of the method in flowchart form.
`
`[0024]
`
`Initially, the method of managed object replication and delivery directs (at
`
`200,300) a client, requesting one or more objects, to an edge server in the network,•
`
`whether or not the edge server has the requested object(s). Preferably, the client is directed
`
`to an optimal edge server, e.g., based on network traffic conditions and server load. As
`
`will be apparent to those skilled in the art, any number of currently known or future
`
`developed mechanisms may be used to select a best or optimal edge server. Determination
`
`of a best or optimal edge server preferably includes selection of an edge server most
`
`suitable for delivery of one or more objects to the client according to any number of
`
`currently known or future developed algorithms. For example, determination of a best or ,
`
`optimal edge server may be performed based on the likelihood of a copy of the requested
`
`object(s) being available at the candidate edge server, on the bandwidth between a
`
`candidate edge server and the client, on a best repeater selector (for example, as described
`
`in U.S. Patent No. 6,185,598) and/or on any number of other criteria.
`
`[0025]
`
`The selected best or optimal edge server 130 determines (at 305) whether
`
`the edge server already has the requested object and, if so, serves (at 205, 310) the object
`
`8
`
`-8-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`to the requesting client 140. For example, the selected edge server 130 will check its
`
`storage to determine whether the requested object is available and if so, may serve the
`
`object to the requesting client 140.
`
`[0026]
`
`If the selected edge server does not have the requested object, a check is
`
`initiated (at 315) for the edge server to determine whether the requested object is popular
`
`and if so, to replicate the popular requested object to the edge server. In embodiments, the
`
`method depicted in FIG. 3(b) and discussed in more detail below is employed to determine
`
`whether the requested object is popular and if so, to replicate the popular requested object
`
`to the edge server.
`
`[0027]
`
`In embodiments, the checking of whether the requested object is popular
`
`and replicating the popular requested object to the edge server may be performed
`
`independently of one or more functions of the method of managed object replication and
`
`delivery, such as the checking if a server has the requested object and serving the
`
`requested object to the client if the server has the requested object or redirecting the client
`
`to a server that has the requested object (and serving the requested object to the client).
`
`Thus, in embodiments, the checking of whether the requested object is popular and
`
`replicating the popular object to the edge server may be performed in parallel with or
`
`before the performance of certain functions of the method of managed object replication
`
`and delivery such as the checking if a server has the requested object and serving the
`
`requested object to the client if the server has the requested object or redirecting the client
`
`to a server that has the requested object (and serving the requested object to the client).
`
`Advantageously, should the checking, redirecting and serving of the requested object fail,
`
`the checking of whether the requested object is popular and replicating the popular object
`
`9
`
`-9-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`to the edge server can manage the continued delivery of objects to clients from edge
`
`servers. Similarly, if the checking of whether the requested object is popular and
`
`replicating the popular object to the edge server should fail, the checking, redirecting and
`
`serving of the requested object can manage the continued delivery of objects from servers
`
`in the network.
`
`[0028]
`
`Further, if the selected edge server does not have the requested object, the
`
`selected edge server directs (at 210,320) the requesting client 140 to a parent server 120.
`
`Preferably the client 140 is redirected to a parent server that has the requested object and is
`
`able to serve (at 215, 345) the requested object to the client. If a parent server does not
`
`have (at 325) the requested object, a check is initiated (at 330) for the parent server to
`
`determine whether the requested object is popular and if so, to replicate the popular
`
`requested object to the parent server. In embodiments, the·method depicted in FIG. 3(b)
`
`and discussed in more detail below is employed to determine whether the requested object
`
`is popular and if so, to replicate the popular requested object to the parent server. As with
`
`the check for the edge server, in embodiments, the checking of whether the requested
`
`object is popular and replicating the popular requested object to the parent server is
`
`performed independently of one or more functions of the method of managed object
`
`replication and delivery such as the checking if a server has the requested object and
`
`serving the requested object to the client if the server has the requested object or
`
`redirecting the client to a server that has the requested object (and serving the requested
`
`object to the client). Thus, in embodiments, the checking of whether the requested object
`
`is popular and replicating the popular requested object to the parent server may be
`
`performed in parallel with or before one or more functions of the method of managed
`
`object replication and delivery such as the checking if a server has the requested object
`
`10
`
`-10-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`and serving the requested object to the client if the server has the requested object or
`
`redirecting the client to a server that has the requested object (and serving the requested
`
`object to the client).
`
`[0029]
`
`Further, if a parent server does not have the requested object, the parent
`
`server could itself use a redirection technique recursively (at 325, 335, 320) until a final
`
`parent server is reached that has the requested object. The parent server that has the
`
`requested object serves (at 215,345) the object to the client. If the object is.determined to
`
`be unavailable (at 335) (from all parent servers), an error message is returned (at 340)
`
`regarding the unavailability of the requested object.
`
`[0030]
`
`As will be apparent to those skilled in the art, numerous methods are
`
`available to redirect a requesting client to another parent server, depending on the
`
`protocol(s) used to request the object. A handling edge server may request information
`
`from a database about to which parent server the client should be redirected. In an
`
`implementation, the edge server might have a local database, populated by pushes of
`
`redirection data from one or more servers in the network. The edge server may also simply
`
`query one or more servers in the network to identify one or more parent servers to which
`
`the client can be directed. When more than one parent server responds, the edge server
`
`may redirect the client to the parent ~erver that responds to the query first, the edge server
`
`may redirect the client to the parent server that is topologically closest to the edge server
`
`in the network or the edge server may redirect the client to the parent server that represents
`
`the best or optimal candidate based on criteria such as network efficiency, bandwidth
`
`requirement and/or cost. Alternatively, an edge server may always go to default parent
`
`servers. Or, as discussed in relation to edge servers, a best or optimal parent server may be
`
`11
`
`-11-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`determined using any of the techniques outlined above. Redirection may be performed by
`
`simply sending the request onto a parent server or returning redirection information to the
`
`client for accessing the parent server. As will be apparent to those skilled in the art, any
`
`number of implementations may be used to provide the redirection information to the
`
`handling edge server.
`
`[0031)
`
`In other embodiments, where the parent servers collectively are not
`
`populated with all of the objects and the network has access to the origin server of a
`
`requested object, the client may be redirected (at 225, 320) to the origin server if the
`
`requested object is not available on the parent servers. If the origin server has the
`
`requested object (at 325), the origin server would serve (at 230, 345) the object directly to
`
`the client (not shown in FIG. 1). Otherwise if the object is unavailable (at 335), an error
`
`message would be returned (at 340) regarding the unavailability of the requested object.
`
`[0032)
`
`Referring to FIG. 3(b), when an edge and/or parent server determines (at
`
`350) that a requested object is popular (by some measure of popularity) but the edge
`
`and/or parent server does not have a copy of the object, the edge and/or parent server
`
`initiates a pull of the object to the edge and/or parent server. So, for example, when the
`
`edge server determines (at 350) that a requested object is popular but the edge server does
`
`not have a copy of the requested object, the edge server initiates the replicating (at 220,
`
`360) of the popular requested object to the edge server from a parent server that has the
`
`requested object. Similarly, for example, when a parent server 120 determines (at 350) that
`
`a requested object is popular but the parent server does not have a copy of the requested
`
`object, the parent server initiates the replicating (at 240, 360) of the popular requested
`
`object to the parent server from an origin server that has the requested object.
`
`12
`
`-12-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`Alternatively, a parent and/or origin server may receive informationregarding object
`
`popularity, such as popularity determinations for objects or data about object popularity,
`
`from one or more edge and/or parent servers and may push popular objects to the edge
`
`and/or parent servers. So, for example, when the parent server determines (at 350) that a
`
`requested object is popular at an edge server but the edge server does not have a copy of
`
`the requested object, the parent server may initiate the replicating (at 220, 360) of the
`
`popular requested object to the edge server from the parent server. Similarly, for example,
`
`when the origin server determines (at 350) that a requested object is popular at a parent
`
`server but the parent server does not have a copy of the requested object, the origin server
`
`initiates the replicating (at 240, 360) of the popular requested object to the parent server
`
`from the origin server.
`
`[0033]
`
`In some embodiments, if none of the parent servers has the requested
`
`object, the edge server initiates the replication (at 235, 360) of the popular requested
`
`object to the edge server from the origin server having the requested object (if the network
`
`has access to the origin server). Preferably, in each case, the replicated object is not served
`
`or further replicated until the object has been completely copied to the respective server.
`
`Optionally, such replicating may be utilized by and between the parent servers themselves
`
`to facilitate the reduction of the traffic to and from the origin server. Further, if the edge
`
`and/or parent server does not have adequate space for the popular requested object, one or
`
`more objects may be purged (at 355) from the edge and/or parent server to make space for
`
`the popular object. In embodiments, the method depicted in FIG. 3(c) and discussed in
`
`more detail below is employed to determine whether any object(s) in the edge and/or
`
`parent server is no longer popular and if so, to delete the no longer popular object(s) from
`
`the edge and/or parent server. Also, as will apparent to those skilled in the art, servers
`
`13
`
`-13-
`
`

`

`WO 03/069437
`
`PCT /0S03/04108
`
`other than the edge and/or parent server for which an object is determined popular may
`
`perform the actual determination of whether an object is popular by using for example,
`
`popularity information provided by the handling edge and/or parent server. The popularity
`
`determinations can then be used to initiate replication (for example, pushing or pulling) of
`
`the object to the edge and/or parent server for the which the object is determined popular.
`
`\
`
`[0034]
`
`Referring to FIG. 3(c), if an object in a server's storage is no longer popular
`
`(at 365), the server may delete the object (at 370) from the storage. For example, an edge
`
`server may delete (at 245, 370) any objects from the edge server's storage that are no
`
`longer popular. Similarly, a parent server may delete (at 250, 370) any objects from the
`
`parent server's storage that are no longer popular. As will be apparent to those skilled in
`
`the art, the determining of wh