Broadcast Network

The present invention is related to space-division broadcast switching networks which provide a one-to-many interconnection capability from their inputs to their outputs. More specifically, the present invention relates to broadcast modules that are capable of being linked together in hub structures. These structures can be used with switching components which unto themselves only provide a one-to-one connecting capability to form a new class of space-division broadcast switching networks.

A space-division switching network is a communication system in which connections from a set of input ports to a set of output ports are established by physically linking paths together by means of switching elements. The term in space-division is used because communication paths are implemented by linking together a dedicated connection in space as opposed to sharing a connection in time.

In most space-division switching networks, the input ports and output ports are linked together in what can generically be referred to as a one-to-one transmit/receive arrangement. These one-to-one transmit/receive arrangements are often referred to as permutation connections. Each input port is directly and permanently attached, by means of an appropriate interfacing mechanism, to a transmit port of a transmit station. The transmit station serves as a source of, for example, voice/data information which is fed into the switching network through the input port to which it is interfaced. Each output port is directly and permanently attached, by means of an appropriate interfacing mechanism, to a receive port of a receive station. The receive station serves as a sink or destination of the voice/data information being transmitted through the switching network over the connecting path that has been implemented. In a permutation connection, the communication requirement between the transmit stations and the receive stations is such that, at any time, each input port must be connected to at most one output port. Networks providing such one-to-one connectivity are usually referred to as permutation switching networks.

There exists a class of communication requirements between the transmit stations and the receive stations where the connectivity required of the switching network is much more demanding than one-to-one port pairing in that an input port interfaced to a transmit station must be connected at times to more than one output port (receive station) in a one-to-many fashion. This one to many communication mode is referred to as broadcasting. Generally, in a broadcast connection from a transmit station to receive stations, it is only of interest to connect an output port (receive station) at any given time to at most one input port (transmit station). A broadcast switching network must be capable of simultaneously providing multiple broadcast connections from the input ports to the output ports with the restriction that no output port can ever be connected at a given time to more than one input port.

There have been a variety of techniques developed with respect to switching networks. U.S. Pat. No. 4,402,008 to Teraslinna discloses a wide band switching architecture. The wide band switching architecture allows wide band signals to be communicated through a wide band switching network with minimal crosstalk between the wide band signals. The wide band switching network is comprised of stages, each of which has a plurality of switching input and output arrays. Each input array has one input terminal and each output array has one output terminal. Each array is one integrated circuit, and crosstalk is reduced by allowing only one wide band signal to be present in each integrated circuit at any one time and by grounding all unused outputs and inputs in the arrays.

U.S. Pat. No. 4,696,000 to Payne discloses a nonblocking self-routing nodes. The broadcast nodes are responsive to the transmissions of address information from an input port to create a plurality of paths through the switching network to communicate on this plurality of paths the address information to the routing states. Each of the routing switch nodes is responsive to receipt of address information to select one of the paths to an address designated output port.

U.S. Pat. No. 4,651,318 to Luderer discloses a multistage packet switching network comprising a plurality of pack switch nodes for communicating broadcast and non-broadcast packets. Each node is responsive to receipt of one of the packets. If a broadcast packet has been received, the switch node transmits this packet to the next sequential stage on all output links interconnecting the switch nodes to the next sequential stage. If the packet is of a non-broadcast type, the switch node decodes the state identification field therein to determine which of the sets of the routing information is to be used for routing that non-broadcast packet to the next sequential stage.

U.S. Pat. No. 4,566,008 to Richards discloses a two-stage, rearrangeable multiconnection switching network for connecting N1 input channels to N2 output channels. The network comprises a number of first stage switches and a second stage switch. The second stage switch has N2 outlets, each connected to one of the N2 output channels. A connection arrangement connects each of the first stage switch ringlets to an associated predetermined input channel such that for any group N2 of input channels, there is a group of N2 of the first stage switches, each having one inlet connection to a different on that group N2 of the input channels. This patent to Richards also discloses that the network is extendable by adding second stage switches and connecting each additional second stage switch to each first stage switch. In larger networks, the first and second stage switches are themselves replaceable by two stage networks in accordance with the invention.

The problem that exists in realizing broadcast connections with a space-division switching network is that the network must have a fan-out capability. When fan-out is used to implement a broadcast connection from a single input port to multiple output ports, the resulting connecting path corresponds to a tree of connecting paths through the network where the input port is the root of the tree and the output ports are leaves of the tree. To establish a tree of connecting paths through a space-division switching network using fan-out is significantly more complex than establishing a set of one-to-one connecting paths. See G. M. Masson, "Upper bounds on fan-out in connection with networks,: IEEE Transactions on Circuit Theory", Vol. CT-20, pp. 222-230; 1973. Modifying the state of a space-division switching network employing fan-out to provide a new connection by rearranging trees of connecting paths is prohibitive.

Accordingly, to satisfy a broadcast connection, a space-division network must have connecting capabilities far in excess of that required for the one-to-one or permutation type of connection. To see this, note that a permutation network with N inputs must be able to realize N! assignments of inputs to outputs while a broadcast network with N inputs must be able to realize N.sup.N assignments. Because the switching modules comprising a broadcast network must have fan-out capabilities relative to their inputs and outputs, much of the well-established theory for the design and analysis of permutation networks is not applicable to the broadcast problem. It is the purpose of this invention to illustrate a broadcast switching structure that employs permutation switching modules linked with collections of broadcast modules in such a way that the broadcast modules from centralized hubs which solely provide the one-to-many or fan-out broadcast function.

The present invention pertains to a broadcast network. The broadcast network comprises N transmit stations, with each transmit station being capable of transmitting a signal and N being an integer .gtoreq.1. There are also M receive stations, where M is an integer .gtoreq.2; I switching stages where I is an integer .gtoreq.0 and a broadcast hub. The broadcast hub and I switching stages are connected such that they are capable of linking the N transmit stations to the M receive stations so that any one of the N transmit stations can transmit a signal to L of the receive stations, where L is an integer and 1.ltoreq.L.ltoreq.M, but each receive station can receive a signal from only one of the N transmit stations at any given time. The broadcast hub and switching stages are arranged to simultaneously any number link more than one of the N transmit stations to desired receive stations at any given time.

FIG. 1 is a schematic representation of a broadcast module.

FIG. 2 is a schematic representation of a broadcast vector.

FIG. 3 is a schematic representation of a broadcast ring.

FIG. 4 is a schematic representation of a broadcast hyper-ring.

FIG. 5 is a schematic representation of a broadcast hyper-ring having 4 broadcast modules.

FIG. 6 is a schematic representation of a 4-input to 4-output broadcast ring.

FIG. 7 is a schematic representation of 2 broadcast vectors linked together to form a broadcast hyper-ring.

FIG. 8 is a schematic representation of 2 vectors, each of which have 3 broadcast modules, that are linked to form a broadcast hyper-ring.

FIG. 9 is a schematic representation of a broadcast vector equivalent to the broadcast hyper-ring shown in FIG. 8.

FIG. 10 is a schematic representation of 2 broadcast rings linked to form a broadcast hyper-ring.

FIG. 11 is a schematic representation of 2 broadcast vectors linked to form a broadcast hyper-ring.

FIG. 12 is a schematic representation of 2 broadcast vectors, each composed of 4 broadcast modules, linked to form a broadcast hyper-ring.

FIG. 13 is a schematic representation of a broadcast hyper-ring equivalent to the broadcast hyper-ring shown in FIG. 12.

FIG. 14 is a schematic representation of a switch threaded broadcast hyper-ring.

FIG. 15 is a schematic representation of a 16-input to 16-output broadcast switching network.

FIG. 16 is a schematic representation of a broadcast switching network with a broadcast hyper-ring realizing a broadcast assignment.

FIG. 17 is a schematic representation of a 16-input to 16-output broadcast switching network utilizing a broadcast ring realizing a broadcast assignment.

FIG. 18 is a schematic representation of a 16-input to 16-output broadcast switching network utilizing only two stages of switches realizing a broadcast assignment.

FIG. 19 is a schematic representation of a 10-input to 12-output broadcast switching network that does not have a presentation network realizing a broadcast assignment.

