12.3 Performance Evaluation of Rerouting Schemes

12.3 Performance Evaluation of Rerouting Schemes

In this section, we use analytical cost modeling to calculate the performance metrics. Our cost model heavily borrows from the work done by Seshan ^[71] and Toh. ^[72], ^[73] The cost modeling involves calculating the time required for each step in the protocol of the rerouting scheme. These individual times are used to calculate the proposed metrics.

We use the network parameters described in the literature ^[74], ^[75], ^[76], ^[77] for our analytical cost models: bandwidth of the wireless link = 2 Mbps; bandwidth of the wired backbone network = 155 Mbps; latency of the wireless link, including data link and network layer processing = 2 ms; latency of the wired backbone, including data link and network layer processing = 500 μs; protocol processing time for control messages = 0.5 ms; protocol processing time for admission control = 2 ms ; maximum size of a control packet = 50 B; maximum size of a data packet = 1 kb; wireless channel acquisition time for a MH from a BS = 5 ms.

We measure the performance of the metrics by changing the number of hops in the appropriate paths, depending on the rerouting scheme. For cost modeling, we assume a perfect delivery of messages and that maximum throughput for a connection is the throughput of the bandwidth of the wireless link. Also, the calculations used in the model are on a per-channel basis. Detailed cost modeling and performance metric calculations can be found in Racherla and coworkers. ^[78]

12.3.1 Comparison of Rerouting Schemes

We first look at the advantages and the disadvantages of each of the rerouting schemes. In order to compare the rerouting schemes, we built cost models for several metrics for each rerouting scheme using the system parameters and the length of the routes. Then, we compare the schemes using the metrics. To this end, we first consider metrics that are not dependent on the path length (in terms of number of hops) of the old/new connection. Next, we consider the metrics that are dependent on the length of the old/new connection. In this case, we vary the path length to determine its effect on these metrics.

12.3.1.1 Advantages and Disadvantages of the Rerouting Schemes

The advantages and disadvantages of the various rerouting schemes are described in Table 12.1.

Table 12.1: Advantages and Disadvantages of Various Rerouting Schemes

Rerouting	Advantages	Disadvantages
Full	Simple, easy to implement	Naive, inefficient, slow, prone to data loss
Partial	Maximizes resource utilization	Prone to data loss, onus of crossover discovery
Tree-virtual	Fastest, efficient, low data loss, works well if enough resources present	Multiple connections, static membership, membership difficult to decide
Tree-group	Fast, efficient, low data loss, dynamic membership	Multiple connections, resource intensive, wasted bandwidth
Cell forwarding	Simple, easy to implement	Requires special anchor node, requires a lot of buffering, inefficient, slow, prone to data loss

12.3.1.2 Metrics not Dependent on the Connection Length

These metrics are fixed and give a complexity of the rerouting protocol in question. We base this comparison on the work done by Akyol and Cox. ^[79], ^[80] These include the number of messages exchanged during handoff and rerouting, the number of nodes and user connections involved for rerouting, the user bandwidth allocated, whether the scheme is tailored for WAN (wide area networks), local area networks, or ATM-based networks. The comparison for the rerouting metrics is shown in Table 12.2.

Table 12.2: Comparison of Rerouting Schemes

Scheme	Type	Mh [a]	Mr [b]	Nodes	UC/BW [c]
Full (no hint)	Full	2	8	2 + D [d]	1/1
Full (hint)	Full	6	5	2 + D	1/1
Incremental (no hint)	Partial	2	9	3 + D	1/1
Incremental (hint)	Partial	7	5	3 + D	1/1
Multicast (no hint)	Tree-group	2	8	N [e] + D	N/N
Multicast (hint)	Tree-group	6	3	N + D	N/N
SRMC	Tree-virtual	3	9	4 + D	N/l
BAHAMA	Cell forwarding	2	5	N + D	1/1
Virtual Tree	Tree-virtual	1	1	3 + D	1/1
Adaptive	Cell forwarding	2	4	3 + D	1/1
Incremental [f] (no hint)	Partial	4	7	3 + D	1/1
Incremental[f] (hint)	Partial	3	4	2	1/1
NCNR (direct link)	Partial	7	2	4 + D	1/1
NCNR (link)	Partial	9	4	N + D	1/1
Picocellular [g] (same subnet)	Tree-group	2	0	N + D	N/N
Picocellular[g] (different subnet)	Tree-group	4	2	N + D	N/N
Note: All the schemes can handle time-dependent and throughput-dependent data.
[a]Mh: Number for messages to perform handoff. [b]Mr: Number for messages to perform rerouting. [c]UC/BW: Number of user connections/bandwidth. [d]D: Topology dependent. [e]N: Number of leaves in tree. [f]Tailored for LANs. Other schemes are tailored for WANs. [g]Tailored for picocells/micocells. Other schemes are tailored for microcells/macrocells.

