Multiplex communications – Channel assignment techniques – Using time slots
Reexamination Certificate
2000-03-07
2003-10-14
Nguyen, Steven (Department: 2665)
Multiplex communications
Channel assignment techniques
Using time slots
C370S395400, C370S418000
Reexamination Certificate
active
06633580
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to computer networks, and more particularly, to a crossbar packet switch suitable for use, in a switching fabric in a computer network. Crossbar switches are generally considered to be the best (performance-wise) packet switches possible to construct. Current known crossbar designs usually implement synchronous time-slotted output port arbitration, and are based on switching of fixed-size date packets. Some reference designs (e.g. ‘Knockout Switch’ developed by Yeh, Hluchy, and Acampora, and ‘gauss Switch’ designed by de Vries and used by the Dutch state telephone company) are also subject to packet (or cell) loss as a result of congestion.
U.S. Pat. No. 6,838,682 to Wicki et al. discloses a crossbar switch in a router circuit. However, the Wicki et al. switch is based on a N×M×N crossbar matrix where M is the number of input buffers per input port thus increasing the size of a standard N×N crossbar, and its arbitration protocol further does not support virtual channel and/or priorities.
Further, McKeown et al. describe in “Tiny Tera; A Packet Switch Cora”, IEEE Micro, Jan./Feb. 1997, pp 26-33 a crossbar switch configuration particularly intended for high speed networks supporting IP. However, the McKeown et at. switch configuration only supports transmission of fixed-size packets, and is based on synchronous time-slotted output port arbitration. It further does not support virtual channels and/or priorities, and it requires use of virtual output queueing at the input.
To implement e.g a System Area Network (SAN) switch based on the previously known crossbar designs referred above, is not desirable for several reasons:
1) Packet size: Typical packet sizes in a SAN could range from tens of Bytes to several hundreds of Bytes. Hence, a SAN switch should not be restricted to fixed-size packets.
2) With a non fixed-size packet a time-slotted arbitration scheme is not desirable due to latency trade-off between small packets and large packets. This calls for non-time-slotted arbitration, i.e. asynchronous arbitration.
3) Virtual Channels and/or Priorities are usually considered to be a requirement in SAN. Thus, the crossbar switch needs to provide a method of sending back information from the output port to the input port concerning the state (Virtual Channel/priority state) of a particular output queue.
4) A switch port in a SAN usually must offer a raw bandwidth in the range of tens of Gbit/s. To achieve this bandwidth with current technology, bundles of 2.5 Gbit/s serializers/de-serializers (SerDes) are usually constructed. These SerDes require many phase-locked loops (PLLs). With current technology there is a limitation to how many PLLs can possibly be put onto one Application Specific Integrated Circuit (ASIC). Therefore it is desirable to choose an implementation which does not require a centralized arbitration scheme.
SUMMARY OF THE INVENTION
To satisfy the above mentioned requirements and to solve the problems of the is prior art, there is provided, in accordance with the present invention,
a crossbar switch for a network, the crossbar switch being an N×N switch having N input ports each with a plurality of buffers capable of storing one data cell) each, and N output ports each with a plurality of buffers capable of storing one data cell each, for switchably coupling any of the N input ports to any of the N output ports, wherein
the switch contains N output port arbiters, the N arbiters operating asynchronously with respect to each other,
each of the N input ports includes a data cell scheduler, each such scheduler being operative to forward a special flag with the data cells to signal start-of-cell and end-of-cell,
the N arbiters and the N schedulers are interconnected by 2×N×N control lines,
the switch output ports operating under an arbitration protocol controlling use of said 2×N×N control lines, the protocol being operative to support the indication of:
output port busy serving another input port
output port active
output port not operational
output port accepting a data cell from an input port and having free output port buffers within a virtual channel and/or priority class for this accepted data cell
output port accepting a data cell from an input port, but not having free output port buffers within a virtual channel and/or priority class for that accepted data cell,
whereby the switch is able to support transmission of non-fixed size data cells.
In a favorable embodiment of the present invention, each of the N input port schedulers has N request output lines and N acknowledge input lines. Similarly, each of the N output port arbiters may be round robin arbiters having N request input control lines and N acknowledge output control lines.
In an even more favorable embodiment, each of the N
2
input port scheduler request output lines is wired to a request input control line for a corresponding output port. Similarly, each of the N
2
output port arbiter acknowledge output control lines may be wired to an acknowledge input line for a corresponding input port.
The scheduler may be operative to forward a clock signal with the data calls, during a data cell transmission from one input port to one output port.
Each input port scheduler may be operative to send a request to an output port for which the scheduler has a queued data cell, by asserting the request output line for that particular output port.
Each output port arbiter may include a first-level aging scoreboard mechanism for output port ownership reservation. In such an embodiment of the invention, each output port arbiter may be operative to monitor the N request input lines, and to send a grant to the one input port that appears next in a fixed round robin schedule or appears in the first-level scoreboard by asserting the acknowledge line for the one input port.
Each output port arbiter may be operative to monitor the N request input lines, and to send an output port busy indication to input ports that were not granted access, by asserting the acknowledge lines for those input ports, the input ports that were not granted access being placed in the scoreboard reservation, hereby giving preference to these input ports at the next output port ownership arbitration, and the output port busy indication being de-asserted whenever the output port is ready for a new output port arbitration.
Each output port arbiter may include a second-level aging scoreboard mechanism for buffer reservation. The output port arbiter that granted one input port access, may be operative to accept a data cell from the one input port if a free output port buffer within a virtual channel and/or priority class for that data cell exists, by asserting the acknowledge line for the one input port, or to reject the cell from that one input port if no free output port buffer exists within a virtual channel and/or priority class for that data cell, by not asserting the acknowledge line for that one input port. In this case, an output port may be operative to reserve, after having rejected a data cell from the one input port, an entry in the said second level scoreboard, hereby reserving an entry for this data cell during a next arbitration interval.
An output port may be judged to be not operational if it does not react to any request input line.
In another embodiment, each input port scheduler is operative to remove a data cell from its corresponding input port buffer, if an output port for which that data cell is destined, is not operational.
Each input port scheduler may be operative to retry request for transmission of a data cell to an output port until that output port grants the input port owrership.
Each input port scheduler may be operative under a protocol that does not allow it to transmit any data cell within one certain virtual channel or priority to any output port holding a previously transmitted data call from the same input port within said certain virtual channel or priority and for which the output port in question di
Schanke Morten
Tørudbakken Ola
Nguyen Steven
Sun Microsystems
LandOfFree
N×N crossbar packet 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 N×N crossbar packet switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and N×N crossbar packet switch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136787