################################################ # # # ## ## ###### ####### ## ## ## ## ## # # ## ## ## ## ## ### ## ## ## ## # # ## ## ## ## #### ## ## ## ## # # ## ## ###### ###### ## ## ## ## ### # # ## ## ## ## ## #### ## ## ## # # ## ## ## ## ## ## ### ## ## ## # # ####### ###### ####### ## ## ## ## ## # # # ################################################ The following paper was originally published in the Proceedings of the USENIX Mobile & Location-Independent Computing Symposium Cambridge, Massachusetts, August 2-3, 1993 For more information about USENIX Association contact: 1. Phone: 510 528-8649 2. FAX: 510 548-5738 3. Email: office@usenix.org 4. WWW URL: https://www.usenix.org (From Proceedings of the USENIX Symposium on Mobile and Location-Independent Computing, Cambridge, Massachusetts, August 1993. This paper, as well as other works on real-time computer networks, is available for anonymous FTP from tenet.ICSI.Berkeley.EDU.) Providing Connection-Oriented Network Services to Mobile Hosts Kimberly Keeton, Bruce A. Mah, Srinivasan Seshan, Randy H. Katz, Domenico Ferrari {kkeeton,bmah,ss,randy,ferrari}@CS.Berkeley.EDU Computer Science Division University of California at Berkeley Abstract Mobile computers using wireless networks, along with multimedia applications, are two emerging trends in computer systems. This new mobile multimedia computing environment presents many challenges, due to the requirements of multimedia applications and the mobile nature of hosts. We present several alternative schemes for maintaining network connections used to provide multimedia service, as hosts move through a nano-cellular radio network. These algorithms modify existing connections by partially reestablishing them to perform handoffs. Using a simple analytical model, we compare the schemes on the basis of the service disruption caused by handoffs, required buffering, and excess resources required to perform the handoffs. 1.0 Introduction Two technological trends of the 1990s are the emerging use of wireless computers and network support for multimedia services. The products of these trends hold forth the promise of being combined in innovative ways to provide applications such as mobile digital video and audio conferencing. The new computing environment presented by wireless multimedia personal communication systems such as discussed in [Sheng92] introduces many challenges, because of the requirements of multimedia applications and the mobile nature of the hosts. Multimedia applications typically have strict requirements such as delay, delay jitter, throughput, and reliability bounds. Real-time network services are designed to guarantee these performance parameters to applications that request them. In order to provide these performance guarantees to individual conversa- tions, approaches such as [Ferrari92] rely on connection-oriented networks and resource reservation. Per-connection resource allocation in a connection-oriented network is necessary to ensure that guarantees will not be violated under conditions of heavy network congestion. (In connectionless network environments, congestion typically causes decreased throughput, increased delay, and even an increased probability of packet loss.) These methods, which are designed for wired networks, do not directly address the mobility of hosts. While these performance guarantees are necessary for the delivery of multimedia data to mobile hosts, our concern in this paper is not providing these guarantees, but instead maintaining the connections in use as a host moves within the network. User mobility forces networks to cope with new dynamics of routing and resource location. Generally, mobile networks are composed of a wired, packet-switching, backbone network and a wireless (e.g. cellular radio or infrared) network. The wireless network is organized into geographically-defined cells, with a control point called a base station (BS) in each of the cells. The base stations, which are attached to the wired network, provide a gateway for communication between the wireless network and the backbone interconnect. As a mobile host (MH) travels between wireless cells, the task of forwarding data between the wired network and the mobile host must be transferred to the new cell's BS. This process, known as a handoff, must maintain end-to-end connectivity in the dynamically reconfigured network topology. Since our model of network communication is connection-oriented, each of the MH's connections (or channels) and the associated connection state must somehow be transferred to this new BS. The effectiveness of the rerouting performed by the handoff algorithm is determined by several criteria. In particular, it is desirable to minimize the service disruptions (such as loss of motion due to the replay of the last frame when subsequent frames do not arrive on time) and overheads such as latency, MH and BS buffering, and excess reservation of network resources. Prior work related to host mobility does not simultaneously address the issues of connection-oriented service and de-centralized control. Much has been accomplished in the context of providing support for the Internet protocol suite in a wireless environment [Ioannidis91, Teraoka91]. However, because its net- work layer protocol (IP) is connectionless, network performance cannot be guaranteed under conditions of high load. Conversely, the cellular telephone network uses circuit switching to provide connection-oriented services. It maintains these connections during handoffs through highly centralized knowledge and control by the mobile telephone switching offices. Two straightforward solutions to the challenge of connection-oriented handoffs are forwarding data from the original BS to the new BS and establishing a new connection between the multimedia source and the new BS. Because these approaches incur considerable overheads, we propose several alternate algo- rithms that modify the existing connections by partially re-establishing them to perform handoffs. The first protocol capitalizes on the logical locality of geographically adjacent cells to partially re-establish the connections during handoff. The second uses multicast facilities to provide connectivity to the new base station when the host moves. We present a quantitative comparison of these strategies using analytically derived formulas for connection setup latency, required buffering, and excess resource reservation. We compare the algorithms and evaluate their feasibility, given the physical limitations imposed by current wireless network technology. Our basis for comparison is the case where connections are fully re-established to the source. 2.0 Environment The physical and logical aspects of the networking environment will play a large role in determining the nature of the handoff algorithms and their requirements. 2.1 Computing Environment The technologies used in the mobile system have a significant impact on the effectiveness of the handoff schemes. We have chosen several technology points, based on typical portable computers and switch-based networks, to characterize our computing environment. For instance, most mobile computers have fully func- tional CPUs, although the low-power requirements of the mobile host may limit its computational capabilities. We assume, however, that the mobile hosts contain enough processing power to run applications and the necessary communication protocols. The wireless and wired network technologies available today define various aspects of mobile communication. We assume a nano-cellular radio network (with cells less than ten meters in diameter) covering the interior of a building. Users (and hence mobile hosts) move occasionally and slowly compared to the speed of the network. Mobile hosts communicate through the radio network to a subset of the base stations; each MH can communicate with at most one BS at a time. These base stations are gateways between the radio network and a switch-based store-and-forward backbone network, and facilitate communication between the mobile hosts and multimedia servers on the backbone network. Base stations are single-homed; that is, they have only one physical connection to the wired network. For simplicity, hosts and switches are interconnected in a hierarchical topology resembling a tree. The switches support duplex connections. (For convenience we refer to the direction towards the MH as the downlink and the direction away from the MH as the uplink.) Finally we assume that the switches and BSs can be programmed to support our handoff algorithms. The characteristics of Code Division Multiple Access (CMDA) radio (< 2 GHz carrier frequency) nano-cellular networks [Schilling91] define some of the wireless communication patterns. In a radio network, there is generally considerable overlap between the cells of the network. (As stated before, however, a MH can communicate with only one BS at a time.) Each host in a radio network knows which BSs are "in range" and which of those BSs has the strongest radio signal. The relative strength of the radio signal from the current BS and the next strongest radio source gives the MH an indication of when it is close to a new cell. The MH can also use the CDMA codes to determine which cell it is approaching. However, handoff algorithms cannot rely with perfect certainty on the availability of this information. Radio networks may have null regions, areas in which a MH loses wireless contact with its BS, possibly due to interference with radio propagation. The cell overlap information cannot be completely relied upon because it may be possible to enter a null region in one cell and exit the region in a different cell. Some radio networks may also have sharp boundaries between some cells (for example, doorways). Transitions across these boundaries may occur too quickly for any advance warning to be useful. Due to these two characteristics of wireless networks, our approach uses information about an impending cell transition as a hint to improve performance, rather than as an integral component of the handoff algorithms. 2.2 Communication Paradigm We assume that the MHs will provide various multimedia services, as described in [Sheng92]. Many multimedia services, such as audio-video conferencing or video playback, have associated with them performance requirements that must be met to guarantee acceptable service to the users. [Ferrari90] describes the requirements that some typical applications place on networks. The Tenet Real-Time Protocol Suite [Ferrari92] is one approach to providing these real-time performance guarantees in packet-switching networks; this approach relies on resource reservation in a connection-oriented network environment. A connection-oriented network paradigm with per-conversation resource reservation is needed to provide performance guarantees. In a connectionless scheme, successive packets may follow different paths in the network, and hence incur different delays in reaching the destination. Packet delays in this environment are much harder to control than if all packets followed the same path, as in a connection-oriented scheme. Per-conversation resource reservation is necessary to ensure that sufficient resources are available for real-time traffic at all times, including periods of high network load and congestion. Because network resources are finite, an admission control policy must be administered, to ensure that resources are not over-subscribed. Before communication can take place, a real-time channel (a connection with performance guarantees) must be established. Channel establishment involves a single source-routed round-trip pass of control messages from the source to the destination of the connection and back. (The Tenet real-time channels are simplex unicast, but it is a fairly simple matter to support duplex real-time channels. Ongoing work is aimed at providing real-time multicast network services.) On the forward pass, admission control tests are performed to ensure that the network will be able to satisfy this channel's performance requirements without violating the guarantees of existing real-time channels. Assuming the tests succeed, node resources (such as bandwidth) are tentatively allocated, pending the acceptance of this channel at all other participating nodes. On the return pass of a successful establishment, the resources of each node are committed to the channel. [Mah93] describes in detail a mechanism and protocol by which real-time channels can be established and managed. We also assume that all connections have at most one MH as an endpoint (e.g., at least one endpoint is a fixed host on the wired network). This assumption somewhat simplifies the design of the algorithms, as they do not need to consider the case where both ends of a connection move simultaneously. 2.3 Topological Knowledge The algorithms that we present modify existing connections to perform handoffs. We call the point where a connection is modified the crossover point. Choosing this crossover point requires some knowledge of the network topology. We assume, however, that control entities have only local knowledge of the network (such as next-hop routing information); this allows them to function without needing large status updates from their peers. This assumption also prevents a single entity from making rerouting decisions independently. Therefore, multiple control entities must collaborate using a distributed algorithm to determine the crossover point. 3.0 Algorithms In this section we discuss three different schemes for handoffs in connection-oriented mobile networks. We present a Full Re-Establishment scheme as a basis for comparison. We then introduce two new algorithms, Incremental Re-Establishment and Multicast-Based Re-Establishment. The algorithms all rely on a number of pre-existing connections in the network, to be used primarily for control purposes. We assume that any two network nodes connected by a link have a control channel between them. Every pair of base stations responsible for physically adjacent cells also has a control connection between them. (We note that these base stations may not be directly connected by a physical link.) In addition, these algorithms require the BSs to buffer a bounded amount of data that has already been transmitted to the mobile host, to ensure that no data is lost when the mobile host moves to an adjacent cell. The algorithms make no attempt to re-order out-of-order packets. They will, however, attempt to prevent data from becoming out of order as the result of a handoff operation. For each algorithm, we give a short description, followed by a brief example of its application re-rerouting a single channel. We also present the optimized case which takes advantage of the cell overlap hint. In each of the examples, the MH moves from the cell whose point of control is BS 1 into the cell corresponding to BS 2. Thus, in all cases, BS 1 is considered to be the "old BS" and BS 2 is considered the "new BS". Numbered lines correspond to control messages exchanged between network entities to complete the handoff. 3.1 Full Re-Establishment The Full Re-Establishment (FR) algorithm executes handoffs by establishing a set of completely new channels between the MH and the servers. 3.1.1 Full Re-Establishment without Hints The "Without Hints" part of Figure 1 depicts the communication necessary to perform the FR scheme in the general case where the MH has no advanced warning that a handoff from BS 1 to BS 2 is about to occur. Once the MH enters the new cell, it identifies itself to the new cell's BS, BS 2, and requests that its connections be rerouted through the new BS (message labeled "1" in the diagram). Included in this greeting message is an identifier for the old BS, BS 1, as well as a list of the identifiers for the various connections originating or terminating on the MH. After BS 2 acknowledges this greeting with message (2), data transmission from the MH may begin. FIGURE 1. Full Re-Establishment In order to avoid an interruption in data service, BS 2 immediately uses the pre-existing BS-to-BS control channel to request that downlink data from each of the MH's connections be forwarded from the original BS (3). Message (3) also requests that BS 2 be allowed to forward uplink data from the MH through BS 1 to the Server. BS 1 acknowledges these requests, and may begin forwarding data to BS 2 just after (4). Once (4) has been received, BS 2 may begin forwarding data transmitted by the MH through BS 1. While this data forwarding is occurring, BS 2 begins establishing connections to each of the appropriate Servers on the network (5). Once a connection is fully established (6), the new BS informs the MH (7) and sends a message (8) to the Server requesting that it redirect all data transmissions down the newly estab- lished downlink. The downlink portion of the connection between Switch B and BS 1 is then torn down in step (9). The redirected downlink data, and the remainder of the data forwarded through BS 1 to the new BS, is buffered at BS 2 to ensure in-order delivery to the MH. Once the new portion of the connection has been established, data from the MH can flow directly to the Server over the new connection. To preserve in-order delivery of the data from the MH to the Server, this uplink data must be initially buffered at BS 2 until the uplink data forwarded through BS 1 is drained from the old portion of the connection. This buffering is proportional to the difference between the transmission delays along the new path and the forwarding/old path. Once all messages forwarded through BS 1 have been delivered to the Server, the uplink portion of the old connection is torn down (10) and uplink data may flow directly through BS 2. The handoff is completed once all of the new connections have been created and the old connections destroyed. 3.1.2 Full Re-Establishment with Hints In a radio network, the MH can take advantage of the overlap between adjacent cells to detect that it is entering a new cell before it loses contact with its current BS. This "hint" allows the MH to request that the current BS establish in advance new connections between the Servers and the new BS. This scenario is shown in the "With Hints" portion of Figure 1. At the hint time, the MH requests (1) that its current BS (BS 1) send a list (2) of active connections to the new BS (BS 2). The new BS may then establish each of the connections to the appropriate network Server (3). A successful establishment is indicated to BS 2 by the acknowledgment in step (4). During this pre-establishment, the MH ceases communications with the old BS and begins communicating with the new BS (5). As in the more general algorithm, this greeting is then acknowledged (6). Depending on how much time has elapsed, the new connections may or may not have been established to the new BS. In the best case, establishment for each of the new connections has been completed, and message (6) also notifies the MH of which connections have been established. As in the more general algorithm without hints, BS 2 then initiates a forwarding request for all of the data transmitted during the radio communication switcho- ver period on a given connection from the Server to BS 1 (7, 8). Downlink data can then be forwarded across the pre-existing channel by BS 1. However, the uplink data is not forwarded, but sent only on the newly established connection to the Server. To ensure in-order delivery of the data from the MH to the Server, this uplink data must be initially buffered at BS 2 until all of the data that was transmitted by the MH (while in the old cell) can be sent along the old connection. This buffering is proportional to the difference between the transmission delays along the two paths, taking into consideration the time for the MH to make contact with the new BS. While downlink data is being forwarded, the new BS sends a message (9) to the server requesting that data be rerouted to the new connection. Once the Server switches active connections, it begins deleting the channel to the old BS (10). After all uplink data has been transported to the Server, the old connection is completely torn down (11). If the MH arrives at the new BS before its connections have been established (but after the hint processing has begun), forwarding for both the down and uplink is initiated as in the general case with no hints. The MH is then notified as each connection is established. At this point, the new BS sends a message to the Server indicating that it may begin sending downlink data over the newly established channel. The teardown of the old channel proceeds as in the general case with no hints. If the MH does not end up fully entering the cell it was approaching but instead eventually moves out of its range, it must send another message to its original BS revoking the hint. This results in a tear-down of the connections that had been set up in anticipation of the arrival of the MH. 3.2 Incremental Re-Establishment In contrast to the FR algorithm, the Incremental Re-Establishment (IR) scheme attempts to re-use as much of an existing connection as possible, creating only the portion between the crossover point and the new cell's BS. The corresponding portion of the original connection is then torn down. 3.2.1 Incremental Re-Establishment without Hints The "Without Hints" portion of Figure 2 illustrates the application of the IR scheme in the general case where the MH has no advanced warning of the impending handoff. When the MH first arrives in a new cell, it sends a greeting message (1) to the new BS, BS 2, which contains a list of connections to be rerouted as well as the identity of the old BS. Data transmission from the MH to BS 2 begins after BS 2 acknowledges this greeting (2). As in the FR scheme, BS 2 requests that BS 1 forward the downlink and uplink data from each of the MH's connections across the BS-to-BS connection (3, 4). FIGURE 2. Incremental Re-Establishment In order to reuse a portion of the existing connection, message (3) also implicitly requests on behalf of the new BS that the old BS invoke the distributed crossover point location process. This location algorithm is initiated by the old BS because the new BS has no knowledge of the connection path to the old BS and possesses only local topological knowledge. BS 1 invokes this decision process by backtracking along the original connection route one hop at a time (5). Each switch along this route decides whether it knows the appropriate crossover point by examining its routing tables. If the switch uses different ports to reach the old and new BSs, it continues to forward this reroute message (Switches A and B in step 5). If the switch uses the same port to reach both the old and new BSs (Switch C), it knows that the switch one hop in the downlink direction (Switch B) is the crossover point. Switch C then communicates this fact to Switch B. Once the crossover point has been identified, the new portion of the connection must be established and the old portion torn down. The first step, establishing the new partial connection between the crossover point (Switch B) and the new BS (BS 2), is performed as it would be in a wired network (6). This connection is established to the MH using message (7). Assuming establishment is successful, acknowledgments are sent from the MH to BS 2 (8) and from BS 2 back along the path to Switch B (9). Message (9) is also an implicit request for Switch B to redirect all data transmitted by the Server down the newly established downlink. As in the FR algorithm, buffering at BS 2 is used to allow in-order delivery of downlink data to the MH. The downlink portion of the connection between Switch B and BS 1 is then torn down in step (10). After step (9), data from the MH can flow directly to the Server through BS 2. This uplink data is buffered at BS 2 to allow the uplink data forwarded through BS 1 to be delivered to the crossover point. Once all messages forwarded through BS 1 to the Server have been delivered to Switch B, the uplink portion of the old connection is torn down (11) and uplink data may flow over the new connection. When all new connections have been created and old connections destroyed, the handoff is complete. 3.2.2 Incremental Re-Establishment with Hints The "With Hints" portion of Figure 2 shows how the cell overlap information can be used to facilitate the handoff. The MH informs the current BS, BS 1, of the potential new BS, BS 2, and requests that new partial connections be established through the appropriate crossover points to the new BS (1). BS 1 communicates the list of connections about to be re-established to the new BS (2), and then invokes the crossover location algorithm (3). Once located, the crossover point, Switch B, begins to establish a new connection to the new BS (4). A successful establishment is indicated to Switch B by the acknowledgment in step (5). While the connection to the new BS is being pre-established, the MH moves completely into the new cell, where it identifies itself (as in the more general algorithm) to BS 2 (6) and is acknowledged (7). Analogous to the FR scheme with hints, in the optimal case where all connections are established, message (7) contains identifiers for the already-established connections. Similarly, BS 2 initiates downlink data forwarding from BS 1 (8, 9) and then requests that the crossover point redirect downlink data over the new connection (10). Again, uplink data is not forwarded through the old BS. Buffering to ensure in-order delivery of both downlink and uplink data is performed as in the FR scheme with hints, except that the endpoint of the two paths under consideration is the crossover point rather than the server. Finally, suboptimal cases are handled in a manner analogous to that of the FR scheme with hints. 3.3 Multicast-Based Re-Establishment To support video conferencing and other distributed applications, some networks support multicast connections with dynamically changing memberships. The use of multicasting has several interesting ramifications. Because data for the downlinks are transmitted simultaneously to multiple base stations during the interim, the actual switchover can be fairly quick, with decreased buffering. This scheme also has an advantage in that only a small layer of functionality needs to be added on top of the multicast facility in order to support mobility. 3.3.1 Multicast-Based Re-Establishment without Hints The "Without Hints" diagram in Figure 3 illustrates the operation of the MB handoff algorithm. The MH detects that it is entering a new cell, so it acquires a wireless channel to the new BS, BS 2, and sends it a greeting message (1). This message contains an identifier for the old BS, BS 1, as well as a list of the identifiers for the various multicast channels originating or terminating on the MH. This greeting is immediately acknowledged by BS 2 (2). BS 2 then sends this channel list to the old BS along the pre-existing BS-to-BS connection (3), requesting that all data for each channel be forwarded to the new BS. In addition, BS 2 requests that it be allowed to forward data from the MH through BS 1. Upon receipt of an acknowledgment (4), BS 2 begins transferring forwarded data from BS 1 to the MH and forwarding MH data destined for the server. FIGURE 3. Multicast-Based Re-Establishment Concurrently with the forwarding requests, BS 2 executes a multicast join operation (which establishes a new branch connecting BS 2 with the existing channel) for each existing channel to add itself to the multicast channel (5). Upon receiving an acknowledgment indicating a successful establishment (6), the new BS notifies the MH of the successful join operation (7). BS 2 synchronizes the data arriving down the new branch with the data being drained from the old BS. To preserve in-order delivery of the data from the MH to the server, this data must be initially buffered at BS 2 until the data forwarded through BS 1 is drained from the old portion of the connection. When all of the multicast joins have completed and all necessary data have been obtained from the old BS, the new BS sends a completion message to the old BS (8) over the control connection. At this point, BS 1 can assume that it has no more responsibilities to the MH, and so it executes a multicast leave operation for each of the channels associated with the MH (9, 10). This operation deallocates node resources along the path from the BS to the first node in common with another branch of the multicast channel. The handoff is complete after the last branch has been torn down. 3.3.2 Multicast-Based Re-Establishment with Hints The "With Hints" diagram in Figure 3 illustrates the advance setup the network performs in response to the hint and a best case scenario for an ensuing handoff. The hint is delivered as a message to BS 1 (1) identifying the potential new BS, BS 2. BS 1 then notifies BS 2 (2) that it should initiate multicast join operations to all of the MH's channels in anticipation of a handoff (3, 4). When the MH loses contact with BS 1 and enters BS 2's cell, it identifies itself with BS 2 as before (5). Due to the hint, BS 2 will have already initiated joins for all of the channels associated with the MH. When the joins have been successfully completed, BS 2 notifies the MH (6) and drains any data buffered for the MH. Finally to complete the handoff, BS 2 sends a com- pletion message to BS 1 (7), which then executes a multicast leave operation for each MH channel (8, 9). Buffering requirements on the BSs are similar to the FR and IR algorithms with hints. 4.0 Analysis In this section, we describe our analysis of the algorithms. We use an analytical model of the algorithms and a characterization of the network to compute the values of various metrics describing the overheads involved in connection rerouting. 4.1 Parameters and Metrics We use a set of technology-dependent parameters, shown in Table 1, to characterize the network. We assume no contention for link bandwidth or other network resources. Third generation wireless networks are capable of supporting megabit per second speeds, and current experimental LANs support gigabit per second bandwidths. Protocol processing time is assumed to be constant except in the case where admission control tests need to be performed, as Tenet-style admission control tests are processing intensive (e.g., 25 ms on a RISC workstation like a DEC 5000/240). We have placed an upper bound of 50 Bytes on control messages, as they generally contain a small, fixed amount of information. (Channel establishment messages may be much larger, however.) The maximum data packet size is chosen to be 8 KBytes, which is an average packet size in many typical local area networks. Finally, the time taken to acquire a wireless channel is dependent on the actual wireless network system in use. Symbol Definition Value ------ ---------- ----- BWwl Bandwidth of the wireless link. 1 Mbps [Schroeder92] BWw Bandwidth of the wired backbone net- 1 Gbps [Brodersen93] work. Lwl Latency of the wireless link, including 7 ms [Brodersen93] data link and network layer processing. Lw Latency of a link in the wired backbone, 500 ms [Zhang92] including data link and network layer pro- cessing. PPTfixed Protocol processing time for control 3 ms messages. PPTadm Protocol processing time for steps where 25 ms admission control is to be performed, in excess of fixed protocol processing time. Sctrl Upper bound on the size of a control 50 bytes message. Sdata Maximum size of a data packet. 8192 bytes Tacquire Time for a MH to acquire a wireless chan- 20 ms [Brodersen93] nel to a base station. TABLE 1. Technology-Dependent Network Parameters Each network connection to and from a mobile host at the time of handoff can be characterized by the set of parameters listed in Table 2. These parameters are dependent on the locations of the mobile host and its multimedia servers, as well as the topology of the network. By varying these parameters, we can examine the overheads associated with each rerouting algorithm over varying lengths of connections. Symbol Definition ------ ---------- Hnew Number of hops to the crossover point from the new (destination) BS. Hold Number of hops to the crossover point from the old (original) BS. Hctrl Number of hops between the old and new BSs along their control channel. Hserver Number of hops between a MH and its multimedia server. TABLE 2. Parameters Characterizing Network Connections. We can measure the performance of the various handoff algorithms using the metrics listed in Table 3. The values of these metrics, evaluated for a given set of technology-dependent parameters and various parameters of network connections, will give some idea of the effectiveness of the different schemes. Tdisrupt corresponds to the service disruption time, that is, the time during which the MH cannot receive data on its downlink. (This disruption may manifest itself as a pause in the playback of video.) Bmh, Bbs,down, and Bbs,up correspond to the buffering required on the MH and the BS to prevent data from becoming out of order as a result of a handoff operation. The bandwidth-space-time products are one measure of the added network resources required to do the handoff. They are essentially the product of the bandwidth provided to a connection, multiplied by the length of the connection and the amount of time that the connection is in existence. Pexcess measures the network resources that are allocated to inactive connections (for example, a channel or portion of a channel that has been established but is not being used to carry data). Pfwd is a measure of the network resources reserved for the forwarding of packets between adjacent BSs during handoff. Symbol Definition ------ ---------- Tdisrupt Service disruption time, the time during which the MH cannot receive data on its downlink. Bmh Buffering required on the MH for buffering of uplink data during handoff. Bbs,down Buffering required in the BSs for buffering of downlink data during handoff. Bbs,up Buffering required in the new BS for buffering of uplink data during handoff. Pexcess Excess bandwidth-space-time product used by inactive channels during handoff. Pfwd Bandwidth-space-time product used by data being forwarded during handoff. TABLE 3. Metrics for Comparing Handoff Algorithms 4.2 Derivation of Metrics We now present the derivation of the metrics listed in Table 3 for the Incremental Re-Establishment algorithm, in the case that there are no hints regarding advance warning of a handoff. The metrics for the other handoff algorithms can be derived in a similar way. Due to space limitations, these derivations are not presented here. This analysis assumes perfect delivery of control messages. (An analysis of the general case in which control messages can be lost during the handoff is an exercise in protocol verification which we intend to address in the future.) We also assume that the maximum throughput for a connection is the throughput of the bandwidth of the wireless link. All of our computations for buffering requirements are derived on a per-channel basis, with the worst case being that in which the channel's throughput is equal to the wireless link's total bandwidth. We compute the time taken for each of the scheme's control messages to be transmitted, forwarded, and if necessary, processed. Message numbers for this section are those from Section 3.2.1 and Figure 2. Message (1) is a greeting from the MH to the BS in the new cell. The latency needed for this message is the sum of the time to acquire a wireless channel, the transmission time of a control message on that channel, the propagation time on the wireless link, and the fixed protocol processing time on the new BS. T1 = Tacquire + (Sctrl/BWwl) + Lwl + PPTfixed (1) Message (2) is an acknowledgment of the greeting back to the mobile host; its total delay is simply the sum of the transmission and propagation times, plus processing time in the mobile host. T2 = (Sctrl/BWwl) + Lwl + PPTfixed (2) Immediately after sending Message (2), the new BS sends a request (3) for forwarding of both uplink and downlink data to the old BS, using the control channel between the two (physically) adjacent base stations. Its total latency is the end-to-end delay through the control channel plus the fixed protocol processing time in the old BS. T3 = [(Sctrl/BWw) + Lw] * Hctrl + PPTfixed (3) The next message, Message (4), is an acknowledgment of the forwarding request, sent from the old BS to the new BS. Its total latency is computed similarly to that of Message (3). T4 = T3 = [(Sctrl/BWw) + Lw] * Hctrl + PPTfixed (4) Immediately after sending Message (4), the old BS begins the distributed crossover point location process (5). The messages needed to find the crossover point will incur a latency () equal to the transmission and propagation time along each hop, plus the fixed control protocol processing time in each switch along the path from the old BS to the crossover point. We note that the PPTfixed term in each hop's latency is necessary because, in contrast to Messages (2) and (3), the switch controller at each hop needs to do some processing of the control message (specifically, to determine whether it knows the crossover point). T5 = [(Sctrl/BWw) + Lw + PPTfixed] * Hold (5) Message (6) is a partial channel establishment from the crossover point to the new BS. Admission control tests need to be executed at each switch along this path, which implies a delay of PPTadm at each hop in addition to the normal PPTfixed required for normal control message processing. T6 = [(Sctrl/BWw) + Lw + PPTfixed + PPTadm] * Hnew + PPTadm (6) Message (7) completes the partial channel establishment from the new BS to the mobile host; therefore the bandwidth and link latency are those of those of the wireless link. T7 = (Sctrl/BWwl) + Lwl + PPTfixed + PPTadm (7) Message (8) is the acknowledgment of the partial channel establishment across the wireless link. T8 = T2 = (Sctrl/BWwl) + Lwl + PPTfixed (8) Acknowledgment of the partial channel establishment (back to the crossover point) is completed by Message (9). This control message retraces the path of the partial establishment, hop by hop. T9 = [(Sctrl/BWw) + Lw + PPTfixed] * Hnew (9) Message (10) begins the teardown of the partial connection from the crossover point to the old BS. As with the Message (5), it must travel hop by hop between switch controllers. T10 = T5 = [(Sctrl/BWw) + Lw + PPTfixed] * Hold (10) A final message, Message (11), is sent from the old BS to the crossover point to complete the teardown of the old leg of the connection. The delay incurred by this message is computed identically to that of Message (10). T11 = T10 = [(Sctrl/BWw) + Lw + PPTfixed] * Hold (11) Using the time spent transmitting, forwarding, and processing each of the control messages, we can compute the values of the various metrics. Tdisrupt, the amount of time during which network service on the downlink to the MH is disrupted, is the time the MH needs to acquire a wireless channel, have the new BS arrange for data forwarding, and for the MH to receive the first forwarded data packet. Tdisrupt = T1 + (Sctrl/BWwl) + T3 + T4 + (Sdata/BWwl) + Lwl (12) The amount of buffering required by the MH is determined by the amount of time during which the MH cannot transmit data on its wireless uplink. This includes the time for the MH to greet the new BS and the time for the new BS to acknowledge the greeting. Bmh = (T1 + T2) * BWwl (13) The amount of buffering required on the old BS for downlink buffering is determined by the amount of data that will need to be "replayed" to the MH through the forwarding channel and the new BS. This data is precisely that which would have been received while the new BS was arranging for data forwarding from the old BS and waiting for the corresponding acknowledgment, plus the data that was being transmitted along the wireless link from the old BS to the MH when the MH moved into the new cell. We assume that the first forwarded data packet immediately follows the acknowledgment of the forwarding request (Message 4). Bbs,down = [T1 + (Sctrl/BWwl) + T3 + (Sctrl/BWw) + Lwl] * BWwl (14) The amount of uplink buffering needed on the new BS is influenced by two terms. The first is the time to establish forwarding (minus the time taken to send the acknowledgment for the MH's greeting and the time needed for the first data packet to be arrive at the new BS). The other term is the difference in the delay between the paths going through the old and new base stations. In the case where a network offers deterministic (or perhaps even statistical) delay bounds [Ferrari92], it would be possible to use those values in this derivation. Bbs,up = max( T3 + T4 - (2Lwl), [Lw + (Sdata/BWw)] * max(Hctrl + Hold - Hnew, 0)) * BWwl (15) The amount of excess bandwidth-space-time product is given by the amount of network resources allocated but not in use. This includes the bandwidth used by the channel between the new BS and the crossover point during establishment of the new partial connection and subsequent acknowledgments and the bandwidth used by the channel between the old BS and the crossover point after the switchover and before that connection has been completely deleted. Pexcess = ({(Hnew^2 + Hnew)/2} * [(Sctrl/BWw) + Lw + PPTfixed + PPTadm] + (T7 + T8 + T9) * Hnew + T10 * Hold + {(Hold^2 + Hold)/2} * [(Sctrl/BWw) + Lw + PPTfixed]) * BWwl (16) The bandwidth-space-time product required for forwarding data from the old BS to the new BS during handoff is dictated by the amount of data that needs to be forwarded. Pfwd = [T1 + (Sctrl/BWwl) + T3 + (Sctrl/BWw) + T5 + T6 + T7 + T8 + T9 + ((Sdata/BWw) + Lw) * Hold + ((Sdata/BWwl) + Lwl)] * BWwl * Hctrl (17) 4.3 Comparison of Schemes We have derived formulae for the performance metrics for the FR, IR, and MB algorithms, with and without the availability of hints regarding advance warning of a handoff. Substituting the values listed in Table 1 into these formulae provides the framework for our analysis. We have varied values from Table 2 to obtain values for the performance metrics listed in Table 3. Hserver was fixed at six hops, while both Hnew and Hold were varied from one to six hops, to simulate the choice of a crossover point anywhere along the path from the base stations to the server. Depending on the size and organization of the switches, the diameter implied by such a network may be as large as a small campus. For simplicity, Hnew and Hold were chosen to be equal for each experiment. Hctrl was chosen to be twice the distance between the crossover point and the old or new BS. For the cases where the algorithms use cell overlap hints, we assume that the MH sends the hint to the old BS one second before it enters the new cell. This value is consistent with the relatively slow movement of users. 4.3.1 Performance Results for Incremental Re-Establishment We present a discussion of the performance results of the FR, IR and MB algorithms, both with and without hints. Graphical results are presented, however, only for the IR scheme. Our analysis of the algorithms using hints assumes the best case, where all connections have been established by the time the MH enters the new cell. FIGURE 4. Service Disruption Times for Incremental Re-Establishment Figure 4 shows the service disruption time in the delivery of downlink data for the IR scheme. Because this metric is dependent on the time to set up data forwarding, it is highly dependent on Hctrl, the number of hops in the path between the old and new BSs. The service disruption time is the same for both the case with and without hints since both request forwarding of downlink data. More generally, because forwarding of downlink data is requested in both FR and MB without hints as well as in FR with hints, the service disruption time for those algorithms is identical to that shown in Figure 4. MB with hints, which does not request downlink forwarding, yields a constant service disruption time, which is longer than the disruption shown in the figure for Hold = Hnew = Hctrl/2 = 1, but shorter than the disruption time for larger hop counts. FIGURE 5. Mobile Host Buffering Requirements for Incremental Re-Establishment Figure 5 displays the mobile host buffering required to temporarily store uplink data from the MH during the time which it is out of communication with any BS. Because this time includes only the greeting message and acknowledgment, the buffering required at the MH is constant over all crossover point topologies with or without the availability of hints. Because of its definition, the MH buffering is constant over all of the handoff algorithms for all combinations of topology and hint availability. FIGURE 6. Base Station Buffering Requirements (Downlink) for Incremental Re-Establishment Figure 6 illustrates the buffering required on the base station for downlink data. As in the case for service disruption, this metric is highly dependent on the time required to initiate data forwarding from the old BS to the new BS. Because each scheme (with the exception of MB with hints) requests this forwarding, the buffering requirements shown in Figure 6 apply to all of these schemes. The constant downlink BS buffering required for MB with hints (to buffer data sent over the radio communication switchover period) is several thousand bits less than that required for the case of Hold = Hnew = Hctrl/2 = 1 shown in the figure. FIGURE 7. Base Station Buffering Requirements (Uplink) for Incremental Re-Establishment The buffering required on the base station for uplink data is shown in Figure 7. For the case when hints are unavailable, this quantity is given by the maximum of the time to set up forwarding and the difference in propagation times to the crossover point along the uplink forwarding path and the new uplink path. Thus, the uplink buffering requirements are directly proportional to the number of hops along the forwarding path between the old and new BSs. The buffering requirements for FR and MB without the availability of hints are identical to those shown without hints in Figure 7. With the availability of hints, none of the algorithms forward uplink data; as a result, the uplink buffering requirements with hints are dependent only on the difference in propagation times to the crossover point along the old and new uplink paths, including the time for the MH to switch cells. Because of the constant relationship between the hop counts used here, this difference is non-positive. Hence, there is no buffering required for uplink data in the hinted IR, FR, and MB cases. FIGURE 8. Excess Bandwidth-Space-Time Utilization for Incremental Re-Establishment Figure 8 diagrams the amount of bandwidth over all links consumed by channels established, but not in use, during a handoff. This value also reflects the duration for which these resources are held. As expected, the excess resources consumed for the case where hints are available exceed those used for the non-hinted case, because the new channel is established in advance through the use of the hint. This effect is magnified as the distance from the crossover point increases because the amount of excess resources held grows as the square of both Hold and Hnew. This same behavior is exhibited by the MB algorithm. Because the resources reserved for the FR scheme are dependent only on the distance between the BS and the server, the plot of Pexcess for FR is constant for both the non-hinted and hinted cases. The use of hints in the IR algorithm results in a nearly ten-fold increase in the resources reserved, but not used, in satisfying a handoff. This factor is highly dependent on the choice of the time value representing how far in advance the hint is received before the MH actually moves into the new cell. FIGURE 9. Forwarding Bandwidth-Space-Time Utilization for Incremental Re-Establishment The amount of bandwidth-link-time resources consumed to perform forwarding is shown in Figure 9. The plots for the cases both with and without hints grow as the distance from the crossover point increases. This behavior is due to the fact that as Hctrl increases, the number of links used to perform forwarding grows. In addition, the amount of data to be forwarded (or time that the resources will be consumed) grows as the time to set up the forwarding increases. The resources used in forwarding data for the case with no hints exceed those used in the case with hints because data must be forwarded during connection establishment for the former scheme. The use of hints results in a decrease in the resources consumed by a factor of two (for small values of the network topology parameters) to three (for larger hop count parameters). This behavior is also exhibited for the FR and MB schemes without hints and the FR scheme with hints. No data is forwarded for the hinted MB scheme. 4.3.2 Analysis of Bandwidth-Space-Time Utilization FIGURE 10. Excess Bandwidth-Space-Time Utilization for All Schemes (Without Hints) We next compare the bandwidth-space-time metrics of Pexcess and Pfwd for the three handoff algorithms. As noted before, these metrics measure the amount of bandwidth used over all of the links and the duration of that bandwidth's use. Figure 10 shows the excess bandwidth consumed during a handoff which proceeds without the availability of hints. Because the resources reserved for the FR scheme are dependent only on the distance between the BS and the server, it does not vary significantly with the length of the control channel. The IR and MB algorithms, however, require increasing amounts of excess bandwidth as the paths from the base stations to the crossover point gets longer. As shown in the figure, a considerable (e.g., five-fold or more) reduction in the resources consumed is possible with the use of the IR or MB algorithms instead of FR for topologies with crossover points close (i.e., within one or two hops) to the BSs. This reduction also depends on the pre-existing control path between BSs being relatively short. FIGURE 11. Excess Bandwidth-Space-Time Utilization for All Schemes (With Hints) Figure 11 shows the corresponding values of Pexcess in the case that hints of upcoming handoffs are available. The bandwidth space-time product is linear for FR, as the time to set up the new connection from the new base station to the server is constant for all cases examined. For IR and MB, however, the length of the channel establishment varies, resulting in the nearly linear increase in Pexcess. Again, the use of IR or MB over FR results in a considerable reduction (e.g., by a factor of three to seven) in resource consumption when the crossover point is close to the BSs and the BS-to-BS control path is relatively short. FIGURE 12. Forwarding Bandwidth-Space-Time Utilization for All Schemes (Without Hints) In Figure 12, the values of Pfwd are shown for all algorithms, assuming no advance warning hints are available. As the length of the required channel establishment is constant, the forwarding bandwidth needed to support the FR algorithm is roughly linear with the length of the control channel. However, the length of the control channel is proportional to the length of the channel establishment required for the IR and MB algorithms. The result is that Pfwd for the IR and MB schemes increases roughly with the square of the length of the control connection. As for previous metrics, the use of IR or MB over FR for a network with logically adjacent BSs and crossover points decreases the amount of resources consumed in forwarding data. This decrease is 30 to 50 per cent for cases when Hold = Hnew = Hctrl/2 is one or two. FIGURE 13. Forwarding Bandwidth-Space-Time Utilization for All Schemes (With Hints) Values of Pfwd for all three algorithms using hints are shown in Figure 13. We note that Pfwd is zero for the hinted scenario applied to the MB algorithm, as no forwarding of data is done in this case. The forwarding resource consumption for FR and IR differ only in the amount of work that must be done to delete the old channel. In the cases where the crossover point is close to the BSs, IR offers a 12 to 15 per cent decrease in resource consumption over FR. 4.3.3 Summary of Results When compared on the basis of service disruption time, MH buffering, or BS buffering, the FR, IR, and MB algorithms are not significantly different. One exception is the case where MB uses hints to perform a handoff, as it does not request downlink data buffering. The algorithms are significantly different, however, on the basis of excess resource consumption and resource consumption for forwarding downlink data. Using these metrics, the MB algorithm generally performs better than the other two schemes studied, for both the cases in which hints were and were not available. MB outperforms FR due to the decreased size of the channels that it must manage. It is more efficient than IR in that it does not require as complicated a channel establishment scheme. The effects of hints on the performance of the algorithms was striking. Depending on how far in advance a hint is available before the MH moves, the excess resources necessary to complete the handoff may be significantly greater than those needed in the case where hints are not available. However, the use of hints can result in a two- to three-fold decrease in the resources necessary to forward data. In addition, the use of hints may significantly decrease the amount of BS buffering required to support in-order delivery of uplink data. These results also show that the effects of network topology are important. If the network is constructed such that the paths between the BSs and the crossover points are short, significant reductions in the resources required for handoffs may be realized for the IR and MB algorithms over the more naive FR algorithm. This effect is also dependent on the distance between physically adjacent BSs, as control data and forwarded data must travel along this path. These results suggest that it is advantageous to place physically adjacent base stations logically close together in the wired network topology used to support mobile hosts. 5.0 Conclusions Two recent trends in computer systems are multimedia applications and mobile computing devices. A combined multimedia, mobile computing environment poses new problems in networks. Multimedia applications typically require certain qualities of service from network services; real-time network services require connections in order to provide real-time performance guarantees. In order to provide such services in a network with mobile hosts, the network must reroute connections as hosts move between cells. We present several schemes for supporting connection-based services in mobile networks. As a basis for comparison, we use a Full Re-Establishment algorithm, which establishes entirely new connections every time a host moves. In contrast, we present the Incremental Re-Establishment algorithm, which modifies an existing connection by establishing only the portion of the channel between the base station and the node where the old and new channels would diverge. Our Multicast-Based scheme relies on network-layer multicasting to deliver data to more than one base station during a handoff. We have performed an evaluation of these handoff schemes using a simple analytically derived model. Our analysis of these algorithms implies that new schemes for re-establishing connections in mobile networks can provide improved performance compared to naive algorithms. In particular, the use of multicast services to support mobile host handoff may yield considerable benefits. The use of cell overlap information to facilitate handoffs may greatly reduce the amount of buffering required, at the cost of an increase in the excess resources consumed in satisfying the handoff. Our results also show that network topology is an important consideration in the design of mobile, connection-based networks. In particular, it is advantageous if physically adjacent base stations can be located with logical locality in the network. 6.0 Future Work Since the human eye can easily interpolate missing video information, we will explore the possibility of eliminating the forwarding of downlink data during a handoff. We anticipate that this will have a significant impact on the service disruption time, resource consumption, and potentially BS buffering. In addition, we will examine our algorithms' behavior in cases where the full benefit of hints cannot be used (for example, if a cell transition follows its corresponding hint so closely that the network does not have time to complete all the processing of the hint). We are currently completing the construction of a trace-driven simulator using the Ptolemy simulation environment [Buck92], which will be used to evaluate the algorithms' performance. In addition, the simulation will quantify the system's capacity for supporting mobile hosts and processing handoffs for a variety of user data traffic and user movement patterns. We also plan to use protocol analysis software such as Spin [Holzmann91] to formally verify the correctness of the FR, IR, and MB protocols. Making physically adjacent base stations logically close means that any changes in connection state (such as rerouting) will take place close to the handoff site, and that the effect on the rest of the network should be minimized. Our longer term research plans include studies of network topology and real-time guarantees. Much of the work done on providing real-time guarantees using resource reservation needs to be modified to support rerouting as in [Parris92]. We hope to investigate how to incorporate real-time guarantees into our handoff algorithms. 7.0 Acknowledgments The authors gratefully thank Ron Widyono of UC Berkeley and Doug Terry of Xerox PARC for their helpful comments and suggestions. This research was supported by the Department of Energy under grant DE-FG03-92ER25135/A000, by the National Science Foundation and the Defense Advanced Research Projects Agency (DARPA) under Cooperative Agreement NCR-8919038 and by the Corporation for National Research Initiatives, AT&T Bell Laboratories, Hitachi Ltd., Hitachi America Ltd., Pacific Bell, the University of California under a MICRO grant, and the International Computer Science Institute. Kimberly Keeton was supported by an AT&T Graduate Fellowship, and Bruce A. Mah was supported by an NSF Graduate Fellowship. 8.0 References [Brodersen93] R. Brodersen, personal communication, Berkeley, CA, June 1993. [Buck92] J. Buck, et al. "Ptolemy: A Framework for Simulating and Prototyping Heterogeneous Systems," International Journal on Computer Simulation, special issue on "Simulation Software Development", 1992. [Ferrari90] D. Ferrari. "Client Requirements for Real-Time Communication Services", IEEE Communications Magazine, Vol. 28, No. 11, November 1990, pp. 65-72. [Ferrari92] D. Ferrari, A. Banerjea, and H. Zhang. "Network Support for Multimedia-A Discussion of the Tenet Approach", Tech. Rept. TR-92-072, International Computer Science Institute, Berkeley, CA, November 1992. [Holzmann91] G. Holzmann. Design and Validation of Computer Protocols, Prentice-Hall, Englewood Cliffs, NJ, 1991. [Ioannidis91] J. Ioannidis and G. Maquire, Jr. "The Design and Implementation of a Mobile Internetworking Architecture", Proc. 1993 Winter USENIX, pp. 491-502. [Mah93] B. Mah. "A Mechanism for the Administration of Real-Time Channels", MS Report, Tech. Rept. UCB/CSD-93-735, University of California, Berkeley, CA, March 1993. [Parris92] C. Parris, H. Zhang, and D. Ferrari, "A Mechanism for Dynamic Re-routing of Real-time Channels", Tech. Rept. TR-92-053, International Computer Science Institute, Berkeley, CA, August 1992. [Schilling91] D. Schilling, et al. "Broadband CDMA for Personal Communications Systems", IEEE Communications Magazine, Vol. 29, No. 11, November 1991, pp. 86-93. [Schroeder92] M. Schroeder, personal communication, Berkeley, CA, October 1992. [Sheng92] S. Sheng, A. Chandrakasan, and R. Brodersen. "A Portable Multimedia Terminal", IEEE Communications Magazine, Vol. 30, No. 12, December 1992, pp. 64-76. [Teraoka91] F. Teraoka, Y. Yokote, and M. Tokoro. "A Network Architecture Providing Host Migration Transparency," Proc. SIGCOMM '91, pp. 209-220. [Zhang92] H. Zhang and T. Fisher. "Preliminary Measurement of the RMTP/RTIP", Proc. Third International Workshop on Network and Operating System Support for Digital Audio and Video, San Diego, CA, November 1992.