Tracking sequence numbers in packet data communication system

• US 5,151,899 A
• Filed: 02/11/1991
• Issued: 09/29/1992
• Est. Priority Date: 02/11/1991
• Status: Expired due to Term

• Current Assignee: Enterasys Networks Incorporated (Extreme Networks, Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Souza, Robert J., Harvey, George A., Varghese, George, Thomas, Robert E.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): SAMUEL, TEMESGHEN
• Application Number:
  US07/654,067
• Time in Patent Office: 596 Days
• Field of Search: 370/94.1, 370/60, 370/100.1, 370/77, 370/55, 370/61, 370/94.2, 370/105.3, 364/200, 364/900
• US Class Current: 370/394
• CPC Class Codes: H04L 1/1835 Buffer management
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A packet data communication network employs sequence numbers in message packets to identify the packets transmitted for a message, so that the order of packets can be checked, and so that the occurrence of lost or duplicated packets can be detected. A method of keeping track of these sequence numbers is provided. Any number below or above a bounded sequence number acceptance window is ignored (not accepted). Bit maps are established for the range of numbers within the bounded window, each bit representing a sequence number and the bit maps indexed by sequence number. One bit map is a received packet map, used to keep track of which sequence numbers have been received and thus to filter duplicate sequence numbers. An end-of-message bit map is used to record the positions of packets having end-of-message flags, and this is used with the received packet map to determine whether all packets of a message have been received, so that an end-of-message trigger can be generated. The sequence number and an end-of-message flag from an incoming packet are used to update these bit maps as each packet is received, then the updated bit maps used to determine the needed action. Two methods are described for tracking these sequence numbers. Both methods have good average-case performance. The first method uses an iterative loop and is more suited for software implementation. The second method uses table lookup to replace the iterative loop and is more suited for hardware implementation. This method has very good worst-case performance.

Claims

1. A method of tracking sequence numbers for message packets in a packet data transmission system, comprising the steps of:

a) assigning sequence numbers in order to a series of packets transmitted from a source to a destination;

b) at said destination, defining an acceptable range of said sequence numbers, said range beginning at a base sequence number and extending for a window which is a small fraction of the available sequence numbers;

c) comparing the sequence number of each message packet received at said station with said acceptable range;

d) discarding all message packets having sequence numbers not within said range;

e) maintaining at said destination a first bit map, and indexing into said first bit map to a sequence number index position representing the sequence number of a packet received at said destination; and

f) for said packet received at said destination, checking its sequence number index position in said first bit map, and discarding said packet if said sequence number index position contains an indication that a packet of the sequence number of this index position has already been received, or, if said index position does not contain said indication, then storing an indication at said index position that a packet has been received.

2. A method according to claim 1 including the step of checking to determine if an incoming packet is an end-of-massage packet, and, if so, changing the condition of a corresponding bit in an end-of-message bit map indexed by sequence number.

3. A method according to claim 2 including the steps of checking to determine if all sequence numbers prior to said corresponding bit in said end-of-message bit map contain said indication in said first bit map, and, if so, providing an end-of-message indication and zeroing all bits in said end-of-message bit map up to the current sequence number.

4. A method according to claim 1 wherein said first bit map is a data array having M rows of N bits per row, and is of the same size as said window.

5. A method according to claim 4 wherein said end-of-message bit map is a data array having M rows of N bits per row.

6. A method according to claim 5 wherein N is a power of 2 and equal to the data path width of processing means in said station, and wherein M is a power of 2, and said window is of a size M times N.

7. A method according to claim 1 including the steps of maintaining a first multi-bit value having a bit which is in a selected condition for each row of said first bit map with all bits containing said indication, generating a table of said first multi-bit values for all combinations of bits in said selected condition, and looking up in said table a new first nulti-bit value when a sequence number is received.

8. A method of tracking sequence numbers in a packet data receiver for use in a transmission system employing sequence numbers for message packets, comprising the steps of:

a) receiving message packets having sequence numbers;

b) comparing each received sequence number with an acceptable range of said sequence numbers in a window extending from a beginning sequence number for a small fraction of the available sequence numbers;

c) discarding a received message packet having a sequence number not within said window;

d) maintaining a first bit map indexed by sequence number in which a bit is placed in a selected condition for each packet received; and

e) checking the first bit map upon receiving each packet and discarding any packet having a sequence number indexing into said first bit map to a bit already in said selected condition in said bit map.

9. A method according to claim 8 including the steps of checking to determine if an incoming packet is an end-of-massage packet, and, if so, placing in a given condition a corresponding bit in an end-of-message bit map indexed by sequence number.

10. A method according to claim 9 including the steps of checking to determine if bits are in said selected condition in said first bit map for sequence numbers of a message prior to said bit in said given condition in said end-of-message bit map, and, if so, providing an end-of-message indication.

