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

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

2002-07-03

2004-05-25

Vanderpuye, Kenneth (Department: 2661)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S428000, C370S394000, C370S429000

Reexamination Certificate

active

06741603

ABSTRACT:

For the convenience of the reader, various acronyms and other terms used in the field of this invention are defined at the end of the specification in a glossary. Other terms used by the applicant to define the operation of the inventive system are defined throughout the specification. For the convenience of the reader, applicant has added a number of topic headings to make the internal organization of this specification apparent and to facilitate location of certain discussions. These topic headings are merely convenient aids and not limitations on the text found within that particular topic.
In order to promote clarity in the description, common terminology for components is used. The use of a specific term for a component suitable for carrying out some purpose within the disclosed invention should be construed as including all technical equivalents which operate to achieve the same purpose, whether or not the internal operation of the named component and the alternative component use the same principles. The use of such specificity to provide clarity should not be misconstrued as limiting the scope of the disclosure to the named component unless the limitation is made explicit in the description or the claims that follow.
FIELD OF THE INVENTION
This invention relates to communications systems and methods, in particular, to packet communication systems and methods.
BACKGROUND OF THE INVENTION
Mis-Ordering in Packet Communications Systems
Packet communication systems, or networks, are commonly used for the conveyance of information for data applications. However, packet networks are not perfect. While many systems are insensitive to absolute propagation delay (APD—the time it takes for a packet to propagate through the network), some systems are sensitive to propagation delay variation (PDV—changes in the APD, also known as jitter or wander).
If PDV varies enough from packet to packet, the packets may get re-ordered packets such that packet N, which was sent before packet N+1, arrives after packet N+1. An example of this mis-ordering is shown in FIG.
1
.
FIG. 1A
illustrates the general progression from transmit bits
1010
through encapsulation
1014
to transmit packets
1020
through the packet network
1024
to arriving packets
1030
through the JAB
1034
and de-encapsulation
1038
to become a stream of receive bits
1040
. Consider a CBR (Constant Bit Rate) application where the bits are created at constant rate R. The rate R remains constant because there are no pauses in the data stream. The application at the receiving end is typically set to receive and process bits at the same rate R. On the path from creation to processing at the receive end the transmit bits
1010
first arrive at a device that encapsulates them into packets and injects the transmit packets
1020
into a packet network
1024
at rate P. Just as the bits arrive from the application at regular intervals (line
1010
of FIG.
1
B), the encapsulating device
1014
sends out packets at regular interval (line
1020
of FIG.
1
B). However, the intervening packet network is not perfect, so it introduces PDV due to congestion.
In general, the mis-ordering of packets does not impair data applications. This is because the communications software associated with these applications will re-order the packets as needed. However, packet communications systems can also be used for transport of data from applications that are not so forgiving. The mis-ordering of packets impairs these applications. Examples include:
Leased line applications transported via circuit emulation
Video applications
Certain data protocols such as SNA
The option exists for using software methods to correct the mis-ordering of packets but it may be impractical for certain applications. For example, a software-based approach requires large amounts of processor power, and may be impractical for high-bandwidth systems.
One prior art solution is disclosed in U.S. Pat. No. 6,134,246 for Inverse Multiplexing Within Asynchronous Transfer Mode Communication Networks. As described in connection with FIG. 11 of the '246 patent, the patent teaches the use of a circular buffer to be used for re-synchronizing the packets based on an applied sequence number. The circular queue increments the position of the read pointer (head of the circular queue) and maintains a state variable (R_Seq_N) that indicates the sequence number of the next packet that should be read at the head of the circular queue. Incoming packets with sequence numbers in the range R_Seq_N to R_Seq_N+buffer size are processed. Packets with sequence numbers less than R_Seq_N are discarded as too late. Although the text in column 21 suggests that really early packets are discarded, the pseudo code indicates that the system handles packets with sequence numbers greater than R_Seq_N+buffer size by sending this early packet and all stored packet to the application and then setting R_Seq_N to be one sequence number larger than this really early packet. The net result is that a packet with a sequence number that is beyond R_Seq_N+buffer number results in that really early packet being processed but leads to the discarding of packets that are not unusually early.
To illustrate this point, consider a case with a buffer of eight addresses:
At time 1 the buffer contains data associated with addresses 2, 3, 4, and 6. The value of R_Seq_N is
105
.
2
(R_Seq_N =
0
1
105)
3
4
5
6
7
105
106
107
109
At time 2, an incoming packet arrives with sequence number
115
. The system reacts by providing the packets with sequence numbers
105
,
106
,
107
,
109
, and
115
to the output port all at once, rather than at an even cadence.
After time 2, R_Seq_N is set to
116
. Thus, when packets with sequence numbers
108
,
110
,
111
,
112
,
113
, and
114
arrive, they are discarded as “too late” since the next expected packet sequence number is
116
.
The sequence number
510
used in the '246 patent is applied by the switching devices and is defined as a 32 bit integer. Thus, '246 patent does not teach how to modify the control logic to handle the situation when the sequence number exceeds the maximum sequence number and restarts (wraps) with 0. Wrapping is to be expected for all practical applications
The method taught by the '246 patent does not include monitoring the position of the buffer tail and thus any use of the buffer depth in a control system would require a separate operation to determine the range of active buffer addresses. The method taught by the '246 patent is designed to ensure in-order packet delivery for non-time-critical packet traffic. Making the state machine synchronous with the incoming data is not a real drawback for this type of traffic, as it is bursty in nature and not time sensitive. The method of the '246 patent is not readily extended to applications that call for draining packets from the buffer at a constant rate. Nor does this method provide filler for missing packets.
Thus, prior art solutions do not provide an efficient, robust means to correct the order of mis-ordered packets.
It is therefore an object of the invention to provide for the efficient correction of packet mis-ordering using sequence numbers and a circular buffer.
It is another object of the invention to provide for the correction of mis-ordered packets to increase the robustness of the service to the end user without adding significantly to the need for processing power to support the application.
These and other advantages of the present invention are apparent from the drawings and the detailed description that follows.
BRIEF SUMMARY OF THE DISCLOSURE
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 p

Affiliated with

Also associated with

Rating

Use of a circular buffer to assure in-order delivery of packets does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Use of a circular buffer to assure in-order delivery of packets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Use of a circular buffer to assure in-order delivery of packets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3204001