Use of a circular buffer to assure in-order delivery of packets

• US 20030026277A1
• Filed: 07/03/2002
• Published: 02/06/2003
• Est. Priority Date: 07/09/2001
• Status: Active Grant

• Current Assignee: Adtran Networks SE (ADTRAN Holdings, Inc.)
• Original Assignee: Overture Networks, Inc. (ADTRAN Holdings, Inc.)
• Inventors: Poupard, Michael Joseph, Pate, Prayson Will
• Granted Patent: US 6,741,603 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 47/32 by discarding or delaying data units, e.g. packets or frames
• CPC Class Codes: H04L 47/34 ensuring sequence integrity, e.g. using sequence numbers
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

A circular buffer is used to receive packets transmitted to an application. Normally, incoming packets are placed at the “tail” of the buffer, which is indicated by the write pointer. Packets to be used by the application are read from the “head” of the buffer, which is indicated by the read pointer. In contrast, the present invention uses the sequence number to direct the packets to specific places in the circular buffer. This inventive use of sequence number allows the packets to be written at the proper place in the buffer, regardless of the location of the write pointer. Within certain limits, a packet that arrives out of sequence is not bound by the position of the write pointer to be placed into the buffer out of sequence. This abstract is provided as a tool for those searching for patents, and not as a limitation on the scope of the claims.

Claims

1. A method of placing an incoming packet into a circular buffer based on a sequence number for the incoming packet, the method comprising:

Calculating a write pointer offset based on the sequence number of the incoming packet and a sequence number of the packet currently associated with a buffer tail pointer for the circular buffer.

2. The method of claim 1 further comprising:

Adjusting the write pointer offset to compensate for the use of sequence numbers on either side of a sequence number transition from a max sequence number back to a minimum sequence number.

3. The method of claim 1 further comprising:

Discarding a too-early incoming packet with a sequence number of at least a sum of a sequence number associated with the packet to be read in the next read operation for the circular buffer plus a total number of addresses for the circular buffer (after adjusting for wrapping of sequence numbers).

4. The method of claim 1 further comprising:

Storing a mildly-early incoming packet with a sequence number less than a sum of a sequence number of the next packet to be read in the next read operation plus a total number of addresses for the circular buffer (after adjusting for wrapping of sequence numbers),

Then storing a timely incoming packet with a sequence number less than the sequence number of the mildly-early incoming packet (after adjusting for wrapping of sequence numbers).

5. The method of claim 1 further comprising:

Maintaining a measure of the fullness of the buffer (“

buffer used”

) by measuring the range defined by the current positions of a buffer head pointer and the buffer tail pointer where the buffer tail pointer points to the buffer position associated with the packet with the largest sequence number (after adjusting for sequence number wrapping) and the buffer tail pointer is independent of the location of the most recent buffer position to receive an incoming packet.

6. The method of claim 1 further wherein the placing of the incoming packet into the circular buffer is done independently and asynchronously from processing of outgoing packets by maintaining a read/head pointer in addition to the buffer tail pointer, wherein:

the buffer tail pointer is used in connection with the write pointer offset to write incoming packets to the appropriate buffer position in response to the arrival of the incoming packet and independent of the actions of the read/head pointer, and

the read/head pointer is updated upon the readout of a previously stored packet and independent of the arrival of incoming packets.

7. A method of storing an incoming packet and placing a control block into a circular buffer based on a sequence number for the incoming packet, the method comprising:

Calculating a write pointer offset based on the sequence number of the incoming packet and a sequence number of a packet currently associated with a buffer tail pointer for the circular buffer,

Writing the control block containing both the sequence number for the incoming packet and a pointer to a memory storage location, the control block written into the circular buffer based on the write pointer offset; and

Storing the incoming packet in the memory storage location corresponding to the pointer in the control block.

8. The method of claim 7 further comprising:

Adjusting the write pointer offset to compensate for the use of sequence numbers on either side of a sequence number transition from a max sequence number back to a minimum sequence number.

9. The method of claim 7 further comprising:

Discarding a too-early incoming packet with a sequence number of at least a sum of a sequence number associated with a packet to be read in the next read operation plus a total number of addresses for the circular buffer (after adjusting for wrapping of sequence numbers).

10. The method of claim 7 further comprising:

Storing a mildly-early incoming packet with a sequence number less than a sum of a sequence number of the next packet to be read in the next read operation plus a total number of addresses for the circular buffer (after adjusting for wrapping of sequence numbers),

Then storing a timely incoming packet with a sequence number less than the sequence number of the mildly-early incoming packet (after adjusting for wrapping of sequence numbers).

11. The method of claim 7 further comprising:

Maintaining a measure of the fullness of the buffer (“

buffer used”

) by measuring the range defined by the current positions of a buffer head pointer and the buffer tail pointer where the buffer tail pointer points to a buffer position associated with a packet with the largest sequence number (after adjusting for sequence number wrapping) and the buffer tail pointer is independent of the location of the most recent buffer position to receive an incoming packet.

12. The method of claim 7 further wherein the placing of the control block for the incoming packet into the circular buffer is done independently and asynchronously from processing of outgoing packets by maintaining a read/head pointer in addition to the buffer tail pointer, wherein:

the buffer tail pointer is used in connection with the write pointer offset to write incoming control blocks for incoming packets to the appropriate buffer position in response to the arrival of the incoming packet and independent of the actions of the read/head pointer; and

the read/head pointer is updated upon the readout of a previously stored packet and independent of the arrival of incoming packets.

13. A method of determining the next circular buffer address in a circular buffer to receive a current incoming packet based on the sequence number of the current incoming packet, the method comprising:

A) Storing the following state variables;

Count of Sequence Numbers;

