Abstract:
In an ATM communications system, a cell entering a switch fabric input port is routed to its destination output port and to a predetermined dedicated second output port. The second output port is connected by a feedback connection to a predetermined dedicated second input port. The cell can then be either switched to the same destination output port or switched to both the same destination output port and the predetermined dedicated second output port, thereby providing the ability to execute a logical multicast with any number of leaves to the destination output port.

Description:
TECHNICAL FIELD OF INVENTION 
     The present invention relates generally to the field of asynchronous transfer mode (ATM) communications and, more particularly, to logical multicasting in an ATM switch fabric. 
     BACKGROUND OF THE INVENTION 
     In an ATM communications system it is often desirable to establish a point-to-multipoint virtual connection (VC), which is known as “multicasting.” For example, a caller at a location in New York may wish to set up a conference call with three other participants, each of whom are in Los Angeles. Rather than establishing three separate cross-country VCs, it is desirable, from a bandwidth perspective, to have a single cross-country VC for the call which is then “multicast” to each participant from a switch point which is closer to the recipients&#39; respective locations. 
     A multicast may be either spatial or logical. A spatial multicast occurs when the recipients are located at different physical switch output ports from one another. A logical multicast occurs when the recipients are located at the same physical output port, for example, on a LAN. So, in our example, if the three recipients are located at several unconnected offices scattered throughout Los Angeles, the multicast would be spatial. If, on the other hand, the recipients are located at a single company with a LAN, the multicast would be logical, since the call would be directed to all three recipients from a single switch output port at the local telephone company central office which serves the LAN. 
     Presently, ATM switches typically have a spatial multicasting capability, and switches which perform both spatial and logical multicasting are available. MMC Networks, Inc., for example, manufactures and sells a switch with full multicasting capabilities. Such switches however, have a number of disadvantages. Fist, a significant amount of available memory in the switch lookup tables must be dedicated to logical multicasting. In addition, logically multicasting switches typically are larger and use significantly more power than switches that do not have logical multicasting capability. They are also much more expensive. As those skilled in the art are well aware, space, power and cost constraints are important considerations in the design of any communications system. 
     SUMMARY OF THE INVENTION 
     In accordance with the present invention, an ATM cell entering a switch fabric input port is routed to its destination output port and to a predetermined dedicated second output port. The second output port is connected by a feedback connection to a predetermined dedicated second input port. The incoming cell can then be either switched to the same destination output port or switched to both the same destination output port and the predetermined dedicated second output port, thereby providing the ability to execute a logical multicast with any number of leaves to the destination output port. 
     It is therefore an object of the present invention to provide a logical multicasting capability using the smaller, cheaper and less power-consuming switches which do not have a built-in logical multicasting function. It is a further object to do so without adding significant size, cost or power consumption to the switch fabric. 
     For a better understanding of the present invention, together with other and further objects, reference is made to the following description, taken in conjunction with the accompanying drawings and its scope will be pointed out in the appended claims. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 depicts an exemplary switch configuration in accordance with the present invention; 
     FIG. 2 is a flow diagram illustrating a logical multicast operation in accordance with the embodiment of the present invention depicted in FIG. 1; 
     FIG. 3 is an illustration of a sample logical multicast in accordance with the present invention using the switch configuration of FIG. 1; 
     FIG. 4 depicts a second exemplary switch configuration in accordance with the present invention; 
     FIG. 5 is an illustration of a sample logical multicast in accordance with the present invention using the switch configuration of FIG. 4; 
     FIG. 6 is an illustration of a second sample logical multicast in accordance with the present invention using the switch configuration of FIG. 4; 
     FIG. 7 depicts a third exemplary switch configuration in accordance with the present invention; and 
     FIG. 8 is an illustration of a sample logical multicast in accordance with the present invention using the switch configuration of FIG.  7 . 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     FIG. 1 depicts an exemplary switch configuration in accordance with the present invention. Switch  10  is an 8×8 ATM switch without a built-in logical multicasting capability. Such a switch is available from, among other vendors, Integrated Device Technologies, Inc. The switch is configured according to the present invention to provide logical multicasting. A feedback connection  12  is provided from output port  8  to input port  8 , each of which is dedicated to the logical multicasting function. The use of the number  8  ports is arbitrary; any input/output pair of ports will suffice. 
     When logical multicasting to a single output port, for example output port  1 , is desired, the lookup table is set up to produce a spatial multicast to the desired output port, in this example port  1 , and to the dedicated output port, in this example port  8 . The information is then routed back via the feedback connection  12  into the switch at input port  8 . If only two virtual connections are desired for the multicast, the cell is then routed only to output port  1 . If one or more additional virtual connections are desired, then a port  1 /port  8  spatial multicast is executed again, with the ATM cell being sent on a second virtual connection out of port  1  and again out of port  8 . The feedback/spatial multicast routine is performed as many times as necessary to achieve the desired number of virtual connections out of port  1 . 
     FIG. 2 is a flow diagram for the above-described routine performed at the switch  10  to obtain a logical multicast. At box  15 , a cell arrives at an input port. At box  18 , the VPI/VCI information and the corresponding entry in the switch lookup table are read. Based upon the lookup table information, at box  22  it is determined whether a spatial multicast to port  8  and any other output port is to be performed, i.e., a logical multicast is desired for the payload information. If not, then, at box  25 , the cell is sent to the desired output port or ports, and the switch does nothing further with the cell. If, however, the lookup table information read at box  18  indicates that a spatial multicast to output port  8  and another destination output port is desired, at box  27  the spatial multicast is performed. At box  30 , the cell is fed back into input port  8  from output port  8 , and the flow diagram then returns to box  18  where the lookup table is again consulted to see if additional VCs to the same output port are set up for the cell. 
     FIG. 3 illustrates a sample logical multicast in accordance with the present invention using the switch configuration of FIG. 1 wherein an 8×8 switch  10  without a built-in logical multicasting capability is configured with a feedback path from output port  8  to input port  8 . In this example, a logical multicast from a sender at input port X to four recipients at output port Y is performed. A cell enters port X of switch  10 . Based upon the VPI/VCI information contained in the cell header, lookup table entry  37  in the lookup table of the switch points to two other lookup table entries  40 ,  42 , thereby indicating that a spatial multicast is to be performed. Entries  40 ,  42 , in turn, route the cell to output port Y on virtual connection VC 1  and to output port  8  at time t=t 1 . As described above, output port  8  has a feedback connection to input port  8 . Based upon the VPI/VCI information in the header of the cell entering input port  8 , lookup table entry  45  again points to two other lookup table entries  47 ,  49  which carry out a spatial multicast to output port Y on virtual connection VC 2  and to output port  8  at time t=t 2 . The cell entering input port  8  from the feedback connection is again spatially multicast. Lookup table entry  52  points to entries  55 ,  57  which route the cell information to output port Y on virtual connection VC 3  and to output port  8  at time t=t 3 . Finally, the cell entering input port  8  from the feedback connection is directed to output port Y on virtual connection VC 4  by lookup table entry  60 . The end result is that the same payload information of the cell which entered input port X is transmitted on four virtual channels out of the same output port. 
     FIG. 4 depicts a second exemplary switch configuration in accordance with the present invention. In this configuration, four 8×8 switches  65 ,  67 ,  69 ,  71  comprise the switch fabric of a network element performing switching among eight service units (SUs) and two line units (LUs). In the unidirectional representation of the bidirectional system depicted in FIG. 4, the output sides of two of the switches  65 ,  69  are connected to the input sides of the other two switches  67 ,  71  via cell bus  74 . The input side of switch  65  and the output side of switch  67  are connected to the eight SUs, while switches  69  and  71  are connected to the two LUs, as well as a CPU which aids in the switching function. Box  77  depicts the address translation (AT), usage parameter control (UPC) and operations, administration and management (OAM) functions which may be carried out by a commercially available chip such as one manufactured by PMC/Sierra under the trade name Atlas. In accordance with the invention, a feedback connection  82  is provided from an output port of switch  71  to an input port of switch  69 . 
     FIG. 5 is an illustration of a sample logical multicast in accordance with the present invention using the switch configuration of FIG.  4 . In this example, a point-to-multipoint connection with three leaves to the same LU 1  output port of switch  71  is established. A cell to be multicast enters the SU 1  input port of switch  65  where VC lookup table entry  83  broadcasts the cell onto the cell bus  74 . Each switch has a different VPI associated with it, and, based upon the VPI information in the header, the cell is recognized and received at switch  71  where, based upon the VCI information in the header, VC lookup table entry  85  effects a spatial multicast, pointing to entries  87 ,  89 . Entry  87  routes the cell out the LU 1  port on VC 1 , and entry  89  routes the cell to output port  8  of switch  71 , through the feedback connection to the designated input port of switch  69 . Entry  91  of the lookup table in switch  69  sends the cell through the switch onto the cell bus  74 . Again, based upon the VPI information, the cell is recognized and received at switch  71 , and based upon the VCI information, entry  93  of the VC lookup table points to entries  95 ,  97 . Entry  95  routes the cell out the LU 1  port on VC 2 , and entry  97  routes the cell to output port  8  of switch  71 , through the feedback connection to the designated input port of switch  69 . The cell is then routed through switch  69  by VC entry  99  to switch  71  and out the LU 1  port on VC 3  by VC entry  101 . 
     FIG. 6 is an illustration of a second sample logical multicast in accordance with the present invention using the switch configuration of FIG.  4 . In this example, a point-to-multipoint connection with three leaves to the same SU 3  output port of switch  67  is established. Since the desired output port is not on the switch having the output port dedicated to logical multicasting, in this case switch  71 , it will be seen that, unlike the previous examples, spatial multicasting within any of the four individual switches which comprise the switch fabric is not necessary to accomplish the desired logical multicast. 
     The cell to be multicast enters the SU 1  input port of switch  65  and is broadcast onto the cell bus  74  by VC lookup table entry  105 . Each of switches  67 ,  71  has a lookup table entry for the cell based upon the VPI/VCI header information. Entry  107  in switch  67  sends the cell to output port SU 3  on VC 1 . Entry  109  in switch  71  sends the cell along the feedback connection  82  to the dedicated input port on switch  69 . Entry  111  in switch  69 , in turn, broadcasts the cell onto the cell bus  74 , and the routine is repeated until the cell is sent on three VCs from the SU 3  output port of switch  67 . 
     As demonstrated in the previous example, a primary advantage of eliminating the need for spatial multicasting by logically multicasting out of a switch which does not have the dedicated feedback path  82  of the invention is that the number of necessary VC lookup table entries is reduced. In the example discussed in connection with FIG. 5, ten entries were necessary to obtain a point to multipoint connection with three leaves. In the example discussed in connection with FIG. 6, however, only eight entries were necessary to obtain the same result, i.e., three leaves from a single output port, where the desired output port was not on the same switch having the dedicated feedback output port. The number n of necessary lookup table entries B may be expressed as B=n+3(n−1)+1 for logical multicasts out of switch  71  where spatial multicasting is necessary, as in FIG. 5, and as B=n+2(n−1)+1 for logical multicasts out of switch  67  where spatial multicasting is not necessary, as in FIG.  6 . 
     A further reduction in the memory required by the four switches comprising the switch fabric may be realized by employing an additional switch dedicated to the logical multicasting function. FIG. 7 depicts a third exemplary switch configuration in accordance with the present invention which employs an additional switch  113  dedicated to the logical multicasting function to ensure that spatial multicasting within any of the four primary switches  65 ,  67 ,  69 ,  71 , is not required for any logical multicasting operations, thereby conserving memory in the four primary switches. Switch  113  employs a feedback cell bus  115  from the outputs to the inputs of the switch. The cell bus  115  feeds into the main cell bus  74 , and provides a significant speed advantage over the use of a single pair of ports. 
     FIG. 8 is an illustration of a sample logical multicast in accordance with the present invention using the switch configuration of FIG.  7 . In this example, a cell coming in to input port SU 1  on switch  65  is multicast three times to the same output port SU 3  of switch  67 . The incoming cell is directed onto the cell bus  74  by lookup table entry  119  in switch  65 . Each of chips  67 ,  113  have lookup table entries for the cell. Entry  121  in chip  67  directs the cell out of the destination output port SU 3  on VC 1 . Entry  123  in chip  113  directs the cell out of the chip and onto the feedback cell bus  115  which broadcasts the cell onto the main cell bus  74 . Again, each of chips  67 ,  113  have lookup table entries for the cell. Entry  125  in chip  67  directs the cell out of the destination output port SU 3  on VC 2 . Entry  127  in chip  113  directs the cell onto cell bus  115  which broadcasts the cell onto the main cell bus  74 . The cell is then accepted at each of chips  67 ,  113  for a third time. Lookup table entry  129  in chip  67  sends the cell out of the destination output port SU 3  on VC 3 , while lookup table entry  131  in chip  113  stops sending the cell since the triple multicast to the designated output port on chip  67  has been accomplished. 
     While this invention has been described with reference to several illustrative examples and embodiments, they should not be interpreted as limiting the scope or spirit of the invention which uses feedback to provide a logical multicasting function in an ATM switch fabric. In actual practice many modifications may be made by those of ordinary skill in the art without deviating from the scope of the invention as expressed in the appended claims.