architecture draft - part 1

[[e-mail]]

Hello Yakov,

Thank you for carefully reading and commenting on the IDPR
architecture draft.  I indeed found your comments useful; they pointed
out those areas of the document that were not clearly spelt out.

In the following note, I have tried to address your questions on the
draft, many of which have been persuasively addressed by Noel and
Woody during the past week.  I haven't covered your questions in
order; instead they are arranged by topic.

I will send a follow-on to cover the rest of the comments.  Please let
me know if you have questions that have yet to be addressed.

Transit Policies
------- --------

Transit policies include offered qualities of service, cost of
service, and domain access restrictions.  For IDPR, we selected the
"distribute restrictions" rather than "restrict distribution" paradigm
because we thought it would make a more manageable implementation and
because we wanted sources to make their route selection based on as
much information as they could obtain.  By making transit policies
public, domains can distribute the range of service offerings and
costs to IDPR entities (route servers in particular) that act on
behalf of users to generate and select appropriate routes.

Yes, the IDPR architecture allows different domains to express
monetary cost in different units (eg., charge per byte or session
time).  And yes, this does complicate the route selection procedures.
Right now, most of the monetary cost related policies are serving as
best-guess place holders only, until we learn more about how they will
be used.

Source Policies
------ --------

In its current version, IDPR does NOT require any changes to hosts.
User service requirements are collected from various sites in the
domain by the administrator of that domain.  They may be described in
text files or telephone conversations or whatever, but there is no
network protocol for collecting this information.  The domain
administrator then configures the domain's source policies based on
the service requirements collected and distributes this information to
each policy gateway in the domain.

In the future, we may wish to add to hosts the ability to specify
their own service requirements.  For IP hosts, perhaps there will be a
set of special options for describing service requirements.  The path
agents would interpret these service requirements and pass them on to
the route servers for generation of routes with the requested
services.  However, for now, IDPR does not expect hosts to communicate
their service requirements through any protocol.

I doubt that every user would want to advertise its source policies
all over the Internet.  For security reasons, users may wish to keep
source policies private.  Moreover, as source policies can be
different for different hosts, advertising source policies at that
granularity means potentially a lot of information that must be
distributed.

Routing Generation and Selection
------- ---------- --- ---------

IDPR route servers are capable of generating routes that are optimal
with respect to a given criteria such as delay and according to the
information contained in their routing information databases (which
need not be complete).  However, we believe that in most cases users
are not as interested in optimal routes as they are in routes whose
services are within given bounds.  That is, a user would accept any
route within a given set of bounds and does not necessarily require
the best route within those bounds.

Removing the requirement for optimal routes means that a route server:
- need not maintain a complete routing information database,;
- can terminate route generation when the first satisfactory route
  has been generated;
- can select, from its route database, a route that meets the
  specified criteria (provided such a route exists), rather than
  generating an optimal route from scratch.

Link State Bias
---- ----- ----

I do not deny a preference for the link state paradigm for
policy-based routing.  But I did not intend to "sweep things under the
rug".

A policy gateway need not understand the syntax and semantics of a
transit policy in order to distribute a link state message.  Rather,
the policy gateway only needs to understand the syntax of the control
portion of the link state message (which does not include the
policies) in order to distribute a link state message.

Yes, to use a given transit policy to generate a route, a route server
needs to know its syntax and semantics.  However, a route server does
not need to understand a transit policy in order to accept a link
state message and store it in its database.

When new policy choices are added to IDPR, the capability to
understand them will not be installed simultaneously in all route
servers.  The route servers that do not understand a new transit
policy cannot use that transit policy to make a route selection.
However, they can store the transit policy in their routing
information database and expect to use it later when they have the
knowledge to interpret it.  A route server may either exclude a domain
X with unknown transit policies from its route, or it may include X in
its route.  That is up to the route server.  In either case, the
policy gateways in X ultimately decide whether to accept or reject the
path during path setup.  This flexibility allows one to gradually
phase in new transit policies without disrupting IDPR routing.

