On-demand digital information delivery system and method using signal fragmentation and linear/fractal sequencing.

• US 5,737,009 A
• Filed: 04/04/1996
• Issued: 04/07/1998
• Est. Priority Date: 04/04/1996
• Status: Expired due to Term

• Current Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Original Assignee: Hughes Electronics Corporation (AT&T, Inc.)
• Inventors: Payton, David W.
• Primary Examiner(s): Britton, Howard W.
• Application Number:
  US08/627,628
• Time in Patent Office: 733 Days
• Field of Search: 348/17
• US Class Current: 725/93
• CPC Class Codes: H04N 21/2312 Data placement on disk arrays data placement in general G06F3/0604
• CPC Class Codes: H04N 21/47202 for requesting content on demand, e.g. video on demand
• CPC Class Codes: H04N 21/6143 involving transmission via a satellite

Abstract

Digital information is delivered on-demand through satellites and other predominantly broadcast transmission systems to local subscribers by fragmenting each digital item into a sequence of ordered fragments and sequencing them based upon the incidence of subscriber requests. Linear and fractal sequencers are used to schedule the fragments when the incidence of requests is respectively below and above a threshold. The linear sequencer responds to the first request by scheduling the item'"'"'s fragments in order at successive time intervals and responds to each successive request by adding only those fragments that the existing schedule cannot accommodate. The fractal sequencer computes a full fractal sequencing pattern, in which the fragments are scheduled with broadcast periods less than or equal to their fragment numbers, and based upon the incidence of requests deletes the fragments in the full pattern that are not required to satisfy the subscribers'"'"' requests. A hybrid sequencer combines the linear and fractal sequencers to minimize the average bandwidth needed to service infrequent requests and places an upper bound on the peak bandwidth required to service frequent requests.

Claims

1. A system for delivering near on-demand digital information to a plurality of local subscribers, comprising:

a fragmentation unit that fragments a digital item into a sequence of N numbered fragments;

a sequencing processor that responds to a subscriber request for the digital item by generating a sequencing pattern having average and peak bandwidths, said sequencing processor selectively adding and deleting fragments from the sequencing pattern based upon the incidence of requests for the digital item such that the average bandwidth required to service requests occurring with an incidence less than a threshold is set at a low value and the peak bandwidth required to service requests occurring with an incidence greater than the threshold is bounded by an upper bound;

a sequence generator that sequences the fragments into a multi-channel data stream in accordance with the sequencing pattern;

a digital transport system that continuously broadcasts the multi-channel data stream over a plurality of channels at successive time intervals to the local subscribers; and

a plurality of local servers for extracting the fragments from the multi-channel data stream, seamlessly integrating the fragments and delivering them to a plurality of playback devices.

2. The system of claim 1, wherein the sequencing processor is programmed to implement a linear sequencer for incidences less than the threshold, which:

a) in response to a first request for the digital item, schedules the item'"'"'s fragments in order at successive time intervals;

b) in response to each successive request, determines the fragments that the existing sequencing pattern is incapable of delivering to the requesting subscriber; and

c) adds those fragments to the existing sequencing pattern at the latest time intervals that will satisfy the requirements of the requesting subscriber'"'"'s local server to seamlessly integrate the fragments.

3. The system of claim 2, wherein said linear sequencer minimizes the average bandwidth required to service requests when the incidence is below the threshold.

4. The system of claim 2, wherein a subscriber'"'"'s request adds M fragments of the digital item to the existing sequencing pattern, each local server comprising:

an interface for generating the subscriber request for a given digital item;

a local storage for storing fragments;

a reassembly processor for receiving the first fragment of the requested item within one time interval from the request and integrating it with succeeding fragments to seamlessly deliver the digital item to the local subscriber; and

a fragment splitter for a) sequentially downloading the M fragments of the requested item and directing them to the reassembly processor, and b) concurrently capturing the remaining fragments for the requested item, which were broadcast in response to previous requests from other subscribers, temporarily storing them in the local storage, and then writing them out as needed to the reassembly processor.

5. The system of claim 1, wherein the sequencing processor is programmed to implement a fractal sequencer for incidences greater than the threshold, which:

