In networks, the stable path problem （SPP） usually results in oscillations in interdomain systems and may cause systems to become unstable. With the rapid development of internet technology, the occurrence of SPPs i...In networks, the stable path problem （SPP） usually results in oscillations in interdomain systems and may cause systems to become unstable. With the rapid development of internet technology, the occurrence of SPPs in interdomain systems has quite recently become a significant focus of research. A framework for checking SPPs is presented in this paper with verification of an interdomain routing system using formal methods and the NuSMV software. Sufficient conditions and necessary conditions for determining SPP occurrence are presented with proof of the method＇s effectiveness. Linear temporal logic was used to model an interdomain routing system and its properties were analyzed. An example is included to demon- strate the method＇s reliability.展开更多
This paper presents a novel approach for checking route oscillation of border gateway protocol(BGP) quickly,by which the privacy of routing policies of autonomous system(AS) can be respected.Firstly,route update chain...This paper presents a novel approach for checking route oscillation of border gateway protocol(BGP) quickly,by which the privacy of routing policies of autonomous system(AS) can be respected.Firstly,route update chain tag(RUCT) is constructed to track the forwarding of update report,and local routing library is made to record the changing history of update report.Then route oscillation can be identified by analyzing correlative state of RUCT and local routing library.The characteristic of this approach is that an arbitrary AS can check route oscillation alone only by sharing its network ID,which greatly respects the pri-vacy of routing policies for each AS.This paper shows that both looping in RUCT and consecutive positive-negative report in local record are sufficient conditions for route oscillation.Comparative experiments demonstrate the availability and efficiency of the proposed approach.展开更多
This paper investigates the routing among autonomous systems (ASs) with quality of service (QoS) requirements. To avoid the intractability of the problem, abstract QoS capability must be informed among ASs, because th...This paper investigates the routing among autonomous systems (ASs) with quality of service (QoS) requirements. To avoid the intractability of the problem, abstract QoS capability must be informed among ASs, because the routhing which constrained QoS has been proved to be nondeterministic polynomial-time (NP) hard even inside an AS. This paper employs the modified Dijkstra algorithm to compute the maximum bottleneck bandwidth inside an AS. This approach lays a basis for the AS-level switching capability on which interdomain advertisement can be performed. Furthermore, the paper models the aggregated traffic in backbone network with fractional Brownian motion (FBM), and by integrating along the time axis in short intervals, a good estimation of the distribution of queue length in the next short intervals can be obtained. The proposed advertisement mechanism can be easily implemented with the current interdomain routing protocols. Numerical study indicates that the presented scheme is effective and feasible.展开更多
基金Supported by the Basic Research Foundation of Tsinghua National Laboratory for Information and Technology (TNList)the JSPS Foundation
文摘In networks, the stable path problem （SPP） usually results in oscillations in interdomain systems and may cause systems to become unstable. With the rapid development of internet technology, the occurrence of SPPs in interdomain systems has quite recently become a significant focus of research. A framework for checking SPPs is presented in this paper with verification of an interdomain routing system using formal methods and the NuSMV software. Sufficient conditions and necessary conditions for determining SPP occurrence are presented with proof of the method＇s effectiveness. Linear temporal logic was used to model an interdomain routing system and its properties were analyzed. An example is included to demon- strate the method＇s reliability.
基金National Basic Research Program of China (2011CB707000)Foundation for Innovative Research Groups of the National Natural Science Foundation of China (60921001)
文摘This paper presents a novel approach for checking route oscillation of border gateway protocol(BGP) quickly,by which the privacy of routing policies of autonomous system(AS) can be respected.Firstly,route update chain tag(RUCT) is constructed to track the forwarding of update report,and local routing library is made to record the changing history of update report.Then route oscillation can be identified by analyzing correlative state of RUCT and local routing library.The characteristic of this approach is that an arbitrary AS can check route oscillation alone only by sharing its network ID,which greatly respects the pri-vacy of routing policies for each AS.This paper shows that both looping in RUCT and consecutive positive-negative report in local record are sufficient conditions for route oscillation.Comparative experiments demonstrate the availability and efficiency of the proposed approach.
文摘This paper investigates the routing among autonomous systems (ASs) with quality of service (QoS) requirements. To avoid the intractability of the problem, abstract QoS capability must be informed among ASs, because the routhing which constrained QoS has been proved to be nondeterministic polynomial-time (NP) hard even inside an AS. This paper employs the modified Dijkstra algorithm to compute the maximum bottleneck bandwidth inside an AS. This approach lays a basis for the AS-level switching capability on which interdomain advertisement can be performed. Furthermore, the paper models the aggregated traffic in backbone network with fractional Brownian motion (FBM), and by integrating along the time axis in short intervals, a good estimation of the distribution of queue length in the next short intervals can be obtained. The proposed advertisement mechanism can be easily implemented with the current interdomain routing protocols. Numerical study indicates that the presented scheme is effective and feasible.
文摘BGP(border gateway protocol,边界网关协议)在设计之初并没有充分考虑安全问题,随着互联网规模的日益壮大,其安全风险也暴露得愈加明显。学术界和工业界提出了诸多方案解决域间路由面临的安全问题,目前真正得以部署的是IETF(the Internet Engineering Task Force,互联网工程任务组)推动的资源公钥基础设施(resource public key infrastructure,RPKI)。综述了RPKI的技术现状和研究进展,重点分析了RPKI存在的问题、现有的解决方案以及不足之处,介绍了RPKI功能扩展的相关研究,最后指出了未来有潜力的研究方向。
