ALTO WG P. Racz
Internet Draft University of Zurich
Intended status: Informational Z. Despotovic
Expires: December 2009 DOCOMO Communications
Laboratories Europe GmbH
June 29, 2009
An ALTO Service based on BGP Routing Information
draft-racz-bgp-based-alto-service-00.txt
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
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 December 29, 2009.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents in effect on the date of
publication of this document (http://trustee.ietf.org/license-info).
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document.
Racz, Despotovic Expires December 29, 2009 [Page 1]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
Abstract
Overlay applications, like Peer-to-Peer (P2P) file-sharing and video
streaming, attract a lot of users and generate a huge amount of data.
Most overlay applications do not take into account the underlying
network topology in their routing decisions and connection
establishment in general. Due to this fact and the large amount of
P2P traffic, overlay applications waste network resources, cause
problems in network management, and result in high costs for ISPs,
especially because of the expensive interconnection links between
ISPs. Therefore, the objective of the ALTO Working Group Charter
[ALTO-charter] is to design and specify an Application-Layer Traffic
Optimization (ALTO) service that will assist P2P applications in
their peer selection process in order to achieve a more efficient
usage of network resources, to reduce operational costs of ISPs, and
to increase the overlay application performance at the same time.
This draft proposes a possible ALTO service that uses BGP routing
information in order to calculate a rating value for peers providing
a certain resource (resource providers). The service is operated by
the ISP. Since BGP routing information is available in any ISP
network and the service accesses the routing information from the
local ISP network, the deployment of the service does not require
changes in the network and the ALTO server can retrieve routing
information automatically.
Table of Contents
1. Introduction...................................................3
2. BGP-Based ALTO Service.........................................3
2.1. Relevant BGP Attributes...................................4
2.1.1. Local Preference.....................................4
2.1.2. AS Path..............................................5
2.1.3. MED..................................................5
2.2. BGP Route Selection.......................................5
2.3. ALTO Rating Calculation...................................6
3. Security Considerations........................................9
4. IANA Considerations............................................9
5. References.....................................................9
5.1. Normative References......................................9
5.2. Informative References....................................9
6. Acknowledgments...............................................10
Racz, Despotovic Expires December 29, 2009 [Page 2]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
1. Introduction
Network traffic generated by Peer-to-Peer (P2P) applications
determines a large portion of the overall traffic in the Internet.
Because P2P applications have limited information about the
underlying network topology, they usually select direct P2P
connections in a suboptimal way. As a result, P2P traffic often
crosses several ISPs, causes high load and congestion on particular
network links, reduces application performance, and generates high
costs for ISPs. This problem is discussed and described in detail in
the ALTO problem statement [draft-ietf-alto-problem-statement].
A possible solution to this problem is to provide network information
(e.g., topology) to P2P applications, as proposed in the ALTO problem
statement [draft-ietf-alto-problem-statement]. By using this
information in P2P applications, it would be possible to optimize P2P
traffic, to increase application performance, and to reduce costs of
ISPs. Thus, both the P2P application and the ISP can benefit from
such an information exchange. Therefore, ISPs have an incentive to
provide such information and P2P applications have an incentive to
use such information.
In the ALTO problem statement [draft-ietf-alto-problem-statement] and
ALTO requirements [draft-ietf-alto-reqs] an ALTO service is proposed
that can provide information about the network to P2P applications.
The service is accessible through the ALTO server. This document
proposes a possible ALTO service based on Border Gateway Protocol
(BGP) [RFC4271] routing information. ALTO clients can query the
proposed service - called BGP-based ALTO service - with a list of IP
addresses and/or IP address ranges representing resource providers.
The service MUST return for each IP address and/or IP address range
in the list a preference value, called ALTO rating. The ALTO rating
is used by P2P applications in their peer selection process to choose
"better" peers. The ALTO rating of a certain IP address is calculated
based on the BGP attributes associated with the route for the given
IP address.
This document uses the terminology as defined in the ALTO problem
statement [draft-ietf-alto-problem-statement].
2. BGP-Based ALTO Service
The BGP-based ALTO service assists P2P applications in their peer
selection process by providing an ALTO rating for each potential
resource provider peer. ALTO clients can query the ALTO server with
the list of IP addresses of the peers the P2P application wants to
connect to. The ALTO server MUST return the ALTO rating for each
Racz, Despotovic Expires December 29, 2009 [Page 3]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
address in the list. The ALTO rating is used by the application to
decide to which peers to connect to. Instead of the IP addresses the
ALTO client can also use IP address ranges. The ALTO service
calculates the ALTO rating based on the BGP attributes associated
with the route for the given IP address.
The BGP routing protocol [RFC4271] is used to exchange routing
information between ISPs and it determines routes for inter-domain
routing between Autonomous Systems (AS). BGP can consider ISP
policies in the routing decision, so that ISPs can influence the
route selection according to their preferences, e.g., costs, peering
vs. transit connections.
Since BGP-based routing reflects the preferences of an ISP regarding
inter-domain connections, BGP routing information can be used to
assist peer selection in overlay applications in order to reduce
inter-domain traffic and to achieve a more efficient inter-domain
traffic pattern between ISPs. ISPs can use their BGP routing
information to provide an ALTO service for overlay applications.
Overlay applications in turn use the ALTO rating returned by the ALTO
service in their peer selection algorithm and select peers that have
a higher ALTO rating and thus improve their performance.
The BGP-based locality information can only be used to optimize
inter-domain P2P traffic. Local IP addresses are considered equal.
Optimizing intra-domain P2P traffic is out-of-scope of this draft and
it requires additional information about the network of the ISP.
2.1. Relevant BGP Attributes
To provide the ALTO rating to overlay applications, the ALTO rating
calculation algorithm uses the Local Preference, the AS Path, and the
MED BGP attributes. Based on these attributes the algorithm
calculates the ALTO rating that can be used by the overlay
application in its peer selection process.
2.1.1. Local Preference
The local preference BGP attribute is used to prefer a route to reach
a certain destination if there are multiple alternative exit routes
from the local AS to the same destination. The local preference
attribute is exchanged between routers in the local AS. Routers
select the route with the highest local preference value from all
alternative routes (cf. Section 2.2.).
Racz, Despotovic Expires December 29, 2009 [Page 4]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
2.1.2. AS Path
The AS path BGP attribute contains a sequence of AS path segments. An
AS path segment is either an AS_SEQUENCE or an AS_SET. An AS_SEQUENCE
contains an ordered list of AS numbers that a route in the UPDATE
message has traversed. An AS_SET is an unordered set of AS numbers
that a route in the UPDATE message has traversed. AS_SETs are used in
case of route aggregation and they reduce the size of the AS_PATH
information. However, by using AS_SETs the information about the
exact AS numbers a route traverses is also lost.
The length of the AS path is calculated by counting the number of AS
numbers in AS_SEQUENCEs and AS_SETs, where an AS_SET counts as 1
independent of how many ASs are in the set. The AS path length
represents the distance to the destination. Routers select the route
with shorter AS path from all alternative routes (cf. Section 2.2.).
2.1.3. MED
By using the multi-exit discriminator (MED) attribute, an AS can
suggest preferred routes to an external AS from the point of view of
the AS that is advertising the given routes. The MED attribute
enables an AS to advertise to external ASs its preference for
incoming routes into its own AS. However, an external AS might select
another route and it does not have to follow the suggestion. Routers
select the route with the lowest MED value from all alternative
routes (cf. Section 2.2.).
2.2. BGP Route Selection
BGP can receive multiple alternative routes to the same destination
from different BGP speakers. BGP will select only one route as the
best path from all alternatives. Considering only the local
preference, AS path, and MED BGP attributes, the BGP route selection
works as follows:
o Prefer the route with the largest local preference value.
o If the alternative routes have the same local preference value,
prefer the route with the shortest AS path.
o If the alternative routes have the same AS path length, prefer the
route with the lowest MED value.
Racz, Despotovic Expires December 29, 2009 [Page 5]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
2.3. ALTO Rating Calculation
The ALTO rating is calculated based on the local preference, AS path,
and MED BGP routing attributes. In inter-domain routing ISPs prefer
to select next hops in a way that considers the business relations
and agreements established with their neighbors. In general the
following relations can be distinguished: customer, provider,
peering, and backup [CR05]. The local preference attribute can be
used to prefer a route over another one to the same destination. ISPs
often use the local preference value to implement their policies that
reflect their business relations with their neighbors [CR05].
Therefore, the local preference attribute is one of the attributes
considered in the ALTO rating calculation. The calculation algorithm
assumes that ISPs assign a non-overlapping range of local preference
values to each type of business relation that allows the comparison
of local preference values of routes to different destinations. ISPs
often assign local preference values in this way [CR05]. For example,
local preference values in the range 90-99 might be used for
customers, 80-89 for peers, 70-79 for providers, and 60-69 for backup
links [CR05].
The AS path attribute represents the distance to a destination. The
ALTO rating calculation prefers peers with shorter AS path length.
This is because if P2P applications establish connections to closer
peers, the application will most probably reach a better performance
and the overall traffic will be reduced, since the traffic traverses
less ASs.
The MED attribute represents a suggestion of route preference from
neighboring ISPs. The ALTO rating calculation tries to follow this
suggestion, if the routes to the peers have the same local preference
and AS path length. Since MED values have a local scope with respect
to an inter-connection between two ISPs and MED values from different
neighboring ISPs cannot be compared in general, the ALTO rating
calculation takes MED values into account only if neighboring ISPs
set the same range of MED values in a common way. This is reflected
by the MED flag in the algorithm.
BGP selects the best route from alternative routes to the same
destination, while the ALTO rating calculation algorithm compares
routes to different destinations based on their BGP attributes.
Therefore, as discussed above, the following prerequisites need to be
fulfilled to be able to use the ALTO rating calculation algorithm:
o Non-overlapping ranges of local preference values are assigned to
routes according to the business relations an ISP has with its
neighbors.
Racz, Despotovic Expires December 29, 2009 [Page 6]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
o The MED value is only considered in the algorithm if all neighbors
of the ISP use the same range of values in a common way. Otherwise
the MED value is not taken into account in the ALTO rating
calculation.
o The Cisco-defined weight BGP attribute is either not used or is
set to the same value for all routes.
The ALTO rating calculation algorithm works as follows. It assigns
the highest ALTO rating to peers (IP addresses or ranges) that are in
the network of the ISP that provides the ALTO service to its
customers. This ensures that first local peers will be selected by
P2P applications if the applications follow the ALTO rating.
Regarding peers outside of the AS of the ISP, the ALTO rating
calculation algorithm assigns rates according to the preference of
the BGP routing protocol. This ensures that peers outside of the AS
will be selected by P2P applications according to the ISP's routing
preference.
The best route selection algorithm of the BGP protocol (cf. Section
2.2.) prefers first routes with the largest local preference value,
then routes with the shortest AS path length, and finally routes with
the lowest MED value. Therefore, the ALTO rating calculation
algorithm also prefers first peers with the largest local preference,
then peers with the shortest AS path length, and finally peers with
the lowest MED value.
The ALTO rating calculation algorithm is specified by the following
pseudo code:
for each IP range that is in the network of the ISP {
/* Assign the highest ALTO rating value to the address range */
if MED flag is set {
ALTO rating = (MAXPREF+1)*(MAXAS+1)*(MAXMED+1)
} else {
ALTO rating = (MAXPREF+1)*(MAXAS+1)
}
}
for each BGP routing entry that is selected as a best path by BGP {
Racz, Despotovic Expires December 29, 2009 [Page 7]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
/* Assign the ALTO rating value based on the BGP attributes */
if MED flag is set {
ALTO rating = local_pref*(MAXAS+1)*(MAXMED+1) +
(MAXAS-as_hops)*(MAXMED+1) +
MAXMED-med
} else {
ALTO rating = local_pref*(MAXAS+1) + MAXAS-as_hops
}
}
In the first for-loop the algorithm assign to each IP range that is
in the network of the ISP the highest ALTO rating. In the second for-
loop the algorithm takes only the BGP routing entries that have been
selected as the best path by the BGP protocol and assigns to these
BGP entries the ALTO rating based on their BGP attributes (i.e.,
local_pref, as_hops, med). The MED attribute is only taken into
account if the MED flag is set (see details above). The algorithm
uses the following three configuration parameters that the ISP has to
set:
o MAXPREF:It is equal to or greater than the largest local
preference value used by BGP speakers in the network of the ISP.
o MAXAS: It is equal to or greater than the largest AS path length
used by BGP speakers in the network of the ISP.
o MAXMED: It is equal to or greater than the largest MED value used
by BGP speakers in the network of the ISP.
The ALTO rating calculation algorithm is running on the ALTO server.
Therefore, the ALTO server has to know the local IP ranges of the ISP
and has to have access to the BGP routing table of the ISP. The local
IP ranges can be configured on the ALTO server or the ALTO server can
extract them from intra-domain routing protocols, like OSPF. The BGP
routing table can be accessed by the ALTO server for example over
SNMP from a BGP reflector in the network of the ISP. The calculation
of ALTO ratings shall be repeated periodically in order to reflect
possible changes in local IP ranges or in the BGP routing.
After calculating the ALTO ratings, the ALTO server is ready to
receive requests from ALTO clients. When the ALTO server receives a
Racz, Despotovic Expires December 29, 2009 [Page 8]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
request with a list of IP addresses, the server determines whether
the IP address is from a local IP range. If it is from a local IP
range, the server takes the highest ALTO rating. If it is from a
remote AS, the server looks up the corresponding BGP routing entry
according to longest prefix match and takes the ALTO rating
calculated for that routing entry. After the server looked up the
ALTO ratings to all IP addresses in the request, it sends back the
list together with the ALTO ratings assigned to each IP address in
the list. The ALTO client then can use the ALTO ratings to select
peers according to the recommendation of the ALTO server.
3. Security Considerations
High-level security considerations can be found in the ALTO problem
statement [draft-ietf-alto-problem-statement] and they apply for this
document as well.
4. IANA Considerations
None.
5. References
5.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC2234] Crocker, D. and Overell, P.(Editors), "Augmented BNF for
Syntax Specifications: ABNF", RFC 2234, Internet Mail
Consortium and Demon Internet Ltd., November 1997.
[RFC4271] Rekhter, Y., Li, T., Hares, S., Ed., "A Border Gateway
Protocol 4 (BGP-4)", RFC 4271, January 2006.
5.2. Informative References
[ALTO-charter] Peterson, J., Marocco, E. and V. Gurbani,
"Application-Layer Traffic Optimization (ALTO) Working
Group Charter", February 2009.
[draft-ietf-alto-reqs] Kiesel, S., Popkin, L., Previdi, S., Woundy,
R., Yang, Y R., "Application-Layer Traffic Optimization
(ALTO) Requirements", Internet-Draft, April, 2009.
Racz, Despotovic Expires December 29, 2009 [Page 9]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
[draft-ietf-alto-problem-statement] Seedorf, J., Burger, E.,
"Application-Layer Traffic Optimization (ALTO) Problem
Statement", Internet-Draft, May, 2009.
[CR05] Caesar, M., Rexford, J., "BGP routing policies in ISP
networks", IEEE Network, Volume: 19, Issue: 6, Nov.-Dec.
2005.
6. Acknowledgments
This work has been performed partially in the framework of the EU ICT
Project SmoothIT (FP7-ICT-216259). The authors would like to thank
all SmoothIT project members explicitly for providing insights and
for their discussions.
Racz, Despotovic Expires December 29, 2009 [Page 10]
Internet-Draft An ALTO Service based on June 2009
BGP Routing Information
Authors' Addresses
Peter Racz
University of Zurich
Binzmuhlestrasse 14
8050 Zurich
Switzerland
Email: racz@ifi.uzh.ch
Zoran Despotovic
DOCOMO Communications Laboratories Europe GmbH
Landsbergerstrasse 312
80687 Munich
Germany
Email: despotovic@docomolab-euro.com
Racz, Despotovic Expires December 29, 2009 [Page 11]