REGISTER  |  SIGN IN
United States Patent5237571
Cotton , ; et al.August 17, 1993
Title
Broadcast system for distributed switching network
Abstract
The broadcast system of the switching network provides for the broadcast or multicast of interface switch status broadcasts and interface switch event broadcasts. An interface switch feature processor initiates a broadcast message made up of two bytes of data on a first channel, with particular command codes to identify the type of data contained within the broadcast message, paired with another two bytes of data in the same frame on a second channel. Broadcast messages are sent into the switching network in a non-broadcast manner until they reach the fold point of the switch network. From the fold point the broadcast messages are broadcast on every available broadcast channel directed out of the switch network towards the interface switches.
Inventors:Cotton; John M. (East Norwald, CT), Olsen; Neil C.  (Milford, CT), Necula; Nicholas  (Mt. Vernon, NY), Oswald; William A.  (Oxford, CT)
Assignee:IPC Information Systems, Inc. (Stamford, CT)
Appl. No.:766637
Filed:September 26, 1991
Current U.S. Class:370/390 370/432 370/522 379/164 379/165 
Current International Class:H04Q 11/04 (20060101)
Field of Search:370/110.1,60,94.1 379/164,165
U.S. Patent Documents
3843845November 1974Ridley
4173713November 1979Giesken et al.
4201889May 1980Lawrence et al.
4201891May 1980Lawrence et al.
4317962March 1982Cox et al.
4817085March 1989De Prycker
4903260February 1990Boettle et al.
4916690April 1990Barri
4998275March 1991Braunstein et al.
Foreign Patent Documents
WO8804869Jun., 1988WO
WO8807297Sep., 1988WO
WO8911764Nov., 1989WO
WO9004316Apr., 1990WO
Other References
"Implementation of a 16 to 16 Switching Element for ATM Exchanges," by P. Barri et al., IEEE Journal on Selected Areas in Communications, vol. 9, No. 5, pp. 751-757 (Jun. 1991). .
"Effects of Output Buffer Sharing on Buffer Requirements in an ATDM Packet Switch," by A. E. Eckberg et al., AT&T Bell Laboratories, Holmdel, New Jersey 07733, pp. 459-465 (IEEE 1988). .
"Metastability Behavior of CMOS ASIC Flip-Flops in Theory and Tests", by Jens U. Horstmann et al., IEEE Journal of Solid-State Circuits, vol. 24, No. 1 pp. 146-157 (Feb. 1989). .
"Input v. Output Queueing on a Space-Division Packet Switch," by Mark J. Karol et al., IEEE Global Telecommunications Conference, Conference Record, vol. 2, Session 19.4, pp. 659-665 (Dec. 1986). .
"Metastable Behavior in Digital Systems," by Lindsay Kleeman et al., IEEE Design & Test of Computers, pp. 4-19 (Dec. 1987). .
"A Shared Buffer Memory Switch for an ATM Exchange," by Hiroshi Kuwahara et al., pp. 118-122 (IEEE 1989). .
"System 12: Review of the Fundamental Concepts," by R. Van Malderen, Electrical Communication, vol. 59, No. 1/2, pp. 20-28 (1985). .
"Large-Scale ATM Multistage Switching Network with Shared Buffer Memory Switches," by Yoshito Sakurai et al., IEEE Communications, vol. 29, No. 1 pp. 90-96 (Jan. 1991). .
"The Behavior of Flip-Flops Used as Synchronizers and Prediction of Their Failure Rate," by Harry J. M. Veendrick, IEEE Journal of Solid-State Circuits, vol. 1 SC-15, No. 2 pp. 169-176 (Feb. 1989)..~
Primary Examiner: Olms; Douglas W.
Assistant Examiner: Blum; Russell W.
Attorney, Agent or Firm:Morgan & Finnegan
Claims

What is claimed is:
1. A system for broadcasting a message across a network of switch elements, comprising:
means for creating a message at one switch element of the network;
means for transmitting said message across communication paths established between switch elements of the network to a reflection point; and
means for retransmitting said message from said reflection point to all switch elements in the network.

2. A system for broadcasting a message across a network of switch elements as set forth in claim 1, wherein said means for creating a message creates said message upon the occurance of an event.

3. A system for broadcasting a message across a network of switch elements, comprising:
means for creating a message at one switch element of the network;
means for transmitting said message across communication paths established between switch elements of the network to a reflection point;
means for retransmitting said message from said reflection point to all switch elements in the network; and
means for each switch element to determine whether said message constitutes a data message or an event message.

4. A system for broadcasting a message across a network of switch elements as set forth in claim 3, wherein said message includes a flag to indicate whether said message is a data message or an event message.

5. A system for broadcasting a message across a network of switch elements as set forth in claim 1, wherein said message includes an identification of the switch element originating said message.

6. A system for broadcasting a message across a network of switch elements, comprising:
means for creating a message at one switch element of the network;
means for transmitting said message across communication paths established between switch elements of the network to a reflection point; and
means for retransmitting said message from said reflection point to all switch elements in the network;
wherein said message includes an identification of the switch element originating said message; and
wherein said message includes an identification of a group of switch elements to which said message is addressed.

7. A system for broadcasting a message across a network of switch elements as set forth in claim 6, further comprising means for recognizing whether a particular switch element is a member of the addressed group.

8. A system for broadcasting a message across a network of switch elements as set forth in claim 7, further comprising means for each member of the addressed group to establish a communication path to said originating switch element in response to said message.

9. A system for broadcasting a message across a network of switch elements as set forth in claim 1, wherein said communication paths further comprise two adjacent time division multiplex channels.

10. A system for providing line status information to key stations connected to switch elements in a digital time division switching network, comprising:
means for creating a digital multi-byte message containing line identification and line status information at a switch element of the network in response to a change in the status of a line;
means for transmitting said message across time division communication paths established between switch elements of the network to a reflection point;
means for retransmitting said message from said reflection point to all switch elements connected to key stations in the network;
means for storing said message in storage tables in each switch element connected to a key station in the network; and
means for providing an association of the status of a particular line with a key on the key station.

11. A system for providing line status information to key stations connected to a network switch elements as set forth in claim 10, further comprising means for establishing the communication path between switch elements of the network as said message traverses a switch element.

12. A system for providing line status information to key stations connected to a network of switch elements as set forth in claim 10, wherein said key stations are turret telephones.

13. A system for providing line status information to a plurality of key stations connected to switch elements in a digital time division switching network, comprising:
means for providing active line information to said key stations
means for detecting a change in the status of a line connected to the system;
means for creating a digital multi-byte message containing encoded line identification and encoded line status information;
means for transmitting said digital multi-byte message over paths independent of voice paths to individual key stations connected to the network system; and
means for storing said encoded line identification and encoded line status information for use by individual key stations.

14. A system for providing line status information to a plurality of key stations in accordance with claim 13, wherein said key stations are turret telephones.

15. A system for providing line status information to a plurality of key stations in accordance with claim 14, wherein said means for storing further comprise storage tables.

16. A system for providing line status information to a plurality of key stations in accordance with claim 15, wherein said storage tables are located in proximity to the key stations.

17. A system for providing line status information to key stations connected to a network of switch elements as set forth in claim 14, further comprising means for providing an association of the status of a particular line with a key on the key station.

18. A system for providing line status information to key stations connected to a network of switch elements as set forth in claim 14, further comprising means for providing changes in line status information to every key station.

19. A method of broadcasting a message across a network of switch elements, comprising the steps of:
creating a message at one switch element of the network;
transmitting said message across communication paths established between switch elements of the network to a reflection point; and
retransmitting said message from said reflection point to all switch elements in the network.

20. A method of broadcasting a message across a network switch elements as set forth in claim 19, further comprising the step of establishing the communication path between switch elements of the network as said message traverses a switch element.

21. A method of broadcasting a message across a network of switch elements as set forth in claim 19, further comprising a step of creating a message upon the occurance of an event.

22. A method of broadcasting a message across a network of switch elements as set forth in claim 19, further comprising the step of determining whether said message constitutes data message or an event message.

23. A method of broadcasting a message across a network of switch elements as set forth in claim 19, further comprising the step of including an identification of the switch element originating said message in said message.

24. A method of broadcasting a message across a network of switch elements as set forth in claim 22, further comprising including an identification of a group of switch elements to which said message is addressed in said message.

25. A method of broadcasting a message across a network of switch elements as set forth in claim 23, further comprising the step of recognizing whether a particular switch element is a member of the addressed group.

26. A method of broadcasting a message across a network of switch elements as set forth in claim 24, further comprising the step of establishing a communication path from each member of the addressed group to said originating switch element in response to said message.

27. A method of broadcasting a message across a network of switch elements as set forth in claim 19, further comprising the steps of utilizing two adjacent time division multiplex channels for each communication path.

28. A method of providing line status information to key stations connected to a network of switch elements, comprising the steps of:
creating a message containing line identification and line status information at a switch element of the network in response to a change in the status of a line;
transmitting said message across communication paths established between switch elements of the network to a reflection point;
retransmitting said lie status message from said reflection point to all switch elements connected to key stations in the network;
storing said messages in storage tables in each switch element connected to a key station in the network; and
providing an association of the status of a particular line with a key on the key station.

29. A method of providing line status information to key stations connected to a network switch elements, comprising the steps of:
creating a message containing line identification and line status information at a switch element of the network in response to a change in the status of a line;
transmitting said message across communication paths established between switch elements of the network to a reflection point;
retransmitting said line status message from said reflection point to all switch elements connected to key stations in the network;
storing said messages in storage tables in each switch element connected to a key station in the network;
providing an association of the status of a particular line with a key on the key station; and
establishing the communication path between switch elements of the network as said message traverses a switch element.

30. A method of providing line status information to key stations connected to a network of switch elements, comprising the steps of:
creating a message containing line identification and line status information at a switch element of the network in response to a change in the status of a line;
transmitting said message across communication paths established between switch elements of the network to a reflection point;
retransmitting said line status message from said reflection point to all switch elements connected to key stations in the network;
storing said messages in storage tables in each switch element connected to a key station in the network;
providing an association of the status of a particular line with a key on the key station; and
providing active line information to the key station.

31. A method of providing line status information to each turret connected to a network of switch elements as set forth in claim 30, further comprising the step of storing said line status messages in a table in the key station.

