Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-06-19
2004-04-06
Ho, Duc (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395710, C370S415000
Reexamination Certificate
active
06717945
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention generally relates to an arbitration method for a crossbar cell switch. More particularly, the present invention relates to a method for arbitrating among crossbar cell switch input queues to select the data to be sent to an output port during a particular switching epoch.
A crossbar switch is a switch that has, conceptually, a set of input (horizontal) paths, a set of output (vertical) paths, and a set of crosspoint switches or crosspoint elements, for interconnecting any one of the vertical paths to any one of the horizontal paths. Crossbar switches may be used in communications applications to provide switching for data or information packets, including Asynchronous Transfer Mode (ATM) cells. ATM cells are 53 bytes in size and are partitioned into a 5-byte header field and a 48-byte information field. When a crossbar switch is used to switch cell-based data traffic, such as ATM traffic, the crossbar switch may be referred to as a crossbar cell switch. The cells switched by the crossbar cell switch may be referred to alternatively as packets or data traffic. The period of time for a cell to be switched from its input port to any output port may be referred to alternatively as a switching epoch or a cell transfer epoch.
Crossbar cell switches may be used in a wide variety of communications applications. For example, whenever cells are received via more than one input port (horizontal path) and the communications traffic from any input needs to be directed to one of multiple output ports (vertical path), a crossbar cell switch may be used. Crossbar cell switches may be used in data switching fabrics including fiber optic or other network hubs, for example.
While many applications for crossbar cell switches exist throughout the communications field, certain design goals are universal. For example, arbitration between input ports is preferably simple and fast to accommodate the high speed cell switching typical of modern cell switching fabrics such as ATM (Asynchronous Transfer Mode) cell switching fabrics. In the past, however, crossbar cell switches have fallen short of these goals.
In typical crossbar cell switches, only one cell may be transferred to a given output port during each cell transfer (switching) epoch. Since two or more input ports may each concurrently have a cell directed to a specific output port, a crossbar cell switch must arbitrate between input ports for service during the current cell transfer (switching) epoch. In other words, the crossbar cell switch must determine which input port may send data to a particular output port during the current cell transfer epoch.
Furthermore, each input port is preferably associated with a buffer to hold cells that cannot be transferred during the current cell transfer epoch. Typically, this buffer forms a first-in-first-out (FIFO) queue at each input port. The cell at the head of the queue at each port is referred to as the “head of line” cell (HoL). Any cell in the queue, including the HoL cell, may be destined to any output port.
In the past, arbitration methods assigned the cell transfer opportunity (which HoL cell to switch) for a given output port for the current cell transfer epoch to the first encountered HoL cell directed to that output. For instance, the cell transfer opportunity for output j for the current cell transfer epoch was assigned by examining, in consecutive order, the HoL cells at each input queue and selecting the first HoL cell directed to output j.
This approach, which consistently gives first opportunities to input port with low index, may be categorized as “unfair.” Additionally, other techniques, including examining the input ports in round robin (cyclic) order were used in the past. In a cyclic technique, the HoL cells at each input queue are examined in sequence beginning with a different, sequential, input port each time. Cyclic techniques attempted to achieve “fairness” (i.e., to prevent a single input port from monopolizing transfer resources.)
After selection of the HoL cell to be transferred to output port j during the current cell transfer epoch, other HoL cells directed to output j are blocked and cannot be transferred during the current cell transfer epoch. Additionally, the cells in each queue following the blocked HoL cells are also blocked because only an HoL cell may be transferred to an output port.
Further examination of the crossbar cell switch operating under existing arbitration methods reveals that if, for instance, the HoL cells of multiple input ports are directed towards the same output port j, a delay of one switching epoch per input port directed to output port j results before all the HoL cells have been switched to the output port j. During this delay, additional cells may arrive at any of the input ports, but must wait until the HoL cell has been switched (transferred) before the new cells (or any other cells higher in the queue) may be considered; this is often termed head of line cell blocking. If the delay in transfer is sufficiently long, cells arriving at an input port overrun that input port's queue and the incoming cell is lost.
This HoL cell blocking phenomenon may result in saturation (i.e., the queue sizes at the input ports grow without bound) when the average transfer load (cells switched per transfer epoch) reaches a certain level. That is, when the crossbar cell switch must transfer a certain average number of cells per cell transfer epoch per input port greater than its saturation threshold, the crossbar cell switch cannot meet the demand and the input port queues grow without bound. The threshold point for saturation may vary based on the type of crossbar cell switch and the system in which it is used. The upper bound on saturation is 1.0 cells per transfer epoch per input port. Generally, switching 1.0 cells per transfer epoch per input port is an unachievable goal in a crossbar cell switch. Theoretical analysis of round robin and other fair arbitration shows that a crossbar cell switch with fair arbitration will saturate when the average cell transfer rate approaches 0.58 cells per switch epoch at any input port.
In operation, an input port may be loaded to 100 percent, during peak loading conditions, so that one cell arrives per input epoch over an extended interval. Saturation may be avoided if the duration of a switch epoch is less than the duration of an input epoch so that, on average, more than one switching opportunity exists for each arriving cell. Alternately, the cycle rate at which switch transfers occur may be higher than the cycle rate at which cells arrive at the input ports.
The ratio of the rate at which switch transfer opportunities (i.e., cycles) occur to the maximum rate at which cells arrive at the input ports is known as the overspeed ratio. For typical fair arbitration methods, the overspeed ratio must be at least 1/0.58 (or about 1.70) to ensure that an input port may handle a peak load without entering saturation. Also, in a typical system, the overspeed ratio is even higher than 1.70 so that the likelihood of a large input queue is minimized.
In yet another know arbitration method, the cyclic examination of input ports start with the input port currently having the largest queue. This arbitration method results in lower input queue occupancy than does the round-robin start referred to previously. However, this arbitration method also experiences saturation at approximately 0.58 cells per switch epoch which seems to be a performance limit on all fair arbitration methods, including the present invention.
The basic performance of a crossbar cell switch is discussed in “Performance Analysis of Nonblocking Packet Switch with Input and Output Buffers,” Oie, Murata, Kubota, Miyahara, IEEE Transactions on Communications, Vol. 40, No. 8, August 1992 (hereafter Oie). Oie discloses a non-blocking packet switch with input buffers, however, Oie does not address arbitration techniques for improving the performance of crossbar cell switches.
Thus, a need exists for an improved crossba
Jue Reginald
Wright David A.
Ho Duc
McAndrews Held & Malloy
Northrop Grumman Corporation
LandOfFree
Queue size arbitration method and apparatus to enhance... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Queue size arbitration method and apparatus to enhance..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Queue size arbitration method and apparatus to enhance... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3192732