Network Working Group I. Widjaja Request For Comments: 2682 Fujitsu Network Communications Category: Informational A. Elwalid Bell Labs, Lucent Technologies September 1999 Performance Issues in VC-Merge Capable ATM LSRs Status of this Memo This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (1999). All Rights Reserved.
AbstractVC merging allows many routes to be mapped to the same VC label, thereby providing a scalable mapping method that can support thousands of edge routers. VC merging requires reassembly buffers so that cells belonging to different packets intended for the same destination do not interleave with each other. This document investigates the impact of VC merging on the additional buffer required for the reassembly buffers and other buffers. The main result indicates that VC merging incurs a minimal overhead compared to non-VC merging in terms of additional buffering. Moreover, the overhead decreases as utilization increases, or as the traffic becomes more bursty. 1], Cisco's Tag switching , Toshiba's CSR , IBM's ARIS , and IETF's MPLS . Although the details of their implementations vary, there is one fundamental concept that is shared by all these proposals: map the route information to short fixed-length labels so that next-hop routers can be determined by direct indexing. Although any layer 2 switching mechanism can in principle be applied, the use of ATM switches in the backbone network is believed to be a very attractive solution since ATM hardware switches have been extensively studied and are widely available in many different
architectures. In this document, we will assume that layer 2 switching uses ATM technology. In this case, each IP packet may be segmented to multiple 53-byte cells before being switched. Traditionally, AAL 5 has been used as the encapsulation method in data communications since it is simple, efficient, and has a powerful error detection mechanism. For the ATM switch to forward incoming cells to the correct outputs, the IP route information needs to be mapped to ATM labels which are kept in the VPI or/and VCI fields. The relevant route information that is stored semi-permanently in the IP routing table contains the tuple (destination, next-hop router). The route information changes when the network state changes and this typically occurs slowly, except during transient cases. The word "destination" typically refers to the destination network (or CIDR prefix), but can be readily generalized to (destination network, QoS), (destination host, QoS), or many other granularities. In this document, the destination can mean any of the above or other possible granularities. Several methods of mapping the route information to ATM labels exist. In the simplest form, each source-destination pair is mapped to a unique VC value at a switch. This method, called the non-VC merging case, allows the receiver to easily reassemble cells into respective packets since the VC values can be used to distinguish the senders. However, if there are n sources and destinations, each switch is potentially required to manage O(n^2) VC labels for full-meshed connectivity. For example, if there are 1,000 sources/destinations, then the size of the VC routing table is on the order of 1,000,000 entries. Clearly, this method is not scalable to large networks. In the second method called VP merging, the VP labels of cells that are intended for the same destination would be translated to the same outgoing VP value, thereby reducing VP consumption downstream. For each VP, the VC value is used to identify the sender so that the receiver can reconstruct packets even though cells from different packets are allowed to interleave. Each switch is now required to manage O(n) VP labels - a considerable saving from O(n^2). Although the number of label entries is considerably reduced, VP merging is limited to only 4,096 entries at the network-to-network interface. Moreover, VP merging requires coordination of the VC values for a given VP, which introduces more complexity. A third method, called VC merging, maps incoming VC labels for the same destination to the same outgoing VC label. This method is scalable and does not have the space constraint problem as in VP merging. With VC merging, cells for the same destination is indistinguishable at the output of a switch. Therefore, cells belonging to different packets for the same destination cannot interleave with each other, or else the receiver will not be able to reassemble the packets. With VC merging, the boundary between two adjacent packets are identified by the "End-of- Packet" (EOP) marker used by AAL 5.
It is worthy to mention that cell interleaving may be allowed if we use the AAL 3/4 Message Identifier (MID) field to identify the sender uniquely. However, this method has some serious drawbacks as: 1) the MID size may not be sufficient to identify all senders, 2) the encapsulation method is not efficient, 3) the CRC capability is not as powerful as in AAL 5, and 4) AAL 3/4 is not as widely supported as AAL 5 in data communications. Before VC merging with no cell interleaving can be qualified as the most promising approach, two main issues need to be addressed. First, the feasibility of an ATM switch that is capable of merging VCs needs to be investigated. Second, there is widespread concern that the additional amount of buffering required to implement VC merging is excessive and thus making the VC-merging method impractical. Through analysis and simulation, we will dispel these concerns in this document by showing that the additional buffer requirement for VC merging is minimal for most practical purposes. Other performance related issues such as additional delay due to VC merging will also be discussed.
The purpose of the RB is to ensure that cells for a given packet do not interleave with other cells that are merged to the same VC. This mechanism (called store-and-forward at the packet level) can be accomplished by storing each incoming cell for a given packet at the RB until the last cell of the packet arrives. When the last cell arrives, all cells in the packet are transferred in an atomic manner to the output buffer for transmission to the next hop. It is worth pointing out that performing a cut-through mode at the RB is not recommended since it would result in wastage of bandwidth if the subsequent cells are delayed. During the transfer of a packet to the output buffer, the incoming VCI is translated to the outgoing VCI by the merging unit. To save VC translation table space, different incoming VCIs are merged to the same outgoing VCI during the translation process if the cells are intended for the same destination. If all traffic is best-effort, full-merging where all incoming VCs destined for the same destination network are mapped to the same outgoing VC, can be implemented. However, if the traffic is composed of multiple classes, it is desirable to implement partial merging, where incoming VCs destined for the same (destination network, QoS) are mapped to the same outgoing VC. Regardless of whether full merging or partial merging is implemented, the output buffer may consist of a single FIFO buffer or multiple buffers each corresponding to a destination network or (destination network, QoS). If a single output buffer is used, then the switch essentially tries to emulate frame switching. If multiple output buffers are used, VC merging is different from frame switching since cells of a given packet are not bound to be transmitted back-to-back. In fact, fair queueing can be implemented so that cells from their respective output buffers are served according to some QoS requirements. Note that cell-by-cell scheduling can be implemented with VC merging, whereas only packet-by-packet scheduling can be implemented with frame switching. In summary, VC merging is more flexible than frame switching and supports better QoS control.
In the simulation, the arrival process to each reassembly buffer is an independent ON-OFF process. Cells within an ON period form a single packet. During an OFF periof, the slots are idle. Note that the ON-OFF process is a general process that can model any traffic process.
6]. The data collected on Feb 10, 1996, in FIX-West network, is in the form of probability mass function versus packet size in bytes. Data collected at other dates closely resemble this one.
The distribution appears bi-modal with two big masses at 40 bytes (about a third) due to TCP acknowledgment packets, and 552 bytes (about 22 percent) due to Maximum Transmission Unit (MTU) limitations in many routers. Other prominent packet sizes include 72 bytes (about 4.1 percent), 576 bytes (about 3.6 percent), 44 bytes (about 3 percent), 185 bytes (about 2.7 percent), and 1500 bytes (about 1.5 percent) due to Ethernet MTU. The mean packet size is 257 bytes, and the variance is 84,287 bytes^2. Thus, the SCV for the Internet packet size is about 1.1. To convert the IP packet size in bytes to ATM cells, we assume AAL 5 using null encapsulation where the additional overhead in AAL 5 is 8 bytes long . Using the null encapsulation technique, the average packet size is about 6.2 ATM cells. We examine the buffer overflow probability against the buffer size using the Internet packet size distribution. The OFF period is assumed to have a geometric distribution. Again, we find that the same behavior as before, except that the buffer requirement drops with Internet packets due to smaller average packet size. 8], which has been used to accurately model video traffic (Star Wars movie) in . The DAR(p) process is a p-th order (lag-p) discrete-time Markov chain. The state of the process at time n depends explicitly on the states at times (n-1), ..., (n-p). We examine the overflow probability for the case where the interarrival time between packets is geometric and independent, and the case where the interarrival time is geometric and correlated to the previous one with coefficient of correlation equal to 0.9. The empirical distribution of the Internet packet size from the last section is used. The utilization is fixed to 0.5 in each case. Although, the overflow probability increases as p increases, the additional amount of buffering actually decreases for VC merging as p, or equivalently the correlation, increases. One can easily conclude that higher-order correlation or long-range dependence, which occurs in self-similar traffic, will result in similar qualitative performance.
delays of the two systems to be consistently about one average packet time for a wide range of utilization. The difference is due to the average time needed to reassemble a packet. To see the effect of cell spacing in a packet, we again simulate the average packet delay for r_s=0.2. We observe that the difference in average delays of VC merging and non-VC merging increases to a few packet times (approximately 20 cells at high utilization). It should be noted that when a VC-merge capable ATM switch reassembles packets, in effect it performs the task that the receiver has to do otherwise. From practical point-of-view, an increase in 20 cells translates to about 60 micro seconds at OC-3 link speed. This additional delay should be insignificant for most applications.
 P. Newman, Tom Lyon and G. Minshall, "Flow Labelled IP: Connectionless ATM Under IP", in Proceedings of INFOCOM'96, San- Francisco, April 1996.  Rekhter,Y., Davie, B., Katz, D., Rosen, E. and G. Swallow, "Cisco Systems' Tag Switching Architecture Overview", RFC 2105, February 1997.  Katsube, Y., Nagami, K. and H. Esaki, "Toshiba's Router Architecture Extensions for ATM: Overview", RFC 2098, February 1997.  A. Viswanathan, N. Feldman, R. Boivie and R. Woundy, "ARIS: Aggregate Route-Based IP Switching", Work in Progress.  R. Callon, P. Doolan, N. Feldman, A. Fredette, G. Swallow and A. Viswanathan, "A Framework for Multiprotocol Label Switching", Work in Progress.  WAN Packet Size Distribution, http://www.nlanr.net/NA/Learn/packetsizes.html.  Heinanen, J., "Multiprotocol Encapsulation over ATM Adaptation Layer 5", RFC 1483, July 1993.  P. Jacobs and P. Lewis, "Discrete Time Series Generated by Mixtures III: Autoregressive Processes (DAR(p))", Technical Report NPS55-78-022, Naval Postgraduate School, 1978.  B.K. Ryu and A. Elwalid, "The Importance of Long-Range Dependence of VBR Video Traffic in ATM Traffic Engineering", ACM SigComm'96, Stanford, CA, pp. 3-14, August 1996.
Acknowledgement Funding for the RFC Editor function is currently provided by the Internet Society.