GB2395408A - Bandwidth allocation in a unicast/multicast system - Google Patents

Abstract

Bandwidth allocation is used when providing unicast and multicast content to users. Content subject to an a-priori contractual arrangement with a content provider is given the highest priority. The next highest priority is given to unicast and remaining bandwidth is allocated to multicast. Multicast communities may be created or eliminated in response to an increase or decrease, respectively, in common user interests or requests.

Description

GB 2395408 A continuation (74) Agent and/or Address for Service: Marks &

Clerk Clifford's Inn, Fetter Lane, LONDON, EC4A 1BZ, United Kingdom

- '9 2395408

UNICAST/MULTICAST ARCHITECTURE

FIELD OP THE INVENTION

The present invention relates generally to systems and methodologies for 5 providing content to users via electronic media BACKGROUND OP TO fNVON

The following patents and other publications are believed to represent the current state of the art: 0 US Patent Application 09/283,598 of Kipois et al, filed 1 April 1999, and corresponding published UK Patent Application 2,351,891, US Patent Application 09/285,214 of Richardson et al, filed 1 April 1999, and corresponding published UK Patent Application 2,348,530, a product called SQUID WEB PROXY CACHE, described at World 5 Wide Web site www.squid.org, an article by Steve Epstein et al, entitled "Macro and MIcro Scheduling", published in NDS Technical Disclosure Bulked, voL 1, number 1, September 1999, at

pages 6 - 8; and the following RFC documents, available at World Wide Web site so www.ieff.org: 1. REC 1945, enticed "Hypertext Transfer Protocol HITPI1.0", dated May 1996.

2. RFC 2186, entitled "Idternet Cache Protocol aCP), version 2", dated September 1997.

3. REC 2187, entitled "Application of Internet Cache Protocol (ICP), version 2", dated September 1997.

The disclosures of all references mentioned above and tbroughout the

present specification are hereby incorporated herein by reference.

so SUMMARY OF low 4VEN=ON

The present m vention seeks to provide improved systems and methodologies for providing content to users via elecomc media

There is thus provided in accordance with a preferred embodiment of the present invention a system for providing content to users including a multicast sub-system providing content to multiple users and a unicast sub-system providing content to individual users. The multicast subsystem is operative to push to each of a s plurality of user communities, content relating to the community and the umcast suh-system being,r open He +.o p.or.de o n de,llal,d to a user, curiieii w:iicn has not been previously pushed to the user.

There is also provided in accordance with another preferred embodiment of the present invention a method for providing content to users. The method includes lo steps of multicasting content to multiple users and unicasg content to individual users. The step of multicasting includes pushing to each of a plurality of user communities, content relating to the cornnunity and the step of includes providing on demand to user, content which has not been previously pushed to the user.

There is also provided in accordance with a preferred embodiment of the 5 present invention a system for providing content to user including a multicast sub-system providing content to multiple users and is operative to push to each of a plurality of user communities, content relating to the cornrnnnity and a bandwidth allocator operative to allocate bandwidth used by the multicast sub-system among the plurality of user communities.

20 There is fierier provided in accordance with a preferred embodiment of the present invention a system for providing content to users including at least one multicast sub-system providing content to multiple users, at least one miscast sub-system providing content to individual users and a bandwidth allocator operative to allocate bandwidth among the- at least one multicast sub-system and the at least one 95 unicast sub-system.

There is provided in accordance with another preferred embodiment of the present invention a system for providing content to users including a multicast subsystem providing content to multiple users and being operative to push to each of a plurality of user commnnides, content relating to the commumty based on at least 30 a-priori determinations and current demand and a bandwidth allocator operative to allocate bandwidth used by the multicast sub-system among at least content based on a-priori determinations and content based on current derring

There is also provided in accordance with yet another preferred embodiment of the present invention a system for providing content to users mcIuding multicast means for providing content to multiple users and unicast means for providing content to individual users, the multicast means being operative to push each of a 5 plurality of user communities, content relating to the cormnunity and the unicast means being ope.h.re to provide on demand to a -u;sr, content which has not been previously pushed to the user.

There is fiercer provided in accordance with another preferred embodiment of the present invention a system for providing content to user including I o muiticast means providing content to multiple users and being operative to push to each of a plurality of user corornunities, content relating to the cornmuruty and bandwidth allocator means operative to allocate bandwidth used by the multicast means among the plurality of user comrnnties.

There is also provided in accordance with a further preferred 5 embodiment of the present invention a system for providing content to users including at least one rnulticast means for providing content to multiple users, at least one nrUcast means for providing content to individual users and bandwidth allocator means operative to allocate bandwidth among the at least one multicast means and the at least one unicast means.

20 There is further provided in accordance with yet another preferred embodiment of the present invention a system for providing content to users. The system includes multicast means for providing content to multiple users and being operative to push to each of a plurality of user comnnrudes, content relating to the community based on at least a priori determinations and current demand and a 2s bandwidth allocator operative to allocate bandwidth used by the multicast means among at least content based on a pnori detenmrmtions and content based on current demand.

There is also provided in accordance with yet another preferred embodiment of the present invention a system for providing unicast and multicast À content to uses any including bandwidth allocation means for providing a guaranteed 30 minimum level of unicast sernce to the extent required and whereas bandwidth remaining Tom the provision of the guaranteed mirnmuTr level of nmcast seance is

employed for multicast, the same broadcast network providing both unicast and multicast. There is further provided in accordance with a preferred embodunent of the present invention a system for providing unicast and multicast content to users and 5 including bandwidth allocation means for allocating highest priority to a-priori content and new Nighest prlorly to - and for aocanog remaking bandwidth to multicast.

Further in accordance with a preferred embodiment of the present invention the system also includes a plurality of satellites having at least one of the following functionalities: broadcast, multicast and unicaSt 10 Still furler in accordance with a preferred embodiment of Me present invention We system also includes at least one of cable networks, digital terrestrial networks, microwave networks, cellular networks and DSL networks. having at least one of Me following fimctionalities: broadcast, multicast and unicast.

Preferably, the unicast functionality is provided by facilities, which also 5 simultaneously provide broadcast and multicast finctionalities.

Additionally in accordance with a preferred embodiment of the present invention the broadcast includes transmission of content to all users within a geographical footprint of a broadcast, including trarission of content in a pay access regime. 20 Further in accordance with a preferred embodiment of the present invention the multicast includes transmission of content to all users we a community having a predefined common interest, within a geographical footprint of a broadcast.

Still furler in accordance with a preferred embodiment of the present invention the unicast includes transmission of content to an individual user based on a 25 request from that user.

Further in accordance with a preferred embodiment of the present invention at least one coordinating facility coordirmtes unicast functionality with at least one of broadcast and multicast functionalities, thereby to enable efficient and effective use of available resources in terms of transmission facilities and bandwidth 30 Preferably, the coordinating functionality provides at least one of the following ctionalities: shifting between casg and multicasdng, bandwidth

allocation within multicast communities and bandwidth allocation between unicast, multicast and a priori broadcast or multicast content.

Additionally or alternatively the coordinating functionality is operative to determine what content is sent in what mower at what time via which facilities to which 5users. Prelela'vly, uIle coordinating functionality is operative to create new multicast communities in response to an increase in common user interests and requests.

Further in accordance with a preferred embodiment of the present invention the one coordinating functionality is operative to eliminate multicast I ocommunities in response to a decrease in common user interests and requests.

Preferably, as a community grows, the amount of bandwidth allocated to that coTrununity increases. Additionally, as a community decreases in size, the amount Of bandwidth allocated to that community decreases.

Additionally or alternatively, there is defined a mirumum multicast 5threshold which is a relative threshold determined by relative demands for various available content.

