Messaging protocol for interactive delivery system Number:7,146,628 from the United States Patent and Trademark Office (PTO) owispatent Efficient messaging techniques that facilitate interactive program guide (IPG) delivery and allow a terminal to specifically designate requested items of information from a server. The IPG can be provided via a number of IPG pages, with each page including a number of defined regions. In one method, selection for a particular region of a particular page is received at a terminal and a determination is made whether the selected region is currently received. If the answer is no, a request for the selected region is generated and sent to a server. The request can conform to a particular message format that includes a number of fields, e.g., a region ID field that identifies the selected region, a subtype field that identifies a particular type, a time slot field that identifies a specific time slot, and a page offset field that identifies a specific page from among many.<H interactive, Messaging, Messaging, proto, 7146628.html, Patent, pto, 7146628

Title: Messaging protocol for interactive delivery system

Abstract: Efficient messaging techniques that facilitate interactive program guide (IPG) delivery and allow a terminal to specifically designate requested items of information from a server. The IPG can be provided via a number of IPG pages, with each page including a number of defined regions. In one method, selection for a particular region of a particular page is received at a terminal and a determination is made whether the selected region is currently received. If the answer is no, a request for the selected region is generated and sent to a server. The request can conform to a particular message format that includes a number of fields, e.g., a region ID field that identifies the selected region, a subtype field that identifies a particular type, a time slot field that identifies a specific time slot, and a page offset field that identifies a specific page from among many.

Patent Number: 7,146,628 Issued on 12/05/2006 to Gordon, et al.

Inventors: Gordon; Donald F. (Los Altos, CA), Edmonds; Jeremy S. (Redwood City, CA), Comito; John P. (Redwood City, CA), Bayrakeri; Sadik (Foster City, CA)
Assignee: Sedna Patent Services, LLC (Philadelphia, PA)

Appl. No.: 09/708,809

Filed: November 8, 2000

Current U.S. Class: 725/54 ; 725/118; 725/39; 725/43; 725/98

Current International Class: G06F 3/00 (20060101); G06F 13/00 (20060101); H04N 5/445 (20060101)

Field of Search: 725/39,40,50,121,43,52,54,98,114 348/461,563,731,564,569

References Cited [Referenced By]

U.S. Patent Documents


5481542	January 1996	Logston et al.
5844620	December 1998	Coleman et al.
6160545	December 2000	Eyer et al.
6563515	May 2003	Reynolds et al.

Primary Examiner: Vu; Ngoc
Attorney, Agent or Firm: Patterson & Sheridan, LLP

Claims

What is claimed is:

1. A method of communications for an interactive program guide (IPG), comprising: receiving, by a session manager from a terminal, a demand-cast request message for a particular region of a particular interactive program guide (IPG) page, the particular region being one of a plurality of regions, the regions including a guide region, a video region, an icon region, and a program description region, the particular IPG page being one of a plurality of IPG pages; sending, by the terminal to the session manager, a stream acquired message, when it is determined at the terminal that the particular region is currently received at the terminal; sending, by the session manager to a transport stream generator, a stream requested message, when the particular region is not currently received at the terminal; sending, by the session manager, to the transport stream generator, a stream acquired message, when the particular region is currently received at the terminal; generating, by the transport stream generator, a stream for the particular region, upon receiving the stream requested message from the session manager.

2. The method of claim 1, wherein demand-cast request message includes a plurality of fields and has a hierarchical structure, the fields including a first field that determines a particular format of remaining fields in the message format.

3. The method of claim 1, wherein the demand-cast request message includes a first field identifying the particular region in the particular IPG page.

4. The method of claim 3, wherein the particular region is the guide region and the demand-cast request message includes a second field identifying a particular filter selected from among a plurality of filters.

5. The method of claim 4, wherein the plurality of filters include one or more filters selected from the group consisting of pay per view (PPV), favorites, movies, kids, and sports filters.

6. The method of claim 4, wherein the demand-cast request message further includes a third field identifying the particular IPG page.

7. The method of claim 6, wherein the third field includes a fourth field indicative of a particular time slot selected from among a plurality of time slots, wherein the selected time slot corresponds to a time period covered by the particular IPG page.

8. The method of claim 7, wherein the third field further includes a fifth field indicative of the particular IPG page selected from the IPG pages available for the selected time slot.

9. The method of claim 2, wherein the region is the video region and the demand-cast request message further includes a second field indicative of a particular type of video selected from among a plurality of video types.

Description

BACKGROUND OF THE INVENTION

The present invention relates to communications systems in general. More specifically, the invention relates to techniques to efficiently deliver interactive program guide (IPG) in a server-centric system.

Over the past few years, the television industry has seen a transformation in a variety of techniques by which its programming is distributed to consumers. Cable television systems are doubling or even tripling system bandwidth with the migration to hybrid fiber coax (HFC) cable plant. Customers unwilling to subscribe to local cable systems have switched in high numbers to direct broadcast satellite (DBS) systems. And, a variety of other approaches have been attempted focusing primarily on high bandwidth digital technologies, intelligent two-way set top terminals, or other methods of trying to offer service differentiated from standard cable and over-the-air broadcast systems.

With this increase in bandwidth, the number of programming choices has also increased. Leveraging off the availability of more intelligent set top terminals, several companies such as Starsight Telecast Inc. and TV Guide, Inc. have developed elaborate systems for providing an interactive listing of a vast array of channel offerings, expanded textual information about individual programs, and the ability to look forward to plan television viewing as much as several weeks in advance.

With this increase in the quantity of programming, it is a challenge to deliver program guide data to viewers in an efficient and effective manner. A large amount of resources (e.g., bandwidth) would normally be needed to continually transmit, for example, two weeks of programming for 200 channels. Therefore, efficient and effective techniques to deliver interactive program guide to a large number of viewers are highly desirable.

