Source: http://www.google.com/patents/US7633887?dq=4052565
Timestamp: 2017-08-19 14:50:47
Document Index: 50195317

Matched Legal Cases: ['§ 119', '§ 112', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4', '§ 4']

Patent US7633887 - On demand peer-to-peer video streaming with multiple description coding - Google Patents
A peer-to-peer novel video streaming scheme is described in which each peer stores and streams videos to the requesting client peers. Each video is encoded into multiple descriptions and each description is placed on a different node. If a serving peer disconnects in the middle of a streaming session,...http://www.google.com/patents/US7633887?utm_source=gb-gplus-sharePatent US7633887 - On demand peer-to-peer video streaming with multiple description coding
Publication number US7633887 B2
Application number US 11/337,833
Also published as US7986637, US20060190615, US20100049867
Publication number 11337833, 337833, US 7633887 B2, US 7633887B2, US-B2-7633887, US7633887 B2, US7633887B2
Original Assignee Panwar Shivendra S, Ross Keith W, Yao Wang
Patent Citations (5), Non-Patent Citations (10), Referenced by (44), Classifications (18), Legal Events (5)
US 7633887 B2
P ( m , M ; r , Q ) = { P ( X = Qm / S ) , m = 0 , 1 , … , M - 1 ∑ l = M NS / Q P ( X = Ql / S ) , m = M
min D ( R 1 , … , R M ) s . t ∑ m = 1 M α m R m = Mr where α m = M m ( m + 1 ) , m = 1 , … , M - 1 and α M = 1 ;
determining a triple (M, r, Q) to be feasible if D(M, r, Q)dmax; and
P ( m , M ; r , Q ) = { P ( X = Qm / S ) , m = 0 , 1 , … , M - 1 ∑ l = M NS / Q P ( X = Ql / S ) , m = M ;
where dmax represents the distortion constraint, M represents a number of descriptions of the video, r represents a bit rate of each description, and Q represents a number of ongoing video sessions, with each session consisting of a multiple sub-streams;
min D ( R 1 , … , R M ) s . t ∑ m = 1 M α m R m = Mr where α m = M m ( m + 1 ) , m = 1 , … , M - 1 and α M = 1 ; and
determine a triple (M, r, Q) to be feasible if D(M, r, Q)≦dmax; and
Benefit is claimed, under 35 U.S.C. § 119(e)(1), to the filing date of U.S. provisional patent application Ser. No. 60/646,080 (referred to as “the '080 provisional”), titled “ON-DEMAND P2P VIDEO STREAMING WITH MULTIPLE DESCRIPTION CODING”, filed on Jan. 21, 2005, and listing Shivendra S. Panwar, Keith W. Ross and Yao Wang as the inventors, for any inventions disclosed in the manner provided by 35 U.S.C. § 112, ¶1. The '080 provisional application is expressly incorporated herein by reference. The scope of the present invention is not limited to any requirements of the specific embodiments described in the '080 provisional application.
FIG. 9 illustrates a video bit stream partitioned into sub-streams according to a multiple description—forward error correction (MD-FEC) video coding technique consistent with the present invention.
Referring back to block 315, the maximum distortion constraint and the availability of sever peers may be used in order to determine an optimal number of video sub-streams such that the maximum distortion constraint is not exceeded thus, ensuring high quality video streaming within a network. Exemplary techniques for performing these acts are described in § 4.4 below.
§ 4.3 Exemplary Apparatus Consistent with the Present Invention
§ 4.4 Refinements and Alternatives
§ 4.4.1 MD-FEC Video Coding
Multiple description (MD) video coding has become an active research area only in the past few years. Although various coders have been proposed (See, e.g., Y. Wang, R. Reibman, and S. Lin, “Multiple description coding for video communications,” Proc. IEEE Special issue on recent advances in video coding and delivery; A. Reibman, H. Jafarkhani, Y. Wang, and M. Orchard, “Multiple Description Coding for Video using Motion Compensated Prediction,” IEEE Trans. Circuit and System for Video Technology, pp. 193-204 (March 2002); and Y. Wang and S. Lin, “Error resilient video coding using multiple description motion compensation,” IEEE Trans. Circuit and System for Video Technology, vol. 12, pp. 438-453 (June 2002), all incorporated herein by reference), most coders generate a fairly small number of descriptions, with M=2 being the most common case. On the other hand, to fully explore the load balancing and error-resilience benefit from employing multiple peer-servers, a larger M is desired.
Instead of designing the source encoder to yield multiple descriptions directly, one can apply unequal forward error coding (FEC) to different parts of a scalable bitstream, commonly known as MD-FEC. (See, e.g., A. Albanese, J. Blomer, J. Edmonds, M. Luby, and M. Sudan, “Priority encoding transmission,” IEEE Trans. Inform. Theory, pp. 1737-1744 (November 1996); and G. Davis and J. Danskin, “Joint source and channel coding for image transmission over lossy packet networks,” Proc. SPIE Conf. Wavelet Applications to Digital Image Processing, (Denver, Colo., August 1996), both incorporated herein by reference.)
D ( R 1 , … , R M ) = ∑ m = 0 M P m D m ( R 1 , … , R M ) ( 1 )
min D ( R 1 , … , R M ) s . t ∑ m = 1 M α m R m = Mr where α m = M m ( m + 1 ) , m = 1 , … , M - 1 and α M = 1 ( 2 )
Let D(M, r, P) denote the optimal value of this optimization problem. This is a non-linear optimal resource allocation problem. Fast algorithms for solving this optimization problem have been presented. (See, e.g., Puri and K. Ramchandran, “Multiple description source coding through forward error correction codes,” 33rd Asilomar Conf. Siqnals, Systems and Computers, (October 1999); A. E. Mohr, R. E. Ladner, and E. A. Riskin, “Approximately optimal assignment for unequal loss protection,” Proc. IEEE Int. Conf. Image Processing, (Vancouver, BC, September 2000); and V. Stankovic, R. Hamzaoui, and Z. Xiong, “Packet loss protection of embedded data with fast local search,” Proc. IEEE Int. Conf. Image Processing, (Rochester, N.Y., September 2002), all incorporated herein by reference.) Assume that the multiple descriptions are created with MD-FEC, and that the partition (R1, R2, . . . , RM) for a given M, r, and P is obtained by solving the optimization problem (2).
§ 4.4.2 Maximizing the Number of Sessions
max Q s . t D ( M , r , Q , ϕ ) ≤ d max ( 3 )
P ( X = k ) = ( N k ) p k ( 1 - p ) N - k , k = 0 , … , N
P ( m , M ; r , Q ) = { P ( X = Qm / S ) , m = 0 , 1 , … , M - 1 ∑ l = m NS / Q P ( X = Ql / S ) , m = M ( 4 )
§ 4.4.3 Optimum Value of M
{ P ( m , M ; r , Q 1 * ) = P ( m , M + 1 ; r , Q 1 * ) , m = 0 , 1 , … , M - 1 P ( M , M ; r , Q 1 * ) = P ( M , M + 1 ; r , Q 1 * ) + P ( M + 1 , M + 1 ; r , Q 1 * ) ( 7 )
D ~ ( M + 1 , r , Q 1 * ) = ∑ m = 1 M + 1 P ( m , M + 1 ; r , Q 1 * ) D ~ ( m , M + 1 , r ) = ∑ m = 1 M - 1 P ( m , M + 1 ; r , Q 1 * ) D ~ ( m , M + 1 , r ) + [ P ( M , M + 1 ; r , Q 1 * ) + P ( M + 1 , M + 1 ; r , Q 1 * ) ] · D ~ ( M , M + 1 , r ) = ∑ m = 1 M - 1 P ( m , M ; r , Q 1 * ) D ( m , M , r ) + P ( M , M ; r , Q 1 * ) D ( M , M , r ) = ∑ m = 1 M P ( m , M ; r , Q 1 * ) D ( m , M , r ) = D ( M , r , Q 1 * )
§ 4.4.4 Average Distortion Analysis for Gaussian Source
D m ( R 1 , … , R M ) = ∑ m = 0 M P m σ 2 · 2 - 2 R m = P 0 σ 2 + ∑ m = 1 M P m σ 2 · 2 - 2 R m ( 11 )
L ( R 1 , … , R M , λ ) = P 0 σ 2 + ∑ m = 1 M P m D ( R m ) + λ ( ∑ m = 1 M α m R m - Mr ) ( 12 )
P m α m ⅆ D ( R m ) ⅆ R m + λ = 0 where α m = M m ( m + 1 ) , m = 1 , … , M - 1 , and α m = 1 ( 13 )
R m = - log 2 ( λ β m c ) / 2 where λ = [ 2 - 2 Mr ∏ m = 1 M ( β m c ) α m ] 1 ∑ m = 1 M α m and β m = α m / P m , c = 2 σ 2 ln 2. ( 14 )
D ( M , r , Q ) = σ 2 [ P 0 + λ c ∑ m = 1 M M m ( m + 1 ) ] ( 15 )
From FIG. 11, notice that when r is greater than some value (around 25), the average distortion increases as r becomes larger. As r decreases, the total rate of each video, M r, decreases but the number of descriptions per session increases (since m=XCu/Qr). If the total rate is near the flat tail of an R-D curve, the decrease in total rate has little negative impact on video quality but an increase in the number of descriptions per session provides stronger resilience to network loss. The more reliable network offsets the video quality degradation due to smaller total rate. However, when r is very small, the average distortion will increase as r decreases, since according to the R-D curve, D(Rm)=σ2·2−2R m , the average distortion is large even if all descriptions are received.
§ 4.4.5 Business Models
§ 4.4.6 Provisioning
§ 4.4.7 Session Management
§ 4.4.8 Location of Management Functions
§ 4.5 Exampels
§ 4.5.1 Simple Example
§ 4.5.2 Simulations
The Foreman video sequence was coded in CIF (352×288) resolution into a scalable bit stream using the MPEG-4 FGS (See, e.g., MoMusys code, “MPEG4 verification model version 18.0,” ISO/IEC JTC1/SC291WG11 Coding of Moving Pictures and Audio, (January 2001), incorporated herein by reference.), at a base layer rate of 150 kbps. Each Group of Frames (GOF) had the duration of T=1 second and comprises 15 frames. The output bits from each GOF were converted to M descriptions using the MD-FEC method, where M is varied from 4 to 32. The total rate of a video after MD-FEC was set to be either 512 kbps, 576 kbps or 640 kbps.
§ 4.5.2.1 Network Setting
Admission Policy: Parameter Qmax was set. If the total number of sessions in the network was greater than Qmax, then the new requests were blocked. In the simulations, six values for Qmax—60, 80, 100, 120, 150 and 180—were chosen.
I ( j , m , i ) = ∑ k = 1 j - 1 M · b k + b j · ( m - 1 ) + i
The description indexed by I(j,m,i) was put on the node I(j,m,i) mod N.
§ 4.5.2.2 Simulation Results
US7046733 Mar 30, 2001 May 16, 2006 Matsushita Electric Industrial Co., Ltd. Data sequencing method to improve transmission of self-similar data in a multi-node network
US20020174443 Mar 30, 2001 Nov 21, 2002 Dennis Bushmitch Data sequencing method to improve transmission of self-similar data in a multi-node network
1 Albanese et al., "Priority encoding transmission," IEEE Trans. Inform. Theory, 1996, 1737-1744.
2 Davis et al., "Joint source and channel for image transmission over lossy packet networks," Proc. SPIE Conf. Wavelet Application to Digital Image Processing, 1996.
3 Mohr et al., "Approximately optimal assignment for unequal loss protection," Proc. IEEE Int. Conf. Image Processing, 2000.
4 MoMusys code, "MPEG4 verification model version 18.0," ISO/IECJTC1/SC29/WG11 Coding of Moving Pictures and Audio, 2001.
5 Puri et al., "Multiple description source coding through forward error correction codes," 33rd Asilomar Cong. Signals, Systems and Computers, 1999.
6 Reibman et al., "Multiple Description Coding for Video using Motion Compensated Prediction," IEEE Trans. Circuit and System for Video Technology, 2002, 193-204.
7 Screen Shot from the Webpage: pplive.com/English/index.shtml, on Jan. 23, 2006.
8 Stankovic et al., "Packet loss protection of embedded data with fast local search," Proc. IEEE Int. Conf. Image Processing, 2002.
9 Wang et al., "Eroor resilient video coding using multiple description motion compensation," IEEE Trans Circuit System for Video Technology, 2002, 12, 438-453.
10 Wang et al., "Multiple description coding for video," Proc. IEEE Special Issue on recent advances in video coding and delivery, 2005.
US8689258 Feb 18, 2011 Apr 1, 2014 Echostar Technologies L.L.C. Apparatus, systems and methods for accessing an initial portion of a media content event
US9426516 Dec 20, 2013 Aug 23, 2016 Echostar Technologies L.L.C. Apparatus, systems and methods for accessing an initial portion of a media content event
US9544366 Dec 19, 2012 Jan 10, 2017 Hive Streaming Ab Highest bandwidth download request policy in a live streaming P2P network
US20070268362 * May 22, 2006 Nov 22, 2007 Matthew James West Compressed data
US20080162718 * Jul 31, 2006 Jul 3, 2008 Yongmin Zhang Method and Apparatus for Transmitting Data in Blocks
US20150222874 * Dec 23, 2014 Aug 6, 2015 Thomson Licensing Distribution of audio visual content for display devices
U.S. Classification 370/254, 709/231, 709/239
Cooperative Classification H04L65/607, H04L65/4084, H04N21/64792, H04N21/4788, H04L29/06027, H04N21/6473, H04N21/8405, H04N21/2668, H04N21/482, H04N21/632, H04L67/1085, H04L67/1048, H04L67/1046, H04L67/104
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:PANWAR, SHIVENDRA S.;ROSS, KEITH W.;WANG, YAO;REEL/FRAME:017550/0285;SIGNING DATES FROM 20060320 TO 20060321
Free format text: LICENSE;ASSIGNOR:POLYTECHNIC UNIVERSITY;REEL/FRAME:019750/0527