High-speed switching processor for a burst-switching communications system

Abstract

This invention provides a high-speed switching processor which may be employed as a component of a link switch or a hub switch in a burst-switching communications system. When so employed, transmission speeds for integrated voice and data services over communications links between switches may be equivalent to the T1 rate or higher. 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. In a preferred embodiment, the architecture of the switching processor includes a data/address bus, control including a stored program in a 64-bit wide PROM, a finite-state machine having character and channel states for generating a jump address in the stored program based on the status of an incoming burst, interfaces with other components of the switch such as the queue sequencer, a companion processor, and a dual-port RAM for generating a buffer address as a function of channel number for the dynamic buffer in character memory in which the incoming burst is being stored. In this architecture, most components of the switching processor operate substantially in parallel with and independently of the control which is a contributing factor to the overall speed advantage realized by the switching processor. With software or firmware variations, the switching processor may be employed as several different components of a link or hub switch.

Claims

We claim:

1. A high-speed switching processor 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 at least one switching processor, a queue sequencer, a character memory, and a channel clock, said character memory and queue sequencer each having a respective bus coupled therewith, said switching processor comprising:

(a) a data/address bus;

(b) control means coupled with said data/address bus for controlling said switching processor, said control means including stored-program memory and execution means, said control means having means for receiving and being responsive to a signal from said channel clock;

(c) jump-address means coupled with said data/address bus and said control means, for generating a jump address based on character-state and channel-state and for transmitting said jump address to said control means, said jump-address means operating substantially in parallel with and independently of said control means;

(d) external-interface means coupled with said data/address bus for providing an interface between said switching processor and said communications links and ports, said external-interface means having the ability to receive a byte in the current channel from a communication link or port, said external-interface means operating substantially in parallel with and independently of said control means;

(e) character-memory interface means coupled with said data/address bus for providing an interface between said switching processor and said character memory, said character-memory interface means having the ability to read or write a byte from said character memory, said character-interface means operating substantially in parallel with and independently of said control means;

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

(g) buffer-address means coupled between said queue-sequencer interface means and said character-memory interface means for generating a buffer address based on the channel number, said buffer-address means having the ability to receive said buffer address from said queue-sequencer interface means, said buffer address means operating substantially in parallel with and independently of said control means;

(h) said jump-address means being coupled with said external-interface means and having the ability to receive a byte of a burst from said external-interface means;

(i) said control means having the ability to receive said jump address from said jump-address means and to transfer processing control to the instruction in said stored-program memory located at the address indicated by said jump address.

2. A high-speed switching processor 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 switching processor 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 switching processor for use in a switch of a burst-switching communications system as described in claim 3 wherein said jump-address means comprises a finite-state machine having character states and channel states.

5. A high-speed switching processor for use in a switch of a burst-switching communications system as described in claim 4 wherein said character states of said finite state machine comprise clear, flag-found, and data-link escape found.

6. A high-speed switching processor for use in a switch of a burst-switching communications system as described in claim 5 wherein said channel states of said finite state machine comprise await first header byte, await second header byte, await third header byte, await fourth header byte, process burst, abort burst, await termination sequence, and process control burst.

7. A high-speed switching processor for use in a switch of a burst-switching communications system as described in claim 1 wherein said buffer-address means includes a dual-port random-access memory.

8. A high-speed switching processor 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.

9. A high-speed switching processor for use in a switch of a burst-switching communications system as described in claim 1 wherein said system includes a link switch and said switching processor is at least one component of said link switch.

10. A high-speed switching processor for use in a switch of a burst-switching communications system as described in claim 1 wherein said communications system includes a hub switch and said switching processor is at least one component of said hub switch.

11. A high-speed switching processor for use in a link 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 at least one switching processor, a queue sequencer, a character memory, and a channel clock, said character memory and queue sequencer each having a respective bus coupled therewith, said switching processor comprising:

(a) a data/address bus;

(b) control means coupled with said data/address bus for controlling said switching processor, said control means including stored-program memory and execution means, said control means having means for receiving and being responsive to a signal from said channel clock;

(c) jump-address means coupled with said data/address bus and said control means, for generating a jump address based on character-state and channel-state and for transmitting said jump address to said control means, said jump-address means operating substantially in parallel with and independently of said control means;

(d) external-interface means coupled with said data/address bus for providing an interface between said switching processor and said ports, said external-interface means having the ability to receive a byte in the current communications channel, said external-interface means operating substantially in parallel with and independently of said control means;

(e) character-memory interface means coupled with said data/address bus for providing an interface between said switching processor and said character memory, said character-memory interface means having the ability to read or write a byte from said character memory, said character-interface means operating substantially in parallel with and independently of said control means;

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

(g) buffer-address means coupled between said queue-sequencer interface means and said character-memory interface means for generating a buffer address based on the channel number, said buffer-address means having the ability to receive said buffer address from said queue-sequencer interface means, said buffer address means operating substantially in parallel with and independently of said control means;

(h) said jump-address means being coupled with said external-interface means and having the ability to receive a byte of a burst from said external-interface means;

(i) said control means having the ability to receive said jump address from said jump-address means and to transfer processing control to the instruction in said stored-program memory located at the address indicated by said jump address.

12. A high-speed switching processor for use in a link switch of a burst-switching communications system as described in claim 11 wherein a byte is eight bits.

13. A high-speed switching processor for use in a link switch of a burst-switching communications system as described in claim 12 wherein said jump-address means comprises a finite-state machine having character states and channel states.

14. A high-speed switching processor for use in a link switch of a burst-switching communications system as described in claim 13 wherein said character states of said finite state machine comprise clear, flag-found, and data-link escape found.

15. A high-speed switching processor for use in a link switch of a burst-switching communications system as described in claim 14 wherein said channel states of said finite state machine comprise await first header byte, await second header byte, await third header byte, await fourth header byte, process burst, abort burst, await termination sequence, and process control burst.

16. A high-speed switching processor for use in a link switch of a burst-switching communications system as described in claim 11 wherein said buffer-address means includes a dual-port random-access memory.

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

Description

CROSS-REFERENCES TO RELATED APPLICATIONS

U.S. patent application Ser. Nos. 762,593, 762,594, 762,641, 762,589, 762,642, 762,588, and 762,591, 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. In particular, 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 switching processor for use in a switch of a burst-switching communications system. In such system, a burst is a plurality of bytes which may represent, for example, a block of data or a spurt of voice energy as sensed by silence/voice detectors. The system includes a plurality of switches interconnected by time-division multiplexed communications links. Each communication 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. In a preferred embodiment of the invention, a byte is eight bits, e.g., as with an ASCII character.

The system also includes a plurality of ports, each port being a component of a switch. A switch includes at least one switching processor, a queue sequencer, a character memory, and a channel clock. The character memory and queue sequencer each has a respective bus coupled therewith.

The switching processor comprises a data/address bus. Control means are coupled with the data/address bus for controlling the switching processor. The control means include stored-program memory and execution means. The control means have means for receiving and being responsive to a signal from the channel clock.

Jump-address means are coupled with the data-address bus and control means. The function of the jump-address means is to generate a jump address based on character-state and channel-state and to transmit the jump address to the control means. The jump-address means operates substantially in parallel with and independently of the control means.

External-interface means are coupled with the data/address bus for providing an interface between the switching processor and the communications links and ports. The external-interface means has the ability to receive a byte in the current channel from a communications link or port. The external-interface means operates substantially in parallel with and independently of the control means.

Character-memory interface means are coupled with the data/address bus for providing an interface between the switching processor and the character memory. The character-memory interface means have the ability to read or write a byte from the character memory. The character-interface means have the ability to operate substantially in parallel with and independently of the control means.

Queue-sequencer interface means are coupled with the data/address bus for providing an interface between the switching processor and the queue sequencer. The queue-sequencer interface means have the ability to receive a buffer address from the queue sequencer. The queue-sequencer interface means operate substantially in parallel with and independently of the control means and queue sequencer.

Buffer-address means are coupled with the queue-sequencer interface means and the character-memory interface means for generating a buffer address based on the channel number. The buffer address means has the ability to receive the buffer address from the queue-sequencer interface means. The buffer address means operate substantially in parallel with and independently of the control means.

The jump-address means are coupled with the external-interface means. The jump-address means have the ability to receive a byte of a burst from the external-interface means.

The control means have the ability to receive the jump address from the jump-address means and to transfer processing control to the instruction in the stored-program memory located at the address indicated by the jump address.

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 aspect of the invention, the jump-address means includes a finite state machine having character states and channel states.

Thus, there is provided a high-speed switching processor which, with appropriate firmware or software modification, may be employed as one or more components of a link and/or hub switch. The switching processor 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 one frame-synchronization bit. The T1 line rate is 1.544 -million bits per second. The T2-carrier has a 6.312 megabit line rate and carries 96 PCM voice channels or the equivalent. These definitions of T-carriers are used only by way of example. These definitions are not critical to the operation or description of the invention.

Link switches may be organized into link groups. Any link switch within a link group has the ability to communicate with any other link switch within the same link group without the communication passing through the hub switch. In FIG. 1, there are four link groups labelled A, B, C, and D, in the drawing. Any communication between link switch 103 and link switch 112 necessarily must pass through hub switch 102; consequently, link switch 103 and link switch 112 are in different link groups, i.e., link groups A and D respectively. Hub switch 102 interconnects distinct link groups.

A small burst-switching system may not require a hub switch. For example, link group A may function as a complete system without hub switch 102. On the other hand, a large burst-switching system or a system having high survivability requirements might require more than one hub switch.