Preferably, the system provides a guaranteed mmirnum level of unicast service to the extent required and wherein bandwidth renaming from the provision of the guaranteed rrnmum level of unicast service is employed for multicast, the same 20broadcast network providing both unicast and multicast Shll furler irt accordance win a preferred embodiment of the present invention the bandwidth not required for contractual unicast service is allocated to multicast, thereby reducing demand for contractual Miscast service and thus, over time, decreasing latency and providing enhanced service to customers.

95Additionally in accordance with a preferred embodiment of the present invention the bandwidth not required for contractual unicast service is allocated not only to multicast but also to better unicast service, in accordance with latency considerations.

Further in accordance with a preferred embodiment of the present invention the available bandwidth is allocated with the highest priority being given to 0a-priori content and the next highest priority bemg given to unicast the remaining bandwidth being employed for multicast

Preferably, the remaining bandwidth is allocated among cornnunities based at least partially on relative community size.

There is provided in accordance with another preferred embodiment of the present invention a method for providing content to user. The method includes the s steps of multicasting content to multiple users by pushing content relating to individual coll.ll,-u-e -mid ailocaung Dandwidin among iLe individual commuiihes.

There is also provided in accordance with a farther preferred embodiment of the present invention a method for providing content to users. The method includes the steps of multicasting content to multiple users, unicasting content to to individual users and allocating bandwidth between the multicasting and the unicasting. There is further provided in accordance with a preferred embodiment of the present invention a method for providing content to users. The method includes multicasting content to multiple users by pushing to each of a plurality or user commumbes, content relating to Me community based on at leant a pnori determinations and cement demand and allocating bandwidth among at least content based on a priori determinations and content based on current demand.

There is also provided in accordance with yet a further preferred embodiment of the present invention a method for providing urucast and multicast 20 content to users and including bandwidth allocation wherein bandwidth remaining from the provision of the guaranteed minimum level of umcast service is employed for multicast, the same broadcast network providing both miscast and multicast.

There is furler prodded accordance with yet another preferred embodiment of the present invention a method for providing nmcast and multicast 25 content to users. The method includes bandwidth allocation, allocating highest priority to a-prior content and next highest priority to unicast and for allocating remaining bandwidth to multicast.

Additionally in accordance with a preferred embodiment of the present invention the method also includes the broadcast of content to an users within a so geographical footpnut of a broadcast, including transmission of content a pay access regime.

Still farther m accordance with a preferred embodiment of the present invention the step of multicasting includes transmission of content to all users within a conunuzity having a Redefined common interest, within a geographical footprint of a broadcast. sFurther in accordance with a preferred embodiment of the present in.e".hic-. the step of Baaing Yn; luces transmission of content to an individual user based on a request from that user.

Moreover in accordance with a preferred embodiment of the present invention at least one coordinating facility coor&tes unicast functionality with at least oone of broadcast arid multicast functionalities, thereby to enable efficient and effective use of available resources in terms of transmission facilities and bandwidth.

Preferably, the coordinating functionality provides at}east one of the following functionalities: shifting between unicastirtg and multicasting, bandwidth allocation within multicast communities and bandwidth allocation between unicast, I multicast and a priori broadcast or multicast content.

Additionally or alternatively, the coordinating fincdonabty is operative to what content is sent in what manner at what time facilities to which users Further in accordance with a preferred embodiment of the present invention the coordinating functionality is operative to create new multicast gocommunities in response to an increase in common user interests and requests.

Additionally in accordance with a preferred embodiment of the present invention the coorrlirating functionality is operative to eliminate multicast communities in response to a decrease in common user interests and requests.

Further in accordance with a preferred embodiment of the present 5invention, as a community grows, the amount of bandwidth allocated to that community increases. Additionally or alternatively, as a community decreases in size, the amount of bandwidth allocated to that community decreases.

Still farther in accordance with a preferred embodiment of the present soinvention the method also includes the step of providing a guaranteed minimum level of unicast service to the extent required and wherem bandwidth remaining from the

provision of the guaranteed minimum level of unicast service is employed for multicast, the same broadcast network providing both unicast and multicast.

Further in accordance with a preferred embodiment of the present invention, the bandwidth not required for contractual unicast service is allocated to s multicast, thereby reducing demand for contractual unicast service and thus, over time, decreeing latency Ed pv-vi' -a rinuIiced service to customers.

Preferably, the bandwidth not required for contractual unicast service is allocated not only to multicast but also to better unicast service, in accordance with latency considerations.

0 Additionally or alternatively, the available bandwidth is allocated with the highest priority being given to a-priori content and the next highest priority being given to unicast, the remairung bandwidth employed being for multicast.

Preferably, the remaining bandwidth is allocated among communities based at least partially on relative community size.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will be understood and appreciated more Filly Mom the following detailed description, taken in conjunction with the drawings in

which: so Fig. 1 is a simplified and generalized pictorial illustration of an integrated multicast/nnicast system and methodology for providing content to users via electronic media Figs. 2A, 2B & 2C are illustrations of three typical operative states of an integrated nulticastlunicast system and methodology of the type shown in Fig. 1 95 illustrating shifts between unicasting and multicasting; Figs. 3A, 3B & 3C are illustrations of three typical operative states of an integrated multicastlnnicast system and methodology of the type shown in Fig. 1 illustrating bandwidth allocation among and within communizes; Figs. 4A, 4B & 4C are illustrations of three typical operative states of an so integrated multicast/unicast system and methodology of the type shown In Fig. I illustrating bandwidth allocation between unicast, multicast and a priori consort; Fig. 5A is a set of diagrams showing changes in bandwidth allocation

and latency over time in accordance with the prior art;

Fig. 5B is a set of diagrams showmO changes iTi bandwidth allocation and latency over time in accordance with one preferred embodiment of the present invention; sFig. SC is a set of diagrams showing changes in bandwidth allocation -id latency Over time in accordance with another preferred embodiment of the present invention; Fig. 6A is a diagram showing changes ire bandwidth allocation over time in accordance with the prior art;

