High-speed queue sequencer for a burst-switching communications system

We claim:

1. A high-speed queue sequencer for use in a switch of a burst-switching communications system, a burst being a plurality of bytes, said system including a plurality of switches interconnected by time-division multiplexed communications links, each link having a plurality of frames within each second of time, each frame having a plurality of channels, each channel having communications capacity for the transmission of one byte, a byte being a predetermined number of bits, a bit being one binary digit, said system including a plurality of ports, each port being a component of a switch, said switch including a queue sequencer and at least one switching processor, said queue sequencer and switching processor(s) being coupled via a queue-sequencer bus, said queue sequencer comprising:

(a) a data/address bus;

(b) control means coupled with said data/address bus for controlling said queue sequencer, said control means including stored-program memory and execution means and queue-memory means for storing administrative information pertaining to bursts passing through said link switch;

(c) enque/deque means coupled with said data/address bus, said enque means for performing the administration required for placing a burst on an output queue, said output queue being a list which indicates those bursts awaiting assignment to an output channel in a communications link, said deque means for assigning the highest priority burst on an output queue to an idle output channel of said communications link and removing said assigned burst from said output queue, said enque/deque means operating substantially in parallel with and independently of said control means;

(d) request-holding means coupled with said data/address bus, for receiving requests from said switching processor(s), determining the priority of each request, storing said pending requests within priority classes, and outputting said requests within each priority class in the same time order as received, said request-holding means operating substantially in parallel with and independently of said control means;

(e) input-interface means coupled between said queue-sequencer bus and said request-holding means, for providing an interface between said queue sequencer and said switching processor(s), said input-interface means having the ability to receive a request from a switching processor of said switch and to transmit said request to said request-holding means, said input-interface means operating substantially in parallel with and independently of said control means; and

(f) output-interface means coupled between said data/address bus and said queue-sequencer bus, for providing an interface between said queue sequencer and said switching processor(s), said output interface means having the ability to transmit a buffer address to a switching processor, said output-interface means operating substantially in parallel with and independently of said control means;

(g) whereby said queue sequencer operates substantially in parallel with and independently of said switching processor(s), and said queue sequencer acts on behalf of all switching processors of said switch.

2. A high-speed queue sequencer for use in a switch of a burst-switching communications system as described in claim 1 wherein the transmission speeds over said communications links are substantially equivalent to the T1 rate or a higher rate.

3. A high-speed queue sequencer for use in a switch of a burst-switching communications system as described in claim 1 wherein a byte is eight bits.

4. A high-speed queue sequencer for use in a switch of a burst-switching communications system as described in claim 1 wherein said request-holding means comprises one or more first-in first-out memories, each of said memories including the required control functions.

5. A high-speed queue sequencer for use in a switch of a burst-switching communications system as described in claim 1 wherein said stored-program memory is a programmable read-only memory having a word length of at least sixty-four bits.

6. A high-speed queue sequencer for use in a switch of a burst-switching system as described in claim 1 wherein said queue-memory means is a random-access memory coupled with said data/address bus and said control means.

7. A high-speed queue sequencer for use in a switch of a burst-switching system as described in claim 1 wherein said communications system includes a link switch and said queue sequencer is a component of said link switch.

8. A high-speed queue sequencer for use in a switch of a burst-switching system as described in claim 1 wherein said communications system includes a hub switch and said queue sequencer is a component of said hub switch.

9. A high-speed queue sequencer for use in a switch of a burst-switching communications system, a burst being a plurality of bytes, a byte being a predetermined number of bits, a bit being one binary digit, said system including a link switch having a plurality of ports, each port being a component of said switch, each port being associated with a communications channel, said link switch including a queue sequencer and at least one switching processor, said queue sequencer and switching processor(s) being coupled via a queue-sequencer bus, said queue sequencer comprising:

(a) a data/address bus;

(b) control means coupled with said data/address bus for controlling said queue sequencer, said control means including stored-program memory and execution means and queue-memory means for storing administrative information pertaining to bursts passing through said link switch;

(c) enque/deque means coupled with said data/address bus, said enque means for performing the administration required for placing a burst on an output queue, said output queue being a list which indicates those bursts awaiting assignment to an output channel, said deque means for assigning the highest priority burst on an output queue to an idle output channel and removing said assigned burst from said output queue, said enque/deque means operating substantially in parallel with and independently of said control means;

(d) request-holding means coupled with said data/address bus, for receiving requests from said switching processor(s), determining the priority of each request, storing said pending requests within priority classes, and outputting said requests within each priority class in the same time order as received, said request-holding means operating substantially in parallel with and independently of said control means;

