Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-11-30
2003-09-23
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S235000
Reexamination Certificate
active
06625159
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to all cell or frame based shared memory switches that control routing-of discrete packets between an input port and an output port.
BACKGROUND OF THE INVENTION
Two basic forms of communications are circuit switched and packet switched communications. Circuit switched communications open a dedicated path of communication between a source and a destination. This forecloses access to the path by other sources and/or destinations even if only a small portion of the bandwidth of the path is being utilized. In the packet switched method, data is broken into packets when transmitted from a source and reassembled at the destination. This allows multiple sources and destinations to divide up and utilize the bandwidth of any given path, but presents a more complex problem because conflicting communications will contend for limited communication path resources.
Such switches require an amount of memory because packets will often have to wait a number of cycles before being transferred due to contention. Multi-port switches are generally classified by the manner in which their memory is allocated, as either input buffered, output buffered or shared memory architectures.
Input buffered switches are those in which packets are stored in an input queue. The recognized problem of these switches is termed head-of-line-blocking (HOL), where a packet at the head of the queue prevents others from being transmitted until the destination port transmits that packet. An algorithm is applied to the packet at the head of the queue to determine its destination. This packet remains at the head of the queue until the destination port processes or transmits the packet. Additional received packets are blocked by the packet at the head of the line. As an example, consider a system having one input port A and two output ports B and C. A situation may occur where output port B has become congested and packets arriving from input port A can not be transmitted to output port B as fast as they are arriving. Packets buffered for output port C will be transmitted. After a time, the buffers will be filled with packets destined for output port B which can not be transmitted. At this point, all packets arriving from input port A for output B and for output port C will be discarded. Even though output capacity for output port C is available, congestion at output port B will cause output port C's packets to be dropped. This head of line blocking is an undesirable effect because congestion on one network path interferes with traffic on other uncongested paths.
Output buffered switches solve these input buffered switch blocking problems by queuing packets at the output ports. This prevents one stream of traffic from a given input port from blocking other streams of traffic destined for a different output port. These switches suffer from a fairness problem though, because there is the potential that where traffic is inbound on two ports and destined for a single output port, one stream will completely consume all available buffers associated with the single port, leaving no buffers for the second stream. The problem is acute in environments with large bursts of traffic. Outbound packets are dissociated from their input port, any input port can therefore consume all the available buffers, leaving very few or no buffers for other input ports.
Shared memory switch architectures alleviate some of problems of both input buffered and output buffered switches, but potentially suffer the same problems of each to a lesser degree. In a shared memory switch, there is a pool of available buffers. These buffers may be allocated as either input or output buffers as needed. Once a buffer is released, it is returned to the pool of available buffers for use again as either an input or output buffer. There is a reduced potential for head-of-line-blocking and unfairness in allocation of the buffers, but each is still possible.
Accordingly, there is need for a shared memory switching method which solves head-of-line-blocking problems and provides improved fairness in allocation of output buffers among input ports. It is an object of the invention to provide such an improved shared memory switching method and switch.
SUMMARY OF THE INVENTION
The present invention provides an improved shared memory switching method and switch in which a guaranteed minimum number of buffers per output port is reserved for each input port. This precludes one input port from blocking the packet traffic of another input port at any of the output ports of the switch. The invention also provides a burst handling capability through optional preferred features in which the shared memory of the switch is divided into reserved and unreserved buffers, with the guaranteed minimum number of buffers being provided from the reserved buffers. The unreserved buffers are available to any port and will handle burst communications that exceed a given input port's allocation of reserved buffers. So that bursts are also handled fairly among input ports, additional optional preferred features of the present invention involve limiting the number of unreserved buffers that may be consumed by a single input port. For fairness among output ports, method also preferably fairly allocates unreserved buffers among the output ports.
REFERENCES:
patent: 5574885 (1996-11-01), Denzel et al.
patent: 5796715 (1998-08-01), Patterson et al.
patent: 5805589 (1998-09-01), Hochschild et al.
patent: 6097705 (2000-08-01), Ben-Michael et al.
patent: 6160814 (2000-12-01), Ren et al.
patent: 6295295 (2001-09-01), Wicklund
patent: 6359861 (2002-03-01), Sui et al.
patent: 2001/0007562 (2001-07-01), Matsuoka et al.
Melvin Bruce W.
Singh Bharat K.
Thaler Patricia A.
Elakam Ahmed
Kizou Hassan
LandOfFree
Nonblocking and fair queuing switching method and shared... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Nonblocking and fair queuing switching method and shared..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonblocking and fair queuing switching method and shared... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101177