大规模接入汇聚路由器ACR转发表管理软件关键技术研究
|
摘要
转发处理引擎是路由器中的关键部件之一,它负责完成IP分组的转发工作。转发处理软件作为路由器系统的一个软件子系统,其核心任务是创建和维护路由转发表。本文结合国家863项目“大规模接入汇聚路由器(ACR)系统性能与关键技术研究”,较深入的研究了ACR路由器转发软件的设计及其实现的关键技术。对转发软件模块及任务划分、转发表管理算法及其实现、转发软件任务调度及内存管理三个大的方面进行了研究。本文所做的工作如下;
1.介绍了ACR路由器转发子系统的软、硬件工作环境,对转发处理软件的功能进行了描述,并对软件进行模块、任务划分,是转发软件设计的基础。
2.对现有路由查找算法进行了分类比较,并指出了当前路由查找算法存在的问题,为ACR路由转发的研究设计提出了新的思路。
3.对现有的基于TCAM的路由表项更新算法进行了分析和比较,给出了基于哈希表的预留空间选择更新转发表算法。该算法可支持IPv4/IPv6双协议栈的路由表项更新,在ACR路由器上已得到实现,取得了较好的效果。
4.分析了VxWorks的任务调度的不足,并在VxWorks的任务调度基础上,构建了以“伪线程”为单位的二级调度策略;分析了当前基于TCAM的转发表管理方案在带突发情况下出现的不足,并基于二级调度策略提出了一种新的二级转发表管理方案,仿真研究表明该方案在带有突发的情况下仍然能够保持系统有效地工作。
5.为了降低数据传输时的操作系统开销和协议处理开销,实现高速数据传输,本文采用了“零拷贝”消息队列,减少了拷贝时所需传递的信息量,并在文章中给出了其实现方案;给出了软件中的内存管理方案,提高了系统中内存的管理效率,为软件的高效、可靠运行提供了理论和技术基础。
6.对系统的改进提出了一些措施,包括表项的一致性、报文的冗余性、系统的安全性以及系统的鲁棒性。
Forwarding engine is the most important part of the Router, its work is to route and forward the IP packet. As a subsystem of the Router software system, the core task of forwarding software is to establish and maintain the forwarding table. This dissertation is devoted to the researches of the key technologies to the design and implements the ACR forwarding software according to the requirements of 863 project: Research on system performance and key technologies of large-scale Access Convergence Router (ACR), and mainly studies the three primary parts: the forwarding table software modules and tasks partition, the forwarding table management algorithms and the implementation, the task scheme and the memory management. The main works of this dissertation are as follows:
1. The software and hardware environment of the ACR forwarding subsystem are introduced, the forwarding software functions are described, the software modules and the tasks are partitioned. This part is the base for forwarding software design.
2. This dissertation classifies and compares current routing lookup algorithms, and points out the shortage of current routing lookup scheme, which provides new ideas to the ACR forwarding design.
3. By analyzing the current TCAM updating algorithms, this dissertation presents a new scheme: Reserving empty space and selective updating algorithm based on hash table. The scheme which supports both IPv4 and IPv6 protocol is implemented in the ACR produced by NDSC, experiment results show it works well.
4. By pointing out the shortcoming of the task scheme in VxWorks OS, this dissertation designs a two stage scheme method based on the "pseudo-thread". By analyzing the shortage of the previous forwarding table management scheme when the updating messages arrive burstily, the dissertation puts forward a new two level forwarding table management scheme. Simulation results indicate that the algorithm works efficiently under the bursty case.
5. To decrease the OS cost and protocol cost when sending data, and transmit data with high speed, the dissertation adopts "zero copy" message queue to decrease the delivered information, and presents the memory management scheme to increase the efficiency to management memory, offers theories and technologies for the software to run with high efficiency and credibility.
6. At last, the dissertation gives some measures to improve the forwarding software subsystem in aspects of the consistency between the routing table and the forwarding table, the redundancy of the ICMP messages, the safety and the robust of the software system.
1.介绍了ACR路由器转发子系统的软、硬件工作环境,对转发处理软件的功能进行了描述,并对软件进行模块、任务划分,是转发软件设计的基础。
2.对现有路由查找算法进行了分类比较,并指出了当前路由查找算法存在的问题,为ACR路由转发的研究设计提出了新的思路。
3.对现有的基于TCAM的路由表项更新算法进行了分析和比较,给出了基于哈希表的预留空间选择更新转发表算法。该算法可支持IPv4/IPv6双协议栈的路由表项更新,在ACR路由器上已得到实现,取得了较好的效果。
4.分析了VxWorks的任务调度的不足,并在VxWorks的任务调度基础上,构建了以“伪线程”为单位的二级调度策略;分析了当前基于TCAM的转发表管理方案在带突发情况下出现的不足,并基于二级调度策略提出了一种新的二级转发表管理方案,仿真研究表明该方案在带有突发的情况下仍然能够保持系统有效地工作。
5.为了降低数据传输时的操作系统开销和协议处理开销,实现高速数据传输,本文采用了“零拷贝”消息队列,减少了拷贝时所需传递的信息量,并在文章中给出了其实现方案;给出了软件中的内存管理方案,提高了系统中内存的管理效率,为软件的高效、可靠运行提供了理论和技术基础。
6.对系统的改进提出了一些措施,包括表项的一致性、报文的冗余性、系统的安全性以及系统的鲁棒性。
Forwarding engine is the most important part of the Router, its work is to route and forward the IP packet. As a subsystem of the Router software system, the core task of forwarding software is to establish and maintain the forwarding table. This dissertation is devoted to the researches of the key technologies to the design and implements the ACR forwarding software according to the requirements of 863 project: Research on system performance and key technologies of large-scale Access Convergence Router (ACR), and mainly studies the three primary parts: the forwarding table software modules and tasks partition, the forwarding table management algorithms and the implementation, the task scheme and the memory management. The main works of this dissertation are as follows:
1. The software and hardware environment of the ACR forwarding subsystem are introduced, the forwarding software functions are described, the software modules and the tasks are partitioned. This part is the base for forwarding software design.
2. This dissertation classifies and compares current routing lookup algorithms, and points out the shortage of current routing lookup scheme, which provides new ideas to the ACR forwarding design.
3. By analyzing the current TCAM updating algorithms, this dissertation presents a new scheme: Reserving empty space and selective updating algorithm based on hash table. The scheme which supports both IPv4 and IPv6 protocol is implemented in the ACR produced by NDSC, experiment results show it works well.
4. By pointing out the shortcoming of the task scheme in VxWorks OS, this dissertation designs a two stage scheme method based on the "pseudo-thread". By analyzing the shortage of the previous forwarding table management scheme when the updating messages arrive burstily, the dissertation puts forward a new two level forwarding table management scheme. Simulation results indicate that the algorithm works efficiently under the bursty case.
5. To decrease the OS cost and protocol cost when sending data, and transmit data with high speed, the dissertation adopts "zero copy" message queue to decrease the delivered information, and presents the memory management scheme to increase the efficiency to management memory, offers theories and technologies for the software to run with high efficiency and credibility.
6. At last, the dissertation gives some measures to improve the forwarding software subsystem in aspects of the consistency between the routing table and the forwarding table, the redundancy of the ICMP messages, the safety and the robust of the software system.
引文
[1]Data on internet activity worldwide(hostcount)[EB/OL].http;//www.gandalf.it/data/data1/htm.2007-2
[2]G.R.Gromov.History of Internet and WWW;The Roads and Crossroads of Internet History[EB/OL].http;//netvalley.com/intvall.html.2007-4-10
[3]汪斌强,邬江兴.基于IPv6的大规模接入汇聚路由器的设想和实现[J].电信科学.2006,22(1);5-9.
[4]D.Decasper,Z.Dittia,G.Parulkar,and B.Plattner.Router Plugins;A software architecture for next generation routers[J].IEEE/ACM Transactions on Networking.2000,8(1);2-15.
[5]D.Decasper,Z.Dittia,G.Parulkar,and B.Plattner.Router Plugins;A Modular and Extensible Software Framework for Modern High Performance Integrated Services Routers[J].Washington university technical report;Wucs-98-08,February 1998.
[6]何宁.张云龙.吴晨.核心路由器发展趋势[J].通信产业报,2001.
[7]King H,Chu J.Zero-copy TCP in solaris[A].In;USENLX Association,ed.Proceedings of the USENLX 1996 Annual Technical Conference[C].San Diego;USENLX Association,1996;253-264.
[8]孔祥营.柏桂枝.嵌入式实时操作系统VxWorks及其开发环境Tornado[M].北京;中国电力出版社,2002.
[9]Wind River Systems Inc.VxWorks Programmer's Guide[M].Wind River Systems,Inc.,2000.
[10]Wind River Systems,Inc.VxWorks Network Programmer's Guide[M].Wind River Systems,Inc.,2000.
[11]Lee J K.Jung S J.Kim S D.et.al Component identification method with coupling and cohesion[C].In;Proceedings of the 8th Asia-Pacific Software Engineering Conference.Macau;IEEE Computer Society Press.2001;79-86.
[12]P Gupta.Algorithms for routing lookups and packet classification[D].Stanford University,2000.
[13]AS1221 BGP Routing Table Analysis Report[EB/OL]http;//bgp.potaroo.net/as1221/bgp-active.html.2007-4-10.
[14]Douglas E.Comer著.林瑶.蒋慧.杜蔚轩等译.用TCP/IP进行网际互联[M].电子工业出版社,2001.
[15]李津生.洪佩琳编著.下一代Iternet的网络技术[M].人民邮电出版社,2001.
[16]Y.Rekhter T.Li.An Architecture for IP Address Allocation with CIDR[EB/OL].http;//rfc.net/rfc1518.html.2007-4-10.
[17]V.Fuller T.Li J.Yu K.Varadhan Classless Inter-Domain Routing(CIDR);An Address Assignment and Aggregation Strategy[EB/OL].http;//rfc.net/rfc1519.html.2007-4-10.
[18]Waldvogel M,Varghese G,Tunner J,et al.Scalable High Speed IP Routing Lookups[J] Computer Communication Review,1997,27(4);2536.
[19]D.R.Morrison.PATRICIA—practical algorithm to retrieve information coded in alphanumeric[J].Journal of the ACM,1968,15(14);514-534.
[20]The Cisco 12000 Series internet routers[EB/OL].http;//www.cisco.com/warp/public/cc/pd/rt/12000/index.shtml.2007-4-10.
[21]V.Srinivasan.Fast and efficient Internet lookups[D].Washington University,1999.
[22]S.Nilsson and G.Karlsson,Fast Address Lookup for Internet Routers[J].Proceedings of Algorithms and Experiments,1998;9-18.
[23]S.Nilsson and G.Karlsson.IP-address lookup using LC-tries[J].IEEE Journal of Selected Areas in Communications,1999,17(6);1083-1092.
[24]M.Waldvogel,G.Varghese,J.Turner and B.Plattner.Scalable high-speed IP routing lookups[J].Proceedings of ACM Sigcomm,1997;25-36.
[25]B.Lampson,V.Srinivasan and G.Varghese.IP lookups using multiway and multicolumn search[J].IEEE/ACM Transactions on Networking,1999,7(3);324-334.
[26]A.J.McAuley and P.Francis.Fast routing table lookup using CAMs[J].Proceedings of IEEE Infocom,1993;1382-1391.
[27]Do Shah and P.Gupta.Fast incremental updates on Ternary-CAMs for routing lookups and packet classification[J].IEEE Micro,2001,21(1);34-41.
[28]兰巨龙.高速路由器转发与调度算法的研究与实现[D].郑州;信息工程大学,2001.11.
[29]P.Gupta,S.Lin and N.McKeown.Routing lookups in hardware at memory access speeds[J].Proceedings of IEEE Infocom,1998;1240-1247.
[30]G.Cheung and S.McCanne.Optimal routing table design for IP address lookups under memory constraints[J].Proceedings of IEEE INFOCOM 1999;1437-1444.
[31]T.Chiueh and P.Pradhan.High performance IP routing table lookup using CPU caching[J].Proceedings of IEEE INFOCOM,1999;1421-1428.
[32]D.Decasper,Z.Dittia,G.Parulkar and B.Plattner.Router plugins;A software architecture for next generation routers[J].IEEE/ACM Transactions on Networking,2000,8(1);2-15.
[33]M.Degermark,A.Brodnik,S.Carlsson and S.Pink.Small forwarding tables for fast routing lookups[J].Proceedings of ACM Sigcomm,1997,27(4);3-14.
[34]W.Doeringer,G.Karjoth and M.Nassehi.Routing on longest-matching prefixes[J].IEEE/ACM Transactions on Networking,1996,4(1);86-97.
[35]D.C.Feldmeier.Improving gateway performance with a routing-table cache[J].Proceedings of IEEE INFOCOM,1988;298-307.
[36]N.F.Huang,S.M.Zhao,Jen-Yi Pan and Chi-An Su.A Fast IP routing lookup scheme for gigabit switching touters[J].Proceedings of IEEE INFOCOM,1999;1429-1436.
[37]T.Kijkanjanarat and H.J.Chao.Fast IP routing lookups for high performance routers[J].Computer Communications,1999,22;1415-1422.
[38]T.V.Lakshman and D.Stiliadis.High-speed policy-based packet forwarding using efficient multi-dimensional range matching[J].Proceedings of ACM Sigcomm,1998;191-202.
[39]V.Srinivasan and G.Varghese.Faster IP lookups using controlled prefix expansion[J].ACM Transactions on Computer Systems,1999,17(1);1-40.
[40]V.Srinivasan and G.Varghese.A survey of recent IP lookup schemes[J].Proceedings of Conference on Protocols for High Speed Networks,1999;9-23.
[41]H.H.Y.Tzeng and T.Przygienda.On fast address lookup algorithms[J].IEEE Journal of Selected Areas in Communications,1999,17(6);1067-1082.
[42]Andrew S.Tanenbaum.Modern Operating Systems[M].北京;机械工业出版社,1999.
[43]纪其进.董永强.一种链路负载自适应的主动队列管理算法[J].软件学报,2006,17(5);1140-1148.
[44]Baiecchi A.Blefari-Melazzi N Steady-state anaysis of the MMPP/G/1/K queue[J].IEEE Trans.Commun.1993,41(4);531～534.
[45]付立政.肖波.侯东.栾贵若.基于独立MMPP业务输入模型的输入/输出排队ATM交换机性能分析方法研究[J].小型微型计算机系统,2001,22(1);33-36.
[46]郑军俊.胡幼华.ATM交换机缓存策略的仿真建模和性能分析[J].计算机应用与软件,2005,22(12);69-71.
[47]杨立峰.ATM网络中基于MMPP的优先队列的分析[J].安徽大学学报(自然科学版),1999,23(3);17-20.
[48]BGP Table Data Prefix Length Distribution[EB/OL].http;//bgp.potaroo.net/as1221.2007-4-10.
[49]F.Baker.Requirements for IP version 4 routers.[EB/OL]http;//rfc.net/rfc1812.html.2007-4-10.
[2]G.R.Gromov.History of Internet and WWW;The Roads and Crossroads of Internet History[EB/OL].http;//netvalley.com/intvall.html.2007-4-10
[3]汪斌强,邬江兴.基于IPv6的大规模接入汇聚路由器的设想和实现[J].电信科学.2006,22(1);5-9.
[4]D.Decasper,Z.Dittia,G.Parulkar,and B.Plattner.Router Plugins;A software architecture for next generation routers[J].IEEE/ACM Transactions on Networking.2000,8(1);2-15.
[5]D.Decasper,Z.Dittia,G.Parulkar,and B.Plattner.Router Plugins;A Modular and Extensible Software Framework for Modern High Performance Integrated Services Routers[J].Washington university technical report;Wucs-98-08,February 1998.
[6]何宁.张云龙.吴晨.核心路由器发展趋势[J].通信产业报,2001.
[7]King H,Chu J.Zero-copy TCP in solaris[A].In;USENLX Association,ed.Proceedings of the USENLX 1996 Annual Technical Conference[C].San Diego;USENLX Association,1996;253-264.
[8]孔祥营.柏桂枝.嵌入式实时操作系统VxWorks及其开发环境Tornado[M].北京;中国电力出版社,2002.
[9]Wind River Systems Inc.VxWorks Programmer's Guide[M].Wind River Systems,Inc.,2000.
[10]Wind River Systems,Inc.VxWorks Network Programmer's Guide[M].Wind River Systems,Inc.,2000.
[11]Lee J K.Jung S J.Kim S D.et.al Component identification method with coupling and cohesion[C].In;Proceedings of the 8th Asia-Pacific Software Engineering Conference.Macau;IEEE Computer Society Press.2001;79-86.
[12]P Gupta.Algorithms for routing lookups and packet classification[D].Stanford University,2000.
[13]AS1221 BGP Routing Table Analysis Report[EB/OL]http;//bgp.potaroo.net/as1221/bgp-active.html.2007-4-10.
[14]Douglas E.Comer著.林瑶.蒋慧.杜蔚轩等译.用TCP/IP进行网际互联[M].电子工业出版社,2001.
[15]李津生.洪佩琳编著.下一代Iternet的网络技术[M].人民邮电出版社,2001.
[16]Y.Rekhter T.Li.An Architecture for IP Address Allocation with CIDR[EB/OL].http;//rfc.net/rfc1518.html.2007-4-10.
[17]V.Fuller T.Li J.Yu K.Varadhan Classless Inter-Domain Routing(CIDR);An Address Assignment and Aggregation Strategy[EB/OL].http;//rfc.net/rfc1519.html.2007-4-10.
[18]Waldvogel M,Varghese G,Tunner J,et al.Scalable High Speed IP Routing Lookups[J] Computer Communication Review,1997,27(4);2536.
[19]D.R.Morrison.PATRICIA—practical algorithm to retrieve information coded in alphanumeric[J].Journal of the ACM,1968,15(14);514-534.
[20]The Cisco 12000 Series internet routers[EB/OL].http;//www.cisco.com/warp/public/cc/pd/rt/12000/index.shtml.2007-4-10.
[21]V.Srinivasan.Fast and efficient Internet lookups[D].Washington University,1999.
[22]S.Nilsson and G.Karlsson,Fast Address Lookup for Internet Routers[J].Proceedings of Algorithms and Experiments,1998;9-18.
[23]S.Nilsson and G.Karlsson.IP-address lookup using LC-tries[J].IEEE Journal of Selected Areas in Communications,1999,17(6);1083-1092.
[24]M.Waldvogel,G.Varghese,J.Turner and B.Plattner.Scalable high-speed IP routing lookups[J].Proceedings of ACM Sigcomm,1997;25-36.
[25]B.Lampson,V.Srinivasan and G.Varghese.IP lookups using multiway and multicolumn search[J].IEEE/ACM Transactions on Networking,1999,7(3);324-334.
[26]A.J.McAuley and P.Francis.Fast routing table lookup using CAMs[J].Proceedings of IEEE Infocom,1993;1382-1391.
[27]Do Shah and P.Gupta.Fast incremental updates on Ternary-CAMs for routing lookups and packet classification[J].IEEE Micro,2001,21(1);34-41.
[28]兰巨龙.高速路由器转发与调度算法的研究与实现[D].郑州;信息工程大学,2001.11.
[29]P.Gupta,S.Lin and N.McKeown.Routing lookups in hardware at memory access speeds[J].Proceedings of IEEE Infocom,1998;1240-1247.
[30]G.Cheung and S.McCanne.Optimal routing table design for IP address lookups under memory constraints[J].Proceedings of IEEE INFOCOM 1999;1437-1444.
[31]T.Chiueh and P.Pradhan.High performance IP routing table lookup using CPU caching[J].Proceedings of IEEE INFOCOM,1999;1421-1428.
[32]D.Decasper,Z.Dittia,G.Parulkar and B.Plattner.Router plugins;A software architecture for next generation routers[J].IEEE/ACM Transactions on Networking,2000,8(1);2-15.
[33]M.Degermark,A.Brodnik,S.Carlsson and S.Pink.Small forwarding tables for fast routing lookups[J].Proceedings of ACM Sigcomm,1997,27(4);3-14.
[34]W.Doeringer,G.Karjoth and M.Nassehi.Routing on longest-matching prefixes[J].IEEE/ACM Transactions on Networking,1996,4(1);86-97.
[35]D.C.Feldmeier.Improving gateway performance with a routing-table cache[J].Proceedings of IEEE INFOCOM,1988;298-307.
[36]N.F.Huang,S.M.Zhao,Jen-Yi Pan and Chi-An Su.A Fast IP routing lookup scheme for gigabit switching touters[J].Proceedings of IEEE INFOCOM,1999;1429-1436.
[37]T.Kijkanjanarat and H.J.Chao.Fast IP routing lookups for high performance routers[J].Computer Communications,1999,22;1415-1422.
[38]T.V.Lakshman and D.Stiliadis.High-speed policy-based packet forwarding using efficient multi-dimensional range matching[J].Proceedings of ACM Sigcomm,1998;191-202.
[39]V.Srinivasan and G.Varghese.Faster IP lookups using controlled prefix expansion[J].ACM Transactions on Computer Systems,1999,17(1);1-40.
[40]V.Srinivasan and G.Varghese.A survey of recent IP lookup schemes[J].Proceedings of Conference on Protocols for High Speed Networks,1999;9-23.
[41]H.H.Y.Tzeng and T.Przygienda.On fast address lookup algorithms[J].IEEE Journal of Selected Areas in Communications,1999,17(6);1067-1082.
[42]Andrew S.Tanenbaum.Modern Operating Systems[M].北京;机械工业出版社,1999.
[43]纪其进.董永强.一种链路负载自适应的主动队列管理算法[J].软件学报,2006,17(5);1140-1148.
[44]Baiecchi A.Blefari-Melazzi N Steady-state anaysis of the MMPP/G/1/K queue[J].IEEE Trans.Commun.1993,41(4);531～534.
[45]付立政.肖波.侯东.栾贵若.基于独立MMPP业务输入模型的输入/输出排队ATM交换机性能分析方法研究[J].小型微型计算机系统,2001,22(1);33-36.
[46]郑军俊.胡幼华.ATM交换机缓存策略的仿真建模和性能分析[J].计算机应用与软件,2005,22(12);69-71.
[47]杨立峰.ATM网络中基于MMPP的优先队列的分析[J].安徽大学学报(自然科学版),1999,23(3);17-20.
[48]BGP Table Data Prefix Length Distribution[EB/OL].http;//bgp.potaroo.net/as1221.2007-4-10.
[49]F.Baker.Requirements for IP version 4 routers.[EB/OL]http;//rfc.net/rfc1812.html.2007-4-10.