System for the parallel assembly of data transmissions in a broadband network

• US 5,469,433 A
• Filed: 04/29/1994
• Issued: 11/21/1995
• Est. Priority Date: 04/29/1994
• Status: Expired due to Term

• Current Assignee: TTI Inventions A LLC (Intellectual Ventures LLC)
• Original Assignee: Bell Communications Research, Inc. (Telefonaktiebolaget LM Ericsson)
• Inventors: McAuley, Anthony J.
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): NGO, RICKY QUOC
• Application Number:
  US08/235,062
• Time in Patent Office: 571 Days
• Field of Search: 370/58.2, 370/58.3, 370/60, 370/61, 370/79, 370/82, 370/85.2, 370/91, 370/92, 370/93, 370/94.1, 370/94.2, 370/105, 370/99, 370/105.1, 370/43
• US Class Current: 370/474
• CPC Class Codes: H04L 1/1635 Cumulative acknowledgement, i.e. the acknowledgement message applying to all previous messages
• CPC Class Codes: H04L 2012/5615 Network termination, e.g. NT1, NT2, PBX
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 69/324 in the data link layer [OSI layer 2], e.g. HDLC
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

The present invention is generally directed to the transmission of data in various types of communication systems, including local area networks (LANs) and wide area networks (WANs). A main object of the present invention is to provide a system based on a parallel structure that can assemble and disassemble packet information in constant time, no matter how corrupted, out of order, or duplicated the arriving packets. A further object of the present invention is to provide a system that would improve efficiency in broadband networks, particularly if implemented in a VLSI chip using the low complexity architecture-and-reassembly of the present invention.

Claims

1. In a telecommunications network, a method for assembling/reassembling data blocks from a plurality of data packets transmitted through the network, each data packet having packet descriptor data describing identity, data sequence start, data sequence end, and packet type of a corresponding data packet, the method comprising the steps of:

receiving an nth data packet to be assembled where n is a number of received data packets;

extracting nth packet descriptor data from the nth data packet;

comparing the nth packet descriptor data with at least mth packet descriptor data to determine if they are duplicates of each other and discarding the nth packet descriptor data if determined to be a duplicate with the mth packet descriptor data, where m is a number of prior stored packet descriptor data in memory, wherein

at least the mth packet descriptor data is stored in a zth memory stage where z is a number of a memory stage among a plurality of memory stages;

comparing the nth packet descriptor data with at least the mth packet descriptor data to determine if a combination of at least the nth data packet with the mth data packet constitutes one of consecutive and overlapping data packets of a data block, and merging at least the nth and mth packet descriptor data if determined to constitute one of consecutive and overlapping data packets;

storing at least one of the nth packet descriptor data in a (z+1)th memory stage and the combination of at least the nth and mth packet descriptor data in a zth memory stage;

updating any packet descriptor data stored in the zth memory stage based on results of said step of comparing to determine consecutive and overlapping data packets;

determining whether any packet descriptor data stored in the memory stages include packet-type packet descriptor data designating a complete data block; and

reading out packet descriptor data with packet-type packet descriptor data designating a complete data block from the memory stages.

2. A method for assembling/reassembling data blocks from a plurality of data packets as claimed in claim 1, wherein each data packet has a packet-type packet descriptor selected from one of a START, a MIDDLE, an END and a COMPLETE packet type, and

when said step of comparing to determine one of consecutive and overlapping data packets determines that the combination does constitute one of consecutive and overlapping data packets, said step of updating the packet-type packet descriptor data in the packet descriptor data stored in the memory stages includes the steps of:

changing the packet-type to START when the packet-type of the nth packet descriptor data is MIDDLE and the packet-type of the mth packet descriptor data is START,

changing the packet-type to COMPLETE when the packet-type of the nth packet descriptor data is END and the packet-type of the mth packet descriptor data is START,

changing the packet-type to MIDDLE when the packet-type of the nth packet descriptor data is MIDDLE and the packet-type of the mth packet descriptor data is MIDDLE,

changing the packet-type to END when the packet-type of the nth packet descriptor data is END and the packet-type of the mth packet descriptor data is MIDDLE, and

maintaining a current packet-type for all other combinations of packet-types from the nth and mth packet descriptor data.

3. A method for assembling/reassembling data blocks from a plurality of data packets as claimed in claim 1, wherein the memory stages are connected in parallel to each other, the method further comprising the step of:

shifting storage of packet descriptor data in the parallel plurality of memory stages after said reading out of packet descriptor data with packet-type packet descriptor data designating a complete data block to cause only the lowermost stages of the parallel plurality of memory stages to be occupied.

7. A method for assembling/reassembling data blocks from a plurality of data packets as claimed in claim 1, the method further comprising the step of:

comparing the nth packet descriptor data with at least mth packet descriptor data to determine if the nth packet descriptor data is corrupted data and discarding the nth packet descriptor data if determined to be corrupted.

4. In a telecommunications network, a method for disassembling data blocks in a plurality of data packets transmitted through the network and assembling/reassembling the plurality of data packets into data blocks, each data packet having packet descriptor data, the method comprising the steps of:

dividing a data block to be disassembled into a plurality of data packets;

inserting a packet descriptor data set into each data packet, the packet descriptor data set including an identity descriptor, a data sequence start descriptor, a data sequence end descriptor, and a packet type descriptor;

transmitting the plurality of data packets through the network;

receiving a first data packet to be assembled;

extracting a first packet descriptor data set from a first data packet;

comparing the first packet descriptor data set with prior packet descriptor data sets stored in memory to determine if the first packet descriptor data set is a duplicate of any prior packet descriptor data set and discarding the first packet descriptor data if determined to be a duplicate of at least one prior packet descriptor data set stored in memory, wherein

each of the prior packet descriptor data sets is stored in one of a plurality of memory stages;

comparing the first packet descriptor data set with the prior packet descriptor data sets stored in memory to determine if a combination of the first data packet with at least one prior received data packet constitutes one of consecutive and overlapping data packets of a data block, and merging the first packet descriptor set and at least one prior packet descriptor data set stored in memory if determined to constitute one of consecutive and overlapping data packets;

storing at least one of the first packet descriptor data set in a next first empty memory stage, and the combination of the first and at least one prior packet descriptor data set in a memory stage currently occupied by the at least one prior packet descriptor data set;

updating the packet type descriptor in the packet descriptor data set stored based on results of said step of comparing to determine one of consecutive and overlapping data packets;

determining whether any packet descriptor data sets stored in the memory stages include a packet-type descriptor designating a complete data block; and

reading out packet descriptor data sets with packet-type descriptors designating a complete data block from the memory stages.

5. A method for disassembling data blocks into a plurality of data packets and then assembling/reassembling the plurality of data packets as claimed in claim 4, wherein

said step of inserting a packet descriptor data set into each data packet includes setting the packet-type descriptor of each packet descriptor data set as one of a START, a MIDDLE, an END and a COMPLETE packet type, and

when said step of comparing to determine one of consecutive and overlapping data packets determines that the combination does constitute one of consecutive and overlapping data packets, said step of updating the packet-type descriptors in the prior packet descriptor data sets stored in the memory stages includes the steps of:

changing the packet-type descriptor to START when the packet-type descriptor of the first packet descriptor data is MIDDLE and the packet-type descriptor of the prior received packet descriptor data is START,

changing the packet-type descriptor to COMPLETE when the packet-type descriptor of the first packet descriptor data is END and the packet-type descriptor of the prior received packet descriptor data is START,

changing the packet-type descriptor to MIDDLE when the packet-type descriptor of the first packet descriptor data is MIDDLE and the packet-type descriptor of the prior received packet descriptor data is MIDDLE,

changing the packet-type descriptor to END when the packet-type descriptor of the first packet descriptor data is END and the packet-type descriptor of the prior received packet descriptor data is MIDDLE, and

maintaining a current packet-type descriptor for all other combinations of packet-type descriptors from the first and prior received packet descriptor data.

6. A method for disassembling data blocks into a plurality of data packets and then assembling/reassembling the plurality of data packets into data blocks as claimed in claim 4, wherein the memory stages are connected in parallel to each other, the method further comprising the step of:

shifting storage of packet descriptor data sets in the parallel plurality of memory stages after said reading out of packet descriptor data sets with packet-type descriptors designating a complete data block to cause only the lowermost stages of the parallel plurality of memory stages to be occupied.

8. A method for disassembling and then assembling/reassembling data blocks from a plurality of data packets as claimed in claim 4, the method further comprising the step of:

comparing the first packet descriptor data set with the prior received packet descriptor data sets to determine if the first data packet is corrupted data and discarding the first data packet set if determined to be corrupted.

9. A device for assembling/reassembling data blocks from a plurality of data packets transmitted through a telecommunications network, each data packet having a packet descriptor data set describing identity, data sequence start, data sequence end, and packet type of a corresponding data packet, the device comprising:

means for receiving data packets to be assembled from the telecommunications network;

memory means connected to said means for receiving for storing at least m packet descriptor data sets from m data packets, said memory means including a plurality of memory stages connected in parallel with each memory stage being formed to store a single packet descriptor data set, where m is a number of received data packets; and

a control circuit connected to said memory means and said receiving means, said control circuit controlling the receiving, storing, and outputting of data packets received from the network, wherein said control circuit includes

means for extracting an nth packet descriptor data set from an nth data packet received from the network,

means for comparing the nth packet descriptor data set with at least the mth packet descriptor data set stored in said memory means to determine at least one of if the nth packet descriptor data set and the mth packet descriptor data set are duplicates of each other, if the nth packet descriptor data is corrupted data, and if a combination of at least the nth data packet with the mth data packet constitutes one of consecutive and overlapping data packets of a data block,

processing means for performing at least one of the following operation;

discarding the nth packet descriptor data set if the nth packet descriptor data set is a duplicate of the mth packet descriptor data set, discarding the nth packet descriptor data set if the nth packet descriptor data set is corrupted data, and merging at least the nth and mth packet descriptor data sets if the combination of at least the nth data packet with the mth data packet constitutes one of consecutive and overlapping data packets of a data block,

means for storing at least one of the nth packet descriptor data set and the combination of the nth and mth packet descriptor data sets in said memory means,

means for updating the packet-type packet descriptor in packet descriptor data sets stored in said memory means based on results of the comparing means,

means for determining whether any packet descriptor data sets stored in said memory means include a packet-type descriptor designating a complete data block, and for reading out packet descriptor data sets with packet-type descriptors designating a complete data block from said memory means, and

means for shifting storage of packet descriptor data sets in said memory means after packet descriptor data sets with packet-type packet descriptor data designating a complete data block are read out to cause only lowermost stages of said memory means to be occupied.

10. A device for assembling/reassembling data blocks from a plurality of data packets transmitted through a telecommunications network according to claim 9, wherein each of said stages in said memory means includes a plurality of stage cells each connected to receive a predetermined packet descriptor from a packet descriptor data set inputted thereto, and a stage controller controlling receiving, outputting, and storing of packet descriptor data sets through the stage cells.

11. A system for disassembling data blocks into a plurality of data packets transmitted through a telecommunications network and assembling/reassembling the plurality of data packets into data blocks, the system comprising:

means for dividing a data block to be disassembled into a plurality of data packets, and for inserting a packet descriptor data set into each data packet, the packet descriptor data set including an identity descriptor, a data sequence start descriptor, a data sequence end descriptor, and a packet-type descriptor;

a first network interface connected to said means for dividing for transmitting the plurality of data packets to the network;

a second network interface for receiving the plurality of data packets from the networks;

memory means for storing prior packet descriptor data sets, said memory means including a plurality of memory stages connected in parallel with each other with each memory stage being formed to store a single packet descriptor data set; and

a control circuit connected to said memory means and said second network interface, said control circuit controlling the receiving, storing, and outputting of data packets received from the network, wherein said control circuit includes

means for extracting a first packet descriptor data set from a first data packet received from the network,

means for comparing the first packet descriptor data set with at least one prior packet descriptor data set stored in said memory means to determine at least one of if the first packet descriptor set and the at least one prior packet descriptor data set are duplicates of each other, if the first packet descriptor data is corrupted data, and if a combination of at least the first data packet with the at least one prior received data packet constitutes one of consecutive and overlapping data packets of a data block,

processing means for performing at least one of the following operations;

discarding the first packet descriptor data set if the first packet descriptor data set is a duplicate of the at least one prior packet descriptor data set, discarding the first packet descriptor data set if the first packet descriptor data set is corrupted data, and combining at least the first and the at least one prior packet descriptor data set if the combination constitutes one of consecutive and overlapping data packets of a data block,

means for storing at least one of the first packet descriptor data set, and the combination of the first and prior packet descriptor data sets in said memory means,

means for updating the packet-type packet descriptor in packet descriptor data sets stored in said memory means based on results of the comparing means,

means for determining whether any packet descriptor data sets stored in said memory means include a packet-type descriptor designating a complete data block, and for reading out packet descriptor data sets with packet-type descriptors designating a complete data block from said memory means, and

means for shifting storage of packet descriptor data sets in said memory means after packet descriptor data sets with packet-type descriptors designating a complete data block are read out to cause only the lowermost stages of said memory means to be occupied.