(e) input-interface means coupled between said queue-sequencer bus and said request-holding means, for providing an interface between said queue sequencer and said switching processor(s), said input-interface means having the ability to receive a request from a switching processor of said link switch and to transmit said request to said request-holding means, said input-interface means operating substantially in parallel with and independently of said control means; and

(f) output-interface means coupled between said data/address bus and said queue-sequencer bus, for providing an interface between said queue sequencer and said switching processor(s), said output interface means having the ability to transmit a buffer address to a switching processor, said output-interface means operating substantially in parallel with and independently of said control means;

(g) whereby said queue sequencer operates substantially in parallel with and independently of said switching processor(s), and said queue sequencer acts on behalf of all switching processors of said link switch.

10. A high-speed queue sequencer for use in a switch of a burst-switching communications system as described in claim 9 wherein a byte is eight bits.

11. A high-speed queue sequencer for use in a switch of a burst-switching communications system as described in claim 9 wherein said request-holding means comprises one or more first-in first-out memories, each of said memories including the required control functions.

12. A high-speed queue sequencer for use in a switch of a burst-switching communications system as described in claim 9 wherein said stored-program memory is a programmable read-only memory having a word length of at least sixty-four bits.

13. A high-speed queue sequencer for use in a switch of a burst-switching system as described in claim 9 wherein said queue-memory means is a random-access memory coupled with said data/address bus and said control means.

14. A high-speed queue sequencer for use in a switch of a burst-switching system as described in claim 9 wherein said communications system includes a link switch and said queue sequencer is a component of said link switch.

15. A high-speed queue sequencer for a burst-switching system as described in claim 9 wherein said communications system includes a hub switch and said queue sequencer is a component of said hub switch.

Description Submit all comments and votes

CROSS-REFERENCES TO RELATED APPLICATIONS

U.S. patent application Ser. Nos. 762,593, 762,594, 762,641, 762,589, 762,592, 762,588, 762,591, and 762,590, filed concurrently herewith and assigned to the same assignee hereof, contain related subject matter.

TECHNICAL FIELD

This invention relates to communications switching systems and their components providing fully integrated voice and data services. More particularly, the invention relates to high-speed processors employed in integrated switches.

BACKGROUND OF THE INVENTION

Communications users, particularly telecommunications users, have required ever-increasing ranges of information transport. In the traditional telephone network, voice signals were transmitted and switched through the network in analog form. Because of economies in certain types of transmission media, voice signals were digitized for transmission purposes. Time-division multiplexing of digital voice signals was the most economical way to utilize the wire-based transmission plant of the telephone network.

With the advent of data processing and distributed data processing systems, a need arose for the transmission of data over communications links and through the telephone network. For purposes herein, "data communications" is broadly defined as any information transmitted through a digital communications network other than digitized voice signals. Currently, the most common type of data communications is alphanumerical data, i.e., text or numerical data. Future communications requirements include the ability to carry image and video communications in substantial proportions. Image communications is the transmission of a still picture or motionless object. Facsimile transmission, presently the most common form of image communications, is the transmission of the image of a block or page of information rather than transmission of the digital representations of the letters or characters which comprise the block or page. Video transmission adds motion to image transmission. It can range from transmission of full motion color television signals to freeze-frame video, which is a series of sequential still images. As image and video communications become more prevalent, the demand for bandwidth will increase dramatically. No doubt, there will be even greater communications demands in the future, both as to diversity of services and traffic capacities.

It is well settled that digital time-division multiplexed transmission is preferred for both voice and data communications for a number of reasons not the least of which are the substantial economies realizable from digital multiplexing. Digital multiplexing can occur between communications of the same type, such as interleaving a plurality of voice conversations onto a single pair of wires. A form of multiplexing can also occur between communications of different types, such as inserting data communications into detectable silence periods in voice communications. Such detectable silence periods may occur while one conversant is listening or in gaps between words or syllables of a speaker. Multiplexing is particularly suited to adapting to variable bandwidth demands which result from the inherently "bursty" nature of most voice and data communications. Thus, integration of voice and data is spurred by the substantial economies of digital multiplexing and the growing diversity of services.

A digital communications network or system is said to be "integrated" or to provide "integrated services" if the network or system has the capacity to transmit voice and data communications through common equipment and facilities. An attribute of integrated communications systems is the use of intelligent processors at various points in the network for control purposes. Control is "distributed" or "dispersed" if the overall network control emanates from multiple geographical points, each point using local information or information provided by distant points via the network itself. Thus, the intelligence in a distributed control network is dispersed throughout the geographical area being served. In particular, a switching decision which needs to be made by a local processor can be made with information immediately available to the local processor. In large communications systems, distributed control generally improves efficiency since the intelligence required to route local traffic is nearby. Distributed control also enhances survivability since a local portion of the system, being self-controlled, will remain operable in the event a distant control point should be out of service.

