Re: Addr: Local Preference Computation

[Curtis Villamizar <[e-mail]>]

In message <19960823.012218.RWOUNDY@RHQVM21>, [e-mail] writes:
> Folks,
> 
> Well, here it is; your comments are solicited...
> 
> -- Richard Woundy, IBM


Rich,

Lets treat this and the BGP4 draft together.

wrt BGP4 - we still need wording to clearly define what to do when
comparing MEDs from different AS.  One vendor just compares MED
regardless of AS.  This is loop free in a single vendor network.  You
have proposed that MEDs be compared among the same AS first, then the
best from each AS compared, ignoring MED.  That would be loop free in
a single vendor network.  The two algorithms in the same network, as
would occur in a multivendor network, would form loops.  Yakov, Tony -
please fix.  I personally don't care which way you fix it, but I know
a router vendor who would rather compares MED regardless of AS because
it is easier to do (rough translation - easy for me to say since I
don't have to write the code).

This does eliminate the need to mention aspath-length in BGP4.  I
still think BGP4 needs a clear statement that any other criteria in
the route selection is non-conformant to BGP4.

> 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.

Paul should be shot.  After Vadim.  ;-)

> 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.

Vendors can do this part differently.  Maybe you should call this an
example implementation.  For example, I would prefer an ASset be
counted as one regardless of how many AS are in the set.  This will
not penalize people for aggregating carefully rather than just tossing
the ASpath.

Your example amounts to fixing Ciscos implementation to interoperate
with others with minimal change.

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

Plus configured constant.

> 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 an ISP can hear this from two different AS and wants to
administratively prefer one set of announcements over the other adding
a constant of 8192 would do the trick.  

Imagine I want to support up to 10 administratively configured
preference values.  If I want to configure MCI backup for a BBN
customer, I'd configure:

  BBN:
  ASPathLengthFactor = 3
  OriginCodeFactor = 1
  LocalPrefMin = 101
  LocalPrefOffset = 8192 * (11-1)

  MCI:
  ASPathLengthFactor = 3
  OriginCodeFactor = 1
  LocalPrefMin = 101
  LocalPrefOffset = 8192 * (11-2)

I might do this for an entire AS-macro (and in fact I do, setting
policy for each prefix the AS macro expands to).  Now suppose in
addition to this AS-macro one of the AS has a connection to some other
provider and now falls into another AS-macro.  We'd have another set
of:

  OtherGuys:
  ASPathLengthFactor = 3
  OriginCodeFactor = 1
  LocalPrefMin = 101
  LocalPrefOffset = 8192 * (11-1)

(btw- If they tell us about this we can set policy to give them
whatever preference order they want, but this sort of thing does
happen).

There is now a tie in the LocalPrefOffset for BBN and OtherGuys.  At
this point the other criteria takes over.

> 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.

This is interesting.  How many UserFunctions do you think your router
vendor should provide (0, 1, infinity?).  Is zero a valid choice?
Mapping attributes into UserFunctions could get tricky and would sure
make for a fun time coding dynamic reconfig (and a lot of CPU running
it).  Still its a good idea.

I can see wanting to consider a UserFunction based on BGP community
and a separate UserFunctions based on perhaps border AS, possibly
another on something else like protocol-source (EBGP, IGP, direct).
Or maybe DPA (PMED, the Bates/Enke attribute, whatever it is).  This
would imply that infinity (or a high integer) would be the best choice
for number of UserFunctions.

In gated the config syntax reads like:

  import proto bgp as xxx {
	prefix masklen len preference value ;
		-or-
	as-path path origin type preference value ;
  };

In Bays config this is (functionally):

  import {
	proto bgp;
	from-as xxx;
	local-pref value;
	prefix-list {
		prefix mask the-mask;
		...
	};
		-and-
	as-path path;
		-and-
	origin type;
  };

There is an implied AND in statements within a policy.  The advantage
is that currently local-pref is set for an entire block of addresses.
If this becomes a calculation,then there is a need for policy
statement that don't imply acceptance, but rather set a variable.  For
example:

  set-value {
	set-user-function N lisp-sexp ;
	...  whole mess of existing policy crtieria
  };

  import {
	action accept;
	...  whole mess of existing policy crtieria
  };

btw- the lisp-sexp is only half joking.  You need an expression syntax
that pulls in certain variables.  For example, you'd need AspathLength
if you want to support the example you gave setting a variable to
k*AspathLength for K different sets of border-as or origin-as or
as-path patterns or whatever.

An incoming prefix may then match any number of policy statements
(preferably a small number) and each would contribute variables that
were used when a statement that actually accepts the route is hit (or
not used if a statement is hit that rejects the route).

(btw- this is not Bay's syntax, it is closer to gated syntax and Bay
semantics).

I think this would be done somehow by modifying route-map syntax and
semantics in IOS, but I'll let Cisco worry about that.  (Or worry
together off list if they want).

> Future Work (unordered)
> -----------------------
> 
> - working group consensus
> - Cisco and gated implementations

I can't speak for Bay, but IMO they'd be interested too.

> - sample configs on real systems
> - ISP trials

What you are really asking for is standardization of config knobs.  I
don't think that's a good idea unless you are sure you have the
ultimate solution to all config problems.

This draft is really just pointing out that there can be creative
ways to set local-pref that can be quite useful and don't negatively
impact loop free interoperability the way introducing new criteria
to the route selection does.

I think this should go out as an informational RFC and provide
examples.  Its OK to make some strong recommendations (like supporting
AspathLength would be high on your list of priorities).

Curtis