There are numerous alternate configurations for system 100, such as star, ring, tree-type configurations, and combinations of these structures, each configuration having certain advantages and disadvantages which may be more or less relevant depending on the requirements of the particular application. System 100 as shown in FIG. 1 is a preferred embodiment of a burst switch for reasons that are set forth below.

System 100 corresponds to a present-day central office or private branch exchange (PBX) typically having a capacity for servicing 98,000 lines and trunks. In burst switching, the switching function has been dispersed, that is, brought closer to the user. The link switches are small so that they can be dispersed into the user neighborhoods or businesses. A typical link switch may be mounted on a pole in residential areas, much like a small distribution transformer, or wall-mounted in a closet in commercial buildings.

The high dispersal of the switching function exhibited in FIG. 1 satisfies an objective of burst switching. The telephone industry has a large investment in outside copper plant. The outside plant represents a significant replacement value compared to the switching and terminal equipment. Burst switching will extend the usefulness of this plant by expanding the use of the plant to new services and improving the efficiency of established services.

The Integrated Services Digital Network (ISDN) is one new service area. This network might call for a bandwidth of 288,000 bits/second at the subscriber instrument or terminal. A short loop leading to a link switch perhaps a few hundred yards away will be better able to support this bandwidth than will a two-wire pair one to three miles long leading to a central office.

Burst switching is expected to permit the extraction of new services and bandwidths from the existing plant by moving much of the switching into the plant. As a side effect, the much shortened average loop length may show much less variation in impedance, permitting the striking of better compromises in the hybrid network. While there may be some delay through a burst network, burst switching will not require echo suppressors.

For installations in a new subdivision or building, or for replacement installations, the amount of copper required to be installed for burst-switch loops is much less than that required for a traditional switch. A recent applications study done by GTE Laboratories shows that burst switches installed in a rural area of about 2000 lines would have required only 15% of the outside plant that the present centralized installation required.

In burst switching, data characters are switched in the same way as digitized voice characters and through the same circuits. Likewise, any type of digitized analog signals, e.g., image packets, will be handled in a fully integrated way by a burst switching system. Fully integrated switches will better adapt to changing traffic mixes, from moment to moment and over the years.

Should the percentage of data compared to voice increase in the coming years, a burst switch will adapt without reconfiguration since it switches data in the same way as voice. Burst switching does differentiate between data and voice in one particular. Voice samples are perishable; excessive delay renders them useless. Data messages can be delayed much longer with acceptable performance. On the other hand, voice is redundant. Some voice samples may be lost without loss of voice quality. Data is not redundant and no bytes may be lost.

Burst switching therefore switches voice samples at higher priority than data so that a voice burst may have the first chance at resources in the case of contention. This minimizes the loss of voice samples (clipping). Data characters will be buffered in the case of contention so that no data is lost, although delivery may be delayed.

Another instance of integration in burst switching is that any port may be coupled with a line or a trunk, as well as being either a voice or data line. The port circuit will differ, but a trunk may appear anywhere in the switch. A trunk may be either analog or digital.

A burst may contain a digitized voice (or speech) or data message. For purposes herein, a burst containing a communication other than digitized speech will be treated as a data communication. A "talkspurt" is a single continuous emission of voice energy as would occur in the pronunciation of a single syllable. A speaker in ordinary conversation issues voice energy 35-40% of the time. Burst switching employs silence (or speech) detection so that system resources such as transmission channels are dedicated only while there is information to send, that is, during the burst. At the conclusion of a burst, the channel is available for assignment to another burst. Thus, burst switching utilizes its resources with two to three times the efficiency of traditional circuit switching, which dedicates a channel to a conversation for the entire duration of the call.

FIG. 2 shows a preferred embodiment of the digital representation of a burst. Burst 120 begins with a four-byte header, indicated as B.sub.1, B.sub.2, B.sub.3, and B.sub.4 in the drawing. In this burst-switching embodiment and for all purposes herein, a byte is eight bits, although this assumption is not critical to the invention. In other embodiments, a byte may comprise one bit, or four bits, or any predetermined number of bits. The choice of eight bits in this embodiment has been made because of the eight-bit capacity of a T-carrier channel and also because a printable character is typically represented by an eight-bit code, e.g., an ASCII code. With the definition of a byte being eight bits, the term "character" herein may be used interchangeably with byte.

In burst 120, the header contains the network address of the burst's destination. As a burst enters a switch, the header is interpreted so as to choose the appropriate link (or port) from the switch leading toward the destination port. The header contains information describing the burst as a voice, data, or control burst. As will be explained in greater detail below, control bursts are messages exchanged between switch processors. The header information is used to queue bursts for output at the desired priority and for other administrative purposes.

The fourth byte of the header is a header checksum which prevents delivery of a burst to a wrong destination. It is deemed better to abort the burst and rely on retransmission in the case of data than to deliver the burst incorrectly. No attempt is made to retransmit voice bursts. A voice burst's lifetime is so transient that there is only one chance to deliver it correctly. If that chance fails, the burst is too old to be useful.

Following the header, burst 120 has an information portion comprising N (any integral number) of bytes. Burst 100 ends with a single burst termination byte, labelled as T in the drawing. Alternatively, more than a single termination byte may be employed as will be explained below. The burst terminator may also be called FLAG herein. Thus, there are five overhead characters for each burst: the four header characters plus the terminator.

When FLAG is received, the receiver knows the burst has been completed. Bursts can be of any length, up to continuous transmission. FLAG may also used as the channel idle character, so that FLAGs will be sent in an idle channel until the next burst begins.

The bit combination chosen for FLAG may arise among the characters to be sent in the burst. There must be no restrictions in the character set available to the data sources. It must be possible to send any combination of binary data.

A data-link escape or DLE character is used to distinguish between the FLAG character as terminator and the FLAG character bit combination as ordinary data. At the source, each FLAG or DLE arising in the data to be sent is preceded by an extra DLE. At the destination, a received DLE is discarded, and the character following the DLE is received without examination for FLAG or DLE, thereby returning the character stream to that of the source. A received FLAG not preceded by DLE is interpreted as a burst terminator.

Each inserted DLE delays the actual data. FLAG and DLE should be chosen such that they occur infrequently in the voice samples or data to be sent, so as to introduce DLE-insertion delay as infrequently as possible. As voice traffic is expected to dominate data in volume through the end of the century, preferred values chosen for these characters are the codec (voice a/d and d/a) outputs representing the maximum positive and negative amplitudes of the analog voice signal. An alternate choice would be the minimum positive and negative values. This choice has particular merit where the minimum values are (in absolute value) below the minimum background noise thresholds. In any event, bit configurations which represent printable characters should not be chosen, since printable characters likely will occur in high frequencies in data and text transmissions.

In FIG. 1, communications links 106 between switches are T1 spans, although other rates could be used, for example, T2 or higher. Bursts are sent between switches in time-division multiplexed channels of the span, with succeeding characters of the burst being transmitted in succeeding frames of the span. The character rate within the channel for a T1-carrier is 8000 characters/second, which matches the codec character generation rate. In burst switching, the voice character transmission rate over communication links is matched to the character rate for the speech character sources and receivers. Therefore, no speed buffering is required at a link switch for voice bursts although, as will be explained, buffering is present in the event of contention. Burst output can begin from a link switch as soon as header routing has been done, so the delay through a link switch can be as little as two channel times, e.g., ten microseconds.

The use of T-carrier channels is an important difference between burst switching and voice packet switching. In packet switching, a packet is transmitted between nodes using the full bandwidth of the link, transmitting the characters of the packet contiguously. A packet's characters will be accumulated at the source (codec) rate, and then transmitted at a higher rate. This implies that the packet's characters must be buffered before the higher rate transmission begins. Since the time of accumulation introduces a delay, the size of the voice packet is strictly limited; otherwise, echo becomes a serious problem. A short packet means that the header overhead becomes significant. For example, suppose that a voice packet is limited to eight samples, or one millisecond's worth of data at 8000 characters/second generation rate. If the header overhead is five characters per packet, thirteen characters must be transmitted to route eight voice samples to the destination, resulting in a bandwidth efficiency of 8/13 or 62%. If only three header characters are required, the voice-packet bandwidth efficiency would be 8/11, or 73%.

By contrast, because the speech transmission rate equals the generation rate in burst switching, there is no need to buffer a speech burst before transmission begins. Transmission can begin a character time or so after burst reception begins, and the burst then continues for any period. Header transmission is required only once per burst.

The average length of a talkspurt depends on the silence detection algorithm used, but generally exceeds 100 milliseconds. The bandwidth efficiency of burst switching for a 100 millisecond burst is 800/805, which exceeds 99%.

Higher calling rates are expected in the future than those prevailing today. Experience has shown that people continue to use their telephones more and for more diversified applications. An example is the increasing transmission of data communications which was virtually nonexistent a decade or two ago.

Another significant example is that of transaction terminals, e.g., credit card verification terminals, which place calls automatically and hold for only the period of a database access. It is not now possible to determine how important this expected increase in call placement rate will be. Nonetheless, an objective of burst switching is to determine an architecture of the switch control elements which can grow gracefully to meet increased calling rates, and which does not exhibit the complexity of multiprocessor central processors.

The traditional approach for common control is to situate the decision-making element (the common control) at the center of the switch, to pull in stimuli from the periphery (signaling and supervision from subscribers), and to issue commands for connections to the switch and to the periphery (for example, for ringing).

A more recent control architecture is to move some processing capability toward the network periphery, in the form of slave processors, particularly in remote switching units. These slave processors can do some lower level preliminary processing, but the final decision making has typically remained at the central control point.

The burst switching approach expands this distributed trend to its limit. The call establishment and feature implementation logic is located in programmable processors associated with the ports in the link or hub switches. As the number of ports in a burst network increases, so will the number of control processors increase, and in a very natural way. Increased processing capability may be provided by adding a processor at an idle port without the complexity and down time entailed by adding a processor to a multiprocessor bus. In a burst-switching system, the number of bursts that can be propagated simultaneously is limited only by the number of port processors and the number of channels in the system. A port processor is a processor component of a port circuit which will be explained in greater detail below.

Messages are exchanged between control processors. For example, message exchange between the calling party processor and the called party processor is required to set up an ordinary call. This message traffic is carried as bursts in the ordinary way and thus adds to the total traffic carried by the network, although the message traffic is not significant. A three minute call between two parties, each issuing voice energy 35% of the time, will generate over one million voice samples; the control message exchange required to set up and release the call will require less than 100 characters, only 0.01% of the load.

External message exchange is not necessarily required. A port-to-port call on one link switch can be established entirely within the link switch, requiring no external control message traffic. The dispersed processors in the link switches also permit continued operation within a burst network region, even if outage prevents the region from communicating with the rest of the network.

Although the decision-making control has been moved to the periphery in burst switching systems, some semi-centralized service processor functions remain. In particular, the translation between directory number and equipment number (dialed number to burst-switch address) is performed by a few database lookup machines distributed throughout the burst network. Another similar network function is the recording of usage information for billing at the conclusion of a call. As will be discussed below, these administrative processes may be implemented in call processors and/or administrative processors. Either of these control processors may be coupled with an idle port of the system.

The advantages seen for distributed control are: processor overload is eliminated as a concern; processing capacity is added naturally and easily as ports are added; and no processor failure, central or otherwise, can bring the burst switching network down.

FIG. 3 shows a block diagram of a preferred embodiment of link switch 132. Link switch 132 is coupled between link switches 130 and 134 of system 100 as shown in FIG. 1. In such an arrangement, link switch 132 processes four types of bursts in transit as follows: link-to-link or through traffic, i.e., bursts passing through link switch 132 from an incoming link to an outgoing link; link-to-port or terminating traffic, i.e., bursts arriving on an incoming link and terminating at a port local to link switch 132; port-to-link or originating traffic, i.e., bursts originating at a port local to link switch 132 and leaving on an outgoing link; and port-to-port or intra-link switch traffic, i.e., bursts originating and terminating at ports local to link switch 132. The dashed arrows in FIG. 3A illustrate the four transit types of bursts passing through a link switch. These four transit types are also described in FIG. 10.

In FIG. 3, link switch 132 includes central memory 160 which is coupled with six high-speed processors as follows: link input processor (LIP) 161, which handles communications incoming from link switch 130; link output processor (LOP) 162, which handles communications outgoing to link switch 130; LIP 164, which handles communications incoming from link switch 134; LOP 166, which handles communications outgoing to link switch 134; port input processor (PIP) 168, which handles communications incoming from the twenty-four port circuits 178; and port output processor (POP) 170, which handles communications outgoing to the twenty-four port circuits 178. Each of these processors is a high-speed specialized switching processor adapted to handle characters and buffers. As will be explained in detail below, the same high-speed processor with slightly different software or firmware may be adapted to meet the six link-switch processor functions. Central memory 160, having high-speed direct-access memory, is coupled with memory arbiter 172 so that only one processor of link switch 132 may obtain access at one time. Memory 160 is the only means of communication between the various processors.

The term "port" does not include port circuit 178. Port circuit 178 physically may be located adjacent to link switch 132 or it may be located remotely, such as on the user premises or within the end-user instrument. Port circuit 178 may be a line circuit, when link switch 132 is coupled with a end-user instrument; or it may be a trunk circuit, when link switch 132 is coupled with another communications system. A port circuit of link switch 132 may also be coupled with a call processor or administrative processor for control purposes, e.g., call set-up. Thus, a port of a link switch, as used herein, describes means within the link switch for coupling with an external circuit or device, but the external circuit or device is not part of the port.

Most of memory 160 is divided into dynamic buffers, which may be assigned to active channels on communication links or ports. Characters are stored on input in a dynamic buffer assigned for the burst to the input channel, and characters for output are read from the buffer assigned to the output channel.

The dynamic buffers are employed as ring or circular buffers, so that the last storage location in a buffer is considered the predecessor of the first. Concurrent input and output can occur, with a character being read for output only a few character times after it has been stored as input. Only a few characters will be in the buffer of a burst which is being outputted at the same rate it is being inputted. The buffer storage locations will be used in round-robin fashion, with the output "chasing" the input and a few characters behind.

Although the normal case is concurrent input and output with only a few characters in a buffer, the dynamic buffering technique readily supports chaining buffers together when more than the storage space of a single buffer is required. A chain of buffers is formed when each buffer holds the address of the next buffer in the chain. This chain structure would be used, for example, when a data burst is temporarily blocked from output because of contention, and the burst's characters are buffered in a chain of one or more buffers until output can begin.

Bursts ready for output are placed on a queue associated with the appropriate output communications link or port. The queues are maintained in memory 160. A queue entry includes two pieces of data: the address of the first buffer of the first burst on the queue, and the address of the first buffer of the last burst on the queue. The queue contains references to bursts awaiting assignment to an available output channel.

There are three queues associated with each output link: high, normal, and low priority. Control bursts are queued on the high priority queue, because it is desirable to expedite control bursts through the switch network and because they typically consist of only ten or twenty bytes, thus occupying channels briefly. Voice bursts are handled at normal priority, and data bursts at low priority. Voice is given preference over data because voice samples, if much delayed, become useless. Data bursts can be buffered and delayed and still remain within acceptable performance limits.

In output link channel processing, whenever an idle channel is encountered, the link queues are examined. If there is a burst on at least one of the queues, the highest priority burst is removed from its queue, assigned to the channel, and the first character (or byte) of the burst transmitted. Consider the case of a burst placed on an output link queue when it is the only burst queued on the link. The first idle channel occurring after the burst has been queued will assume its transmission, thus minimizing interchannel delay. Generally, the transmission channel will differ from the channel of reception.

The six processors of link switch 132 compete for access to memory 160. When a processor is placing a burst on a queue, for example, more than one memory access may be required without interruption before the memory can be made available for use by another processor. Otherwise, the queue reference to the burst may be incomplete. Since all communications passing through link switch 132 must pass through memory 160, the speed of link switch 132 depends on the speed of memory 160. For these reasons, memory 160 is under control of memory arbiter 172.

Memory arbitration means are known in the art. FIG. 3B shows a prior art parallel priority-resolving circuit 450, taken from Y. Pakir, Multi-Microprocessor Systems, page 91, published by Academic Press, 1983, which would be suitable with appropriate modification for arbiter 172 of FIG. 3. When requests for memory access are pending from several processors, the highest priority request is serviced first by circuit 450. Priority may be determined by category and time of request such that requests within higher-ranked categories are serviced first and requests within the same category are serviced on a first-come first-serve basis. If only one request is pending, it is serviced immediately. See also The Handbook of Computers and Computing, edited by Arthur H. Seidman and Ivan Flores, pp. 227-232, and further references cited on p. 232, published by Van Nostrand Reinhold Company Inc., 1984.

Memory 160 includes a timing control, to generate read and write pulses, and random access memory. The buffer address and character index (which are sent via a character memory bus by a switching processor) are concatenated to form the address of a unique character.

A burst progresses through a link switch, from input link to output link, in the following steps:

1. Incoming communications:

(a) The first byte of a burst is received from an unassigned link input channel; the byte is stored in a buffer in memory.

(b) If the first byte contains sufficient information for routing, the buffer is placed on the appropriate link output queue.

(c) The second byte is received and stored. If the burst has not been routed on the first byte and the second byte contains sufficient information for routing, the buffer is placed on the appropriate link output queue.

(d) The third byte is received and stored. If the burst has not been routed as yet, it is destined for a port on the same link switch. The third byte identifies the local port.

(e) The fourth byte is received and stored, and the header checksum calculated.

(f) If the checksum is bad, receipt of the burst is aborted, and subsequent bytes before the end-of-burst FLAG are discarded.

(g) If the checksum is good, received bytes are stored in the buffer until the end-of-burst FLAG has been received.

2. Channel Congestion:

(a) Channel congestion occurs when there are more bursts on a link's output queues than there are idle channels on the output link. The system should be engineered so that channel congestion is an infrequent occurrence.

(b) While a burst awaits assignment to an idle output channel, input continues to the buffer.

(c) Voice: If two milliseconds' worth of voice samples have been accumulated and output has not begun, some or all of the accumulated characters are discarded. This is called clipping. The threshold value is variable.

(d) Data: If the buffer accumulating data characters fills, another buffer is acquired and linked to the first buffer. Data is not discarded as a result of channel congestion, although its transmission may be delayed.

3. Outgoing Communications:

(a) When an idle link output channel occurs, the output processor will remove the first burst from the highest priority nonempty queue, and output the first byte of the burst.

(b) Thereafter in each successive channel time, the next (successive) byte of the burst is outputted in the same output channel. Input and output proceed concurrently.

