REGISTER  |  SIGN IN
United States Patent5351236
PawelskiSeptember 27, 1994
Title
Multirate, sonet-ready, switching arrangement
Abstract
A time-division multiplex switch (100) switches a hierarchy of data rates. It sets up higher-rate connections not as a plurality of individual lowest-rate connections but as one or more time slots in each one of a plurality of sequential frames (40, 50) that correspond to that higher rate in each superframe (30). A time-slot-interchange switching element (131, 141 ) of the switch utilizes a plurality of physically or logically distinct double-buffered data memories (301, 302, 303) each corresponding to a different one of the superframe and different-size ones of the frames. Reading and writing of each of the data memories' buffers alternates with the corresponding one of the superframe and different-size frames; reading of a data memory's buffer immediately follows writing of that buffer. Information from all incoming time slots is written into each one of the data memories, but only information corresponding to the data rate of an individual data memory's corresponding frame size is read that data memory into outgoing time slots. A control memory (305) maps memory locations of the data memories to output time slots. A corresponding control architecture in a switching element (1700) of a time-multiplexed switch (120)uses control memory (1701) that maps input ports to time slots of an output port.
Inventors:Pawelski; Robert L. (Lisle, IL)
Assignee:AT&T Bell Laboratories (Murray Hill, NJ)
Appl. No.:963976
Filed:October 20, 1992
Current U.S. Class:370/358 370/376 
Current International Class:H04Q 11/04 (20060101)
Field of Search:370/59,60,60.1,94.1,58.1-58.3,112,66,68,84,54 340/825.8
U.S. Patent Documents
4485468November 1984Slana
4855996August 1989Douskalis
4967405October 1990Upp et al.
4991168February 1991Richards
4993016February 1991Richards
4998242March 1991Upp
5005170April 19911elson
5040173August 1991Richards
5119368June 1992Hiltner et al.
5130975July 1992Akata
5146455September 1992Goke et al.
5161152September 1992Czerwiec et al.
5197063March 1993Nakano et al.
5265090November 1993Guinand et al.
Other References
Enhanced Network, Product/Service Information, document No. 50041.16/04-91 (Apr. 12, 1991), Northern Telecom, pp. 1-22, A-1-A-9, B-1-B-3. .
Synchronous Optical Networks (SONET), Technical Advisory TA-TSY-000253, Issue 2 (May 1987), Bell Communications Reserach, Inc., pp. 1-77. .
Synchronous Optical Network (SONET) Transport Systems: Common Generic Criteria, Technical Reference TR-NWT-000253, Issue 2 (Dec. 1991), Bell Communications Research, Inc., pp. 3-1`3-76..~
Primary Examiner: Chin; Wellington
Assistant Examiner: Nguyen; Chau T.
Attorney, Agent or Firm:Volejnicek; David
Claims

I claim:
1. A switching element for switching connections having a hierarchy of data rates comprising a lowest rate corresponding to one time slot of a time-division multiplex (TDM) superframe of time slots and at least one higher rate corresponding to at least one time slot of a predetermined frame of time slots within said TDM superframe, said switching element comprising:
a first port;
a plurality of second ports;
control memory means for defining switched connections having said lowest rate and said at least one higher rate, said control memory means including a different control memory location for each time slot of said superframe wherein contents of each control memory location indicate which second port is to be connected to said first port during every occurrence of a switching element output time slot that corresponds to said control memory location;
means responsive to contents of said control memory locations for connecting said first port to ones of said second ports during first time-slot intervals to effect connections having said lowest rate and for connecting said first port to ones of said second ports during second time-slot intervals to effect connections having said at least one higher rate; and
means for programming said control memory means to define an individual switched connection corresponding to a selected rate of the hierarchy and including
means for detecting occurrence of a switching element output time slot corresponding to the individual switched connection within each frame that corresponds to the selected rate in a switching element output superframe, and
means coupled to the detecting means and to the control memory means and responsive to each detection for writing, into the control memory location that corresponds to the detected output time slot, information specifying one of said second ports that is to be connected to said first port during each occurrence of said output time slot that corresponds to said control memory location that corresponds to the detected output time slot.

2. The switching element of claim 1 wherein said switching element functions as a time-multiplexed space switch.

3. Apparatus for switching connections having a hierarchy of data rates comprising a lowest rate corresponding to one time slot of a time-division multiplex (TDM) frame of time slots and at least one higher rate corresponding to a plurality of time slots within said TDM frame, said apparatus comprising:
means, responsive to a command to establish a given connection having a higher rate of said at least one higher rate, said command specifying only one time slot within said TDM frame and a data rate for said given connection, for determining from said specified time slot and data rate a set of a plurality of time slots within said TDM frame for said given connection;
control memory means having locations corresponding to said TDM frame of time slots;
means coupled to the means for determining a set of a plurality of time slots for said given connection, for determining locations in said control memory means that correspond to determined said set of a plurality of time slots;
means coupled to the means for determining a set of a plurality of time slots for said given connection, for writing information defining said given connection into determined said locations of said control memory means; and
switching means responsive to reading of said connection-defining information written into said determined locations of said control memory means for establishing said given connection having said higher rate.

4. The apparatus of claim 3 wherein:
the location-determining means are responsive to a command to establish a connection having said lowest rate, said command specifying a time slot within said frame and a data rate for said connection having said lowest rate, for determining a location in said control memory that corresponds to said specified time slot;
the writing means write information defining said connection having said lowest rate into said determined location of said control memory; and
said switching element is responsive to reading of said stored lowest-rate connection information written into said determined location of said control memory for establishing said connection having said lowest rate.

5. The apparatus of claim 3 wherein said switching means is a time-slot interchanger and said determined set of time slots comprises output time slots of said time-slot interchanger.

6. The apparatus of claim 5 wherein said information defining said given connection identifies input time slots of said time-slot interchanger.

7. The apparatus of claim 6 wherein said command specifies only one output time slot and an input time slot corresponding to said one output time slot.

8. The apparatus of claim 3 wherein said switching means is a time-multiplexed space-switching element having a plurality of first ports and a second port and said determined set of time slots comprise output time slots of said time-multiplexed space-switching element.

9. The apparatus of claim 8 wherein said information defining said given connection identifies one of said first ports.

10. The apparatus of claim 3 wherein said command specifies only one output time slot and one of said first ports that corresponds to said one output time slot.

11. A time-slot interchanger comprising:
data memory means;
control memory means having a plurality of locations each corresponding to a different one of a plurality of time slots of a time-division multiplex frame;
means responsive to a request for a connection comprising multiple time slots of the time-division multiplex frame, said request specifying only one input time slot and one output time slot and a data rate of said connection, for determining, from specified said time slots and specified said data rate, other input time slots and output time slots for use for said connection comprising multiple time slots;
means coupled to the determining means, for writing into locations of said control memory means which correspond to said one output time slot and determined said other output time slots, information identifying said one input time slot and determined said other input time slots; and
said data memory means being responsive to said control memory means for transmitting information, stored from said one input time slot and said determined other input time slots, in said one output time slot and said determined other output time slots.

12. A time-slot interchanger in accordance with claim 11 wherein
input time slots and output time slots of each higher rate within the hierarchy have a predefined spacing within said time-division multiplex frame; and
said determining means determines said other input time slots and said other output time slots in accordance with said predefined spacing.

13. A time-multiplexed space switch comprising:
a plurality of first ports;
a second port;
control memory means having a plurality of locations each corresponding to a different one of a plurality of time slots of a time-division multiplex frame;
means responsive to a request for a connection comprising multiple time slots of the time-division multiplex frame, said request specifying a first port and only one output time slot of said switch and a data rate for said connection, for determining, from specified said first port and one output time slot and data rate, other output time slots of said switch for use for said connection comprising multiple time slots;
means for writing into locations of said control memory means which correspond to said one output time slot and determined said other output time slots, information defining said first port; and
means responsive to said control memory means for transmitting information from input time slots of one of defined said first port and said second port, in said one output time slot and said determined other output time slots of the other of said defined first port and said second port.

14. A time-multiplexed space switch in accordance with claim 13 wherein:
input time slots and output time slots of each higher rate within the hierarchy have a predefined spacing within said time-division multiplex frame; and
said determining means determines said other output time slots in accordance with said predefined spacing.

15. Apparatus for switching connections having a hierarchy of data rates comprising a lowest rate corresponding to one time slot of a time-division frame of time slots, said hierarchy comprising at least one higher rate corresponding to a plurality of time slots of predefined spacing within said time-division frame, said apparatus comprising:
means responsive to a request to establish a given connection having said higher rate for determining a set of time slots of said predefined spacing within said time-division frame for said given connection;
control memory means for defining switched connections having said lowest rate and said at least one higher rate, said control memory means including a different control memory location for each time slot of said time-division frame of time slots wherein contents of each control memory location indicate which input time slot is to be connected to an output time slot corresponding to said memory location during every occurrence of said output time slot that corresponds to said control memory location;
means for determining locations in said control memory means that correspond to determined said set of time slots;
means for writing information defining said given connection into determined said locations of said control memory means, including
means for detecting each occurrence of a switching element output time slot corresponding to said given connection within said time-division frame, and
means coupled to the detecting means and to the control memory means and responsive to each detection for writing, into the control memory location that corresponds to the detected output time slot, information specifying one of said input time slots that is to be connected to said detected output time slot during each occurrence of said output time slot that corresponds to said control memory location that corresponds to the detected output time slot; and
switching means responsive to reading of connection information written into said determined locations of said control memory means for establishing said connection having said higher rate.

16. A method of switching connections having a hierarchy of data rates comprising a lowest rate corresponding to one time slot of a time-division multiplex (TDM) superframe of time slots and at least one higher rate corresponding to at least one time slot of a predetermined frame of time slots within said TDM superframe, said switching method comprising the steps of:
during each time slot of said TDM superframe, reading a different control memory location of a programmable control memory means that defines switched connections having said lowest rate and a higher rate of said at least one higher rate, said control memory means including a different control memory location for each time slot of said TDM superframe, wherein contents of each control memory location indicate which one of a plurality of first ports is to be connected to a second port during every occurrence of a switching element output time slot that corresponds to said control memory location;
in response to contents of said control memory locations, connecting said second port to ones of said first ports during first time-slot intervals to effect connections having said lowest rate and for connecting said second port to ones of said first ports during second time-slot intervals to effect connections having said higher rate; and
reprogramming said control memory means to define an individual switched connection corresponding to a selected rate of the hierarchy and including the steps of
detecting occurrence of a switching element output time slot corresponding to the individual switched connection within each frame that corresponds to the selected rate in a switching element output TDM superframe, and
in response to each detection, writing into the control memory location that corresponds to the detected output time slot, information specifying one of said first ports that is to be connected to said second port during each occurrence of said output time slot that corresponds to said control memory location that corresponds to the detected output time slot.

17. The switching method of claim 16 wherein said switching method performs a time-multiplexed space-switching function.

18. A method of controlling a switching element for switching connections having a hierarchy of data rates comprising a lowest rate corresponding to one time slot of a time-division multiplex (TDM) frame of time slots and at least one higher rate corresponding to a plurality of time slots within said TDM frame, said method comprising the steps of:
in response to a command to establish a given connection through said switching element having a higher rate of said at least one higher rate, said command specifying only one time slot within said TDM frame and a data rate for said given connection, determining from specified said one time slot and specified said data rate a set of a plurality of time slots within said TDM frame for said given connection;
determining locations in a control memory that correspond to determined said set of a plurality of time slots;
storing in determined said locations of said control memory information defining said given connection; and
operating said switching element in response to reading of stored said connection information from said control memory to establish said given connection having said higher rate.

19. A method in accordance with claim 18 further comprising the steps of:
in response to a command to establish a connection through said switching element having said lowest rate, said command specifying a time slot within said TDM frame and a data rate for said connection having said lowest rate, determining a location in said control memory that corresponds to specified said time slot;
storing information defining said connection having said lowest rate in determined said location of said control memory; and
operating said switching element in response to reading of stored said lowest-rate connection information to establish said connection having said lowest rate.

20. A method in accordance with claim 18 wherein said switching element is a time-slot interchanger and said determined set of time slots comprises output time slots of said time-slot interchanger.

21. A method in accordance with claim 20 wherein said information defining said given connection identifies input time slots of said time-slot interchanger.

22. A method in accordance with claim 21 wherein said command specifies only one output time slot and an input time slot corresponding to said one output time slot.

23. A method in accordance with claim 18 wherein said switching element is a time-multiplexed space-switching element having a plurality of first ports and a second port and said determined set of time slots comprise output time slots of said time-multiplexed space-switching element.

24. A method in accordance with claim 23 wherein said information defining said given connection identifies one of said first ports.

25. A method in accordance with claim 24 wherein said command specifies only one output time slot and one of said first ports that corresponds to said one output time slot.

26. A method of controlling a time-slot interchanger having a data memory and a control memory that includes a plurality of locations each corresponding to a different one of a plurality of time slots of a time-division multiplex frame, the method comprising the steps of:
in response to a request for a connection comprising multiple time slots of the time-division multiplex frame, said request specifying only one input time slot and one output time slot and a data rate of said connection, determining, from specified said time slots and specified said data rate, other input time slots and output time slots for use for said connection comprising multiple time slots;
writing into locations of said control memory which correspond to said one output time slot and determined said other output time slots, information identifying said one input time slot and determined said other input time slots; and
in response to contents of said control memory, transmitting information stored from said one input time slot and said determined other input time slots, in said one output time slot and said determined other output time slots.

27. The method in accordance with claim 26 wherein
input time slots and output time slots of each higher rate within the hierarchy have a predefined spacing within said time-division multiplex frame; and
said step of determining determines said other input time slots and said other output time slots in accordance with said predefined spacing.

28. A method of controlling a time-multiplexed space switch having a plurality of first ports, a second port, and a control memory having a plurality of locations each corresponding to a different one of a plurality of time slots of a time-division multiplex frame, the method comprising the steps of:
in response to a request for a connection comprising multiple time slots of the time-division multiplex frame, said request specifying a first port and only one output time slot of said switch and a data rate for said connection, determining, from specified said first port and one output time slot and data rate, other output time slots of said switch for use for said connection comprising multiple time slots;
writing into locations of said control memory which correspond to said one output time slot and determined said other output time slots, information defining said first port; and
in response to contents of said control memory, transmitting information from input time slots of one of defined said first port and said second port, in said one output time slot and said determined other output time slots of the other of said defined first port and said second port.

29. The method in accordance with claim 28 wherein:
input time slots and output time slots of each higher rate within the hierarchy have a predefined spacing within said time-division multiplex frame; and
said step of determining determines said other output time slots in accordance with said predefined spacing.
Description
CROSS-REFERENCE TO RELATED APPLICATIONS

This application is related to the following concurrently-filed and jointly-owned applications:

R. L. Pawelski, "Multirate, Sonet-Ready, Switching Arrangement", Case 3 U.S. patent application Ser. No. 07/964,537;

M. F. Paker, R. L. Pawelski, and W. A. Payne, III, "A TDM Circuit-Switching Arrangement that Handles Frames of Different Sizes"; U.S. patent application Ser. No. 07/963,975 and

M. F. Paker, R. L. Pawelski, W. A. Payne, III, and G. W. Richards, "Hierarchical Path Hunt for Multirate Connections"U.S. patent application Ser. No. 07/964,224.

TECHNICAL FIELD

This invention relates to telecommunications switching.

BACKGROUND OF THE INVENTION

Time-division multiplex (TDM) circuit-switching techniques have been in widespread commercial use for quite some time. Central to typical prior-art TDM arrangements is the notion of a "frame" divided into a predetermined number of time slots. The frame has a fixed, predetermined duration, and individual duplicate frames follow each other in sequential succession. Thus each time slot recurs at a fixed frequency, or rate, referred to herein as the "frame rate". For example, if the frame has a duration of 125 .mu.sec, each time slot recurs at a rate of 1/(125.times.10.sup.-6) sec=8 KHz. Each communicating frame is assigned to one or more time slots and, when the time slot(s) occur, the channel is enabled to place data on and/or remove data from the TDM medium (e.g. a communications link or a switching fabric). The traffic of the different communicating channels is thereby interleaved on the TDM medium. If a plurality of non-adjacent time slots within a single frame is assigned to a channel, that channel's traffic is also interleaved inside each frame with the traffic of other channels.

In recent years, standards have been developed for the transport of broadband communications. Among these are the Synchronous Optical Network (SONET) and the similar Synchronous Digital Hierarchy (SDH). The expected growth in synchronous transport facilities based on SONET and SDH supports a need for more efficient synchronous switch fabric architectures. The modular byte-interleaved structure of SONET is based on Synchronous Transport Signal level 1, or STS-1, format, in which overhead plus payload results in a rate of 51.840 Mb/s. The STS-1 frame consists of 90 columns by 9 rows of bytes, or 810 bytes, with a frame rate of 125 .mu.s. The first three columns in the frame are devoted to transport overhead (TOH), while the remaining 87
columns carry the payload, including one column devoted to path overhead (POH). 87 columns of payload constitute a Synchronous Payload Envelope (SPE). However, an SPE can cross frame boundaries, and is allowed to float anywhere within the payload-carrying portion one or more contiguous frames to accommodate the semi-synchronous nature of the transport facilities. For switching of rates below the STS-1 rate, a switch assumes that the path overhead has been aligned with the first column following transport overhead.

Super STS-1 signals (STS-N) are formed by byte-multiplexing the N constituent STS-1 signals, with the resultant bandwidth being N times that of the STS-1rate. Conversely, sub STS-1 signals are transported in Virtual Tributaries (VTs), of which four sizes are defined at present, namely VT1.5 (1.728Mb/s), VT2 (2.304 Mb/s), VT3 (3.456 Mb/s) and VT6 (6.912 M/b/s). To accommodate mixes of VTs, the VT-structured STS-1 SPE is divided into 7 VT groups, with each group occupying 12 columns of the
9-row frame structure; 2 columns remain unused are referred to as STUFF columns. A VT group may contain 4 VT1.5s, 3 VT2s, 2 VT3s, or 1 VT 6. Both the super STS and sub STS signals retain the frame rate of 125 .mu.s.

FIG. 2 shows a 3-dimensional representation of an STS-12 flame as illustrative example. There are 12 vertical planes which represent the 12 STS-1s, each composed of 90 columns and 9 rows, for a total of 9720 bytes. Vertical columns may be grouped to form Virtual Tributaries (VTs), as shown by the four regularly-spaced columns representing a VT2 in position #3. While a VT2 requires 4 regularly-spaced columns, as shown, a VT1.5 requires 3 regularly-spaced columns, a VT3 requires 6
regularly-spaced columns, and a VT6 requires 12 regularly-spaced columns. Finally, a DS-0, corresponding to a 64 kilobits-per-second rate, appears as a single byte within one row and column. There are a maximum of 774 DS-0s per STS-1, some of which may be used for additional overhead functions; 756 DS-Os are available for traffic transport.

The three component sub-rates of an STS-N frame--STS-1, VT, and DS-0--may be switched independently by three separate switching fabrics, each dedicated to switching one of the sub-rates. But this is inefficient in the amount of equipment used: it requires demultiplexers at the inputs to the switching fabrics to separate the sub-rates, a separate switching fabric for each sub-rate, and multiplexers at the outputs from the switching fabrics to combine the switched sub-rates back into STS-N frames. The use of a single switching fabric for all sub-rates is therefore preferable.

Given a switching fabric capable of switching multiple rates within an STS-N format, one is faced with the problem of efficiently setting up multirate calls through such a fabric. One approach is to treat a call of any given bandwidth as multiple DS-0 calls. Although this is a flexible approach, the disadvantage is that a path-hunt and a path-setup must be performed individually for each DS-0 call. For example, a single STS-1 call would require as many as 810 individual path hunts and control-memory-setups. This is inefficient both in terms of the amount of time required for the path hunting and the number of control communications required to set up the individual paths. There is an associated need for switching elements that are adapted for efficient multirate application.

SUMMARY OF THE INVENTION

This need is met and a technical advance is achieved in accordance with the principles of the invention in a switching element and associated control method where the switching element switches a hierarchy of data rates including a lowest rate corresponding to one time slot of a time-division frame of time slots, and at least one higher rate corresponding to a plurality of time slots--preferably of predefined spacing, for ease of implementation--within the time-division frame. Generally, according to one aspect of the invention, rather than setting up a higher rate connection as a plurality of individual lowest-rate connections, a set of time slots for the connection is determined from a single time slot that is specified by a command that requests the connection to be made. Locations are determined in a control memory that correspond to the set of time slots, and those locations are used to store information defining the connection. The switching element is then operated in response to reading of the stored connection information from the control memory to establish the higher-rate connection. Illustratively, the switching element serves either as a time-slot interchange switching element or as a time-multiplexed space-switching element. In the former case, the specified single time slot is illustratively specified in terms of an output time slot and a corresponding input time slot that maps thereinto. In the latter case, the specified single time slot is illustratively specified in terms of an output time slot and a corresponding port.

Furthermore, a connection is established through the switching element at the lowest rate by using a single time slot within the frame that is specified by the command requesting the lowest-rate connection. The corresponding control memory location is used to store the necessary connection information, which is read to operate the switching element to establish the lowest-rate connection. Illustratively, the switching element is a time-slot interchanger, the control memory locations correspond to output time-slots of the time-slot interchanger, and the information defining the connection identifies input time slots of the time-slot interchanger. Alternatively, the switching element is a time-multiplexed space switch having first (e.g., input) ports and a second (e.g., output) port, the control memory locations correspond to output time slots of the switch, and the information defining the connection identifies one of the first ports.

Illustratively, the connection command specifies a data-rate corresponding to a plurality of time slots of predefined spacing within the time-division multiplex frame, and output time slots--and corresponding input time slots in the case of the time-slot interchanger--are determined in accordance with the predefined spacing. In the illustrative embodiment herein, the time-division multiplex frame is an STS-12 frame and the hierarchy of data rates comprises an STS-1 rate, any of a plurality of VT rates, and a DS-0 rate.

According to another aspect of the invention, a switching element--illustratively functioning as a time-slot interchanger--for switching the hierarchy of the data rates comprises first double-buffered data memory locations corresponding to each time slot of the superframe, second double-buffered data memory locations corresponding to each time slot of the predefined frame, and a control memory for defining switched connections at the lowest and the higher rate. Reading and writing of the first double-buffered data memory locations alternates with the superframes. That is, one buffer of the data memory locations is written during a first superframe and another buffer of those locations is read during the first superframe, but the one buffer is read during a next superframe and the other buffer is written during the next superframe. Most significantly, reading and writing of the second double-buffered data memory locations alternates with the frames. In accordance with the switched-connection definitions stored in the control memory, information is read from the first double-buffered data memory locations to effect switched connections at the lowest rate, and information is read from the second double-buffered data memory locations to effect switched connections at the higher rate. Illustratively, information is likewise written into the first locations to effect the lowest-rate connections and is written into the second locations to effect the higher-rate connections; in one implementation, all information is written into both the first and the second locations.

In one disclosed embodiment, the first and second double-buffered data memory locations are physically located in separate double-buffered data memories. In another disclosed embodiment, the first and second locations are physically located in one double-buffered data memory, and the second locations are a subset of the first locations. In one disclosed variant of the second embodiment, the second locations are N-buffered where N is an integer greater than two, and a sequence of N buffers of the second locations and buffers of the first locations occupy same physical locations of the data memory. The N buffers of the sequence are written sequentially, and reading of an individual buffer of the sequence occurs while writing occurs in an immediately-succeeding buffer of the sequence.

According to a further aspect of the invention, the switching element comprises a plurality of physical or logical data memories each one of which corresponds to a different one of (a) the superframe and (b) different-size ones of the frames within the superframe. Significantly, each data memory has information written thereinto during an individual frame period of the corresponding one of the superframe and the different-size frames, and has information read therefrom during a frame period of the corresponding one of the superframe and the different-size frames which immediately follows the individual frame period. Received information, contained by an incoming superframe and its included frames, is written into corresponding ones of the data memories. A control arrangement, such as a control memory shared by the plurality of data memories, maps time slots of the incoming superframe into time slots of an outgoing superframe. This mapping is followed in reading, into an outgoing superframe and its included frames, the stored information from corresponding ones of the data memories. Reading of data memory locations alternates between different ones of the data memories with changes in a corresponding one of the data rates of successive switching element output time slots. Illustratively, writing of data memory locations likewise alternates between different ones of the data memories with changes in a corresponding one of the data rates of successive switching element input time slots.

Illustratively, the control arrangement indicates, for individual switching-element output time slots, a corresponding data rate of the hierarchy, and in response thereto information is read from the data memory that corresponds to the superframe during output time slots for which the control arrangement indicates the lower rate, while information is read from the data memory that corresponds to the frames that correspond to the higher rate during output time slots for which the control arrangement indicates the higher rates. Further illustratively, the control arrangement gives the like rate indication for input time slots, and in response thereto information is correspondingly written into one or another of the memories during those input time slots.

According to yet a further aspect of the invention, the control memory of the switching element includes a different control memory location for each time slot of an outgoing superframe. In the case of a time-slot interchange switching element, contents of each control memory location indicate which input time slot is to be connected to the corresponding output time slot during every occurrence of that corresponding output time slot. In the case of time-multiplexed space-switching element, contents of each control memory location indicate which first (e.g., inputs) port is to be connected to the corresponding output time slot of the switching element during every occurrence of that corresponding output time slot. The contents of different ones of the control memory locations are then used during different time-slot intervals to effect connections at the lowest and the higher rates. The switching element further includes an arrangement for programming the control memory to define an individual switched connection corresponding to a selected rate of the hierarchy. The programming arrangement detects occurrence of an output time slot corresponding to the individual switched connection within each frame (including superframe) that corresponds to the selected rate in an output superframe, and writes into the control memory location that corresponds to the detected time slot the information that specifies either one of the input time slots or one of the first ports that is to be connected to the output time slot during each occurrence of that output time slot that corresponds to the written control memory location.

In a switching system constructed and operated according to one or more aspects of the invention, a hierarchy of data rates may be switched in a single shared switching fabric. Yet each data rate undergoes a switching delay that is proportional only to its corresponding frame rate. This means that the higher the data rate, the less switching delay it encounters. Any desired connection requires the specification of only a single time slot. Other time slots which are required for higher-rate connections are then determined automatically, and control memories are automatically programmed accordingly. Programming of connections is thereby simplified. The data memories of a switching element share a control memory, thereby simplifying the architecture and the programming of desired connections. The same control architecture may be used for switching elements of different types, resulting in yet further architectural simplicity. And because of the commonality of the control architecture, different switching elements can share portions of the control circuitry, resulting in further simplification, reduced circuit-pack size, and cost savings.

These and other advantages and features of the invention will become apparent from the following description of an illustrative embodiment of the invention taken together with the drawing.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a block diagram of a time-division multiplex circuit-switching system that incorporates an illustrative embodiment of the invention;

FIG. 2 is a block diagram of the internal configuration of a SONET STS-12 frame;

FIG. 3 is a block diagram of a first illustrative embodiment of a time-slot interchanger (TSI) of the system of FIG. 1;

FIGS. 4-6 are a circuit diagram of a first illustrative implementation of the TSI of FIG. 3;

FIG. 7 is a table of the ranges of address values that define frames of different types in the TSI implementation of FIGS. 4-6;

FIGS. 8-9, along with FIG. 4, are a circuit diagram of a second illustrative implementation of the TSI of FIG. 3;

FIG. 10 is a block diagram of a second illustrative embodiment of a TSI of the system of FIG. 1;

FIG. 11-13 are a circuit diagram of an illustrative implementation of the TSI of FIG. 10;

FIG. 14 is a block diagram of a third illustrative embodiment of a TSI of the system of FIG. 1;

FIGS. 15-17 are a circuit diagram of a first illustrative implementation of the TSI of FIG. 14;

FIG. 18 is a table of the address-compensation values of the 4-word shift register of the TSI implementation of FIGS. 15-17;

FIGS. 19-21 are a circuit diagram of a second illustrative implementation of the TSI of FIG. 14;

FIG. 22 is a block diagram of the time-multiplexed switch (TMS) of the system of FIG. 1;

FIG. 23 is a circuit diagram of a first illustrative implementation of an output control of the TMS of FIG. 22;

FIG. 24 is a circuit diagram of a second illustrative implementation of an output control of the TMS of FIG. 23;

FIG. 25 is a circuit diagram of a third illustrative implementation of an output control of the TMS of FIG. 22;

FIG. 26 is a circuit diagram of a fourth illustrative implementation of an output control of the TMS of FIG. 22;

FIG. 27 is a block diagram of timeslot-status table-hierarchies for the TSIs of the switching system of FIG. 1, which hierarchies are implemented by matrices shown in FIGS. 28-31;

FIG. 28 is a block diagram of TSI STS-1 timeslot block status matrices for the TSIs of the switching system of FIG. 1;

FIG. 29 is a block diagram of VT timeslot block status matrices for the TSIs of the switching system of FIG. 1;

FIG. 30 is a block diagram of VT group status matrices for the TSIs of the switching system of FIG. 1;

FIG. 31 is a block diagram of DS-0 timeslot block status matrices for the TSIs of the switching system of FIG. 1;

FIGS. 32-33 are a flow diagram of a broadband path-hunt procedure performed by the control processor of the switching system of FIG. 1;

FIG. 34 is a flow diagram of multiple STS-1 path-hunt procedure of the broadband path-hunt procedure of FIGS. 32-33;

FIG. 35 is a flow diagram of one STS-1 path-hunt procedure of the multiple STS-1 path-hunt procedure of FIG. 34;

FIG. 36 is a flow diagram of multiple VT6 path-hunt procedure of the broadband path-hunt procedure of FIGS. 32-33;

FIGS. 37-43 are a flow diagram of one VT6 path-hunt procedure of the multiple VT6 path-hunt procedure of FIG. 36;

FIG. 44 is a flow diagram of multiple VT3 path-hunt procedure of the broadband path-hunt procedure of FIGS. 32-33;

FIGS. 45-51 are a flow diagram of one VT3 path-hunt procedure of the multiple VT3 path-hunt procedure of FIG. 44;

FIG. 52 is a flow diagram of multiple VT2 path-hunt procedure of the broadband path-hunt procedure of FIGS. 32-33;

FIGS. 53-59 are a flow diagram of one VT2 path-hunt procedure of the multiple VT2 path-hunt procedure of FIG. 52;

FIG. 60 is a flow diagram of multiple VT1.5 path-hunt procedure of the broadband path-hunt procedure of FIGS. 32-33;

FIGS. 61-67 are a flow diagram of one VT1.5 path-hunt procedure of the multiple VT1.5 path-hunt procedure of FIG. 60;

FIG. 68 is a flow diagram of multiple DS-0 path-hunt procedure of the broadband path-hunt procedure of FIGS. 32-33; and

FIGS. 69-95 are a flow diagram of one DS-0 path-hunt procedure of the multiple DS-0 path-hunt procedure of FIG. 68.

DETAILED DESCRIPTION

FIG. 1 is a block diagram of an exemplary SONET switching system 100 in accordance with the invention. System 100 is of the time-space-time (T-S-T) type with 64 input time-slot interchangers (TSIs) 131 connected to system input links 111 through elastic stores 121 and their output links 161, a central 64.times.64 time-multiplexed switch (TMS) 120 connected to output links 17 1 of TSIs 131, and 64 output time-slot interchangers 141 connected to TMS output links 181 and to system output links 151. Input TSIs 131 each receive the 9720 bytes of SONET STS-12 frames (FIG. 2) incoming on their respective input links 161 after they are aligned by elastic stores 121. A central control processor 110 controls system 100 and, in particular, performs path hunts through the system and controls the various switching elements CTSIs, TMS) in accordance with the path-hunt results.

It is well-known in the art that, in an N.times.N switching fabric, 2N paths are needed through the switch in order to obtain strictly-non-blocking performance. It is also well-known to obtain the 2N paths through a T-S-T switch by duplicating the T-S-T stages and operating the two duplicate fabrics in parallel. This duplication is assumed but not shown in FIG. 1 in order to avoid undue complexity of the illustration.

As was mentioned previously, FIG. 2 is a SONET STS-12 frame map. Note that the 90 columns of each of the twelve included STS-1 frames include four overhead columns (columns 0-3) as well as two stuff columns (columns 32 and 61 ). FIG. 2
illustrates the four columns used for a single VT2 virtual tributary. The four columns are evenly spaced apart by 21 columns (excluding stuff columns). Other virtual tributary rates VT 1.5, VT3, VT6 may also be accommodated within the format. A single DS-0 (64 kilobits-per-second) channel represents a single byte of the STS-12 frame.

Note that the layout of the 9720 bytes of a single 125-microsecond frame is depicted in three dimensions, with the order of transmission (1-2-3) as shown on the right-hand side of FIG. 2. The twelve STS-1 frames are thus transmitted in a byte-interleaved manner. One byte of the same row and column of each STS-1 frame is transmitted in succession, followed by one byte of the same row and next column of each STS-1. When one byte of each column of a row of each STS-1 frame has been transmitted, transmission proceeds to the first column of the next row of each STS-1 frame, and the process repeats.

Returning to FIG. 1, each input TSI 131 is capable of switching any of the 9720 bytes, or time slots, of an STS-12 frame received from an elastic store 121 to any other byte position, or time slot, on a time-multiplexed link 171 to TMS 120; all time-slot interchanging occurs within the boundaries of individual STS-12 frames; each output TSI 141 has a like capability. The SONET STS-12 format is maintained internally within system 100, with the exception that a parity bit is added to each eight-bit byte for internal transmission.

A first illustrative embodiment of a TSI 131 or 141 is shown in FIG. 3. As indicated, TSI 131 or 141 comprises three data buffer memories 301-303. Each memory 301-303 is double-buffered: it comprises two buffers 311 and 312, one of which is written while the other is read and the two of which alternate in time between being read and written. Each memory 301-303 has its data input connected to its TSI's input link 161 or 181 and receives all bytes of each incoming STS-12 frame. The data outputs of the three memories 301-303 of an individual TSI are connected to inputs of a selector 304 whose output is connected to the TSI's output link 171 or 151. At any one time, the data output of only one of the memories 301-303 of a TSI is selected by selector 304 as the output of that TSI. Memories 301-303 and selector 304 of each TSI 131 or 141 operate under control of a control memory 305.

Each memory 301-303 of a TSI 131 or 141 serves a different type of transmission rate. Memory 301 serves the DS-0 rate, memory 302 serves the VT rate, and memory 303 serves the STS-1rate. The different rates require different amounts of buffering, resulting in memories 301-303 being of different depths. A particular DS-0 channel appears in the data stream of an STS-12 frame only once, every 9720 bytes. Hence, memory 301 must buffer a full STS-12 frame, and so each buffer 311 and 312
of memory 301 is 9720 bytes deep. A particular VT channel appears in the data stream of an STS-12 frame at least once in every row of one of the twelve STS-1s, i.e., at least once in each horizontal plane of rows that make up the STS-12 frame. Hence, memory 302 must buffer one such horizontal plane. Every such horizontal plane comprises 12(one for each STS-1)-by-86(one for each column excluding overhead and stuff columns), or 1008, bytes. Therefore, each buffer 311 and 312 of memory 302 is 1008
bytes deep. Finally, a particular STS-1 channel appears in the data stream of an STS-12 frame every 12th byte. Hence, memory 303 must buffer 12 bytes of an STS-12, and so each buffer 311 and 312 of memory 303 is 12 bytes deep.

For ease of understanding, memory 301, operating under control of control memory 305, may be thought of as implementing a TSI 131 or 141 for 9720-byte frames (shown as STS-12 or DS-0 frame 30 in FIG. 2); memory 302 may be thought of as implementing a TSI for 1008-byte frames (shown as VT frame 40 in FIG. 2), and memory 303 may be thought of as implementing a TSI for 12-byte frames (shown as STS frame 50 in FIG. 2). Since the rate of a full STS-12 superframe is 125 .mu.s, memory 301
causes a buffering delay of 125 .mu.s for DS-0 rate traffic, memory 302 causes a buffering delay of only 1/9.125 .mu.s for VT rate traffic, and memory 303 causes a buffering delay of only 1/810.125 .mu.s for STS-1rate traffic. This is a significant improvement over the conventional buffering delay of at least the full-frame rate of 125 .mu.s for all traffic rates.

While the 9720 time-slot STS-12 has been referred to above as a superframe that comprises STS-1, VT, and DS-0 frames, an alternative and equivalent terminology is to refer to the STS-12 as a frame and to refer to the STS-1s, VTs, and DS-Os as sub-frames. For ease of discussion, the STS-12s, STS-1s VTs, and DS-Os will all be referred to below merely as frames.

FIGS. 4-6 collectively make up a first illustrative implementation of TSI 131 or 141 of FIG. 3. FIG. 4 depicts various frame-byte, or time-slot, counters that serve as control memory 305 address generators. Although the bytes received by input TSI 131 comprise eight bits, the internal time slots comprise an additional ninth parity bit; accordingly, a 9-bit byte clock CLK/9 signal line 520 is used to drive each of four time-slot counters: a modulo-12 counter 501, a modulo-90 counter 502, a modulo-1008 counter 506, and a modulo-9720 counter 511. The counters are reset by a FRM signal line 521 at the end of each STS-12 or DS-0 frame 30. Modulo-12 counter 501 generates a four-bit STS ADDRESS, and when it reaches its terminal count, at the end of an STS frame 50, it generates a terminal count (TC) signal to toggle a flip-flop 504 that generates an STS.sub.-- FRM signal in response, and to enable modulo-90 counter 502. Accordingly, modulo-90 counter 502 counts the 90 columns of the STS-1
frame format (FIG. 2) and generates a corresponding COL signal. When it reaches its terminal count, modulo-90 counter 502 also generates a TC signal. The TC signal outputs of both counters 501 and 502 are connected to inputs of an AND gate 503. Thus, when both modulo-12 counter 501 and modulo-90 counter 502 reach their terminal count, AND gate 503 generates a VT.sub.-- FRM.sub.-- END signal to indicate the end of a VT frame 40, and also toggles a flip-flop 505 to generate a VT.sub.-- FRM signal. The VT.sub.-- FRM.sub.-- END signal is used to reset modulo-1008 counter 506. The COL signal is transmitted to inputs of each of three comparators 507, 508, 509, whose outputs effectively disable modulo 1008 counter via NOR gate 510 for columns<=3, =32, or =61, whereby the overhead and stuff columns are not counted as part of VT frame 40. Modulo- 1008 counter 506 generates a 10-bit VT.sub.-- ADDRESS signal. Modulo-9720 counter 511 generates a 14-bit DS-0 address signal, and when it reaches its terminal count, at the end of a DS-0 frame 30, it generates a TC signal to toggle a flip-flop 512 that generates a DS0.sub.-- FRM signal in response.

FIG. 5 is a diagram of the circuitry that generates control data for storage in control memory 305 of a TSI 131 or 141 from information supplied as a result of a path-hunt performed by control processor 110. This control information specifies which incoming time-slot of an incoming STS-12 frame is to be switched to which outgoing time-slot of the corresponding outgoing STS-12 frame. Since system 100 is adapted to establish connections of three types of rates (that is, STS-1, VT, and DS-0
connections), and treats each type as having its own frame size (that is, respectively, STS frame 50, VT frame 40, and DS-0 frame 30), the control circuitry must be able to distinguish which time slots belong to which of these three types of frames 30,
40, and 50.

At least two possible ways of accomplishing this distinction offer themselves. One is to use the same sequential numbers to designate the same sequential time slots of all three types of frames, but associate with each number an indication (e.g., a separate number) that indicates which type of frame is being referred to. The other is to use numbers from different number ranges to designate time slots of the different frame types, whereby the range used serves as the indication of which frame type is being referred to. The illustrative implementation shown in FIGS. 5-7 adopts the latter approach.

The time-slot coding table that is used to identify both the type of connection (type of frame) as well as the initial time slot of that connection is shown in FIG. 7. As shown, a VT frame 40 address is encoded with the four most-significant bits having a binary value of 1110 (or a hexadecimal value of 0.times.E), and an STS frame 50 address is encoded with the four most significant bits having a binary value of 1111 (or a hexadecimal value of 0.times.F). The remaining bits for a VT or an STS frame define the first time slot of that connection. DS-0 connections, which represent a single time slot, are encoded by decimal numbers from 0 through 9719.

Returning to FIG. 5, the path-hunt information that defines a particular single connection selected by control processor 110 is received from processor 110 in three registers: an input time-slot register 601, an output time-slot register 602, and an offset register 603. Contents of output time-slot register 602 identify a particular time-slot at the output of a TSI 131 or 141 according to the convention of FIG. 7. Contents of input time-slot register 601 identify, also according to the convention of FIG. 7, the input time-slot that is to be switched to the output time-slot identified by register 602. Circuitry associated with input time-slot register 601 in FIG. 5 generates the control data that are to be stored in control memory 305. Circuitry associated with output time-slot register 602 in FIG. 5 determines at which address of memory 305 the just-mentioned control data are to be stored. The addresses of control memory 305 have a one-to-one correspondence to the 9720 output time slots of an STS-12 frame output by a TSI 131 or 141.

Offset register 603 receives the constant offset, or spacing between data-bearing columns of an STS-12 frame, that is necessary for the type of VT connection being set up. For example, for a VT2 connection, an offset of 21.12=252 (decimal) would be stored in offset register 603. The stored offsets are 336, 168, or 84 for the other VT1.5, VT3, and VT6 connections, respectively. Contents of offset register 603 are null for a non-VT connection. Preferably, an additional register (not shown) further receives information that selects one of the duplicate switching fabrics that were discussed in conjunction with FIG. 1.

Control memory 305 is updated on-the-fly. Normally, control memory 305 is only read, in a cyclical manner. When it is necessary to change a word of control memory 305, the circuitry of FIG. 5 waits until occurrence of the cycle during which that word of control memory 305 is normally read. It then changes the cycle to a write cycle, writes the new data word into control memory 305, and at the same time supplies that data word to the other circuitry of TSI 131 or 141 in place of the now-overwritten data word that would have normally been read from control memory 305.

Comparators 609 and 610 respectively determine whether the four most-significant bits in register 602 define a VT or an STS connection. The respective VT and STS outputs of comparators 609 and 610 control a selector 617. If the contents of register 602 define an STS connection, a control memory 305 write-enable (CMWE) signal is generated by selector 617 each time the four least-significant bits of register 602 are equal to the STS ADDR generated by modulo-12 counter 501, as indicated by the output of a comparator 614. If the contents of register 602 define a DS-0 connection (signified by no match being detected at comparators 609 and 610), a CM.sub.-- WE signal is generated by selector 617 during the time slot when the 1.4 bits of register 602 are equal to the DS-0 ADDR generated by modulo-9720 counter 511, as indicated by the output of a comparator 615.

Whereas each STS connection occurs once during each STS frame 50 and each DS-0 connection occurs once during each DS-0 frame 30, each VT connection occurs one or more times during each VT frame 40. Hence, the matter is more complicated when the contents of register 602 define a VT connection. For the case of a VT connection, there is provided an S-R flip-flop 618 that is set by the VT.sub.-- FRM.sub.-- END output of gate 503 of FIG. 4 and that is reset by the CM.sub.-- WE output of selector
617. When it becomes set at the end of an STS-1, flip-flop 618 generates a VT.sub.-- STRT signal that controls a selector 611 and causes selector 611 to select a first one of its two inputs for connection to its output. The first input of selector 611
is connected to the nine least-significant bits of output time-slot register 14, whereas the second input of selector 611 is connected to the output of a register 612.

When the contents of register 602 define a VT connection, either the contents of register 612 or the nine least-significant bits of output time-slot register 602 are transmitted by a selector 611 to comparator 616, depending upon whether the first or a subsequent occurrence of the VT connection in a VT frame 40 is being searched for. When those bits are the same as the VT ADDR generated by modulo-1008 counter 506, as indicated by comparator 616, selector 617 generates a CM.sub.-- WE signal. The output of selector 611 is also added by an adder 613 to the contents of offset register 603, and the sum is stored in register 612. The contents of register 612 are transmitted via selector 611 to comparator 616, and a CM.sub.-- WE is generated by selector 617 during the next occurrence of the VT connection in this VT frame 40. This process repeats throughout each VT frame 40.

Preferably, comparator 616 is disabled, by VT.sub.-- DISABLE signal generated by gate 510 of FIG. 5, during the occurrence of output time slots that correspond to the overhead and stuff columns of an STS-1. This disabling of comparator 616
lessens the possibility of a spurious, erroneous, output from comparator 616 while modulo-1008 counter 506 is disabled.

As was mentioned previously, the information that is written in control memory 305 (FIG. 6) comes from input time-slot register 601. The four most-significant bits are always written directly to control memory 305. In the case of an STS or DS-0
connection, the 10 least-significant bits are also written directly to control memory 305. However, for VT connections, an arrangement comprising a selector 605, an adder 607, and a register 606 generates the input time-slot identifiers for the VT connection, and transmits those via a selector 608 to control memory 305. The arrangement comprising elements 605-607 duplicates the arrangement comprising elements 611-613, with the exception that the first input of selector 605 is connected to the 10
least-significant bits of input time-slot register 601. Selector 608 is controlled by the VT output of comparator 609, analogously to selector 617.

FIG. 6 is a diagram of the circuitry that implements control by memory 305 over a TSI 131 or 141. The contents of locations 306 of memory 305 represent the input-time-slot to output-time-slot assignment that is to be effected by a TSI 131 or 141
for each STS-12 frame. Because an STS-12 or DS-0 frame 30 has 9720 time slots, memory 305 is 9720 words deep. Addresses of memory 305 words are sequenced-through by the DS-0 ADDR generated by modulo-9720 counter 51 1 of FIG. 4. Normally, CM.sub.-- WE signal line is not asserted and the words of memory 305 are cyclically read out, one word per time-slot interval, to provide on an ADDR bus 701 the address of a word of the appropriate one of data memories 301-303 that is to be written out as the output of the TSI during that instant time-slot. A word of control data is written into memory 305 in response to the CM.sub.-- WE signal line being asserted. In response to this assertion, the fourteen-bit address CM.sub.-- DATA that is generated in FIG. 5
is output by a gate 701 onto ADDR bus 701, from where it is both written into memory 305 and made available to the other circuitry of FIG. 6 in place of the address that would otherwise normally have been read out of memory 305.

As was mentioned previously, each memory 301-303 serves a different one of the STS, VT, and DS-0 connection types. Memories 301-303 are double-buffered: each of the two buffers 311 and 312 is alternatively written during one corresponding frame period and is read during the next corresponding frame period. The data input DATA IN, which corresponds to link 161 or 181, is connected to all three of data memories 301-303, and each incoming STS-12 frame is written into each one of these memories
301-303. At each memory 301-303, DATA IN is connected through a respective one of selectors 731-733 to the data inputs of both buffers 311 and 312. Which buffer 311 or 312 is written at any given time is controlled at each memory 301-303 respectively by the STS.sub.-- FRM, VT.sub.-- FRM, and DS0.sub.-- FRM signals, which control the outputs of selectors 731-733, respectively.

Addresses are conveyed to data memories 301-303 in the following manner. At each memory 301-303, ADDR bus 701 is connected to a first input of one, and the second input of another, of a pair of selectors 704-705, 711-712, and 721-722, respectively. The second input of the one, and the first input of the other, of the pair of selectors 704-705 is connected to the STS ADDRESS signal line from modulo-12 counter 501 of FIG. 4 and both selectors are controlled by the STS FRM signal line from flip-flop 504 of FIG. 4. The second input of the one, and the first input of the other, of the pair of selectors 711-712 is connected to the VT ADDRESS signal line from modulo-1008 counter 506 of FIG. 4 and both selectors are controlled by the VT.sub.-- FRM signal line from flip-flop 505 of FIG. 4. And the second input of the one, and the first input of the other, of the pair of selectors 721-722 is connected to the DS-0 ADDRESS signal line from modulo-9720 counter 511 of FIG. 4 and both selectors are controlled by the DS0.sub.-- FRM signal line from flip-flop 512 of FIG. 4. The output of each selector of the three pairs of selectors 704-705, 711-712, and 721-722 is connected to the address input of a different one of the buffers 311
and 312 of the corresponding one of the data memories 301-303.

ADDR bus 701 supplies the address of a data buffer word that is to be read while the STS ADDRESS, VT ADDRESS, and DS-0 ADDRESS lines supply the addresses of words of data buffers which are to be written with data incoming on DATA IN. And the STS.sub.-- FRM, VT.sub.-- FRM, and DS0.sub.-- FRM signal lines select which address is supplied to which buffer 311 and 312 of a memory 301-303. The addresses are alternately supplied to the two buffers 311-312 of each memory 301-303 so that--as was mentioned above--one of the buffers 311-312 is read while the other is written during one corresponding frame period, and vice versa during the next corresponding frame period.

The data outputs of both buffers 311 and 312 of each memory 301-303 are connected to the data inputs of a corresponding one of selectors 708, 7 15, and 725, respectively, whose outputs are in turn connected to the inputs of a selector 726. Selectors 708, 715, and 725 are respectively controlled by the STS.sub.-- FRM, VT.sub.-- FRM, and DS0.sub.-- FRM signal lines, so as to always select for output the one of the buffers 311 and 312 of the corresponding memory to which addresses are being supplied from control memory 305 via ADDR bus 701. Selector 304 in turn selects among the STS, VT, and DS-0 data memories under the control of VT.sub.-- EN and STS.sub.-- EN signals which are generated by comparators 702 and 703, respectively. Comparators 702 and 703 respectively determine whether the most-significant bits of the address generated by control memory 305 on ADDR bus 701 define a VT or an STS connection. Detection of neither a VT or an STS connection signifies a DS-0 connection. Selector 304 selects for output from TSI 131 or 141 on link 171 or 151 the output of the one of the memories 301-303 that corresponds to the detected connection type.

FIGS. 4 and 8-9 collectively make up a second illustrative implementation of TSI 131 or 141 of FIG. 3. As was mentioned previously, since system 100 is adapted to establish connections, or channels, of three types of rates, the TSI control circuitry must be able to distinguish between time slots of the three types of frames 30, 40, and 50 of FIG. 2. One way of accomplishing this distinction is illustrated in FIGS. 5-6. Another way, which uses the same sequential numbers to designate the same sequential time slots of all three types of frames but associates with each number an indication (e.g., a separate number) that indicates which type of frame is being referred to, is illustrated in FIGS. 8-9. A comparison of FIG. 5 with FIG. 8 and of FIG. 6 with FIG. 9 readily shows that they are identical in many respects. The same numerical designations are used for elements which they have in common. Only the differences are discussed below.

In FIG. 8, a bandwidth-type register 604 is substituted for comparators 609 and 610 of FIG. 5. Like registers 601-603, register 604 is loaded by control processor 110 with information defining a particular connection selected as a result of a path hunt. The contents of register 604 are two bits whose value identifies the bandwidth of the desired connection. The rest of FIG. 8 duplicates FIG. 5.

In FIG. 9, a bandwidth-type memory 755 is substituted for comparators 702 and 703 of FIG. 6, and produces the same two-bit output, with one bit representing the VT.sub.-- EN signal and the other bit representing the STS.sub.-- EN signal. Bandwidth-type memory 755 has locations 756 and is of the same depth as control memory 305, and is addressed and cycled-through in tandem with control memory 305 by DS-0 ADDR signals. Also like control memory 305, bandwidth-type memory 755 is enabled to be written with a new word of data in response to the CM.sub.-- WE signal. Associated with bandwidth-type memory 755 is a gate 751 which performs a function equivalent to that performed for control memory 305 by gate 701, and which allows bandwidth-type memory 755 to be updated on-the-fly and at the same time as control memory 305. Normally, CM.sub.-- WE signal line is not asserted and words of both memories 305 and 755 are cyclically read out. A word of control data is written into each memory 305
and 755 in response to the CM.sub.-- WE signal line being asserted. In response to this assertion, the two-bit VT or STS signal that is generated by bandwidth-type register 604 of FIG. 8 is output by gate 751 onto the VT.sub.-- EN, STS.sub.-- EN signal line, from where it is both written into memory 755 and made available to the other circuitry of FIG. 9 in place of the word of memory 755 that would otherwise normally have been read out of memory 755.

While FIG. 3 shows an embodiment of a TSI having physically separate data memories for each connection type, FIG. 10 shows an alternative embodiment of TSI 131 having logically separate data memories for each connection type implemented in a single physical memory. The memory is sized to accommodate the largest possible frame, i.e., a DS0 frame 30, and hence is the same physical memory as memory 301 of FIG. 3. It is therefore designated by the same numeral 301. The first 12 bytes of memory 301 serve as the equivalent of STS memory 303 of FIG. 3, and are designated as STS portion 303' in FIG. 10. The first 1080 bytes of memory 301 serve as the functional equivalent of VT memory 302 of FIG. 3, and are designated as VT portion 302' in FIG. 10. And the full memory 301 serves as the equivalent of DS0 memory 301 of FIG. 3, and is designated as DS0 portion 301' in FIG. 10. Just like the memories 301-303 of FIG. 3, memory 301 of FIG. 10 is double-buffered and comprises two buffers 311
and 312.

It will be noted that VT portion 302' consists of 1080 bytes of memory, as compared with 1008 bytes for VT 302 of FIG. 2. These extra 72 bytes are used to store the STUFF and OVERHEAD bytes that accompany each VT frame 40. These 72 bytes are discarded and ignored by memory 302 of FIG. 3, and could be handled in the same way in FIG. 10. However, for VT type calls, the appearance rate varies between 336, 252, 168, or 84 bytes, depending on the VT type. In order to allow TSI 131 or 141 to ignore these variances and make the hardware simpler, a common appearance rate of 1080 bytes is used in FIG. 10. This rate guarantees that at least one byte from every VT channel is stored in a buffer 311 or 312 before switching over to the other buffer
312 or 311 takes place.

In operation, memory 301 of FIG. 10 is used in the identical manner as memories 301-303 of FIG. 3. The use of buffers 311 and 312 alternates for each connection type at the rate commensurate with that connection's frame size, i.e., every 12
bytes for an STS connection, every 1080 bytes for a VT connection, and every 9720 bytes for a DS-0 connection. Due to the different frame rates of the different connections, it is possible that bytes may arrive, as part of one connection type, for storage in one of the buffers 311 or 312 while bytes are being read out of that buffer as part of another connection type. Hence, buffers 311 and 312 either are dual-ported devices, so as to accommodate simultaneous reads and writes, or are high-speed devices that support two successive cycles--both a read and a write--during successive halves of a single time--slot interval.

FIGS. 11--13 collectively make up a first illustrative implementation of TSI 131 of FIG. 10. A comparison of FIG. 4 with FIG. 11 shows that they are identical in many respects. The same numerical designations are used for elements which they have in common. Only the differences are discussed below.

In FIG. 11, a modulo-1080 counter 1506 replaces modulo-1008 counter 506 of FIG. 4, and the VT.sub.-- DISABLE circuit 507-510 is eliminated. Modulo-1080 counter 1506 counts the bytes that make up each horizontal plane of the STS-12 frame of FIG.
2. This plane may be referred to as an augmented VT frame 40', as it is composed of VT frame 40 plus the 72 bytes of the STUFF and OVERHEAD columns that lie in the same plane as the VT frame 40. And since the STUFF bytes are no longer being ignored but are being counted, the circuit 507-510 is no longer needed.

A comparison of FIG. 8 with FIG. 12 likewise shows that these figures are identical in many respects. The same numerical designations are used for elements which they have in common, and only their differences are discussed hereinbelow.

Since modulo-1080 counter 1506 of FIG. 11 includes the overhead and stuff columns (see FIG. 2) in its count, the spacing of addresses generated by counter 1506 of columns of a particular VT-rate channel is not regular in the augmented VT frame
40'--contrary to the VT frame 40--related output of modulo-1008 counter 506 of FIG. 4. This irregularity of spacing must be compensated for in FIG. 12 whenever the contents of offset register 603 are used to address a VT channel's columns. Accordingly, adders 607 and 613 of FIG. 8 are replaced in FIG. 12 by adders 1607 and 1613, respectively, and associated control comparators 1609 and 1610. Each control comparator 1609 and 1610 monitors the selector input to its corresponding adder, referred to as "old" address, and the adder output, referred to as "new" address. During any operational cycle when control comparator 1609 or 1610 determines that (a) "old" address is less than decimal 384 and "new" address is greater than decimal 383, or (b) "old" address is less than 732 and "new" address is greater than decimal 731, the control comparator causes its corresponding adder to increment new address by decimal 12.

Turning briefly to FIG. 13, the implementation shown in FIG. 13 also uses a bandwidth-type memory like the implementation shown in FIG. 9. In FIG. 9, each incoming byte is written into each data memory 301-303, and so bandwidth-type memory 755
need only indicate the bandwidth-type of each byte selected for output. But in FIG. 13, them is only one data memory 301 to write incoming data into, and therefore bandwidth-type memory 1755 of FIG. 13 must additionally indicate the bandwidth-type of each incoming byte. Bandwidth-type memory 1755 must therefore be provided with address control analogous to that which is provided to control memory 305. But because bandwidth-type memory 1755 relates to--indicates--the bandwidth of incoming bytes, unlike control memory 305 it must have its address control derived from the contents of input time-slot register 601. Returning to consideration of FIG. 12, there is accordingly provided circuitry 1620, 1611, 1612, 1623, and 1614-1618 which duplicates the circuitry 611, 612, 613, 610, and 614-618 of FIG. 9, but with the following exceptions: a first input of selector 1611 is connected to the output of input time slot register 601, selector 1611 is controlled by a signal VT-STRT' which is the output of flip-flop 1618, and the output of selector 1617 is designated as BW.sub.-- WE (bandwidth-type memory write enable).

Turning again to FIG. 13, bandwidth-type memory 1755 must indicate the bandwidth-type of each incoming byte. Accordingly, bandwidth-type memory 1755 is twice as wide as memory 775 of FIG. 9, and has two two-bit outputs. The VT.sub.-- EN, STS.sub.-- EN output corresponds to the output of memory 755 and indicates the bandwidth-type of the byte selected to be read out of data memory 301. A VT.sub.-- EN', STS.sub.-- EN' output indicates the bandwidth-type of the byte being written into data memory 301.

As in the case of FIG. 9, locations 306 of control memory 305 and locations 1756 of bandwidth-type memory 1755 are addressed and read out in a cyclical manner by DS-0 ADDRESS. The VT.sub.-- EN, STS.sub.-- EN output of memory 1755 controls a selector 1202, while the VT.sub.-- EN', STS.sub.-- EN' output controls a selector 1201. Selector 1202 has the STS.sub.-- FRM, VT.sub.-- FRM, and DS0.sub.-- FRM signals connected to its inputs, while selector 1201 has the inverted values of these same signals connected to its inputs. It had been explained previously that each of these signals changes its value during successive occurrence of the corresponding frame type. Consequently, for any one of the three frame types 30, 40, 50, selectors 1201
and 1202 each output a different value during any one frame, and each changes the value of its output during successive frames.

The VT.sub.-- EN', STS.sub.-- EN' output of memory 1755 further controls the output of a selector 1200, which has STS.sub.-- ADDRESS, VT.sub.-- ADDRESS, and DS0.sub.-- ADDRESS signal lines connected to its inputs. Consequently, selector 1200
outputs the address that corresponds to the frame type of the bit that is presently to be written into memory 301. The output of selector 1200 and the output of control memory 305 are connected to inputs of a selector 1203. The output of selector 1203
is connected to address inputs of buffers 311 and 312. Selector 1203 operates under control of a clock-generated read-write R/W signal. R/W signal changes value twice during each time-slot interval. During the first half of the time-slot interval, the R/W signal indicates a data memory-write cycle and causes selector 1203 to supply to memory 301 the address selected by selector 1200.

The output of selector 1201 is connected to an input of an AND gate 1204, and to an inverted input of an AND gate 1205. Second inverted inputs of gates 1204 and 1205 are connected to R/W signal line. Output of gate 1204 is connected to a write-enable (WE) input of buffer 31 1, while output of gate 1205 is connected to a WE input of buffer 312. Gates 1204 and 1205 enable the one of the two buffers 311 and 312 that is presently selected by the output of selector 1201 to be written with a byte of data incoming to buffers 311 and 312 on DATA IN line during the write cycle of each time-slot interval.

During the second half of each time-slot interval, the R/W signal indicates a data-memory-read cycle and causes selector 1203 to supply to memory 301 the address that is output by control memory 305. Both buffers' WE inputs are disabled during this cycle, and so both buffers are read. Outputs of buffers 311 and 312 are connected to inputs of a selector 1206, which operates under control of the output of selector 1202. Selector 1206 selects the output of the one of the buffers 311 and 312
that is picked by the output of selector 1202 as the output of TSI 131 and transmits it on DATA OUT line.

New control information from CM.sub.-- DATA line (from HG. 12) is written into control memory 305 under control of gate 701 and the CM.sub.-- WE signal, as was the case in FIG. 9. Bandwidth-type memory 1755 is written in a corresponding manner. The VT.sub.-- EN, STS.sub.-- EN and VT.sub.-- EN', STS.sub.-- EN' inputs/outputs of memory 1755 each have a respective gate 1751 and 1752 connected thereto. Gate 1751 operates under control of the CM.sub.-- WE signal, while gate 1752 operates under control of the BW.sub.-- WE signal (from FIG. 12). These signals also control the writing of the respective parts of the bandwidth-type memory 1755. The inputs of gates 1751 and 1752 are connected to the VT, STS output of bandwidth-type register 604
(from FIG. 12). When the CM.sub.-- WE line is asserted, a normal read cycle of the data-memory-output-indicating portion (i.e., VT.sub.-- EN, STS.sub.-- EN) of bandwidth-type memory 1755 is converted into a write cycle. At the same time, gate 1751
supplies the VT, STS output of bandwidth-type register 604 to VT.sub.-- EN, STS.sub.-- EN signal line, from where the VT, STS output is written into bandwidth-type memory 1755. Similarly, when the BW.sub.-- WE line is asserted, a normal read cycle of the data-memory-input-indicating portion (i.e.. VT.sub.-- EN', STS.sub.-- EN') of bandwidth-type memory 1755 is converted into a write cycle and, at the same time, gate 1752 supplies the VT, STS output of register 604 to VT.sub.-- EN', STS.sub.-- EN' signal line from where this output is written into memory 1755.

FIG. 14 shows an alternative embodiment of the single-shared-memory TSI implementation. Unlike the implementation of FIG. 10, this implementation writes each incoming full STS-12 frame into data memory sequentially, and thereby dispenses with the requirement of knowing to which one of the frame types 30, 40, and 50 an incoming byte belongs. Like the implementation of FIG. 10, this implementation makes use of a single double-buffered data memory, designated as 1301. Unlike in FIG. 10, however, the two buffers 311 and 312 of FIG. 14 are implemented in sequence in a single physical memory device. To allow memory 1301 to be simultaneously read and written, memory 1301 is implemented as a dual-ported device. Each buffer 311 and 312 is sized to accommodate a full STS-12 frame, which is also the DS-0 frame 30. Hence, each buffer 311 and 312 of FIG. 14 is of the same size as the corresponding buffers of FIG. 10, and memory 1301 is 2.9720=19440 words deep.

Like the implementation of FIG. 10, the implementation of FIG. 14 has logically separate data memories for each connection type which share the same physical memory locations. However, because an STS-12 frame is written into data memory 1301
sequentially, as if it were composed only of DS-0 type channels, each sequential 12 bytes of memory 1301 serve as the equivalent of STS memory 303 of FIG. 3 and STS portion 303' of FIG. 10. Hence, there are a plurality of logical STS memories, with each sequential 12 bytes being designated as a separate STS portion 303". Similarly, each 1080 bytes of memory 1301 serve as the functional equivalent of VT memory 302 of FIG. 3 and VT portion 302' of FIG. 10, and so each sequential 1080 bytes of memory 1301
are designated as a separate VT portion 303". And each full buffer 311 or 312 serves as the equivalent of DS-0 memory 301 of FIG. 10, and is designated as DS0 portion 301".

The addresses that are stored in control memory 305 for sub-rate calls are controlled so as to read from the preceding sub-frame (i.e., the preceding STS portion 303" for an STS sub-rate, or the preceding VT portion 302" for a VT subrate) to the sub-frame that is being written, irrespective of whether the read and written sub-frames are in the same or in different buffers 311 or 312. The addresses are calculated algorithmically, as required when the frame that is being read is in one buffer 311
while the frame that is being written has overlapped into the other buffer 312, and vice versa. The calculation views memory 1301 as a single continuous buffer of 19,440 bytes.

FIGS. 15-17 collectively make up an implementation of TSI 131 or 141 of FIG. 14. A comparison of FIG. 15 with FIG. 4 readily shows that they are identical in many respects. The same numerical designations are used for elements which they have in common. Only the differences are discussed below.

Since reading and writing of sub-frames in FIG. 14 occurs in adjacent portions 301"-303" irrespective of whether or not they lie in the same or in different buffers 311 and 312, the toggle flip-flops 504, 505, and 512 of FIG. 4 are no longer needed to indicate a changeover between buffers 311 and 312. Hence, these flip-flops are eliminated from FIG. 15. Also, since data memory 1301 of FIG. 14 is twice as deep as data memory 301 of FIG. 3, modulo-9720 counter 511 of FIG. 4 is replaced in FIG. 15 with a modulo-19440 counter 1511. Counter 1511 is reset only once every two STS-12 frame periods, i.e., at half the STS-12 frame rate, and hence counter 1511 is provided with a FRM/2 lead 1522 which is connected to its reset (RST) input and which resets counter 1511 once every 19440 time slots.

Additionally, FIG. 15 includes circuitry 1550-1555 for generating an EN.sub.-- MATCH signal that directs the circuitry of FIG. 16 to commence searching for the address of a control memory 305 location that is to be written, only at the beginning of an even STS-12 frame (the beginning of buffer 311 of FIG. 14), and for generating a STOP signal that directs the circuitry of FIG. 16 to end the search at the end of an odd STS-12 frame (the end of buffer 312 of FIG. 14). Circuitry 1550-1555 includes a D-type flip-flop 1550 whose D input is latched to a logical "1" level and whose CLK input is connected to a START signal line. Control processor 110 asserts START signal line after loading the registers of FIG. 16, to indicate that it has made available the information necessary for the search to commence. The output of flip-flop 1550 is connected to one input of an AND gate 1551, whose other input is connected to the TC output of modulo-19440 counter 1511. The output of gate 1551 is connected to the S input of an S-R flip-flop 1553 and to the R input of an S-R flip-flop 1554. The output of flip-flop 1553 is connected to the EN.sub.-- MATCH signal line and to the D input of a D-type flip-flop 1555 whose output is connected to one input of an AND gate 1552. The CLK input of flip-flop 1555 is connected to CLK/9 line 520, to delay the propagation of the EN.sub.-- MATCH signal to AND gate 1552 by one time-slot period. The other input of gate 1552 is connected to the TC output of counter 1511, and the output of gate 1552 is connected to the S input of flip-flop 1554. The output of flip-flop 1554 forms the STOP signal, and is further connected to the R inputs of flip-flops 1553 and 1550. Assertion of START signal by control processor 110 enables the next assertion of the TC output by counter 1511 to cause flip-flop 1553 to generate the EN.sub.-- MATCH signal. The next assertion of the TC output by counter 1511 causes flip-flop 1554 to generate the STOP signal, which in turn causes flip-flop 1553 to cancel the EN.sub.-- MATCH signal.

Turning to FIG. 16, a comparison thereof with FIG. 8 shows their CM.sub.-- WE and VT.sub.-- START signal-generation portions to be identical. The same numerical designations are used in both figures for elements which they have in common, and only the differences are discussed below.

In the data memory implementation shown in FIG. 14, the input time slot that corresponds to (that is to be output during) a particular output time slot is not always stored in the same data memory location. Rather, that input time slot moves from portion 301-303 to successive portion 301"-303" in memory 1301. It is therefore no longer sufficient for an input time slot register, such as register 601 of FIG. 8, to specify the address of only a single data memory location. Rather, the register must now specify the addresses of a whole sequence of data memory locations. Consequently, the simple input time-slot register 601 of FIG. 8 is replaced in FIG. 16 with an input time-slot register/modulo-19440 counter 160 1. For each change in switched connections being effected, control processor 110 loads register/counter 1601 with an initial value. From that initial value, register/counter 1601 increments its count during each time-slot period, thereby producing the correct input time slot address during every occurrence of the corresponding output time slot (e.g., during every assertion of CM.sub.-- WE signal line).

The initial value loaded by control processor 110 into register/counter 1601 is equal to 19440 minus the frame size of the channel being switched (9720 for a DS-0 channel; 1080 for a VT channel; 12 for an STS-1 channel) plus the sequence number, within the sequence of 19440 time slots of two STS-12 frames, of the first input time slot of the subject channel that is being switched. In other words, it specifies the data memory 1301 address in the very last portion 301"-303" that corresponds to the frame size of the channel that is to be switched, at which address is stored the input time slot that should be switched out during the first occurrence of the output time slot that corresponds to the switched channel. Conceptually, one can view this as the drawing of HG. 14 being overlayed onto a cylinder such that the bottom wraps around to join with the top to form a seamless circular buffer.

The reason for this initial value is the following. An output time slot and the writing of memory 1301 occur during the same time slot. Hence, the output time slot is properly thought of as occurring in the partition 301"-303" that is then being written. By action of the EN.sub.-- MATCH signal generated in FIG. 15, comparators 614-616 start looking for, and find, an output time slot match in (i.e., during the writing of) the first partition 301"-303" of data memory 1301. It will be recalled that reading from data memory 1301 is done in a partition 301"-303" that immediately precedes the partition 301-303 that is being written. For the first partition 301"-303" of memory 1301, the immediately-preceding partition is the last partition 301-303 (on account of memory 1301 being a circular buffer). Hence, upon the detection by comparators 614-616 of the first matching output time slot, in the first partition 301"-303" of memory 1301, register/counter 160 1 must indicate the reading of an input time slot from the immediately-preceding partition, which is the last partition 301"- 303" of memory 1301. And that is precisely what the initial value of register/counter 1601 does.

The stuff and path overhead columns neatly divide the payload envelope of an STS-N frame into three partitions of equal size, as shown in FIG. 2. In turn, the 12 columns of a VT group neatly divide between the partitions, with four columns lying in each partition. Hence, an equal number of columns of any one of the rates VT1.5, VT3, and VT6 lie in each of the partitions. Consequently, the distance (in time slots) between the input time slots and output time slots is constant, regardless of the partition.

Unfortunately, the same is not true for the VT2 rate. A VT2 rate occupies 4 columns of the 12 columns of a VT group, and these 4 columns cannot be evenly divided between the three payload partitions created by the POH and stuff columns. Hence, the distance from the input time slots to the output time slots will change if they happen to fall into different partitions, and this lack of regularity must be compensated for. This is the purpose of the circuits 1605-1609. The compensation is necessary when a column of input time slots of a VT2 rate lies to one side of a stuff or POH column while the column of corresponding output time slots lies to the other side of that stuff or POH column. In that case, the address generated by register/counter 1601 is high or low by 12 (the number of time slots in one row of the stuff or POH column). Control processor 110 knows when this will happen, based on the following consideration.

There are N.21 VT2 channels in an STS-N frame. For all N.21 VT2 channels, their first column lies in the first partition and their last--fourth--column lies in the last--third--partition. For the first set of N.7 of the N.21 VT2 channels, their second column lies in the first partition and their third column lies in the second partition. For the next set of N.7 VT2 channels, both their second and third columns lie in the second partition. And for the last set of N.7 VT2 channels, their second column lies in the second partition while their third column lies in the third partition. Consequently, no compensation is ever required for the first and fourth columns of a VT2 channel irrespective of which other VT2 channel it is being switched to, but compensation may be required for the second and third columns of a VT2 channel and depends upon the relative positioning of the input VT2 and output VT2 within the three N.7 sets of VT2 channels in an STS-N frame. The requisite compensation, for each of the four columns of a VT2, is shown in the table of FIG. 18.

Consequently, when loading registers 602-604 and 1601 of FIG. 16 with information defining a switched connection for a VT2 channel, control processor 110 loads the corresponding one of the entries of the table of FIG. 18 into a four-word shift register 1605. For switched connections of channels other than VT2 channels. processor 110 loads register 1605 with all zeros. Furthermore, in the international SDH standard, stuff columns are positioned directly next to the overhead columns.. Hence, above-described problem does not arise, i.e., there is no need for any compensation. Consequently, when the system of FIG. 1 is switching SDH framers, processor 110 loads register 1605 with all zeros for all switched connections including VT2
connections.

The generation of input data to control memory 1301 of FIG. 17 by the circuitry of FIG. 16 occurs as follows. Following loading by control processor 110 of registers 602-604, 1601, and 1605 with the results of a path hunt and issuance of the START signal, circuits 611-617 generate the CM.sub.-- WE signal upon occurrence of the desired output time slot. The CM.sub.-- WE signal sets R-S slip-flop 1609, whose output enables AND gate 1606 to start supplying CM.sub.-- WE signals to the clock input of register 1605 and also enables AND gate 1607 to start supplying time-slot interval signals from CLK/9 signal line 520 to the clock input of register/counter 1601. The output of flip-flop 1609 also enables register/counter 1601 and register 1605
to start responding to their clock inputs.

Acting as a clock input to register 1605, the CM.sub.-- WE signals causes register 1605 to output the first of its four words. The output of register 1605 is connected to its input to form a recirculating register, and also to one end of a summing circuit 1608 whose other input is connected to the output of register/counter 1608. Circuit 1608 compensates the input time-slot address generated by register/counter 1601 by the value supplied by register 1605 and outputs the compensated address as CM.sub.-- DATA to control memory 1305 of FIG. 17. The output of register 1605 remains constant until the next occurrence of the CM.sub.-- WE signal, which causes register 1605 to output the next one of its four words. Generation of the STOP signal in FIG. 15 at the end of a read cycle through data memory 1301 of FIG. 14 resets flip-flop 1609, thereby disabling both AND gates 1606 and 1607 and the outputs of register/counter 1601 and register 1605.

Since all input time slots are stored sequentially in data memory 1301 of FIG. 14, no bandwidth-type indication is required to supplement the output of control memory 1305 in the implementation of FIGS. 15-17. Hence, turning to FIG. 17, a bandwidth-type memory is not used. Control memory 1305 has the same depth as data memory 1301--19440 word locations 1306. Memory 1305 is controlled in the same manner as explained for the illustrations discussed previously, e.g., HG. 13. The output of control memory 1305 is connected to a first input of a selector 1703 whose second input is connected to DS-0 ADDR. Selector 1703 operates under control R/W signal line to supply both split-cycle read and write addresses to the address input of data memory 1301, similarly to selector 1203 of FIG. 13.

The contents of memory 1305 are programmed such that during every data memory 1301 read/write cycle, the most-significant-bit output of memory 1305 has the opposite value of the most-significant bit of DS-0 ADDR. Thus, buffer 311 of memory 1301
is read while buffer 312 is written, and vice versa. The R/W signal line is also connected to the write enable (WE) control input of memory 1301. The data (D) input of memory 1301 is connected to the DATA IN line and the output of memory 1301 is connected directly to the DATA OUT line which represents link 171 or 151.

Yet another implementation of TSI 131 or 141 of FIG. 4 is shown in FIGS. 19-21. The departure of this implementation from that of FIGS. 15-17 is that it uses a control memory 305 that is only half as deep. Because of this, only half of the count that was previously required is needed to cycle through the addresses of this reduced-size control memory 305. Modulo-19440 counter of FIG. 15 is therefore replaced in FIG. 19 with a modulo-9720 counter 511 which is reset by the FRM signal line
521. But because the reduced-size control memory 305 has a capacity to address only one of the buffers 311 and 312 of data memory 1301, it must be used twice and its output must be modified during the second use in order for it to address all of data memory 1301. For this purpose, there is included in FIG. 19 a toggle flip-flop 512 which duplicates the flip-flop 512 of FIG. 4. In other respects FIGS. 15 and 19 are identical.

Again, because control memory 305 can hold only half of the addresses of control memory 1305 of FIG. 17, input time-slot register/modulo-19440 counter 1601 of FIG. 16 is replaced in FIG. 20 with an input time-slot register/modulo-9720 counter
2601 and an S-R flip-flop 2602. Flip-flop 2602 is set by control processor 110 at the same time as it loads the registers of FIG. 20. It is reset by the terminal count of register/counter 2601. The output of flip-flop 2602 forms a FRM.sub.-- OFFSET signal which indicates whether the present count of register/counter 2601 is generating an address of buffer 311 or of buffer 312 of data memory 1301. In other respects, FIGS. 16 and 20 are identical.

FIG. 21 parallels FIG. 17 in many respects, and the same numerals are used to designate elements common to both figures. Only the differences are discussed.

The FRM.sub.-- OFFSET signal is written into control memory 305 along with the CM.sub.-- DATA signal. The writing thereof into locations 306 of memory 305 is controlled by a gate 2150 in the identical manner as gate 701 controls the writing of the CM.sub.-- DATA signal into memory 305.

The FRM.sub.-- OFFSET signal output of gate 2150 and of control memory 305 forms an input to an exclusive-OR gate 2151, whose output is connected to the first input of selector 1703 in parallel with the CM.sub.-- WE signal output of gate 701 and of control memory 305. The DS0.sub.-- FRM signal is connected to the second input of selector 1703 in parallel with the DS0.sub.-- ADDRESS signal, and also forms the second input to exclusive-OR gate 2151. Therefore, the FRM-OFFSET signal acts as an indicator of which one of buffers 311 and 312 is being read, and the DS0.sub.-- FRM signal acts as an indicator of which one of buffers 311 and 312 is being written.

It will be remembered, from the discussion of FIG. 16, that the initial value of register/counter 1601 points into the last partition 301"-303" of memory 1301. To have the same be true of register/counter 2601, flip-flop 2602 is initialized by control processor 110 with a value of "1". Thereafter, when register/counter 2601 begins to count and reaches its terminal count for the first time, its count value in conjunction with the FRM.sub.-- OFFSET value output by flip-flop 2602 points to the last location of memory 1301. Flip-flop 2602 is therefore reset at this time, so that the next count of register/counter 2601 in conjunction with the FRM.sub.-- OFFSET value will point to the first location of memory 1301. Significantly, the value of FRM.sub.-- OFFSET will not change again until flip-flop 2602 is set by control processor 110 at the beginning of a new call setup. That means that only those locations in control memory 305 that are read during the occurrence--the writing--of the first partition 301"-303" of memory 1301 have stored an FRM.sub.-- OFFSET value of "1 ". But the contents of control memory 305 are used twice: for the first time during the occurrence--the writing--of buffer 311 and a second time during the occurrence--the writing--of buffer 312. Consequently, those same locations in control memory 305 that have stored an FRM OFFSET value of "1" will be read during the occurrence--the writing--of the first partition 301"-303" of the second buffer 312 of memory 1301. But during this occurrence of the first partition 301"-303" of the second buffer 312, the last partition 301"-303" of the first buffer 311 should be read. Hence, the stored FRM OFFSET value of 1 is incorrect and must be changed to a 0. This is the function of exclusive-OR gate 2151.

During the occurrence of the second and all subsequent portions 301"-303" of the second buffer 312, reading should be of the first and subsequent portions 301"-303" of the second buffer and not of the first buffer 311. But, as was explained above, the FRM.sub.-- OFFSET value stored by control memory 305 locations used at this time is 0. Hence, the stored FRM.sub.-- OFFSET value of 0 is incorrect and must be changed to a 1. This is another function of exclusive-OR gate 2151.

Returning to FIG. 1, exercise of control over TMS 120 is implemented in much the same way as over a TSI 131 or 141. FIG. 22 shows an illustrative implementation of TMS 120. It comprises a plurality of output controls 1700, one for each TMS output link 181. Each output control 1700 comprises a selector 1702 and associated control memory 1701. Connected to the inputs of each selector 1702 are all of the TMS input links 171. Each selector 1702 operates under control of its own control memory 1701. During each time-slot interval, control memory 1701 of each selector 1702 selects one of the input links 17 1 of the corresponding selector 1702 for connection to its output link 181.

Just as there are numerous possible implementations of a TSI 131 or 141, there are correspondingly numerous implementations of output controls 1700. The implementation of an output control 1700 that corresponds to the TSI 131 or 141
implementation of FIGS. 4-6 is shown in FIG. 23. The implementation shares the circuitry of FIG. 4 with TSI 141 of its corresponding TMS output link 181. For the programming of control memory 1701, this implementation uses circuitry that duplicates that of FIG. 5 in many respects. TMS output time slot register 1802 duplicates the function of output time-slot register 602. Input port register 1801 serves a similar function to input time-slot register 601, but specifies which of the TMS input ports, or links 171, is to be connected by selector 1702 to the TMS output port, or link 181, during the time slot specified by register 1802. Offset register 1803 duplicates offset register 603. Similarly, elements 1809-1818 duplicate elements
609-618.

The output of input port register 1801 is connected to the input of a gate 1901, which serves the same function for control memory 1701 as gate 701 serves for control memory 305 of FIG. 6. Gate 1901 is controlled by the TMS-CM-WE output of selector 1817, as is the write enable input of control memory 1701. Like memory 305, control memory 1701 is cycled through by DS-0 ADDR. Control memory 1701 is 9720 word locations 1702 deep, one for each byte/time slot of an STS-12 frame.

The implementation of an output control 1700 that corresponds to the TSI 131 or 141 implementation of FIGS. 4 and 8-9 is shown in FIG. 24. The implementation shares the circuitry of FIG. 4 with TSI 141 of its corresponding TMS output link 181. For the programming of locations 1702 of control memory 1701, this implementation uses circuitry that duplicates that of FIG. 8 in many respects. Just as FIG. 8 is substantially identical to FIG. 5 but replaces comparators 609 and 610 with bandwidth-type register 604, the implementation of FIG. 20 is substantially identical to that of FIG. 23 but replaces comparators 1809 and 1810 with bandwidth-type register 1804, which duplicates the function of register 604 of FIG. 8. The same numerals are used in FIGS. 23 and 24 to designate elements that are common to both.

The implementation of an output control 1700 that corresponds to the TSI 131 or 141 implementation of FIGS. 11-13 is shown in FIG. 25. This implementation shares the circuitry of FIG. 11 with TSI 141 of its corresponding TMS output link 181. For the programming of control memory 1701, this implementation uses circuitry that duplicates portions of HG. 12. The implementation of FIG. 25 is substantially identical to that of FIG. 24 but replaces adder 1813 with an adder 2813 and control comparator 2810, which respectively duplicate adder 1613 and control comparator 1610 of FIG. 12. Control memory 1701 of FIG. 25 is again 9720 words deep, one for each byte/time slot of an STS-12 frame.

The implementation of an output control 1700 that corresponds to the TSI 131 or 141 implementation of FIGS. 15-17 is shown in FIG. 26. This implementation shares the circuitry of FIG. 15 with TSI 141 of its corresponding TMS output link 181. For the programming of control memory 1701, this implementation uses circuitry that duplicates portions of HG. 16. The implementation of FIG. 26 is substantially identical to that of FIG. 24. However, this embodiment, control memory 1701 is 19440 word locations 1702 deep, spanning the two STS-12 frames of storage of data memory 1301 of FIG. 14, and hence DS-0 ADDR is 15 bits wide. The information stored in control memory 1701 is identical for both STS-12 frames, i.e., the contents of the two halves of memory 1701 are duplicates of each other.

An alternative equivalent implementation is to make memory 1701 of FIG. 26 only half as deep, i.e., 9720 words deep, and addressed by only the 14 least-significant bits of DS-0 ADDR, i.e., addressed by DS-0 ADDR modulo 9720. alternative implementation corresponds to the TSI 131 or 141 implementation FIGS. 19-21.

As was mentioned previously, the switching fabric of FIG. 1--TSIs and TMS--would normally be duplicated and the two duplicate fabrics would be operated in parallel in order to obtain strictly-non-blocking performance. The implementations of output controls 1700 shown in FIGS. 22-26 assume that each output control 1700 of both duplicate TMSs 120 has its own, duplicate, circuitry for loading control memory 1701. An alternative implementation reduces the amount of required circuitry by sharing non-duplicated memory-loading circuitry among the pair of control memories 1701 of the corresponding output controls 1700 of the duplicate TMSs 120. In such a shared implementation, each FIG. 22-26 further includes a register (not shown) that is written by control processor 110 at the time of writing of the other registers to indicate which one of the pair of control memories 1701 is to be loaded.

As described above, the hardware of system 100 is configured to switch connections (also referred to herein as channels) at three different types of rates: STS-1, VT, and DS-0. However, system 100 is not limited to switching connections having these specific rates. Rather, a connection may have any rate up to and including the STS-12 rate, and system 100 allocates as much available bandwidth to each connection as that connection requires. Bandwidth is allocated in different-size blocks whose sizes correspond to the specific rates which the hardware is configured to switch. A connection's full allocated bandwidth will therefore comprise one: or more individually-allocated blocks of bandwidth preferably corresponding to c, ne more of the STS-1, VT, and DS-0 rates. Bandwidth allocation is accomplished hierarchically, such that as much of the required bandwidth is allocated in the largest available bandwidth blocks without wasting bandwidth, the remaining required bandwidth is allocated in the next-smaller available bandwidth blocks, and so until the connection's full bandwidth requirement has been met.

A characteristic of this approach is that each rate will suffer a different time delay through the switching system equal to the switch delay of that rate's corresponding frame. Therefore, for each call, the traffic switched at a higher rate will have to be delayed at the switch output to re-synchronize it with the call's traffic switched at the lowest rate used for that call. However, this is not expected to result in significant performance degradation, because calls spanning a wide range of rates are expected to be rare.

In view of this need to delay a call's traffic being switched at higher rates, it is necessary to retain this traffic at the switch output for some time without immediately overwriting it with subsequent switched frames of traffic corresponding to those rates. One way of achieving this is to retain the call's traffic in the output switching element's data memory. The implementation of data memory 1301 shown in FIG. 14 is particularly suited for this purpose, because it retains each rate's corresponding frames until the slowest rate's frame, i.e., the entire DS-0 frame, has been received at the output.

It should be noted that a similar situation exists with calls that are unrelated and of different rates arriving at the switch output with different delay characteristics. Because they are unrelated, these calls need not be delayed further but instead, the SONET/SDH pointer mechanism can be used to reconcile the different delays.

One of the requirements of the SONET/SDH standards is that section and line overhead (i.e., the first 3 columns) of each constituent STS-1 of an STS-N signal must be aligned such that the N framing bytes are contiguous in their transmission. The Synchronous Payload Envelope (SPE) is allowed to float relative to the STS-1 overhead bytes. The SPE starting location is identified by a pointer located in the respective STS-1 overhead and will be referred to as the STS-1 level pointer. Virtual tributaries (VTs) are carried within the STS-1 SPE. VTs have their own SPE which may float in a similar fashion to the STS-1 SPE or may be locked, meaning that the VT SPE does not move relative to the STS-1 SPE. Floating VTs therefore have a VT level pointer analogous to the STS-1 level pointer. The VT pointers always appear as the first seven to twenty-eight bytes (depending on the VT size) of the STS-1 SPE. Floating VTs are preferred for carrying asynchronous payloads, such as a DS-1, that is not locked to the same clock as the switch. This allows these asynchronous signals to pass through the switch without added delay. Therefore, it is preferable to transport signals in the floating format. When the VT payload is to be switched, as in the case of DS-Os carried in a VT, a slip buffer is used to convert the floating VT to a locked VT. Locked VTs carry payloads that are synchronized to the switch clock and therefore are ideal for locating individual bytes (time slots) such as DS-Os for switching. The SONET/SDH standards however do not allow mixing locked VTs with floating VTs within a STS-1. For a multirate switch, all traffic being switched below the STS-1 level is done using the floating format. All traffic that is being switched below the VT level (i.e., DS-Os) is converted to a pseudo-floating format. That is, the VT SPE passes through a slip buffer so that the SPE appears locked, and the VT level pointer is set to 0. For VT level switching, the VT pointer is incremented by an amount corresponding to the value of the STS-1 level pointer. The STS-1 level pointer is set to 0, meaning that the STS-1 SPE, and consequently the VT pointers, start in the first position of the payload envelope. For switching at the STS-1 and above levels, the STS-1 pointer is passed to the switch without change.

After switching in a TSI, the VTs will exit the TSI shifted down one row relative to the overhead due to the VT frame length of one row of the 125 microsecond frame. The STS-1 level pointer is therefore incremented by an equivalent amount showing the SPE as a whole being shifted. For DS-0 level switching, the delay is the full 125 microsecond frame time, which places the VT pointer associated with the DS-Os one row above the VT pointers associated with the VTs being switched at that level. However, all VT pointers must be contiguous. The path hunting mechanism must therefore offset the output time-slot assignments for DS-0 level calls by one row, thereby allowing the VT pointers to be contiguous once again. Finally, if STS-1 or above calls are switched as an entity, their respective STS-1 level pointers and VT level pointers pass through the switch unchanged. If, however, these higher-rate call types must be split partially into lower-rate portions to avoid blocking, and the lower-rate portion is of type VT, then the STS-1 level pointers must be incremented by an amount representing the added delay of one row required to be inserted in the high-rate portion of the call to resynchronize that portion with the lower rate portion, as described above.

This hierarchical allocation and corresponding path hunts are accomplished as follows. Turning to FIG. 27, conceptually, each TSI 131 and 141 has an associated hierarchy 2700 of status tables 2701-2703 stored conventionally in the memory of control processor 110 to be used to perform path hunts through system 100. Each one of the plurality of layers 2721-2723 of each hierarchy 2700 corresponds to a different one of the STS-1, VT, and DS-0 data rates, respectively. Each one of the layers
2721-2723 comprises one or more corresponding status tables 2701-2703, respectively. The STS-1rate layer 2721 contains one STS-1 timeslot block status table 2701 which has twelve entries 2711. Each entry 2711 corresponds to one time slot equivalent to an STS-1 frame 30 (see FIG. 2). Hence, each entry 2711 represents the bandwidth of one STS-1 within an STS-12. Each entry 2711 is encoded to indicate whether the corresponding bandwidth is fully idle. partially idle, or busy.

For every entry 2711, the VT rate layer 2722 contains a different corresponding VT timeslot block status table 2702. Hence, there are 12 status tables 2702 for each table 2701. Each status table 2702 has up to 28 entries 2712, each corresponding to a different VT of an STS-1. How many entries 2712 a table 2702 has at any one time depends upon the mix of VT types that the corresponding STS-1 carries at that time. Each entry 2712 of layer 2722 corresponds to a timeslot equivalent to of one VT within an STS-1. Hence, each entry 2712 represents the bandwidth of one VT. Each entry 2712 is also encoded to indicate whether the corresponding bandwidth is fully idle, partially idle, or busy.

For every entry 2712, the DS-0 rate layer 2723 contains a corresponding DS0 timeslot block status table 2703. Hence, the number of tables 2703 in layer 2723 varies with the number of VT entries in tables 2702 in layer 2722. Each status table
2703 has a plurality of entries 2713, each corresponding to a different DS-0 of the corresponding VT. How many entries 2713 a table 2703 has depends upon the corresponding VT type. Each entry 2713 represents the bandwidth of one DS-0, i.e., of one time slot of an STS-12 frame. Hence, there is a total of 9720 entries 2713 in one layer 2723. Each entry 2713 is encoded to indicate whether the corresponding bandwidth is idle or busy.

The hierarchy 2700 of tables may be expanded to contain addition M levels--for example, to include an STS-3 upper level and an H0 (i.e., 384 kbps) next-to-lowest level. However, there is a tradeoff between the number of levels and the width of each level. The three-level hierarchy 2700 shown in FIG. 27 represents a reasonable tradeoff.

To establish a given connection between a given input TSI 131 and a given output TSI 141, matching idle input-TSI output time-slots and output-TSI input time-slots must be found. To perform a path hunt between a TSI 131 and a TSI 141, control processor 110 searches their corresponding hierarchies 2700 of status tables in a predefined way. For an STS-1rate or a higher-rate connection, the preferred choice is to find matching idle ent