Chapter 12: Handoff and Rerouting in Cellular Data Networks

Gopal Racherla and Sridhar Radhakrishnan

12.1 Introduction

Cellular mobile data networks consist of wireless mobile hosts (MH), static hosts (SH), and an underlying wired network consisting of base stations (BS) and intermediate routers. Each base station has a geographical area of coverage called a cell. Hosts communicate with each other using the base stations and the underlying wired network. Figure 12.1 shows the architecture of a cellular data network. The figure shows the fixed cellular backbone consisting of base stations and a group of mobile hosts that can move from one cell to another. When a mobile host moves from one cell to another, it registers with the base station of the new cell. If there is an ongoing communication session between two hosts and one of the hosts moves out of its present cell, the session is interrupted. In order for the session to be restarted, a handoff or handover needs to take place in the network. Handoff is the process of transferring the control and responsibility for maintaining communication connectivity from one base station to another. Handoff is used by the mobile network to provide the mobile hosts with seamless access to network services and the freedom of mobility beyond the cell coverage of a base station. Rerouting is the process of setting up a new route (path) between the hosts after the handoff has occurred. Handoff ^[1], ^[2], ^[3], ^[4], ^[5], ^[6] in mobile and wireless networks has been an active topic of research and development for the past several years. The rerouting problem also has been studied extensively in cellular, mobile, and wireless networks, including wireless ATM, ^[7], ^[8], ^[9], ^[10], ^[11], ^[12], ^[13] picocellular networks, ^[14] cellular networks, ^[15] wireless LANs, ^[16], ^[17], ^[18] and connectionless networks. ^[19], ^[20], ^[21], ^[22], ^[23]

Figure 12.1: Architecture of a cellular data network.

Communication in a mobile data network can be either between two static hosts (static-static), a static host and a mobile host (static-mobile), or two mobile hosts (mobile-mobile). Static-static communication and its related routing algorithms have been studied extensively in the literature. Static-mobile communication and the consequent handoff and rerouting also have been studied in detail. ^[24], ^[25], ^[26], ^[27], ^[28] However, mobile-mobile rerouting has not been explored much in the literature. There are only a few ^[29], ^[30], ^[31] suggested schemes for mobile-mobile data communication and rerouting in mobile data networks. However, these mobile-mobile rerouting schemes are suboptimal. In addition, these schemes do not look at different rerouting strategies. Racherla and coworkers ^[32] have proposed a scheme for performing optimal rerouting in mobile-mobile networks.

In this chapter, we survey, classify, analyze, and evaluate several known rerouting (static-mobile and mobile-mobile) techniques for connection-oriented cellular data networks. We study connection-oriented networks as they provide performance guarantees needed for delivery of multimedia data to mobile hosts. We classify the various rerouting schemes in four major categories and do a survey of related work in detail. We use a set of rerouting metrics in order to compare and classify various static-mobile and mobile-mobile rerouting schemes. We discuss the characteristics and performance metrics used for the comparison of static-mobile and mobile-mobile rerouting in more detail later in the chapter.

The rest of the chapter is organized as follows. In this section, we continue to explore the nuances of the rerouting process in more detail. We study the characteristics of rerouting and use them for comparison and classification of rerouting schemes proposed in the literature. We classify various rerouting schemes in four categories. In Section 12.2, we analyze and evaluate the various rerouting classes. Each class is explained in detail, including the protocol used for rerouting, the advantages and disadvantages of the class, and implementation examples and variations of the rerouting class. In Section 12.3, we evaluate the rerouting schemes using several performance metrics that are calculated using analytical cost modeling. We study the issues involved in mobile-mobile rerouting, including potential problems and solution ideas for alleviating these problems, as well as all the known solutions for rerouting in mobile-mobile connections, in Section 12.4. In Section 12.5, we compare these schemes using several performance metrics including the total rerouting distance, the cumulative connection path length and the number of connections as the mobile hosts move. Finally, in Section 12.6, we present our conclusions and the plan for future work.

12.1.1 Classification of Rerouting Schemes

