INTERNET-DRAFT A. T. Cambell, S. Kim, J. Gomez, C-Y. Wan Columbia University Z. Turanyi, A. Valko Ericsson October 1999 Expires May 2000 Cellular IP Performance Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months vand may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract Cellular IP specifies a protocol that allows routing IP datagrams to a mobile host. The protocol is intended to provide local mobility and handoff support. It can interwork with Mobile IP [1] to provide wide area mobility support. This I-D provides performance results based on the implementation and analysis of Cellular IP as defined by draft draft-valko-cellularip-01.txt [2]. The evaluation is focused on handoff performance, optimum active-state-timeout choice and scalability issues. The Cellular IP source code used for the experimental results presented in this Internet-Draft is freely available from comet.columbia.edu/cellularip. Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 1] INTERNET-DRAFT Cellular IP Performance 18 November 1999 Table of Contents 1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Implementation 3 2.1. Node Module . . . . . . . . . . . . . . . . . . . . . . . 3 2.2. Mobile Host Module. . . . . . . . . . . . . . . . . . . . 4 3. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . 4 3.1. The experiments . . . . . . . . . . . . . . . . . . . . . 4 3.2. Handoff Performance . . . . . . . . . . . . . . . . . . . 5 3.3. Active-state-timeout. . . . . . . . . . . . . . . . . . . 8 3.4. Scalability Issues. . . . . . . . . . . . . . . . . . . . 9 References 11 Authors' Addresses 11 1. Introduction Cellular IP inherits cellular technology principles for mobility management, passive connectivity and handoff support, but implements these around the IP paradigm. The universal component of a Cellular IP network is the Cellular IP node that serves as wireless access point but at the same time routes IP packets and integrates cellular control functionality traditionally found in Mobile Switching Centers (MSC) and Base Station Controllers (BSC). The nodes are built on regular IP forwarding engine, but IP routing is replaced by Cellular IP routing and location management. The Cellular IP network is connected to the Internet via a gateway router. Mobile hosts attached to the network use the IP address of the gateway as their Mobile IP care-of address. In Cellular IP, location management and handoff support are integrated with routing. To minimize control messaging, regular data packets transmitted by mobile hosts are used to establish host location information. Uplink packets are routed from a mobile host to a gateway on a hop-by-hop basis. The path taken by these packets is cached in intermediate nodes. To route downlink packets addressed to a mobile host the path used by recent packets transmitted by a mobile host is reversed. When the mobile host has no data to send then it transmits ICMP IP packets called route-updates to the gateway to maintain its downlink routing soft-state. Following the principle of passive connectivity commonly found in cellular systems mobile hosts that have not received packets for some period of time allow their downlink routes be cleared from the caches as dictated by soft-state timers. In order to route packets to idle hosts a Cellular IP mechanism called paging is used. The source code for Cellular IP v1.0 [4] developed at Columbia University is freely available (comet.columbia.edu/cellularip) for experimentation. This Internet-Draft provides an overview of the source code design and implementation. In addition, the experimental results presented in this memo are based on the public domain source code operating on a Cellular IP testbed built at Columbia University. For a full discussion of Cellular IP see [3] and for a full Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 2] INTERNET-DRAFT Cellular IP Performance 18 November 1999 specification of the protocol see [2]. 2. Implementation Cellular IP is based on modular software design and is implemented on FreeBSD 3.2 software platforms in user space. Cellular IP is comprised two protocol modules: the node and mobile host modules. Both protocol modules rely on a common system module. The system module filters IP packets from the physical medium and moves them to user space and delivers packets processed in user space to the required network interface. The system module uses the Berkeley Packet Filter's Packet Capture library (PCAP). In what follows, we describe the node and mobile host protocol modules. 2.1. Node Module As described previously, the Cellular IP node serves as wireless access point, router and location manager. In addition, our implementation allows a node to also implement the gateway functionality relying on the kernel's IP routing function. In our implementation, the uplink and downlink neighbors are configured by network management. This is in contrast to the gateway beacon approach discussed in [2]. Along with the routing and (optional) paging cache, the most important functions of the node include: - a paging update function, which maintains the paging cache by updating it for each uplink packet and by clearing expired mappings; - a classifier, which parses uplink packets and selects those that should update the routing cache (data, route-update and semisoft packets); - a route update function, which maintains the routing cache by updating it for each packet selected by the classifier and clears expired mappings; - a routing cache lookup function, which parses downlink packets and searches the routing cache for mapping(s) associated with the destination mobile host; - a paging cache lookup function, which searches the paging cache for mappings if a routing cache mapping was not found; - a forwarding engine, which forwards downlink packets to the interface selected by routing cache lookup in the first instance and by paging cache lookup if no route was found; and - a delay device, which is temporarily inserted in the downlink route if a semisoft handoff is in progress. Our implementation uses 2 Mbps 2.4 GHz WaveLAN radio devices, but the protocol module can transparently interwork with other radio interfaces. Note that the source code also works with a variety of higher speed radios (e.g., Aironet's 11 Mbps and WaveLAN IEEE 802.11 Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 3] INTERNET-DRAFT Cellular IP Performance 18 November 1999 10/6 Mbps cards). A Cellular IP node may have multiple air interfaces or no air interface at all if it serves as a concentrator node only. In addition to the functions described above, the node contains a beacon generator for each wireless interface. In Cellular IP, the content of the beacon is similar to the standard WaveLAN beacon but is extended with the gateway's IP address. 2.2. Mobile host module The mobile host module is implemented as a deamon that in our experimental testbed runs in user space. The standard IP protocol stack is not touched by the Cellular IP deamon and applications are unaware of mobility. The main elements of the deamon are as follows: - a handoff controller, which keeps statistics of measured beacon strengths and decides and performs handoff. Handoff mainly involves the setting of radio frequency and changing the IP default route to a new node's address. In the case of the semi-soft handoff mode, a semi-soft packet is first transmitted to the new base station has part of the mobile initiated handoff procedure and after a constant time delay the handoff is completed to the new base station. - a protocol state machine, which has two states: active and idle state. In idle state, any incoming packet triggers a transition to active state. At the same time, a timer is initiated that is reset by each incoming packet. The expiration of the timer triggers the transition to idle state. - a control packet generator, which periodically transmits route- update or paging-update packets as required by the state machine. The packet generator also monitors outgoing packet to stop transmitting control packets when data is being transmitted. 3. Evaluation To evaluate Cellular IP performance we have built a testbed and designed a set of experiments to analyze the Cellular IP algorithms discussed in [2]. In what follows we describe our Cellular IP testbed configuration and experimental results. 3.1 The Experiments The goal of the experiments is to evaluate the performance and scalability of the Cellular IP protocol. An important object of the first experiment is to analyze the performance of hard and semi-soft handoffs and to investigate the impact of handoff on TCP performance. The second experiment investigates the cost of setting the active- state-timeout. In the third and last experiment we investigate the scalability limits of a node based on off the shelf multi-homed PC hardware. This experiment provides some insight into what would be achievable for a Cellular IP node built from commodity hardware, operating systems and air-interfaces. The experimental results of the Cellular IP node implementation are therefore conditioned more by the technology used than the protocol itself. Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 4] INTERNET-DRAFT Cellular IP Performance 18 November 1999 | _______ ___|___ | | | | | Host | | Router| |_______| LAN |_______| _________|_______________________________|________ ___|___ | | Gateway | B1 | |_______| _________| |________ ___|___ ___|___ | | | | | B2 | | B3 | |_______| |_______| ____ | | | MH | |____| Figure 1. A Cellular IP Testbed Figure 1. Cellular IP Testbed URL:http://comet.columbia.edu/cellularip/publications/draft-gomez- cellularip-perf-00.pdf All of the experiments described below were conducted using the configuration of shown in Figure 1. The Cellular IP network consists of three nodes, all multi-homed 300 MHz Pentium PCs. One of the nodes also serves as gateway router. 100 Mbps full duplex links interconnects Cellular IP nodes and the gateway is connected to a 100 Mbps Ethernet LAN. In the experiments, the correspondent host is a Sun SPARCstation 5 with Solaris operating system. The mobile host is a 300 MHz Pentium PC notebook. The mobile host and the nodes are equipped with WaveLAN 2.4 GHz radio interfaces. These devices can operate at eight different frequencies to avoid interference between adjacent cells. In the testbed the nodes stations are statically assigned frequencies while the mobile can dynamically change frequency to perform a handoff. Throughout the experiments the mobile host is in the overlapping region of the cells which gave us full control over handoffs. We have extended the mobile host's implementation with a utility that can periodically trigger handoffs regardless of the signal strength observed at the mobile host under experiment. A handoff initiated by this utility tool is identical to a handoff triggered by signal strength measurements at the mobile host. 3.2. Handoff Performance In this experiment we measured packet loss for hard and semi-soft handoff. During these measurements the mobile host receives 100 byte Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 5] INTERNET-DRAFT Cellular IP Performance 18 November 1999 UDP packets at rates of 25 and 50 packets per second (pps) while continually making handoffs between nodes B2 and B3 every 5 seconds. The measurement results are shown in Table 1. Each point in the table was obtained by averaging loss measurements over 50 consecutive handoffs. To vary the round-trip time between the mobile host and B1, we emulate an increasing load that results in an increased buffering of downlink packets. Table 1 shows that hard handoff causes packet losses proportional to the round-trip time and to the downlink packet rate. Under these experimental conditions hard handoff results in at least 1 packet loss for small mobile to gateway round-trip delays and up to 4 packet losses for delays of 80 ms. Packet Loss per Handoff | Hard(25 pps) Hard(50 pps) Semi-soft(25 and 50 pps) _________________|____________________________________________________ Mobile-GW 3 | 0.2 0.68 0 roud-trip 43 | 1.22 2.64 0 time [ms] 83 | 2.21 4.50 0 Table 1. Downlink Packet Loss during Handoff Figure 2. Downlink Packet Loss during Handoff URL:http://comet.columbia.edu/cellularip/publications/draft-gomez- cellularip-perf-00.pdf Table 1 also shows packet loss that results from using Cellular IP semi-soft handoff [2]. The experimental conditions for semi-soft and hard handoff were identical. In these experiments, the new downlink packet stream was delayed by one buffer holding for each packet until the arrival of the next downlink packet. See [3] for full details. When the semi-soft handoff is complete, the last packet is cleared from the delay device [3] buffer and is forwarded to the mobile host. Table 1 illustrates that semi-soft handoff eliminated packet loss entirely. Note that buffering a single packet in the delay element is sufficient to eliminate loss even in the case of a large round-trip time when hard handoff resulted in the loss of up to four packets. This is because semi-soft buffering is only used to compensate for the difference between the transmission times along the old and new paths and not for the entire round-trip time between the mobile and the cross-over point. In the next experiment, we studied the impact of handoff performance on TCP Reno throughput. The mobile host performed continuous handoff between B2 and B3 at fixed time intervals. We measured TCP throughput using ttcp by downloading 16 MBytes of data from the correspondent host to the mobile host. Each data point represents an average of 6 independent measurements. TCP throughput to a mobile host performing hard handoff is shown in Table 2. The throughput measured at zero handoff frequency (i.e., under no handoff conditions) is slightly less than the 1.6 Mbps achieved using standard IP forwarding in the same configuration. This difference between IP and Cellular IP Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 6] INTERNET-DRAFT Cellular IP Performance 18 November 1999 forwarding is attributed to the fact that IP is implemented in the kernel and Cellular IP in user space. In addition, Cellular IP uses PCAP to forward packets, which is not optimized for IP forwarding. We observe that the performance of TCP degrades as the handoff frequency increases due to packet loss. As the handoff rate increases TCP has less time to recover from loss forcing it to operate below its optimal point and resulting in a significant drop in performance as the handoff rate moves toward one per second. The next experiment investigated the improvement gained using the semi-soft handoff. The experimental condition for the semi-soft and hard handoff measurements were identical. Table 2 also shows TCP throughput to a mobile host that performs semi-soft handoffs at increasing rates. Semi-soft handoff reduced packet loss and significantly improved the throughput in relation to hard handoff. Downlink TCP throughput [kbps] | Hard Semi-soft Semi-soft | (1 buffer) (8 buffer) ____________|_____________________________________________ 0 | 1500 1510 1560 2 | 1423 1426 1530 Number of 3 | 1193 1411 1520 handoffs 5 | 1120 1350 1500 per minute 10 | 1082 1345 1490 20 | 966 1300 1480 30 | 891 1232 1470 60 | 519 1036 1430 Table 2. Throughput of TCP Donwload Figure 3. Throughput of TCP Download URL:http://comet.columbia.edu/cellularip/publications/draft-gomez- cellularip-perf-00.pdf However, unlike in the UDP traffic experiment, packet loss is not entirely eliminated which is reflected in the decline of throughput at increasing handoff frequency. We attribute this to the fact that the delay we inserted in the downlink packet stream by buffering packets is tied to the packet inter-arrival time which is both shorter and more irregular in a TCP flow than in our UDP example. To introduce sufficient delay even if a few packets arrive back-to-back, we changed the semi-soft delay element to an 8-packet circular buffer. Table 2 shows the performance results using this delay element. Here, packet loss at handoff is entirely eliminated and a slight disturbance only remains due to the transmission delay variations encountered at handoff. We point out that even for one handoff per second, the throughput is almost identical to that observed for a static host. This result looks very promising. Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 7] INTERNET-DRAFT Cellular IP Performance 18 November 1999 3.3. Active-State-Timeout Now we analyze the tradeoff involved in the setting of the active- state-timeout. In Table 3, we show paging traffic rate measured in the testbed using a set of typical Internet applications. It must be noted that these values depend heavily on the user behavior and this data is presented for illustrative purposes only. Our measurements involved 4 minute sessions where the route-update time is 100 ms and a recently created route has a validity time of 300 ms. In the telnet and WWW sessions the mobile host is the client. We collected data from two sets of measurements for two different active-state-timeout values. As discussed in [2], this parameter determines the time a mobile host maintains its routing cache mappings after receiving a packet. In other words, the active-state- timeout reflects the expectation that one downlink packet may with high probability be soon followed by another and that it is worth keeping up-to-date routing information for some time, despite the cost associated with transmitting route-update packets. Indeed, as Table 3 shows, taking a larger active-state-timeout decreases the paging traffic for all applications. The difference between applications is also intuitive. An interactive application (e.g., telnet) sends one or more packets to the server triggering some action on the server side. This in turn results in new packet(s) being sent back. In the case of a local server, paging only occurs when the time to process the request exceeds the active-state- timeout. This is rare, hence the low paging rate for local telnet sessions. The packet round-trip time adds to the server processing time for remote sessions. Table 3 shows that in some cases the total response time exceeded 1 sec in this example. Rate of Paging Traffic to Mobile [bps] | telnet telnet WWW WWW VIC VIC | local remote local remote to mobile from mobile ________________|____________________________________________________ Active 100 ms | 79 391 118 1507 800 39 state 1 sec | 2 94 47 438 61 3 timeout Table 3. Paging Traffic Rate Generate by Some Applications Figure 4. Paging Traffic Rate Generated by Some Applications URL:http://comet.columbia.edu/cellularip/publications/draft-gomez- cellularip-perf-00.pdf A similar difference can be observed between the local and remote WWW sessions. In this case paging occurs when the response time exceeded the active-state-timeout. We observe that this is rare when accessing a local server but frequent in the case of remote communications. In addition, when large amounts of data are downloaded TCP sometimes stalls which also resulted in paging being triggered for any pauses that exceeded the active-state-timeout. Our final example application is VIC. With the mobile host being the receiver of the video stream, Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 8] INTERNET-DRAFT Cellular IP Performance 18 November 1999 we note that the state machine at the mobile host rarely moves to idle state since each incoming packet resets the active-state- timeout. Because of the relatively large data rate (500 kbps) in our experiment the paging rate is significant, however. We observed that when the mobile host transmits packet video then the downlink packets only carry quality of service information and paging rate is negligible. 3.4. Scalability The main concern in terms of scalability is the use of per-host routes. We believe that there has to be per-host state in the access network to support high performance handoff. In Cellular IP scalability is achieved despite per host routes by separating the location management of idle from active mobile hosts. Data packets are normally routed by route cache mappings. The size of the route cache is determined by the number of mobile hosts in active state at any one time. This way the Cellular IP network can accommodate very large number of mobile hosts without having to search large data bases for each packet and This separation principle is fundamental to scalability as per-host state is to handoff performance in a Cellular IP network. In following experiment we investigate the performance of our node implementation. Table 4 shows the node throughput for linear and binary-tree search algorithms measured on a multi-homed 300 MHz Pentium PC using ttcp and 1500 byte packets. In these measurements we substituted a 100 Mbps Ethernet connection for the radio interface and created routing cache mappings for random IP addresses to emulate a large active user population. The fact that the throughput curve is hardly decreasing with increasing routing cache size (binary-tree search) suggests that in the studied scenarios the performance bottleneck was not the cache lookup time. To verify this assumption we also measured the throughput that a single traffic stream achieved using standard IP forwarding through the multi-homed PC. As shown in Table 4, the Cellular IP node throughput is somewhat below the standard IP throughput due to the additional packet processing involved with PCAP and additional packet copies across kernel and user space domains. In our implementation, the routing cache is stored in a binary tree to achieve fast lookups. We also measured the performance of the search algorithm and found that the maximum packet rate can be well approximated as 2,500,000 ______________ 1 + 2 log(n) where n is the number of mappings in the cache. This explains that the performance bottleneck was found to be the network interface throughput rather then the search time over the range measured. For significantly larger user populations the cache lookup would likely become a bottleneck too. We did not, however, verify this thesis due to memory size constraints and unavailability of network interfaces that operated in excess of 100 Mbps. To illustrate this phenomenon we Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000 [Page 9] INTERNET-DRAFT Cellular IP Performance 18 November 1999 also experimented with linear search instead of the binary tree. The throughput measured for the linear case is presented in Table 4 and shows that when the user population exceeds 100 the cache lookup becomes the bottleneck. When the user population reaches 5000 the maximum throughput obtained is drastically diminished. Throughput [Mbps] | Linear Binary | Search Search _____________________|_________________________________ 1 | 65 63 11 | 64 62 101 | 63 62 Number of 301 | 55 62 entries in 1001 | 44 61 routing cache 4001 | 22 61 6001 | 14 61 100001 | - 60 1000001 | - 59 IP forwarding throughput = 73 Mbps. Table 4. Node Throughput. Figure 5. Node Throughput URL:http://comet.columbia.edu/cellularip/publications/draft-gomez- cellularip-perf-00.pdf The advantage of using paging is now clear from the results. If for example, a network serves n mobile hosts at a time, 0.1*n active at a time, then we can scale up the results obtained in Table 4 by a factor of 10 for example. In addition, with state-of-the-art L2 hardware Cellular IP will out perform these results in terms of the number of users that can be supported. This means that scalability limits are promising, but no doubt there are limits. However this is the price paid for the simplicity of the protocol design and smooth handoff support. This confirms the strength of Cellular IP as an access technology that can interwork with Mobile IP to provide global mobility. Another way to leverage the scalability problem created by using per-host routes is to shorten the validity times of active entries in the routing cache and/or reducing the duration that a mobile host actively keeps its route updated as in the case of active state. These two procedures further limit the number of valid entries in a routing cache thus reducing route searching times to a minimum for incoming packets. Shortening validity times of routing entries can only be achieved at the expense of increasing the transmission rate of route-update packets in mobile hosts. On the other hand, by reducing the active-state-timeout value the mobile host can limit the period of time it keeps its route updated (e.g., transmit route- update packets) after it received the last packet. Therefore a compromise between the size of the routing cache and the load of Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000[Page 10] INTERNET-DRAFT Cellular IP Performance 18 November 1999 control packets in the access network is important. For full details associated with the evaluation of Cellular IP draft-valko-cellularip-01.txt see [3] References [1] "IP Mobility Support," C. Perkins, ed., IETF RFC 2002, October 1996. [2] "Cellular IP," A. Valko, Z. Turanyi, A.T. Campbell, J. Gomez, Internet Draft, draft-valko-cellularip-01.txt, October 1999, Work in Progress. [3] "Performance of a Cellular IP", A. T. Campbell, J. Gomez, S. Kim, A. Valko, Z. Turanyi and C.-Y. Wan October 1999 (submitted for publication). [4] Cellular IP Source Code Distribution, comet.columbia.edu/cellularip, November, 1999. Authors' Addresses Andrew T. Campbell, Sanghyo Kim, Javier Gomez, Chieh-Yih Wan Department of Electrical Engineering, Columbia University Rm. 801 Schapiro Research Building 530 W. 120th Street, New York, N.Y. 10027 phone: (212) 854 3109 fax : (212) 316 9068 email: [javierg,campbell,shkim2,wan]@comet.columbia.edu Zoltan R. Turanyi, Andras G. Valko Ericsson Traffic Analysis and Network Performance Laboratory H-1300 Bp.3.P.O.Box 197, Hungary phone: +36 1 437 7774 fax : +36 1 437 7219 email: andras.valko,@lt.eth.ericsson.se, Zoltan.Turanyi@eth.ericsson.se Campbell, Gomez, Kim, Turanyi, Valko,Wan Expires May 2000[Page 11]