Serial Array Time Slot Interchangers and Optical Implementations.
We consider time slot interchangers (TSIs) which are built from 2/spl times/2 exchange switches and delays and which are useful for time division multiplexed (TDM) systems in telecommunications and pipelined systems such as time multiplexed optical multiprocessors. We formulate a general method for constructing TSIs based on multistage interconnection networks in the space domain via space-to-time mapping. Two types of TSIs, time slot permuters and time slot sorters, are considered. We review the time slot permuter based on the Benes network, and obtain the /spl Lambdaspl tilde/ time slot permuter based on the bit-controlled, self-routing /spl Lambda/ permutation network. The time slot sorter, S/sub N/, is obtained from the Batcher spatial sorting network. The generalized Lambda time slot permuter /spl Lambdasub Nsup q/ is obtained, in an algorithmic approach, by combining the idea of the /spl Lambdaspl tilde/ time slot permuter and Q-way bitonic decomposition (Q=2/sup q/). The numbers of switches, control complexities, and frame delays of these architectures are compared, and the problem of crosstalk in optical implementation is discussed. It is shown that control complexity can be traded against the number of switches.
Introduction
The need to reorder data transmitted serially in time appears in nearly every complex
serial digital system. The most extensive use is probably in time division multiplexed
(TDM) communications. Using TDM terminology, a frame consisting of N time
slots identifies an data packet contained in a slot by its sequential position with respect to
the start of the frame. Switching among communications channels corresponds to changing
the relative order of time slots in the frame. With the increasing use of optics in com-
munications, photonic techniques for TDM switching have attracted a great deal of
interest [1]. Additional interest comes from the design of a serial optical computer [2], in
which words in a serial memory [3] can be considered as time slots in a fixed length
frame. Time multiplexing multiple computers on the same serial hardware, as proposed
in [4], establishes a correspondence between time slot interchange and multiprocessor
interconnection networks. The availability of optical exchange switches and the ease of
implementing optical delay by fiber encourages the study of time slot interchangers built
from 2-2 exchange switches and delays.
We take a time slot interchanger (TSI) to be a system with one serial input consisting
of a fixed length frame of N time slots and producing one serial output frame of the
same time slots in a permuted order. We consider only systems with frame integrity, so
output slots for a given input frame are adjacent, with no intervening gaps. Any such
system performing a non-trivial permutation must have an associated frame delay, since
a slot can only move toward the beginning of the frame without violating input before
output ordering if the beginning of the frame is delayed. The maximum required frame
delay is N -1 slot intervals, corresponding to the last slot of the input becoming the first
slot of the output frame. Thompson [5] described a time slot interchanger using order N
optical switches and delay lines. Ramanan, Jordan and Sauer [6] demonstrated an architecture
using only 2log 2 N - 1 switches and delay lines which was capable of performing
an arbitrary permutation of N time slots. Hunter and Smith [7] have considered multiple
TDM channel switching using the same optical elements.
In this paper we consider TSIs based on multistage interconnection networks in the
space domain, e.g., [8]. The mapping to switch and delay line structures is based on a
single switch and delay line stage able to do elementary permutations. Several architectures
with differing numbers of switches and control complexities are developed and
compared with respect to these features and other aspects of their optical implementa-
tions. The paper is limited to time domain permutation, but the same techniques can
yield networks to permute multiple time slots on multiple space channels [9].
II. Serial Array Time Slot Interchangers
The TSIs described are derived from a simple stage capable of selectively interchanging
pairs of time slots. A correspondence theorem and mapping procedure allow
time division switching structures to be derived from corresponding space division net-
works. TSIs based on the Benes v
, Batcher, and L networks lead to distinctly different
switch counts and control complexities. The TSIs derived from the Benes v and Lambda
networks are permuters, which perform any of the N ! permutations of an N slot frame.
The TSI derived from the Batcher network is a sorter which sorts time slots based on a
key in their header.
II.1 The K stage
The TSIs treated here consist of stages, each of which is made up of a 2-2 exchange
switch with one output fed back to one input through a fixed length delay. An optical
implementation can use a switched directional coupler and fiber delay. An electronic
stage, with logic gates for exchange and a shift register for delay, is also possible. Figure
1 shows the permutation capability of one such stage, which we call a K stage. The
switch is a five terminal device, but the control input is not shown. The electrical or optical
control signal sets the exchange switch in the cross "x" or bar "=" state during each
slot time D.
If the switch is always in the cross state, the output will be the input delayed by D.
If the switch is placed in the bar state during the second of a pair of time slots to be
exchanged, the output stream of numbered time slots will correspond to the input stream
delayed by one slot time with the appropriate pair exchanged. Figure 1 shows the control
inputs to exchange pairs (2,3) and (6,7). If D is more than one slot, non-adjacent pairs
can be exchanged.
It is clear that multiple disjoint pairs of a frame can be exchanged. What happens
when the switch is in the bar state for overlapping pairs is shown by characterizing the K
stage by a two dimensional diagram called a cascade branch, shown in Fig. 2 for a one
slot delay. Time is represented by the vertical axis and each temporal switching point as
a separate exchange switch. Information routed vertically represents that passed through
the delay line to the next time point. Horizontally routed information passes to the output
of the K stage. For ease of diagramming, the cross state of a switch in the cascade
branch diagram corresponds to an "=" control at the corresponding K stage control time,
and the bar state to an "x" control.
A K stage maintains frame integrity if and only if its first and last control inputs are
"x", corresponding to the bar state of the top and bottom cascade branch switches. The
serial array interchangers described maintain frame integrity in each stage so that the property
follows immediately between input and output to the whole array.
K (D)
Input
Control Seq. x x x # x x x # x

