12.2 Analysis of Rerouting Schemes


12.2 Analysis of Rerouting Schemes

In this section, we describe for each class of rerouting the basic protocol and its different implementations, advantages, and disadvantages. Self-descriptive figures are provided to aid in the explanation.

In the descriptions of the rerouting schemes, we make the following assumptions. There is coverage overlap between cells. An MH communicates with only one BS at a time. Each MH can measure the radio signal strength of the base stations in order to know about its entry into a new cell. Handoff and rerouting is initiated by the destination mobile host (MHD). The source mobile host (MHS) is assumed to be stationary during the rerouting process.

12.2.1 Common Handshaking Signals for Rerouting Schemes

Many handshaking signals during the rerouting process are common to all the rerouting schemes. We have abstracted these signals in order to avoid repetition in all the rerouting schemes. Using the framework that we describe here, we can selectively compare the rerouting schemes, with or without these handshaking signals. The handshaking protocol is assumed to be completed before the actual rerouting protocol. We describe these signals for rerouting schemes, with and without hints, separately. In case of schemes without hints, the handshaking protocol is the same for all the rerouting schemes. However, the handshaking protocol varies for schemes that use hints. We now describe these handshaking schemes briefly.

12.2.1.1 Without Hints

The handshaking protocol for all rerouting schemes without hints is shown in Figure 12.4. The messages are:

  1. MHD enters the new cell and requests a connection with BSnew after identifying itself. MHD informs BSnew the identity of BSold and its present connections.

  2. BSnew acknowledges the MHD request. MHD can continue its transmissions.

  3. BSnew requests BSold to forward MHD's data to BSnew. The message requests also that BSnew be allowed to be the "anchor" for MHD's transmission.

  4. BSold acknowledges and grants permission to BSnew. After this, BSnew begins forwarding MHD's transmitted data to MHS through BSold.

click to expand
Figure 12.4: Rerouting handshaking without hints.

12.2.1.2 With Hints

The handshaking protocol for rerouting with hints is dependent on the rerouting scheme. Only the partial rerouting scheme has a different handshaking protocol, as shown in Figure 12.5. It should be noted that BS is a special base station that has different functionality for each of the rerouting schemes. In the schemes other than partial rerouting, the handshaking protocol is as follows:

  1. MHD requests BSold to send a list of active connections to BSnew.

  2. BSold sends the list to BSnew.

  3. BSnew establishes the connections with BS.

  4. BS acknowledges the establishing of the connections.

click to expand
Figure 12.5: Rerouting handshaking with hints.

In case of partial rerouting, BSold invokes the crossover discovery algorithm and BSnew establishes the connections with BS. BS then acknowledges the establishment of the connections.

12.2.2 Full Rerouting

Full rerouting can occur with or without hints. We describe later the generic full rerouting schemes without hints. Detailed protocol descriptions of all rerouting schemes (with and without hints) are explained in Seshan [57] and Racherla and coworkers. [58] Figures 12.6 and 12.7 describe the protocol of a generic full rerouting without hints and full rerouting with hints, respectively.

click to expand
Figure 12.6: Full rerouting without hints.

click to expand
Figure 12.7: Full rerouting with hints.

12.2.2.1 Implementations

An implementation of full rerouting, namely, full reestablishment schemes with and without hints, is described by Seshan. [59] The generic full rerouting explained prviously is the same as Seshan's implementation. The source (a video server in the implementation) is assumed to be fixed, while the destination is the MHD. The mobile host moves from the old base station BSold to the new base station BSnew. The rerouting involves finding a new route from BSnew to BSS.

12.2.2.2 Special Metrics

With respect to full rerouting, we look at two special metrics, namely, old connection teardown time and new connection setup time.

  1. Old connection tear down time (Ttear): It is the total time required for BSdest to inform BSold to tear down the old connection and for BSold to comply.

  2. New connection setup time (Ttear): It is the total time elapsed from the time MHD informs BSold to send a list of active connections to the time when BSdest confirms the establishment of the connections.

12.2.3 Partial Rerouting