oFig. 6B is a diagram showing changes m bandwidth allocation over time in accordance with one preferred embodiment of the present invention; Fig. 6C is a diagram showing changes in bandwidth allocation over time in accordance with another preferred embodiment of the present invert on; Fig. 6D is a diagram showing changes in bandwidth allocation over time 5in accordance with yet another preferred embodiment ofthe present invention, Fig. 6E is a diagram showing changes in bandwidth allocation over time in accordance with sell knower preferred embodiment of the present irveon; Figs. 7A, 7B and 7C are simplified fictional block diagrams illushadng three alternative functionalities of the system shown in Fig. 1; 20Figs. 8A and 8B are sunplified functional block diagrams illustag two alternative realizations of the functionality described in Figs. 3A - 3C and Fig. 7A, Figs. 9A11, 9A12, 9B/1 and 9B/2 are simplified flow diagrams corresponding respectively to the simplified fimctiollal block diagrams of [Pigs. 8A and 8B; 25Figs. lOA and lOB are sLmplified fimctional block diagrams illustrating two alternative realizations of the functionality described in Figs. 4A & 4B and Fig. 7B, Figs. 11A/1, 11A/2, llBI1 and llB/2 are simplified flow diagrams corresponding respectively to the simplified nchonal block diagrams of Figs. lOA and JOB; soFigs. 12A and 12B are simplified fimctional block diagrams illustrating two altezDadve realizations of the functionality described in Figs. 4C and Fig 7C, Figs. 13A11, 13A/2, 13B/1 and 13B/2 are simplified flow diagrams

corresponding respectively to the simplified functional block diagrams of Figs. 12A and 12B;, Fig. 14 is a simplified flowchart illustrating the operation of an algorithm for bandwidth allocation in an urucastmulticast environment, wherein unicast and s multicast do not share the same bandwidth; rig. 1 is a simpered flowchart illustrating the operation of an algorithm for bandwidth allocation in a unicast-multicast environment, wherein unicast and multicast do share the same bandwidth, and Fig. 16 is a simplified flowchart illustrating the operation of an algorithm lo for bandwidth allocation in an unicast-multicast envronrnen:t, wherein unlcast, a priori multicast and triggered multicast share We same bandwidth i., DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS -

lleference is now made to Fig. 1, which is a sunplified and generalized is pictorial illustration of an integrated multicast/unicast system and methodology for providing content to users via electronic media As seen in Fig. 1 there is provided an integrated multicastfmicast system which typically includes a plurality of satellites 100 which have at least one and preferably all of the following futionaIities: broadcast, multicast and unicast.

So Broadcast, multicast and Outcast finctioralities may also be provided by cable, networks, digital terrestrial networks, microwave networks, cellular networks and DSL networks, as well as any other broadband facilities. Unicast functionality may additionally be provided by PSIN facilities.

It is appreciated that unicast functionality may or may not be provided by 25 facilities, which also simultaneously provide broadcast arid multicast functionalities.

Throughout, the following definitions are employed: BROADCAST transmission of content to all users within a geographical footprint of a broadcast, including anission of content in a pay access regime; 30 MULTICAST - transmission of content to all users within a commmuty having a predefined common interest, within a geographical footprint of a broadcast, UNICAST - transmission of content to an individual user based on a n

request from that user, including, for example, HTTP or FTP.

In accordance with a preferred embodiment of the present invention, orate or more coordinating facilities, symbolized by a block 102, coordinate the unicast functionality with at least one and preferably both of the broadcast and multicast 5 finctionalities, thereby to enable most efficient and effective use of available resources iDl terlilS OI Admission facilities and bandwidth. This coordination, as win be described hereinbelow in detail, may take the form of shifting between unicasting and multicasting and is described hereinbelow with respect to Figs. 2A, 2B and 2C, bandwidth allocation within multicast comrrunities, as described hereinbelow with lo respect to Figs. 3A, 3B and 3C, bandwidth allocation between unicast, multicast and a pnori broadcast or multicast content, other tradeoff and various combinations and subcombinations of the foregoing.

Coordinating facilities 102 preferably determine what content is sent in what manner at what time via which facilities to which users. For example, coordinating Is facilities 102 govern terrestrial Cast transmissions, symbolized by arrows 104, satellite unicast transmissions, symbolized by an arrow 106 and satellite broadcasts and multicasts symbolized by footprints 108.

Reference is now made to Figs. 2A, 2B 2C, which are illustrations of three typical operative states of err integrated multicastiunicast system and methodology 20 of the type shown in Fig. I illustrating shins between unicasdng and multcasting.

Fig. 2A shows multicast Mom a coordiDadug center 200 to a plurality of multicast communities, typically including a business multicast corurunity 202, a sports multicast community 204 and a youth multicast community 206. The symbolic n employed in Figs. 2A - 2C indicates the size of the community by the number of 25 individuals shown therewithin. Fig. 2A also shows a user 208 who receives science content via a rnicast and also a user 210, who is a member of the business multicast community 202, who also receives nature content via a unicast.

A comparison of Fig. 2B with Fig. 2A shows the creation of a new nature multicast community 212, which may overlap with another multicast cot unity, 30 such as the business multicast community 202, to indicate that a user may belong to multiple multicast communities simultaneously.

It is appreciated that new codes are created in response to an

increase in common user interests and requests. Thus, as symbolized by an additional user having nature interests in Fig. 2B, when the nlnT her of users expressing a common interest reaches an appropriate threshold, a new multicast community may be automatically created in accordance with the present invention.

5 Fig. 2C shows an opposite trend from that illustrated in Fig. 2B wherein due to a decree iri cuari user interests and requests, muncast commurnhes are eliminated. Thus, as symbolized by removal of a user previously having sports interests, designated by reference numeral 214 in Fig. 2C, causing the number of users expressing a common interest in sports to fall below an appropriate threshold, the sports to community 204 appeanog in Fig. 2A is auto_adcally elirrdT ated in accordance with the present invention as shown in Fig. 2C.

Reference is now marle to Figs. 3A, 3B & 3C, which are illustrations of . three typical operative states of an integrated mulucast/unicast system and methodology of the type shown in Fig. I illustrating bandwidth allocation among and within 5 commurnties. As seen in Figs. 3A and 3B, as a community grows, here indicated symbolically by the number of individuals located with a circle representing the community, the amount of bandwidth allocated to that community, here indicated symbolically by the radius of the circle, increases. Concomitantly, as a commmity so decreases in size, the amount of bandwidth allocated to that community decreases. An increase in the size of the community and thus in the bandwidth allocation thereto is exemplified by the youth comnuntty at the right of Figs. 3A and 3B. A decrease in the size of the community is exemplified by the business community at the left of Figs. 3A and 3B.

95 A comparison of Figs. 3B and 3C illustrates typical bandwidth allocation within a community. It is seen that a symbolic member of the community, indicated by reference numeral 302, who was receiving Disney in Fig. 3B, shins to Warner Bros. in Fig. 3C. This, when statistically significant, results in a reallocation of bandwidth between Disney and Warner Bros. in Fig. 3C. In this case, whereas Warner Bros. was so unicast in Fig. 3B to a symbolic member of the community, indicated by reference numeral 304, the increased demand for Warner Bros. Fig. 3C passes a mluimmn multicast threshold and causes Wamer Bros. to be multicast in Fig. 3C. Concomitantly,

the decreased demand for Disney causes Disney, which was multicast in Fig. 3B to be unicast to a symbolic member of the community 306 in Fig. 3C.

It is appreciated that the minimum multicast threshold is typically not an absolute threshold but rather a relative threshold determined by relative demands for s venous available content.

It is appreciated that in "Lhe embodiment of Figs. 3A - 3C unicast bandwidth is not provided by the broadcast network and does not employ its bandwidth.

Reference is now made to Figs. 4A, 4B & 4C, which are illustrations of three typical operative states of an integrated multicast/unicast system and methodology lo of the type shown in Fig. 1 illustrating bandwidth allocation between unicast, multicast and a pnori content. In the embodiment of Figs. 4A - 4C, as contrasted with that of Figs. 3A - 3C, there is provided a guaranteed mininQn level of unicast service to the extent required Bandwidth remaining from the provision of the guaranteed minimum level of unicast service is employed for multicast. It is assigned that the same broadcast network 5 provides both unicast and multicast, which is quite corer Tnon in cable and DSL service.

Considering Figs. 4A and 4B, it is seen that the amount of unicast demand decreases from Fig. 4A to Fig 4B. This increases the amount of bandwidth available for multicast As seen in Fig. 4B, typically the business community takes up this added bandwidth ir asmuch as Bloomberg, a business service, is now multicast.

90 In this context, reference is also marle to Fig. 5A, which shows dynamic allocation over tune of available bandwidth between contractual unicast service and better unicast service in accordance with the priorart It is seen that in the prior art,

generally the greater the percentage of contractual nmcast service, the greater the resulting latency. Thus better service, i.e. lower latency results from lowered dernaTds 95 for contractual unicast service.

ID accordance with the present invention, as exemplified by Fig. 5B, bandwidth not required for contractual Cast service is allocated to multicast, as described hereinabove with reference to Figs. 4A and 4B. The av;1nhiIity of multicast service reduces the demand for contractual unicast service and thus, over time, the so latency decreases, providing enhanced service to customers. It is noted particularly that the availability of multicast service inherently reduces latency since content is pushed to and cached at the customer and thus can be retrieved instantaneously.

] Fig. 5C illustrates a further enhancement of the nvention described hereinabove with reference to Figs. 4A and 4B. In Fig. SC, bandwidth left over Tom contractual unicast service is allocated not only to mudticast but also, in certain cases to better unicast service. Typically a detemmation whether to allocate the left over 5 bandwidth to multicast or to better unicast service is made based on exceedance of a min=l'Uml 1mUlLiC=i ^mreshoid, which is preferably absolute but may be determined by relative demands for content.