12. A system for disassembling data blocks into a plurality of data packets transmitted through a telecommunications network and assembling/reassembling the plurality of data packets into data blocks according to claim 11, wherein each of said stages in said memory means includes a plurality of stage cells each connected to receive a predetermined packet descriptor from a packet descriptor data set inputted thereto, and a stage controller controlling receiving, outputting, and storing of packet descriptor data sets through the stage cells.

13. A system for disassembling data blocks into a plurality of data packets transmitted through a telecommunications network and assembling/reassembling the plurality of data packets into data blocks according to claim 11, further comprising:

a disassembly adaptor circuit connected to an input of said memory means so as to interface said memory means with said means for dividing a data block to be disassembled.

14. A method for sending data through a telecommunications network between a transmitting station and a receiving station, the method comprising the steps of:

dividing a data block into a plurality of data packets at the transmitting station;

inserting a packet descriptor data set into each data packet;

transmitting the plurality of data packets through the network;

extracting the packet descriptor data set from the data packet when received at the receiving station;

comparing the packet descriptor data set with prior packet descriptor data sets stored in memory to determine if there is duplicative or overlapping data;

updating the packet descriptor data set relative to the prior packet descriptor data sets based on a result of said step of comparing with the prior packet descriptor data sets;

storing the packet descriptor data set in one of a plurality of memory stages based on the result of said step of comparing with prior packet descriptor data sets;

determining whether any packet descriptor data sets stored in the plurality of memory stages designate a complete data block; and

reading out from the memory stages packet descriptor data sets designating a complete data block.

15. A method for sending data through a telecommunications network according to claim 14, said method further comprising the step of:

determining if the received data packet is corrupted data and discarding the received data packet set if determined to be corrupted.

16. A method for sending data as claimed in claim 14, wherein said steps of comparing the packet descriptor data set with prior packet descriptor data sets and updating the packet descriptor data set further include the steps of

determining if the packet descriptor data set is a duplicate of any of the prior packet descriptor data sets stored in memory and discarding the packet descriptor data set if determined to be a duplicate of at least one prior packet descriptor data set, and

determining if a combination of the packet descriptor data set with at least one prior packet descriptor data set constitutes one of consecutive and overlapping data packets of a data block, and combining the packet descriptor set and at least one prior packet descriptor data set if determined to constitute one of consecutive and overlapping data packets.

17. A system for transmitting data through a telecommunications network, the system comprising:

means for dividing a data block into a plurality of data packets, and for inserting a packet descriptor data set into each data packet;

a first network interface connected to said means for dividing for transmitting the plurality of data packets to the network;

a second network interface for receiving a plurality of data packets from the network;

memory means for storing prior packet descriptor data sets, said memory means including a plurality of memory stages connected in parallel with each memory stage being formed to store a single packet descriptor data set; and

a control circuit connected to said memory means and said second network interface, said control circuit including means for comparing a packet descriptor data set of a received data packet with at least one prior packet descriptor data set stored in said memory means, processing means for updating the packet descriptor data set based on an output from the comparing means, and means for determining whether any packet descriptor data sets stored in said memory means designate a complete data block and for reading out from said memory means packet descriptor data sets designating a complete data block.

18. A system for transmitting data as claimed in claim 17, wherein the comparing means of said control circuit includes means for determining at least one of if the data packet is a duplicate of a prior received data packet, if the data packet is corrupted data, and if a combination of at least the data packet with the at least one prior received data packet constitutes consecutive data packets of a data block.

19. A system for transmitting data as claimed in claim 18, wherein the processing means of said control circuit includes means for performing at least one of the following operations:

discarding the packet descriptor data set if the packet descriptor data set is a duplicate of the at least one prior packet descriptor data set, discarding the packet descriptor data set if the packet descriptor data set is corrupted data; and

merging at least the packet descriptor data set and the at least one prior packet descriptor data set if the combination constitutes one of consecutive and overlapping data packets of a data block.

20. A system for transmitting data as claimed in claim 17, wherein said control circuit further includes means for shifting storage of packet descriptor data sets in said memory means after packet descriptor data sets with packet-type descriptors designating a complete data block are read out.

21. A system for transmitting data as claimed in claim 17, wherein each of said stages in said memory means includes a plurality of stage cells and a stage controller controlling receiving, outputting and storing of packet descriptor data sets through the stage cells.

22. A system for transmitting data as claimed in claim 17, further comprising:

a disassembly adaptor circuit connected to an input of said memory means so as to interface said memory means with said means for dividing a data block.