Method and apparatus for preserving packet squencing in a packet transmission system

• US 5,337,313 A
• Filed: 11/12/1992
• Issued: 08/09/1994
• Est. Priority Date: 11/12/1992
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Yednak, Mark A., Buchholz, Dale R., Doss, William K., Robbins, Karen E., Hamilton, R. Lee Jr.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Patel, Ajit
• Application Number:
  US07/975,360
• Time in Patent Office: 635 Days
• Field of Search: 370/60, 370/94.1, 370/94.2, 370/60.1, 370/85.13, 370/85.14, 370/92, 371/67.1, 371/60, 371/32, 371/57.1, 371/57.2, 340/825.06, 340/825.07, 340/825.52
• US Class Current: 370/394
• CPC Class Codes: H04L 2012/5616 Terminal equipment, e.g. codecs, synch.
• CPC Class Codes: H04L 2012/565 Sequence integrity
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method and apparatus for preserving the sequential relationship of a plurality of data packets 310 generated by separate source devices 14 and ordered as a data stream 300, despite transmission over radio channels which introduce ordering errors comprises method steps and apparatus structure for identifying at a first terminal, data packets from within the data stream as a function of source, generating data packet sequence information for identified data packets, storing values corresponding to data packet sequence numbers as a function of source and transmitting data packets, source device identity and packet sequence information to a second terminal having first terminal source device and data packet sequence information. Upon receipt of a first terminal transmission, the second terminal retrieves from second terminal memory, first terminal data packet sequence information and compares the stored data packet sequence information with received data packet sequence information. As a function of the comparison, received data packets are forwarded to an appropriate application for further processing when sequence information sequence numbers compare and stored in an order determined by the sequence information when the sequence numbers do not compare.

Claims

1. A method, for in a packet transmission system, for preserving the sequential relationship of a data stream of data packets generated by a plurality of source devices and communicated between a first terminal and a second terminal over channels which introduce ordering errors, comprising the steps of:

at said first terminal;

identifying data packets from within the data stream as a function of source device identification information;

generating data packet sequence information for the identified data packets;

storing in first terminal memory, values corresponding to data packet sequence information, indexed as a function of source device identification; and

transmitting first terminal transmissions comprising data packets, source device identification information and packet sequence information to said second terminal having first terminal source device and data packet sequence information;

at said second terminal;

receiving said first terminal transmissions;

fetching from second terminal memory, first terminal data packet sequence information when addressed by first terminal source device identification information;

comparing fetched data packet sequence information with received data packet sequence information;

forwarding a received data packet for further processing when the sequence information sequence numbers match; and

storing at least some of the received data packets in second terminal memory in an order determined by the sequence information when the sequence information sequence numbers do not match.

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

identifying, at said first terminal, said plurality of source devices;

transmitting to said second terminal, first terminal source device identification information on each one of said plurality of source devices, prior to transmission of data packets from said each one of said plurality of source devices, respectively;

feeding second terminal memory with first terminal source device identification information as a memory address signal;

mapping tables in second terminal memory for storage of first terminal source device and data packet sequence information as a function of the memory address signals; and

intializing the second terminal memory mapped tables, prior to the receipt of a first terminal transmission having source device identification information which addresses the initialized memory table.

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

determining when a received transmission is to be communicated to all source devices connected to a terminal; and

synchronizing the sequence number information for that received transmission with the sequence number information maintained by the packet transmission system when a transmission is to be communicated to all source devices has not previously been received.

4. The method of claim 1 wherein the step of generating packet sequence information further comprises the steps of;

tracking data packet sequencing; and

commencing a packet timer upon queuing the transmission packet for transmission.

5. The method of claim 4 wherein upon an indication of a packet timer time out a transmit window bit map status is updated to determine an oldest unacknowledged transmission packet.

6. The method of claim 1 wherein the step of forwarding a received data packet for further processing further comprises the steps of:

forwarding the data packet to an appropriate application for further handling;

updating a receive window bit map status to indicate receipt of said data packet; and

determining whether any previously received and out of order data packets are to be forwarded to the appropriate application.

7. The method of claim 1 wherein the step of storing at least some of the received data packets further comprises the steps of:

storing a received data packet when the sequence information sequence numbers match within a range from V(r+1 to V(r)+(2^n-2 -1), where V(r) is a value representing an anticipated sequence number for the received data packet and n is a number of bits used to encode that sequence number value V(r);

updating a bit map status to indicate receipt of said data packet; and

commencing a timer.

8. The method of claim 7 wherein upon indication of a timer time out, the stored data packets are forwarded to an appropriate application in an order as determined by sequence number.

9. The method of claim 1 further comprises the step of:

discarding the received data packet when the sequence information sequence numbers do not match by more than V(r)+(2^n-1), where V(r) is a value representing an anticipated sequence number for the received data packet and n is a number of bits used to encode that sequence number value V(r).

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

forwarding a received data packet for further processing when the sequence information sequences numbers match within a range from V(r)+(2^n-2) to V(r)+(2^n-1 -1) where V(r) is a value representing an anticipated sequence number for the received data packet and n is a number of bits used to encode that sequence number value V(r);

updating a bit map status to indicate receipt of said data packet; and

synchronizing the sequence number information within the second terminal memory map with the sequence number information within the received packet.

11. A communication system controller for use with a general purpose microprocessor, said controller comprising:

a computer program storage medium having a computer program stored thereon for execution by said microprocessor to preserve the sequential relationship of a data stream of data packets generated by a plurality of source devices and communicated between a first terminal and a second terminal, said program comprising;

at said first terminal;

means for identifying data packets from within the data stream as a function of source device identification information;

means for generating data packet sequence information for identified data packets;

a first random access memory, associated with the identifying means and the generating means;

means for feeding to said first memory, source device identification information, as an address signal;

means for storing in said first memory, values corresponding to data packet sequence information, indexed by source device identification information; and

a transmitter, coupled to the first random access memory, for transmitting first terminal transmissions comprising data packets, source device identification information and data packet sequence information to said second terminal;

at said second terminal;

a receiver for receiving said first terminal transmissions;

a second random access memory, coupled to the receiver, having first terminal source device and data packet sequence information;

means, coupled to the second memory, for fetching first terminal data packet sequence information from the second memory when said second memory is addressed by received source device identification information;

means for comparing the fetched data packet sequence information sequence number with received data packet sequence information sequence number;

means, responsive to the comparison, for forwarding a received data packet for further processing when sequence information sequence numbers match;

storing the received data packet when the sequence information sequence numbers match within a range from V(r)+1 to V(r)+(2^n-2 -1);

forwarding the received data packet for further processing when the sequence information sequence numbers match within a range from V(r)+(2^n-2) to V(r)+(2^n-1 -1); and

discarding the received data packet when the sequence information sequence numbers do not match by more than V(r)+(2^n-1) where V(r) is a value representing an anticipated sequence number for the received data packet and n is a number of bits used to encode that sequence number value V(r).

12. The communication system controller of claim 11 wherein said program further comprises:

means for identifying said plurality of first terminal source devices;

means for transmitting to said second terminal, first terminal source device identification information on each one of said plurality of source devices, prior to transmission of data packets from said each one of said plurality of source devices, respectively;

means for feeding second terminal memory with first terminal source device identification information as a memory address signal;

means for mapping tables in second terminal memory for storage of first terminal source device and packet sequence number information as a function of the memory address signals; and

means for initializing a second terminal memory mapped table, prior to the receipt of a first terminal transmission having source device identification information which addresses the initialized memory table.

13. The communication system controller of claim 11 wherein said program further comprises:

means for determining when a received transmission is to be communicated to all source devices connected to a terminal; and

means for synchronizing the sequence number information for that received transmission with the sequence number information maintained by the system when a transmission is to be communicated to all source devices has not previously been received.

14. The communication system controller of claim 11 wherein said program further comprises:

means for tracking data packet sequencing;

means for building a transmission packet reassembly header;

means for building a transmission packet; and

means for commencing a packet timer upon queuing the transmission packet for transmission.

15. The communication system controller of claim 14 wherein upon an indication of a packet timer time out a transmit window bit map status is updated to determine an oldest unacknowledged transmission packet.

16. The communication system controller of claim 11 wherein the means for forwarding a received data packet for further processing when sequence information sequence numbers compare further comprises:

means for forwarding the data packet to an appropriate application for further handling;

means for updating a receive window bit map status to indicate receipt of said data packet; and

means for determining whether any previously received and out of order data packets are to be forwarded to the appropriate application.

17. The communication system controller of claim 11 wherein the means for storing the received data packet when the sequence information sequence numbers match within a range from V(r)+1 to V(r)+(2^n-2 -1), further comprises:

means for storing the received data packet in memory in an order as determined by the data packet sequence information;

means for updating a receive window bit map status to indicate receipt of said data packet; and

means for commencing a sequence number timer.

18. The communication system controller of claim 17 wherein wherein upon identification of a sequence number time out the stored data packet is forwarded to an appropriate application.

19. The communication system controller of claim 11 wherein the means for forwarding a received data packet for further processing when the sequence information sequence numbers match within a range from V(r)+(2^n-2) to V(r)+(2^n-1 -1) further comprises:

means for forwarding the data packet to an appropriate application for further handling;

means for updating receive window bit map status to indicate receipt of said data packets; and

means for synchronizing the sequence number information within the second terminal memory map with the sequence number information within the received transmission.

20. The communication system controller of claim 11 wherein said data packet sequence information comprises:

source device identification information;

a transmit sequence number assigned to the next transmission packet associated with a source device;

a sequence number value assigned to an oldest unacknowledged transmission packet associated with a source device;

a transmit window bit-map to manage packets acknowledged out of order;

a receive sequence number, stored in memory, and representative of the sequence number for a packet next expected to be received; and

a receive window bit map to manage packets received out of order.

21. An RF communication system for preserving the sequential relationship of a data stream of data packets generated by a plurality of source devices and communicated between a first terminal and a second terminal, said communication system comprising:

said first terminal including;

a microprocessor for identifying said plurality of source devices, identifying data packets from within the data stream as a function of source and generating data packet sequence numbers for identified data packets;

random access memory, coupled to the microprocessor, for storing a table of values corresponding to data packet sequence numbers as a function of source device identification;

a transmitter, controlled by the microprocessor and coupled to the random access memory, for transmitting data packets, source device identity and packet sequence numbers to said second terminal having first terminal source device and data packet sequence number information;

said second terminal including;

a receiver for receiving first terminal transmissions;

random access memory, coupled to the receiver, for storing a table values corresponding to first terminal data packet sequence number information; and

a microprocessor, coupled to the receiver and random access memory, for fetching first terminal data packet sequence number information from random access memory when random access memory is addressed by source device identification,

comparing the fetched data packet sequence number with a received data packet sequence number, forwarding a received data packet to an application for further processing when sequence information sequence numbers match, storing the received data packet when the sequence information sequence numbers match within a range from V(r)+1 to V(r)+(2^n-2 -1), forwarding a received data packet to an application for further processing when the sequence information sequence numbers match within a range from V(r)+(2^n-2) to V(r)+(2^n-1 -1); and

discarding the received data packet when the sequence information sequence numbers do not match by more than V(r)+(2^n-1), where V(r) is a value representing an anticipated sequence number for the received data packet and n is a number of bits used to encode that sequence number value V(r).