HLP Implementation
Version0.1
International Computer Science Institute
1Introduction
Hybrid Link-State Path-Vector Protocol,or HLP,is an inter-domain routing protocol designed as a replacement for the current Border Gateway Protocol(BGP).Using a combination of link-state and path vector routing,it provides greater scalability,better fault isolation and better convergence.
The core of HLP is the inclusion of the economic and political structure of the Internet into inter-domain routing.That is,BGP currently considers each AS as a node in a general graph without any specific structure(using explicit policies to constrain routing),whereas HLP assumes that the Internet structure is basically hierarchical with the provider autonomous systems(ASs)being the roots of customer ASs.
HLP explicitly includes the relationship between2neighboring ASs in its protocol.This will reduce misconfigurations which should hopefully reduce the occurrence of routing abnormalities.However,the tradeoff is some amount of inflexi-bility in the routing algorithm.This is resolved using exceptions that ar
e expected to be rare and therefore acceptable. This report summarizes implementation of HLP on the XORP[1]software router.The implementation reuses much of the code in XORP’s BGP module.
2Definitions
We say that two ASs are in the same hierarchy if there exists a directed path between them such that the path consists of any number of provider links followed by any number of customer links.This definition of hierarchy implies that there exists at least one route between two ASs in a hierarchy that does not include(provider)(customer)(provider)links. Two ASs are neighbors if there exists a link between them.The relationship between neighboring ASs(peer,customer, or provider)determine the overall structure of the network,which can be as simple as shown in Figure1a,or consist of overlapping hierarchies as shown in Figure1b.In thefigure,each node represents an AS;the neighboring AS at a higher tier is the provider,similarly an AS at a lower tier is the customer.Thus,AS A is the provider of AS B,which in turn is A’s customer.Neighboring ASs at the same tier are also called peering ASs.Note that the use of tiers in Figure1and in
protocol.
subsequentfigures only allows for graphical representation of relationships,it is not present in the act
ual HLP
HLP divides the network into hierarchies consisting of providers and their customer ASs,and peering ASs in different hierarchies allow routing between hierarchies.As will be explained in the next section,this division of the network into
separate components increases scalability,as well as reduces the convergence time for route updates.
3Routing Information Dissemination
Two types of routing packets are used to disseminate routing information:link-state advertisements(LSAs)and fragmented path-vector(FPV)1.As is the case in OSPF,LSAs areflooded throughout a hierarchy,and allow construction of the entire hierarchy topology.FPVs are used to route between ASs;they contain the numbers of peering ASs between hierarchies. LSAs that have not previously been received are forwarded in the following manner:
1.if they are from customers,we forward to all neighbors,except the customers from which they arrive.
2.if they are from providers,we forward only to neighboring customers,not providers.
The objective of the above rules is to restrict LSAs to the hierarchies from which they originate.Failure to do so will imply that multi-homing ASs belonging to different hierarchies can cause LSAs to be disseminated throughout the entire Internet. The rules above implements this restriction,illustrated in Figure2.By definition,AS C belongs to both hierarchies1and 2,and rule1allows LSAs from AS B to be forwarded to C.At C,rule2prevents LSAs from A from being forwarded to AS D.On the other hand,LSAs involving C will be disseminated in both hierarchies,which is correct since C is a member both.
of
FPVs are used to forward routes from one hierarchy to another.They are similar to path-vector packets used in BGP,except that they do not include the AS path within hierarchies.Rules that govern forwarding of FPVs are given as follows:
1.FPVs from providers are disseminated only to customers,not to peers or other providers.
2.FPVs from peers are forwarded to neighboring peers and customers,but not providers.
4Routing Algorithm
The mechanism to choose a route to a particular destination AS is similar to that currently used in BGP.This eases the implementation of exceptions which will be covered in the next section,as well a
s the creation of FPVs for routes to customers within the hierarchy Basically,we store routes for destination ASs reachable from each neighboring AS,then decide the winning route for a particular destination.The handling of routes contained within FPVs is straightforward and similar to that of BGP,but routing information gained from LSAs needs to be converted to the same form as that in FPVs. The conversion is elaborated on in the next section.
4.1From LSAs to Routes
We denote the least cost of reaching AS A from B by cost(B,A),a route from A to B with cost C by route[(A,B),C], and we perform the conversion in the following manner,assuming that the operations are taking place in AS X:
1.for each neighbor N
2.if neighbor is a customer
3.for each downstream customer AS Apeer
4pute cost(N,A)
6.associate route[(X,A),C]with N
7.else if neighbor is a provider
8.for each of the non-customer ASs in the hierarchy
9pute cost(N,A)
11.associate route[(X,A),C]with N
The computation is broken into two parts,steps2to5,and6to9of the algorithm above.This is required because forwarding of routes from a provider to a peer should take place only if the destination AS is a customer2.
To distinguish between the origin of the routes,we tag them with the following:
PROVIDER
LSA:Route for non-customer destination AS within the same hierarchy,determined using link-state inf
ormation.
PEER
LSA:Route for customer destination AS obtained using link-state information.
An example is given in Figure3,where we focus on AS C.Table1shows the routes,costs and tags associated with each neighbor.
Neighbor Cost
(C,A)PROVIDER
A3LSA
(C,E)PROVIDER
A15LSA
(C,D)PROVIDER
D26LSA
(C,A)PROVIDER
F5LSA
Table1:Table containing routes,costs and tags for example converting LSAs to routes
4.2From FPV to Routes
Creation of routes from FPVs are much simpler,and is similar to that in BGP:
1.if FPV is from a provider P
and associate them with P
3.if FPV is from a peer Q
tag with PEER_FPV,and associate with Q
5.if FPV is from customer,treat FPV as coming from peer,
extract route(prepending this AS’number)and metric,
tag with PEER_FPV,and associate with Q
Note that step5only occurs due to an exception in the customer AS.
Figure3:Example illustrating LSA to route conversion
4.3Route Selection
The winning route to a particular destination is selected according to the following order of preferences:
1.customer route(ie.tagged with CUSTOMER
Neighbor Type
PROVIDER Customer
FPV
CUSTOMER Peer
Table2:Route types that can be forwarded to corresponding neighboring AS types
5Exceptions
HLP supports three different types of exceptions.The primary use of exceptions is to support operations that are currently used in BGP but not covered by the default HLP rules.The format in which exceptions are specified and stored is given by where
from
link specifies the neighboring link to which winning routes will be propagated,and
AS number refers to the destination AS that this particular exception is for.
In HLP,a from link is given by the tuple:
5.1Exception1
Figure4:(a)Example illustrating effect of exception1on rest of hierarchy.D announces that it does not have a customer route to C.B uses graph in(b)to compute shortest paths to all ASs in the same hierarchy except A,D and F).B uses the graph in(c)to compute the shortest path to C.
Thefirst exception,illustrated in Figure4,allows an AS(say D)to choose an alternate route to a customer(C)via a peer (E).The route choose is dependent on the customer AS,and should not affect routes to other ASs.D indicates its intention via LSAs to other ASs in the same hierarchy that it is not choosing customer routes to C.D also informs E that it no longer has a customer route to C.If,ignoring customer routes,the winning route is from E,then D forwards that FPV to its peers and customers.However,if the winning route is from another peer not specified in the exception,then the corresponding FPV will not be forwarded.
Using the same example,exception1is specified by
where is specified using the tuple
5.2Exception2
This exception specifies that winning routes from the stated provider is to be forwarded to a particular peer,which is typically not done.In Figure5,the exception
allows winning routes to AS Z from provider A to be forwarded to D.
5.3Exception3
The last exception supported is similar to exception2.Here,routes are forwarded from a peer to a provider.Currently, the provider simply accepts incoming FPVs from customers,treating them as though they are from peers.If,for security reasons,providers should reject FPVs from customers,then additional configuration will be required in the provider.
Figure5:Simple network illustrating route forwarding from provider to peer
5.4Exception Format and Matching
The type of exception does not explicitly need to be specified.Instead,the neighbor relationship associated with the links given in each exception rule can be used to determine this.The format is thus simplified,and should hopefully reduce the occurrence of misconfigurations.Table3gives the combination of links that indicate the kind of exception specified.
From To Exception Type
NULL1
Peer
Peer3
Table3:Combination of link types associated with each exception type
6Data Structures
In this section we describe the data structures used to maintain state in a HLP router.Figure6shows theflow of routing information through the system,as well as the major components of the system.
Figure6:Flow of routing information through system
We describe each component below:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。