System and method for storing a sequential data stream

Abstract

The present invention provides an improved apparatus and method for the receipt of high-speed sequential data streams. It utilizes the concept of banked memories to reduce the required speed and size of the input buffers used to receive the data streams. This allows the device to employ large, relatively slow memory elements, thereby permitting large amounts of sequential data to be stored by the receiving device. Using control information that was written as the data was being stored in the memory banks, a reordering element is later able to retrieve the data elements from the plurality of memory banks, in an order that is different from that in which the stream was received, and to reassemble the data stream into the original sequence.

What is claimed: 
     
       1. A device for receiving and storing a data stream comprising a plurality of data elements, transmitted in a predetermined sequence, and later retransmitting said data elements in said predetermined sequence, said device comprising:
 a plurality of storage elements, wherein each of said storage elements selectively receives and stores a portion of said data elements in a first ordered sequence; 
 a logic element, wherein said logic element generates and stores information associated with said data stream, and generates and transmits status information associated with each of said stored data elements based on said information associated with said data stream; and 
 a reordering element, wherein said reordering element receives said stored data elements from said plurality of storage elements and said associated status information from said logic element in a second ordered sequence, stores said data elements and retransmits said data elements in said predetermined sequence. 
 
     
     
       2. The device of  claim 1 , wherein said first and said second ordered sequences are the same. 
     
     
       3. The device of  claim 1 , wherein said status information comprises information related to the relative position of said data element in said stream. 
     
     
       4. The device of  claim 1 , wherein said first ordered sequence is repeated after each one of said plurality of storage elements receives one data element from said stream. 
     
     
       5. The device of  claim 1 , wherein said second ordered sequence is repeated after said reordering element receives one data element from each one of said plurality of storage elements. 
     
     
       6. The device of  claim 1 , wherein said reordering element creates revised status information based on said status information, and stores said revised status information. 
     
     
       7. The device of  claim 1 , wherein said reordering element further comprises a plurality of individually addressable storage elements and a write control logic element adapted to determine into which of said plurality of individually addressable storage elements said stored data element is stored based on said associated status. 
     
     
       8. The device of  claim 1 , wherein said reordering element further comprises a first plurality of individually addressable storage elements, a second plurality of individually addressable storage elements and a write control logic element adapted to determine into which plurality of individually addressable storage elements said stored data element is stored based on said second ordered sequence in which said stored data elements are received, wherein said first plurality receives data elements from said second plurality and from said storage elements in said predetermined sequence. 
     
     
       9. The device of  claim 1 , wherein said reordering element further comprises a first plurality of individually addressable storage elements, a second plurality of individually addressable storage elements and a write control logic element adapted to determine into which storage element of said second plurality said data element is to be stored, and wherein said first plurality of addressable storage elements receives data elements from said second plurality of addressable storage elements in said predetermined sequence. 
     
     
       10. A method of receiving and storing a data stream comprising a plurality of data elements, transmitted in a predetermined sequence, and later retransmitting said data elements in said predetermined sequence, said method comprising:
 a. providing a plurality of storage elements, each adapted to selectively receive and store a portion of said data elements, and a reordering element adapted to receive said stored data elements from said plurality of storage elements and to transmit said data elements in said predetermined sequence; 
 b. storing a sequential data element from said stream in one of said storage elements according to a first order; 
 c. repeating step b until each of said plurality of said data elements has stored one data element; 
 d. selectively storing each of the subsequent data elements in said plurality of storage elements, following said first order of said storage elements as utilized in steps b and c; 
 e. transmitting a stored data element from one of said storage elements to said reordering element, whereby said storage element is selected based on a second order, and storing said stored data element in said reordering element; 
 f. repeating step e until each of said storage elements has transmitted one data element; 
 g. selectively transmitting each of the remaining stored data elements from said plurality of storage elements, following said second order as utilized in steps e and f until each of said stored data elements associated with said stream has been stored by said reordering element; and 
 h. retransmitting said stored data elements from said reordering element in said predetermined sequence. 
 
     
     
       11. The method of  claim 10 , further comprising: providing a logic element adapted to create and store control information associated with said data stream and to generate status information associated with each of said stored data elements based on said control information. 
     
     
       12. The method of  claim 11 , wherein said reordering element receives said status information, and generates and stores revised control information associated with each data element. 
     
     
       13. The method of  claim 11 , wherein said reordering element receives said data elements in said second sequence and uses said associated status information to reorder said data elements into said predetermined sequence. 
     
     
       14. A device, comprising:
 a plurality of storage elements; and   a reordering element;   wherein the device is configured to:
 receive, via a network, a data stream having data elements that have been transmitted in an original sequence; 
 store data elements in the received data stream to ones of the plurality of storage elements according to a first ordering that is based, at least in part, on respective portions of a recurring time interval in which the data elements are received; and 
 generate information associated with the data stream; 
   wherein the reordering element is configured to receive, according to a second ordering, the stored data elements along with the generated information associated with the data stream, and wherein the reordering element is configured to output the received data elements in the original sequence.   
     
     
       15. The device of claim 14, wherein the first and second orderings are the same. 
     
     
       16. The device of claim 14, wherein at least first and second ones of the data elements are respectively stored in first and second ones of the plurality of storage elements based on the first and second data elements being respectively received in first and second ones of the different time intervals. 
     
     
       17. The device of claim 14, wherein a speed at which the device is configured to receive the data stream is greater than a speed with which one or more storage elements in the plurality of storage elements are capable of storing data. 
     
     
       18. The device of claim 14, wherein the generated information associated with the data stream includes information identifying a data element that is first in the original sequence and information identifying a data element that is last in the original sequence. 
     
     
       19. The device of claim 14, wherein the generated information includes information indicating one of the plurality of storage elements to which a first-received one of the plurality of data elements is stored. 
     
     
       20. A method, comprising:
 a network device receiving a data stream via a network, wherein the data stream comprises a plurality of data elements that were transmitted in an original sequence;   the network device selectively storing at least first and second ones of the plurality of data elements, respectively, in at least first and second ones of a plurality of storage elements according to a first order that is based at least in part on respective portions of a recurring time interval in which the first and second data elements were received;   the network device generating information associated with the data stream, wherein the generated information includes information corresponding to at least the first and second ones of the plurality of the data elements;   the network device transmitting the plurality of data elements from the plurality of storage elements to a reordering element according to a second order; and   the reordering element outputting the plurality of data elements in the original sequence, wherein said outputting is based, at least in part, upon the generated information associated with the data stream.   
     
     
       21. The method of claim 20, wherein the generated information includes control information and status information. 
     
     
       22. The method of claim 21, wherein the control information includes a starting address of the data stream within the plurality of storage elements. 
     
     
       23. The method of claim 20, further comprising outputting at least one of the plurality of data elements in the original sequence while receiving one or more data elements from an additional data stream. 
     
     
       24. The method of claim 20, further comprising:
 prior to said outputting, the reordering element causing the plurality of data elements to be stored according to the second order.   
     
     
       25. The method of claim 20, wherein said selectively storing includes receiving and discarding data marked as invalid prior to storing at least a third one of the plurality of data elements in a third one of the plurality of storage elements according to the first order.