Rerouting in cellular mobile environments occurs as result of a handoff. When a mobile host moves from one cell to another, a handoff is said to have taken place. In order to maintain communication connectivity, packets have to be rerouted to and from the MH. This process of reestablishment of a route (connection) is called as rerouting. Figure 12.2 depicts the rerouting process. Initially, the source mobile host (MH_s) is in a session with the destination mobile host (MH_D). MH_S is in the cell being administered by source base station (BS_S). After some time, MH_D moves from the cell of BS_old to BS_new after performing a handoff while MH_s is stationary. The old route (between BS_s and BS_old) and the new route (between BS_s and BS_new) may be the same, partially the same or completely different. Because of overlaps in the cell coverage of adjacent cells, MH_D may get a radio "hint" before it enters its cell. Using the radio hint, MH_D can request BS_old to inform BS_new to set up the required connections in advance. This mechanism of using radio hints is known as radio hint processing.

Figure 12.2: Rerouting process.

We classify the rerouting strategies broadly as full rerouting, partial rerouting, tree-based rerouting, and cell forwarding rerouting. Each of the schemes can be either with or without a radio hint. ^[33], ^[34], ^[35] Full rerouting involves establishing a new routing path from BS_new to BS_S. Full rerouting schemes are slow and inefficient and hence perform poorly. Examples of such schemes include full reestablishment without hints and full reestablishment with hint rerouting. ^[36] Partial rerouting involves finding the crossover point of the route between BS_S and BS_old and the route between BS_S and BS_new with a view to increasing route reuse. Examples of these schemes include incremental reestablishment without hints and incremental reestablishment with hint rerouting ^[37], ^[38] and Nearest Common Neighbor Routing (NCNR). ^[39] Tree rerouting involves routing using a tree-based structure for communication. The base stations in the network form the nodes of the tree. The tree has a specially designated base station that acts as the root of the tree. Some implementations may have multiple trees that form the communication structure. This scheme typically uses multicasting for communication. Tree rerouting can be either (a) to a group (tree-group rerouting) as described in multicast reestablishment rerouting (with and without hint) ^[40] and the picocellular network architecture rerouting, ^[41] or (b) from a single source to a single destination using a virtual tree (tree-virtual rerouting), where only one branch of the tree is active at a time. Examples of this scheme include the virtual tree scheme ^[42] and the SRMC scheme. ^[43] Also, tree-group rerouting can have either a static ^[44], ^[45] or a dynamic group ^[46] to communicate with. Static tree-group rerouting involves a group consisting of members that do not change over time, while in the case of a dynamic tree-group rerouting the membership of a group may change. Cell forwarding rerouting involves designating a specialized base station to forward data packets to the MH_D when it moves from a "home" area. Such schemes include the ones described in the adaptive routing scheme ^[47] and the BAHAMA scheme. ^[48] Figure 12.3 shows the classification scheme.

Figure 12.3: Classification of rerouting schemes.

12.1.2 Related Work

In this section, we briefly describe related work in the area of comparative analysis of handovers and rerouting.

Toh explained how handovers in multicast connections can be achieved irrespective of the kind of multicast tree (source-based, server-based, or core-based) used in a wireless ATM environment. ^[49] Toh has proposed solutions to handle handover and rerouting for both multicast and unicast connections without categorizing rerouting strategies. However, his scheme also does not consider pure cell-forwarding schemes. The rerouting algorithm used in Toh's approach is partial rerouting using a crossover discovery algorithm. Toh demonstrates how this handoff and rerouting scheme can be used for both unicast and multicast connections using either distributed or centralized connection management. Toh's work considers partial rerouting with static-mobile connections.

Ramanathan and Steenstrup ^[50] have made an extensive survey of routing techniques for cellular, satellite, and packet radio networks. They categorize different types of handoffs in cellular telecommunication networks. These include mobile-controlled handoff (the MH chooses its new BS based on the relative signal strength), network controlled handoff (the MH's current BS decides the occurrence of a handoff based on the signal strength from the mobile host), mobile-assisted handoff (the MH's current BS requests the MH for information on the signal strengths from several nearby base stations and then decides, in consultation with the mobile switching center, when a handoff has occurred), and soft handoff (the MH may be affiliated to multiple base stations with approximately equal signal quality).

