[Search] [txt|pdfized|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Network Working Group                                      L. Benmohamed
INTERNET-DRAFT                                  Johns Hopkins University
draft-liang-bgp-qos-00.txt                                      C. Liang
Expires: December 21, 2006                      Johns Hopkins University
                                                                E. Naber
                                                Johns Hopkins University
                                                               A. Terzis
                                                Johns Hopkins University
                                                           June 19, 2006


   QoS Enhancements to BGP in Support of Multiple Classes of Service


Status of This Memo

   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 becomes
   aware will be disclosed, in accordance with Section 6 of 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/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

Abstract

   This document specifies the requirements posed on multi-domain
   Quality of Service (QoS) routing protocols that provide multiple
   classes of service with multi-dimensional QoS requirements.  In
   particular, it discusses enhancements to Border Gateway Protocol
   version 4 (BGPv4) that allow nodes to discover multiple paths with
   associated QoS attributes.  In addition, this documents discusses the
   details of several new algorithms, such as the dominant path
   selection algorithm (DPSA).

1. Introduction

   BGPv4 is the dominating inter-domain routing protocol in the
   Internet.  It was designed with minimal overhead traffic for
   scalability, and it offers extensive policy support for business
   needs.  Information sharing among External Border Gateway Protocol


Benmohamed, et al.       Expires December 21, 2006              [Page 1]


Internet-Draft              BGP QoS Enhancements               June 2006


   (eBGP) peers is limited.  The only information passed from an AS to
   its neighbors is the set of destination network prefixes reachable
   from itself and the sequence of ASs to each destination network
   prefix.

   Many emerging needs in commercial and military networking have
   exposed limitations of the current eBGP.  These future IP networks
   will support a very diverse mix of applications with very diverse QoS
   requirements.  In addition, some of these networks may consist of a
   diverse set of component networks (wireless and wireline, fixed and
   mobile with different degrees of mobility, long-term and short-term
   ad-hoc), and these component networks may have dynamic service
   capabilities.  Therefore, different paths between the same endpoints
   may have very different QoS characteristics, and these QoS
   characteristics may be time-variant.  Having the capability to
   specify QoS requirements in routing, session admission, packet
   scheduling, buffer management, service restoration priority, degree
   of security protection, and similar other decisions will become an
   important need in future IP networks.

   This document specifies BGPv4 enhancements that allow multi-topology
   (exposing multiple routes) and QoS-aware routing, using several QoS
   metrics of importance to different applications.  Unlike some other
   similar work, our enhancements support multiple QoS metrics and do
   not require any changes in the inter-domain routing architecture that
   BGPv4 is based upon.  Since the enhanced BGP does not limit routers
   to advertise only one route for each destination prefix, we define
   the notion of dominant paths to keep the amount of information
   transfer to the minimum needed to be scalable.  The enhanced BGP also
   incorporates mechanisms, such as Multiprotocol Label Switching
   (MPLS), and defines network-wide traffic classes to pin the route
   taken by packets with the same QoS requirements.

2. BGPv4 Enhancements

   There are five enhancements to BGPv4 that enable multi-paths and QoS-
   aware routing:

      (1) Exchanging potentially multiple paths per destination prefix.

      (2) Maintaining multiple QoS metrics for each path.

      (3) Pruning the set of known paths to a dominant set while
          maintaining optimality.

      (4) Choosing a particular path from this dominant set for the
          unique QoS requirements of a traffic class.

      (5) Enforcing the selected route.

   BGPv4 restricts each router to advertise to its neighbors only one


Benmohamed, et al.       Expires December 21, 2006              [Page 2]


Internet-Draft              BGP QoS Enhancements               June 2006


   route per destination prefix.  This information hiding behavior can
   prevent a router from learning the particular path that most
   appropriately addresses the QoS requirements for a given traffic
   class.  Enhancement (1) removes this limitation, allowing each BGP
   router to advertise a set of dominant paths.  Enhancement (2)
   associates a list of QoS metrics with each link, which are then used
   to make route decision.  Details on how path QoS metrics are embedded
   in BGP_UPDATE messages and maintained will be discussed in more
   detail in later sections.  The notion of dominant paths is
   enhancement (3), and it prevents each BGP router from advertising
   every path it knows.  Dominant paths are selected by dominant path
   selection algorithm (DPSA), which is discussed in more detail in
   later sections.  Exchanging all of these additional paths and QoS
   attributes is pointless unless the QoS-aware routing path decision is
   actually enforced.  Enhancement (5) can be implemented with various
   mechanisms, which are discussed in our previous work [1].  We have
   chosen to run MPLS on route assignment by enhancement (4) to pin the
   path for each application's data flow.  Class-assignment algorithm of
   enhancement (4) will be discussed in more detail in later sections.

   Incorporating these enhancements requires updating BGPv4 path
   selection process accordingly.

      - BGPv4 first manipulates path attributes, such as Local_Pref and
      AS_Path, so that routes from one or some neighbors are enabled.
      However, in order for QoS routing to be effective by being able to
      choose among a larger set of routes, routes from all neighbors
      should ideally be enabled.

      - In BGPv4 path selection process, each border router (BR) that
      terminates an enabled route selects itself among all enabled
      routes as an AS egress point.  Then, non-egress nodes selects one
      of these egress points.  Instead, under QoS routing, all enabled
      routes to a destination D received at a BR (from both iBGP and
      eBGP peers) undergo DPSA where a set of dominant paths is
      selected.  This set of dominant paths is maintained for routing
      and advertisement.

2.1 Maintaining Path QoS Metrics

   The BGPv4 UPDATE message includes the AS_PATH attribute, which stores
   the sequence of ASs to reach the associated destination prefixes.  In
   order to retain the structure of the BGPv4 UPDATE message, path QoS
   metrics are embedded in the AS_PATH attribute.  This extension of the
   AS_PATH attribute has been modeled after TLV (Type-Length-Value)
   model.  The TLV model provides a flexible architecture that will
   support the specific metrics that we are currently interested in, and
   it also provides support for any additional metrics in the future.
   Figure 1 and 2 show the old format and the new format of AS-PATH
   attribute:



Benmohamed, et al.       Expires December 21, 2006              [Page 3]


Internet-Draft              BGP QoS Enhancements               June 2006


                        -----------------------
                        | Length of | Path to |
                        | Attribute | Prefix  |
                        -----------------------
                Figure 1: BGPv4 AS_PATH attribute format

   ------------------------------------------------------------------
   | Length of | # Metrics |    Type    |   Length   |    Value   |
   | Attribute |    = N    | (Metric 1) | (Metric 1) | (Metric 1) |  ...
   ------------------------------------------------------------------

             ----------------------------------------------------
               |    Type    |   Length   |    Value   | Path to |
          ...  | (Metric N) | (Metric N) | (Metric N) | Prefix  |
             ----------------------------------------------------
              Figure 2: Extended AS_PATH attribute format

   Each path QoS metric value is the accumulation of the QoS metric
   value of all the links that the path consists of.  Therefore,
   maintaining path QoS metrics is a combined effort of each node along
   that path.  The general accumulation rules are:

      - When advertising a path to another AS, the advertising node
      combines its intra-AS metric values with the metric values
      accumulated for the path thus far.

      - When receiving a path from another AS, the receiving node
      combines the metric values on the link that connects the receiving
      node to the advertising node with the metric values accumulated
      for the path thus far.

2.2 Dominant Path Select Algorithm (DPSA)

   For QoS requirements with a single metric, such as bandwidth, it is
   sufficient to know a path with the largest available bandwidth.  If
   the best path is not feasible, then no other paths are.  However, for
   QoS requirements with multiple metrics, such as bandwidth and delay,
   there might not be a single best path.  The notion of dominant path
   is defined as a path where there is no other path with all QoS
   metrics being better.  If a path P dominates a set S of paths, then
   paths in S do not need to be advertised as path P is the only one
   needed to make QoS routing decisions.  Indeed, if a connection
   request cannot be supported by P then no path in S can satisfy the
   request.

   To illustrate DPSA, we will look at a small network topology with six
   paths from the source to the destination node.  In addition, this
   network topology has two QoS metrics of interest: delay and
   bandwidth.

                   ^


Benmohamed, et al.       Expires December 21, 2006              [Page 4]


Internet-Draft              BGP QoS Enhancements               June 2006


                   |
                 BANDWIDTH
                   |
                   |            P3  P4
                   |        P2          P5
                   |    P1                  P6
                   |
                  -+---------------------------DELAY->
                   |
     Figure 3: Delay and bandwidth QoS characteristics of the six
                                 paths

   Figure 3 shows the delay and bandwidth QoS characteristics of the six
   paths in the network.  DPSA selects P1, P2, and P3 to be the dominant
   paths because they are not covered by any other paths.  P4, P5, and
   P6 are covered by P3 because P3 is equal or better in all QoS
   metrics.

   For each destination prefix in the Loc-Routing Information Base (Loc-
   RIB), we have to select a set of dominant paths for advertisement.
   Therefore, DPSA should be logically placed between Loc-RIB and BGPv4
   Output Policy Engine.  If there are more than one potentially
   dominant paths with all QoS metrics being equal, then the tie-
   breaking strategies described below narrows down to only one path.
   The first strategy is to prefer paths with the lowest AS hop counts,
   and the second strategy is to prefer paths with the lowest next-hop
   IP address.

2.3 Route Assignment For Each Traffic Class

   There are various mechanisms that can be used to pin the selected
   path for a particular application's data flow.  We have chosen to
   run MPLS on the notion of traffic classes.  A set of network-wide
   traffic classes are pre-defined on every node, and the task of class-
   assignment algorithm is to assign at most dominant one path to each
   traffic class under every destination prefix.  For each traffic
   class, the algorithm starts by selecting a set of paths that can
   satisfy the QoS requirements of the traffic class.  Then, from this
   set of paths, the best path is assigned to the traffic class.  For
   QoS requirements with bandwidth and delay, the best path can be
   defined as the path with the largest Euclidean distance from the
   traffic class requirement.

   For each destination prefix in the Loc-Routing Information Base (Loc-
   RIB), we have to assign at most one dominant path to each traffic
   class.  Therefore, class-assignment assignment should be logically
   placed between Loc-RIB and Forwarding Information Base (FIB).  If
   there are more than one suitable paths for a traffic class, then the
   tie-breaking strategies described below narrows down to only one
   path.  The first strategy is to prefer paths with the lowest AS hop
   counts, and the second strategy is to prefer paths with the lowest


Benmohamed, et al.       Expires December 21, 2006              [Page 5]


Internet-Draft              BGP QoS Enhancements               June 2006


   next-hop IP address.

2.4 Forwarding Decision

   Forwarding decision at data plane depends on two information: packet
   destination address and packet traffic class.  Both IPv4 Type of
   Service (TOS) field and IPv6 Priority field can store the identifier
   of the traffic class the packet belongs to.  Longest-prefix-matching
   algorithm is first performed on the packet destination address to
   find the most specific destination address prefix in FIB.  Since
   there might be multiple routes under a given address prefix in FIB,
   packet traffic class identifier is then used to match the route with
   the same traffic class identifier.  The packet is dropped either if
   longest-prefix-matching algorithm does not return a destination
   address prefix from FIB, or if there is no route matching packet
   traffic class.

3. Relevant Results

   Simulation results on the dynamic behavior and the scalability of
   enhanced BGP are discussed in our previous work [2].  In addition, a
   proof of DPSA convergence under the assumption of synchronous
   operation is also presented in our previous work [2].

4. Security Considerations

   This document does not directly concern security.  It is believed
   that this extension inherits security issues in BGPv4.

5. IANA Considerations

   This document has no actions for IANA.

6. Informative References

   [1] L. Benmohamed, B. Doshi, T. DeSimone, R. Cole, "Inter-Domain
   Routing with Multi-Dimensional QoS Requirements", IEEE Milcom 2005

   [2] L. Benmohamed, C. Liang, E. Naber, A. Terzis, "QoS Enhancements
   to BGP in Support of Multiple Classes of Service", June 2006

7. Authors' Addresses

   Lotfi Benmohamed
   Johns Hopkins University - Applied Physics Laboratory
   11100 Johns Hopkins Road
   Laurel MD, 20723
   US

   EMail: lotfi.benmohamed@jhuapl.edu



Benmohamed, et al.       Expires December 21, 2006              [Page 6]


Internet-Draft              BGP QoS Enhancements               June 2006



   Chieh-Jan Mike Liang
   Johns Hopkins University - Computer Science Department
   3400 North Charles Street, 224 NEB
   Baltimore MD, 21218
   US

   EMail: cliang4@cs.jhu.edu


   Eric Naber
   Johns Hopkins University - Applied Physics Laboratory
   11100 Johns Hopkins Road
   Laurel MD, 20723
   US

   EMail: eric.naber@jhuapl.edu


   Andreas Terzis
   Johns Hopkins University - Computer Science Department
   3400 North Charles Street, 224 NEB
   Baltimore MD, 21218
   US

   Phone: +1 410 516 5847
   EMail: terzis@cs.jhu.edu

Copyright Notice

   Copyright (C) The Internet Society (2006).

   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.

   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.










Benmohamed, et al.       Expires December 21, 2006              [Page 7]