(c) When the ending FLAG is taken from the buffer, it is sent in the channel, the buffer returned to the free list, and the channel returned to idle. The channel is now available for transmission of another burst.

The hub switch is a high-speed high-capacity burst switch used at points of high concentration in a burst switching network. The primary function of the hub switch is to transmit communications between link groups. FIG. 4 shows hub switch 102 of system 100 having means for coupling with link groups A, B, C, and D. Four switching units, each shown as SU in the drawing, are connected in a ring about two hubs, 180 and 182. Hub 180 carries a parallel transmission of at least one byte in one direction, and hub 182 has the same parallel capacity in the opposite direction.

In the embodiment of FIG. 4, each hub switching unit is coupled with two link groups. SU 184 is coupled with link switch 192 of link group A via communications link 188. SU 184 also is coupled with link switch 190 of link group B via communications link 186. The advantage of this configuration is that each link group of system 100 is coupled with two switching units. In the event a switching unit should fail, the link group will not be isolated because of the alternate communications route through the other switching unit.

FIG. 5 shows a block diagram of SU 184 of hub switch 102. As shown in FIG. 4, SU 184 is coupled with link switch 192 of link group A and link switch 190 of link group B. In FIG. 5, communications link 188 is shown as input line 198 (to hub switch 102) and output line 200, and communications link 186 is shown as input line 194 and output line 196.

The architecture of SU 184 is somewhat analogous to that of link switch 132. Central memory 202 is coupled in this embodiment with eight high-speed processors as follows: link input processor (LIP) 204, which handles communications incoming from link switch 190; link output processor (LOP) 206, which handles communications outgoing to link switch 190; LIP 208, which handles communications incoming from link switch 192; LOP 210, which handles communications outgoing to link switch 192; hub input processor (HIP) 212, which handles communications from hub switching element (HSE) 220 incoming to memory 202; hub output processor (HOP) 214, which handles communications outgoing from memory 202 to HSE 220; HIP 216, which handles communications from HSE 222 incoming to memory 202; and HOP 218, which handles communications outgoing from memory 202 to HSE 222. The primary function of the hub switching element is to place communications on and off the hub. As shown in FIG. 5, HSE 220 provides service to hub 182 which transmits in one direction, and HSE 222 provides service to hub 180 which transmits in the opposite direction. Memory 202 is coupled with memory arbiter 224 so that only one processor may obtain access at any particular time. In FIG. 5, the architecture of SU 184 to the right of dashed line AA resembles closely that of a link switch, i.e., a central memory coupled with various special-purpose high-speed processors. The HIP, HOP, and HSE are each the same processor as LIP and LOP with firmware or software modifications.

For example, 256 switching units may be coupled to form a hub ring in the arrangement shown in FIG. 4. In an alternate embodiment, an even larger number of switching units may be coupled in the hub ring. There may be two or more hub rings in a hub switch, e.g., hubs 180 and 182, for redundancy and to double the number of available transfer channels within the hub switch.

Referring to the embodiment of the hub switch shown in FIG. 5, hubs 180 and 182 are time-division multiplexed. There are 32 channels on the hub during each T1 frame time. Each hub channel is divided into 256 clock ticks. Each clock tick advances a word on the hub ring from one SU to the next SU. Within a hub channel (256 ticks), each SU can send a hub word to any other SU since there are 256 switching units on the hub ring. Thus, in each hub channel, 256 origin SU's can send 256 hub words to 256 destination SU's. A hub word is the full (parallel) complement of bits that can be transferred simultaneously on the hub.

Assuming the hub is one byte wide, the hub ring clock rate is (8000 frames/second).times.(32 channels/frame).times.(256 ticks/channel)=65,536,000 ticks/second. A four-byte-wide hub would require one-fourth this rate, or 16,384,000 ticks/second. Whatever the width of the hub, there is one additional control bit, called the "busy" bit.

Each hub signal line has but one load, that of the corresponding bit in the successor HSE. Higher rates can be sustained in this configuration than would be possible in a high fan-out bus structure.

As shown in FIG. 4, each SU typically has two T1 links leading to remote link switches. A hub switch with 256 SU's has the following transfer capacity: (256 SU's).times.(2 T1 links/SU).times.(24 T1 channels/link).times.(8000 bytes/second/channel)=98,304,000 bytes/second. As was shown above, a hub ring having a width of one byte (so that a byte is advanced on the hub each clock tick), has capacity of 65,536,000 ticks/second or an equivalent number of bytes/second. Therefore, two hub rings are required to support the example of a hub switch having 256 switching units.

Hub switch 184 shown in FIG. 5 is a preferred embodiment, but alternate embodiments are possible and may be desirable to meet special requirements of a communications system.

As will be explained below, in order to send a burst from an origin HSE to a destination HSE requires that a hub channel be chosen in which the origin HSE is transmit idle and the destination HSE is receive idle. Thereafter, the remainder of the burst is sent in that channel. A burst's progress through a hub switch is similar to a burst's progress through a link switch.

1. At the origin HSE:

(a) The burst begins to arrive from an input link.

(b) The burst's characters are buffered in the central memory of the switching unit. The address of the destination HSE is determined from the header of the burst.

(c) The burst is queued for transmission on one hub or the other.

(d) An idle channel is chosen on the hub.

(e) Successive bytes of the burst are transmitted on the hub in successive occurrences of the selected hub channel.

2. At each intermediary HSE:

(a) The bytes of the burst are transferred along the hub through the HSE directly without passing through the central memory of the switching unit.

3. At the destination HSE:

(a) The bytes of the burst are taken off the hub by the HSE and stored in the central memory of the switching unit as the bytes arrive.

(b) The header bytes are interpreted to determine the appropriate output link.

(e) The burst is queued on the appropriate output link.

(f) Output commences in the first idle output link channel.

In preferred burst-switching network configurations, each link switch has at least two communications links leading toward any other link switch. Either link may be used if the route lengths are similar; the alternate link provides a route in the case of outage. An autonomcus control processor coupled with a link switch will permit continuance of service among all link switches which can communicate.

The hub switch preferably comprises two load-sharing hub rings, either of which could be used to propagate a burst. In the case of hub ring failure, the other hub ring can be used for any burst. As was shown above, a single hub ring may not have sufficient capacity to handle peak traffic. Very large scale integration (VLSI) versions of the HSE's are expected to be small enough so that an entire hub ring will fit on a card. In this case, the hub switch may comprise two sets of two-hub rings; one ring of each set may be active at all times and the second ring of each set may be backup capacity.

Another alternative is to construct a burst-switch network with more than one hub switch, so complete failure of a hub switch (requiring two or more simultaneous failures in the hub switch) would inhibit communications in only part of the network. This alternative is attractive in applications requiring a high degree of survivability such as in military applications where communications outages can result because of hostile action as well as random circuit failure.

Dispersal of link switches makes repair more difficult than repair at a centralized switch. The burst-switching network should have substantial diagnostic capability so that failures may be identified and remedial action taken quickly.

A burst-switching network should have background tests and exercise routines which run automatically at other than peak-load times. For example, adjacent link switches may exchange test messages at regular intervals. A link switch which has not received an expected test message within a prescribed time will make a report via an alternate link switch to a service processor.

Since loops have no appearance at the central office, a link switch should also have the capability to execute loop and subscriber instrument tests, automatically or upon control from a manned maintenance position, and to return a report of the results.

In addition to the system structure shown in FIG. 1, there are any number of alternate embodiments of burst-switching systems. The following are examples of alternate system structures and embodiments. These examples are intended to be representative but not inclusive. A burst-switching system may comprise a single link switch providing service to a plurality of ports. A burst-switching system may comprise a plurality of link switches in a single link group. A burst-switching system may have a plurality of link groups coupled by a hub switch having a single hub, or the hub switch may have two or more hubs. A burst-switching system may comprise a plurality of link groups interconnected by a plurality of hub switches, each hub switch having one or more hubs. In these systems, each link switch provides service to one or more ports. A port may be coupled with a user end instrument via a line circuit, or it may be coupled with a trunk leading to another communications system via a trunk circuit, or a port may be coupled with a call processor or an administrative processor. As has been mentioned, burst switches are coupled by means of communications links in various configurations, examples being star, ring, tree configurations, and combinations thereof. Communications links may be full-duplex T-carrier spans.

In FIG. 1, suppose user X of link group A has made a connection with user Y of link group B. The connection might be called a "virtual" connection since it consists only of X's knowledge of Y's address, and conversely. No resources of system 100 are used except when a burst is in transit.

Assuming X and Y are coupled with voice or speech ports, the following summarizes the transit of a burst from X to Y through system 100.

1. When X's voice detector (located in the port circuit) senses voice, it causes a burst header to be issued to X's link switch. The header contains Y's address.

2. X's link switch determines from the header that the burst must be routed to the hub switch. X's link switch selects the first free channel in a communications link leading toward the hub switch and transmits the first byte of the burst in it.

3. Each link switch nearer the hub switch in turn executes the same procedure, interpreting the header address and transmitting the burst in the first free channel of a communications link leading toward the hub switch.

4. The hub switch determines from the burst header which link group contains port Y. The hub switch passes the burst through the hub to Y's link group.

5. Each link switch in Y's link group interprets the header address and forwards the burst in the first free channel of a communications link leading toward Y's link switch.

6. Upon receipt of the burst, Y's link switch discards the header, as it has served its purpose of directing the burst to Y. Y's link switch sends the information portion of the burst to Y.