Bush ^[51] has classified handoff schemes for mobile ATM networks. The classification is specific to handovers (and not rerouting) for connection-oriented networks. These include pivotal connection handoff (a specific base station is chosen as a pivot to perform handoff), IP mobility-based handoff (handoffs require IP packet forwarding using mechanisms such as loose source routing), and handoff tree (a preestablished virtual circuit tree is used to automatically detect handoffs in a wireless ATM environment).

Cohen and Segall ^[52] describe a scheme for connection management and rerouting in standard (not wireless/mobile) ATM networks. Their rerouting is a Network Node Interface protocol, which can be invoked when an intermediate link or node in the virtual path fails. The protocol reroutes all the affected nodes to an alternate virtual path.

Ramjee et al. ^[53] have performed experimental performance evaluations of five types of rerouting protocols for wireless ATM networks. Their rerouting protocols are primarily based on crossover switch-based rerouting using mobile-directed hand-off. In order to perform rerouting in an ATM environment, the ATM switch at the crossover point must change the appropriate entry in the translation table. This involves dismantling the old entry (break) and installing the new entry (make). Their evaluation includes the following rerouting schemes: make-break (make followed by break), break-make (break followed by make), chaining (cell forwarding from the old base station to the new base station), make-break with chaining, and break-make with chaining.

Song and coworkers ^[54] have defined five kinds of rerouting schemes for connection-oriented networks:

1. Connection-extension rerouting: This rerouting is the same as cell forwarding rerouting.

2. Destination-based rerouting: In this scheme, the rerouting point is predetermined at the connection time. This is similar to connection-extension rerouting except the rerouting base station is a predetermined base station and not necessarily the old base station.

3. Branch-point-traversal-based rerouting: This rerouting is the same as partial rerouting.

4. Multicast-join-based rerouting: This rerouting is the same as tree-group rerouting.

5. Virtual-tree-based rerouting: This rerouting is the same as tree-virtual rerouting.

Mishra and Srivastava ^[55] have classified rerouting schemes in an ATM environment as:

• Extension: This rerouting is the same as cell forwarding rerouting.

• Extension with loop removal: This rerouting is a specialized case of cell forwarding rerouting with removal of any possible path loops caused by chaining.

• Total rebuild: This rerouting is the same as full rerouting.

• Partial rebuild: This rerouting is the same as partial rerouting. There are two variants in this scheme (fixed or dynamically chosen crossover point).

• Multicast to neighbors: This rerouting is the same as tree-group rerouting.

Naylon et al. ^[56] have provided classification of rerouting in the wireless ATM LANs as follows:

• Virtual connection tree: This rerouting is the same as tree-virtual rerouting.

• Path rerouting: This rerouting is the same as partial rerouting.

• Path extension scheme: This rerouting is the same as cell forwarding rerouting.

From the related work described here, we see that our classification encompasses all the proposed rerouting schemes we have described. In this sense, our work can be viewed as a generalization of previous rerouting classifications. As we shall we in the subsequent sections of the chapter, our contribution in this work is fourfold. First, we provide a comprehensive framework for comparing rerouting strategies for connection-oriented cellular data networks. We subsume also the classification proposed by various authors in the literature. Second, we analyze and evaluate the performance of the rerouting schemes using a large array of metrics, including the ones proposed by other researchers. We propose and evaluate specialized metrics that are applicable to each class of rerouting schemes. Third, we abstract the common handshaking signals from all the rerouting schemes (with and without hints) to avoid repetition and provide also a framework to compare these common handshaking signals. Finally, we compare and contrast the performance of rerouting in mobile-mobile connections. This last contribution is the first such attempt, to the best of our knowledge.

^[1]Acampora, A., An architecture and methodology for mobile-executed handoff in cellular ATM networks, IEEE J. Selected Areas Commun., 12 (8), 1365–1375, 1994.

^[2]Bush, S., "Handoff mechanism for mobile ATM systems," Internet draft, 1995.

^[3]Seshan, S., Low latency handoff for cellular data networks, Ph.D. diss., University of California, Berkeley, 1995.

^[4]Racherla, G., Radhakrishnan, S., and Sekharan, C.N., A framework for evaluation of rerouting in connection-oriented mobile networks, Technical report, School of Computer Science, University of Oklahoma, Norman, 1998.

^[5]Toh, C-K., The design and implementation of a hybrid handover protocol for multimedia wireless LANs, Proc. ACM Mobicom, Berkeley, California, November 1995.