32. A method of providing line status information to a plurality of key stations, connected to switch elements in a digital time division switching network, comprising the steps of:
detecting a change in the status of a line connected to the system;
creating a digital multi-byte message containing encoded line identification and encoded line status information;
transmitting said digital multi-byte message over paths independent of voice paths to individual key stations connected to the network;
storing said encoded line identification and encoded line status information for use by individual key stations.

33. A method of providing line status information to a plurality of key stations in accordance with claim 31, further comprising the step of utilizing turret telephones as said key stations.

34. A method of providing line status information to a plurality of key stations as set forth in claim 31, wherein said step of storing further comprises the step of storing said line identification and line status information in storage tables.

35. A method of providing line status information to a plurality of key stations as set forth in claim 33, further comprising the step of locating said storage tables in proximity to the key stations.
Description
BACKGROUND OF THE INVENTION

This invention relates to distributed processing systems and, more particularly, to broadcast systems for use in a distributed switching network.

Multi-line telephone key stations, sometimes referred to as "trader turrets", are widely used in rapid communication networks such as trading operations in banks, brokerage houses, and other financial institutions. Telephones of this type provide direct access to a large number of telephone lines with a line being selected by the depression of a single key on the key station. Trader turrets generally include at least thirty line keys and often have several hundred. Trader turrets are normally used in networks where the number of lines is greater than the number of telephones whereas, with normal telephone key stations, the number of telephones exceeds the number of lines.

Each telephone key station may have access to other telephone key stations in the system within a trading room and to a large number of outside lines and private lines. Each telephone user may be connected to several lines or terminals at the same time in a conferencing mode.

A large trading room can include many transactions each involving many millions of dollars. A typical trading transaction involves a rapid series of short telephone conversations to, for example, locate traders having the desired security for sale at the best price. A typical call lasts only for a few second and there may be many calls per minute during the course of a single transaction.

An important feature required in such trader network systems is a provision at each telephone key station for displaying the current status of each of the lines accessible to the station. The line status display usually takes the form of a continually lit indication for a "busy" line, a flashing indication for a line on "hold" or "ringing", and no indication for a free line. A prior system for monitoring line status is disclosed in U.S. Pat. No. 4,998,275 issued to Braunstein et. al. In addition, a trader turret telephone station must be capable of indicating the line which is in use so that the trader can at all times identify the other party on the line.

In prior switching networks used in key telephone systems, line status indication was generally a dedicated activity involving the continuous polling of line cards by a processor and the continuous distribution of line status data. Line status information, unlike voice or data transmission, is continuously transmitted across the system on a polled rather than an event basis. Additionally, the implementation of the polling type line status transmission system is such that the only information available via the system are simple not-in-use, ringing, busy, and hold line indications.

In large key systems continuous transmission of the status of every line in the system results in high traffic loading on the polling mechanism or excessive delay in status signalling. Due to the high traffic loading and the system-specific implementation of the line status transmission system, the system is also not adaptable to other system functions such as the broadcast of system data and event occurences.

SUMMARY OF THE INVENTION

With the foregoing in mind, it is an object of the invention to provide a novel method and apparatus for multicasting or broadcasting messages across a switching network.

It is an object of the invention to provide a method and apparatus for simultaneous multicasting or broadcasting messages from multiple origination points across a switching network.

It is an object of the invention to provide a method and apparatus for broadcasting line status information to key stations on an event basis.

It is an object of the invention to provide a method and apparatus for providing line status indication at each key station connected to a distributed switching network.

The line status broadcast system in accordance with this invention is based on event broadcasting rather than status polling. The interface switches monitor the lines and determine when a change in line status occurs. Line status memories associated with the key stations store the current status for each of the lines connected to the switching network. Line status information is broadcast to update all of the line status memories. The line status memories are used in conjunction with line key assignment tables to provide appropriate line status indications on the key station adjacent the assigned line keys.

The broadcast messages corresponding to line status changes are sent into the switching network in a non-broadcast manner until they reach a fold or reflection point in the network. From the fold point the messages fan out and are broadcast on all switch ports toward all of the line status memories. Each of the switch elements include an "in" FIFO buffer and an "out" FIFO buffer. The FIFO buffers prevent the overlap of messages arriving from several sources at the same time.

BRIEF DESCRIPTION OF DRAWINGS

A more complete understanding of the present invention may be had by reference to the following Detailed Description with the accompanying drawings, wherein:

FIG. 1 is a block diagram of the switching network;

FIG. 2 is a data format diagram;

FIG. 3a, 1/2 and 2/2, is a block diagram of a switch element in the switching network;

FIG. 3b is a conceptual diagram of the switch element of FIG. 3a;

FIG. 3c illustrates the layout of an interface switch of FIG. 1;

FIGS. 3d and 3e illustrate of a switch element employed in a conference or a duplex path;

FIG. 4 is a schematic diagram of the FIFO buffer section of FIG. 3a;

FIG. 5 is a functional block diagram of the feature processor section of FIG. 3a;

FIG. 6 illustrates the controller and feature processing memory map;

FIG. 7a illustrates crosspoint first channel in/out lookup tables;

FIG. 7b illustrates a next channel in link list table;

FIG. 7c illustrates a next channel out link list table;

FIG. 8 illustrates a block diagram of a packet control buffer;

FIG. 9a is a conceptual diagram of an availability table in accordance with the instant invention;

FIG. 9b is a schematic diagram of a single associative memory cell of the availability table;

FIG. 9c is a schematic block diagram of the channel allocation system;

FIG. 9d is a schematic block diagram of the channel select register;

FIG. 9e and 9f are schematic block diagrams illustrating the search functions of the channel select register;

FIG. 9g is a schematic block diagram illustrating the components of the port select register;

FIG. 10 is a conceptual drawing of a key station as may be connected to the switching network;

FIG. 11a is a conceptual drawing of a key station interface as may be connected to the switching network;

FIG. 11b is a conceptual drawing of a private line interface as may be connected to the switching network;

FIG. 12a-12c illustrate an example of the action sequence for originating duplex voice path between a key station and a line;

FIG. 13, 1/2 and 2/2, illustrates a diagram of a conference path;

FIG. 14 is a diagram illustrating the structure of a broadcast message;

FIG. 15, 1/2 and 2/2, is a diagram illustrating propagation of a broadcast message through the switching network toward the fold point;

FIG. 16, 1/2 and 2/2, is a diagram illustrating propagation of a broadcast message through the switching network outward from the fold point;

FIG. 17a is a diagram illustrating the structure of a broadcast index table; and

FIG. 17b is a diagram illustrating the structure of a button table.

DETAILED DESCRIPTION OF THE DRAWINGS

A. System Layout

FIG. 1 illustrates a switching network for interconnecting various types of voice or data equipment and telephone lines, indicated generally as units 11-15 in accordance with the instant invention. In the preferred embodiment, the switching network generally includes four stages. The first two stages, referred to as interface (I/F) switches 22 and access switches (AS) 24, are in terminal units 20 which provide an entry point to the switching network for telephone lines and terminal equipment. The third and fourth stages, referred to as the section switches 26 and the reflection switches 28, respectively, are located on individual switch planes 30.

Each of the terminal units 20 includes fourteen interface switches 22 and three access switches 24. Each of the interface switches in a terminal unit is coupled by a communications link to each of the three associated access switches. In the preferred embodiment, there are six switching planes 30 in the switching network Each of the 3 access switches of a terminal unit is coupled to a different set of four out of the six switching planes via its corresponding communications link.

A section switch on a switching plane is linked to two out of the three access switches from each terminal unit and, therefore, since there are nineteen section switches on a switching plane in a maximum system of this configuration, there can be as many as ninety-five terminal units coupled to each plane.

In the maximum system of this configuration each switching plane also includes nine reflection switches 28, each of which is linked to all of the other section switches. With this arrangement, a communication path can be established from a key station to a line termination via an interface switch and any one of three access switches and an interface switch at the key station end, appropriate section switches and reflection switches on any one of six switching planes, and any one of three access switches and the interface switch at the line end. Should any access switch, section switch, reflection switch, or switching plane fail, there are always many alternative paths available through the switching network. Should an interface switch fail, the failure only affects the terminal units connected to the particular failed interface switch and does not affect the operation of the remainder of the system. The total number of switches at any stage depends on the size of the system, the degree of non-blocking communication required and the degree of redundancy required. Other embodiments of the switching network may have other configurations for connecting the switch elements.

Each of the switch elements operates independently and is controlled by separate processors. In the preferred embodiment, all switch elements--interface switches, access switches, section switches and reflection switches--include many common structural elements. Each switch element includes multiple input switch ports and multiple output switch ports. Communication via a switch port is on thirty-two time divided channels. The system architecture is based on the use of 24-bit pulse code modulated (PCM) channels that simultaneously transmit and receive speech and data. The processors associated with each switch element can switch in space (from one port to another) and can switch in time (from one channel to another).

In the preferred embodiment as disclosed, reflection switches, section switches, and access switches are basically the same and each has nineteen switch ports. The interface switch is similar to the other switch elements but smaller, including only a single terminal port and four switch ports. Other embodiments of the interface switch may have more than four switch ports.

B. Port Group Assignments

The switching network provides multiple routes for transmitting voice or data communications between a source and destination. Thus, at any given switch element, there may be a number of switch ports that are available for sending the transmission towards its destination. A port group specifies a number of switch ports for a switch element that can be utilized for routing such a transmission to its destination. The port groups are defined (i.e., switch ports assigned to which port groups) once the configuration of the switching network is established. The port group assignment information can thereafter be loaded into the appropriate switch elements during system initialization. In the preferred embodiment, 32 port groups are available. Port groups 0 through 19 are reserved for identifying individual switch ports, while switch port groups 20 through 31 are reserved for specifying groups of switch ports.

