Martha's comments

[[e-mail]]

Noel,

>
>    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.
>
>	I think this claim (and some of the preceeeding text) is too
>broad to be supportable. Most research in graph theory has concentrated
>on algorithms which compute optimal routes to all destinations, not on a
>pair-wise basis. I think it would be appropriate to wait until the
>research is done on the latter case, and see what results. Also, I
>suspect that further research on algorithms which are close to optimal
>(probably probabilstic, and thus not guaranteed to be within bounds), but
>not optimal, will give us algorithms that are much less expensive than
>exponential.

	In view of your comment I would suggest to modify my proposed
	text as follows (I marked changes with "|"):

  "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, unless future research would
|  be able to come up with new algorithms that have less than
|  exponential computational complexity.

   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 either all the domains throughout the Internet
|  employ the same charging scheme, or future research will produce
|  new algorithms with less than exponential computational complexity."

	The modifications are intended to explicitly reflect
 your assertion that there is a probability that future
	research would be able to come up with algorithms
	that would have less than exponential complexity.

>
>
>    I would suggest you to look at the storage complexity overhead
>    for IDRP that was published in the April's issue of CCR.
>
>Is this material available online?

	Unfortunately no, but I hope you can get access to ACM CCR.
	If not, let me know and I'll send you a hard copy.

Yakov.