Partial rerouting tries to use as much of the old route as possible in the new route. The heart of partial rerouting is the crossover discovery algorithm. [60], [61] The algorithm aims to find the base station (called the crossover point) that belongs to both the old and the new route so that the overlap between the old and the new path is maximized. We assume that BScross is the base station at the crossover point. Figure 12.8 shows the protocol of a generic partial rerouting without hints.

click to expand
Figure 12.8: Partial rerouting without hints.

12.2.3.1 Implementations

There are many variations of implementing partial rerouting. Seshan [62] gives an implementation called incremental reestablishment rerouting with and without hints. The protocol of Seshan's implementation is the same as the generic protocol described previously. However, the protocol does not specify the crossover discovery mechanism.

Toh [63] gives an implementation of partial rerouting, also called incremental reestablishment with and without hints. Toh's implementation is tailored for wireless LANs (local area networks). Toh's strategy for partial rerouting without hints, unlike the generic partial rerouting without hints described in Figure 12.8, assumes that the wireless link between the MH and BSold has failed, resulting in the unavailability of hints. In Toh's incremental reestablishment rerouting without hints protocol, BSold does not acknowledge the MH (message 2 in the generic protocol). Also, messages 3 and 4 are absent, and there is cell loss as BSnew does not request BSold to forward cells. In addition, there are no explicit messages to tear down the old connection (messages 10 and 11). In case of Toh's incremental reestablishment rerouting with hints, BSnew invokes the crossover discovery algorithm (message 3) instead of BSold as described in the generic partial rerouting with hints scheme. [64] Also, messages 8 and 9 intended for cell forwarding from BSold to BSnew are absent, resulting is cell loss. Toh describes many algorithms for discovery of the crossover switch. Akyol and Cox's [65], [66] strategy, called NCNR rerouting, performs partial rerouting by choosing the crossover discovery as the nearest common neighbor of the BSold and BSnew. Their scheme checks to see if there is a direct link between BSnew and BSold and whether the traffic is time dependent (e.g., voice, video) or throughput dependent (e.g., data). It should be noted that the performance of the partial rerouting is strongly dependent on the performance of the crossover discovery algorithm.

12.2.3.2 Special Metrics

With respect to partial rerouting, we study several performance metrics, including old connection teardown time, new connection setup time, the time required to invoke crossover discovery algorithm, the time required to actually discover the crossover switch, and the efficiency of path reuse.

  1. Old connection teardown time (Ttear): It is the time required for BScross to inform BSold to tear down the old connection and for BSold to comply.

  2. New connection setup time (Tnew): It is the total time elapsed since MHD requests a connection with BSnew till the confirmation of the establishment of the new connection.

  3. Time required for invoking the crossover discovery algorithm (Tcross): The total time in the rerouting process until the crossover switch discovery algorithm has been invoked.

  4. Time to discover the crossover switch (Tdiscover): The total time for finding the crossover point after invoking the crossover discovery algorithm. This term depends on the algorithm used.

  5. Partial reuse efficiency (ηpart): The fraction of the new path that has been reused.

12.2.4 Tree Rerouting

Tree routing involves setting up and using a tree with base stations as nodes to communicate to a group of base stations. The tree can be either static or dynamic.

12.2.4.1 Tree-Group Rerouting

Figure 12.9 describes the protocol of a generic tree-group rerouting without hints. In this case, there is a dynamic multicast tree built that is used to multicast data to a group of base stations. The base station BSroot is the root of the multicast tree. The messages used to perform rerouting are described in the figure.

click to expand
Figure 12.9: Tree-group rerouting without hints.

12.2.4.2 Tree-Virtual Rerouting

Figure 12.10 describes the protocol of a tree-virtual rerouting without hints. Let BSroot be the root of the virtual tree that connects a group of base stations. There are no tree-virtual rerouting algorithms with hints described in the literature. However, it is easy to conceive such a class. The most important aspect of this class of rerouting is that one path (from the root of the tree to the leaves of the tree) is active at a time unlike the tree-group rerouting. We assume that the virtual tree is established statically and is in place before the commencement of the rerouting process.

click to expand
Figure 12.10: Tree-virtual rerouting without hints.

12.2.4.3 Implementations

