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

From: "Onur Arpacioglu" <[email-masked]>
Date: Fri, 26 Sep 2003 12:05:44 -0400

Dear all,

Firstly, thanks for the responses regarding our draft. Below are some
comments about absolute, relative and sufficient scalability, which have
been the discussion topics in the last couple of emails.

*********************
Jakob Eriksson wrote:

I'm find the definition of absolute scalability rather redundant, since
it is impossible to achieve. To see why this is so, try to achieve
bounded end-to-end delay in an infinitely large network, and you'll see
what I mean. Given our current light-speed limitation, one would have to
cram an infinite number of network terminals into a finite space, which
is a difficult task indeed.
**********************

I do not agree that absolute scalability is redundant. Absolute
scalability can be important, because it tells us what will happen when
the scaling parameter grows large: Will the efficiency of the network
vanish? That is, will it still be possible to provide a constant
throughput, a bounded delay with bounded power and memory requirements?
Therefore, absolute scalability tells us whether or not the
(method,environment) pair will allow the network to continue operating
efficiently, as the parameter grows large. For example, if the scaling
parameter is the number of nodes, the knowledge of absolute scalability
will tell us whether or not it is possible to support a large number of
users in the network.

I also do not agree that absolute scalability is never achievable. As it
is explained in the draft, it is strongly dependent on the environmental
variables as well as the method under consideration. It is true that
under most of the network scenarios that people consider today, absolute
scalability is not achievable when the scaling parameter is the number
of nodes. However, this is due to the assumptions of those network
scenarios (such as random traffic pattern assumption). There is no law
that says: "Absolute scalability is not achievable under any
circumstances". Also, as a relevant example, if the number of nodes is
growing, reference [3] in the draft implies that a protocol will not be
absolutely scalable if the area of the network is kept constant and/or
the average number of hops between a source and a destination becomes
unbounded, whereas this may not be the case if the area of the network
is increased at an appropriate rate, and the average number of hops
between a source and a destination is kept bounded. This is just one
example which shows that there can be environments where absolutely
scalable methods can exist.

***********************
Cesar Santivanez wrote:

I agree with Richard that introducing  the `optimally scalable'
definition will prove to be quite useful. Even if we can not develop an
`optimally scalable' protocol yet, knowing some of its properties will
help to focus the research effort. We can use knowledge of (bounds on)
the properties of the `optimally scalable' protocol the same way people
in the information theory field have used the shannon theoretical
limits: as a guide on detecting areas where the state-of-the-art was far
from  the achievable limits and therefore spending time and effort was
likely to  result on great performance improvements.
************************

I also agree that in general, knowledge of (or bounds on) the optimal
situation can be useful, since this knowledge can help us not to waste
time and effort to look for things that are better than the optimal.
However, making such a definition also requires defining the criteria
for optimal scalability. For example, is the optimally scalable routing
protocol (1) the protocol with the least overhead, (2) the protocol with
the least delay, (3) the protocol with the highest throughput (4) or
some weighted combination of (1),(2),(3)? I think different people will
give different answers to this question. Therefore, an "optimally
scalable" definition also requires specifying the criteria for
optimality as well as the environment, since for different environments
the optimally scalable method can be different. Another related
definition may be "optimally scalable with respect to a given
(metric,environment) pair".

***********************
Cesar Santivanez wrote:

Besides the term `optimally scalable' I think we should also introduce
the term `sufficiently scalable'. Roughly speaking, a protocol would be
deemed sufficiently scalable if, even though it is no absolutely
scalable, it is scalable enough so that it is not the main cause of
network performance degradation.
************************

I think, similar to "optimal scalability", "sufficient scalability" also
requires the specification of certain criteria as well as the
environment. In addition, sufficient scalability only tells that the
method is not performing worse(with respect to a metric) than some other
environmental variable (HSLS overhead vs. traffic load in Cesar's
example). Therefore, I think that in general, definition of
"sufficiently scalability" would be dependent on the environment very
much. For example, a slight change in one of the environmental
variables, such as the random traffic pattern assumption, can turn a
sufficiently scalable protocol into an insufficiently scalable protocol
or vice versa. Above all, in the current definition, the choice of the
environmental variable with which the method is compared seems to be a
subjective choice. For example, instead of comparing the overhead of the
routing protocol with the traffic load, one may also compare the
overhead of the routing protocol with the overhead of another layer in
the protocol stack, and reach different conclusions.

I want to emphasize that in this draft we are aiming to keep our
definitions as objective as possible in order to prevent situations,
where a researcher calls a method scalable, whereas another researcher
calls the same method not scalable, as much as possible.  We feel that
the "optimal scalability" definition may achieve this objectivity
provided that it is defined with respect to an appropriate metric or
combination of metrics, and the environment, but we are unsure that it
would be possible to obtain the necessary objectivity for the *current*
"sufficient scalability" definition, because of its heavy dependence on
the environmental variables and the subjective choice of the
environmental variable with which the comparison is done with respect to
a given metric.

Regards,

Onur Arpacioglu.
Cornell University,
School of Electrical and Computer Engineering,
Wireless Networks Laboratory,
389 Frank Rhodes Hall,
Ithaca, NY 14853
Email:[email-masked]

-----Original Message-----
From: [email-masked] [mailto:[email-masked]]
On Behalf Of Cesar Santivanez
Sent: Wednesday, September 24, 2003 5:22 PM
To: Jakob Eriksson
Cc: [email-masked]
Subject: Re: [Ans-research] Absolute, optimal, sufficient scalability? I
say "more" is enough.

Hi Jacob,

Please, see in-line comments:

Jakob Eriksson wrote:

> Although I haven't spent much time thinking about the "optimally" and 
> "sufficiently" alternatives, I can't see any reason to define them,

I do.  See comments below.

> since the protocol that is "more" scalable (as per the original
> definition) than every other protocol, is the best we currently know 
> how to do. After all, we're defining scalability in order to be able 
> to compare protocols, right?

That is one of the main reasons, but not the only one.
We do not only want to compare EXISTING protocols
but would like to develop new ones, with better scalability properties.
clear definitions and goals will help providing a sense of direction in
this effort. For example, if we prove that a particular protocol is
optimally scalable with respect to network size, we won't spend time and
effort trying to develop an alternative protocol with better scalability
properties with respect to network size.

The experience in other areas, particularly coding theory, has shown the
utility of such definitions. Knowledge of the channel capacity and the
entropy of a source has guided researchers in the development of coding
schemes. They knew that much could be gained when their codes were 5 dB
from the Shannon limit, and that not much improvement could be achieved
when the codes got close to 0.5 dB from that limit. A clear conceptual
framework was extremely helpful when deciding if a research effort was
worthwhile.

Thus, I see advantages on introducing the definitions -- at least for
the people involved in new protocols development. At the same time, I
see no harm in doing so.  I don't think introducing the `optimally' and
`sufficiently' scalable definitions adds a tremendous amount of
complexity or that it may cause confusion to some people. If someone
finds that a `more/less' comparison is enough for his/her work, then
he/she may choose not to use the other definitions.

> Not to make claims about optimality, which we
> all know will anyway be false in some sense or other.

Clear definitions and well defined scenarios and assumptions would avoid
false or imprecise statements.

> Jakob Eriksson
> U.C. Riverside

Regards

Cesar

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

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

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

---

From: Cesar Santivanez <[email-masked]>
Date: Fri, 26 Sep 2003 21:35:52 -0400

Hi Onur,

Thank you for your response.

I am addressing some of your comments below:

> for optimal scalability.

I Agree. But this is also the case for absolute scalability and have been already
addressed in your draft.  That is, scalability only makes sense with respect to
the triplet (environment, independent parameters, primary metric(s)).
For example  I can talk about a routing algorithm being `absolute scalable'
with respect to the triplet:
environment: bounded degree, random destinations.
Parameter: network size.
Metric: bandwidth consumption.

Thus, I can also talk about a routing algorithm being `optimally scalable'
with respect to the same triplet, if the primary metric's performance
is the BEST of all possible algorithms. There is no ambiguity.
Of course, the fact that a rotuing protocol be scalable w.r.t. the
bandwidth consumption criteria DOES not mean that it is scalable
w.r.t. to another criteria such as memory consumption.

I do not see the ambiguity when the primary criteria is a single metric.
Things may turn a little more complicated when the primary metric
is a vector, as for example (bandwidth consumption, delay). Then,
if we say that a routing protocol is optimally scalable w.r.t. the biduple
(bandwidth, delay) then the performance on each of these criterias
should outperform the perfromance of any other algortihm.
This may not be possible, and therefore we may have algorithms
that are optimally scalable w.r.t. (bandwidth comsumption) and
(delay)  but not both. Still, I do not see the problem or the ambiguity.
We are just extending a previous definition..

> For example, is the optimally scalable routing
> some weighted combination of (1),(2),(3)?

