Subject: Re: [Ans-research] Absolute, optimal, sufficient scalability?

From: Richard Ogier <[email-masked]>
Date: Thu, 02 Oct 2003 06:07:02 -0700

Onur, Cesar, and all:

I want to comment on "sufficient scalability".  The following paragraph
by Onur clarifies the term and helps to support the point I will make.

> I understand what you mean. It is actually equivalent to comparing two
> methods w.r.t. a metric; Method 1: Actual routing protocol. Method 2:
> Genie routing protocol. Metric: Total bandwidth consumption (including
> traffic load). If the methods are EQUALLY scalable w.r.t. the metric
> (see section 2.6. of the draft for the definition of EQUALLY scalable),
> then your definition calls method 1 'sufficiently scalable'.

It is possible that a genie method is "more scalable" than an 
"optimally scalable" (real) method, but an "optimally scalable" 
method cannot be "more scalable" than a genie method.
Therefore, a "sufficiently scalable" method is also "optimally
scalable", so the term "sufficiently scalable" is not needed.

The reason it might not have looked this way in Cesar's original example
(using total overhead) is because total overhead is not an appropriate
choice for a metric, since it is actually the *difference* between the
total bandwidth consumption and the genie bandwidth consumption.
"Total bandwidth consumption" would be the appropriate metric in this case,
although I am not sure it should be one of the primary metrics that define
"absolute scalability" (and possibly "maximal scalability").

I would also like to make a point regarding end-to-end delay as a metric.
If the network model is such that the average distance between source
and destination is unbounded, for example O(N^0.5), then the genie method,
and an optimal method, should achieve an average end-to-end delay that
is O(N^0.5). It might therefore be better to redefine "absolute scalability"
to require only that the average end-to-end delay is proportional to the 
average number of hops between source and destination. Or perhaps omit
end-to-end delay from the set of primary metrics, and include only
per-hop delay (requiring it to be bounded by a constant).  

Regards,
Richard

_______________________________________________
Ans-research mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ans-research

---

From: Cesar Santivanez <[email-masked]>
Date: Thu, 02 Oct 2003 16:17:48 -0400

Hi Richard,

I agree with most of your coments.  BElow I am addressing the discrepancies.

> scalable", so the term "sufficiently scalable" is not needed.

A sufficient scalable method is not necesarily `optimally scalable'.
To see this let's consider a networking scenario where the bandwidth
consumption of the genie-approach is O(N^1.5) where N is the
network size. Let's see two cases.

Case 1. There exist an optmally scalable protocol Opt that induces an extra
bandwidth  consumption (total overhead) that is O(N^1.25). There is also
a protocol P  whose total overhead is O(N^1.4).
Both protocols (Opt and P) are sufffient scalable, since in both cases the
total bandwidth consumption is O(N^1.5)

For Opt:  Bandwidth consumption = O(N^1.5) + O(N^1.25) = O(N^1.5)
For P:      Bandwidth consumption = O(N^1.5) + O(N^1.4) = O(N^1.5)

So, P is NOT optimally scalable but it is sufficent scalable. Note that for very
large netwroks it may make sense to prefer P over Opt in some implementations
if P is simpler to implement.

Case 2. The optimally scalable routing protocol Opt for this networking scenario
induce - for argument sake -- an extra  bandwidth consumption (total overhead)
that is O(N^2). Protocol Opt is NOT suffient scalable since

For Opt:  Bandwidth consumption = O(N^1.5) + O(N^2) = O(N^2)

Protocol Opt bandwidth consumption O(N^2) increases faster than the genie
approach O(N^1.5).

Note that for a protocol be deemed `sufficient scalable' in this case 2, the protocol's
total overhead consumption should be O(N^1.5) or less. Thus, there is no `sufficient
scalable' protocol in this scenario.

> "absolute scalability" (and possibly "maximal scalability").

Yeah.  When defining `absolute scalability' you want to use a routing metric such
as `extra bandwidth consumption'. We typically call that : `overhead'. Some people
refer to it as `control overhead', and we refer to `total overhead' since
we have to take into account extra transmissions due to route's sub-optimality.
So, when defining `absolute' or `maximal' scalability we refer to total overhead,
and when we talk about `sufficent' scalability we talk about `total bandwidth
consumption'. This may seem confusing but we actually refer to the same
quantity: bandwidth consumption. It may seem that we don't since we use a different
term (`overhead'), but we should keep in mind that overhead is not other thing that
`extra bandwidth consumption'.

The same can be said about delay, energy, and other metrics of interest.

Regards

Cesar

--
Cesar Santivanez, Ph.D.
Network Scientist
Internetwork Research
BBN Technologies (A verizon unit)

---

From: Richard Ogier <[email-masked]>
Date: Fri, 03 Oct 2003 07:08:53 -0700

Hi Cesar,

Please see my comments below.

Cesar Santivanez wrote:

Hi Richard,

Richard Ogier wrote:

Onur, Cesar, and all:

All your examples use "total overhead" as the metric.  My whole point is
that this is not an

appropriate metric, since it is actually the *difference* between the total
bandwidth

consumption with an actual method and with a genie method.  The appropriate
metric

is "total bandwidth consumption".    With this metric, a sufficiently scalable
method

is always optimally scalable.

For Opt: Bandwidth consumption = O(N^1.5) + O(N^2)
= O(N^2)

I am not sure the phrase "you want to" is justified.   Why do you want to
use "extra bandwidth consumption"

instead of "total bandwidth consumption"  for defining absolute scalability?

I can see that the metric "total overhead" is useful and have read your paper
on it, but I don't think

it is an appropriate metric for defining scalability, since it is a "difference
metric" (as I explained above).

For defining absolute or maximal scalability, we need to carefully select
a few appropriate metrics,

called "primary metrics"  in the scalability draft.   The draft specifies
a preliminary set of primary metrics,

which does not include "total overhead".

This is exactly my point (and I was not confused by it).  In my opinion,
"total bandwidth consumption"

is an appropriate metric for defining scalability (whether absolute or optimal
or maximal or sufficient).

"Total overhead" is a useful metric, but I don't think it is appropriate
for defining scalability.

If the metric "total bandwidth consumption" is used, then "sufficient scalability"

is the same as "optimal scalability", which keeps things simple.

It looks like we could use another opinion.  Onur?

Regards,

Richard

Regards

Cesar