12.3.1.2.1 Number of Messages Exchanged during Handoff

The partial rerouting scheme with hints requires the maximum number of messages for handoff while full rerouting without hints, partial rerouting without hints, tree-group rerouting without hints, tree-virtual rerouting, and cell forwarding rerouting require the least.

12.3.1.2.2 Number of Messages Exchanged during Rerouting

Cell forwarding rerouting requires the maximum number of messages exchanged during rerouting while tree-group with hints requires the minimum number.

12.3.1.2.3 Number of Nodes Involved in Handoff and Rerouting

The number of the nodes required depends on the network topology. However, in terms of the minimum requirements, the full rerouting schemes are the best, as they require two nodes (BS_old and BS_new) in addition to BS_dest, while the other schemes require at least three nodes in addition to BS_dest.

12.3.1.2.4 Number of User Connections Established for Rerouting

The tree-group rerouting schemes can handle N_mcast, connections, while the others handle only one connection.

12.3.1.2.5 User Bandwidth Allocated for Handoff and Rerouting

If we consider the bandwidth allocated for handoff and rerouting for the full rerouting without hints as unity, then all the schemes have the same bandwidth requirements with the exception of the tree-group rerouting schemes. The tree-group rerouting requires a bandwidth that is N times the unit bandwidth requirements.

12.3.1.3 Metrics Dependent on the Connection Length

We now study the metrics that depend on the connection path length. Figures 12.12(a-d) show the effect of old connection path length on the service disruption time, total rerouting time, buffering requirements at the mobile host, buffering requirements at the base station on the uplink, and buffering requirements at the base station on the downlink, respectively. In these figures, we vary the old connection path length from 1 hop to 10 hops. We assume that the new connection path length is of the same length as the old connection and the control path length is twice the size of the connection path length (based on the assumptions in Seshan ^[81] and Gopal and co-workers). ^[82] We now discuss the performance of the various rerouting schemes in detail.

Figure 12.12: Performance metrics dependent on path length for rerouting— (a) service disruption time; (b) buffering at mobile host; (c) buffering at base station (uplink); (d) buffering at base station (downlink); (e) total rerouting completion time.

12.3.1.3.1 Service Disruption Time

Figure 12.12(a) depicts the effect of old connection path length on the service disruption time. From the figure, we see that:

1. The minimum service disruption time is for the tree-group with hints rerouting scheme. It does not vary with the number of hops in the path.

2. For all schemes, except the tree-group with hints, the service disruption time is dependent on the control path length between BS_old and BS_new. This is because, in the case of tree-group with hints scheme, there is no need to forward the data from BS_old to BS_new as the data is being multicast to both BS_old and BS_new.

3. The service disruption time for the full without hints, full with hints, partial without hints, partial with hints, tree-group without hints, and cell forwarding rerouting schemes is the same because all of these schemes depend on forwarding of downlink data from BS_old. The service disruption time for tree-virtual rerouting is not dependent on the length of control path, as it does not rely on downlink data forwarding. However, it is dependent on the length of the new path. In case of the tree-virtual rerouting, when the mobile host moves to a new base station, the root automatically recognizes that a handoff has taken place.

12.3.1.3.2 Buffering Required at the Mobile Host

Figure 12.12(b) depicts the effect of old connection path length on the buffering requirements at the mobile host. From the figure, we see that in each rerouting scheme, the buffering at the MH is only used to buffer data for the two specific messages in their respective protocol. The first is the registration message that MH sends to the BS_new and the second is for the acknowledgment that it receives in response to the first message; the cost of the messages is constant for the given parameters for all the schemes. All the schemes require the same amount of buffering at the MH.

12.3.1.3.3 Buffering Required in Base Station for the Uplink

Figure 12.12(c) depicts the effect of old connection path length on the buffering requirements at the base station for the uplink. From the figure, we see that:

1. The buffering requirements for uplink data for all the schemes without hints, including tree-virtual and cell forwarding, are the same.

2. There are no buffering requirements for uplink data for all the schemes with hints if the length of new and old forwarding path is the same. In general, buffering is dependent on the difference of the old and new path lengths.

3. Except for the case of tree-virtual rerouting, the buffering requirement for uplink data is proportional to the forwarding path length. In the case of tree-virtual rerouting, the buffering requirement for uplink data is proportional to the new path length between BS_src and BS_new.

