Guided random seek support for media streaming

• US 7,640,353 B2
• Filed: 04/27/2006
• Issued: 12/29/2009
• Est. Priority Date: 04/27/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shen, Guo Bin, Li, Shipeng, Zheng, Changxi
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Assistant Examiner(s): Baron, James T
• Application Number:
  US11/380,619
• Publication Number:
  US 20070255844A1
• Time in Patent Office: 1,342 Days
• Field of Search: 709/219, 709230-231, 725/105, 725116-119, 725/135
• US Class Current: 709/231
• CPC Class Codes: H04L 12/00 Data switching networks interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 65/00 Network arrangements, protocols or services for supporting real-time applications in data packet communication real-time or near real-time messaging, e.g. instant messaging [IM] H04L51/04; selective video distribution H04N21/00
• CPC Class Codes: H04L 65/65 Network streaming protocols, e.g. real-time transport protocol [RTP] or real-time control protocol [RTCP]
• CPC Class Codes: H04L 65/764 at the destination reformatting of additional data in video clients H04N21/4355
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

Seek support facilitates convenient access to portions of a media file a user wishes to access. Seek support is provided by a usage model based on prior users'"'"' access of a media file or expected user access patterns. The usage model reflects expected next segments a user will seek when accessing the media file. A prefetching model derived from the usage model reduces seeking delay by prefetching one or more expected next segments identified from the usage model that will result in minimal seeking distance. Correspondingly, a method of prefetching segments also facilitates access to the media file. A quantity of segments of a media file to be prefetched and a current region of a media file being access are identified. At least one next segment identified by the prefetching model as an expected next seeking destination from the current region is identified, and the next segment is prefetched.

Claims

1. A computer-implemented method, comprising:

identifying a quantity of segments of a media file to be prefetched;

generating a usage model reflecting expected next segments a user will seek when accessing a media file, the usage model including one of;

an empirical usage model statistically summarizing usage data representing a manner in which prior users have accessed segments of a media file,

an initial usage model representing a predicted manner in which users are expected to access segments of the media file, and

the initial usage model augmented by the usage data representing the manner in which users have accessed segments of the media file; and

identifying a prefetching model from the usage model to reduce a seeking delay in accessing one or more next segments by prefetching one or more expected next segments identified from the usage model, wherein identifying the prefetching model includes;

representing the usage model as a probability function of a user seeking a particular segment, wherein the probability function is a function including representations of;

access occurrences for each segment,

seeking occurrences for each segment, and

both the access occurrences and the seeking occurrences for each segment, wherein the probability function p(x) includes;

p(x)=C×

P_p(X)×

P_s(x)

where;

x represents each of the segments of the media file,

C represents a normalization factor,

P_p(x) represents the access occurrences for each segment x, and

P_s(x) represents the seeking occurrences for each segment x, and

deriving the prefetching model from the usage model to minimize a seeking distance; and

prefetching the segments in accordance with the prefetching model.

2. The method of claim 1, wherein the empirical usage model includes:

a plurality of access occurrences representing a number of instances the segments were accessed by the users; and

a plurality of seeking occurrences, representing a number of instances the segments were a seek destination for the users.

3. The method of claim 1, wherein the seeking distance is defined as a distance between a desired seeking destination and a resulting position of a next desired segment derived from the usage model, and a seeking distance D_g includes:

$D_g=E<br><br>\{d<br><br>\left(x,g<br><br>\left(x\right)\right)<br><br><br><br>x\in <br><br>L\}={\int <br><br>}_{x\in <br><br>L}<br><br>d<br><br>\left(x,g<br><br>\left(x\right)\right)<br><br>p<br><br>\left(x\right)<br><br>d<br><br>x$

where;

E represents an expectation of the seeking distance;

g(x) is the prefetching model;

d(x, g(x)) is the seeking distance as a function of the segment x and the prefetching model g(x); and

L is a number of segments to be prefetched.

