Source: http://www.google.com/patents/US6522646?dq=7,339,580
Timestamp: 2016-12-08 04:18:05
Document Index: 202021682

Matched Legal Cases: ['art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138', 'art 138']

Patent US6522646 - Expandable telecommunications system - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsAn open, high speed, high bandwidth digital communication network for connecting multiple programmable telecommunications switches to form a large capacity, non-blocking switching system. Each network switching node includes circuitry for transmitting and receiving variable-length, packetized information...http://www.google.com/patents/US6522646?utm_source=gb-gplus-sharePatent US6522646 - Expandable telecommunications systemAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS6522646 B1Publication typeGrantApplication numberUS 09/343,949Publication dateFeb 18, 2003Filing dateJun 30, 1999Priority dateMar 8, 1994Fee statusLapsedAlso published asCA2184726A1, CA2184726C, CN1116752C, CN1147322A, CN1294727C, CN1509026A, CN1953427A, CN100576828C, DE69529155D1, DE69529155T2, EP0749653A1, EP0749653B1, US5544163, US5737320, US5864551, US6118779, WO1995024788A2, WO1995024788A3Publication number09343949, 343949, US 6522646 B1, US 6522646B1, US-B1-6522646, US6522646 B1, US6522646B1InventorsRobert P. MadonnaOriginal AssigneeExcel Switching Co.Export CitationBiBTeX, EndNote, RefManPatent Citations (37), Referenced by (7), Classifications (26), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetExpandable telecommunications system
US 6522646 B1Abstract
This application is a divisional of Ser. No. 09/137,496, filed Aug. 20, 1998, now U.S. Pat. No. 6,118,779, which is a divisional of Ser. No. 08/455,935, filed May 31, 1995, now U.S. Pat. No. 5,864,551, which is a divisional of Ser. No. 08/207,931, filed Mar. 8, 1994, now issued as U.S. Pat. No. 5,544,163.
One conventional approach may be referred to, for shorthand, as the “bus extension” approach. In many conventional telecommunications switches, one or more internal buses are provided for carrying information, including voice, data and control information, between various parts of the switch. Buses are well suited for carrying such information since, by definition, multiple devices (e.g., circuit boards or cards) may interface with the buses and share them in accordance with a defined communication protocol. In a telecommunications switch, it is typical to find one or more buses interconnecting a series of cards which physically terminate telephone lines or trunks with other cards which perform switching, control or other functions.
As the shorthand name suggests, the concept underlying the bus extension approach is simply to connect additional cards, which provide additional switching capacity or other functions, with the existing buses. In addition to the two major disadvantages noted above, there are several other disadvantages to this approach. First, there are physical limitations as to the number of cards that can be physically connected to or share the buses without degrading the system's performance. Second, in order to permit significant future expansion, the buses and other portions of the system must be constructed, in the first instance, to handle far greater traffic than is required prior to any expansion of the system. These limitations are related to the electrical and mechanical characteristics of the buses (or perhaps a particular one of the buses) and their effective operating speeds. Attempts to overcome these limitations (e.g., using an excessively large number of connections to the bus) tends to increase the cost and complexity of the “base” or unexpanded system, possibly rendering the system too costly for some applications. There is also a limitation related to the processing power required to actually performing the switching functions as well as control traffic on the buses.
A second approach may be referred to as the “modular” approach for shorthand. In the modular approach, the concept is to provide a switching system which is constructed from a series of essentially identical modules. Each module provides a finite amount of switching capacity which may be added to an existing system (one or more at a time) to increase the overall capacity of the system.
Again, in addition to the major disadvantages noted earlier, the modular approach has other deficiencies. In order to provide fully non-blocking operation, each and every module as built must have the capability to receive circuit switched data from every other module up to whatever the maximum number of modules may be. In terms of hardware, this means that each module must be built with a sufficiently large memory to hold the maximum amount of circuit switched data which could be received if the maximum number of modules are connected together. For example, if each module is capable of switching the equivalent of 64 ports and a maximum of eight modules may be connected together, then each module must necessarily contain a memory capable of holding circuit switched data for (8×64)=512 ports. Thus, in the modular approach, it is the maximum switching capacity of the fully expanded system which determines the size of the memory that each module must have. For larger systems (i.e., on the order of a few thousand ports or larger), constructing such a memory becomes impractical due to both the accompanying number of physical network/line interfaces as well as the additional circuitry needed to control the memory.
Second, in order to maintain a truly “modular” system, it is impossible to vary the switching capacity of individual modules.
In accordance with one method of transferring information between nodes, each node uses the network to transmit one or more packets, each of which has an “empty” payload, which are received first by an adjacent node. The adjacent node determines the source of the received packet and the packet's status by the information contained in the control portion of the packet. If that adjacent node has information to send to the node which transmitted the packet, the adjacent node inserts such information into the payload of the packet, then allows the packet to pass to the next adjacent node on the network. If the adjacent node has no information for the node that originated the packet, the packet simply passes to the next adjacent node on the network. This process is repeated at each node until the packet traverses the complete network and returns with a “full” payload to the node from which it originated. At that point, information which was inserted into the packet by other nodes is captured by the node which originated the packet. In turn, each node transmits an “empty” packet which traverses the network and returns with information from other nodes. In this fashion, information of any type originating from any port served by any node may be transferred to any other port of the same or different node in the system.
In accordance with an alternative method of transferring information between nodes, each node uses the network to transmit one or more packets, each of which has a “full” payload that contains information originating from that node. Each such packet is initially received by an adjacent node which determines the origin of the packet and whether any of the information contained therein is needed by that adjacent node. If so, such information is captured from the payload before the packet passes to the next adjacent node. If no information is needed, the packet simply passes to the next adjacent node. Again, this process is repeated until each node on the network has transmitted one or more packets with a “full” payload and each such packet has traversed the complete network, thereby allowing each node access to the information originated by each other node.
In yet another embodiment of the present invention, one or more nodes may be used to “bridge” one network to another. A bridge node is common to two networks and is capable of exchanging information bidirectionally between such networks. A bridge node may also be used to connect networks which operate at different speeds.
FIGS. 1A and 1B show a large capacity, expandable, fully programmable telecommunications switching system 2. The system 2 includes a host 4 and a series of programmable switching nodes 6 a-6 h. Each of nodes 6 a-6 h includes a host interface which is connected in communicating relationship with host 4 by a local area network (LAN) such as Ethernet or by multiple asynchronous communication (RS-232) links 8. It should be understood that other types of host/node interfaces may be used instead of or in addition to the LAN/RS-232 links 8. Although only a single host 4 is shown, use of LAN 8 to provide host/node communications permits multiple hosts to control the system 2 (or parts thereof) by configuring each host as a “client” and each node as a “server.” For purposes of improved clarity in this drawing, the host interfaces of nodes 6 a and 6 f-6 h are truncated.
Each of nodes 6 a-6 h includes digital network/line interfaces for connection with the public switched telephone network (PSTN) or a private network 10. The term “private network” is intended in a broad sense to refer to any network or line or other interface other than the PSTN. Again, for enhanced clarity, the network/line interfaces of nodes 6 b-6 e are truncated. As shown by representative node 6 g, the network/line interfaces may terminate either digital networks or analog trunks/lines, or combinations of both types. The network/line interfaces of a given node may include suitable interfaces for performing communications using ATM, Signaling System 7 (SS7), ISDN, T1/robbed bit, E1/CAS or other communication protocols.
Node 6 g is nominally designated “master node A” (active master node) and node 6 h is nominally designated “master node B” (standby master node for redundancy). A synchronization reference line (ref 1 . . . ref n) extends from active master node 6 g to each other switching node, although some such lines are truncated for clarity. As is explained in detail below in connection with FIGS. 3A through 3E, any of nodes 6 a-6 h may be configured as the active master node or the standby master node. However, at any given time, there may be one and only one active master node.
Using inter-nodal network 12, a port of any given node may be connected to any other port of the same node or any other node in a fully non-blocking manner. In this preferred embodiment, with a total of eight switching nodes 6 a-6 h interconnected by the inter-nodal network 12, if all of the bandwidth of the inter-nodal network 12 is used for transferring circuit switched data, the system 2 is capable of switching (8×2,048=) 16,384 ports, which equates to 8,192 simultaneous, two-way calls.
It should be understood that each of nodes 6 a-6 h operates independently with respect to the network/line interfaces terminated thereon. That is, any node may be removed or added to inter-nodal network 12 without impairing the operations or network/line interfaces of the other nodes. Further, the switching capacity of each switching node may be established independently from the switching capacities of other nodes (i.e., “small” switches may be combined with “large” switches on the same inter-nodal network 12). Thus, the overall switching capacity of the system 2 may be increased simply by adding additional switching nodes to the inter-nodal network 12, subject to certain limitation regarding the data transmission rate of that network, or additional inter-nodal networks 12 which are discussed below.
FIG. 1E shows preferred embodiments for several packets which may be used to transfer information over inter-nodal network 12. A circuit switched data packet 3 and a voice processing packet 5 are similarly constructed and each includes a control portion which contains a busy indicator (BI) followed by address and control information. The busy indicator may be used, as described in detail below, to denote the current status of a given packet as either “busy” (meaning the packet may not be used by a node to transfer information) or “free”.
The address information preferably includes an address for either the source (SRC) node from which the packet originates or the destination (DEST) node for which the packet is intended, or both. Each address (source or destination) preferably includes a “network address” which uniquely identifies a particular inter-nodal network. Such identification is necessary since, as described below, multiple inter-nodal networks may be used to connect the same or different groups of nodes. Each address (source or destination) preferably also includes a “nodal address” which uniquely identifies a particular node on a particular inter-nodal network. Additional address information may include an explicit “port address” for uniquely identifying a particular port or groups of ports.
In general, packets 3 and 5, which carry circuit switched data, require “port addresses” since such data is subject to distribution across multiple nodes and/or ports. As an alternative to explicit “port addresses” (which, in the context of a large switching system would represent thousands of bytes of additional information carried by the packet), implicit “port addresses” may be determined by maintaining a predetermined order of the circuit switched data within the payload. For example, packets 3 and 5 are depicted as having sufficient payload capacities to carry a total of 2,048 bytes of circuit switched data. When such bytes are placed in the payload, they are preferably arranged in an order which corresponds exactly with the sequence of time slots at a given node. Specifically, the byte of circuit switched data which corresponds to the “first” time slot (time slot (TS) 0) of a given node is placed first in the payload, followed by the remaining bytes in sequential order. By this arrangement, any given node may either load circuit switched data into or extract data from the payload and, by simply counting the position of a particular byte relative to the first byte in the payload, know exactly the time slot with which the byte corresponds.
In contrast, packets 7 and 9 do not generally require “port addresses” since the information carried by those types of packets is not circuit switched data.
A packet switched data packet 7 and a maintenance packet 9 are similarly constructed (their lengths or payload capacities are variable), except that these types of packet do not carry circuit switched data but, as described below, are intended to transfer packet switched data which originates from a single point (source) and is destined to be transferred to another single point (destination) or to multiple single points (“broadcast”). The status and control portions of packets 7 and 9 may include information which indicates whether a destination node for a given packet was able to accept the packet or was busy at the time of receipt and unable to accept the packet.
A ring (network) IO card 40 a serves as an interface between one pair of rings (designated Set A, Rings 1 and 2), which together are designated inter-nodal network 12 a, and a nodal switch 44 a that is designated the “local bus master,” the significance of which is described below. A first host interface 42 a handles all communication between host 4 and the node of FIG. 2A.
For convenience, throughout the remainder of this description, the term “local port” shall be used to refer, with respect to a given node, to a time slot containing circuit switched data transmitted from a line card 26 to all nodal switches 44, MFDSP cards 36 and ISDN-24 cards 38 (if any), or a time slot containing data transmitted from any nodal switch 44, MFDSP card 36 or ISDN-24 card 38 to a line card 26. The term “remote port” shall be used to refer, with respect to a given node, to a local port of a different node.
FIGS. 2B and 2C show a preferred embodiment of a second type of programmable switching node. This type of node is preferably based on an off-the-shelf PC which includes a PC-486 (or equivalent) and peripherals 48, an ISA (AT) bus 50 and a mass storage device 52. The PC-486 48 may be used to run a user's application software and effectively operate as a host 4. Alternatively, an optional host interface 42 a may be used to connect an “external” host (such as host 4 in FIGS. 1A through 1D) to control the node. In addition to components already identified in connection with the preceding figure, several additional components are provided in this embodiment. A voice processing resources bus interface 54 provides bidirectional communication between switching bus 30 a and two voice processing buses, PEB bus 60 and/or MVIP bus 62. PEB bus 60 and MVIP bus 62 represent well known, “standard” interfaces for communicating with commercially available, widely used voice processing resources 56 and 58, respectively. For example, Dialogic Corporation of New Jersey produces a family of voice processing resource boards or cards which plug directly into PEB bus 60 and may be used in diverse applications including voice mail, fax mail, interactive voice response and others.
Separate, but identical, circuitry is provided for interfacing with and transferring information to or from ring 2. Like reference numbers are used to identify corresponding components. As explained below in connection with FIGS. 6A and 6B, during periods of time when nodal switch 44 a operates in a “loopback” mode, the output of transmitter 84 b is effectively connected to the input of receiver 70 a, as indicated in phantom and reference number 71 a. Similarly, the input of receiver 70 b is effectively connected to the output of transmitter 84 a, as indicated by reference number 71 b. Nodal switch 44 a includes additional components for timing and synchronization functions, which are grouped together as master node options 65 and local bus master options 71. Master node options 65 include an inter-nodal synchronization circuit 67 and a master ring oscillator 69. Synchronization circuit 67 generates reference signals ref 1 . . . ref n, each of which is supplied to one other switching node (see FIGS. 1A through 1D). Synchronization circuit 67 also generates a nodal frame synchronization signal and a master ring clock signal, both of which are supplied to the packet control circuits 92 a and 92 b. Local bus master options 71 include a local bus HDLC control 73 and a local synchronization circuit 75. Local bus HDLC control 73 is connected in communicating relationship with CPU address and data buses 114 and 116, respectively, and generates a series of control signals 1 . . . n which are supplied to all other cards (i.e., other nodal switches, line cards, MFDSP cards and ISDN-24 cards) associated with a given node for controlling access to the HDLC bus.
Further details regarding the construction of receiver memory 108 and transmitter memory 102 are shown in FIGS. 3F and 3G. Transmitter memory 102 is organized into dual circuit switched data banks 122 and 126, and dual constant areas 124 and 128. Similarly, receiver memory 108 is organized into dual circuit switched data banks 130 and 134, and dual constant areas 132 and 136. The dual circuit switched data banks of each memory are operable, in conjunction with their respective maps and counters, to time switch circuit switched data. That is, during a given time slot, a byte of circuit is switched data is written sequentially into a memory location in one of the circuit switched data banks, while circuit switched data stored in the other circuit switched data bank is read “selectively.” The term “selectively” is used in this description to refer a process of applying addresses which are supplied by a map. During alternate 125 μs time periods, the roles of the circuit switched data banks reverse, thus interchanging the time slots to effect time switching.
Configuration Synchronization and Initialization
Before proceeding with an overview of the operation of nodal switch 44 a, it is helpful to understand how each switch may be configured to operate and what its responsibilities are in terms of system synchronization and initialization. With reference again to FIGS. 1A, 1B and 3A through 3E, it should be understood that each programmable switching node 6 a-6 h must contain at least one, but may contain more than one, nodal switch 44 a. It should also be understood that, in general, two types of synchronization must be considered: inter-nodal network synchronization and PSTN (or private network) synchronization.
Each nodal switch 44 a is preferably configurable, by software, to operate as (1) a combination master node and local bus master, (2) a local bus master only, or (3) neither a master node nor a local bus master, but simply a “standard” switch. The configuration rules are as follows. For each inter-nodal network 12, there must at any given time be one and only nodal switch which is operating as the master node. Whichever nodal switch is operating as the master node may also operate as the local bus master for its node. Within a given node, there must at any given time be one and only one nodal switch which is operating as the local bus master for that node. Lastly, within a given node, at any given time there may be one or more nodal switches operating as standard switches.
In order to make this “local” circuit switched data (stored in memory 102) available to every other node served by inter-nodal network 12, one of two methods may be used. In the first method, transmitter 66 and packet handling circuit 78 a (it is assumed that ring 1 is the ring assigned to this node for transmission of packets) formulate a packet whose payload is “empty” (meaning that the payload contains no circuit switched data, except for data from local ports which are connected to other local ports), but which has sufficient capacity to hold up to 2,048 bytes of circuit switched data. Transmitter 84 a then transmits the “empty” packet. If we assume, for example, that the “empty” packet is transmitted by node 6 c, then node 6 d will be the first node to receive that packet (i.e., the first adjacent node in the direction of flow around the ring is the first to receive the “empty” packet).
At either node 6b or 6 d, the “empty” packet is received by receiver 70 a and eventually passed to packet handling circuit 78 a. Packet handling circuit 78 a receives circuit switched data which is read selectively from circuit switched data banks 122 and 126 in response to addresses supplied by map (ring 1) 96. In other words, by virtue of the addresses and control it supplies, ring map 96 causes particular bytes (or possibly all of the bytes or none of the bytes) of “local” circuit switched data stored in banks 122 and 126 to be selectively read from those banks and passed to the packet handling circuit 78 a. A similar process occurs in parallel with map (ring 2) 98, memory 102 and packet handling circuit 78 b. Packet handling circuit 78 a inserts the “local” circuit switched data it receives (if any) into the payload of the received “empty” packet while that packet is passing to the transmitter 84 a for transmission to the next node on the inter-nodal network 12. This process is repeated such that each other node, in succession, has the opportunity to insert its own “local” circuit switched data in the payload of the packet which originated from node 6 c. If a particular node has no “local” circuit switched data to insert in the payload, the received packet passes unaltered to the next node. Eventually, the packet which was sent out “empty” traverses the entire ring on which it was transmitted and returns “full” to the node from which it was transmitted (originated). At that node (6 c), circuit switched data from the payload of the “full” packet is passed through ring select circuit 94, written sequentially into receiver memory 108 and then time switched out as LSDATA or SLDATA. This method is referred to as the “Empty Send/Full Return” or ESFR method for shorthand.
The ESFR method is repeated such that each node, in turn, transmits an “empty” packet and receives a “full” return packet (on the node's assigned ring), thereby enabling “local” circuit switched data originating from any port at any node to be effectively transferred to any other port of the same or different node. All circuit switched data is preferably transferred in less than 125 μs to avoid loss of samples. As explained below, it should also be understood that the ESFR method may be used to “broadcast” or transfer information originating from one port to more than one other ports.
In the second method, the concept is for each node, in turn, to originate (transmit) a packet whose payload is “full” when sent, but “empty” upon return. Thus, a shorthand name for this method is the “Full Send/Empty Return” or FSER method. In the FSER method, all of the “local” circuit switched data stored in circuit switched data banks 122 and 126 of transmitter memory 102 is read sequentially and supplied to packet handling circuit 78 a. A “full” packet is constructed whose payload includes all of the “local” circuit switched data for a given node. The “full” packet is transmitted by transmitter 84 a and is received by the first adjacent node. The data in the payload is selectively extracted and passed, via ring select circuit 94, to receiver 68. That data is then selectively written into data banks 130 and 134 of receiver memory 108. This process is repeated until a “full” packet transmitted by each node has been received by every other node, thus achieving the same overall result of enabling “local” circuit switched data originating from any port at any node to be effectively transferred to any other port of the same or different node.
Referring now to FIGS. 3A through 3E, 4A and 4B, further details of the ESFR method will be described. It should be understood that the flowchart of FIG. 4B represents the steps which are performed, in parallel, at each node by that node's packet control circuits (92 a and 92 b), the packet handling circuits 78 a and 78 b and related circuitry. It should be kept in mind that when the ESFR method is used, “empty” packets are transmitted on only one ring and received on only one ring (assigned during initialization). For this example, it is assumed that node 6 i in FIG. 4A is preparing to transmit an “empty” packet over the inter-nodal network 12 for the purpose of collecting circuit switched data from other nodes, including node 6 j. The process begins at start on reset step 138, which is a state in which the node is essentially waiting for a frame (which contains a packet) to arrive on the inter-nodal network work 12. At step 140, a determination is made whether the start of a frame has been detected. If a start of frame is not detected, the process returns to start 138. Alternatively, if the start of a frame is detected, meaning that a packet was received by node 6 i, then the contents of the control portion of the packet are checked to determine if the packet is “busy” at step 142. A packet's “busy” or not busy (“free”) status is indicated by the busy indicator (BI) in the control portion of the packet (FIG. 1E). If the packet is not busy, meaning it is “free” for node 6 i to use, the process proceeds to step 144 where a determination is made whether the circuit switched data (CSD) window for node 6 i is open. The “CSD window” refers to a designated period of time which is allocated for all of the to nodes to transmit “empty” circuit switched data packets.
If the CSD window is not open, meaning that it is not the appropriate time for node 6 i to transmit an “empty” packet for circuit switched data, then the process returns to start 138. If the CSD window is open, then the process advances to step 146 at which node 6 i starts the process of sending a packet by transmitting a “busy” control word over the network 12 to take control of the packet. Next, at step 150, node 6 i continues the process of sending an “empty” packet over the network 12. Note, however, that at step 148, node 6 i must insert “local connect data” (if any) into the payload of the “empty” packet while transmission continues. The term “local connect data” refers to circuit switched data which is both originating from and destined for one or more local ports of a given node which is sending an “empty” packet. In other words, local connect data is circuit switched data which is to be switched from one local port to another local port of the same node over inter-nodal network 12. Thus, in this example, if node 6 i has any local ports which are connected to each other, the circuit switched data pertaining to those ports would be inserted into the payload of the “empty” packet at step 148. In effect, node 6 i (or any other node) transmits local connect data to itself. Next, at step 152, the transmit flag (XF) 90 a (FIG. 3A) is set to serve as a reminder to node 6 i that it has transmitted an “empty” packet over the network 12 and that it should receive the return “full” packet in the future.
Next, the process returns to start 138 to await receipt of another frame. Once the start of another frame is detected and it is determined that the packet within the frame is “busy” (not free), the process advances to step 154 where a determination is made as to whether the transmit flag is set. If XF is not set, meaning that the packet which was just received originated from another node, then the process proceeds to step 162 where address information contained in the control portion of the packet is checked to determine the (nodal) source of the packet. Thus, in this example, when node 6 j actually receives the “empty” packet transmitted by node 6 i, the process would advance to step 162 because node 6 j's transmit flag would not be set. At this point, node 6 j must insert appropriate circuit switched data into the payload of the packet. In this example, the appropriate circuit switched data is data pertaining to any of node 6 j's local ports which already are (or are about to be) connected to any of node 6 i's local ports. As shown in FIG. 4A, this is accomplished by CPU 64 a in node 6 j writing address and control data into one of the address maps 96, 98 such that the appropriate circuit switched data is written selectively into the payload of the received packet at step 164. This step represents the beginning of a second stage of switching (node to node) performed by the system 17. Error status information is then placed in the status and control portion of the packet at step 165.
Next, under normal circumstances, the now “full” return packet is received by node 6 i. If so, the process advances through steps 138, 140 and 142, to step 154 where again a determination is made (this time by node 6 i) as to the status of the transmit flag. Since node 6 i previously set its transmit flag (at step 152 when the “empty” packet was transmitted), that node determines that the flag is indeed set. At step 156, the busy indicator in the control portion of the packet is changed so that the packet, when passed to the next node, is “free” and may be used by another node. The circuit switched data contained in the payload, which consists of any local connect data that was inserted at step 148 along with all circuit switched data inserted by each other node (including node 6 j), is then written sequentially into the receiver memory 108. Finally, the transmit flag is cleared at step 160 and error status information is checked at step 161 before the process returns to start 138. When circuit switched data is eventually time switched out of memory 108, it is processed by pad lookup circuit 110 which operates in a conventional manner to perform A-law to μ-law (or vice versa) conversions.
FIGS. 4C and 4D show an embodiment of the ESFR method in which both circuit switched data and packet switched data may be transferred between nodes. The initial steps are the same as those shown in FIG. 4B. However, note at step 144 that when a particular node determines that the CSD window is not open, meaning that its circuit switched data was already transmitted (in the current 125 μs frame), the process advances to step 155 instead of returning immediately to start 138. At step 155, a determination is made whether an “empty” data packet, which will be used to collect packet switching information from other nodes, is ready for transmission and the receiver memory is ready. If the “empty” data packet is not ready or the receiver memory is full (not ready), the process returns to start 138. Otherwise, the process advances to step 157 at which information in the control portion of that packet is changed to designate the packet as “empty”. The “empty” packet is then transmitted at step 159, the transmit flag is set at step 161, and the process returns to start 138.
When the next frame is received, the process advances through steps 138, 140 and 142. Assuming that the received packet (within the frame) is designated “busy,” the process advances to step 154 where the status of the transmit flag is checked. If the transmit flag is set, meaning that the node receiving this packet previously transmitted either an “empty” packet to collect packet switched data (at steps 159, 161) or an “empty” packet to collect circuit switched data (at steps 148-152), then the process advances to step 166 where a determination is made of what type of packet has just been received, again by examining information in the control portion of the packet. The type of packet is indicative of whether the packet's payload contains circuit switched data, packet switched data or possibly other types of data (e.g., voice processing or maintenance). If the packet is the type that carries circuit switched data, the process advances through steps 158 and 160, just as described in connection with FIG. 4B. If the packet is the type that carries packet switched data, the process advances to step 168 where a determination is made whether the packet is full. If the packet is not full, it means that no other node had any packet switched data to send (at least during the period of time it took for the packet to traverse the network) to the node which originally transmitted (and has just received) that packet. In that event, the transmit flag is cleared at step 171 and the process returns to start 138.
With reference again to step 154, if a determination is made that the transmit flag is not set, meaning that the packet which was just received originated from another node, then the process advances to step 182 where, like step 166, a determination is made regarding the packet type. If the packet is of the type that carries circuit switched data, the process proceeds through steps 162, 164, and 165 just as in FIG. 4B. If the packet is the type that carries packet switched data, then the process advances to step 188 where a determination is made whether the packet is “empty.” If the packet is not “empty,” meaning that another node already filled the payload, the packet passes to the next node and the process returns to start 138.
Alternatively, if the packet is “empty,” meaning it was originally transmitted “empty” by another node for the purpose of collecting packet switched data and no other node has already “filled” the payload, then the process advances to step 190 where the node which has received the packet determines whether it has any packet switched data to send to the node which originally transmitted the packet. If not, the “empty” packet is passed to the next node and the process returns to start 138. If so, the packet is marked “full” at step 192, the packet switched data is placed in the payload and the “full” packet is transmitted to the next node at step 194.
Within each framing window, approximately one-half of the available time (i.e., 62.5 μs) is allocated for all nodes, in round-robin fashion, to transfer circuit switched data to other nodes. Such transfers may be made using either the ESFR or FSER method, or both, and may involve any type of packet carrying packet switched data (or even circuit is switched data which is being used for another purpose), including packets 5, 7 and 9 of FIG. 1E. The remaining time within each window is allocated for nodes to transfer packet switched data (if any) to other nodes. Note that “priority” is given to the circuit switched data, since all such data from all nodes is transferred before any packet switched data may be transferred.
The ESFR method may also be used to “broadcast” circuit switched data to multiple ports of the same node or across multiple nodes. For example, if there is “local” circuit switched data which is intended for broadcast to multiple local ports, multiple copies of that data is simply inserted into the payload of the “empty” packet at step 148 (FIGS. 4B and 4C). In other words, multiple copies of the byte of data that is intended for broadcast are selectively placed in the payload in locations corresponding to the local ports which are to receive the broadcast. Similarly, if circuit switched data from a remote port is intended for broadcast, multiple copies of that data are inserted at step 164 into locations in the payload(s) (i.e., one packet/payload is needed for each node which has a port that is supposed to receive the broadcast) corresponding to the intended ports.
To summarize, as reflected in FIG. 4A, when the ESFR method is used to transfer data, each node in round-robin fashion transmits an “empty” packet for the purpose of collecting data from all other nodes served by the inter-nodal network 12. Upon receipt of an “empty” packet transmitted by another node, each node operates to selectively read data from one of its memories and place it in the payload of the “empty” packet. When the now “full” packet eventually returns to the node which transmitted it, the data contained within the payload is sequentially written into one of that node's receiver memories. This step marks the completion of the second stage of switching (one-way node to node) performed by the system.
With reference to FIGS. 5A through 5C, further details of the FSER method will be described in the context of a preferred embodiment of a “combined” method in which the FSER method is used to transfer packet switched data and the ESFR method is used to transfer circuit switched data. For enhanced clarity, the portions of FIGS. 5B and 5C which represent the FSER method are enclosed with broken lines. The portions of FIGS. 5B and 5C which represent the ESFR method lie outside of the broken lines and are identical to the steps of FIGS. 4C and 4D which are denoted by like reference numbers.
At step 144, if a determination is made that the CSD window is not open, meaning that it is not the appropriate time to collect circuit switched data from other nodes, the process advances to step 196 where a determination is made whether a “full” data packet (containing packet switched data) is ready for transmission to another node. If not, the process returns to start 138 to await the arrival of another frame. If a data packet is ready, meaning that the payload of the packet is loaded with the packet switched data and an appropriate (nodal) destination address is placed in the control portion of the packet, the packet is marked “full” at step 198. The “full” data packet is then transmitted at step 200. Next, the transmit flag is set at step 202 and the process returns to start 138 to await the arrival of another frame.
Now, consider what happens when a “full” data packet which was transmitted by one node is received by another node. The process advances through steps 138, 140 and 142 to step 154 where a determination is made as to whether the receiving node's transmit flag is set. If that flag is not set, meaning that the packet originated from a different node, the process advances to step 182 where it is determined, in this example, that the packet contains packet switched data as opposed to circuit switched data. Next, at step 214, the nodal destination address of the packet is checked to determine whether the receiving node is the intended recipient of the packet. If not, the process returns to start 138. If so, the receiving node checks to see if its packet receiver memory 118 (FIG. 3A) is ready to accept the packet at step 216. If memory 118 is not ready to accept (e.g., because the memory is currently full), the process advances to step 220 where information is inserted into the status and control portion of the packet to indicate that the node was busy and was unable to accept the packet. The process then returns to start 138.
Lastly, we shall consider the situation where a “full” data packet returns to the node which transmitted it. In this instance, the process advances from step 138 to step 154 where it is determined that the receiving node's transmit flag is indeed set. At step 156, the packet's busy indicator is released (changed to “free”) followed by a determination at step 166 of what type of data the packet contains. In this example, the packet contains packet switched data, so the process advances to step 204 where the transmit flag is cleared. Next, at step 206 a determination is made, based on information contained within the status and control portion of the packet, as to whether the node to whom the packet was addressed was busy. If so, meaning the packet was not accepted by the destination node, the process returns to start 138 to make another attempt to deliver the packet to its destination. If not, the packet transmitter memory (constant areas 124 and 128 in FIG. 3F) is marked empty at step 208. A determination is then made at step 210 whether the packet was accepted by the destination node to which it was addressed. If so, the process returns to start 138. If not, errors are logged at step 212 before returning to start 138.
It should be apparent that the FSER method may be used to transfer circuit switched data as well as packet switched data. When circuit switched data is to be transferred, each node, in turn, transmits a “full” packet whose payload is filled with circuit switched data (for all local ports) which is read sequentially from the transmitter memory 102. As a given node receives, in turn, a “full” packet transmitted by every other node, the given node takes appropriate data from the payload of each such packet and selectively writes data into its receiver memory 108 in response to addresses supplied by sequential counter/map 104. Note that the addresses supplied by counter/map 104 are “global” addresses (i.e., the combination of the implicit port address and the nodal source address), meaning each may represent any port of any node in the entire system. Because the circuit switched data corresponding to these global addresses is written to locations in memory 108 (which correspond to local ports), an address translation must be performed in order to eventually read such data out of memory 108 in the correct order. An address map translation circuit 105 receives as inputs the addresses produced by sequential counter/map 104 of memory 108 where data is stored. The addresses produced by address map local 107 are used to select constant areas within memory 108 and pad values from pad lookup 110.
Like the ESFR method, the FSER method may be used to broadcast circuit switched data to multiple ports. At a given single node, this is accomplished by making multiple copies of the data intended for broadcast from the payload of a “full” packet and selectively writing such data into multiple locations of that node's receiver memory. Similarly, different nodes may be instructed to copy the same broadcast data from the payload of a “full” packet and selectively write such data into one or more locations of those nodes' respective receiver memories, thereby effecting broadcasting across multiple nodes.
Having presented various alternatives for transferring information across inter-nodal network 12, a specific example of how a call is connected between ports which are physically associated with different nodes will now be described. With reference once again to FIGS. 1A, 1B, 2A and 3A through 3E, it should be kept in mind that each node 6 a-6 h necessarily includes at least one nodal switch 44 a. We shall assume that a calling party whose line is interfaced with node 6 h goes off-hook and dials a number which corresponds to a called party whose line is interfaced with node 6 e. The host 4 receives a “request for service” message (which may include the dialed digits) from CPU 64 in node 6 h. The host 4 determines that a connection must be established between nodes 6 h and 6 e and, in response, issues a “connect” message (with port address information) to both nodes' CPUs 64 to connect to each other.
Now, let us consider for a moment what happens just at node 6 h. Circuit switched data from the calling party's line is initially passed, via bus 30 a, from one of the line cards to nodal switch 44 a. For purposes of this example, we shall further assume that that data is stored in transmitter memory 102. Next, if the ESFR method is used, when an “empty” packet transmitted (originated) by node 6 e over the inter-nodal network 12 is received by node 6 h, the circuit switched data from the calling party is time switched out of memory 102 and inserted into the payload of that packet, which will eventually return to node 6 e. At this point, a one-way circuit switched connection exists between the calling party (node 6 h) and node 6 e, a “time” portion executed by the transmitter memory 102 and a second stage portion executed by the inter-nodal network 12. Next, node 6 e's receiver 68 receives its return “full” packet containing the circuit switched data from the calling party. That data is time switched through receiver memory 108 and passed via bus 30 a to the line card 20 to which the called party is interfaced. At this point, a complete one-way connection exists between the calling party (node 6 h) and the called party (node 6 e). Exactly the same process is repeated, in reverse, to establish the other half of the desired two-way connection.
Alternatively, the FSER method could be used to connect the same call. In that case, transmitter 102 in node 6 h time switches the calling party's circuit switched data into a “full” packet which is transmitted over the inter-nodal network 12. Node 6 e, upon receipt of the “full” packet, extracts the calling party's circuit switched data, stores the data in receiver memory 108, and time switches the data to the line card to which the called party is interfaced. Again, the process is carried out in reverse to establish the other half of a two-way connection.
FIGS. 6A and 6B show the expandable telecommunications system 17 (FIGS. 1C and 1D) modified to illustrate the effect of a failure of programmable switching node or a portion of the inter-nodal network 12. In this example, node 6 f has failed or a portion of inter-nodal network 12 has failed (or possibly a malfunction was detected and the node was taken out of service by the host 4). The nodes 6 e and 6 g which are adjacent to the failed node 6 f begin to operate in “loopback” mode. In loopback mode, the circuitry within a node which is normally used to receive information from one ring is connected to the circuitry which is normally used to transmit information on the other ring, as denoted by reference numbers 71 a and 71 b in FIGS. 3A, 6A, and 6B. Thus, when a given node operates in loop back mode, all information received on one ring is immediately transmitted on the other ring. A particular node may be instructed by the host 4 to operate in loopback mode or, alternatively, operation may begin automatically in response to expiration of a “watchdog” timer.
FIG. 7 shows another alternative embodiment of the present invention in which four programmable switching nodes 6k-6n are connected together by an inter-nodal network 12 which consists of one pair of rings, pair A, and one redundant pair of rings, pair B. It should be understood that this embodiment is not limited to only four switching nodes and that one or more additional nodes may be added. In this embodiment, the and width of pair A is preferably sufficiently large that under normal operating conditions, all data (i.e., circuit switched and packet switched) may be transferred by that pair alone. Pair B preferably has comparable bandwidth to that of pair A and remains in a “'standby” mode under normal conditions. In the event of a failure of either of pair A's rings, pair B enters a regular operating mode and assumes responsibility for transferring all of the data. Also, it is preferable that only one pair of rings is “active,” but that both pairs actually transfer information between nodes in parallel. This is to ensure that, in the event of a failure of the “active” ring, connections (calls) which are already established can be maintained and not dropped.
In terms of communications services, circuit 112 operates to dynamically prevent nodal switches 44 a and 44 c from effectively transmitting circuit switched data over bus 30 a during time slots in which a service is being provided by any of cards 36 or 38. Details of how “ownership” or the authority to transmit data during a given time slot may be dynamically passed from one device to another (and back again) are disclosed in co-pending application Ser. No. 08/001,113, incorporated by reference above.
Under normal operating conditions, inter-nodal networks 12 g and 12 i are preferably active and are used to transfer all information between all nodes. The remaining inter-nodal networks 12 h and 12 j preferably have comparable bandwidth to that of 12 g and 12 i and transfer information is parallel with 12 h and 12 j, but remain in a “standby” mode. In the event of a failure of either of the rings of networks 12 g and 12 i, the corresponding redundant network becomes active.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4038638Jun 1, 1976Jul 26, 1977Bell Telephone Laboratories, IncorporatedEfficient rearrangeable multistage switching networksUS4173713May 25, 1978Nov 6, 1979International Telephone & Telegraph CorporationContinuously expandable switching networkUS4228536May 29, 1979Oct 14, 1980Redcom Laboratories, Inc.Time division digital communication systemUS4229816May 29, 1979Oct 21, 1980Redcom Laboratories, Inc.Timing signal generation and distribution system for TDM telecommunications systemsUS4456987Mar 22, 1982Jun 26, 1984International Telephone And Telegraph CorporationDigital switching networkUS4501021May 3, 1982Feb 19, 1985General Signal CorporationFiber optic data highwayUS4527012 *Jan 31, 1983Jul 2, 1985Redcom Laboratories Inc.Communications switching system with modular switching communications peripheral and host computerUS4539676Sep 13, 1982Sep 3, 1985At&T Bell LaboratoriesBulk/interactive data switching systemUS4547880 *Nov 14, 1983Oct 15, 1985Able ComputerCommunication control apparatus for digital devicesUS4569041 *Mar 14, 1984Feb 4, 1986Nec CorporationIntegrated circuit/packet switching systemUS4686330Dec 16, 1983Aug 11, 1987Telecommunications Radioelectriques Et Telephoniques TrtTelephone switching systemUS4757497 *Dec 3, 1986Jul 12, 1988Lan-Tel, Inc.Local area voice/data communications and switching systemUS4792947Apr 13, 1987Dec 20, 1988Hitachi, Ltd.Method of multi-address communicationUS4805172Apr 10, 1987Feb 14, 1989Redeom Laboratories, Inc.Time division multiplex (TDM) switching system especially for pulse code modulated (PCM) telephony signalsUS4962497 *Sep 21, 1989Oct 9, 1990At&T Bell LaboratoriesBuilding-block architecture of a multi-node circuit-and packet-switching systemUS5003533Jul 25, 1989Mar 26, 1991Mitsubishi Denki Kabushiki KaishaNode processing systemUS5008663Jul 22, 1987Apr 16, 1991British Telecommunications Public Company LimitedCommunications systemsUS5029199Aug 10, 1989Jul 2, 1991Boston TechnologyDistributed control and storage for a large capacity messaging systemUS5051987Jul 18, 1989Sep 24, 1991Racal-Milgo LimitedInformation transmission network including a plurality of nodes interconnected by links and methods for the transmission of information through a network including a plurality of nodes interconnected by linksUS5105424Jun 2, 1988Apr 14, 1992California Institute Of TechnologyInter-computer message routing system with each computer having separate routinng automata for each dimension of the networkUS5111198Dec 18, 1990May 5, 1992Thinking Machines CorporationMethod of routing a plurality of messages in a multi-node computer networkUS5119370Sep 28, 1989Jun 2, 1992Northern Telecom LimitedSwitching node for a communications switching networkUS5151900Jun 14, 1991Sep 29, 1992Washington Research FoundationChaos router systemUS5253252Mar 12, 1991Oct 12, 1993The Foxboro CompanyToken device for distributed time scheduling in a data processing systemUS5278848Jun 18, 1991Jan 11, 1994Noboru YamaguchiBidirectional communication methodUS5349579 *Jan 5, 1993Sep 20, 1994Excel, Inc.Telecommunication switch with programmable communications servicesUS5353283May 28, 1993Oct 4, 1994Bell Communications Research, Inc.General internet method for routing packets in a communications networkUS5477530Dec 19, 1994Dec 19, 1995International Business Machines CorporationMethod and apparatus for managing communications between multi-node quota-based communication systemsUS5477547Jul 29, 1994Dec 19, 1995Kabushiki Kaisha ToshibaInter-LAN connection equipmentUS5542047Apr 23, 1991Jul 30, 1996Texas Instruments IncorporatedDistributed network monitoring system for monitoring node and link statusUS5661720Oct 9, 1996Aug 26, 1997Fujitsu LimitedMulti-ring network having plural rings connected by nodeUS5923643 *Feb 27, 1997Jul 13, 1999Excel, Inc.Redundancy, expanded switching capacity and fault isolation arrangements for expandable telecommunications systemUSRE31852Jul 1, 1982Mar 19, 1985Willemijn Houdstermaatschappij BVData transmission systemEP0119105A2Mar 16, 1984Sep 19, 1984Nec CorporationIntegrated circuit/packet switching systemEP0256526A2Aug 13, 1987Feb 24, 1988Nec CorporationPacket-switched communications network for efficiently switching non-burst signalsFR2538662A1 Title not availableGB1243464A Title not available* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS6885671 *Aug 21, 2000Apr 26, 2005Sprint Communications Company L.P.System and method for connecting a callUS7274702 *Nov 27, 2001Sep 25, 20074198638 Canada Inc.Programmable interconnect system for scalable routerUS8788076 *Mar 16, 2007Jul 22, 2014Savant Systems, LlcDistributed switching system for programmable multimedia controllerUS9313564 *Apr 19, 2012Apr 12, 2016Broadcom CorporationLine interface unit with feedback controlUS20030099247 *Nov 27, 2001May 29, 2003Rene ToutantProgrammable interconnect system for scalable routerUS20050091304 *Oct 27, 2004Apr 28, 2005Advanced Premise Technologies, LlcTelecommunications device and methodUS20080228934 *Mar 16, 2007Sep 18, 2008Eschholz Siegmar KDistributed switching system for programmable multimedia controller* Cited by examinerClassifications U.S. Classification370/353, 370/401International ClassificationH04M3/00, H04Q11/04, H04L12/56, H04L12/64, H04L12/43, H04Q3/00Cooperative ClassificationH04L12/6418, H04Q11/0478, H04L2012/6481, H04L2012/6443, H04L2012/6437, H04L12/43, H04L2012/5612, H04L49/105, H04L2012/6486, H04L2012/6475, H04Q3/002, H04L2012/6459, Y10S379/909European ClassificationH04L49/10F1, H04L12/43, H04Q3/00D1, H04Q11/04S2, H04L12/64BLegal EventsDateCodeEventDescriptionJul 21, 2006FPAYFee paymentYear of fee payment: 4Aug 16, 2010FPAYFee paymentYear of fee payment: 8Sep 26, 2014REMIMaintenance fee reminder mailedFeb 18, 2015LAPSLapse for failure to pay maintenance feesApr 7, 2015FPExpired due to failure to pay maintenance feeEffective date: 20150218RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services