Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-03-23
2004-09-07
Pham, Chi (Department: 2667)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S455000, C370S537000
Reexamination Certificate
active
06788698
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a technique for controlling switching of a plurality of input ports for transmitting data to an output port, and it can be applied to, for example, an ATM switch or an IP packet switch.
2. Related Background Art
In the case of transmitting a packet from an input port to an output port, a shared buffer type or an output buffer type of switch may be provided between the input port and the output port. This type of switch analyzes header information of the packet transmitted from the input port and accumulates the packet in a buffer (logical queue) provided for each output port or each priority class of each output port, based on destination information included in the header information.
When the packets to a specific output port continuously conflicts, the number of the packets accumulated in the buffer exceeds a threshold value which is a maximum limit capable of accumulating to the buffer. In this case, a process for sequentially discarding the packets from the oldest one is performed.
Furthermore, when a vacant area for one packet is produced in the buffer and the packets from a plurality of the input port conflict, an arbitration process for determining whether or not to accumulate in the buffer or to discard the packet is performed between the conflicting packets. In this case, import priority may be established at the input ports and the packets may be accumulated in the buffer in accordance with this priority.
FIG. 1
is a view for explaining conventional packet allocation processing, and shows an example in which the priority of the input ports is fixed. Specifically, in
FIG. 1
, a shared buffer type or an output buffer type of switch, which has four input ports and four output ports, is assumed.
The input ports shown in
FIG. 1
are connected to a common bus, and each input port regularly sends the packets to the bus in a fixed period. Therefore, the timing division multiplex (TDM) of the bus is realized.
For example,
FIG. 1
shows an example that the input ports Lin
2
and Lin
3
try to send the packets to the buffer
101
, when a buffer
101
connected to the output port has a vacant area able to accumulate only one packet.
The import priority of the input port is fixed as shown in
FIG. 1
, and the input port Lin
1
has the highest import priority while the input port Lin
4
has the lowest priority. Therefore, when the input ports Lin
2
and Lin
3
conflict with each other, the packet from the input port Lin
2
is necessarily selected, and the packet from the input port Lin
3
is discarded. It is to be noted that smaller values of numeric figures in a column “FETCH PRIORITY” in
FIG. 1
have the higher import priority.
On the other hand,
FIG. 2
is a view showing a conventional example in which the import priority of the input ports is periodically changed. Specifically, the import priority of the input ports is changed in turn in synchronism with the timing for inputting the packets to the bus. For example, in
FIGS. 2A
,
2
B and
2
D, since the import priority of the input port Lin
2
is higher than the import priority of the input port Lin
3
, the packet sent from the input port Lin
2
is accumulated in the buffer
101
, and the packet sent from the input port Lin
3
is discarded.
On the other hand, in
FIG. 2C
, since the input port Lin
3
has the higher import priority than the input port Lin
2
, the packet from the input port Lin
3
is accumulated in the buffer
101
while the packet from the input port Lin
2
is discarded.
However, in
FIG. 2
, since the import priority of the input ports is changed constantly in the same direction, a difference of the priority occurs by each input port. That is, for example, the priority is lowered in the order of input ports Lin
1
, Lin
2
, Lin
3
and Lin
4
. Therefore, if a conflict occurs between the input ports Lin
2
and Lin
3
, the packet from the input port Lin
2
is accumulated in the buffer
101
three times out of four times, and the packet from the input port Lin
3
is accumulated in the buffer
101
only one time out of four times.
On the other hand, there is a round robin system as a known technique for impartially selecting the respective input ports. As shown in
FIG. 3
, this system has a feature in which the arrays indicating the import priority are arranged in a ring shape and the array element having the highest priority just before is arranged to the rearmost position of the arrays. The arrays are changed in turn in the clockwise direction or counterclockwise direction in order to select the input port.
Each array is constituted by an element and a pointer as shown in FIG.
3
. The element indicates identification information of a storage device (register) and the pointer indicates identification information of the input port. In the import priority control, the pointer (for example, P1) is first read from the element (for example, 1) at which the input port having the highest import priority may be stored this time, and the input port to be read is selected. In the next reading cycle, the pointer (for example, P2) is read from the element (for example, 2) subsequent to the element read in the previous cycle in order to select the input port in the order of the arrays.
FIG. 4
is views showing the operation of the round robin system, and illustrates an example that the input ports Lin
2
and Lin
3
try to send the packets to the buffer
101
, when the buffer
101
connected to the output port has a vacant area in which only one packet can be stored.
When the import priority of the input ports is as shown in the column “FETCH PRIORITY” in
FIG. 4A
, since the import priority of the input port Lin
2
is higher than that of the input port Lin
3
, the packet sent from the input port Lin
2
is accumulated in the buffer
101
.
As shown in
FIG. 4B
, the import priority of the input ports is changed in turn in the clockwise direction. That is, in the next import timing, as shown in
FIG. 4C
, the import priority is changed so that the import priority of the input port Lin
1
having the highest priority just before. In this case, the input port Lin
2
has the higher import priority than the input port Lin
3
, and the packet sent from the input port Lin
3
is accumulated in the buffer
101
.
Similarly, in the next import timing, the import priority of the input port Lin
3
which was highest just before becomes lowest as shown in
FIG. 4E and
, in the next import timing, the import priority of the input port Lin
4
which was highest in the previous time becomes lowest as shown in FIG.
4
G.
In
FIGS. 4B
,
4
D,
4
F and
4
H, a port selected from the input ports Lin
2
and Lin
3
is encircled. As shown in the drawings, the input port Lin
2
is selected two times out of four times and the input port Lin
3
is selected in the remaining two times. In this manner, according to the round robin system, the conflicting input ports can be impartially selected.
However, in the round robin system, since the current arrays are determined in dependence on the previous arrays, the previous arrays such as shown in
FIG. 3
must be always stored. Since a flip-flop or a memory is usually used for storing the arrays, the circuit is complicated.
FIG. 5
is a timing chart showing the conceptual operation of the round robin system showing in FIG.
4
. At time t
1
in
FIG. 5
, P
2
is specified as a headmost pointer and the corresponding element is then read in sequence in synchronism with a clock by selecting the pointer value P
2
as a reference at time t
2
to t
6
. In
FIG. 5
, the input ports Lin
2
, Lin
3
, Lin
4
and Lin
1
are sequentially read as the elements.
Subsequently, at time t
8
, P
3
is designated as a headmost pointer. Here, in order to designate P
3
, the firstly-designated pointer value P
2
must be detected at time t
7
. The designated pointer value must be previously stored in order to perform such detection, and a circuit for detecting the pointer value is necessary.
Thus, the round robin system requires a circuit for de
Bandai Ryouichi
Miyazawa Yuichi
Sakaue Kenji
Unekawa Yasuo
Boakye Alexander O.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Pham Chi
LandOfFree
Data switching apparatus and data switching method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data switching apparatus and data switching method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data switching apparatus and data switching method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3226597