It is appreciated that the scenario of Fig. SC is typically one wherein there is available sufficient bandwidth for all required content and the allocation of the lo remaining bandwidth is made purely or principally based on latency considerations, predicated on the understanding Mat lower latency is translated into increased customer satisfaction. It may thus be appreciated from a comparison of the latency shown in.

Figs. 5B and 5C, that the enhancement of Fig. SC produces an overall decrease in 5 latency overtime.

Fig. 4C shows a somewhat more complex situation them that shown in Fig. 4A, wherein there also exists an a-priori commitment to broadcast or multicast a certain amount of content determined by a contractual arrangement with a content provider. In such a case We available bandwidth is allocated with Me highest priority 20 being given to the a- priori content and the next highest priority being given to miscast The remaining bandwidth is employed for multicast and is allocated among and within communizes typically in a roanner similar to that described hereinabove with reference to Figs. lA- 3C.

In this context, reference is also made to Fig. 6A, which shows dynamic 95 allocation over time of available bandwidth between a priors broadcast or multicast, typically including EPG (Electronic Program Guide), contractual unicast service and better unicast service in accordance with the prior art.

Fig. 6B shows dynamic allocation over time of available bandwidth between a pnori broadcast or muldcast, typically including EPG (Electronic Program 30 Guide), contractual unicast service and multicast on demand in accordance with Me present invention.

Fig. 6C shows dynamic allocation over time of available bandwidth

between a priori broadcast or multicast, typically including EPG (Electronic Program Guide), contractual unicast service, better unicast service and multicast on demand in accordance with the present invention.

Fig. 6D shows dynamic allocation over time of available bandwidth s between a priori broadcast or multicast, which is now divided into required content and nice to -me cuniez:ri and typically includes EPG (Electronic Program Guide), contractual unicast service, better unicast service and multicast on demand in accordance with the present invention.

Fig. 6E shows dynamic allocation over time of available bandwidth o between a priori broadcast or muIticast, which is row divided into required content and nuce to have content and typically includes EPG (Electronic Program Guide), contractual unicast service, better unicast service and multicast on demand in accordance with the present invention. The difference between Fig. 6E and Fig. 6D is the allocation to multicast of some of the bandwidth, which is used for nice to have I s content.

Reference is now made to Figs. 7A, 7B and 7C, which are simplified functional block diagrams illustrating three alternative functionatities of the system shown in Fig. 1 employing asymmetric networks including nonbalanced forward and rehire paths, wherein the forVvard path has substantially greater bandwidth than the 20 return path Fig. 7A provides functionality suitable for use in the systems shown in Figs. 3A - 36. Fig. 7B provides functionality suitable for use in the system shown in Figs. 4A &; 4B and Fig. 7C provides functionality suitable for use in the system shown in Fig. 4C.

95 As seen in Fig. 7A, typically first and second end users 702 and 704 are enabled to surf the Internet using a conventional PSTN network 706, which defies a two-way return path. In the course of surfing the Internet, one or more of the end users may communicate with a web server 708, which may be a conventional web server.

In accordance with a preferred embodiment of the present invention, the 3Q web server 708 may cause a multicast delivery server 710 to srnit web content via a bandwidth allocator 712, which typically includes bandwidth allocation decision finctionali, a multiplexer and a modulator. Bandwidth allocator 712 preferably

transmits content received Dom multicast delivery server 710 via a broadband forward path 714, typically including one or more satellites 716 to the first and second end users 702 and 704, to the extent of available allocated bandwidth of the one or more satellites 716. Additionally or alternatively bandwidth allocator 712 may transmit over any 5 suitable forward pate, including a broadcast network such as a cable network 717, a digits' tel=uLnu-rietwurx 7i9 or an AWL network (not shown).

Referring now to Fig. 7B, it is seen that typically first and second end users 722 and 724 are enabled to surf the Interpret via a forward path and a return path The return path, is a one-way, typically out of band, return path via an asymmetric I o network, such as a VSAT network, a DOCSIS cable network or an ADSL network. The forward path employs the same network that is used for the return path, in disduction to the structure of Fig. 7\ In the embodiment of Fig. 7B, the end users 722 and 724 query over the one-way return path indicated by arrows 726 via a one- way return path hub 728, such as s a conventional VSAT hub, a CMTS or a DSLAM. In the course of surfing the Internet, one or more of Me end users may communicate with a web server 730, which may be a conventional web server.

In accordance with a preferred embodiment of the present invention, the web server 730 may cause a multicast delivery server 732 to trart web content via a 20 bandwidth allocator 734, which typically includes bandwidth allocation decision functionality, a multiplexer and a modulator. Bandwidth allocator 734 preferably transmits content received from muldcast delivery server 732 via a broadband forward path 733, typically including one or more satellites 736 to the ilrit and second end users 722 and 724, to the extent of available allocated bandwidth of the one or more satellites 25 736. Additionally or alternatively bandwidth allocator 734 may transit over any suitable forward path, including a broadcast network such as a cable network 737, a digital terrestrial network 739 or an ADSL network (not shown).

Referring now to Fig. 7C, it is seen that typically first and second end users 752 and 754 are enabled to surf the Interpret via a forward path and a return paw so The rem path, is a one-way, typically out of band, return path via an asymmetric network such as a VSAT network a DOCSIS cable network or an ADSL network. The forward path employs the same network that is used for the return partly in disduction to

the structure of Fig. 7A.

In the embodiment of Fig. 7C, the end users 752 and 754 query over the one-way return path indicated by arrows 756 via a one-way return path hub 758, such as a conventional VSAT hub, a CMTS or a DSLAM. In the course of surfing the Internet, s one or more of the end users may communicate with a web server 760, which may be a conven.;on web server.

In accordance with a preferred embodiment of the present invention, the web server 760 may cause a multicast delivery server 762 to transmit web content via a bandwidth allocator 764, which typically includes bandwidth allocation decision o functionality, a multiplexer and a modulator.

The bandwidth allocator 764 may also concurrently receive content via an a-priori broadcaster server 765 from one or more content providers 766. Bandwidth allocator 764 preferably transmits content received Mom multicast delivery server 762 and a-priori broadcast server 765 via a broadband forward path 767, typically including 5 one or more satellites 768 to the first and second end users 752 and 754, to the extent of available allocated bandwidth of the one or more satellites 768.

Additionally or alternatively bandwidth allocator 764 may transmit over any suitable forward path, including a broadcast network such as a cable network 769, a digital terrestrial network 770 or an ADSL network (not shown).

20 It is appreciated that essential differences between the structures shown in Figs. 7A, 7B and 7C appear in bandwidth allocation decisions. In the embodiment of Fig. 7A, the bandwidth is allocated among various multicast transmissions. In the embodiment of Fig. 7B, the bandwidth is allocated not only between various multicast transmissions but also between various unicast content transmissions. In the 75 embodiment of Fig. 7C, the bandwidth is allocated additionally among a-priori broadcasts. Reference is now made to Figs. 8A and 8B, which are simplified functional block diagrams illustrating two alternative realizations of the functionality described in Figs. 3A - 3C. Refernug initially to Fig. 8A, typically two end-user clients 30 800 and 802 are shown, it being understood that a multiplicity of such end-user clients employ the system. Each of the end user clients 800 and 802 preferably includes a browser 804 who communicates with a plug-in profiler 806 and with a standard web

