An Analysis of BGP Convergence Properties.pdf

《An Analysis of BGP Convergence Properties.pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、AnAnalysisofBGPConvergencePropertiesTimothyG.GriffinGordonWilfonggriffin@research.bell-labs.com,gtwQresearch.bell-labs.comBellLaboratories,LucentTechnologies600MountainAvenue,MurrayHillNJAbstractWhilemostroutingpolicyconflictsareofamanageablenature,withBGPthereisthepossibilitythattheycould

2、leadTheBorderGatewayProtocol(BGP)isthedefactointer-theprotocoltodiverge.Thatis,suchinconsistenciescoulddomainroutingprotocolusedtoexchangereachabilityinfor-causeacollectionofASestoexchangeBGProutingmessagesmationbetweenAutonomousSystemsintheglobalInternet.indefinitelywithouteverconvergingo

3、nasetofstableroutes.BGPisapath-vectorprotocolthatallowseachAutonomousWhilepuredistance-vectorprotocolssuchasRIP[8]areguar-Systemtooverridedistance-basedmetricswithpolicy-basedanteedtoconverge,thesameisnottrueforBGP.Theproofmetricswhenchoosingbestroutes.Varadhanetal.[18]haveofconvergencefor

4、RIP-likeprotocols(seeforexample[3])re-shownthatitispossibleforagroupofAutonomousSystemsliesonthemonotonicityofthedistancemetric.SinceBGPtoindependentlydefineBGPpoliciesthattogetherleadtoallowsindividualASroutingpoliciestooverridetheshortestBGPprotocoloscillationsthatneverconvergeonastablep

5、athchoice,thisprooftechniquecannotbeextendedtoBGP.routing.OneapproachtoaddressingthisproblemisbasedIndeed,Varadhanetal.[18]haveshownthatthereareroutingonstaticanalysisofroutingpoliciestodetermineiftheyarepoliciesthatcancauseBGPtodiverge.safe.Weexploretheworst-casecomplexityforconvergence-I

6、sitpossibletoguaranteethatBGPwillnotdiverge?orientedstaticanalysisofBGProutingpolicies.WepresentWecallthistheBGPwnwergenceproblem.BGPdivergenceanabstractmodelofBGPanduseittodefineseveralglobalcouldintroducealargeamountofinstabilityintotheglobalsanityconditionsonroutingpoliciesthatarerelate

7、dtoBGProutingsystem.Severalstudies[6,12,14,131haveexaminedconvergence/divergence.Foreachconditionweshowthatthethedynamicbehaviorofinterdomainroutingandhavehigh-complexityofstaticallycheckingitiseitherNP-completeorlightedthenegativeimpactofunstableroutes.Howeve