Martha's comments

[[e-mail]]

Martha,

Thanks for your reply. I am glad that you found my comments useful.
I hope few other members of the group would agree with your assessment
of my comments and take a constructive look at them (like you did),
rather than just flaming, accusing me of all mortal sins and implicating me
in all kinds of conspiracy....

Well, on a constructive side here are my specific suggestions
that I would propose to put in the architecture document.
They mostly based on your note.



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

 It would be quite useful to put the above in the architecture document.
 I would also suggest to augment it by the following text:

  "On a negative side by choosing "distribute restrictions"
     rather than "restrict distribution" paradigm IDPR forces
     domains to participate in processing and distribution of
     information that may be of no use to them; thus placing
     an unjustifiable burden on their resources."
>
>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.

 I think that "complicate the route selection procedure" is
 gross understatement. In fact, in certain cases such computation
 is just impossible, regardless of complexity. For instance,
 unless the route computation procedure knows A PRIORI the exact properties
 of the traffic you intended to send in terms of how many bytes,
 how many packets, and the duration of a session, there is
 no way, regardless of complexity, to compute an optimal cost route.
 So, to begin with, allowing different domains to express cost
 in different units in conjuction with promise to compute minimum
  cost routes assumes that the route selection knows
 IN ADVANCE numbers of bytes, number of packets (and packet sizes as well),
 and the duration of a session;  otherwise, an optimal cost route
 can not be compute, regardless of the incurred complexity.

 Now let's put aside the feasibility of having all this
 information know a priori, and
 let's assume that all this information is available.
 Specifically, the routes server knows in advance the number of bytes,
 number of packets (as well as size of each packet) and the duration
 of a session, and let's take a closer
 look at the complexity of the computation. I can't see how
 you can claim to compute an optimal cost route with anything less
 exponential complexity.

 Thus, to clarify the issue I would suggest to add the following
 text to the architecture document :

  "In presence of heterogeneous charging schemes (e.g. cost per
   byte, cost per packet, cost per session), computation
   of a minimum cost route requires a priori knowledge
   by the entity that performs computation
   of the number of bytes, number of packets and sizes of each
   packet, and the duration of a session. If all that
   information is not available, computation of a minimum
   cost route is impossible. That, but itself,
   is likely to make computation of a minimum cost route
   in presence of heterogeneous charging schemes impractical.

   Even if one assumes that such information is available,
   the computational complexity of selecting a minimum cost
   route would be exponential, thus making it impractial for
   all, but small internets.

   Thus, while the architecture can provide information about
   heterogeneous charging schemes supported by various domains,
   the architecture can not realistically support computation of a minimum
   cost route unless all the domains throughout the Internet
   employ the same charging scheme."

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

 That would be quite useful to include in the text.

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

 There is a confusion between "user service requirements" and
 "hosts requirements". The first paragraph talks about "user
 service requirements"; the second about "host service requirements".
 To clarify the issue I would also suggest to add the following text
 (mostly from the second paragraph above):

    "In its current version, IDPR does not support service requirements
     with granularity of an individual user, unless there is a one-to-one
     mapping between a user and a host.

     In the future, we may wish to add to hosts the ability to specify
     user 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 users to communicate
     their service requirements through any protocol.

     To summarize, support for user service requirements for IP hosts
     can not be implemented without host software modifications."

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

 If the route computation procedure is capable of computing
 routes within given bounds, then it is rather easy to show
 that the route computation procedure can also produce optimal
 routes with not too much added computational complexity
 (the added complexity is logarithmic to the possible range of
 a metric).

 So, if the route computation procedure is capable
 of guaranteeing that it can compute a route within a given set
 of bounds, if such a route is present, then the same procedure
 can be used for computing an optimal route.

 To summarize, in a general case there is not too much difference in
 computational complexity between computing an optimal route
 and computing a route whose services are within given bounds.

 Thus removing the requirement for optimal routes is not
 that different from removing the requirement for routes
 whose services are within given bounds.

 To fix confusion on the subject of optimal route computation
 versus maintaining only partial informaion database
 I would suggest to add the following text:

     "It can be shown that under rather general assumptions
      computing optimal routes is not much more expensive
      that computing routes whose services are within given
      bounds. Since computation of an optimal route
      can not be performed in presence of only partial
      routing information, it follows that computation of
      routes whose services are within given bounds
      can not be performed in presence of partial routing
      information either.

      To summarize, computing routes whose services are within
      given bounds and maintaining only partial routing information
      database are two mutually unsatisfiable requirements."



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

 I wonder why did you pick up BGP ? Why not IDRP. I don't
 think you'll be able to make such claims with respect to
 storage complexity as you made if
 you'll use IDRP. As a matter of fact, I would suggest
 you to look at the storage complexity overhead for IDRP
 that was published in the April's issue of CCR.
 I hope that would change your conclusions.

 With respect to the computational overhead,
 as you pointed out further in your message, even with BGP
 you are likely to get less computational overhead than
 with IDPR. The difference would be even more striking
 if you'll use IDRP. I really don't understand why did
 you pick up BGP ?

 In view of the above, your assumption about "very little difference"
 seems incorrect from any point of view when you'll consider
 IDRP vs IDPR. Therefore, it might be useful to
 revisit all this and focus not only on the functionality
 but on the cost associated with the functionality.

>I will send a follow-on to cover the rest of the comments.

 I am looking forward to see them.

Yakov.