12.4 Mobile-Mobile Rerouting in Connection-Oriented Networks

Static-static communication has been studied extensively and the routing algorithms for this type of communication are well known. The problem with the rerouting schemes for connection-oriented mobile networks described in the literature is the assumption that only one of the parties communicating in a session can be a mobile host (typically, the destination) and the other is stationary. Only Racherla and coworkers, ^[84] Ghai and Singh, ^[85] Biswas, ^[86] and cellular telecommunications standard IS-41(c) ^[87], ^[88] suggest schemes for mobile-host-to-mobile-host communication. Biswas' ^[89] strategy uses an already preestablished route between two stationary hosts that house the mobile agents in charge of the communication. The only rerouting involves both the source and destination mobile hosts establishing paths to these stationary hosts. The disadvantage of this scheme is that if the mobile hosts keep moving, the path used for communication may be inefficient, as the scheme does not dynamically update the paths based on the location of the mobile hosts. The scheme proposed by Ghai and Singh suffers from the same problem. In addition, Ghai and Singh's scheme uses only dynamic multicast rerouting. The complex setup architecture uses a three-tier hierarchy (mobile host, base station, and supervisory host). In case of cellular telecommunications using the EIA/TIA IS-41(c) standard, cell forwarding rerouting is used continuously for multiple handoffs, as the mobile hosts move away from the original source and the destination base stations. The obvious disadvantage is that the new cell forwarding routes used are not optimal. We shall see this in more detail later as we compare all these schemes. In addition, these schemes do not look at different rerouting strategies known for static-mobile connections. Racherla and coworkers ^[90] have proposed a generic framework for mobile-mobile rerouting allowing unlimited movement by both the source and destination mobile hosts, while alleviating the problem of nonoptimal paths. Also, this framework for mobile-mobile rerouting is not tied to the type of rerouting (full, partial, cell, tree-based). These rerouting schemes basically concentrate on deciding the endpoints on the connections and can, in theory, use any type of rerouting. In this chapter, we compare the performance of these rerouting algorithms. Our comparison is based on calculating the total rerouting distance, the cumulative connection path length, and the amount of resources used as the mobiles move. As seen earlier, the metrics that determine efficiency of rerouting schemes in static-mobile connections are dependent on connection length. For example, the total rerouting path length gives a good estimate of metrics such as throughput, the total rerouting time, the service disruption time, and buffering requirements at the base stations.

We know of only these four techniques to perform rerouting in mobile-mobile connections. In this section, we discuss these techniques in more detail and look at their drawbacks and at the technique suggested by Racherla to alleviate them.

12.4.1 Problems in Mobile-Mobile Rerouting

Rerouting techniques that work for static-mobile connections do not work for mobile-mobile connections, as they cause some problems. We discuss the problems in this section.

12.4.1.1 Inefficiency

The original protocol assumes that only one end of a session is mobile. So, if MH_S moves (and assumes that MH_D is fixed), it establishes the new path between BS_SN and BS_DO, whereas if MH_D moves also (and assumes that MH_S is fixed), it establishes the new path between BS_DN and BS_SO instead of the correct path being established between BS_SN and BS_DN. So, the rerouting and path establishment would be inefficient.

12.4.1.2 Lack of Coordination

There is no mechanism to coordinate between the source and destination base stations. The bottom line is that the algorithm suffers from the classic problems of asynchronous messages and the lack of synchronization.

12.4.2 Techniques for Mobile-Mobile Rerouting

We now discuss the known techniques for rerouting in mobile-mobile connections. Specifically, we will look into the details of the schemes proposed by Racherla and coworkers, ^[91] Ghai and Singh, ^[92] Biswas, ^[93] and the EIA/TIA IS-41(c) cellular telecommunications standard. We look also at an approach for extending Biswas' work for mobile-mobile rerouting using core-based trees.

12.4.2.1 Biswas' Strategy: Mobile Representative and Segment-Based Rerouting