Tail Pointer wherein the Tail Pointer is a pointer to a highest circular buffer address where a packet has been written (taking wrapping of circular buffer addresses into account);

Tail Sequence Number wherein the Tail Sequence Number is a sequence number for the packet in the circular buffer address corresponding to the Tail Pointer;

Buffer Size wherein the Buffer Size is the total number of addresses for the circular buffer; and

Current Read Pointer wherein the Current Read Pointer is the circular buffer address for a next packet that will be read from the circular buffer;

B) Receiving a current packet;

C) Setting the Current Sequence Number equal to the sequence number for the current incoming packet;

D) Setting the Write Pointer Offset=(Current Sequence Number−

Tail Sequence Number);

E) Adjusting Write Pointer Offset for sequence number wrapping;

IF (Write Pointer Offset<

0−

Buffer Size)

THEN

Write Pointer Offset=Write Pointer Offset+Count of Sequence Numbers;

F) Adjusting Write Point Offset for going backwards across the sequence number wrap due to an out-of-order delivery;

IF (Write Pointer Offset>

Buffer Size)

THEN

Write Pointer=Write Pointer−

Count of Sequence Numbers;

G) Setting Buffer Spaces Used=(1+Tail Pointer−

Current Read Pointer) modulus (Buffer Size);

H) Setting Buffer Spaces Available=Buffer Size−

Buffer Spaces Used

I) Writing in-range packet;

IF (Write Pointer Offset>

Buffer Spaces Available)

THEN Discard

ELSE

IF (Write Pointer Offset<

(1−

Buffer Spaces Used))

THEN Discard

ELSE

New Write Pointer=(Tail Pointer+Write Pointer Offset) modulus (Buffer Size); and

Write the current incoming packet to circular buffer address indicated by the New Write Pointer; and

J) Check for new buffer tail;

IF (Current Read Pointer<

Tail Pointer<

New Write Pointer) OR

IF (New Write Pointer<

Current Read Pointer<

Tail Pointer) OR

IF (Tail Pointer<

New Write Pointer<

Current Read Pointer)

THEN

Tail Pointer=New Write Pointer; and

Tail Sequence Number=Current Sequence Number.

14. A method of storing incoming packets that includes storing control blocks comprising pointers to the stored packets and sequence numbers for the stored packets, the method including a step of determining a next circular buffer address in a circular buffer to receive the control block related to a current incoming packet, the determination based on a sequence number of the current incoming packet, the step of determining the next circular buffer address comprising:

A) Storing the following state variables;

Count of Sequence Numbers;

Tail Pointer wherein the Tail Pointer is a pointer to a highest circular buffer address where a control block has been written (taking wrapping of circular buffer addresses into account);

Tail Sequence Number wherein the Tail Sequence Number is a sequence number for the control block in the circular buffer address corresponding to the Tail Pointer;

Buffer Size wherein the Buffer Size is the total number of addresses for the circular buffer; and

Current Read Pointer wherein the Current Read Pointer is the circular buffer address for a next control block that will be read from the circular buffer to trigger the reading of the stored packet associated with the control block;

B) Receiving a current incoming packet;

C) Setting the Current Sequence Number equal to the sequence number for the current incoming packet;

D) Setting the Write Pointer Offset=(Current Sequence Number−

Tail Sequence Number);

E) Adjusting Write Pointer Offset for sequence number wrapping;

IF (Write Pointer Offset<

0−

Buffer Size)

THEN

Write Pointer Offset=Write Pointer Offset+Count of Sequence Numbers;

F) Adjusting Write Point Offset for going backwards across the sequence number wrap due to an out-of-order delivery;

IF (Write Pointer Offset>

Buffer Size)

THEN

Write Pointer=Write Pointer−

Count of Sequence Numbers;

G) Setting Buffer Spaces Used=(1+Tail Pointer−

Current Read Pointer) modulus (Buffer Size);

H) Setting Buffer Spaces Available=Buffer Size−

Buffer Spaces Used

I) Writing the control block for an in-range packet;

IF (Write Pointer Offset>

Buffer Spaces Available)

THEN discard incoming packet

ELSE

IF (Write Pointer Offset<

(1−

Buffer Spaces Used))

THEN discard incoming packet

ELSE

New Write Pointer=(Tail Pointer+Write Pointer Offset) modulus (Buffer Size); and

Write the control block for the current incoming packet to circular buffer address indicated by the New Write Pointer; and

J) Check for new buffer tail;

IF (Current Read Pointer<

Tail Pointer<

New Write Pointer) OR

IF (New Write Pointer<

Current Read Pointer<

Tail Pointer) OR

IF (Tail Pointer<

New Write Pointer<

Current Read Pointer)

THEN

Tail Pointer=New Write Pointer; and

Tail Sequence Number=Current Sequence Number.

15. An apparatus for re-ordering mildly out-of-sequence incoming packets through the use of a circular buffer, the apparatus comprising:

The circular buffer with a set of circular buffer memory slots, each slot having a unique circular buffer address;

A means for reading stored packets asynchronously to the arrival of new incoming packets;

A means for maintaining a tail pointer; and

A means for calculating a write pointer offset from the tail pointer to determine the circular buffer memory address to be used in connection with an incoming packet;

the means for calculating the write pointer offset including a means for determining that the incoming packet is sufficiently out-of-sequence that the incoming packet must be discarded.

16. The apparatus of claim 15 further comprising a means for writing the incoming packet to the circular buffer memory slot associated with the circular buffer address identified by the write pointer offset.

17. The apparatus of claim 15 further comprising a means for writing:

1) a control block to the circular buffer memory slot associated with the circular buffer address identified by the write pointer offset, the control block containing a representation of the sequence number for the incoming packet and a pointer to a memory storage location outside of the circular buffer; and

2) the incoming packet to the memory storage location identified in the control block.