Distributed voice-data switching on multi-stage interconnection networks

• US 4,679,190 A
• Filed: 04/28/1986
• Issued: 07/07/1987
• Est. Priority Date: 04/28/1986
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Kumar, Manoj, Dias, Daniel M., Maruyama, Kiyoshi, Lien, Yeong-Chang L.
• Primary Examiner(s): Olms, Douglas W.
• Application Number:
  US06/856,321
• Time in Patent Office: 435 Days
• Field of Search: 370/60, 370/94, 340/825.5, 340/825.51, 340/825.79, 340/825.8
• US Class Current: 370/355
• CPC Class Codes: H04L 49/101 using crossbar or matrix
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane
• CPC Class Codes: H04Q 11/04 for time-division multiplexing H04Q11/0001 takes precedence

Abstract

A method of switching synchronous and asynchronous data packets through a multi-stage interconnection network (MIN), so as to insure that packets with the highest assignable priority level will never be blocked at any stage of the network. More specifically, this invention relates to a method of switching voice and data packets over the MIN wherein each of the address bits in each packet determine the connection to be established at each particular stage in the network and wherein each packet has therein a priority level. In each time slot of a frame, the priority level of the packets stored in a particular originating adapter are compared and the packet with the highest priority level in each adapter is forwarded through the MIN and routed through the MIN as described above. Also, at each subswitch at each stage of the MIN, if two or more packets request the same subswitch output, only the packet with the higher priority is forwarded to the subswitch output. A packet will be assigned the highest priority only if a corresponding packet for a given circuit connection with second highest priority level was successfully transmitted through the MIN.

Claims

1. A method of switching packets through a multistage interconnection switching network, comprising the steps of:

(a) assigning a packet, for a circuit connection, the highest assignable priority level only after a corresponding packet, for the circuit connection, with the second highest assignable priority level, was successfully transmitted from a corresponding input of a subswitch of the first stage of the switching network to a corresponding output of a subswitch of the last stage of the switching network;

(b) transmitting each packet at the input of each subswitch of the first stage of the switching network to an output of the same corresponding subswitch, which output is indicated by a respective address bit in the respective packet, a given packet being transmitted as provided for in this step of this claim, only if no other packet, at the same corresponding subswitch, requests the same output of the subswitch;

(c) transmitting the packet with the highest priority level of all the packets at the inputs of each subswitch of the first stage of the switching network to the output of the same corresponding subswitch, which output is indicated by the respective address bit in the respective packet being transmitted, a given packet being transmitted as provided for in this step of this claim only if other packets at the same corresponding subswitch with different priority levels request the same output of the corresponding subswitch;

(d) transmitting, for each subswitch of the first stage of the switching network, any one, of a number of packets transmitted to the inputs of the respective subswitch of the first stage of the switching network, to the output of the respective subswitch indicated by a respective address bit in the one packet, if the number of packets are of the same priority level and request the same output of the respective subswitch; and

(e) repeating steps b, c, and d for packets at inputs of subswitches of subsequent stages of the switching network until the packets reach respective outputs of subswitches of the last stage of the network, the outputs of the respective subswitches of any of the subsequent stages being requested by respective subsequent address bits in the respective packets so that packets are transmitted from the inputs of the subswitches of the first stage of the multistage interconnection network to the respective outputs of the last stage of the interconnection network.

2. A method as recited in claim 1, wherein only synchronous data packets are assigned the highest assignable priority level.

3. A method as recited in claim 1, further comprising the steps of:

(a) storing a packet in each originating adapter having a request at its input to send a packet which has therein a priority level and an address corresponding to a terminating adapter, each originating adapter being connected to an input of a subswitch of the first stage of the switching network;

(b) comparing within a given time slot the priority levels of a number of packets stored in each originating adapter; and

(c) transmitting, from each adapter, within the given time slot, the packet with the highest priority level in each originating adapter to the output of each respective adapter, each output being connected to a particular subswitch input of the first stage of the switching network.

4. A method as recited in claim 3, further comprising the steps of:

removing from the storage of each of the originating adapters, the packets that were successfully transmitted from the respective originating adapter to the respective output of a subswitch of the last stage of the switching network.

5. A method as recited in claim 1, wherein the multistage interconnection switching network is a digital shuffle exchange network.

6. A method as recited in claim 1, wherein there are four or more priority levels which a packet can have.

7. A method as recited in claim 1, wherein the second highest assignable priority level is assigned to a packet which has a request to set up a circuit connection for sending synchronous data.

8. A method as recited in claim 7, wherein the synchronous data is voice data.

9. A method of integrally switching packets of synchronous and asynchronous data from a plurality of inputs of originating adapters to a plurality of outputs of terminating adapters over a multistage interconnection switching network with distributed control, the paths of the network from the originating adapters to the terminating adapters changing at most once in every time slot, with a number of the paths being repeated in corresponding time slots of subsequent frames, the method comprising the steps of:

(a) assigning a packet, for a circuit connection, the highest assignable priority level only after a packet, for the circuit connection, with the second highest assignable priority level was successfully transmitted from a corresponding originating adapter to a corresponding terminating adapter, the circuit connection being established in each time slot of corresponding time slots of a number of frames;

(b) storing a packet in each of the originating adapters having a request at its input to send a packet which has therein a priority level and an address corresponding to one of the terminating adapters, the priority level being any one of a plurality of levels;