Biswas ^[94] proposes the use of software mobile agents called mobile representatives that handle the connection management operations of the mobile host. The representatives reside on one of the intermediate routers. Each mobile host has a corresponding mobile representative. It is assumed that the source mobile host MH_S (resp. the destination mobile host MH_D) is in the cell corresponding to the base station BS_S (resp. BS_D) and its mobile representative is MR_S (resp. MR_D). Thus, the initial route in the source mobile host-destination mobile host connection is MH_S - BS_S - MR_S -MR_D - BS_D - MH_D. The crux of Biswas' rerouting strategy is that the path connecting the corresponding source and the destination mobile representative is the same during the lifetime of the connection except the portion of the connection between the mobile host and the mobile representative that changes with handoff.

12.4.2.1.1 Problem with Biswas' Strategy

The disadvantage of this scheme is that if the mobile hosts keep moving, the path used for communication may be inefficient, as the scheme does not dynamically update the paths based on the location of the mobile hosts.

12.4.2.2 CBT (Core-Based Tree) Strategy: Extending Biswas' Work

We propose an extension of Biswas' approach by using a core-based tree connecting the source mobile representative to a group of destination mobile representatives instead of a simple path connecting the mobile representatives. The advantage with this scheme is that the total rerouting distance can be reduced significantly compared to Biswas' strategy. We will see in detail how this can be accomplished when we analyze the performance of this strategy.

12.4.2.2.1 Problem with the CBT Strategy

The only problem with the CBT is the excess use of resources as the core-based tree has to be built a priori for the purpose of rerouting.

12.4.2.3 Ghai and Singh's Strategy: Two-Level Picocellular Rerouting

Ghai and Singh ^[95] present a picocellular-based architecture wherein the number of handoffs and therefore handoff overhead within the network increases as cell size decreases. Their proposal describes a network architecture that supports a method for reducing the handoff overhead and the buffer space requirements using multicast groups and mobile trajectory prediction. Base stations (referred in this proposal as mobility support stations or MSSs) do not have any intelligence, but rely on a centralized authority called a supervisory host. The supervisory host calculates the mobile's likely trajectory, and forms a multicast group for MSSs that the mobile is likely to handoff to in the near future. All packets are multicast to this group. MSSs do not currently host the mobile host buffer packets in anticipation of a handoff. Such buffered packets are tossed out when the MSSs receive an update of the mobile's acknowledged sequence numbers. A connection-oriented network architecture is described also in this proposal. Virtual circuits are set up between the endpoints for communication. The communication is optimized for the case where two mobiles use the base stations and supervisory host(s). Multiple supervisory hosts are needed if the communicating mobile hosts are under the supervision of different supervisory hosts.

12.4.2.3.1 Problem with Ghai and Singh's Strategy

The scheme proposed by Ghai and Singh suffers from several drawbacks. The architecture is fixed, rigid, and requires a tree or tree-like topology. In addition, it requires an extra level of hierarchy (supervisory hosts), compared to the other schemes that we discussed earlier. This hierarchy results in longer paths. In addition, this scheme performs rerouting using a tree-group mechanism and does not allow for the other rerouting strategies.

12.4.2.4 EIA/TIA IS-41(c) Rerouting

The EIA/TIA IS-41(c) Protocol for cellular communications is designed to deal with handoffs and the subsequent forwarding of connections as the mobile hosts move. This is done by cell forwarding rerouting (called chaining in the scheme). Chaining in this case is done using switches as opposed to base stations used in all the other schemes described earlier. Because the connections are through switches, the links to old base stations are automatically removed during switching. These protocols are meant for circuit-switched networks and not for packet-switched networks. Data loss and data ordering is not an important concern in this case.

12.4.2.4.1 Problem with EIA/TIA IS-41(c) Rerouting

We cannot compare this scheme with the other schemes described earlier as this scheme is for circuit-switched networks and switches are used instead of base stations. However, because the rerouting involves cell forwarding, the rerouting is nonoptimal and inefficient.

12.4.2.5 Racherla's Framework for Mobile-Mobile Rerouting

