Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-02-29
2004-05-04
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S462000
Reexamination Certificate
active
06731645
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of communications in general, and more particularly to network communications.
BACKGROUND OF THE INVENTION
Network switches (switches) may provide for the transmission of data from inputs of the switch to outputs of the switch. For example, a switch having N inputs and N outputs (an N×N switch) may provide connectivity between any of the N inputs and any of the N outputs. Data received on an input can typically be switched to any of the outputs of the switch.
FIG. 1
is a block diagram which illustrates a
2
N×
2
N switch that uses 4 N×N switch elements to allow data received at any of the switch's
2
N input ports to be switched to any of switch's
2
N output ports. In particular, first through fourth switch elements
100
a-d
provide switching wherein data received on any of the input ports
1
-
2
N can be switched to any number of the output ports
1
-
2
N. For example, data received at input port
1
can be switched to the Output ports
1
to N through the first switch element
100
a
and/or to the output ports N+1 to
2
N through the second switch element
100
b
. Similarly, data received at input port N+1 can be switched to output ports
1
to N through the third switch element
100
c
and/or to the output ports N+1 to
2
N through the fourth switch element
100
d
. According to
FIG. 1
, the switch elements can represent separate integrated circuit devices.
Data received at the input ports
1
-
2
N can typically be directed to any combination of the output ports
1
-
2
N. For example, data received at input port
1
may be directed to a single output port or to all of the output ports. Furthermore, data received at more than one input port can be directed to a common output port. For example, data that is to be directed to output port
1
can be received at all input ports
1
-
2
N. Moreover, the data can be received simultaneously. Consequently, each of the output ports has an associated queue that can be used to store data directed to that output port until the output port is available for transmission. Thus, a switch having N output ports can have N queues (one queue associated with each output port).
Additional switch elements can be added to the switch to increase the amount of data that the switch can process. For example, an N×N switch can be expanded to a
2
N×
2
N switch by quadrupling the number of switch elements. For example, according to
FIG. 1
, the first switch element
100
a
may be used to implement an N×N switch. To expand the switch to
2
N×
2
N, four switch elements are needed (i.e., the relationship between the number of input and outputs that can be switched and the number of switch elements can be quadratic). Moreover, as more switch elements are added, more switch elements may need to be coordinated during transmission of data from the output ports. For example, both the first switch element
100
a
and the third switch element
100
c
can transmit data onto output port
1
. Accordingly, the transmission of data by the first and third switch elements
110
a, c
may need to be coordinated to reduce the likelihood of contentions on the output ports which they share.
A centralized queue control circuit
105
can control which of the switch elements may transmit. For example, if two streams of data each directed to the output port
1
are received at input port
1
and input port N+1 respectively, the centralized queue control circuit
105
controls when the first switch element
110
a
transmits on the output port
1
and when the third switch element
100
c
transmits data on the output port
1
. Accordingly, the centralized queue control circuit
105
may first enable the first switch element
100
a
to transmit on the output port
1
and then enable the third switch element
100
c
to transmit on the output port
1
. The centralized queue control circuit
105
can “ping-pong” between enabling the first and third switch elements to switch the two streams of data to the output port
1
. Unfortunately, the “ping-pong” approach described above may result in an uneven or “unfair” allocation of the output port bandwidth among the switch elements used to switch the data to the desired output port. In particular, if a first switch element receives data directed to an output port at more input ports than does a second switch element, the bandwidth allocated to the first switch element can be divided among more input ports. Consequently, the bandwidth available to each of the input ports of the first switch element is a fraction of the total bandwidth allocated to the first switch element. For example, if data directed to output port
1
, is received at input ports
1
to N of the first switch element
100
a
and at input-port N+1 of the third switch element
100
c
, the first switch element
100
a
will queue data received at input ports
1
to N while the third switch element
100
c
will queue data received at input port N+1.
The centralized queue control circuit
105
can alternatingly select the first switch element
100
a
and the third switch element
100
c
for transmission therefrom. Alternating between the first and third switch elements
100
a, c
may result in 50% of the output port bandwidth being allocated to the each of the switch elements. For a switch element of size N=16 this may result in input ports
1
-
16
each obtaining approximately 3% of the output port bandwidth while input port
17
receives 50% of the bandwidth. Accordingly, there continues to exist a need to provide queued memory switches that can be expanded while maintaining fairness thereof without adding undue complexity to the associated control logic.
SUMMARY OF THE INVENTION
The present invention can provide methods, switches, systems, and computer program products that allow improved fairness in queued memory switches when devices are added to the queued memory switch to increase the capacity thereof by enabling the devices to transmit the data in the order in which the data was received.
In one embodiment of the present invention, first and second data are received at first and second inputs of first and second devices included in the queued memory switch. The first and second data are directed to the same output of the queued memory switch. An indication is made of the order of reception of the first and second data at the first and second devices. The first and second data are transmitted from the output of the queued memory switch in the indicated order of reception. Therefore, the unfair distribution of output port bandwidth associated with some conventional systems described above, may be reduced by enabling the devices to transmit the data in the order in which the data was received.
In another embodiment of the present invention, the first and second data are respective first and second cells of data. Alternatively, the first and second data may be respective first and second frames of data.
In yet another embodiment of the present invention, the indication includes a series of indications of the reception of the first and second data at a series of reception times.
In a still further embodiment of the present invention, the indication includes indicating reception of the first data and non-reception of the second data if the first data is received at a reception time and the second data is not received at each reception time. Alternatively, the indication includes indicating non-reception of the first data and reception of the second data if the second data is received at the reception time and the first data is not received at each reception time. Finally, the indication may include indicating the reception of the first data and reception of the second data if the first and second data are received at each reception time.
In still another aspect of the present invention, the indication includes storing a first indication of the reception of the first data at each reception time and storing a second indicat
Kizou Hassan
Myers Bigel Sibley & Sajovec P.A.
Swickhamer Christopher M
LandOfFree
Methods, switches, systems, and computer program products... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods, switches, systems, and computer program products..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods, switches, systems, and computer program products... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3254503