Route servers need not store all transit policies received.  They can
choose to store only those transit policies that allow access to
traffic from their domain, that their domain allows to be included in
policy routes, or that they can understand.  Hence, complete routing
information from all IDPR domains stored in each route server is not
required by the IDPR architecture.

Complexity
----------

When comparing link state routing/source specified forwarding and
distance vector routing/hop-by-hop forwarding for policy routing, I
concentrated on the differences in functionality provided rather than
storage, communication, and computational complexity.  The reason was
not that I was trying to hide the exorbitant cost of link state
routing, but rather that when comparing IDPR to BGP, I found that
there was very little difference in the amount of resources needed for
each of these approaches, under anticipated network conditions.

About a year ago, I tried a little comparison between BGP and IDPR
in terms of resources required.  I made certain assumptions such
as, informally stated as follows:
- transit policies were of the type gleaned from the RFC 1125;
- there were no source policies;
- number of domains, path length, and number of networks in a domain,
  similar to those in your BGP analysis document;
- each domain received a routing update about a given domain
  from each neighbor;
- a variety of average number of neighboring domains (less than 20);
- low rate of changes in domains (less than one change a day per domain).

With these not unreasonable assumptions, I was somewhat surprised to
find little difference between the two protocols in the storage,
communications, and computation required for distributing, processing,
and storing routing information and setting up and storing forwarding
information.  I had expected IDPR to be much more expensive.  Instead,
I found that the costs were very close and in several cases IDPR was
even less expensive than BGP.

The route generation cost comparison was more difficult.  With IDPR,
each source domain has to absorb the cost of generating routes.
However, pure transit domains need not compute any routes, because
IDPR uses source specified forwarding.  Hence, the redundant
computations associated with more traditional link state algorithms
(in which each node independently computes all routes to all
destinations using the link state database) are reduced by IDPR, in an
environment in which only some of the domains are sources of data
messages.

With BGP, each node executes a pattern matching procedure for each
update messsage received, comparing AD-paths and networks against
configured templates to determine acceptability of the route contained
in the update message.  Route generation is distributed among all
nodes along the route.  If all domains are sources of traffic to
different destinations, and if the number and size of the BGP
templates is quite small, then BGP routes will cost less to generate
than IDPR routes.  If this is not the case, then it is not easy to
make a general statement about which approach provides lower-cost
route generation.

One can always pick a set of assumptions about network conditions such
that link state/source specified routing requires more resources than
distance vector/hop-by-hop routing.  And, one can easily pick a
different set of assumptions such that the opposite is true.  Hence,
one must pose a very specific set of assumptions before attempting to
compare the complexities of the two approaches.  One cannot make
meaningful general statements.

Encapsulation
-------------

Wtih IDPR, we made a decision to encapsulate IDPR messages in headers
that were understandable by the local domain.  This allows an IDPR
message to tunnel through any type of domain - IP, CLNP, Appletalk,
you name it.

In, for example, an all-IP internetwork, one might consider
eliminating the encapsulation, carrying the IDPR data message header
in IP options, and changing the destination address at each policy
gateway to correspond to the next policy gateway.  

However, remember that the IDPR architecture allows each IDPR data
message to be protected by a digital signature and that each digital
signature covers the entirety of the IDPR data message.  For an IDPR
data message covered by a digital signature, if the digital signature
is generated by the source domain's private key, for example, no other
domain is able to sign the message.  Hence, intermediate policy
gateways along the path cannot arbitrarily adjust fields in the
message, because they cannot produce a valid signature for the
message.

Perhaps our decisions to allow IDPR data messages to be signed and to
make the signature cover the entirety of the IDPR message are
overkill.  We may want to relax these security restrictions, so that
in cases with uniform domains, we could collapse some of the
encapulating header information.  We need to weigh the alternatives
carefully.

m