cache 808.

The standard web cache 808 may be a standard cache such as all MI(::ROSOFT INTERNET EXPLORER cache or alternatively may be an external proxy cache such as an APACHE proxy cache.

5 The combination of browser 804 and cache 808 is employed for nn'enti on a!..,eb s lo AAA5. her all. lee us 0 sir 8 04 ^1^^ cA fly cnec as cache us for - requested IJRLs and only queries a web server, such as the community web server 818, when the requested URL is not in cache or out of date.

Plug-in profiler 806 stores historical surfing information relating to pages 0 requested by the browser 804. Profiler 806 communicates with a community creation server 810 at predetermined times or at times responsive to various possible criteria The cormounity creation server 810 preferably communicates with all erAd-user client filers 806. Co. nunity creation server 810 preferably analyzes the client profiles and, on the basis of this analysis, dynamically creates, modifies and Reconstructs 5 cornrAunit;^es. The community creation server 810 preferably outputs to a cornmity set-up manager 812, which configures the venous end uses in accordance with community creation/modificatior/deconstruction instructions received Mom server 810.

Community set-up manager 812 also interfaces with a bandwidth allocator 814 in order 20 to enable the bandwidth allocator 814 to malice appropriate bandwidth allocation determinations. Communitr set-up Sager 812 also mterces with a unicast/multicast decision switch 816, which is operative to send content by unicast, until the simultaneous demand for such content justifies sending the content by multicast.

95 Unicast/multicast decision switch 816 is preferably incorporated into a community web server 818.

In accordance with a preferred embodiment of the present invention, each community is served by a single community web server 818 and associated unicast/muldcast decision switch 816.

30 When and so long as simultaneous declared for a given web page exceeds a given threshold, unicast/multicast switch 816 triggem bandwidth allocator 814 to allocate multicast forward path bandwidth for multicast of that web page. Bandwidth

allocator 814 may employ a dynamic pre-emptive queue of URLs for such allocation.

In practice, the bandwidth allocator 814 may be responsive to the amount of available bandwidth for dynamically changing the threshold of switch 816.

Bandwidth allocator 814 also interfaces with a multicast set-up manager 5 820 which in turn interfaces with a multicast announcement server 822 and a multicast delivery server 8;4. -lye multicast announcement server 822 is operative to announce to all end users in a given community the estimated time and address of upcoming multicasts. The multicast delivery server 824 is operative to deliver the multicasts to the cache 808, of each end user client 802 associated with the given corrmuruty.

0 - Referring now to Fig. 8B, it is appreciated that whereas in the embodiment of Fig. 8A, each community is served by a centralized community web server 818, the embodiment of Fig. 8B, a generic web server facility 850, inclcling one or more servers which may be at disparate locations, is employed to serve multiple communities. In this embodiment the generic web server facility 850 communicates 5 with end users without regard to the communities to which they belong. Therefore, in the embodiment of Fig. 8B, a bandwidth allocator 854 is preferably co-located with a urucastlmulticast decision switch 856.

In the embodiment of Fig. 8B, a community set-up manager 852 interfaces with the unicast/multicast decision switch 856, here incorporated with to bandwidth allocator 854, and need not interface with the generic web server 850.

Preferably, in the embodiment of Fig. 8B, decisions as to which content to multicast or unicast and as to the amount of bandwidth to allocate to the venous muliticasts are maple by the co-located unicast/multicast decision switch 856 and bandwidth allocator 854.

Therefore, the generic web sewer facility 850 is required to continually update the 95 unicast/multicast decision switch 856 as to all web pages queried and as to the community identification thereof.

The remainder of Be embodiment of Fig. 8B is identical to that of Fig. 8A. Identical elements are identified in Fig. 8B by tub same reference numerals employed in Fig. 8A.

so The embodiment of Fig. 8B has an advantage over the embodunent of Fig. 8A in that in Fig. 8B, the web servers are generic and distributed among the venous communities. A disadvantage of the embodiment of Fig. 8B re} adve to the embodiment

of Fig. 8A is that greatly enhanced tragic is generated between generic web server facility 850 and the unicast/multicast decision switch 856.

Reference is now made to Figs. 9A and 9B, which are simplified flow diagrams corresponding respectively to the simplified fimctional block diagrams of 5 Figs. 8A and 8B.

Turning to Fig. PA, i: seen that along a time scale from the top of Fig. 9A to the bottom thereof, initially users conduct browsing using browser 804 prior to Connation of any community. Eventually, due to action of the profiler 806, a community IS formed by community set-up manager 812 in response to a trigger from community lo creation server 810.

Following formation of a community, when end users who are members of the coranunity engage in browsing, using browser 804, and when the demand among members of the community for a given web page exceeds a threshold established by.: unicast/multicast decision switch 816 of the community web server 818' the content of t-

s the given web page is multicast to the entire commmity subject to bandwidth availability constraints.

Following the multicast, end users office community can access the content of the given web page Mom their local cache with nearly zero latency.

Refemng now to Fig. 9B, it is seen that the states of the functionality So may be identical to those shown in Fig. 9A. A principal deference is in that whereas in the embodunent of Fig. 9A, the threshold is established by unicastlmulticast decision switch 816 of the comnunity web server 818, in the embodiment of Fig. SIB, the threshold is established by the urucast/multicast decision switch 856 co-located with the bandwidth allocator 854.

95 Reference is now made to Figs. 10A and lOB, which are simplified fimctional block diagrams illustrating two alternative realizations of We fimctionalitY described Figs. 4A & 4B and Fig. 7B, and to Figs. 11A and 11B are sunplified flow diagram corresponding respectively to the simplified fimctional block diagrams of Figs. 1 OA and 1 OB.

0 Refemug in tinily to Fig. lOA, typically two end-user clients 1000 and 1002 are shown, it being underwood that a multiplicity of such end-user clients employ the system. Each of the end user clients 1000 and 1002 preferably includes a browser

1004, which communicates with a plug-in profiler 1006 and with a standard web cache 1008. The standard web cache 1008 may be a standard cache such as an MICROSOFT INTERNET EXPLORER cache or alternatively may be an external 5 proxy cache such as an APACHE proxy cache.

T,h.e ccmb:at.cn of uru-ws iu0 and cache lUU8 is employed for conventional web surdug wherein the browser 1004 initially checks cache 1008 for requested URLs and only queries a web server, such as the cornmurrity web server 1018, when the requested URL is not in cache or out of date.

0Plug-m profiler 1006 stores historical surfing information relating to pages requested by the browser 1004. Profiler 1006 conucates with a community creation server 1010 at predetnined times or at times responsive to venous possible criteria. The comnuni creation server 1010 preferably commnrucates with all 15end-user client profilers 1006. Cornrr unity creation server 1010 preferably analyzes the client profiles and, on the basis of this analysis, dynamically creates, modifies and deconsbructs communities.

The community creation server 1010 preferably outputs to a community setup manager 1012, which configures the various end users in accordance with to community creation/modification/deconstrction instructions received Mom server 1010. Community set-up manager 1012 also interfaces with abadwidth allocator 1014 in order to enable the bandwidth allocator 1014 to malce appropriate bandwidth allocation determinations.

Cornnunity set-up manager 1012 also interfaces with a unicast/multicast Is decision switch 1016, which is operative to send content by Precast' until the simultaneous demand for such content justifies sending the content by multicast Unicast/multicast decision switch 1016 is preferably incorporated unto a community web server 1018.

In accordance with a preferred embodiment of the present invention, 30 each community is served by a single coTnunity web server 1018 and associated unicast/multicast decision switch 1016.

When and so long as simultaneous demand for a given web page exceeds

