Abstract:
An ATM switch for directing traffic flow of native ATM cell traffic and frame based packets between an input and an output port of the switch comprises a device for receiving native ATM cells and transporting the native ATM cells to the output port for output at a switch output rate; a device for receiving the frame based packets; a device for segmenting each received frame based packet into a corresponding plurality of ATM cells and transmitting the plurality of ATM cells to the output port at an ATM cell transmission rate; and a control device for controlling the ATM cell transmission rate to enable reduction of ATM cell loss at the output port and corresponding frame relay packet loss at the expense of packet delay.

Description:
RELATED APPLICATIONS  
       [0001]    This application claims the benefit of provisional U.S. Patent Application Serial No. 60/040,249 filed Feb. 11, 1997. 
     
    
     
       FIELD OF THE INVENTION  
         [0002]    The present invention relates generally to packet-switching communication systems, e.g., ATM (Asynchronous Transfer Mode), and particularly, to schemes for shaping traffic in ATM and packet data switches.  
         BACKGROUND OF THE INVENTION  
         [0003]    ATM switches are beginning to make an appearance in service provider&#39;s networks. However, the networking technology of choice for end-users remains packet-switching technology, including, for example, IP/Frame relay (FR) packets, IPX and ATM FUNI, and TCP (UDP)/IP(IP) among others due to the slow penetration of native ATM to desktops. This implies that enterprise switches in the near future will need to provide FR and IP interfaces on the premises side and ATM connectivity on the wide-area network (WAN) side.  
           [0004]    [0004]FIG. 1 illustrates an enterprise switch  10  with IP packet or frame relay traffic  20  being multiplexed with native ATM traffic  25  onto a wide-area links. Particularly, at the FR/IP interface card  22 , a segmentation process is performed in the ATM adaption layer (AAL) whereby IP and/or frame relay (FR) packets (collectively “Packets”) are converted to ATM cells. Particularly, as shown in FIGS.  2 ( a ) and  2 ( b ) the segmentation process involves converting FR packets  20   a, b, c  into corresponding one or more ATM cells  30   a, b, c,  respectively, in accordance with well known SAR (segmentation and reassembly) techniques. In such a configuration, for example, a 1500 byte FR Packet generates  30  ATM cells, instantaneously, with each ATM cell having about 53 bytes. As shown in FIG. 1, these ATM cells are transported through the ATM switch fabric  32  at the switch port rate to the egress port queue  35  of ATM output card  40 . Since the switch port speed can be orders of magnitude larger than the egress port rate, the ATM cells  30  arrive at a very high rate relative to the port queue service rate. That is, the instantaneous rate of arrival of ATM cells at the egress port queue  35  is substantially greater than the output speed at the wide-area WAN egress link  50 , e.g., a T- 1  link, resulting in queue buildup and cell losses which have a serious performance impact on the ATM and non-ATM traffic. For example, there may be difficulties in meeting the cell loss and other Quality-Of-Service (QoS) guarantees for the ATM services, and large Packet losses for the non-ATM traffic since single ATM cell losses cause loss of entire packets. While one could account for this high-rate burst in the ATM connection admission control (CAC) mechanism, it would be prohibitively expensive in terms of the bandwidth required to prevent e.g., cell loss.  
           [0005]    It would thus be desirable to shape the ATM cells resulting from the segmentation of packets in order to smooth the ATM cell bursts at the switch outputs and reduce their congestion impact.  
         SUMMARY OF THE INVENTION  
         [0006]    The invention is a packet traffic shaping scheme for one or more streams of packet traffic sharing a common resource, e.g., an output egress link in a packet switching device. A first stream of delay tolerant packets, e.g. IP/frame-based packets, are multiplexed to a second stream of packets, e.g. native ATM cells having to meet QoS guarantees. Particularly, the invention provides for the dynamic shaping of the first stream of traffic that is effective in limiting the FR and IP packet loss and the ATM cell loss at the expense of some additional delays for FR and IP traffic which additional delays are acceptable for the packet traffic.  
           [0007]    One aspect of the invention is to provide, in an ATM interface switch, an open-loop shaping scheme that shapes traffic “constantly” regardless of the congestion on the WAN egress link. Another aspect of the invention is a closed-loop shaping scheme whereby the FR and IP traffic is shaped only when there is congestion on the egress hnk. This closed-loop scheme provides superior performance to the first since shaping only takes place when it is needed.  
           [0008]    The various features of novelty which characterize the invention are pointed out with particularity in the claims annexed to and forming a part of the disclosure. For a better understanding of the invention, its operating advantages, and specific objects attained by its use, reference should be had to the drawing and descriptive matter in which there are illustrated and described preferred embodiments of the invention. 
       
    
    
     BRIEF DESCRIPTION OF DRAWINGS  
       [0009]    [0009]FIG. 1 is a general diagram illustrating an ATM switch capable of multiplexing native ATM cell and IP/FR data.  
         [0010]    [0010]FIG. 2 is a diagram illustrating segmentation of IP and/or FR Packets data into ATM cells.  
         [0011]    [0011]FIG. 3( a ) illustrates a traffic shaping scheme of the first embodiment of the invention.  
         [0012]    [0012]FIG. 3( b ) illustrates a variation of the traffic shaping scheme of the first embodiment of the invention.  
         [0013]    [0013]FIG. 4 illustrates the circuit implementation of a traffic shaping scheme of the second embodiment of the invention.  
         [0014]    [0014]FIG. 5 illustrates ATM cell traffic transmission as governed by the shaping scheme of the second embodiment of the invention.  
         [0015]    [0015]FIG. 6 illustrates a variation of egress buffer queue thresholding technique implemented by the shaping scheme of the second embodiment of the invention.  
         [0016]    [0016]FIG. 7( a ) illustrates a plot of Stop/Go shaping loss rates versus stop thresholds.  
         [0017]    [0017]FIG. 7( b ) illustrates a plot of Frame delay versus stop thresholds.  
         [0018]    [0018]FIG. 8( a ) illustrates a plot of shaping method performance impact on FR packet loss rates.  
         [0019]    [0019]FIG. 8( b ) illustrates a plot of shaping method performance impact on FR delay.  
         [0020]    [0020]FIG. 9 illustrates a plot of the ATM Cell loss rate for different shaping methods. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0021]    As packet traffic does not have any binding QoS guarantees, or, have only loosely defined QoS guarantees, this traffic is shaped to reduce the performance impact of large high-rate bursts. This shaping implies that ATM and non-ATM cell loss could be reduced at the expense of some additional delays for the packet traffic.  
         [0022]    [0022]FIG. 3( a ) illustrates the result of an open-loop ATM traffic shaping scheme that is blind to congestion on the WAN egress link. In this embodiment, SAR mechanisms are implemented at the FR/IP Interface card  22  (FIG. 1) to shape the output ATM cell traffic to conform to a given peak cell-rate (PCR), i.e., just enforce a minimum spacing between output ATM cells. Thus, as shown in FIG. 3( a ) ATM cells  30  are output with a spacing of 1/PCR and may be implemented by commercially available SAR (segmentation and reassembly) chips, e.g., the Bt8230 provided by provided by Brooktree Corp. As is known, such SAR chips are already employed in ATM cell rate policing, e.g., the so-called “leaky bucket” policing.  
         [0023]    In accordance with the principles of the invention, a variation of the first embodiment is an open-loop ATM traffic shaping scheme that shapes ATM cell traffic to conform to a given peak cell-rate (PCR) and sustainable cell-rate (SCR). The PCR/SCR shaping imposes two restrictions on the cell stream arising from the segmentation of the packet traffic. First, it enforces a minimum spacing between the ATM cells proportional to the inverse of the PCR, and second, it ensures that the number of cells departing the shaper in any time unit “t”, denoted as D(t), always obeys the following relation: 
           D ( t )≦ SCR t+MBS, ∀t&gt; 0, 
         [0024]    where MBS denotes the maximum burst-size beyond the SCR. FIG. 3( b ) illustrates the ATM traffic output of the FR and IP interface card in accordance with the SCR/PCR shaping scheme with a minimum spacing  33  between ATM cells denoted as 1/PCR, and a minimum spacing  34  between groups of ATM cells in accordance with the relation (MBS−1)*(1/SCR−1/PCR). As mentioned above, this shaping may also be implemented by commercially available SAR (segmentation and reassembly) chips.  
         [0025]    A second scheme, referred to as Stop/Go Shaping, shapes the packet traffic only when there is congestion at the egress ATM queue. As shown in the detailed illustration of the ATM switch in FIG. 4, congestion at the egress port  40  is detected based on a first “stop” threshold  36   a  on the queue occupancy at the egress queue  35  which information is signaled back to the shaper buffer  27  located at the FR/IP Packet interface card  22  either via a hardwire connection, an built-in backpressure mechanism (not shown) or, preferably, a special virtual circuit, e.g., VC  37  setup within the switch. Shaping in this closed-loop scheme is simplistic in that the cell stream  30  derived from the Packet shaper buffer  27  is turned off, i.e., no ATM cells are allowed to leave the shaper, when congestion is detected at the egress queue  35 , and, is turned on again, i.e., ATM cells are allowed to leave the shaper, when the congestion subsides. As shown in FIG. 4, the abatement of congestion is detected based on a second “go” threshold  36   b  on queue occupancy that is lower than the first threshold. Preferably, the first stop threshold  36   a  is set near the memory limit of the egress queue  35  and the go queue occupancy threshold  36   b  is set to provide a hysteresis in order to avoid queue oscillations about the single first threshold level. As in the first embodiment, SAR chips may be employed to shape, in accordance to the feedback, the ATM cell traffic in the second embodiment.  
         [0026]    [0026]FIG. 5 illustrates the stop/go shaping scheme of the preferred embodiment whereby cells  30   d  are transported to the egress buffer  35  at the switch port speed when the queue occupancy threshold is greater than the “go” threshold  36   b.  As shown in FIG. 5, when the queue occupancy threshold is determined to be greater than the “stop” threshold  36   a,  the traffic of ATM cells  30   e  is stopped from being transported to the egress buffer.  
         [0027]    It should be understood that instead of completely stopping transmission of the ATM traffic upon detection of congestion, transmission rate of segmented ATM cells  30  may be drastically reduced to a point where congestion at the egress buffer is avoided. Alternatively, in accordance with the principles of the invention, the stop/go ATM cell traffic shaping scheme of the preferred embodiment may be implemented by establishing multiple egress queue occupancy thresholds, e.g., three or more thresholds, to enable finer control of the performance. For instance, as shown in FIG. 6, egress queue  35  may have a first stop threshold  36   x  enabling the ATM cell stream  30  to be transported from the shaper buffer  27  at a first reduced rate PCR 1 , for example, and, an additional stop threshold  36   z  enabling the ATM cell stream  30  to be transported from the shaper buffer  27  at a second reduced rate PCR 2 , whereby PCR 1 &gt;PCR 2 . Of course, the PCR 2  may be set to zero, to completely stop traffic flow when egress queue congestion is detected. It should be understood that, in this case, associated with stop threshold  36   x  is go threshold  36   w,  and associated with stop threshold  36   z  is go threshold  36   y.    
         [0028]    When egress queue length drops below go threshold  36   y  after it has exceeded stop threshold  36   z,  the output rate will switch from PCR 2  to PCR 1 . Later, if the egress queue length continues to drop below go threshold  36   w,  then the output rate is switched back to PCR. Note that a three threshold scheme can be defined to achieve the same purpose.  
         [0029]    For a given shaping scheme, performance metrics such as Frame Relay (FR) Packet loss rate and average delay (for packet traffic) and ATM cell loss, were evaluated using the queueing model, such as illustrated in FIG. 4, and choosing suitable simulation values for traffic parameters. It should be understood that a FR packet is considered lost when any of the cells constituting the packet is lost. As shown in FIG. 4, native ATM cell traffic  25  and ATM cells  30  generated from the Packet traffic compete for bandwidth and buffer space at the egress port queue  35  shown in the Figure as an ATM multiplexer  41  having a completely shared buffer of size B cells and implementing, for example, a first-come,first-served (FCFS) service discipline  39 . The cell transmission time at the multiplexer  41  is taken to be the unit of time. Both the packet source  30  and the native ATM source  25  are assumed to alternate between transmission (ON) and silent (OFF) periods according to, e.g., a 2-state Markov chain. When a source is ON, it is assumed to generate deterministically-spaced packets (cells) at time units of T on  such as shown in FIG. 5. The number of packets (cells) in the ON period is taken to be geometrically distributed with mean P on . The length of the packet (cell) is taken to be a fixed L. The peak rate of the source is then given as p=L/T on  and the mean rate m=p/b, where b denotes the burstiness of the source.  
         [0030]    A simulation of the stop/go shaping method was conducted with the following traffic parameters: Frame relay packets size was fixed at L=1528 bytes with a T on , set to 16, P on  set to 100, and b set to 6.667; ATM cell size was 53 bytes, P on  set to 100, and b set to 6.667 values. The value of the T on , for ATM cell traffic was varied to keep the total load fixed at 80% of available bandwidth. In evaluating the performance of the stop/go shaping method, the FR frame traffic amounted to about 30% of the total traffic with the remaining traffic being native ATM cell traffic. For the simulation, it was assumed that the FR and ATM sources compete for a buffer space B equal to, e.g., 3200 cells at the ATM multiplexer. For purposes of the delay computations, a T 1  link is assumed, with the time for an ATM cell to be transmitted onto the link to be about 0.27 milliseconds and taken as unit time. Note, that in the stop/go simulation, there is a delay involved in signaling the congestion at the egress queue  35  to the interface card  22  which is taken to be equal to unit time.  
         [0031]    In order to study the impacts of the stop/go thresholds on the FR and ATM cell losses for the Stop/Go Shaping method, the peak rate is fixed (same as no shaping rate) and the FR traffic is transmitted into the ATM multiplexer  41  with the Stop and Go thresholds varied. FIG. 7( a ) illustrates the FR and ATM cell loss rate (y-axis) versus the queue occupancy stop threshold (x-axis) and, FIG. 7( b ) illustrates a plot of the average FR frame delay versus the queue occupancy stop threshold (x-axis), for the Stop/Go Shaping method. As indicated by lines  5 , it can be seen that the FR loss is relatively unaffected by the choice of the stop threshold at the egress queue  35  because the loss can be completely controlled as long as the room between the Stop threshold and the egress buffer limit is sufficient to accommodate any ATM cells  30  in transit from the FR interface card  22  to the egress ATM card  40  before the congestion indication reaches the interface card  22 . For the considered parameter settings, this value is 16 cells which is generally small since the switching delay within a switch is typically small, e.g., in the order of microseconds, and hence the number of cells in transit is small. Hence, no loss occurs till the Stop threshold exceeds, e.g., 3184 for a buffer of size 3200, indicated in FIG. 7( a ).  
         [0032]    As for the ATM cell loss both the Stop and Go thresholds have an impact. As shown in FIG. 7( a ), as both the Stop and Go thresholds increase, as indicated by lines  52   a,  and  52   b,  the ATM cell loss increases. Hence, smaller values of these thresholds are desirable. However, from a FR delay standpoint, higher values of the thresholds are desired as indicated by FR frame delay lines  53   a  and  53   b  plotted in FIG. 7( a ). As seen in the FIG. 7( b ) the relative impact of the thresholds on the delay is small however, and hence a value of the Stop threshold that is close to the value necessary to prevent frame loss, e.g., 3184, and the Go threshold to be small, e.g., 2560 may be chosen.  
         [0033]    [0033]FIG. 8( a ) illustrates a plot of the FR Packet loss (y-axis) for different percentages of FR traffic (x-axis) for each of the different shaping methods and the no-shaping case, and FIG. 8( b ) illustrates a plot of the average FR frame delay in seconds (y-axis) for different percentages of FR traffic (x-axis) for each of the different shaping methods and the no-shaping case. FIG. 9 illustrates a plot of the ATM cell loss rate (y-axis) for different percentages of FR traffic (x-axis) for each of the different shaping methods and the no-shaping case. It can be seen that all of the shaping schemes dramatically reduce the FR loss with the PCR/SCR and the Peak Rate shaping schemes reducing the packet loss from about 15-45% for the no-shaping case to about 5-25% and the packet loss for the Stop/Go scheme being zero. This reduced FR loss is clearly achieved at the expense of some additional delays in all the schemes. For instance, with an equal mix of FR and ATM traffic, the delay is roughly doubled over the no-shaping case to about 1 sec. from 0.5 sec. Finally, the ATM cell loss for the PCR scheme is comparable to no-shaping case in general, but considerably improved in some cases. It is, however, almost uniformly worse for the PCR/SCR scheme, compared to the no-shaping case, probably due to a non-optimal choice of parameters, for this scheme. As shown in FIG. 9, the Stop/Go scheme results in reducing the ATM cell loss from about 0-8% as indicated by line  56   a  (no-shaping scheme) to the range of 0-4% as indicated by line  56   b.    
         [0034]    As shown in FIG. 9, the Stop/Go shaping scheme is extremely effective in limiting the FR and ATM cell loss at the expense of some additional delays for FR traffic. Further, the choice of “optimal” parameters for this scheme is extremely simple and result in predictable and uniformly superior performance.  
         [0035]    The foregoing merely illustrates the principles of the present invention. Those skilled in the art will be able to devise various modifications, which although not explicitly described or shown herein, embody the principles of the invention and are thus within its spirit and scope.