摘要
随着互联网规模的膨胀,大量的实时应用部署在互联网上,这些实时应用对网络时延提出了更加严格的要求。然而,目前互联网部署的域内路由协议无法满足实时应用对网络时延的要求,因此提高域内路由可用性成为了一项亟待解决的关键性科学问题。学术界和工业界提出利用路由保护方案来提高路由可用性,从而减少由于网络故障造成的网络中断和报文丢失。已有的路由保护方案将网络中的节点同等对待,没有考虑节点在网络中的重要程度,然而实际情况并非如此。因此,提出了一种基于关键节点的域内路由保护算法(Intra-domain Routing Protection Algorithm Based on Critical Nodes,RPBCN)。首先,建立路由可用性模型,以定量衡量路由可用性;其次,建立节点关键度模型,以定量衡量网络中节点的重要程度;最后,基于路由可用性模型和节点关键度模型,提出基于关键节点的域内路由保护方案。实验结果表明,RPBCN在保证路由可用性的前提下极大地降低了算法的计算开销,从而为ISP解决路由可用性问题提供了一种全新的高效解决方案。
With the expansion of the Internet,a large number of real-time applications are deployed on the Internet,which places greater demands on network delay.However,the current deployed intra-domain routing protocol cannot meet the requirements of real-time application for network delay.Therefore,improving the Internet routing availability has become an urgent problem.Academia and industry employ routing protection schemes to quickly respond to network failures and improve Internet routing availability.The existing routing protection schemes do not consider the importance of nodes in the network.However,the importance of different nodes in the network is not the same in real networks.To solve this problem,an intra-domain routing protection algorithm based on critical nodes(RPBCN)was proposed.Firstly,an Internet routing availability model is built,which can quantitatively measure the Internet routing availability.Then,a node criticality model is established,which can quantitatively measure the importance of nodes in the network.At last,RPBCN is proposed based on the Internet routing availability model and node criticality model.The experiment results show that RPBCN greatly improves the Internet routing availability while possessing low computation overhead,which provides an efficient solution for the ISP to solve the Internet route availability problem.
引文
[1]Internet Users[OL].http://www.internetworldstats.com/top20.htm.
[2]GENG H J,SHI X G,YIN X,et al.Algebra and algorithms for multipath QoS routing in link state networks[J].Journal of Communications and Networks,2017,19(2):189-200.
[3]Reaching 50 million users[OL].http://visual.ly/reaching-50-million-users.
[4]第38次中国互联网络发展状况统计报告[R].中国互联网信息中心,2016.
[5]CLARK D.The design philosophy of the DARPA Internet protocols[J].ACM SIGCOMM Computer Communication Review,1988,18(4):106-114.
[6]GOODE B.Voice over internet protocol(voip)[J].Proceedings of the IEEE,2002,90(9):1495-1517.
[7]DREW P,GALLON C.Next-generation VoIP network architecture[R].Multiservice Switching Forum,2003.
[8]KRIST P.Scalable and Efficient Multipath Routing:Complexity and Algorithms[C]∥2015IEEE 23rd International Conference on Network Protocols(ICNP).IEEE,2015:376-385.
[9]ZHENG J,XU H,ZHU X,et al.We’ve Got You Covered:Failure Recovery with Backup Tunnels in Traffic Engineering[C]∥IEEE 24rd International Conference on Network Protocols(ICNP).IEEE,2016:1-10.
[10]YANG B,LIU J,SHENKER S,et al.Keep forwarding:Towards k-link failure resilient routing[C]∥IEEE Conference on Computer Communications.IEEE INFOCOM,2014:1617-1625.
[11]PAL S,GADDE R,LATCHMAN H A.On the reliability of voice over ip(voip)telephony[C]∥The SPRING 9th International Conference on Computing,Communications and Control Technologies.Orlando,Florida,USA,2011.
[12]YALLOUZ J,ROTTENSTREICH O,BABARCZI P,et al.Optimal Link-Disjoint Node-“Somewhat Disjoint”Paths[C]∥2016IEEE 24rd International Conference on Network Protocols(ICNP).IEEE,2016:1-10.
[13]MOY J.rfc 2328:Ospf version 2[OL].http://tools.ietf.org/html/rfc2328.
[14]ATLAS A K,ZININ A.Basic Specification for IP Fast Reroute:Loop-Free Alternates[OL].http://www.heise.de/netze/rfc/rfcs/rfcs5286.shtml.
[15]SHAND M.Ip fast reroute using not-via addresses[J].Cisco Systems Conference Dapricot,2003,137(654):29-42.
[16]SRIDHARAN A,GUERIN R,DIOT C.Achieving near-optimal traffic engineering solutions for current ospf/is-is networks[J].IEEE/ACM Transactions on Networking(TON),2005,13(2):234-247.
[17]FRANCOIS P,BONAVENTURE O.An evaluation of ip-based fast reroute techniques[C]∥ACM Conference on Emerging Network Experiment and Technology.ACM,2005:244-245.
[18]KWONG K W,GAO L,GUERIN R,et al.On the feasibility and efficacy of protection routing in IP networks[C]∥Proc.IEEE INFOCOM.2010:1235-1243.
[19]VO H Q,LYSNE O,KVALBEIN A.Routing with joker links for maximized robustness[C]∥IFIP Networking Conference.2013:1-9.
[20]CHO S,ELHOURNAI T,RAMASUBRAMANIAN S.Independent directed acyclic graphs for resilient multipath routing[J].IEEE/ACM Trans.on Networking,2012,20(1):153-162.
[21]Advanced networking for research and education[OL].https://www.internet2.edu/products-services/advanced-networking.
[22]SPRING N,MAHAJAN R,WETHERALL D,et al.Measuring isp topologies with rocketfuel[J].IEEE/ACM Transactions on Networking,2004,12(1):2-16.
1)http://www.cs.bu.edu/brite