FIG. 20 is a schematic representation of broadcast hubs embedded in a broadcast switching network.

FIG. 21 is a schematic representation of a broadcast switching network to be used in illustrating the broadcast network control algorithm.

FIG. 22 is a schematic representation of the broadcast hyper-ring of FIG. 21 with associated presentation network outputs and distribution network inputs realizing a broadcast assignment.

FIG. 23 is a schematic representation of a 4 input, 4 output switching network with a broadcast ring of 16 broadcast modules.

FIG. 24 is a schematic representation of an implementation of a broadcast module.

Referring now to the drawings wherein like reference numerals refer to similar or identical parts throughout the several views, and more specifically to FIG. 1, there is shown a schematic drawing of a broadcast module 20. In general, a broadcast module has two distinct sets of input ports and two distinct sets of output ports:

1. a set of q external input ports denoted as E.sub.i ={e.sub.i1, e.sub.i2, . . . , e.sub.iq }

2. a set of r external output ports denoted as E.sub.o ={e.sub.o1, e.sub.o2, . . .,e.sub.or }

3. a set of s intermodule or internal input ports denoted I.sub.i ={i.sub.i1, i.sub.i2, . . . , i.sub.is }

4. a set of t intermodule or internal output ports denoted I.sub.o ={i.sub.o1, i.sub.o2, . . ., i.sub.ot }.

The first letter of the subscript of an external or internal port denotation identifies it as an input port, i, or output port, o. The second letter identifies which internal or external input port or output port it is of the set of internal or external input ports or output ports. In general, (.vertline.E.sub.i .vertline.=q).noteq.(.vertline.E.sub.o .vertline.=r).noteq.(.vertline.I.sub.i .vertline.=s).noteq.(.vertline.I.sub.o .vertline.=t) where .vertline.A.vertline. denotes cardinality or size of the set A. Finally, .vertline.E.sub.i .vertline..gtoreq.0, .vertline.E.sub.o .vertline..gtoreq.0, .vertline.I.sub.i .vertline..gtoreq.0, and .vertline.I.sub.o .vertline..gtoreq.0.

For purposes of identification herein, for any given broadcast module represented schematically, the most vertical input port or output port, whether it be an internal or external input or output, is the lowest indexed input or output port (that is, e.sub.i1, e.sub.o1, i.sub.i1, i.sub.o1). The least vertical input or output is the highest indexed input or output port (that is, e.sub.ig, e.sub.or, i.sub.is, i.sub.ot). The identity of any given external/internal input or output is determined by position relative to the other inputs and outputs. The external or internal inputs or outputs are distinct, and their identity is counted from 1 to q for the external inputs, from 1 to r for the external outputs, from 1 to s for the internal inputs, and from 1 to t for the internal outputs.

The external inputs and outputs provide for data or signal flow into and out of the broadcast structure that the broadcast modules have been linked together to form; the intermodule inputs and outputs provide for data or signal flow among the broadcast modules in the structure. These broadcast module inputs and outputs can pass signals or data serially or in parallel depending on the broadcast application.

There is complete fan-out capability between the inputs and the outputs of a broadcast module. In other words, under the restriction that each output can be connected to at most one input in a broadcast module, any external or intermodule/internal input can transmit data to any number (indeed, perhaps all) of the external/internal outputs.

A broadcast module is distinct from a switching module. In a switching module there are only external inputs and external outputs and only one-to-one connections are possible between these external inputs and external outputs. In other words, there is no fan-out capability. A switching module can be viewed as a much less complex, less expensive device when compared to a broadcast module.

A state of a broadcast module is defined in terms of the connections established between the input ports and output ports in the module. For example, a broadcast module 34, as used in the broadcast structure of FIG. 6, has one external input port e.sub.i1 ; one external output port e.sub.o1 ; one internal input port i.sub.il and one internal output port i.sub.o1. There are 27 possible states (3.sup.3) for such a broadcast module 34, as shown in Table 1. In general, a broadcast module can be placed in any of (q+s).sup.r+t states relative to input to output connections. This is generally accomplished by well-know control means that can also be linked throughout the overall broadcast network system to enable a signal to move through the network as desired. See for instance, Benes, Mathematical Theory of Connecting Networks and Telephone Traffic, Academic Press, New York, 1965.

The first line of Table 1 identifies the three outputs of the broadcast module of FIG. 3. The 27 lines underneath the first line of Table 1 are each comprised of three inputs and list the various states or connections between the inputs and the outputs. For instance, the first of these lines indicates that the e.sub.i1 input port is connected to each output port. This is but one state. It should be noted that, for broadcast purposes, only those states which have no more than one input connected to any number of the outputs are allowed. Thus, while there are more states, such as the e.sub.il and i.sub.il input ports connected to the e.sub.o1 output port, this is not a valid state.

The broadcast modules can be linked together to form different types of structures. These structures serve as broadcast hubs in broadcast switching networks. Signal or data fan-out in the invented broadcast switching networks takes place only within the broadcast hubs.

The most basic broadcast hub is a broadcast vector 22. FIG. 2 shows an example of a broadcast vector 22 where there are N vertically linked (via internal inputs and outputs) broadcast modules. Other than the most and least vertical broadcast modules in the broadcast vector, the broadcast modules are directly linked only to their neighboring two broadcast modules. The most vertical broadcast module 23 and the least vertical broadcast module 24 are only directly linked to one other broadcast module and are not directly linked to each other.

FIG. 3 shows a structure wherein the broadcast modules form a broadcast ring 25. In a broadcast ring the most vertical and least vertical broadcast modules are linked to each other with the remaining structure identical to the broadcast vector of FIG. 2. For exemplary purposes FIGS. 2 and 3 have only one external input, one external output, two internal inputs, and two internal outputs.

The most elementary of all broadcast modules has .vertline.E.sub.i .vertline.=E.sub.o .vertline.=.vertline.I.sub.i .vertline.=.vertline.I.sub.o1 .vertline.= 1. FIG. 6 shows a 4-input to 4-output broadcast ring 88 composed of such a broadcast module. As is seen in the following, broadcast switching networks utilizing such limited broadcast modules have greater demands on their connectivity for the realization of broadcast assignments than those that utilize more robust broadcast modules.

FIG. 4 shows a broadcast structure wherein the broadcast module forms a broadcast hyper-ring 26. A broadcast hyper-ring is composed of broadcast modules that are directly linked to other and/or more than their nearest neighbor broadcast modules in the broadcast ring. This linking of broadcast modules in a broadcast structure by means of internal inputs and outputs is called threading.

In the example shown in FIG. 4, each broadcast module is linked to every other broadcast module, and the threading is said to be complete.

FIG. 5 shows a 16-input to 16-output broadcast hyper-ring 200. For each broadcast module 202 therein there are four external inputs, four external outputs, three intermodule/internal inputs, and three intermodule array outputs. That is, .vertline.E.sub.i .vertline.=.vertline.E.sub.o .vertline.=4 and .vertline.I.sub.i .vertline.=.vertline.I.sub.o .vertline.=3. In FIG. 5 each of the four broadcast modules has a link to each of the other broadcast modules. That is, the threading is complete. In general, the broadcast modules in a broadcast vector, ring, or hyper-ring have links to only a subset of the other broadcast modules in the broadcast vector, ring, or hyper-ring. That is, the threading is incomplete. These links can be single links as shown in FIG. 5, or the links can be multiple/redundant links.

FIG. 7 shows another example of a broadcast hyper-ring. This hyper-ring is composed of two vectors 209, 211. To better understand this class of hyper-ring structure, observe the explicit example given in FIG. 8 of two vectors 213, 215 having three broadcast modules 217 each. In FIG. 9 an equivalent version of the structure of FIG. 8 is given. It is seen that in this hyper-ring, broadcast modules A, B, and C have external inputs, internal inputs and outputs, but no external outputs; similarly, broadcast modules D, E, and F have external outputs, internal inputs and outputs, but no external inputs. Yet the same overall results with respect to internal and external connections of the structure in FIG. 8 is achieved.

FIG. 10 shows another broadcast hyper-ring composed of two rings 221, 223. Clearly, this is similar to the structure of FIG. 7 except the broadcast modules 1 and N of these two rings 211, 223 are directly linked. It should be clear that broadcast hyper-rings composed of combinations of vectors, rings, and other hyper-rings are also possible.

FIG. 11 shows another example of a hyper-ring 27. In the example of a hyper-ring shown in FIG. 11, the most vertical broadcast module 23 of the broadcast vector 30 is linked to the most vertical broadcast module 28 of the broadcast vector 32. Additionally, the least vertical broadcast module 24 of the broadcast vector 30 is linked to the least vertical broadcast module 29 of the broadcast vector 32. The distinction between this class of hyper-ring and that previously shown can be better understood from FIG. 12 and FIG. 13. FIG. 12 shows such a hyper-ring involving eight broadcast modules. FIG. 13 shows the exact same structure but where the threading of the linkage among the broadcast modules is more apparent. In the previously shown hyper-rings, each broadcast module A, B, C, and D have external outputs, and only broadcast modules, 1, 2, 3, and 4 have external inputs. Broadcast modules 1, 2, 3, and 4 have only internal outputs, and broadcast modules A, B, C, and D have only internal inputs. The threading of links among the modules is more complex relative to that of the hyper-rings previously shown. One final variation of a hyper-ring permits the threading to be varied by placing switching modules 227 between the internal inputs and outputs. An example of a switch-threaded broadcast hyper-ring is shown in FIG. 14.

Broadcast switching networks can be formed by embedding broadcast hubs into structures otherwise composed of switching modules (that unto themselves can only provide one-to-one or permutation interconnection capability). The most basic design of a broadcast switching network simply places a broadcast vector, ring, or hyper-ring between two permutation switching networks. This is referred to as a PBD network. FIG. 15 shows a 16-input to 16-output PBD broadcast switching network. It consists of a 16-input to 16-output three-stage space-division permutation network, called the presentation network 302, linked to the external inputs of a broadcast hyper-ring 306, followed by another 16-input to 16-output space-division permutation network, called the distribution network 304, linked to the external outputs of the same broadcast hyper-ring 306. The two 16-input to 16-output permutation networks are comprised of linked (4.times.4) switching modules. The (4.times.4) switching modules need only have one-to-one connection capability from their inputs to their outputs for this overall PBD structure to provide broadcast switching capability.

The 16-input to 16-output permutation network on the left-hand side of the broadcast hyper-ring 306 shown in FIG. 15 serves as a presentation network 302 to the broadcast hyper-ring 306 in that its function is to provide a single linking path from each transmit station input port to some external input of the broadcast hyper-ring 306. The 16-input to 16-output permutation network on the right-hand side of the hyper-ring serves as a distribution network 304 from the broadcast hyper-ring 306 in that its function is to provide a one-to-one linking path from each external output of the broadcast hyper-ring 306 to which a broadcast hyper-ring 306 input has transmitted a signal or data to the appropriate network output destination. In other words, the presentation network 302 presents the signal or data to be broadcast to the receive station of the broadcast hyper-ring 306, and the distribution network 304 distributes the signal or data emanating from the broadcast hyper-ring 306 to the appropriate receive stations. The broadcast hyper-ring 306, in addition to performing the broadcast function, must also align the signal or data to accommodate the transfer from the presentation network 306 to the distribution network 304. The ability of the broadcast hyper-ring 306 to do this depends on parameters of its structure such as .vertline.E.sub.i .vertline., .vertline.E.sub.o .vertline., .vertline.I.sub.i .vertline., and and .vertline.I.sub.o .vertline. and the threading of the internal/intermodule connecting links.

It should be appreciated that the presentation and distribution networks 302, 304 do not necessarily have to function as complete permutation networks in order for the overall structure to provide complete broadcast capability. Indeed, broadcast switching network designs shall be shown below wherein the presentation/distribution networks 302, 304 employed cannot perform all permutations. The interplay among the three components of a PBD network, (that is, the presentation network, the broadcast vector, ring, or hyper-ring, and the distribution network) is critical to the operation of the invented broadcast switching network.

A decomposition technique by which the broadcast switching network design approach of employing the functional triplex of presentation, distribution, and broadcast can be iteratively used is implicit in the design shown in FIG. 15. Note that in FIG. 15, a 16-input to 16-output broadcast switching network 300 has been designed by using two 16-input to 16-output permutation networks, a presentation network 302 and a distribution network 304, and a broadcast structure which is shown here as a broadcast hyper-ring 306. In other words, the large broadcast switching network was designed by using permutation networks (for which a multitude of designs are known) and smaller broadcast networks. The same design concept could now be repeated for each individual broadcast network. Iterating the design in this way would eventually lead to the point where the broadcast network would be realizable with elementary broadcast modules.

Realization of a broadcast assignment is shown in FIG. 16. These broadcast assignments involve a transmission to each output in the broadcast switching network 400. To denote a broadcast assignment, the transmit station can be denoted by the set 1,2 . . . 16 and the receive stations can be denoted by the set a, b, . . . , p. The broadcast assignment can then be described by the following broadcast connections:

where O.sub.j is the subset of the receive station set denoting the outputs to which transmit station j is to broadcast its signal or data. Accordingly, the example broadcast assignment of FIG. 16 is represented by

In this broadcast assignment representation, those transmit stations which are not connected to receive stations in the assignment are not represented. In the realization of these broadcast connections as depicted in FIG. 16, it is seen that the broadcast hyper-ring 402 is the only part of the broadcast switching network 400 providing fan-out. The presentation network 404 and the distribution network 406 are only providing permutation connections relative to their inputs and outputs. Moreover, the paths through the presentation network 404 emanate only from transmit stations 1,3,4,6,10, and 15. (The circuitous path by which transmit station 10 is connected to output o is particularly worth noting in FIG. 16 as it illustrates the flexibility with which fan-out can be implemented with the threading pattern used in the broadcast hub.)

Consider, for instance, the realization of broadcast connection (10.fwdarw.(g, l, o)) in FIG. 16. The transmit port 408 of transmit station 10 is interfaced to the second input port 410 of switch 412. Switch 412 is in the first switching stage 414 of presentation network 404. The second input port 410 of switch 412 is connected to the second output port 416 of switch 412. The second output port 416 of switch 412 is linked to the third input port 418 of switch 420. Switch 420 is in the second switching stage 422 of presentation network 404. The third input port 418 of switch 420 is connected to the third output port 424 of switch 420. The third output port 424 of switch 420 is linked to the second input port 426 of switch 428. Switch 428 is in the third switching stage 430 of presentation network 404. The second input port 426 of switch 428 is connected to the fourth output port 432 of switch 428. The fourth output port 432 of switch 428 is linked to the e.sub.i4 input port of broadcast module 434. Fan-out takes place in broadcast module 434 in broadcast hyper-ring 402. Broadcast hyper-ring 434 is in such a state that the e.sub.i4 input port is fanned-out to the i.sub.o2, e.sub.o3, and e.sub.o4 output ports of broadcast module 434.

The i.sub.o2 output port of broadcast module 434 is linked to the i.sub.i2 input port of broadcast module 436. Broadcast module 436 is in a state such that the i.sub.i2 input port of broadcast module 436 is connected to the i.sub.o1 output port of broadcast module 436. The i.sub.o1 output port of broadcast module 436 is connected to the i.sub.il input port of the broadcast module 438. Broadcast module 438 is in broadcast hyper-ring 402. The i.sub.il input port of broadcast module 438 is connected to the e.sub.o2 output port of broadcast module 438. The e.sub.o2 output port of broadcast module 438 is linked to the second input port 440 of switch 442. Switch 442 is in the first switching stage 444 of distribution network 406. The second input port 440 of switch 442 is connected to the second output port 446 of switch 442. The second output port 446 of switch 442 is linked to the fourth input port 448 of switch 450. Switch 450 is in the second switching stage 452 of distribution network 406. The fourth input port 448 of switch 450 is connected to the fourth output port 454 of switch 450. The fourth output port 454 of switch 450 is linked to the second input port 456 of switch 458. Switch 458 is in the third switching stage 460 of distribution network 406. The second input port 456 of switch 458 is connected to the third output port 462 of switch 458. The third output port 462 of switch 458 is interfaced to the receive port 464 of receive station o.

