模块化分布式路由器数据平面研究与实现
|
摘要
随着网络规模和复杂性不断增加,互联网体系结构正面临着重大理论挑战。路由器的处理能力逐渐难适应用户网络之间流量不断增大的要求,需要对路由器不断的进行升级才能满足这种日趋增大的流量。但是对于路由器而言,一般路由器的瓶颈在于转发引擎的处理速率而不在于端口速率。也就是说路由器的板卡接口速率往往大于路由器的转发引擎的处理能力,很有可能由于路由器的转发能力不够而引起路由器的端口拥塞。此时,可以利用现有的多台路由器组成一个分布式路由器系统,让多台路由器共享转发引擎资源,从而充分利用现有的设备资源。
本文依次从软件平台、负载模型、负载均衡等方面展开研究。针对分布式路由系统之间的流量均衡问题,用排队论的理论分析了适合分布式路由器的负载均衡算法,提出一种基于各个子卡路由器空闲负载能力的动态负载均衡算法,使得各子卡路由器之间能够尽可能的分享自身的转发能力,使得参与分布式路由器系统的各个路由器能发挥最大的利用率。
为了满足快速增长的网络需求,本文提出了一种分布式软件路由器的结构,该结构可以为异构平台上路由器管理和应用程序提供统一的抽象环境,将不同的路由器组合为有机的整体。本文从转发平台和应用程序接口两个方面对系统平台进行了详细的论述,并提出了设计和实现的方案。同时,在linux环境下搭建运行了基于Click的模块化分布式软件路由器原型系统,并获得了较好的转发性能。
针对同一个子卡路由器转发到其它子卡路由器中的数据流量能够尽可能的延时一致,实现各个流量之间的延时公平性,论文采用了DRR调度算法与VOQ调度算法结合使用的方式。通过引入计次传递机制,避免分布式路由器系统中可能出现长期得不到服务的数据包占用过多的系统资源现象。
As the network scale and complexity enlarging rapidly, Internet architecture is facing a grand academic challenge. The forwarding ability of the original routers cannot suffer the requirement of the user network, so it requires upgrading of the routers to satisfy these changes. The bottleneck of the router is not depended on the speed of the port, but depended on by the speed of the forwarding engine. It means that the forwarding ability of the influence the block of the routers. As this condition, the original routers can be grouped up to be a distributed router system, and share the forwarding abilities among different routers.
This thesis discusses some problems of distributed router, such as software platform, Traffic model, load balance, and address lookup. Queuing theory is used to analyze the traffic model and proper load balancing algorithm of router cluster. To solve the load balance of the distributed router system, the thesis proposes a dynamic load balance algorithm based on the forwarding ability of each card router. The dynamic load balance algorithm can help the card routers to share the forwarding ablates with the other card routers, and make sure the load balance among the card routers.
To satisfy this requirement, the thesis presents a distributed router system. The fabric can provide an abstract environment for the management and protocol applications. The thesis discusses the two layers of the system:forwarding platform and the APIs. We apply the distributed router system under LINUX environment, and get good performance result of the forwarding ability.
To ensure the forwarding flow from one card router to other routers can have the same latency, the thesis use DRR algorithm working with the VOQ algorithm to ensure the fair latency between the different data flows. And a counted transferring mechanism is used to avoid some packets that consume too much system resources.
本文依次从软件平台、负载模型、负载均衡等方面展开研究。针对分布式路由系统之间的流量均衡问题,用排队论的理论分析了适合分布式路由器的负载均衡算法,提出一种基于各个子卡路由器空闲负载能力的动态负载均衡算法,使得各子卡路由器之间能够尽可能的分享自身的转发能力,使得参与分布式路由器系统的各个路由器能发挥最大的利用率。
为了满足快速增长的网络需求,本文提出了一种分布式软件路由器的结构,该结构可以为异构平台上路由器管理和应用程序提供统一的抽象环境,将不同的路由器组合为有机的整体。本文从转发平台和应用程序接口两个方面对系统平台进行了详细的论述,并提出了设计和实现的方案。同时,在linux环境下搭建运行了基于Click的模块化分布式软件路由器原型系统,并获得了较好的转发性能。
针对同一个子卡路由器转发到其它子卡路由器中的数据流量能够尽可能的延时一致,实现各个流量之间的延时公平性,论文采用了DRR调度算法与VOQ调度算法结合使用的方式。通过引入计次传递机制,避免分布式路由器系统中可能出现长期得不到服务的数据包占用过多的系统资源现象。
As the network scale and complexity enlarging rapidly, Internet architecture is facing a grand academic challenge. The forwarding ability of the original routers cannot suffer the requirement of the user network, so it requires upgrading of the routers to satisfy these changes. The bottleneck of the router is not depended on the speed of the port, but depended on by the speed of the forwarding engine. It means that the forwarding ability of the influence the block of the routers. As this condition, the original routers can be grouped up to be a distributed router system, and share the forwarding abilities among different routers.
This thesis discusses some problems of distributed router, such as software platform, Traffic model, load balance, and address lookup. Queuing theory is used to analyze the traffic model and proper load balancing algorithm of router cluster. To solve the load balance of the distributed router system, the thesis proposes a dynamic load balance algorithm based on the forwarding ability of each card router. The dynamic load balance algorithm can help the card routers to share the forwarding ablates with the other card routers, and make sure the load balance among the card routers.
To satisfy this requirement, the thesis presents a distributed router system. The fabric can provide an abstract environment for the management and protocol applications. The thesis discusses the two layers of the system:forwarding platform and the APIs. We apply the distributed router system under LINUX environment, and get good performance result of the forwarding ability.
To ensure the forwarding flow from one card router to other routers can have the same latency, the thesis use DRR algorithm working with the VOQ algorithm to ensure the fair latency between the different data flows. And a counted transferring mechanism is used to avoid some packets that consume too much system resources.
引文
[1]F. Baker. "Requirements for IP Version 4 Routers,"RFC1812, June 1995.
[2]李胜磊.高性能路由器体系结构及其关键技术研究博士论文西安交通大学。2002
[3]Asia- Pacific Advanced Network. http://www.apan.net
[4]林闯,任丰原.可控可信可扩展的新一代互联网.软件学报,2004,15(12)：1815-1821
[5]Blake P. Resource. Telephony, February 2001. Available at http://telephonyonline.com/ar/telecom resource/index.htm
[6]Name Router 4.1 Software Product Description. http://www.eurokom.ie/wade/name-router.html
[7]Eddie Kohler. The Click Modular Router. http://www.pdos.lcs.mit.edu/papers/click:kohler-phd/thesis.pdf.
[8]Benjie Chen, and Robert Morris, Flexible Control of Parallelism in a Multiprocessor PC Router. http://www.pdos.lcs.mit.edu/papers/click:usenix01/usenix01.pdf
[9]Eddie Kohler, Robert Morris, and Massimiliano Poletto. Modular Components for Network. Address Translation. http://www.pdos.lcs.mit.edu/papers/click-rewriter/paper.pdf
[10]李纪运、董小社、童端.负载均衡路由器实现动态均衡的研究.微电子学与计算机2003.7：26-29
[11]熊庆旭.输入排队结构交换机分组调度研究[J].通信学报2005,26(6)：118-129
Xiong Qingxu. Research on packet scheduling in input-queued switches[J].Journal of China Institute of Communication,2005,26(6):118-129(in Chinese)
[12]A. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services
Networks:the Single Node Case. IEEE PACM Trans on Networking,1993,1(3):344-357.
[13]Z. Zhang, D. Towsley, and J. Kurose, Statistical analysis of generalized processor sharing
scheduling discipline, IEEE Journal on Selected Areas in Communications, 95,13(6):1071-1080
[14]邬海涛,王重钢,隆克平,等.一种新的基于GPS的分组公平调度器,电子学报,2002.4：460-463
[15]A. Demers, et al. Analysis and simulation of a fair queuing algorithm[J]. Journal of
Internetworking Research and Experience,1990.10:3-26
[16]Bennett J C R, Zhang H. WF2Q:Worst-case Fair Weighted Fair Queuing. Proceedings of IEEE INFOCOM'96 [C].1996-03:120-128.
[17]Bennett J. Zhang H., "Hierarchical packet fair queueing algorithms," IEEE/ACM Transactions on
[18]S. J. Golestani. "A self-clocked fair queuing scheme for broadband applications," IEEE
INFOCOMM'94, Pages.636-645,1994.
[19]P. Goyal,H.M. Vin. "Start-time fair queueing: A scheduling algorithm for integrated services
packet switching networks," IEEE/ ACM Trans. on Networking,1997.10(5): 690-703,
[20]D. Stiliadis,A. Varma. "Efficient fair queueing algorithms for packet-switched networks," IEEE/ACM Trans. on Networking,1998.6(2):175-185,
[21]MGH. Katevenis, "Fast Switching and Fair Control of Congested Flow in Broadband Networks," IEEE on Selected Areas Comm,1987, Pages 1315-1326
[22]M. Katevenis, S. Sidiropoulos, C. Courcoubetis, "Weighted Round-Robin cell multiplexing in a general-purpose ATM switch chip," IEEE J. Selected Areas Commun. Vol.9, no.8, Pages 1265-1279,1991.
[23]M. Shreedhar, G. Varghese. "Efficient Fair Queueing Using Deficit Round Robin," Proceedings for SIGCOMM'95,1995.
[24]伍翔,孔红伟,汪卫章等.一种改进的DRR调度算法.电子与信息学报.2003.5：704-710
[25]徐恪,吴建平,吴剑,徐明伟,高性能路由器操作系统HEROS中的高可用性设计,863学术年会,2001.5。
[26]张福阳,熊庆旭,一种简单的VOQ交换机时延确保分组调度算法,北京航空航天大学学报,2008.11
[2]李胜磊.高性能路由器体系结构及其关键技术研究博士论文西安交通大学。2002
[3]Asia- Pacific Advanced Network. http://www.apan.net
[4]林闯,任丰原.可控可信可扩展的新一代互联网.软件学报,2004,15(12)：1815-1821
[5]Blake P. Resource. Telephony, February 2001. Available at http://telephonyonline.com/ar/telecom resource/index.htm
[6]Name Router 4.1 Software Product Description. http://www.eurokom.ie/wade/name-router.html
[7]Eddie Kohler. The Click Modular Router. http://www.pdos.lcs.mit.edu/papers/click:kohler-phd/thesis.pdf.
[8]Benjie Chen, and Robert Morris, Flexible Control of Parallelism in a Multiprocessor PC Router. http://www.pdos.lcs.mit.edu/papers/click:usenix01/usenix01.pdf
[9]Eddie Kohler, Robert Morris, and Massimiliano Poletto. Modular Components for Network. Address Translation. http://www.pdos.lcs.mit.edu/papers/click-rewriter/paper.pdf
[10]李纪运、董小社、童端.负载均衡路由器实现动态均衡的研究.微电子学与计算机2003.7：26-29
[11]熊庆旭.输入排队结构交换机分组调度研究[J].通信学报2005,26(6)：118-129
Xiong Qingxu. Research on packet scheduling in input-queued switches[J].Journal of China Institute of Communication,2005,26(6):118-129(in Chinese)
[12]A. Parekh. A Generalized Processor Sharing Approach to Flow Control in Integrated Services
Networks:the Single Node Case. IEEE PACM Trans on Networking,1993,1(3):344-357.
[13]Z. Zhang, D. Towsley, and J. Kurose, Statistical analysis of generalized processor sharing
scheduling discipline, IEEE Journal on Selected Areas in Communications, 95,13(6):1071-1080
[14]邬海涛,王重钢,隆克平,等.一种新的基于GPS的分组公平调度器,电子学报,2002.4：460-463
[15]A. Demers, et al. Analysis and simulation of a fair queuing algorithm[J]. Journal of
Internetworking Research and Experience,1990.10:3-26
[16]Bennett J C R, Zhang H. WF2Q:Worst-case Fair Weighted Fair Queuing. Proceedings of IEEE INFOCOM'96 [C].1996-03:120-128.
[17]Bennett J. Zhang H., "Hierarchical packet fair queueing algorithms," IEEE/ACM Transactions on
[18]S. J. Golestani. "A self-clocked fair queuing scheme for broadband applications," IEEE
INFOCOMM'94, Pages.636-645,1994.
[19]P. Goyal,H.M. Vin. "Start-time fair queueing: A scheduling algorithm for integrated services
packet switching networks," IEEE/ ACM Trans. on Networking,1997.10(5): 690-703,
[20]D. Stiliadis,A. Varma. "Efficient fair queueing algorithms for packet-switched networks," IEEE/ACM Trans. on Networking,1998.6(2):175-185,
[21]MGH. Katevenis, "Fast Switching and Fair Control of Congested Flow in Broadband Networks," IEEE on Selected Areas Comm,1987, Pages 1315-1326
[22]M. Katevenis, S. Sidiropoulos, C. Courcoubetis, "Weighted Round-Robin cell multiplexing in a general-purpose ATM switch chip," IEEE J. Selected Areas Commun. Vol.9, no.8, Pages 1265-1279,1991.
[23]M. Shreedhar, G. Varghese. "Efficient Fair Queueing Using Deficit Round Robin," Proceedings for SIGCOMM'95,1995.
[24]伍翔,孔红伟,汪卫章等.一种改进的DRR调度算法.电子与信息学报.2003.5：704-710
[25]徐恪,吴建平,吴剑,徐明伟,高性能路由器操作系统HEROS中的高可用性设计,863学术年会,2001.5。
[26]张福阳,熊庆旭,一种简单的VOQ交换机时延确保分组调度算法,北京航空航天大学学报,2008.11