Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-07-14
2003-07-15
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S353000, C370S354000, C370S363000, C370S374000, C370S383000, C370S394000, C370S395620, C370S413000, C370S414000, C370S415000, C370S416000, C370S417000
Reexamination Certificate
active
06594270
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to packet-based communication systems wherein data packets are required to form a queue. The invention is applicable but not limited to, network devices such as routers, switches, adapters and suchlike.
2. Description of Related Art
It is well known in most types of packet-based systems to provide some means, for example a FIFO defined in an allotted space in static random access memory, for holding a respective one of a multiplicity of queues of packets. In particular, packet queues may be formed for packets received by a respective port of a network device and packets may be formed into queues before they are transmitted from the respective ports of the device. It is well understood that it is necessary to provide temporary storage in the form of queues so as to take into account the differences in data rates of individual devices and links between devices as well as other considerations such as congestion, contention resolution and so forth. In a specific form of the invention described by way of example hereinafter, queues are formed at the transmit side of a switch prior to transmission across the switch; but queues may be formed in a variety of different contexts and it is not desired to limit the invention to that particular context.
It is customary to define a queue of packets by means of a ‘head’ or write pointer and a ‘tail’ or read pointer. As its name suggest, the head pointer defines the start of a queue and normally indicates the position at which new data packets will be written to the queue. The tail pointer indicates the position at which packets will be read from the queue.
It is known to form queues not only in hardware but in static random access memory and also dynamic random access memory or buffer memory wherein, unlike the formation of FIFOs in static random access memory the queue is formed by the allotment of buffers from a free pool to a particular queue under the access of a free pool controller (such as described in British patent 2321820 by way of example). However, in principle the usage of pointers is the same. It is also not important whether the head pointer points to the last location in which data has been written and so indirectly defines the next location in which the writing of a new packet will commence (as may be adopted for FIFOs implemented in SRAM) or actually points to the next free location in a buffer allotted to that memory queue, as is the practice in various forms of dynamic random access memory.
It is customary, when each packet enters the system (for example a network device wherein queues are formed), a packet receives a ‘time stamp’ to indicate the time of arrival. It is customary that when the packet has been processed the time stamp is compared with the current time to determine whether the packet has aged too much, that is to say has been held for a time which is, arbitrarily, too long. One example of this process is described in EP-A-0594196.
It is customary to define a system time (with which a packet is ‘stamped’ as it enters the system) by means of a recycling counter. The reason for this is that (as is well known), packets comprise a header portion including address data, such as media access control addresses and/or network addresses, and control data defining the packet type and other attributes, followed by the information or user data and checksum or redundancy code data. The process of stamping constitutes part of the encapsulation or deencapsulation process involving reading and/or writing of header fields and the particular action of stamping requires the writing of data into an allotted field space within the header or control portion of the data packet. Since the age field is necessarily limited, being only a few bits or even a single bit, the artificial system time must recycle. The number of bits in the age field and the recycling period are to a large extent a matter of choice, depending on the nature of the device, the traffic it must bear and the data rate at which it is required to perform.
In any event, there exists a difficulty in recycling ageing schemes, such that if a packet is delayed for an unusual time, the counter may recycle so that over age packets that should be discarded might not be discarded on the basis of a comparison of their entry age with a current system age. This may partly be offset by the employment of a comparatively long recycling period, but then the system tends to have a course granularity, thus to say the individual intervals of age (represented by the least significant bit in an age field) represent what may be an excessive unit of time.
SUMMARY OF THE INVENTION
The invention is based on the use of at least one and preferably two queue pointers to keep track of the age of packets in the queue. These include a pointer, conveniently called a ‘discard’ pointer which assumes for each ageing interval an earlier value of the head pointer so that the queue between the discard pointer and the read pointer comprises ‘over-age’ data.
In a particular example, each queue has two ageing pointers, called herein ‘current’ and ‘discard’ which are controlled in accordance with the increments of system age such that on each increment the queue head pointer is stored as a current ageing pointer and a valid flag is set whereas a previous value of the current pointer and its flag are stored as the discard pointer. The data held between the discard and the tail pointers thereby indicate all packets that have been in the queue longer than two increments of age and which now may be discarded because they are over age.
Such a process can be made to occur at every ageing increment and accordingly the discard pointer will move up the queue so that even if data cannot be removed from the queue the amount of data which is defined as ‘over-age’ will simply increase. Because the ‘over-age’ packets are defined as occurring between the discard pointer and the tail pointer, it is impossible for the stale data to become valid, unlike systems employing a simple comparison between a recycling system age and a stamped value obtained from a previous value of the artificial system age.
The above and further features of the invention will be explained hereinafter with reference to a specific example and with reference to the accompanying drawings.
REFERENCES:
patent: 4654654 (1987-03-01), Butler
patent: 5748627 (1998-05-01), Weir
patent: 2325597 (1998-11-01), None
Drummond-Murray Justin A
Law David J
Moran Paul J
Parry Robin
3Com Corporation
Emdadi Kamran
Nixon & Vanderhye P.C.
Yao Kwang Bin
LandOfFree
Ageing of data packets using queue pointers does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ageing of data packets using queue pointers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ageing of data packets using queue pointers will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3010612