7. After assigning the outbound channel, each link switch passes the burst through itself, byte by byte, receiving each byte in a channel of the inbound link and sending each byte in the channel it has assigned on the outbound link.

8. Each link switch, when it receives the termination byte of the burst, frees the outbound link channel previously assigned to the burst. This channel is now available for assignment to another burst.

Each link switch except the destination link switch makes its routing choice on the basis of the first header byte alone. The hub switch finds Y's link group number in the second byte. Y's link switch finds Y's port number in the third byte. Each link switch will delay the burst only a couple of character times as it passes the burst characters along. If the burst could be viewed as it passes from X to Y, one would see the burst strung over all the intermediary link switches, with each link switch holding a few characters of the burst.

Each link switch makes it own outbound link channel assignment. In general, the burst will arrive at a link switch in one inbound link channel and leave on a different outbound link channel. If a burst passes through N (any integral number) communications links between its origin and its destination, there will be N independent channel assignments.

If X and Y had been in the same link group, the burst would not have passed through the hub switch. If X and Y had been on the same link switch, the burst would not have passed through a communication link.

LINK SWITCH

Link switch 132 is shown in FIG. 1 with respect to its neighboring link switches, link switch 130 on the left and link switch 134 on the right. Every byte of a burst passing through link switch 132 passes through central memory 160, as shown in FIG. 3. The central memory is divided into buffers which can be dynamically assigned to a time-division multiplexed channel of a communications link or port. The central memory is the common and only communication path among the several switching processors. Simultaneous requests for memory access are arbitrated by memory arbiter 172.

The switching processors administer the movement of characters between central memory and link channels or port circuits. In the embodiment of FIG. 3, link switch 132 has six switching processors, each of which is basically the same processor. In different applications within the link switch, each processor executes a slightly different program. A control program for each processor is stored in read-only memory (ROM) within the respective processor. Each processor has local random-access memory (RAM), in which status and buffer address information is maintained for each link channel and port served by the processor.

The switching processors are special purpose processors adapted for high speed. LIP 161, for example, upon receipt of a character in a channel of link 140, performs all necessary steps for inputting that character within the channel time including the internal administrative steps required for buffer maintenance, channel assignments, etc. LIP 160 must be capable of repeating the same steps for a character of another burst arriving in the next channel. Similarly, LOP 162 must be capable of processing and outputting characters at the T1 rate. A T1 channel is 5.21 microseconds in duration.

In FIG. 3, PIP 168 and POP 170 use input port bus 174 and output port bus 176, respectively, to scan the port circuits in cyclic fashion, so that there is a time interval or "channel" associated with each port on each bus. Thus, the port processors' actions in processing port channels are similar to the input and output processors' actions in processing link channels. In the embodiment of FIG. 3, twenty-four port circuits are serially coupled on port buses 174 and 176. Each port circuit 178 performs those functions relating to an individual port, including: burst creation; silence/speech detection for voice ports; analog-to-digital and digital-to-analog conversion for voice ports; and the required BORSCHT functions, which are the standard functions associated with a line card in a traditional digital switching system.

FIG. 6 shows an alternate embodiment of link switch 132 which replaces the port buses, shown in FIG. 3, between PIP 168, POP 170, and port circuits 178 with digital multiplexer circuit 250. Multiplexer circuit 250 multiplexes between the twenty-four parallel digital lines 256 and T1 path 252 to PIP 168, and between T1 path 254 from POP 170 and the twenty-four parallel digital lines 256.

This embodiment of a link switch has a number of advantages over the embodiment of FIG. 3. The PIP and POP external interfaces are now the same T1 interfaces as those of the LIP and LOP, respectively. Port circuits 258 may now be located at the end-user instruments, e.g., telephones, providing digital-line interconnects to the link switch with the benefits of noise immunity and remote testability which digital transmission provides.

As has been mentioned, central memory 160 is partitioned into dynamic buffers. FIG. 7 shows an acceptable format for these buffers. Buffer 300 is associated with a burst in transit. For example, the burst may be incoming to the link switch in link channel 1 and outgoing in link channel 5. In the local memory of the input processor, buffer 300 will be associated with channel 1; and in the local memory of the output processor, buffer memory 300 will be associated with channel 5. Therefore, buffer 300 is associated with an input channel (or port) and an output channel (or port).

Buffer 300 contains a fixed number of words, e.g., five words, each word being one byte. It also has three parameters associated with it. The first parameter, NEXT, contains the address of the first buffer of the next burst on queue. If there is no next burst on queue, NEXT is set to a predetermined character, such as zero. The second parameter, CNT, is the number of written and unread characters in buffer 300. The third parameter, SUCC, is the address of the successor buffer of this burst. If there is no successor buffer, SUCC is set to a predetermined character, such as zero. The informational portion of buffer 300, INFO1, INFO2, . . . , INFON, (N=5 in this example), contains bytes of the burst in transit. Buffer 300 is shown as containing five informational bytes for ease of illustration. In a preferred embodiment, buffer 300 contains 32 informational bytes.

Normally, only one buffer is required for a burst, and the characters flow through the buffer from input to output. If a data burst is delayed because there are temporarily insufficient link channels, more than one buffer may be required to hold the burst's characters until an output channel can be assigned. In this case, buffers are chained together, with the SUCC field of each buffer holding the address of its successor buffer of the burst.

A queue is associated with an output communications link or port, and also associated with a burst-priority type. As shown in FIG. 8, each queue includes a queue header and the burst buffers on the queue. The queue header comprises two data elements: the address of the first buffer of the first burst on the queue, FRST, and the address of the first buffer of the last burst on the queue, LAST.

FIG. 8 shows queue 310 having three bursts on it: a first burst of two buffers with addresses A and B; a second burst of one buffer with address C; and a third burst of one buffer with address D. Queue header 312 comprises FRST, which contains the address of buffer A, and LAST, which contains the address of buffer D. The arrows in the drawing show the linkages between the various buffers and queue header.

The informational portions of the buffers are cyclic or ring buffers wherein the last information location in the buffer is treated as the predecessor of the first informational location. A buffer is used as the exchange medium between an input processor and an output processor. The input processor stores a byte of a burst into the buffer using the buffer address (the memory address of its first location) and an input offset from the first location, called PUTINDX. Concurrently, the output processor reads a character of the burst from the buffer using the buffer address and an output offset from the first location, called GETINDX. The offset designates or "points" to the location in the buffer into which the next character of the burst to be received will be stored or from which the next character of the burst will be transmitted.

Both processors use CNT, the count of written but unread characters in the buffer. CNT is used by the input processor to assure that it does not store a character in a full buffer, and it is used by the output processor to assure that it does not read a character from an empty buffer, "empty" meaning that all characters in the buffer have already been outputted.

FIGS. 9A and 9B show buffer 320 which, for purposes of illustration, has five INFO locations. In FIG. 9A, the input processor has stored the first three characters of a burst, "a," "b," and "c." The output processor has not yet begun to output the burst. In FIG. 9B, the output processor has outputted the first three characters of the burst, and the input processor has stored three additional characters, "d," "e," and "f." The respective positions of PUTINDX and GETINDX are shown in each drawing. The horizontal lines through "b" and "c" in FIG. 9B indicate that these characters have already been outputted although not erased.

FIG. 10 illustrates the flow of four bursts, labelled A, B, C, and D in the drawing, through link switch 330. Characters of bursts A and B are arriving in two preassigned channels of an inbound link, while characters of bursts C and D are arriving from two local ports. Each of the buffers, Buf1 through Buf4, has been assigned to one of the bursts, respectively.

Characters of burst A progress through link switch 330 as follows. When the channel in which burst A is arriving occurs, the LIP receives the next character of the burst from the channel and deposits it in Buf1. The address of Buf1 is available to the LIP in its local memory associated with burst A's input channel number.

When the channel in which burst A is being transmitted occurs, the LOP takes the next character from Buf1 and sends it in the assigned outbound link channel. The address of Buf1 is available to the LOP in its local memory associated with burst A's output channel number.

The characters of bursts B, C, and D are processed in similar fashion. These four bursts represent the four combinations within a link switch between links and ports. Burst A passes through link switch 330 from input link to output link; burst B, from input link to output port; burst C, from input port to output link; and burst D from input port to output port.

The continuous flow aspect of a burst through a link switch should be noted. The storing of individual characters in buffers has been described. Over a period of time, a stream of bytes, i.e., a burst, flows through a buffer with straightforward logic and high efficiency. The buffers are dynamically assigned to bursts in transit through the link switch. This is true even in the case where both the origin and destination ports are local to the same link switch, e.g., burst D.

In the following, a burst will be traced through a link switch from the time of arrival of the first byte or character until the last character has been sent. FIG. 11A shows the conditions in central memory 340 before the first character of the burst arrives. The buffer, labelled "BUF" in the drawing, which will be assigned to the burst is on the free list, F. The free list is a queue containing the addresses of those buffers available for assignment. Arrow 342 indicates that F points to BUF as being available for assignment.

FIG. 11B shows the conditions in central memory 340 after the first character has arrived. The LIP has removed BUF from F and stored BUF's address in the portion of its local memory associated with the input link channel. Arrow 346 indicates the association in the LIP's memory between the input link channel and BUF. The LIP has stored the character into BUF; determined from the burst's destination address in the first header character that the burst is to be forwarded via the output link; and placed the burst on an outbound link queue, Q. Q contains references to bursts awaiting assignment to a channel for output on a particular communications link. Arrow 344 indicates that Q points to BUF as ready for assignment to an open channel in the output link associated with Q.

FIG. 11C shows the conditions in central memory 340 after the output link channel has been assigned. The LOP has found a free output channel and examined Q to see if any bursts are ready for assignment to an available output channel. Further, the LOP has found the burst's buffer address in Q; removed the burst from Q; stored the buffer address in the portion of its local memory associated with the output channel; and read the burst's first character from BUF and transmitted it in the output channel. Arrow 348 indicates the association in the LOP's memory between BUF and the output channel. These LOP actions have been performed independently of the LIP, except that the two processors have communicated via central memory 340 and they may have contended for access to the central memory.

The conditions shown in FIG. 11C will prevail for most of the remainder of the burst. As the burst's input channel occurs, the LIP takes the next character of the burst and stores it into BUF. As the burst's output channel occurs, the LOP reads the next character from the buffer and outputs it. The LIP and LOP each know the buffer identity, because each processor has stored the buffer address in its local memory.

In the normal case, the LIP is one character ahead of the LOP so that BUF contains one character at any time. In the event there is a delay in the output channel assignment, the LIP will be more than one character ahead of the LOP, and there will be more than one character in the buffer during the burst except for the transmission of the last character.

FIG. 11D shows the conditions in central memory 340 after the LIP has detected the termination character at the end of the burst. The LIP has stored the termination character into BUF and dissociated BUF from the input channel in its local memory. The LIP is ready to begin receiving another burst in the same input channel which, if present, would be stored into a new buffer in central memory since the LOP may still be using the old buffer for outputting the first burst. The LOP continues to output the remaining character or characters in BUF independently of the LIP.

FIG. 11E shows the conditions in central memory 340 after the LOP has found the termination character in BUF. The LOP has read the termination sequence from BUF and transmitted it; and returned BUF to the free list.

To expand on the assignment of output channels to bursts in a situation where there is contention for output channels, the following example is provided. FIG. 12A shows link switch 360 coupled with link switch 362 via communications link 364 in which there are only two channels (so that the example will be short). Three users, A, B, and C, desire to send four bursts over link 364; two bursts originate from user A, and one burst each originates from users B and C. It is assumed that the bursts are in the same priority class.

FIG. 12B is a pictorial of link 364 from link switch 360 to link switch 362 in which the assignments of bursts to the two channels as a function of time are described. As indicated in the drawing, time increases toward the left so that the rightmost slot is earliest in time. Initially, both channels are idle, as indicated by "X" in both channel slots 366 and 368. At time a, link switch 360 receives the first byte of the first burst, A.sub.1, from user A. Link switch 360 transmits the first character of A.sub.1, in slot 370, which is the first idle output channel occurring after time a. Slot 370 represents Channel 1. Channel 2 continues to be idle, as shown in slot 372.

At time b, link switch 360 receives the first byte of a burst from user B. The first available output slot is Channel 2 in slot 374, and the first character of burst B is transmitted therein.

At time c, the first byte of a burst from user C has been received by link switch 360. Since both channels are assigned, burst C will be accumulated in a buffer or buffers of the central memory (the length of time depending on whether burst C is a voice or data burst) and placed on a waiting queue until a channel is available. The bar over A.sub.1 in slot 376 indicates the terminator character for burst A.sub.1. Therefore, Channel 1 will be free during the succeeding frame. The first character of burst C is transmitted in slot 378.

At time d, the first byte of a second burst, A.sub.2, has been received by link switch 360. Since both channels are occupied, A.sub.2 is accumulated and placed on a waiting queue. Burst B terminates in slot 380, and the first character of burst A.sub.2 is transmitted in slot 382.

In slot 384, burst C terminates. Since there are no unassigned bursts awaiting transmission, Channel 1 becomes idle in slot 386. Likewise, Channel 2 becomes idle in slot 390 after the termination of burst A.sub.2 in slot 388.

This example illustrates queuing of bursts during contention for output channels and that channel assignment is only for the duration of a burst. The example further illustrates that user A's first burst was assigned to Channel 1 and A's second burst was assigned to Channel 2.

Each link switch through which a burst passes forwards the burst toward its destination port on the basis of the destination port's equipment address contained in the burst's header. Referring to FIG. 1, assume a burst originates at port X of link group A and its destination is port Y of link group B. A port address has three components: link group; link switch within link group; and port number within link switch.

Each link switch has three priority queues associated with each of its communications links, one queue for each type of burst. There are three types of bursts: control, voice, and data. Control bursts have high priority. It is desirable that they propagate quickly through the system in order to maintain system responsiveness. Since control bursts are short, they will not occupy channels for long periods. Data bursts have low priority. Data bursts can accommodate delays better than voice bursts; consequently, this type of burst can be buffered effectively. Voice bursts have middle priority. Voice bursts have preference over data bursts because voice samples, if delayed substantially, have diminishing value.

FIG. 13 shows format 400, a preferred format of a burst. A burst comprises a sequence of eight-bit bytes or characters, having a four-byte header preceding a variable-length information portion followed by a termination character at the end of the burst. The first header word contains three fields: burst type, group, and destination link switch, labelled in the drawing as BT, G, and DLS, respectively. The burst type may be 0, 1, or 2, indicating that the burst is a control, voice, or data burst, respectively. The group bit may be 0 or 1. When G=1, the burst header is currently in a different link group than the link group of the destination port. Thus, the burst will be routed through the hub switch. When G=0, the burst header is currently located in the link group of the destination port. Note that the G bit is reset as the burst header passes through the hub switch into the destination link group. DLS ranges from 0 to 15 and indicates the number of the destination link switch within the destination link group.

The second header byte contains DLG, the destination link group number, which ranges from 0 to 255. The third byte of the header contains DP, the destination port number, which ranges from 0 to 31. The destination port number is within the destination link switch, which in turn is within the destination link group. The fourth header byte, HCS, contains the header check sequence. HCS ranges from 0 to 255 and provides means for corroborating error-free receipt of the first three words of the burst header.

Following the burst header is the information portion of the burst. The information portion has a variable number of bytes, meaning that the number of information bytes generally will be different in every burst. In control and data bursts, the last two bytes of the information portion may contain a burst check sequence, indicated as "(BCS)" in the drawing. The burst check sequence provides means by which the presence of errors in the received information portion of a burst may be detected. When an error is detected, the recipient may attempt to correct the error with error correction techniques or the recipient may request retransmission of the burst.

The termination character, TC, defines the end of a burst. As will be explained below, use of a data-link escape character in combination with the termination character will provide the system with means for distinguishing the termination character as a data character occurring in the middle of a burst and the termination character as a terminator occurring at the end of a burst. Termination characters are transmitted in idle channels to indicate the availability of these channels for assignments to bursts.

There are numerous alternate definitions of burst formats which may be appropriate for various system configurations. Format 400 has been described as an example. Assuming format 400 is employed in a burst-switching system, a link switch routes a particular burst in the following steps.

1. Upon receipt of the first header byte of a burst, the link switch examines the G bit. If the G bit is set, the link switch is not a member of the destination link group and the burst must be routed to the hub switch. The link switch places the burst on the appropriate priority queue of the communication link leading toward the hub switch. If the G bit is reset, the burst is in the destination link group and the DLS field of the first header byte must be examined to determine whether or not the link switch is itself the destination link switch. If the link switch is not the destination link switch, the burst is placed on the appropriate priority queue of the link leading toward the destination link switch. If the link switch is itself the destination link switch, the link switch holds the first header byte awaiting the remainder of the header and, in particular, the third header byte in which the destination port is specified.

2. Upon receipt of the second header byte of a burst by a link switch not in the destination link group (G bit set), the link switch passes the second header byte through on the assigned communications link toward the hub switch. Upon receipt of the second header byte by a link switch within the destination link group (G bit reset), the link switch determines whether or not it is the destination link switch. If the link switch is not the destination link switch, the link switch passes the second header byte through on the assigned link to the destination link switch. If the link switch is itself the destination link switch, the second header byte is held awaiting the third and fourth header bytes. The second header byte is used by the hub switch to route bursts between link groups. In the process of routing a burst into a destination link group, the hub switch resets the G bit in the first header byte so that link switches within the destination link group may determine the burst's status from the first header word of the burst. If there are more than one hub switch, the hub switch which passes the burst into the destination link group, i.e., the last hub switch through which the burst passes, resets the G bit.

3. Upon receipt of the third header byte of a burst, the action of the link switch again depends on whether or not the link switch is the destination link switch. If the link switch is not the destination link switch, the link switch passes through the third header byte on the assigned link toward the destination link switch. If the link switch is itself the destination link switch, the link switch determines the destination port from the DP field of the third header word.

4. Upon receipt of the fourth header byte of a burst, the link switch checks the header check sequence in the HCS field. If HCS is bad, indicating there is at least one error in the burst header, the link switch aborts transmission of the burst by sending the termination sequence in lieu the remainder of the burst. If HCS is good, the action of the link switch depends on whether or not the link switch is the destination link switch. If the link switch is not the destination link switch, the link switch passes through the fourth header byte on the assigned link to the destination link switch. If the link switch is itself the destination link switch, the link switch discards the entire burst header and places the burst on a queue to the destination port.

The last character of a burst is always a termination character. Whenever an output channel is idle, termination characters are transmitted in the channel. When a channel becomes idle after the transmission of a burst, there will be one or more termination characters following the burst in the channel. This adds a degree of safety in the event a termination character is sent at the conclusion of a burst, but the termination character is not received as such because of error.