As shown in FIG. 1, interface switches have one terminal port (Port #18) connected to terminal equipment and three switch ports (Port #0-Port #2) coupled to the three access switches in the same terminal unit. One port (Port #3) in every interface switch is reserved for the bridge port (a switch port of which the output is connected to the input, as discussed below). Additionally, one port (Port #19) in every interface switch is reserved for the link data port (switch port that allows the switch elements to send and receive data packets to and from the network, as will be discussed in greater detail below). Preferably, the following port group assignments are utilized for interface switches:

______________________________________ Interface Switch Port Groups Associated Ports ______________________________________ 0 Port #0 (to access switch stage) 1 Port #1 (to access switch stage) 2 Port #2 (to access switch stage) 3 Port #3
(to bridge) 4-17 undefined 18 Port #18 (to terminal equipment) 19 Port #19 (link data port) 20 Port #'s 0, 1, 2 21 Port #'s 0, 1 22 Port #'s 1, 2 23 Port #'s 0, 2 24-31 undefined ______________________________________

This convention allows all three switch ports connecting the interface switch to the access switches to be identified for the outgoing communications link (port group 20), any combination of two switch ports going to an access switch (port groups
21 through 23) to be identified, or any individual switch port to be identified as the outgoing communications link to the access stage (port groups 0 through 2).

As shown in FIG. 1, fourteen switch ports (Port #0-Port #13) of an access switch are coupled to the fourteen associated interface switches on the terminal unit and the remaining four switch ports (Port #14-Port #17) of an access switch are coupled to four section switches on four of the six switching planes. One port (Port #19) in every access switch is reserved for the link data port. Additionally, one port (Port #18) in every access switch is coupled to a tape device for recording desired transmissions. Preferably, the following port group assignments are utilized for access switches:

______________________________________ Access Switch Port Groups Associated Ports ______________________________________ 0-19 respective individual port (Port #0-Port #19) 20 Port #'s 14, 15, 16, 17 (to section switch stage) 21-31 undefined ______________________________________

This convention allows all four switch ports connecting the access switch to the section switches to be identified as the outgoing communications link, or any individual switch port to be identified as the outgoing communications link. Due to the redundant architecture of the switching network, any of the four switch planes connected to an access switch may be utilized for the transmission. Thus, port group 20 sufficiently identifies the outgoing route. However, port groups 21 through 31
remain available for further definition of port groups.

As shown in FIG. 1, ten switch ports (Port #0-Port #9) of a section switch are coupled to the associated access switches of five terminal units (TU1-TU5) and nine switch ports (Port #10-Port #18) of the section switch are coupled to the nine reflection switches on the same switch plane. For illustrative purposes, terminal unit TU1 is coupled to Port #0 and Port #5; TU2 is coupled to Port #1 and Port #6; TU3 is coupled to Port #2 and Port #7; TU4 is coupled to Port #3 and Port #8; and TU5 is connected to Port #4 and Port #9. One port (Port #19) in every section switch is reserved for the link data port. Preferably, the following port group assignments are utilized for section switches:

______________________________________ Section Switch Port Groups Associated Ports ______________________________________ 0-19 respective individual port (Port # 0-Port #19) 20 Port #'s 0, 5 (associated with TU1) 21 Port #'s 1, 6 (associated with TU2) 22 Port #'s 2, 7 (associated with TU3) 23 Port #'s 3, 8 (associated with TU4) 24 Port #'s 4, 9 (associated with TU5) 25 Port #10 through Port #18 26-31 undefined ______________________________________

This convention defines a port group for each of the terminal units connected to the section switch. Additionally, this convention defines a port group (port group 25) for transmissions going to reflection switches. For transmissions travelling from a section switch to a reflection switch, the transmission may be directed to any of the nine reflection switches.

As shown in FIG. 1, a reflection switch can send a transmission to any section switch (via Port #0-Port #18) and thus to any terminal unit. However, to reach a particular terminal unit from a reflection switch only one section switch is suitable. Thus, no port groups are defined. One port (Port #19) in every reflection switch is reserved for the link data port. Preferably, the following individual port group assignments are utilized for reflection switches:

______________________________________ Reflection Switch Port Groups Associated Ports ______________________________________ 0-19 individual port (Port #0-Port #19) 20-31 undefined ______________________________________

This convention identifies only individual switch ports as the appropriate output route from a reflection switch.

C. Switch Data Format

The data format for the switch element is illustrated in FIG. 2. Each communications link carries thirty-two channels of time division multiplexed (TDM) digital information in a serial format. As illustrated, each frame of the TDM format includes thirty-two channels. Each channel has thirty bits over the communication links including twenty-four bits of information when processed in a switch element. Each switch element provides a 5B/4B decoding on the incoming channel segments and as a result, the 30-bit segment in the communications link is converted to a 24-bit segment of information. The remaining six bits are utilized for error correction. The encoding is used to ensure an adequate 1's density for clock extraction and provide even parity for error detection on communication links and ensure that the framing signal in channel zero of a frame cannot be imitated. Each switch element before transmitting the 24-bit channel information performs a 4B/5B encoding and provides the communication link with the 30-bit channel. The length of each frame is 125 .mu.sec. Channel 0 of each frame includes synchronizing information and may include clocking information. Channels 30 and 31 may be used to broadcast line status information.

In the preferred embodiment, the twenty-four bits of information of a channel word ar divided into eight bits of command code and sixteen bits of argument. Some examples of command codes are "Path Set", "Path Clear", "Not Acknowledged (NAK)", and "Confirm." Variations of the "Path Set" command may include "path set data private"; "path set data multicast"; "path set voice duplex"; "path set voice simplex" and "path set voice private." The particular command is according to an 8 bit code which appears at the beginning of each channel word. These commands when present, are interpreted by the processors in the system to perform their respective functions. The 16-bit argument contains the data being conveyed through the switch.

D. Addressing Scheme

Route selection through the switching network utilizes an addressing scheme including logical address codes (LACs), type address codes (TACs) and packet address codes (PACs). Routing itself through the switching network relies on logical address codes.

A LAC is unique code number assigned to a location in the switching network from which data can originate or to which data can be sent. For example, the location defined by a LAC could be an analog line card, a trader station, a digital line T1
channel line card, a processing function (software location), or a switch element within the switch.

A LAC is used by the switch elements in the switching network for path routing. For example, in response to a "path set" command the switch elements will establish a communication path across the switching network from one LAC which may be an incoming line, to another LAC which may be a key station or some other terminal equipment. Thereafter appropriate channels for the communication path are selected and allocated throughout the communication to transmit information from originating LAC to the destination LAC, until the end of communication or forced release. A particular advantage of using LACs is that it provides a layer of isolation from physical changes in the system.

A TAC or type address code is a unique code indicating a group of LACs to which data may be multicast simultaneously, i.e., a one to many transmission of data.

A PAC is used to identify a packet type. When a packet is sent, the sending program is linked to the code and data of the packet and therefore the structure of the packet is known. However, when a packet is received, the structure of the packet is not known to the receiving processor. By assigning a PAC to individual packets, a local translation and substitution may be performed between the packet address code and the target processor packet software addresses.

In addition to its logical address code (LAC), each switch element in the switching network is assigned a physical switch address (PSA) that identifies the position or node of the switch element in the switching network. Although each switch element in the network is assigned a unique LAC, several processors can have the same PSA. For example, both a key station and the interface switch to which the key station is connected will have the same PSA because they are located at the same node of the switching network. Preferably, a PSA is comprised of four bytes that identify the position of a LAC by specifying the path that must be taken from the reflection stage of the switching network in order to reach the LAC.

The first byte of the PSA identifies the switch port that must be taken from the reflection switch stage in order to direct the transmission to a section switch that can send the transmission to its destination. (Port #1 for each reflection switch is coupled to the first section switch on the switch plane, Port #2 for each reflection switch is coupled to the second section switch on the switch plane, etc.)

The second byte of the PSA identifies the switch port that must be taken from the appropriate section switch in order to direct the transmission to its destination. Similarly, the third byte of the PSA identifies the switch port that must be taken from the appropriate access switch in order to direct the transmission to its destination.

Finally, to fully identify the position of a LAC associated with a section switch or reflection switch, the fourth byte of the PSA specifies the switch plane that the switch element is on. For an access switch, the fourth byte specifies which one of the three access switches on a terminal unit the access switch is. For an interface switch or other LAC, the fourth byte is zero.

The system center 15 maintains a load image array that catalogues the physical switch address (PSA) for each logical address code (LAC) that has been assigned in the network. Additionally, the load image array maintains a packet of specific data for each switch element including the LAC and TAC that dentify the adjacent switching elements.

E. System Center

Referring to FIG. 1, the system center 15 is responsible for initialization and maintenance of the switching system. The system center includes a file server 15a and a computer terminal 15b which have access to the switching network through interface switches 21. The system center is used to assign unique LAC TAC and PAC address codes and to analyze these assignments to distribute data as necessary for initialization of the system.

As will be explained in more detail, during initialization of the system, each switch element polls the neighboring switch elements as to their understanding of their identity. The switch elements closer to the system center obtain their identity first. Once each switch element has determined its identity within the switching system, the system center transmits the appropriate software and data to the switch element.

The system center also maintains system status information. During the operation of the switching network, if a switch port of a switch element becomes inoperative, a report is sent to the system center identifying the switch port responsible for the anomaly. The system center does analysis concerning the suspected faulty communication link and gives guidance to maintenance personnel as to corrective action.

F. Basic Switch Element

The basic layout for a switch element is shown in FIG. 3a including nineteen switch ports each having a channel receiver and a channel transmitter. As explained previously, a communications link supplies serial data to or from a switch port in a serial thirty-two channel time division multiplexed (TDM) frame format with twenty-four bits of information per channel. The first eight bits of each channel is used for commands such as setting a path or clearing a path, while the remaining sixteen bits are used for data transmission. Channel 0 is used for clocking information and includes a coded identifier (1111100000) which identifies the beginning of a frame.

The switch element includes nineteen channel receivers 100 and nineteen channel transmitters 102. Incoming data from another switch element or, in the case of interface switches, from a terminal port is stored in a crosspoint memory 122 on a channel-by-channel basis as directed by an in-address pointer register 128. Similarly, data can be read from the crosspoint memory and directed to a selected channel transmitter of a switch port and a selected channel by an out-address pointer register
130. In this fashion, incoming data can be shifted in space (from any channel receiver of a switch port to any channel transmitter of a switch port) and can be shifted in time (from one input channel to any output channel). The switch element is capable of summing data being placed in a particular crosspoint memory location to provide conferencing by addition of the data for two or more channels.

Data on the incoming communications link 170 is fed serially to the channel receiver 100. The channel receiver includes a shift register 106 for receiving the serial data input and converting the data from serial to parallel format. The first ten bits of the shift register are coupled to a frame synchronous detector 108 which looks for a coded identifier of the frame beginning. The shift register is also coupled to a channel information latch 104 which receives one data channel at a time. The frame synchronous detector 108 is coupled to a channel counter 110 which identifies the current incoming channel number for the data in the channel information latch 104.

As mentioned before, at the beginning of each frame, a 10-bit frame synchronous word is provided which consists of five 0's followed by five 1's (1111100000). When the frame sync detector recognizes the frame sync pattern, the counter is reset and thereafter counts channels to keep track of the incoming channel numbers. The shift register 106 converts the serial incoming bit stream into a parallel word and provides the channel word latch 104 with the parallel word.

A channel selector 112 samples the respective channel word latches of the ports in sequence and transfers the data in parallel to an in-data register 114. The output of the in-data register 114 is coupled to a multiplexer 118 and to a 16-bit saturation adder 116. A crosspoint temporary register 120 provides data from a crosspoint (X point) memory location to the second input of the adder. The output of the adder is also coupled to the multiplexer and the output of the multiplexer is coupled to the crosspoint memory 122.

During each switch port time slot, incoming channel information is stored in a crosspoint memory location and during each outgoing time slot the contents of a crosspoint memory location is retrieved and provided to an outgoing channel transmitter
102. The crosspoint memory is a fast 640.times.24 bit RAM which transfers data from incoming communications links to appropriate outgoing communications links.

The addresses of crosspoint memory locations for incoming and outgoing channel information are stored in pointer RAM 134. The addresses of the crosspoint memory locations in the pointer RAM are indexed by switch port and channel number. The pointer RAM 134 is a fast (640.times.2).times.12 static RAM reserved for two sets of crosspoint memory addresses or pointers associated with each of the incoming and outgoing channels.

The pointer RAM index is defined as an 11 bit address as "PPPPPCCCCC" where A=0 or 1, which denotes an address for an incoming channel or an address for an outgoing channel respectively. CCCCC is the channel number from 0 to 31, and PPPPP is the port number from 0 to 19, where 19 is an address of a link data port and 18 is an address reserved for the terminal port which is used in interface switches only. The pointer RAM data is defined as 10 bits for a crosspoint memory location, 1 bit to denote whether idle codes will be flagged, and one bit to denote if the cross point memory location is part of a conference call or a reset bit.

The pointer RAM is coupled to pointer data out registers 132a and 133b. Pointer data out register 132a is coupled to an in-address pointer register 128, and pointer data out register 132b is coupled to an out-address pointer register 130. The in-address pointer register directs the incoming data to its allocated crosspoint memory location 122a. Similarly, the out-address pointer register selects the outgoing data from its allocated crosspoint memory location 122b. The outgoing data is sent from out-data register 124 to the appropriate switch port via the channel information register in the channel transmitter 102.

Channel transmitter 102 provides a serial outgoing data stream to outgoing communications link 172. The channel transmitter 102 includes a channel word register 174 which receives the outgoing channel word in parallel format. The channel word register 174 is coupled to a shift register 176. The shift register converts the parallel data into a serial bit stream. At the beginning of each outgoing frame, the frame synchronous bits (1111100000) are provided by sequence port and local channel number 139 to director 126 and thereafter to channel transmitter 102 and sent by shift register 176.

In each channel receiver 100 the channel counter 110 provides the incoming channel number to a pointer address register 136a via selector 112. The pointer address register 136a is also coupled to a sequencer 138 which keeps track of the switch port number being served. The pointer address register 136a is coupled to the pointer RAM 134, and provides the incoming channel and switch port number to the pointer RAM.

The sequencer 139 is coupled to pointer address register 136b which provides the pointer RAM with local channel number and the switch port number. It may be appreciated that the local channel number is not the same as the incoming channel number. It is preferable to maintain two separate channel counts because incoming channel words arrive at individual switch ports at different times and, therefore, are not synchronous. However, the channel transmitter at every switch port transmits the same channel number at the same time.

During one channel time period, each switch port is assigned a unique time slot. Each switch port time slot is then divided into six phase periods by the system clock. During each switch port time slot, two phase periods are used to transfer out an outgoing data from its crosspoint memory location to its channel information register. Similarly, two phase periods are used to transfer an incoming data to its destination crosspoint memory location. The final two phase periods are reserved for controller 140 data transfers.

The switch element also includes a real time controller 140 coupled to a controller bus 150. The controller is coupled to in-data register 114 via data bus 141 allowing the controller to send information to a crosspoint memory location. Similarly the controller is coupled to out-data register 124 via data bus 143, allowing the controller to receive information from a crosspoint memory location. A FIFO buffer section 144 is also coupled to the controller bus 150. As part of its responsibilities, the controller initializes and manages the switch ports, and sets and clears communication paths to lines, key stations and other processors.

The switch element also contains a feature processor section 146, which is coupled to a feature processor bus 152. The feature processor section provides call processing functions, initializations, fault recovery and maintenance. Feature processor section 146 and controller 140 communicate with each other via event FIFO 156, action FIFO 158 and free FIFO 160. The feature processor and the controller are also able to share memory resources through gate 154. Gate 154 couples the controller bus 150 to feature processor bus 152 at appropriate times. It can be appreciated that the functions of the controller and the feature processor may be combined and provided by one very fast processor.

A destination port store (DPS) 164 is provided and is coupled to the controller bus 150. The destination port store is a memory table which contains routing information for each logical address code (LAC). By indexing into the destination port store by a logical address code (LAC), the controller can find the port or group of ports that should be used to forward the call to its destination.

A channel allocation system (CAS) 162 is provided and is coupled to the controller bus 150. During the setting of a path across the switch element, the controller must select one or more free channels on outgoing communications links in order to complete the connection. The channel allocation system performs this activity in a short, fixed and repeatable time interval at the controller's request. It chooses the first available channel and distributes the load among switch ports in the same functional group.

The link data ports (LDP) 148a and 148b, which are coupled to the controller bus, provide the mechanism to launch and receive data packets to and from the network. To the switch ports of the switch element, the link data ports appear merely as another switch port. The link data port has 32 dedicated time slots which can read from and write to switch element crosspoint memory locations. To the controller 140, the link data port appears as 32 RAM locations.

The clocking for the switch element has not been shown in FIG. 5a as various clocking techniques well known to those skilled in the art can be utilized. For example, a centralized clock with dedicated lines to each switch element may be provided. A preferable clock, however, is a distributed clocking mechanism wherein the clock signals are transmitted throughout the system over the same communications links that carry the voice and data as disclosed in copending U.S. patent application Ser. No. 766,647, entitled, DISTRIBUTED CLOCKING SYSTEM. The disclosure of this patent application is incorporated herein in its entirety by reference.

The output of the selector 112 is coupled to a command decoder 142 via data bus 141. The output of the command decoder is in turn coupled to the FIFO buffer section 144. When a switch port time slot is set for a particular switch port, e.g., switch port number 1, the channel data is transferred to the in-data register 114 via selector 112 and the incoming channel number information is transferred to pointer address register 136a via selector 112. The first 8 bits of the channel data are checked by the command decoder 142 which decodes the incoming commands If the command decoder recognizes a command that requires the attention of the controller, it provides the incoming channel word to the FIFO buffer section 144 for further processing by the controller and the feature processor.

The pointer address register 136a at this point contains the incoming channel and switch port number; the channel number being obtained from the selector 112 and the switch port number from the sequencer 138. The pointer address register thereafter indexes the pointer RAM 134 with the switch port and channel number, to obtain the address of the appropriate crosspoint memory location. The address of the crosspoint memory location is then provided to pointer data out register 132a.

The in-data register 114 contains the data provided by the selector. The in-address pointer register 128 retrieves the crosspoint memory location from the pointer-data out register 132a. The in-address pointer register 128 is also coupled to the adder 116 and the multiplexer 118. The data in the in-address pointer register includes a flag signal that is provided by the controller when loading the pointer RAM data. The flag signal may be sent to the adder and the multiplexer. When a flag signal enable is provided to the adder 116 and multiplexer 118, the contents of the in-data register 114 are stored directly in the designated "in" crosspoint memory location 122a. If the flag signal enable is absent, the contents of the designated crosspoint memory location 122a are added to the contents of in-data register 114 and multiplexer 118 takes and stores the summed result in the designated crosspoint memory location 122a.

During the transmit time slot for the switch port, a procedure similar to that described above takes place. In this time slot, however, the pointer address register 136b is loaded with the local channel number and the switch port number provided by sequencer 139. The address of the crosspoint memory location is then sent to out-address pointer register 130 which points to designated "out" cross-point memory location 122b. The contents of designated crosspoint memory location 122b is sent to out data register 124. The contents of the out data register may be sent to controller 140 or may be directly loaded in the switch port director 126. The switch port director 126 now has the appropriate data which is transmitted to channel information register 174 and finally to outgoing communications link 172.

The information in pointer RAM 134 is loaded via controller 140. The switch element processors are responsible for allocating the appropriate crosspoint memory locations for each switch port and channel number. This information is fed into the pointer RAM 134 from the controller. As described above, the information on any channel of any incoming switch port can be switched to any other channel of an outgoing switch port in the switch element.

The adder 116 and the in address pointer registers 128 allow a flexible many-to-one operation wherein many incoming channels can be added together. The sum may be stored in the crosspoint memory location for a designated outgoing channel. As will be explained in more detail, this flexibility allows for duplex and conferencing features. For example, if a line and a trader key telephone station are connected as a duplex path, or if a number of trader key telephone station users wish to talk to each other, the contents of each channel corresponding to each line or user is merely added to the contents of the other channels. Accordingly, if the incoming channel is part of a duplex path or a conference call, the channel data is added to the existing contents of the crosspoint memory location using the adder 116.

Similarly, the out-address pointer register 130 allows for one-to-many operation. The out-address pointer register may point to the same crosspoint memory location for different outgoing channels on different switch ports. Data in an outgoing channel is fetched from the crosspoint memory location and store in the channel transmitter for transmission during the next channel time. If the crosspoint memory location read is a part of a conference call, the memory location is reset to a zero value.

FIG. 3b is a conceptual diagram of the switch element described in FIG. 3a. For the purpose of clarity the switch element illustrated in FIG. 3b will be used hereinafter instead of the switch element illustrated in FIG. 3a, as concepts may be more easily visualized with a simplified figure. Each pair of channel receivers 100 and channel transmitters 102 of FIG. 3a is shown as one switch port 173 including incoming link 170 and outgoing link 172. Feature processor section 146 of FIG. 3a is also shown to be connected to controller 140 each utilizing the shared memory space 147. Shared memory 147 in FIG. 3b represents feature processor RAM 168 and controller RAM 166 of FIG. 3a. Link data ports 148a and 148b of FIG. 3a are shown as one link data port 148 in FIG. 3b. Crosspoint memory 122 of FIG. 3a is also shown in FIG. 3b with one memory location identified as "F" for forward crosspoint memory location and another memory location identified as "R" for reverse crosspoint memory location as will be described in more detail hereinafter. Broadcast FIFO buffers 186 are also shown in FIG. 3b which are part of the FIFO buffer section 144 of FIG. 3a. Broadcast FIFO buffers, as it will be further described, are utilized when receiving and transmitting status broadcast messages from one switch element to the other. Additional elements that are relevant may be added to the switch element of FIG. 3b to provide a clear conceptual understanding.

As previously mentioned, each of reflection switches, section switches, and access switches in the switching network are the same as the switch element described in FIG. 3a and FIG. 3b.

FIG. 3c illustrates the layout of an interface switch stage 22 of FIG. 1. The interface switch is a scaled-down version of the switch element as described before, and is connected to various terminal equipment and line cards to provide them access to the switching network. The interface switch 22 includes a terminal port and four switch ports each having a channel transmitter and a channel receiver. In order to simplify the drawing, the switch element is illustrated only with relevant components.

Terminal port 171 provides access to the key station or line card via a communications link. In each interface switch, one switch port is allocated as a bridge port 173. A bridge port is similar to any other switch port except that the channel receiver of the bridge port is connected to the channel transmitter as shown in FIG. 3c. Therefore, the contents read from the crosspoint memory location associated with the bridge port is sent back into the interface switch and stored in its appropriate crosspoint memory location.

The feature processor 146 in the interface switch performs additional functions that are not performed by other switch elements in the switching network. The functions performed by the feature processor include call handling by a call handler software 175; downloading the configuration tables from the system center; and running diagnostics at boot up, upon reset, and on a continuing basis. In addition, the feature processors in the interface switches that are connected to key stations receive and analyze the line key actuation messages directly from the key station. The line key actuation messages may include setting a path to a line or to another key station, clearing or releasing a line on a key station, setting a conference call with other lines and key stations, setting a private communication path between a key station and a line or another key station and many other features depending on the user's needs and requirements. The feature processor in the interface switches that are connected to key stations also assemble and transmit line status information for each of the key stations connected to the interface switch.

For interface switches connected to line cards, the feature processor acquires and broadcasts line status at appropriate times via the switch ports to the switching network. The feature processor also provides call handling for the voice channels coupled to the line card. Either a simplex or a duplex path may be set between one originating switch port to a terminating switch port. Between these two ports there may exist several tandem connections to other switch ports. In a duplex communication, the switch elements of the originating and the terminating switch port set a path toward the same destination, i.e., a bridge port in an interface card. In a duplex communication the first half of a duplex path from the originating switch port and from the destination switch port towards a destination bridge port is referred to as a forward leg in each switch element. It is possible to have a plurality of duplex paths, for example, in a call conference set-up where all the interface switches involved set a path towards the same destination bridge port.

FIGS. 3d-3e illustrate an example of a switch element 99, employed in a call conference path. In FIG. 3d, switch port A receives a channel, the contents of which is addressed to a destination bridge port via a channel of switch port C of switch element 99. Switch port B also receives a channel, the contents of which is also addressed to the same destination bridge port via a channel of switch port C. In a call conference with multiple parties involved, other ports in the switch element may also receive channels, contents of which are addressed to the same destination bridge port via switch port C of the switch element. At the switch element where two or more paths to the same destination bridge port intersect, the two's complement sum of the incoming channel information for both channels is provided by adder 116 and is stored in a forward crosspoint memory location 174 identified as "F", and passed along to the destination via switch port C.

The second half of the duplex path which originates from the bridge port and provides the distribution of the summed forward legs to all interface switches involved in a call is referred to as the reverse leg. FIG. 3e illustrates the switch element 99, employed in the reverse leg of the conference call. Switch port C receives a channel from the bridge port. The contents of the channel is a sum of all the channel words in the conference call, and is stored in a reverse crosspoint memory location 176 identified as "R". The contents of the reverse crosspoint memory location is addressed to the originating and destination interface switches via channels of switch ports A and B.

Accordingly, the forward crosspoint memory location "F" is associated with the forward leg of a path and the reverse crosspoint memory location "R" is associated with the reverse leg of a path.

Each incoming channel word of switch port 170a and 170b of FIG. 3d and 170c of FIG. 3e has an address of a crosspoint memory location in the Pointer RAM 134 associated with it. On the forward leg of a duplex voice path, the switch element 99
will add the incoming channel word to the existing contents of forward crosspoint memory 174 by adder 116 and update. The in-address pointer register 128 allows for many-to-one operation by providing the same crosspoint memory location for all data routed to the same destination. Therefore the data contained in many incoming channels with the same destination can be added and stored in the same forward crosspoint memory location 174. On the forward leg of a duplex path, the forward crosspoint memory location 174 is read and its contents are provided to the outgoing channel. Thereafter, the content of the crosspoint memory location 174 is cleared.

On the reverse leg of a duplex path, the switch element 99 will write the incoming channel word into the reverse crosspoint memory location 176. Each outgoing channel word 172a and 172b of FIG. 3e and 172c of FIG. 3d similarly has an address of a crosspoint memory location in the pointer RAM 134 associated with it. The out-address pointer register 130 allows for one-to-many operation by pointing to the same reverse memory location 176. Therefore the contents of the reverse memory location 176
is available to many outgoing channels corresponding to the conference path. On the reverse leg of a duplex path, the outgoing channel word from the reverse crosspoint memory location is read and is provided to the outgoing channels.

G. Controller & Feature Processor

A switch element might receive at the same time various command codes and their corresponding arguments from the communication links connected to its switch ports. The rate of incoming commands can be faster than the controller's processing time. Therefore each switch element has a First In First Out (FIFO) buffer section to receive the incoming commands and provide the necessary information to the controller on a first in first out basis. The incoming commands and their corresponding arguments are provided to the FIFO buffer section 144 via command decoder 142 of FIG. 3a. At appropriate time the information stored in the FIFO buffers are read by the controller 140 via controller bus 150 in FIG. 3a.

FIG. 4 is a schematic diagram of the FIFO buffer section 144. The FIFO buffer section 144 contains four FIFO buffers: path set FIFO buffer 180; path clear FIFO buffer 182; channel monitor FIFO buffer 184; and broadcast FIFO buffer 186. The crosspoint memory locations and the switch ports are accessed by the controller 140 of FIG. 3a through the four FIFO buffers.

The path set FIFO buffer 180 presents path set commands from incoming channels for the controller to process. The FIFO contents corresponding to each path set command is forty bits wide. During the read function the path set FIFO buffer provides the controller with the port and channel number in ten bits, the local channel time in six bits, the command code in eight bits and the argument for that command in sixteen bits. The argument for the path set command is the destination logical address code (LAC). Therefore, an incoming path set command on a communications link is detected by a switch port and placed in the path set FIFO 180. At some moment later, the controller will read the FIFO as explained above, and use the logical address code to index into the destination port store 164 in FIG. 3a. The destination port store then provides the outgoing port or group of ports to use.

FIFO buffer 182 is used to store path clear and not acknowledged (NAK) commands. The FIFO buffer 182 is read similar to the path set FIFO except that its contents are 34 bits. During the read function, the FIFO 182 provides the controller with the port and channel number in 10 bits, the command code in eight bits and its corresponding argument in sixteen bits. The argument for a path clear command is the destination logical address code (LAC), and the argument for a NAK command is the channel number and the type of the command.

FIFO buffer 184 is used to present alarms, error conditions and warning commands to the controller 140. One bit in the pointer RAM 134 data is used to enable or disable the channel monitor FIFO buffer on a switch port and channel basis. The FIFO buffer 184 contains thirty-four bits. During the read function, FIFO buffer 184 provides the controller with the port and channel number in ten bits, a command code in eight bits and its corresponding argument in sixteen bits.

As it will be explained in more detail hereinafter, status broadcast FIFO's 186 are utilized for storing and forwarding broadcast messages.

FIG. 5 is a functional block diagram of feature processor section 146 of FIG. 3a. The feature processor is a common processor design for all the switch elements in the switching network. This permits one design to be used in all the switch elements, thereby simplifying each switch element design and providing a common building block for future designs.

The feature processor 190 is a SPARC processor. The feature processor bus 152 contains an address bus which is a 24-bit subset of the feature processor 32 address bits. The feature processor bus 152 also includes an external data bus which is thirty two bits wide.

The basic support circuitry includes a memory protection unit (MPU) 192, RAM 194, boot EPROM 196 which is a 512K byte memory, watch dog (WD) timer 198, oscillator 200, physical location I.D. 202, interrupt controller 204, peripheral interface
206, memory gate controller 208, status buffer 210, control latch 212, address decoder 214 and timers 216.

Code and data tables are downloaded from the system center 15 hard disks to the RAM 194. The RAM is static for the high speed memory requirements and for battery backup use. The boot EPROM 196 contains the bootstrap and self test code. Each switch element is able to determine its own switch element type and its physical position within the system by reading a 14-bit register in the physical location ID section 202 provided from the backplane via a dedicated I/O port in the physical location I.D. section. Memory protection Unit (MPU) 192 controls the right of access to different sections of the RAM 194 for the software entities running in the feature processor. Memory gate controller 208 controls the memory gate 154 in FIG. 3a, which allows the controller 140 or the feature processor section 146 to have access to each other's environment at specific times. Peripheral interface section 206 allows terminal equipment and line cards to have direct access to feature processor section 146
of the interface switches.

FIG. 6 illustrates the controller and Feature processor memory map. The controller RAM 166 which is a high speed RAM contains a switch port and channel to crosspoint mapping tables 212. The mapping tables include a crosspoint first channel-in lookup table 214, crosspoint first channel-out lookup table 215 both indexed by crosspoint number, a next channel in link list table 216 indexed by port and channel, and a next channel out link list table 218 which is also indexed by port and channel. The controller RAM also contains a free crosspoint FIFO buffer 220. The controller RAM additionally contains Path Control Buffers (PCBs) 222 corresponding to each active voice and data channel. The PCB is a block of memory allocated at each end of a path that is used for real time status monitoring and management of the path. The Controller RAM 166 is interfaced with Feature Processor RAM 194 via memory gate 154.

Referring to FIG. 6, the controller has a copy of the incoming channel information address in a local controller in-address register which also contains 5 bits for the Return Channel Number and 8 bits for Packet Control Buffer Index number. Therefore, the contents of the incoming channel information address in the controller in-address register has the following format:

______________________________________ Controller In-address Register Crosspoint memory location address 10 bits Conference leg flag 1 bit Busy flag (Channel Monitor Enable) 1 bit Return channel # 5 bits Packet control buffer index # 8
bits Idle Count 5 bits ______________________________________

The packet control buffer index number allows any event on any switch port and channel to be associated with a packet control buffer if one exists. For switching network switch elements this field will be left blank. The controller RAM 166 will also contain a copy of the crosspoint memory location address of the outgoing channel word and the logical address code for the ultimate path destination in a local controller out address register. Therefore the contents of the controller out-address register in the controller RAM has the following format:

______________________________________ Controller Out-address Register Crosspoint memory location address 10 bits Conference leg flag 1 bit Busy flag 1 bit Destination logical address code # 16 bits ______________________________________

As illustrated in FIG. 6 the Feature Processor RAM contains destination port store 230, line status table 234, call message buffers 236, and call message FIFO buffers which include event FIFO buffer 156, action FIFO 158, free FIFO 160, and packet buffers 232. A call message buffer (CMB) 238 is used by the feature processor and it has an identical data structure as the path control buffer 222. Call message FIFO's 156, 158 and 160 are path message FIFO buffers for sending "event" information to the feature processor and action commands information from the feature processor. Therefore, the call message FIFO buffers allow interaction between the feature processor and the controller in each switch element.

The destination port store 230 (DPS) is a memory table indexed by logical address codes for selecting an outgoing switch port or switch port group. Therefore, when each switch element receives a command code to set up a path to a destination logical address code (LAC), the destination port store provides the switch port or the group of switch ports available that can direct incoming channel data towards that destination LAC. The outgoing switch port or the group of switch ports associated with a LAC is set at system initialization or dynamically thereafter when there is a physical reconfiguration in the system. Once the outgoing switch port or group of switch ports is provided, the switch element directs that switch port information to channel allocation system (CAS) 162 of FIG. 3a to select an optimum port and channel in the selected switch port. The resulting switch port and channel is then stored in the destination port store table 230 as the selected outgoing switch port and channel. The destination port store 230 stores the forward crosspoint memory location address. The reverse crosspoint memory location address is found via a mate table which can be indexed by the corresponding forward crosspoint memory location address. Similarly, a forward crosspoint memory location address can be found via the corresponding reverse crosspoint memory location address. The format of the destination port store is therefore as follows:

______________________________________ Destination Port Store Outport/group 5 bits Crosspoint memory location address 10 bits Count 5 bits L 1 bit Out going port selected 5 bits Out going channel selected 5 bits ______________________________________

Where outport/group is the switch port or group of switch ports selected that may route the claimed data to its desired destination. The Count entry stores the number of connections on the switch element which are part of a particular path. L (local bit) is set if the destination LAC is local to the switch element.

If on a path set command, contained in incoming channel information, examination of the destination port store shows no existing path to the destination logical address code, an available crosspoint memory location address for the incoming channel word is read from the free FIFO. If however, examination of the destination port store shows a path already existing, the count entry is not zero and the corresponding crosspoint memory location address in the Destination Port Store 230 (DPS) would be used.

In a simplex path, the entry for the crosspoint memory location address in the destination port store is used to store the address of forward crosspoint memory location. In a duplex path, the entry for the crosspoint memory location address in the destination path store would also store the address of forward crosspoint memory location, to be used for the forward leg. Thereafter, the address of the reverse crosspoint memory location for a duplex path is found by examination of the controller mate table.

The count field can be thought of as the number of connections on a switch element in a particular path. It is incremented four times when the path is first set. Once for the incoming channel of the forward leg. Once for the outgoing channel in the forward leg, once for the incoming channel of a reverse leg, and once for the outgoing channel in a reverse leg. Subsequent path sets for the same logical address code number entering the switch element will increment the count by two, once for the incoming forward channel and once for the outgoing reverse channel.

The L bit in the destination port store (DPS) in each switch element indicates whether the switch port corresponding to the destination logical address code is in the same switch element. For a data path when the L bit is set the destination is assumed to be the link data port (LDP) for that switch element.

When a group of ports are available for a corresponding logical address code, the switch element assures that the traffic load among the available ports is equally distributed. The switch port or group of switch ports provided by the Destination Port Store, are used to access the channel allocation system 162 of FIG. 5a along with the last switch port parameter to locate the next available free channel. If more than one switch port in the switch port group have the same shortest channel time, the "last switch port" information is used to make the choice. By looking at the "last switch port" entry the CAS selects the next available switch port in the group. The "last switch port" table entry is updated each time a channel is allocated from a switch port group.

FIGS. 7a-7c illustrate crosspoint first channel in lookup table 214, crosspoint first channel out lookup table 215, next channel in link list table 216, and next channel out link list table 218 of FIG. 6. It is necessary at times to locate all parties involved in a call with only a switch port and channel or crosspoint memory location address. Tables 214, 215, 216 and 218 can provide this information. FIG. 7a illustrates the crosspoint first channel in/out lookup tables 214 and 215 in more detail. By indexing into each of the tables by a crosspoint memory location address, the first switch port and channel assigned to write into and read from the crosspoint memory location can be found. For a forward crosspoint memory location, there is only one outgoing channel reading from the crosspoint memory location. For a reverse crosspoint memory location, there is only one switch port and channel writing into the reverse crosspoint memory location. The layout of the entries in the crosspoint first in/out lookup table are shown below:

______________________________________ Crosspoint IN/OUT First switch port and channel in 10 bits First switch port and channel out 10 bits ______________________________________

FIG. 7b illustrates next channel in link list table 216 and FIG. 7c illustrates the next channel out link list table 218. It may be appreciated that there can be multiple switch ports and channels writing into a forward crosspoint memory location. When writing into a forward crosspoint memory location, the contents of each channel is added to the previous contents of the forward crosspoint memory location and the sum is stored. Similarly there can be multiple ports and channels reading from a reverse crosspoint memory location. To find all participants in a path, fixed length tables 216 and 218 contain a number of linked lists, one for incoming channels and one for outgoing channels. The first switch port and channel to write into a crosspoint memory location can be found by using the crosspoint first channel in/out lookup table 214 and 215 a indicated before. The first port and channel is used to index into the next channel in link list table 216 to obtain the next port and channel writing into the same forward crosspoint memory location. If the index switch port and channel 240 is the only channel writing into the crosspoint memory location, or if the index switch port and channel 240 are last port and channel, then the contents of the next channel in the link list table location will be NULL.

When a switch port and a channel are added to a path, it must be added to the end of the link lists. When a switch port or channel is removed from the path then the linked list must be compressed. The layout of the entries in the in/out link list tables are as follows:

______________________________________ Next Channel In Linked List Table Previous switch port and channel in 10 bits Next switch port and channel in 10 bits Next Channel Out Linked List Table Previous switch port and channel out 10 bits Next switch port and channel out 10 bits ______________________________________

It may be appreciated that, in addition to the elements of the switching network, protocol layers are necessary to make routing decisions, test the components, respond to error conditions and communicate with other protocol layers. Within the Controller two software layers exist and are identified as switching path protocol (SPP) and switching connection protocol (SCP). The switching path protocol is responsible for end-to-end path management. It interfaces with the feature processor section 146, the link data ports 148 of FIG. 3a and the switching connection protocol (SCP) SCP is responsible for the stage by stage connections across the network. The SCP interfaces with the switching path protocol (SPP) in the controller 140. The switching path protocol communicates with the feature processor section via the message FIFO buffers 156, 158 and 160 illustrated in FIGS. 3a and 6.

FIG. 8 illustrates a block diagram of a packet control buffer (PCB) with corresponding (PCB) entries. Since the switching path protocol may simultaneously manage many active channels, each channel using the same controller processor and software as a common resource, some means must be provided to recall the state of each active channel when the time comes to service the channel using this common resource. This state information of each active channel is maintained by path control buffers (PCBs).

There are ninety-six available path control buffers. They are dynamically assigned to either a terminal port, a bridge port, or a link data port (LDP). At initialization they are all placed in a double linked list identified as a "Free" list. They are moved from the beginning of the free list to the end of the "Transient" list during the setting up of a path. Once the path is established and tested via confirm commands, the path control buffer allocated to a path is placed in a "talk" list for a voice path and a "link data port (LDP)" list for a data path.

During the termination of the path, the path control buffer is moved back to the transient list and once the path clear function is complete, the path control buffer is returned to the end of the "free" list.

As illustrated in FIG. 6, the path control buffer 222 is used by the controller to manage the real time details of each active call and path throughout its life, and to provide a record which may be used to trace its history, particularly for problem tracing. The call message buffer 238 (CMB) is used by the feature processor section to pass "Action" requests to the switching path protocol via the "Action" FIFO buffer 158 and by the switching path protocol to pass the current state of a path control buffer (PCB) to the feature processor by means of the "Event" FIFO 156. The "event" communication message buffers (CMBs) have event specific structures with a common element. A CMB is a subset of a path control buffer. For a path set, a communication message buffer is the means for the feature processor to provide to the switching path protocol the desired parameters of the path to be created. For originating and terminating paths, a path control buffer is used by the controller to record the path parameters and real time status. For data calls, a path control buffer is used to manage the transfer of the data to and from the required data buffers in memory. PCBs are shared by both the switching path protocol and switching connect protocol.

Each incoming/outgoing channel pair in a link data port will be driven by a state machine also (implemented by the controller's switching path protocol (SPP) software) responding to network commands and feature processor commands. This allows the controller to handle the path until there is a successful conclusion, or there is a natural break or an error condition. It allows the switching path protocol to handle an incoming path set autonomously, until it needs to alert the feature processor when it has reached a certain stage.

Throughout the lifetime of each call the channel monitor FIFO 184 (FIG. 4) in the interface switch remains connected, and maintains a complete record of the connection details in a packet control buffer which is managed by the SPP. The information in the packet control buffer is shared by both the switching path protocol and switching control protocol. Whenever a stage is reached where call processing needs to make a decision, a copy of the present state of the call and its data is placed in a call message buffer (CMB) and a pointer to the CMB is placed in the Event Message FIFO buffer.

Path control buffers contain many fields for providing pertinent data and each field entry may be used during an active call. If the call message buffer 238 passes information to the feature processor from the switching path protocol (SPP), the information is the "event" type and the incoming command and argument. However, if a call message buffer passes information to the switching path protocol from the feature processor, the information in this word is the path control code which indicates the desired "action" to be performed. The control code will determine the structure of the command specific portion of the communication message buffer (CMB).

A packet control buffer corresponding to a path contains an entry representing its packet control buffer (PCB) number which is from 0 to 95. This allows the controller to correlate its packet control buffer with the feature processor path ID. The PCB number is provided by the controller. Any subsequent events to the controller pertaining to this path include the controller ID which is the PCB number.

State/Path status entry contains the state of the data or terminal port channel pair state machine and some pertinent status bits.

When an active link data port channel is processed, the switching path protocol will execute a state machine for that link data port and channel with the state being provided by the state entry in the Pocket Control Buffer. The switching path protocol (SPP) is responsible for the contents of the state entry. When the SPP passes a signal to the feature processor, the feature processor examines the command entry and the status bits to determine the cause of the event.

FIFO buffer 156 is polled by the feature processor at some regular rate determined by a scheduler. Path status information is as follows:

______________________________________ Path Status ______________________________________ Path set attempt overflow (E) Path clear (E) Packet sent (E) Path fail (E) ACK (E) Packet received (E) NAK (E) Packet transmit fail (E) Speech path complete (E) ______________________________________

Another entry in the packet control buffer contains information on local logical address code (LAC) and distant logical address code. The local LAC is the originating LAC when setting a path or the destination LAC when terminating a path. The distant LAC is the destination LAC used when originating a path set or the originating LAC when terminating a path.

Depending on system requirements, some terminal ports of interface switches may serve as tape recorders for recording speech. An entry for containing information on tape port and channels in the packet control buffer is used for tape path sets (which are held until a configuration change is made). It contains the port and channel numbers that need to be joined to a voice path (from a tape card served by the interface switch) to make a connection to a tape channel.

A further entry in the packet control buffer contains information on path and call message buffer identity. The path identity number is used by the feature processor to identify the path for commands, and the call message buffer pointer in feature processor RAM for freeing up obsolete call message buffers for new actions.

The feature processor is responsible for allocating path IDs. When the feature processor initiates a path set, the path identity entry indicates that information. When the switching path protocol passes an event signal to the feature processor for a new path (speech path complete, for example) the path identity will be blank. The feature processor will assign a path ID and include it in the next command back to the switching path protocol.

The feature processor identifies which path a call message buffer is associated with by the path ID. The switching path protocol identifies the path by the controller ID entry in the communication message buffer (CMB). The controller ID is the path control buffer number assigned to a particular path.

When the switching path protocol passes an event signal to the feature processor, the call message buffer identity tells the feature processor which call message buffer (CMB) can be free. The feature processor is responsible for managing the CMB resource allocation and then clears the CMB and places the pointer for the CMB into the free pool.

The join parameters entry in the packet control buffer contains the port and channel pair for a joining. The act of associating a terminal port, a bridge port, or a tape port and channel to a crosspoint memory location is a joining. If the path set command from the Communication Handler is not an automatic join, the contents of the join parameters entry are interpreted as the port-channels used to connect to forward or reverse crosspoint memory locations. If however the path set is not automatic join, the communication handler will have to do a separate join of the switch port and channels. The switch port and channel pair is set by the feature processor. The join information contains three bits. One bit for originating and terminating, one bit for forward and reverse and one bit for active and inactive.

The attempt count and delay information entry is the number of attempts the switching path protocol has made when setting up a path. Delay is a general purpose timer. The use of the timer is dependent upon the state. The granularity of this timer is 125 .mu.s or one frame. This entry is set and used by the switching path protocol only. A typical use of this timer would be setting the timer to 8 after sending a confirm command. The state would be "confirm pending". If the timer times out before the confirm is returned, the switching path protocol would launch another confirm command via a link data port. Once the confirm is received, the contents of the delay is 8 minus the current entry. This is the frame delay of the confirm command and is needed by the processors in each interface card for echo cancellation.

Confirms are launched into the switching network via a link data port channel. This allows the controller to accurately determine when the confirm command was sent into the switching network and when it was received back from a round trip. The packet control buffer has a entry to keep track of the link data port containing the confirm command.

The parameters that are used for measuring the confirm round trip delay in a port each have an entry in the packet control buffer corresponding to the path. These parameters are: start of time for confirm sent; end of time for confirm sent; incoming reverse port that confirm is received; and incoming reverse channel time which is the local channel time that the incoming reverse channel for a voice path is processed.

During the operation of the switching network, path information is sent throughout the system via data path set. The packet type entry (data paths only) in the packet control buffer contains the information in the argument portion of a "PACKET TYPE" command. Since many data packets are transmitted via the switching network, various packet types have to be differentiated. The relevant packet type information is written into this entry by the switching path protocol upon reception of a "packet type" command or loaded by the feature processor when passing a "send packet" action to the switching path protocol.

The packet buffer control entry contains information for data paths only. This entry contains the pointer to the packet buffer control block.

The packet start entry contains the base pointer for the current "transmit" or "receive" packet corresponding to a switch element sending or receiving a packet. This entry is set by the feature processor when transmitting a packet and set by the switching path protocol (SPP) when receiving a packet. The receiving SPP fills the entry from a list of available packet buffers. There are several link lists of packet buffers corresponding to each packet buffer size. The SPP gets an appropriate packet buffer from the link list. Thereafter, the list is replenished by the feature processor.

The packet limit entry contains information for data paths only. On transmit, it contains the actual size of the packet and is set by the feature processor. For receive, this is a value which defines the size of the current packet. The maximum size of the packet is already defined by the packet type command. When "next word=packet limit", the packet has been sent and the next channel must contain the "end of packet command" and a checksum. The checksum can occur before this (evident by the reception of the end of packet command) if the packet length is less than the Packet Limit.

The original word/next word entry in the packet control buffer contains information for data paths only. The original word is the starting offset from the base address which indicates the beginning of a transmit o receive buffer when transmitting or receiving data. This allows the starting offset to be copied to the "next word" when a packet error occurs. This eliminates the need to keep the pointer to the packet buffer control block.

The next word is the index offset from Packet Start to the current entry of the packet buffer. During transmit, this entry points to the next packet entry to be transmitted from the packet buffer. During receive, this entry points to the destination in the packet buffer of the next data received on the data channel. When a complete packet is received, the feature processor can use this entry to determine the length of the packet.

The checksum for data paths entry contains the checksum of the current packet being sent. It is calculated and transmitted at the end of the packet as the argument of a Checksum command by the originating switching path protocol when transmitting a packet and is calculated and compared to the received checksum command argument by the destination switching path protocol when receiving a packet. This value is calculated by adding the data to the previous checksum entry. The updated checksum is then stored in the original location. When starting to send or receive a packet, this entry is set to zero. This checksum will be the sum of the arguments for data command codes and packet type.

The crosspoint information entry is used to store both the address of forward and reverse crosspoint memory locations. This information is necessary for doing joins as well as for orderly clear down in the event of negative acknowledges (NAKs) or forced release.

Communication between the protocol layers is accomplished through the call message FIFO buffers. The data relating to each path and call in progress is held in a separate path control buffer in the controller RAM. A similar structure is held for each path/call, either in progress or planned, in the feature processor RAM. The data relating to path "actions" requested by the feature processor, or "events" returned by a switching path protocol monitored channel to the feature processor, are passed between them using call message FIFO buffers in feature processor RAM which are accessible by both the switching path protocol (controller) and the feature processor section. The Communication Handler is responsible for the management of the call message buffers (CMBs). Access to these CMBs is controlled by an index for each. These indexes are passed between the SPP and the feature processor section in a way that prevents either from interfering with the operation of the other, by means of call message FIFO buffers 156, 158 and 160.

The FIFO buffers are 9 bits wide allowing 512 possible call message buffers. The 9 bits define the call message buffer index. The location of the call message buffer can be found using the CMB base pointer entry in the feature processor memory map table located in feature processor RAM. The message buffers provided are shown below:

______________________________________ FIFO BUFFER WRITTEN BY READ BY ______________________________________ Free (empty CMBs) Feature processor SPP (controller) Event SPP (controller) Feature processor Action Feature processor SPP (controller) ______________________________________

The free message FIFO buffer contains pointers to call message buffers which are presently unoccupied. The feature processor places the call message buffer and the related pointer in a pool of empty CMBs. There are two sets of free call message buffers, both managed by the feature processor. The pool of free call message buffers is maintained separately from the free CMB FIFO buffer so that the feature processor does not need to access the free CMB FIFO buffer when it wishes to prepare a CMB with a path or packet request to place in the action FIFO buffer. It is from this pool that the feature processor replenishes the free CMB FIFO buffer.

The feature processor monitors the occupancy of the free message FIFO buffer 160, and maintains an adequate supply of communication message buffer (CMB) numbers from zero to 511. The feature processor will take a pointer to any empty CMB from the pool and load it with the parameters for a new call before placing the pointer in the Action FIFO buffer 158. The switching path protocol will take a pointer to a free communication message buffer from the free FIFO buffer 160 whenever a new incoming call is detected or an action takes place on the path that requires reporting.

The act of the switching path protocol (controller) taking a communication message buffer pointed to by a pointer in the action FIFO buffer 158 entails copying the pertinent information from the communication message buffer into a packet control buffer in high speed RAM in the address space of the controller. Before placing a pointer to a communication message buffer in the Event FIFO buffer 156, the controller must copy the appropriate entries of the packet control buffer in its high speed RAM
166 back to the CMB location in the Feature Processor RAM.

Those packet control buffers whose contents have been copied back into a communication message buffer in a feature processor RAM when they contain incomplete calls, and whose CMB pointers have been placed in the event FIFO buffer 156, continue to be retained by the switching path protocol managing the calls to ensure correct handling of any further activity. The communication message buffer will contain the call state at the time the event was posted. Any subsequent events which need to be passed to the feature processor will be done by fetching another communication message buffer from the free FIFO. The feature processor will then read the CMBs in the correct order because of the FIFO function.

H. Channel Allocation Store

The channel allocation system according to the invention maintains the availability (busy/free status) of every outgoing channel on every switch port in the switch element 15 and determines the earliest free channel within a specified time window on the identified switch ports. In the preferred embodiment, the channel allocation system receives an identification from the switch element controller of the port group to be utilized for the outgoing communications link. The channel allocation system maintains the assignment of which switch ports comprise each port group. The port group indicates which switch ports should be searched for the earliest free channel. Port groups 0 through 19 are reserved for identifying individual switch ports, while port groups 20 through 31 are reserved for specifying groups of switch ports. When a port group is specified as an outgoing route, the identities of the individual switch port(s) comprising the port group must be determined.

An availability table 300, as shown in FIG. 9a, is the central element of the channel allocation system. In selection of an output switch port and channel, the free/busy status of the switch ports and channels, maintained in the availability table 300, is searched for the earliest free channel. To limit the search of the availability table 300 to appropriate switch ports and channels, the rows and columns of the availability table 300 (corresponding to switch ports and channels of the switch element 15) to be included in the search may be controlled. Means may be provided to enable only the rows of the availability table 300 that correspond to the switch ports included in the identified port group. Similarly, means may be provided to enable only certain columns corresponding to certain channels of the availability table 300.

The availability table 300, configured as an array of associative memory cells 302, maintains the availability (free/busy status) of each channel in the switch element. The availability table 300 is used to ascertain the earliest free channel within a specified time window on the switch ports identified by the port group. A basic switch element has 20 switch ports with 32 channels. Accordingly, in order to store the availability of each port and channel, the availability table 300 is arranged in 20 rows of associative memory cells 302 (one row for each of the switch ports) with 32 columns (one for each channel). By convention, if a channel is available the corresponding cell 302 in the availability table 300 will have a value of 1
(high logic value), and if the channel is busy the corresponding cell 302 will have a value of 0 (low logic value). In this manner, the appropriate rows of the availability table 300 can be readily searched for the earliest available channel.

A schematic diagram of an individual associative memory cell 302 of the availability table 300 is shown in FIG. 9b. As shown in the figure, each cell 302 of the availability table 300 has a memory element 304, 6 inputs and 2 outputs. The memory element 304 maintains the free/busy status (0 or 1) of the corresponding switch port and channel. An individual cell 302 in the availability table 300 is enabled (included in a search) when both its Horizontal Enable (H.sub.EN) and Vertical Enable (V.sub.EN) inputs have logic values of 1.

A column of the availability table 300 is constructed by connecting the Vertical Output (V.sub.OUT) of each cell 302 to the Vertical Input (V.sub.IN) of the cell 302 beneath it. Similarly, a row in the availability table 300 is created by connecting the Horizontal Output (H.sub.OUT) of each cell 302 to the Horizontal Input (H.sub.IN) of the cell 302 immediately to its right. Furthermore, the Vertical Input (V.sub.IN) to each cell 302 in the top row of the array and the Horizontal Input (H.sub.IN) to each cell in the left column of the array are wired to logic values of 0.

The value in the memory element 304 in each cell 302, shown in FIG. 9b, may be controlled by the CH.sub.UP input (Selected Channel Update) and the ST.sub.INIT input (Status Initialization). The CH.sub.UP input is utilized to set the cell 302
corresponding to the selected channel to the busy state. Additionally, the ST.sub.INIT input (Status Initialization) directly controls the availability state of each memory element 304. The ST.sub.INIT input can be used, e.g., to initialize the status of each cell 302 to a free state at system initialization, to update the value of a cell 302 to a free state or to set all of the cells 302 associated with channels that are not normally available for call routing to a busy state (e.g., clocking and status broadcast channels).

The logic of each cell 302 in the availability table 300 is such that the Horizontal Output (H.sub.OUT) of a particular row in the availability table 300 will have a logic value of 1 if the respective row is enabled by its Horizontal Enable (H.sub.EN) and any cell in the row, which is simultaneously enabled by its corresponding Vertical Enable signal (V.sub.EN), is free (indicated by a logic value of 1 in its memory element 304). Similarly, the Vertical Output (V.sub.OUT) of a particular column in the availability table 300 will have a logic value of 1 if its respective column is enabled by its Vertical Enable (V.sub.EN) and any cell in the column, simultaneously enabled by its corresponding Horizontal Enable signal (H.sub.EN), is free (indicated by a logic value of 1 in its memory element 304). This logic can be implemented with the following boolean equations:

where M equals the value stored in the memory element 304.

As preferably embodied, the channel allocation system shown in FIG. 9c, is comprised of the availability table 300, as well as a switch port enable block 306, a channel enable block 308, and channel and switch port output blocks 310, 312.

As shown in FIG. 9c, the switch port enable block 306 is comprised of a port group input register 314, port group decoder 316, port group decode registers 318 and switch port latch 320. The switch port enable block 306 receives search requests (in the form of a 5 bit port group) from the switch element controller by means of its port group input register 314. The 5 bit port group value is translated by the switch port enable block 306 into the switch ports that should be searched for free channels. The switch port enable block 306 decodes the 5 bit port group value and activates its appropriate output line(s) (each of the 20 outputs of switch port enable block 306 correspond to a switch port). The output lines are latched by means of the switch port latch 320 (containing 20 latches) and serve to enable the corresponding row(s) in the availability table 300.

When a port group value between 0 and 19 (corresponding to an individual switch port) is received at the port group input register 314, the 5 bit port group number is decoded by the logic of the port group decoder 316 to activate the corresponding switch port output line to the availability table 300. Similarly, when a port group value between 20 and 31 (corresponding to a defined group of switch ports) is received at the port group input register 314 it is used to access one of twelve port group decode registers 318. These port group decode registers 318 are 20-bit registers that allow any of the 20 bits (each corresponding to a switch port) to be marked during system initialization in order to indicate those switch ports included in a particular port group. During initialization, the switch element controller initiates a series of twelve SET PORT GROUP commands (one for each port group decode register) that indicate the port group decode register address and the corresponding data that identifies the port(s) in the port group. The data consists of a 20 bit word where each bit corresponds to a switch port. A 1 in the bit position indicates that the associated switch port is a part of that port group and a 0 in the bit position indicates that the switch port is not a part of the port group. (If any ports are taken out of service, or returned to service, during system operation the port group decode registers 318 can be reprogrammed).

During operation, the output of the port group decode register 318 addressed by the port group value, via the port group decoder 316, activates the corresponding output lines of the switch port enable block 306. The outputs of the switch port enable block 306 are used to drive the Horizontal Enable lines (H.sub.EN) of the rows of cells 302 in the availability table 300; thus enabling the appropriate rows of the availability table 300.

As preferably embodied, a timing search window may be implemented by a channel enable block 308, shown in FIG. 9c, which includes start and end channel input registers 322, 324, channel decoder 326 and channel select register 328. The timing window is defined by two 5 bit values indicating the start and end channel values. These values are received from the switch element controller and placed in the start and end channel input registers 322, 324. The start and end channels define the timing window over which the free channel searches are performed.

Due to the non-alignment of frames arriving on the different switch ports of a switch element, a path set-up command received on a particular channel of an incoming switch port may not correspond to the same local channel number of the respective switch element. Thus, the arriving path set-up command should be assigned a local channel time corresponding to the channel of the respective switch element. The start channel for the search is equal to the local channel number of the incoming path set-up command plus 1, enabling the first free channel to be as close as possible to the incoming channel. The end channel is generally the start channel minus one (or the local channel number of the incoming path set-up command) to allow the search window to include all of the channels. The 5 bit start and end values are entered into the channel decoder 326 which access the channel select register 328.

As illustrated in FIG. 9d, the channel select register 328 is made up of a ring of 32 associative memory cells 330 (one for each column of the availability table 300). The channel select register 328 performs two functions in the channel allocation process. The functional state of the channel select register 328 is controlled by the logical value at the Function Select input (F.sub.S) of each cell 330. In the first function, where F.sub.S equals 1, the channel select register 328
initiates a broad search of the availability table 300 by enabling all of the columns in the availability table 300 within the defined search window. The broad search of the availability table 300 ascertains all of the available channels within the search window on the appropriate switch ports (enabled rows). In the second function, where F.sub.S equals 0, the channel select register 328 performs a focused search by evaluating those channels that were determined in the broad search to be available and then selecting the earliest available cell 330 within the search window (corresponding to the earliest available channel). During the focused search, only the one column in the availability table 300 associated with the selected channel is enabled, and the particular switch ports having an available channel in the selected time slot are ascertained.

As shown in FIG. 9d, the channel select register 328 (illustrated with seven cell) is created by connecting the Horizontal Output (H.sub.OUT) of each cell 330 to the Horizontal Input (H.sub.IN) of the cell 330 to its right. A circular register is created by connecting the Horizontal Output (H.sub.OUT) of the last cell in the channel select register 328 to the Horizontal Input (H.sub.IN) of the first cell. The start and end channels provide two inputs (S and E) to each of the register cells
330. By convention, the channel decoder 326 outputs a logical value of 1 to the S input of the cell 330 selected as the start cell, while the S input for all of the other cells 330 in the channel select register 328 will have logic values of 0. Similarly, the E input to the cell 330 selected as the end cell will have a logical value of 1 while the E input for all of the other cells 330 will have logic values of 0.

As shown in FIG. 9d, each cell 330 in the channel select register 328 has a memory element 332, 5 inputs and 2 outputs. The value stored in the memory element 332 controls whether or not the corresponding column of the availability table 300 is enabled. By convention, the memory element 332 will have a 1 if the corresponding column is to be enabled, and will have a 0 otherwise. The Vertical Output (V.sub.OUT) of each cell 330, equal to the value contained in the memory element 332, is used to drive the Vertical Enable lines (V.sub.EN) of the columns of cells 302 in the availability table 300. The Vertical Inputs (V.sub.IN) to each cell 330 in the register 328 are received from the Vertical Outputs (V.sub.OUT) of the bottom row of cells 302
in the availability table 300 and will have logic values of 1 for those columns having available channels on the appropriate switch port(s) (enabled rows). The Function Select input (F.sub.S) controls the functional state of the channel select register
328.

FIG. 9e illustrates the first function (broad search) of channel select register 328, illustrated with seven cells 330. The first function of the channel select register 328 is activated by setting the value of the Function Select input (F.sub.S) to each cell 330 in the channel select register 328 to a logic value of 1. The logic of each cell 330 in the register 328 is such that when F.sub.S (function select) has a logic value of 1 the value of the memory element 332 in each cell 330
will have a logical value of 1 for each of the cells between (and including) the defined start and end channels, as shown in FIG. 9e. This logic can be implemented with the following boolean equations:

where M equals the value stored in the memory element 332 and F.sub.S equals 1. During the broad search of the availability table 300, all of the columns in the window between the start and end channels are enabled (by having V.sub.OUT equal to
1 for each of the corresponding cells 330). The Vertical Inputs (V.sub.IN) to each cell 330 in the register 328, received from the corresponding columns of the availability table 300, will have logic values of 1 for those columns having available channels on the enabled switch port(s).

The second function of the channel