With the ever-increasing demand for transmission bandwidth, it is axiomatic that higher bit rates will be employed over communications links in the future. On the Bell System T1-carrier, of which millions of miles are already installed, a communications link carries 1.544 million bits per second. Links with substantially higher bit rates are feasible even with current technology. The provision of integrated services over high-speed communications links will require new methods, procedures, and protocols governing information transport through the network. In particular, additional bandwidth required by the system for routing and administration, i.e., the "overhead," should be minimized while permitting reasonable flexibility within the network to adapt to changing circumstances. Integrated switching apparatus should be capable of transmitting and routing information at T1 rates and higher, so that optimal channel utilization can be achieved.

Communications systems planners, and in particular telecommunications systems planners, seek high-speed processors for use in switches such that communications links may support integrated services at the T1 transmission rate (or the equivalent) and even faster rates. Such high-speed processors should have other features, such as low cost, ease of maintenance, high suitability for implementation in very-large scale integration technology, etc. It would substantially advance the state of the communications art if such a high-speed processor were available.

DISCLOSURE OF THE INVENTION

It is, therefore, an object of the invention to obviate the deficiencies in the existing art and to make a significant new contribution to the field of communications systems.

It is an object of the invention to provide a communications system having fully integrated voice and data services.

An object of the invention is to provide a communications system employing high-speed communications links, such links having bit rates of T1 or higher.

It is an object of the invention to provide a communications system having highly distributed control and equipment.

An object of the invention is to provide a communications system wherein the control functions are administered entirely through the transmission network; where reallocation of control capacity may be achieved entirely through the transmission network, flexibly, and with virtually no disruption of user services; and where in the event of a failure of a control processor, the responsibilities of the failed processor may be reassigned to one or more surviving control processors.

Another object of the invention is to provide an integrated communications system which makes efficient use of the copper-wire plants of existing telephone networks.

It is an object of the invention to provide methods of information transport within a communications system which require minimal routing and administrative overhead while permitting adequate network flexibility to adapt to changing circumstances.

An object of the invention is to provide an integrated communications system which features low-cost modular components with highly redundant circuits well suited for implementation in very large scale integration technology.

It is an object of the invention to provide an integrated communications system which has the capability to transport voice communications without subscriber-perceptible distortion or delay except possibly under overload conditions.

An object of the invention is to provide a communications system having the capability within each switching node to allocate bandwidth dynamically, i.e., within the current communications channel, and thereby to maximize bandwidth utilization throughout the system.

It is an object of the invention to provide methods of information transport within a communications system which have the capability of handling bursty information, i.e., digital messages of varying length, in a highly efficient manner.

An object of the invention is to provide a link switch which may be employed in a communications system, such link switch having an embodiment which is relatively small and inexpensive whereby it may be highly dispersed geographically and, if desirable, located nearby or on subscriber premises.

It is an object of the invention to provide a hub switch which may be employed in a communications system, such hub switch being a high-speed high-capacity switch which may be located at points of high concentration in the system.

An object of the invention is to provide a high-speed switching processor which may be embodied as a component or as several components in a link switch and/or hub switch of a communications system.

It is an object of the invention to provide a high-speed queue sequencer which may be employed in some embodiments of a communications system as a component in a link switch and/or hub switch.

An object of the invention is to provide a communications system having the capability of providing digital communications from origin port to destination port whereby possible noise interference will be substantially reduced, ease of maintenance improved, and security and privacy enhanced, particularly in the case where the origin port and/or destination port is located on user premises.

It is an object of the invention to provide an integrated communications system wherein the transmission rates received at the ports for bursts containing digitized voice are approximately equal to burst transmission rates over communications links, so that speed buffering of voice bursts within link switches is not required.

It is another object of the invention to provide an intelligent port circuit for a link switch, such port circuit having a high degree of control intelligence whereby the distributed control feature of a communications system may be enhanced when the port circuit is remotely located.

An object of the invention is to provide a port circuit for a link switch which may be located in the vicinity of the subscriber, on the subscriber's premises, or within end-user equipment, such that call or message propagation capacity exists at the hub-switch level, link-switch level, and even at the end-user equipment level, if desired.

