HK1117680A - Methods and apparatus for scheduling of content delivery over a distribution network - Google Patents

Abstract

A method is provided for scheduling a presentation for delivery over a distribution network. The method comprises generating a contact window that comprises a selected time duration, performing an allocation cycle to allocate the presentation to the contact window, determining whether the presentation can be allocated, adjusting the selected time duration of the contact window if the presentation cannot be allocated, and repeating said performing, determining and adjusting until the presentation can be allocated.

Description

Method and apparatus for scheduling content delivery over a distributed network

Claiming priority in accordance with 35 U.S.C. § 119

This patent application claims priority from provisional application No. 60/660,740 entitled "a METHOD AND APPARATUS for SERVICE PLANNING AND ANALYSIS" filed on 10.3.2005, AND assigned to the present assignee AND expressly incorporated herein by reference.

Technical Field

The present application relates generally to the operation of data networks, and more particularly, to methods and apparatus for service planning and analysis.

Background

Data networks, such as wireless communication networks, must make a trade-off between services tailored for a single terminal and services provided to a large number of terminals. For example, distributing content to a large number of mobile terminals (subscribers) is a complex problem. This is particularly true for mobile terminals that communicate using relatively slow radio communication links. Therefore, it is very important that a content provider can efficiently deliver content to various mobile terminals.

In current content delivery/media distribution systems, a content provider delivers a presentation (presentation) on a network resource. However, the amount of bandwidth available to deliver a presentation may vary due to network loading. Typically, the device obtains the selected presentation by contacting the distribution system. However, when a large number of devices attempt to obtain content at the same time, various scheduling problems arise. For example, if there is insufficient bandwidth to deliver a presentation, it may be difficult for the device to successfully obtain the presentation. Network delivery performance may be poor and bandwidth wasted because current delivery systems fail to account for network load, the number of devices in the system, the number of presentations to support, and other network characteristics.

Accordingly, there is a need for a system that operates to flexibly and efficiently schedule content for delivery to devices on a distribution network, where factors such as the number of services to be supported, the number of subscribers, network load, and other network characteristics have been considered.

Disclosure of Invention

In one or more embodiments, a Service Planning and Analysis (SPA) system is provided that operates to provide a flexible and efficient system for planning, scheduling, and delivering content over a distribution network.

In one aspect, a method for scheduling a presentation for delivery over a distribution network is provided. The method comprises the following steps: generating a contact window comprising a selected duration; executing an assignment loop to assign the presentation to the contact window; determining whether the presentation can be assigned; adjusting the selected duration of the contact window when the presentation cannot be assigned; and repeating the performing, determining, and adjusting until the presentation can be assigned.

In another aspect, an apparatus for scheduling presentations for delivery over a distribution network is provided. The apparatus comprises logic configured to determine one or more parameters. The apparatus also comprises logic configured to process the one or more parameters to perform a method comprising: generating a contact window comprising a selected duration; executing an assignment loop to assign the presentation to the contact window; determining whether the presentation can be assigned; adjusting the selected duration of the contact window when the presentation cannot be assigned; and repeating the performing, determining, and adjusting until the presentation can be assigned.

In another aspect, an apparatus for scheduling presentations for delivery over a distribution network is provided. The apparatus comprises: means for generating a contact window comprising a selected duration; and means for executing an assignment loop to assign the presentation to the contact window. The apparatus further comprises: means for determining whether the presentation can be assigned; and means for adjusting the selected duration of the contact window when the presentation cannot be assigned. The apparatus also includes means for repeating the performing, determining, and adjusting until the presentation can be assigned.

In another aspect, a computer-readable medium is provided having a computer program which, when executed by at least one processor, is operative to schedule a presentation for delivery over a distribution network. The computer program includes: instructions for generating a contact window comprising a selected duration; and instructions for executing an assignment loop to assign the presentation to the contact window. The computer program further comprises: instructions for determining whether the presentation can be allocated; instructions for adjusting the selected duration of the contact window when the presentation cannot be assigned; and instructions for repeating the executing, determining, and adjusting until the presentation can be allocated.

In another aspect, at least one processor is provided that is configured to perform a method for scheduling a presentation for delivery over a distribution network. The method comprises the following steps: generating a contact window comprising a selected duration; and executing an assignment loop to assign the presentation to the contact window. The method further comprises the following steps: determining whether the presentation can be assigned; adjusting the selected duration of the contact window when the presentation cannot be assigned; and repeating the performing, determining, and adjusting until the presentation can be assigned.

Other aspects of the embodiments will be appreciated upon review of the brief description of the drawings, detailed description, and claims set forth herein.

Drawings

The foregoing aspects of the embodiments described herein will be more readily understood by reference to the following detailed description, taken in conjunction with the accompanying drawings, in which:

figure 1 shows a network including one embodiment of an SPA system.

Figure 2 shows one embodiment of a content delivery system that includes one embodiment of an SPA system.

FIG. 3 shows one embodiment of SPA logic for use in embodiments of the SPA system.

Fig. 4 shows a chart to illustrate sector traffic for an embodiment of the SPA system.

Fig. 5 illustrates the relationship between contact windows and delivery windows for use in embodiments of SPA systems.

Fig. 6 shows a schedule to illustrate the manner in which presentations are assigned priorities in an embodiment of the SPA system.

FIG. 7 shows one embodiment of a method to provide a scheduling algorithm for use in embodiments of the SPA system.

Fig. 8-10 show graphs that respectively illustrate three scheduling scenarios that may occur during operation of the method shown in fig. 7.

FIG. 11 shows one embodiment of a method to provide a scheduling algorithm for use in embodiments of the SPA system that utilizes a uniformity factor to schedule content.

12-14 show diagrams to illustrate the operation of the method shown in FIG. 11.

FIG. 15 shows one embodiment of an SLU used in embodiments of the SPA system.

FIG. 16 shows one embodiment of SPA logic used in an embodiment of a SPA system.

Detailed Description

