Generating and communicating source identification information to enable reliable communications
First Claim
1. A method for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising:
- generating source identification data from the K source data units;
transmitting a first data stream to a receiver, wherein the first data stream comprises a set of the source data units, wherein the first data stream does not have the source identification data; and
transmitting a second data stream to the receiver, wherein the second data stream comprises the source identification data, wherein the second data stream is distinct from the first data stream, wherein the source identification data is distinct from the set of the source data units transmitted on the first data stream, and wherein the source identification data is usable to identify source data units in the set of source data units transmitted on the first data stream.
2 Assignments
0 Petitions
Accused Products
Abstract
A method of generating Source Identification information from a source packet stream and reliably transmitting the Source Identification information from a source to a destination over a communications channel is provided. The method operates on a set of source packets, wherein Source Identification information for each source packet to be transmitted is derived and delivered with the Source Identification information of all or most other source packets of an associated source block. The method includes techniques to minimize the network bandwidth required to deliver Source Identification information and techniques to overcome network impairments. When combined with FEC techniques, retransmission techniques, or combinations of FEC techniques and retransmission techniques, the methods described herein allow receivers to recover lost source packets, while simultaneously ensuring that the original source packets are not modified and thereby ensuring backwards compatibility for legacy receivers.
-
Citations
35 Claims
-
1. A method for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising:
-
generating source identification data from the K source data units; transmitting a first data stream to a receiver, wherein the first data stream comprises a set of the source data units, wherein the first data stream does not have the source identification data; and transmitting a second data stream to the receiver, wherein the second data stream comprises the source identification data, wherein the second data stream is distinct from the first data stream, wherein the source identification data is distinct from the set of the source data units transmitted on the first data stream, and wherein the source identification data is usable to identify source data units in the set of source data units transmitted on the first data stream. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14, 15)
-
-
12. A method for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising:
-
generating source identification data from the K source data units, comprising; a) creating an ordered set S from each of the K source data units; i) applying a hash function, Hi, to each member of S, wherein Hi maps the members of S to one of a possible L hash outputs and wherein Hi maps at least X of the members of S to a unique hash output; ii) creating a vector corresponding to the L hash outputs, wherein the vector indicates which of the L hash outputs experience collisions and which of the L hash outputs uniquely map to a member of S; iii) creating a set, Si, comprising the elements of S that do not map to a unique hash output; iv) iterating steps i-iii until either Si is an empty set or a maximum number of iterations have been executed, wherein for each iteration of steps i-iii Si is used as S, wherein for each iteration Hi is a hash function that differs from the hash function used during the previous iteration of steps i-iii, wherein for each iteration the values of L and X can change; and b) generating source identification data from the vectors created during each iteration of steps i-iii; c) transmitting a first data stream to a receiver, wherein the first data stream comprises a set of the source data units; and d) transmitting a second data stream to the receiver, wherein the second data stream comprises the source identification data. - View Dependent Claims (13)
-
-
16. A method for receiving source identification data and associating the source identification data with source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising:
-
receiving a plurality of source data units from a first data stream, wherein the first data stream does not have the source identification data; receiving source identification data from a second data stream, wherein the second data stream is distinct from the first data stream; and associating the source identification data obtained from a set of packets from the second data stream with the plurality of source data units obtained from packets distinct from the set of packets from the second data stream, wherein the source identification data is usable to identify source data units in the plurality of source data units. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 32, 33)
-
-
26. A method for receiving source identification data and associating the source identification data with source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the method comprising:
-
receiving a plurality of source data units from a first data stream; receiving source identification data from a second data stream; and associating the source identification data with the plurality of source data units comprises; i) creating a set, S, from each of the plurality of source data units; ii) applying a hash function, Hi, to each member of S to obtain a hashed output associated with each of member of S, wherein Hi maps each of the members of S to one of a possible L hash outputs; iii) determining which of the hashed outputs uniquely identify the source data unit associated with the hashed output; iv) if it is determined that a hashed output does uniquely identify a source data unit, removing the uniquely identified source data unit from S and associating a proper set of identification data from the source identification data with the uniquely identified source data unit; and v) if it is determined that one of the hashed output is not unique, iterating steps i-iii unit S is an empty set or until a maximum number of iterations have been executed, wherein for each iteration Hi is a hash function that differs from the hash function used during the pervious iteration of steps ii-iv with a potentially different value of L. - View Dependent Claims (27, 28, 29, 30, 31)
-
-
34. A system for generating and transmitting source identification data for source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the system comprising:
-
means for generating source identification data from the K source data units; and means for transmitting a first data stream and a second data stream to a receiver, wherein the first data stream comprises a set of the source data units, wherein the first data stream does not have the source identification data, wherein the second data stream comprises the source identification data, wherein the second data stream is distinct from the first data stream, wherein the source identification data is distinct from the set of the source data units transmitted on the first data stream, and wherein the source identification data is usable to identify source data units in the set of source data units transmitted on the first data stream.
-
-
35. A system for receiving source identification data and associating the source identification data with source data, wherein the source data has been divided into K source data units, wherein K is greater than one, wherein the source identification data can be used to identify the position of source data units relative to other source data units and to identify lost or corrupted source data units, the system comprising:
-
means for receiving a plurality of source data units from a first data stream and receiving source identification data from a second data stream, wherein the first data stream does not have the source identification data, wherein the second data stream is distinct from the first data stream; and means for associating the source identification data obtained from a set of packets from the second data stream with the plurality of source data units obtained from packets distinct from the set of packets from the second data stream, wherein the source identification data is usable to identify source data units in the plurality of source data units.
-
Specification