11. A method according to claim 9 including the step of zeroing all bits in said end-of-message bit map up to the current sequence number if said end-of-message indication is provided.

12. A method according to claim 8 wherein said first bit map is a data array having M rows of N bits per row, and is of the same size as said window.

13. A method according to claim 12 wherein said end-of-message bit map is a data array having M rows of N bits per row.

14. A method according to claim 13 wherein N is a power of 2 and equal to the data path width of processing means in said station, and wherein M is a power of 2, and said window is of a size M times N.

15. A method according to claim 8 including the steps of maintaining a first multi-bit value having a bit which is a logic "1" for each row of said first bit map with all bits in said selected condition, generating a table of said first multi-bit values for all combinations of bits, and looking up in said table a new first multi-bit value when a sequence number is received.

16. A packet data receiver apparatus for use in a transmission system employing sequence numbers for message packets, comprising:

a) means for receiving message packets having sequence numbers;

b) means for comparing each sequence number with a window defining an acceptable range of said sequence numbers, said window beginning at a base sequence number and extending for a small fraction of the available sequence numbers, and for discarding a received message packet having a sequence number not within said range;

c) means for maintaining a first bit map indexed by sequence number in which a bit is placed in a given condition for each packet received; and

d) means for checking the first bit map upon receiving each packet and discarding any packet having a sequence number indexing into said first bit map to a bit already in said given condition.

17. Apparatus according to claim 16 including means for checking to determine if an incoming packet is an end-of-massage packet, and, if so, placing in a selected condition a corresponding bit in an end-of-message bit map indexed by sequence number.

18. Apparatus according to claim 17 including means for checking to determine if bits are in said given condition in said first bit map for sequence numbers of a message prior to said bit in said selected condition in said end-of-message bit map, and, if so, providing an end-of-message indication.

19. Apparatus according to claim 18 including means for zeroing all bits in said end-of-message bit map up to the current sequence number if said end-of-message indication is provided.

20. Apparatus according to claim 19 including means for maintaining an index of the current row in said first bit map and said end-of-message bit map, and incrementing said index of the current row if all bits in the current row are in said given condition.

21. Apparatus according to claim 16 wherein said first bit map is a data array having M rows of N bits per row, and is of the same size as said window.

22. Apparatus according to claim 21 wherein said end-to-message bit map is a data array having M rows of N bits per row.

23. Apparatus according to claim 22 wherein N is a power of 2 and equal to the data path width of processing means in said apparatus, and wherein M is a power of 2, and said window is of a size M times N.

24. Apparatus according to claim 16 including means for maintaining a first multi-bit value having an indicator bit for each row of said first bit map with all bits in said given condition, generating a table of said first multi-bit values for all combinations of bits, and looking up in said table a new first multi-bit value when a sequence number is received.

25. A packet data transmission system employing packet sequence numbers assigned in order, comprising, at a receiving station:

a) means for defining an acceptable range of said sequence numbers, said acceptable range beginning at a base sequence number and extending for a window which is a small fraction of the available sequence numbers;

b) means for comparing the sequence number of each message packet received with said acceptable range, and for discarding all message packets having sequence numbers not within said range;

c) means for maintaining a first bit map, each bit of said bit map being in a set or not-set condition, and for indexing into said first bit map to a bit position representing the sequence number of a received packet;

d) means for checking said bit position in said first bit map for said received packet, and discarding said received packet if the bit at said bit position is already in said set condition, or changing the bit at said bit position to a set condition if in said not-set condition.

26. Apparatus according to claim 25 including means for checking to determine if an incoming packet is an end-of-massage packet, and, if so, changing to a set condition a corresponding bit in an end-of-message bit map indexed by sequence number.

27. Apparatus according to claim 26 including means for checking to determine if all sequence numbers prior to said corresponding bit in said end-of-message bit map are in said set condition in said first bit map, and, if so, providing an end-of-message indication.

28. Apparatus according to claim 27 including means for zeroing all bits in said end-of-message bit map up to the current sequence number if said end-of-message indication is provided.

29. Apparatus according to claim 26 including means for maintaining an index of the current row in said first bit map and said end-of-message bit map, and incrementing said index of the current row if all bits in the current row are set in said set condition.

30. Apparatus according to claim 26 wherein said first bit map is a data array having M rows of N bits per row.

31. Apparatus according to claim 30 wherein said end-of-message bit map is a data array having M rows of N bits per row.

32. Apparatus according to claim 31 wherein N is a power of 2 and equal to the data path width of processing means in said apparatus, and wherein M is a power of 2, and said window is of a size M times N.

33. Apparatus according to claim 32 wherein said sequence number is at least a 32-bit number.

34. Apparatus according to claim 25 including means for maintaining a first multi-bit value having a bit indicating each row of said first bit map with all bits in said set condition, generating a table of said first multi-bit values for all combinations of bits, and looking up in said table a new first multi-bit value when a sequence number is received.