Self-routing multistage switching network for fast packet switching system

• US 4,899,334 A
• Filed: 10/11/1988
• Issued: 02/06/1990
• Est. Priority Date: 10/19/1987
• Status: Expired due to Term

• Current Assignee: OKI Electric Industry Company Limited
• Original Assignee: OKI Electric Industry Company Limited
• Inventors: Shimizu, Shogo
• Primary Examiner(s): NOT, DEFINED
• Assistant Examiner(s): Marcelo, Melvin
• Application Number:
  US07/256,405
• Time in Patent Office: 483 Days
• Field of Search: 370/60, 370/94, 370/14, 370/15, 370/61
• US Class Current: 370/411
• CPC Class Codes: H04L 49/1507 Distribute and route fabrics, e.g. sorting-routing or Batcher-Banyan
• CPC Class Codes: H04L 49/3009 Header conversion, routing tables or routing tags
• CPC Class Codes: H04L 49/3018 Input queuing
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane

Abstract

A self-routing multistage switching network for a fast packet switching system suitable for multimedia communication. The self-routing multistage switching network has packet buffer means for storing packets, provided only in an input stage and respectively connected to input ports, and switching networks having no packet storing function and provided after the packet buffer means. The self-routing multistage switching network detects beforehand while packets are transmitted therethrough whether or not the packets are transmitted therethrough instead of being discarded, reports information for identifying the packets which are transmitted instead of being discarded backward to the packet buffer means through transmission routes through which the packets have been transmitted, and deletes the packets stored in the packet buffer means and corresponding to the packets which are allowed to be transmitted through the self-routing multistage switching network after sending out the same packets. The self-routing multistage switching network is capable of transmitting a plurality of packets for a piece of comunication without entailing outrun between the packets.

Claims

1. A self-routing multistage switching network for a fast packet switching system for transmitting a plurality of packets applied to a plurality of input ports to a plurality of output ports, comprising;

(a) packet buffer means capable of storing packets, provided only in an input stage, and respectively connected to the input ports;

(b) self-routing multistage switching means, including a switching network connected to the output terminals of the packet buffer means, for routing a packet over a variable transmission route, having no packet storing function, and including a plurality of unit switches capable of self-routing control;

(c) detecting means for detecting beforehand whether or not the packets applied to the self-routing multistage switching means are transmitted through the selfrouting multistage switching means without being discarded;

(d) reporting means for reporting identification information which identifies a packet which can be transmitted instead of being discarded, backward to the packet buffer means through the same transmission route of the self-routing multistage switching means through which the packet has been transmitted; and

(e) control means for deleting a packet from a storage means of the packet buffer means after completion of sending out of a packet, if the packet is identified by the identification information given to the packet buffer means by the reporting means as a packet which can be transmitted instead of being discarded

2. A self-routing multistage switching network for a fast packet switching system for transmitting a plurality of packets applied to a plurality of input ports forward to a plurality of output ports, comprising:

(a) packet buffer means capable of storing packets, provided only in an input stage, and respectively connected to the input ports;

(b) first sorting network means connected to output terminals of the packet buffer means, including a plurality of unit switches capable of selfrouting control, for routing a packet over a variable transmission route, and having means for reporting reporting backward to the packet buffer means, along a same transmission route through the unit switches that a packet has been transmitted identification information identifying the packet;

(c) discarding network means connected to output terminals of the first sorting network means, for selecting only one packet among a plurality of packets contending for a same output port and discarding the rest of the plurality of packets;

(d) second sorting network means having input terminals connected to output terminals of the discarding network means, and comprising a plurality of unit switches with a comparing function;

(e) routing network means having input terminals connected to the second sorting network means, and comprising a plurality of unit switches with a selecting function; and

(f) control means for deleting a packet identified by identification information given to the packet buffer means by the reporting means, from a storage means of the packet buffer means after completion of sending out the packet from the packet buffer means.

3. A self-routing multistage switching network for a fast packet switching system for transmitting a plurality of packets applied to a plurality of input ports to a plurality of target output ports, comprising:

(a) packet buffer means capable of storing packets, provided only in an input stage, and respectively connected to the input ports;

(b) preliminary network means connected to the output terminals of the packet buffer means, and having a detecting function to detect whether or not preliminary packets set out from the packet buffer means can be transmitted through the preliminary network means instead of being discarded and a function to report the preliminary packet which is transmitted instead of being discarded backward to the packet buffer means through the same transmission route through which the same packet has been transmitted;

(c) virtual network means having input terminals connected to output terminals of the packet buffer means, and capable of switching operation for transmitting the virtual packets sent out from the packet buffer means to the respective target output ports; and

(d) control means for producing preliminary packets from packets stored in the packet buffer means, sending out the preliminary packets to the preliminary network, producing virtual packets on the basis of the results of selective operation of the preliminary network, and sending out the virtual packets to the virtual network.

4. A self-routing multistage switching network according to claim 3, wherein the preliminary network means comprises:

first sorting network means comprising a plurality of unit switches with comparing and reporting functions and provided in the first stage; and

discarding network means provided in the second stage, for selecting only one preliminary packet among a plurality of preliminary packets contending for the same output port as a winner, and for reporting the preliminary packet selected as a winner through the first sorting network means to the packet buffer means;

and the virtual network means comprises;

a second sorting network means comprising a plurality of unit switches with a comparing function and provided in the first stage; and

a routing means comprising a plurality of unit switches with an output selecting function, provided in the second stage, and having output terminals connected to the plurality of output ports.