The e.sub.o3 output port of broadcast module 434 is linked to the third input port 466 of switch 468. Switch 468 is in switching stage 444. The third input port 466 of switch 468 is connected to the third output port 470 of switch 468. The third output port 470 of switch 468 is linked to the third input port 472 of switch 474. Switch 474 is in switching stage 452. The third input port 472 of switch 474 is connected to the second output port 476 of switch 474. The second output port 476 of switch 474 is connected to the third input port 478 of switch 480. The third input port 478 of switch 480 is connected to the third output port 482 of switch 480. The third output port 482 of switch 480 is interfaced to the receive port 484 of receive station g.

The e.sub.o4 output port of broadcast module 434 is connected to the fourth input port 486 of switch 468. The fourth input port 486 of switch 468 is connected to the fourth output port 488 of switch 468. The fourth output port 488 of switch 468 is linked to the third input port 490 of switch 492. Switch 492 is in switching stage 452. The third input port 490 of switch 492 is connected to the third output port 494 of switch 492. The third output port 494 of switch 492 is linked to the fourth input port 496 of switch 497. Switch 497 is in switching stage 460. The fourth input port 496 of switch 497 is connected to the fourth output port 498 of switch 497. The fourth output port 498 of switch 497 is interfaced to the receive port 499 of receive station 1.

The other connecting paths depicted in broadcast switching network 400, which allow the additional broadcast connections of the example broadcast assignment to be realized, are not described. However, such connecting paths are similar to that discussed for broadcast connection (10.fwdarw.(g, l, o)), except that different broadcast modules and switches, or different input and output ports of the same broadcast modules and switches are utilized, as is apparent from FIG. 16.

In FIG. 17, another realization of the example broadcast assignment used in FIG. 16 is shown for a PBD broadcast switching network 500 utilizing a broadcast ring 528 composed of the elementary broadcast modules depicted in FIG. 6 where .vertline.E.sub.i .vertline.=.vertline.E.sub.o .vertline.=.vertline.I.sub.i .vertline.=.vertline.I.sub.o .vertline.=1. It should be appreciated that there is significantly less flexibility in the ways in which a broadcast assignment can be realized with this broadcast switching network 500 relative to the broadcast switching network 300 shown in FIG. 15. This is because it is only possible for the broadcast ring 528 to fan-out the signals to be transmitted to the distribution network in restricted sequences.

Consider, for instance, the realization of broadcast assignment (1.fwdarw.(b, f, k)). The transmit port 502 of transmit station 1 is interfaced to the first input port 504 of switch 506 in the first switching stage 508 in the presentation network 510. The first input port 504 of switch 506 is connected to the first output port 512 of switch 506 which in turn is linked to the first input port 514 of switch 516. Switch 516 is in the second switching stage 517 of the presentation network 510. The first output port 518 of switch 516 is linked to the first input port 520 of switch 522. Switch 522 is in the third switching stage 523 of the presentation network 510. The first input port 520 of switch 522 is connected to the second output port 524 of switch 522. The second output port 524 of switch 522 is connected to the e.sub.il input port of broadcast module 526 of broadcast hyper-ring 528. Broadcast module 526 is in a state such that the e.sub.il input port thereof is fanned-out to the i.sub.o1 output port and to the e.sub.o1 output port of broadcast module 526.

The i.sub.o1 output port of broadcast module 526 is linked to the i.sub.il input port of broadcast module 530. The i.sub.il input port of broadcast module 530 is in a state such that the i.sub.il input port thereof is fanned-out to the e.sub.o1 output port and the o1 i.sub.o1 output port of broadcast module 530.

The i.sub.o1 output port of broadcast module 530 is linked to the i.sub.il input port of broadcast module 532. The broadcast module 532 is in a state such that the i.sub.il input port thereof is connected to the e.sub.o1 output port of broadcast module 532. The e.sub.o1 output port of broadcast module 532 is linked to the fourth input port 534 of switch 536. Switch 536 is in the first switching stage 538 of distribution network 540. The fourth input port 534 of switch 536 is connected to the fourth output port 540 of switch 530 which in turn is linked to the fourth input port 542 of switch 544 Switch 544 is in the second switching stage 546 of the distribution network 540. The fourth input port 542 of switch 544 is connected to the third output port 548 of switch 544. The fourth input port 550 of switch 552 is connected to the third output port 556 of switch 552. The third output port 556 of switch 552 is linked to the receive port 558 of receive station K.

The e.sub.o1 output port of broadcast module 530 is linked to the first input port 560 of switch 562. Switch 562 is in the first switching stage 538. The first input port 560 of switch 562 is connected to the first output port 564 of switch 562. The first output port 564 of switch 562 is linked to the first input port 566 of switch 568. Switch 568 is in the second switching stage 546. The first input port 566 of switch 568 is connected to the first output port 570 of switch 568. The first output port 570 of switch 568 is linked to the first input port 572 of switch 574. Switch 574 is in the third switching stage 554. The first input port 572 of switch 574 is connected to the second output port 576 of switch 574. The second output port 576 of switch 574 is linked to the receive port 578 of receive station B.

The e.sub.o1 output port of broadcast module 526 is linked to the second input port 580 of switch 562. The second input port 580 of switch 562 is connected to the second output port 582 of switch 562. The second output port 582 of switch 562 is linked to the first input port 584 of switch 586. Switch 586 is in the second switching stage 546. The first input port 584 of switch 586 is connected to the second output port 588 of switch 586. The second output port 588 of switch 586 is linked to the second input port 590 of switch 592. Switch 592 is in the third switching stage 554. The second input port 590 of switch 592 is connected to the second output port 594 of switch 592. The second output port 594 of switch 592 is linked to the receive port 596 of receive station F.

The other connecting paths depicted in broadcast switching network 500 which allow the additional broadcast assignments therein to be realized are not described. However, such connecting paths are similar to the connecting paths discussed for broadcast assignment (1.fwdarw.(b, f, k)), except that different broadcast modules and switches, or different input and output ports of the same broadcast modules and switches are utilized, as is apparent from FIG. 17.

As was mentioned previously, for a PBD network to realize broadcast assignments, it is not necessary that a broadcast ring be placed directly between two complete permutation networks as shown in FIG. 15. FIG. 18 shows another version of a 16-input to 16-output broadcast switching network 600. In this 16-input to 16-output broadcast switching network, there are only two stages of (4.times.4)-switch modules comprising the distribution network 604. Clearly, neither the presentation network 602 nor the distribution network 604 can perform all permutations of its inputs onto its outputs. FIG. 18 also shows a realization of the same broadcast assignments considered in FIGS. 16 and 17 with this broadcast switching network 600. Observation of the broadcast switching network 600 shown in FIG. 18 reveals that it is the network 300 shown in FIG. 15 with the first and last switching stages of the presentation broadcast switching network and distribution network thereof deleted, respectively. The fact that the broadcast assignments can still be realized attests to the linking power of the broadcast hyper-ring being utilized. Broadcast switching network 600 depicts a realization of the example broadcast assignment:

In order, for instance, for broadcast assignment (6.fwdarw.(c, i, j, p)) to be realized, the transmit port 606 of transmit station 6 is interfaced to the second input port 608 of switch 610. Switch 610 is in switching stage 612 of the presentation network 602. The second input port 608 of switch 610 is connected to the third output port 612 of switch 610. The third output port 612 of switch 610 is linked to the second input port 614 of switch 616. Switch 616 is in switching stage 618 of presentation network 602. The second input port 614 of switch 616 is connected to the first output port 620 of switch 616. The first output port 620 of switch 616 is linked to the e.sub.i l input port of broadcast module 622. Broadcast module 622 is in broadcast hyper-ring 624. Broadcast module 622 is in a state such that the e.sub.il input port of broadcast module 622 is fanned-out to the i.sub.o3, i.sub.o1, e.sub.o1, and e.sub.o4 output ports.