It all depends on what your primary metric is. If your primary metric
is a triplet including the three metric above, then a protocol
should outperform all the other in ALL the three criteria to be deemed
scalable. Note that in this example this does not think impossible
since the protocol with least total overhead will have higher throughput,
and since the delay has a strong dependence in the network throghput
(as load increases) it is likely that the protocol that provides more
throughput will also provide lower delays.

However, if you ask for a metric of the type (throughput, memory requirements,
processing power) then iti is unlikely that you get a protocol that outperform
all other in the three criterias.

Still, if you develop a protocol that has the best thrughput and memory
requirements properties under a given set of scenarios and independent
paramentes, it would be useful that you have the definitions allowing
to state that fact precisely.

> I think different people will

Agreed, but this is already coveedr in the draft... Absolute scalability is also
with respect to (environment, parameters, metric).

> environment.

See my previous answer.

> In addition, sufficient scalability only tells that the
> example).

No. It was not the intention of the definition. I apologize if I did not express
myself correctly. I am comparing the routing protocol performance (on a
well defined triplet : enviroment, parameter. metric) to the *network*
performance. And by network performance U refer to the performance that is
obtained when perfect routng information is available by free (a genie approach).

In my previous e-mail example, the environment was the one described
in [4] : bounded degree, uniformly distributed destinations, the running parameter
was network size, and the criteria of interest was bandwidth consumption.
Thus, I have to compare bandwidth consumption when I have the `genie'
routing (e.g. traffic load) to the bandwidth consumption when a actual routing
algorithm (e.g. HSLS)is present (traffic load + total overhead).  Thus,
for the routing protocol not to cause degradation, and be `sufficiently scalable'
I need that the total overhead  increases more slowly than the traffic load.
I guess that jumping to compare `total overhead' to traffic load was the cause of
confusion.

Let's say that I want to see if a routing algorithm is `suffiently scalable' with respect
to delay or memory consumption. Then what I need to do is to measure the delay
and memory requirements when optimal routing decision are provided on-the-fly
for a genie, to the actual delay and memory consumption when a real-life
routing module is in place.

So, there is no ambiguity or subjetivity on what I am comparing. I must
compare apples to apples. If delay is my performance criteria, I must compare
delay with genie routing versus delay with a given routing protocol.
It may not be obvious that this was what I did in my previous example since
total overhead and traffic load appear as different quantities, nut they are not.
AS defined in [4], they are just the two terms involved in the bandwidth
consumption computation, that is, under any routing protocol, the bandwidth
consumed is equal to traffic load + total overhead.

I apologize for the confusion.

> Therefore, I think that in general, definition of

> or vice versa.

Of course... And this is also true for the absoulute scalable protocol.
If you change the scenario (say, add traffic locality), the scalability
results change. That is why you defined scalability in terms of the
triplet: scenario, paramenters, metric. isnt it???

> Above all, in the current definition, the choice of the
> subjective choice.

No.  apologize for the confusion. See comment above.

> For example, instead of comparing the overhead of the

Nope. We are comapring `without routing -- using a genie' versus
`using my routing algorithm'. There is no ambiguity or subjectivity.

> calls the same method not scalable, as much as possible.

I agree. And I must say I like your draft.

> We feel that

I think that an objective definiton can be easily stated in the context
of your draft.  It is more difficult to do it here, in the context of an e-mail
with informal language, since we leave room for confusion.

> Regards,

Thanks for your comments.

Cesar

> ---

---

From: "Onur Arpacioglu" <[email-masked]>
Date: Mon, 29 Sep 2003 12:34:27 -0400

Hi Cesar,

Thank you for your comments. I have a few more comments below:

***************************
*> However, making such a definition also requires defining the criteria

*> for optimal scalability.
*
*I Agree. But this is also the case for absolute scalability and have
been
*already addressed in your draft.  That is, scalability only makes sense
*with respect to the triplet (environment, independent parameters,
primary
*metric(s)). For example  I can talk about a routing algorithm being
*`absolute scalable' with respect to the triplet:
*environment: bounded degree, random destinations.
*Parameter: network size.
*Metric: bandwidth consumption.
*
*Thus, I can also talk about a routing algorithm being `optimally
scalable'
*with respect to the same triplet, if the primary metric's performance
is 
*the BEST of all possible algorithms. There is no ambiguity. Of course,
the
*fact that a rotuing protocol be scalable w.r.t. the bandwidth
consumption
*criteria DOES not mean that it is scalable w.r.t. to another criteria
such
*as memory consumption.
*
*I do not see the ambiguity when the primary criteria is a single
metric. 
*Things may turn a little more complicated when the primary metric is a
vector, 
*as for example (bandwidth consumption, delay). Then, if we say that a
routing 
*protocol is optimally scalable w.r.t. the biduple (bandwidth, delay)
then the 
*performance on each of these criterias should outperform the
perfromance of any
*other algortihm. This may not be possible, and therefore we may have
algorithms
*that are optimally scalable w.r.t. (bandwidth comsumption) and (delay)
but not both. 
***************************

