System for recovering lost information in a data stream

• US 6,445,717 B1
• Filed: 05/01/1998
• Issued: 09/03/2002
• Est. Priority Date: 05/01/1998
• Status: Expired due to Term

• Current Assignee: Niwot Networks Incorporated
• Original Assignee: Niwot Networks Incorporated
• Inventors: Gibson, William A., Noble, George E., Stearns, Chris J.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): LOGSDON, JOSEPH B
• Application Number:
  US09/071,103
• Time in Patent Office: 1,586 Days
• Field of Search: 370/464, 370/465, 370/468, 370/473, 370/474, 370/476, 370/912, 709/230, 709/236, 709/237, 714/1, 714/48, 714/701, 714/746, 714/747, 714/748, 714/749, 714/751, 714/752, 714/761, 714/762, 714/774, 714/776, 714/779, 714/799, 714/800
• US Class Current: 370/473
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 1/0071 Use of interleaving interleaving per se H03M13/27
• CPC Class Codes: H04L 1/0075 Transmission of coding parameters to receiver H04L1/0023 takes precedence
• CPC Class Codes: H04L 1/0083 Formatting with frames or packets; Protocol or part of protocol for error control
• CPC Class Codes: H04L 2212/00 Encapsulation of packets
• CPC Class Codes: H04L 65/1101 Session protocols
• CPC Class Codes: H04L 65/70 Media network packetisation
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 69/26 Special purpose or proprietary protocols or architectures network applications for proprietary or special purpose networking environments H04L67/12
• CPC Class Codes: H04L 69/326 in the transport layer [OSI layer 4] H04L69/16 takes precedence
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 370/912 Packet communications

Abstract

Data which is transmitted over the internet or other transmission networks is first divided up into individual information packets, transmitted and then reassembled into useful data after reception. Parity packets are included in with the information packets in the transmission of data in order to enable the regeneration of any information packets which were lost or damaged during transmission. The grouping of information packets and parity packets derived therefrom is termed a chunk. Chunk arrangements to recover from all cases of single and double lost packets are disclosed. Bursts of lost packets are recovered by interleaving the transmission of packets from different chunks. If the recovery is not successful then retransmission occurs in a manner similar to TCP.

Claims

1. 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;

generating, at said first host, at least one parity payload corresponding to each Chunk Information Block and derived from a subset of said one or more information payloads within said Chunk Information Block;

transmitting, from said first host to said second host, said one or more information payloads along with the corresponding said at least one parity payload;

receiving, in said second host, said one or more information payloads and said corresponding said at least one parity payload;

detecting, in said second host, any problems in receipt of said plurality of information payloads;

recovering, in said second host, in response to the step of detecting, 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 acknowledgement 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; and

retransmitting, from said first host to said second host, said one or more information payloads along with the corresponding said at least one parity payload in response to failure to receive said acknowledgement within an allowed time.

2. The method of claim 1 further comprising the steps of:

before transmitting, from said first host to said second host, said one or more information payloads first converting, in said first host, each information payload of said plurality of information payloads and each parity payload of said at least one parity payload into a corresponding transmission packet by addition of a header wherein said header includes information identifying a type of the packet as containing an information payload or a parity payload and wherein said header includes information identifying the information block from which the transmission packet is derived and wherein said header includes information identifying which packet the transmission packet is with respect to other transmission packets in the block from which the transmission packet is derived; and

after receiving, in said second host, said transmission packets, arranging the payloads regardless of the order in which they were transmitted or received into a logical order in accordance with information block from which they were derived prior to transmission.

3. The method of claim 2 wherein the set of transmission packets derived from each Chunk Information Block is termed a Chunk and the set of M Chunks derived from each Super Information Block is termed a SuperChunk, with the step of:

before transmitting, from said first host to said second host, interleaving the packets M ways such that, if M is greater than 1, no two packets from the same chunk are transmitted adjacently in time.

4. The method of claim 3 with the additional steps of:

maintaining, in said first host, a history of acknowledgements received and retransmissions sent;

before dividing, in said first host, said data stream into at least one Super Information Block;

selectively changing the value of M based on a configuration option or retransmission history such that subsequent SuperChunks may be transmitted with a different value of M.

5. The method of claim 4 with the additional steps of:

decreasing the value of M should the retransmission history reflect few retransmissions,

increasing the value of M should the retransmission history reflect excess retransmissions,

