System for recovering lost information in a data stream

A method for use in transmitting a data stream over a network between a first host and a second host, said method comprising the steps of:

• dividing, at said first host, said data stream into at least one Super Information Block;
• dividing, at said first host, said Super Information Block into M, where M is at least one, Chunk Information Blocks wherein each Chunk Information Block includes one or more information payloads;
• selectively generating, at said first host, zero or more parity payloads corresponding to each Chunk Information Block and derived from a subset of said one or more information payloads within said Chunk Information Block wherein said zero or more parity payloads is selectively generated in accordance with a configuration option and retransmission history associated with said method;
• transmitting, from said first host to said second host, said plurality of information payloads along with any corresponding said at least one parity payload;
• receiving, in said second host, said plurality of information payloads and any corresponding said at least one parity payload;
• detecting, in said second host, any problems in receipt of said plurality of information payloads;
• determining, in said second host, whether any of said at least one parity packet have been received;
• recovering, in said second host, in response to the step of detecting and in response to the determination that said at least one parity packet has been received, lost payloads of said plurality of information payloads using said corresponding said at least one parity payload;
• sending an acknowledgment from said second host to said first host indicating whether retransmission of at least one identified payload of said plurality of information payloads is required;
• receiving said acknowledgment in said first host;
• retransmitting, from said first host to said second host, said at least one identified payload in response to receipt of said acknowledgement indicating that retransmission is required;
• retransmitting, from said first host to said second host, said plurality of information payloads along with any corresponding said at least one parity payload in response to failure to receive said acknowledgement within an allowed time;
• and
• updating, in said first host, a retransmission history of acknowledgements received and retransmissions sent.

A method for use in transmitting a data stream over a network between a first host and a second host, said method comprising the steps of:

• dividing, at said first host, said data stream into at least one Super Information Block;
• dividing, at said first host, said Super Information Block into M, where M is at least one, Chunk Information Blocks wherein each Chunk Information Block up to 2N−1−N information payloads where N is greater than 2;
• generating, at said first host, N parity payloads corresponding to each Chunk Information Block and derived from a subset of the plurality of information payloads within the corresponding said Chunk Information Block;
• transmitting, from said first host to said second host, the plurality of information payloads along with the corresponding said N parity payloads;
• receiving, in said second host, information payloads and parity payloads transmitted from said first host;
• detecting, in said second host, any lost information payloads;
• and
• recovering, in said second host, in response to the step of detecting, said lost information payloads using the received information payloads and received parity payloads.

A method for use in transmitting a data stream over a network between a first host and a second host, said method comprising the steps of:

• dividing, at said first host, said data stream into Super Information Blocks;
• selecting a value M greater than or equal to 1;
• dividing each Super Information Block into M Chunk Information Blocks;
• dividing each Chunk Information Block into at least one Information Packet;
• selecting a parity type to be used in creation of Parity Packets wherein said parity type is selected from the group consisting of:
• a first parity type where none of said Parity Packets are generated;
• a second parity type where one of said Parity Packets is generated per chunk derived from N Information packets;
• and
• a third parity type where N of said Parity Packets are generated per chunk derived from up to 2N−1−N Information packets where the arrangement of derivation is such that the Information Packets can all be reconstructed even if any two of the set of Information Packets and Parity Packets are lost;
• building a header for each Information Packet in each Chunk wherein said Chunk includes the Information Packets and any Parity Packets associated with a corresponding Chunk Information Block and wherein each header contains:
• a Sequence Number which indicates the first byte position in the data stream from which said Chunk Information Block was divided;
• a Chunk length which is the number of data stream bytes contained in said Chunk Information Block;
• a redtype indicating both which of said plurality of parity types was selected to arrange this chunk and the value of N for said second and third parity types;
• a redwhich which is unique for each packet in said Chunk, identifying whether it is a parity or a information packet and which packet it is;
• a packet payload length which indicates the number of data stream bytes contained in this particular Information Packet;
• an ACK TCP flag and Acknowledgement Number such that if the ACK TCP flag is on, the receiving portion of said first host expects the next chunk received from said second host to have that value as its sequence number;
• a Timestamp Value which is approximately the local time at said first host when the Chunk is to be sent;
• and
• a Timestamp Echo Reply which, when the ACK TCP flag is on, is the value from the Timestamp received within the chunk which is being acknowledged by the acknowledgment;
• building a header for each Parity Packet in each Chunk wherein said header contains:
• a Sequence Number which indicates the first byte position in the data stream from which said Chunk Information Block was divided;
• a redtype indicating both which of said plurality of parity types was used to arrange this chunk and the value of N for said second and third parity types;
• a redwhich which is unique for each packet in said Chunk, identifying whether it is a parity or a information packet and which packet it is;
• and
• a packet payload length which indicates the number of parity payload bytes contained in the Parity Packet;
• transmitting from said first host to said second host the Information Packets and the Parity Packets of said Super Information Block wherein the packets from different Chunks are interleaved M ways;
• receiving, in said second host, the transmitted packets;
• arranging, in said second host, said interleaved packets into their logical order, regardless of the order of their reception wherein said logical order is determined in accordance with the Sequence Number and the redwhich and the redtype in the header of each received packet;
• detecting, in said second host, lost Information Packets;
• attempting recovery, in said second host, of the data stream information in said lost Information Packets;
• sending an acknowledgment from said second host to said first host indicating the next data stream byte expected from said first host wherein said acknowledgment has a header including said Time Stamp Echo Reply and including said ACK TCP and including said Acknowledgement Number and wherein said ACK TCP flag is on;
• receiving said acknowledgment in said first host;
• retransmitting Information Packets and Parity Packets in response to receipt of duplicate acknowledgments or in response to failure to receive acknowledgments;
• maintaining a history of retransmissions;
• and
• selecting, in said first host, new values of said M, said parity type, and said N to change the redundancy of the transmission of said data stream in response to said retransmission history.