Note: Descriptions are shown in the official language in which they were submitted.
t ,
CA 02541873 2001-09-05
-1-
PACKET SWITCHING EQUIPMENT AND SWITCHING CONTROL METHOD
This application is a division of Canadian Application No. 2,356,727
filed September 5, 2001 for Packet Switching Equipment and Switching
Control Method
BACKGROUND OF THE INVENTION
Field of the Invention
The present invention relates generally to a packet switching
equipment and a switching control method. More particularly, the
invention relates to a switching control system in a packet switching
equipment for switching a packet between a particular input port and a
particular output port by employing packet communication technology,
such as ATM (Asynchronous Transfer Mode), IP (Internet Protocol) and so
forth.
Description of the Related Art
Conventionally, a packet switching equipment of this kind is
constructed with input buffer portions 1-1 to 1-n [input buffer portions 1-2
to 1-(n-1) are eliminated from illustration] which will be occasionally
identified by reference numeral 1 as generally referred to, an arbiter
portion 2 and a switch core portion 5 as shown in Fig. i1.
The switch core portion 5 performs switching of packets between
input ports 100-1 to 100-n [input ports 100-2 to 100-(n-1) are
eliminated from illustration] which will be occasionally identified by
reference numeral 102 as generally referred to, and output ports
101-1 to 101-n [output ports 101-2 to 101-(n-1)
i
CA 02541873 2001-09-05
- 2 -
are eliminated from illustration] which will be occasionally
identified by reference numeral 101 as generally referred to.
Each of input buffer portions 1-1 to 1-n includes logic
queue 11-1 to 11-n [ logic queues 11-2 to 11- ( n-1 ) are eliminated
from illustration] which will be occasionally identified by
reference numeral 11 as generally referred to, a packet input
portion 12 and a packet output portion 13 and temporarily store
the.packets arriving to the input ports 100-1 to 100-n. The
arbiter portion 2 performs arbitration of output demand from
the input buffer portions 1-1 to 1-n for outputting an output
permission depending upon result of arbitration and applies
opening and closing command to points of intersections in the
switch.core portion 5.
As the switch core portion 5, as shown in Fig. l2, it has
been considered a construction for opening and closing (ON/OFF)
of the points of intersections 50 of transmission paths extending
in grating form. In this construction, when a plurality of input
ports 100 transmit packets to a particular output port 101
simultaneously, packet collision is caused for breakage of data
transferred by the packets. Therefore, at the same timing, the
input port 100 to transmit the packet to the particular output
port has to be limited to one.E
Next, discussion will be given for operation of the
conventional packet switching equipment. The packets arriving
to the input ports 100-1 to 100-n are stored in the logic queues
CA 02541873 2001-09-05
- 3 -
11-1 to 1l-n in the respective input buffer portions. The input
buffer portions 1-1 to 1-n check destination output ports 101-1
to 101-n from header information of the leading packets of the
logic queues 11-1 to 11-n and notify an output demand for
outputting to a destination output port, to the arbiter portion
2 by an output demand signal.
The arbiter portion 2 aggregates output demand signals
from all input buffer portions 1-1 to 1-n. When output demands
from a plurality of input buffer portions 1-1 to 1-n are present
for the same output ports 101-l to 101-n (upon occurrence of
conflict), arbitration is performed for providing an output
permission only for selected one of the input buffer portions
1-1 to 1-n.
The arbiter portion 2 performs arbitration for avoiding
packet collision at all output ports 101-1 to 101-n . Thereafter,
acceptance and rejection of demand is notified to the input
buffer portions 1-1 to 1-n by using the output permission signal.
The input buffer portion n which is accepted the demand transmits
the leading packet to the switch core portion 5. The switch
core portion 5 opens and closes the points of intersections
50 for switching the predetermined output ports 101-1 to lOln
on the basis of the result of4arbitration obtained from the
arbiter portion 2.
As shown in Fig. 13; in the above-mentioned conventional
packet switching equipment, when the arbiter portion 2 made
CA 02541873 2001-09-05
-4-
decision to permit outputting to the output port #2 for the input buffer #0
which contains the leading packet designated to the output port #2, the
output permission for outputting to the output port #2 is given for the
input buffer #0 from the arbiter portion 2. At the same time, the switch
core portion 5 is commanded to close the point of intersection between the
input port #0 and the output port #2 and is controlled so that packet can
be switched between the objected ports.
As set forth above, the conventional construction requires control of
the switch core portion 5 corresponding to the content of the decision in
the arbiter portion 2, and thus, requires synchronous operations of the
input buffer portions 1-1 to 1-n, arbiter portion 2 and the switch core
portion 5 without disturbance which makes the control structure of the
switch core portion 5 complicated.
SUMMARY OF THE INVENTION
Therefore, the present invention has been worked out in view of the
problem set forth above. It is an object of the present invention to provide
a packet switching equipment and a switching control method, in which
operation of the switch core portion is performed independent of content
of decision of an arbiter portion and overall equipment can be constructed
with simple control structure.
According to the first aspect of the present invention, a packet
switching equipment for switching packets between input ports and output
CA 02541873 2001-09-05
-5-
ports, comprises:
input buffer portions temporarily storing packets arriving to the
input ports, adding labels identifying destination port numbers to the
packets, and outputting packets with added labels;
a switch core portion for switching the packets on the basis of the
labels added by the input buffer portions; and
an arbiter portion providing output permissions to the input buffer
portions for outputting to the output ports,
a sorting network autonomously sorting and concentrating the
packets on the basis of the labels added to the packets being applied to
the switch core portion.
According to the second aspect of the present invention, switching
control method for a packet switching equipment for switching packets
between input ports and output ports, comprises:
receiving packets at input buffer portions;
adding labels to the packets at the input buffer portions, the labels
identifying destination port numbers;
switching the packets on the basis of the labels added by the input
buffer portions by a switch core portion;
providing output permissions by an arbiter portion to the input
buffer portions for outputting to the output ports by an arbiter portion;
and
employing a sorting network autonomously sorting and
concentrating the packets on the basis of the labels added to the packets
CA 02541873 2001-09-05
-6-
~in the switch core portion.
In the construction set forth above, the switch core portion executes
autonomous sorting and concentration only with reference to the labels
added to the input packets, and is independent of the contend of decision
of the arbiter portion. Therefore, it becomes unnecessary to employ
complicated control structure establishing synchronization over the entire
packet switching equipment, and thus, control of the packet switching
equipment can be made simple.
In the preferred construction, the arbiter portion may execute an
output destination adjusting process for providing output permission for
outputting to the output ports for the input buffer portions storing the
packets with avoiding overlapping and a vacant port adjusting process
assigning idle output ports not occupied by any input buffer portions for
idle input buffer portions not obtaining output permission. The input buffer
portions assigned the output ports by the output destination adjusting
process, may output valid packets to . the assigned output ports and the
input buffer portions assigned the output ports by the vacant port
adjusting process may generate and output dummy packets addressed to
the assigned output ports.
By outputting the dummy packet from the input buffer portions
assigned to the idle output ports, in the case where the sorting network for
sorting and concentrating the packets in order of labels, the packets can
be accurately switched to the objective output ports.
The packet switching equipment may further comprise a packet
CA 02541873 2001-09-05
_ 7 _
filtering portion provided corresponding to respective output ports and
passing only valid packets and abandoning dummy packets.
Thus, the dummy packet will not be output externally from the
packet switching equipment to restrict wasting of the network resource.
BRIEF DESCRIPTION OF THE DRAWINGS
The present invention will be understood more fully from the
detailed description given hereinafter and from the accompanying
drawings of the preferred embodiment of the present invention, which,
however, should not be taken to be lirr~itative to the invention, but are for
explanation and understanding only.
In the drawings:
Fig. 1 is a block diagram showing a construction of one embodiment
of a packet switching equipment according to the present invention;
Fig. 2 is an illustration showing a construction of a Batcher network
of input port number = output port number = i6;
Fig. 3 is an illustration showing a condition where packets having
destination portion numbers #0, #4, #6, #1i, #15 are sorted by the
Batcher network;
CA 02541873 2001-09-05
Fig. 4 is a flowchart showing a flow of arbitration process
executed in the arbiter portion of Fig. 1;
Fig. 5 is a flowchart showing a flow of arbitration process
executed in the arbiter portion of Fig. 1;
Fig. 6 is an illustration showing one example of a packet
format in the equipment output from the input buffer portion
of Fig. 1;
Fig. 7 is an illustration showing a packet switching
operation in one embodiment of the packet switching equipment
according to the present invention;
Fig. 8 is an illustration showing a condition after
execution of a vacant port arbitration process in one embodiment
of the packet switching equipment according to the present
invention;
Fig. 9 is an illustration showing a condition of output
destination arbitration process after execution of a vacant
port arbitration process in one embodiment of the packet
switching equipment according to the present invention;
Fig. 10 is an illustration for explaining operation of
the switch core portion and a filtering portion of Fig. 1;
Fig. 11 is a block diagram showing a construction of the
conventional packet switching equipment;
Fig. 12 is a block diagram showing a construction of the
conventional switch core portion; and
Fig. 13 is an illustration showing one condition showing
CA 02541873 2001-09-05
_ g _
operation process in t'he conventional packet switching
equipment.
DESCRIPTION OF THE PREFERRED EMBODIMENT
The present invention will be discussed hereinafter in
detail in terms of the preferred embodiment of a packet switching
equipment according to the present invention with reference
to the accompanying drawings. In the following description,
numerous specific details are set forth in order to provide
a thorough understanding of the present invention.
Fig. 1 is a block diagram showing a construction of one
embodiment of the packet switching equipment according to the
present invention. In Fig. 1, one embodiment of the packet
switching equipment is constructed with input buffer portions
1-1 to 1-n [ input portions 1-2 to 1- ( n-1 ) are eliminated from
illustration] which will be identified by a reference numeral
100 as generally referred to, a switch core portion 3, an arbiter
portion 2 and filtering portions 4-1 to 4-n (filtering portions
4-2 to 4-(n-1) are eliminated from illustration) which will
be identified by reference numerals 4 as generally referred
to. The input buffers 1-1 to 1-n includes logic queues 11-1
to 11-n [logic queues 11-2 to li-(n-1) are eliminated from
illustration] which will be identified by reference numeral
11 as generally referred to, a packet input portion 12 and a
packet output portion 13.
The logic queues 11-1 to 11-n are constructed to store
CA 02541873 2001-09-05
- 10 -
all of arriving packets in FIFO (First In First Out) manner.
It may also be possible to have a construction to provide FIFO
per f low, in which packet belongs . In either case, the present
invention is applicable and equivalent effect may be achieved.
The construction of the logic queues 11-1 to 11-n should not
serve as limitative factor for the present invention.
In the later case, the packet input portion 12 extracts
flow identifier from the header portion of the packet arriving
to the input ports 100-1 to 100-n [ input ports 100-2 to 100-(n-1 )
are eliminated from illustration] which will be identified by
the reference numeral 100 as generally referred to, and
recognizes a service class, in which packet belongs, and a
destination output port by making reference to a f low information
database with taking the flow identifier as key. On the basis
of the result of recognitions, the packets are stored in
appropriate logic queues 11-1 to 11-n.
On the other hand, for the input buffer portions 1-1 to
1-n, numbers for identification are assigned. In the shown
embodiment, for port number N, integer in a range of 0 to N-1
are assigned.
The switch core portion 3 for switching between the input
ports 100-1 to 100-n and outputi ports 101-1 to 101-n [output
ports 101-2 to 101-(n-1) are eliminated from illustration] which
will be identified by reference numeral 101 as generally referred
to, is constructed with a sorting network. As the sorting
CA 02541873 2001-09-05
- 11 -
network, it may be a Batcher network proposed in "SortingNetworks
and Their Applications" (K. E. Batcher, Proc. 1968, Spring Joint
Computer Conf., pp. 307 to 314).
Fig. 2 is an illustration showing a construction of the
Batcher network of input port number = output port number =
16. In Fig. 2, the Batcher network has simple construction,
in which 2 x 2 unit switches are connected in plurality of stages .
In the unit switch, the packet having greater label value is
sorted in outgoing line of direction of arrow to be output.
By repeatingsortingthe packet containing the destination
port number as label value in each stage toward output direction,
the label values are sorted in ascending order and output from
the Batcher network. It should be noted that the output packet
of the Batcher network is concentrated in order of the label,
and not necessarily output to the objective output port.
Fig. 3 is an illustration showing a condition where packets
having destination portion numbers #0, #4, #6, #11, #15 are
sorted by the Batcher network. In Fig . 3 , while the packet having
the destination port number #0 is output from the objective
output port, other packets are not output from the objective
output port.
By providing Banyan netwdrk performing self-routing of
the packet in the later stage of the Batcher network, the packet
can be output to the objective output port. This construction
is called as Batcher-Banyan network and has been proposed in
CA 02541873 2001-09-05
- 12 -
"A Broadband Packet Switch for Integrated Transport" (J. Y.
Hui, IEEE J. Sel. Areas Comm., Vol. SAC-5, No. 8, pp 1264 -
1273, Oct. 1987).
In the Batcher-Banyan network, a routing network becomes
necessary in addition to the sorting network to cause increasing
of hardware amount. The switch core portion 3 of the packet
switching equipment according to the present invention is.
constructed with the sorting network and the equipment is
constructed with smaller hardware amount.
Figs. 4 and 5 are flowcharts showing a flow of arbitration
process executed in the arbiter portion 2 of Fig. 1. Arbitration
process is consisted of an output destination adjusting process
for providing output permissions for outputting to the output
ports 101-1 to 101-n for the input buffer portions 1-1 to 1-n
containing packets with avoiding overlapping, and vacant port
adjusting process for assigning idle output ports not occupied
by any input buffer portion 1-1 to 1-n to idle input buffer
portions not obtaining output permission.
As shown in Fig. 4, by executing the output destination
adjusting process at first (step A2 of Fig. 4), the output
permissions for outputting to the output ports 101-1 to 101-n
are given for the input buffer potions 1-1 to 1-n having packets
to be output, and then the vacant port adjusting process is
executed ( step A3 of Fig. 4 ) for assigning the idle output ports
to the idle input buffer portions.
CA 02541873 2001-09-05
- 13 -
On the other hand, as shown in Fig . 5 , the output destination
adjustingprocess (step B2 of Fig. 2 ) and the vacant portadjusting
process (step B3 of Fig. 5) are executed in parallel with
exchanging information with each other.
In this case, both of output destination adjusting process
and the vacant port adjusting process are simply required to
be completed until the packets are output from the input buffer
portions 1-1 to 1-n. Manner of combination of the output
destination adjusting process and the vacant port adjusting
process does not limit the present invention, and various
modificationsassociating with this should beencompassedwithin
a scope of the present invention.
Fig. 6 is an illustration showing one example of a packet
format in the equipment output from the input buffer portions
1-1 ~~1-not Fig. 1. In Fig. 6, a packet format 300 in the equipment
is consisted of a BSY portion, an address portion and a payload
portion. The BSY portion is an identifier indicating whether
the packet constructed with the shown format is valid or not,
in which a null packet is indicated by "0" and a valid packet
is indicated by "1".
The externally input packet is stored in the payload
portion in the packet input portion 12, and the BSY portion
is set to "1" . In the input buffer portions 1-1 to 1-n which
obtain the output permission by the output destination adjusting
process, the packet having "1" in the BSY portion is taken out
CA 02541873 2001-09-05
- 14 -
from the logic queues 11-1 to 11-n for outputting by setting
the destination output port number in the address portion as
label, at the packet output portion 13.
When the output permission is obtained by the vacant port
adjusting process, the packet output portion 13 sets "0" in
the BSY portion and the assigned vacant port number in the address
portion as label to generate a dummy packet for outputting without
taking out the packet from the logic queues 11-1 to 11-n.
The filtering portions 4-1 to 4-n arranged per output
ports 101-1 to 101-n make reference to the BSY portion of the
packet format to pass the packet of BSY = "1" and abandon the
packet of BSY = "0" . This is for preventing the null dummy packet
generated in the packet switching equipment from being output
externally from the equipment.
Fig. 7 is an illustration showing a packet switching
operation in one embodiment of the packet switching equipment
according to the present invention. Here, as input and output
port number/input buffer number, 0, 1, 2, 3 are assigned.
As initial condition, the input buffer #0 has the packet
addressed to the output port #2, and the input buffer #1 has
the packets addressed to the output ports #0, #1, #2 and #3.
The input buffer #2 has packets addressed to output ports #0
and #2. The input buffer #3 has the packet addressed to the
output port #2 . It should be noted that, in the shown embodiment,
discussion will be given for packet switching operation on the
CA 02541873 2001-09-05
- 15 -
basis of the arbitration process shown in Fig. 4. It should
be noted that, even with the arbitration process shown in Fig.
5, packet switching can be performed similarly to the packet
switching operation shown in Fig. 4.
In Fig. 7, the output destination adjusting process of
the arbiter portion 2 provides the output permission for
outputting to the output port #2 for the input buffer #0, and
the output permission for outputting to the output port #0 for
the input buffer #1. Method for assigning the output permission
is not limited to the shown method but can be any applicable
methods. At this time, the idle output ports are the output
ports #1 and #3, and the input buffers #2 and #3 do not have
a packet which can be output to the idle output ports and thus
are idle input buffer portions.
Fig. 8 is an illustration showing a condition after
execution of a vacant port arbitration process in one embodiment
of the packet switching equipment according to the present
invention. In Fig. 8, the vacant port adjusting process assigns
the idle output ports #1 and #3 to the idle input buffers #2
and #3, respectively.
Here, method for assigning the output permission is not
limited to the shown method but fan be any applicable methods .
For example, it is possible to assign vacant output ports sorted
in ascending order, the input buffer number in ascending order
may be assigned.
CA 02541873 2001-09-05
- 16 -
Fig. 9 is .an illustration showing a condition of output
destination arbitration process after execution of a vacant
port arbitration process in one embodiment of the packet
switching equipment according to the present invention. In Fig.
9 , the input buf f er portions which obtained the output permission
through the output destination adjusting process output the
packets addressed to the corresponding output ports.
The input buffer portions assigned the vacant ports
through the vacant port adjusting process output the dummy
packets which are set "0" in the BSY portions and assigned vacant
port number in the address portions.
Fig. l0 is an illustration for explaining operation of
the switch core portion 3 and a filtering portions 4-1 to 4-4
of Fig . 1. In Fig . 10 , the sorting network as the switch core
portion 3 performs sorting and concentration on the basis of
the label values set in the address portions of the packet output
from the input buffer portion 1-1 to 1-4. The shown operation
is easily realized by applying the Batcher network as the sorting
network.
Since packets for all output ports are present
irrespective of valid packet and dummy packet, the packets can
be output to the objective output ports by the sorting network.
On the other hand, in the filtering portion 4-1 to 4-4 receiving
the packet, the packet having BSY = "0" is abandoned and the
packet having BSY = "1" is passed. At this time, the packet
CA 02541873 2001-09-05
- 17 -
body from the payload portion of the packet format is taken
out.
As set forth above, by employing the sorting network
autonomously sorting and concentrating the packets on the basis
of the labels applied to the input packets, such as Batcher
network, in the switch core portion 3, by executing the output
destination adjusting process giving output permission for
outputting to the output ports 101-1 to 101-n for the input
buffer portions 1-1 to 1-n with avoiding overlapping, and the
vacant port adjusting process assigning the idle output ports
not occupied by the input buffer portions 1-1 to 1-n for_the
idle input buffer portion not obtaining the output permission,
by outputting the packets to the output ports 101-1 to 101-n
assigned for the input buffer portions 1-1 to 1-n through the
output destination adjusting process, and by generating and
outputting the dummy packets addressed to the output ports 101-1
to 101-n by the input buffer portions, to which the output ports
101-1 to 101-n are assigned, through the vacant port adjusting
process, the switch core portion 3 is permitted to operate
independent of content of decision of the arbiter portion 2.
Thus, the packet switching equipment with quite simple
construction which does not requite complicate control structure
which establishes synchronization over the entire equipment,
can be constructed.
Although the present invention has been illustrated and
CA 02541873 2001-09-05
- 18 -
described with respect to exemplary embodiment thereof, it
should be understood by those skilled in the art that the foregoing
and various other changes, omission and additions may be made
therein and thereto, without departing from the spirit and scope
of the present invention. Therefore, the present invention
should not be understood as limited to the specific embodiment
set out above but to include all possible embodiments which
can be embodiedwithin a scope encompassed and equivalent thereof
with respect to the feature set out in the appended claims.
In the present invention, since the sorting network for
autonomously sorting and concentrating the packets on the basis
of the label applied to the packet, is employed in the switch
core portion 3, the switch core portion 3 only performs
autonomously sorting and concentrating with reference to only
label of the input packet to permit operation independent of
the content of decision made by the arbiter portion 2 . Therefore,
simple control of the packet switching equipment which does
not require complicate control structure which establishes
synchronization over the entire equipment, can be constructed.
On the other hand, in the present invention, by executing
the output destination adjusting process for providing output
permission for outputting to trie output ports 101-1 to 101-n
for the input buffer portions 1-1 to 1-nwith avoiding overlapping
and the vacant port adjusting process for assigning idle output
port not occupied by any input buffer portion 1-1 to 1-n for
CA 02541873 2001-09-05
- 19 -
the idle input buffer portion not obtaining the output permission,
by outputting packets to addressed output ports 101-1 to 101-n
by the input buffer portions 1-1 to 1-n assigned the output
ports 101-1 to 101-n by the output destination adjusting process,
and by generating and outputting the dummy packet addressed
to the output ports 101-1 to 101-n by the input buffer portions
1-1 to 1-n assigned the output ports 101-1 to 101-n by the vacant
port adjusting process, the packet can be accurately switched
to the objective output port in the sorting network sorting
and concentrating the packets in order of the labels.
Furthermore, by providing the information indicative of
valid packet or dummy packet for the packet, and arranging the
packet filtering portions 4-1 to 4-n for passing only valid
packets and abandoning the null dummy packets, corresponding
to the output ports 101-1 to 101-n of the packet switching
equipment, the null dummy packet will never be output externally
from the packet switch equipment to restrict wasting of the
network resource.
As set forth above, with the present invention, in the
packet switching equipment performing switching of packets
between the input ports and the output ports , the packets arriving
to the input port are output with labels indicative of the
destination port number added in the input buffer portion, the
packets are switched in the switch core portion on the basis
of the labels added in the input buffer portion, the input buffer
CA 02541873 2001-09-05
- 20 -
portions to provide output permission for outputting to the
output ports are adjusted by the arbiter portion, and the sorting
network for autonomously sorting and concentrating the packet
on the basis of the labels provided for the packets is applied
to the switch core portion. Therefore, the operation of the
switch core portion can be independent of content of decision
of the arbiter portion to construct the overall equipment with
simple control structure.