Moreover, the increased bandwidth has allowed service providers to offer various services such as regular programming, pay-per-view (PPV), video-on-demand (VOD), music channels, and so on. The large amount of programming offered by each of these services typically necessitates the use of a separate user interface especially adopted for the service. As more services are provided and the complexity of these services increases, the user interfaces becomes more complicated to implement and for users to navigate. Thus, an integrated user interface that supports these various services, especially interactive program guide (IPG) and VOD, are highly desirable.

SUMMARY OF THE INVENTION

The present invention provides messaging techniques that can be advantageously used to support an interactive program guide (IPG) delivery system. The IPG can be provided via a number of IPG pages, with each IPG page being defined with a number of regions (or portions). The non-redundant regions for the IPG pages can be encoded, and some of the encoded regions can be continually transmitted (i.e., broadcast) and some others can be transmitted as requested (i.e., demand-cast). To implement a bandwidth efficient demand-cast system, only the necessary regions not currently received at a terminal are requested (as oppose to entire pages), and the head-end transmits only the requested regions.

An aspect of the invention provides efficient messaging techniques to facilitate the IPG delivery scheme described above. These messaging techniques allow the terminals to specifically designate the requested items of information (i.e., the specific regions of interest).

An embodiment of the invention provides a method for requesting information for IPG, with the IPG being provided via a number of IPG pages and each IPG page including a number of defined regions (e.g., a guide region, a video region, and so on). In accordance with the method, selection for a particular region of a particular IPG page is received at a terminal and a determination is made whether the selected region is currently received at the terminal. If the selected region is not currently received, a request for the selected region is generated and sent to a server of an information distribution system. The selected region may be defined to be a guide region for a program listing if the selected IPG page is not currently received at the terminal.

The request can be generated based on a particular message format that includes a number of fields. In a specific implementation, the request for a guide region includes a region ID field that identifies the selected region, a subtype field that identifies a particular filter (if any) used to filter programs to be included in the program listing, a time slot field that identifies a specific time slot for the selected IPG page, and a page offset field that identifies a particular page from among a number of pages available for the selected time slot.

Other message formats can be defined for requests of other regions of the IPG page. For example, for picture-in-picture encoding scenarios, one of a number of video steams can be shown in the barker video region upon request from a set top terminal. In this case, the request for the video region may include the region ID that identifies the barker region, the subtype field that may be used to identify the type of video stream being requested, such as sports-related, kids-related, and the like, and time slot and page offset fields can be reserved to be used for future implementation purposes.

The invention further provides other methods and system elements (i.e., terminal and server) that implement various aspects, embodiments, and features of the invention, as described in further detail below.

The foregoing, together with other aspects of this invention, will become more apparent when referring to the following specification, claims, and accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

The teachings of the invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings.

FIG. 1 is a diagram of an illustrative communications network for distributing video sequences to a number of terminals in accordance with an embodiment of the invention;

FIGS. 2 6 are diagrams of various methods and topologies for demand-casting interactive program guide (IPG) pages in accordance with embodiments of the invention;

FIGS. 2A and 2B are respectively a flow diagram and a topology for a first push method for demand-casting IPG pages in accordance with an embodiment of the invention;

FIGS. 3A and 3B are respectively a flow diagram and a topology for a second push method for demand-casting IPG pages in accordance with an embodiment of the invention;

FIGS. 4A and 4B are respectively a flow diagram and a topology for a first pull method for demand-casting IPG pages in accordance with an embodiment of the invention;

FIGS. 5A and 5B are respectively a flow diagram and a topology for a second pull method for demand-casting IPG pages in accordance with an embodiment of the invention;

FIGS. 6A and 6B are respectively a flow diagram and a topology for a third pull method for demand-casting IPG pages in accordance with an embodiment of the invention;

FIG. 6C is a flow diagram showing a method for terminating (or continuing) demand-casts in accordance with the third pull method;

FIG. 7 is a diagram of a two-way system for efficient delivery of demand-cast video sequences in accordance with an embodiment of the invention;

FIG. 8 depicts an example of a set of IPG pages for continual broadcast and other IPG pages for demand-cast in accordance with an embodiment of the invention;

FIG. 9 is an example of one picture taken from a video sequence that can be encoded using the invention;

FIGS. 10 13 are block diagrams of first, second, third, and fourth architectures, respectively, for managing delivery of video sequences of an interactive program guide in accordance with embodiments of the invention;

FIG. 14 is a block diagram of an embodiment of set top terminal (STT) 1408 suitable for producing an IPG page and supporting various aspects of the invention;

FIGS. 15A 15D are diagrams of an embodiment of the messaging between the terminal, the session manager, and the transport stream generator;

FIG. 16 is a diagram of an example showing the status of active demand-cast streams in an IPG multiplex;

FIGS. 17A and 17B are diagrams illustrating various scenarios for activation and release of a demand-cast stream;

FIG. 18A is a diagram of an embodiment of a message format that can be used to send a demand-cast request; and

FIGS. 18B through 18D are diagrams of an embodiment of message formats that can be used to send requests for a particular guide listing for a guide region, a particular video for a video region, and an icon region, respectively.

To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common within a figure.

DESCRIPTION OF THE SPECIFIC EMBODIMENTS

A. Illustrative Communications Network

FIG. 1 is a diagram of an illustrative communications network 100 for distributing video sequences to a number of terminals in accordance with an embodiment of the invention. Communications network 100 may be a cable distribution network, but other types of distribution networks may also be used and are within the spirit and scope of the invention.

As shown in FIG. 1, communications network 100 includes one or more head-ends (HE) 102, one or more centers for local neighborhood equipment (LNE) 104, a number of distribution nodes 106, and a number of terminals 108. Local neighborhood equipment 104 may be located, for example, at remote hubs of a cable distribution network. Terminals 108 may be user terminals, interactive set-top terminals (STT), or other devices with interactive functionalities.

B. Example Methods and Topologies

As used herein, "demand-cast" refers to the process of managing and delivering content to one or more users in response to user demand for the content. "Broadcast" refers to the process of managing and delivering content to a number of users on a continual basis. "Pointcast" refers to the process of managing and delivering content to a particular user. And "Narrowcast" refers to the process of managing and delivering content to a group of users.

