Time division multiplexing (TDM) is a useful technique for aggregating lower speed data streams into higher speed streams for transmission across a network. Typically, TDM traffic is used in connection-based, fixed bandwidth networks like the SONET data network. In such a network, alignment of data streams is crucial at switching nodes, since data is switched based on its arrival time. TDM switches typically operate based on a static setup that enables desired switching patterns. A new connection is serviced by creating a new data path through the network using control signaling outside the data path—the data path must be fully configured from end to end before any data can be transmitted. By contrast, packet-based or connectionless networks transmit data packets which include the address information required to enable each packet to reach its destination. Connectionless networks can dynamically adopt switching configurations to suit currently available packets. However, connectionless networks are subject to congestion problems if many packets which must share a network path are suddenly simultaneously received. Connection-oriented networks manage congestion perfectly, at the expense of wasted bandwidth if there is no traffic for an established connection.
TDM networks typically carry multiplexed traffic by allocating a portion of the total available connection time to each connection, based on some regular timing scheme. For example, a single SONET OC-12 connection is a multiplexed aggregate of 12 STS-1 connections. Each STS-1 connection is regularly allocated 1/12th of the total available connection time to serially transmit its next 8 bits (i.e. byte) via an optical connection, as specified in the SONET standard. Each STS-1 connection byte is referred to as a “grain” of that connection. 12 STS-1 connection grains aggregated to make up an OC-12 connection are called a “grain group.” Each grain group is numerically ordered, from the first to the twelfth grain of the corresponding STS-1s. A TDM switch typically accepts a number of multiplexed input connections and switches them, not as the aggregates it receives, but at some lower level, delivering newly reconstituted aggregates at its outputs.
TDM switches can be characterized by their capability to service arbitrary loads of connection requests (calls). For example, a switch is “non-blocking” if any load of calls can always be mapped successfully from the switch's input ports to the switch's output ports, regardless of any existing call load being serviced by the switch. A switch is “rearrangeably non-blocking” if servicing a new call may require rearrangement (without interruption) of existing calls to enable the switch to service a call that would otherwise be blocked. A “strictly non-blocking switch” can service any new load of calls, provided all of the switch inputs and outputs required to service the load are available (i.e. unused). A switch is “blocking” if there are possible existing call load states for which no input-to-output port mapping rearrangement will enable the switch to successfully map a new call load from the switch's input ports to the switch's output ports.
Strictly non-blocking switches require hardware proportional to the square of the number of inputs and the number of grains per input, or O(n2g2) where n is the number of inputs and g is the number of grains per input. Hardware complexity can be reduced to O(n2+g2) by using a so-called Clos architecture or its equivalent (Time:Space:Time or Space:Time:Space architectures, for example). But, such hardware savings compromise switching capability: the reduced hardware complexity switch is only rearrangeably non-blocking for unicast calls (i.e. a call in which one ingress grain is scheduled for delivery to one egress port); it is blocking for arbitrary loads of multicast calls (i.e. a call in which one ingress grain is scheduled for delivery to more than one egress port). Moreover, a scheduling algorithm must be used to determine how to route each new call through the reduced hardware complexity switch, taking into account all previously scheduled calls being handled by the switch. Hardware can be added to allow a switch to handle more calls—for example by increasing multicasting capability and eliminating the need to rearrange existing calls. But, regardless of whether a switch is strictly non-blocking for arbitrary loads of multicast calls, rearrangeably non-blocking for restricted widths of multicast calls (i.e. a call in which one ingress grain is scheduled for delivery to less than some predefined maximum number of egress ports), or simply blocking under certain conditions, physical limitations often prevent construction of switches of needed capacities.
In order to build larger switches, switching fabrics are formed by connecting switches together in regular patterns. One useful wiring pattern is a 3-stage fabric with 3 columns of switches regularly connected together, as shown in FIG. 1. The first stage (column) of the FIG. 1 fabric has n1 devices, each labeled <a,b> where a=1 and b=1, . . . , n1. The second (center) stage of the FIG. 1 fabric has n2 devices, each labeled <a,b> where a=2 and b=1, . . . , n2. The third stage of the FIG. 1 fabric has n3 devices, each labeled <a,b> where a=3 and b=1, . . . , n3. An output of each first stage device is connected to deliver a maximum input connection load of ti grains to an input of each center stage device. Each first stage device has a total input capacity it grains, and usually it≦n2·ti. An output of each center stage device is connected to deliver a maximum output connection load of to grains to an input of each third stage device. Each third stage device has a total output capacity ot grains, and usually ot≦n2·to.
Ideally, the center stage devices are designed so that they are non-blocking for whatever level of multicast calls the fabric is required to handle—all multicasting is handled by the center stage. Center stage devices with reduced multicasting capability can be used if corresponding degradation in multicast capability is acceptable. The first and third stage devices are designed so that they are non-blocking for unicast calls. The FIG. 1 fabric has an input speedup factor is=n2·ti/it, an output speedup factor os=n2·to/ot, a total input capacity of n1·it calls and a total output capacity of n3·ot calls. In some applications, is and os simultaneously have values greater than 1. In other applications, is or os, or both, simultaneously have values less than 1. Typically, a fabric's speedup is the same into and out of the center stage, in which case the fabric's overall speedup factor s=is=os. But, s can be expressed in different ways, one common example being s=min(is,os). Of course, if input capacity exceeds output capacity, then some switching capacity is unused. Conversely, if output capacity exceeds input capacity, additional output capacity can be “created” by multicasting calls to achieve full switching capacity usage. Although FIG. 1 shows only one connection between any two devices, persons skilled in the art will understand that each depicted connection represents aggregate connective capacity between two devices. In such fabrics, it is common to have multiple physical links connecting two switches. ti and to thus represent, respectively, total connection load capacity of all physical links into and out of the center stage.
The FIG. 1 fabric's aggregate bandwidth is equal to the lowest bandwidth of any of the 3 columns of switches. In this way, fabrics of arbitrary size can be built from any smaller sized switches. The 3-stage fabric is a conceptual organization that can take many real forms. For example, the first and third stage switches of a conceptual 3-stage fabric are often a single physical device. This allows a fabric's first and third stages to be located at a convenient ingress/egress point (physical ingress/egress connectors are often co-located). 3-stage fabrics are somewhat equivalent to Clos networks, in that they are not strictly non-blocking without impractical amounts of speedup, require a scheduling algorithm to derive a switch setting for scheduling a newly received call, and may require rearrangement of existing (i.e. previously scheduled) calls to facilitate scheduling of a newly received call.
For each newly received call, the scheduling algorithm examines the new call and the existing switch setting used to service the switch's existing call load, to determine a new switch setting that will preserve all existing end-to-end calls while permitting the new call to be scheduled. Here, “preserve” means that the inputs and outputs of each previously scheduled call are maintained in the new switch setting, although the internal path through the 3-stage fabric may differ (i.e. be rearranged). The optimal new switch setting is one that rearranges the fewest existing calls and leaves the fabric's latent (i.e. unused) switching capability evenly balanced among all switches. The problem of determining optimal switch settings for a 3-stage fabric is “NP-complete,” meaning that there is no known way to solve the problem other than generating all possible switching schedules and examining them to determine which one is optimal.
FIG. 2 depicts a simple 3-stage switching fabric for which n1=n2=2 and n3=3. The first stage has n1=2 switches, each of which is capable of receiving 3 grains on each of 4 input ports and outputting 6 grains on each of 2 output ports. The second stage has n2=2 switches, each of which is capable of receiving 6 grains on each of 2 input ports and outputting 4 grains on each of 3 output ports. The third stage has n3=3 switches, each of which is capable of receiving 4 grains on each of 2 input ports and outputting 2 grains on each of 4 output ports.
More particularly, each output port of each first stage device is connected to deliver ti=6 grains to an input port of each center stage device; and, each output port of each center stage device is connected to deliver to=4 grains to an input port of each third stage device. Each first stage device has a total input capacity it≦n2·ti=2·6=12 grains. Each third stage device has a total output capacity ot≦n2·to=2·4=8 grains. The FIG. 2 fabric has an input speedup factor is=n2·ti/it=2·6/12=1, an output speedup factor os=n2·to/ot=2·4/8=1, an overall speedup factor s=is·os=1·1=1, a total input capacity n1·n2·ti=2·2·6=24 calls and a total output capacity n3·n2·to3·2·4=24 calls.
In the particular situation depicted in FIG. 2, switch <1, 1> has received at its input port 1 an input signal consisting of grain A assigned to a first ingress timeslot, nothing assigned to a second ingress timeslot, and grain B assigned to a third ingress timeslot. At its input port 2, switch <1, 1> has received an input signal consisting of nothing assigned to the first ingress timeslot, grain C assigned to the second ingress timeslot, and grain D assigned to the third ingress timeslot. At its input port 3, switch <1, 1> has received an input signal consisting of grain E assigned to the first ingress timeslot, and nothing assigned to the second or third ingress timeslots. At its input port 4, switch <1, 1> has received an input signal consisting of nothing assigned to the first ingress timeslot, grain F assigned to the second ingress timeslot, and grain G assigned to the third ingress timeslot. Switch <1, 1> rearranges its input signals by reassigning (unicasting) grains A and B to its output port 1's egress timeslots 3 and 5 respectively, reassigning grain C to output port 2's egress timeslot 1, reassigning grains D and E to output port 1's egress timeslots 6 and 2 respectively, and reassigning grains F and G to output port 2's egress timeslots 3 and 4 respectively.
Switch <1,2> has received at its input port 1 an input signal consisting of grain H assigned to the first ingress timeslot, grain I assigned to the second ingress timeslot, and grain J assigned to the third ingress timeslot. At its input port 2, switch <1,2> has received an input signal consisting of grain K assigned to the first ingress timeslot, and nothing assigned to the second or third ingress timeslots. At its input port 3, switch <1,2> has received an input signal consisting of grain L assigned to the first ingress timeslot, grain M assigned to the second ingress timeslot and nothing assigned to the third ingress timeslot. At its input port 4, switch <1,2> has received an input signal consisting of nothing assigned to the first or second ingress timeslots, and grain N assigned to the third ingress timeslot. Switch <1,2> rearranges its input signals by reassigning (unicasting) grains H and I to its output port 2's egress timeslots 3 and 6 respectively, reassigning grain J to output port 1's egress timeslot 1, reassigning grain K to output port 2's egress timeslot 5, and reassigning grains L, M and N to output port 1's egress timeslots 5, 4 and 3 respectively.
Output port 1 of switch <1, 1> is connected as aforesaid to deliver ti=6 grains to input port 1 of switch <2, 1>, output port 2 of switch <1, 1> is connected to deliver ti=6 grains to input port 1 of switch <2,2>, output port 1 of switch <1,2> is connected to deliver ti=6 grains to input port 2 of switch <2, 1>, and output port 2 of switch <1,2> is connected to deliver ti=6 grains to input port 2 of switch <2,2>.
Switch <2,1> rearranges its input signals by 2-casting grain A to its output port 2's egress timeslot 1 and to its output port 3's egress timeslot 4, unicasting grain B to output port 2's egress timeslot 4, unicasting grain D to output port 1's egress timeslot 2, 3-casting grain E to its output port 1's egress timeslot 1 and to its output port 2's egress timeslot 2 and to its output port 3's egress timeslot 3, 2-casting grain J to its output port 2's egress timeslot 3 and to its output port 3's egress timeslot 2, unicasting grain L to output port 3's egress timeslot 1, and unicasting grains M and N to output port 1's egress timeslots 4 and 3 respectively.
Switch <2,2> rearranges its input signals by 3-casting grain C to its output port 1's egress timeslot 2 and to output port 2's egress timeslot 3 and to output port 3's egress timeslot 1, 2-casting grain F to output port 1's egress timeslot 1 and to output port 2's egress timeslot 1, unicasting grain G to output port 2's egress timeslot 2, 2-casting grain H to output port 1's egress timeslot 4 and to output port 3's egress timeslot 3, and unicasting grains I and K to output port 3's egress timeslots 4 and 2 respectively.
Output port 1 of switch <2, 1> is connected as aforesaid to deliver t0=4 grains to input port 1 of switch <3, 1>, output port 2 of switch <2, 1> is connected to deliver to=4 grains to input port 1 of switch <3,2>, output port 3 of switch <2, 1> is connected to deliver to=4 grains to input port 1 of switch <3,3>, output port 1 of switch <2,2> is connected to deliver to=4 grains to input port 2 of switch <3,1>, output port 2 of switch <2,2> is connected to deliver to=4 grains to input port 2 of switch <3,2>, and output port 3 of switch <2,2> is connected to deliver to=4 grains to input port 2 of switch <3,3>.
Switch <3, 1> rearranges its input signals by reassigning (unicasting) grains F and M to its output port 1's egress timeslots 1 and 2 respectively, reassigning grains D and N to output port 2's egress timeslots 1 and 2 respectively, reassigning grain H to output port 3's egress timeslot 1, and reassigning grains C and E to output port 4's egress timeslots 1 and 2 respectively.
Switch <3,2> rearranges its input signals by reassigning (unicasting) grains F and A to its output port 1's egress timeslots 1 and 2 respectively, reassigning grains G and C to output port 2's egress timeslots 1 and 2 respectively, reassigning grains E and B to output port 3's egress timeslots 1 and 2 respectively, and reassigning grain J to output port 4's egress timeslot 2.
Switch <3,3> rearranges its input signals by reassigning (unicasting) grains H and J to its output port 1's egress timeslots 1 and 2 respectively, reassigning grains I and C to output port 2's egress timeslots 1 and 2 respectively, reassigning grains K and L to output port 3's egress timeslots 1 and 2 respectively, and reassigning grains A and E to output port 4's egress timeslots 1 and 2 respectively.
To be entirely unambiguous, a call must be specified in terms of its associated input device, port and timeslot; and, its associated output device(s), port(s) and timeslot(s) parameters. A unicast call can be specified as X:(w→x), a 2-cast call can be specified as X:(w→x, y) and a 3-cast call can be specified as X:(w→x, y, z) where X is the label of the call that originates at <stage, device, port, timeslot>w and is received at <stage, device, port, timeslot> x, y and z respectively. Call labels are analogous to grains. Thus, in FIG. 2, each letter-labeled grain represents a different call. The calls currently scheduled on the FIG. 2 fabric are:
A:(<1,1,1,1>→<3,2,1,2>, <3,3,4,1>)
B:(<1,1,1,3>→<3,2,3,2>)
C:(<1,1,2,2>→<3,1,4,1>, <3,2,2,2>, <3,3,2,2>)
D:(<1,1,2,3>→<3,1,2,1>)
E:(<1,1,3,1>→<3,1,4,2>, <3,2,3,1>, <3,3,4,2>)
F:(<1,1,4,2>→<3,1,1,1>, <3,2,1,1>)
G:(<1,1,4,3>→<3,2,2,1>)
H:(<1,2,1,1>→<3,1,3,1>, <3,3,1,1>)
I:(<1,2,1,2>→<3,3,2,1>)
J:(<1,2,1,3>→<3,2,4,2>, <3,3,1,2>)
K:(<1,2,2,1>→<3,3,3,1>)
L:(<1,2,3,1>→<3,3,3,2>)
M:(<1,2,3,2>→<3,1,1,2>)
N:(<1,2,4,2>→<3,1,2,2>)
FIG. 3A shows the FIG. 2 fabric carrying calls:
A:(<1,1,1,1>→<3,1,1,1>1)
B:(<1,1,1,2>→<3,1,1,2>)
C: (<1,1,1,3>→<3,1,2,1>)
D:(<1,1,2,1>→<3,1,2,2>)
E:(<1,1,2,2>→<3,2,1,1>)
F:(<1,1,2,3>→<3,2,1,2>)
G:(<1,2,1,1>→<3,2,2,1>)
H:(<1,2,1,2>→<3,2,1,2>)
I:(<1,2,1,3>→<3,2,3,1>)
J:(<1,2,2,1>→<3,2,3,2>)
K:(<1,2,2,2>→<3,3,1,1>)
L:(<1,2,2,3>→<3,3,1,2>).
Suppose that a new call M:(<1,1,3,1>→<3,2,4,1>) is to be scheduled on the FIG. 3A fabric. That new call cannot be routed through switch <1, 1> to switch <3,2> even though input port 3 of switch <1, 1> is unused and output port 4 of switch <3,2> is unused. This is because the connection between switch <1, 1> and switch <2, 1> is already carrying its maximum of ti=6 grains and the connection between switch <2,2> and switch <3,2> is already carrying its maximum of to=4 grains. Similarly, a new call N:(<1,2,3,1>→<3,1,4,1>) cannot be routed through switch <1,2> to switch <3, 1> even though input port 3 of switch <1,2> is unused and output port 4 of switch <3,1> is unused, because the connection between switch <1,2> and switch <2,2> is already carrying its maximum of ti=6 grains and the connection between switch <2, 1> and switch <3, 1> is already carrying its maximum of t0=4 grains. Potentially available switching capacity via unused input ports 3, 4 of switch <1, 1> to unused output port 4 of switch <3,2> and similar capacity from unused ports of switch <1,2> to switch <3, 1> is thus wasted, reducing the fabric's overall scheduling capability unless the existing call load can be rearranged to improve the fabric's scheduling capability. Such rearrangement is not always possible. It can thus be seen that even if a 3-stage fabric is constructed of strictly non-blocking switching devices, the overall fabric can be blocking, due to the foregoing connection allocation problem.
FIG. 3B shows the FIG. 2 fabric carrying the same call load as in FIG. 3A, but with the load evenly balanced between each first and second stage switch and between each second and third stage switch. Specifically, the load between switch <1, 1> and switch <2, 1> is 3 grains, as is the load between switch <1, 1> and switch <2,2>, the load between switch <1,2> and switch <2, 1> and the load between switch <1,2> and switch <2,2>. The load between switch <2, 1> and switch <3, 1> is 2 grains, as is the load between switch <2,2> and switch <3, 1>; the load between switch <2, 1> and switch <3,2> is 3 grains, as is the load between switch <2,2> and switch <3,2>; and, the load between switch <2, 1> and switch <3,3> is 1 grain, as is the load between switch <2,2> and switch <3,3>. Thus, although the FIG. 3B fabric is carrying the same call load as the FIG. 3A fabric, the FIG. 3B fabric can carry the new call M:(<1,1,3,1>→<3,2,4,1>) whereas the FIG. 3A fabric cannot.
For example, because the load between switch <1, 1> and switch <2, 1> is less than ti=6 grains and the load between switch <2, 1> and switch <3,2> is less than to=4 grains, call M:(<1,1,3,1>→<3,2,4,1>) can be routed through switch <1, 1> to switch <2, 1> and thence to switch <3,2>. Alternatively, because the load between switch <1, 1> and switch <2,2> is less than ti=6 grains and the load between switch <2,2> and switch <3,2> is less than to=4 grains, call M:(<1,1,3,1>→<3,2,4,1>) could be routed through switch <1, 1> to switch <2,2> and thence to switch <3,2>. Similarly, call N:(<1,2,3,1>→<3,1,4,1>) could be routed through switch <1,2> to switch <2, 1> and thence to switch <3,2>; or, through switch <1,2> to switch <2,2> and thence to switch <3,2>.
This invention facilitates call load balancing to improve a switching fabric's connection scheduling capability.