Figure

1: K stage with pair exchange capability
bar
state
cross
state
c ="-"
c ="="
K (1)#

Figure

2: Cascade branch representation of a K stage
The serial array architectures use delays which are multiples of one slot time and
will be labeled with the integer multiple. Input slots are partitioned by a K stage with
delay greater than one into disjoint sequences of interacting slots, and the cascade branch
diagrams change as in Fig. 3. If K (M ) is a K stage with feedback delay of M slot times,
I3
I4
I6
I3
I4
I6
I3
I4
I6
O2
O3
O4
O6
O2
O3
O4
O6
O2
O3
O4
O6
Figure

3: K stages for different feedback delays
then it partitions a frame of groups of q interacting slots, with
successive slots in a group separated by M slot times. A K (M ) stage must start and end
its sequence of control inputs with M "x"s to maintain frame integrity.
The cascade branch shows that a K stage has permutation capability beyond pair
exchange, but all of the architectures we consider in this paper restrict its use to exchanging
disjoint pairs. Reasons for doing this include limiting the number of times a slot
traverses a potentially lossy switch and allowing the use of the feedback free K stage
discussed in Sect. II.3. In addition, attempts to use the more general permutation capability
of the feedback K stage have not yielded significantly improved architectures. An
architecture to perform two way perfect shuffle of N inputs using #log 3 N # stages [10] is
an interesting exception. The restriction to pair exchange is imposed by fixing "x" controls
at times in addition to those required by frame integrity, so that the cascade branch
separates into disjoint pair exchanges, each controlled by the K stage control input at a
control point.
Even divisibility of N by M is assured if we restrict both N and M to powers of
two, Frame integrity and the restriction to exchange of disjoint
pairs fix the switch control C t of a K (M ) stage to "x" at times
Frame
Disjoint pairs: 2iM - t - (2i +1)M -1, 1 -i - N /(2M ).
This leaves N /2 slot times, or control points, where the control input can be freely
chosen as "=" to exchange a pair of slots separated by M or as "x" to maintain the original
order. The control point times are:
Control points: (2i
th control point: t
Summarizing, the results to be used in the following time domain permutation
schemes rely on the definition of a K stage and its pair interchange property.
stage with delay D performs one of two operations on a pair of time
slots arriving at its input and separated by time D. It either outputs both 1st and 2nd slots
delayed by D, or it delays the 1st slot by 2D and transmits the 2nd slot with no delay.
Theorem: If a frame of N time slots is applied to a K stage with an associated delay
D of an integral number of time slots, pairs of slots in the frame separated by D can be
selectively exchanged while maintaining frame integrity.
II.2 A space to time mapping scheme
The above discussion leads to a mapping of a class of space division switching networks
onto corresponding time division switching structures. The following definition
and lemma establish a correspondence between the K stage and a space division switch.
We restrict the discussion to (N -N ) switching networks using (2-2) exchange switching
elements (SEs) and restrict
Definition 1: A transposition unit, denoted by T N
M , N even, 1 - M - N /2, is a
switching stage consisting of a column of N /2 SEs connected as follows: the first unconnected
pair of input ports (i , i +M ) of the stage are connected to the inputs of an SE
whose outputs are connected to the pair of output ports (i , i +M ) of the stage.
The transposition unit implements a product of disjoint pair transpositions. If E is
just a column of N /2 SEs, then
1 . If s N is the perfect shuffle permutation, then
N /2 can be written s N Es N
representing N /2 SEs with a shuffle connection in front
and an unshuffle in back. We deviate here from the standard mathematical notation by
composing permutations from left to right rather than right to left. This gives a direct
correspondence to spatial permutation networks with inputs on the left and outputs on the
right. Notationally then, a permutation is applied to an input vector standing on its left to
produce an output vector. Exchanging shuffle and unshuffle gives s N
.
Lemma 1: The transposition unit T N
M in the space domain can be implemented in the
time domain by an exchange stage K (M ). (See Fig. 4.)
Theorem 1: A time slot interchanger can be obtained from any space division
switching network built entirely on transposition units.
We describe several space domain networks to which Theorem 1 is applicable,
either because they are already based on transposition units or because they can be
modified so that each building block is a transposition unit. Versions of the Benes v net-work
and sorting networks will be covered.
In summary, the method for obtaining a time slot interchanger is as follows.
# Identify a switching network whose basic building blocks are either transposition
units T N
M or can be replaced by them.
# Replace each T N
M with a K (M ). Each K (M ) emulates N /2 SEs and its control can
be derived from that of the SEs. The i th control point value for the K stage is
determined by the control of the i th SE.
II.3 Delay considerations in a K stage
Frame delay is an important characteristic of a TSI which does not apply to space
domain switches. A K (M stage restricted to exchanging disjoint pairs and to maintaining
frame integrity introduces a frame delay of M . If several such stages are connected
into a linear array, the whole array maintains frame integrity and has a frame delay equal
Figure

4: Transposition units and corresponding K stages
to the sum of its stage delays. The description of the K stage tacitly assumed that all
delay was associated with the explicit feedback delay. This is true for low speed opera-
tion, when the delay through the exchange switch can be neglected, but switch delay can
become significant for high speed operation. If the switch in Fig. 1 has a delay of D
between any input and output and D< D, then reducing the explicit delay to D-D yields
a K stage which performs as before, except for an increased frame delay of D+D .
However, if D> D, the K stage of Fig. 1 can no longer exchange slots separated by
time D. A modified K stage requiring an extra exchange switch accommodates arbitrary
switch delay and still exchanges slots separated by D. Figure 5 shows a lumped delay
diagram of such a K stage. The delay d in the figure can be chosen arbitrarily. If
disappears into the switch delays, except for its use to delay the control
input of the second switch. In a fiber optic implementation, d must also accommodate
the delay in interconnecting fibers and that of the 3dB coupler used to fan out the input.
The frame delay through the modified, feed forward K stage of Fig. 5 is d+D. If d is
measured in units of a slot time, then the frame delay for the modified stage is d+M . The
K stage of Fig. 5 does not have the full switching capability of the cascade branch shown
in Fig. 2, but it is equivalent for disjoint pair exchanges.
II.4 The RJS time slot permuter
The Benes v
network [11] is a space division permutation network which can be
modified to use only transposition units as building blocks. Its corresponding time
domain structure was reported by Ramanan, Jordan and Sauer [6], and we review this
time slot interchanger in the context of this paper.
Note that T N
can be accomplished by a single (2-2) optical switch
with delay N /2, K (N /2), for N even. The (N -N ) Benes v
network b N is
In order to introduce transposition units, consider the modified Benes v network b - N with
inputs and outputs renumbered,
d
d+D
d
In
Out
Control

Figure

5: K stage accommodating long switch delay
N /2 .
Note that if M divides N /2 evenly, then
M and of course #
Thus the modified Benes v network can be shown by recursive application of the above
construction to consist entirely of transposition units,
N /4 . T N
N /2 .
The mapping procedure yields the RJS time slot permuter consisting of (2n -1) K stages,
By modifying the Benes v construction to recursively partition into odd and even
input and output sets instead of upper and lower numbered halves, a second form of the
Benes v network in both time and space domains can be obtained as
. T N
N /2 . T N
There is little difference between b - N and b - N in the space domain. Both require the same
number of 2-2 switches. In the time domain, however, because each K (M ) contributes a
frame delay of M , the total delay of b - N is (2N - times while that of b - N is only
times. This makes b - N preferable as a time slot permuter. The frame
delay may have an additional contribution of d time slots per stage if the feed forward
form of the K stage is used. The total frame delay of b - N would then be
(b - N
The control inputs to each SE of the space division networks b - N and b - N are
obtained by simple modifications of the Benes v
looping control algorithm [12]. The input
to the SE in position i of column j directly determines the control of the j th K stage at
the i th control point. Control point times are measured from the entry of the frame into
that K stage.
II.5 Time domain sorting network: S N
As the K stage of Fig. 1 forms the basis for the RJS permuter, a K stage with control
derived from the comparison of destination tags contained in two time slots can form the
basis for time domain sorting. Continuing to restrict K stages to pairwise exchange, the
state at a control point is determined by comparing the tag of the time slot entering the
stage with that of the slot emerging from the delay. The cross or bar choice ensures that
the slot with the lower tag emerges first (second) for a sort in increasing (decreasing)
order.

Figure

6 shows such a comparison controlled K stage and the corresponding
space domain comparator to which it corresponds. Not shown are additional
delays necessary to allow control to be determined before the time slots reach the switch.
These are easily incorporated, and may be small for long time slots with short leading
tags. A simple time domain sorter is based on the well known Batcher sorting network
[13], which is in turn based on the Batcher bitonic sorting network. A brief review of the
A
A

Figure

Time domain 2-2 magnitude comparator
Batcher sorter and bitonic sorter lays the foundation for the time domain version. A
bitonic sorting network is a multistage network which can sort a bitonic sequence, and is
essentially a concatenation of an ascending and a descending monotonic sequence.
Definition 2: A basic bitonic sequence is a concatenation of two monotonic
sequences, one ascending and one descending.
Definition 3: A bitonic sequence is one obtained by a cyclic shift of a basic bitonic
sequence.
Sorting of a bitonic sequence is based on the ability to rearrange a bitonic sequence
into two bitonic sequences of equal length such that all members of one sequence are less
than or equal to all members of the other.
Definition 4: The bitonic decomposition, D N , of a bitonic sequence of N numbers is
a rearrangement of the given bitonic sequence into a monotonic sequence of two bitonic
sequences of equal length.
The bitonic decomposition can be accomplished by a shuffle permutation followed by a
stage of N /2 magnitude comparators followed by an inverse shuffle. We will use the previous
notation sEs
N /2 for such a structure, understanding that now the individual
2-2 SEs of E are controlled by magnitude comparison.
The Batcher bitonic sorting network B N
* is defined recursively as

and since D
N /2 , it can be represented in terms of transposition units:
N /4 . T N
1 .
The Batcher sorting network sorts the first and second halves of the input sequence
in ascending and descending order, respectively, to obtain a bitonic sequence. The
resulting bitonic sequence is then sorted using the Batcher bitonic sorter. If B N and B # N
are Batcher sorting networks for ascending and descending order, respectively, then
* .
A two elements sequence is bitonic, so
1 starts the recursion.
If we suppress information, readily derived from the original recursive definition,
about whether a given comparator of a stage sorts in increasing or decreasing order. The
Batcher sorting network in terms of transposition stages has the form
N /4 . T N
1 .
The number of switching stages of B N , each consisting of N /2 comparators is
s
and each stage consists of N /2 two input magnitude comparators.
The time slot sorter based on the Batcher sorter is obtained by replacing each T N
M by
a K stage with comparison based control. The time domain bitonic sorter is just
and the general time slot sorter is defined recursively as

where S N /2 sorts in increasing order for the first half frame and in decreasing order for the
second half. The time slot sorter thus has n (n +1)/2 K stages, consisting of one switch,
one delay line and one comparator each. The general form can be represented as
It remains only to determine whether the output of the magnitude comparator specifies
increasing or decreasing ordering of the time slots at each control point.
In the space network, number comparators from top to bottom as
Then increasing or decreasing output is determined by the stage number and the comparator
number. In the time slot sorter, 0 - j < N /2 numbers the control points for the
stage. Using the fact that
* and

both sort in the same order, we obtain a regular pattern for increasing or decreasing order
exchange at each control point. There are n groups successive stages with
every stage in a group having the same exchange order pattern. Group q , 0 - q < n ,
consists of stagesq (q +1)
where stages are numbered from left to right starting at zero. For the N /2 control points
in each stage of group q , sorting is in increasing order for control point j if
and in decreasing order for control point j if
# .
An example of a time slot sorter for a frame of 8 slots with the sorting order for each
control point is shown in Fig. 7.
The frame delay associated with a time slot sorter consists of at least two parts.
First, there is the sum over all stages of the delay of M slots associated with a K (M
stage. Second, there is a delay, say h , necessary to prevent the time slot entering the
stage from arriving at the switch of Fig. 6 before the output of the comparator is deter-
mined. Since h is a fraction of a slot time, the corresponding delay for the time slot
emerging from the feedback does not contribute to frame delay because it is subsumed in
the feedback loop delay. In addition, if the feed forward K stage, modified to account for
switch delay, is used, there will also be a d term added to the frame delay per stage. The
general form of the frame delay for the bitonic time slot sorter is
f (S N
and for the general time slot sorter it is
f (S N
In summary, the time slot sorter has the advantages of having the control done
independently at each switch on the basis of a destination tag and of performing a sort on
the tags rather than a strict permutation. These advantages are obtained at the cost of
stages as opposed to 2n -1 for the RJS permuter. The frame delay is about
2N compared to about 3N /2 for the RJS permuter. Control is determined by simple
comparison and the sorting order pattern at the stage.
II.6 Single bit controlled time domain permuter: L - N
The time domain version of the Batcher sorter, S N , eliminates the need for precomputing
switch control but requires an n bit comparator to control each switch. By using a
time domain equivalent of the Lambda permutation network [14], switch control can be
reduced to testing a single bit of the header of the time slot emerging from the feedback
delay.

Figure

8 shows the structure of the switch control required. The latch is triggered
d
d
d
d
d
d
Control
Point
Sorting decreasing

Figure

7: Time slot sorter and control for
Latch

Figure

8: Bit controlled feedback exchange stage, K (D, d k )
at the beginning of slot times corresponding to control points and uses either the input bit
or its complement to set the exchange state, depending on whether increasing or decreasing
order output is needed. If the delay D is an integral number of slot times, and b is the
time for one bit, then the switch is controlled by bit d k of the header,
assuming that the header bits arrive low order bit first. An increasing order bit controlled
stage, K (D, d k ), causes the time slot emerging from the delay to exit the stage immediately
and to be delayed once more if d stage, K (D, d # k ), reverses the
procedure for a decreasing order output.
If the destination tags of the time slots have binary representations
the L network is built up of the Batcher bitonic sorters
described in the previous section, except that they use only a single bit of d as a sort key.
It is important to note that two time slots can be ordered on a single bit by observing only
one of them. If the key bit is zero the slot is assigned to the lower output position, which
will be demanded if the bit of its paired time slot is one and will be acceptable if it is
zero. Similarly, a key bit of one directs the slot to the higher output position. We thus let
Batcher sorter which uses the single header bit d k as a key.
The L network is constructed recursively using the formula
# L N /2
The L N /2 subnetworks permute using only bits d n -2 . d 1 d 0 of the destination tags. The
permutation capability of the L network results from the fact that the bitonic decomposi-
tion, D N (d n -1 ), will leave the N /2 destination tags with d n in the lower half and the
N /2 with d n in the upper half of the output array. L N can thus be built from transposition
units and mapped into the time domain by replacing each D R (d k ) or D R (d # k ) by
K (D, d k ) or K (D, d # k ), respectively. The recursive structure of the L time slot permuter,
L - N , is given by
For example, the L time slot permuter for eight slots can be written
where d - k is either d k or d # k for the correct sorting order. In general,
The number of stages of the L network is calculated from the recurrence
s (L N
starting with s (L This results in
s (L N
The number of stages of the L network is the number of K stages, and hence the number
of 2-2 switches in the L time slot permuter.
The frame delay of the L time slot permuter follows from the recurrence
the frame delay of the time slot sorter, and the frame delay for single K stages,
f (K (R d. The added delay of d per stage applies in case the feed-forward version
of the K stage is used, but the extra delay h for header interpretation is subsumed by
the feedback delay. The result is
The substructure of the serial array L - N establishes the sorting order for a stage and
control point. The array is divided into n -1 groups according to the index i in the outer
product, followed by one final stage which always sorts in increasing order
on bit d 0 . Group i consists of i (i stages, all of which sort on bit d i . Each
major group is partitioned into a rightmost stage and i subgroups consisting of, from left
to right, 1, 2, ., i stages in each subgroup. Using to number from left to
right, starts at stage
Again numbering from left to right, stage w is the left
stage of subgroup q of group u . The unique rightmost stage of group u always sorts in
increasing order. For the subgroups of group i , the sorting order at different control
points is as described for the time slot permuter S 2 i . In particular, stages
constitute subgroup q of group u . For any stage in a subgroup indexed by q , sorting is
in increasing order at control point j , 0- j <N /2, if
and in decreasing order for control point j if
# .
The sorting order described above is shown for the L - Fig. 9.
The main advantage of the L network is distributed control using one bit of the destination
of one entering slot. The network does not sort; the destination tags must
represent a permutation. Bit control comes at a cost of n (n 2 +5)/6 K stages and a frame
delay of about 3N .
II.7 Multiple bit controlled time domain permuter: L - N
The time slot sorter S N and the time slot permuter L - N are controlled by comparing
all bits of the destination tags and examining one bit of one tag, respectively. In the q -bit
controlled L - N
q each instance of a switch setting is determined by a q -bit comparison of
input destination tags. Thus the local control complexity of L - N
q varies from n -bit comparison
of S N to a single bit control of L - N , while the hardware complexity varies from
O (n 2 ) to O (n 3 ). The complexity of the q -bit comparison is O (1) if the data is presented
serially, but trade-offs are possible if data and tags have some parallelism. We obtain L - N
directly from the Q -way bitonic decomposition
Definition 5: A Q-way bitonic decomposition of a bitonic sequence C of length
N =QP is an arrangement of elements of C yielding a sequence C
. C - Q
where each component C - i is a bitonic sequence of length P and the sequence of the sets
Lemma 2: Let C be a bitonic sequence of length N =QP . Let C
subsequences of C consisting of the smallest P elements of C , the next smallest P ele-
ments, and so on. Then C
. C - Q is a Q -way bitonic decomposition of C and
Proof: See [15].

Figure

9: The L - 16 network and sorting orders
To avoid the sequential construction of Lemma 2 a parallel construction of a Q -way
bitonic decomposition of a bitonic sequence of QP elements is possible by rearranging in
ascending (or descending) order each of the P subsequences consisting of every P th element
of the given sequence. In the row-ordered, Q-P matrix representation of the
sequence, this is just sorting each column separately [15]. The lemma for the Q=2 case
was given in [13], and the proof for the general case was given in [15], based on the
zero-one principle.
Lemma 3: (Q -way bitonic decomposition) Let
. C Q be a bitonic
sequence of length
Q be the sequence obtained by
sorting
Q in ascending order, and let C
. C - Q is
a Q -way bitonic decomposition of C and C - 1 -C - 2 -C - Q .
Note that Definition 4 of Sect. II.5 gives a 2-way bitonic decomposition.
Corollary 1: (2 q -way bitonic decomposition) A 2 q -way bitonic decomposition of
a bitonic sequence of length obtained by recursive application of 2-way
decomposition q times. In particular, a bitonic sequence of elements is sorted by
recursively applying the 2-way bitonic decomposition n times.
In particular, given a bitonic time sequence, the 2 q way bitonic decomposition can
be performed by a serial array of q K stages
Corollary 2: (Decomposition of a permutation) Given a sequence as a permutation
of 0, ., N -1, bitonic in the high order q bits, q <n , the sequence resulting
from the 2 q -way bitonic decomposition of Corollary 1 in the high order q bits is sorted
in the high order q bits and so each component of the decomposition is a permutation of
in the low order n -q bits.
The idea of the generalized Lambda time slot permuter L - N
an integer multiple of q , for a frame of N time slots is to sort the slot numbers q bits by
bits. From Corollary 2 and Corollary 1 the L - N
q permuter is obtained starting with
using
denotes the operation in the high order q bits, and S N /2 sorts
the first and the second half frames respectively in ascending and descending order. Note
that L - N
. Thus each instance of switching in a K stage of L - N
q is controlled
by a q -bit comparator for q >1. However, for q =1, i.e., in L - N , it is controlled
only by a single bit of the earlier arriving slot. For example, L -
2 and L - 64
are
.
The number of K stages in L - N
q ), and the frame delay, f (L - N
q ), are computed
as
Because L N only needs to use the header of the slot in the delay loop for the control
decision, the factor (h +d) is replaced by d in the case of q =1. Of course, d=0 unless the
feed forward version of the K stage is being used.
III. Hardware and Control Complexity

Table

compares TSI architectures in terms of switch count, control space, number
of bit comparisons, the required number of bit comparators, frame delay and control
delay. Hardware cost is estimated by the number of switches. This is especially accurate
in an optical implementation because optical switches are expensive, whereas delays are
just loops of fiber. The first row orders the architectures by increasing hardware complexity

We call the number of bits required to control all switches at all slot times the control
space. This includes the fixed control bits for maintaining frame integrity and fixed
control point settings restricting the K stage to pair exchange. The control space is
shown in the second row of the table, while the number of bit comparisons to compute
the control is given by the third row. For the RJS time slot permuter, computing the control
for the first (log 2 N - 1) switches requires source/destination and destination/source
random access memories (RAM), each of size N . The computation requires O (Nn )
address comparisons, or O (Nn 2 ) bit comparisons, where there are bits in the
destination address. Each remaining stage requires only N /2 bit comparisons. The other
two algorithms compute control on the fly using no RAM. The sorter does N /2 word
comparisons in each of O (n 2 ) stages, for O (Nn 3 ) bit comparisons. The Lambda permuter
also requires O (Nn 3 ) bit comparisons, with N /2 at each of O (n 3 ) stages. Control
hardware is estimated by the number of bit comparators needed. The looping algorithm
could use a single bit comparator serially, but would probably use n in the form of a
word comparator, since memory access is by word. The sorter requires O (n 2 ) bit comparators
since destination addresses arrive serially, and the Lambda permuter requires
O (n 3 ) bit comparators, one for each stage.
Frame delay is O (Nw ) in all the architectures, where w is the length of a time slot.
Control delay represents the time required to compute the control space. The looping
algorithm must gather destination information for all time slots in a frame before computation
can begin, and 2n -1 passes over it are then made, so the control delay is the maximum
of O (Nw ) and O (Nn 2 t) where t is the time for one bit comparison. The control
delay is O (n 3 t) for the other two architectures and can be overlapped with frame delay.
Parallelism in the control computation also distinguishes the TSI architectures.
Parallel versions of the looping control algorithm are possible, e.g. see [16], but are not
RJS Permuter Sorter Lambda Permuter
Switches
Control space O (Nn
Bit comparisons O
Bit comparators O (n
Pipelining
Memories (bits) O (Nn
Frame delay O (Nw ) O (Nw ) O (Nw )
Control delay

Table

1: Comparison of hardware cost and control complexity
considered here. This makes the RJS control parallelism only n for word level comparis-
ons. The parallelism in the other networks is of the pipelined form and comes from control
computations being done simultaneously for many slots distributed over the array.
Pipelined parallelism is O (n 2 ) in the sorter and O (n 3 ) in the Lambda permuter.
The table helps compare implementations based on cost and latency. Cost includes
number of switches and the cost of the control. The number of switches increases in
order by a power of n among the three architectures. Both control cost and time are
important. The RJS looping control uses little hardware if computed serially before the
frame enters the TSI. The other architectures have parallel control computation distributed
over O (n 2 ) switches in the sorter and over O (n 3 ) switches in the Lambda TSI.
Latency is determined both by control delay and frame delay. Frame delay dominates in
the sorter and Lambda permuter and is of the order of the frame length, or O (N ). Control
delay dominates in the RJS permuter and is at least O (N ). If slot lengths are O (Nn )
or more bits, all the TSIs would have the same order of latency. This could be the case in
integrated voice, video and data communications for switching at the higher TDM levels.
Where latency is critical, the sorter is a better choice since it requires a factor of n fewer
switches than the Lambda permuter and would be less expensive unless single bit control
is important.
IV. Optical Implementation of Time Slot Interchangers
The serial array TSIs can be implemented with advantage in many technologies.
Optical implementation, which motivated this research, has the advantage of inexpen-
sive, precise delays in waveguides. Optical exchange switches are available but introduce
some design problems. Lithium niobate electro-optic directional couplers [17] are
probably the best developed optical exchange switches. Their drawbacks include loss
and crosstalk between optical channels. Optical switches can also have transmission
bandwidths higher than their switching rate, which makes long time slots desirable to
compensate for the guard bands which must separate them. Comparators of header information
must be followed by enough delay that switching can occur in time. Since this
paper treats system architecture, we only address impacts of loss and crosstalk from that
perspective and do not do detailed calculations of their values. Such calculations for optical
TSI systems can be found in [7].
Most loss comes from connecting fiber to waveguides on lithium niobate, making it
important to minimize the number of times any signal crosses a switch. The feed forward
K stage has some advantage in this regard. Losses are large enough that even small
systems require optical signal restoration. Since fiber is a major system component, it is
natural to use erbium doped fiber amplifiers [18]. Optical switches with built-in restoration
are also being developed [19]. Crosstalk is intrinsically less of a problem, but since
erbium amplifiers amplify small noise signals well, it can become serious once loss is
eliminated. Crosstalk can be addressed by an architectural technique called dilation [20].
Dilation first expands the number of switches so that no switch has two simultaneous
input signals, and in a second phase contracts the number by transformations which
preserve the absence of simultaneous inputs. Figure 10 shows the transformations.
Dilation of an individual K stage is shown in Fig. 11. Control signals are derived
from the original K stage control. For the feedback form, c ="x" for all times except
when the second of a pair of slots to be exchanged enters the stage, when c ="=". Normally
c -="=", but when the second of a pair of slots to be exchanged enters the K stage at
the left c -="x" at that time and D time units later. For the feed forward version, c ="="
except for the first slot of a pair to be exchanged and c -="x" except for the second slot of
the pair. When stages are chained, the first contraction transformation of Fig. 10 can be
applied between stages. For either the feedback or feed forward version, an s stage array
requires 2s +1 switches. Thus dilation doubles the number of switches in an array of
feedback stages but only adds one switch to the feed forward form.
Considering both loss and crosstalk thus influences the architecture in two ways.
Loss prompts the use of networks with the minimum number of K stages and favors the
feed forward form because signals undergo one fewer switch crossing than in the worst
Expansion
Contraction

Figure

10: Transformations used in dilation
c
c
Feedback form
Feed forward form

Figure

11: Dilated K stages
case for the feedback form. Dilation eliminates crosstalk by having only one switch
input active at a time and makes the number of switches required for feedback and feed
forward versions the same. Thus a feed forward dilated serial array is preferred for optical
switches exhibiting both loss and crosstalk.
V. Conclusion
We presented several TSIs for TDM systems built from 2-2 exchange switches and
delays. The basic building block is a temporal exchange structure called the K stage,
which has both feedback and feed-forward forms. The TSIs are linear arrays of these
stages.
The RJS time slot permuter, with an optimal switch requirement of O (n
was derived from the Benes v
network, and its control needs to be precomputed for an
entire frame. Other TSIs - the time slot sorter S N , and the permuters L N
q , and L N -
have hardware complexities varying from O (n 2 ) to O (n 3 ) and control complexity of a
stage varying from n -bit to 1-bit magnitude comparisons. The comparisons are done
independently at each stage as the frame passes and do not require global knowledge as
in the RJS permuter.
Frame delays associated with switching and delays associated with controlling these
architectures were also compared. Some issues connected with optical implementation
of these TSIs were discussed, including the problems of crosstalk, finite delays associated
with switches, and use of delays to extract header information for switch control.



--R

"Photonic time-division switching systems,"
"Bit-serial architecture for optical com- puting,"
"Fiber optic delay line memory,"
"Time multiplexed optical computers,"
"An experimental photonic time-slot inter- changer using optical fibers as reentrant delay-line memories,"
"A new time domain, multi-stage permutation algorithm,"
"New architectures for optical TDM switching,"
"A survey of interconnection networks,"
"Multichannel Time Slot Permuters,"
"Photonic architectures for performing perfect shuffle on a time-division multiplexed signal,"

"On a class of rearrangeable switching net- works,"
"Sorting networks and their applications,"
"The Lambda network: A new permutation network,"
"K-Way Bitonic Sort,"
"A fast parallel algorithm for routing in permutation networks,"
Guided Wave Optoelectronics

"Low-loss, packaged, 2-2 semiconductor optical amplifier switch,"
"Dilated networks for photonic switching,"
--TR
K-Way Bitonic Sort
Time multiplexed optical computers

--CTR
Srinivasan Ramasubramanian , Arun K. Somani, MICRON: a framework for connection establishment in optical networks, IEEE/ACM Transactions on Networking (TON), v.16 n.2, p.473-485, April 2008
Cheng-Shang Chang , Yi-Ting Chen , Jay Cheng , Po-Kai Huang , Duan-Shin Lee, From switching theory to "queueing" theory, ACM SIGMETRICS Performance Evaluation Review, v.34 n.2, September 2006
Chunming Qiao , Rami Melhem, Reducing Communication Latency with Path Multiplexing in Optically Interconnected Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.8 n.2, p.97-108, February 1997
benes network;time slot sorters;telecommunications;time division multiplexing;multiprocessor interconnection networks;optical implementations;optical information processing;serial array time slot interchangers;bitonic decomposition;crosstalk;time division multiplexed systems;multistage interconnection networks;control complexity;exchange switches;space-to-time mapping;pipelined systems;logic arrays;optical interconnections;time multiplexed optical multiprocessors;batcher spatial sorting network;self-routing /spl Lambda/ permutation network;time slot permuters