2024年4月21日发(作者：刷机精灵安卓官网下载)

HLPImplementation

Version0.1

InternationalComputerScienceInstitute

1Introduction

HybridLink-StatePath-VectorProtocol,orHLP,isaninter-domainroutingprotocoldesignedasareplacementforthe

currentBorderGatewayProtocol(BGP).Usingacombinationoflink-stateandpathvectorrouting,itprovidesgreater

scalability,betterfaultisolationandbetterconvergence.

ThecoreofHLPistheinclusionoftheec

is,BGPcurrentlyconsiderseachASasanodeinageneralgraphwithoutanyspecificstructure(usingexplicitpoliciesto

constrainrouting),whereasHLPassumesthattheInternetstructureisbasicallyhierarchicalwiththeproviderautonomous

systems(ASs)beingtherootsofcustomerASs.

HLPexplillreducemisconfigurations

r,thetradeoffissomeamountofinflexi-

resolvedusingexceptionsthatareexpectedtoberareandthereforeacceptable.

ThisreportsummarizesimplementationofHLPontheXORP[1]lementationreusesmuchofthe

codeinXORP’sBGPmodule.

2Definitions

WesaythattwoASsareinthesamehierarchyifthereexistsadirectedpathbetweenthemsuchthatthepathconsistsof

finitionofhierarchyimpliesthatthere

existsatleastoneroutebetweentwoASsinahierarchythatdoesnotinclude(provider)(customer)(provider)links.

ationshipbetweenneighboringASs(peer,customer,

orprovider)determinetheoverallstructureofthenetwork,whichcanbeassimpleasshowninFigure1a,orconsistof

figure,eachnoderepresentsanAS;theneighboringASatahigher

tieristheprovider,,ASAistheproviderofASB,whichinturnis

A’attheuseoftiersinFigure1andin

subsequentfiguresonlyallowsforgraphicalrepresentationofrelationships,itisnotpresentintheactualHLPprotocol.

(a)

tier i

A

C

(b)

tier i+1

B

tier i+2

tier i+3

Figure1:(a)Simpleand(b)complexAShierarchies

HLPdividesthenetworkintohierarchiesconsistingofprovidersandtheircustomerASs,andpeeringASsindifferent

beexplainedinthenextsection,thisdivisionofthenetworkinto

1

separatecomponentsincreasesscalability,aswellasreducestheconvergencetimeforrouteupdates.

3RoutingInformationDissemination

Twotypesofroutingpacketsareusedtodisseminateroutinginformation:link-stateadvertisements(LSAs)andfragmented

path-vector(FPV)

1

.AsisthecaseinOSPF,LSAsarefloodedthroughoutahierarchy,andallowconstructionoftheentire

eusedtoroutebetweenASs;theycontainthenumbersofpeeringASsbetweenhierarchies.

LSAsthathavenotpreviouslybeenreceivedareforwardedinthefollowingmanner:

arefromcustomers,weforwardtoallneighbors,exceptthecustomersfromwhichtheyarrive.

arefromproviders,weforwardonlytoneighboringcustomers,notproviders.

Theobjectiveoftheaetodosowillimply

thatmulti-homingASsbelongingtodifferenthierarchiescancauseLSAstobedisseminatedthroughouttheentireInternet.

Therulesaboveimplementsthisrestriction,finition,ASCbelongstobothhierarchies1and

2,,rule2preventsLSAsfromAfrombeingforwardedto

therhand,LSAsinvolvingCwillbedisseminatedinbothhierarchies,whichiscorrectsinceCisamember

ofboth.

tier i

A

D

tier i+1

B

C

E

hierarchy 1hierarchy 2

Figure2:ExampleillustratingrestrictionofLSAswithinoriginatinghierarchies

esimilartopath-vectorpacketsusedinBGP,except

hatgovernforwardingofFPVsaregivenasfollows:

omprovidersaredisseminatedonlytocustomers,nottopeersorotherproviders.

ompeersareforwardedtoneighboringpeersandcustomers,butnotproviders.

4RoutingAlgorithm

Themechanismtochoosearsesthe

implementationofexceptionswhichwillbecoveredinthenextsection,aswellasthecreationofFPVsforroutesto

customerswithinthehierarchyBasically,westoreroutesfordestinationASsreachablefromeachneighboringAS,then

dlingofroutescontainedwithinFPVsisstraightforwardand

similartothatofBGP,butroutinginformationgainedfromLSAsneedstobeconvertedtothesameformasthatinFPVs.

Theconversioniselaboratedoninthenextsection.

4.1FromLSAstoRoutes

WedenotetheleastcostofreachingASAfromBbycost(B,A),aroutefromAtoBwithcostCbyroute[(A,B),C],

andweperformtheconversioninthefollowingmanner,assumingthattheoperationsaretakingplaceinASX: