一种实时网络多QoS自适应路由算法
|
摘要
随着因特网实时性应用的高速增长，IP网络的QoS(Quality of Service，服务质量)路由问题已成为当今网络通信领域的一个研究热点。作为QoS路由算法之一，基于蚁群算法的自适应路由选择算法一经提出，因算法简单且易于实现而得到了很多学者的关注，并取得了较多的研究成果。本文从流量工程的角度出发，对现有的自适应路由算法进行了深入的探讨，并提出了一种基于时延信息的多QoS路由算法以满足多QoS约束条件，同时更大效率地利用网络资源。
具体研究内容包括如下几个方面：
1．通过阅读大量的中英文文献，对路由协议、自适应路由、多QoS路由等基本概念和原理作了比较系统而完整的阐述；同时分析了当前国内外对多QoS路由算法的研究现状以及未来发展趋势。
2．针对蚁群算法存在的局限性，提出了一种基于时延的自适应路由算法。算法能够凭借路径时延信息并结合网络中各路径的利用率情况自适应的调整发送路径，并以概率的形式选择路径，一方面尽可能地使端到端数据传送过程时延最小化，另一方面使网络流量分布均匀，以减少网络拥塞发生的概率。
3．在上述研究的基础上，提出了一种基于时延的自适应多QoS路由算法。该算法直接利用前一周期的时延信息来更新路由表，以作为当前寻找路径的依据，在满足带宽和时延波动约束条件下，使数据传送过程时延最小化。结果提高了网络资源的利用率，同时避免了网络中拥塞发生的可能性。
4．结合网络实验室建设，对实现网络互联和数据传送可以采用的一些常用路由配置方法进行了简单的描述，同时提供了一些相关的命令和示例。
With the development of the real-time applications in Internet, the QoS (Quality of Service) routing algorithms in IP network have become an important issue. As one of the QoS routing algorithms, ant colony algorithm has gained increasing attention recently for its excellent properties and easy implementation. This thesis reviewed the existing adaptive routing algorithms and proposed a multiple QoS constrained routing algorithm based on delay information in order to avoid network congestion and to utilize network resources effectively.
The main contents of this thesis are as follows:
1. This thesis reviews the principles, development and the present state of routing protocol, adaptive routing and multiple QoS routing algorithms, and briefly discusses the future trend in QoS routing algorithms.
2. After analyzing a common used ant colony routing algorithm, this thesis proposed a new fast adaptive routing algorithm to overcome the drawbacks of the ant-based algorithm. The new algorithm uses network delay information directly to choose path by probability. Its application will minimize the delay for an end-to-end data transmission and optimize the distribution of network resources to avoid network congestion.
3. The multiple QoS adaptive routing algorithm has been proposed. It can refresh the router table by the previous delay information to find a suitable path with the constraints of the bandwidth and the delay-jitter. Simulation results show that the algorithm improves the utilization of the network resource and avoids the network congestion obviously.
4. To construct our experimental network, this thesis discusses the techniques to build a network and gives a practical example.
具体研究内容包括如下几个方面：
1．通过阅读大量的中英文文献，对路由协议、自适应路由、多QoS路由等基本概念和原理作了比较系统而完整的阐述；同时分析了当前国内外对多QoS路由算法的研究现状以及未来发展趋势。
2．针对蚁群算法存在的局限性，提出了一种基于时延的自适应路由算法。算法能够凭借路径时延信息并结合网络中各路径的利用率情况自适应的调整发送路径，并以概率的形式选择路径，一方面尽可能地使端到端数据传送过程时延最小化，另一方面使网络流量分布均匀，以减少网络拥塞发生的概率。
3．在上述研究的基础上，提出了一种基于时延的自适应多QoS路由算法。该算法直接利用前一周期的时延信息来更新路由表，以作为当前寻找路径的依据，在满足带宽和时延波动约束条件下，使数据传送过程时延最小化。结果提高了网络资源的利用率，同时避免了网络中拥塞发生的可能性。
4．结合网络实验室建设，对实现网络互联和数据传送可以采用的一些常用路由配置方法进行了简单的描述，同时提供了一些相关的命令和示例。
With the development of the real-time applications in Internet, the QoS (Quality of Service) routing algorithms in IP network have become an important issue. As one of the QoS routing algorithms, ant colony algorithm has gained increasing attention recently for its excellent properties and easy implementation. This thesis reviewed the existing adaptive routing algorithms and proposed a multiple QoS constrained routing algorithm based on delay information in order to avoid network congestion and to utilize network resources effectively.
The main contents of this thesis are as follows:
1. This thesis reviews the principles, development and the present state of routing protocol, adaptive routing and multiple QoS routing algorithms, and briefly discusses the future trend in QoS routing algorithms.
2. After analyzing a common used ant colony routing algorithm, this thesis proposed a new fast adaptive routing algorithm to overcome the drawbacks of the ant-based algorithm. The new algorithm uses network delay information directly to choose path by probability. Its application will minimize the delay for an end-to-end data transmission and optimize the distribution of network resources to avoid network congestion.
3. The multiple QoS adaptive routing algorithm has been proposed. It can refresh the router table by the previous delay information to find a suitable path with the constraints of the bandwidth and the delay-jitter. Simulation results show that the algorithm improves the utilization of the network resource and avoids the network congestion obviously.
4. To construct our experimental network, this thesis discusses the techniques to build a network and gives a practical example.
引文
Andersson, L., P. Doolan, N. Feldman, et al. (2001). Label distribution protocol specification, RFC3036
Apostolopoulos, G., R. Guerin, S. Kamat (1999). Implementation and performance measurements of QoS routing extensions to OSPF. Proceedings of the IEEE INFOCOM'99, New York, NY, 2:680-688
Barolli, L., A. Koyama, T. Yamada, and S.Yokoyama (2001). An integrated CAC and routing strategy for high-speed large-scale networks using cooperative agents. Trans. of Information Processing Society of Japan, 42(2): 222-233
Bernet, Y., P. Ford, R. Yavatkar, et al. (2000). A framework for integrated services operation over diffserv networks. RFC2998.
Blake, S., D. Black, M. Carlson, et al. (1998). An architecture for differentiated services. RFC2475
Caro, G. Di and M. Dorigo (1998). AntNet: distributed stigmergetic control for communications networks. Artificial Intelligence Research, 9:317-365
Chen, S., K. Nahrstedt (1998). Distributed quality-of-service routing in high-speed networks based on selective probing. Proceedings of the 23rd Annual Conference on Local Computer Networks. Boston, MA, 80-89
Chen, S., K. Nahrstedt (1998). Distributed QoS routing with imprecise state information. Proceedings of the 7th International Conference on Computer Communications and Networks, 614-621
Chen, S., K. Nahrstedt (1998). On finding multi-constrained paths. Proceedings of the IEEE International Conference on Communications, Atlanta, 874-879
Cidon, I., R. Rom, Y. Shavitt (1997). Multi-path routing combined with resource reservation. Proceedings of the IEEE INFOCOM'97, Kobe, 92-100
Colorni, S., M. Dorigo, V. Maniezzo (1991). Distributed optimization by ant colonies. Proceedings of the European Conference on Artificial Life, Paris,
134-142
Dijkstra, E.W (1959). A note on two problems in connection with graphs. Numeric Mathematics, 1 : 269-271
Dorigo, M., L. M. Gambardella (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans on Evolutionary, 1(1):53-66
Dorigo, M. and G. Di Caro (1999). Ant colony optimization: a new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation, Washington D.C., 2:1470-1477
Ergun, F., R. Sinha, L. Zhang (2000). QoS routing with performance-dependent costs. Proceedings of the IEEE INFOCOM 2000, Tel Aviv, Israel, 1:137-146
Fernando, K., V. M. Piet, K. Turgay, et al. (2002). An overview of constraint-based path selection algorithms for QoS routing. IEEE Communications Magazine, 40(12): 50-55
Hassin, R.(1992). Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research, 17 (1): 36-42
Hou, J. and B.Wang (2000). Multicast routing and its QoS extension: problems, algorithms and protocols. IEEE Networks, 14(1): 22-36
Hui, Chi-Chung (1999). Improved strategies for dynamic load balancing. IEEE Concurrency, 7:58-67
Hunt, R. (2002). A review of quality of service mechanisms in IP-based networks-integrated and differentiated services, multi-layers switching, MPLS and traffic engineering. Computer Communications, 25:100-108
Ishida., K., K. Amano, N. Kannari (1998). A delay-constrained least-cost path routing protocol and the synthesis method. Proceedings of the Fifth International Conference on Real-time Computing Systems and Applications, New York, 10:58-65
Jaffe, J. M. (1984). Algorithms for finding paths with multiple constraints. Networks, 14:95-116
Juttner, A., B. Szviatovski, I. Mecs, et al. (2001). Lagrange relaxation based method
for the QoS routing problem. Proceedings of the IEEE INFOCOM 2001, 2:782-791
Korkmaz, T., M. Krunz (2001). A randomized algorithm for finding a path subject to multiple QoS requirements. Computer Networks, 36:251-268
Korkmaz, T., M. Krunz (2001). Multi-constrained optimal path selection. Proceedings of the IEEE INFOCOM 2001, Piscataway, NJ, 2:834-843
Li, C., X. Sean Wang (1996). A data model for supporting on-line analytical processing. Proceedings of the Fifth International Conference on Information and Knowledge Management, Maryland, 81-88
Lipperts, S., B. Kreller (1999). Mobile agents in telecommunications networks - a simulative approach to load balancing. Proceedings of the 5th Intl. Conf. Information Systems, Analysis and Synthesis, ISAS'99, Orlando, 3:58-65
Lorenz, D.H., A. Orda, D. Raz, et al. (2000). Efficient QoS partition and routing of unicast and multicast. Proceedings IEEE/IETF IWQoS, Pittsburgh, 6:75-83
Ma, Q., P. Steenkiste (1999). Supporting dynamic inter-class resource sharing: a multi-class QoS routing algorithm. Proceedings of the IEEE INFOCOM'99, New York, 2:649-660
Ni, L.M., P. K. McKinley (1993). A survey of wormhole routing techniques in direct networks. IEEE Computer, 26(2): 62-76
Oida, K., M. Sekido (1999). An agent-based routing system for QoS guarantees. Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, 833- 838
Orda, A. (1999). Routing with end-to-end QoS guarantees in broadband networks. IEEE/ACM Transactions on Networking, 7(3): 365-374
Orda, A., A. Sprintson (2000). QoS routing: the precomputation perspective. Proceedings of the IEEE INFOCOM 2000, Israel, 1:128-136
Phillips, C.A. (1993). The network inhibition problem. Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, California, 3:776-785
Raz, D., Y. Shavitt, D. Raz, et al. (2000). Optimal partition of QoS requirements with discrete cost functions. Proceedings of the IEEE INFOCOM 2000, Tel
Aviv, Israel, 613-622
Salama, H.F., D.S. Reeves, Y. Viniotis (1997). A distributed algorithm for delay-constrained unicast routing. Proceedings of the INFOCOM'97 Conference, New York, 1:84-91
Salama, H.F., D.S. Reeves, Y. Viniotis (2000). A distributed algorithm for delay-constrained unicast routing. IEEE/ACM Transactions on Networking, Japan, 8(2): 239-250
Schoonderwoerd, R., O. Holland, J. Bruten, et al. (1996). Ant based load balancing in telecommunication networks. Adaptive Behavior, 5:169-207
Shin, K.G., C. Chou (1997). Statistical real-time channels on multi-access bus networks. IEEE Trans. on Parallel and Distributed Systems, 8(8):769-780
Stallings, W. (1998). High-speed networks: TCP /IP and ATM design principles. Prentice Hall, New York, January, 1998
WANG, Jianxin, CHEN Jian'er (2002). An effective randomized QoS routing algorithm on networks with inaccurate parameters. Computer Science and Technology, 17(1): 38-46
Wang, Z., J. Crowcroft (1996). QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications, 14(7): 1228-1234
Widyono, R. (1994). The design and evaluation of routing algorithms for real-time channels. Technical Report TR-94-024, University of California at Berkeley & International Computer Science Institute. Feb. 1994
William, R. (2002). Cisco OSPF Command and Configuration Handbook. Cisco Press. Indianapolis, April, 2002
Yuan, X. (2002). Heuristic algorithms for multi-constrained quality of service routing. IEEE/ACM Transactions on Networking, 10(2): 244-256.
陈萍，董天临(2003)．基于非精确信息的QoS组播路由遗传算法．应用科学学报，21(1)：30-35．
崔勇，吴建平，徐恪等(2002)．互联网络服务质量路由算法研究综述．软件学报，13(11)：2065-2075．
董小社，伍卫国，戴智伟等(2002)．基于WDM技术的虚拟多环互连网络的自适应路由算法．计算机学报，25(7)：778-783
顾军华，侯向丹，宋洁等(2002)．基于蚂蚁算法的QoS组播路由问题求解．河北工业大学学报，23(4)：19-24．
侯越先，何丕廉，孙学军(2002)．自适应随机化链路状态路由算法．计算机研究与发展，39(11)：1498-1504．
吕国英，刘泽民，周正(2001)．基于蚂蚁算法的分布式QoS路由选择算法．通信学报，22(9)：34-42．
糜正琨，徐名海(2003)．IP网络QoS模型及实现技术．中兴通讯高级论坛，Vol.50，2003-10．
汤庸，杨学良，区海翔等(2001)．基于IP网络的自适应QoS管理方案研究．计算机学报，24(1)：32-39
王保顺(2003)．校园网设计与远程教学系统开发．北京，人民邮电出版社，2003年1月。
王建新，陈松乔，陈建二等(2001)．基于QoS的随机源选路由算法研究．小型微型计算机系统，22(8)：917-920．
王伟平，王建新，陈建二等(2002)．结合网络资源开销估算的QoS改进路由算法．小型微型计算机系统，23(5)：521-523．
王颖，谢剑英(2001)．一种基于改进蚁群算法的多点路由算法．系统工程与电子技术，23(8)：98-101．
熊桂喜，王小虎译(1998)．计算机网络(第三版)，北京，清华大学出版社，1998年7月．
袁刚，甘家宝，王文东等(2003)．MPLS网络的QoS及其管理框架实现方式．重庆邮电学院学报，15(3)：57-83．
张素兵，刘泽民(2001)．基于蚂蚁算法的时延受限分布式多播路由研究．通信学报，22(3)：70-74．
Cisco路由器配置手册．中国轻工业出版社，北京，2000年1月。
Apostolopoulos, G., R. Guerin, S. Kamat (1999). Implementation and performance measurements of QoS routing extensions to OSPF. Proceedings of the IEEE INFOCOM'99, New York, NY, 2:680-688
Barolli, L., A. Koyama, T. Yamada, and S.Yokoyama (2001). An integrated CAC and routing strategy for high-speed large-scale networks using cooperative agents. Trans. of Information Processing Society of Japan, 42(2): 222-233
Bernet, Y., P. Ford, R. Yavatkar, et al. (2000). A framework for integrated services operation over diffserv networks. RFC2998.
Blake, S., D. Black, M. Carlson, et al. (1998). An architecture for differentiated services. RFC2475
Caro, G. Di and M. Dorigo (1998). AntNet: distributed stigmergetic control for communications networks. Artificial Intelligence Research, 9:317-365
Chen, S., K. Nahrstedt (1998). Distributed quality-of-service routing in high-speed networks based on selective probing. Proceedings of the 23rd Annual Conference on Local Computer Networks. Boston, MA, 80-89
Chen, S., K. Nahrstedt (1998). Distributed QoS routing with imprecise state information. Proceedings of the 7th International Conference on Computer Communications and Networks, 614-621
Chen, S., K. Nahrstedt (1998). On finding multi-constrained paths. Proceedings of the IEEE International Conference on Communications, Atlanta, 874-879
Cidon, I., R. Rom, Y. Shavitt (1997). Multi-path routing combined with resource reservation. Proceedings of the IEEE INFOCOM'97, Kobe, 92-100
Colorni, S., M. Dorigo, V. Maniezzo (1991). Distributed optimization by ant colonies. Proceedings of the European Conference on Artificial Life, Paris,
134-142
Dijkstra, E.W (1959). A note on two problems in connection with graphs. Numeric Mathematics, 1 : 269-271
Dorigo, M., L. M. Gambardella (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans on Evolutionary, 1(1):53-66
Dorigo, M. and G. Di Caro (1999). Ant colony optimization: a new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation, Washington D.C., 2:1470-1477
Ergun, F., R. Sinha, L. Zhang (2000). QoS routing with performance-dependent costs. Proceedings of the IEEE INFOCOM 2000, Tel Aviv, Israel, 1:137-146
Fernando, K., V. M. Piet, K. Turgay, et al. (2002). An overview of constraint-based path selection algorithms for QoS routing. IEEE Communications Magazine, 40(12): 50-55
Hassin, R.(1992). Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research, 17 (1): 36-42
Hou, J. and B.Wang (2000). Multicast routing and its QoS extension: problems, algorithms and protocols. IEEE Networks, 14(1): 22-36
Hui, Chi-Chung (1999). Improved strategies for dynamic load balancing. IEEE Concurrency, 7:58-67
Hunt, R. (2002). A review of quality of service mechanisms in IP-based networks-integrated and differentiated services, multi-layers switching, MPLS and traffic engineering. Computer Communications, 25:100-108
Ishida., K., K. Amano, N. Kannari (1998). A delay-constrained least-cost path routing protocol and the synthesis method. Proceedings of the Fifth International Conference on Real-time Computing Systems and Applications, New York, 10:58-65
Jaffe, J. M. (1984). Algorithms for finding paths with multiple constraints. Networks, 14:95-116
Juttner, A., B. Szviatovski, I. Mecs, et al. (2001). Lagrange relaxation based method
for the QoS routing problem. Proceedings of the IEEE INFOCOM 2001, 2:782-791
Korkmaz, T., M. Krunz (2001). A randomized algorithm for finding a path subject to multiple QoS requirements. Computer Networks, 36:251-268
Korkmaz, T., M. Krunz (2001). Multi-constrained optimal path selection. Proceedings of the IEEE INFOCOM 2001, Piscataway, NJ, 2:834-843
Li, C., X. Sean Wang (1996). A data model for supporting on-line analytical processing. Proceedings of the Fifth International Conference on Information and Knowledge Management, Maryland, 81-88
Lipperts, S., B. Kreller (1999). Mobile agents in telecommunications networks - a simulative approach to load balancing. Proceedings of the 5th Intl. Conf. Information Systems, Analysis and Synthesis, ISAS'99, Orlando, 3:58-65
Lorenz, D.H., A. Orda, D. Raz, et al. (2000). Efficient QoS partition and routing of unicast and multicast. Proceedings IEEE/IETF IWQoS, Pittsburgh, 6:75-83
Ma, Q., P. Steenkiste (1999). Supporting dynamic inter-class resource sharing: a multi-class QoS routing algorithm. Proceedings of the IEEE INFOCOM'99, New York, 2:649-660
Ni, L.M., P. K. McKinley (1993). A survey of wormhole routing techniques in direct networks. IEEE Computer, 26(2): 62-76
Oida, K., M. Sekido (1999). An agent-based routing system for QoS guarantees. Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics, 833- 838
Orda, A. (1999). Routing with end-to-end QoS guarantees in broadband networks. IEEE/ACM Transactions on Networking, 7(3): 365-374
Orda, A., A. Sprintson (2000). QoS routing: the precomputation perspective. Proceedings of the IEEE INFOCOM 2000, Israel, 1:128-136
Phillips, C.A. (1993). The network inhibition problem. Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, California, 3:776-785
Raz, D., Y. Shavitt, D. Raz, et al. (2000). Optimal partition of QoS requirements with discrete cost functions. Proceedings of the IEEE INFOCOM 2000, Tel
Aviv, Israel, 613-622
Salama, H.F., D.S. Reeves, Y. Viniotis (1997). A distributed algorithm for delay-constrained unicast routing. Proceedings of the INFOCOM'97 Conference, New York, 1:84-91
Salama, H.F., D.S. Reeves, Y. Viniotis (2000). A distributed algorithm for delay-constrained unicast routing. IEEE/ACM Transactions on Networking, Japan, 8(2): 239-250
Schoonderwoerd, R., O. Holland, J. Bruten, et al. (1996). Ant based load balancing in telecommunication networks. Adaptive Behavior, 5:169-207
Shin, K.G., C. Chou (1997). Statistical real-time channels on multi-access bus networks. IEEE Trans. on Parallel and Distributed Systems, 8(8):769-780
Stallings, W. (1998). High-speed networks: TCP /IP and ATM design principles. Prentice Hall, New York, January, 1998
WANG, Jianxin, CHEN Jian'er (2002). An effective randomized QoS routing algorithm on networks with inaccurate parameters. Computer Science and Technology, 17(1): 38-46
Wang, Z., J. Crowcroft (1996). QoS routing for supporting resource reservation. IEEE Journal on Selected Areas in Communications, 14(7): 1228-1234
Widyono, R. (1994). The design and evaluation of routing algorithms for real-time channels. Technical Report TR-94-024, University of California at Berkeley & International Computer Science Institute. Feb. 1994
William, R. (2002). Cisco OSPF Command and Configuration Handbook. Cisco Press. Indianapolis, April, 2002
Yuan, X. (2002). Heuristic algorithms for multi-constrained quality of service routing. IEEE/ACM Transactions on Networking, 10(2): 244-256.
陈萍，董天临(2003)．基于非精确信息的QoS组播路由遗传算法．应用科学学报，21(1)：30-35．
崔勇，吴建平，徐恪等(2002)．互联网络服务质量路由算法研究综述．软件学报，13(11)：2065-2075．
董小社，伍卫国，戴智伟等(2002)．基于WDM技术的虚拟多环互连网络的自适应路由算法．计算机学报，25(7)：778-783
顾军华，侯向丹，宋洁等(2002)．基于蚂蚁算法的QoS组播路由问题求解．河北工业大学学报，23(4)：19-24．
侯越先，何丕廉，孙学军(2002)．自适应随机化链路状态路由算法．计算机研究与发展，39(11)：1498-1504．
吕国英，刘泽民，周正(2001)．基于蚂蚁算法的分布式QoS路由选择算法．通信学报，22(9)：34-42．
糜正琨，徐名海(2003)．IP网络QoS模型及实现技术．中兴通讯高级论坛，Vol.50，2003-10．
汤庸，杨学良，区海翔等(2001)．基于IP网络的自适应QoS管理方案研究．计算机学报，24(1)：32-39
王保顺(2003)．校园网设计与远程教学系统开发．北京，人民邮电出版社，2003年1月。
王建新，陈松乔，陈建二等(2001)．基于QoS的随机源选路由算法研究．小型微型计算机系统，22(8)：917-920．
王伟平，王建新，陈建二等(2002)．结合网络资源开销估算的QoS改进路由算法．小型微型计算机系统，23(5)：521-523．
王颖，谢剑英(2001)．一种基于改进蚁群算法的多点路由算法．系统工程与电子技术，23(8)：98-101．
熊桂喜，王小虎译(1998)．计算机网络(第三版)，北京，清华大学出版社，1998年7月．
袁刚，甘家宝，王文东等(2003)．MPLS网络的QoS及其管理框架实现方式．重庆邮电学院学报，15(3)：57-83．
张素兵，刘泽民(2001)．基于蚂蚁算法的时延受限分布式多播路由研究．通信学报，22(3)：70-74．
Cisco路由器配置手册．中国轻工业出版社，北京，2000年1月。