leaving unchanged the value of M should the retransmission history reflect acceptable retransmissions.

6. The method of claim 2 wherein the step of generating said at least one parity payload comprises the step of:

generating one parity payload corresponding to each Chunk Information Block where said each Chunk Information Block includes at most N information payloads such that any 1 lost payload may be recovered at the destination.

7. The method of claim 6 wherein the set of transmission packets derived from each Chunk Information Block is termed a Chunk, with the additional steps of:

maintaining, in said first host, a retransmission history of acknowledgements received and retransmissions sent;

one of;

increasing the value of N should the retransmission history reflect few retransmissions,

decreasing the value of N should the retransmission history reflect excess retransmissions,

leaving unchanged the value of N should the retransmission history reflect acceptable retransmissions; and

wherein said header further includes a N identifier to identify the value of N used in generating said N parity payloads.

8. The method of claim 2 wherein the step of generating said at least one parity payload comprises the step of:

generating N parity payloads corresponding to each Chunk Information Block where N is an integer greater than 2 and wherein said each Chunk Information Block includes at most ((2^N−

1)−

N) information payloads such that any 2 lost payloads may be recovered at the destination.

9. The method of claim 8 wherein the set of transmission packets derived from each Chunk Information Block is termed a Chunk, with the additional steps of:

maintaining, in said first host, a retransmission history of acknowledgements received and retransmissions sent;

one of;

increasing the value of N should the retransmission history reflect few retransmissions,

decreasing the value of N should the retransmission history reflect excess retransmissions,

leaving unchanged the value of N should the retransmission history reflect acceptable retransmissions; and

wherein said header further includes a N identifier to identify the value of N used in generating said N parity payloads.

10. The method of claim 2 wherein, in said first host, the set of transmission packets derived from each Chunk Information Block is termed a Chunk and wherein the step of generating said at least one parity payload comprises the steps of:

selecting a selected parity type from a plurality of parity types;

generating said at least one parity payload using the selected parity type; and

wherein said header further includes a parity type identifier to identify the selected parity type used in said Chunk.

11. The method of claim 10 wherein the step of generating using the selected parity type includes the step of:

using at least two different selected parity types of said plurality of parity types for generation of parity payloads in different Chunks.

12. The method of claim 10 with the additional step of:

maintaining, in said first host, a retransmission history of acknowledgements received and retransmissions sent; and

wherein generating using the selected parity type includes the steps of;

generating, in response to selecting a first parity type, a single parity payload in each Chunk wherein said Chunk includes N information payloads where N is an integer greater 1;

generating, in response to selecting a second parity type, N parity payloads in each Chunk where N is an integer greater than 2 and wherein said each Chunk includes at most ((2^N−

1)−

N) information payloads.

13. The method of claim 12 wherein the step of maintaining a retransmission history includes the step of:

selecting a new selected parity type from said plurality of parity types based on said retransmission history; and

wherein the subsequent step of generating, at said first host, said at least one parity payload is done in accordance with said new selected parity type.

14. The method of claim 13 wherein the step of selecting said new selected parity type comprises one of:

switching from the first parity type to the second parity type should the retransmission history reflect excess retransmissions,

switching from the second parity type to the first parity type should the retransmission history reflect few retransmissions,

leaving unchanged the parity type should the retransmission history reflect acceptable retransmissions.

15. The method of claim 10 wherein said header further includes a value N that defines the maximum number of packets that may be in the Chunk.

16. The method of claim 10 wherein said header further includes a chunk length that defines the number of information payload bytes in the Chunk.

17. The method of claim 2 wherein said header further includes a timestamp value and a timestamp echo reply.

18. 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.

19. The method of claim 18 further comprising the step of:

before transmitting, from said first host to said second host, said one or more information payloads first converting, in said first host, each information payload of said plurality of information payloads and each parity payload of the zero or more parity payloads into a corresponding transmission packet by addition of a header wherein said header includes information identifying a type of the packet as containing an information payload or a parity payload and wherein said header includes information identifying the information block from which the transmission packet is derived and wherein said header includes information identifying which packet the transmission packet is with respect to other transmission packets in the block from which the transmission packet is derived; and

after receiving, in said second host, said transmission packets, arranging the payloads regardless of the order in which they were transmitted or received into a logical order in accordance with information block from which they were derived prior to transmission.

20. The method of claim 19 wherein said header further includes a timestamp value and a timestamp echo reply.

