Non-blocking multi-cast switching system
AssigneeWashington University
InventorJonathan S. Turner
Life of this patent
Estimating the term…
Abstract
A multi-cast switching system comprised of a pair of high speed data networks, each of said data networks being either a Benes network, a Clos network, or a Cantor network, and configured to provide point-to-point switching only in the first network and multi-cast switching in the second network, may be non-blocking for adding a multi-cast connection and re-arrangeably non-blocking for augmenting an existing multi-cast connection using the algorithm which essentially consists of identifying the most lightly loaded middle stage switch, connecting the input to the middle stage switch, and connecting the outputs to the middle stage switch. A minimal speed advantage for each type of network is presented and thereby reduces the cost of each network in order to achieve non-blocking operation.
Claims14
A multi-cast high speed data packet switching fabric, said fabric comprising a first network having means for handling point-to-point traffic and a second network connected back-to-back with said first network, said second network having means for handling multi-cast traffic, said first and second networks each being one of either a Benes network with a speed advantage of approximately 2k-1-2(k-2)/d, a Clos network with a speed advantage of approximately 1+2d/m, or a Cantor network with a speed advantage of approximately 1+2(k+1)/m-2(k-2)/dm, and said switching fabric having means for adding a new multi-cast connection through both networks without blocking.
A multi-cast high speed data packet switching fabric, said fabric being comprised of a pair of three-stage Benes networks connected back-to-back, the first of said networks having means for handling point-to-point switching and the second of said networks having means for handling multi-cast traffic, each of said Benes networks having a speed advantage of approximately 2k-1-2 (k-2)/d, said switching fabric having means for adding a new multi-cast connection through both networks without blocking.
In a multi-cast high speed data packet switching fabric, said fabric being comprised of a pair of three-stage Benes networks connected back-to-back, the first of said networks having means for handling point-to-point switching and the second of said networks having means for handling multi-cast traffic, each of said Benes networks having a speed advantage of approximately 2k-1-2 (k-2)/d, said switching fabric thereby having five stages, the improvement comprising a method for augmenting an existing data packet connection to an additional output (y) in a fifth stage switch, said method comprising the steps of:
- a. determining if a branch of the existing data packet connection terminates in the same fifth stage switch containing Y, if so, then
- b. adding y internally in said fifth stage switch to said connection, if not then
- c. connecting y through an available path from y to a fourth stage switch through which the connection passes, if no such fourth-stage switch then
- d. connecting y through an available path from y to a third stage switch through which the connection passes, if no such third stage switch then
- e. re-routing the augmented multi-cast connection through all five stages.
In a multi-cast high speed data packet switching fabric, said fabric being comprised of a pair of three-stage Benes networks connected back-to-back, the first of said networks having means for handling point-to-point switching and the second of said networks having means for handling multi-cast traffic, each of said Benes networks having a speed advantage of approximately 2k-1-2 (k-2)/d, the switching fabric thereby having five stages, the improvement comprising a method for adding a new multi-cast connection through both networks without blocking, the method comprising the steps of:
- a. identifying the most lightly loaded third stage switch (Z), adding a branch from the input of said new multi-cast connection to Z, and
- b. adding a branch from Z to each of the outputs of said multi-cast connection.
In a multi-cast high speed data packet switching fabric, said fabric being comprised of a pair of five-stage Benes networks connected back-to-back, the first of said networks having means for handling point-to-point switching and the second of said networks having means for handling multi-cast traffic, each of said Benes networks having a speed advantage of approximately five, the switching fabric thereby having nine stages, the improvement comprising a method for adding a new multi-cast connection through both networks without blocking, the method comprising the steps of:
- a. identifying the most lightly loaded third stage switch (Z), adding a branch from the input of said new multi-cast connection to Z, and
- b. adding a branch from Z to each of the outputs of said multi-cast connection.
Dependencies are inferred from the claim text.