Media data streaming considering performance characteristics of the streaming path

Abstract

A method and system thereof for streaming media data are described. Media data comprising blocks of data are streamed in an order that is selected according to the performance characteristics of the network path used for the streaming.

1. A method of streaming media data in a network, said method comprising:
 receiving media data comprising blocks of data in a first order; 
 reordering said blocks of data in a second order different from said first order, said second order corresponding to an order that is selected according to performance characteristics, wherein said performance characteristics comprise delays associated with said path, wherein said delays comprise at least one of a propagation delay associated with data traveling over links in said path, a queue delay associated with nodes encountered on said path, and a retransmission delay associated with retransmitting lost data; and 
 streaming said blocks of data in said order that is selected according to said performance characteristics of a path used for said streaming. 
 
     
     
       2. The method of  claim 1  wherein said performance characteristics comprise data packet losses. 
     
     
       3. The method of  claim 1  wherein said blocks of data are characterized according to their relative importance, wherein said order is also selected according to said relative importance. 
     
     
       4. The method of  claim 1  wherein said blocks of data comprise frames of video data. 
     
     
       5. The method of  claim 4  wherein said frames are predictively encoded. 
     
     
       6. The method of  claim 1  wherein said streaming further comprises:
 sending a block of data ahead of time relative to when it would have been sent according to an initial intended order of streaming, wherein said block of data moves ahead a first number of positions relative to its position in said initial intended order. 
 
     
     
       7. The method of  claim 6  further comprising:
 delaying transmission of a second number of other blocks of data, wherein said first number and said second number are equal. 
 
     
     
       8. A method of streaming media data comprising blocks of data, said method comprising:
 predicting whether said blocks of data will arrive at a destination node on time for different orders of streaming; said predicting comprising:
 determining probabilities of various lengths of delay associated with a path to said destination node; 
 varying said probabilities resulting in a plurality of network performance models that characterize network performance; 
 determining, for each of said network performance models and for each of a number of different orders of streaming, a probability that said blocks of data will arrive at said destination node on time; and 
 selecting, for each of said network performance models, an order of streaming for which said probability that said blocks of data will arrive at said destination node on time is maximized; and 
 
 specifying an order for streaming said blocks of data using results from said predicting. 
 
     
     
       9. The method of  claim 8  wherein some portion of said various lengths of delay is estimated. 
     
     
       10. The method of  claim 8  wherein some portion of said various lengths of delay is based on measurements of actual performance along said path. 
     
     
       11. The method of  claim 8  wherein a network performance model comprises a probability density function. 
     
     
       12. The method of  claim 8  wherein a network performance model comprises a probability mass function. 
     
     
       13. The method of  claim 8  further comprising:
 for each of said network performance models, storing in a lookup table said order of streaming for which said probability is maximized. 
 
     
     
       14. The method of  claim 13  further comprising:
 determining a network performance model that characterizes delays associated with said path to said destination node; and 
 selecting from said lookup table an order of streaming corresponding to said network performance model. 
 
     
     
       15. The method of  claim 8  wherein said blocks of data are interrelated, wherein said predicting considers dependencies between said blocks. 
     
     
       16. The method of  claim 15  wherein said blocks of data comprise frames of video data that are predictively encoded. 
     
     
       17. The method of  claim 8  wherein said blocks of data are separated into groups of blocks, wherein blocks of data in a group are ordered in a periodic arrangement that is repeated from group to group, wherein said predicting is performed for a single group for each of said different orders of streaming. 
     
     
       18. The method of  claim 8  wherein said blocks of data are associated with an initial streaming order, wherein a different order of streaming is achieved by moving a block of data forward a first number of positions relative to said initial streaming order. 
     
     
       19. The method of  claim 18  wherein said different order of streaming is achieved by also moving a second number of blocks of data backward at least one position each relative to said initial streaming order, wherein said first number and said second number are equal. 
     
     
       20. The method of  claim 18  wherein said first number is limited to a predetermined value. 
     
     
       21. The method of  claim 8  further comprising:
 measuring performance characteristics of a path to said destination node; and 
 using measured performance characteristics in said predicting. 
 
     
     
       22. A method of streaming blocks of data over a network, said method comprising:
 receiving said blocks of data in a first order; 
 selecting an order for streaming said blocks of data, said order determined according to performance characteristics of a path used for said streaming, said selecting comprising:
 determining a network performance model that characterizes delays associated with said path; 
 selecting from a lookup table said order of streaming corresponding to said network performance model; and 
 reordering said blocks of data in a second order different from said first order, said second order corresponding to said order of streaming corresponding to said network performance model; and 
 
 streaming said blocks of data according to said second order. 
 
     
     
       23. The method of  claim 22  wherein said blocks of data constitute media data. 
     
     
       24. The method of  claim 23  wherein said blocks of data comprise predictively encoded media data. 
     
     
       25. The method of  claim 22  wherein said performance characteristics comprise delays associated with said path. 
     
     
       26. The method of  claim 25  wherein said delays comprise at least one of a propagation delay associated with data traveling over links in said path, a queue delay associated with nodes encountered on said path, and a retransmission delay associated with retransmitting lost data. 
     
     
       27. The method of  claim 22  comprising:
 predicting whether said blocks of data will arrive at a destination node on time for different orders of streaming; and 
 specifying an order for streaming said blocks of data using results from said predicting. 
 
     
     
       28. The method of  claim 22  comprising:
 measuring network performance characteristics associated with said path; and 
 selecting an order of streaming from said lookup table corresponding to measured network performance characteristics. 
 
     
     
       29. A non-transitory computer-usable storage medium having computer-readable program code embodied therein for causing a computer system to perform a method of streaming media data comprising blocks of data comprising:
 determining a probability of whether said blocks of data will arrive late at a destination node for different orders of streaming, said determining said probability comprising:
 determining probabilities of various lengths of delay associated with a path to said destination node; 
 varying said probabilities resulting in a plurality of network performance models that characterize delays associated with said path to said destination node: 
 determining, for each of said network performance models and for each of said different orders of streaming and for each of a number of different orders of streaming, a probability that said blocks of data will arrive at said destination node on time; and 
 selecting, for each of said network performance models, an order of streaming for which said probability that said blocks of data will arrive late at said destination node on time is minimized; and 
 
 specifying an order for streaming said blocks of data using said probability. 
 
     
     
       30. The non-transitory computer-usable storage medium of  claim 29  wherein said blocks of data comprise frames of video data that are predictively encoded. 
     
     
       31. The non-transitory computer-usable storage medium of  claim 29  wherein said blocks of data are associated with an initial streaming order, wherein a different order of streaming is achieved by moving, relative to said initial streaming order, a block of data forward a first number of positions and a second number of blocks of data backward at least one position each, wherein said first number and said second number are equal. 
     
     
       32. A system for streaming media data in a network, said system comprising:
 an input device for receiving media data comprising blocks of data, wherein said blocks of data are received in a first order; and 
 an output device for streaming said blocks of data in an order that is selected according to performance characteristics of a path used for said streaming, wherein said blocks of data are reordered in a second order different from said first order, said second order corresponding to said order that is selected according to said performance characteristics, wherein said performance characteristics comprise delays associated with said path, wherein said delays comprise at least one of a propagation delay associated with data traveling over links in said path, a queue delay associated with nodes encountered on said path, and a retransmission delay associated with retransmitting lost data. 
 
     
     
       33. The system of  claim 32  wherein said performance characteristics comprise data packet losses. 
     
     
       34. The system of  claim 32  wherein said blocks of data are characterized according to their relative importance, wherein said order is also selected according to said relative importance. 
     
     
       35. The system of  claim 32  wherein said blocks of data comprise frames of video data that are predictively encoded. 
     
     
       36. The system of  claim 32  wherein a block of data is sent ahead of time relative to when it would have been sent according to an initial intended order of streaming, wherein said block of data moves ahead a first number of positions relative to its position in said initial intended order. 
     
     
       37. A system for streaming blocks of data over a network, said system comprising:
 an input element for receiving said blocks of data in a first order; 
 a controller element for selecting an order for streaming said blocks of data, said order determined according to performance characteristics of a path used for said streaming, wherein said controller element reorders said blocks of data in a second order different from said first order, said second order corresponding to said order determined according to said performance characteristics, wherein said performance characteristics comprise delays associated with said path, wherein said delays comprise at least one of a propagation delay associated with data traveling over links in said path, a queue delay associated with nodes encountered on said path, and a retransmission delay associated with retransmitting lost data; and 
 an output element for streaming said blocks of data according to said second order. 
 
     
     
       38. The system of  claim 37  wherein said blocks of data constitute media data that are predictively encoded. 
     
     
       39. The system of  claim 37  wherein said order for streaming said blocks of data is specified according to a prediction of whether said blocks of data will arrive at a destination node on time. 
     
     
       40. The system of  claim 37  wherein said order for streaming said blocks of data is selected from a lookup table.