It is another object of the invention to provide a port circuit for a link switch, such port circuit having a loop-back testing capability, whereby components of a burst switching system may be remotely monitored for operability including components of the port circuit itself.

An object of the invention is to provide a method of call set-up and take-down in a telephone communications system.

It is another object of the invention to provide a highly distributed control architecture for a communications system in which control capacity can be added or deleted incrementally with virtually no disruption in user services.

These objects are accomplished, in one aspect of the invention, by the provision of a high-speed queue sequencer for use in a switch of a burst-switching communications system. In such system, a burst is a plurality of bytes which represents, for example, a block of data or a spurt of voice energy sensed by silence/voice detectors located at voice ports. The system includes a plurality of switches interconnected by time-division multiplexed communications links. Each link has a plurality of frames within each second of time. Each frame has a plurality of channels. Each channel has communications capacity for the transmission of one byte. A byte is a predetermined number of bits, a bit being one binary digit. The system also includes a plurality of ports. Each port is a component of a link switch. A switch includes the queue sequencer and at least one switching processor. The queue sequencer and switching processor(s) are coupled via a queue-sequencer bus.

The architecture of the queue sequencer comprises a data/address bus. Control means are coupled with the data/address bus for controlling the queue sequencer. The control means includes stored-program memory and execution means, and queue-memory means for storing administrative information pertaining to bursts passing through the link switch.

Enque/deque means are coupled with the data/address bus. The verb "enque" means to add an entry to a queue; the verb "deque" means to delete an entry from a queue. The enque function performs the administration required for placing a burst on an output queue. The output queue is a list which indicates those bursts awaiting assignment to an output channel in a communications link. The deque function assigns the highest priority burst on an output queue to an idle output channel of the communications link and removes the assigned burst from the output queue. The enque/deque means operates substantially in parallel with and independently of the control means.

Request-holding means are coupled with the data/address bus. The request holding means function is to receive requests or commands from any switching processor(s), to determine the priority of each request, to store pending requests within priority classes, and to output these requests within priority classes in the same time order as received. The request-holding means operate substantially in parallel with and independently of the control means.

Input-interface means are coupled between the queue-sequencer bus and the request-holding means. The function of the input-interface means is to provide an interface between the queue sequencer and the switching processor(s). The input-interface means have the ability to receive a request or command from any switching processor of the switch and to transmit this request to the request-holding means. The input-interface means operate substantially in parallel with and independently of the control means.

Output-interface means are coupled between the data/address bus and the queue-sequencer bus. The function of the output-interface means is to provide an interface between the queue sequencer and the switching processor(s). The output-interface means have the ability to transmit a buffer address to a switching processor. The output-interface means operate substantially in parallel with and independently of the control means.

The queue sequencer operates substantially in parallel with and independently of the switching processor(s); and the queue sequencer acts on behalf of all switching processors of the switch.

In one embodiment of the invention, the burst-switching communications system includes a link switch and the switching processor is at least one component of the link switch. In another embodiment of the invention, the system includes a hub switch and the switching processor is at least one component of the hub switch.

In yet another embodiment of the invention, the request-holding means comprise one or more first-in first-out memories including the required control logic.

Thus, there is provided a high-speed queue sequencer which will meet the growing communications needs of the present and foreseeable future. This processor incorporates many features and advantages which will be explained in greater detail below.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of an embodiment of a burst-switching system.

FIG. 2 shows a preferred embodiment of the digital format of a burst.

FIG. 3 is a block diagram of a link switch in accordance with the invention.

FIG. 3A illustrates the four types of bursts in transit processed by a link switch.

FIG. 3B illustrates a typical prior art parallel priority-resolving circuit which may be used in various embodiments of the invention.

FIG. 4 is a block diagram of a hub switch showing, in particular, the coupling between the switching units of the hub switch with link groups.

FIG. 5 is a block diagram of a hub switch in accordance with the invention.

FIG. 6 is a block diagram of an alternate embodiment of a link switch showing a digital multiplexer coupled between the input and output port processors and twenty-four end-user instruments.

FIG. 7 shows the format of a dynamic buffer containing a portion of a burst in the central memory of a link switch.

FIG. 8 diagrammatically illustrates the linkages between buffers for three bursts on a queue within a link switch.

FIGS. 9A and 9B each show a buffer within character memory of a link switch at two different times in the processing of a burst through the link switch in order to illustrate the input and output indices of the buffer.

FIG. 10 illustrates the flow of four bursts through the input and output processors and character memory of a link switch.

FIGS. 11A through 11E show the linkages between the input and output processors and the queues and buffers in the central memory of a link switch for the various stages in the processing of a burst through a link switch from the time of arrival of the first byte to the time of transmission of the last byte.

