Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-21
2004-11-02
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S386000
Reexamination Certificate
active
06813274
ABSTRACT:
FIELD OF THE INVENTION
The present invention pertains to the field of network switches and data switching. In particular, the present invention relates to a network switch and method for data switching using a crossbar switch fabric with output port groups operating concurrently and independently.
BACKGROUND OF THE INVENTION
A network switch is a data switching device that forwards a data unit (“packet”) from a source network component to a destination network component. Typically, a network switch receives a packet from the source network component via an input port and sends a packet to the destination network component via an output port. A prior network switch for packet switching utilizes a crossbar switch. A crossbar switch is a switching device that forwards packets directly from input ports to output ports without buffering.
A problem associated with a crossbar switch is “output port contention.” Output port contention occurs when multiple packets are destined to the same output port and only one packet may be forwarded to an output port at a time. As such, packets may be dropped with resulting data loss. To prevent data loss due to output port contention, packets are stored temporarily in input buffers on the input side of the crossbar switch allowing the packets to be forwarded at a later time. Another problem associated with a crossbar switch is “input port contention.” Input port contention occurs when an input port has multiple requests to switch packets, and only one request can be granted at a time. Thus, packets may be dropped because of denied requests.
In a prior network switch, a single memory is logically partitioned to provide input buffers for inputs to the crossbar switch. The input buffers store temporarily packets that are to be forwarded to the crossbar switch to avoid data loss. For such a prior input buffer crossbar switch scheme, an input port may request to send a packet from an input buffer to multiple output ports. Also, the input port may request to send packets from multiple input buffers to a single output port. The prior input buffer crossbar switch scheme utilizes a single scheduler to resolve the requests to send packets from the input ports to the output ports. For a large switch, the number of requests a single scheduler is required to process is very high, which affects throughput and causes buffer memory to be used inefficiently. Throughput relates to the amount of packets that can be switched at one time. Throughput also relates to latency, that is, the amount of time it takes to switch the packets.
Furthermore, the single scheduler for the prior network switch must resolve output port contention for all the output ports such that each output port receives at most one packet at a time. The single scheduler must also resolve input port contention for all the input buffers of each input port such that each input port sends at most one packet at a time. As a result, a bottleneck may occur during packet switching because of the sophisticated input buffer management that is required for a single scheduler to resolve output port and input port contention.
For example,
FIG. 1
shows a prior network switch
100
having an N×M crossbar switch
101
, plurality of input ports (
105
,
110
,
115
,
120
), plurality of output ports (
135
,
140
,
145
,
150
), and a single scheduler
130
. N×M crossbar switch
101
operates functionally as an N×M crossbar switch having N inputs and M outputs. For purposes of explanation, N and M=4 for N×M crossbar switch
101
such that N×M crossbar switch
101
has 4 inputs (inputs
1
through
4
) and 4 outputs coupled to output ports
1
through
4
(
135
-
150
). Each output of crossbar switch
101
includes 4 data lines (data line
1
through
4
). Data lines
1
through
4
are coupled with input ports
1
through
4
, respectively.
Each output port
1
through
4
receives a set of data lines (data lines
1
through
4
). Input ports
1
through
4
provide packets to crossbar switch
101
via inputs
1
through
4
, respectively. Crossbar switch
101
forwards packets from the input ports to output ports
1
through
4
via corresponding data lines. Crossbar switch
101
provides a common interconnection for switching packets from input ports to output ports.
For the prior network switch
100
, input ports
1
through
4
store packets temporarily in input buffer memories
106
,
111
,
116
, and
121
, respectively, that are partitioned into four input buffers
1
through
4
. The input buffers are used to alleviate output port contention and allow N×M crossbar switch
101
to operate at an input line speed for the input buffer memories. Each input buffer is designated for one of the output ports. For example, input buffers
1
through
4
of input ports
1
through
4
are designated for output ports
1
through
4
, respectively.
Input buffers
1
through
4
for input ports
1
through
4
provide packets to selectors
107
,
112
,
117
, and
122
, respectively. The selectors are devices that output selectively a single packet from multiple inputs. For example, selectors
107
,
112
,
117
, and
122
select which packets from input buffers
1
through
4
are to be forwarded to crossbar switch
101
. Scheduler
130
controls selectors
107
,
112
,
117
, and
122
via request/control lines. Output ports
1
through
4
include selectors
136
,
141
,
146
, and
151
, respectively. The selectors for the output ports are devices that output selectively a single packet from multiple input data lines. Thus, selectors
136
,
141
,
146
, and
151
select which packets are forwarded from input ports
1
through
4
to a respective output port. Scheduler
130
also controls selectors
136
,
141
,
146
, and
151
via a control line coupled to each output port.
Scheduler
130
receives requests to send packets through crossbar switch
101
to desired output ports. Scheduler
130
receives the requests from input ports
1
through
4
via the request/control lines. Scheduler
130
schedules packet switching by granting or denying the requests. Scheduler
130
grants or denies the requests by sending control signals to selectors
107
,
112
,
117
, and
122
via the request/control lines, which determine a desired packet from one of the input buffers
1
through
4
for forwarding to crossbar switch
101
. Scheduler
130
also controls selectors
136
,
141
,
146
, and
151
to receive a packet on one of the data lines
1
through
4
for output ports
1
through
4
, respectively. For example, if scheduler
130
grants a request to send a packet from input buffer
1
of input port
1
to output port
1
, scheduler
130
controls selector
107
to output a packet from input buffer
1
and controls selector
136
to receive the packet on data line
1
and output the packet to output port
1
. A limitation with the prior network switch
100
is that scheduler
130
can grant only one request at a time for each input port. Thus, an input ports sends at most one packet at a time.
For example,
FIG. 2
a
shows an illustration of input ports requesting to send packets to output ports for the prior network switch
100
. Referring to
FIG. 2
a
, input port
1
requests to send a packet to output ports
1
through
4
. Input port
2
requests to send a packet to output port
3
. Input port
3
has no requests to send a packet. Input port
4
requests to send a packet for output port
1
and output port
4
.
For the prior switch
100
, scheduler
130
must arbitrate requests for input ports
1
through
4
to send packets to output ports
1
through
4
. A disadvantage with prior network switch
100
is that scheduler
130
must resolve N×M or 4×4 requests for output ports
1
through
4
, which requires complex scheduling for a single scheduler. Another disadvantage related to the prior network switch
100
is that only one packet can be sent from an input port at a time. Consequently, because scheduler
130
can grant only one request for each input port
Chang Paul
Fang Chien
Prasad Sharat
Suzuki Hiroshi
Cisco Technology Inc.
Olms Douglas
Pizarro Ricardo M.
LandOfFree
Network switch and method for data switching using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Network switch and method for data switching using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Network switch and method for data switching using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3347047