Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-05-11
2004-03-09
Vincent, David (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
Reexamination Certificate
active
06704312
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a packet switching apparatus and method applied in a network system, and particularly to a switching apparatus and method with rate guarantees and without internal speedup, using bandwidth decomposition.
2. Description of the Related Art
FIG. 1
is a schematic diagram of a well-known 4×4 input-buffered crossbar switch, wherein one end of the crossbar switch
11
includes a plurality of input ports, and each input port includes an input buffer
12
. The input buffers
12
are used to store packets entering the input ports and prevent losing the packets due to business of the crossbar switch
11
. Another end of the crossbar switch
11
is connected to a plurality of output ports. There is a controller (not shown) at the intersection of each column and each row of the crosscar switch
11
to control the direction of data flow. As shown in
FIG. 1
, for example, a connecting point
13
represents a corresponding controller at the on position, and the first input port is connected to the fourth output port, the second input port is connected to the second output port, the third input port is connected to the first output port, the fourth input port is connected to the third output port. If logic one represents the on connection and logic zero represents the off connection, a permutation matrix can be derived to represent the above connection pattern. If the cycle time in which a fixed number of packets are transfered by the crossbar switch
11
is divided into a plurality of time slots with a minimum of one package transferred between any input port and any output port only occurring in one time slot, then synchronization of package transference will be derived. It is a key point to find out what the connection patterns of the crossbar switch
11
are in each time slot.
Prior art uses internal speed up inside the crossbar switch
11
to reach 100% throughput. In other words, the speed of packet switching should be faster than the speed of packet transference, and the ratio of that is about 2 times or even more. Besides, the maximal matching between input packets and output port of the crossbar switch
11
should be determined within every time slot to output the greatest number of packets within every time slot. As described above, because a maximal matching algorithm is executed within every time slot, the speed of the crossbar switch
11
can not be increased to fit the application to current high speed networks.
Another kind of crossbar switch without internal speedup is disclosed by A. Hung, G. Kesidis and N. Mckeown, “ATM input-buffered switches with guaranteed-rate property,” Proc. IEEE ISCC'98, Athens, pp. 331-335, 1998, which uses a weighted round robin algorithm to derive rate guarantees and 100% output utilization. The above-mentioned crossbar switch must define a frame length beforehand, and packs constant number of input packets inside the frame. When the frame size is too large, the packet delay will be increased and a lot of memory will be needed to store all the connection patterns during the cycle time of the crossbar switch. When the frame size is too small, the utilization of the bandwidth will be decreased.
As mentioned above, the crossbar switch applied in current network transmission does not completely satisfy the needs of the market.
SUMMARY OF THE INVENTION
Accordingly, an objective of the present invention is to resolve the drawbacks of needing internal speedup and low utilization of the crossbar switch as in the prior art. In order to accomplish the object, the present invention proposes a switching apparatus applied in packet switching of a network system using bandwidth decomposition. The present invention also proposes a scheduling algorithm applied in an input-buffered crossbar switch. The present invention has the following characteristics:
(1) it is not necessary to speed up inside the present switching apparatus using bandwidth decomposition;
(2) it is not necessary to determine a maximal matching between input packets and output ports within every time slot;
(3) it is not necessary to define a frame length;
(4) the switching apparatus using bandwidth decomposition according to the present invention can reach 100% utilization of output rate;
(5) the present switching apparatus using bandwidth decomposition can afford quality of service (QoS) in network transmission, such as packet delay, queue length of input buffers, etc;
(6) the present switching apparatus using bandwidth decomposition affords different service qualities for clients with different service grades;
(7) In practical application, the present switching apparatus using bandwidth decomposition can be implemented by hardware circuit, especially being formed by a single chip and embedding the chip on the motherboard of a switching machine, such as Hub, Switch, etc.
The present invention proposes a switching apparatus applied in packet switching of a network system using bandwidth decomposition. An element r
i,j
in the rate matrix R=(r
i,j
) represents the input rate assigned to the traffic from the i-th input port to the j-th output port of an input-buffered N×N crossbar switch. The apparatus aspect of the present invention mainly comprises a rate-measuring mechanism, a plurality of input ports, a crossbar switch and a processing mechanism. The rate-measuring mechanism is used to dynamically measure the input rate of the present switching apparatus. The plurality of input ports, connected to said rate-measuring mechanism, include a plurality of storing devices for storing input packets. The crossbar switch, connected to said plurality of input ports, is used to transfer said plurality of input packets to the plurality of output ports of said switching apparatus using bandwidth decomposition. The processing mechanism, connected to said rate-measuring mechanism, is used to transform said rate matrix into connection patterns of said crossbar switch in each time slot of the cycle time.
The present invention regarding method mainly comprises the following steps: the step of using a von Neumann algorithm to transform the rate matrix R= of a N×N input-buffered crossbar switch to a doubly stochastic matrix {tilde over (R)}; the step of using a Birkhoff theorem to decompose said doubly stochastic matrix into a linear combination of a plurality of permutation matrices, all said plurality of permutation matrices corresponding to a connection pattern of said crossbar switch; and the step of using a Packetized Generalized Processor Sharing algorithm to set up a connection pattern of said crossbar switch in each time slot of the cycle time.
REFERENCES:
patent: 5541914 (1996-07-01), Krishnamoorthy et al.
patent: 5634004 (1997-05-01), Gopinath et al.
patent: 5680634 (1997-10-01), Estes
patent: 5850399 (1998-12-01), Ganmukhi et al.
patent: 5852740 (1998-12-01), Estes
patent: 5905730 (1999-05-01), Yang et al.
patent: 5925097 (1999-07-01), Gopinath et al.
patent: 6195187 (2001-02-01), Soref et al.
patent: 6341134 (2002-01-01), Toutain et al.
A.W.Marshall, Inequalities: Theory of Majorization and its Applications, Mathematics in Science and Engineering, vol. 143, (1979) Chapter 2, pp. 18-52.
Abhay K. Parekh, A Generalized Processor Sharing Approach To Flow Control in Integrated Services Networks: The Single-Node Case, IEEE/ACM Transactions on Netwroking, vol. 1, No. 3 (1993) pp. 344-357.
A. Hung, et al., “ATM Input-Buffered Switches With the Guaranteed-Rate Property”, IEEE, (1998), pp. 331-335.
Chang, C-S et al. “On Service Guarantees FR Input Buffered Crossbar Switches: A Capacity Decomposition Approach by Birkhoff and Von Neumann”1999 Seventh International Workshop Seminar (1999) pp. 79-86.
Chang Cheng-Shang
Chen Wen-Jyh
Huang Hsiang-Yi
Chang Cheng-Shang
Ladas & Parry
Vincent David
LandOfFree
Switching apparatus and method using bandwidth decomposition 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 apparatus and method using bandwidth decomposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switching apparatus and method using bandwidth decomposition will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3249838