4. The method of claim 3, wherein the prefetching model g(x) includes an optimal scheduling model, g(x), wherein g(x) includes:

$\stackrel{\_}{g<br><br>\left(x\right)}=\underset{g}{\arg <br><br><br><br>\min }<br><br><br><br>\{E<br><br>\left\{d<br><br>\left(x,g<br><br>\left(x\right)\right)|x\in <br><br>L\right\}.$

5. The method of claim 4, wherein the optimal scheduling model is derived at least in part by:

representing the prefetching model as a scalar quantization function; and

applying scalar quantization to solve the scalar quantization function.

6. The method of claim 5, wherein the scalar quantization function is solved using a Lloyd algorithm.

7. The method of claim 1, wherein the scheduling model directs prefetching of segments from at least one peer in a peer-to-peer network for a subsequent user accessing the media file.

8. A computer-implemented method, comprising:

dividing an audiovisual file into a plurality of segments;

accessing a usage model including;

an empirical usage model based on data representing a manner in which a plurality of users accessed an audiovisual file, wherein the empirical usage model represents at least one of;

access occurrences representing a number of instances of each of the segments accessed by the users;

seeking occurrences, representing a number of instances of each of the segments that was a seek destination for the users;

or

both, the access occurrences and the seeking occurrences; and

an initial usage model representing a predicted manner in which users are expected to access segments of the audiovisual file, the initial usage model augmented by the data representing the manner in which the plurality of users accessed the audiovisual file;

determining from the usage model a probability of a user seeking one or more segments while accessing the audiovisual file;

applying scalar quantization to derive a prefetching model from the probability to minimize a seeking distance to an anticipated next desired segment, wherein deriving the prefetching model includes representing the usage model as a probability function of a user seeking a particular segment, wherein the probability function p(x) includes;

p(x)=C×

P_p(x)×

P_s(x)

where;

x represents each of the segments of the audiovisual file,

C represents a normalization factor.

P_p(x) represents the access occurrences for each segment x, and

P_s(x) represents the seeking occurrences for each segment x; and

prefetching the segments in accordance with the prefetching model.

9. The method of claim 8, wherein the scalar quantization is solved using a Lloyd algorithm.

10. A computer-implemented method, comprising:

identifying a quantity of segments of a media file to be prefetched;

identifying a current region of a media file being accessed;

using a prefetching model, determining at least one next segment identified by a scheduling model as an expected next seeking destination from the current region, wherein using the prefetching model includes representing the usage model as a probability function of a user seeking a particular segment, wherein the probability function p(x) includes;

p(x)=C×

P_p(x)×

P_s(x)

where;

x represents each of the segments of the media file,

C represents a normalization factor,

P_p(x) represents the access occurrences for each segment x, and

P_s(x) represents the seeking occurrences for each segment x; and

prefetching the next segment in accordance with the prefetching model.

11. The method of claim 10, wherein the prefetching model used for each region of the media file is determined for each region of the media file.

12. The method of claim 10, wherein the quantity of segments to be prefetched is determined by at least one of:

available storage for caching prefetched segments;

available bandwidth by which the prefetched segments are retrieved; and

user preferences.

13. The method of claim 10, further comprising prefetching each of a quantity of next segments indicated as next segments identified by the prefetching model as expected next seeking destinations until the quantity of next segments reaches the quantity of segments to be prefetched.

14. The method of claim 13, wherein the prefetching model includes a hierarchical model, wherein:

the media file includes a plurality of regions, with at least a portion of the plurality of regions including a hierarchy of subregions, and at least one of the subregions includes a plurality of subregion segments; and

when seeking to a subregion results in the prefetching model wherein the plurality of next segments, combined with a plurality previously fetched segments, exceeds the quantity of segments, prefetching at least one segment from a subregion higher in the hierarchy of subregions is released to provide storage for prefetching at least one of the plurality of next segments.

15. The method of claim 14, wherein the hierarchial model includes a plurality of levels, and wherein a number of levels included in the hierarchial model is determined based on available storage for caching prefetched segments.