Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
1999-10-13
2004-01-20
Nguyen, Chau (Department: 2663)
Multiplex communications
Data flow congestion prevention or control
C370S235000, C370S413000
Reexamination Certificate
active
06680908
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to network switches for packet-based communication systems such as Ethernet networks and also to an improved method of operating such a network switch. The term ‘switch’ is intended to refer broadly to a device which receives data packets at any of a multiplicity of physical ‘ports’ addressed and which can internally switch those packets so that received packets are forwarded from one or more ports in response to that address data or modified forms of such data. The invention is applicable to a variety of different switch architectures, as indicated hereinafter. The invention is intended to be applicable to both ‘bridges’ and ‘routers’.
BACKGROUND TO THE INVENTION
Broadly, switches of the kind to which the invention relates have a multiplicity of physical ports at which addressed data packets can be received The data traffic, and therefore the occupancy of bandwidth, to any particular port may vary widely. Typically, the switch includes means for temporarily storing packets received by the input ports and means (hereinafter termed ‘output buffer’) for the temporary storage of data packets before they are forwarded from an output port. Such means might be individual FIFO stores, respective allocated memory space or other forms of memory. The switch includes a forwarding database which is built up typically by reading of source addresses in incoming packets, and permits from an examination of a received packet and recourse to associated data, the determination of each port from which a receive packet should be dispatched. Packets having destination addresses which do not appear in the database need to be ‘broadcast’ either throughout the whole or part of the network in order to achieve address resolution. Generally, switches which rely on media access control, or layer
2
, addresses are termed ‘bridges’ whereas switch devices which rely on logical link control (layer
3
) addresses are termed ‘routers’.
In almost all switches of this general kind, there is a conflict of bandwidth requirements of different types of packet In any practical system, the buffer space available for the transmit ports of a switch is limited and accordingly switches in practice are inherently liable to congestion.
Various techniques are currently used to bridge and or route data packets of different type. These techniques generally rely on the individual packets protocols or priorities to influence the speed of transmission through the switch and/or to determine whether the packet will be discarded if the device becomes congested. Generally, packets of higher priority experience the lower rate of discard. However, when and how many packets of each priority are discarded depends on a variety of factors such as the state of congestion of the switch at the time of discard, the priority algorithm which is used and so on. Thus the output bandwidth occupied by each type may range from zero (when all the packets are discarded) to full (with no discard). In practice, whether any given packet is forwarded across a switch to an output buffer and is forwarded from the respective port actually depends on whether that buffer is already full. Fullness of a buffer is customarily presumed to exist when the buffer reaches a state of fullness which is less than the total physical memory space allocated to an output queue of packets.
For a variety of traffic, such as voice data, the possibility that, at least temporarily, there might be no bandwidth available for the transmission of the respective data and that packets are discarded is undesirable.
The object of the present invention is to provide for at least one type of traffic, as denoted by relevant data within the packets, a minimum bandwidth in an output link.
SUMMARY OF THE INVENTION
In a preferred form of the invention, bandwidth allocation for each defined packet type is achieved using a single buffer memory space. Different categories of packet are selected by (preferably) examination of protocol fields and/or priority fields in packets received by the switch. Each selected category is preallocated a minimum proportion of the total available output bandwidth. This is equated to the same proportion as the number of bytes of the total transmit port's buffer size. Thus for example if the total bandwidth available on a link to which data is forwarded from the buffer is 1 Gigabit per second and a packet of given category is allocated one tenth of the available bandwidth, then its minimum bandwidth allocation will be 100 megabits per second. If the total transmit port's buffer space is, for example, 100 kilobytes, then one tenth of the buffer space, in this case 10 kilobytes, of the buffer space is reserved for packets of that category. As packets of the different categories are written into the buffer, a running accumulation may be kept of the total bytes allocated for the various types. Similarly, as packets of a given category are emptied from the buffer, by forwarding over the associated link, the running accumulation of the packet sizes of that category is decremented according to the bytes of the output packets. Thereby the total byte count for a given packet category is known continuously. Before a new packet can be written into the buffer, the accumulated total is compared with the allocated value and a decision made whether to discard or retain the packet. If the respective accumulated total is less than the respective allocated number, the packet will be allowed into the buffer because the packet type has reserved bandwidth available. However, if the respective accumulated amount exceeds the respective allocated number, the packet will be discarded. Restricting the packet categories to a percentage of the buffer size is in effect reserving minimum bandwidth for each category under congested conditions.
It will be appreciated that in general according to the invention packets of the different categories will be intermixed within a single buffer. Discarding packets only after they exceed the respective allocation of bytes within the output buffer not only ensures that a minimum bandwidth is guaranteed for at least each packet category in congested units, but also, under non-congested conditions, the actual bandwidth used by a packet category can exceed its allocation because it may still use up to the maximum available bandwidth on the link provided that the buffer quota is not exceeded.
It may be necessary, if lower latency is required for certain packet categories, to employ two or more buffers to constitute the allocated memory space.
REFERENCES:
patent: 5781801 (1998-07-01), Flanagan et al.
patent: 6108306 (2000-08-01), Kalkunte et al.
patent: 6285658 (2001-09-01), Packer
patent: 6412000 (2002-06-01), Riddle et al.
patent: 6418118 (2002-07-01), Hay et al.
patent: 6456590 (2002-09-01), Ren et al.
patent: 6493315 (2002-12-01), Simpson et al.
patent: 6496478 (2002-12-01), Choi et al.
patent: A-41300/93 (1993-12-01), None
patent: 0 577 359 (1994-01-01), None
patent: 0 748 087 (1996-12-01), None
patent: 0 577 359 (1998-04-01), None
patent: 2 321 820 (1998-08-01), None
patent: 2 339 371 (2000-01-01), None
Allwright Gareth E
Choi Kam
Gibson Patrick
Hay Christopher
3Com Corporation
George Keith M.
Nguyen Chau
Nixon & Vanderhye P.C.
LandOfFree
Network switch including bandwidth allocation controller 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 switch including bandwidth allocation controller, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network switch including bandwidth allocation controller will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3206922