I agree; defining optimal scalability w.r.t. (environment, independent
parameter, primary metric(s)) triplet has no ambuguity. I was actually
referring to this while I was saying:

> Another related definition may be "optimally scalable with respect to
a given
> (metric,environment) pair".

I think you clarified this well, in the above explanation.

***********************
*> In addition, sufficient scalability only tells that the method is not

*> performing worse(with respect to a metric) than some other 
*> environmental variable (HSLS overhead vs. traffic load in Cesar's 
*> example).
*
*No. It was not the intention of the definition. I apologize if I did
not express
*myself correctly. I am comparing the routing protocol performance (on a
well defined
*triplet : enviroment, parameter. metric) to the *network* performance.
And by 
*network performance U refer to the performance that is obtained when
perfect routng 
*information is available by free (a genie approach).
*
*In my previous e-mail example, the environment was the one described in
[4] : 
*bounded degree, uniformly distributed destinations, the running
parameter was network 
*size, and the criteria of interest was bandwidth consumption. Thus, I
have to compare 
*bandwidth consumption when I have the `genie' routing (e.g. traffic
load) to the bandwidth 
*consumption when a actual routing algorithm (e.g. HSLS)is present
(traffic load + total 
*overhead).  Thus, for the routing protocol not to cause degradation,
and be `sufficiently 
*scalable' I need that the total overhead  increases more slowly than
the traffic load. I 
*guess that jumping to compare `total overhead' to traffic load was the
cause of confusion.
*....So, there is no ambiguity or subjetivity on what I am comparing. I
must compare apples 
*to apples. If delay is my performance criteria, I must compare delay
with genie routing 
*versus delay with a given routing protocol.
*....We are comapring `without routing -- using a genie' versus `using
my routing algorithm'. 
*There is no ambiguity or subjectivity.
***********************

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

I agree that you are comparing apples with apples, but I am not sure
about how in general one can objectively define a *genie method*. In
your example, for a routing protocol, you defined it as the routing
protocol that has the full topology knowledge without any overhead, and
has the ability to route through the shortest paths (without
experiencing any lower layer problems such as collisions, buffer
overflows, etc.). However, someone else may define a different genie
protocol by giving it more or less intelligence or capabilities, and
this may turn the definition of the genie method into a subjective
definition. As a result, in my opinion, sufficient scalability
definition can be an objective definition provided that the associated
genie method can be objectively defined.

Regards,

Onur Arpacioglu.
Cornell University,

---

From: Richard Ogier <[email-masked]>
Date: Mon, 29 Sep 2003 10:54:10 -0700

>> Another related definition may be "optimally scalable with respect to a given

> I think you clarified this well, in the above explanation.

This was also my intention in the message where I proposed the
term "optimally scalable", and I clarified this in my message of Sep 21.
Thus, "optimally scalable" could also be called "most scalable" (versus "more scalable")
with respect to a given (parameter, metric, environment).

Since a method can be "optimally scalable" w.r.t. one metric but not another metric,
I think another term is needed, perhaps "maximally scalable", to indicate that
there does not exist another method that is "more scalable" w.r.t. at least one
primary metric without being "less scalable" w.r.t. some other primary metric.

Regards,
Richard

---

From: Cesar Santivanez <[email-masked]>
Date: Mon, 29 Sep 2003 19:51:06 -0400

Hi Onur,

Thanks for your response. It is good to see that we are in agreement.
It is tru that an objective definition of the `genie' routing must be
provided. Such a definition could be:

`genie-routing'  benchmark: performance results obtained when
-- just before each packet transmission --  an imaginary omniscient
routing module tells the node what is the best next hop for the
packet's destination. The imaginary routing module consumes no
resources (bandwidth, energy, rocessing, etc.)

Note that the above definition is advocating using hop-by-hop routing
over, say, elastic virtual circuits or reactive routing. It is only saying
that  using the best next-hop in a packet per packet basis is the best
you can do. Also, note there is no point in assuming a snarter more
capable genie,  since the only thing the genie provide is the next hop
info, and once you define a genie that provides the best next hop,
then there is no other genie that can do better ;-)

