モバイルIPにおけるモバイルエージェントの動的Proxy-based負荷分散方式
7
0
0
全文
(2) cant delays at the mobility agents, i.e. foreign and home agents. Due to the highly unpredictable nature of the IP data traÆc, eÆcient load balancing applied in multiple home agents schemes is crucial to the overall performance improvement. In this paper, we propose a novel threshold-based dynamic load balancing policy that uses a realistic data-sharing model operational at each home agent. The proposed architecture eÆciently uses parallel processing for handling the overhead generated by the load balancing, which results in minimal performance degradation.. 1. Introduction. In this paper, we study the performance of Mobile IP [6] [5] [8], the Internet Protocol extension that provides proper mobility support. Here we consider the mobility extensions of IPv4, the worldwide used Internet engine, although the load balancing policies we evaluate can also be used in the case of IPv6. There are many Mobile IP implementations worldwide, as the international community is heading towards a signi
(3) cant increase of the number of potential mobile terminal users for whom mobility support must be provided. In our paper we develop a simulator for studying the performance of a multiple home agents protocol extension based on the one proposed in [2]. We propose a novel threshold-based dynamic load balancing policy, and compare the overall performance under various system con
(4) gurations. Our policy is based on a real-time data exchange mechanism between the home agents. The exchanged data consist of queue length information, designed to provide an accurate estimation of the servers load degree. This mechanism is implemented using a realistic overhead model that we propose and analyze. Furthermore, we introduce two new tuning parameters that can be adjusted in order to achieve optimal performance.. Doctoral Program in Engineering, University of Tsukuba, Tsukuba, Ibaraki 305-8573, Japan, [email protected] y Institute of Information Science & Electronics University of Tsukuba, Tsukuba Science City, Ibaraki 305-8573, Japan fkameda,[email protected]. 1 −13−.
(5) 2. The Proposed Load Balancing Policy for the Multiple HA protocol. We propose a threshold-based dynamic load balancing policy, designed to optimally distribute the load among the home agents. This policy operates on top of the infrastructure provided by the multiple home agents protocol extension and uses a realistic overhead model suitable for implementation.. 2.1. Description. There are several threshold-related load balancing policies proposed in distributed computer processing. We designed our own using the idea of the the double-threshold policy [7] as a starting point. We extended and adapted the concept to the requirements of the multiple home agent protocol environment. Our policy is proxy based, in the sense that the HN router is instructed to re-direct packets to di erent HAs, as opposed to classical packet dequeuing used in [7]. The threshold policy is sender initiated, meaning that only a \full" server can take the decision to re-assign a speci
(6) c source.. 2.2. Structure and Implementation. We de
(7) ne 2 functional layers with respect to the operating context:. . External Operation Layer - Visible from outside the server Each server must provide information about its queue status and update it to all the other servers. This information is stored in each server's threshold load balancing policy table (in short, policy table ), and will serve as reference for future load balancing actions. For example, every time a server attempts to transfer a source, it will choose the most vacant server available, according to its policy table. The more accurate the information in the policy table is, the better and more eÆcient the load balancing actions are expected to be.. . Internal Operation Layer - The internal representation Since our policy is sender initiated, only \full" servers are allowed to perform load balancing actions. Therefore, a server (HAi ) only needs to check whether its state is \full" or not. Regardless the number of QS's used externally, it is only the threshold that matters in this respect, and has direct impact on the load balancing decision process at HAi . The QS's are only used to determine when the server should advertise its queue length information, and do not in uence the load balancing decisions taken by HAi .. 2.3. Tuning Parameters. Our threshold-based load balancing policy is source-driven and proxy-based. As such, when balancing the load, servers need not extract individual packets from their queues, at the cost of weaker control over their queue lengths. Our threshold load balancing policy limits this drawback by providing two
(8) ne-tuning parameters: the number of queue slices (NQS) and the retry latency (RL). NQS is a server characteristic that can be used to tune up the granularity coeÆcient of the advertised data. An increase in NQS would provide more accurate information. Instead of \vacant" and \full", a theoretically unlimited range of \vacancy degrees" becomes available between these two. With precise. 2 −14−.
(9) information available, HAj would choose \the most vacant" server to transfer a source to, limiting the above described bouncing e ect. When a server (HAi ) queue length exceeds the threshold level, according to the threshold-based load balancing policy speci
(10) cation, HAi will attempt to transfer a source to another server. At this point, it will choose one of its assigned sources, according to the number of packets from that source in the queue. Since each source represents the aggregated traÆc of several corresponding hosts, it may be diÆcult to predict the future behavior of that source. As such, even though a source has sent a large number of packets to the queue of HAi , it may very soon become (almost) silent, leading to little change in the posttransfer server queue length. In order to avoid that, we provide a mechanism to evaluate the eÆciency of a transfer, based on retry loops. Every time a server transfers a source, a packet timer is set to N. After N packets are serviced (the timer expires), the queue status is re-evaluated and compared to the value stored when the transfer was made.. . Case A. If the new value is smaller, it means the source transfer was eÆcient, and the timer is set again to N. This process continues until the queue length falls below the queue threshold, at which moment the timer is reset automatically.. . Case B. If the new value is greater or equal than the old one, the transfer was ineÆcient and another source transfer is attempted. At this point, if a transfer is not possible because all the servers are full, another attempt is scheduled after N packets (timer set to N), and so on (unless HAi becomes empty).. We call the amount of packets retry latency (RL). This is an important parameter because it sets the frequency a server evaluates the eÆciency of a load balancing action (source transfer).. 3. Results. In this section, we show the performance curves for the threshold- based load balancing policy. We are particularly interested in assessing the in uence of the tuning parameters on the overall performance (see Table 1 for a description of the parameters used in the simulations). For comparison, we provide simulation results obtained without using dynamic load balancing, in a socalled \optimal static" con
(11) guration. The sources are statically assigned to the home agents, and never re-allocated during simulation. The initial assignment is performed such that the sources are optimally distributed among the home agents. Each simulation batch consists of several runs obtained for di erent values of the threshold, all other parameters held constant. The results presented have been obtained with BC = 5% con
(12) dence intervals, using the batch means method [?] with BS = 700. The sources generate highly irregular traÆc, with 1;21 =95, 5.. 3.1 The Number of Queue Slices 3.1.1. Homogeneous Sources and Servers. In Fig. 1, we show the e ect of di erent values of NQS on the mean response time, in a 4 identical server con
(13) guration, with 64 sources. The results are obtained for a server utilization U ' 60%. This is how the
(14) rmly ascending slope can be explained: due to the bursty characteristic of the traÆc, packets tend to queue up rapidly in queues, followed by a long silence. Low values of the threshold are associated 3 −15−.
(15) 14. Mean Response Time [s]. 12. 10. 8. 6. 4 N = 8, NQS = 1 N = 8, NQS = 10 N = 8, NQS = 20 Optimal Static 2 20. 30. 40. 50. 60 70 Threshold [packets]. 80. 90. 100. 1: The e ect of NQS = 1,10,20 on an 8 HA system with identical sources and servers. N=8, S=64, =7.5, =5, RL = 5. 図. with an increase in the load balancing activity, causing an improvement in the overall performance. It is shown that, for this con
(16) guration, NQS has a limited e ect on the mean response time. While NQS = 10 yields better performance than NQS = 1, NQS = 20 shows no improvement. Although the information accuracy increases with NQS, the bene
(17) t reaches the saturation level for NQS ' 10. In all three cases, the threshold policy clearly results in improved performance over the optimal static. 3.1.2. Heterogeneous Sources. Previously, the sources were considered to be identical, i.e. with identical traÆc shapes (1;2 ) and mean arrival rate during an ON period (). This time, the sources still have identical traÆc shapes, but generate packets at di erent rates. In a home network with 4 home agents with = 10 and 32 sources, we assign di erent mean arrival rates to sources in an ON state. Starting from the mean = 7:5, we obtain:. 8 >< 3:5 i = >: 11:5. i = 2k. ; k = 0 : : : 31. i = 2k + 1. In Fig.2, we plot the mean response time for the threshold policy with NQS = 1, 20 in an unbalanced sources con
(18) guration, compared with NQS = 1 for balanced traÆc. The mean response time for optimal static policy is also provided. NQS = 20 shows a slight performance improvement to NQS = 1 unbalanced, while NQS = 1 balanced outperforms the other two. In all cases the threshold policy behaves better than the optimal static. 3.1.3. Heterogeneous Servers. In an environment similar to 3.1.1, the impact of NQS on di erent capacity servers is examined. In this scenario, based on the assumption that each server is aware of its own processing capacity, the servers are assigned di erent values for thresholds. Conceptually, the threshold represents the maximum capacity of a server, corresponding to a limit-case waiting time. Therefore, by de
(19) ning a unique maximum waiting 4 −16−.
(20) 8. 7. Mean Response Time [s]. 6. 5. 4. 3. 2. NQS = 1, unbalanced NQS = 20, unbalanced NQS = 1, balanced Optimal Static. 1 20. 30. 40. 50. 60 70 Threshold [packets]. 80. 90. 100. 2: The e ect of NQS = 1,20 on an 4 HA system with unbalanced/balanced sources. N=8, S=64, =7.5, =10, RL = 5. 図. time for all the servers within one simulation run, we adjust the thresholds values from the formula : UT2 UTN UT 1 WT = UT 1 = 2 = : : : = N = , where N is the number of home agents, UTi represents the threshold for server HAi , and W T is the maximum waiting time. Given the system average UT and , each home agent HAi can calculate its own UTi . i are generated according to :. 8> < i = >: . ( N2. i) N. (N. (i + 1)) N. 2. if i < N2. . ; N = 2k. otherwise. In Fig. 3, like in the identical servers case, the mean response time for NQS = 10 is smaller than for NQS = 1, but here the performance gain is more signi
(21) cant. In conclusion, although greater values of NQS tend to generally decrease the global mean response time, the performance improvement is more substantial for irregular home network con
(22) gurations, with di erent capacity home agents.. 3.2. The E ect of the Retry Latency. In our simulation experiments, the retry latency RL exhibited a signi
(23) cantly lower level of sensitivity to traÆc changes, compared with NQS. In Fig.4, the mean response time for RL = 0, 1, 5, 20, 1000 is shown. Load balancing overhead is included, with QNC = 0.5 and MC = 0.1. Each \full" home agent transfers a source, and then re-evaluates its queue to estimate the eÆciency of the load balancing action. The retry latency is the amount of time elapsed until re-evaluation is performed (measured in number of processed packets ). If RL is very large (1000 in our case), such re-evaluation never occurs, and the \full" server only transfers one source until its queue length eventually falls bellow the threshold. This explains the horizontal shape of the mean response time curve for RL = 1000, similar to that of the optimal static. A too small value for RL, however, determined an unstable behavior, since several sources, at each home agent, were being continuously transferred in and out due to insuÆcient time to properly evaluate the eÆciency of the load balancing actions. A value of RL = 5 generally provided optimal performance for 5 −17−.
(24) 13 NQS = 1 NQS = 10 12 11. Mean Response Time [s]. 10 9 8 7 6 5 4 3 20. 30. 40. 50. 60 70 Threshold [packets]. 80. 90. 100. 3: The e ect of NQS = 1,10 on a system with 8 di erent capacity servers. N=8, S=64, =7.5, =5, RL = 5. 図. 7. Mean Response Time [s]. 6. 5. 4. 3. 2. RL = 0 RL = 1 RL = 5 RL = 20 RL = 1000. 1 20. 30. 40. 50. 60. 70. 80. 90. 100. Threshold [packets]. 4: The e ect of RL = 0,1,5,20,1000 on a system with 4 di erent capacity servers. N=4, S=64, =7.5, =10, NQS = 1, QNC = 0.5, MC = 0.1. 図. all the studied cases.. 4. Conclusions and Future Work. We have developed a simulator by which we studied the performance of a multiple home agents architecture in a Mobile IP network. Our simulator could be used with little modi
(25) cation in any proxy-based multiple agents scheme based on dynamic mobile host allocation using additional registration messages. We introduced a novel threshold-based load balancing policy, providing a comprehensive performance study and analyzing all the parameters involved. Special
(26) ne-tuning parameters (the number of queue slices and the retry latency ) have been introduced to provide better control over the policy behavior for di erent system con
(27) gurations, under various conditions of traÆc. Results showed that generally, our threshold-based policy clearly outperformed the optimal static scheme, in all the scenarios considered. The threshold-based load-balancing can be eÆciently used not only in the context of Mobile IP, but 6 −18−.
(28) N S. General. 1 2 . Threshold LBP. NQS RL QNC 表. The number of home agents in the system; The number of transmitting sources (equal to the number of mobile nodes because each source represents the aggregated traÆc for one mobile node); The rate a source turns ON with; The rate a source turns OFF with; (1 and 2 are exponentially distributed); The arrival rate of packets coming from one source in an ON state; The service rate of each home agent; The number of queue slices; The retry latency; The queue noti
(29) cation packets service coeÆcient; 1: Simulation Parameters. also in any similar environment operating on top of a proxy-based load balancing enabling infrastructure. Tuning parameters such as the retry latency can be con
(30) gured to provide adequate behavior in the case of non-deterministic sources, whether the input ow consists of network packets, jobs and the like. In our future work, we consider the possibility of an extension to the case of a hierarchical foreign agents architecture that could be used, for instance, inside large ISP domain areas.. 参考文献 [1] B. Chambless and J. Binkley. Harp - home agent redundancy protocol. 00.txt, IETF draft, work in progress, 1997.. chambless-mobileip-harp-. [2] Jason Jue and Dipak Ghosal. Design and analysis of a replicated server architecture for supporting ip-host mobility. Cluster Computing Special Issue on Mobile Computing, 1(2), 1998. [3] Hisao Kameda, Jie Li, Chonggun Kim, and Yongbing Zhang. Computer Systems. Springer Verlag, 1997.. Optimal Load Balancing in Distributed. [4] Jie Li and Hisao Kameda. Load balancing problems for multi-class jobs load balancing problems for multi-class jobs in distributed/parallel computer systems. IEEE Transactions on Computers, 47(3):322{332, 1998. [5] Charles Perkins.. . Addison-Wesley, 1998.. Mobile IP - Design Principles and Practices. [6] Charles Perkins ed. Ip mobility support for ipv4.. RFC 3220. , 2002.. [7] N. G. Shiravatri and P. Krueger. Two adaptive location policies for global scheduling algorithms. Proc. 10th Int. Conf. Dist. Computing Syst., pages 502{509, 1991. [8] James D. Solomon.. Mobile IP - The Internet Unplugged. 7 −19−. . Prentice Hall, 1998..
(31)
図
関連したドキュメント
It is suggested by our method that most of the quadratic algebras for all St¨ ackel equivalence classes of 3D second order quantum superintegrable systems on conformally flat
Keywords: continuous time random walk, Brownian motion, collision time, skew Young tableaux, tandem queue.. AMS 2000 Subject Classification: Primary:
Maria Cecilia Zanardi, São Paulo State University (UNESP), Guaratinguetá, 12516-410 São Paulo,
Then it follows immediately from a suitable version of “Hensel’s Lemma” [cf., e.g., the argument of [4], Lemma 2.1] that S may be obtained, as the notation suggests, as the m A
In order to be able to apply the Cartan–K¨ ahler theorem to prove existence of solutions in the real-analytic category, one needs a stronger result than Proposition 2.3; one needs
Our method of proof can also be used to recover the rational homotopy of L K(2) S 0 as well as the chromatic splitting conjecture at primes p > 3 [16]; we only need to use the
The first result concerning a lower bound for the nth prime number is due to Rosser [15, Theorem 1].. He showed that the inequality (1.3) holds for every positive
While conducting an experiment regarding fetal move- ments as a result of Pulsed Wave Doppler (PWD) ultrasound, [8] we encountered the severe artifacts in the acquired image2.
