Re: "optimal" routes and IDPR

[[e-mail]]

This is in responce to the martha:

Thanks for your comments on my earlier message. Here are my comments on your
reply.

>I don't believe that the architecture document ever stated that IDPR
>CANNOT generate "optimal" routes.  IDPR can generate any kind of
>routes that are expressible in terms of the source and transit
>policies.  The point is, the route generation and selection procedures
>within a domain can be as fancy or as basic as the administrator of
>that domain wishes.

Can be- yes. But I believe only theoretically.
Do you "really" think that optimising a route from  thousands of possible
policy templates (expressed at the finer granularity of hosts and many other
conditions) is a such a simple affair. Now let me quote from the relevant
documents/ literature, what these have to say:

1. IDPR Protocol specification Version 1: March 1992
Section 6: Page 57

Same paragraph also appears as it is in

An Architecture for IDPR - March 1992 ( section 4.2) Page

"Route Computation is perhaps the most computationally complex part of
IDPR, because of the number of domains and the number and heterogeneity of
policies that it must accommodate. If one *opts* for a global optimization
procedure that generates a set of routes for all source/destination domain
pairs and all applicable policies, one invites *COMBINATORIAL EXPLOSION*.
  
2. Design and evaluation of IDPR Protocols ( Breslau and Estrin) 
Internetworking: research and experience, Vol. 2 177-198(1991)

Page 195:

"Even with *coarse grained* policies that change slowly, route synthesis for
IDPR arhcitecture presents a *CHALLENGE*. One approach is to compute some
valid policy routes ahead of time. Alternatively, policy routes could be
computed on-demand as they are needed. Precomputation of all policy routes in
a large internet with fine-grained policies is *COMPUTATIONALLY
INTRACTABLE*."

With above explanations,  I am not sure whether protocol can perform 
following operations for me and avoid "combinatorial explosion" and 
"challenge":

a." Get me a route with minimum delay to USC in US."
b." Get me a route with maximum throughput to USC in US."
c." Get me a route with maximum bandwidth to USC in US."

.. and so on.

All such requests *do* require global optimization. I do not think that I
would be very happy to have a NEW protocol that can not even support basic
QOS requests. Now just visualise how easily such a request can be supported by
IDRP maintaining multiple QOS FIBs. 

>Remember that the route servers for a given domain are under the
>control of the adminstrator for that domain.  The domain administrator
>can choose how to implement the route generation procedures and the
>routing information database retention procedures for its own domain.

In other words, this part of architecture is undefined and not yet fully 
resolved.  Architecture is little short of asking every domain to do its own 
research in Graph Optimization to get a route to a destination. On one hand 
the document talks about it as a challenge; on the other hand it leaves it to
domain administrators. Sorry to say, it looks to me quite unconvincing
argument.

>For example, the administrator for domain X can choose to implement
>its route server so that it records all routing information for all
>domains and always optimizes its chosen route according to the quality
>of service requested for the flow (minimum delay, minimum cost, or
>maximum bandwidth).  The administrator for domain Y may implement its
>route server so that it stores only routing information from domains
>that do not charge for transit service and always selects the first
>(not necessarily the "best") route found to a given destination.
>
>The degree of complexity of route generation is entirely the choice
>of the administrator of an individual domain.

Not true either. Again without putting my own words, let us see what others
have to say: 

2. Design and evaluation of IDPR Protocols ( Breslau and Estrin) 
Internetworking: research and experience, Vol. 2 177-198(1991)

Page 195 ( third paragraph):

"Route computation complexity (in IDPR) is a function of internet size,
dynamics and the granularity of the policies expressed by transit regions.

Therefore, it not ENTIRELY the choice of the administrator of an individual
domain. His complexity is dependent upon the complexity of policies that
other transit ADs express. You can not simply sidetrack the basic reason why
it is complex. 

The above reference also goes to say:

"Given that route computation is a computatinally intensive task, it is not
*practical* to compute routes frequently. ( remember earlier paragraph talked
about intractablity of pre-computing the routes.- so neither you can compute
routes frequently, nor you can pre-compute the routes. Looks quite difficult
dilemma to me). 

Addiing more from the same reference:

"If policy terms are highly dynamic, PRs will frequently be out
of date. Therefore, PTs should change slowly. For similar reasons,
policies should not be excessively fine-grained" 

There are two difficulties with it. First, IDPR claims that it is meant for
supporting fine grained policies. But then simulataneously, it also puts the
restrictions that policies should not be fine grained. It is like saying 
that you can have something, but are not allowed to have it. In short, a 
situation like this means that the claim is meaningless beacuse it 
cannot be used. Secondly, how do you stop transit ADs from making policies
which are not fine grained?

In the last, let me once more imphasize ( Yakov has already pointed it) that 
it is not possible to choose a route that minimizes cost in heterogenous 
charging policy environment because it amounts to comparing apples 
with oranges. You can not compare the cost of an AD that charges on per 
packet basis with another AD that charges on the basis of Flow/session 
time. To compare relative cost of one over another, one must know 
absolute packet count or rael time for which communication will be valid. 
Secondly, charging policies are not so simple that they can be easily
represented in policies. Here is an example to try:

--- Taken from IPLPDN wg mail-----

( PVC is Permannent Virtual Circuit - Let us assume they are Temprarory
FLOWS in IDPR case from a Transit AD, and let us also ignore the 
actual values). 

More precisely, Nynex'proposed tariff is as follows:

        56/64 kbps access port: $67/month
        first PVC: no additional charge
        2nd - 5th  PVC: $10 each
        6th - 10th PV: $5 each
        more than that: $1 each


Thus, the monthly charge is doubled when you increase the number
of PVCs from one to twelve. These charges will be halved during 
night time (9PM to 9AM) and doubled during peak time ( 9AM to 2PM). 

------------------------------------

On one more count, I have difficulty with IDPR. IDPR assumes that transit
policies are "usaully" public. What happens if AD does not wish to advertise
its policies to all but wish to restrict this to only some ADs in the 
internet.

Cheers,

brijesh

PS: please note that I am not trying to put down IDPR as a source routing 
protocol but I am only pointing out its flaws. And I think- with these flaws,
it cannot be a popular choice of ADs if they have some simpler alternative.