21. The method of claim 19 wherein, in said first host, the set of transmission packets derived from each Chunk Information Block is termed a Chunk and wherein:

said header further includes a parity type identifier to identify the selected parity type used in said Chunk; and

wherein the step of selectively generating said zero or more parity payloads comprises the steps of;

selecting a selected parity type from a plurality of parity types;

generating said parity payload if the selected parity type specifies that parity packets are to be generated;

or

not generating said parity payload if the selected parity type specifies that parity packets are not to be generated.

22. The method of claim 21 wherein selectively generating using the selected parity type includes one of:

generating, in response to selecting a first parity type, no parity payload in each Chunk wherein said Chunk includes 1 or more information payloads;

or

generating, in response to selecting a second parity type, 1 parity payloads in each Chunk where N is an integer greater than 1 and wherein said each Chunk includes at most N information payloads.

23. The method of claim 22 wherein the step of selecting said new selected parity type comprises one of:

switching from the first parity type to the second parity type should the retransmission history reflect excess retransmissions,

switching from the second parity type to the first parity type should the retransmission history reflect few retransmissions,

leaving unchanged the parity type should the retransmission history reflect acceptable retransmissions.

24. The method of claim 22 wherein said header further includes the value of N when the second parity type is specified.

25. The method of claim 24 wherein the set of transmission packets derived from each Chunk Information Block is termed a Chunk, with the additional step of one of:

increasing the value of N should the retransmission history reflect few retransmissions,

decreasing the value of N should the retransmission history reflect excess retransmissions,

leaving unchanged the value of N should the retransmission history reflect acceptable retransmissions.

26. The method of claim 21 wherein selectively generating using the selected parity type includes one of:

generating, in response to selecting a first parity type, no parity payload in each Chunk wherein said Chunk includes 1 information payloads;

generating, in response to selecting a second parity type, 1 parity payloads in each Chunk where N is an integer greater than 1 and wherein said each Chunk includes at most N information payloads;

or

generating, in response to selecting a third parity type, N parity payloads in each Chunk where N is an integer greater than 2 and wherein said each Chunk includes at most 2^N−

1−

N information payloads.

27. The method of claim 26 wherein the step of selecting said new selected parity type comprises one of:

switching from the first parity type to the second parity type should the retransmission history reflect excess retransmissions,

switching from the first parity type to the third parity type should the retransmission history reflect excess retransmissions,

switching from the second parity type to the third parity type should the retransmission history reflect excess retransmissions,

switching from the third parity type to the second parity type should the retransmission history reflect few retransmissions,

switching from the third parity type to the first parity type should the retransmission history reflect few retransmissions,

switching from the second parity type to the first parity type should the retransmission history reflect few retransmissions,

leaving unchanged the parity type should the retransmission history reflect acceptable retransmissions.

28. The method of claim 26 wherein said header further includes the value of N when either the second parity type or third parity type is selected.

29. The method of claim 28 wherein said header further includes the value of N when the second parity type is specified and with the additional step of one of:

increasing the value of N should the retransmission history reflect few retransmissions,

decreasing the value of N should the retransmission history reflect excess retransmissions,

leaving unchanged the value of N should the retransmission history reflect acceptable retransmissions.

30. 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 2^N−

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.

31. The method of claim 30 further comprising the steps of:

before transmitting, from said first host to said second host, said one or more information payloads first converting, in said first host, each information payload of said up to 2^N−

1−

N information payloads and each parity payload of said N parity payloads into a corresponding transmission packet by addition of a header wherein said header includes information identifying a type of the packet as containing an information payload or a parity payload and wherein said header includes information identifying the Chunk Information Block from which the transmission packet is derived and wherein said header includes information identifying which packet the transmission packet is with respect to other transmission packets in the Chunk Information Block from which the transmission packet is derived; and

after receiving, in said second host, said transmission packets, arranging the payloads regardless of the order in which they were transmitted or received into a logical order in accordance with the Chunk Information Block from which they were derived prior to transmission.

32. The method of claim 31 wherein the set of transmission packets derived from each Chunk Information Block is termed a Chunk and the set of M Chunks derived from each Super Information Block is termed a SuperChunk, with the step of:

before transmitting, from said first host to said second host, interleaving the packets M ways such that, if M is greater than 1, no two packets from the same chunk are transmitted adjacently in time.

33. The method of claim 31 wherein the said header further includes the value of N.

34. 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 2^N−

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.