Switching element and packet switch

• US 6,754,205 B1
• Filed: 03/03/2000
• Issued: 06/22/2004
• Est. Priority Date: 03/04/1999
• Status: Expired due to Fees

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Sakaue, Kenji
• Primary Examiner(s): Vanderpuye, Kenneth
• Application Number:
  US09/518,236
• Time in Patent Office: 1,572 Days
• Field of Search: 370/357, 370/389, 370/395.1, 370/388, 370/360, 370/412-414
• US Class Current: 370/360
• CPC Class Codes: H04L 2012/5665 Interaction of ATM with other protocols
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/253 using establishment or release of connections between ports
• CPC Class Codes: H04L 49/3072 Packet splitting

Abstract

Input ports IP0 through IP8 transmit request packets by different two kinds of routing patterns A and B before actual cells are transmitted. The number of request packets having reached target output ports OP0 through OP8 is compared by a request packet comparing/measuring circuit CHP. The input ports IP0 through IP8 transmit actual cells by a routing pattern of the routing patterns A and B, by which the number of the request packets having reached the target output ports is larger. Thus, the throughput of a packet switch is improved.

Claims

1. A switching element for use in a packet switch, comprising:

a crossbar switch for inputting packets from a plurality of packet input paths and for outputting said packets from one of a plurality of packet output paths in accordance with routing pattern information included in said packets; and

an arbiter for inputting request packets from a plurality of request input paths and for outputting said request packets from one of a plurality of request output paths in accordance with routing pattern information included in said request packets, said arbiter selecting and outputting one of said request packets when said request packets are to collide with each other to be outputted to the same request output path of said plurality of request output paths, wherein said arbiter returns a negative acknowledge signal to a transmission source or sources, from which the other request packet or request packets of said request packets being not selected have been transmitted, when said request packets collide with each other.

2. A packet switch comprising:

a plurality of input ports for accumulating and sequentially transmitting inputted packets and for transmitting first request packets by a first routing pattern and second request packets by a second routing pattern;

a switching network for sequentially outputting said packets and said first and second request packets, which have been inputted from said plurality of input ports, to a target output port via a plurality of switching elements arranged in the form of lattice, each of said switching elements including;

a crossbar switch for inputting said packets from a plurality of packet input paths and for outputting said packets from one of a plurality of packet output paths in accordance with routing pattern information included in said packets;

a first arbiter for inputting said first request packets from a plurality of first input paths and for outputting said first request packets from one of a plurality of first output paths in accordance with routing pattern information included in said first request packets, said first arbiter selecting and outputting one of said first request packets when said first request packets are to collide with each other to be outputted to the same first output path of said plurality of first output paths; and

a second arbiter for inputting said second request packets from a plurality of second input paths and for outputting said second request packets from one of a plurality of second output paths in accordance with routing pattern information included in said second request packets, said second arbiter selecting and outputting one of said second request packets when said second request packets are to collide with each other to be outputted to the same second output path of said plurality of second output paths; and

a result output circuit for outputting a comparison result indicative signal for causing said input ports to transmit packets by one of said first and second routing patterns in next cycle, by which more request packets have reached said output port, on the basis of the result of transmission of said first and second request packets.

3. A packet switch as set forth in claim 2, wherein said result output circuit outputs said comparative result indicative signal for causing said input ports to transmit said packets by a predetermined first or second routing pattern when the same number of said first and second request packets have reached said output port.

4. A packet switch as set forth in claim 3, wherein said first arbiter returns a first negative acknowledge signal to a transmission source or sources having transmitted said first request packet being not selected, when said plurality of first request packets collide with each other;

and

said second arbiter return a second negative acknowledge signal to a transmission source or sources having transmitted said second request packet being not selected, when said plurality of second request packets collide with each other.

5. A packet switch as set forth in claim 4, wherein in case of transmitting said packets by said first routing pattern, said input ports other than said input port having received said first negative acknowledge signal in the last cycle transmits said packets, and

in case of transmitting said packets by said second routing pattern, said input port other than said input port having received said second negative acknowledge signal in the last cycle transmits said packets.

