To my parents, my wife Orit and my kids for their love and support.

This research thesis was done under the supervision of Professor Israel Cidon and in cooperation with Professor Joseph (Seffi) Naor in the Faculty of Electrical Engineering.

I would like to thank Professor Israel Cidon and Professor Seffi Naor for their dedicated and helpful supervision throughout this work. The knowledge that I have learnt from them is invaluable and working with them was both an honor and a pleasure.

The generous financial help of the Technion and the Eshkol Foundation of the Israeli Ministry of Science are gratefully acknowledged. I would also like to thank the Gutwirth Foundation and the Intel Corporation for the distinguished awards that they have given me.

Personal Communication Service (PCS) networks enable people to communicate independently of their location and while they move from place to place. For providing continuous communication to mobile users, every PCS network employs a mobility management mechanism. It is composed of two components; A location management for tracking the location of mobile users and a handoff management for maintaining sessions between mobile users while they change their attachment points to the system's infrastructure. The increasing population of mobile users leads to congestion problems in these systems. This motivates the development of new management schemes that efficiently utilize both radio bandwidth and the infrastructure network resources.

This work deals with different aspects of the location and handoff management. Initially, we present two novel location schemes that are based on hierarchical organization of the location servers for efficient usage of the network resources. The first is termed the hierarchical region scheme and every level of the hierarchy represents a partition to geographic regions. Within each level, the system records the location of every mobile user to a certain degree of accuracy, where the degree of accuracy is increased as we go down the levels until we reach the mobile user attachment point. The second is termed the hybrid scheme and it combines the hierarchical region scheme with the home location server approach. For both strategies, we develop distributed procedures for locating the mobile users (Search operation) and updating the system location records (Update operation) with user movements. The proposed schemes guarantee upper bound on the procedure costs: The amortized complexity of the mobile user update operations is O(Move log Move), where "Move" is the total geographic distance that the mobile user has traveled. The upper bound of a search operation is linear with the distance between the search originator and the target node. Unlike previous results, these upper bounds do not depend on the network size. Simulation results show that the proposed schemes yield lower average overhead for both the search and update operations then the other methods described in the literature.

We also present a complementary location scheme that efficiently utilizes the radio spectrum as well as the network resources with low computational overhead. This scheme integrates the concept of location areas with the location prediction idea and it based on results from traffic flow theory. This theory suggests that people tend to reside in specific places for long periods of time. Occasionally, they move to new locations and try to minimize the travel time using highways as much as possible. The scheme uses two complement sets of location areas that overlap each other. The first set contains small location areas and is designated for locating mobile users in a quasi-static state. The second set covers the highways and it is designated to track mobile users while they are traveling from place to place, where each highway is covered by a single location area. The dual set design enables tracking mobile users at a high degree of accuracy with low update cost while they are quasi-static state, and reduces the amount of update operations when they travel. For tracing mobile users on a highway, the scheme uses a system of moving location areas. A moving location area (MLA) is a limited location area that defines the location of a group of mobile users, which are geographically concentrated and move in the same direction. The scheme guarantees low rate of update and search operations at each cell of the system and these advantages are also backed by simulation results.

This research also considers the design of handoff rerouting algorithms for reducing the overall session cost. Most modern communication systems that are used as an infrastructure for PCS networks are based on connection-based technologies. In these systems the session cost is composed of two components. The setup cost represents the cost associated with the handoff operations and the hold cost determines the expense related to the use of network resources held by the connection. This work introduces for the first time rerouting algorithms for general graphs which are cost effective in terms of their worst case analysis. The algorithms are analyzed using a competitive analysis approach and it is proved that the competitive ratio of the proposed algorithms is 3. We also prove that the competitive ratio of the best online algorithm is at least 2, which means that the proposed algorithms are close in terms of worst case behavior to the best possible rerouting algorithm. In addition, experimental results also show that the proposed algorithms indeed balance between the session setup cost and the hold cost, yielding overall lower cost when compared to other algorithms described in the literature.

Finally, we proposed a new mobility management scheme for supporting mobile hosts in IP-based networks. Unlike other PCS network, the IP protocol is connectionless and each datagram is routed individually to its destination. This motivates the design of different mobility management adapted to connectionless technologies. For IP networks, we present a simple mobility scheme, termed the anchor chain scheme. The scheme combines pointer forwarding and caching methods. Every mobile host is associated with a chain of anchors that connects it to its home agent. Each anchor defines the location of the mobile host at a certain degree of accuracy. The accuracy is increased along the chain until the attachment point of the mobile host is reached. We develop distributed procedures for updating the anchor chain (Binding operation) with mobile host movements and for delivering messages to a mobile host (Delivery operation). In terms of worst case performance, the total cost of the binding operations is O(Move log Move), where "Move" is the total geographic distance that the mobile user has traveled since its activation. The total length of the mobile host's pointer path is linear with the distance between the mobile host and its home network, and the delivery cost is near optimal. In addition, the anchor chain of a mobile host is determined dynamically with no need for preliminary definitions of static anchors or regions. Our simulation results show that the anchor chain scheme also yields lower average overheads for both the binding and the delivery operations than other methods that are described in the literature. We believe that the proposed scheme is scalable, fairly easy to implement and therefore attractive for supporting mobile hosts.

Abstract and Glossary.
Introduction to Mobility Management.
Hierarchical Schemes for Location Management.
Efficient Location Management Based on Moving Location Areas.
Dynamic Session Management for Static and Mobile Users.
Efficient Handoff Rerouting Algorithms.
An Anchor Chain Scheme for IP Mobility.