^[6]Toh, C-K., A unifying methodology for handovers of heterogeneous connections in wireless ATM networks, in Computer Communication Review, 1997, pp. 12–30.

^[7]Acampora, A., An architecture and methodology for mobile-executed handoff in cellular ATM networks, IEEE J. Selected Areas Commun., 12 (8), 1365–1375, 1994.

^[8]Bush, S., "Handoff mechanism for mobile ATM systems," Internet draft, 1995.

^[9]Akyol, B. and Cox, D., Handling mobility in a wireless ATM network, Proc. IEEE InfoCom 96, 3, 8, 1405–1413, March 1996.

^[10]Akyol, B. and Cox, D., Rerouting for handoff in a wireless ATM network, IEEE Personal Commun., 3 (5), 26–33, 1996.

^[11]Naylon, J. et al., Low-latency handover in a wireless ATM LAN, IEEE J. Selected Areas Commun., 16 (6), 909–921, 1998.

^[12]Srivastava, M. and Mishra, P.P., Effect of connection rerouting on application performance in mobile networks, IEEE Trans. Comput., 47 (4), 371–390, 1998.

^[13]Keeton, K. et al., Providing connection-oriented network services to mobile hosts, Proc. USENIX Symposium on Mobile and Location Independent Computing, Cambridge, Massachusetts, August 1993, pp. 83–102.

^[14]Ghai, R. and Singh, S., An architecture and communication protocol for picocellular networks, IEEE Personal Commun., Third Quarter, 36–47, 1994.

^[15]Seshan, S., Low latency handoff for cellular data networks, Ph.D. diss., University of California, Berkeley, 1995.

^[16]Toh, C-K., The design and implementation of a hybrid handover protocol for multimedia wireless LANs, Proc. ACM Mobicom, Berkeley, California, November 1995.

^[17]Toh, C-K., A unifying methodology for handovers of heterogeneous connections in wireless ATM networks, in Computer Communication Review, 1997, pp. 12–30.

^[18]Toh, C-K., Performance evaluation of crossover switch discovery algorithms for wireless ATM LANs, Proc. IEEE InfoCom, San Francisco, March 1996, pp. 1380–1387.

^[19]Rekhter, Y. and Perkins, C., Optimal routing for mobile hosts using IPs loose source route option, IETF RFC, 1992.

^[20]Teraoka, F. et al., VIP: a protocol providing host mobility, Commun. ACM, 37 (8), 67–75, 1994.

^[21]Mobile IP Working Group, Routing support for IP mobile hosts, Internet draft, 1993.

^[22]Wada, H. et al., Mobile computing environment based on Internet packet forwarding, Proc. USENIX Tech. Conf., San Diego, California, Winter 1993, pp. 503–517.

^[23]Biswas, S.K., Handling real-time traffic in mobile networks, Ph.D. diss., University of Cambridge, 1994.

^[24]Akyol, B. and Cox, D., Handling mobility in a wireless ATM network, Proc. IEEE InfoCom 96, 3, 8, 1405–1413, March 1996.

^[25]Akyol, B. and Cox, D., Rerouting for handoff in a wireless ATM network, IEEE Personal Commun., 3 (5), 26–33, 1996.

^[26]Ghai, R. and Singh, S., An architecture and communication protocol for picocellular networks, IEEE Personal Commun., Third Quarter, 36–47, 1994.

^[27]Toh, C-K., Performance evaluation of crossover switch discovery algorithms for wireless ATM LANs, Proc. IEEE InfoCom, San Francisco, March 1996, pp. 1380–1387.

^[28]Biswas, S.K., Handling real-time traffic in mobile networks, Ph.D. diss., University of Cambridge, 1994.

^[29]Racherla, G., Radhakrishnan, S., and Sekharan, C.N., A framework for evaluation of rerouting in connection-oriented mobile networks, Technical report, School of Computer Science, University of Oklahoma, Norman, 1998.

^[30]Ghai, R. and Singh, S., An architecture and communication protocol for picocellular networks, IEEE Personal Commun., Third Quarter, 36–47, 1994.

^[31]Biswas, S.K., Handling real-time traffic in mobile networks, Ph.D. diss., University of Cambridge, 1994.