FIGS. 2 6 are diagrams of various methods and topologies for demand-casting interactive program guide (IPG) pages. These methods and topologies are presented for purposes of edification and are not meant to limit the scope of the invention.

1. First Push Method for Demand-Cast

FIG. 2A is a flow diagram showing a first push method 200 for demand-casting IPG pages in accordance with an embodiment of the invention. As described below, method 200 includes four steps.

In a first step 202, a first set of IPG pages to be broadcast is predetermined. The first set of IPG pages may comprise video sequences, for example, for a current time period. For instance, if the current time is 1:07 pm, then the current time period may include programming from 1:00 pm to 2:30 pm, assuming a 90-minute time period.

In a second step 204, a second set of IPG pages to be broadcast is predetermined. The second set of IPG pages may comprise video sequences, for example, for a prime time period. Such prime time period is a time period during which a large number of viewers typically watch TV programming. For example, the prime time period may include programming from 6:00 pm to 9:00 pm.

In a third step 206, the bandwidth to broadcast the first and second sets of IPG pages is allocated by the distribution system for that purpose. For example, as described below in more detail, a bandwidth manager (BWM) within head-end 102 and/or local neighborhood equipment 104 allocates the necessary bandwidth within the in-band network to broadcast the first and second sets of IPG pages to the terminals. If the first and second sets overlap, then only the non-redundant video sequences need to be broadcast, and only enough bandwidth to broadcast the non-redundant video sequences needs to be allocated. Such situation may occur, for example, when the current time period overlaps the prime time period.

In a fourth step 208, the IPG pages of the first and second sets are broadcast to terminals 108 within the broadcast range. The broadcast range may comprise all terminals 108 downstream from head-end 102 or local neighborhood equipment 104. Only non-redundant content needs to be broadcast, and the broadcast is achieved within the allocated in-band bandwidth.

FIG. 2B depicts a first push topology 250 for demand-casting IPG pages in accordance with an embodiment of the invention. Topology 250 corresponds to the first push method 200 of FIG. 2A. As shown in FIG. 2B, the IPG pages are transmitted from head-end 102 or local neighborhood equipment 104 downstream within communications network 100. As shown in FIG. 2B, the broadcast is "pushed" from head-end 102 or local neighborhood equipment 104 to distribution nodes 106 and finally to a number of terminals 108.

2. Second Push Method for Demand-Cast

FIG. 3A is a flow diagram showing a second push method 300 for demand-casting IPG pages in accordance with an embodiment of the invention. As described below, method 300 includes three steps.

In a first step 302, one or more IPG pages are selected to be narrowcast to a group of terminals 352. For example, the group of terminals may be a group comprising a high concentration of users with a particular ethnicity or special interest, and the selected IPG page(s) may comprise programming targeted to that ethnic or special interest group. As another example, the group of terminals may comprise terminals in a school campus or business, and the selected IPG page(s) may comprise class instruction or other targeted material. The group of terminals may include terminals in one geographic area or terminals dispersed among different geographic areas but linked, for example, via a network group address.

In a second step 304, the bandwidth to narrowcast the selected IPG page(s) is allocated by the distribution system for that purpose. For example, as described below in more detail, the bandwidth manager (BWM) within head-end 102 and/or local neighborhood equipment 104 allocates the necessary bandwidth within the in-band network to narrowcast the selected IPG page(s) to the group of terminals. If the requested IPG page(s) are already being broadcast as shown in FIGS. 2A and 2B, then no additional bandwidth for a narrowcast needs be allocated.

In a third step 306, the selected IPG page(s) are narrowcast to the group of terminals. The narrowcast needs only to be received by terminals within the group of terminals 352 and does not need to be received by other terminals. The narrowcast is sent downstream from head-end 102 or local neighborhood equipment 104 to the group of terminals. The narrowcast is achieved within the allocated in-band bandwidth. If the requested IPG page(s) are already being broadcast as shown in FIGS. 2A and 2B, then the narrowcast needs not be performed.

FIG. 3B depicts a second push topology 350 for demand-casting IPG pages in accordance with an embodiment of the invention. Topology 350 corresponds to the second push method 300 of FIG. 3A. As shown in FIG. 3B, the IPG page(s) are transmitted from head-end 102 or local neighborhood equipment 104 downstream within communications network 100. As shown in FIG. 3B, the narrowcast is pushed from head-end 102 or local neighborhood equipment 104 to one or more distribution nodes 106 and finally to the terminals within group of terminals 352.

3. First Pull Method for Demand-Cast

FIG. 4A is a flow diagram showing a first pull method 400 for demand-casting IPG pages in accordance with an embodiment of the invention. As described below, method 400 includes three steps.

In a first step 402, a request for an IPG page is received from a terminal 108. The request is transmitted upstream from terminal 108 to head-end 102 or local neighborhood equipment 104 via communications network 100. The upstream transmission may be achieved via an out-of-band network or, alternatively, via an in-band network. Such request from the requesting terminal may comprise, for example, a look-ahead request for programming for a time period ahead of the current time period. For a system where one or more IPG pages are already broadcast as shown in FIGS. 2A and 2B, the requesting terminal may first check to see whether or not the requested IPG page is already being broadcast before transmitting the request upstream.

In a second step 404, the bandwidth to pointcast the requested IPG page is allocated by the distribution system for that purpose. For example, as described in more detail below, the bandwidth manager within head-end 102 and/or local neighborhood equipment 104 may allocate the necessary bandwidth within the in-band network to pointcast the requested IPG page to the requesting terminal. The allocation is performed if sufficient system resources are available to establish a pointcast session. Moreover, if the requested IPG page is already being broadcast as shown in FIGS. 2A and 2B, then no additional bandwidth for a pointcast needs be allocated.

In a third step 406, the requested IPG page is pointcast to the requesting terminal. The pointcast needs only to be received by the requesting terminal and does not need to be received by other terminals. The pointcast is sent downstream from head-end 102 or local neighborhood equipment 104 to the requesting terminal. The pointcast, if necessary, is achieved within the allocated in-band bandwidth. If the requested IPG page is already being broadcast as shown in FIGS. 2A and 2B, then the pointcast needs not be performed.

