Method and apparatus for sequence number checking

• US 6,978,384 B1
• Filed: 09/19/2001
• Issued: 12/20/2005
• Est. Priority Date: 09/19/2000
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: BBNT Solutions LLC (Rtx Corporation), Verizon Corporate Services Group Incorporated (Verizon Communications Inc.)
• Inventors: Milliken, Walter Clark
• Primary Examiner(s): Barron, Gilberto
• Assistant Examiner(s): SANDOVAL, KRISTIN D
• Application Number:
  US09/955,830
• Time in Patent Office: 1,553 Days
• Field of Search: 713/160, 713/162, 713/177, 713/151, 713/201, 380/262, 708/212, 709/227, 709/228
• US Class Current: 726/26
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 63/164 at the network layer
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

Methods and systems are provided for sequence number checking. Sequence numbers of data packets are compared to a “sliding” window. The sliding window indicates a range of sequence numbers considered valid (or invalid). The size of the sliding window may be a particular value or varied. If a sequence number is “below” the sliding window, then it may be considered invalid. If a sequence number is within the sliding window, then it may be further checked to determine if a duplicate sequence number has been received. If a sequence number is “above” the sliding window, then it may be considered valid and the sliding window is advanced. The sliding window and sequence numbers are processed using multiple level bitmaps, which indicate a historical state of sequence numbers received. Furthermore, the multiple level bitmaps may comprise summary bits to summarize a state of subsequent bits.

Claims

1. A sequence number checker, comprising:

a bit map memory storing a first multiple level bit map representing a first sequence number of a first packet received by said sequence number checker; and

a processor to compute a second multiple level bit map representing a second sequence number of a second packet received by said sequence number checker subsequent to said first packet, said second multiple level bit map being compared to said first multiple level bit map to produce a result indicating actions to be performed on said second packet.

2. The sequence number checker according to claim 1, further comprising:

a window controller to maintain a sliding window representing a range of sequence numbers; and

a window memory storing a bottom value and a top value for said sliding window.

3. The sequence number checker according to claim 2, wherein said range of sequence numbers is a fixed size.

4. The sequence number checker according to claim 2, wherein said range of sequence numbers has a variable sized based upon characteristics of a security association.

5. The sequence number checker according to claim 1, wherein said bit map memory further comprises:

a partition assigned to said security association.

6. A method comprising:

determining characteristics of a security association, the characteristics including a window size, the determining including defining a multiple level bitmap representing sequence numbers of packets;

setting a bottom value and a top value to define a window based on said window size, said setting including setting at least one bit of the multiple level bitmap;

receiving a sequence number for a packet;

comparing said sequence number to said window, said comparison using the multiple level bitmap;

setting a new top value equal to said sequence number if said sequence number is greater than the said top value; and

setting a new bottom value based on said new top value and said window size.

7. A method for maintaining a window of valid sequence numbers, comprising:

setting a bottom value and a top value to define a window;

receiving a sequence number for a packet;

comparing said sequence number to said window;

setting at least one summary bit in a multiple level bitmap, to set a new top value, if said sequence number is greater than said top value, wherein said at least one summary bit indicates a validity of a contiguous range of bits within said multiple level bitmap; and

setting a new bottom value based on said new top value.

8. A method for checking sequence numbers, comprising:

receiving a sequence number for a packet;

converting said sequence number to a first multiple level bit map;

retrieving a second multiple level bit map stored in a bit map memory;

dividing said first multiple level bit map into a first plurality of summary bits;

dividing said second multiple level bit map into a second plurality of summary bits; and

comparing said first and second plurality of summary bits to produce a result indicating validity of said sequence number.

9. The method according to claim 8, wherein said comparing step further comprises:

setting a value for at least one of said second plurality of summary bits based on said result; and

setting a range of contiguous bits in said second multiple level bit map based on said result.

10. The method according to claim 9, wherein setting said range of contiguous bits in said second multiple level bit map comprises setting said range of contiguous bits to a value of 0 when at least one of said second plurality of summary bits changes from a value of 0 to a value of 1.

11. The method according to claim 9, further comprising:

passing said packet upon producing a result indicating said sequence number is valid.

12. The method according to claim 9, further comprising:

discarding said packet upon producing a result indicating said sequence number is invalid.

13. An apparatus for maintaining a window of valid sequence numbers, comprising:

means for setting a bottom value and a top value to define a window;

means for receiving a sequence number for a packet;

means for comparing said sequence number to said window;

means for setting at least one summary bit in a multiple level bitmap, to set a new top value, if said sequence number is greater than said top value, wherein said at least one summary bit indicates a validity of a contiguous range of bits within said multiple level bitmap; and

means for setting a new bottom value based on said new top value.

14. An apparatus for checking sequence numbers, comprising:

means for receiving a sequence number for a packet;

means for converting said sequence number to a first multiple level bit map;

means for retrieving a second multiple level bit map stored in a bit map memory;

means for dividing said first multiple level bit map into a first plurality of summary bits;

means for dividing said second multiple level bit map into a second plurality of summary bits; and

means for comparing said first and second plurality of summary bits to produce a result indicating validity of said sequence number.