^[32]Racherla, G., Radhakrishnan, S., and Sekharan, C.N., A framework for evaluation of rerouting in connection-oriented mobile networks, Technical report, School of Computer Science, University of Oklahoma, Norman, 1998.

^[33]Seshan, S., Low latency handoff for cellular data networks, Ph.D. diss., University of California, Berkeley, 1995.

^[34]Racherla, G., Radhakrishnan, S., and Sekharan, C.N., A framework for evaluation of rerouting in connection-oriented mobile networks, Technical report, School of Computer Science, University of Oklahoma, Norman, 1998.

^[35]Toh, C-K., The design and implementation of a hybrid handover protocol for multimedia wireless LANs, Proc. ACM Mobicom, Berkeley, California, November 1995.

^[36]Seshan, S., Low latency handoff for cellular data networks, Ph.D. diss., University of California, Berkeley, 1995.

^[37]Seshan, S., Low latency handoff for cellular data networks, Ph.D. diss., University of California, Berkeley, 1995.

^[38]Toh, C-K., The design and implementation of a hybrid handover protocol for multimedia wireless LANs, Proc. ACM Mobicom, Berkeley, California, November 1995.

^[39]Akyol, B. and Cox, D., Rerouting for handoff in a wireless ATM network, IEEE Personal Commun., 3 (5), 26–33, 1996.

^[40]Seshan, S., Low latency handoff for cellular data networks, Ph.D. diss., University of California, Berkeley, 1995.

^[41]Ghai, R. and Singh, S., An architecture and communication protocol for picocellular networks, IEEE Personal Commun., Third Quarter, 36–47, 1994.

^[42]Acampora, A., An architecture and methodology for mobile-executed handoff in cellular ATM networks, IEEE J. Selected Areas Commun., 12 (8), 1365–1375, 1994.

^[43]Yuan, R., Biswas, S.K., and Raychaudhuri, D., Mobility support in a wireless ATM network, Proc. 5th Workshop on Third Generation Wireless Information Networks, Kluwer, Dordrecht, 1995, pp. 335–45.

^[44]Seshan, S., Low latency handoff for cellular data networks, Ph.D. diss., University of California, Berkeley, 1995.

^[45]Yuan, R., Biswas, S.K., and Raychaudhuri, D., Mobility support in a wireless ATM network, Proc. 5th Workshop on Third Generation Wireless Information Networks, Kluwer, Dordrecht, 1995, pp. 335–45.

^[46]Ghai, R. and Singh, S., An architecture and communication protocol for picocellular networks, IEEE Personal Commun., Third Quarter, 36–47, 1994.

^[47]Eng, K.Y. et al., A wireless broadband ad-hoc ATM local area network, ACM J. Wireless Networks (WINET), 1 (2), 161–174, 1995.

^[48]Ramanathan, S. and Streenstrup, M., A survey of routing techniques for mobile communication networks, ACM/Baltzer Mobile Networks Appl., Special issue on Routing in Mobile Communications Networks, 1 (2), 89–104, 1996.

^[49]Toh, C-K., A unifying methodology for handovers of heterogeneous connections in wireless ATM networks, in Computer Communication Review, 1997, pp. 12–30.

^[50]Cohen, R. and Segall, A,. Connection management and rerouting in ATM networks, Internet draft, 1998.

^[51]Bush, S., "Handoff mechanism for mobile ATM systems," Internet draft, 1995.

^[52]Ramjee, R., La Porta, T.F., Kurose, J., and Towsley, D., Performance evaluation of connection rerouting schemes for ATM-based wireless networks, IEEE/ACM Trans. Networking, 6 (3), 249–261, 1998.

^[53]Song, M., Choi, Y., and Kim, C., Connection-information-based connection rerouting for connection oriented mobile communication networks, Distributed Systems Engineering, 5, 47–65. 1998.

^[54]EIA/TIA, IS-41(c), Cellular radio telecommunications intersystem operations, 1995.

^[55]Srivastava, M. and Mishra, P.P., Effect of connection rerouting on application performance in mobile networks, IEEE Trans. Comput., 47 (4), 371–390, 1998.

^[56]Naylon, J. et al., Low-latency handover in a wireless ATM LAN, IEEE J. Selected Areas Commun., 16 (6), 909–921, 1998.