US5151899A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Tracking sequence numbers in packet data communication system
Assignee: Enterasys Networks Inc
•
Filing: 1991-02-11
•
Granted: 1992-09-29
•
Expires: 2011-02-11
Abstract
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.
Inventors
- 👤 Robert E. Thomas
- 👤 George Varghese
- 👤 Robert J. Souza
- 👤 George A. Harvey
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 20:45
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/12; H04L1/16; H04L1/18; H04L1/1829; H04L1/1835; H04L9/00; H04L9/40
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
206 words
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.
Claim 2
Independent Claim
206 words
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.
Claim 3
Dependent Claim
40 words
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.
Claim 4
Dependent Claim
57 words
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.
Claim 5
Dependent Claim
32 words
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.
Claim 6
Dependent Claim
23 words
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.
Claim 7
Dependent Claim
44 words
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.
Claim 8
Dependent Claim
72 words
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.
Claim 9
Independent Claim
141 words
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.
Claim 10
Independent Claim
141 words
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.
Claim 11
Dependent Claim
41 words
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.
Claim 12
Dependent Claim
51 words
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.
Claim 13
Dependent Claim
30 words
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.
Claim 14
Dependent Claim
32 words
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.
Claim 15
Dependent Claim
23 words
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.
Claim 16
Dependent Claim
44 words
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.
Claim 17
Dependent Claim
68 words
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.
Claim 18
Dependent Claim
140 words
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.
Claim 19
Dependent Claim
140 words
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.
Claim 20
Dependent Claim
39 words
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.
Claim 21
Dependent Claim
49 words
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.
Claim 22
Dependent Claim
28 words
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.
Claim 23
Dependent Claim
45 words
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.
Claim 24
Dependent Claim
31 words
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.
Claim 25
Dependent Claim
22 words
Apparatus according to claim 21 wherein said end-to-message bit map is a data array having M rows of N bits per row.
Claim 26
Dependent Claim
43 words
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.
Claim 27
Dependent Claim
62 words
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.
Claim 28
Dependent Claim
173 words
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.
Claim 29
Dependent Claim
173 words
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.
Claim 30
Dependent Claim
39 words
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.
Claim 31
Dependent Claim
42 words
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.
Claim 32
Dependent Claim
28 words
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.
Claim 33
Dependent Claim
46 words
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.
Claim 34
Dependent Claim
22 words
Apparatus according to claim 26 wherein said first bit map is a data array having M rows of N bits per row.
Claim 35
Dependent Claim
22 words
Apparatus according to claim 30 wherein said end-of-message bit map is a data array having M rows of N bits per row.
Claim 36
Dependent Claim
43 words
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.
Claim 37
Dependent Claim
15 words
Apparatus according to claim 32 wherein said sequence number is at least a 32-bit number.
Claim 38
Dependent Claim
61 words
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.
References Cited (Backward Citations)
US4439859A
Cited
US4646235A
Cited
US4564937A
Cited
US4611280A
Cited
US4679139A
Cited
US4617657A
Cited
US4631673A
Cited
US4680705A
Cited
US4799215A
Cited
US4803651A
Cited
US4918687A
Cited
US4964119A
Cited
US5007052A
Cited
US5056085A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-09-29 | 1996-03-30 | 1996-09-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-09-29 | 2000-03-30 | 2000-09-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-09-29 | 2004-03-30 | 2004-09-29 | $7700.00 | Window Closed / Lapsed |