Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-25
2003-04-29
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395710, C370S394000
Reexamination Certificate
active
06556571
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to network systems and switches that control the flow of data around the network, and more particularly to a high capacity asynchronous transfer mode (ATM) switches and schedulers that manage the flow of ATM cells through that switch.
2. Description of the Related Art
ATM switches has been deployed in numerous LAN/WAN and telecommunication systems. The basic architecture of an ATM switch is shown in FIG.
1
. The switch consists on a set of input ports, a set of output ports and a centralized scheduler. Streaming ATM cells arrive at the input ports and are switched to its designated output port(s). Any input can go to any one of the outputs in a time variant manner as determined by the ATM scheduler. With many ATM switches, a restriction is imposed that during any cell-time, exactly one cell can be scheduled. This input can connect to one or several outputs. Hence, the mapping of inputs to outputs is a one-to-many operation. If one input is switched to only one output, the mode of connection is called unicast. If on the other hand, if an input is sent to multiple output ports, the connection is called multicast. The maximum rate at which the scheduler can perform these connections is a factor which determines the maximum throughput of the ATM switch.
A variety of ATM scheduler architectures have been presented in the literature. Many of these papers focus on the input/output buffered ATM switch. See I. Iliadis, “Performance of a Packet Switch with Input and Output Queueing under Unbalanced Traffic,”
IEEE INFOCOM
, 1992 and I. Iliadis and W. E. DenZel, “Performance of a Packet Switch with Input and Output Queueing,”
IEEE INFO COM
, 1990. In an input/output buffered switch, cell queuing occurs at the input ports. All the input buffers operate at the line rate, which can be 622 Mbits/sec. or at a similar rate. One of the drawbacks of input buffering is Head-Of-Line (HOL) blocking which results in an input cell not being sent because its output buffer is full. This problem may be alleviated by queueing cells in the input modules according to their destination ports. All the queues are stored in a shared common memory.
One of the earlier methods of scheduling ATM cells is First-In-First-Out (FIFO). This method services the connections in the order in which the cells arrive at the inputs. While this method is simple, it does not guarantee fair share bandwidth. To solve this problem, fair share schedulers have been proposed. See A. Demers et. al., “Analysis and Simulation of a Fair Queueing Algorithm,”
Journal of Inter
-
networking: Research and Experience
, pp. 3-26, January 1990, Golestani, “A Self-Clocked Fair Queueing Scheme for Broadband Applications,”
IEEE INFOCOM
, June 1994, and J. Bennett and H. Zhang, “WF
2
Q: Worst-Case Fair Weighted Fair Queueing,”
IEEE INFOCOM
, pp. 120-128, March 1996. One type of fair share scheduling that has been proposed is the Weighted Round Robin. See M. Katevenis et. al., “Weighted Round Robin Cell Multiplexing in a General Purpose ATM Switch,”
IEEE JSAC
, pp. 1265-1279, October 1991.
For generality, the architecture of the scheduler can be represented as a finite state machine, as illustrated in FIG.
2
. The present state of the finite state machine (FSM), labeled P_STATE, indicates the currently selected input port that is performing the switch connection. The next selected input port, labeled N_STATE, is a function of the present state P_STATE and the two input signals, IB_STATUS and OB_STATUS. The signals IB_STATUS and OR_STATUS are status signals from the input and output buffers respectively. IB_STATUS indicates which of the input buffers (IBs) are BUSY or NOT_BUSY, i.e. whether or not it contains a cell. OB_STATUS indicates the level of congestion at the output buffers (OBs) by asserting signals STOP, SHAPE or GO for the cells destined for a particular output buffer. Thus, GO indicates that cells may be sent to the OB at its maximum line rate, and conversely, STOP prohibits the transmission of cells. The SHAPE signal, instructs the slowing down of the transmission of cells to the OB. In this state machine, it is noted that the input signals and the present state is used to determine the next state: the FSM is called the Mealy machine.
While the prior art systems have improved the speed of switches through better scheduling, small improvements in speed may be very beneficial for network performance. Additionally, the above switches do not have a high degree of scalability. Thus, if the number of ports to a switch is increased, the total processing delay of the switch increases with the number of ports. The prior art systems are also not compact in terms of the logic gates required, which is especially important when the system is implemented in silicon technology.
SUMMARY OF THE INVENTION
An object of the present invention is to provide a scheduler for a high capacity ATM switch that employs a Round Robin Scheduler that is capable of operating at high speeds.
Another object of the invention is to provide a scheduler that is compact in terms of logic gate requirements and is very scalable.
Still another object of the invention is to provide a scheduler having a total processing delay of the switch that is logarithmic with increasing number of ports on the switch, instead of increasing linearly with the number of ports.
A further object is to provide a scheduler for a switch that has a robust architecture and is capable of greater throughput.
According to the first aspect of this invention, an ATM switch is provided for controlling a flow of ATM cells in a network having input ports, output ports, and a centralized scheduler. The centralized scheduler uses a tree architecture to process packets containing data referencing a previously selected input port. The scheduler then selects a particular input port from the set of input ports and, sends the ATM cell, at the head of the port queue, port to a designated output. The scheduler may alternately employ cut-through routing to select the particular input port.
In another embodiment, the centralized scheduler selects the particular input port based on detected ready states of said input port. The ready states may be a not ready state, an ordinary ready state or priority ready state where the states are used to set precedence in the scheduler. Additionally, the selected port may also be based on the minimum cell rates of the input ports.
In a third embodiment, the scheduler of the ATM switch employs a tree architecture structure having a binary tree structure or a quartinary tree structure. Additionally, the ATM switch can be operated in unicast and multicast modes of connection.
In a fourth embodiment, a method of scheduling input signals arriving at input ports to be sent to output ports is provided. The ready states of said input ports are determined, one of said input ports is selected in a round robin fashion based on said ready states, and the input signals are sent from the selected input ports to a designated output port. The selection process uses a tree architecture having a given number of nodes such that packets, containing information related to a previously selected input port, the ready states and the output ports, pass through the nodes and a particular packet is selected having the designated output port.
In a fifth embodiment, each of the nodes has two inputs and one output and determines which input is provided to said output by on the fly comparisons of certain bits of each packet.
In a sixth embodiment, the switch is an ATM switch.
In a seventh embodiment, the scheduling employs a tree architecture structure having a binary tree structure or a quartinary tree structure and may be operated in unicast and multicast modes of connection. In an eighth embodiment, the selection process is conducted in a weighted round robin fashion.
In the ninth embodiment, an ATM switch is provided for controlling a flow of ATM cells in a network having input ports, output ports, and a centralized scheduler
Ishii Alexander T.
Shahrier Sharif M.
Kizou Hassan
NEC USA Inc.
Qureshi Afsar M.
LandOfFree
Fast round robin priority port scheduler for high capacity... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast round robin priority port scheduler for high capacity..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast round robin priority port scheduler for high capacity... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3013206