Acampora [67] describes a rerouting scheme using virtual connection trees in a wireless ATM environment. A virtual connection tree is a collection of base stations and wired switching nodes and the connecting links. Each virtual connection tree, which is statically built prior to rerouting, has a fixed root node and the leaves of the tree are base stations. For each mobile connection, the tree provides a set of virtual connection numbers in each direction, each associated with a path from a leaf and root. When a mobile host that is already in the tree wants to handoff to another base station (in the same tree), it starts to transmit ATM cells with the connection number assigned for use between itself and the new base station. The cells flow along the fixed path between the new base station and the root. Appropriate translation tables are maintained at the nodes of the tree to understand and implement handoff and the consequent rerouting. Seshan [68] describes a scheme for tree-group rerouting called multicasting reestablishment. The protocol of the generic tree-group rerouting described earlier is based on Seshan's proposed scheme, which includes strategies for multicasting rerouting with and without hints. However, Seshan's scheme does not address the issue of how the members of the groups are decided. Ghai and Singh [69] describe a tree-group rerouting scheme based on a dynamic grouping of base stations and the mobility characteristics of the MH. The scheme is for a picocellular network with a three-tier hierarchy of cells. The scheme does not take advantage of hints to aid in rerouting.

12.2.4.4 Special Metrics

12.2.4.4.1 Tree-Virtual Rerouting
  • Virtual tree setup time (Tvtree-setup): It is the time required for setting up the virtual tree, which includes the time to choose the root, broadcast the information to all the nodes of the tree, and for all the nodes to join the tree.

  • Virtual tree teardown time (Tvtree-tear): It is the time required to tear down the virtual tree.

  • Number of nodes in virtual tree (Nvtree): Nvtree is determined statically and remains fixed.

12.2.4.4.2 Tree-Group Rerouting
  • Multicast tree setup time (Tmcast-setup): The time required to set up the multicast tree.

  • Multicast tree teardown time (Tmcast-tear): The time required to tear down the multicast tree.

  • Number of nodes in the multicast tree (Nmcast): Nmcast depends on the algorithm in question. In static algorithms, this value is fixed and remains constant. In algorithms that dynamically decide the number on-the-fly, the number changes dynamically.

  • Multicast join/leave time (Tmcast-jn, Tmcast_lv): The time required for nodes of the multicast tree to join or leave the tree.

12.2.5 Cell Forwarding Rerouting

Cell forwarding rerouting involves using a specialized base station (BSfwd) as an "anchor." Cell forwarding is used in many rerouting schemes implicitly. Full rerouting and partial rerouting can be considered specialized cell forwarding rerouting schemes. The anchor in all these cases is BSold. Figure 12.11 describes the protocol of a generic cell forwarding rerouting without hints. There is no known cell forwarding scheme described in the literature, although such a scheme can be easily conceived. In the remainder of the discussion, when we refer to cell forwarding, we assume that the anchor is the old base station; thus, in this case data is simply forwarded from the previous destination base station. Therefore, we simply do not need any signaling other than the regular handshake without hints. In other words, steps 5 through 10 do not exist; this way, we avoid the overhead of setting up the new path and tearing down the old path.

click to expand
Figure 12.11: Cell forwarding rerouting without hints.

12.2.5.1 Implementations

Cell forwarding and its variations are used in almost all rerouting schemes. In most cases, the old base station, BSold, acts as the anchor. Yuan [70] describes a scheme using a specialized "anchor" to perform the cell forwarding.

12.2.5.2 Special metrics

In the case of cell forwarding, we study the following special metrics:

  • Old connection teardown time (Ttear): This is true only if there is a specialized anchor used for forwarding data.

  • New connection setup time (Tnew): This is true only if there is a specialized anchor used for forwarding data.

  • Time to establish a path between BSold and BSfwd (Tcellfwd-path): It is the time required to set up a path between BSold and BSfwd.

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

[58]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.

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

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

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

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

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

[64]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.

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

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

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

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

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

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




Wireless Internet Handbook. Technologies, Standards and Applications
Wireless Internet Handbook: Technologies, Standards, and Applications (Internet and Communications)
ISBN: 0849315026
EAN: 2147483647
Year: 2003
Pages: 239

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net