Addr: Local Preference Computation

[[e-mail]]

Folks,

Well, here it is; your comments are solicited...

-- Richard Woundy, IBM


Incorporating Multiple Policy Criteria into the Local Preference
================================================================

Richard Woundy
IBM
[e-mail]
8/23/96


Summary
-------

Most current BGP router implementations introduce other tie-breakers,
besides the tie-breakers listed in (RFC-1771), to the BGP path selection
process. These other tie-breakers usually include shortest AS path
length and lowest origin code, and are hard-coded into the router
software. Because the existence and the ordering of such tie-breakers
are not standardized nor universally accepted, I-BGP route loops are
likely when routers from different vendors are deployed in a single BGP
autonomous system.

This memo recommends an approach in which the ISP's policies concerning
AS path length, origin code, and other factors, are folded into the
I-BGP local preference value. The BGP border router calculates the local
preference using a linear function with user-configurable weighting
factors. As an additional feature, the router operator may specify
additional policy statements that increment or decrement (not merely
set) the local preference value.

This idea was originally suggested by Paul Traina in the IDR Working
Group meeting at the Montreal IETF (June 1996), but the author accepts
responsibility for all errors in this memo.


Advantages
----------

The approach of this memo offers two primary advantages for ISPs: a
reasonable basis for multivendor I-BGP interoperability, and an ability
to configure more flexible ISP-specific routing policies.

To promote multivendor I-BGP interoperability, router vendors should be
encouraged to remove the hard-coded explicit comparisons of AS path
lengths and origin codes. Past experience has shown that different BGP
implementations have chosen different attributes, or different
comparison orderings, that conflict with other existing BGP
implementations' choices; the result is routing loops in multivendor
router environments. Multivendor I-BGP interoperability is possible if
router implementations follow the path selection steps outlined in
(RFC-1771): lowest local preference, lowest MED, lowest interior
distance, external before internal routes, and lowest BGP ID. Router
vendors can ensure reasonable path selection with minimal user
configuration by selecting reasonable default weighting factors
(described below) for the local preference calculation.

An ISP may configure alternate weighting factors in the local preference
calculation for ISP-specific policies. For example, an ISP can ignore
the origin code in BGP path selection by setting the local preference
weighting factor for origin codes to zero. An ISP may also change the
relative priority of (virtual) attribute comparisons by selecting the
appropriate weighting factors. Assuming that all routers in the
autonomous system use the same path selection algorithm (per the
previous paragraph), then even inconsistent weighting factors within an
autonomous system will not cause I-BGP routing loops.

Note that some interim router configuration options may be needed to
transition from current BGP implementations to implementations based on
this memo, since it may not be possible to update software of all BGP
routers simultaneously in some autonomous systems. However,
implementations based on this memo will interoperate with
implementations using future local preference calculation functions, so
long as all implementations use the same path selection rules.


Local Preference Calculation Variables
--------------------------------------

The local preference is a four octet non-negative integer, for which
higher values are preferred. The local preference calculation must
ensure that its output is also a non-negative integer.

Two variables in the local preference calculation are based on specific
attributes of a specific BGP route R: ASPathLength(R) and OriginCode(R)
-- in this memo these variable names are shortened to ASPathLength and
OriginCode. The ASPathLength is the number of ASes (including
duplicates) in all AS path segments in the route's AS_PATH. Because the
maximum BGP message size is 4096 octets, and AS numbers are two octets,
the maximum ASPathLength is less than 2048. The OriginCode is the same
as the ORIGIN data octet, with legal values 0, 1, and 2. Therefore,
  0 <= ASPathLength < 2048, and
  0 <= OriginCode < 3.

An ISP can control its routing policy with the user configuration
variables ASPathLengthFactor and OriginCodeFactor, which are specified
as non-negative integers. If an ISP wishes to ignore the ORIGIN
attribute in BGP path selection, it can assign an OriginCodeFactor of
zero, for example.

Since most ISPs prefer shorter AS paths and lower origin codes (if they
have any preference at all), the ASPathLengthFactor and OriginCodeFactor
are implicitly negative in the local preference calculation. To prevent
the local preference calculation from producing negative results, this
memo defines a variable CounterBalanceWeight, where
  CounterBalanceWeight = (2047 * ASPathLengthFactor)
                          + (2 * OriginCodeFactor).

Finally, an ISP may configure the LocalPrefMin variable, which can be
useful for local preference calculation transition. To prevent the local
preference calculation result from wrapping its four octet value, the
router should ensure that
  CounterBalanceWeight + LocalPrefMin < 2**32.

The local preference calculation function becomes
  LocalPreference = CounterBalanceWeight
                    - (ASPathLengthFactor * ASPathLength)
                    - (OriginCodeFactor * OriginCode)
                    + LocalPrefMin.

