Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-12-02
2002-07-09
Ngo, Ricky (Department: 2731)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S236000
Reexamination Certificate
active
06418118
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to packet-based data communication systems, particularly though not necessarily exclusively Ethernet networks and more particularly those conforming to IEEE Standard 802.3 (1998) Edition, or compatible with that Edition or subsequent revisions. The invention is concerned with the selective discard of packets in response to ‘flow control’ frames or their equivalent.
BACKGROUND OF THE INVENTION
As is well known in the art, data networks such as local area networks or wide area networks generally include a multiplicity of network devices, such as switches, routers, bridges and so on which have a multiplicity of ports on which data packets can be received and from which data packets can be forwarded. It is generally necessary or desirable for a network device to include storage space, such as a buffer memory, in which packets may be temporarily stored after they have been received and before they are forwarded from a relevant port or ports. In some devices there is packet storage space associated with the receiving section of each port and the transmitting section of each port; this memory space may be in addition to or in substitution for a common memory space. It is usually necessary to provide such memory space because, for example, owing to limitations of bandwidth, congestion, contention between packets or other reasons packets cannot be immediately dispatched from a network device after they have been received and any necessary processing of the packet has been performed. Such processing may include recourse to a forwarding database in order to determine the next hop on the route which the packet needs to take from its source to its ultimate destination. Since memory space either for the device in general or in relation to a particular port is necessarily limited, the device will, in order to avoid head of line blocking start discarding packets when memory space is not available.
One known method of avoiding packet loss is the technique known as ‘flow control’. In the particular Standard mentioned above, flow control is defined as the sending of a particular control frame on a link to a device, the control frame including a globally assigned media access control address, an operation code and a selectable or controllable operand. The operation code defines a pause and the operand indicates the duration of the pause. When a device receives such a control frame at a port, it is inhibited from dispatching any ordinary data frames or packets (but not control frames) from that port to the originator of the flow control frame for a ‘pause’ time specified by the operand. In the particular Standard indicated above, control frames of this nature and the operations initiated by such control frames are described on pages 1206 to 1215 of IEEE Standard 802.3, 1998 Edition published by the Institute of Electrical and Electronic Engineers, Inc N.Y. 10017-2394, USA. It will be apparent that the invention is not limited to that particular Standard and may be employed generally in circumstances where a network device can be remotely inhibited from sending packets for some interval, whether adjustable or not, by means of some control frame or signal.
Flow control is normally used within network devices such as switches to achieve a lossless mode of operation. A device which is capable of responding to flow control normally contains substantial memory so that packets may be held in that memory space at least for the duration of the pause time. However, for certain types of traffic, particularly audio traffic such as voice messages, the variable delay to packets caused by the operation of flow control can be undesirable. For the sake of explanation, it is convenient to refer to ‘latency critical’ packets which may render a message difficult to understand or unintelligible if they are delayed unduly, typically beyond 10 or 20 milliseconds. It is probably better for such packets to be discarded rather than for a message to contain differentially delayed packets, that is to say packets with a different latency owing to the onset or cessation of flow control.
One proposal for dealing with the problem is the time stamping of packets. This may be achieved by defining, in a packet header, an age field, which may be a single or multi-bit field written according to the content of a clock driven counter. The artificial age which is written into the age field when a packet is received by a device may be compared at some suitable time, for example when the packet would otherwise be forwarded from the device, with the current age and the packet discarded if the age field does not correspond to the current age. Such a technique requires an operation on the receive packet, to write in the age field, and the provision of additional memory space to accommodate the time associated with the arrival of the packet.
The present invention is concerned with an improved system which provides for selective discard of packets, preferably according to traffic type, and avoids or renders unnecessary for this purpose the time stamping of individual packets.
SUMMARY OF THE INVENTION
The invention is based on the examination of the relevant data in headers of packets to sort the packets according to traffic type so that packets are stored in at least two groups, of which one group consists of packets of a particular type (e.g. having a critical latency) and the other group is composed of other packets. A count of packets in the first group is made at the onset of a pause. If the pause period is greater than some threshold or programmed interval, the number of packets specified in the count is discarded from the first group. It is generally preferable (and usual for other purposes) to organise the sorted groups of packets as queues. The selective discard provides space within the group (i.e. queue) for the acceptance of newly arrived traffic. Preferably, after the expiry of an interval, a new packet count is obtained so that packets that are still arriving during a pause period can continually be discarded to maintain the traffic flow into this queue.
It is preferable to examine data within a packet and to use, for example, layer ⅔ priorities to provide a basis for sorting the packets into a critical queue and at least one non-critical queue.
Further objections and features of the invention will be apparent from the detailed description that follows.
REFERENCES:
patent: 4630259 (1986-12-01), Larson et al.
patent: 5444706 (1995-08-01), Osaki
patent: 5953335 (1999-09-01), Erimli et al.
patent: 5999515 (1999-12-01), Ohashi
patent: 6163528 (2000-12-01), Nagamoto
patent: 6252849 (2001-06-01), Rom et al.
patent: 95/18499 (1995-07-01), None
patent: 98/09408 (1998-03-01), None
Allwright Gareth E
Choi Kam
Gibson Patrick
Hay Christopher
3Com Corporation
Ngo Ricky
Nixon & Vanderhye P.C.
LandOfFree
Network device including selective discard 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 Network device including selective discard of packets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network device including selective discard of packets will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2867827