Anycast service model and its QoS routing algorithm

Abstract

In the Internet, a group of replicated servers is commonly used in order to improve the scalability of network service. Anycast service is a new network service that can improve network load distribution and simplify certain applications. In this paper, the authors described a simple anycast service model in the Internet without significant affecting the routing and protocol processing infrastructure that was already in place, and proposed an anycast QoS routing algorithm for this model. The algorithm used randomized method to balance network load and improve its performance. Several new techniques are proposed in the algorithm, first, theminimum hops for each node are used in the algorithm, which are used as metric for computing the probability of possible out-links. The metric is pre-computed for each node in the network, which can simplify the network complexity and provide the routing process with useful information. Second, randomness is used at the link level and depends dynamically on the routing configuration. This provides great flexibility for the routing process, prevents the routing process from overusing certain fixed routing paths, and adequately balances the delay of the routing path. the authors assess the quality of QoS algorithm in terms of the acceptance ratio on anycast QoS requests, and the simulation results on a variety of network topologies and on various parameters show that the algorithm has good performances and can balance network load effectively.

Keywords

QoS / anycast service / network routing / randomized algorithm

References

[1] XiaoXi-peng, LionelNi. Internet QoS: a big picture[J]. IEEE Network Magazine, 1999, 13(2): 8-18

[2] ZhangZhi-liEnd-to-end support for statistical quality-of-service guarantees in multimedia networks [D], 1997, Amherst, University of Massachusetts

[3] Rajagppalan B, Nair R, Sandick H, et al. A framework for QoS-based routing in the Internet[R]. IETF, RFC 2386, 1998.

[4] NewtonHNewron’s telecom dictionary 12th edition[M], 1997, Changsha, Flatiron Press

[5] BasturkE, EngelR, HaasR, et al.Using network layer anycast for load distribution in the internet[R], 1997, Changsha, IBM Research

[6] Partridge C, Mendez T, Milliken W. Host anycasting service [R]. IETF, RFC 1546, 1993.

[7] Hinden R, Deering S. IP version 6 addressing architecture [R]. IETF, RFC 1884, 1995.

[8] Bhattacharjee S, Ammar H M, Zegura W E, et al. Application-layer anycasting[A]. The 16th Annual Joint Conference of the IEEE Computer and Communications Societies[C]. Kobe, Japan, 1997.

[9] Noble C. Optimal video distribution using anycasting service [A]. The 9th Annual Conference of the Internet Society[C]. San Jose, Canada, 1999.

[10] XuanDong, JiaWei-jia, ZhaoWei. A routing protocol for anycast messages[J]. IEEE Trans Parallel and Distributed Systems, 2000, 11(6): 571-588

[11] LorenzH D, OrdaA. QoS routing in networks with uncertain parameters[J]. IEEE/ACM Trans Networking, 1998, 6(6): 768-778

[12] SunQuan, LangendorferH. Routing for low call blocking in high-speed general topology networks[J]. Computer Networks and ISDN Systems, 1998, 30(7): 795-804

[13] RampalS, ReevesS D. An evaluation of routing and admission control algorithms for multimedia traffic[J]. Computer Communication, 1995, 18(10): 755-768

[14] WANG Jian-xin, WANG Wei-ping, CHEN Jian-er, et al. A randomized QoS routing algorithm on networks with inaccurate link-state information[A]. The 16th World Computer Conference[C]. Beijing, 2000.