FIGS. 12A and 12B illustrate the assignments of bursts to output channels within a link switch in the presence of contention for output channels.

FIG. 13 is a pictorial showing a preferred format of a burst including particular fields within the four header bytes.

FIG. 14 is a table summarizing the data-link escape procedure in accordance with the invention.

FIG. 15 is a schematic representation of a hub switch employed in a burst-switching network.

FIG. 16 is a schematic representation of a single switching unit of the hub switch of FIG. 15.

FIG. 17 shows a block diagram of a hub switching element of the switching unit illustrated in FIG. 16.

FIG. 18 is a diagram illustrating the relationships between hub channels and hub ring circulation periods during a time-division multiplexed hub frame.

FIG. 19 is a diagram illustrating the format of digital burst signals processed by the hub switch.

FIG. 20 is a table summarizing the operations of a switching unit of a hub switch.

FIG. 21 contains a block diagram of a typical link switch showing the queue sequencer and various embodiments, or firmware variants, of the switching processor.

FIG. 22 is a block diagram of the architecture of the basic switching processor.

FIG. 23 is a character state diagram for the finite state machine of the switching processor showing three states.

FIG. 24 is a channel state diagram for the finite state machine of the switching processor showing eight states.

FIG. 25 is a block diagram of the architecture of a queue sequencer in accordance with the invention.

FIG. 25A is a block diagram of an interface circuit employing handshaking logic which, with appropriate adaptation, may be used as any of the interfaces in the switching processor or queue sequencer.

FIG. 26 is a diagram showing the microcode format of the queue sequencer.

FIG. 27 is a diagram showing the microcode format of the switching processor.

FIG. 28 shows the memory configuration of the queue sequencer.

FIG. 29 shows the memory configuration of the switching processor.

FIG. 30 is a functional flowchart for the input processors of a link switch.

FIG. 31 is a functional flowchart for the output processors of a link switch.

FIG. 32 is a block diagram of a port circuit for an analog line which may be employed as a component of a link switch as shown in FIGS. 3 and 6.

FIG. 33 is a block diagram illustrating service sets and the hierarchy of service providers in a typical control architecture for a burst-switching system.

FIG. 34 is a diagram outlining the steps executed by various control processors required to set up a simple call in a burst-switching telephone communications system, such call originating at port X and terminating at port Y of the system.

FIG. 35 illustrates certain control bursts transmitted between control processors in a typical burst-switching control architecture, the illustrated control bursts corresponding to steps in a method of call set-up and take-down in accordance with the invention.

BEST MODE FOR CARRYING OUT THE INVENTION

For a better understanding of the present invention, together with other and further objects, advantages, and capabilities thereof, reference is made to the following disclosure and appended claims taken in conjunction with the above-described drawings.

Burst switching employs novel methods and equipment for switching digitized voice and data in a fully integrated way. As will be evident from the definition of a burst, any form of digital communications may be handled by burst switching. Burst switching systems typically are characterized by highly dispersed small switches, distributed control, and improved bandwidth efficiencies.

FIG. 1 shows a preferred embodiment of burst switching system 100. System 100 comprises high-capacity hub switch 102 and a plurality of link switches 104. Link switches 104 typically are small switching elements serving, for example, thirty-two ports or less. Twenty-four ports is a preferred number because of the twenty-four channels in a T1 span. Switches are coupled to each other by time-division multiplexed communications links 106, e.g., a T1-span. A plurality of end-user instruments 108 may be coupled via lines 110 with line circuits (not shown in the drawing). The line circuits are in turn coupled with ports which are components of link switches 104. A port of a link switch provides means of access to system 100 by users, by control processors, or by other distinct communications systems. A port-interface circuit provides an appropriate interface with such user, control processor, or other communications system. When interfacing with an end-user instrument, the port-interface circuit will be denoted herein as a line circuit. When interfacing with another communications system, the port-interface circuit will be denoted herein as a trunk circuit. When interfacing with a control processor or when speaking generically, the terms "port-interface circuit" or "port circuit" will be used herein.

For purposes herein, T-carriers comprise a hierarchy of digital transmission systems designed to carry voice or speech and other signals in digital form, employing pulse-code-modulation (PCM) and time-division multiplexing (TDM) techniques. The T1-carrier has twenty-four PCM speech channels. Each signal is sampled 8,000 times per second. Each sample is represented by an eight-bit code. Each frame is 193 bits, comprising a sample for each of the twenty-four speech channels followed at the end of the frame by