Alos, note that the definition DOES NOT require the assumption
"without experiencing any lower layer problems such as collisions, buffer
overflows, etc.". I would say that the lower layer problems depend on the
lower layer protocols' choices, and as such is part of the `environmental
assumptions'.  Of course, when doing theoretical analyisis of routig
protocols we would tend to choose a simplified environment (in terms
of MAC and physical layer)  for tractability without losing (much)
generality. Recall that the choice of MAC layer protocol used shouldn't
affect the routing protocol's scalability properties.

Finally, the above definition does not talk about what information the
genie would need to make its decision. For illustration purposes we have
talked about  a genie having full knowledge of the topology information.
But it may well be that for some metrics (e.g. delay) other info is relevant (e.g.
queue occupancies in intermediate nodes, etc.).  What we are saying
is that the genie just happens to know the right answer.  Of course, we will have
to compare this with actual routng protocols that will need some way of
finding/propagating/storing the relevant information.

Regards

Cesar

---

From: Cesar Santivanez <[email-masked]>
Date: Mon, 29 Sep 2003 19:59:33 -0400

There is a small but important typo in my last e-mail:

It says:

> Note that the above definition *is* advocating using hop-by-hop routing

> over, say, elastic virtual circuits or reactive routing.

It should have said:

Note that the above definition ** is NOT ** advocating using hop-by-hop
routing over, say, elastic virtual circuits or reactive routing.

Sorry about that

Cesar

---

From: "Onur Arpacioglu" <[email-masked]>
Date: Tue, 30 Sep 2003 14:58:51 -0400

Hi Richard,

>> referring to this while I was saying:
...
>This was also my intention in the message where I proposed the term
>"optimally scalable", and I clarified this in my message of Sep 21.
>Thus, "optimally scalable" could also be called "most scalable"
>(versus "more scalable") with respect to a given (parameter, metric,
environment).

I think now we all understand the same things about the definition of
optimal scalability. Naming it "most scalable" or "optimally scalable"
are both fine with me. It only changes how you state it:

(1)Method X is optimally scalable w.r.t. a given (parameter, metric,
environment), or
(2)Method X is the most scalable method w.r.t. a given (parameter,
metric, environment).

>Since a method can be "optimally scalable" w.r.t. one metric but not
another
>metric,

I agree

>I think another term is needed, perhaps "maximally scalable", to
>indicate that there does not exist another method that is "more
scalable"
>w.r.t. at least one primary metric without being "less scalable" w.r.t.

>some other primary metric.

I also think we need another definition, thanks for bringing this up.
However, in general, if "maximally scalable" has the above definition, I
think that maximally scalable methods may NOT have UNIQUE scaling
properties in terms of the metrics. Consider the following example:

Suppose we have two metrics in a given environment, and for simplicity
suppose that there are four methods in the method space and their
metrics (w.r.t. a given parameter N) all have polynomial forms as
follows:

			Metric 1 (m1)	Metric 2 (m2)
Method	
E1				N^1			N^5
E2				N^2			N^4
E3				N^3			N^2
E4				N^4			N^1

So, for relative scalability (denoting more scalable by >), we have:
*E1>E2>E3>E4 w.r.t. m1, and E4>E3>E2>E1 w.r.t. m2.
*E1 is the most scalable method w.r.t. m1.
*E4 is the most scalable method w.r.t. m2.

Now, applying your definition:

*Compared to E2, E1 is the only method that is more scalable than E2
w.r.t. m1, but E1 is less scalable than E2 w.r.t. m2. Also, E3 and E4
are the only methods that are more scalable than E2 w.r.t. m2, but they
are less scalable than E2 w.r.t. m1. Thus, according to the definition,
E2 is *maximally scalable*.
*Likewise, compared to E3, E4 is the only method that is more scalable
than E3 w.r.t. m2, but E4 is less scalable than E3 w.r.t. m1. Also, E1
and E2 are the only methods that are more scalable than E3 w.r.t. m1,
but they are less scalable than E3 w.r.t. m2. Therefore, E3 is also
*maximally scalable*.

So, although E2 and E3 have different scaling properties w.r.t. m1 and
m2, they are both maximally scalable.

This is just one example which shows that the maximally scalable
methods, with the current definition, may not have unique scaling
properties. In general, there can be many such methods.

As a result, I am not sure what information the current definition will
give us, since many maximally scalable methods that have different
scaling properties (in terms of the metrics) can exist at the same time.

Regards,

Onur Arpacioglu.
Cornell University,