HK1172756B - A method and apparatus of delivering an audio video asset - Google Patents

Description

Method and device for distributing audio and video resources

Technical Field

The invention relates to a method of distributing an audio-visual asset and an apparatus for planning the distribution of an audio-visual asset.

Background

Increasingly, devices designed to enable consumption of video content feature large persistent storage and support broadcast and networking technologies.

Operators who wish to make video content available to devices equipped with multiple reception capabilities have a large number of transmission methods and techniques to choose from, including unicast (via a managed network or via the internet), broadcast (via satellite, terrestrial or cable systems) or multicast (via a managed network).

The broadcast capability will typically involve leasing the repeater for a contracted period of time. Unicast delivery via the internet may be provided in a variety of ways, including deployment of content servers in appropriate facilities, utilization of media hosting services, making content available via pay-as-you-go "cloud" services, or active participation in regional or global Content Distribution Networks (CDNs). Internet Protocol Television (IPTV) multicast or Video On Demand (VOD) capabilities may exist if the provider is able to utilize a managed IP network, for example, if content is distributed to customers of a single Internet Service Provider (ISP).

Each of these mechanisms may be used to distribute content at varying rates and times with respect to viewing. For example, the content may be distributed by broadcast transmission in a period prior to the viewing time (as is typically the case with broadcast push distribution), or may be distributed by unicast transmission at a higher rate starting at the viewing time (as is typically the case with progressive downloading).

Each method incurs costs in different aspects. For example, leasing satellite transponders for long periods of time typically costs a relatively large amount, typically millions of euros per year, while internet-based CDNs typically charge a few cents per Gigabyte (GB) for distribution of video content based on the amount distributed. Meanwhile, large volumes of bandwidth purchased at a co-location facility are charged based on peak usage, typically tens of euros per megabit per second (Mb/s).

The cost of distribution also depends on the nature of the distribution method. For example, content broadcast via satellite may be acquired by any tuner within its geographic coverage area (typically a large area that may include millions of distribution destinations). In contrast, delivery from a CDN by unicast transmission requires that a different copy of the content be sent to each destination, increasing delivery costs in proportion to the number of viewers.

Each possible path between a distribution source and a destination has an associated capacity that limits the content that can be distributed within a given time frame. For example, in the case of broadcasting, this capacity is determined by the available transponder bandwidth and the number and types of tuners available at the destination. In the case of internet or IPTV distribution, this capacity is determined in part by broadband access connectivity, but may also depend on one or more points of shared capacity between the source and destination, such as the ISP's connectivity to the wider internet.

Internet distribution resources are often provided by capacity on the basis of expected peak utilization. However, the demand for capacity is rarely constant over time, so resources are often underutilized during off-peak periods. Online video services such as the iPlayer (available from British Broadcasting Company (BBC)) have been shown to exhibit usage patterns with relatively high peak-to-average ratios, similar to those of broadcast television viewing. Thus, there is a relatively high probability of such capacity being used inefficiently for that service type.

Each distribution to be made may be associated with business criteria such as distribution deadline, priority or cost target.

CDN overlay networks are technologies that focus on Internet delivery mechanisms, typically combining multiple CDNs and some type of point-to-point (P2P) capability (see http:// blogs. gartner. com/lydia _ leong/2008/10/21/CDN-overlays-and-more-on-media).

Minimizing the weighted sum of objective functions is a technique well known from the field of multiple objective optimization and is used in cases where other types of optimization are computationally infeasible.

The following references are deemed to represent the state of the art:

european patent application EP 1476992 to Mitsubishi Denki Kabushiki Kaisha;

nikolova et al, U.S. patent application US 2008/0025222;

british patent application GB 2418267 by QinetiQ ltd;

U.S. patent applications US 2009/100459 to Riedl et al;

european patent EP 1563669 by Nokia corporation;

international patent application WO2009/087550 to Alcatel Lucent;

U.S. patent US 7,423,973 to Qualcomm;

international patent application WO2006/072825 to Nortel networks, Inc.; and

international patent application WO2009/076121 by Cisco technologies Inc.

Disclosure of Invention

An operator with capacity for multiple networks faces the problem of how to perform distribution of devices equipped with multiple reception capabilities in a way that makes optimal use of the different available distribution mechanisms, taking into account the factors described above, while meeting applicable business standards and optimizing for often conflicting objectives such as time and cost.

There is provided, in accordance with an embodiment of the present invention, a method of distributing an audio video asset, the method including: receiving an instruction specifying an audio video asset to be distributed and a distribution destination for the audio video asset, wherein a distribution destination represents one or more physical distribution recipients; determining a distribution path representing different distribution technologies available for distributing the audio video asset to the distribution destination; obtaining a set of path capacity timelines for the distribution paths, wherein the path capacity timelines in the set of path capacity timelines each model an amount of available capacity that varies over time; processing the path capacity timeline to produce distribution path capacities; applying an allocation algorithm to the distribution path capacities to generate candidate distribution allocations, wherein candidate distribution allocations each include one or more time periods during which a defined amount of capacity can be allocated for distribution of the audio video asset; applying a cost function to the candidate distribution allocations to produce cost values, wherein the cost values each represent a cost of distributing the audio video asset according to the candidate distribution allocation; calculating a score for the candidate distribution allocation in dependence upon a cost value for the candidate distribution allocation and one or more other objectives; selecting the candidate distribution allocation with the lowest score to produce a selected candidate distribution allocation; and distributing the audio video resources according to the selected candidate distribution allocation scheme.

Further, in accordance with an embodiment of the present invention, the instruction also specifies criteria relating to a method of implementing the instruction.

Still further in accordance with an embodiment of the present invention, the criteria includes a time window within which the audio video asset is distributed.

Further in accordance with an embodiment of the present invention, the criteria includes a priority flag indicating that the distribution of the audio video asset is to be considered to have priority over the distribution of other audio video assets.

Further, according to an embodiment of the present invention, the determining the distribution path includes: for each distribution path, a distribution receiver associated with the distribution capability is matched to the distribution source represented by the distribution option according to one or more criteria of a distribution scheme representing the distribution technology.

Further, according to an embodiment of the present invention, the determining of the distribution path further includes removing a distribution path that does not satisfy a rule that controls use of a distribution option of the distribution destination.

Still further in accordance with an embodiment of the present invention, the group of obtaining a path capacity timeline comprises: for each distribution path, a path capacity timeline associated with the distribution destination option and a path capacity timeline associated with the distribution destination are obtained.

Further, according to an embodiment of the present invention, the group of acquiring a path capacity timeline further includes: for each distribution path, a path capacity timeline associated with the distribution scheme is obtained.

Furthermore, in accordance with an embodiment of the present invention, the set of the acquisition path capacity timelines further includes: for each distribution path, determining whether the distribution destination has any child destinations and examining any child destinations for further child destinations until a leaf destination is identified; and a path capacity timeline associated with the leaf destination is obtained.

Further, according to an embodiment of the present invention, the processing of the path capacity timeline includes: a minimization function is performed for each set of the path capacity timelines.

Still further in accordance with an embodiment of the present invention, the allocation algorithm allocates capacity as early as possible within a limit of available capacity specified by a distribution path capacity, and calculates the capacity to allocate in accordance with a size of the audio video asset to be distributed and a number of physical distribution recipients.

Further in accordance with an embodiment of the present invention, the allocation algorithm allocates capacity during a period proportional to a defined peak capacity to average capacity ratio and a defined peak capacity period, and calculates the capacity to allocate as a function of the size of the audio video asset to be distributed, the number of physical distribution recipients, and a probability that the audio video asset is being viewed, wherein the probability that the audio video asset is being viewed is derived from content viewing statistics.

Furthermore, according to an embodiment of the invention, the allocation algorithm: identifying an existing allocation scheme for the audio video assets to be distributed; allocating capacity suitable for an existing allocation scheme if the existing allocation scheme exists; otherwise, allocating capacity as early as possible within the limits of available capacity specified by the distribution path capacity; wherein the capacity to be allocated is calculated from the duration and coding bit rate of the audio video asset to be distributed.

Further, in accordance with an embodiment of the present invention, the allocation algorithm is parameterized with one or more time windows representing one or more time periods, and one candidate distribution allocation is returned for each of the one or more time periods.

Still further in accordance with an embodiment of the present invention, each candidate distribution allocation comprises more than one consecutive time period.

Further, the cost function is parameterized using a time period and a plurality of capacity bands, a capacity band of the plurality of capacity bands being associated with a cost factor, and the cost function identifies a set of peak capacity values in the distribution path capacity at regular intervals over a fixed period, discards a maximum 5% of the peak capacity values of the set of peak capacity values, selects a next maximum peak capacity value as a peak capacity value within the fixed period, determines a cost of the fixed period by multiplying the peak capacity value of the fixed period by a cost factor determined by reference to a capacity band, and determines a cost value of a candidate distribution allocation from the usage represented by the candidate distribution allocation and the cost of the fixed period.

Furthermore, according to an embodiment of the invention, the cost function is parameterized using time segments, each time segment being associated with a capacity band and a cost factor, wherein the cost of the whole time segment is calculated as a weighted sum of each time segment.

Further, according to an embodiment of the invention, the cost function is parameterized using a time period and a plurality of capacity bands, each of the plurality of capacity bands being associated with a cost factor, and data comprising the candidate distribution allocations distributed over a fixed period is calculated, a cost factor is determined by reference to a capacity band, and a cost value for the candidate distribution allocation is calculated from the data and the cost factor.

Still further in accordance with an embodiment of the present invention, the cost function is also parameterized with time periods, each time period being associated with a capacity band and a cost factor, and the associated cost factors are determined by reference to the capacity band and the time periods.

Further, the cost function is parameterized using a cost factor and a time period, and the usage represented by the distribution candidate allocation is calculated as a proportion of the total capacity within the time period, and a cost value for the candidate distribution allocation is calculated as a function of the proportion and the cost factor.

Further, according to an embodiment of the present invention, the one or more other objects include: the cost is minimized; or minimizing the time to the end of the distribution of the audio video asset; or minimizing the duration of the distribution of the audio video asset.

Further, according to an embodiment of the present invention, calculating the score of the candidate distribution allocation comprises: for the one or more other targets, obtaining a target weight, and modifying a standard value of the target by multiplying the standard value by the target weight, thereby producing a set of weighted values; and summing the set of weighted values to produce the score.

There is further provided, in accordance with another embodiment of the present invention, apparatus for scheduled distribution of an audio-visual asset, the apparatus including: means for receiving an instruction specifying an audio video asset to be distributed and a distribution destination for the audio video asset, wherein a distribution destination represents one or more physical distribution recipients; means for determining a distribution path representing different distribution technologies available for distributing the audio video asset to the distribution destination; means for obtaining a set of path capacity timelines for the distribution paths, wherein the path capacity timelines in the set of path capacity timelines each model an amount of available capacity that varies over time; means for processing the path capacity timeline to produce one or more distribution path capacities; means for applying an allocation algorithm to the distribution path capacities to generate candidate distribution allocations, wherein candidate distribution allocations each include one or more time periods during which a defined amount of capacity can be allocated for distribution of the audio video asset; means for applying a cost function to the candidate distribution allocations to produce cost values, wherein the cost values each represent a cost of distributing the audio video asset according to the candidate distribution allocations; means for calculating a score for the candidate distribution allocation dependent on the cost value for the candidate distribution allocation and one or more other objectives; means for selecting the candidate distribution allocation with the lowest score to produce a selected candidate distribution allocation; and means for distributing the audio video asset according to the selected candidate distribution allocation scheme.

Drawings

The invention will be more fully understood and appreciated from the following detailed description taken in conjunction with the accompanying drawings, in which:

FIG. 1 is a simplified schematic illustration of a system constructed and operative in accordance with an embodiment of the invention;

FIG. 2 is a flow diagram of a method operated by the system of FIG. 1, in accordance with an embodiment of the present invention;

FIG. 3 is a simplified schematic diagram of a resource instruction according to an embodiment of the invention;

FIG. 4 is a simplified schematic diagram of how a distribution path is determined according to an embodiment of the present invention;

FIG. 5 is a simplified schematic diagram of a distribution path determined according to an embodiment of the present invention;

FIG. 6 is a flow chart of a capacity timeline processing method according to an embodiment of the present invention;

FIG. 7 is a simplified diagram of acquiring a capacity timeline according to an embodiment of the present invention;

FIGS. 8 and 9 are simplified schematic diagrams of how a capacity timeline is handled according to an embodiment of the present invention;

FIG. 10 is a flow diagram of a method of applying an allocation algorithm to path capacities in accordance with an embodiment of the present invention;

FIGS. 11 through 15 are simplified schematic diagrams of an allocation algorithm according to an embodiment of the present invention;

FIG. 16 is a flow diagram of a method of assigning costs to candidate allocation schemes according to an embodiment of the present invention;

FIG. 17 is a simplified schematic diagram of a candidate allocation scheme according to an embodiment of the present invention;

FIG. 18 is a flow diagram of a method of selecting a candidate allocation scheme according to an embodiment of the present invention; and

FIG. 19 is a simplified schematic diagram of scored candidate assignments, according to an embodiment of the invention.

Detailed Description

According to embodiments of the present invention, different distribution technologies, such as satellite broadcast or internet distribution, are each represented by a scheme in the system. Each solution uses this technique to define prototype components of the distribution path. These elements include sources and receivers, such as satellite transponders and satellite tuners in the case of broadcast distribution; or a streaming media server and network interface in the case of internet distribution. Further, each scheme defines a different way in which capacity may be allocated and spent.

The system is configured with one or more distribution options, each distribution option representing a distribution source from a scenario and being associated with one or more allocation scenarios and cost calculation algorithms specific to the scenario.

The system is also configured with a plurality of distribution destinations, each distribution destination representing one or more physical distribution recipients. The distribution destinations are arranged into a hierarchical structure so that a wide population section can be efficiently processed. For example, a destination representing a "family with children" may be configured with two sub-destinations "london region" and "manchester region" so that any of the three groups of physical distribution recipients can be handled separately. The distribution destination is associated with a plurality of capabilities, each capability representing a distribution receiver from a scheme.

The system is also configured with a plurality of capacity timelines. Each capacity timeline models the amount of available capacity over time, e.g., Mb/s over a 48 hour period. One capacity timeline is associated with each distribution option and at least one capacity timeline is associated with each distribution destination. Further, the capacity timeline may be associated with more than one distribution destination. The nature of the correlation between the capacity timeline and the distribution options or destinations is specific to one scheme. For example, a distribution destination may have two capacity timelines associated with receivers from an internet distribution scheme, one representing broadband access capacity and the other representing capacity within a particular ISP network.

It should be noted that by configuring the available capacity in this way, the platform is able to perform control of the load that would be incurred by a series of distributed resources (distributed resources directly under the control of the platform and distributed resources under the control of a third party).

The system is also configured with rules that control the use of the distribution options of the distribution destinations. For example, it may be desirable to limit the use of distribution options representing streaming media servers for distribution destinations that exist in a particular IP address space.

The system is further configured with a plurality of heuristics that enable comparison of candidate distribution allocations made according to different schemes to a plurality of objectives. For example, one heuristic may attempt to minimize cost while another attempts to minimize distribution completion time. These heuristics are configured with weights that reflect their relative importance to the platform.

In addition to the configured model elements described above, the system also accesses a body of data detailing content viewing statistics. This data may be captured directly from users of the platform via a suitable audience measurement system or may be provided from an external source such as the broadcaster program audience research club (BARB) or Nielsen ratings.

Referring to FIG. 1, a system according to an embodiment of the invention is shown. The audio video content resources (live content 101 and non-live content 103) are absorbed by the platform's distribution planner 105 and instructions 106 for those resources received from the platform's user's home content storage device 107. The audio video content asset can be distributed to the storage device 107 in many different ways. For example, through a satellite broadcast network utilizing a satellite uplink 109, a satellite transponder 111, and a satellite dish and satellite tuner 113. Or through the public internet 115 using a data center 117 (also referred to as a media server or download server) or CDN 119 (also referred to as a streaming server) and a network interface. Other distribution routes will be apparent to those skilled in the art, including those using private (administrative) IP network 121.

Referring now to FIG. 2 and in accordance with an embodiment of the present invention, the distribution planner 105 performs a series of steps of model operations of the distribution resources available to the platform. As previously described, the different distribution techniques are organized into schemas, each schema being associated with various distribution resource types, allocation algorithms, and cost functions. A capacity timeline is assigned to the resources and specifies rules relating to how the resources may be used. Heuristics are defined that enable comparison of possible distribution solutions using different schemes.

The distribution tasks are received by the system as instructions (step 201), each instruction specifying the resource to be scheduled for distribution, the distribution destination, and any criteria to be adhered to. For each instruction, a set of possible distribution paths is determined (step 203). For each distribution path, an applicable set of capacity timelines are obtained and processed (step 205), resulting in a distribution path capacity. For each path capacity, an allocation algorithm is applied based on the associated scheme to generate zero or more candidate distribution allocation schemes (step 207). For each candidate distribution allocation, a cost function is applied based on the associated scheme, resulting in zero or more calculated cost candidate distribution allocations for each distribution path (step 209). Once all distribution paths have been processed, each candidate allocation is scored via heuristics evaluating relative costs, schedules, and meeting any criteria, and one candidate allocation is selected from the set of candidate allocations (step 211). Finally, the associated capacity timeline is updated to reflect the selected allocation scheme, the decisions are stored (step 213) and commands for performing the distribution are generated (step 215).

In this manner, the distribution decision for one or more instructions may be locally optimized for a variety of factors, including but not limited to, the capacity available in the different distribution mechanisms, the cost incurred by their use, the time of distribution, and other criteria.

Each of the steps described above will now be described in more detail below.

The distribution tasks are received by the system as instructions (step 201), each instruction specifying a resource to be distributed and a distribution destination, as shown, for example, in fig. 3. Further, each instruction may specify criteria in the form of constraints or priorities that relate to the manner in which the instruction is implemented. An example of a constraint is a time window within which the distribution must be completed. An example of priority is a priority flag indicating that the distribution should be considered to have priority over other distributions. Instructions are typically processed in batches by the system. In each batch, the system typically merges instructions together where there is a crossover in resources, destinations, and criteria.

For each instruction, the system determines a set of distribution paths that can be used to distribute the resource to the specified destination (step 203). Referring to fig. 4, a distribution receiver (e.g., network interface; DVB-S tuner; DVB-S2 tuner) associated with capabilities (e.g., broadband; satellite) configured for a destination (e.g., a child' S home) is matched with a distribution source (e.g., streaming server; download server; DVB-S repeater; DVB-S2 repeater) according to a standard specific to the scheme. For example, a satellite broadcast scheme would match a DVB-S tuner with a DVB-S transponder rather than with a DVB-S2 transponder; while an internet solution would match the streaming server and download server to the network interface. Delivery options configured for those delivery sources are then obtained (e.g., "CDN service company," "European data center," "SatCasting company"). This results in a set of paths, each path consisting of distribution options, destinations, capabilities and scenarios. For example, three such paths are shown in FIG. 5. The set of generated distribution paths may be reduced by removing those paths that do not satisfy the configured rules governing the use of distribution options for distribution destinations. For example, for business reasons, the rules may be configured to specify that the destination must not utilize "CDN service company," thus removing the third path from the group described above.

For each distribution path under consideration, the system determines a path capacity (step 205). First, a capacity timeline associated with a distribution path is obtained. For each distribution path, there are a minimum of two capacity timelines — one associated with the distribution option and one or more associated with the distribution destination or scenario.

Referring now to FIG. 6, to analyze the capacity timeline for distribution destinations, the system first determines whether the destination has any child destinations. If so, the child destinations themselves are checked for children, etc., until a leaf destination is identified (step 601). The system then retrieves the capacity timelines associated with these page destinations (step 603). An additional capacity timeline for the distribution options is obtained (step 605) and/or an additional capacity timeline for the distribution path scheme may also be obtained (step 607). An example is shown in fig. 7, in which the capacity timeline is acquired for the distribution option "european data center", the scenario "internet", and each page destination "london region" and "manchester region". Each capacity timeline plots (as dotted lines) the configured limits imposed on the available capacity over time. The capacity that has been used is shown by shading.

The scenario-dependent algorithm then processes the acquired capacity timeline (step 609), resulting in a distribution path capacity (a processed capacity timeline for the distribution path).

For most solutions (e.g., internet distribution solutions), the distribution path capacity can be calculated by performing a minimize or maximize function on the set of acquired capacity timelines (to calculate available, unused capacity, to minimize available capacity or maximize unavailable capacity, and then compared to capacity limits). FIG. 8 shows the resulting processed capacity timeline with used, unavailable capacity "added" together to produce a capacity region with a capacity limit 801, a used, unavailable capacity region 803, and an unused, available capacity region 805.

For some schemes (e.g., satellite broadcast schemes), an alternative distribution path capacity calculation is typically used due to constraints on the possible capacity values of the page destination timeline. These constraints are due to the fact that satellite tuners are typically not used at all or at all. That is, after tuning, the customer of the satellite tuner may choose to use 3Mbps, 7Mbps, or any other number, but the entire theoretical capacity (51.6Mbps, but typically only 33Mbps for DVB-S) will still be distributed to the tuner. Thus, while a tuner is tuned to a satellite multiplex on a particular frequency, the tuner cannot receive content from a satellite multiplex on any other frequency. The minimum value is further constrained to be the least common multiple of the tuner capacity. For example, using two tuners (typically providing a total capacity of 66 Mbps), possible capacity values are 66Mbps, 33Mbps, and 0 Mbps. Referring to fig. 9, the resource 901 to be distributed has been scheduled for broadcast on a repeater associated with SatCasting corporation. The tuner associated with the "london area" is arranged to tune to the transponder associated with SatCasting corporation for a period of time 903. The tuner associated with the "london region" is also arranged to tune to some other transponder for a period of time 905. The resulting processed capacity timeline thus indicates:

a currently scheduled broadcast of the resources to be distributed on the SatCasting company forwarder 907. This capacity can be allocated to distribute resources (as opposed to an internet distribution scheme, where this capacity would be specified as used capacity and therefore would not be available to distribute resources-the difference between unicast and broadcast transmissions;

a delegation to other scheduled broadcasts to be distributed on the SatCasting company transponders 909. This capacity cannot be allocated to distribute resources.

A delegation to some other transponder 911. Nothing can be distributed from the SatCasting company transponders during this period because the tuner can only be tuned to one frequency at a time.

It should be noted that FIG. 9 illustrates the "logical" usage caused by a resource. During the period of time when the currently scheduled broadcast for a resource occurs, the tuner has been delegated to the repeater in question and can record some other resource. To take advantage of the striped existing distribution scheme, the customer would need to be able to record at least two items simultaneously from the same transponder. Otherwise, the earliest distribution would be directly to the right of the entire shadow region. However, this logic is the responsibility of the allocation algorithm from the satellite broadcast scheme-the output of this stage is merely a statement of the fact that the available capacity over time for this distribution path is available.

For each distribution path capacity, the system generates one or more candidate distribution allocations (step 207), each allocation consisting of one or more time periods during which a defined amount of capacity may be allocated.

Referring now to fig. 10, for a distribution path capacity under consideration, an allocation algorithm associated with the distribution options for that distribution path is obtained (step 1001). The algorithm will be one of the base algorithms defined by the associated scheme and set during configuration according to the nature of the distribution options. The allocation algorithm is then applied to the distribution path capacity (step 1003) and candidate allocations are generated and added to the list of candidate allocations to be processed (step 1005).

The allocation algorithms differ in the way the capacity is allocated and the factors that influence the allocation. The purpose of this stage (step 207) is to generate a list of feasible candidate distribution allocations within constraints for later consideration based on more general criteria such as priority or cost. Different non-limiting examples of allocation algorithms will now be described with reference to fig. 11 to 15.

The allocation algorithm of the internet distribution scheme intended for scheduled resource distribution allocates capacity as early as possible within the limits of available capacity as specified by the processed capacity timeline (shown in fig. 11). The amount of capacity required for distribution is calculated directly from the resource size and the number of physical distribution recipients.

Another allocation algorithm for internet distribution schemes intended for on-demand distribution of resources allocates capacity during a period proportional to a defined peak-to-average ratio and a defined peak period (as shown in fig. 12). The amount of capacity required for distribution is calculated from the resource size, the number of recipients of the physical distribution, and the probability that those resources are being viewed. The probability that a resource is being viewed is derived from the content viewing statistics that the system can utilize during configuration. It should be noted that the capacity timeline used in this manner represents the probability distribution of load over time, rather than an indicative plan for capacity usage.

Another allocation algorithm from the satellite broadcast distribution scheme first identifies an existing allocation scheme for the resources specified in the instructions. If no existing allocation scheme exists, the algorithm allocates capacity as early as possible within the limits of available capacity as specified by the processed capacity timeline. If an existing allocation scheme for the resources specified in the instruction does exist, then capacity appropriate for the existing allocation scheme is allocated (as shown in FIG. 13). The amount of capacity required for distribution is calculated from the duration of the resource and the coding bit rate. It should be noted that the created candidate allocation scheme that fits the existing allocation scheme does not use extra capacity from the capacity timeline associated with the distribution options. It should further be noted that this type of allocation algorithm assumes that the distribution technique in use allows the destination to obtain more than one item simultaneously from the distribution options. In the case where the satellite broadcast tuner can only be used to acquire one item in a given time period, this allocation algorithm is modified to allocate capacity for the duration of the resource rather than using the encoding bit rate.

Variations of the allocation algorithm described above may be affected by the cost factor. The allocation algorithm of the internet distribution scheme intended for scheduled resource distribution may be parameterized using one or more time windows, returning a candidate allocation scheme at each time period (as shown in fig. 14). This may be used to reflect the fact that the cost of distributing resources varies over the time of day.

It should be noted that instead of generating multiple allocation schemes, each allocation scheme itself may consist of more than one consecutive period (as shown in fig. 15). This may occur, for example, where the allocation to be made within a given period is greater than the first or indeed any one period of free capacity. Whether multiple time periods can be returned depends on the distribution algorithm — it may be reasonable for a scheduled internet distribution to divide the distribution of a given instruction over several time periods, whereas not allowing this may be a matter of policy for satellite broadcast distribution.

For each candidate allocation scheme, the system generates an associated cost (step 209).

Referring to fig. 16, for the candidate allocation under consideration, distribution options are obtained (step 1601). The cost function associated with the retrieved distribution options is then obtained (step 1603). The cost function will be one of several such cost functions defined by the associated scheme and set during configuration according to the nature of the distribution options. The obtained cost function is then applied to the candidate allocation scheme and the cost is assigned to the candidate allocation scheme (step 1605).

The cost function reflects the manner in which the use of capacity associated with the distribution options incurs cost to the platform. These costs are also typically dependent on business agreements, not only by scheme and by usage pattern.

An example of a cost function for an internet distribution scheme calculates cost based on 95 percent capacity usage. A parameterized cost function is used with a period and a plurality of capacity bands, each capacity band associated with a cost factor. The function identifies sets of peak capacity values in the capacity timeline at regular intervals over a fixed period of time. The largest 5% of these values are discarded and the next highest value is considered the capacity usage value within the fixed period. The relevant cost factor is determined by reference to the capacity band and the cost over the fixed period is calculated by multiplying the cost factor by the capacity usage value. The allocation cost is then calculated from the usage represented by the allocation plan and the cost over the period.

The variation of the cost function described above calculates the cost based on 95 percent capacity, where different rates are applied at different times of the day. The function is parameterized using more than one time period, each time period being related to a capacity band and a cost factor as above. First, as described above, the cost factor associated with the capacity band and the time period is used to calculate the cost per time period. The cost over the total period is calculated as a weighted sum of each individual period.

Another example of a cost function for an internet distribution scheme calculates a cost based on the amount of data distributed. The function is parameterized using a time period and a plurality of capacity bands, each capacity band being associated with a cost factor. Data comprising candidate allocation schemes distributed over a fixed period of time is calculated and a relevant cost factor is determined by a reference band. The allocation cost is then calculated from the data distributed by the allocation scheme and the cost factor. A variation of this cost function calculates the cost based on the distributed data, where different rates are applied at different times of the day. The function is parameterized using more than one time period, each time period being related to a quantum band and a cost factor as described above. The distributed data is calculated as described above and the associated cost factor is determined by both the reference amount band and the time period.

An example of a cost function for a broadcast distribution scheme calculates a cost based on proportional resource usage. The function is parameterized using a cost factor and a time period. The usage represented by the candidate allocation is calculated as a proportion of the total capacity over the period. An allocation cost is then calculated based on the ratio and the cost factor.

The system now has multiple candidate allocations using a series of distribution options associated with the instructions. Each candidate allocation scheme represents one way to implement instructions within the capacity constraints of the distribution path. If a given instruction is directed indirectly to more than one destination, there may be several candidates for that instruction. As shown in fig. 17, each candidate allocation scheme (1701, 1703, 1705) has a plurality of attributes including one or more scheduled periods of resource distribution and a cost score.

The candidate allocation scheme 1701 makes use of DVB-S repeaters allocated to the distribution option entitled "SatCasting company". The resource to be distributed is "Popular Soap Opera" which is expected to be viewed widely (it has a 75% probability of being viewed). The logical destination is a "london area" that includes 50,000 different physical destinations. The instructions specify that the distribution is considered to be of relative priority and that the calculated cost score is $ 47. Distribution will start at 10:00 on thursday, content will be distributed at 6Mb/s, and will end at 10: 30.

The candidate allocation 1703 utilizes a download server assigned to the distribution option entitled "european data center". Because this is a candidate allocation scheme that implements the same instruction, the resources to be distributed, associated viewing probabilities, destinations, and criteria are the same as described above with respect to candidate allocation scheme 1701. The distribution starts earlier on tuesday 06:00, but takes longer to distribute the content, which is 1Mb/s because of the lower rate. The distribution ends on tuesday 09: 00. The calculated cost score for this candidate allocation scheme is higher, $1500, reflecting the unicast mode of transmission and the resulting capacity required to handle multiple different distribution destinations.

Candidate allocation scheme 1705 utilizes a streaming server assigned to a delivery option entitled "CDN service company". As above, the resource, destination, and instruction criteria remain the same. However, in this case, the distribution intent is on-demand. The peak viewing time is estimated to be 19:00 on friday and the content bit rate is 3 Mb/s. The content duration is one hour. The cost score calculated for this candidate allocation is again higher, being $10,000. This reflects the number of different delivery destinations modified by the viewing probability, since the CDN is charged based on the amount delivered as well as the high rate charged by the CDN and the relatively large amount of content delivered at this bit rate and duration.

For each candidate allocation, the system generates a total score and selects the candidate allocation with the lowest score (step 211).

The total score is obtained by applying one or more configured heuristics to generate values that are then combined by computing a weighted sum.

Heuristics represent decision objectives and their items are assigned according to the attributes and instruction criteria of the candidate allocation scheme. Each heuristic is typically formulated in a minimal function manner.

Default goals that are typically applied by the system include minimizing cost, minimizing time to completion of distribution, and minimizing duration of distribution.

The presence of deadlines in the instruction standard allows the system to select heuristics that minimize the positive deviation between the deadlines specified in the instruction standard and the dispatch completion time. The presence of the priority flag in the instruction criteria allows the system to select a heuristic that minimizes the time to completion of the dispatch while having a non-linear bias towards the dispatch ahead. This replaces the default target.

Each heuristic is configured with a weight between 0 and 1 reflecting its importance to the platform. Referring to FIG. 18, for each target of each candidate assignment, a weight is obtained (step 1801), which the system then modifies by multiplying the standard value returned by the heuristic by its weight to obtain a score (step 1803). The set of weighted values (scores) for the results are then summed into an overall score (step 1805), which is then stored (step 1807). The system then selects the candidate allocation with the lowest score (step 1809). FIG. 19 shows a table illustrating exemplary targets, criteria values, weights, scores, and total scores. In this example, the cost is more important than all other targets (weighting of 0.6), and the distribution time (weighting of 0.3) and completion time (weighting of 0.1) are considered less important by the platform.

It should be noted that given the allocation algorithm and cost function described above, the number of destinations and the probability of viewing of a resource has an impact on the resulting cost of the candidate allocation scheme. In particular, unicast distribution tends to incur much greater costs than broadcasting for a large number of destinations with high viewing probability. This will in turn strongly favor broadcasting, all other factors being equal, based on the cost of the instructions of this nature.

The system then updates its internal state to reflect the selected candidate allocation, stores the decision and discards the other candidate allocations (step 213). The selected candidate allocation plans constitute a distribution plan that implements the original instructions.

The capacity timeline for the delivery options, destinations and plans associated with the selected candidate allocation plan is updated according to the manner in which the capacity is allocated. Changes to the capacity timeline and allocation details are then maintained by reference to the satisfied instruction so that subsequent requests to cancel the instruction can be satisfied. A distribution plan indication carrying details of the distribution plan is generated (step 215) and distributed to downstream systems responsible for performing the distribution of the resources.

An automatic decision making system is described that efficiently utilizes a large number of heterogeneous distribution mechanisms (e.g., satellite broadcast and internet unicast) in terms of transmission cost and time to distribute video resources to a large number of devices with heterogeneous acquisition capabilities (e.g., multi-tuner STBs with broadband capabilities). Some advantages of the above system include: abstracting key aspects of other heterogeneous distribution mechanisms into a model of generic, comparable elements; a reduction of resource distribution instructions for hierarchically organizing destinations into different distribution paths involving a particular distribution mechanism element based on the model; determining an available capacity for each different distribution path by applying an algorithm to a plurality of capacity timelines, wherein each capacity timeline represents the available capacity over time for a given distribution mechanism element; by using an algorithm designed to reflect the effect of a variety of factors on the manner in which capacity is allocated (including in particular viewing probability), a range of feasible allocation schemes are generated within time and capacity constraints with reference to the available capacity of the distribution path to satisfy a given instruction; assigning a cost score to each allocation scheme using a cost function designed to reflect the manner in which the use of capacity associated with a particular distribution mechanism incurs cost to the platform; and selecting a preferred allocation from a set of candidate allocations using a technique that minimizes a weighted sum of objective functions based on the candidate allocation attributes and a plurality of objectives specified in part by the instructions under consideration and in part by the system configuration. Other advantages will be apparent to those skilled in the art.

It will be appreciated that the software components of the invention may be implemented in ROM (read only memory) form, if desired. The software components may typically be implemented in hardware using conventional techniques, if desired. It should also be appreciated that the software components may be instantiated, for example, as a computer program product, a tangible medium, or as a signal interpretable by an appropriate computer.

It is appreciated that various features of the invention which are, for clarity, described in the context of separate embodiments, may also be provided in combination in a single embodiment. Conversely, various features of the invention which are, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable subcombination.

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. Rather, the scope of the invention is defined only by the appended claims.

Claims (22)

1. A method for distributing an audio video asset, the method comprising:

receiving instructions, each instruction specifying an audio video asset to be distributed and a distribution destination for the audio video asset, wherein a distribution destination represents one or more physical distribution recipients;

determining a distribution path available for distributing the audio video asset to the distribution destination, wherein the determining comprises: for each distribution path, matching a distribution receiver associated with the distribution capability to a distribution source represented by a distribution option according to one or more criteria of a distribution scheme representing the distribution technology;

obtaining a set of path capacity timelines for the distribution paths, wherein the path capacity timelines in the set of path capacity timelines each model an amount of available capacity that varies over time;

processing the path capacity timeline to produce distribution path capacities;

applying an allocation algorithm to the distribution path capacities to generate candidate distribution allocations, wherein candidate distribution allocations each include one or more time periods during which a defined amount of capacity can be allocated for distribution of the audio video asset;

applying a cost function to the candidate distribution allocations to produce cost values, wherein the cost values each represent a cost of distributing the audio video asset according to the candidate distribution allocation;

calculating a score for the candidate distribution allocation in dependence upon the cost value for the candidate distribution allocation and one or more other objectives;

selecting the candidate distribution allocation with the lowest score to produce a selected candidate distribution allocation; and

distributing the audio video asset according to the selected candidate distribution allocation scheme,

wherein processing the path capacity timeline comprises: minimizing available capacity on said set of path capacity timelines or maximizing unavailable capacity on said set of path capacity timelines, and comparing the result of said minimizing or maximizing with a capacity limit.

2. The method of claim 1, wherein the instruction further specifies criteria relating to a manner in which the instruction is implemented.

3. The method of claim 2, wherein the criteria comprises a time window within which the audio video asset is distributed.

4. The method of claim 3, wherein the criteria comprises a priority flag indicating that distribution of the audio video asset is to be considered prioritized relative to distribution of other audio video assets.

5. The method of claim 1, wherein the determining a distribution path further comprises removing a distribution path that does not satisfy a rule controlling use of distribution options of distribution destinations.

6. The method of claim 1, wherein said obtaining the set of path capacity timelines comprises: for each distribution path, a path capacity timeline associated with the distribution destination option and a path capacity timeline associated with the distribution destination are obtained.

7. The method of claim 6, wherein said obtaining said set of path capacity timelines further comprises: for each distribution path, a path capacity timeline associated with the distribution scheme is obtained.

8. The method of claim 6, wherein said obtaining said set of path capacity timelines further comprises: for each distribution path, determining whether the distribution destination has any child destinations and examining any child destinations for further child destinations until a leaf destination is identified; and a path capacity timeline associated with the leaf destination is obtained.

9. The method of claim 1, wherein the processing of the path capacity timeline comprises: a minimization function is performed for each set of the path capacity timelines.

10. The method of claim 1, wherein the allocation algorithm allocates capacity as early as possible within a limit of available capacity specified by a distribution path capacity, and the capacity to allocate is calculated from a size of the audio video asset to distribute and a number of physical distribution recipients.

11. The method of claim 1, wherein the allocation algorithm allocates capacity for a period proportional to a defined peak capacity to average capacity ratio and a defined peak capacity period, and the capacity to allocate is calculated as a function of a size of the audio video asset to be distributed, a number of physical distribution recipients, and a probability that the audio video asset is being viewed, wherein the probability that the audio video asset is being viewed is derived from content viewing statistics.

12. The method of claim 1, wherein the allocation algorithm:

identifying an existing allocation scheme for the audio video assets to be distributed;

allocating capacity suitable for an existing allocation scheme if the existing allocation scheme exists; and

otherwise, capacity is allocated as early as possible within the limits of available capacity specified by the distribution path capacity;

wherein the capacity to be allocated is calculated from the duration and coding bit rate of the audio video asset to be distributed.

13. The method of claim 1, wherein the allocation algorithm is parameterized using one or more time windows representing one or more time periods, and one candidate distribution allocation is returned for each of the one or more time periods.

14. The method of claim 1, wherein each candidate distribution allocation comprises more than one consecutive time period.

15. The method of claim 1, wherein the cost function is parameterized using a time period and a plurality of capacity bands, a capacity band of the plurality of capacity bands being associated with a cost factor, and the cost function identifies a set of peak capacity values in distribution path capacity at regular intervals over a fixed period, discards a largest 5% of the peak capacity values of the set of peak capacity values, selects a next largest peak capacity value as a peak capacity value within the fixed period, determines a cost for the fixed period by multiplying the peak capacity value for the fixed period by a cost factor determined by reference to a capacity band, and determines a value for a candidate distribution allocation scheme according to the usage represented by the candidate distribution allocation scheme and the cost for the fixed period.

16. The method of claim 15, wherein the cost function is further parameterized using time periods, each time period being associated with a capacity band and a cost factor, wherein the cost for the entire time period is calculated as a weighted sum of each time period.

17. The method of claim 1, wherein the cost function is parameterized using a time period and a plurality of capacity bands, each of which is associated with a cost factor, and calculating data distributed over a fixed period of time that includes the candidate distribution allocations, determining a cost factor by reference to a capacity band, and calculating a cost value for the candidate distribution allocation from the data and the cost factor.

18. The method of claim 17, wherein the cost function is further parameterized using a time period and a volume band, wherein each of the volume bands is associated with a cost factor, and the associated cost factor is determined by reference to the volume band and the time period.

19. The method of claim 1 wherein the cost function is parameterized using a cost factor and a time period, and the usage represented by the candidate allocations is calculated as a proportion of the total capacity over the time period, and a cost value for the candidate allocation is calculated as a function of the proportion and the cost factor.

20. The method of claim 1, wherein the one or more other objectives comprise: the cost is minimized; or minimizing the time to the end of the distribution of the audio video asset; or minimizing the duration of the distribution of the audio video asset.

21. The method of claim 20, the calculating the score for the candidate distribution allocation comprising:

for the one or more other targets, obtaining a target weight, and modifying a standard value of the target by multiplying the standard value by the target weight, thereby producing a set of weighted values; and

summing the set of weighted values to produce the score.

22. An apparatus for scheduled distribution of audio video assets, the apparatus comprising:

means for receiving instructions, each instruction specifying an audio video asset to be distributed and a distribution destination for the audio video asset, wherein a distribution destination represents one or more physical distribution recipients;

means for determining a distribution path available for distributing the audio video asset to the distribution destination, wherein the determining comprises: for each distribution path, matching a distribution receiver associated with the distribution capability to a distribution source represented by a distribution option according to one or more criteria of a distribution scheme representing the distribution technology;

means for obtaining a set of path capacity timelines for the distribution paths, wherein the path capacity timelines in the set of path capacity timelines each model an amount of available capacity that varies over time;

means for processing the path capacity timeline to produce one or more distribution path capacities;

means for applying an allocation algorithm to the distribution path capacities to generate candidate distribution allocations, wherein candidate distribution allocations each include one or more time periods during which a defined amount of capacity can be allocated for distribution of the audio video asset;

means for applying a cost function to the candidate distribution allocations to produce cost values, wherein the cost values each represent a cost of distributing the audio video asset according to the candidate distribution allocations;

means for calculating a score for the candidate distribution allocation dependent on the cost value for the candidate distribution allocation and one or more other objectives;

means for selecting the candidate distribution allocation with the lowest score to produce a selected candidate distribution allocation; and

means for distributing the audio video asset according to the selected candidate distribution allocation scheme,

the means for processing the path capacity timeline to generate one or more distribution path capacities comprises: means for minimizing available capacity on the set of path capacity timelines or maximizing unavailable capacity on the set of path capacity timelines, and means for comparing the result of the minimizing or maximizing to a capacity limit.