针对层次化名字路由的聚合机制
|
摘要
为了从根本上解决现有互联网存在的可扩展性、移动性和安全性等方面的问题,全新的未来互联网体系结构得到了广泛研究.其中,命名数据网络(named data networking,简称NDN)利用网内缓存和多路转发实现了基于层次化名字的高效数据传输,从根本上解决了现有互联网所面临的问题.内容的层次化名字具有数量庞大、结构复杂等特点,现有的基于IP的路由转发机制无法直接应用于NDN网络,需要有针对性地研究高效的层次化名字路由机制,保证海量网络内容的正常路由转发.路由聚合是缩减网络路由规模的主要措施.不同于现有的面向本地NDN路由表查表过程的优化,路由聚合需要全网协同处理,在不同网络节点上不断对聚合路由进行聚合.这对聚合路由标识和聚合路由可用性评估提出了诸多要求.为此,研究并提出了针对层次化名字路由的聚合机制,包括两个方面的工作:(1)构建了一种全新的计数布隆过滤器——堆叠布隆过滤器,该过滤器支持多过滤器合并,用于压缩表示被聚合路由名字;(2)给出了一种动态路由聚合机制,在保证NDN网络路由转发准确性的同时,缩小全网路由规模,最大程度地优化了路由转发效率.在真实网络拓扑上构建了仿真平台,经过实验验证,该路由聚合机制以可控的少量冗余转发为代价,有效地压缩了全网路由规模,提升了全网路由转发效率,保证了海量在线内容的高效路由转发,为NDN网络投入实际部署提供了前提.
TCP/IP-based Internet is faced with severe challenges in scalability, mobility, security, and controllability, which makes it necessary to research the clean-slate architecture for Internet. Named Data Networking(NDN) leverages in-network caching and multipath transmission to support data name-based packet transmission, and conquers the aforementioned challenges faced by the conventional Internet. Considering the huge number and the significant diversity of hierarchical names used in NDN, the existing IP-based routing cannot be directly applied, and efficient hierarchical name-based routing mechanisms are desired to gurantee stable data transmission.Route aggregation is the core mechanism for FIB size reduction in the TCP/IP-based Internet. Hierarchical name-based route aggregation leverages router cooperation over the whole network to aggregate routes recursively, different from the existing researches for name-based route lookup optimization on a single router. To achieve effective hierarchical name-based route aggregation, identifier generation is focused on in route aggregation and utility evaluation of the aggregated routes. Ultimately, a hierarchical name-based route aggregation scheme is proposed, including two parts:(1) A novel combinable counting Bloom filter for representing aggregated route names compactly, namely, Compounded Counting Bloom Filter(CCBF);(2) A dynamic route aggregation scheme over the whole network for aggregating routes recursively according to their utility. To evaluate the performance of the proposed route aggregation scheme, extensive simulations are performed based on real network topology. Evaluation results show that the proposed scheme can significantly reduce FIB size and improve FIB lookup efficiency at the cost of small number of false positive lookup results. This work provides a foundation for practical NDN deployment.
TCP/IP-based Internet is faced with severe challenges in scalability, mobility, security, and controllability, which makes it necessary to research the clean-slate architecture for Internet. Named Data Networking(NDN) leverages in-network caching and multipath transmission to support data name-based packet transmission, and conquers the aforementioned challenges faced by the conventional Internet. Considering the huge number and the significant diversity of hierarchical names used in NDN, the existing IP-based routing cannot be directly applied, and efficient hierarchical name-based routing mechanisms are desired to gurantee stable data transmission.Route aggregation is the core mechanism for FIB size reduction in the TCP/IP-based Internet. Hierarchical name-based route aggregation leverages router cooperation over the whole network to aggregate routes recursively, different from the existing researches for name-based route lookup optimization on a single router. To achieve effective hierarchical name-based route aggregation, identifier generation is focused on in route aggregation and utility evaluation of the aggregated routes. Ultimately, a hierarchical name-based route aggregation scheme is proposed, including two parts:(1) A novel combinable counting Bloom filter for representing aggregated route names compactly, namely, Compounded Counting Bloom Filter(CCBF);(2) A dynamic route aggregation scheme over the whole network for aggregating routes recursively according to their utility. To evaluate the performance of the proposed route aggregation scheme, extensive simulations are performed based on real network topology. Evaluation results show that the proposed scheme can significantly reduce FIB size and improve FIB lookup efficiency at the cost of small number of false positive lookup results. This work provides a foundation for practical NDN deployment.
引文
[1]Bari MF,Chowdhury SR,Ahmed R,Boutaba R,Mathieu B.A survey of naming and routing in information-centric networks.IEEECommunications Magazine,2012,50(12):44-53.[doi:10.1109/MCOM.2012.6384450]
[2]Koponen T,Chawla M,Chun BG,Ermolinskiy A,Kim KH,Shenker S,Stoica I.A data-oriented(and beyond)network architecture.In:Proc.of the 2007 Conf.on Applications,Technologies,Architectures,and Protocols for Computer Communications.New York:ACM Press,2007.181-192.[doi:10.1145/1282427.1282402]
[3]Roberts J.The clean-slate approach to future internet design:A survey of research initiatives.Annals of Telecommunications,2009,64(5):271-276.[doi:10.1007/s12243-009-0109-y]
[4]Xie GG,Zhang YJ,Li ZY,Sun Y,Xie YK,Li ZC,Liu YJ.A survey on future internet architecture.Chinese Journal of Computers,2012,35(6):1109-1119(in Chinese with English abstract).[doi:10.3724/SP.J.1016.2012.01109]
[5]Wu C,Zhang YX,Zhou YZ,Fu XM.A survey for the development of information-centric networking.Chinese Journal of Computers,2015,38(3):455-471(in Chinese with English abstract).[doi:10.3724/SP.J.1016.2015.00455]
[6]Jacobson V,Smetters DK,Thornton JD,Plass MF,Briggs NH,Braynard RL.Networking named content.In:Proc.of the 5th Int’l Conf.on Emerging Networking Experiments and Technologies.New York:ACM Press,2009.1-12.[doi:10.1145/1658939.1658941]
[7]Zhang LX,Jacobson V,Zhang BC,Tsudik G,Claffy KC,Massey D,Abdelzaher T,Wang L,Crowley P,Yeh E.Named data networking(NDN)project.Technical Report,NDN-0001,Los Angeles:UCLA,2017.
[8]Wu H,Shi JX,Wang YX,Wang YL,Zhang G,Wang Y,Liu B,Zhang BC.On incremental deployment of named data networking in local area networks.In:Proc.of the Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEEPress,2017.82-94.[doi:10.1109/ANCS.2017.18]
[9]Liang CC,Yu FR,Zhang X.Information-centric network function virtualization over 5G mobile wireless networks.IEEE Network,2015,29(3):68-74.[doi:10.1109/MNET.2015.7113228]
[10]Wang Y,He KQ,Dai HC,Meng W,Jiang JC,Liu B,Yan C.Scalable name lookup in ndn using effective name component encoding.In:Proc.of the 2012 IEEE 32nd Int’l Conf.on Distributed Computing Systems.Piscataway:IEEE,2012.688-697.[doi:10.1109/ICDCS.2012.35]
[11]Wang Y,Zu Y,Zhang T,Peng KY,Dong QF,Liu B,Meng W,Dai HC,Tian X,Xu ZH,Wu H,Yang D.Wire speed name lookup:A GPU-based approach.In:Proc.of the 10th USENIX Conf.on Networked Systems Design and Implementation.Berkeley:USENIX Association,2013.199-212.
[12]Shi JX,Liang T,Wu H,Liu B,Zhang BC.NDN-NIC:Name-based filtering on network interface card.In:Proc.of the 3rd ACMConf.on Information-centric Networking.New York:ACM Press,2016.40-49.[doi:10.1145/2984356.2984358]
[13]So W,Narayanan A,Oran D,Wang YG.Toward fast NDN software forwarding lookup engine based on hash tables.In:Proc.of the 2012 ACM/IEEE Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEE,2012.85-86.[doi:10.1145/2396556.2396575]
[14]So W,Narayanan A,Oran D,Stapp M.Named data networking on a router:Forwarding at 20Gbps and beyond.In:Proc.of the ACM SIGCOMM 2013 Conf.on SIGCOMM.New York:ACM Press,2013.495-496.[doi:10.1145/2486001.2491699]
[15]Le F,Xie GG,Zhang H.On route aggregation.In:Proc.of the 7th Conf.on Emerging Networking Experiments and Technologies.New York:ACM Press,2011.1-12.[doi:10.1145/2079296.2079302]
[16]Degermark M,Brodnik A,Carlsson S,Pink S.Small forwarding tables for fast routing lookups.In:Proc.of the ACMSIGCOMM’97 Conf.on Applications,Technologies,Architectures,and Protocols for Computer Communication.New York:ACMPress,1997.3-14.[doi:10.1145/263105.263133]
[17]Dharmapurikar S,Krishnamurthy P,Taylor DE.Longest prefix matching using Bloom filters.In:Proc.of the 2003 Conf.on Applications,Technologies,Architectures,and Protocols for Computer Communications.New York:ACM Press,2003.201-212.[doi:10.1145/863955.863979]
[18]Pong F,Tzeng NF.Concise lookup tables for IPv4 and IPv6 longest prefix matching in scalable routers.IEEE Trans.on Networking,2012,20(3):729-741.[doi:10.1109/TNET.2011.2167158]
[19]Yi C,Afanasyev A,Wang L,Zhang BC,Zhang LX.Adaptive forwarding in named data networking.ACM SIGCOMM Computer Communication Review,2012,42(3):62-67.[doi:10.1145/2317307.2317319]
[20]Wang L,Hoque AKM,Yi C,Alyyan A,Zhang BC.OSPFN:An OSPF based routing protocol for named data networking.Technical Report,NDN-0003.Memphis:University of Memphis,2012.
[21]Hoque AKMM,Amin SO,Alyyan A,Zhang BC,Zhang LX,Wang L.NLSR:Named-data link state routing protocol.In:Proc.of the 3rd ACM SIGCOMM Workshop on Information-centric Networking.New York:ACM Press,2013.15-20.[doi:10.1145/2491224.2491231]
[22]Li F,Chen FY,Wu JM,Xie HY.Fast longest prefix name lookup for content-centric network forwarding.In:Proc.of the 2012ACM/IEEE Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEE,2012.73-74.[doi:10.1145/2396556.2396569]
[23]Dai HC,Lu JY,Wang Y,Liu B.A two-layer intra-domain routing scheme for named data networking.In:Proc.of the 2012 IEEEGlobal Communications Conf.Piscataway:IEEE,2012.2815-2820.[doi:10.1109/GLOCOM.2012.6503543]
[24]Garcia-Luna-Aceves JJ.A more scalable approach to content centric networking.In:Proc.of the 2015 24th Int’l Conf.on Computer Communication and Networks.Piscataway:IEEE,2015.1-8.[doi:10.1109/ICCCN.2015.7288363]
[25]Yuan HW,Crowley P.Reliably scalable name prefix lookup.In:Proc.of the 2015 ACM/IEEE Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEE,2015.111-121.[doi:10.1109/ANCS.2015.7110125]
[26]Broder A,Mitzenmacher M.Network applications of Bloom filters:A survey.Internet Mathematics,2004,1(4):485-509.[doi:10.1080/15427951.2004.10129096]
[27]Fan L,Cao P,Almeida J,Broder AZ.Summary cache:A scalavble wide-area Web cache sharing protocol.ACM SIGCOMMComputer Commnication Review,1998,28(4):254-265.[doi:10.1145/285243.285287]
[28]Cohen S,Matias Y.Spectral Bloom filters.In:Proc.of the 2003 ACM SIGMOD Int’l Conf.on Management of Data.New York:ACM Press,2003.241-252.[doi:10.1145/872757.872787]
[29]Bonomi F,Mitzenmacher M,Panigrahy R,Singh S,Varghese G.An improved construction for counting Bloom filters.In:Proc.of the 14th Conf.on Annual European Symp.London:Springer-Verlag,2006.684-695.[doi:10.1007/11841036_61]
[30]Huang K,Zhang J,Zhang DF,Xie GG,Salamatian K,Liu AX,Li W.A multi-partitioning approach to building fast and accurate counting Bloom filters.In:Proc.of the 2013 IEEE 27th Int’l Symp.on Parallel and Distributed Processing.Piscataway:IEEE,2013.1159-1170.[doi:10.1109/IPDPS.2013.51]
[31]Béla B.Random Graphs.2nd ed.,Cambridge:Cambridge University Press,2001.130-159.
[32]Afanasyev A,Moiseenko I,Zhang LX.NDNSIM:NDN simulator for ns-3.Technical Report,NDN-0005.Los Angeles:UCLA,2012.
[33]Spring N,Mahajan R,Wetherall D,Anderson T.Measuring ISP topologies with rocketfuel.ACM SIGCOMM Computer Communication Review,2002,32(4):133-145.[doi:10.1145/964725.633039]
[4]谢高岗,张玉军,李振宇,孙毅,谢应科,李忠诚,刘韵洁.未来互联网体系结构研究综述.计算机学报,2012,35(6):1109-1119.[doi:10.3724/SP.J.1016.2012.01109]
[5]吴超,张尧学,周悦芝,傅晓明.信息中心网络发展研究综述.计算机学报,2015,38(3):455-471.[doi:10.3724/SP.J.1016.2015.00455]
[2]Koponen T,Chawla M,Chun BG,Ermolinskiy A,Kim KH,Shenker S,Stoica I.A data-oriented(and beyond)network architecture.In:Proc.of the 2007 Conf.on Applications,Technologies,Architectures,and Protocols for Computer Communications.New York:ACM Press,2007.181-192.[doi:10.1145/1282427.1282402]
[3]Roberts J.The clean-slate approach to future internet design:A survey of research initiatives.Annals of Telecommunications,2009,64(5):271-276.[doi:10.1007/s12243-009-0109-y]
[4]Xie GG,Zhang YJ,Li ZY,Sun Y,Xie YK,Li ZC,Liu YJ.A survey on future internet architecture.Chinese Journal of Computers,2012,35(6):1109-1119(in Chinese with English abstract).[doi:10.3724/SP.J.1016.2012.01109]
[5]Wu C,Zhang YX,Zhou YZ,Fu XM.A survey for the development of information-centric networking.Chinese Journal of Computers,2015,38(3):455-471(in Chinese with English abstract).[doi:10.3724/SP.J.1016.2015.00455]
[6]Jacobson V,Smetters DK,Thornton JD,Plass MF,Briggs NH,Braynard RL.Networking named content.In:Proc.of the 5th Int’l Conf.on Emerging Networking Experiments and Technologies.New York:ACM Press,2009.1-12.[doi:10.1145/1658939.1658941]
[7]Zhang LX,Jacobson V,Zhang BC,Tsudik G,Claffy KC,Massey D,Abdelzaher T,Wang L,Crowley P,Yeh E.Named data networking(NDN)project.Technical Report,NDN-0001,Los Angeles:UCLA,2017.
[8]Wu H,Shi JX,Wang YX,Wang YL,Zhang G,Wang Y,Liu B,Zhang BC.On incremental deployment of named data networking in local area networks.In:Proc.of the Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEEPress,2017.82-94.[doi:10.1109/ANCS.2017.18]
[9]Liang CC,Yu FR,Zhang X.Information-centric network function virtualization over 5G mobile wireless networks.IEEE Network,2015,29(3):68-74.[doi:10.1109/MNET.2015.7113228]
[10]Wang Y,He KQ,Dai HC,Meng W,Jiang JC,Liu B,Yan C.Scalable name lookup in ndn using effective name component encoding.In:Proc.of the 2012 IEEE 32nd Int’l Conf.on Distributed Computing Systems.Piscataway:IEEE,2012.688-697.[doi:10.1109/ICDCS.2012.35]
[11]Wang Y,Zu Y,Zhang T,Peng KY,Dong QF,Liu B,Meng W,Dai HC,Tian X,Xu ZH,Wu H,Yang D.Wire speed name lookup:A GPU-based approach.In:Proc.of the 10th USENIX Conf.on Networked Systems Design and Implementation.Berkeley:USENIX Association,2013.199-212.
[12]Shi JX,Liang T,Wu H,Liu B,Zhang BC.NDN-NIC:Name-based filtering on network interface card.In:Proc.of the 3rd ACMConf.on Information-centric Networking.New York:ACM Press,2016.40-49.[doi:10.1145/2984356.2984358]
[13]So W,Narayanan A,Oran D,Wang YG.Toward fast NDN software forwarding lookup engine based on hash tables.In:Proc.of the 2012 ACM/IEEE Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEE,2012.85-86.[doi:10.1145/2396556.2396575]
[14]So W,Narayanan A,Oran D,Stapp M.Named data networking on a router:Forwarding at 20Gbps and beyond.In:Proc.of the ACM SIGCOMM 2013 Conf.on SIGCOMM.New York:ACM Press,2013.495-496.[doi:10.1145/2486001.2491699]
[15]Le F,Xie GG,Zhang H.On route aggregation.In:Proc.of the 7th Conf.on Emerging Networking Experiments and Technologies.New York:ACM Press,2011.1-12.[doi:10.1145/2079296.2079302]
[16]Degermark M,Brodnik A,Carlsson S,Pink S.Small forwarding tables for fast routing lookups.In:Proc.of the ACMSIGCOMM’97 Conf.on Applications,Technologies,Architectures,and Protocols for Computer Communication.New York:ACMPress,1997.3-14.[doi:10.1145/263105.263133]
[17]Dharmapurikar S,Krishnamurthy P,Taylor DE.Longest prefix matching using Bloom filters.In:Proc.of the 2003 Conf.on Applications,Technologies,Architectures,and Protocols for Computer Communications.New York:ACM Press,2003.201-212.[doi:10.1145/863955.863979]
[18]Pong F,Tzeng NF.Concise lookup tables for IPv4 and IPv6 longest prefix matching in scalable routers.IEEE Trans.on Networking,2012,20(3):729-741.[doi:10.1109/TNET.2011.2167158]
[19]Yi C,Afanasyev A,Wang L,Zhang BC,Zhang LX.Adaptive forwarding in named data networking.ACM SIGCOMM Computer Communication Review,2012,42(3):62-67.[doi:10.1145/2317307.2317319]
[20]Wang L,Hoque AKM,Yi C,Alyyan A,Zhang BC.OSPFN:An OSPF based routing protocol for named data networking.Technical Report,NDN-0003.Memphis:University of Memphis,2012.
[21]Hoque AKMM,Amin SO,Alyyan A,Zhang BC,Zhang LX,Wang L.NLSR:Named-data link state routing protocol.In:Proc.of the 3rd ACM SIGCOMM Workshop on Information-centric Networking.New York:ACM Press,2013.15-20.[doi:10.1145/2491224.2491231]
[22]Li F,Chen FY,Wu JM,Xie HY.Fast longest prefix name lookup for content-centric network forwarding.In:Proc.of the 2012ACM/IEEE Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEE,2012.73-74.[doi:10.1145/2396556.2396569]
[23]Dai HC,Lu JY,Wang Y,Liu B.A two-layer intra-domain routing scheme for named data networking.In:Proc.of the 2012 IEEEGlobal Communications Conf.Piscataway:IEEE,2012.2815-2820.[doi:10.1109/GLOCOM.2012.6503543]
[24]Garcia-Luna-Aceves JJ.A more scalable approach to content centric networking.In:Proc.of the 2015 24th Int’l Conf.on Computer Communication and Networks.Piscataway:IEEE,2015.1-8.[doi:10.1109/ICCCN.2015.7288363]
[25]Yuan HW,Crowley P.Reliably scalable name prefix lookup.In:Proc.of the 2015 ACM/IEEE Symp.on Architectures for Networking and Communications Systems.Piscataway:IEEE,2015.111-121.[doi:10.1109/ANCS.2015.7110125]
[26]Broder A,Mitzenmacher M.Network applications of Bloom filters:A survey.Internet Mathematics,2004,1(4):485-509.[doi:10.1080/15427951.2004.10129096]
[27]Fan L,Cao P,Almeida J,Broder AZ.Summary cache:A scalavble wide-area Web cache sharing protocol.ACM SIGCOMMComputer Commnication Review,1998,28(4):254-265.[doi:10.1145/285243.285287]
[28]Cohen S,Matias Y.Spectral Bloom filters.In:Proc.of the 2003 ACM SIGMOD Int’l Conf.on Management of Data.New York:ACM Press,2003.241-252.[doi:10.1145/872757.872787]
[29]Bonomi F,Mitzenmacher M,Panigrahy R,Singh S,Varghese G.An improved construction for counting Bloom filters.In:Proc.of the 14th Conf.on Annual European Symp.London:Springer-Verlag,2006.684-695.[doi:10.1007/11841036_61]
[30]Huang K,Zhang J,Zhang DF,Xie GG,Salamatian K,Liu AX,Li W.A multi-partitioning approach to building fast and accurate counting Bloom filters.In:Proc.of the 2013 IEEE 27th Int’l Symp.on Parallel and Distributed Processing.Piscataway:IEEE,2013.1159-1170.[doi:10.1109/IPDPS.2013.51]
[31]Béla B.Random Graphs.2nd ed.,Cambridge:Cambridge University Press,2001.130-159.
[32]Afanasyev A,Moiseenko I,Zhang LX.NDNSIM:NDN simulator for ns-3.Technical Report,NDN-0005.Los Angeles:UCLA,2012.
[33]Spring N,Mahajan R,Wetherall D,Anderson T.Measuring ISP topologies with rocketfuel.ACM SIGCOMM Computer Communication Review,2002,32(4):133-145.[doi:10.1145/964725.633039]
[4]谢高岗,张玉军,李振宇,孙毅,谢应科,李忠诚,刘韵洁.未来互联网体系结构研究综述.计算机学报,2012,35(6):1109-1119.[doi:10.3724/SP.J.1016.2012.01109]
[5]吴超,张尧学,周悦芝,傅晓明.信息中心网络发展研究综述.计算机学报,2015,38(3):455-471.[doi:10.3724/SP.J.1016.2015.00455]