Subject: [Ans-research] Comment on scalability draft

From: Richard Ogier <[email-masked]>
Date: Wed, 17 Sep 2003 12:55:56 -0700

Hello,

I can't attend the ANS meeting tomorrow, but I have a few comments on the
scalability draft  <draft-irtf-ans-scalability-definition-00.txt>.

I like the definitions of absolute and relative scalability, and the 
fact that all metrics
must be considered for absolute scalability (but a metric must be 
specified for
relative scalability).

I think there are many important environments for which an absolutely 
scalable
method does not exist, e.g., if the number of hops between a source and a
destination is not bounded by a constant.  In these environments, relative
scalability must be considered, and the goal will be to show that a 
given method
is more scalable than other methods.

Maybe another term should be introduced, such as "optimally scalable", that
indicates a given method is more scalable than any other possible method
(when an absolutely scalable method does not exist). 

Richard

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

---

From: "[email-masked]" <[email-masked]>
Date: Sat, 20 Sep 2003 10:41:42 -0400 (EDT)

Hi Richard,

Thanks for your comments on the draft.

> (when an absolutely scalable method does not exist). 

The term "optimal scalability" sounds interesting, but I am not sure how
it could be practically applied. In other words, I am not sure how one can
state that there cannot exist another method that is more scalable. If you
have any example in mind, please bring it up - it would help to understand 
this term.

In essence, what I am saying is that if a method A scales, say, with the 
number of nodes as O(N^a), and a<0 (i.e., A is not absoultely scalable), 
then, in principle, there always can be another method B which scales better
with N; i.e., O(N^b), where a<b<0.

Does this make sense?

Zygmunt.
=-=-==-=-=-=
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-
Prof. Zygmunt J. Haas                    http://people.ece.cornell.edu/haas 
Wireless Networks Laboratory		 http://wnl.ece.cornell.edu
School of Electrical Engineering         
Cornell University			 tel: +1-607-255-3454
323 Frank Rhodes Hall			 fax: +1-607-255-9072
Ithaca, NY 14853			 e-mail: [email-masked]
U.S.A                             
	WNL web page: http://wnl.ece.cornell.edu
~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-~-

---

From: Richard Ogier <[email-masked]>
Date: Sun, 21 Sep 2003 09:54:36 -0700

Hello Zygmunt,

[email-masked] wrote:

Hi Richard,

One example that comes to mind is HSLS (the main example used in your draft).

Quoting from the abstract of the MobiHoc 2001 paper that presented HSLS:

"This algorithm is shown to have nearly the best possible asymptotic
overhead for

any routing algorithm - proactive or reactive."

So if the word "nearly" could be removed, then HSLS would be "optimally scalable"

in the number of nodes, with respect to the total overhead metric and the
network

model defined in the paper.

In general, if one could *prove* that method A is "more scalable" than any
other method (for

a given metric and network model), then one can say that method A is "optimally
scalable".

But this is really a minor point, since your draft already defines "more
scalable", so it almost

goes without saying that a method that is "more scalable" than any other
method is

"optimally scalable".   One reason I like the term "optimally scalable" is
because, in some cases,

an "absolutely scalable" method may not exist, in which case the ultimate
goal is to find an

"optimally scalable" method.

Regards,

Richard

Does this make sense?

Zygmunt.
=-=-==-=-=-=
Ithaca, NY 14853 e-mail: [email-masked]
nell.edu

Hello,

Maybe another term should be introduced, such as "optimally scalable", that
indicates a given method is more scalable than any other possible method
(when an absolutely scalable method does not exist). <
br>
Richard

---

From: Cesar Santivanez <[email-masked]>
Date: Tue, 23 Sep 2003 23:05:08 -0400

Zigmunt, Richard, and all,

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.

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.
To illustrate this definition, let's consider once again the scenario described
in our Infocom paper (reference [4] in the scalability definitions draft
 <draft-irtf-and-scalability-notes-00.txt>). That scenario is a bounded-degree
ad hoc network with an uniform traffic distribution. In this setting the average
path length grows as N^(0.5) -- where N is the network size -- and the traffic
injected by each node is independent of network size, so the total traffic injected
over the network is O(N).  Thus, the total number of transmissions grows
as N^(1.5). Now, consider, for argument sake, that a routing protocol R has a
total overhead (defined in [4])  that increases as N^(1.25). Protocol R is
obviously not absolutely scalable (since bandwidth only increases as O(N)).
This means that as  we increase the network size the routing protocol will
eventually cause the network to break. However, by comparing the rate of
increase of the  routing protocol  (1.25) and the rate of the traffic load (1.5)
we can see that  the network will break well BEFORE routing protocol R
overhead becomes an issue.

Alternatively, we can see that the ratio of protocol R's total overhead to
the traffic load tends to zero as the netwrok size grows. Thus, as network
size grows (probaly thanks to new technologies allowing for higher transmission
rates -- i.e. more bandwidth) the impact of routing protocol R over
the network performance tends to be neglectable.

In this case, one could argue that protocol R is `good enough' for this
particular scenario, and research effort should be directed in other, more fruitful
directions (e.g. other scanarios, or trying to scale to parameters other than
network size, etc.).

So, I think we should formally define when a routing protocol is `good enough',
or `sufficiently scalable'.  Note that for some scenarios the `optimally scalable'
protocol may not be `good enough', and in other scenarios a good enough protocol
need not be optimally scalable.

One final note regarding the HSLS example. We showed that it scales as N^(1.5)
with respect to network size, and in that sense it matches the traffic load of an
ad hoc network under the scenario desccribed in [4]. In this sense, we can say that
it is `sufficiently scalable' with respect to network size.  However, we have not
proved  that HSLS is `optimally' scalable witrh respect to network size. We showed
that it scaled better than KNOWN protocols, but we have not been able to prove that
it scales better that ANY possible protocol. We believe that such a prive exists, but
have not been able to find it so far .... Any takers??

Regards

Cesar

Richard Ogier wrote:

>       "This algorithm is shown to have nearly the best possible asymptotic overhead for
> in the number of nodes, with respect to the total overhead metric and the network
> In general, if one could *prove* that method A is "more scalable" than any other method (for
> a given metric and network model), then one can say that method A is "optimally scalable".
> But this is really a minor point, since your draft already defines "more scalable", so it almost
> goes without saying that a method that is "more scalable" than any other method is
> "optimally scalable".   One reason I like the term "optimally scalable" is because, in some cases,
> an "absolutely scalable" method may not exist, in which case the ultimate goal is to find an
> _______________________________________________ Ans-research mailing list [email-masked] https://www1.ietf.org/mailman/listinfo/ans-research

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

---

From: Jakob Eriksson <[email-masked]>
Date: Tue, 23 Sep 2003 20:17:50 -0700

Hello everyone,

I must disagree with the previous posters regarding scalability 
definitions. Rather than defining absolute, optimal or sufficient 
scalability, I suggest we drop all three terms and be satisfied with 
the very useful, and well defined, "more" scalable, that was part of 
the original draft.

As those of you who attended the meeting at MobiCom know, 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.

Although I haven't spent much time thinking about the "optimally" and 
"sufficiently" alternatives, I can't see any reason to define them, 
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? Not to make claims about optimality, which we 
all know will anyway be false in some sense or other.

Jakob Eriksson
U.C. Riverside

---

From: Cesar Santivanez <[email-masked]>
Date: Wed, 24 Sep 2003 17:21:41 -0400

Hi Jacob,

Please, see in-line comments:

> "sufficiently" alternatives, I can't see any reason to define them,

I do.  See comments below.

> 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

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

Regards

Cesar