a Even threshold, unicast/multicast switch 1016 triggers bandwidth allocator 1014 to allocate multicast forward path bandwidth for multicast of that web page. Bandwidth allocator 1014 may employ a dynamic preemptive queue of URLs for such allocation.

In practice, the bandwidth allocator 1014 may be responsive to the 5 amount of available bandwidth for dynTrucally changing the threshold of switch 1016.

T. cot;-t to ARC Cal.uod,u,i uirigs. 8A - 9B, here au Cast Traffic is forwarded over the broadcast forward path from web server 1018 to cache 1008.

Bandwidth allocator 1014 takes into account both unicast and multicast traffic in allocating the available bandwidth of the forward path. Bandwidth allocator 1014 10 essentially makes two different types of decisions: allocation between unmask and multicast and allocation of the multicast bandwidth among communities and URLs. It is appreciated that the bandwidth allocation is performed by a logical entity, which may be embodied m one or more physically distributed network elements, such as routers.

Bandwidth allocator 1014 additionally interfaces with a multicast set-up 15 manager 1020 which in turn interfaces with a multicast announcement server 1022 and a multicast delivery server 1024. The multicast announcement server 1022 is operative to announce to all end users in a Even community the estimated time and address of upcoming multicasts. The multicast delivery server 1024 LS operative to deliver the multicasts to the cache 1008, of each end user client 1002 associated with the given 20 community.

Refemng now to Fig. lOB, it is appreciated Cat whereas in the embodiment of Fig. 10A, each community is served by a centralized community web server 1018, in the embodiment of Fig. 10B, a generic web server facility lOSO, including one or more servers which may be at disparate locations, is employed to serve 25 multiple cornnunities. In this embodiment the generic web server facility 1050 communicates with end users without regard to the comnmTties to which they belong.

Therefore, in the embodiment of Fig. lOB, a bandwidth allocator 1054 is preferabI co-located with a unicast/multicast decision switch 1056.

In the embodiment of Fig. 10B, a comity set-up manager 1052 so interfaces with the unicast/multicast decision switch 1056, here incorporated win bandwidth allocator 1054, and need not interface with the generic web server 1050.

Preferably, in the embodiment of Fig. 1 OB, decisions as to which content to multicast or

u3ncast and as to the amount of bandwidth to allocate to the various multicasts are made by the co-located ucastlmulticast decision switch 1056 and bandwidth allocator 1054; Therefore, Be generic web server facility 1050 is required to continually update the unicast/multicast decision switch 1056 as to all web pages queried and as to the 5 community identification thereof.

The He-Ides Of 'e emwrumen of Fig. 1UB is identical to that of Fig. lOA. Identical elements are identified in Fig. lOB by the same reference nurrerals employedin rig. lOA.

The embodiment of Fig. 10B has an advantage over the embodiment of lo Fig. lOA Mat in Fig. 10B, the web servers are generic and distributed among the various cornmuties. A disadvantage of the embodiment of Fig. 10B relative to the embodiment of Fig. lOA is that greatly enhanced traffic is generated between generic web server facility 1050 and the unicast/multicast decision switch 1056.

Reference is now specifically made to Figs. 11A and 11B, which are is simplified flow diagrams corresponding respectively to the simplified functional block diagrams of Figs. lOA and lOB.

Turning to Fig. 1 IA, it sem that along a tune scale from the top of Fig. I IA to the bottom thereof, initially users conduct browsing using browser 1004 prior to fonnabon of any community. Eventually, due to action of the profiler 1006, a So community is formed by community set-up manager 1012 in response to a trigger from community creation server 1010.

Following formation of a community, when end users who are members of the community engage in browsing, using browser 1004, and when the defined among members of the community for a given web page exceeds a threshold established 25 by unicast/multicast decision switch 1016 of the community web server 1018, the content of the given web page is multicast to the entire community subject to bandwidth availability constraints.

Following the multict, end users of the cornunity can access the content of the given web page from their local cache with nearly zero latency.

30 It is noted that in contrast to the embodiment of Fig. 9A, in the embodiment of Fig. 11A during both preomnunity forrnaidon browsing and postommunity Connation browsing, the community web server 1018 requests forward

path bandwidth Mom bandwidth allocator 1014.

Referring now to Fig. I 1B, it Is seen that the states of the functionality may be identical to those shown in Fig. l lA. A principal difference is in that whereas in the embodiment of Fig. l lA, the threshold is established by unicast/multicast decision s switch 1016 of the community web server 1018, in the embodiment of Fig. IlB, the t'rshc7d is euqlished by 4'-- c^u'-='uc-. ucci Rich iO56, co-located wim the bandwidth allocator 1054.

Reference is now made to Figs. 12A and 12B, which are simplified linctional block diagrams ilIusadug two alternative realons of the functionality lo described in Figs. 4C, 6B - 6E and 7C and also to Figs. 13A and 13B, which are simplified flow diagrams corresponding respectively to the simplified functional block diagrams of Figs. 12A and 12B.

Refemag initially to Fig. 12A, typically two end-user clients 1200 and 1202 are shown, it being understood that a multiplicity of such end-user clients employ ' 5 the system. Each of the end user clients 1200 and 1202 preferably includes a browser 1204 which communicates with a plug-in profiler 1206 and with a standard web cache 1208. The. - ndard web cache 1208 may be a standard cache such as an MICROSOFT BERNET EXPLORER cache or alternatively may be an external 20 proxy cache such as an APACHE proxy cache.

The combination of browser 1204 and cache 1208 is employed for conventional web surfing wherem the browser 1204 initially checks cache 1208 for requested URLs and only queries a web server, such as the community web server 1218, when the requested URL is not In cache or out of date.

25 Plug-in profiler 1206 stores historical surfing information relating to pages requested by the browser 1204. Profiler 1206 communicates with a community creation server 1210 at predetermined tunes or at tunes responsive to various possible criteria The community creation server 1210 preferably communicates with Al 30 end-user client profilers 1206. Community creation server 1210 preferably analyzes the client profiles and, on the basis of this analysis, dynamically creates, modifies anr1 deconshacts cormunides.

The community creation server 1210 preferably outputs to a community setup manager 1212, which configures the various end users in accordance with community creabon/modificatiort/deconstruction instructions received from server 1210. Community set-up manager 1212 also interfaces with a bandwidth allocator 1214 5 in order to enable the bandwidth allocator 1214 to make appropriate bandwidth allocation deterrnnhonc In contrast with the embodiment of Fig. 1 OA, in the embodiment of Fig. 12A, the bandwidth allocator 1214 also interfaces with a content provider which makes a priori broadcast requests which require allocation of forward path bandwidth thereto lo by the bandwidth allocator 1214. The content provider may distinguish in its a priori broadcast requests between "must have" and "nice to have" broadcast requests, allowing the bandwidth allocator 1214 a certain, limited, measure of discretion in terms of - allocation of bandwidth for "nice to have" broadcast requests.

Community set-up manager 1212 also interfaces with a unicasmulticast 5 decision switch 1216, which is operative to send content by unicast, und1 the simultaneous demand for such content justifies sending the content by multicast.

Unicast/multicast decision switch 1216 is preferably incorporated into a cormnunity web server 1218.

In accordance with a preferred enho&ent of the present invention, 20 each comnurity is served by a single community web server 1218 and associated unicast/multicast decision switch 1216.

When and so long as simultaneous demand for a given web page exceeds a given threshold, unicastimulUcast switch 1216 triggers bandwidth allocator 1214 to allocate multicast forward path bandwidth for mulUcast of that web page. Bandwidth o5 allocator 1214 may employ a dynamic pre- emptive queue of URLs for such allocation.

In practice, the bandwidth allocator 1214 rrmy be responsive to the amountof available bandwidth for dynamically changing the threshold of switch 1216.

