Note: Descriptions are shown in the official language in which they were submitted.
7 ~
FIELD OF THE INV~NTTON:
This invention relates to communication
systems, and in particular to switching systems for
digital data.
BACKGROUND TO THE INVENTION:
For ISDN or other applications, a
communication switching system is required to switch
data carried in standard time slots, each corresponding
to a channel, grouped in frames. This has been
typically done in ISDN systems by concatenating standard
64 kb/s channels.
Unfortunately, in many prior art switching
systems, different channels in the same bit stream
experienced different delays during the switching
operation. This resulted in data getting out of order
and becoming corrupted. Such a system is unacceptable
for ISDN applications. Canadian application Serial No.
2,076,144 published February 17, 1993 discloses a
transmission system with a delay in frames correcting
system.
Data enters a switch in specific channels, and
is stored. It is then switched by reading the store,
and leaves the switch in different channels. Since the
different output channels are not in the same sequence
as the incoming channels, different delays result from
the assignment of time slots to the data from that of
the incoming bit stream.
One of the ways of eliminating the out of
order problem due to differing delays on different
channels has been to provide a constant delay to the
data. In the past, this involved buffering an entire
frame of data and then switching this buffered data one
or more frames later. This provided the constant delay
- 2 - ~ ~ Q ~ n
by giving maximum delay to all channels. Such a
multiple frame delay is taught in the above application.
Constant delay was a requirement for data
packet switches. In such systems, the packets of data
were extracted from the data stream and were then
switched individually through a switching mechanism.
Many inputs share a common physical interface.
A protocol is established so that each of the input and
output devices can share the bandwidth of the bus, but
each has exclusive use of the bus during its period.
Newer mechanisms allow many packets to be switched at
once, but still extract the packets before switching.
SUMMARY OF THE INVENTION:
The present invention assigns outgoing
channels to incoming channels so that all channels are
switched in order, but rather than with maximum delay as
in the prior art, the present invention provides minimum
delay. The present invention also allows the switching
of constant bit rate channels of differing bit rates.
It can provide channel assignment with a constant delay
within one frame for concatenated communication
channels, and allows the assignment of incoming and
outgoing channels to provide an unambiguous constant
delay period.
With proper alignment of delay between
incoming and outgoing data streams, it is possible to
provide constant delay switching. It is also possible
to provide constant delay switching between streams of
different data rates.
In accordance with an embodiment of the
invention, a method of assigning data from time slots on
an input bus to time slots on an output bus is comprised
of determining the order of time slots of data in an
-
- 3 - ~ ~ Q ~
input frame, determining whether each time slot of data
in an input frame is to be located in the same or later
s time slot in an output frame, or whether it is to be
located in an earlier time slot in an output frame; in
the event each time slot of data of the input frame is
to be located in the same or in a later time slot in an
output frame, applying each time slot of data of the
input frame to the same or a later time slot in the
output frame; in the event a time slot of data of the
input frame is to be located in an earlier time slot in
an output frame, delay for one time slot interval and
then apply each time slot of data of the input frame to
the same or a later time slot in the output frame;
whereby the order of time slots in a stream of output
data is always from an earlier time slot to a later time
slot.
In accordance with another embodiment, a
method of assigning data from time slots on an input bus
to time slots on an output bus is comprised of firstly
connecting the time slots from the input bus to the time
slots on the output bus in order beginning with the
first time slot of each frame on the input bus; in the
event the first connecting step does not result in
constant delay of time slots within a frame of data
between the input and the output bus, secondly
connecting the time slots from the input bus to the time
slots on the output bus shifted one time slot later in
time; and repeating the second connecting step until
there is constant delay of time slots within a frame of
data between the input and the output bus.
BRI~ INTRODUCTION TO TH~ DRAWINGS:
A better understanding of the invention will
be obtained by reference to the detailed description
-
- 3a - 2 ~ ~ ~ Q ~ 7
below, in conjunction with the following drawings, in
which:
SFigure 1 illustrates frames of input data and
frames of output data relating to particular delays,
Figure 2 is a block diagram illustrating an
embodiment of the invention, and
Figure 3 illustrates a timing diagram used to
10understand the operation of the embodiment of Figure 2.
DETAILED DESCRIPTION OF THE INVENTION:
Turning to Figure 1, a pair of sequential
frame intervals labelled frame A and frame B are
~4~ 21~900~
illustrated. The line labelled input data illustrates
four incoming time slots, carrying time slot numbers 2,
3, 4 and 1. It is desired to apply data from incoming
time slots to outgoing time slots such that the data
which is in order in the incoming time slots is in order
in the outgoing time slots. This will be referred to
below as the connection of incoming to outgoing time
slots.
The assignment of time slots in the two data
streams of input data and output data is arbitrary.
There is no requirement that the pattern of outgoing
time slots should depend on the pattern of incoming time
slots. If the data in the incoming time slots, for
example, were in order by channel ABCD, connections
would be made such that the outgoing data would be again
be in order by channel ABCD with the minimum delay.
In order to understand the description below,
the following is defined. A time slot is considered to
be numbered greater than another time slot if it occurs
later in the frame, and thus it is given a greater time
slot number. A time slot is considered numbered lesser
if it occurs earlier in the frame than another time
slot. A connection is called SF (same frame) if it
connects an incoming time slot to a greater or equal
outgoing time slot. A connection is called PF (previous
frame) if it connects an incoming time slot with a
lesser time slot. In an SF connection, the data in the
outgoing frame came from the same frame on the incoming
channels. In a PF connection, the data in the outgoing
frame came from the immediately previous frame on the
incoming channels.
A connection passes data in order if it meets
the following requirements:
(a) The connections between incoming and
outgoing time slots must be in sequence. The sequence
' -
_ 5 _ ~ 7 -4
may be allowed to wrap around the end of the frame, as
s may be seen with the numbered time slots in the input
data of Figure 1.
(b) All connections must be PF;
or
All the connections can be listed starting
from the first incoming time slot in two groups with all
SF connections to the left and all PF connections to the
right. Thus in the input data figure shown in Figure 1,
the connections can be listed with the order of the
incoming channels as SF, SF, SF, PF.
Thus the output data can be checked to
determine whether there is constant delay within a frame
of data between the input and output bus. In order to
produce the constant delay, the incoming time slots
should be connected to the outgoing time slots in order,
beginning with the first of each. This is illustrated
in Figure 1, where the output data with no delay shows
the input time slot 2 connected to output time slot 2,
input time slot 3 connected to output time slot 3, etc.
It should be determined whether each time slot of data
in the input frame is to be located in the same or later
time slot in the output frame, or whether it is to be
located in an earlier time slot in an output frame. If
each time slot of data of the input frame is to be
located in the same or later time slot in an output
frame, each time slot of data of the output frame is
applied to the same or a later time slot in the output
frame. This does not exist in the example shown in
Figure 1.
However in the event a time slot of data of
3s the input frame is to be located in an earlier time slot
of an output frame, there should be delay for one time
6 2 1~g0~7
slot interval, and each time slot of data of the input
frame should be applied to the same or later time slot
in the output frame.
The time slot numbered 1 in the input data of
Figure 1 follows a higher numbered time slot, and
therefore it meets the last-noted criterion. A delay is
introduced, and the time slot data of the frame
indicated is shifted as shown in the data line shown as
OUTPUT DATA T2. It may be seen that the time slot 1 has
been shifted into the first time slot of the following
frame, thus rendering the time slots in the second
frame, frame B, in numerical sequence. All of the time
slots in frame B will thus be designated SF.
Thus it has been determined that if the
incoming time slots connected to the outgoing time slots
in order beginning with the first of each did not
produce the desired requirements, and the incoming time
slots are connected to the outgoing time slots such that
the connections are shifted one time slot later in time
than the previous connection.
Clearly the connection has a delay of less
than one frame, and in the example shown, has a delay of
only a single time slot. The delay results in the
minimum possible delay for the set of time slots given.
In the event this shift does not result in
constant delay of time slots within a frame of data
between the input and output bus, the step is repeated
again, shifting one time slot at a time, until there is
constant delay of time slots within a frame of data
between the input and output bus.
In order to effect the above, the switching
circuitry must be able to switch without substantial
delay from an incoming time slot to an outgoing time
slot which has the same or greater time slot number, and
~_ ~7~ 21~07
the switching mechanism must be able to switch from an
incoming time slot to an outgoing time slot up to one
frame time away.
Considering Figures 2 and 3, an embodiment of
a system for effecting the above, an input serial bus 1
carries frames of serial data in 8 bit bytes, each
designating a time slot. A parallel bus 3 carries time
slot assigned data which is to be e.g. switched in a
space division switching mechanism from one bus to
another.
Similarly, data received from bus 3 is time
slot assigned and eventually output on serial output bus
5. Those buses can be wired, optical fiber, etc.
Bus 3 can interface a multiplexer connected to
e.g. 16 buses. The structure between the serial buses
and bus 3 interconnects the data carried on bus 3 with
the serial data stream. The function is to reassign
data channels so that data can be transferred between
the two buses. In one embodiment, data is created in
fixed channels by interfaces connected to the buses
multiplexed and connected to bus 3. The fixed channels
are reassigned to variable channels by the structure
described herein to allow the data to be switched
through a central space switch.
A channel consisting of e.g. 8 bits of data
arrives on the input serial databus 1 stream. In a
preferred embodiment there are 256 channels for each
125 ~s frame. The data is converted from serial to
parallel in S/P converter 7, and at the end of the
incoming channel time, it is latched to a register 9,
where it is stored for the next channel time, while the
next channel is being converted from serial to parallel.
During the first half of the next channel
time, the outputs of the register 9 are enabled under
control of processor 11. The data stored in latch 9 is
_ -8- 21~U07
received in a memory 13. Memory 13 is 256 bytes long by
8 bits wide, and thus has sufficient capacity to hold
one frame of data. Memory 13 is thus a cyclic memory
which holds the last frame of data.
s Under control of processor 11, a connection
memory 15 generates addresses and applies those
addresses to memory 13 to store the incoming data from
latch 9 at locations related to the channel number of
the incoming serial data stream.
During the second half of the channel time,
the connection memory generates addresses relating to
the time slot number of the serial channel which is to
be switched to bus 3. Upon addressing memory 13 during
the second half of the channel time and enabling memory
13 to read, rather than write the data as it had during
the first half of the channel time, the data
corresponding to the time slot number of the serial
channel which is to be switched to bus 3 is read into
buffer 17. The output buffer is enabled and the data is
output to bus 3.
Thus by appropriately designating the output
channel addresses, the data read into and stored in
memory 13 can be output to bus 3 with an appropriate
delay, and in a selectable sequence.
The data on bus 3 is then latched into
multiplexer/demultiplexer 19, for application to
appropriate serial buses 21.
The system involving transmission of data from
buses 21 to serial bus 5 is similar to that described
above, except in reverse. Demultiplexed data on bus 3
is applied to buffer 23, is written into frame memory
25, is read into latch 27 from memory 25, is converted
from latch 27 into serial data in parallel to serial
converter 29, and is output on serial data bus 5.
- 21~30~7
g
_
It will be noted that there is a difference in
speed between the bus rate on bus 1 and the bus rate on
buses 21. If data is to be switched to or from the same
numbered channels, the reading time of memory 13 should
S be established so that there is a delay between the bus
21 and bus 1.
The circuit must arrange delay between the
data on any of buses 21 and that on outgoing serial bus
5. The frame of the outgoing serial bus 5 should be
established so that it is one input bus channel time
behind the input bus 21 frame. In this way, data on
e.g. channel 0 of the input bus 21 may be switched to
channel 0 of the outgoing serial stream on bus 5.
With the above structure, it is possible to
switch data from bus 21 to bus 5 in the same manner as
previously described for data from bus 1 being switched
to serial streams on buses 21.
The timing illustrated in Figure 3 facilitates
sharing of the bandwidth of the parallel bus 3 by
alternating its use between transmit and receive data.
The internal latching of data in the transmit time slot
assignor involving elements 23, 25, 27 and 29 is similar
to the latching of data in the received time slot
assignor involving elements 7, 9, 13 and 17.
With proper delay, it is possible to switch
data between streams of different but compatible rates.
For example one can set the ratio between 1:1 and 16:1
or a higher ratio.
It should be noted that the addresses
generated by the connection memory can be completely
arbitrary. All that need occur is that each incoming
channel is stored in a known location. The locations
generated for the outgoing channels will be those known
locations.
210~
- 10-
',_
There could be for example, fixed incoming
channels and variable outgoing channels, variable
incoming channels and fixed outgoing channels, fixed
incoming channels and fixed outgoing channels or
S variable incoming channels and variable outgoing
channels. Fixed in this case designates locations fixed
relative to system timing.
Where there is variable incoming to variable
outgoing channels, it may be desired to switch only a
few channels from serial streams containing a great many
channels. In that case only those channels which are to
be switched need to be stored while the others are
ignored. This could allow the operation of a circuit
with smaller data memories 13 and 25.
A person understanding this invention may now
conceive of alternative structures and embodiments or
variations of the above. All of those which fall within
the scope of the claims appended hereto are considered
to be part of the present invention.