As an example, suppose an ISP wants to favor BGP routes with shorter AS
paths, and favor lower origin codes when routes have the same AS path
length. In addition, the ISP wants a minimum local preference value of
101, because the default local preference value for its non-upgraded
routers is 100. The ISP can configure
  ASPathLengthFactor = 3,
  OriginCodeFactor = 1, and
  LocalPrefMin = 101.
Then, CounterBalanceWeight = 6143, and 101 <= LocalPreference <= 6244.

If the ISP wanted to favor BGP routes with lower origin codes, and favor
shorter AS paths when routes have the same origin code, then the ISP can
configure
  ASPathLengthFactor = 1,
  OriginCodeFactor = 2048, and
  LocalPrefMin = 101.
Then, CounterBalanceWeight = 6143, and 101 <= LocalPreference <= 6244.


Modifications to the Local Preference Calculation
-------------------------------------------------

The routing policy of an ISP often takes into account more than just AS
path length and the origin code. An ISP may wish to account for
characteristics such as neighbor ASes, specific AS path patterns, and/or
BGP communities when evaluating routes.

This memo defines a "policy feature" to be a means of classifying routes
into a small set of equivalence classes, over which is defined a total
ordering. In English, this means that any two routes in the same
equivalence class are equivalent with respect to the policy feature, and
that all routes from one equivalence class are uniformly either "better"
or "worse" than all the routes from another equivalence class with
respect to the policy feature. Assume that there are K equivalence
classes for a given feature, where K >= 1. Each equivalence class is
assigned an integer value k, 0 <= k < K, where equivalence classes with
larger values of k are better than classes with smaller values of k.

As a concrete example, suppose an ISP wants to configure a BGP
community-based policy feature, in which community attribute values A
and B are equivalent, attribute values A and B are better than attribute
value C, and attribute value C is better than any other attribute value
(or a missing community attribute). This policy feature contains three
equivalence classes (K = 3). Routes with community attribute values A
and/or B are labelled k = 2, routes with value C are labelled k = 1, and
all other routes are labelled k = 0.

To simplify the discussion, this memo only discusses a single policy
feature at a time, instead of multiple policy features which may have
different relative priorities within the ISP's routing policy. Further,
this memo considers policy features that add to, not subtract from, the
local preference value.

The local preference calculation function, for routes from equivalence
class k, becomes
  LocalPreference = CounterBalanceWeight
                    - (ASPathLengthFactor * ASPathLength)
                    - (OriginCodeFactor * OriginCode)
                    + LocalPrefMin
                    + UserFunction(k), where UserFunction(k) is a
function with parameter k. The actual function depends on the relative
priority of the policy feature with respect to AS path length and origin
codes for the ISP policy. Note that the value of UserFunction(k) is the
same for all routes that belong to equivalence class k, for ease of
configuration. To prevent the local preference calculation result from
wrapping its four octet value, the router should ensure that
  CounterBalanceWeight + LocalPrefMin + max(UserFunction(k)) < 2**32.

First, suppose that the ISP policy (virtually) is to consider the policy
feature first before either the AS path lengths or origin codes. This
can be configured by defining
  UserFunction(k) = k * CounterBalanceWeight,
and ensuring that
  (K * CounterBalanceWeight) + LocalPrefMin < 2**32.
This example is a primary reason that this memo distinguishes between
the CounterBalanceWeight and LocalPrefMin variables.

Now suppose that the ISP policy is to consider the policy feature as a
tie-breaker after comparing AS path lengths and origin codes. This can
be configured by multiplying ASPathLengthFactor and OriginCodeFactor by
K (the number of equivalence classes), and by setting
  UserFunction(k) = k.
For example, if the ISP policy is to consider AS path length first,
then the origin code, and finally the policy feature, then it configures
  ASPathLengthFactor = 3 * K,
  OriginCodeFactor = K, and
  UserFunction(k) = k.
Again, the 2**32 upper limit on local preference must be observed.


Modifications with Non-Unique Local Preference Values
-----------------------------------------------------

The previous local preference calculation discussions assume that
different combinations of policy feature equivalence class, AS path
length, and origin code need to map to unique local preference values.
This property is required when a rigid hierarchy of comparisons is
desired -- for example, first BGP community, then AS path length, then
origin code.

However, not all ISP policies are completely hierarchical. For example,
consider an ISP policy for which routes from certain "semi-confederate"
neighbor ASes are to be treated as if their AS path length is shorter by
one AS number (this is somewhat different from using true BGP AS
Confederations, in which the AS path is not lengthened between
confederates). An ISP can configure this policy by classifying routes
from the "semi-confederate" neighbors in class k = 1, and all other
routes into class k = 0, and setting
  UserFunction(k) = k * ASPathLengthFactor.
Of course, the 2**32 upper limit on local preference must be observed.


Future Work (unordered)
-----------------------

- working group consensus
- Cisco and gated implementations
- sample configs on real systems
- ISP trials