All unicast traffic is forwarded over the broadcast forward path from web server 1218 to cache 1208. Bandwidth allocator 1214 takes into account both unicast 30 and multicast traffic m allocating the available bandwidth of the forward path.

Bandwidth allocator 1214 essentially makes two different types of decisions: allocation between unicast and multicast and allocation of the multicast bandwidth among

communities and URLs. It is appreciated that the bandwidth allocation is performed by a logical entity, which may be embodied in one or more physically distributed network elements, such as routers.

Bandwidth allocator 1214 additionally interfaces with a multicast set-up 5 manager 1220 which in turn interfaces with a multicast announcement server 1222 and a.'ltic==t delivery server 12. Age-uluc= announcement server 1222 is operative to announce to all end users in a given community the estimated tune and address of upcoming multicasts. The multicast delivery server 1218 is operative to deliver the multicasts to the cache 1208, of each end user client 1202 associated with the given 0 conununity. Refernng now to Fig. 12B, it is appreciated that where in the embodiment of Fig. 12A, each community is served by a centralized community web - 3 server 1218, in the embodunent of Fig. 12B, a generic web server facility 1250, including one or more servers which may be at disparate locations, is employed to serve 5 multiple communities. In this embodiment the generic web server facility 1250 communicates with end users without regard to the communities to which they belong.

Therefore, in the embodiment of Fig. 1233, a bandwidth allocator 1254 is preferably co-located with a nmcastlmulticast decision switch 1256.

In the embodiment of Fig. 12B, a community set-up manager 1252 20 interfaces with the unicastmulticast decision switch 1256, here incorporated with bandwidth allocator 1254, and need not Ice with the generic web server 1250.

Preferably, in the embodiment of Fig. 12B, decisions to which content to multicast or unicast and as to the amount of bandwidth to allocate to the various multicasts are made by the co-located unicast/multicast decision switch 1256 and bandwidth allocator 1254.

as Therefore, the generic web server facility 1250 is required to continually update the unicast/multicast decision switch 1256 as to all web pages queried and as to the community identification thereof.

The reminder of the embodiment of Fig. 12B is identical to that of Fig. 12A. Identical elements are identified in Fig. 12B by the same reference numerals so employed in Fig. 12N The embodiment of Fig. 12B has an advantage over the embodiment of Fig. 12A in that in Fig. 12B, the web servers are generic and distributed among the

- - r v various communities. A disadvantage of the embodiment of Fig. 12B relative to the embodiment of Fig. 12A is that greatly enhanced traffic is generated between generic web server facility 1250 and Me unicast/multicast decision switch 1256.

Reference is now specifically made to Figs. 13A and 13B, which are s simplified flow diagrams corresponding respectively to the simplified functional block dia,,mq of Figs. 12A and lnB.

Turning to Fig. 13A, it seer, that along a time scale Mom the top of Fig. I 3A to the bottom thereof, initially users conduct browsing using browser 1204 prior to Connation of any community. Eventually, due to action of the profiler 1206, a 0 community is formed by community set-up manager 1212 in response to a bigger from community creation server 1210.

Following formation of a community, when end users who are members of the community engage m browsing, using browser 1204, and when the demand among members of the cor ununity for a given web page exceeds a threshold established 5 by unicastlmulticast decision switch 1216 of the commmity web server 1218, the content of the given web page is multicast to the entire conlruty subject to bandwidth availability constants.

Following the multicast, end users of the community can access the content of the given web page from their local cache with nearly zero latency.

90 Dunng both pre-commty fornadon browsing and post-community formation browsing, the community web server 1218 requests forward path bandwidth from bandwidth allocator 1214.

Refemug now to Fig. 13B, it is seen that the states of the fimctionality may be identical to those shown in Fig. 13A. A principal difference is in that whereas in :5 the embodiment of Pig. 13A, the threshold is established by unicast/multicast decision switch 1216 of the community web server 1218, in the embodiment of Fig. 13B, the threshold is established by the unicaslmulticast decision snatch 1256, co-located with the bandwidth allocator 1254.

Reference is now He to Fig. 14, which is a simplified flowchart so illusng the operation of an algorithm for bandwidth allocation in a umcast-multicast environment, wherein unicast and multicast do not share the same bandwidth As seen in Fig. 14, there is provided an algorithm for bandwidth allocation in which a sampling

time duration, typically of the order of minutes, is selected, and the current community size is determined for each community.

A multicast candidacy threshold for each community is determined using data regarding current cornmuty size for a selected sampling time duration. The 5 determination of the multicast candidacy threshold is preferably carried out as follows: An initial assllmptinn is mace 0 +,^ the 7 7 number of hilt or a cite for a given population of potential surfers over a given time duration, which characterizes a "popular site". The multicast candidacy threshold for each community is taken to be this minimum number multiplied by the sampling time duration and I o multiplied by the current size of each community.

The number of hits per URL for each community dunug each sampling time duration is monitored and converted to a URL hit score, which may be weighted according to trends in the Bander of hits per URL.

Multicast candidacy of a given site is determined by applying the Is multicast candidacy threshold to the URL hit score. If a given site is not considered as a multicast candidate, the nnber of hits thereon per community nevertheless continues to be monitored.

If a given site is considered to be a multicast candidate, the URL hit score is normalized for the community size and used to create a clout score based not 90 only on per capita popularity but also on the community size. This clout score could be identical to the URL hit score, but need not necessarily be so, inasmuch as various types of linear and non-linear weightings may be incorporated in the clout score.

The candidate sites are queued based on their respective clout scores The queue positions of the candidate sites may vary over time in accordance with 25 variations in their clout scores.

The content of the site having the highest queue position is multicasted to the extent of the availability of multicast bandwidth.

Determination of the multicast candidacy threshold may be made in accordance with the length of the queue of candidate sites. This may be done in the 30 following manner: If the queue size exceeds a predetpnmned maxitnlun queue threshold, the multicast candidacy threshold is modified by increasing the minimum number of hits on

a site for a given population of potential surfers over a given time duration, which is required to characterize a site as a "popular site".

Similarly, if Me queue size falls below a predetemuned nmimum queue threshold, the multicast candidacy threshold may be modified by reducing the miniruTm 5 number of hits on a site for a given population of potential surfers over a given time duration. which is requited to ch a site a "pep 1= site".

The amount of bandwidth allocated to multicasting of site content to members of each community may be monitored.

Reference is now made to Pig. 15, which is a simplified flowchart 0 illustrating We operation of an algorithm for bandwidth allocation in a nmcast-multicast environment, wherein unicast and multicast share the same bandwidth. As seen Fig. 14, a sampling time duration, typically of the order of minutes, is selected and the - content community size is detennined for each community.

A multicast candidacy threshold for each community is determirred using 15 data regarding current community size for a selected sampling hme duration. The determination of the multicast candidacy threshold is preferably carried out as follows: An initial assumption is made to the mom number of hits on a site for a given population of potential surfers over a given time duration, which characterizes a "popular site". The multicast candidacy threshold for each community is 20 taken to be this magnum number multiplied by the sampling time duration and multiplied by the current.qi of each community. 7 The number of hits per IJRL for each commnty during each sampling time duration is monitored and converted to a VRL hit score, which may be weighted according to trends in the number of hits per URL.

2s Multicast candidacy of a given site is determined by applying the multicast candidacy threshold to the URL hit score. If a given site is not considered as a multicast candidate, the number of hits thereon per community nevertheless continues to be monitored.

If a given site is considered to be a muiticast candidate, the URL hit so score is normalized for the corny size and used to create a clout score based not only on per capita popularity but also on the coTnunity size. This clout score could be identical to the URL hit score, but need not necessarily be so, inasmuch as various types

of linear and non-linear weightings may be incorporated in the clout score.