(c) comparing within a given time slot the priority levels of a number of packets stored in each of the originating adapters;

(d) transmitting from each adapter within the given time slot, the packet with the highest priority level in each of the originating adapters to the output of each adapter, each output of each adapter being connected to a particular subswitch input of the first stage of the switching network;

(e) transmitting each packet, transmitted to a respective subswitch input of the first stage of the switching network, to a respective subswitch output indicated by the first address bit in each respective packet, a given packet being transmitted as provided for in this step of this claim only if other packets at the same corresponding subswitch with different priority levels request the same output of the corresponding subswitch;

(f) transmitting, for each subswitch, the packet, with the highest priority level of the packets transmitted to the inputs of the respective subswitch of the first stage of the switching network, to the output of the respective subswitch indicated by the first address bit in that packet, a given packet being transmitted as provided for in this step of this claim only if other packets at the same corresponding subswitch with different priority levels request the same output of the corresponding subswitch;

(g) transmitting, for each subswitch of the first stage of the switching network any one, of a number of packets transmitted to the inputs of the respective subswitch of the first stage of the switching network, to the output of the respective subswitch indicated by the first address bit in the one packet, if the number of packets are of the same priority level and request the same output of the respective subswitch;

(h) repeating steps e, f, and g for packets at inputs of subswitches of subsequent stages of the switching network until the packets reach respective outputs of subswitches of the last stage of the network, which outputs, of the last stage, are connected to the inputs of the terminating adapters, the outputs of the respective subswitches of any of the subsequent stages being requested by respective subsequent address bits in the respective packets so that a packet is transmitted from the originating adapter to corresponding terminating adapters within the given time slot of step (c); and

(i) removing from the storage of each of the originating adapters the packets that were acknowledged to have been successfully transmitted to a respective terminating adapter.

10. A method of integrally switching packets of synchronous and asynchronous data from a plurality of inputs or originating adapters to a plurality of outputs of terminating adapters over a digital shuffle exchange network, comprising the steps of:

(a) storing an established call request packet, with a highest priority level and an address corresponding to one of the terminating adapters, in each of the originating adapters having a request at its input to continue a call that has been set up;

(b) storing a call set up request packet in a pending call set up request queue in each of the originating adapters having a request at its input to establish a new call, the call set up request packet having a second priority level lower than that of the highest priority level, and having an address corresponding to one of the terminating adapters;

(c) storing an asynchronous data request packet with an asynchronous data request in a data buffer in each of the originating adapters having a request at its input to send asynchronous data, the asynchronous data packet having a third priority level lower than that of the second priority level and having an address corresponding to one of the terminating adapters;

(d) comparing within a given time slot, the priority levels of a number of packets stored in each of the originating adapters, with one of the number being at the head of the pending call set up request queue if there are such requests in the queue, another of the number being from the data buffer if there are packets in the buffer, and a third of the number being an established call request packet if there is an established call request packet to be transmitted in the given time slot;

(e) transmitting from each adapter, within the given time slot, the packet of step (d) with the highest priority in each of the originating adapters, the respective packet being transmitted to the input of a subswitch of the first stage of the shuffle exchange network, a respective call set up request packet being transmitted only if the slot at the time time for transmission of the call set up request packet has not been allocated for accepting only call set-up request packets;

(f) transmitting each packet at the input of each subswitch of the first stage of the switching network to an output of the same corresponding subswitch, which output is indicated by a respective address bit in the respective packet, a given packet being transmitted as provided for in this step of this claim only if no other packet, at the same corresponding subswitch, requests the same output of the subswitch;

(g) transmitting the packet with the highest priority level of all the packets at the inputs of each subswitch of the first stage of the switching network to the output of the same corresponding subswitch, which output is indicated by the respective address bit in the respective packet being transmitted, a given packet being transmitted as provided for in this step of this claim only if other packets at the same corresponding subswitch with different priority levels request the same output of the corresponding subswitch;

(h) transmitting, for each subswitch of the first stage of the switching network, any one, of a number of packets transmitted to the inputs of the respective subswitch of the first stage of the switching network, to the output of the respective subswitch indicated by a respective address bit in the one packet, if the number of packets are of the same priority level and request the same output of the respective subswitch; and

(i) repeating steps b, c, and d for packets at inputs of subswitches of subsequent stages of the switching network until the packets reach respective outputs of subswitches of the last stage of the network, the outputs of the respective subswitches of any of the subsequent stages being requested by respective subsequent address bits in the respective packets so that packets are transmitted from the inputs of the subswitches of the first stage of the multistage interconnection network to the respective outputs of the last stage of the interconnection network;

(j) transmitting a positive acknowledgement to each of the originating adapters from which a packet was successfully transmitted to a respective adapter of the terminating adapters as in step (i); and

(k) removing, from the storage of each of the originating adapters, the packets that were acknowledged to have been successfully transmitted as in step (j).

11. A method as received in claim 10, wherein the percentage, of the the total slot positions of each frame that are allocated to established call request packets, is bounded by a fixed number.

12. A method as recited in claim 10, wherein the granularity of the network is a packet.

13. A method as recited in claim 10, wherein the individual sub-switches of the shuffle exchange network are opened or closed during a period of one time slot to provide conductive path from each of the originating adapters to respective terminating adapters corresponding to the address in the packets to be transmitted in the time slot.