In one or more embodiments, a Service Planning and Analysis (SPA) system is provided that operates to provide a flexible and efficient system for planning, scheduling, and delivering content to authorized devices over a distribution network. The system is particularly well suited for use in a wireless network environment, but may also be used in any type of network environment, including but not limited to, a communications network, a public network (e.g., the Internet), a private network (e.g., a Virtual Private Network (VPN)), a local area network, a wide area network, a remote network, or any other type of data network.

Fig. 1 shows a network 100 that includes one embodiment of an SPA system. Network 100 includes a content delivery system 102 that operates to distribute content over a distribution network 104. In one embodiment, the content delivery system 102 delivers content in the form of a presentation, the presentation being associated with one or more services. The network 104 may include any type of wired and/or wireless network. The network 104 communicates with various devices 106. Devices 106 include, for example, PDA108, mobile phone 110, and notebook computer 112. The network 104 communicates with the device 106 using a wireless communication link 114, which wireless communication link 114 may include any suitable wireless communication technology. Thus, the distribution network 104 may be operable to deliver content to authorized devices, which may include any type or number of authorized devices.

The content delivery system 102 includes one or more servers, including a server 116, the server 116 being operative to deliver content having a scheduled presentation form over the network 104. For example, the content delivery system communicates with the network using communication link 124, communication link 124 comprising any suitable type of communication technology. The content delivery system also includes SPA logic 118 that operates to provide service planning and analysis to allow the content delivery system 102 to efficiently plan, schedule, and deliver content over the network 104.

In one embodiment, SPA logic 118 provides a central point for scheduled content delivery. Embodiments of SPA logic 118 provide the following three primary functions:

1. scheduling a presentation associated with a service

2. Calculating total memory required for a service

3. A duration of availability for a presentation is derived.

Using SPA logic 118, an operator may determine how many services the network 104 is capable of supporting and generate a contact window for each scheduled presentation associated with a service. For example, the contact window defines a time interval during which content is available to authorized devices on the network 104. In one embodiment, the contact window is sent to the device 106 via a system information update. Thus, the subscribing device uses the contact window to determine when to contact the network 104 to retrieve the selected presentation. In one embodiment, the SPA logic 118 contains a content delivery scheduling algorithm for scheduling presentations and deriving associated contact windows. A more detailed description of the scheduling algorithm is provided in another part of this document.

In one embodiment, SPA logic 118 calculates the total amount of memory required on the device for a device user to subscribe to a service. The calculation has taken into account whether a buffering of the presentation is required. The memory requirements are also sent to the devices 106 so each device can determine whether its memory is sufficient for a subscription for the service. In one embodiment, SPA logic 118 calculates an availability duration value that indicates a duration of time for which a presentation is available for viewing by a user.

In one embodiment, SPA logic 118 operates in an un-networked mode to allow an operator to perform hypothesis analysis by trading off, for example, the number of services available versus the number of content updated daily, and to determine which best achieves the desired system performance, service model, and/or revenue point.

In one embodiment, SPA logic 118 receives operator input via operator input 120 and outputs a "service queue (SLU)" 122. SLU 122 contains a list of services, along with the number of presentations that can be scheduled for each service and the contact window for each presentation. Once the operator is satisfied with the SLU 122, the operator can save it and specify the time at which the new SLU will begin to take effect.

Embodiments of SPA logic 118 may be used to execute an initial service plan prior to deploying content delivery system services. It may also be used after a period of time to determine whether a new service can be added without affecting existing services already provided with the subscriber. In addition, the operator may use the SPA logic 118 to modify the content update schedule for existing services in the system.

In one embodiment, SPA logic 118 operates in two modes as follows.

1. Non-network mode

2. Network mode

In the non-network mode, SPA logic 118 is disconnected from content delivery system 102 and does not rely on any information supplied by content delivery system 102. The operator inputs data to run the SPA logic 118 and save any SLUs output from the SPA logic 118 locally.

In network mode, SPA logic 118 establishes a connection with content delivery system 102 and reads and writes information to a delivery system database (not shown). In this mode, the operator can save the SLU in the database or read an existing SLU from the database.

In one embodiment, the operator may run SPA logic 118 in a non-network mode (i.e., offline) when planning for services to be provided by content delivery system 102. Once the operator is satisfied with the generated SLU, the operator may connect the SPA logic 118 to the content delivery system 102 and submit the SLU to the database.

In another embodiment, the operator may initially connect SPA logic 118 to content delivery system 102 in order to retrieve an existing SLU. After retrieving the SLU, the operator may use the SPA logic 118 in a non-network mode to study hypothetical situations, or may change or modify the SLU to generate a new SLU.

In one embodiment, SPA logic 118 uses operator input 120 to allow an operator to input parameters for generating SLUs. These parameters may have any suitable format and are categorized as "global parameters" and "service specific" parameters, as indicated below.

Global parameters

Average forward link sector traffic — this is the average of the forward link capacity per sector for a single antenna receiver.

Utilization of non-content delivery system traffic-percentage of sector capacity used by non-content delivery system traffic. This factor is entered every hour of the day. The unused percentage is the amount of sector capacity available for use by the content delivery system.

Number of sectors-the total number of sectors served by the content delivery system.

Service ID-identifying a service in a content delivery system

Service level List-list of sequentially ranked services

Service queue validation time-the time at which the SLU begins to validate.

Service specific parameters

Expected number of subscribers-the number of content delivery system subscribers expected for a certain service.

Maximum presentation size-the maximum size of a presentation, in kilobytes (Kbyte), this value is entered for each presentation.

Presentation watch time-the time at which the content delivery system Program Guide (PG) announces the available presentations for viewing. This value is entered for each presentation.

Presentation deadline-the time at which content is available at the content server for delivery to authorized devices. This value is entered for each presentation.

Acquisition deadline-a time value (in minutes) used to calculate the presentation deadline, calculated by subtracting the acquisition deadline from the presentation viewing time.