a) computes a full fractal sequencing pattern, in which the fragments are scheduled to have broadcast periods less than or equal to their fragment numbers;

b) monitor the incidence of the subscribers'"'"' on-demand requests;

c) identify the fragments in the full fractal sequencing pattern that are not required to satisfy the subscribers'"'"' requests; and

d) delete the identified fragments from the full fractal sequencing pattern to form the sequencing pattern.

6. The system of claim 5, wherein in step c the fractal sequencer,

tracks the most recent subscriber request, and

identifies the numbered fragments in the full fractal sequencing pattern that are scheduled at greater than j time intervals past the most recent subscriber request where j is the period assigned to each of said fragments in the fractal sequence.

7. The system of claim 6, wherein the fractal sequencer places said upper bound on the peak bandwidth at approximately 1+ln(N).

8. The system of claim 5, wherein each local server comprises:

an interface for generating the subscriber request for a given digital item;

a local storage for storing fragments;

a fragment splitter for downloading fragments from the transport system during successive time intervals in response to the subscriber request and storing them in the local storage so that the first fragment is available within one time interval from the subscriber request and thereafter the succeeding numbered fragments are available within their respective periods; and

a reassembly processor for reading each successive fragment from said local storage and integrating it with the preceding fragment to seamlessly deliver the digital item to the local subscriber.

9. The system of claim 5, wherein the fragments are scheduled at their assigned periods with respective offsets in the full fractal sequencing pattern and a number L of said fragments being prestored in the local servers, said fractal sequencer in step a being programmed to:

a) initialize a control variable equal to L+1 to indicate the current fragment for sequencing;

b) initialize a plurality of fractal trees equal to the number of channels where the fractal trees have root nodes Pj in a base set that includes successive prime numbers up to the number of trees, said fractal trees being expanded by splitting its root node into Pj branches Bi, which terminate at unassigned leaf nodes having prime factors Ri for i=0 to Pj-1, said leaf nodes having broadcast periods equal to the product of the prime numbers assigned to the leaf nodes traversed from the root node to the particular leaf node;

c) select one of the fractal trees and one of its unassigned leaf nodes based upon the unassigned leaf nodes'"'"' broadcast periods;

d) compute an expansion factor, which is the largest integer which when multiplied by the period of the selected leaf node is less than or equal to the value of control variable;

e) if the expansion factor equals one, assign the current fragment to the current leaf node, increment the control variable, and return to step c until all of the fragments are assigned;

f) if the expansion factor is greater than one, compute a prime factorization of the extension factor to generate an ordered list of prime factors;

g) recursively spawn subtrees from the current leaf node until the ordered list is exhausted, said subtrees including a plurality of leaf nodes equal to the respective prime factor, said current leaf node being reset to the first leaf node in the successively spawned subtrees;

h) assign the current fragment to the current leaf node, increment the control variable, and return to step c until all of the fragments are assigned;

i) compute each fragment'"'"'s period as the product of the prime factors Ri associated with the leaf nodes traversed from the root node to the fragments'"'"' assigned leaf node;

j) compute each fragment'"'"'s offset as a function of the branches Bi and prime factors Ri traversed from the root node to the fragment'"'"'s leaf node; and

k) assign the fragments to the designated channels in accordance with the fragments'"'"' periods and offsets.

10. The system of claim 9, wherein the fractal sequencer is programmed to select the fractal tree and leaf node in step c by:

computing a match score for each of the unassigned leaf nodes, said match scores being equal to the difference between the value of the control variable and the largest integer multiple of the broadcast period that is smaller than the value of the control variable; and

selecting the leaf node having the smallest match score, and if two or more match scores are equal, selecting the leaf node having the largest broadcast period.

11. The system of claim 10, wherein the fractal sequencer is programmed to compute each fragment'"'"'s offset in step j as follows:

##EQU3## where q is the number of nodes traversed from the root node to the fragment'"'"'s leaf node.

12. The system of claim 1, wherein the sequencing processor is programmed to implement a hybrid sequencer which selects linear and fractal sequencers when the incidence of requests is less and greater than the threshold, respectively, to generate the sequencing pattern, said linear sequencer responding to each successive request by augmenting the sequencing pattern with those fragments that cannot be captured by the requesting subscriber from the existing sequencing pattern and said fractal sequencer generating a full fractal sequencing pattern and, based upon the incidence of requests, omitting those fragments that are not required to service the subscribers.