The i.sub.o3 output port of broadcast module 622 is connected to the i.sub.i3 input port of broadcast module 626. The i.sub.i3 output port of broadcast module 626 is linked to the first input port 628 of switch 630. Switch 630 is in switching stage 632 of distribution network 604. The first input port 628 of switch 630 is connected to the third output port 634 of switch 630. The third output port 634 of switch 630 is linked to the fourth input port 636 of switch 638. Switch 638 is in switching stage 640 of distribution network 604. The fourth input port 636 of switch 638 is connected to the second output port 642 of switch 638. The second output port 642 of switch 638 is interfaced to the receive port 644 of receive station j.

The e.sub.o4 output port of broadcast module 622 is linked to the fourth input port 646 of switch 648. Switch 648 is in switching stage 632. The fourth input port 646 of switch 648 is connected to the first output port 650 of switch 648. The first output port 650 of switch 648 is linked to the third input port 652 of switch 654. Switch 654 is in switching stage 640. The third input port 652 of switch 654 is connected to the third output port 656 of switch 654. The third output port 656 of switch 654 is interfaced to the receive port 658 of receive station c.

The e.sub.o1 output port of broadcast module 622 is linked to the first input port 660 of switch 648. The fourth output port 662 of switch 648 is linked to the third input port 664 of switch 666. Switch 666 is in switching stage 640. The third input port 664 of switch 666 is connected to the fourth output port 668 of switch 666. The fourth output port 668 of switch 666 is interfaced to the receive port 670 of receive station p.

The i.sub.o1 output port of broadcast module 622 is linked to the i.sub.i2 input port of broadcast module 672. Broadcast module 672 is in broadcast hyper-ring 624. Broadcast module 672 is in a state such that the i.sub.i2 input port is connected to the e.sub.o4 output port of broadcast module 672. The e.sub.o4 output port of broadcast module 672 is linked to the fourth input port 674 of switch 676. Switch 676 is in switching stage 632. The fourth input port 674 of switch 676 is connected to the third output port 678 of switch 676. The third output port 678 of switch 676 is linked to the second input port 680 of switch 638. The second input port 680 of switch 638 is connected to the first output port 682 of switch 638. The first output port 682 of switch 638 is interfaced to the receive port 684 of receive station i.

The other connecting paths depicted in broadcast switching network 600, which allow the additional broadcast assignments therein to be realized, are not described. However, such connecting paths are similar to the connecting paths discussed for broadcast assignment (6.fwdarw.(c, i, j, p)), except that different broadcast modules and switches, or different input and output ports of the same broadcast modules and switches are utilized, as is apparent from FIG. 18.

In FIG. 19 a 10-input to 12-output broadcast switching network 700 is shown realizing a broadcast assignment involving 5 of the 10 inputs. In this broadcast switching network 700 there is no presentation network. Again, the broadcast switching network 700 has unto itself sufficient connecting capability to broadcast and align the inputs to satisfy this request. Indeed, for the broadcast network of FIG. 19, all 12.sup.10 broadcast assignments are realizable.

Broadcast switching network 700 depicts broadcast assignments (1.fwdarw.(e, k)), (2.fwdarw.(a, f, l)), (5.fwdarw.(d)), (8.fwdarw.(b, g, i)), (10.fwdarw.(c. h. j)). In order, for instance, for broadcast assignment (2.fwdarw.(a, f, l)) to be realized, transmit port 702 of transmit station 2 is interfaced to the e.sub.i2 input port of broadcast module 704. The e.sub.i2 input port of broadcast module 704 is fanned-out to the e.sub.o1, e.sub.o2, and e.sub.o3 output ports of broadcast module 704. Broadcast module. 704 is in broadcast ring 706. The e.sub.o1 output port of broadcast module 704 is linked to the first input port 708 of switch 710 which in turn is connected to the first output port 716 of switch 710. The first output port 716 of switch 710 is linked to the first input port 718 of switch 720. Switch 720 is in switching stage 722 in distribution network 714. The first input port 718 of switch 720 is connected to the first output port 724 of switch 720. The first output port 724 of switch 720 is interfaced to the receive port 726 of receive station a.

The e.sub.o2 output port of broadcast module 704 is linked to the second input port 728 switch 710. The second input port 728 of switch 710 is connected to the second output port 730 of switch 710. The second output port 730 of switch 710 is linked to the first input port 732 of switch 734. Switch 734 is in switching stage 722. The first input port 732 of switch 734 is connected to the second output port 736 of switch 734. The second output port 736 of switch 734 is interfaced to the receive port 738 of receive port F.

The e.sub.o3 output port of broadcast module 704 is connected to the third input port 740 of switch 710. The third input port 740 of switch 710 is connected to the third output port 742 of switch 710. The third output port 742 of switch 710 is linked to the first input port 744 of switch 746. Switch 746 is in switching stage 722. The first input port 744 of switch 746 is connected to the fourth output port 748 of switch 746. The fourth output port 748 of switch 746 is interfaced to the receive port 750 of receive station l.

The other connecting paths depicted in broadcast switching network 700 which allow the additional broadcast assignments therein to be realized are not described. However, such connecting paths are similar to the connecting paths discussed for broadcast assignment (2.fwdarw.(a, f, l)), except that different broadcast modules and switches, or different input and output ports of the same broadcast modules and switches are utilized, as is apparent from FIG. 19.

It should be clear that many variations of the above broadcast switching network designs are possible. For example, a PB network could be designed in a manner similar to that discussed for the BD network. As another example, observe that in the examples given of PBD networks, the linkage pattern from the presentation network to the broadcast hub and from the broadcast hub to the distribution network is direct in the sense that the output ports of each switch module in the last stage of the presentation network are linked directly to the input ports of the corresponding broadcast module in the broadcast hub and, similarly, the output ports of each broadcast module in the broadcast hub are linked directly to the input ports of the corresponding switch module in first stage of the distribution network. An alternative would be to shuffle this linkage pattern. One possibility of such a shuffled linkage pattern would be to use the same pattern shown between each stage of the presentation and the distribution networks. As yet still another example of a variation of the broadcast switching network designs being considered, not only is there no reason why the number of input ports or the number of output ports should be equal in a broadcast switching network, but the number of inputs and outputs to the broadcast hub can also be different from each other and/or the number of network inputs and outputs. Indeed, having more broadcast hub inputs/outputs in comparison to network inputs/outputs can greatly facilitate broadcasting capability.

Finally, while previous discussion of the broadcast hubs have explicitly considered structures defined as vectors, rings, and hyper-rings, other structures, such as hyper-cubes, could also be used for broadcast hub structures.

Many other designs are possible. FIG. 20 illustrates the general concept of embedding broadcast hubs into a switching structure. In such a general configuration, the notions of presentation and distribution are not explicitly apparent. Nevertheless, the underlying ideas supporting such general network designs are identical to that upon which the basic PBD network design is based.

The issue of establishing connecting paths through a broadcast switching network will now be discussed. Path set-up control of the broadcast switching structures being described here has two components which need to be tightly coordinated:

1. Setting up connecting paths through the switching modules.

2. Fan-out of these paths within the broadcast hubs.

Accordingly, to establish a broadcast connection from a specified broadcast network input to some specified set of broadcast network outputs, the availability and reachability of inputs/outputs of the switching modules and external/internal inputs/outputs of the broadcast hub must be taken into account. To facilitate a discussion of a control algorithm which does this, the basic PBD network of FIG. 15 will be considered. It should be understood that the algorithm could easily be modified to handle general variations of the basic PBD network design.

Clearly, the connecting capabilities of the presentation and distribution networks of FIG. 15 are central to the details of any broadcast network control algorithm. In general in a PBD network, if both the presentation and distribution networks are non-blocking in the sense that any connection from an idle input to an idle output within the presentation or distribution network can be established without disturbing any of the existing connections, then the overall broadcast network control algorithm can exploit this nonblocking switching capability relative to fan-out of the connecting paths within the broadcast hub. If, however, existing connecting paths in the presentation and distribution networks must at times be rearranged to establish a new broadcast connection or to add to a broadcast connection, then the overall broadcast network control algorithm must take into account these potential rearrangement requirements relative to the fan-out of the connecting paths within the broadcast hub. Finally, if the presentation and/or distribution networks cannot provide full connectivity between their inputs and outputs, then the broadcast network control algorithm must attempt to compensate for these limitations by means of the fan-out of connecting paths within the broadcast hub.