In one embodiment, the amount of "non-content delivery system traffic" sector utilization is entered every hour over a 24 hour period. The operator may obtain this information from the wireless system operator. The presentation information is entered during any period (e.g., 7 day, 30 day, 6 month, or one year period).

SPA logic 118 uses information entered by the operator to generate SLU 122. In one embodiment, SLU 122 includes the following information.

Contact window start time-the time at which the device can contact the network to download a presentation. This value is provided for each scheduled presentation. For unscheduled presentations, the contact window start time is set to zero.

Contact window duration-the time interval during which the device can remain in contact with the network to download a presentation. This value is provided for each scheduled presentation. For unscheduled presentations, the contact window duration is set to zero.

Subscription memory — the amount of memory required to subscribe to a service. In one embodiment, the amount of memory is determined only for successfully scheduled demonstrations.

Presentation availability duration-the time interval available for viewing a presentation. This value is provided for each presentation. For an unscheduled presentation, the presentation availability duration is set to zero.

In addition to the above outputs, the SLU 122 also contains all of the input parameters. The input parameters are maintained in case the operator wants to reload the existing SLU and modify any input parameters to conduct the hypothesis study.

Thus, embodiments of the SPA system operate to allow for the creation, storage, modification, activation, or use of SLUs to provide hypothetical cases. The SLU is used by the content delivery system to deliver scheduled content to authorized devices over a distribution network. Thus, the SPA system operates to provide a flexible and efficient system for planning, scheduling, and delivering content over a distribution network. It should be noted that network 100 illustrates only one implementation and that other implementations are possible within the scope of the embodiments.

Fig. 2 shows one embodiment of a content delivery system 200 that includes one embodiment of an SPA system. Content delivery system 200 includes one or more content providers 208, content server 210, database 206, service provisioning server 204, and service provisioning manager 202. In one embodiment, the SPA logic 212 is provided as part of the service provisioning server 204. For example, SPA logic 212 may be SPA logic 118 shown in fig. 1. It should be noted that SPA logic 212 may be stand-alone logic, or may be part of any other component of delivery system 200.

In one embodiment, SPA logic 212 operates to provide planning, scheduling, and analysis for use by other delivery system components so that content can be flexibly and efficiently delivered to authorized devices over a distribution network. For example, in one embodiment, the SPA system is operated to enable the following sequence of functions.

SPA logic 212 accepts operator input via service provisioning manager 202 to generate SLU 214. The operator may use SPA logic 212 to try various input parameter sets to determine which input parameter set produces the most desirable SLU.

2. Assuming an offline mode, once an acceptable SLU214 is obtained, the operator performs a service binding process for each service that the operator has created in the SLU214, and then the operator publishes the desired SLU214 to the database 206.

4. The operator accepts the SLU214 and if the SPA system is operating in network mode, the operator may submit the SLU214 into the database 206.

5. When SLU214 is successfully written to database 206, provisioning server 204 sends a message to content server 210 indicating that a new SLU214 is available.

6. Assume that the content provider has been notified in advance before the new SLU214 begins to take effect. The content server receives a program guide from the content provider 208 based on the new SLU 214. There may be more than one SLU in the database 206. However, only one SLU is active at any given time.

7. Content server 210 checks the information received from content provider 208 against SLU214 to ensure that content server 210 can use the presentation in accordance with the SLU in effect.

The notification of the new SLU214 is available for the content server 210 to determine when content should begin to be requested from the content provider 208 in order to meet the presentation deadline (the time required for the presentation to be available on the content server 210 for delivery to the device). In one embodiment, content server 210 periodically polls content provider 208 for new information such as program guides, presentations, and program recordings. For example, content server 210 may receive a presentation program guide days before it receives the program. Upon receiving the program guide, the content server 210 operates to verify the information in the program guide in accordance with the new SLU214 and set the appropriate time to request content from the content provider 208.

If the presentation received by content server 210 is larger than the maximum size indicated in SLU214, content server 210 will discard the presentation and issue a system alert. If the time that content server 210 receives the presentation from content provider 208 is later than the presentation deadline indicated in SLU214, content server 210 will issue a system alert. When a presentation is not available, a device in contact with the content delivery network will automatically reattempt retrieval based on any suitable retry schedule.

Thus, the SPA system operates to provide a flexible and efficient system for planning, scheduling, and delivering content over a distribution network. It should be noted that the delivery system 200 illustrates only one implementation and that other implementations are possible within the scope of the embodiments.

Fig. 3 shows one embodiment of SPA logic 300 for use in embodiments of SPA systems. For example, SPA logic 300 is suitable for use as SPA logic 118 shown in fig. 1 or SPA logic 212 shown in fig. 2. SPA logic 300 includes processing logic 302, scheduling logic 310, operator interface (I/F) logic 312, memory 314, and communication logic 316, all coupled to a data bus 318. In one embodiment, the scheduling logic 310 further includes availability logic 304, memory logic 306, priority logic 308.

In one or more embodiments, the processing logic 302 comprises a CPU, processor, gate array, hardware logic, memory elements, virtual machine, software, and/or any combination of hardware and software. Thus, processing logic 302 generally comprises logic for executing machine-readable instructions, as well as logic for controlling or communicating with one or more other functional elements of SPA logic 300 via internal data bus 318.

Communication logic 316 comprises hardware logic and/or software that operates to allow SPA logic 300 to transmit and receive data and/or other information with remote devices or systems using communication link 320. For example, in one embodiment, communication link 320 comprises any suitable type of communication link to allow SPA logic 300 to communicate with other entities of the content delivery system.

Memory 314 comprises any suitable memory device operable to store any type of information. For example, memory 308 may comprise RAM, flash memory, EEPROM, a hard disk, and/or any other type of storage device. In one embodiment, memory 314 operates to store one or more versions of SLU 322 that are generated as part of the operation of SPA logic 300.

