数字有机体流量调度系统负载均衡及容错机制的设计与实现
摘要
当今世界已经步入网络时代。网络深入人们的工作、生活、娱乐等方方面面。网络用户的增加使得网络地址(IPV4)匮乏。人们对网络质量要求的不断提高，给现有网络设备带来巨大挑战。能否让网络设备适应逐渐发展的用户需要，能否提高一个高速、稳定、安全的网络等等一系列问题成为网络发展的关键。
面对上述需求，我们基于Linux平台开发了集网络路由与分布式并行系统于一体的数字有机体流量调度系统。其通过网络地址转换(NAT)解决网络地址不足的问题，同时具备了一道天然的防火墙。通过多出口和多节点并行工作，有效的提高了系统的负载能力，增强了该设备的灵活性和适应性。同时节点间及出口间相互冗余备份，极大的提高了设备的稳定性和可用性。
本文就数字有机体流量调度系统负载均衡及容错两个关键问题进行了深入的讨论，并给出了我们的具体实现，最后给出了几个关键测试的测试过程及测试结果。本文主要贡献以及内容包括：
1．对网络负载均衡和负载调度进行了深入的分析，并对已有负载均衡算法和负载调度模型进行了总结分析。
2．提出了一种新的适合数字有机体流量调度系统及类似系统使用的负载均衡算法。该算法基于负反馈机制，具有开销小、效率高、自适应性和自容错性四个特点。
3．对常用的分布式节点检测机制进行了介绍，在此基础上提出了一种将心跳检测算法和检查点检测算法相结合的节点检测算法。该算法具有良好的适应性和较高的检测准确性。
4．对数字有机体流量调度系统的关键技术及其实现进行了测试，给出测试结果并对结果进行了详细的分析。对前面提出负载均衡策略，负载均衡算法及容错机制进行了验证。
Internet plays a much more important role in people's life than before. The number of Internet user increases sharply, which leads to the lake of IP address (IPV4). People pay much attention to the quality of network. This gives the network devices a big challenge. The key points are how to improve capacity and make network fast, stabile and safe.
Facing with these challenges, we implemented Digital Organism Load Scheduling System (DOLSS), which combined the advantage of distributed and parallel system to network routing. Through network address translation (NAT) mechanism, our system can solves the problem of IP address shortage and provide safe clean networks. Through distributed and parallel technique, the capacity, flexibility and adaptability of our system is enhanced. The stability and availability of network can be guaranteed.
This paper focuses on the load balancing and fault tolerance mechanisms of DOLSS. The main contributions and contents are as following:
1. Have a deeply analyzing of network load scheduling and load balancing. Give a summary of several load balancing algorithms and load scheduling models.
2. Give a new load balancing algorithm, which can be used on not only DOLSS, but also other system. The algorithm is based on a feedback mechanism and has four characters: low cost, high efficiency, well adaptability and self fault tolerance.
3. Give a new node checking algorithm combining the advantage of heart beat checking algorithms and check point checking algorithms. The checking accurate rate and stability of the algorithm are improved.
4. Make tests on the main features of digital organism load scheduling system. List out the test processes and test results. Also analyze the test results. Validate the theories about network load scheduling and load balancing, through the test.
面对上述需求，我们基于Linux平台开发了集网络路由与分布式并行系统于一体的数字有机体流量调度系统。其通过网络地址转换(NAT)解决网络地址不足的问题，同时具备了一道天然的防火墙。通过多出口和多节点并行工作，有效的提高了系统的负载能力，增强了该设备的灵活性和适应性。同时节点间及出口间相互冗余备份，极大的提高了设备的稳定性和可用性。
本文就数字有机体流量调度系统负载均衡及容错两个关键问题进行了深入的讨论，并给出了我们的具体实现，最后给出了几个关键测试的测试过程及测试结果。本文主要贡献以及内容包括：
1．对网络负载均衡和负载调度进行了深入的分析，并对已有负载均衡算法和负载调度模型进行了总结分析。
2．提出了一种新的适合数字有机体流量调度系统及类似系统使用的负载均衡算法。该算法基于负反馈机制，具有开销小、效率高、自适应性和自容错性四个特点。
3．对常用的分布式节点检测机制进行了介绍，在此基础上提出了一种将心跳检测算法和检查点检测算法相结合的节点检测算法。该算法具有良好的适应性和较高的检测准确性。
4．对数字有机体流量调度系统的关键技术及其实现进行了测试，给出测试结果并对结果进行了详细的分析。对前面提出负载均衡策略，负载均衡算法及容错机制进行了验证。
Internet plays a much more important role in people's life than before. The number of Internet user increases sharply, which leads to the lake of IP address (IPV4). People pay much attention to the quality of network. This gives the network devices a big challenge. The key points are how to improve capacity and make network fast, stabile and safe.
Facing with these challenges, we implemented Digital Organism Load Scheduling System (DOLSS), which combined the advantage of distributed and parallel system to network routing. Through network address translation (NAT) mechanism, our system can solves the problem of IP address shortage and provide safe clean networks. Through distributed and parallel technique, the capacity, flexibility and adaptability of our system is enhanced. The stability and availability of network can be guaranteed.
This paper focuses on the load balancing and fault tolerance mechanisms of DOLSS. The main contributions and contents are as following:
1. Have a deeply analyzing of network load scheduling and load balancing. Give a summary of several load balancing algorithms and load scheduling models.
2. Give a new load balancing algorithm, which can be used on not only DOLSS, but also other system. The algorithm is based on a feedback mechanism and has four characters: low cost, high efficiency, well adaptability and self fault tolerance.
3. Give a new node checking algorithm combining the advantage of heart beat checking algorithms and check point checking algorithms. The checking accurate rate and stability of the algorithm are improved.
4. Make tests on the main features of digital organism load scheduling system. List out the test processes and test results. Also analyze the test results. Validate the theories about network load scheduling and load balancing, through the test.
引文
[1]．刘心松，王典荫等，数字有机体抗毁结构的研究，西部广播电视，2005年02期
[2]．Andrew S．Tanenbaum 著，陆丽娜 伍卫国 刘隆国 等译校．分布式操作系统．北京：电子工业出版社，1999
[3]．Andrew S．Tanenbaum，Maarten van Steen 著，杨剑锋 常晓波 李敏 译。分布式系统原理与范型．北京：清华大学出版社，2004．9
[4]．Doreen L．Galli著 徐良宪 唐英 毛家菊 金恩华 等译．分布式操作系统原理与实践．北京：机械工业出版社，2003
[5]．Jie Wu．，高传善 等译．分布式系统设计．北京：机械工业出版社，2001
[6]．Rajkumar Buyya编 郑伟民 石威 汪东升等译．高性能集群计算：结构与系统(第一卷)北京：电子工业出版社2001
[7]．林成江，李三立．一种可适应的分布式动态负载平衡策略及其仿真[J]．计算机学报，1995，18(10)．
[8]．何炎祥，刘朝阳，邓爱林．基于工作站的分布式系统中的负载分配和平衡策略[J]．计算机工程，1999，25(11)．
[9]．David R．Butenhof 著，于磊 曾刚译．POSIX多线程程序设计．北京：中国电力出版社，2003
[10]．Douglas E．Comer著，林瑶蒋慧等译，谢希仁审校．用TCP／IP进行网际互连：原理、协议与结构(第一卷)．北京：电子工业出版社，2003
[11]．钱方．分布计算环境中冗余服务管理机制的研究与实现．博士论文，2000．5
[12]．沈海华，陈世敏等．WWW集群服务器的数据副本分布方式研究．软件学报，2000，12
[13]．胡华平，金士尧等．分布式实时系统的高可靠性研究与实现．计算机研究与发展，1998．9，第9期
[14]．李宏亮，胡国平，胡华平等．强实时双系统中容错技术研究．国防科技大学学报．2000，6．
[15]．杨文波王志英等．高性能分布式双工实时容错系统中的若干技术问题．小型计算机系统，2001，2．
[16]．杨文波王志英等．高性能分布式双工实时容错系统中的若干技术问题．小型计算机系统，2001，2．
[17]．徐敏，王行仁等．同构型分布式计算机系统的启发式任务分配算法．计算机学报，1994，17(2)：112—119
[18]．阂应弊．容错计算二十五年．计算机学报，1995．12，第12期
[19]．戈应安．分布式实时系统的容错设计与实现．博士论文，1998．5，2页。
[20]．齐振国．利用冗余技术提高软件容错能力．沈阳师范学院学报(自然科学版)，2002年10月第4期
[21]．林观德．分布式系统中负载共享策略的研究．《广西师范学报》(自然科学版)，1998，15(3)，63-67．
[22]．邓玉华．“分布式系统中网络负载平衡的研究和应用”．西南交通大学，2002年3月
[23]．胡凯，胡建平．机群并行计算中负载的关键问题[J]．计算机科学，2000，27(7)，8-11．
[24]．陈华平，计泰旭．分布式动态负载平衡调度的一个通用模型[J]．软件学报，1998，9(1)，25-29．
[25]．莫则查，李晓梅．工作站网络环境下的并行计算[J]．计算机学报，1997，20(6)，510-517．
[26]．邸烁，郑纬民，王鼎兴．可扩展并行Web Server集群技术．小型微型计算机系统，1999年10期
[27]．陈志刚，李登，曾志文．基于Java RMI技术的中间应用服务器动态负载均衡模型的实现．《计算机工程》，2001，27(7)，45-50．
[28]．陈志刚，李登，曾志文．分布式系统中动态负载均衡实现模型研究．《中南工业大学学报》(自然科学版)，2001．
[29]．林闯．随机Petri网模型的转化设计[J]．软件学报，2000，11(1)，104-109．
[30]．吴思，陈萃萌．RIPS调度策略研究[J]．计算机科学，2001，28(1)，13-15．
[31]. Balasubramanian, J., Schmidt, D. C., Dowdy, L., &Othman, O. (n.d.). Evaluating the Performance of Middleware Load Balancing Strategies
[32]. [Egevang, K., & Francis, P. (1994). RFC 1631-The IP Network Address Translator (NAT) [WWW document]. URL http://rfc.net/rfc1631.html
[33]. Marien, A. (2004). Load Balancing URL http://www.cs.kuleuven.ac.be/~andrem/
[34]. O'Sullivan, L. (n.d.). Load Sharing using IP Address Translation (LSNAT) [www document].URL http://ntrg.cs.tcd.ie/undergrad/4ba2.01/group8/LSNAT.html
[35]. ]Srisuresh, P., & Gan, D. (1998). RFC 2391-Load Sharing using IP Network Address Translation (LSNAT) [www document]. URL http://rfc.net/rfc2391.html
[36]. Adiseshu Hari, Subhash Suri, Guru Parulkar. Detecting and resolving packet filter conflicts. INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , Volume: 3 , 26-30 Mar 2000:1203 -1212
[37]. Singh, K. A configurable 5-D packet classification engine with 4Mpacket/s throughput for high-speed data networking. Sol id-State Circuits Conference, 2000. Digest of Technical Papers. ISSCC. 2000 IEEE International, 2000:82 -83
[38]. LiLi Qiu, Geroge Varghese, Subhash Suri. Fast Firewall Implementations for Software and Hardware-based Routers; 9th International Conference on Network Protocols. Riverside, CA, November 2001.241-250
[39]. Hac, A., " Load balancing in distributed systems: A summary" , Performance Evaluation Review, 16, 2-4, Feb.1989, 17-19
[40]. Ching-chih Han, Kang G. Shin, Jian Wu. A Fault-Tolerant Schedul ing Algorithm for Real-Time Periodic Tasks with Possible Software Faults. Trans. on ComPuters. 2003, 52(3):362-372.
[41]. Heejo Lee, Jong Kim, Sung Je Hong . Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems .IEEE Trans on Parallel and Distributed System. 2003, 14(4):394-407
[42]. B. Ravindram. Engineering Dynamic Real-Time Distributed Systems Architecture, System Description Language , and Middleware.Trans. IEEE Trans on Software Engineering.2002, 28(1):30-57
[2]．Andrew S．Tanenbaum 著，陆丽娜 伍卫国 刘隆国 等译校．分布式操作系统．北京：电子工业出版社，1999
[3]．Andrew S．Tanenbaum，Maarten van Steen 著，杨剑锋 常晓波 李敏 译。分布式系统原理与范型．北京：清华大学出版社，2004．9
[4]．Doreen L．Galli著 徐良宪 唐英 毛家菊 金恩华 等译．分布式操作系统原理与实践．北京：机械工业出版社，2003
[5]．Jie Wu．，高传善 等译．分布式系统设计．北京：机械工业出版社，2001
[6]．Rajkumar Buyya编 郑伟民 石威 汪东升等译．高性能集群计算：结构与系统(第一卷)北京：电子工业出版社2001
[7]．林成江，李三立．一种可适应的分布式动态负载平衡策略及其仿真[J]．计算机学报，1995，18(10)．
[8]．何炎祥，刘朝阳，邓爱林．基于工作站的分布式系统中的负载分配和平衡策略[J]．计算机工程，1999，25(11)．
[9]．David R．Butenhof 著，于磊 曾刚译．POSIX多线程程序设计．北京：中国电力出版社，2003
[10]．Douglas E．Comer著，林瑶蒋慧等译，谢希仁审校．用TCP／IP进行网际互连：原理、协议与结构(第一卷)．北京：电子工业出版社，2003
[11]．钱方．分布计算环境中冗余服务管理机制的研究与实现．博士论文，2000．5
[12]．沈海华，陈世敏等．WWW集群服务器的数据副本分布方式研究．软件学报，2000，12
[13]．胡华平，金士尧等．分布式实时系统的高可靠性研究与实现．计算机研究与发展，1998．9，第9期
[14]．李宏亮，胡国平，胡华平等．强实时双系统中容错技术研究．国防科技大学学报．2000，6．
[15]．杨文波王志英等．高性能分布式双工实时容错系统中的若干技术问题．小型计算机系统，2001，2．
[16]．杨文波王志英等．高性能分布式双工实时容错系统中的若干技术问题．小型计算机系统，2001，2．
[17]．徐敏，王行仁等．同构型分布式计算机系统的启发式任务分配算法．计算机学报，1994，17(2)：112—119
[18]．阂应弊．容错计算二十五年．计算机学报，1995．12，第12期
[19]．戈应安．分布式实时系统的容错设计与实现．博士论文，1998．5，2页。
[20]．齐振国．利用冗余技术提高软件容错能力．沈阳师范学院学报(自然科学版)，2002年10月第4期
[21]．林观德．分布式系统中负载共享策略的研究．《广西师范学报》(自然科学版)，1998，15(3)，63-67．
[22]．邓玉华．“分布式系统中网络负载平衡的研究和应用”．西南交通大学，2002年3月
[23]．胡凯，胡建平．机群并行计算中负载的关键问题[J]．计算机科学，2000，27(7)，8-11．
[24]．陈华平，计泰旭．分布式动态负载平衡调度的一个通用模型[J]．软件学报，1998，9(1)，25-29．
[25]．莫则查，李晓梅．工作站网络环境下的并行计算[J]．计算机学报，1997，20(6)，510-517．
[26]．邸烁，郑纬民，王鼎兴．可扩展并行Web Server集群技术．小型微型计算机系统，1999年10期
[27]．陈志刚，李登，曾志文．基于Java RMI技术的中间应用服务器动态负载均衡模型的实现．《计算机工程》，2001，27(7)，45-50．
[28]．陈志刚，李登，曾志文．分布式系统中动态负载均衡实现模型研究．《中南工业大学学报》(自然科学版)，2001．
[29]．林闯．随机Petri网模型的转化设计[J]．软件学报，2000，11(1)，104-109．
[30]．吴思，陈萃萌．RIPS调度策略研究[J]．计算机科学，2001，28(1)，13-15．
[31]. Balasubramanian, J., Schmidt, D. C., Dowdy, L., &Othman, O. (n.d.). Evaluating the Performance of Middleware Load Balancing Strategies
[32]. [Egevang, K., & Francis, P. (1994). RFC 1631-The IP Network Address Translator (NAT) [WWW document]. URL http://rfc.net/rfc1631.html
[33]. Marien, A. (2004). Load Balancing URL http://www.cs.kuleuven.ac.be/~andrem/
[34]. O'Sullivan, L. (n.d.). Load Sharing using IP Address Translation (LSNAT) [www document].URL http://ntrg.cs.tcd.ie/undergrad/4ba2.01/group8/LSNAT.html
[35]. ]Srisuresh, P., & Gan, D. (1998). RFC 2391-Load Sharing using IP Network Address Translation (LSNAT) [www document]. URL http://rfc.net/rfc2391.html
[36]. Adiseshu Hari, Subhash Suri, Guru Parulkar. Detecting and resolving packet filter conflicts. INFOCOM 2000. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings. IEEE , Volume: 3 , 26-30 Mar 2000:1203 -1212
[37]. Singh, K. A configurable 5-D packet classification engine with 4Mpacket/s throughput for high-speed data networking. Sol id-State Circuits Conference, 2000. Digest of Technical Papers. ISSCC. 2000 IEEE International, 2000:82 -83
[38]. LiLi Qiu, Geroge Varghese, Subhash Suri. Fast Firewall Implementations for Software and Hardware-based Routers; 9th International Conference on Network Protocols. Riverside, CA, November 2001.241-250
[39]. Hac, A., " Load balancing in distributed systems: A summary" , Performance Evaluation Review, 16, 2-4, Feb.1989, 17-19
[40]. Ching-chih Han, Kang G. Shin, Jian Wu. A Fault-Tolerant Schedul ing Algorithm for Real-Time Periodic Tasks with Possible Software Faults. Trans. on ComPuters. 2003, 52(3):362-372.
[41]. Heejo Lee, Jong Kim, Sung Je Hong . Processor Allocation and Task Scheduling of Matrix Chain Products on Parallel Systems .IEEE Trans on Parallel and Distributed System. 2003, 14(4):394-407
[42]. B. Ravindram. Engineering Dynamic Real-Time Distributed Systems Architecture, System Description Language , and Middleware.Trans. IEEE Trans on Software Engineering.2002, 28(1):30-57