13. The system of claim 12, wherein the hybrid sequencer further includes forward and reverse transition sequencers for executing the linear-to-fractal and fractal-to-linear transitions, respectively.

14. The system of claim 13, wherein the forward transition sequencer is programmed to:

determine those fragments that would have to be added to the existing sequencing pattern using the linear sequencer to satisfy the most recent subscriber request when that request causes the incidence of requests to cross a threshold; and

reschedule all of the fragments in the existing sequencing pattern and the additional fragments to conform to a fractal sequencing pattern.

15. The system of claim 14, wherein the forward transition sequencer reschedules the fragments by:

generating a plurality of candidate fractal sequencing patterns;

computing a mismatch between each of the candidate fractal sequencing patterns and the existing sequencing pattern with the additional fragments;

selecting the candidate fractal sequencing pattern with the smallest mismatch; and

scheduling the remaining mismatched fragments as transition fragments.

16. The system of claim 15, wherein the candidate fractal sequencing patterns are generated by:

initializing a plurality of fractal trees having root nodes Pj in a base set that includes successive prime numbers up to the number of trees, said fractal trees being expanded by splitting its root node into Pj branches Bi, which terminate at unassigned leaf nodes having prime factors Ri for i=0 to Pj-1, each of said leaf nodes having broadcast T_i periods equal to the product of the prime numbers assigned to the leaf nodes traversed from the root node to the leaf node, which is given by;

##EQU4## and an offset O_i given by;

##EQU5## where q is the number of nodes traversed from the root node to the fragment'"'"'s leaf node;

assigning the numbered fragments to the leaf nodes such that their assigned periods are less than or equal to their fragment numbers; and

interchanging the branches Bi to generate the candidate fractal sequencing patterns, in which the same leaf node in each pattern has the same period but a different offset.

17. The system of claim 15, wherein the candidate fractal sequencing patterns are generated by:

initializing a plurality of fractal trees having root nodes Pj in a base set that includes successive prime numbers up to the number of trees, said fractal trees being expanded by splitting its root node into Pj branches Bi, which terminate at unassigned leaf nodes having prime factors Ri for i=0 to Pj-1, each of said leaf nodes having broadcast T_i periods equal to the product of the prime numbers assigned to the leaf nodes traversed from the root node to the leaf node, which is given by;

##EQU6## and an offset O_i given by;

##EQU7## where q is the number of nodes traversed from the root node to the fragment'"'"'s leaf node;

assigning the numbered fragments to the leaf nodes such that their assigned periods are less than or equal to their fragment numbers; and

swapping the positions of the numbered fragments between trees so that the newly assigned period for each of the fragments is less than or equal to its number.

18. The system of claim 13, wherein the reverse transition circuit is programmed to:

keep the existing sequencing pattern from the fractal sequencer intact when the most recent request causes the incidence of requests to cross a threshold; and

schedule the additional fragments required for the most recent request and subsequent thereafter according to the linear sequencer.

19. The system of claim 13, wherein the reverse transition sequencer is programmed to:

maintain all of the subscriber requests for the last N time intervals;

when the incidence of requests falls below the threshold, determine the assigned periods T_k for each of the N fragments;

identify the earliest request that is no more than T_k time intervals prior to the scheduled broadcast time interval for the k^th fragment;

schedule the k^th fragment for broadcast at the k^th time interval after its corresponding earliest request; and

schedule the most recent and subsequent requests with the linear sequencer.

20. The system of claim 13, wherein the hybrid sequencer selects the linear sequencer when the incidence of requests is less than a threshold, said linear sequencer being programmed to:

a) in response to a first request for the digital item, schedule the item'"'"'s fragments in order at successive time intervals;

b) in response to each successive request, determine the fragments that the existing sequencing pattern is incapable of delivering to the requesting subscriber; and

c) add those fragments to the existing sequencing pattern at the latest time intervals that will satisfy the requirements of the requesting subscriber'"'"'s local server to seamlessly integrate the fragments, and

