Network Working Group C. Pelsser
S. Uhlig
O. Bonaventure
Internet-Draft UCL (Belgium)
Expires: April 2005 October 2004
Limitations induced by BGP on the computation of interdomain LSPs
draft-pelsser-bgp-pce-00.txt
Status of this Memo
This document is an Internet-Draft and is subject to all provisions
of section 3 of RFC 3667. By submitting this Internet-Draft, each
author represents that any applicable patent or other IPR claims of
which he or she is aware have been or will be disclosed, and any of
which he or she become aware will be disclosed, in accordance with
RFC 3668.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as
Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This Internet-Draft will expire on April 1, 2005.
Copyright Notice
Copyright (C) The Internet Society (2004).
Abstract
Path Computation Elements have been proposed to aid the establishment
of interdomain Label Switched Paths. We propose to colocate the PCE
with a route reflector and show that the performance of such a PCE
depends on the quality of the interdomain routes that it collects.
Pelsser Expires April 2005 [Page 1]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
1. Introduction
Service Providers have been using MPLS for various purposes inside
their networks. Recently, several service providers have expressed
their requirements[INTER-AS] to also use MPLS accross interdomain
boundaries, notably for QoS, traffic engineering and fast restoration
purposes. One of the proposed solutions to aid the establishment of
interdomain LSPs is the utilization of a Path Computation Element
(PCE).
The current PCE architecture document [PCE] mentions several
solutions for the synchronization of the PCE TED. A first solution is
that the PCE will participate in the IGP of the different ASes
involved in the interdomain path. This solution is applicable in
limited environments, for example when two domains belong to the same
company, but we do not expect that it will become widely used,
notably due to the confidentiality requirements expressed in [INTER-
AS]. The second solution proposed in [PCE] is to use an out-of-band
TED synchronization. In this case, each PCE will regularly obtain
topological information from the neighboring domains by using a
mechanism or a protocol that is still to be defined.
When considering the utilization of a PCE to aid in the establishment
of interdomain LSPs, the PCE should collect interdomain in addition
to intradomain routes. A possible solution would be to co-locate a
PCE with a BGP route reflector [VERSATILERR] as a route reflector
naturally collects those interdomain routes.
PE1 ---- R1 ----- R2 ======= R5 ----- R6 --- PE2
| | | |
| | | |
R3 ----- R4 ======= R7 ----- R8 --- PE3
<------- AS1 -------> <------- AS2 ------- >
Figure 1: Simple interdomain topology
However, simply using a route reflector to collect the interdomain
routes may not be sufficient to allow the PCE to have enough
visibility on the interdomain routes to establish primary and backup
interdomain LSPs. For example, let us consider the simple interdomain
topology shown in figure 1 and assume that router PE1 needs to
establish interdomain LSPs towards PE2 and PE3 and that there are two
peering links between AS1 and AS2 (R2-R5 and R4-R7).
Pelsser Expires April 2005 [Page 2]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
Let us first consider the case of a full iBGP mesh inside AS1 and
that the IP addresses of PE2 and PE3 belong to the same prefix
advertised by AS2.
A common configuration in the case of backup links is to use a low
local-pref value for the routes learned via the backup link and a
normal local-pref for the routes learned via the other link. If link
R2-R5 is the primary link and link R4-R7 a backup link, R2 will
advertise the routes learned from R5 in the iBGP mesh with a high
local-pref attribute. For each destination reachable via the R4-R7
link, R4 will receive a better route via iBGP from R2. Thus, R4 will
not advertise any route learned from AS2 in the iBGP mesh and PE1
will not be aware that the R4-R7 link can be used to establish a
primary or a backup interdomain LSP.
If the same local-pref values are used for both links, a similar
problem would occur if AS2 attaches different MED values to the
interdomain routes advertised by R5 and R7. In this case, only one
route will be advertised in the iBGP full-mesh.
If PE1 needs to send VoIP packets towards PE2 and PE3, it would be
interesting to allow PE1 to use the shortest path towards PE2 and
PE3. In a pure IP network, operators might want to use the MED
attribute for this purpose. Assume that AS2 advertises two /32
addresses for PE2 and PE3. R5 advertises PE2/32 with a MED of 2 and
PE3/32 with a MED of 3 and similarly for R7. The result of this
utilization of the MED attribute will be that PE1 will only receive a
single route to reach PE2/32 (via R5) and a single route to reach
PE3/32 (via R7). With those routes, it will be difficult for PE1 to
establish both a primary and a link-disjoint backup LSP.
In large ASes, the iBGP full mesh is replaced by Confederations
[CONF] or Route Reflectors [RR]. Let us consider that R1, R2, R3 and
R4 are Route Reflectors and that PE1 is a client of R1. In this case,
R1 will only advertise its own best route towards each destination to
PE1. Thus, PE1 will never learn two distinct routes towards a
destination. If PE1 uses a PCE, for example implemented on R3, to
compute the interdomain paths, then the PCE can benefit from all the
routes that it learned via iBGP. If local-pref and MED are not used,
then the PCE will learn two routes towards PE2 and PE3. Thus, the PCE
will be able to compute disjoint paths to reach PE2 and PE3 on behalf
of PE1. Unfortunately, this solution is not sufficient if different
local-pref values are used for the peering links with AS2. In this
case, the PCE will suffer from the same problem of limited visibility
as discussed above. The same applies if the MED attribute is used.
2. Interdomain path computation techniques
Pelsser Expires April 2005 [Page 3]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
For the purpose of illustrating the issues in interdomain constrained
LSPs computation, we consider two alternative techniques. The first
technique, CSPF, relies on the availability of the complete topology
at a PCE in the network. This technique is only applicable when the
administrators running the different ASes are willing to share
topology information. It is an ideal situation that may not occur in
practice except eventually between 2 ASes that belong to the same
company. We use this technique as a benchmark. It consists of a
centralized approach where the PCE possessing the intradomain
topology of all the ASes is responsible for the computation of
interdomain paths. The second approach is applicable in a more
general framework. It is a decentralized technique where each node on
the path of the LSP completes the path computation toward the
destination based on local routing information. We call this
technique the Distributed Path Computation (DPC) technique. This
technique is applicable for the establishment of LSPs crossing any
number of ASes.
The LSPs considered in this paper are subject to end-to-end delay
guarantees as well as link and node disjointness constraints.
In the centralized path computation technique, a Path Computation
Element (PCE) [PCE] centralizes the topology information of both ASes
and uses this information to compute the path of the inter-AS LSPs.
The PCE collects the link state packets advertised by the IGP in both
ASes and thus possesses the complete topology of the two ASes with
the TE information, if either IS-IS TE or OSPF-TE is used. For the
purpose of this draft we assume that the delays of the links are
distributed by the IGP. Based on this information, the PCE runs a
CSPF algorithm. It runs Dijkstra algorithm with costs set to the
delay of the links and sends the computed path to the source of the
LSP, if the path respects the delay constraint. For the disjoint
path computation, the PCE first prunes from the topology the links
and nodes that are on the primary path. Then, it runs the computation
as for the primary path.
The Distributed Path Computation technique relies on the routing
information distributed by BGP. Each router uses a single best BGP
route to forward IP packets toward each distant destination prefix.
These routes are stored in its Local Routing Information Base (Loc-
RIB). However, a router may receive one route toward each prefix from
each of its peers. If they pass the import filters, these routes are
stored in its Adj-RIB-Ins. We use these routes to compute our
constrained paths. As a consequence, the computed paths respect the
BGP policies of the ASes that are enforced by the import and export
filters inside the BGP routers.
Pelsser Expires April 2005 [Page 4]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
In the DPC technique, the ingress ASBRs (or the head-end of the LSP)
select the egress ASBR based on the routes in their local Adj-RIB-In.
Ingress ASBRs select the route with the Next-Hop (NH) that is
reachable through a path with the smallest delay and respecting the
disjointness constraints. This consists in performing a CSPF inside
the AS toward all the NHs advertised with the destination prefix,
with the delay as metric. Once the NH is selected, the LSP is
established toward this NH using RSVP-TE with an ERO containing the
computed constrained path segment. We assume that egress ASBRs know
the delays toward directly connected eBGP peers. Egress ASBRs then,
select a NH in the neighboring AS from the NHs of the routes toward
the destination of the LSP, in the local Adj-RIB-Ins. In the
destination AS, the ingress ASBR performs a CSPF toward the tail-end
of the LSP.
We note that if a node needs to complete the path computation but
does not have routes in its Adj-RIB-Ins, with NHs that can be joined
by a path segment respecting the constraints, cranckback takes place.
A RSVP Path Error message is sent back to the source. An upstream
node on the path, the previous ASBR in our case, computes an
alternative path toward the destination, based on interdomain route
advertisement toward the PE destination prefix that have not been
tried.
3. Simulation results
Our simulations were performed over the C-BGP simulator [CBGP]. We
consider interdomain topologies composed of two interconnected ASes,
the simplest case for interdomain LSPs. Each AS contains several
interconnected routers. Furthermore, the routers in each AS are
grouped in POPs as in most networks. A small POP may contain a single
router while a large POP may be composed of a few tens of routers.
The ASes are interconnected with one peering link in each city where
both ASes have a POP. To establish interdomain LSPs, we consider the
case of inter-AS VPNs where each AS may offer VPNs services toward
the POPs of the other AS. For this reason, we attach a Provider Edge
(PE) router to each POP containing more than one router. This PE
router is connected to two different routers inside the POP for
redundancy reasons. We establish a full mesh of traffic engineered
LSPs between those PE routers.
The AS topologies, with link delays and routers grouped in POPs, used
for this purpose, have been collected by the rocketfuel project
[ROCKETFUEL].
We assigned a bandwidth of 10 Gbps to each link. Moreover, each link
Pelsser Expires April 2005 [Page 5]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
connecting a PE router to other routers has a delay set to 1 ms. The
same delay of 1 ms is assigned to the inter-AS links that we added to
interconnect the ASes two by two. A router in each POP is configured
as a route reflector, all the routers inside the POP are fully meshed
from an iBGP viewpoint, for optimal intra-POP routing, and the route
reflectors themselves are fully-meshed as recommended by [RR].
----------------------------------------------------------
| Topo | ASes | Nodes | Links | LSPs |
-----------------------------------------------------------
| | ASN1 | ASN2 | | intra | inter | total | |
----------------------------------------------------------
|topo0 | 3257 | 3967 | 281 | 557 | 3 | 560 | 828 |
|topo3 | 1755 | 3257 | 291 | 575 | 14 | 589 | 920 |
|topo7 | 1239 | 6461 | 495 | 1428 | 8 | 1436 | 682 |
-----------------------------------------------------------
Table 1: Properties of the topologies
To illustrate the techniques described earlier, we compute primary
and backup paths with a 100ms delay constraint, with or without
100Mbps bandwidth reservations. That is, for each primary path, we
compute an end-to-end link and node disjoint path with the same
constraints as for the primary path, for protection purposes. The
existence of backup paths is used as an indication of the diversity
of the paths available to the centralized and the distributed
techniques.
--------------------------
| Topo | primary | backup |
|--------------------------
|topo0 | 100 | 100 |
|topo3 | 100 | 100 |
|topo7 | 100 | 100 |
-------------------------
Table 2: Percentage of interdomain LSPs established when a centralised
PCE computes the paths for the interdomain LSPs
Table 2 shows that, as expected, when a centralised PCE with complete
knowledge of the IGP routing tables of both ASes is used, then all
interdomain LSPs, both primary and link-disjoint backup LSPs can be
established. However, such a PCE design does not meet the
confidentiality requirements of [INTER-AS].
--------------------------
| Topo | primary | backup |
|--------------------------
|topo0 | 100 | 0 |
Pelsser Expires April 2005 [Page 6]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
|topo3 | 100 | 5 |
|topo7 | 100 | 3 |
-------------------------
Table 3: Percentage of interdomain LSPs established when interdomain
paths are computed by head-end LSRs
Table 3 shows that when no PCE is used, the head-end LSRs have
difficulties in finding the appropriate paths for the interdomain
LSPs. The main reason why the head-end LSR is unable to establish
the backup interdomain LSPs is that it did not receive enough
interdomain routes from its route reflector. Table 4, shows that the
utilization of a PCE co-located with a Route Reflector significantly
improves the percentage of backup LSPs that are established in the
considered topologies. The main reason why it is not possible to
establish all backup LSPs is that the Route Reflectors already
summarize interdomain routes and not all interdomain routes appear in
the iBGP mesh between the route reflectors.
--------------------------
| Topo | primary | backup |
|--------------------------
|topo0 | 100 | 64 |
|topo3 | 100 | 78 |
|topo7 | 100 | 74 |
-------------------------
Table 4: Percentage of interdomain LSPs established when interdomain
paths are computed by a PCE colocated with a Route Reflector
4. Conclusion
PCE can play an important role to aid head-end LSRs in the
establishment of interdomain LSPs. However, to meet the
confidentiality requirements of [INTER-AS], it must be noted that the
performance of the PCE will depend on the interdomain routes that it
receives. One solution to ensure that a PCE receives enough
interdomain routes would be to colocate it with a Route Reflector.
However, even in this case, the PCE may not know all the available
routes and may have difficulties to find appropriate interdomain
paths.
The development of the Path Computation Elements should take into
account the need to collect enough interdomain routes on the PCE. A
possible approach would be to allow border routers to advertise
multiple paths (their best and possibly several non-best paths) to
the PCE, at least for the interdomain routes towards taild-end LSRs.
Pelsser Expires April 2005 [Page 7]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
BGP extensions allowing to advertise multiple BGP routes have already
been proposed earlier [MULTIPLE].
5. Security Considerations
The security consideration of [PCE] are applicable for this document.
References
[INTER-AS] Zhang, R., Vasseur, JP., et. al., "MPLS Inter-AS Traffic
Engineering requirements", draft-ietf-tewg-interas-mpls-te-
req-06.txt, January 2004 (work in progress).
[VERSATILE-RR] O. Bonaventure, S. Uhlig, and B. Quoitin. The case for
more versatile BGP Route Reflectors, July 2004. Work in progress,
draft-bonaventure-bgp-route-reflectors-00.txt.
[PCE] A. Farrel, J.P. Vasseur, J. Ash, Path Computation Element (PCE)
Architecture, Internet draft, draft-ash-pce-architecture-00.txt, work
in progress, September 2004
[ROCKETFUEL] R. Mahajan, N. Spring, D. Wetherall, T. Anderson,
Inferring link weights using end-to-end measurements, 2nd Internet
Measurement Workshop (IMW2002), Marseille, France, Nov. 2002
[CBGP] B. Quoitin, C-BGP, an efficient BGP simulator,
http://cbgp.info.ucl.ac.be, March 2004
[CONF] P. Traina, Autonomous System confederations, RFC1965, June
1996
[RR] T. Bates, R. Chandra, E. Chen, BGP Route Reflection - an
alternative to full mesh iBGP, April 2000, RFC 2796
[MULTIPLE] D. Walton and D. Cook and A. Retana and J. Scudder,
Advertisement of multiple paths in BGP, Internet draft, draft-walton-
bgp-add-paths-01.txt, work in progress, Nov. 2002
[IPOM] C. Pelsser, S. Uhlig, O. Bonaventure, On the difficulty of
establishing interdomain LSPs, Proceedings IPOM'2004, Beijing China,
October 2004
Acknowledgment
This work was supported by the Waloon Government (DGTRE) within the
Pelsser Expires April 2005 [Page 8]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
TOTEM project (http://totem.info.ucl.ac.be).
Authors' Addresses
Cristel Pelsser
Steve Uhlig
Olivier Bonaventure
Dept. CSE, Universite catholique de Louvain
EMail: {name}@info.ucl.ac.be
Pelsser Expires April 2005 [Page 9]
Internet-Draft draft-pelsser-bgp-pce-00.txt October 2004
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET
ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED,
INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE
INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The Internet Society (2004). This document is subject
to the rights, licenses and restrictions contained in BCP 78, and
except as set forth therein, the authors retain all their rights.
Pelsser Expires April 2005 [Page 10]