The termination character has a unique character code. It must be possible to send any character stream through a link or hub switch, including streams in which the termination character code itself occurs. A method is required by which the termination character can be recognized as an end-of-burst when so intended or as a data character in a stream when so intended.

The method employed for distinguishing the termination character from a data character is derived from the escaping technique of Binary Synchronous Communications. It is similar to the bit-stuffing technique of HDLC (High-level Data Link Control) except that in this case, the method is a byte-stuffing technique. The byte that is stuffed or inserted is a second special character called data-link escape character. In the following, the termination character is designated by TRM; and the data-link escape character, by DLE.

At the source, whenever a TRM or DLE bit configuration arises in data to be sent, a DLE is inserted before the data character for transmission. Thus, the source transformations are:

TRM is replaced by DLE TRM;

DLE is replaced by DLE DLE;

X is replaced by X, if X does not equal TRM or DLE.

At the destination whenever DLE is received, it is discarded. The character received immediately following the discarded DLE is accepted without examination for control significance. Thus, the destination transformation is:

DLE Y is replaced by Y, Y is any character.

If a TRM is received without a prefixing DLE, the TRM interpreted as an end-of-burst character. FIG. 14 contains Table 410 summarizing the data link escape procedure.

Each inserted DLE delays the actual characters of the burst. Accordingly, the codes for TRM and DLE must be chosen such that they occur infrequently in the voice samples and data to be sent. Since voice is expected to dominate data in volume within the foreseeable future, meritorious choices for values of these characters are the codec (voice A/D and D/A) outputs representing the maximum positive and maximum negative amplitudes of the analog voice signal. As previously discussed, the minimum amplitudes may be alternate choices in appropriate circumstances.

As has been stated, every burst is terminated with one or more TRM characters. Suppose a burst is terminated by a single TRM character. Then, any character in a burst altered by noise into TRM, or any DLE TRM altered by noise into X TRM, would cause the switch to treat the burst as two distinct bursts. The latter part of the original burst, now erroneously treated as a second burst, would likely fail the header check sequence test, so that the "second" burst would not be delivered to its intended destination. Conversely, suppose a single TRM between two actual bursts should be altered by noise into a non-TRM character. The second burst, now erroneously treated as part of the first burst, will be erroneously delivered to the destination port of the first burst.

The probability of these errors can be reduced to any desired small value by requiring that a burst be terminated by a redundant sequence of TRM characters rather than by a single TRM. For example, the termination character sequence could comprise five TRM characters, with end-of-burst declared upon the reception of three TRM characters within any five-character sequence. In order for an end-of-burst error to occur in this case, three non-TRM characters would have to be changed to TRM characters, or three TRM characters would have to be changed to non-TRM characters. The probability of error has been reduced substantially over the case of a single-TRM character procedure.

There are any number of burst termination schemes that could be employed in a burst-switching system. The choice for any particular system will depend on system characteristics and design goals. The examples discussed herein are intended to illustrate the wide range of options available.

The link and hub switches described herein have autonomous "in-line" switching capability which by itself distinguishes them from their existing art counterparts. Each switch may be connected between communications links having T1 (or higher) capacity. With each incoming channel, each switch has the capability to make and implement an appropriate routing decision for the information contained within the channel. The routing decision is made autonomously by the switch without reliance on any outside source, e.g., a central control switch. Moreover, all of the processing relating to the routing decision is performed within the time allotted to the incoming channel. When the channel time has elapsed, the switch is ready to repeat the procedure for information contained in the succeeding channel, and so on. Thus, the switch processing is in large part synchronized with the channel and frame timing of the communications links. In some embodiments, the actual channel slot timing is employed as a "restart" signal or interrupt for commencement of the switching algorithm. As has been explained, the switching algorithm must be capable of (among other functions) originating, continuing, and terminating burst transmissions which are in transit through the switch.

Burst switching fully integrates voice and data bursts. Generally speaking, only one character's worth of buffering is required in burst switching, because the voice transmission rates are matched with the T1 rate. Burst switches move every burst through a dynamic buffer; in the event of temporary channel contention, information (especially data) will not be lost.

The delay through a burst switch is an important performance parameter for voice transmission. Too much delay will make echo intolerable. In burst switching, the characters of a burst generally pass through a switch with a delay of less than four channel times. No speed buffering is required and, consequently, neither echo suppressors nor echo cancelers are required.

Different bursts on the same call may have different channel-exchange delays through the switching nodes. However, all characters within a speech burst experience the same delay. The magnitude of the variable delay component between talkspurts is less than the average silence period between talkspurts. Therefore, the variable delay between talkspurts is virtually unnoticeable.

A burst may be of any length, and a single header suffices for every burst. A typical talkspurt averages about 250 milliseconds, or 2000 pulse-code modulation characters. Assuming a burst header of four bytes and a one-byte terminator, the overhead for each burst is five bytes. The burst header overhead for the average talkspurt expressed as a percentage is 5/2000 or less than one percent. If a five-byte terminator sequence is employed instead of a one-byte terminator, the burst header overhead is still less than one percent.

A burst switch easily handles data transmissions at rates less than 64 kilobits per second (kb/s). When data is received from a user at less than 64 kb/s, a conveniently sized block of such data is accumulated in the port processor. This block is then transmitted through the system as a burst at the 64 kb/s rate. The same method would apply where the burst-switching channel rate is other than 64 kb/s.

It is expected that the switching services of the future will require a wide variety of bit rates, from low-speed data terminals of, say, 1200 bits/second, through digitally encoded voice of 16 to 64 kilobits/second, to high-speed data devices and digitally encoded video. The term "bandwidth efficiency" is often used to denote the ease with which a switch handles a variety of transmission rates. Because a burst has message structure as well as channelized operation, transmission rates higher than the channel rate can be handled with relative ease by employing a number of channels together for the transmission of a single burst. In a burst-switching system having a 64 kb/s channel rate, an N.times.64 kb/s burst would be treated as N separate (but related) bursts each at the 64 kb/s rate, where N is an integer greater than one. The N related bursts may be transmitted to the burst's destination in separate channels and then reassembled into the original N.times.64 kb/s burst. The message structure of burst switching permits reassembly of related bursts in proper order even though the N related bursts may not arrive at the destination in phase synchronization.

Future switching services are expected to require greater digital data handling capacity. Burst-switching systems may operate in a link-switch level error checking and retransmission mode for data bursts. Each data burst is fully buffered at each switch. The error-check test for a burst must be passed before the burst is retransmitted to the next switch along the route. Another error-checking mode is end-to-end error checking. In this mode, error checking of a data burst is performed only by the destination link switch. If the error check fails, the destination link switch requests retransmission of the data burst by the origin link switch.

The notion of end-to-end error checking is extended to the ultimate when the error checking is performed in the port processors and the port processors are located on user premises or within end-user instruments. The end-to-end digital-transmission capability possible with this architecture yields other advantages, such as improved diagnostic capability and enhanced security and privacy of voice and data communications. In the latter case, encryption and decryption of digital communications can also be performed in the port processors.

HUB SWITCH

The hub switch 500 as illustrated in FIG. 15 is a high -speed, high-capacity TDM switch for transferring the bytes of a message burst received in any inbound link channel from any link group to an outbound link channel of the appropriate link group as determined by address information in the message burst. The hub switch 500 includes N switching units 501 connected in a ring. In order to provide the advantages of redundancy, two hub buses 502 and 503 may be provided to propagate signals around the ring in either direction. Each switching unit is connected to a link group by one or more TDM link communication links 504.

An origin switching unit which receives a byte of digitally encoded information on an incoming link channel places the byte on the ring. The byte is passed from switching unit to switching unit around the ring until it arrives at its destination switching unit as designated by address information contained in the message burst.

As illustrated by the diagram of FIG. 19, a burst consists of a header (HDR), the information or data being transferred (INFO), and a termination character sequence of termination characters (TCS). The header contains the address to which the burst is being sent along with other identifying information on the burst. The information portion of the burst is a continuous stream of bytes. The length of the burst varies. Usually for speech information the burst is between 100 and 300 milliseconds in length. The termination character sequence of termination characters (bytes) indicates the end of the burst. The sequence of termination characters is continuous within a channel while it remains idle.

Transfer of bytes of digitally encoded information around the hub ring takes place in C hub channels having the same frame period as the inbound and outbound TDM link channels. Each byte moving around the hub ring from an origin switching unit to a destination switching unit during a hub channel time slot must be transferred from switching unit to switching unit at a rate so as to propagate completely around the hub ring in a ring circulation period equal to the hub channel time slot. Movement of a byte from one switching unit to the next takes place during each tick of a central clock 505.

As illustrated by the diagram of FIG. 18, during each frame there are C channel time slots, and during each hub channel time slot there are N clock ticks. In the illustrative embodiment under discussion the frame time is 125 microseconds, the same as the T1 frame time of the link channel in the link communication links 504. The number of hub channels per frame, C is 32. C can not be less than the number of link channels (24 in a T1 system). The number of clock ticks in a frame is C.times.N. In the embodiment under discussion the number of switching units, N, is 256.

In order for communication to take place between the different link groups connected to the various switching units of the hub switch, the link switch of the origin link group must find an idle channel to its associated switching unit of the hub switch. This origin switching unit in the hub switch must then find an idle hub channel between itself and the destination switching unit of the hub switch. Finally, the destination switching unit must find an idle link channel to communicate to the destination link switch in its associated link group.