the hybrid sequencer selects the fractal sequencer when the incidence of requests is greater than the threshold, said fractal sequencer being programmed to;

d) computes a full fractal sequencing pattern, in which the fragments are scheduled to have broadcast periods less than or equal to their fragment numbers;

e) monitor the incidence of the subscribers'"'"' on-demand requests;

f) track the most recent subscriber request to identify the numbered fragments in the full fractal sequencing pattern that are scheduled at greater than j time intervals past the most recent subscriber request where j is the number corresponding to each of said fragments'"'"' assigned periods; and

g) delete the identified fragments from the full fractal sequencing pattern to form the sequencing pattern.

21. A system for delivering on-demand digital information to a plurality of local subscribers, comprising:

a fragmentation unit that provides a digital item as a sequence of N numbered fragments;

a linear sequencer that responds to subscriber requests occurring at an incidence less than a given threshold by generating a linear sequencing pattern for broadcasting said fragments, said sequencing processor responding to subsequent requests for the digital item by adding those fragments needed to service the requests to the existing linear sequencing pattern;

a fractal sequencer that responds to subscriber requests occurring at an incidence greater than the given threshold by generating a fractal sequencing pattern for broadcasting said fragments, said fractal sequencer computing a full fractal pattern in which each fragment is scheduled with a broadcast period less than or equal to its associated number and then selectively deleting fragments from the full fractal pattern in accordance with the incidence of subscriber requests to form the fractal sequencing pattern; and

a transition sequencer for controlling the transition from the linear-to-fractal and fractal-to-linear sequencing patterns when the incidence of requests cross the given threshold by generating a transition pattern;

a sequencer generator that sequencer the fragments into a multi-channel data stream in accordance with said linear, fractal, and transition sequencing patterns;

a digital transport system that continuously broadcasts the multi-channel data stream over a plurality of channels at successive time intervals to the local subscribers; and

a plurality of local servers for extracting the fragments from the multi-channel data stream, seamlessly integrating the fragments and delivering them to a plurality of playback devices.

22. The system of claim 21, wherein the transition sequencer includes a forward transition sequencer that:

determines those fragments that would have to be added to the existing linear sequencing pattern using the linear sequencer to satisfy the most recent subscriber request when that request causes the incidence of requests to cross the given threshold; and

reschedules all of the fragments in the existing linear sequencing pattern and the additional fragments to conform to a fractal sequencing pattern.

23. The system of claim 22, wherein the forward transition sequencer reschedules the fragments by:

generating a plurality of candidate fractal sequencing patterns;

computing a mismatch between each of the candidate fractal sequencing patterns and the existing sequencing pattern with the additional fragments;

selecting the candidate fractal sequencing pattern with the smallest mismatch; and

scheduling the remaining mismatched fragments as transition fragments.

24. The system of claim 23, wherein the candidate fractal sequencing patterns are generated by:

initializing a plurality of fractal trees having root nodes Pj in a base set that includes successive prime numbers up to the number of trees, said fractal trees being expanded by splitting its root node into Pj branches Bi, which terminate at unassigned leaf nodes having prime factors Ri for i=0 to Pj-1, each of said leaf nodes having broadcast T_i periods equal to the product of the prime numbers assigned to the leaf nodes traversed from the root node to the leaf node, which is given by;

##EQU8## and an offset O_i given by;

##EQU9## where q is the number of nodes traversed from the root node to the fragment'"'"'s leaf node;

assigning the numbered fragments to the leaf nodes such that their assigned periods are less than or equal to their fragment numbers; and

interchanging the branches Bi to generate the candidate fractal sequencing patterns, in which the same leaf node in each pattern has the same period but a different offset.

25. The system of claim 23, wherein the candidate fractal sequencing patterns are generated by:

initializing a plurality of fractal trees having root nodes Pj in a base set that includes successive prime numbers up to the number of trees, said fractal trees being expanded by splitting its root node into Pj branches Bi, which terminate at unassigned leaf nodes having prime factors Ri for i=0 to Pj-1, each of said leaf nodes having broadcast T_i periods equal to the product of the prime numbers assigned to the leaf nodes traversed from the root node to the leaf node, which is given by;

##EQU10## and an offset O_i given by;