The operator I/F312 comprises hardware logic and/or software that operates to allow the SPA logic 300 to interact with an operator to receive one or more parameters for use in embodiments of the SPA system. For example, in one embodiment, the operator I/F312 is used to receive operator input while the SPA logic 300 is operating in a non-network mode (i.e., offline or stand-alone). In non-network mode, the operator can input parameters to the SPA logic 300 to perform the hypothetical case.

The scheduling logic 310 comprises a CPU, processor, gate array, hardware logic, memory elements, virtual machine, software, and/or any combination of hardware and software. In one or more embodiments, scheduling logic 310 is operative to execute a scheduling algorithm to generate SLU 322. A more detailed description of the scheduling algorithm and SLU 322 is provided in another portion of this document.

The priority logic 308 comprises a CPU, processor, gate array, hardware logic, memory elements, virtual machine, software, and/or any combination of hardware and software. In one or more embodiments, priority logic 308 is operative to determine content priorities to allow scheduling logic 310 to schedule content presentations in a selected order. A more detailed description of the operation of priority logic 308 is provided in another portion of this document.

The memory logic 306 comprises a CPU, processor, gate array, hardware logic, memory elements, virtual machine, software, and/or any combination of hardware and software. In one or more embodiments, the memory logic 306 is operative to determine a memory requirement for the device to attempt to receive the content in the SLU. A more detailed description of the operation of the memory logic 306 is provided in another portion of this document.

The availability logic 304 comprises a CPU, processor, gate array, hardware logic, memory elements, virtual machine, software, and/or any combination of hardware and software. In one or more embodiments, the availability logic 304 is operative to determine an availability duration, which indicates a duration of time for which content is available for the device to receive. A more detailed description of the operation of the availability logic 304 is provided in another portion of this document.

During operation, SPA logic 300 is operative to perform one or more of the following functions.

1. Operator input is received via operator I/F312. The operator input may select the operating mode of SPA logic 300, or may provide global parameters, service specific parameters, or other parameters.

2. A content priority is determined for content to be delivered.

3. A contact window is generated for content delivery.

4. The scheduling algorithm is executed based on the content priority to generate an SLU for the content presentation.

5. Memory requirements are determined based on the SLU.

6. An availability duration for the presentation is determined.

In one embodiment, the SPA system comprises a computer program stored on a computer-readable medium having one or more program instructions ("program instructions") that, when executed by at least one processor (e.g., the processing logic 302), provide the functionality described herein. For example, the program instructions may be loaded into SPA logic 300 from a computer-readable medium that interfaces to SPA logic 300, such as a floppy disk, CDROM, memory card, flash memory device, RAM, ROM, or any other type of storage device or computer-readable medium. In another embodiment, the program instructions may be downloaded into the SPA logic 300 from an external device or network resource. The program instructions, when executed by the processing logic 302, provide embodiments of the SPA system as described herein.

Thus, SPA logic 300 operates to provide a flexible and efficient system for planning, scheduling, and delivering content over a distribution network. It should be noted that SPA logic 300 illustrates only one implementation and that other implementations are possible within the scope of the embodiments.

Sector traffic

Fig. 4 shows a graph 400 to illustrate sector traffic for an embodiment of an SPA system. Graph 400 illustrates the average sector traffic for each portion over a 24 hour period in two-dimensional boxes. The height of the box represents the average sector traffic and the width of the box represents the selected portion over a 24 hour period. Traffic that is "non-content delivery system" traffic for a 24 hour period is shown generally as shaded area 402. This is traffic due to other network systems or functions. The amount of bandwidth that the content delivery system can use to deliver content is shown at 404. This area represents the area of the box not occupied by the non-content delivery system traffic 402.

SPA scheduling algorithm

In one embodiment, scheduling logic 310 is operative to provide a scheduling algorithm for scheduling (i.e., packing) a number of presentations (objects) within the available sector bandwidth. In one embodiment, the scheduling algorithm derives one or more association windows based on assumptions about average sector traffic and sector capacity used by non-content delivery system traffic on average. For example, in a wireless network environment, forward link sector traffic varies with channel conditions and the type of traffic being sent on the forward link. In general, maximum forward link sector traffic occurs when all sector users are FTP users and they want to download an infinitely large file. This particular traffic model can produce higher sector traffic than a traffic model that mixes FTP users, WAP users, and HTTP users, since all users receive only data. Since the traffic mix during the program download may not be predictable, the algorithm assumes an average value for sector traffic. This average is assumed to be constant over a 24 hour scheduling period and is the same for all sectors serving the content delivery system. It should be noted, however, that embodiments of the algorithm can be adjusted to utilize multiple sector traffic values over a 24 hour period, and/or to provide different traffic values for different sectors serving the content delivery system.

Since the content delivery system may not be the only one data service using sector capacity, the scheduling algorithm is operated to account for other non-content delivery system traffic that is competing in terms of forward link resources. In one embodiment, the operator enters the percentage of non-content delivery system traffic that utilizes sector capacity per hour. In one embodiment, the algorithm assumes that these values are the same for all sectors serving the content delivery system. In practice, the use of non-content delivery system traffic may differ for different sectors because the traffic load for traffic type mixes and non-content delivery system users is not the same. However, embodiments of the scheduling algorithm may operate without using sector specific information, as this information changes dynamically. Thus, in the preferred embodiment, the algorithm assumes that the average sector traffic and average usage of non-content delivery system traffic represents the entire network serving the content delivery system.

In one embodiment, the algorithm also assumes that the content delivery system subscribers are evenly distributed across all sectors serving the content delivery system. In general, it is expected that content delivery system subscribers will be more concentrated in some sectors than others, and that the number of subscribers per sector will vary dynamically over the course of a day. However, in the preferred embodiment, the scheduling algorithm is operative to provide only one content delivery schedule for the entire network. It should be noted, however, that in other embodiments, the algorithm may utilize sector specific information.

Algorithm annotation

In one or more embodiments, the SPA system provides a content delivery scheduling algorithm that utilizes one or more of the following parameters.

C: average sector traffic per hour

·N_s: total number of services