Since there may be congestion at the hub switch switching units such that an idle hub channel or outgoing link channel is not immediately available when needed, and since some channel slip between channels is inevitable, each switching unit must include buffer memory and processors to manage the memory. FIG. 16 illustrates a switching unit. The switching unit includes a first hub switch element 515 connected to the hub bus 502 for transferring bytes in one direction around the hub switch ring. A second hub switch element 517 is connected to the hub bus 503 for transferring bytes around the hub switch ring in the opposite direction. The switching unit also includes a memory 516 and processors for managing the information into, out of, and within the memory. The processors, which are designated with respect to the memory, include two link input processors (LIP) 521 and 526 between incoming link channels and the memory and link output processors (LOP) 522 and 527 between the memory and the outgoing link channels. A hub input processor (HIP) 523 and a hub output processor (HOP) 524 are between the hub switch element 515 and the memory 516. The processors associated with the second hub switch element 517 are a HIP 518 and a HOP 519.

A principal function of the processors is controlling the routing of bytes between the memory 516 and the hub channels, and between the memory 516 and the link channels. They also have other functions including the acquisition of channels and the assignment and deassignment of dynamic memory buffers within the memory 516 to hub and link channels. These and other functions such as sequencing and queuing are managed in essentially the same manner as similar functions are performed by the link switches described in detail previously. The functions of transferring bytes from the memory 516 to the hub ring 502 by way of the hub switch element 515 and transferring bytes off the hub ring 502 by way of the hub switch element 515 are controlled by the HOP 524 and HIP 523. The memory 516, HIP 523 and HOP 524 together with a LIP and a LOP in effect form a variety of link switch serving as an interface between the link group and the hub switch element 515. The processors associated with the second hub switch element 517 function in a corresponding manner in transferring bytes between the memory 516 and the hub ring 503.

In summary, a message burst passes through the hub switch from an incoming channel of one link group to an outgoing channel of another link group in the following manner. Bytes of the burst arriving at the origin hub switching unit 501 on an incoming link channel are buffered in the switching unit memory 516. The first bytes, or header, of the burst contain address information; one byte, specifically the second byte, designating the destination link group and therefore the destination switching unit. The received bytes are queued for transmission on the hub bus. A hub channel in which the origin switching unit is transmit idle and the destination switching unit is receive idle is selected. The bytes of the burst are loaded onto the selected hub channel, one byte during each hub channel frame. A byte is transferred directly between the hub switch elements of adjacent intervening switching units on each clock tick without passing through the memories 516. Upon arriving at the destination switching unit, each byte is stored in the memory. The header bytes are interpreted to determine the appropriate output link group, if more than one link group is associated with the destination switching unit. The bytes are queued on the appropriate outbound link, and output begins on the first idle outbound link channel.

Hub Channel Transfer-General

FIG. 17 is a block diagram illustrating the first hub switch element 515 of a switching unit 501. The hub switch element handles the transfer of bytes from the preceding hub switch element and to the succeeding hub switch element along the hub ring bus 502. Also, under control of the HOP and HIP the hub switch element loads bytes from the memory 516 to the ring when the switching unit is an origin, and unloads bytes from the ring into the memory 516 for transmission on an outbound link channel when the switching unit is a destination.

Each hub switch element includes a destination memory 540 which contains the switching unit destination address for each hub channel in which the hub switch element 515 is transmit active. In addition a transmit active memory 559 contains a bit for each hub channel indicating the transmit busy or idle states of each hub channel for the hub switch element. Each hub switch element also includes a destination counter 531 which at the start of each hub channel or ring circulation period is set to the hub switch element's address. On each clock tick (TCLK) the destination counter 531 is decremented. Also on each tick the byte circulating on the ring which is in the THIS-SU storage register 532 of the hub switch element is transferred on the hub bus 502 by a multiplexer 533 to the storage register of the next succeeding switching unit. At the same time the byte in the register of the preceding switching unit moves into the THIS-SU register 532 of the switching unit.

When the hub switch element 515 of the switching unit 501 is serving as an origin for a message burst, the byte to be transferred during a hub channel time slot is placed in the hub-in data register 535 by way of a hub-in data series register 539 at the start of the hub channel time slot by the HOP to await transfer onto the ring. At the same time, an activity bit indicating that the hub switch element needs a hub channel is placed in a need channel register 545. Also, the destination switching unit address is placed in the destination register 536 from the destination memory 540 at the start of the hub channel time slot or ring circulation period. Upon the clock tick that causes the contents of the destination counter 531 to be the same as the address in the destination register 536, a comparator 537 produces an output. This indication of a match is applied to a channel acquisition and data transfer section 538 which causes the multiplexer 533 to transfer the contents of the hub-in data register 535 rather than the contents of the THIS-SU register 532 onto the hub bus to the succeeding switching unit.

As stated above, each byte on the ring is transferred from one switching unit to the next succeeding switching unit on each tick during the hub channel time slot. On the last tick of the ring circulation period at the end of the hub channel time slot each byte on the ring is transferred to the THIS-SU register 532 of its destination switching unit. On the next tick starting a ring circulation period and hub channel, the byte stored in the THIS-SU register 532 is transferred to the hub-out data register 548 for placing in the memory 516 by the HIP and transmission on an outbound link channel by the LOP.

Hub Channel Acquisition-General

Movement of the bytes of a message burst during successive frames of a hub channel involves coordination between a HOP of the origin switching unit and a HIP of the destination switching unit. The HOP controls fetching a byte from the memory of the origin switching unit and placing it on the hub ring bus, and the HIP of the destination switching unit takes the byte from the hub ring bus and places it in its memory . The HOP can process only one byte movement and the associated functions during each hub channel or ring circulation period, and the HIP can process only one byte movement and the associated functions during each hub channel or ring circulation period. Thus, for each burst, a free hub channel must be found during which both the origin switching unit is transmit idle and the destination switching unit is receive idle.

The need for acquiring a hub channel is recognized by the origin switching unit when an incoming link channel becomes busy. Therefore, the finding of a free hub channel must be accomplished at the origin switching unit. The origin switching unit knows its transmit busy/idle status for each of the hub channels. In order to select a free channel, it must also have information on the receive busy/idle status for each of the hub channels for the destination switching unit.

In order to provide information on the receive busy/idle status of each switching unit during the ring circulation period of a hub channel on the hub ring bus 502, an activity line 541 is provided in the hub ring in parallel with the hub ring bus 502. A receive activity memory 543 stores a bit for each hub channel indicating whether the hub switch element 515 is receive busy or receive idle for that hub channel. At the beginning of each hub channel period the bit indicating the receive busy/idle status of the hub switch element for that hub channel is transferred to the THIS-SU register 532 of the succeeding switching unit. This activity bit is propagated around the ring from switching unit to switching unit during subsequent ticks. Thus, any switching unit can determine the hub channel receive busy/idle status for any other switching unit by examining the activity bit placed in its THIS-SU register 532 on the appropriate tick during the ring circulation period.

When an origin switching unit must find a free hub channel to a destination switching unit, the address of the destination switching unit is placed in the destination register 536 of the hub switch element and the first byte of the burst which is to be transmitted is transferred into the hub-in data unit register 535 at the start of the first hub channel in which the hub switch element of the origin switching unit is transmit idle. In addition the HOP sets the need channel register 545 to indicate the need for a hub channel for transmitting the byte in the hub-in data register 535.

On the clock tick when the contents of the destination counter 531 are the same as the contents of the destination register 536, the comparator 537 produces an output indicating that it is the appropriate point in the ring circulation period for loading the byte in the hub-in data register 535 onto the hub ring bus 502. The activity bit in the THIS-SU register 532 indicates the receive busy/idle status of the destination switching unit, and a bit in the transmit activity memory 559 indicates the transmit busy/idle status of the hub switch element of the origin switching unit. If these bits indicate that the destination switching unit is receive idle and the origin switching unit is transmit idle for this hub channel, a hub channel has been found for sending the burst from the origin switching unit to the destination switching unit.

The origin switching unit seizes this hub channel by setting the activity bit to busy as it is transmitted by the multiplexer 533 to the succeeding switching unit on line 541. At the same time the first byte of the burst is transferred from the hub-in data register 535 to the succeeding switching unit on line 502 by the multiplexer 533. In addition, the channel acquisition and transfer section 538 sets a channel seized register 546 to indicate to the HOP that a successful hub channel acquisition and data insertion on the hub ring bus have been made. The HOP stores the appropriate information in the memory 516 so that subsequent bytes of the burst will be transferred into the hub-in data registers 539 and 535 at the appropriate times for transmission to the destination switching unit on the acquired hub channel during successive frames. The indication that the acquired hub channel is now transmit busy is placed in the transmit activity memory 559 and the address of the destination switching unit for the hub channel is placed in the destination memory 540 to complete the hub channel acquisition procedure.

Since the activity bit being propagated on the activity line 541 is set to busy by the origin switching unit when seizing a hub channel, any downstream switching unit which may also be seeking an idle channel to the same destination switching unit will be aware that the destination switching unit is receive busy for the current hub channel. Thus no confusion arises out of substantially simultaneous requests for a hub channel by different switching units to the same destination.

At the tick terminating one hub channel and starting the next, the byte in the THIS-SU register 532 is transferred into the hub-out data register 548 and the activity bit is transferred into the receive activity memory 543. The receive activity bit placed in the receive activity memory 543 is propagated on the activity line 541 during the next frame of the same hub channel. The byte in the hub-out data register 548 is transferred to the hub-out data serie