Packet switch and packet switching method using priority...

Details Packet switch and packet switching method using priority... Packet switch and packet switching method using priority...

1999-12-15

2003-11-04

Vanderpuye, Kenneth (Department: 2732)

Multiplex communications

Data flow congestion prevention or control

C370S235000, C370S389000

Reexamination Certificate

active

06643256

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a packet switch and a packet switching method for switching packets between a plurality of ports.
2. Description of the Background Art
In recent years, there are considerable progresses in the field of data communications. Traditionally, the most representative communication network has been a telephone network, but the importance of a data communication network such as Internet is increasing rapidly due to the spread of PCs for business use and home use. Recently a technique for realizing telephone service on the data communication network has also been developed by taking advantages of low cost and high efficiency of the data communication network, and there is even a discussion of amalgamation of the telephone network into the data communication network.
Now, the data communication networks are mostly packet switching networks (which are to be construed as including ATM switching networks) that carry out communications of data to be transmitted to which information indicating a destination is attached, that is, packets (which are to be construed as including cells in ATM. As the traffic amount of the data communications increases, there is an increasing demand for a larger scale packet switch for switching these packets.
There are many propositions for a configuration of a packet switch, which can be largely classified into two types. One is a multiple stage switch type in which the number of ports can be made large, which is a rather old type, and the other is a single stage switch type in which the number of ports is small, which is a relatively new type.
The single stage switch type packet switches are often equipped with a congestion control mechanism in order to prevent a congested output port from affecting flows of packets destined to the other non-congested output ports. In contrast, the multiple stage switch type packet switches presuppose that the traffic characteristics (rate) are determined in advance, so that a severe congestion has not been taken into consideration in most of them. It appears that this is also largely due to the fact that it has been difficult to implement a mechanism for dealing with the congestion in the multiple stage switch type which presupposes the extension to the large number of ports, because the congestion occurs as a result of interplay between a plurality of input ports and a plurality of output ports.
In the Internet which is the most representative data communication network, a rate by which each user transfers packets is not determined in advance, so that the congestion can possibly occur anywhere at any time. For this reason, in designing an architecture of a packet switch, techniques for dealing with the congestion are equally important as techniques for realizing the large scale implementation. The techniques for dealing with the congestion include a technique for notifying a user so as to have the packet transfer rate lowered by the user when the congestion occurs within the packet switch, and a technique for preventing the occurred congestion from affecting flows of packets that are unrelated to that congestion.
In the following, such a conventional multiple stage switch type packet switch will be described briefly.
In the case of the multiple stage switch type packet switch, a large scale packet switch can be obtained by combining smaller switching elements in multiple stages (see Joseph Y. Hui: “Switching and Traffic Theory for Integrated Broadband Networks”, ISBN 0-7923-9061-X, Kluwer Academic Publishers, 1990, sections 5.5 and 6.3).
FIG. 1
shows an exemplary configuration of a multiple stage switch type packet switch of 27 inputs and 27 outputs obtained by combining switching elements
145
each having 3 inputs and 3 outputs.
A packet entered from an input port
121
is transferred from an input side transfer unit
102
via a switching unit
104
to a desired output side transfer unit
106
, and outputted from there to an output port
161
. This multiple stage switch type packet switch can be extended to a lager packet switch by increasing the number of switching elements and the number of stages. Also, when each switching element is replaced by a larger switching element of 8 inputs and 8 outputs, for instance, a large scale packet switch can be formed using lesser number of switching elements.
A well known configuration of the multiple stage switch type packet switch is that in which a random network and a routing network are connected in cascade connection. A random network
141
and a routing network
143
of
FIG. 1
are coupling networks that are line symmetric with respect to each other. In each network, any input link can reach to arbitrary output link, through a unique route. By connecting the random network and the routing network in cascade connection, there are as many routes from a given input side transfer unit
102
to a given output side transfer unit
106
as the number of switching elements on a border between the random network and the routing network (nine in FIG.
1
).
A packet outputted from the input side transfer unit
102
is transferred to a randomly selected link so as not to collide with other packets within the random network
141
and reaches to an input of the routing network
143
. This random transfer is done for the purpose of distributing packets probabilistically to inputs (nine in
FIG. 1
) of the routing network
143
. The packet is then transferred according to its destination within the routing network
143
and reaches to the output side transfer unit
106
.
Inside the routing network
143
, there is a possibility for a packet collision to occur as a result of having a plurality of packets simultaneously transferred towards one and the same output link of some switching element. If they are packets destined to the same output side transfer unit
106
, they are bound to collide, and even if they are packets destined to different output side transfer units
106
they may still collide. In a packet switch in which each switching element does not have a queuing buffer, when the collision occurs, only one of these packets is transferred while the other one is immediately discarded. When a packet is discarded as a result of such a collision, the corresponding input side transfer unit
102
re-transmits the discarded packet.
In this way, even when a packet is discarded inside the switching unit
104
, the input side transfer unit
102
keeps re-transmitting that packet until it is successfully transferred to the output side transfer unit
106
. Consequently, the packet information will never be lost inside the switching unit
104
. When viewed from outside of the packet switch, the packet is discarded only inside the input side transfer unit
102
and the output side transfer unit
106
.
In the packet transfer control in such a multiple stage switch type packet switch, three types of congestion may occur, each of which will now be described. Here, for the sake of clarity of the explanation, it is assumed that the switching unit
104
has 4 inputs and 4 outputs obtained by combining switching elements of 2 inputs and 2 outputs each in 3 stages as shown in
FIGS. 2
to
4
.
Even in this small scale switching unit, the configuration is basically the same as
FIG. 1
in that it has the random network
141
from the first stage switching element
145
up to the input of the second stage switching element, and the routing network
143
from the output of the second stage switching element up to the third switching element
145
, so that the following description of the three types of congestion is applicable to the switching unit of
FIG. 1
or even larger scale.
First, with reference to
FIG. 2
, the first type of congestion will be described.
In an example shown in
FIG. 2
, it is assumed that a packet destined to the output transfer unit [C] exists at the input side transfer unit [A], and a packet destined to the output side transfer unit [D] exists at the input side trans

Affiliated with

Also associated with

Rating

Packet switch and packet switching method using priority... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Packet switch and packet switching method using priority..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Packet switch and packet switching method using priority... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3154750