Thus, to give explicit details of a broadcast network control algorithm requires that the presentation and distribution network control components be explicitly described. In the following, an example of a broadcast network control algorithm will be given in which the issues of presentation and distribution network control are de-coupled from the issue of broadcast hub control. This is justified by the fact that whether the presentation or distribution networks are non-blocking or rearrangeable, algorithms for establishing connections through such presentation and distribution networks are well-known. (See C. Clos, "A Study of Nonblocking Switching Networks," BSTJ, vol. 32, no. 2 March, 1953, 406-424; V. Benes, Mathematical Theory of Connecting Networks and Telephone Traffic Academic Press, New York, 1965.) Accordingly, it will be assumed that the presentation network and distribution network control components of the overall broadcast network control algorithm can utilize these algorithms. Furthermore, if either the presentation network or distribution network involved in a broadcast network design does not have full accessibility between their respective inputs and outputs (for example, see FIGS. 18 and 19), then it will be assumed that this limited accessibility can in some way be characterized and this information will be made available to the broadcast network control algorithm for its use in determining connecting paths within the broadcast network to satisfy some broadcast assignment.

To describe a broadcast network control algorithm, the broadcast network shown in FIG. 21 will be considered. Suppose the broadcast connection to be realized is (7.fwdarw.(k, p)). In other words, input 7 of presentation input stage switch 2 (denoted (PI2)) is to be connected to some broadcast network output k of distribution output stage switch 3 (DO3) and output p of distribution output stage switch 4 (DO4).

Suppose further that at the time of the broadcast connection request, input 7 is not connected to any network outputs. This means that there is currently no connecting path from input 7 to the broadcast hyper-ring through the presentation network. Hence, to establish the broadcast connection (7.fwdarw.(k, p)), a connecting path must be provided through the network from input 7 to some idle presentation network output.

Suppose at the time of this request, the state of the presentation network is such that the idle presentation network outputs are the following: outputs a and b of presentation output stage switch 1 (denoted as P01(a) and P01(b)); outputs a and c of presentation output stage switch 2 (P02(a) and P02(c)); outputs a and d of presentation output stage switch 3 (P03(a) and P03(d)); and outputs a and b of presentation output stage switch 4 (P04(a) and P04(b)). This is illustrated in FIG. 22 which is an expansion of the output stage of the presentation network, the broadcast hyper-ring, and the input stage of the distribution network of FIG. 21. The "B's" and "I's" in FIG. 22 correspond to busy and idle, respectively.

Similarly, at the time of this request, suppose that the state of the distribution network is such that the idle distribution network inputs are the following: input 2 of distribution input stage switch 2 (denoted as DI2(2)); input 1 of distribution input stage switch 3 (DI3(1)); and input 4 of distribution input stage switch 4 (DI4(4)). This is also illustrated in FIG. 22.

Clearly, the ability to fan-out a new connecting path through the broadcast hyper-ring depends in part on the nature of the fan-out currently implemented. Note in FIG. 22 that the connecting path presented to the broadcast hyper-ring by P01(c) is being fanned-out to four broadcast hyper-ring external outputs: B1(e.sub.o1), B1(e.sub.o2), B3(e.sub.o2), and B4(e.sub.o1). Because this fan-out utilizes different broadcast modules, both the fan-out and the corresponding broadcast connection are said to be distributed. Because this fan-out does not utilize sequential inputs of the distribution network, both the fan-out and the broadcast connection are said to be non-sequential. Ideally, all fan-outs in the broadcast connection would be non-distributed and sequential. However growth and termination of other broadcast connections might prevent this from being achievable. For example, implementing a non-distributed sequential broadcast connection over the broadcast hyper-ring might require extensive or prohibitive rearrangement in the presentation and/or distribution networks. Or, as another example, implementing a non-distributed sequential broadcast connection over the broadcast hyper-ring might be impossible because of the limited connecting capability of the presentation and/or distribution networks.

Even assuming full reachability of input 7 to all the presentation network output stage switches, it should be clear from observing FIG. 22 that it is not possible to provide the broadcast connection from input 7 of P14 to output k of DO3 and output p of DO4 by using either a non-distributed or a sequential fan-out. Accordingly, to add (7.fwdarw.(k, p)) to the broadcast connections being realized without disturbing any of these connections, the broadcast network control algorithm must fan-out the connecting paths over multiple broadcast modules in the broadcast hyper-ring. To accomplish this, the reachability and availability of external and internal inputs and outputs of each broadcast module must be known relative to input 7 and outputs k and p:

A presentation network output switch availability list will be defined to be a list of the output switches of the presentation network that currently have idle links into broadcast modules. This list will be denoted as POAV. For FIG. 22,

A presentation network output switch reachability list will be defined relative to the broadcast network input that is to be connected to the broadcast network outputs according to some requested broadcast connection. For our broadcast connection example of (7.fwdarw.(k, p)), this list will be denoted as POR.sub.7. A presentation network output switch reachability list corresponds to the set of output switches of the presentation network to which an input (input 7 in the broadcast connection example of (7.fwdarw.(k, p))) has access given the current state of the presentation network and/or the operational restrictions under which connecting paths must be established through it. Ideally, POR.sub.7 POAV. This would mean that input 7 could be connected to each presentation network output switch with an idle link to a broadcast module. This, of course, would be the case if the presentation network were non-blocking, or if the presentation network were rearrangeable and there were no limits on the extent to which rearrangements could take place. However, in general, POR.sub.7 POAV and the broadcast network control algorithm must utilize POR.sub.7 .andgate.POAV.

Similarly, a distribution network input switch availability list will be defined to be a list of the input switches of the distribution network that have idle links from the broadcast modules. This list will be denoted as DIAV. For FIG. 22,

Distribution network output switch reachability lists will be defined relative to each of the broadcast network outputs that is to be connected to the broadcasting input according to some requested broadcast connection. For our broadcast connection example of (7.fwdarw.(k, p)), these lists will be denoted as DIR.sub.k and DIR.sub.p. Distribution network output switch reachability lists correspond to the input switches of the distribution network to which each of the outputs (k and p in the broadcast connection example of (7.fwdarw.(k, p))) have access given the current state of the distribution network and/or the operational restrictions under which connecting paths can be established through it. In general, DIR.sub.k DIAV and DIR.sub.p DIAV and the broadcast network control algorithm must utilize DIR.sub.k .andgate.DIAV and DIR.sub.p .andgate.DIAV.

To realize the broadcast connection (7.fwdarw.(k, p)), the broadcast network control algorithm must fan-out one of the presentation network connecting paths available to the broadcast hyper-ring from one of the output switches in POR.sub.7 .andgate.POAV into two connecting paths within the broadcast ring and then connect one of these fanned-out paths to a distribution network input switch in DIR.sub.k .andgate.DIAV and connect the other fanned-out path to a distribution network input switch in DIR.sub.p .andgate.DIAV. To do this, the available connectivity of each of the broadcast modules in the broadcast hyper-ring to the output switches of the presentation network, to the input switches of the distribution network, and to other broadcast modules must be considered. For each broadcast module, a broadcast module connectivity list will denote the set of output switches of the presentation network, input switches of the distribution network, and other broadcast modules to which that broadcast module can currently be directly connected. If there are broadcast modules, the broadcast module connectivity lists will be denoted BM1, BM2, . . . , BMm, where BMi corresponds to broadcast module i. In FIG. 9,

Note that PO1 is listed twice in BM1. This because there are two idle links from PO1 into BM1. For the same reason there are multiple listings of PO2 in BM2, PO3, in BM3, and PO4 in BM4. Similarly, if BMi had t idle links into DIi, then would be listed t times in BMi. Finally, the fact that in this example BMi's only list POi's and DIi's (in addition to the Bj's) is only a result of the direct linkage patterns between broadcast hyper-ring and the output switch stage of the presentation network and the input switch stage of the distribution network.

The following algorithm formally characterizes the above discussion in a general context:

1. Given a requested broadcast connection (x.fwdarw.(a,b, . . . , c)), determine the following sets:

If .DELTA..sub.x =POR.sub.x .andgate.POAV=.PHI., or if .theta..sub.i =.PHI. for i .epsilon.(a,b, . . . c), go to step 13, otherwise, proceed to step 2.

Comment: The presentation network output switches that are reachable from input x by means of compatible connecting paths relative to existing connections and have idle links into broadcast modules are determined in this step and denoted by the set .DELTA..sub.x. If .DELTA..sub.x is empty, then given the current set of connecting paths through the presentation network and the operational restrictions under which the connecting paths can be established, input x cannot reach the broadcast hub. The distribution network input switches that have idle links from broadcast modules and are reachable from each of the outputs a,b, . . . , c by means of compatible connecting paths relative to existing connections and the operational restrictions under which the connecting paths can be established are also established in this step and are denoted, respectively, as .theta..sub.a, .theta..sub.b, . . . .theta..sub.c. If any .theta..sub.i is empty, then given the current set of connecting paths through the distribution network and the operational restrictions under which the connecting paths can be established, output i cannot be reached from the broadcast hub. Finally, it should be noted here that a non-empty .theta..sub.i means that there are connecting paths from the input stage of the distribution network to output i that are compatible with existing paths. However, paths corresponding to a .theta..sub.i and paths corresponding to a .theta..sub.j might not be compatible with each other. The algorithm will deal with this issue in step 9.

2. Determine BM1, BM2, . . . , BMm.

Comment: The broadcast module connectivity lists denoting the set of output switches of the presentation network, input switches of the distribution network, and other broadcast modules to which each broadcast module can currently be directly connected are established in this step.

3. Choose an element, say, POi.epsilon..DELTA..sub.x. If .DELTA..sub.x =.PHI., go to step 13.

Comment: A presentation network output switch, POi, is selected which has idle links into the broadcast hub and which can be reached from input x with a compatible connecting path.

4. Let .SIGMA. be the set of all the Bk's for which POi.epsilon.BMk.

Comment: In this step, all the broadcast modules which can be reached from POi are determined as the set .SIGMA..

5. If .SIGMA.=.PHI., set .DELTA..sub.x =.DELTA..sub.x -POi and go to step 3. If .SIGMA..noteq..PHI., choose an element, say, Bk.epsilon..SIGMA. and let .GAMMA.={BMk}.

Comment: If no broadcast modules can be reached from the selected POi (i.e., .SIGMA.=.PHI.), then another presentation network output switch POj.noteq.POi, POj.epsilon..DELTA..sub.x must be selected in step 3. Otherwise, some Bk.epsilon..SIGMA. is chosen as the broadcast module to which POi will be connected. .GAMMA. is initially defined as the broadcast module connectivity list for Bk. The set .GAMMA. will contain among its elements other broadcast modules which can be reached directly from Bk and input switches of the distribution network that can also be reached directly from Bk.

6. Let .LAMBDA. be the union of all BMj for which Bj.epsilon..GAMMA. and also for which BMj .GAMMA.

Comment: Additional broadcast modules and/or distribution network input switches that can be reached by input x through broadcast modules to which Bk has idle links are determined in the initial execution of this step. Subsequent iterations of this step will determine broadcast modules and/or distribution network input switches that can be reached by input x indirectly through other broadcast modules.

7. Let .GAMMA.=.GAMMA..orgate..LAMBDA.. If .LAMBDA.=.PHI., go to step 7; if .LAMBDA..noteq..PHI., go to step 6.

Comment: .GAMMA. is updated in this step by including in it all the elements of .LAMBDA. determined in step 6. If the .LAMBDA. determined in the most recent iteration of step 6 was empty, then the current .GAMMA. contains among its elements all of the broadcast modules and/or distribution network input switches that can be reached by input x through the selected POi, and step 7 should now be performed. If the .LAMBDA. determined in the most recent iteration of step 6 was not empty, then step 6 must be executed again for there is the possibility that broadcast modules and/or distribution network input switches in addition to those currently included in .GAMMA. can be reached by input x through POi.

8. Let .OMEGA..sub.x =(a, b, . . . , c) denote the output set in the broadcast connection (x.fwdarw.(a, b, . . . , c)

9. Choose an output s.epsilon..OMEGA..sub.x. Select a DI.sub.q .epsilon..GAMMA. for which DI.sub.q .epsilon..theta..sub.s =DIR.sub.s .andgate.DIAV, and for which there is an compatible connecting path through the distribution network from Di.sub.q to output s relative to all other connecting paths that have been previously selected in iterations of this step for the partial realization of (x.fwdarw.(a,b, . . . , c)). If such a DI.sub.q can be found, set .GAMMA.=.GAMMA.DI.sub.q and go to step 10; if no such DI.sub.q can be found, go to step 11.

Comment: In this step, an attempt is made to determine a connecting path from input x to output s via DI.sub.q for the partial realization of (x.fwdarw.(a,b, . . . , c)). This path can be denoted as (x.fwdarw.POi.fwdarw.DI.sub.q .fwdarw.s). By the construction of .GAMMA., it is known that input x can reach DI.sub.q .epsilon..GAMMA. through the broadcast hub. However, it must be determined whether a compatible path exists from DI.sub.q to output s relative to other connecting paths through the distribution network determined in previous executions of this step of the algorithm for partially realizing (x.fwdarw.(a, b, . . . , c)). For example, suppose that in previous iterations of this step, compatible paths through the distribution network have been determined for (s.sub.1,s.sub.2, . . . , s.sub.k) (a,b, . . . , c)). Suppose further that in the current iteration of this step of the algorithm no DI.sub.q .epsilon..GAMMA. could be found for which a path corresponding to DI.sub.q .fwdarw.s existed which was compatible with all of the paths through the distribution network determined for (s.sub.1, s.sub.2, . . . , s.sub.k) (a,b, . . . , c) corresponding to (DIr.fwdarw.s). In such a case, alternative paths through the distribution network for some subset of the (s.sub.1, s.sub.2, . . . , s.sub.k) (a,b, . . . , c) would be sought in step 11. Otherwise, the algorithm deletes a single listing of DI.sub.q from F and proceeds to step 10 where output s is deleted from .OMEGA..sub.x and it is determined whether the complete broadcast connection (x.fwdarw.(a,b, . . . , c)) can now be realized or whether only part of this connection has been addressed and further iterations of step 9 are required. Finally, it should be clear that in the initial execution of this step, since DI.sub.q .epsilon..theta..sub.s =DIR.sub.s DIAV, no conflict with existing connecting paths through the distribution network can occur.

10. Set .OMEGA..sub.x =.OMEGA..sub.x -s. If .OMEGA..sub.x =.0., go to step 12; otherwise, go to step 9.

Comment: If after s is removed from .OMEGA..sub.x, the result is that .OMEGA..sub.x is empty, then connecting paths through the broadcast hub and the distribution network have been determined for the complete realization of (x.fwdarw.(a,b, . . . , c)) and the algorithm stops. If after s is removed from .OMEGA..sub.x, the result is that .OMEGA..sub.x is not empty, then a realization of (x.fwdarw.(a,b, . . . , c)) has only been partially determined, and the algorithm returns to step 9 to consider the remaining part of (x.fwdarw.(a,b, . . . , c)).

11. Let (s.sub.1,s.sub.2, . . . , s.sub.k) (a,b, . . . , c) denote the subset of outputs to which compatible paths through the distribution network have thus far been determined.

Let the elements of the set (P.sup.1.sub.si, . . . , P.sup.ri.sub.si) denote all the paths through the distribution network to output s.sub.i .epsilon.(s.sub.1,s.sub.2, . . . , s.sub.k) which are compatible with the existing paths through the distribution network (not considering previously determined paths to other outputs in (s.sub.1,s.sub.2, . . . , s.sub.k) (a,b, . . . , c)). Similarly, let the elements of the set (P.sup.1.sub.s, . . . P.sup.r.sub.s) denote all the paths through the distribution network to output s which are compatible with the existing paths through the distribution network (not considering previously determined paths to outputs in (s.sub.1,s.sub.2, . . . , s.sub.k) (a,b, . . . , c)). Let P.sub.si .epsilon.(P.sup.1.sub.si, . . . , P.sup.ri.sub.si) denote the path through the distribution network to output s.sub.i .epsilon.(s.sub.1,s.sub.2, . . . , s.sub.k) selected for use in the realization of (x.fwdarw.(a,b, . . . , c)) in a previous iteration of this algorithm.

Attempt to select one path from each of the sets of paths, (P.sup.1.sub.s1, . . . , P.sup.r1.sub.s1), (P.sup.1.sub.s2, . . . , P.sup.r2.sub.s2), . . . , (P.sup.1.sub.sk, . . . , P.sup.rk.sub.sk), and (P.sup.1.sub.s, . . . , P.sup.r.sub.s) such that the resulting set of paths is mutually compatible.

If such a selection of paths can be found, it represents a new set of connecting paths through the distribution network connecting input x to outputs (s.sub.1,s.sub.2, . . . , s.sub.k,s) (a,b, . . . , c). Go to step 10 after updating .GAMMA. by first adding into it, for each s.sub.i .epsilon. (s.sub.1,s.sub.2, . . . , s.sub.k) (a,b, . . . , c)), each DI.sub.q used in a P.sub.si that had been previously determined as the connecting path through the distribution network to the output s.sub.i and then deleting the DIr used in the newly selected connecting path through the distribution network to the output s.sub.i.

If no such selection of paths can be found, let

Comment: This step is reached if, using a path in the presentation network from input x through POi and into the broadcast hub through Bk, no DI.sub.q .epsilon. .GAMMA. can be found for which there is a compatible connecting path through the distribution network to output s relative to all other connecting paths that have been previously determined in iterations of the algorithm for the partial realization of (x.fwdarw.(a,b, . . . , c)). (s.sub.1,s.sub.2, . . . , s.sub.k) (a,b, . . . , c) denotes the subset of outputs to which compatible paths through the distribution network have thus far been determined. The paths to each si (s.sub.1, s.sub.2, . . . , s.sub.k) must be reconsidered to determine if alternative paths compatible with a path to output s can be found. If no such set of mutually compatible paths can be found, then either a new Bi.noteq.Bk, Bi.epsilon..SIGMA. must be selected as the broadcast module to which POi is connected or a new POj.noteq.POi, POj.epsilon..DELTA..sub.x must be considered for the path from input x into the broadcast hub. If no such Bi or POj is available, a complete realization of (x.fwdarw.(a,b, . . . , c)) is not possible given the current set of connecting paths through the presentation and/or distribution network and the operational restrictions under which connecting paths can be established.

12. STOP. A complete realization of (x.fwdarw.(a,b, . . . , c)) has been determined.

13. STOP. A complete realization of (x.fwdarw.(a,b, . . . , c)) is not possible given the current set of connecting paths through the presentation and/or distribution network and the operational restrictions under which connecting paths can be established.

In the example of (7.fwdarw.(k,p)) for the sake of simplicity, assume that POR.sub.7 POAV=POAV, DIR.sub.k DIAV=DIAV, and DIR.sub.p DIAV=DIAV. Then the control algorithm would execute as follows.

1. Given the requested broadcast connection (7.fwdarw.(k,p)),

2.

3. Choose PO2.epsilon..DELTA..sub.7.

4.

5. Choose B2.epsilon..SIGMA.

6.

7.

6.

7.

6.

8. .OMEGA..sub.7 =(k,p)

9. Choose output k.epsilon..OMEGA..sub.7. Select DI2.epsilon..GAMMA. where DI2.epsilon..theta..sub.k =(DI2,DI3,DI4). There is a compatible connecting path through the distribution network from DI2 to output k.

10. .OMEGA..sub.7 =.OMEGA..sub.7 -k=(p).

9. Choose output p.epsilon..OMEGA..sub.7. Select DI4.epsilon..GAMMA. where DI4.epsilon..theta..sub.p =(DI2,DI3,DI4) There is a compatible connecting path through the distribution network from DI4. .GAMMA.=.GAMMA.-DI4=(PO2,PO2,DI2,B1,B4,PO1,PO1,B2,PO4, PO4,B2,B3,P03,DI3,B1,B2)

10. .OMEGA..sub.7 =.OMEGA..sub.7 -p=.0..

12. STOP. A complete realization of (7.fwdarw.(k,p)) has been determined. It consists of the connecting paths (7.fwdarw.PO2.fwdarw.B2.fwdarw.DI2.fwdarw.k) and (7.fwdarw.PO2.fwdarw.B2.fwdarw.B4.fwdarw.DI4.fwdarw.p).

In general, depending on the connecting capabilities of the presentation and distribution network, and the structure and link threading of the broadcast modules in the broadcast hub, all broadcast assignment might not be realizable in a given network. However, if all broadcast assignments are realizable in a given broadcast network, then for any requested broadcast connection the network control algorithm specified above will always result in a complete realization. FIG. 23 shows a broadcast network 1000 utilizing a broadcast ring 1001 for which all broadcast assignments are realizable and for which the control algorithm always produces a complete realization for any requested broadcast assignment. Given any set of connecting paths implemented in the presentation network 1002 and distribution network 1004, the control algorithm can realize a new broadcast assignment or add to an existing broadcast assignment without any disturbance of the currently implemented paths. This illustrates that the network control algorithm fully utilizes the connecting capability of the broadcast network structure.

The above algorithm has been described from the perspective of realizing an entirely new broadcast assignment in the network. That is, the requested broadcast connection (x.fwdarw.(a,b, . . . c)) is such that input x is assumed to be not connected to any outputs before this broadcast connection is requested. If instead the request was to add an output to an already existing connection in the network, the algorithm could still be used and would operate similarly. For example, suppose (x.fwdarw.(a,b, . . . c)) existed and output d, d .epsilon. (a,b, . . . c), requested to join this broadcast connection. Since a connecting path from input x to the broadcast hub has already been established through some POi, .GAMMA. would be determined for this POi. Similarly, .theta..sub.a, .theta..sub.b, . . . .theta..sub.c and .theta..sub.d would be determined. The algorithm would then proceed as though the currently existing connecting paths for outputs a,b, . . . c represented a partial realization of (x.fwdarw.(a,b, . . . c,d)

A broadcast module can be constructed by using N:1 multiplexers which permit a single output to be connected to any one of the N inputs as controlled by log.sub.2 N control lines. The setting of the connections can be stored in buffers that connect directly to the multiplexers. These buffers are loaded from a serial control line through a 1:N de-multiplexer which permits a single input line to be connected to any one of N outputs as controlled by log.sub.2 N control lines.

FIG. 24 depicts such a broadcast module with 4 inputs (denoted 1, 2, 3, and 4) and 4 outputs (denoted a, b, c, and d). Each multiplexer has 4 inputs, 1 output and 2 control lines (denoted 1 and 0). The control information for each multiplexer 1010 is stored in a 2 bit buffer 1011. The buffer 1011 is loaded from line k through a 1:4 de-multiplexer 1014. The de-muliplexer has 1 input, 4 outputs, and 2 control lines (denoted 1 and 0). Clock lines are not shown in FIG. 24, but it should be understood that the control signal k is loaded into the appropriate buffer 1011 synchronized with a clock signal. The buffer 1011 which is loaded is determined by the signals on X and Y. When the 2 bit buffers 1011 are loaded, the connections from (1,2,3,4) to (a,b,c,d) are established. Clearly, broadcasting one input to more than one output can be accomplished by simply loading the 2 bit buffers 1011 controlling the multiplexers 1010 associated with those outputs, with the 2 bit binary number associated with broadcasting the input.

Although the invention has been described in detail in the foregoing embodiments for the purpose of illustration, it is to be understood that such detail is solely for that purpose and that variations can be made therein by those skilled in the art without departing from the spirit and scope of the invention except as it may be described by the following claims.