J: j service, j ∈ N_s

·N_p ^j: for the j service, the total number of presentations to be scheduled in a week time, j ∈ N_s

·P_i ^j: the presentation i belonging to the service of j,，j∈N_s

·K_i ^j: the maximum size of a presentation i belonging to the j service,，j∈N_s

·s_i ^j: demonstration P_i ^jThe start time of the contact window of (c),，j∈N_s

·e_i ^j: demonstration P_i ^jThe end time of the contact window of (c),and is

·: demonstration P_i ^jThe contact window of (a) is displayed,，j∈N_s

·v_i ^j: demonstration P_i ^jThe viewing time of (c). This is the time announced in the PG at which the subscriber can view the presentation,，j∈N_s

·d_i ^j: demonstration P_i ^jThe time-off of (a) is,，j∈N_s. This is the time required for a presentation to be available on the content server for delivery to the device

·: a delivery window. This definition may be used to schedule a presentation P_i ^jThe total time of the transfer of (a) is,，j∈N_s

·G_i ^j: delivering a demonstration P_i ^jThe total amount of forward air link resources required,，j∈N_s

·n^j: total number of subscribers to the service j, j ∈ N_s

Z: number of sectors serving a content delivery system service

B (k): percentage of non-content delivery system traffic in the kth hour, k ∈ {1, 2., 24)

Note that T_i ^jThe representation may be used to schedule a presentation P_i ^jTotal time of delivery of (1). Operation according to a scheduling algorithm and interval T_i ^jDuring periods of non-content delivery system traffic utilization, the following situations may arise.

1. Contact window W of program_i ^jIs P_i ^jIs less than or equal to the transmission window

2. Absence of schedulable programs P_i ^jThe contact window of (a), i.e.,

fig. 5 illustrates the relationship between a contact window 502 and a delivery window 504 used in embodiments of the SPA system. Scenario 1 above describes the case where the algorithm can successfully schedule a presentation. It should be noted that the contact window 502 may be smaller than the delivery window 504, as shown in FIG. 5.

Case 2 above describes the transfer window T being specified_i ^jThe internal algorithm cannot schedule a presentation because other presentations have been scheduled in the same time interval or there is a large amount of non-content delivery system traffic within the delivery window. For example, in FIG. 5, T_iIs a pass window 504, where V_iIs equal to or greater than d_iAnd W is_iIs a contact window 502, where e_iIs equal to or greater than s_i. The delivery window 504 will generally exceed the contact window 502 in size to allow flexible delivery of the presentation.

Delivering a demonstration P_i ^jThe total forward air link resource required for each sector is G_i ^jThis is derived as follows.

For demonstration P_i ^jAnd i ∈ N_p，j∈N_s

The first term in the equation represents the P to be demonstrated_i ^jThe total forward air link resources (bytes) per sector required to deliver to all subscribers at once. Second term theta_i ⁱRepresentation for use with a presentation P_i ^jAdditional forward air link resources retransmitted to each sector of the subset of devices that did not receive content in the first transmission. Will assume a value theta_i ⁱIs zero.

In one embodiment, the scheduling algorithm may schedule N if the following characteristics hold_i ^j(*j∈N_s)：

The above equation represents: all presentations may be scheduled if the total amount of content delivery system traffic is less than or equal to the total amount of unused sector bandwidth during the selected scheduling period. It should be noted that due to the limiting factor associated with when a presentation should be delivered (delivery deadline), not all presentations may be scheduled even though the above characteristics hold.

Priority level of presentation

In one embodiment, the algorithm schedules presentations in order of presentation priority. For example, priority logic 308 operates to determine a presentation priority for use by a scheduling algorithm in scheduling a presentation. The presentation with the higher priority level is scheduled first, and then the presentation with the lower priority level is scheduled. In one embodiment, the priority logic 308 operates to prioritize presentations in order of service level. For example, if the service includes more than one presentation, the presentation with the earliest presentation view time is assigned a higher priority. It should be noted that the scheduling algorithm is operable to rank presentations based on any characteristic or condition and assign priorities accordingly, affecting the scheduling order.

