Network Working Group Xingwei Wang INTERNET-DRAFT Changqing Yuan Expires: August 2004 Bo Song February 2004 Soft-Handoff-Supporting Motion-Prediction-and-QoS-Negotiation-Based Fan- Shaped Flexible Resource Reservation and Rerouting Mechanisms in Mobile Wireless Internet Status of This Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or cite them other than as "work in progress". The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/lid-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Abstract Considering movement characteristics of mobile users, the authors have proposed a kind of soft-handoff-supporting motion-prediction- and-QoS-negotiation-based fan-shaped flexible resource reservation mechanism, which can provide QoS guarantees to mobile user effectively. The signaling overhead for handoff gets effective control by reverse rerouting mechanisms, being much advantageous than partial rerouting and complete rerouting. Combining the above two mechanisms, soft handoff can be guaranteed and high resource utilization can be attained in the mobile wireless Internet. Simulation has shown the proposed mechanisms are both efficient and effective. Wang, et. al Expires - August 2004 [Page 1] Internet-Draft MPQN-based FSFR3 February 2004 TABLE OF CONTENTS 1. Introduction.................................................... 2 1.1 Resource Reservation........................................ 4 1.2 Rerouting................................................... 4 2. Details......................................................... 5 2.1 Motion-prediction-and-QoS-negotiation-based fan-shaped flexible resource reservation mechanisms........................ 5 2.1.1 Movement velocity determination........................ 7 2.1.2 Movement trend judgment based on the user movement velocity and probability model............................... 8 2.1.3 Flexible fan-shaped resource reservation styles and parameter computation....................................... 10 2.1.4 Solutions to the frequent handoff problems with low velocity mobile users....................................... 11 2.1.5 Procedures of the flexible fan-shaped resource reservation................................................. 12 2.1.6 QoS negotiation....................................... 13 2.2 QoS control at the wireless access router.................. 16 2.3 reverse rerouting.......................................... 17 2.3.1 Comparison among reverse rerouting, partial rerouting and complete rerouting.......................................... 18 2.3.2 Tradeoff between the reverse rerouting and complete rerouting................................................... 21 2.3.3 reverse rerouting algorithm........................... 22 3. Conclusions.................................................... 22 4. References..................................................... 22 5. Author's Addresses............................................. 24 1. Introduction Mobile wireless Internet has become a great trend on the NGI (Next Generation Internet) research with the great progress of mobile communication and Internet technology. It provides personalized information service to mobile users. However, due to user mobility, the topology and resources of mobile wireless Internet change dynamically. How to manage and utilize network resources effectively to meet the QoS (Quality of Service) demand of mobile users has been a difficult problem that mobile wireless Internet must confront with. Wang, et. al Expires - August 2004 [Page 2] Internet-Draft MPQN-based FSFR3 February 2004 +--------------+ +--------------+ | +---+ | | +---+ | | |WAR| | | |WAR| | | +---+ | *----* *----* | +---+ | | / \ | / \ / \ | / \ | | +---+ +---+-+--* ER * * ER *--+-+---+ +---+ | | |WAR| |WAR| | \ / \ / | |WAR| |WAR| | | +---+ +---+ | *----* *----* | +---+ +---+ | +--------------+ \ / +--------------+ WLAN \ / 3G \ / +------------\-----/-----------+ | Core *----* | | Network / \ | | * CR * | | \ / | | *----* | | / \ | | / \ | | *----* *----* | | / \ / \ | | * CR * * CR * | | \ / \ / | | *----* *----* | +---------|----------|---------+ +---------------+ | | +--------------+ | +---+ | | | | +---+ | | |WAR| | | | | |WAR| | | +---+ | *----* *----* | +---+ | | / \ | / \ / \ | / \ | | +---+ +---+-+--* ER * * ER *----+-+---+ +---+ | | |WAR| |WAR| | \ / \ / | |WAR| |WAR| | | +---+ +---+ | *----* *----* | +---+ +---+ | +---------------+ +--------------+ SATELLITE GSM CR --------------- Core Router ER --------------- Edge Router WAR --------------- Wireless Access Router Figure 1 mobile wireless Internet architecture The architecture of mobile wireless Internet is illustrated in Figure 1. It is composed of core network and access network. Accordingly, there are three kinds of important routers in mobile wireless Internet: core router, edge router and access router. Every wireless access router is responsible for a wireless cell. Wang, et. al Expires - August 2004 [Page 3] Internet-Draft MPQN-based FSFR3 February 2004 1.1 Resource Reservation The main goal of the resource reservation mechanism is to allocate network resources to user applications. To offer the required services [4], some mechanisms are used to setup and maintain certain resource reservation states along the data flow path by routers. In the mobile wireless Internet environment, wireless channels are unreliable and bandwidth resources are limited. Under such circumstances, when a mobile user moves from one cell to another cell, to make advanced resource reservations for him is an effective way to ensure his communication QoS. Some kinds of resource reservation schemes used in mobile wireless Internet environment such as MRSVP[5] and HMRSVP[8] have been presented. Although those schemes all take the movement characteristics of mobile users into account, they do not consider how to make use of user movement rules and resource utilizations before and after handoff. [7] has analyzed user movement rule prediction, however, it does not take user movement velocity into account. [10] has presented an adaptive resource reservation scheme, guaranteeing smooth communication with QoS degradation, thus unsuitable to high QoS services. With main characteristics of mobile wireless Internet environment in mind, based on effective prediction on user movement velocity, a flexible fan-shaped resource reservation mechanism is presented. It depends on motion prediction and QoS negotiation means, supporting soft handoff in mobile wireless Internet. 1.2 Rerouting In Mobile wireless Internet, rerouting after the handoff is also an important problem. To solve this problem, there are mainly two schemes: partial rerouting and complete rerouting[12]. In partial rerouting, the original routing information are reserved as much as possible, only the varied parts are updated. One of its advantages is less processing time and overhead. However, the new route probably is not optimal, leading to inefficient network resource utilization, and the original QoS guarantees (such as delay and delay jitter) broken. In complete rerouting, the original routing is completely replaced with the newly generated one by default routing algorithm, which is usually optimal. One of its main disadvantages is higher processing delay and overhead. Both these two kinds of rerouting schemes have distinguished features. In [16], FHRP(Footprint Handover Rerouting Protocol) has been presented. It takes advantage of both features of partial and complete rerouting. To some degree, it is only optimal to Wang, et. al Expires - August 2004 [Page 4] Internet-Draft MPQN-based FSFR3 February 2004 continuously moving user with frequent handoff within large motion region. For small motion region, partial rerouting is still used. In mobile wireless Internet, a majority of mobile users move within a small range, leading to large amount of extended routes existing in the network, occupying large amount of network resources, making network performance degrade. Taking features of complete rerouting and partial rerouting into account and based on the topology characteristics of mobile wireless Internet, a reverse rerouting mechanism is proposed by the authors. 2. Details In the proposed soft-handoff-supporting motion-prediction-and-QoS- negotiation-based fan-shaped flexible resource reservation mechanisms, the user motion velocity is determined by the wireless cell magnetic field intensity distribution in the mobile wireless Internet. The probability model in [9] is used to identify the user motion profile. The procedures of resource reservation, procedures of QoS negotiation and QoS control policies of wireless access router are described. Finally, a reverse rerouting mechanism is introduced. 2.1 Motion-prediction-and-QoS-negotiation-based fan-shaped flexible resource reservation mechanisms It can provide mobile users QoS guarantees effectively to make advanced resource reservation in the target wireless cell where they will move. However, with the random nature of user motion in mind, a flexible fan-shaped resource reservation mechanism is proposed, in order to improve the accuracy of resource reservation with relevant cells or to make certain the mobile users with random movement receiving QoS guarantees from surrounding cells with high probability. It is illustrated in Figure 2. Wang, et. al Expires - August 2004 [Page 5] Internet-Draft MPQN-based FSFR3 February 2004 +--+--+ | 0 | +--+--+ ^ | | +---+ +---+ +---+ +---+ | / *--\*-/---* \ / \ / \ | \ 1 / \ 2 \/ \ 3 / \ 4 / | +---+ +---+\ +---+ +---+ | \ | +---+ +---+ \ +---+ +---+ | / *---\*-/-* \ / \ / \ | \ 5 / \ 6\ / \\ 7 / \ 8 / | +---+ +--|+ +---+ +---+ | *-> * | | +---+/ +--|+ +---+ +---+ | / /\ / | \ / | \ / \ | \ 9 * / \10 * / \ | 11/ \ 12 / | / +---+ +--|+ +---+ +---+ +--+ | | +---+ +--*+ +---+ +---+ / \ / | \ / | \ / \ \ 13 / \14 * / \ *15 / \ 16 / +---+ +-/-+ /---+ +---+ Figure 2 illustration of flexible fan-shaped resource reservation In Figure 2, a mobile user movement trend is indicated by the arrow direction. He is communicating with some others in wireless cell 0. According to his movement trend, which the arrow tells, wireless cell 10 should be considered as the main target of resource reservation. However, in order to prevent QoS guarantees disrupted or degraded due to the sudden diversion of user movement, the necessary amount of resources should also be reserved within wireless cell 5,6 and 14. If the mobile user moves rapidly, resource reservations should also be considered within wireless cell 12, 7, 11 and 15. Thus, the so-called fan-shaped resource reservations have emerged, with cell 9 being its center. When the mobile user changes his movement trend from horizontal to vertical, the fan-shaped piece's angle should be enlarged or contracted accordingly. When the mobile user change movement trend along horizontal direction, the radius of the fan- shaped piece should be increased or decreased accordingly. Thus the goal of providing sufficient QoS guarantees to mobile users has been achieved. Wang, et. al Expires - August 2004 [Page 6] Internet-Draft MPQN-based FSFR3 February 2004 2.1.1 Movement velocity determination +----------------------------+ / \ / \ / --* p4,s4 \ / / \ / / \ / - -* p3,s3 ~/| \ / / / / \ / / / / \ / / - / \ + - / / + \ / / -* p2,s2 / / \ / - / / / \ / / / / / \ - / - / / \ / - / / / \ // -- / / \ *----------* p1,s1 / / \ ~~ / \ / +----------------------------+ Figure 3 illustration of user movement Movement velocity is determined mainly by tracing wireless cell's wireless signal intensity here. Record the magnetic field intensity of the wireless cell, which is serving a mobile user at four time spot:t1,p1,t2,p2,t3,p3,t4,p4. According to wireless cell magnetic field intensity distribution and p1, p2, p3 , p4 , compute the distances between the relevant base stations and mobile user. Then, get user motion velocity and acceleration while he is leaving the center of the wireless cell. Both velocity and acceleration are vectors, and denote them using v and a as follows: |v|=[(s2-s1)/(t2-t1)+(s4-s3)/(t4-t3)]/2 (1) get the value of acceleration according to the formula as follows : 2 2 2|a|s=|v2| -|v1| (2) s=[(s3+s4)-(s1+s2)]/2 (3) |v1|=(s2- s1)/(t2-t1) (4) Wang, et. al Expires - August 2004 [Page 7] Internet-Draft MPQN-based FSFR3 February 2004 |v2|=(s4-s3)/(t4 -t3) (5) 2.1.2 Movement trend judgment based on the user movement velocity and probability model. A summary of some movement categories and their movement velocity ranges is shown in Table 1. +-------------+----------------+-------------------------+ | Movement | Movement | Movement | | categories | velocity(km/h) | diversion probability | +-------------+----------------+-------------------------+ | Airplane | >300 | Very Low | +------------------------------+-------------------------+ | Train | 80-200 | Low | +------------------------------+-------------------------+ | Car | 20-200 | Not High | +------------------------------+-------------------------+ | Bicycle | 0-20 | High | +------------------------------+-------------------------+ | On Foot | 0-10 | Very High | +------------------------------+-------------------------+ Table 1 analysis table of movement diversion For the movement diversion probability, the movement tracks of the above mentioned movement categories are also taken into consideration. Except bicycle and on-foot categories, others are usually on the straight-line-shaped track in the normal conditions; in other words, the movement diversion probability is low. However the movement diversion here is not on its traditional meanings.It is limited to one wireless cell. In other words, the possibility of movement diversion is considered within the scope of a wireless cell. Although a certain mobile user is surely changing his movement direction within his current wireless cell, due to the very small arc of his movement track, it can be considered as a straight line, and then movement diversion is not considered occurring, as shown in Figure 4. Wang, et. al Expires - August 2004 [Page 8] Internet-Draft MPQN-based FSFR3 February 2004 ~ ~ ~ ~ *---+---* *-~-+---* ~ / \ / ~ \ / ~ \ / ~ \ * ~ * * ~ * \ ~ / \ ~/ \~ / \ /~ ~ *---+---* *---+---* ~ ~ ~ ~ Figure 4 low velocity diversion and high velocity diversion Such cases often take place. As shown in Figure 4, for only one wireless cell, high velocity movement diversion can be treated as just moving in straight-line, that is, the higher the movement velocity, the lower the movement diversion probability. Thus, it can be roughly deduced from the above reasoning: the higher the velocity, the higher the movement acceleration, and the lower the movement diversion possibility. According to [9], under the precondition of constant velocity, the probability density function of the angle B which denote the mobile user's movement diversion direction satisfies the normal distribution with its average value is zero. According to above analysis and the conclusion from [9], such a conclusion can be drawn: the higher the velocity of mobile user is, the lower the normal distribution deviation is, and vice versa. In [7], the effect of movement velocity value has not been taken into consideration. Thus, it can not adapt to velocity variation well and can not provide sufficient QoS guarantees to mobile users. For this reason, in the proposed flexible fan-shaped resource reservation mechanisms, define the probability distribution function of B as follows: Suppose velocity is v, acceleration is a, the fan-shaped piece angle is B, then B 2 1 -(---) P(B)=---------e c (6) +---- \/ 2*PI*c Here,c=k(|v| +a*/_\t) (a>0 means velocity is increasing, a<0 means Wang, et. al Expires - August 2004 [Page 9] Internet-Draft MPQN-based FSFR3 February 2004 the velocity is decreasing), /_\t is a short time period (usually one second). Here, use acceleration to slightly tune the current velocity, so that the effect of future movement velocity variation on B has also been taken into account. 2.1.3 flexible fan-shaped resource reservation styles and parameter computation Flexible fan-shaped resource reservation mechanisms support two styles of resource reservations: soft reservation and hard reservation. The former is a type of shared resource reservation. Other users can use the reserved resources, if the user who has made the resource reservation is not using the reserved resources. However, once the user who has made the resource reservation needs to use the reserved resources, the temporary user must release those resources immediately. The latter is a style of resource reservation with exclusion. Only the user who has made reservation can use the reserved resources, even if he has no use of the reserved resources currently, others cannot use the reserved resources, unless the reserved resources have been released. Consider the example shown in Figure 2, the proposed flexible fan- shaped resource reservation mechanisms make hard resource reservation in the wireless cell 10, and make soft resource reservation in wireless cell 5, 6, 14 and even 1,2,7,11,15. Like this, not only resource reservation is effectively made in the wireless cell 10 where the mobile user will enter with very high probability, but also make resource reservation in place for the wireless cells where user will move with relatively low probability, reducing the negative effect of handoff on QoS when the mobile user actually has moved into the wireless cell with low arriving probability. Suppose the user QoS class is L. According to the probability distribution of B, set a probability guarantee threshold for class L=i, i.e.Ui = k0/i , k0 is a constant. Then, according to formula (6), P(Bi)=Ui is satisfied. -1 Suppose P (Ui) is the reverse function of P(Bi), then -1 Bi = P (Ui) (7) It can be seen that, the higher the user QoS class is, the smaller the value of the threshold is, the bigger the B value is. The original resource release time Tf , the resource reservation startup time T and the radius of the fan-shape r are computed as Wang, et. al Expires - August 2004 [Page 10] Internet-Draft MPQN-based FSFR3 February 2004 follows: Q Tf = k1 * ------ (8) Pf * L +- -|v| / e * Q | k2 * --------- , |v|=v0 \ +- |v|*Q r=k3 * ------- (10) L In formula (8) (9) (10), k1,k2 and k3 all are tuning coefficients, and Q is the network load parameter. In formula (8), Pf is the user coming back probability. According to the probability model in 2.1.2,Pf=P(PI). In addition, v0 is a threshold of velocity. When the current movement velocity is bigger than or equal to v0, the value of T is zero, initiating the resource reservation immediately; otherwise, the value of T is greater than zero, and only initiating the resource reservation after time period T has elapsed. 2.1.4 Solutions to the frequent handoff problems with low velocity mobile users According to the probability distribution of B, if the user movement velocity is very low, the movement diversion possibility will be very high. If a mobile user changes his movement direction back and forth frequently in a short time period, some operations, such as initiating resource reservation and releasing the reserved resources, will certainly take place frequently, causing severe waste of resources. Thus, some control measures must be taken to prevent the occurrence of such situation. The following countermeasures can be considered. (1) Reducing the occurrence of handoff It is well known that there is no strict boundary between wireless cells. On the boundary, the magnetic field of two neighbor cells intersects, as shown in the Figure 5. For a mobile user with high velocity, when he moves to point A, the probability of his moving Wang, et. al Expires - August 2004 [Page 11] Internet-Draft MPQN-based FSFR3 February 2004 into the neighboring wireless cell is very high, and then resource reservation at point A should be initiated and handoff occurs. For a mobile user with low velocity, according to the statement in 2.1.2, the probability of his movement diversion is relatively high. If resource reservation is initiated and handoff take place at point A, due to the high probability of his coming back and handoff again after a while, severe resource waste will occur. Therefore, for a mobile user with low velocity, only when he moves across point B, be resource reservation initiated and handoff taking place, reducing the occurrence frequency of resource reservation and handoff significantly. *---+---*---+---* / / \ \ / / \ \ * A@* @*B * \ \ / / \ \ / / *---+---*---+---* Figure 5 illustration of decrease handoff (2) Postpone the release of the reserved resources in the original wireless cell Even if a mobile user with low velocity has crossed wireless cell boundary and the handoff has occurred, the probability of his returning is still high. Thus, the action of releasing the original reserved resources should be postponed, keeping the original resource in soft reserved state for a while. Then, when the user returns to the original wireless cell again, it is unnecessary to initiate resource reservation again. 2.1.5 procedures of the flexible fan-shaped resource reservation The procedures of the motion-prediction-and-QoS-negotiation-based flexible fan-shaped resource reservation mechanisms are as follows: Step 1: The mobile user traces magnetic field intensity of current base-station and its variation. When the magnetic field intensity becomes lower than the present threshold, go to step 2. Step 2: The mobile user sends a request message to the access router of current wireless cell, requiring the router to do certain reservation computation for handoff. When the corresponding router has received the request message, it determine the movement velocity v and acceleration a of the mobile user rapidly. According to the mobile user's QoS class L and the Wang, et. al Expires - August 2004 [Page 12] Internet-Draft MPQN-based FSFR3 February 2004 load parameter of network Q, the router computes the following parameter values: resource reservation initiation time T, the original reserved resource releasing time Tf, fan-shape piece angle B, fan-shape radius r. According to the values of B and r, determine the target wireless cells where resource reservation should be made, go to step 3. Step 3: According to T, the access router of current wireless cell send request messages to the access routers of the target wireless cells, notify them of the following information: bandwidth to be reserved, reservation direction, reservation style (soft or hard), etc, go to step 4. Step 4: The access routers of the target wireless cells issue resource reservation signaling packet.If the available resources in some wireless cells cannot sustain the required QoS levels of the handed-in users, the corresponding access routers and users will make QoS negotiation (refer to 2.1.6). If QoS negotiation succeeds, go to step 8; otherwise go to step 5. Step 5: If the user chooses giving up, go to step 6; if he chooses waiting, go to step 7. Step 6: The access router of current wireless cell sends notifications to those access routers that have failed in resource reservation or have not used the reserved resources though they have made successful resource reservation, and tell them to release the resources. The procedures of the resource reservation end. Step 7:The access router of current wireless cell continue to send request messages to the access routers of the wireless cells that have failed in resource reservation, try to make resource reservation again, according to the original request. Try it at most M times. If succeed, go to step 8; otherwise go to step 6. Step 8: Resource reservation has succeeded. Within the wireless cell that the user has moved into, the user uses the reserved resource to continue his communication, the procedures of the resource reservation end. For the wireless cell that the user does not move into, go to step 6. 2.1.6 QoS negotiation The purpose of making resource reservation is to guarantee the QoS of users, but when the available network resources cannot meet the resource reservation requests of users, QoS negotiation is necessary. Here, QoS negotiation has two stages as follow: Wang, et. al Expires - August 2004 [Page 13] Internet-Draft MPQN-based FSFR3 February 2004 Network negotiation stage: check whether there is enough deprivable resource along the determined route. The high priority user can deprive the resources of the low priority user. For example, the real-time service user can deprive the resources of non-real-time service user. User negotiation stage: when there are no deprivable resources along the determined route, negotiate with the user, asking him whether he agree to degrade his QoS requirement, or some others cases. There are also two ways of deprivation at the stage of network negotiation: soft deprivation and hard deprivation. Soft deprivation: Before the user handoff, the reserved resources by him can be used by other users with low priority. However, once that user who has made resource reservation handed-off, the low priority user should return the resources to him immediately. In the proposed flexible fan-shaped resource reservation mechanism, for the wireless cells where resources are limited and the user will enter with low probability, soft deprivation is carried out. Hard deprivation: Current user must return deprivable resources to the high priority user who has reserved those resources. For the wireless cells where resources are limited and the user will enter with high probability, hard deprivation is carried out. The procedures of QoS negotiation is described as follows: At the beginning, a mobile user sends a message to make a request for resource reservation. After it has received the message, according to the content of the message about the user QoS request, the access router initiates corresponding resource reservation for the mobile user. If the available resources in the network can meet the user's demand, the user keeps normal communication. If resource reservation failed, i.e. the user QoS requirement cannot be satisfied end-to-end, QoS negotiation takes place. At first, enter into network negotiation stage, and carry out soft or hard deprivation; If succeed, the user keep normal communication; otherwise, enter into user negotiation stage, asking the user whether he agree to degrade his QoS requirement. If the user agreed, keep communication with lowered QoS, at the same time resource status being monitored. If enough resources in the network become available to meet the original user QoS requirement again, the access router take necessary measures to return to the original QoS level. If the user does not agree to degrade his QoS requirement, there are still two kinds of choices to be made. One is that the user waits for a while, the other is the user give up this communication. If the user chooses the latter, the procedures of resource reservation end. If the user chooses waiting Wang, et. al Expires - August 2004 [Page 14] Internet-Draft MPQN-based FSFR3 February 2004 for a while, the access router needs to do resource reservation again periodically. Once succeeded some times later, the access router notifies the user of resuming normal communication. If M times failures have been encountered, the access router notifies the user that resource reservation failed. +-----------+ | start | +-----+-----+ | +-----V-----+ | n=1 | +-----+-----+ | +---------V----------+ |resource reservation|<------------------------------+ +---------+----------+ | | | Y +------------------+ N | +--| succeeded? |----------+ | | +------------------+ | | | +-------------------V------------------+ | +------V------+ | network negotiation | | | normal | | Y +---------------------------------+| | |communication|<--- +---| soft/hard deprivation succeeded?|| | +------^------+ | +---------------------------------+| | | | |N | | | +-------------------|------------------+ | | | | | +-------------------V------------------+ | | | user negotiation | | | | Y +--------------------------+ N | | | | +----| degrade QoS? |-+ | | | | | +--------------------------+ | | | | | | | | | | +-|---------------------------------|--+ | | | | | | +-----------V----------+ +---V---+ | | | |<--------+ | n=n+1 | | | + low Qos communication+<-----+ | +---+---+ | | | | | | | | | +-----------+----------+ | | +---V---+N| | | | | | n>M? |-+ | +-----------V---------------+ | | +-------+ | |network resource monitoring| | | | Y | +-----------+---------------+ | | +-------V-------+ | | | | |notify resource| | | | | | reservation | Wang, et. al Expires - August 2004 [Page 15] Internet-Draft MPQN-based FSFR3 February 2004 | +------------V-----------+ N | | | failure | | | resource released? |-----+ | +---------------+ | +------------------------+ | | | | | Y | | | | | |Y +-----------V-----------+ N | +--| QoS satisfied? |--------+ +-----------------------+ Figure 6 procedures of QoS negotiation 2.2 QoS control at the wireless access router Because the wireless channel resource is limited and unreliable (such as high error rate and limited channel capacity), it is easy to become the bottleneck hop on the end-to-end route in mobile wireless Internet. In order to use network resources efficiently, combined with the proposed resource reservation mechanisms, add necessary QoS control function to the access router of wireless cell. In a wireless cell, there are two types of connection request: request that a local user makes in local wireless cell, the other is the handoff request that a foreign user makes. Obviously, the effect of interrupting an existing session is worse than refusing a new connection request. Thus, in the QoS control policy of the wireless access router, the handoff request should have higher priority than the new connection request. Because wireless channel is often influenced by natural environment, the wireless access router should know current wireless channel stutus of its cell, so that it can provide enough QoS support to mobile users. The QoS control procedures of the wireless access router are as follows: (1) At first, a local user in the wireless cell, who wants to communicate with others, sends a registration request message to the local access router, registering capacities of sending and receiving packets, bandwidth requirement and budget. (2) After the access router has received the registration request, according to current network resource status, if possible, it allocates corresponding wireless channel resource to the user; otherwise, initiate QoS negotiation with the user. (3) For packets, which have entered into the access router, if the Wang, et. al Expires - August 2004 [Page 16] Internet-Draft MPQN-based FSFR3 February 2004 resources of current network are limited, put them into corresponding queues. There are two queues. One is for real-time services; the other is for best effort services. Give high priority to real-time packets. (4) For the resource reservation request packet sent by the user who will handed-in the local wireless cell, if there are enough resources available, the router forward it immediately, at the same time, the access router makes a resource reservation for the user in the wireless channel; otherwise, the access router gives them higher priority than real-time ones. 2.3 reverse rerouting Before introducing the concept of the reverse rerouting, describe the concept of resource handover firstly. In mobile wireless Internet, after a mobile user handoff, direct use of the resource along the same parts between original and new route is called resource handover. When a mobile user handoffs, look for the router that lead to the access router of the target wireless cell with lowest delay or lest hops along the current route reversely, and then do resource reservation from that router to the access router of the target wireless cell; for the same parts along the original route, just do resource handover. Resource reservation overhead has been reduced significantly, especially in the case that handoff takes place between two neighboring wireless cells administered by the same edge router. Such a kind of mechanism is called reverse rerouting. For example, in Figure 7, R1, R2, R3, R4 and R5 are all routers. R4 and R5 support wireless access. H0 is a static user or a mobile user without handoff. MH is a mobile user who will make handoffs. When MH moved into R4 wireless cell from R5 wireless cell, along the route from access router H0 to router R5 reversely, H0 looks for the router that get to the R4 with the lest hops. The result is that the router R3 is the access point with the shortest path. Thus, along the path from the access router of H0 to R3, just do resource handover; only for the path from R3 to R4, do resource reservation. For the original path from R3 to R5, after Tf has elapsed, if the MH does not return, the original reserved resources will be released. Wang, et. al Expires - August 2004 [Page 17] Internet-Draft MPQN-based FSFR3 February 2004 +----+ +-----+ _ _ _ / \ | H0 +------+ \ R1 + +-----+ ' ' ' \ \ / ' +----+----------+----+ ' / / / \ ' / | + R2 + +----+ ' \ \ / / \ ' \ +----+ + R3 + ' | / \ / ' /__ __ / +----+-'---------\---+----+ | ' | / \ | ' |+ R4 + | ' ' ' | \ / +----+ ' \ +----+-+ / \ ' -- -- --| + R5 + ' || \ / ' || +----+ ' || | ' || | ' || #------------|-------&----#----|-------------& | +-----+ | | +-----+ | | | MH +---------->+ MH | | | +-----+ | | +-----+ | #--------------------&----#------------------& ''''''''' original route _ _ _ _ _ the route after handoff Figure 7 illustration of rerouting The fulfillment of resource handover is through resource reservation marks. As Figure 7 illustrates, when the initial route is set up between H0 and MH, resources along the path from H0 to MH will be marked "reserved by H0 and MH" before normal communication is initiated. The reserved resources by H0 and MH will not be released until the communication between them is over. When MH handoff, if reverse rerouting mechanisms used, reserved resources along the path H0-R1-R3 should be handed over. R3 just select the R4 as its next hop to the MH, and resources along the path H0-R1-R3 are still kept in reserved state. 2.3.1 Comparison among reverse rerouting, partial rerouting and complete rerouting. Here, for rerouting signaling overhead, only resource reservation Wang, et. al Expires - August 2004 [Page 18] Internet-Draft MPQN-based FSFR3 February 2004 signaling overhead is taken into account. Due to the same size of resource reservation signaling packet, hop number of resource reservation path indicates rerouting signaling overhead directly. In this sense, the changed path length is shortest in partial rerouting, thus, signaling overhead is lowest; the changed path length is longest in complete rerouting, thus, signaling overhead is highest. Mobile wireless Internet is composed of core network and access network. Huge amount of handoffs take place between two neighboring wireless cells administrated by the same edge router, the result of reverse rerouting and complete rerouting is often the same, as figure 8 shows: - - - - / +----+ \ +-----+ - - - - / \ \ | H0 +--------+ R1 + \ +-----+ ~ ~ ~ ~ \ / - - - - - - - - - - ' ' ' ~ +----+-----------------+----+ \ ' ~ ~ |~ ~ ~ ~ ~ ~ ~ ~ / \ \ ' ' ' | ' ' ' ' ' ' ~+ R3 + | ' |' ' ' ' ~\ / / ' +----+ ' ' ~+----+ | '/ \ ' ' ~ ~ ~| | '+ R2 + ' ' ' ~| | '\ / ' ' ~| | '+----+ ' ' ~| | ' ' '|' ' ~| | | ' ~| | #------------|-------&----#-'-~|-------------& | +-----+ | | +-----+ | | | MH +---------->+ MH | | | +-----+ | | +-----+ | #--------------------&----#------------------& _ _ _ _ _ complete rerouting ' ' ' ' ' partial rerouting ~ ~ ~ ~ ~ reverse rerouting Figure 8 comparison of three kinds of rerouting schemes when handoff occurs between two wireless mobile cells administrated by the same edge router The meaning of every icon in figure 8 is the same as in figure 7. In figure 8, R2 and R3 are access routers, both connecting with edge router R1. From figure 8, It can be seen that the result of reverse Wang, et. al Expires - August 2004 [Page 19] Internet-Draft MPQN-based FSFR3 February 2004 rerouting and complete rerouting is the same. For the handoff between the wireless cells administered by the same edge router, reverse rerouting get the same result with complete rerouting, however, not only with the same signaling overhead as partial rerouting, but also with higher resource utilization. When hand off took place between the wireless cells that are administered by different edge routers, the reverse rerouting often get different result than complete rerouting. However, compared with the results of partial rerouting [12], the reverse rerouting consumes less bandwidth. Figure 9 illustrates these three kinds of rerouting schemes. _ _ _ _ /+----+ \ +-----+ _ _ _// \ \ | H0 +------+ R1 + | +-----+ ~ ~ ~ \ / /_ _ _ _ _ _ _ ' ' ' ' ~ +----+----------+----+ \ ' ~ / / \ \ ' ~ / + R2 + | ' +----+ ~ \ / / ' / \ ~ +----+ / ' + R3 + ~ / - - - ' \ / ~ / /_ _ ' +----+-~-~-~-~-~-~-~-+----+ \ ' ' ' ' | ' ' ' ' ' ' ~/ \ \ ' | ' '~+ R4 + | ' | ' ' ' '~\ / | ' +----+ ' '~+----+-+ | ' / \ ' '~ ~ ~ ~| | ' + R5 +' ' ' ' ~| | ' \ / ' ' ~| | ' +----+ ' ' ~| | ' ' ' |' ' ~| | | ' ~| | #------------|-------&----#----|-------------& | +-----+ | | +-----+ | | | MH +---------->+ MH | | | +-----+ | | +-----+ | #--------------------&----#------------------& _ _ _ _ _ complete rerouting ' ' ' ' ' partial rerouting ~ ~ ~ ~ ~ reverse rerouting Figure 9 comparison of three kinds of rerouting schemes when handoff occurs between two wireless mobile cells administrated by different edge router Wang, et. al Expires - August 2004 [Page 20] Internet-Draft MPQN-based FSFR3 February 2004 The meaning of every icon in figure 9 is the same as in figure 7. In figure 9, Router R1.R2 and R3 constitute a simple core network. R4 and R5 are the access routers. When MH handoff, use these three kinds of rerouting schemes respectively. As a result, for resource consumption, reverse rerouting is between complete rerouting and partial rerouting, however, for signaling overhead, reverse rerouting equals to the partial rerouting. Thus, compared with partial rerouting and complete rerouting, reverse rerouting is in a advantageous position. 2.3.2 Tradeoff between the reverse rerouting and complete rerouting Reverse rerouting usually does not achieve the same resource utilization of complete rerouting. Just like tradeoff made between reverse rerouting and complete rerouting in [16] when handoff occurs, tradeoff between reverse rerouting and complete rerouting is also needed here. Define some concepts at first. Reverse merging router: in reverse rerouting scheme, it is the router that be found in the opposite direction with the lowest hops to the access router that is serving for the user after the handoff. Reverse hop number: number of the hops between the reverse merging router and the access router that is serving for the user before the handoff, denoted by tn. Access hops: number of the hops between the access router that is serving for the user before the handoff and the access router that is serving for the user after the handoff, denoted by tm. Minimum of access hops: number of the hops between the reverse merging router and the access router that is serving for the user after the handoff, denoted by stm. In general, tradeoff between complete rerouting and the reverse rerouting is based on reverse hop number. The larger the reverse hop number is, the smaller the distance between the reverse handover router and the other communication end, the smaller the difference of signaling overhead between reverse rerouting and the complete rerouting, the more complete rerouting should be adopted. Set a constant K as a threshold of reverse hops, its value is determined according to actual networking situation. When tn<=K, use reverse rerouting; otherwise use complete rerouting. Wang, et. al Expires - August 2004 [Page 21] Internet-Draft MPQN-based FSFR3 February 2004 2.3.3 reverse rerouting algorithm Reverse rerouting algorithm is described as follows: Step 1: the value of tn is initialized to zero, reverse handover router is set to the access router that is serving for the user before handoff, and stm is set to the value of tm of the access router that is serving for the user before handoff. Step 2: Find the router of the previous hop in the opposite direction. If the router is the access router of the other communication end, then go to step 5; otherwise, increase the value of tn by one, go to step 3. Step 3: Compute the value of tm of current router. If tm<=stm, go to step 4; otherwise, go to step 2. Step 4: If tn<=K, then the reverse handover router is set to current router, the value of stm is set to the value of tm of current router, go to step2; otherwise, adopt complete rerouting scheme, using the default routing algorithm of the network to find the new route. The algorithm is finished. Step 5: Do resource handover operation on the reverse handover router, and do resource reservation between the reverse handover router and the access router that is serving for the user after handoff. The algorithm is finished. 3.Conclusions Considering movement characteristics of mobile users, the proposed soft-handoff-supporting motion-prediction-and-QoS-negotiation-based fan-shaped flexible resource reservation can provide QoS guarantees to mobile user effectively. The signaling overhead for handoff gets effective control by reverse rerouting mechanisms, being much advantageous than partial rerouting and complete rerouting. Combining the above two mechanisms, soft handoff can be guaranteed and high resource utilization can be attained in the mobile wireless Internet. Simulation has shown the proposed mechanisms are both efficient and effective. 4. References [1] Wang Xingwei et al. Research on Quality of Service Management Mechanisms in Distributed Multimedia Systems. Journal of Software, 1998, 9(2): 87-90. [2] C.Perkins. IP Mobility Support. RFC2002. Wang, et. al Expires - August 2004 [Page 22] Internet-Draft MPQN-based FSFR3 February 2004 [3] L.Zhang. RSVP:A New Rusource ReSerVation Protocol. IEEE Network, 1993, 7(5): 8-18. [4] Zhu Xiaogang et al. An Analysis is of the Implementation of Internet QoS Services Based on RSVP. Digit Communication, 1998, 4: 5-7. [5] ANUP KUMAR TALUKDAR etc. MRSVP:A Resource Reservation Protocol for an Integrated Services Network with Mobile Hosts. Wireless Networks, 2001, 7(1): 5-19. [6] Wang Chunfeng et al. Admission Control of Resource Management in Mobile Internet. ZHONGXING TELECOM TECHNOLOGY, 2003, 4: 29-32. [7] Huang Qiubo et al. An Improvement to Call Admission and Control Scheme in Next Generation Wireless Networks. MINI-MICRO SYSTEM, 2003, 24(8): 1437-1440. [8] Tseng Chienchao,lee Gwo Chuan,Liu Ren Shiou. HMRSVP:A Hierarchical Mobile RSVP Protocol. Wireless Networks, 2003, 9(2): 95-102. [9] I-Fei Tsai and Rong-Hong Jan. The lookahead strategy For distance-based location tracking in wireless cellular networks. ACM SIGMOBILE Mobile Computing and Communications Review, 1999, 3(4): 27-38. [10] Lee. K. Adaptive Network Support for Mobile Multimedia. In Proc. of the 1st Annual International Conference on Mobile Computing and Networking, pp. 62-74, November 1995. [11] Kevin Fall and Kannan Varadhman. The NS manual(formerly ns note and documentation). [12] Wangliang et al. Dynamic probability path optimization strategy for satellite handoff in LEO networks. JOURNAL OF CHINA INSTITUTE OF COMMUNICATION, 2002, 23(9): 8-15. [13] Fengjing et al. Extended RSVP Supporting Adaptability Routing. Computer Integrated Manufacturing Systems, 2002, 8(2): 155-161. [14] Li Hanbing et al. A Resource Optimization-Based Fuzzy Algorithm for QoS Path Selecting. JOURNAL OF COMPUTER RESEARCH & DEVELOPMENT, 2000, 37(3): 372-375. [15] Cuiyong et al. Research on Internetwork QoS Routing Algorithms: a Survey. Journal of Software, 2002, 13(11): 2066-2075. Wang, et. al Expires - August 2004 [Page 23] Internet-Draft MPQN-based FSFR3 February 2004 [16] Uzunalioglu H, Akyldizie, Yesha Y. Footprint handover rerouting protocol for low earth orbit satellite networks. Wireless Networks, 1999, 5(5): 327-337. 5. Author's Addresses Xingwei Wang, Changqing Yuan, Bo Song Computing Center of Northeastern University No.3-11,Wenhua Road,Heping District Shenyang,P.R.China Phone: 86-24-83687240 Email: wangxw@mail.neu.edu.cn Wang, et. al Expires - August 2004 [Page 24]