##EQU11## where q is the number of nodes traversed from the root node to the fragment'"'"'s leaf node;

assigning the numbered fragments to the leaf nodes such that their assigned periods are less than or equal to their fragment numbers; and

swapping the positions of the numbered fragments between trees so that the newly assigned period for each of the fragments is less than or equal to its number.

26. The system of claim 21, wherein the transition sequencer includes a reverse transition sequencer that:

keeps the existing fractal sequencing pattern from the fractal sequencer intact when the most recent request causes the incidence of requests to fall below the threshold; and

schedules the additional fragments required for the most recent request and subsequent requests according to the linear sequencer.

27. The system of claim 21, wherein the transition sequencer includes a reverse transition sequencer that:

maintains all of the subscriber requests for the last N time intervals;

when the incidence of requests falls below the threshold, determine the assigned periods T_k for each of the N fragments;

identify the earliest request that is no more than T_k time intervals prior to the scheduled broadcast time interval for the k^th fragment;

schedule the k^th fragment for broadcast at the k^th time interval after its corresponding earliest request; and

schedule the most recent and subsequent requests with the linear sequencer.

28. The system of claim 21, wherein linear sequencer is programmed to:

a) in response to a first request for the digital item, schedule the item'"'"'s fragments in order at successive time intervals;

b) in response to each successive request, determine the fragments that the existing sequencing pattern is incapable of delivering to the requesting subscriber; and

c) add those fragments to the existing sequencing pattern at the latest time intervals that will satisfy the requirements of the requesting subscriber'"'"'s local server to seamlessly integrate the fragments, and

said fractal sequencer being programmed to;

d) compute the full fractal sequencing pattern;

e) monitor the incidence of the subscribers'"'"' on-demand requests;

f) track the most recent subscriber request to identify the numbered fragments in the full fractal sequencing pattern that are scheduled at greater than j time intervals past the most recent subscriber request where j is the period assigned to each of said fragments in the fractal sequence; and

g) delete the identified fragments from the full fractal sequencing pattern to form the fractal sequencing pattern.

29. A method for delivering on-demand digital information to local subscribers, comprising

fragmenting a digital item into a sequence of N numbered fragments;

monitoring the incidence of on-demand requests for the digital item from a plurality of local subscribers;

generating a sequencing pattern for scheduling the fragments at successive time intervals over a bandwidth, said sequencing pattern dynamically allocating the bandwidth based upon the incidence of requests to minimize the average bandwidth required to service requests occurring with an incidence less than a threshold and to place an upper bound of approximately 1+ln(N) on the peak bandwidth required to service requests occurring with an incidence greater than the threshold; and

broadcasting the fragments in accordance with the sequencing pattern so that each requesting subscriber receives the first fragment within a known number of time intervals from their respective requests and receives the successive numbered fragments in time to seamlessly integrate the numbered fragments to reconstruct the digital item.

30. The method of claim 29, wherein the sequencing pattern is generated by:

a) in response to a first request for the digital item, scheduling the item'"'"'s fragments in order at successive time intervals;

b) in response to each successive request, determining the fragments that the existing sequencing pattern is incapable of delivering to the requesting subscriber; and

c) adding those fragments to the existing sequencing pattern at the latest time intervals that will satisfy the requirements of the requesting subscriber'"'"'s local server to seamlessly integrate the fragments.

31. The method of claim 29, wherein the sequencing pattern is generating by:

a) computing a full fractal sequencing pattern, in which the fragments are scheduled to have broadcast periods less than or equal to their fragment numbers;

b) identifying the fragments in the full fractal sequencing pattern that are not required to satisfy the subscribers'"'"' requests; and

d) deleting the identified fragments from the full fractal sequencing pattern to form the sequencing pattern.

32. The method of claim 31, wherein the fragments are identified by:

tracking the most recent subscriber request, and

identifying the numbered fragments in the full fractal sequencing pattern that are scheduled at greater than j time intervals past the most recent subscriber request where j is the period assigned to each of said fragments in the fractal sequence.

33. A method for delivering on-demand digital information to local subscribers, comprising

fragmenting a digital item into a sequence of N numbered fragments;

monitoring the incidence of on-demand requests for the digital item from a plurality of local subscribers;

if the incidence of requests is less than a given threshold, scheduling the item'"'"'s fragments in order at successive time intervals to generate a linear sequencing pattern in response to a first request for the item, and thereafter responding to subsequent requests for the digital item by adding those fragments needed to service the requests to the existing linear sequencing pattern;

if the incidence of requests is greater than the given threshold, generating a full fractal sequencing pattern by scheduling each fragment with a broadcast period less than or equal to its associated number and then selectively deleting fragments from the full fractal pattern in accordance with the incidence of the subscriber requests to form a dynamic fractal sequencing pattern;

when the incidence of requests crosses the threshold, controlling the linear-to-fractal and fractal-to-linear sequencing pattern transitions so that the subscribers receive the first fragment within a known number of time intervals from their respective requests and receive the successive numbered fragments in time to seamlessly integrate the numbered fragments to reconstruct the digital item; and

broadcasting the fragments in accordance with the linear and dynamic fractal sequencing patterns.

34. The method of claim 33, wherein the fragments in the full fractal pattern are selectively deleted by:

tracking the most recent subscriber request, and

deleting the numbered fragments in the full fractal sequencing pattern that are scheduled at greater than j time intervals past the most recent subscriber request where j is the period assigned to each of said fragments in the fractal sequence.

35. The method of claim 33, wherein the linear-to-fractal transition is executed by:

determining those fragments that would have to be added to the existing linear sequencing pattern to satisfy the most recent subscriber request;

generating a plurality of candidate fractal sequencing patterns;

computing a mismatch between each of the candidate fractal sequencing patterns and the existing sequencing pattern with the additional fragments;

selecting the candidate fractal sequencing pattern with the smallest mismatch; and

scheduling the remaining mismatched fragments as transition fragments.

36. The method of claim 35, wherein the candidate fractal sequencing patterns are generated by:

initializing a plurality of fractal trees having root nodes Pj in a base set that includes successive prime numbers up to the number of trees, said fractal trees being expanded by splitting its root node into Pj branches Bi, which terminate at unassigned leaf nodes having prime factors Ri for i=0 to Pj-1, each of said leaf nodes having broadcast T_i periods equal to the product of the prime numbers assigned to the leaf nodes traversed from the root node to the leaf node, which is given by;

##EQU12## and an offset O_i given by;

##EQU13## where q is the number of nodes traversed from the root node to the fragment'"'"'s leaf node;

assigning the numbered fragments to the leaf nodes such that their assigned periods are less than or equal to their fragment numbers; and

interchanging the branches Bi to generate the candidate fractal sequencing patterns, in which the same leaf node in each pattern has the same period but a different offset.

37. The method of claim 35, wherein the candidate fractal sequencing patterns are generated by:

initializing a plurality of fractal trees having root nodes Pj in a base set that includes successive prime numbers up to the number of trees, said fractal trees being expanded by splitting its root node into Pj branches Bi, which terminate at unassigned leaf nodes having prime factors Ri for i=0 to Pj-1, each of said leaf nodes having broadcast T_i periods equal to the product of the prime numbers assigned to the leaf nodes traversed from the root node to the leaf node, which is given by;

##EQU14## and an offset O_i given by;

##EQU15## where q is the number of nodes traversed from the root node to the fragment'"'"'s leaf node;

assigning the numbered fragments to the leaf nodes such that their assigned periods are less than or equal to their fragment numbers; and

swapping the positions of the numbered fragments between trees so that the newly assigned period for each of the fragments is less than or equal to its number.

38. The method of claim 35, wherein fractal-to-linear transition is executed by:

keeping the existing dynamic fractal sequencing pattern intact; and

scheduling the additional fragments required for the most recent request and subsequent thereafter according to the linear sequencer.

39. The method of claim 35, wherein the fractal-to-linear transition is executed by:

maintaining all of the subscriber requests for the last N time intervals;

when the incidence of requests falls below the threshold, determining the assigned periods T_k for each of the N fragments;

identifying the earliest request that is no more than T_k time intervals prior to the scheduled broadcast time interval for the k^th fragment;

scheduling the k^th fragment for broadcast at the k^th time interval after its corresponding earliest request; and

scheduling the most recent and subsequent requests with the linear sequencer.