FIG. 4B depicts a first pull topology 450 for demand-casting IPG pages in accordance with an embodiment of the invention. Topology 450 corresponds to first pull method 400 shown in FIG. 4A. As shown in FIG. 4B, the request is transmitted upstream from the requesting terminal 108 to head-end 102 or local neighborhood equipment 104 via communications network 100. Subsequently, the requested IPG page is pointcast downstream from head-end 102 or local neighborhood equipment 104 to the requesting terminal via communications network 100.

4. Second Pull Method for Demand-Cast

FIG. 5A is a flow diagram showing a second pull method 500 for demand-casting IPG pages in accordance with an embodiment of the invention. As described below, method 500 includes three steps.

In a first step 502, a request for an IPG page is received from a requesting terminal 552. The request is transmitted upstream from requesting terminal 552 to head-end 102 or local neighborhood equipment 104 via communications network 100. The upstream transmission may be achieved via an out-of-band network or, alternatively, via an in-band network. Such request may comprise, for example, a look-ahead request for special interest programming available for a future time period ahead of the current time period. For a system where a set or sets of IPG pages are already being broadcast as shown in FIGS. 2A and 2B, requesting terminal 552 may first check to determine whether or not the requested IPG page is already being broadcast before transmitting the request upstream.

In a second step 504, the bandwidth to narrowcast the requested IPG page is allocated by the distribution system for that purpose. For example, as described below in relation to FIGS. 7 and 8, the bandwidth manager within head-end 102 and/or local neighborhood equipment 104 may allocate the necessary bandwidth within the in-band network to narrowcast the requested IPG page to a group of terminals 554 that includes requesting terminal 552. The allocation is performed if sufficient system resources are available to establish a narrowcast session. If the requested IPG page is already being broadcast as shown in FIGS. 2A and 2B, then no additional bandwidth for a pointcast needs to be allocated. The group of terminals 554 may include terminals in one geographic area or terminals dispersed among different geographic areas but linked, for example, via a network group address.

In a third step 506, the requested IPG page is narrowcast to group of terminals 554. The narrowcast needs only to be received by the terminals within group of terminals 554 and does not need to be received by other terminals. The narrowcast is sent downstream from head-end 102 or local neighborhood equipment 104 to group of terminals 554. The narrowcast is achieved within the allocated in-band bandwidth. If the requested IPG page is already being broadcast as shown in FIGS. 2A and 2B, then the narrowcast needs not be performed.

FIG. 5B depicts a second pull topology 550 for demand-casting IPG pages in accordance with an embodiment of the invention. Topology 550 corresponds to second pull method 500 shown in FIG. 5A. As shown in FIG. 5B, the request is transmitted upstream from requesting terminal 552 to head-end 102 or local neighborhood equipment 104 via communications network 100. Subsequently, the requested IPG page is narrowcast downstream from head-end 102 or local neighborhood equipment 104 to group of terminals 554, which includes requesting terminal 552, via communications network 100.

5. Third Pull Method for Demand-Cast

FIG. 6A is a flow diagram showing a third pull method 600 for demand-casting IPG pages in accordance with an embodiment of the invention. As described below, method 600 includes six steps.

In a first step 602, a request for an IPG page is received from a first terminal 652. The request is transmitted upstream from first terminal 652 to head-end 102 or local neighborhood equipment 104 via communications network 100. The upstream transmission may be achieved via an out-of-band network or, alternatively, via an in-band network. Such request from first terminal 652 may comprise, for example, a look-ahead request for programming for a future time period ahead of the current time period. For a system where one or more IPG pages are already being broadcast as shown in FIGS. 2A and 2B, first terminal 652 may first check to see whether or not the requested IPG page is already being broadcast before transmitting the request upstream.

In a second step 604, a stream 656 may be assigned by the distribution system to pointcast the requested IPG page. The assignment is performed if sufficient system resources are available to establish a pointcast session. For example, as described below in more detail, the bandwidth manager within head-end 102 and/or local neighborhood equipment 104 may determine that sufficient resources are available to assign stream 656 to pointcast the requested IPG page to first terminal 652. The stream assignment may be achieved, for example, by assigning a particular value to the program identifier (PID) for stream 656. If the requested IPG page is already being broadcast as shown in FIGS. 2A and 2B, then stream 656 needs not be assigned.

In a third step 606, the requested IPG page is pointcast to first terminal 652 via assigned stream 656. This may be achieved by transmitting packets that are identified by the particular PID value and contain a video sequence of the requested IPG page. The pointcast needs only to be received by first terminal 652 and does not need to be received by other terminals. The pointcast is sent downstream from head-end 102 or local neighborhood equipment 104 to first terminal 652. If the requested IPG page is already being broadcast as shown in FIGS. 2A and 2B, then the pointcast needs not be performed.

In a fourth step 608, a request for an IPG page is received from a second terminal 654. In this example, the IPG page requested by second terminal 654 is the same as the IPG page requested by first terminal 652. Similar to the first request, the second request is transmitted upstream from second terminal 654 to head-end 102 or local neighborhood equipment 104 via communications network 100 via an out-of-band network or an in-band network. Second terminal 654 may be in the same or different geographic area as first terminal 652.

In a fifth step 610, the identifier (e.g., PID value) for the assigned stream 656 is transmitted from head-end 102 or local neighborhood equipment 104 to second terminal 654. This enables the next step 612 to occur without use of additional PIDs or additional network bandwidth.

And in a sixth step 612, second terminal 654 receives the requested IPG page via the same assigned stream 656, which was used to deliver the IPG page to first terminal 652. Second terminal 654 may be set to decode and present packets that are identified by the particular PID value for stream 656. Such packets contain the video sequence of the requested IPG page. In this manner, "sharing" of stream 656 occurs, changing the previous "single" pointcast to a "double" pointcast.

