Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-04-16
2003-04-01
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S413000
Reexamination Certificate
active
06542507
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital LAN and WAN traffic switches, particularly ATM (Asynchronous Transfer Mode) switches.
STATE OF THE ART
An ATM cell switch takes cells from many sources, and routes them to many destinations. Such a switch may. be hardware-based, or hardware and software based. The architecture can be generalized as shown in FIG.
1
. Cells arrive on input ports
1
to N
in
and are switched through a switch “fabric”
100
to various ones of output ports
1
to N
out
.
A “cell” is a fixed size unit (53 bytes), which constitutes a fraction of a larger communication. Cells come in on input ports, and get routed to output ports.
Sometimes, “collisions” take place between cells. That is, cells come in on two or more input ports that are destined for the same output port. There are two scenarios which describe the condition when two or more cells are destined to the same output port: 1) momentary contention or cell collision; and 2) sustained contention or congestion.
In either case, the collisions create the need for “queuing,” where one or more cells have to wait in line to be delivered to the output port.
With some architectures, even when there are no collisions, “blocking” can take place. Blocking occurs when a cell cannot be delivered because the delivery of other cells is taking up the resources necessary for the delivery of the blocked cell. This is often referred to as “head of line” (HOL) blocking. Blocking is undesirable, since it can delay the delivery of other cells. Also, blocked cells must be queued, just like cells delayed due to collisions.
Due to these inevitable delays in delivery, a successful architecture must properly queue cells for delivery. Such queuing is referred to herein as “buffering”. Buffering requires buffer control. Buffer control tells the switch buffers when to release a cell from a queue for delivery to the output port.
Even with buffer control, it is sometimes necessary to “drop” cells. For instance, when cells come in on input ports
1
and
2
, all destined for output port
3
, it is often the situation that more cells come in than can be output from port
3
. The cells begin to be queued up in the buffers. If this situation continues long enough, the buffers get filled up, and cells need to be thrown away, or “dropped.” A good design minimizes the amount of cells that need to be dropped.
Prior solutions to buffer control fall into two basic categories: 1) input buffering with input control; and 2) output buffering with output control.
With input buffering and input control, cells are queued at the input ports, and released to the output ports based on the state of the input queues. The advantage of buffering at the input is that it requires smaller buffers to maintain the same levels of dropping when compared to output buffering. Also, when cells are buffered at the input cells can be dropped before going across the switch fabric. This reduces the total traffic load on the switch fabric, which reduces the chance of chronic congestion at the output port.
The problem with input buffering and input control is that cells are released through the switch fabric based on the state of each individual input buffer. That is, when there are cells in the input buffer, they are released to the output ports based on metrics that are available at the input port: size of the input buffers, incoming rate, length of time since a cell was last released, etc. This often leads to non-optimal control strategies, since input control segregates flow control information such that any one input controller does not have status information on its peer input controller.
With output buffering and output control, cells are immediately passed through from the input port, through the switch fabric, and to a buffer on the output port. There, cells are released from the queues to go out the output ports. The control is based on the state of the output port.
The advantage of output buffering is that the buffers can be controlled with the very precise information gathered at the output port. For instance, if an output port is busy transmitting a cell, there is no use releasing another one. Conversely, if an output port is idle, ideally a cell would be immediately released to it for transmission. With output buffering and output control, all the information is available at the output port to implement very precise control algorithms.
Problems encountered with output buffering and output control include increased traffic and increased buffer size. With output buffering and output control, cells are dropped after they go across the switch fabric; this creates extra traffic across the switch fabric, which exacerbates congestion states. Output buffering and output control also requires larger buffers to maintain the same level of “cell drop” performance as input buffering, since cells can be delivered to output buffers from several sources. This also means that output buffers can be filled very rapidly, and so must support the aggregate input port bandwidth. This problem becomes insurmountable as the number of ports in the system increases. In general, instantaneous bandwidth into an output queue is linear with the number of ports. This leads to exponential growth in total queue sizes as the number of ports increases.
What is needed, then, is an improved buffer control arrangement suitable for a high-speed, high-performance digital traffic switch.
SUMMARY OF THE INVENTION
The present invention, generally speaking, uses input buffering and output control to provide a high-speed, high-performance digital traffic switch. This approach solves the problems noted above with respect to the prior art. More particularly, in accordance with one embodiment of the invention, a method is provided for controlling buffering of discrete information units of digital data within a digital switch having multiple input ports, multiple output ports, a switch fabric, an input buffer control unit, an input buffer unit, an output data flow control unit, and an output rate buffer unit. The switch fabric has having an input side and an output side, for switching a discrete information unit received at any of the input ports to any of the output ports. Discrete information units received at the input ports are buffered within the input buffer unit, and the input buffer control unit then generates a “Request” to release (from the input buffer unit) a “discrete information unit” destined for a particular output port. The output data flow control unit monitors status of the output port and, in response to the “Request”, generates a “Grant” to release (from the input buffer control unit) the discrete information unit destined for the particular output port.
In this approach, dropped discrete information units (cells) are dropped at the input port, and so will not be transmitted across the switch fabric. This reduces the traffic load on the switch fabric during congested periods, and allows the output stage of the switch fabric to be designed with only the bandwidth required by the output port. Because the traffic load across the switch fabric is regulated by the output port, this architecture scales well to larger systems.
Input buffering and output control allows for the use of smaller buffers for the same level of “discrete information unit (cell) drop” performance that would be provided by output buffering and output control.
Input buffering and output control provides all the information to the output data flow controller necessary to implement very precise control algorithms. These algorithms can then administer switch fabric admission policies and contract enforcement fairly across all input ports.
REFERENCES:
patent: 5325356 (1994-06-01), Lyles
patent: 5371893 (1994-12-01), Price et al.
patent: 5446738 (1995-08-01), Kim et al.
patent: 5448559 (1995-09-01), Hayter et al.
patent: 5448701 (1995-09-01), Metz, Jr. et al.
patent: 5459455 (1995-10-01), Sato
patent: 5475679 (1995-12-01), Munter
patent: 5511070 (1996-04-01), Lyles
patent: 5550823 (1996-08-01), Irie e
Bailey John W.
Hoogenboom Christopher Leo
Khacherian Todd L.
Nishimura Michael Jon
Wallner John Daniel
Alcatel
Yao Kwang Bin
LandOfFree
Input buffering/output control for a digital traffic switch does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Input buffering/output control for a digital traffic switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Input buffering/output control for a digital traffic switch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3078726