12.3.1.3.4 Buffering Required in Base Station for the Downlink

Figure 12.12(d) depicts the effect of the old connection path length on the buffering requirements at the base station for the downlink. From the figure, we see that:

1. This metric is very closely dependent on the time required for forwarding downlink data from BS_old to BS_new.

2. Because all schemes with the exception of the tree-group with hints and tree-virtual scheme require data forwarding of downlink data, the buffering required in the base station for downlink for them is larger than the requirements for the tree-group with hints scheme.

3. The buffering requirements are the maximum for the tree-virtual rerouting as it does not rely on downlink data forwarding on the control path between BS_old to BS_new. BS_new has to buffer all the data on the downlink until it gets an acknowledgment from the server (source) that it has accepted the request to reroute data to BS_new.

4. There is a fixed amount of downlink buffering for the tree-group with hints scheme. This is used to buffer the data during the handoff period alone while the others require downlink buffering for the handoff and the time period until BS_new requests forwarding of data.

12.3.1.3.5 Rerouting Completion Time

Figure 12.12(e) depicts the effect of old connection path length on the rerouting completion time. From the figure, we see that:

1. The minimum rerouting time is for the tree-virtual rerouting scheme. The metric varies with the length of the new path (and hence with the number of hops in the old path). However, there is no need to either forward downlink data or form new connections or delete connections as the virtual tree is fixed.

2. The rerouting completion time for cell forwarding is comparable to the rerouting time for tree-virtual rerouting. In case of cell forwarding, there is no need to form new connections or delete old connections as the connection path is simply extended. The problem with cell forwarding is in the case of multiple handoffs, the length of the downlink forwarding path can become very large, giving rise to inefficiency. For tree-group with hints, rerouting the completion time is dependent on old path length and performs fairly well because it does not require any downlink data forwarding.

3. Full rerouting and partial rerouting perform worse than the other rerouting schemes. When the old path is small, full rerouting performs worse than partial rerouting. However, as the old (and the new) path length increases, partial rerouting performs worse than full rerouting because of the additional onus of computing the crossover point.

4. The completion time for the rerouting schemes with hints is less than their counterparts, which do not take advantage of hints. The completion time for rerouting schemes without hints is dependent on the length of the new path. In case of rerouting schemes with hints, the completion time is dependent and closely related to time needed for forwarding downlink data and to tear down old connections.

12.3.1.3.6 Special Metrics

Table 12.3 shows the values of some of the special metrics (described earlier) for the different rerouting schemes. More analysis of these results can be found in Racherla and coworkers. ^[83] We see from the previous discussions that:

1. The tree-group with hints and tree-virtual schemes perform the best among the rerouting schemes. However, they use a lot more resources for preestablishing the tree and maintaining it. This overhead may be worthwhile for time-critical applications that require low rerouting completion time and service disruption.

2. In order to minimize service disruption, tree-group rerouting with hints is the best choice. If the rerouting completion time is the criterion considered, tree-virtual and cell forwarding rerouting perform the best, as they do not require forming new paths and tearing down old paths.

3. It is certainly advantageous to use rerouting with hints. This readily improves service disruption time (for tree-group rerouting), total rerouting completion time, and uplink buffering requirements at the base station.

4. Needless to say, the topology of the network is important. In essence, the lengths of the new and old paths are of vital importance.

5. Most of the rerouting schemes behave somewhat similarly because the underlying mechanisms use downlink data forwarding.

6. The full rerouting and the partial rerouting schemes perform the worst, as they involve forming new paths, tearing down old paths, and downlink data forwarding.

Table 12.3: Special Metrics for Rerouting Schemes

Rerouting Scheme Special Metrics	Without Hints	With Hints
Full
Old path teardown time	12.36 ms	12.36 ms
New path setup time	23.82 ms	23.76 ms
Partial
Old path teardown time	12.36 ms	12.36 ms
New path setup time	16.18 ms	15.55 ms
Crossover discovery time	1.06 ms	1.06 ms
Partial reuse efficiency	0.5	0.5
Tree-group
Tree teardown time	12.36 ms	12.36 ms
Tree setup time	16.43 ms	16.43 ms
Tree-virtual
Old path teardown time	12.36 ms	12.36 ms
Tree setup time	16.43 ms	16.43 ms
Cell forwarding
Old path teardown time	12.36 ms	12.36 ms
New path setup time	16.18 ms	16.18 ms

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

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

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

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

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

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

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

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

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

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

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

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

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