Similarly, other terminals may "share" the pointcast if they request the same IPG page and can receive the requested IPG page via the same stream 656. In this manner, any number of terminals may share the pointcast. This sharing results in more efficient use of the available bandwidth.

FIG. 6B depicts a third pull topology 650 for demand-casting IPG pages in accordance with an embodiment of the invention. Topology 650 corresponds to pointcast "sharing" method 600 shown in FIG. 6A. As shown in FIG. 6B, a request is transmitted upstream from first terminal 652 to head-end 102 or local neighborhood equipment 104 via communications network 100. In response, the requested IPG page is pointcast by stream 656 from head-end 102 or local neighborhood equipment 104 to first terminal 652. Next, a second request for the same IPG page is transmitted upstream from second terminal 654 to head-end 102 or local neighborhood equipment 104 via communications network 100. In response, the identifier for stream 656 is transmitted from head-end 102 or local neighborhood equipment 104 to second terminal 654. Subsequently, second terminal 654 uses the identifier to receive the IPG page from the same stream 656.

FIG. 6C is a flow diagram showing a method 660 for terminating (or continuing) demand-casts in accordance with third pull method 600. As described below, method 660 includes five steps.

In a first step 662, a terminal finishes viewing a stream used to send an IPG page. In the example described above in FIGS. 6A and 6B, the terminal may be either first terminal 652 or second terminal 654. In general, the terminal may be any of the terminals that are sharing the same stream, or the last terminal to view a stream that was previously shared.

In a second step 664, head-end 102 or local neighborhood equipment 104 is notified that the terminal has finished viewing the stream. Such notification can be achieved by the terminal by sending a communication upstream to head-end 102 or local neighborhood equipment 104 via an out-of-band or in-band network.

In a third step 666, a determination is made whether or not that stream is being viewed by one or more terminals. As described in more detail below, this determination is done within head-end 102 or local neighborhood equipment 104 and may be done by a bandwidth manager in conjunction with a session manager.

In a fourth step 668, if one or more terminals are still viewing that stream, then head-end 102 or local neighborhood equipment 104 continues to transmit the stream. Such transmission is typically performed by an in-band delivery system.

Finally, in a fifth step 670, if no other terminals are viewing that stream, then the stream is "torn down" so that it is no longer transmitted and no longer takes up network bandwidth. The torn-down stream is then available for reassignment and the bandwidth can be reused to transmit a different pointcast, narrowcast, or broadcast.

C. Demand-Cast System

1. Guide Page Usage Frequency Distribution

The usage of guide pages can be characterized by their frequency distribution. Certain pages in a guide page matrix, such as those in the current time slot and adjacent time slots ("near look-ahead") are likely to be accessed more frequently by viewers. Other guide pages, such as the "far look-ahead" pages, are likely to be accessed less frequently. These characteristics of guide page usage can be supported by a demand-cast model described herein. Access to all possible guide pages in the guide page matrix can be achieved by sending in a transport stream a combination of continually broadcast guide pages for pages that are more frequently accessed, and temporarily broadcast or demand-cast guide pages for pages less frequently accessed. In an embodiment, current and near look-ahead pages are sent in a broadcast fashion and far look-ahead pages are sent in a demand-cast fashion.

2. Demand-Cast Overview

A demand-cast IPG system is a two-way system employing communication between the terminal in the communications network and the head-end via a back-channel. Demand-cast pages are inserted in the transport stream for temporary broadcast in response to access demand generated by viewers in the network. When a particular viewer requests a particular guide page, one of two things can occur. If the requested page is already in the IPG broadcast, the terminal simply acquires the corresponding stream. Otherwise, if the page is not in the broadcast, the terminal requests the head-end to insert a stream in the IPG multiplex for the requested page. The head-end can then replace the least frequently accessed and not currently accessed stream in the IPG multiplex with a stream for the newly requested page.

When a terminal no longer accesses a guide page, it informs the head-end that it has released it. When accessing a demand-cast page, an IPG application at the terminal can "time-out" following a certain period of inactivity (e.g., 2 minutes) by the viewer. If a time-out occurs, the terminal can inform the head-end that it has released the page. Informing the head-end when demand-cast pages are released ensures that non-accessed demand-cast pages are available for substitution. If a terminal requests a new demand-cast page to be inserted into the IPG multiplex and there is no slot available in the IPG multiplex, the head-end refuses to insert a stream for the newly requested guide page, which then results in a blockage. Most statistical multiplexed systems are susceptible to blockage if loaded with an excessive number of users and during chaotic episodes. An advantage of the demand-cast model is that if a particular page is likely to be extensively accessed, such as a page listing a major sports event, the page only needs to be inserted once into the transport stream. The page is then readily accessible by any number of terminals without consuming additional bandwidth.

3. Latency in Broadcast vs. Demand-Cast

Access to guide pages within a short delay (i.e., with low latency) is an important feature for interactive program guide. Continually broadcast pages offer a low latency access, whereas demand-cast pages may incur additional processing delays if not yet included in the transport stream. In an embodiment, frequently accessed pages, such as those in the current time slot and near look-ahead time slots, and perhaps prime-time slots, are broadcast continually so that they can be accessed with the lowest possible latency. Less frequently accessed far look-ahead pages can be sent via demand-cast.

4. System Description

FIG. 7 is a diagram of a two-way system 700 that can efficiently deliver demand-cast video sequences in accordance with an embodiment of the invention. System 700 includes a session manager (SM) 702 and a transport stream generator (TSG) 704.

Session manager 702 and transport stream generator 704 may be co-located within a distribution center. The distribution center may comprise, for example, head-end 102 in communications network 100. Alternatively, session manager 702 and transport stream generator 704 may be at different locations. For example, session manager 702 may be located at head-end 102, and transport stream generator 704 may be located at local neighborhood equipment 104 in communications system 100.

Session manager 702 and transport stream generator 704 are both coupled to a number of terminals 708 via a distribution network. The distribution network may comprise, for example, a cable distribution network as illustrated in FIG. 1. In that example, terminals 708 would comprise terminals 108 or an equivalent functionality integrated into a computer system or advanced television. Alternatively, for example, the distribution network may comprise a satellite communications system or another type of communications system (telephonic, wireless, etc.).