Fig. 6 shows a schedule 600 to illustrate the manner in which presentations are assigned priorities in an embodiment of the SPA system. For example, the priorities shown in the schedule 600 are generated by the priority logic 308. The schedule 600 shows presentation times for three services (i.e., service #1, service #2, and service # 3). In this example, the services are ranked according to a service ranking order. Service #1 is ranked highest, then service #2, and then service # 3. Service #1 has three presentations with viewing times of 7:00, 9:00, and 11: 00. The first presentation of service #1 is assigned presentation priority one (1), as shown at 602, because it belongs to the service with the highest service level and has the earliest viewing time. The second presentation of service #3 has the lowest priority (as shown at 604) because it belongs to the service with the lowest service level and has the latest viewing time. The remaining presentations are prioritized in a similar manner. It should also be noted, however, that schedule 600 illustrates only one technique for setting priorities, and the SPA system may operate to assign priorities using any other suitable technique or criteria.

Examples of algorithmic operations

The following is an example of the operation of one embodiment of the scheduling algorithm provided by one embodiment of the SPA system. For example, scheduling logic 310 is operative to provide a scheduling algorithm, the operation of which is described below. In one or more embodiments, the scheduling algorithm is configured to generate a content delivery schedule for achieving one or more of the following purposes.

1. A contact window is generated as close as possible to the viewing time. The algorithm starts from the viewing time and allocates resources until it reaches the presentation deadline. This allows the latest content to be delivered as close to viewing time as possible.

2. A schedule is generated to keep the contact window continuous and uniform in time. Since any subscribing device can "request" content at any time while the contact window is open, the content should be evenly distributed across the delivery window in order for the system to meet the needs of any device.

3. The schedule is generated so that the contact window is kept as wide as possible. The wider the contact window, the more evenly the content can be distributed. This in turn will result in a more even load of network resources. By avoiding load peaks, the load on the network is evenly distributed, thereby providing a higher success rate of delivery.

In this example, the scheduling algorithm is configured to run at half-hour time granularity, one megabyte (Mbyte) scheduling units, within each allocation cycle. It should be noted, however, that the scheduling algorithm may be configured to run at different time granularities and memory unit sizes. Since the time granularity is set to half an hour, the presentation viewing time is rounded to half an hour in the schedule. In one embodiment, the presentation is first ranked based on a selected criteria. For example, priority logic 308 is operative to rank presentations as described above. The scheduling algorithm then operates as described in the following method.

FIG. 7 shows one embodiment of a method 700 to provide a scheduling algorithm for use in embodiments of the SPA system. For example, in one embodiment, the method 700 is provided by the operation of the scheduling logic 310, and the method 700 is described below with reference to the scheduling logic 310. Method 700 assumes the following parameters.

Contact window start time: si

Contact window end time: ei

Program acquisition duration: di

Program viewing time: vi

A transmission window: ti-vi-di

Granularity unit: tu

The method begins at block 702, where selected parameters are initialized. For example, the contact window start time is set as the program acquisition deadline and the contact window end time is set as the program viewing time. Further, the particle size time was set to thirty minutes.

At block 704, one or more allocation cycles are performed until the full size presentation has been distributed in time units within the contact window. In one embodiment, the allocation cycle begins at the contact window end time and proceeds to the contact window start time. The algorithm applies a scheduling unit (byte) for each time unit within the contact window in each allocation cycle. The process is repeated until the full size presentation is distributed in time units within the contact window.

At block 706, a test is performed to determine if a full size presentation can be allocated across the entire contact window. If the presentation can be assigned, the presentation is successfully scheduled and the method ends at block 708. If the presentation cannot be assigned over the entire contact window, the method proceeds to block 710.

At block 710, the contact window start time is increased by the size of the granularity unit. For example, the contact window start time is increased by thirty minutes.

At block 712, a test is performed to determine if the contact window start time is equal to the contact window end time. If the contact window start time is not equal to the contact window end time, the method returns to block 704 to retry the scheduling process. If the contact window start time is equal to the contact window end time, the method proceeds to block 714.

At block 714, the contact window end time is reduced by the size of the granularity time. For example, the contact window end time is reduced by thirty minutes.

At block 716, a test is performed to determine if the contact window end time is equal to the program acquisition deadline. If the contact window end time is equal to the program acquisition deadline, the presentation cannot be scheduled and the method proceeds to block 718. If the contact window end time is not equal to the program acquisition deadline, the method proceeds to block 720.

At block 720, the contact window start time is set to the program acquisition deadline. The method then proceeds to block 704 to retry the scheduling process.

Thus, the method 700 operates to provide one embodiment of a scheduling algorithm for use in embodiments of SPA systems. It should be noted that the method 700 is just one implementation and that other implementations are possible within the scope of the embodiments. For example, any of the functions in the method 700 may be added, changed, deleted, modified, combined, or adjusted within the scope of the embodiments.

Fig. 8-10 show graphs that respectively illustrate three scheduling scenarios that may occur during operation of the method 700. All the cases illustrate that the scheduling algorithm provided by the method 700 applies a scheduling unit (byte) to each time unit within the contact window for each allocation cycle from the end time of the contact window until the start time of the contact window. This process is repeated until all of the media minutes have been completely and successfully allocated. The remaining media minutes are evenly distributed over time units with more resources allocated to the content during the last allocation cycle.

Fig. 8 illustrates a first scenario in which the scheduling algorithm provided by method 700 is unable to allocate content in time units from 5:30 to 6:00 on a first allocation cycle, as shown at 802. The scheduling algorithm provided by method 700 then moves the contact window start time to 6:00 and repeats the scheduling function. This process is repeated until all media minutes are allocated on the new contact window, or until all media minutes cannot be scheduled.

Fig. 9 illustrates a second scenario in which the scheduling algorithm provided by method 700 succeeds after the contact window end time has shifted from 9:30 to 8: 00. For example, the content window end time is transferred when content is not allocable within a time unit from 8:00 to 8:30, as shown at 902.

Fig. 10 illustrates a third scenario, where the scheduling algorithm provided by method 700 succeeds after changing both the contact window start time and the contact window end time accordingly to allow all media minutes to be allocated on the new contact window. For example, as shown at 1002, content may not be allocated in time units from 5:00 to 5:30, so the contact window start time is shifted to 5: 30. Further, as shown at 1004, content may not be allocated in time units from 8:00 to 8:30, so the contact window end time is shifted to 8: 00.

Uniformity factor

The scheduling algorithm provided by the method 700 does not take into account the uniformity factor. Each device is given a contact window that indicates the time interval during which the device can contact the network to receive content. The device selects random times evenly distributed between the contact window start time and the contact window end time within which to contact the network. Thus, the network resource allocation is uniformly distributed within the contact window. In a first round of operation of the algorithm provided by method 700, the algorithm attempts to allocate network resources within a delivery window. Once the allocation is successful, the algorithm will go through a second pass to allocate the resources evenly over the resulting contact window.

In one embodiment, the contact window is selected to be non-uniform. The server is then operated to communicate the non-uniform nature of the window to the device. Thus, the device is operative to weight the non-uniformity of the contact window when connecting to the server. In one embodiment, a non-uniform contact window is more bandwidth efficient because more presentations can be scheduled for delivery.

FIG. 11 shows one embodiment of a method 1100 to provide a scheduling algorithm for use in embodiments of the SPA system that utilizes a uniformity factor to schedule content. For example, the method 1100 represents how uniformity may be achieved assuming a uniformity factor of 0.8. In one embodiment, the scheduling logic 310 is operative to provide the functionality of the method 1100 described below.

At block 1102, a time cell is selected within the contact window having the greatest deviation. At block 1104, a test is performed to determine if the selected time cell is at the edge of the contact window. If the time cell is at the edge of the contact window, the method proceeds to block 1106. If the time cell is not at the edge of the contact window, the method proceeds to block 1108.

At block 1106, the bytes associated with the selected time cell are evenly distributed over other time cells within the contact window. The contact window start time or contact window end time is also updated accordingly.

At block 1110, a test is performed to determine if the allocation was successful. If the allocation is successful, the method proceeds to block 1112. If the assignment is unsuccessful, the method ends at block 114 because the program cannot be scheduled.

At block 1112, a test is performed to determine if the deviation over the contact window is less than (1-uniformity factor). For example, assume a uniformity factor of 0.8. If the deviation over the contact window is not less than (1-uniformity factor), the method returns to block 1102. If the deviation over the contact window is less than (1-uniformity factor), the program is successfully scheduled and the method ends at block 1116.

At block 1108, the value of parameter (A) is set equal to all time cell bytes to the left of (including) the selected time cell. At block 1118, the value of parameter (B) is set equal to all time unit bytes to the right of (including) the selected time unit.

At block 1120, a test is performed to determine if parameter a is less than or equal to parameter B. If parameter A is less than or equal to parameter B, the method proceeds to block 1124. If parameter A is not less than or equal to parameter B, the method proceeds to block 1122.

At block 1124, all bytes in A are evenly allocated to the right side of the selected time cell and the contact window start time is updated accordingly. At block 1126, a test is performed to determine if the allocation was successful. If the allocation is successful, the method proceeds to block 1112. If the allocation is not successful, the method proceeds to block 1130.

At block 1130, all bytes are allocated to the other side of the selected time cell and the contact window is updated accordingly. At block 1132, a test is performed to determine whether the allocation was successful. If the allocation is successful, the method proceeds to block 1112. If the assignment is unsuccessful, the program cannot be scheduled and the method ends at block 1114.

At block 1122, all bytes in B are evenly allocated to the left side of the selected time cell and the contact window end time is updated accordingly. At block 1128, a test is performed to determine whether the allocation was successful. If the allocation is successful, the method proceeds to block 1112. If the allocation is not successful, the method proceeds to block 1130.

Thus, the method 1100 operates to provide one embodiment of a scheduling algorithm for use in embodiments of SPA systems, where the scheduling algorithm utilizes a selected uniformity factor. It should be noted that the method 1100 is just one implementation and that other implementations are possible within the scope of the embodiments. For example, any of the functions in the method 1100 may be added, changed, deleted, modified, combined, or adjusted within the scope of the embodiments.

Fig. 12-14 show diagrams to illustrate the operation of the method 1100 shown in fig. 11.

FIG. 12 shows a chart to illustrate the operation of method 1100 when the deviation over the contact window is greater than (1-uniformity factor). Thus, cell "a 6" is the selected time cell (as shown at 1202) and is determined during the operations of block 1102 of method 1100.

After the time cell "a 6" is selected, the values of parameter a and parameter B are calculated, which correspond to the operations of block 1108 and block 1118, respectively, of method 1100. Therefore, the values of a and B can be expressed as follows.

A＝a1+a2+a3+a4+a5+a6

B＝a6+a7+a8

It will be assumed that A > B, such that all time cells in B are evenly allocated to the left of cell a6, the allocation corresponding to the operations of block 1122 of method 1100.

FIG. 13 shows a chart to illustrate how the entire time cell in B is evenly distributed to the left of cell a 6. For example, time cells a6, a7, and a8 are allocated into boxes b1, b2, b3, b4, and b5 to the left of a6, as shown at 1302. In addition, the contact window end time is updated, as shown at 1304.

After this successful assignment, the deviation over the contact window is still greater than (1-uniformity factor). This determination corresponds to the test performed at block 1112 of method 1100. Cell "b 3" is then selected when the function at block 1102 of method 1100 is performed.

After cell "B3" is selected, the values of parameter a and parameter B are calculated, which correspond to the operations of block 1108 and block 1118, respectively, of method 1100. Therefore, the values of a and B can be expressed as follows.

A＝b1+b2+b3

B＝b3+b4+b5

It will be assumed that a < ═ B, such that all time cells in a are evenly allocated to the right of cell B3, the allocation corresponding to the operations of block 1124 of method 1100.

FIG. 14 shows a chart illustrating how all of the time cells in A are evenly distributed to the right of cell b3, where the distribution corresponds to the operations of block 1124 of method 1100. For example, time cells b1, b2, and b3 are allocated into boxes c4 and c5 to the right of b3, as shown at 1402. In addition, the start time of the contact window is updated, as shown at 1404.

After successful assignment, the deviation over the contact window is less than (1-uniformity factor). Thus, the presentation is successfully scheduled, which corresponds to block 1116 of method 1100.

Deriving subscribed memory and availability duration

In one embodiment, the memory logic 306 is operative to determine the subscribed memory required for each service. The subscribed memory for each service is the total amount of memory available on the device that is needed before the device user can subscribe to the service. The number of presentations that each service may store on the device depends on the buffer flag. For example, the buffer flag may have a value ranging from 1 to N. In one embodiment, the buffer flag determines how many demonstrations may be stored on the device at any given time, and thus it indicates the amount of memory that must be available on the device during a selected scheduling period.

In one embodiment, the availability logic 304 is operative to determine an availability duration describing a duration of time for which the presentation is available for viewing. In one embodiment, the availability duration is based on the buffer flag.

FIG. 15 shows one embodiment of SLU 1500 used in an embodiment of a SPA system. For example, SLU 1500 may be SLU 322 shown in FIG. 3. In one embodiment, SLU 1500 is generated by scheduling logic 310.

SLU 1500 includes one or more instances of each presented parameter sequence. In one embodiment, the sequence of parameters includes a contact window start time 1502, a contact window duration 1504, a subscribed-to memory size 1506, an availability duration 1508, and an associated parameter 1510. For example, the associated parameters 1510 may include parameters entered by an operator to initialize a scheduling algorithm. It should be noted that SLU 1500 represents only one implementation and that other implementations are possible within the scope of the embodiments.

Figure 16 shows one embodiment of SPA logic 1600 used in embodiments of SPA systems. The SPA logic 1600 includes means for generating a contact window 1602, means for performing an assignment 1604, means for determining 1606, means for adjusting 1608, and means for repeating 1610.

In one embodiment, the means for generating 1602 includes hardware and/or software and is operative to generate a contact window that includes a selected duration.

In one embodiment, the means for performing an assignment 1604 comprises hardware and/or software and is operative to perform an assignment loop in order to assign the presentation to the contact window.

In one embodiment, means for determining 1606 comprises hardware and/or software and is operative to determine whether a presentation can be distributed.

In one embodiment, the means for adjusting 1608 comprises hardware and/or software and is operative to adjust the selected duration of the contact window when the presentation cannot be assigned.

In one embodiment, the means for repeating 1610 comprises hardware and/or software and is operative to control the devices 1604, 1606, and 1608 to repeat their operations until a presentation can be distributed.

It should be noted that SPA logic 1600 represents only one implementation and that other implementations are possible within the scope of the embodiments.

The various illustrative logics, logical blocks, modules, and circuits described in connection with the embodiments disclosed herein may be implemented or performed with a general purpose processor, a Digital Signal Processor (DSP), an Application Specific Integrated Circuit (ASIC), a Field Programmable Gate Array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general purpose processor may be a microprocessor, but in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. A software module may reside in RAM memory, flash memory, ROM memory, EPROM memory, EEPROM memory, registers, hard disk, a removable disk, a CD-ROM, or any other form of storage medium known in the art. An exemplary storage medium is coupled to the processor such the processor can read information from, and write information to, the storage medium. In the alternative, the storage medium may be integral to the processor. The processor and the storage medium may reside in an ASIC. The ASIC may reside in a user terminal. In the alternative, the processor and the storage medium may reside as discrete components in a user terminal.

The description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments may be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments, e.g., in an instant messaging service or any general wireless data communication applications, without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. The word "exemplary" is used exclusively herein to mean "serving as an example, instance, or illustration. Any embodiment described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments.

Thus, while embodiments of the SPA system have been illustrated and described herein, it will be appreciated that various changes can be made to the embodiments without departing from their spirit or essential characteristics. Accordingly, the disclosures and descriptions herein are intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.

Claims (15)

1. A method for scheduling a presentation for delivery over a distributed network, the method comprising:

generating a contact window comprising a selected duration;

executing an assignment loop to assign the presentation to the contact window;

determining whether the presentation can be assigned;

adjusting the selected duration of the contact window if the presentation cannot be assigned; and repeating the performing, determining, and adjusting until the presentation can be assigned.

2. The method of claim 1, wherein the performing comprises:

defining the contact window to include one or more time units; and

allocating a selected portion of the presentation to available bandwidth in each of the one or more time units until the presentation is allocated.

3. The method of claim 1, further comprising reallocating the presentation within the contact window to achieve a selected uniformity factor.

4. An apparatus for scheduling a presentation for delivery over a distributed network, the apparatus comprising:

logic configured to determine one or more parameters; and

logic configured to process the one or more parameters to perform a method comprising:

generating a contact window comprising a selected duration;

executing an assignment loop to assign the presentation to the contact window;

determining whether the presentation can be assigned;

adjusting the selected duration of the contact window if the presentation cannot be assigned; and repeating the performing, determining, and adjusting until the presentation can be assigned.

5. The apparatus of claim 4, wherein the performing comprises:

defining the contact window to include one or more time units; and

allocating a selected portion of the presentation to available bandwidth in each of the one or more time units until the presentation is allocated.

6. The apparatus of claim 4, further comprising logic configured to redistribute the presentation within the contact window to achieve a selected uniformity factor.

7. An apparatus for scheduling a presentation for delivery over a distributed network, the apparatus comprising:

means for generating a contact window comprising a selected duration;

means for executing an assignment loop to assign the presentation to the contact window;

means for determining whether the presentation can be assigned;

means for adjusting the selected duration of the contact window if the presentation cannot be assigned;

and

means for repeating the performing, determining, and adjusting until the presentation can be assigned.

8. The apparatus of claim 7, wherein the means for performing comprises:

means for defining the contact window to include one or more time units; and

means for allocating a selected portion of the presentation to available bandwidth in each of the one or more time units until the presentation is allocated.

9. The apparatus of claim 7, further comprising means for reallocating the presentation within the contact window to achieve a selected uniformity factor.

10. A computer-readable medium having a computer program which, when executed by at least one processor, operates to schedule a presentation for delivery over a distribution network, the computer program comprising:

instructions for generating a contact window comprising a selected duration;

instructions for executing an assignment loop to assign the presentation to the contact window;

instructions for determining whether the presentation can be allocated;

instructions for adjusting the selected duration of the contact window if the presentation cannot be assigned;

and

instructions for repeating the executing, determining, and adjusting until the presentation can be allocated.

11. The computer program of claim 10, wherein the instructions for executing comprise:

instructions for defining the contact window to include one or more time units; and

instructions for allocating a selected portion of the presentation to available bandwidth in each of the one or more time units until the presentation is allocated.

12. The computer program of claim 10, further comprising instructions for reallocating the presentation within the contact window to achieve a selected uniformity factor.

13. At least one processor configured to perform a method for scheduling a presentation for delivery over a distribution network, the method comprising:

generating a contact window comprising a selected duration;

executing an assignment loop to assign the presentation to the contact window;

determining whether the presentation can be assigned;

adjusting the selected duration of the contact window if the presentation cannot be assigned; and repeating the performing, determining, and adjusting until the presentation can be assigned.

14. The method of claim 13, wherein the performing comprises:

defining the contact window to include one or more time units; and

allocating a selected portion of the presentation to available bandwidth in each of the one or more time units until the presentation is allocated.

15. The method of claim 13, further comprising reallocating the presentation within the contact window to achieve a selected uniformity factor.