Abstract:
A multiport non-blocking high capacity ATM and packet switch is a single chip switching solution for ATM and packet systems. It is capable of 8×8 switching of 800 Mbit/s per port in both directions. The ports support UTOPIA Level 2 interfaces. The switch is non-blocking and lossless, incorporating a backpressure mechanism for eliminating congestion toward any one port. The switch supports prioritized and variable size cell and packet switching.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The invention relates to telecommunications. More particularly, the invention relates to a multiport non-blocking high capacity ATM and packet switch.  
           [0003]    2. State of the Art  
           [0004]    The first commercial digital voice communications system was installed in 1962 in Chicago, Ill. The system was called “T1” and was based on the time division multiplexing (TDM) of twenty-four telephone calls on two twisted wire pairs. The T1 system is still widely used today and forms a basic building block for higher capacity communication systems including T3 which transports twenty-eight T1 signals. The designations T1 and T3 were originally coined to describe a particular type of carrier equipment. Today T1 and T3 are often used to refer to a carrier system, a data rate, and various multiplexing and framing conventions. It is more accurate to use the designations “DS1” and “DS3” when referring to the multiplexed digital signal carried by the T1 and T3 carriers, respectively.  
           [0005]    Today, another higher bandwidth TDM system is in use. This system is referred to as the synchronous optical network (SONET) or, in Europe, the synchronous digital hierarchy (SDH). The SONET network is designed to provide enormous bandwidth. SONET signals are referred to as Synchronous Transport Signals (STS) or Optical Carriers (OC). The narrowest SONET signal is referred to as STS-1 or OC-1. It has a bandwidth of 51.84 Mb/s which is sufficient to carry twenty-eight DS1 signals or a single DS3 signal. The hierarchy includes STS-3 (OC-3) which is three times the bandwidth of an STS-1 (OC-1) signal, and higher bandwidth signals increasing in multiples of four, i.e. STS-12 (OC-12), STS-48 (CC-48), STS-192 (OC-192), and STS-768 (OC-768).  
           [0006]    The T1 and T3 networks were originally designed for digital voice communication. In a voice network minor bit errors can be tolerated as a small amount of noise. However, in a data network, a minor bit error cannot be tolerated. In the early 1970s, another technology was deployed to support data networks. The technology was called “packet switching”. Unlike the T1 and T3 networks, packet switching was designed for data communications only. In packet switching, a “packet” of data includes a header, a payload, and a cyclic redundancy check (CRC). The header includes addressing information as well as an indication of the length of the payload. The payload contains the actual data which is being transmitted over the network. The CRC is used for error detection. The receiver of the packet performs a calculation with the bits in the packet and compares the result of the calculation to the CRC value. If the CRC value is not the same as the result of the calculation, it means that the packet was damaged in transit. According to the packet switching scheme, the damaged packet is discarded and the receiver sends a message to the transmitter to resend the packet. One popular packet switching scheme for wide area networks (WANs), known as X.25, utilizes a packet which has a fixed payload of 128 octets. Other packet switching schemes allow variable length packets up to 2,000 octets. Frame Relay is an example of a WAN packet switching scheme which utilizes variable sized packets and Ethernet is an example of a local area network (LAN) packet switching scheme which utilizes variable sized packets.  
           [0007]    Concurrent with the development of packet switching several groups around the world began to consider standards for the interconnection of computer networks and coined the term “internetworking”. The leading pioneers in internetworking were the founders of ARPANET (the Advanced Research Projects Network). ARPA, a U.S. Department of Defense organization, developed and implemented the transmission control protocol (TCP) and the internet protocol (IP). The TCP/IP code was dedicated to the public domain and was rapidly adopted by universities, private companies, and research centers around the world. An important feature of IP is that it allows fragmentation operations, i.e. the segmentation of packets into smaller units. This is essential to allow networks which utilize large packets to be coupled to networks which utilize smaller packets. Today, TCP/IP is the foundation of the Internet. It is used for email, file transfer, and for browsing the Worldwide Web. It is so popular that many organizations are hoping to make it the worldwide network for all types of communication, including voice and video.  
           [0008]    Perhaps the most awaited, and now fastest growing technology in the field of telecommunications is known as Asynchronous Transfer Mode (ATM) technology. ATM was originally conceived as a carrier of integrated traffic, e.g. voice, data, and video. ATM utilizes fixed length packets (called “cells”) of 53 octets (5 octets header and 48 octets payload). ATM may be implemented in either a LAN or a WAN.  
           [0009]    Current ATM service is offered in different categories according to a user&#39;s needs. Some of these categories include constant bit rate (CBR), variable bit rate (VBR), unspecified bit rate (UBR), and available bit rate (ABR). CBR service is given a high priority and is used for streaming data such as voice and video where a loss of cells would cause a noticeable degradation of the stream. UBR and ABR services are given a low priority and are used for data transfers such as email, file transfer, and web browsing where sudden loss of bandwidth (bursty bandwidth) can be tolerated. ATM service is sometimes referred to as “statistical multiplexing” as it attempts to free up bandwidth which is not needed by an idle connection for use by another connection.  
           [0010]    ATM switches (like other packet switches) typically include multiple buffers, queues, or FIFOs for managing the flow of ATM cells through the switch. Generally, a separate buffer is provided for each outlet from the switch. However, it is also known to have separate buffers at the inlets to the switch. Buffer thresholds are set to prevent buffer overflow. If the number of cells in a buffer exceeds the threshold, no more cells are allowed to enter the buffer. Cells attempting to enter a buffer which has reached its threshold will be discarded.  
           [0011]    Within the ATM technology, a commonly used interface specification for passing ATM cells between chips on a circuit board is the UTOPIA interface. The UTOPIA interface is specified in ATM Forum standard specification af_phy — 0039.000 (UTOPIA Level 2, Version 1, June 1995) which is hereby incorporated by reference herein in its entirety. The present UTOPIA standard defines an interface between a so-called PHY (physical) device and an ATM device for the transfer of fixed length ATM cells. According to the UTOPIA standard, the PHY device is responsible for performing cell-delineation (via the header error correction (HEC) code) and for (de)scrambling the cell payload of the ATM cells. The PHY device may also perform lower level framing functions, for example, SONET framing. The ATM device is responsible for higher level functions such as buffering and scheduling ATM cells and SAR.  
           [0012]    Today, SONET, ATM, and IP are converging to provide consumers and businesses with multiple telecommunications services such as multimedia conferencing, video on demand, and high speed Internet access. Moreover, because of changes in the regulation of the telecommunications companies, many companies now compete to provide the same or similar services. Given the number of competing companies and the amount of bandwidth sought, an increasingly large number of physical switches are in use.  
           [0013]    In order to lower the costs associated with providing telecommunications services, it is desirable to create broadband switching components which are smaller in size.  
         SUMMARY OF THE INVENTION  
         [0014]    It is therefore an object of the invention to provide a high capacity switch on a single chip.  
           [0015]    It is also an object of the invention to provide a high capacity switch on a single chip which has multiple UTOPIA Level 2 ports on the chip.  
           [0016]    It is another object of the invention to provide a high capacity switch which is non-blocking.  
           [0017]    It is still another object of the invention to provide a high capacity switch which incorporates a backpressure mechanism for eliminating congestion toward any port.  
           [0018]    In accord with these objects which will be discussed in detail below, the switch according to the invention is a cell-based switch on a single chip having an internal unidirectional slotted looped bus, a bus controller, a microprocessor interface, and eight UTOPIA switch ports.  
           [0019]    The bus controller performs several functions. It continuously generates fixed size time slots, or “free cells” to the bus, terminates received cells and relays undelivered cells to the bus. It provides a host microprocessor interface for switch management and controls cell access between the host and remote processors through one or multiple switch ports. It collects switch statistics and, together with each switch port, performs a medium access control protocol for prioritized fair cell access among all the switch ports.  
           [0020]    The internal unidirectional slotted looped bus and the medium access control protocol are preferably based on co-owned U.S. Pat. Nos. 5,402,422 and 5,631,906, the complete disclosures of which are hereby incorporated herein by reference.  
           [0021]    Each port includes a full duplex switch interface with two :O ingress FIFO buffers (high priority and low priority), five egress FIFO buffers (control, high priority multicast, low priority multicast, high priority unicast and low priority unicast), a flow control mechanism which includes a counter array and a backpressure indicator, as well as a 16-bit mode UTOPIA Level 2 compliant interface.  
           [0022]    The internal cell size on the looped bus is 80 bytes. For each cell, the first 16 byte overhead is used for the MAC (Medium Access Control) field, address/map fields, and high-speed inter-block communication fields. The remaining 64 bytes are used to carry the payload. The switch is configurable to handle both ATM cells and non-ATM packets.  
           [0023]    For unicast traffic, the flow control mechanism is per egress queue based. For multicast traffic, however, it is global. A centralized 32-bit backpressure bitmap located inside the bus controller provides congestion status from egress queues to each ingress port. For each priority level of multicast, a common UTOPIA port address is used for all ports and a common backpressure bit is used.  
           [0024]    The two ingress FIFO buffers at each port store and forward cells coming from the UTOPIA Level 2 interface. To prevent egress queue overflow, a nineteen counter array is employed at the ingress port to count the number of cells destined for each egress queue from each of the ingress queues. There are sixteen counters for unicast traffic logging. In addition, there are three counters to count cells destined for the two multicast queues and the control traffic queue. When a cell arrives, regardless of which buffer it belongs to, a corresponding counter, identified by the cell destination queue address, is increased by 1. When a cell leaves either buffer, the same counter is decreased by 1. Thus, each counter records the number of cells outstanding in the ingress buffers for a particular egress queue. A back-pressure signal for each egress queue can be generated with respect to a predetermined counter threshold value. When a counter value reaches the threshold, that is, ingress congestion occurs, a backpressure signal is asserted to stop the UTOPIA Level 2 interface from accepting any further cells destined for that particular egress queue. When the counter value decreases from the threshold, the backpressure signal is immediately de-asserted so that other cells destined for that egress queue can be accepted.  
           [0025]    According to the presently preferred embodiment, backpressure signals are asserted when either ingress or egress congestion occurs. Between the two back-pressure sources, a logical OR function is used for backpressure signal generation. In order to prevent head-of-line blocking, cells waiting in ingress buffers are switched regardless of backpressure bitmap changes.  
           [0026]    Additional objects and advantages of the invention will become apparent to those skilled in the art upon reference to the detailed description taken in conjunction with the provided figures. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0027]    [0027]FIG. 1 is a high level block diagram of a switch according to the invention;  
         [0028]    [0028]FIG. 2 is a high level block diagram of one of the ports of the switch;  
         [0029]    [0029]FIG. 3 is a table illustrating the format of the internal cell structure of the switch when configured to carry ATM cells;  
         [0030]    [0030]FIG. 4 is a table illustrating the format of the internal cell structure of the switch when configured to carry non-ATM packet payload;  
         [0031]    [0031]FIG. 5 is a timing diagram illustrating the timing of UTOPIA transmit Multi-PHY; and  
         [0032]    [0032]FIG. 6 is a timing diagram illustrating the timing of UTOPIA receive Multi-PHY. 
     
    
     DESCRIPTION OF THE APPENDIX  
       [0033]    Attached hereto as an appendix is the Transwitch® TXC-05840 Data Sheet Product Preview (64 pages) which provides additional low level information about an embodiment of the invention which has been reduced to practice.  
       DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0034]    Referring now to FIG. 1, the switch  10  according to the invention is a cell-based switch on a single chip having an internal unidirectional slotted looped bus  12 , a bus controller  14 , a microprocessor interface  16 , and eight switch ports  18   a - 18   h . A ninth port is shown as part of the bus controller  14 . As used herein, these ports may be referred to as ports  0 - 8 . The bus controller  14  and the interface  16  are optionally coupled to a mailbox  15 . The switch also includes an IEEE Joint Test Action Group (JTAG) interface  20 , a phase locked loop (PLL)  22 , and a resettable clock generator  24 .  
         [0035]    According to the presently preferred embodiment, the bus  12  is 128-bits (sixteen bytes) wide and is clocked at 200 MHz. The internal cell size on the bus is eighty bytes. Thus, a cell is moved onto or off of the bus in five clock cycles. For each cell, the first sixteen bytes are overhead used for the MAC (Medium Access Control) field, address/map fields, and high-speed inter-block communication fields. The remaining sixty-four bytes are used to carry the payload. The switch is configurable to handle both ATM cells and non-ATM packets as discussed below with reference to FIGS. 3 and 4.  
         [0036]    The bus controller  14  performs several functions. It continuously generates fixed size time slots, or “free cells” to the bus  12 , terminates received cells and relays undelivered cells to the bus  12 . It provides a host microprocessor interface for switch management and control cell access between the host and remote processors through one or multiple switch ports. It collects switch statistics and, together with each switch port  18   a - 18   h , performs a medium access control protocol for prioritized fair cell access among all the switch ports.  
         [0037]    Turning now to FIG. 2, each port  18   a - 18   h  includes a full duplex switch port interface with a high priority ingress FIFO buffer  26 , a low priority ingress FIFO buffer  28 , a control egress FIFO buffer  30 , a high priority multicast egress FIFO buffer  32 , a low priority multicast egress FIFO buffer  34 , a high priority unicast egress FIFO buffer  36 , and a low priority unicast egress FIFO buffer  38 . Each port also includes a flow control mechanism which includes a counter array  40  and a backpressure indicator  42 . Each port also includes a sixteen-bit mode UTOPIA Level 2 compliant interface  44   a ,  44   b.    
         [0038]    [0038]FIG. 3 illustrates the cell structure when the switch is configured to carry ATM cells. In ATM mode, the cell can be 54/56/58/60/62/64 bytes, corresponding to the padding of 0/2/4/6/8/10 bytes. The last fifty-four bytes are used for carrying a standard ATM cell and a multicast bitmap. As shown in FIG. 3, the first twelve bits of the ATM cell (VPI field for the NNI cell structure) is used to carry the multicast bitmap. Since the present implementation of the switch has eight ports, four of the twelve bits are not used but are reserved. The UDF2 field of the ATM cell is used to carry the source port address.  
         [0039]    [0039]FIG. 4 illustrates the cell structure for non-standard ATM or packet cells. As shown in FIG. 4, the multicast bitmap can be placed anywhere within the first fourteen bytes of the cell. During the switch initialization, a three-bit field of enable switch command (EN_SW) is used to specify the start byte of this multicast bitmap. The valid start byte position is from byte  1  to byte  13 . All the other bytes not used for the multicast bitmap can be used for carrying overhead or payload.  
         [0040]    Referring once again to FIG. 2, for unicast traffic, the flow control mechanism is egress queue based. For multicast traffic, however, it is global. A centralized thirty-two-bit backpressure bitmap  46  located inside the switch engine  14  provides congestion status from egress queues 30, 32, 34, 36, 38 to each ingress port  44   a . For each priority level of multicast, a common UTOPIA port address is used for all ports and a common backpressure bit is used. According to the presently preferred embodiment, UTOPIA PHY addresses are mapped to port egress queues as shown in Table 1.  
                                     TABLE 1                       UTOPIA PHY Address   Egress Queue   Port Number                                0   Control   0       1   Multicast High Priority   1-8       2   Multicast Low Priority   1-8       3   Unicast High Priority   1       4   Unicast Low Priority   1       5   Unicast High Priority   2       6   Unicast Low Priority   2       7   Unicast High Priority   3       8   Unicast Low Priority   3       9   Unicast High Priority   4       10   Unicast Low Priority   4       11   Unicast High Priority   5       12   Unicast Low Priority   5       13   Unicast High Priority   6       14   Unicast Low Priority   6       15   Unicast High Priority   7       16   Unicast Low Priority   7       17   Unicast High Priority   8       18   Unicast Low Priority   8       19-31   Reserved   Reserved                  
 
         [0041]    Of the five egress queues 30, 32, 34, 36, 38, four are dedicated to user traffic and one is for control traffic. The descending order of priority is control traffic, high priority multicast, high priority unicast, low priority multicast, and low priority unicast. The user traffic buffers are all the same length, e.g. forty-eight cells as shown in FIG. 2. The control queue does not require so large a buffer. As shown in FIG. 2, a two cell buffer is sufficient for control traffic.  
         [0042]    The two ingress FIFO buffers  26 ,  28  at each port store and forward cells coming from the UTOPIA Level 2 interface  44   a . To prevent egress queue overflow, an array of nineteen counters  40  is employed to count the number of cells destined for each egress queue from each of the ingress queues. There are sixteen counters for unicast traffic logging. In addition, there are three counters to count cells destined for the two multicast queues and the control traffic queue. When a cell arrives, regardless of which buffer in which port it belongs to, a corresponding counter, identified by the cell destination queue address, is increased by 1. When the cell leaves the queue, the same counter is decreased by 1. Thus, each counter records the number of cells outstanding in the ingress buffers for each egress queue in the switch. A backpressure signal for each egress queue can be generated from the nineteen counter array with respect to predetermined counter threshold values. When a counter value reaches the threshold, a backpressure signal is asserted to stop the UTOPIA Level 2 interface  44   a  from accepting any further cells destined for that particular egress queue. When the counter value decreases from the threshold, the backpressure signal is immediately de-asserted so that other cells destined for that egress queue can be accepted.  
         [0043]    According to the presently preferred embodiment, each of the ingress buffers are permitted to hold up to two cells for the same egress queue. Thus, each counter of the counter array  40  counts up to two cells for each egress queue destination. For a switch with N ports, the high priority ingress queue of each port should therefore hold 2*(N+2) cells and the low priority queue should hold 2*(N+1) cells. Although the presently preferred embodiment of the switch has eight ports, the buffer sizes indicated in FIG. 2 are for a ten-port switch.  
         [0044]    Unlike ingress flow control, egress backpressure is controlled globally. To perform lossless cell switching between multiple ports and to support heterogeneous port speed switch configurations, each egress user traffic queue must be able to absorb burst traffic simultaneously coming from multiple ingress ports for a certain time period. When an egress queue accumulates cells up to a point possibly causing overflow, it raises a warning signal and the signal sets a relative bit in the backpressure bitmap. Through a feedback mechanism, this will immediately trigger all ingress ports to stop accepting any more cells destined for the congested egress queue. Two parameters are used to determine when to raise and lower the warning signal. These are high watermark adjustment (HWMA) and watermark offset (WM_OFFSET). HWMA is used for raising the congestion condition flag and WM_OFFSET is used for clearing the congestion condition flag. Both parameters are user programmable. The parameter HWMA is switch based and it is set globally. The parameter WM_OFFSET is per port based and it is set individually. Users can change each parameter dynamically to optimize applications performance in terms of active port numbers and port rate. When the cell inflow rate is greater than the cell outflow rate in an egress queue, cells will accumulate in the queue. When the number of cells reaches the predetermined HWMA point, a congestion condition is indicated and a corresponding bit in the backpressure bitmap is set.  
         [0045]    At any given moment, there can be multiple cells in transition on the switch bus. The number of cells in transition depends on the number of switch ports. For the worst case scenario, all the cells in transition may destined for a congested egress queue. Moreover, each ingress port can hold up to two cells destined for the same egress queue. To prevent cell overflow for such a case, the HWMA value must be greater or equal to the maximum number of cells in transition plus two cells coming from each of the active ingress queues. The value of HWMA can be expressed as Equation (1) where C t  and P active  denote cells in transition and number of active ingress ports, respectively.  
           HWMA≧C   t +2( P   active −1)   (1)  
         [0046]    When the number of cells in a queue drops to a congestion clearance point, the congestion flag is lowered. The congestion clearance point is defined as the queue size less the HWMA less the WM_OFFSET. For a Utopia2 interface rate, the minimum congestion clearance point is 2. For higher speed port rate, the congestion clearance point must be larger, e.g. between 4 and 8. In switches with heterogeneous port speeds, each port may keep separate WM_OFFSET value.  
         [0047]    According to the preferred embodiment, backpressure signals are asserted when either ingress or egress congestion occurs. Between the two backpressure sources, a logical OR function  48  is used for backpressure signal generation to the UTOPIA input interface  44   a . In order to prevent head-of-line blocking, cells waiting in ingress queues  26 ,  28  are switched regardless of backpressure bitmap changes.  
         [0048]    When the UTOPIA input interface receives a backpressure indication, it uses standard UTOPIA signaling to refuse cells destined for the affected queue.  
         [0049]    It will be appreciated that in the case of multicast cells, congestion at any one egress queue will cause a backpressure indication at the source port which will affect all destination ports. To alleviate this outcome, an egress link status based timeout mechanism is available to prevent multicast backpressure from starving multicast traffic for an excessive time due to link failure experienced at an egress port. The timeout mechanism utilizes a timer (not shown) to monitor the egress link status. A transmission of any cell from the egress port resets the timer. The timer is started when any egress queue is not empty and the transmission does not occur. A link failure is detected when the timer expires. In that case, the affected port cancels both multicast backpressures regardless of congestion status. As a result, a link failure at one egress port will not affect multicast cell deliveries of the other egress ports. The egress port experiencing link failure will eventually drop all cells due to queue overflow.  
         [0050]    Whenever a link failure is detected, the affected egress port generates an interrupt to the host (if not masked). The host is able to monitor relative statistics counters of user traffic to determine whether a link failure is recovered. The host can also issue control cells to test the condition of the egress port link status by checking the value change of the egress control counter. The link status recovery is triggered by the transmission of either a unicast or a multicast cell. Upon such an instance, the affected egress port resets the timeout timer and restores normal operation of the multicast backpressure mechanism.  
         [0051]    The timeout value is determined during the switch initialization. The default value can be 1 or 2 ms. For any ports not activated, cells coming to them from the switch bus are always dropped.  
         [0052]    Detailed timing diagrams for the UTOPIA interfaces of the switch are provided in FIGS. 5 and 6, with values for the timing intervals given in Tables 2 and 3. All output times are measured with a maximum 25 pF load capacitance, unless noted otherwise. Timing parameters are measured at voltage levels of (V IH +V IL )/2 and (V OH +V OL )/2, for input and output signals, respectively.  
                                                             TABLE 2                       Parameter   Symbol   Min   Typ   Max   Unit                                RXnCLKI clock cycle time   t CYC     20           ns       RXnCLKI duty cycle,       40       60   %       t PWH /t CYC         RXnDATA (0-15), RXnSOC   t SU(1)     4.0           ns       setuptime to RXnCLKI       RXnADDR (0-4) setup time to   t SU(2)     5.0           ns       RXnCLKI       RXnENB setup time to   t SU(3)     6.0           ns       RXnCLKI       RXnDATA (0-15), RXnSOC,   t H(1)     1.0           ns       RXnADDR (0-4), RXnENB hold       time after RXnCLKI       RXnCLAV delay from RXnCLKI   t D(1)     2.0       12   ns                  
 
         [0053]    [0053]                                                             TABLE 3                       Parameter   Symbol   Min   Typ   Max   Unit                                TXnCLKI clock cycle time   t CYC     20           ns       TXnCLKI duty cycle,       40       60   %       t PWH /t CYC         TXnADDR (0-4) setuptime to   t SU(1)     4.0           ns       TXnCLKI       TXnENB setup time to   t SU(2)     7.5           ns       RXnCLKI       TXnENB, TXnADDR (0-4)   t H(1)     1.0           ns       HOLD time after TXnCLKI       TXnDATA (0-15) delay from   t D(1)     2.0       11.5   ns       TXnCLKI       TXnSOC, TXnCLAV delay from   t D(2)     2.0       11   ns       TXnCLKI                    
         [0054]    There have been described and illustrated herein a multiport non-blocking high capacity atm and packet switch. While particular embodiments of the invention have been described, it is not intended that the invention be limited thereto, as it is intended that the invention be as broad in scope as the art will allow and that the specification be read likewise. It will therefore be appreciated by those skilled in the art that yet other modifications could be made to the provided invention without deviating from its spirit and scope as so claimed.