One terminal 708 and its links to session manager 702 and transport stream generator 704 are illustrated in FIG. 7. In the specific embodiment shown in FIG. 7, terminal 708 receives in-band communication from transport stream generator 704 and sends out-of-band (OOB) communications to session manager 702. In an alternative embodiment, the communication to session manager 702 may comprise upstream in-band communications.

Session manager 702 may comprise, in one embodiment, a computer system residing at head-end 102. The computer system may comprise, for example, a computer server running a particular operating system (e.g., a version of the UNIX or Windows operating system). The computer system may receive out-of-band communication from terminals 708 via a connection to the network controller. For example, the connection may comprise an Ethernet connection, and the network controller may comprise a controller from General Instruments Corp (now part of Motorola Inc.) or another supplier. The computer system also communicates with and controls transport stream generator 704 via a network connection such as an Ethernet connection.

Session manager 702 manages delivery of IPG pages to terminals 708 on a number of cable nodes, with each node being served by a separate IPG multiplexed transport stream generated at a corresponding transport stream generator 704. Session manager 702 also monitors demand-cast stream usage by terminals 708. Session manager 702 tracks IPG demand-cast streams that are acquired by at least one terminal 708. For example, session manager 702 can maintain a table that dynamically lists which terminals 708 are using each stream. This tracking is performed for each IPG multiplexed transport stream managed by session manager 702.

Session manager 702 also accepts messages from terminals 708 indicating that they have acquired, released, or requested demand-cast streams. A new terminal 708 that has acquired a demand-cast stream is registered (i.e., added) to the stream, and a terminal 708 that has released a demand-cast stream is removed from the registry for the stream. Session manager 702 informs the corresponding transport stream generator 704 if there is no longer any terminals 708 registered to a particular demand-cast stream, and also informs transport stream generator 704 when a terminal 708 requests a demand-cast stream. In one embodiment, session manager 702 may time-out acquisition of a stream by any terminal 708 if the terminal has not released the stream within a particular period of time (e.g., a few minutes). The time-out may be implemented by removing terminals 708 from the registry for the stream after the particular period of time.

Transport stream generator 704 may comprise, in one embodiment, a computer system residing at head-end 102. The computer system may comprise, for example, a computer server running a particular operating system (e.g., a version of Windows or UNIX operating system). Alternatively, transport stream generator 704 may be located apart from session manager 702, for example, at local neighborhood equipment 104. Each transport stream generator 704 is coupled to an associated session manager 702, for example, via an Ethernet network. Transport stream generator 704 may generate one or more IPG multiplexed transport streams, with each transport stream being broadcast to a respective node in the distribution system.

In one embodiment, the IPG multiplexed transport stream comprises an MPEG transport stream. In this case, transport stream generator 704 may communicate with terminals 708 via tables in the private section of the MPEG transport stream. Such table may include a list of available demand-cast streams, along with the address of the source transport stream generator 704 and information to identify the particular IPG multiplexed transport stream to which the table belongs.

Transport stream generator 704 manages each IPG multiplexed transport stream that it generates. Transport stream generator 704 receives information from session manager 702 indicating whether each demand-cast stream being served is currently being acquired by any terminal, or not at all. That is, transport stream generator 704 is informed by session manager 702 when a demand-cast stream is no longer being acquired by any terminals 708.

In one embodiment, transport stream generator 704 maintains a status for each demand-cast stream being served. The status for each stream is adjusted upon receipt by transport stream generator 704 of certain messages from session manager 702. In an embodiment, the basic states for the stream status comprise an "acquired" state that denotes that the demand-cast stream is being acquired by one or more terminals 708, and a "released" state that denotes that the demand-cast stream is not being acquired by any terminal 708. Transport stream generator 704 continues to serve "acquired" demand-cast streams by multiplexing them into the appropriate transport streams and replaces "released" demand-cast streams with new demand-cast streams upon receipt of request messages from session manager 702. In an embodiment, transport stream generator 704 also keeps track of the order in which the streams are released, so that the oldest released stream may be used as the most likely candidate for replacement.

If all demand-cast streams in a particular IPG multiplexed transport stream are "acquired," then a new stream may not be inserted into the transport stream, and transport stream generator 704 may refuse any new requests. In such case, a message indicating such refusal may be sent to session manager 702 and/or the requesting terminal 708.

In an embodiment, terminal 708 comprises a set-top terminal (STT) for use by a service subscriber. The STT may comprise an embedded system that includes a tuner, a demultiplexer, and a decoder, as described in further detail below. The STT drives the subscriber's display unit or TV set, and it may be coupled to transport stream generator 704 via an RF feed from a cable distribution network. The IPG pages may be received from a particular IPG multiplexed transport stream on a particular modulated carrier signal. In an embodiment, the IPG multiplexed transport stream may comprise an ensemble of elementary MPEG video streams, with each elementary stream representing a portion of the guide.

In an embodiment, terminal 708 includes IPG client software application that resides at the terminal. The IPG client application is responsible for presenting the IPG to the viewer, and demultiplexes and decodes IPG pages requested by the user. If a requested page is already being received via the IPG multiplexed transport stream, then the IPG client application acquires the stream immediately and sends a message to session manager 702 indicating that it has acquired the stream. And if the requested page is not in the IPG multiplexed transport stream, then the IPG client application sends a request message to session manager 702. Subsequently, the IPG client application acquires the stream once it is transmitted by transport stream generator 704 and received by terminal 708. In addition, if a stream is no longer being acquired, the IPG client application sends a release message to session manager 702. In an embodiment, if there is no remote control or other activity by the user for a particular period of time (e.g., a few minutes), then the IPG client application times-out the acquisition. The time-out may be accomplished, for example, by sending a release message to session manager 702 and acquiring a broadcast stream instead.

D. Major Modules of Demand-Cast System

