Multiplex communications – Pathfinding or routing – Through a circuit switch
Reexamination Certificate
2000-03-03
2004-06-22
Vanderpuye, Kenneth (Department: 2661)
Multiplex communications
Pathfinding or routing
Through a circuit switch
C370S388000
Reexamination Certificate
active
06754205
ABSTRACT:
RELATED APPLICATION
This application claims benefit of priority under 35 U.S.C. §119 to Japanese Patent Application No. H11-57596, filed on Mar. 4, 1999, the entire contents of which are incorporated by reference herein.
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a switching element and a packet switch. More specifically, the invention relates to a switching element for use in a packet switch on an input buffer system, and a packet switch on an input buffer system.
2. Description of Related Background Art
As a device for switching a fixed-length packet, there is an asynchronous transfer mode (ATM) switch.
FIG. 11
shows the construction of a conventional ATM switch. As shown in
FIG. 11
, the ATM switch has a plurality of ATM cell transmitting mechanisms.
That is, as shown on the left in
FIG. 11
, the ATM switch has nine input ports IP
0
through IP
8
, which are connected to nine input links Link
10
through Link
18
, respectively. In addition, as shown on the right in
FIG. 11
, the ATM switch has nine output ports OP
0
through OP
8
, which are connected nine output links Link
20
through Link
28
, respectively. The ATM switch also has a switching network for transferring a cell, which is inputted from an optional input link of the input links Link
10
through Link
18
, to an optional output link of the output links Link
20
through Link
28
.
The switching network of the ATM switch comprises a plurality of switching elements SE
00
_
00
through SE
10
_
10
, which are arranged in the form of lattice to be connected to each other. In the example of
FIG. 11
, there is shown a multistage connection construction of three stages assuming that a column of three switching elements arranged in vertical directions is one stage. One switching element in a certain stage is capable of transmitting a cell to all of the switching elements in the next stage.
The cell has destination information in its header, so that the cell transmitted from one of the input ports IP
0
through IP
8
to the switching network is designed to autonomously arrive at a target output port of the output ports OP
0
through OP
8
via each of the switching elements SE
00
_
00
through SE
10
_
10
. Each of the switching elements SE
00
_
00
through SE
10
_
10
analyzes the destination information of the header of the cell, and transmits the cell to a target switching element in the next stage. Finally, the switching elements SE
00
_
00
through SE
10
_
10
in the third stage transmit the cell to a target one of the output ports OP
0
through OP
8
.
One of the characteristics of the ATM switch is that when a cell transmitted from each of the input ports IP
0
through IP
8
in a certain cell cycle collides with another cell to be discarded, the ATM switch has the function of selecting a cell transmitting path different from the initial path in the next cell cycle to inhibit the cells from colliding with each other in the switching network.
The switching procedure will be described in detail below. The switching elements SE
00
_
00
through SE
10
_
00
in the first stage are designed to transmit cells, which are inputted from the input ports IP
0
through IP
8
, to an optional switching element randomly selected from the switching elements SE
00
_
01
through SE
10
_
01
in the second stage.
At this time, if a cell collides with another cell in any one of the switching elements SE
00
_
01
through SE
10
_
01
in the second stage to be discarded without being selected by an arbiter, which is provided in each of the switching elements, so as not to arrive at a target one of the output ports OP
0
through OP
8
, a negative acknowledge signal is returned to a corresponding one of the input ports IP
0
through IP
8
, from which the discarded cell has been transmitted.
If a cell arrives at a target one of the output ports OP
0
through OP
8
without colliding with another cell in any one of the switching element SE
00
_
01
through SE
10
_
01
in the second stage, the negative acknowledge signal is not returned to the corresponding one of the input ports IP
0
through IP
8
, from which the cell has been transmitted. In addition, even if a cell collides with another cell in any one of the switching element SE
00
_
01
through SE
10
_
01
in the second stage, if the cell is selected by the arbiter, which is provided in each of the switching elements, to arrive at a target one of the output ports OP
0
through OP
8
, the negative acknowledge signal is not returned to corresponding one of the input port IP
0
through IP
8
, from which the cell has been transmitted.
The negative acknowledge signal is generated in each of the switching elements SE
00
_
01
through SE
10
_
01
. If a plurality of cells passing through the same output path are inputted to any one of the switching elements SE
00
_
01
through SE
10
_
01
, the switching element performs conciliation in accordance with a predetermined algorithm to select and output any one of the cells. Then, the above described negative acknowledge signal is returned to a corresponding one of the input ports IP
0
through IP
8
, from which an unselected one of the cells has been transmitted. The corresponding one of the input ports IP
0
through IP
8
having received the negative acknowledge signal retransmits the discarded cell in the next cell cycle since the cell transmitted therefrom has been discarded. At this time, a cell transmitting path (routing pattern) different from the cell cycle is selected.
In order to change the cell transmitting path (routing pattern), each of the switching elements SE
00
_
00
through SE
10
_
00
in the first stage has the function of transmitting a cell to any one of the switching elements SE
00
_
01
through SE
10
_
01
in the second stage. Then, a corresponding one of the switching elements SE
00
_
00
through SE
10
_
00
in the first stage transmits a cell to any one of the switching elements SE
00
_
01
through SE
10
_
01
in the second stage, which is different from that in the cell cycle, to change the cell transmitting path.
When the transmission of a cell ends in failure in the first cell cycle to retransmit the cell in the second cell cycle, it is possible to select a cell transmitting path, by which the number of discarded cells is smaller, in accordance with a predetermined algorithm. For example, the Evil-Twin algorithm is known as such an algorithm. By transmitting the cell in the second cell cycle in accordance with this algorithm, the number of collisions of cells in the switching network can be smaller than that when the cell is randomly transmitted in the second cell cycle.
As can be seen from the foregoing, in the conventional ATM switch, each of the input ports IP
0
through IP
8
selects only one cell transmitting path in one cell cycle. Then, when the first transmission of a cell ends in failure, the second transmission of the cell is tried in the next cell cycle. Therefore, there is a problem in that the probability of succeeding in the transmission of the cell by the first try is low. That is, there is a problem in that cells are easy to collide with each other in the switching network so that the network is clogged with the cells to reduce throughput. Such a problem tends to increase as the scale of the network increases.
FIG. 12
shows a status wherein, in a certain cell cycle, a cell to be transmitted from an input link Link
10
toward an output link Link
22
is inputted, and a cell to be transmitted from an input link Link
14
toward an output link Link
20
is inputted. By a routing pattern A shown in
FIG. 12
, these two cells collide with each other in a switching element SE
00
_
01
in the second stage. Therefore, for example, the cell transmitted from the input link Link
14
is discarded without being selected by an arbiter, which is provided in the switching element SE
00
_
01
. The routing pattern A is herein a pattern determined at random or in accordance with a predetermined algorithm.
On the other hand, even in the same status as that in
FIG.
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Kabushiki Kaisha Toshiba
Vanderpuye Kenneth
LandOfFree
Switching element and 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 Switching element and packet switch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switching element and packet switch will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3306588