In order to avoid the above-mentioned problems, Racherla and coworkers ^[96] proposed a source-initiated distributed rerouting algorithm. In this algorithm, the source base station is responsible for initiating the rerouting. The destination base station informs the source base station of the movement of MH_D. The establishment and removal of routes is initiated by the appropriate source base stations. The crux of this proposed framework is that incorrect requests for new path establishment are rejected, unlike the other proposed rerouting algorithms described earlier. In addition, Racherla's framework for rerouting in mobile-mobile communications is independent of the type of rerouting scheme (full, partial, tree-based or cell forwarding). Each base station maintains data structures in its local memory to keep track of connections, movements, and identities of mobile hosts MH_S and MH_D. This data structure allows base stations to decide whether or not to accept the creation or termination of a route during the rerouting procedure. The framework assumes that there are no lost messages and that the messages are delivered in a first-in, first-out manner on a channel. A mobile host can move any number of times. However, it eventually stays in a cell long enough for the rerouting to be completed. Each MH receives a radio hint informing it of its movement into another cell, which can be used to set up connections a priori. The framework assumes that there is initially a connection between the base stations corresponding to MH_S and MH_D. This proposed scheme has the following advantages over the other schemes described earlier:

It uses optimal routes and avoids creating unnecessary routes.
It gives the flexibility to use either full, partial, tree, or cell forwarding routing.
It is independent of the network architecture and network topology.
Packet loss is kept to a minimum using radio hints effectively.
Processing at the mobile hosts is kept at a minimum.

12.4.3 Comparison of Rerouting Schemes for Mobile-Mobile Connections

We compare the previously described schemes based on the rerouting distances. We use the extended cross-bar network and analysis as suggested by Song and coworkers ^[97] for calculating the rerouting distance. The extended cross-bar architecture allows for simplified calculations. The analysis can be extended to other types of networks. In the architecture, the nodes represent the base stations. The horizontal and vertical links are of length 1, while the slanted links are in length. We use RD_S,D to represent the reroute distance between nodes S and D. We use TRD(a, d) to represent the total rerouting distance between BS_SN and BS_DN, where the initial path length between the source and destination base station is a and the movement distance of the MH from its initial position is d. We denote the performance metrics for each of the rerouting schemes by using the name of the scheme as a subscript.

We assume that:

The MH_S and MH_D are moving in a straight line in the same direction, and the top and the bottom of the network grid respectively.
The mobile hosts both moved hops.
MH_S moves from cell of its old base station BS_SO to a new old base station BS_SN.
MH_D moves from cell of its old base station BS_DO to a new old base station BS_DN.
There is a connection path between the old base stations for the mobile hosts to start with. The minimum length of this route is a, and is shown as the straight line connecting BS_SO and BS_DO.
The mobile hosts stay at the new base station long enough for the rerouting to be completed.
For simplicity of analysis, we assume that the mobile hosts start moving at the same time and continue moving at the same speed.

We calculate the following metrics for comparing the performance for all of the mobile-mobile rerouting schemes. We consider each case separately for calculating the metrics.

Total rerouting distance (TRD(a, d)): This is the rerouting path length connecting the new source and destination base stations after the mobile hosts have moved d hops from their initial positions and the initial path length between their corresponding base stations is a hops. This metric gives a good estimate of the system throughput for the connection between the source and the destination mobile hosts.
Cumulative connection path length (CCPL): This is the cumulative total of the lengths of new reroute paths formed and torn down as the mobile hosts move. In order to calculate the CCPL for the rerouting scheme, we calculate the cumulative length of new paths formed (CLNP) and the cumulative length of old paths torn down (CLOP). So, CCPL is the sum of CLNP and CLOP. This metric is an indicator of the system disruption, the cumulative rerouting time, and the buffering requirements for the connection between the source and the destination mobile hosts.
Number of connections (NC): We calculate the amount of resources reserved of each connection pair in terms of the maximum number of connections that can exist at any time during the entire rerouting process. This metric gives a reflection of the resources used by the system.

^[84]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.

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

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

^[87]Racherla, G., Radhakrishnan, S., and Sekharan, C.N., A distributed rerouting algorithm for mobile-mobile connections in connection-oriented mobile networks, Proc. 7th Int. Conf. Comput. Commun. Networks (ICCCN), September 1998, pp. 40–44.

^[88]Wu, O.T.W. and Leung, V.C.M., B-ISDN architectures and protocols to support wireless personal communications internetworking, Proc. PIMRC'95, Toronto, Canada, September 1995.

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

^[90]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.

^[91]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.

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

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

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

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

^[96]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.

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