6. A packet switch as set forth in claim 5, wherein said result output circuit counts the number of said first and second request packets having reached said output port,

outputs said comparison result indicative signal for causing said input ports to transmit said packet by said first routing pattern in the next cycle when the number of said first request packets is larger than the number of said second request packets, and

outputs said comparison result indicative signal for causing said input ports to transmit said packet by said second routing pattern in the next cycle when the number of said second request packets is larger than the number of said first request packets.

7. A packet switch as set forth in claim 6, wherein said result output circuit comprises:

a subtracter for inputting the number of said first and second request packets having reached said output ports and for calculating a difference between said first request packets and said second request packets to output a differential signal; and

a register for inputting said differential signal to hold said differential signal for a predetermined period of time to output said comparative result indicative signal.

8. A packet switch as set forth in claim 6, wherein said result output circuit comprises:

a first parallel/serial converter for inputting a first identification signal, which indicates whether said first request packets have reached said output port, in parallel every said output port to serially convert said first identification signal to output a first serial signal;

a second parallel/serial converter for inputting a second identification signal, which indicates whether said second request packets have reached said output port, in parallel every said output port to serially convert said second identification signal to output a second serial signal;

a first accumulator for inputting said first serial signal and for calculating the number of said first request packets having reached said output ports on the basis of said first serial signal to output a first digital signal;

a second accumulator for inputting said second serial signal and for calculating the number of said second request packets having reached said output ports on the basis of said second serial signal to output a second digital signal; and

a comparator for inputting said first and second digital signals to digitally compare both to output said comparative result indicative signal.

9. A packet switch as set forth in claim 6, wherein said result output circuit comprises:

a first register for inputting a first bit map information indicative of the number of said first request packets having reached said output ports and for outputting first ON signals, the number of which is the same as the number of said first request packets having reached said output port, on the basis of said first bit map information;

a second register for inputting a second bit map information indicative of the number of said second request packets having reached said output ports and for outputting second ON signals, the number of which is the same as the number of said second request packets having reached said output port, on the basis of said second bit map information;

a first transistor group having first transistors, the number of which is the same as the number of said output ports, the number of said first transistors turned on being the same as the number of said first ON signal;

a second transistor group having second transistors, the number of which is the same as the number of said output ports, the number of said second transistors turned on being the same as the number of said second ON signal;

a first capacitor connected to said first transistor group, said first capacitor being more rapidly discharged as the increase of the number of said first transistors turned on;

a second capacitor connected to said second transistor group, said second capacitor being more rapidly discharged as the increase of the number of said second transistors turned on; and

a level comparator for sensing a difference between the discharge duration of said first capacitor and the discharge duration of said second capacitor, said level comparator outputting said comparative result indicative signal for transmitting said packets by said first routing pattern when the discharge duration of said first capacitor is shorter than the discharge duration of said second capacitor, and outputting said comparative result indicative signal for transmitting said cell by said second routing pattern when the discharge duration of said second capacitor is shorter than the discharge duration of said first capacitor.

10. A packet switch as set forth in claim 4, wherein said result output circuit counts the number of said first and second negative acknowledge signals returned to said input port,

outputs said comparative result indicative signal for causing said input ports to transmit said packet by said second routing pattern in the next cycle when the number of said first negative acknowledge signals is larger than the number of said second negative acknowledge signals, and

outputs said comparative result indicative signal for causing said input ports to transmit said packet by said first routing pattern in the next cycle when the number of said second negative acknowledge signals is larger than the number of said first negative acknowledge signals.

11. A packet switch as set forth in claim 10, wherein in case of transmitting said packets by said first routing pattern, said input ports other than said input port having received said first negative acknowledge signal in the last cycle transmits said packets, and

in case of said input ports transmits said packets by said second routing pattern, said input ports other than said input port having received said second negative acknowledge signal in the last cycle transmits said packets.

12. A packet switch comprising:

a plurality of input ports for accumulating and sequentially transmitting inputted packets, and for transmitting first request packets by a first routing pattern in the first half of a cycle before said packets are transmitted and for transmitting second request packets by a second routing pattern in the second half of said cycle;

a switching network for sequentially outputting said packets and said first and second request packets, which have been inputted from said plurality of input ports, to a target output port via a plurality of switching elements arranged in the form of lattice, each of said switching elements including;

a crossbar switch for inputting said packets from a plurality of packet input paths and for outputting said packets from one of a plurality of packet output paths in accordance with routing pattern information included In each of said packets; and

an arbiter for inputting said first and second request packets from a plurality of request input paths and for outputting said first and second request packets from one of a plurality of request output paths in accordance with routing pattern information included in said first and second request packets, said arbiter selecting and outputting one of said first request packets when one of said first request packets collide with another of said first request packets to be outputted to the same request output path, and said arbiter selecting and outputting one of said second request packets when one of said second request packets collide with another of said second request packets to be outputted to the same request output path; and

a result output circuit for outputting a comparison result indicative signal for causing said input ports to transmit packets by a routing pattern of said first and second routing patterns in next cycle, by which more request packets have reached said output port, on the basis of the result of transmission of said first and second request packets.

13. A packet switch as set forth in claim 12, wherein said result output circuit outputs said comparative result indicative signal for causing said input ports to transmit said packets by a predetermined first or second routing pattern when the same number of said first and second request packets have reached said output port.

14. A packet switch as set forth in claim 13, wherein said arbiter returns a first negative acknowledge signal to a transmission source or sources having transmitted said first request packet being not selected, when one of said first request packets collide with another of said first request packets, and returns a second negative acknowledge signal to a transmission source or sources having transmitted said second request packet being not selected, when one of said second request packets collide with another of said second request packets.

15. A packet switch as set forth in claim 14, wherein in case of transmitting packets by said first routing pattern, said input ports other than said output port having received said first negative acknowledge signal in the last cycle transmits said packets, and

in case of transmitting said packets by said second routing pattern, said input ports other than said output port having received said second negative acknowledge signal in the last cycle transmits said packets.

16. A packet switch comprising:

a plurality of input ports for accumulating and sequentially transmitting inputted packets;

a switching network for outputting said packets inputted from said plurality of input ports, to a target output port sequentially via a plurality of switching elements arranged in the form of lattice, each of said switching elements having a crossbar for selecting and outputting one of said packets when said packets collide with each other to be outputted to the same output path and for returning negative acknowledge signals to an input port, from which one of said packets being not selected has been transmitted; and

a switching signal output circuit for counting the number of said negative acknowledge signals returned to said input ports and for outputting a switching indicative signal for causing said input ports to switch a routing pattern when the counted number of said negative acknowledge signals exceeds a predetermined value.

17. A packet switch comprising:

a plurality of input ports for accumulating and sequentially transmitting inputted packets and for transmitting request packets by one routing pattern;

a switching network for sequentially outputting said packets and said request packets, which have been inputted from said plurality of input ports, to a target output port via a plurality of switching elements arranged in the form of lattice, each of said switching elements including;

a crossbar switch for inputting said packets from a plurality of packet input paths and for outputting said packets from one of a plurality of packet output paths in accordance with routing pattern information included in said packets; and

an arbiter for inputting said request packets from a plurality of request input paths and for outputting said request packets from one of a plurality of request output paths in accordance with routing pattern information included in said request packets, said arbiter selecting and outputting one of said request packets when one of said request packets collides with another of said request packets to be outputted to the same request output path of said request output paths, and said arbiter returning negative acknowledge signals to a transmission source or sources having transmitted said request packets being not selected; and

a switching signal output circuit for counting the number of said negative acknowledge signals returned to said input ports and for outputting a switching indicative signal for causing said input ports to transmit packets by a routing pattern different from said one routing pattern in next cycle.

18. A packet switch as set forth in claim 17, wherein said output ports have a first routing pattern and a second routing pattern different from said first routing pattern, as said routing pattern, and which alternately select one of said first and second routing patterns on the basis of input of said switching indicative signal.