The candidate sites are queued based on their respective clout scores.

The queue positions of the candidate sites may vary over time in accordance with variations in their clout scores.

5 The content of the site having the highest queue position is multicasted to the extent of Ike alla ahi_hy of m,ltir.t b:3nd,,A,A+h In the embcA. lent C' Ci';. 1c' the availability of multicast bandwidth is determined In part by the utilization of commonly available bandwidth by unicast, which has a higher priority than multicast.

Ti1US it may be understood that multicast bandwidth is 'leftover" bandwidth which is l o not utilized by unicast.

The embodiment of Fig. 15, which involves sharing bandwidth between unicast and multicast, has an additional important features that increased multicasting of site content lowers the requirement for unicast bandwidth. This, in turn, makes more multicast bandwidth available. The increased availability of multicast bandwidth tends to reduce Me length of the queue for transmission. With this in mind, it may be appreciated that determination of the multicast candidacy threshold may be made in accordance with the length of the queue of candidate sites, typically in a manner somewhat different from that described hereinabove in connection with Fig. 14.

If the queue size falls below a predetermined queue threshold, similarly 20 to the situation in Fig 14, the multicast candidacy Fold is modified by reducing the minimum number of hits on a site for a given population of potential surfers over a given time duration, which is reared to character a size as a "popular site". Id this case, however, the multicast candidacy threshold is not permitted to fall below a minimum multicast candidacy threshold. If the minimum multicast candidacy threshold us is reached, the remaining available bandwidth is allocated to unicast hanission in order to reduce latency thereof.

Reference is now marle to Fig. 16, which is a simplified flowchart illustrating the operation of an algorithm for bandwidth allocation in a micast-multicast environment, wherein unicast, a priori multicast and triggered multicast share the same 30 bandwidth As seen in Figs. 14 and 15, a sampling time duration, typically of the order of minutes, Is selected and the c;=ert community size is determined for each community.

A multicast candidacy threshold for each community is determined using data regarding current community size for a selected sampling tune duration. The determination of the multicast candidacy threshold is preferably carried out as follows: An initial assumption is made as to the minimum number of hits on a site s for a given population of potential surfers over a Even time duration, which chat ac,erizes a '!popmar site. one muihcast candidacy threshold for each cormnunity is talcen to be this rninirn''m number multiplied by the sampling time duration and multiplied by the current size of each community.

The number of hits per URL for each community during each sampling lo time duration is monitored and converted to a URL hit score, which may be weighted according to trends in the number of hits per URL.

Multicast candidacy of a given site is determined by applying the multicast candidacy threshold to the URL hit score. If a given site is not considered as a multicast candidate, the number of hits thereon per community nevertheless continues to Is be monitored.

If a given site is considered to be a multicast candidate, the URL hit score is normalized for the community size and used to create a clout score based not only on per capita popularity but also on the community size. This clout score could be identical to the URL hit score, but need not necessarily be so, inamnuch as various types 20 of linear and nonlinear weightings may be incorporated in the clout score.

The candidate sites are queued based on their respective clout scores.

The queue positions of the candidate sites may vary over time accordance with variations in their clout scores.

The content of the site having the highest queue position is multicasted 25 to the extent of the availability of multicast bandwidth. In the embodiment of Fig. 16, the availability of multicast bandwidth is deterrred in part by the utilization of commonly available bandwidth by unicast, which has a higher priority than multicast and in part by a piori multicast broadcasting.

A priori multicast broadcasting typically includes a portion, here termed so "must have", which has the highest priory for bandwidth, exceeding that of unicast and all other multicast. A priori multicast broadcasting may also include a portion, here termed "Tuce to haves', which has a lower priority than "must have" and typically has the

same priority as other multicast transmissions. In the preferred embodiment of Fig 16, "nice to have" multicast, is given a static clout score which is an average clout score among multicast candidates Thus it may be understood that unicast bandwidth is "leftover" 5 bandwidth which is not utilized by "must have" a prion multicast and non "must have" mcincast bandwidth including "nice to have" a priori and other multicast, is "leftover" bandwidth which is not utilized by unicast The embodiment of Fig. 16, which involves sharing bandwidth between a prion multicast, unicast and multicast, also has the additional feature that increased i0 multicasting of site content lowers the requirement for unicast bandwidth This, tum, makes more multicast bandwidth available. The increased availability of multicast bandwidth tends to reduce the length of the queue for transmission. With this in rmud, it may be appreciated that determination of the multicast candidacy threshold may be made in accordance with the length of the queue of candidate sites, typically in a 5 manner described hereinabove in cormection with Fig. 15.

It will be appreciated by persons skilled in the art that the present invention is not limited by what has been particularly shown and described hereinabove.

Rawer the scope of the present invention includes both combinations and subcombina;tions of the various features described hereinabove as well as variations and So modifications which would occur to persons skilled in the art upon reading the specification aM which are not in the prior art.

j

Claims (1)

1. A method for providing unicast and multicast content to users and including bandwidth allocation, allocating highest priority to a-priori content and s next highest priority to unicast and for allocating remaining bandwidth to multicast.

2. A method according to claim 1 and including broadcast of content to all users within a geographical footprint of a broadcast, including transmission of content in a pay access regime.

3. A method according to either claim l or claim 2 and wherein multicasting includes transmission of content to all users within a community having a predefined common interest, within a geographical footprint of a broadcast.

5 4. A method according to any of claims 1 - 3 and wherein unicasting includes transmission of content to an individual user based on a request from that user. 5. A method according to any of claims l - 4 and wherein at least one so coordinating facility coordinates unicast functionality with at least one of broadcast and multicast functionalities, thereby to enable efficient and effective use of available resources in terms of transmission facilities and bandwidth.

6. A method according to claim 5 and wherein said at least one as coordinating functionality provides at least one of the following tunctionalities: shifting between unicasting and multicasting; bandwidth allocation within multicast communities; and bandwidth allocation between unicast, multicast and a priori broadcast or multicast content.

7. A method according to claim 5 and wherein said at least one coordinating functionality is operative to what content is sent in what manner at what time facilities to which users.

5 8. A method according to any of claims S - 7 and wherein said at least one coordinating functionality is operative to create new multicast communities in response to an increase in common user interests and requests.

9. A method according to any of claims 5 - 8 and wherein said at least lo one coordinating functionality is operative to eliminate multicast communities in response to a decrease in common user interests and requests.

10. A method according to any of claims 1 - 9 and wherein as a community grows, the amount of bandwidth allocated to that community increases.

11. A method according to any of claims 1 - 10 and wherein as a community decreases in size, the amount of bandwidth allocated to that community decreases. 20 12. A method according to any of claims 1 - 11 and including providing a guaranteed minimum level of unicast service to the extent required and wherein bandwidth remaining from the provision of the guaranteed minimum level of unicast service is employed for multicast, the same broadcast network providing both unicast and multicast.

13. A method according to any of claims 1 - 12 and wherein bandwidth not required for contractual unicast service is allocated to multicast, thereby reducing demand for contractual unicast service and thus, over time, decreasing latency and providing enhanced service to customers.

14. A method according to any of claims 1 - 13 and wherein bandwidth not required for contractual unicast service is allocated not only to multicast but also to better unicast service, in accordance with latency considerations.

5 15. A method according to any of claims 2 - 14 and wherein available bandwidth is allocated with the highest priority being given to a-priori content and the next highest priority being given to unicast, the remaining bandwidth employed being for multicast.

o 16. A method according to claim 15 and wherein said remaining bandwidth is allocated among communities based at least partially on relative community size.

17. A method according to any of claims 1 - 16 and substantially as Is described hereinabove.

18. A method according to any of claims 1 - 16 and substantially as shown in the drawings.