routing by preference

[Martha Steenstrup <[e-mail]>]

Hello Yuko,

After viewing your video, I have the following comments about your
"routing by preference" problem and some suggestions for handling it
within the context of IDPR.

It seems as if routing by preference, i.e., specifying the set of
"unfavorable" domains and taking the "shortest" path through such
domains can be problematic.  Generating the shortest (according to
some metric such as distance, delay, monetary cost) path between
source and destination may not be consistent with routing by
preference.  That is, if routing by preference is strictly enforced,
and one always selects the shortest routes across unfavorable domains,
one may end up with a path which is not the shortest path between
source and destination.  The following example illustrates this.

Suppose we want to generate a route between Hx in domain X and Hy in
domain Y.  Suppose that S and T are two intervening domains and S is
unfavorable from the perspective of both Hx and Hy.  Suppose that S
has two virtual gateways, T1 and T2, to T and one virtual gateway, X1,
to X.  Furthermore, suppose that the distance from X1 to T1 is 25, and
the distance from X1 to T2 is 50.  Moreover, suppose that the distance
from T1 to the virtual gateway Y1 connecting T to Y is 100, and the
distance from T2 to the virtual gateway Y1 is 40.  With strict routing
by preference one would choose the route through X1, T1, and Y1, with
distance 125.  However, the shortest route is through X1, T2, and Y1
with distance 90.

I think you have to be careful when deciding when you actually want to
route by preference.  With strict routing by preference, the local
optimizations in unfavorable domains do not necessarily lead to
end-to-end optimization between source and destination domains.
Hence, you must decide when the shortest end-to-end path takes
precedence over selecting the shortest routes through unfavorable
domains.  Moreover, if the source requires that the qualities of
service and the monetary cost of service for a route be kept within
specified constraints, then satisfaction of these constraints should
take precedence over selecting the shortest routes through unfavorable
domains.

Here are some suggestions for using IDPR to do routing by preference.

IDPR version 1 supports source policies and thus source "preferences".
These source policies specify, for a route between a set of source
hosts and destination hosts:
- the qualities of service desired,
- the monetary cost of service desired, and
- the domains to exclude, favor, or avoid if possible.
One can treat "avoid if possible" as synonymous with "unfavorable".
Currently, source policies are configurable and cannot be dynamically
updated by hosts themselves.

You could include as part of the source policies, the preferences of
the destinations listed in the source policy.  For example, if
destination Hz considers that domain W should be avoided if possible,
this information will be incorporated into the source policies
involving destination Hz.  Hence, these sorts of destination
preferences could be accommodated without modifying IDPR.

A route server generating a route on behalf of a source host accounts
for the source policies when generating and selecting a route.  Each
route server executes its own route generation procedure.  Note that
IDPR provides as part of the domain transit policies the qualities and
monetary costs of service for traversing a domain between pairs of
virtual gateways.  Hence, when routing by preference, a route server
may select routes across a domain according to any metrics available
in domain transit policies.

For strict routing by preference, your implementation of the route
generation procedure should exhibit the following behavior.  The route
server should try to select the route that minimizes the "cost"
attributed to traversing unfavorable domains.  However, this
minimization should be subject to the service constraints specified in
the source policy.  That is, the route selected should obey these
service constraints.

You also mentioned the ability to factor in the "cost" in travelling
from source or destination hosts to virtual gateways in the same
domains in order to choose a favored exit virtual gateway from the
source domain or entry virtual gateway at the destination domain.

Currently, IDPR does not handle this sort of information.  Hosts have
no information about IDPR, and virtual gateways have no information
about which hosts in their domain favor them.  Moreover, path setup
messages contain no information about source and destination hosts,
only source and destination domains.

IDPR currently supports multiple source and destination host flows
over a single path.  Hence, a favored entry or exit gateway for one
host may not be the same for all hosts using the path.  So the notion
of favorite gateway entry or exit virtual gateway does not always make
sense.

Nevertheless, for a single source host you could do the following.  At
the source domain, if a host were configured with information about
its favorite exit virtual gateway, it could loose source route all of
its inter-domain traffic to this favorite virtual gateway.  The
virtual gateway in trun would select an IDPR policy route to the
destination.  However, this implies that the host also knows which of
its traffic is intra-domain and which is inter-domain.  Perhaps the
first-hop router for the host could make this determination and could
force loose source routing to the preferred virtual gateway, on behalf
of the host.

The favorite entry virtual gateway at the destination is much more
difficult to handle.  IDPR path setup messages would have to carry
information about destination hosts, and entry virtual gateways would
have to know which hosts in the domain favored which virtual gateways.

When a path agent in the destination domain received a path setup
message, that path agent (a member of a virtual gateway) could return
in its path accept message information about preferred virtual
gateways for the given destination hosts, if the given virtual gateway
were not the preferred entry virtual gateway.  (However, there may not
be a single preferred virtual gateway if there are many destination
hosts for the path.)

The path agent in the source domain, upon receiving a path accept
message with suggested alternate virtual gateway entry points could
request a route server to try to generate a feasible (i.e., constraint
satisfying) route that includes one of the favored entry virtual
gateways at the destination.  If successful, the source path agent
would tear down the original path and set up the new path.  If
unsuccessful, the source path agent would use the original path.

This solution requires some changes to the IDPR path control protocol.

m