The demand-cast system includes three major subsystems: the set top terminal (STT), the session manager (SM), and the transport stream generator (TSG). For a better understanding of the invention, a specific implementation of each subsystem is now described. Other implementations are also possible and within the scope of the invention.

1. Set-Top Terminal (STT)

The STT is the end-user or cable service subscriber tuner/demultiplexer/decoder and embedded system. In an embodiment, the STT used in initial pilot deployments of the demand-cast system is the General Instruments DCT-2000. The STT is coupled to the cable operator RF feed and drives the subscriber's display unit or TV set. The IPG content is provided in an IPG transport stream (i.e., IPG multiplex) located on a specific QAM carrier. The IPG multiplex contains an ensemble of elementary MPEG video streams, with each elementary video stream representing portions of the guide and some of these streams representing guide grid pages. The STT receives messages from the head-end via tables in the private section of the IPG transport stream (in-band messaging.) The STT sends messages to the head-end via an out-of-band back-channel or return path.

The STT includes an IPG application that is responsible for presenting (e.g., the DIVA Interactive Program Guide) to the viewer. The IPG application demultiplexes and decodes IPG pages requested by the user. If a particular page is in the IPG transport stream, the STT can quickly acquire the stream and inform the session manager that it has requested the page. And if the page is not in the IPG multiplex, the STT also sends a message to the session manager that it has requested it. The STT then acquires the stream once the stream is included in the IPG multiplex. When the STT no longer acquires a particular guide stream, it informs the session manager that it has released the stream.

In an embodiment, if the STT is on a particular demand-cast stream for more than a particular period of time (e.g., 2 minutes) without any remote control activity, the STT times-out. The STT then acquires a broadcast stream instead and informs the session manager that it has released the demand-cast stream.

2. Session Manager (SM)

In an embodiment, the session manager is implemented with a computer system (e.g., a SPARC Station running the Solaris operating system from SunMicrosystems, Inc.) residing at the cable head-end. The session manager is coupled via Ethernet to the server side of a network controller (NC) from General Instruments Corp. and is the receiver of out-of-band return path messages originating from the STTs. The session manager can handle STTs on multiple cable nodes, each node being served by a separate IPG multiplex. The session manager communicates with and controls the transport stream generators via Ethernet. The transport stream generators generate the IPG transport streams.

The session manager manages one or more cable networks and monitors demand-cast stream usage. The session manager also tracks IPG demand-cast streams that are acquired by at least one STT and maintains a dynamic list of STTs that are using each demand-cast stream. This tracking is achieved for each IPG multiplex managed by the session manager. The session manager accepts messages from the STTs indicating requests for, or release of, demand-cast streams. An STT that has acquired a demand-cast stream is registered to the stream, and an STT that has released a demand-cast stream is removed from the stream's registry. The session manager informs the transport stream generator if there are no longer any STTs using a particular demand-cast stream, and also informs the transport stream generator when an STT requests a demand-cast stream.

In an embodiment, the session manager times-out an STT from a demand-cast stream if the STT has not released the stream within a particular time period (e.g., a few minutes). The session manager can achieve this by removing the STT from the demand-cast stream's registry.

3. Transport Stream Generator (TSG)

In an embodiment, the transport stream generator is implemented with a computer system (e.g., running a WindowNT operating system from Microsoft Corp.) residing at the cable head-end. The transport stream generator is coupled via Ethernet to the session manager controlling it. The transport stream generator produces one or more IPG transport streams, with each transport stream being broadcast to a respective node. In an embodiment, the transport stream generator communicates with the STTs via tables in the private section of the IPG transport streams. The table contains a list of the available demand-cast streams along with the IP address of the source transport stream generator (e.g., its IP address) and the channel number of the IPG multiplex (i.e., which multiplex it is in the transport stream generator).

The transport stream generator manages the transport stream for each IPG multiplex it generates. The transport stream generator receives information from the session manager for each demand-cast stream indicating whether the stream is currently acquired by any STT or released by all STTs. The transport stream generator is informed by the session manager when there is no longer any STT on a particular demand-cast stream and when an STT requests a demand-cast stream.

The transport stream generator maintains the status for all demand-cast streams in each IPG multiplex. The transport stream generator adjusts the status for each demand-cast stream each time it receives a message from the session manager for the stream. The basic status for each stream includes "acquired" for a stream that is in use by one or more STTs and "released" for a stream that is not in use by any STT. The transport stream generator continues to send "acquired" streams in its IPG multiplexes and replaces "released" streams with new demand-cast streams as they are requested. The transport stream generator also keeps track of the age of the released streams and the best candidate for replacement is the oldest released stream. If all demand-cast streams in a multiplex are "acquired" then it may not be possible to insert a new stream when requested and the transport stream generator can refuse to process the request.

E. Example of Interactive Program Guide

An embodiment of an interactive program guide in accordance with the invention is described below. The embodiment is described for purposes of illustration and is not meant to limit the scope of the invention.

FIG. 8 depicts an example of a set of IPG pages for continual broadcast and other IPG pages for variable demand-cast in accordance with an embodiment of the invention. In the specific example shown in FIG. 8, 40 IPG pages are continually broadcast and up to 30 IPG pages may be variably demand-cast. There are 10 guide pages per time slot, and the continual broadcast includes 10 guide pages for the current time slot and 30 guide pages for the next three 1-hour time slots. The variably demand-cast pages may be any pages within the guide page matrix that are not currently being broadcast.

In such a system, when a request for a guide page is made by a particular terminal, either one of two scenarios can occur. First, if the page is already in the IPG broadcast, then the terminal simply acquires the stream for the page from the IPG broadcast. Alternatively, if the page is not in the broadcast, then the terminal transmits a request for the page to the head-end. The head-end may then fulfill the request by replacing the currently transmitted stream that is least frequently accessed and not currently accessed with another stream containing the requested page.

Subsequently, the terminal eventually ends its access to the guide page. This may occur because the user has instructed the terminal to view a different page. Alternatively, this may occur because of a time-out due to inactivity over a particular period of time (e.g., 2 minutes). In any case, if the terminal is no longer accessing the guide page, then the terminal transmits a message to the head-end indicating that it has released the corresponding stream. Informing the head-end when demand-cast pages become released ensures that non-accessed demand-cast pages become available for substitution, as described above.

An advantage of the invention is that, if a particular page is extensively accessed (such as a page listing a major sports event), then the system needs to insert the particular page only once into the transport stream. Once inserted, the page is readily accessible by any number of terminals without requiring additional bandwidth. Other systems may be more susceptible to blockage, which occurs, for example, when a newly requested page cannot be inserted into the transport stream because no bandwidth is available within the transport stream.

An IPG delivery system in accordance with an embodiment of the invention is a two-way system that is capable of supporting two-way communication between the terminals on the cable network and the equipment in the cable head-end. For example, communication may be transmitted from the terminals to the head-end via a back-channel, and content may be transmitted from the head-end to the terminals by insertion into a transport stream.

FIG. 9 depicts an example of an IPG page 900 in accordance with an embodiment of the invention. In the specific embodiment shown in FIG. 9, IPG page 900 includes a region 905, a guide region 910, a video region 920, an icon region 940, a program description region 950, a logo region 960, and a date/time display 970. Other designs for the IPG page with different layouts, configurations, and combinations of regions and objects can be contemplated and are within the scope of the invention.

Time slot region 905 includes a first time slot object 905a and a second time slot object 905b that indicate the time slots for which program guide is being provided on the IPG page. Guide region 910 is used to display program listings for a group of channels. In the embodiment shown in FIG. 9, the program listings show the available programming in two half-hour time slots. Guide region 910 thus includes a number of channel objects 912a through 912j used to display channel information for a guide listing of channels. Guide region 910 further includes a pair of channel indicator icons 914a and 914b that identifies the current cursor location.

Program description region 950 is used to present descriptive information relating to a particular program selected from the program listings, or may be used to show other information. Video region 920 may be used to display images, videos, text, or a combination thereof, which may be used for advertisements, previews, or other purposes. Video region 920 may be implemented as described above in a server-centric manner. Logo region 960 may include a logo of a service operator or other entity and may be optionally displayed. Date/time display 970 may be configurable by the user and may also be optionally displayed.

Icon region 940 is used to display various icons, which may be created and/or enabled by the user. Each icon in icon region 940 can represent a filter or a link to another IPG page or a particular interface. Each filter selects a particular type of programming to be included in the program listings shown in guide region 910. For example, a Pay Per View (PPV) icon 941 may be a filter that selects only PPV programming to be included in the program listings. A Favorites icon 942 may be a filter that selects only channels designated by the user to be among his or her favorites. A Movies icon 943 may be a filter that selects only movies or movie channels. A Kids icon 944 may be a filter that selects only channels for children or programming appropriate for or produced for viewing by children. A Sports icon 945 may be a filter that selects only sports channels or sports-related programming. A Music icon 946 is a link to a music interface. An Options icon 947 may also be a link to a menu of IPG options that the user may select amongst. The options may include (1) configuration and selection/deselection information of IPG related services, (2) custom information such as deactivating some of the filters or accessing the custom condensed listing menus, and others. A Weather icon 948 may be a link to an interface to weather information.

As an illustration, in a system comprising 80 channels of information, the channels are displayed in 10-channel groups having associated with them two half-hour time slots. In this organization, 8 video PIDs are provided to carry the present-time channel/time/title information, one or more audio PIDs are provided to carry the audio barker and/or one or more data PIDs (or other data transport method) are provided to carry the program description data, overlay data, and the like. To fully broadcast interactive program information for up to 24 hours in advance, 192 (e.g., 8*24) video PIDs are provided, along with one or more audio PIDs and, optionally, one or more data PIDs.

The time depth of a program guide, which is defined by the amount of time in programming, is provided in the broadcast video PIDs for the particular channel groups. The channel depth of the program guide is defined by the number of channels available through the guide (as compared to the total number of channels in the system). In a system providing only half of the available channels via the broadcast video PIDs, the channel depth is 50%. In a system providing 12 hours of "look-ahead" time slot, the time depth is 12 hours. In a system providing 16 hours of "look-ahead" time slot and 4 hours of "look-back" time slot, the time depth is +16/-4 hours.

The video streams representing the IPG are sent in a one or more transport streams, within the form of a single program or multi-programs as described above. A user desiring to view the next 1-hour time interval (e.g., 10:00 11:00) may activate a "scroll right" object (or move the joystick to the right when a program within guide region 910 occupies the final displayed time interval). Such activation results in a controller within the terminal noting that a new time interval is desired. The video stream desired for the new time interval is then decoded and displayed. If the corresponding video stream is within the same transport stream (i.e., a new PID), then the stream is simply decoded and presented. If the desired video stream is within a different transport stream, then that transport stream is extracted from the broadcast stream and the desired video stream is decoded and presented. And if the desired transport stream is within a different broadcast stream, then that broadcast stream is tuned, the desired transport stream is extracted, and the desired video stream is decoded and presented.

A user interaction requesting in a prior time interval or a different set of channels results in the retrieval and presentation of the desired video stream. If the desired video stream is not part of the broadcast video streams, then a pointcast session, for example, may be initiated as described above for FIGS. 4A and 4B. For this pointcast session, the terminal sends a message to the head-end via a back channel requesting a particular stream. The head-end processes the request, retrieves the desired stream from the information server, and incorporates the stream within a transport stream as a video PID. Preferably, the desired stream is inserted into the transport stream currently being tuned/selected by the terminal. The head-end further informs the terminal which PID should be received and from which transport stream it should be demultiplexed. The terminal then retrieves the desired video PID. If the video PID is within a different transport stream, the terminal first demultiplexes that transport stream (possibly by tuning a different QAM stream within the forward channel).

Typically, upon completion of the viewing of the desired stream, the terminal indicates to the head-end that it no longer needs the stream. In response, the head-end tears down the pointcast session. The terminal th