Subject: [Ans-research] Direction of ANS RG

From: "Elizabeth M. Belding-Royer" <[email-masked]>
Date: Mon, 7 Apr 2003 11:56:35 -0700 (PDT)

Hi,

There are a number of you on the mailing list now so I think we
should start discussing the direction and emphasis of this research
group.

At the Bar BOF at the IETF meeting, we talked about a number of 
potential directions for the group.  The over-riding point that
became evident as we continued our discussion was that we need
a clear definition of what scalability is.  Since the group's 
focus is scalability in ad hoc networks, we need to first define
the problem we are working on before we can begin to propose 
solutions.  This topic has been discussed in a different flavor 
on the MANET mailing list in terms of trying to define the type
of network the MANET group should focus on.  It has become evident
from these discussions that there are a number of dimensions 
to defining a network.  Likewise, there will be multiple dimensions
to consider when defining scalability.  These are likely to include
number of nodes, network size, traffic model, mobility, and others.

One of the first things that could be a product of this research
group is an information document defining scalability along all
of the different possible axes.  This will enable us to focus more
clearly on the type of networks we are researching.  It will also
most likely benefit the MANET group as well.

Does anyone have thoughts either on this as our future direction or
on how to begin undertaking this task?

Elizabeth

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

---

From: Joe Macker <[email-masked]>
Date: Mon, 07 Apr 2003 16:22:35 -0400

Although slightly different in scope and intent you could look at RFC 2357 for some ideas.
I think a short information document talking about issues and scope might be relevant.
Doesn't have to be perfect.

-Joe

---

From: Joe Macker <[email-masked]>
Date: Mon, 07 Apr 2003 16:40:40 -0400

>Doesn't have to be perfect.

Before the threads start, by the above, I meant it could be a short discussion layouting 
some basic ANS tradeoffs and problem space issues without getting into solution sets right
away.

---

From: John Stine <[email-masked]>
Date: Mon, 07 Apr 2003 16:41:09 -0400

Hi Elizabeth,

    I was looking forward to a new mailing list that would have a more
research oriented nature but must admit that I am a bit disappointed
that we have chosen scalability as our focus.  This appears to be an
effort to create the environments in which to compare the IETF MANET
routing protocol solutions rather than an effort to find new and better
solutions for all aspects of ad hoc networking.   There is a very rich
design space at the physical layer but the IETF MANET charter to focus
on IP routing solutions has separated this design space from potential
solutions.  The recent discussions on the MANET mailing list on
interlayer communication and dependence is far more interesting and
would be the direction I would want a new group to follow.  Would it be
possible to allow the discussion to go in this direction?

    Some topics I would like to see discussed is an articulation of the
pros and cons of implementing routing above and below IP.  Can
functionality be divided?  Can routing be integrated with an access
protocol?  How can such integration be exploited to improve networking
performance?  What functionality has to be above IP to give layers 4+ an
interface that remains quinessentially IP?  What capability should
higher layer protocols have to affect the operation of lower layer
protocols for purposes of QoS, security, or some other goal?    Is the
802.11 layer 1 and 2 solution the best we can do?  Say an access
protocol provides a QoS capability, how should a higher layer protocol
communicate its selection?  What are the mechanisms for interlayer
communication (read this as IP and above to and from below IP)?  I know
positions on these topics border on being religious beliefs but it seems
silly to me to limit our design space.

John

---

From: Jakob Eriksson <[email-masked]>
Date: Mon, 7 Apr 2003 16:34:06 -0700

Hi there,

The topics outlined by Elisabeth earlier deal with how to recognize
scalability when we see it. I would like to see some discussion on
known facts/absolute truths on how to achieve scalability, to see if
there are any such beasts. Of course, since scalability has yet to
be defined, this will have to be a rather informal discussion.
Nevertheless, it would be good to hear people's opinions in
these matters.

To stir up some discussion, I'd like to volunteer some candidates for
known facts/absolute truths. These are the "known facts" that I'm
using as guidelines in my own work. Feel free to rip them apart,
and please elaborate on specific problems you see.

7 Candidates for "Known Facts" concerning MANETS
=========================================

1. Protocols that rely on flooding do not scale to large networks.
To some extent, this could mean that reactive protocols aren't
likely to scale, unless someone comes up with a non-flooding
reactive scheme. Limited flooding may still have some merit.

2. Protocols that use a flat namespace for addresses do not
scale to large networks. In essence, in order to scale to thousands
of nodes or even millions of nodes, some kind of hierarchy is
needed. ZRP, for example, takes a small step in that direction, but
in the limit, a two-level hierarchy is almost flat anyway.

3. For scalability, the address of a node should reflect its current
position in the network topology. This is similar to the previous
point. If addresses indicate a position in the network, routing is very
much simplified. However, it means that addresses must change
as nodes change position in the network, so there may be a
trade-off here.

4. Centralized services do not scale. In the optimal routing protocol,
there can be no reliance on centralized services.

5. Wireless omnidirectional does not scale. In order to scale to very
large networks, we have to support wires and directional antennas.
That is, we cannot depend on particular characteristics of
omnidirectional transmission, although we can very well use them
when available.

6. How a mac/network protocol interacts with TCP is irrelevant.
TCP was not made for lossy channels. Design for mac/network
layer scalability and a natural transport layer will follow.

7. Last, but not least, routing protocols that rely on geographical
location information are undesirable for many reasons. Beside
the obvious problems (energy, bulk, cost, precision, indoor
operation etc.), a geographic location does not reliably correspond
to a location in a network topology. Two disjoint domains could
very well coexist in the same geographical location, with an
intersection in some other part of the world. Thus, relying on GPS
or equiv. even for rough guidance, may be very harmful for large
networks.

Note that the above is not criticism against anyone's earlier, current
or future work, but simply a controversial starting point for 
discussion.
I'd love to see more candidates for absolute truths, and arguments
for and against those mentioned above. Flame away, =)

Jakob Eriksson
U.C. Riverside

* The opinions expressed above are mine and not necessarily the
policy of my school, department, research group or advisor =) *

---

From: Anders Nilsson <[email-masked]>
Date: Tue, 08 Apr 2003 11:06:50 +0200

Hello all,

I think the first aim of this group should be to produce a document like 
RFC 2501, but for large and scalable ad hoc networks. As Elzabeth says, 
this document should discuss the problems we are
facing, known issues, various performance and evaluation criterias etc. 
Although larger ad hoc networks have many similarities with smaller or 
moderate networks, the design considerations are different. We still 
consider the same issues and problems, but some of the existing problems 
tend to grow with the size of the network.

As already mentioned, we must consider the number of nodes, network 
size, traffic model, rate of mobility. We should try to visualize the 
properties future applications will have. Will these produce bursty 
traffic or more smooth traffic.  In some cases, the type of expected 
applications and their expected traffic and mobility patterns, might 
have a vital impact on the performance of the network.
An other very important part is the density of the network. This is 
important both in terms of congestion and overload, and in terms of 
connectivity. A sparse network might have low connectivity while a dense 
network might have a very high connectivity.  But the dense network also 
has higher congestion and traffic/routing load.
It would be nice if we could have a common set of performance metrics, 
that reflect the scalability of the network.

> reactive scheme. Limited flooding may still have some merit.

I agree, but this also depends on the amount traffic in the network. 
S.J. Lee et al. showed that AODV could scale to very larger network. 
When the amount of traffic was fairly low. Pure proactive schemes, 
except maybe LANMAR,  all tend to scale poorly.

> in the limit, a two-level hierarchy is almost flat anyway.

I agree that we probably need some kind of hierarchy when the network 
becomes very large. But this is not the same thing as having a 
hierarchical namespace. I think it is possible to come with solutions 
that use a flat addressing scheme, but that still relies on a hierarchy.

> as nodes change position in the network, so there may be a

Yes, the problem here becomes a mobile IP sort of problem. For this to work
we need some kind of handover sheme and/or lookup scheme. When a node 
receives a new address, the old one will no longer be available, e.g. 
hard handover. If the network is a hybrid one, we can probably use 
existing solutions. But if it is a pure ad hoc network, the problem 
becomes more difficult to solve, at least for ongoing sessions and 
proactive schemes

> there can be no reliance on centralized services.

Why not? I am not saying having centralized services is optimal, but I 
do think centralized services can help scalability. Say we a special 
node in the network providing a special service such as DNS. If all 
nodes in the network know of this node, or neighboring nodes know of it, 
a node doesn't need to first serach for it. The node could then 
unicast/mulicast/anycast packets to the intended service node. This 
might not be optimal, and it do make the network more vulnerable, but I 
think it will improve scalability. By the way, I don't think there will 
ever be an optimal routing protocol, a one size fits all.

> omnidirectional transmission, although we can very well use them

Right. Directional antennas will surely improve performance, but we 
shouldn't have
to rely on them either.

> layer scalability and a natural transport layer will follow.

I think what you say here is a contradiction. I think a TCP version that 
handle large network with lossy channels will developed, but only 
through interaction with the mac and network levels. So the mac/network 
and transport layer interaction is very much relevant, and is an area 
that I think should receive more attention.

> or equiv. even for rough guidance, may be very harmful for large
I can't say I agree with you here at all. The obvious problems you 
mentioned are so obvious at all. The GPS technology is developing all 
the time, and the devices themselves becomes smaller and more power 
conservative. In future there is a possibility that all network equipped 
devices will also include GPS or similiar devices. And what is the 
problem of having two disjoint domains coexisting in the same 
geographical area? Maybe, if you force the addressing scheme to stricly 
reflect your position, will you have problems with this. But that is an 
addressing problem, not a routing problem. The problem is how to 
determine the position of a node. There are numerous solutions to how 
this problem can be solved, and some of them work quite well. But there 
are reason for taking advantage of GPS information. There are many 
applications that could benefit from having an exact geographical 
position, not the least military applications, but also many civilian ones.

regards,

Anders Nilsson

---

From: Einar Vollset <[email-masked]>
Date: Tue, 8 Apr 2003 11:28:11 +0100

All,

> solutions for all aspects of ad hoc networking.

I must say I agree with John here. On the MANET list, we were urged to
stop discussing research topics in order to focus more on the 
engineering
aspects and getting protocols to Experimental RFC status, and setting
up an IRTF list was hailed as the answer.
Not that I don't think scalability is important,
quite the contrary, but it does mean that research on MANETs in other
areas such as reliability, QoS, services++ are left in the lurk.

I suppose the answer to this is setting up another mailing list..

Cheers,

Einar

---

From: Einar Vollset <[email-masked]>
Date: Tue, 8 Apr 2003 11:44:52 +0100

> there can be no reliance on centralized services.

On the routing level I definately agree with this. To me, this is one of
the key characteristics and benefits of MANETs.
> omnidirectional transmission, although we can very well use them

I'll have to disagree on this point. I think what is required is a 
fundamental shift
in thinking about routing as something which happens in one-dimensional
space to two-dimensional space. My belief is that the omnidirectional
property of 99.99% of packet radios can be utilized to the benefit of
the routing protocol. (A very simple example is the use of passive
acknowledgments as hinted at in the original ODMRP paper).
(At least this is my own personal crusade at the moment.. )

> or equiv. even for rough guidance, may be very harmful for large

I agree with Anders on this, I think location information will become
more and more common (it is, after all one of the key points in the
current push for pervasive/ubiquitous computing), and I think not making
use of it would be rather silly :-)

Cheers,

Einar

---

From: Shubhranshu <[email-masked]>
Date: Tue, 08 Apr 2003 20:16:42 -0800

hello,

> solutions for all aspects of ad hoc networking.

     I feel ( and wish)  that most members won't go for
creating environments  to compare MANET protocol solutions. As most of
the MANET protocols doesn't scale well. AODV has been shown to be
a better SCALABLE candidate,  but then here SCALABLE means millions of
 nodes not just hundreds.

> There is a very rich

I favour considering discussion about interlayer communication and
dependence
but its my  feeling that by itself,   it won't give us the real Scalable
network that we are looking for. For that we need to
focus on ADDRESSING MECHANISM.

> silly to me to limit our design space.

Any discussion which may lead to better scalable network are welcome.

---

From: Shubhranshu <[email-masked]>
Date: Tue, 08 Apr 2003 20:32:04 -0800

Hi,

> except maybe LANMAR,  all tend to scale poorly.

 Yes, AODV does scale to very large network but  I feel
 this scalabality should not be our concern here.  Scalabality here
 should IDEALLY mean scaling to the size of the  internet !!!!
And to achieve this we have to start AFRESH !!!!

> that use a flat addressing scheme, but that still relies on a hierarchy.

So far I feel hierarchical based addressing is the path that may lead us to
a real scalable network !!!!!

Warm Regards
Shubhranshu Singh

---

From: Sukanta Kumar Hazra <[email-masked]>
Date: Tue, 8 Apr 2003 20:12:54 +0800

Einar,

> I suppose the answer to this is setting up another mailing list..

You have issues with the term "scalability", which I can appreciate.
However if I recall correctly then most of the issues that you mentioned
were discussed in the BAR BOF. Except for security, I can't remember any
other topic being shown a red flag. Maybe we should not take
"scalability" in a narrow sense, and instead look at research that
enable scalable ad hoc networks, which include reliability etc. And I
haven't encountered any opposition to discussion on QoS etc. on this
list, so why is there a need for new list?

- Sukanta

--

---

From: <[email-masked]>
Date: Tue, 8 Apr 2003 08:15:11 -0400 (EDT)

Dear All,

With regards to scalability ....

I think that before we jump into any conclusions and set up "universal
truths," we need to make sure that we are comparing apples with apples ...

In my understanding, "scalability" is a complex issue and I am not even
sure that we all mean the same thing .... I think that we all understand
that scalability means that we increase SOMETHING#1 and that this increase
has an effect on SOMETHING#2. But what these SOMETHING#1 and SOMETHING#2
are may not be universally agreed upon. To be more specific, we can talk 
about SOMETHING#1 as the number of nodes in the network (probably the 
common conception), but it can also be the coverage area of the network 
(i.e., the size of the network), the density of nodes, etc. Similarly,
SOMETHING#2 could be the delay or throughput (again, probably the common
conception), but it could also be the processing (computational) load, the
increase in the amount of control traffic (i.e., network management cost,
the energy usage (i.e., network lifetime), etc.

Therefore, maybe the right approach would be to set up a set of
independent parameters (the SOMETHING#1's) and the set of matrics (the
SOMETHING#2's). I.e., both SOMETHING#1 and SOMETHING#2 are *vectors*.

Not to even mention the issue of what we define as "scalable."
Gupta and Kumar in their paper discussed scalability of the end-to-end
throughput of wireless ad hoc networks and concluded that it behaves as
O(1/sqrt(N)), where N is the number of nodes in the network. Is this
scalable? Probably not. So what could we define as scalable? Maybe the 
right thing is to talk about relative scalability, rather than in absolute 
terms; i.e.,  to compare the scalability of one protocol vs. another. With 
this approach, we could say, for example, that protocol#1 is more scalable
than protocol#2, when scalability is defined as the increase in the
end-to-end delay with the increase in the node density.

And further, all this would be meaningless, if we do not state the
conditions of such an evaluation. For example, what is the mobility model
(some protocols will behave differently in stationary environment, vs.
highly mobile environment), or what is the transmission/propagation
models, etc, etc, etc.

In other words, I think that the first step would be for us to precisely 
define what is it that we want to evaluate and to "synchronize" our terms.

With regards to the "charter" of the group ... I think that we should
expand it to more than just the scalability issue. I, for one, would like
to see some discussion about QoS, security, etc.

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: Sukanta Kumar Hazra <[email-masked]>
Date: Tue, 8 Apr 2003 20:42:48 +0800

Jakob,

> 7 Candidates for "Known Facts" concerning MANETS

You obviously mean global flooding right.

> in the limit, a two-level hierarchy is almost flat anyway.

I couldn't agree more.
> as nodes change position in the network, so there may be a

Its a strong SHOULD. If addresses change frequently, then we could have
a lot of issues there. Maintaining TCP session comes to mind.

> there can be no reliance on centralized services.

Agree.
> layer scalability and a natural transport layer will follow.

"irrelevant"!

> or equiv. even for rough guidance, may be very harmful for large

But it may be less complex.

> for and against those mentioned above. Flame away, =)

Another "absolute truth" is that the network (ad hoc or otherwise) is
there for applications. Most applications at present are based on the
client-server model (not distributed). Some application frameworks such
as peer-to-peer are more suited to ad hoc networks, since they localize
the communication. It is something that we must keep in mind, though
this group is not working on application frameworks.

Yet another "absolute truth" is that there should be mechanisms to take
into account node capabilities (power, willingness to route, cpu
cycles), in essence some policy based routing.

- Sukanta

---

From: Sukanta Kumar Hazra <[email-masked]>
Date: Tue, 8 Apr 2003 20:22:34 +0800

A
PGP-ID: 0x8E084AD5
Key-Fingerprint: 9C0D B00C C62A 7059 5314  99FC CE90 478A 8E08 4AD5
Shubhranshu,

> a better SCALABLE candidate,  but then here SCALABLE means millions of

Hmm... that is where the argument starts. "AODV has been shown to be a
better SCALABLE candidate", using which metric? I am not against having
a metric which I could refer to when making those statements. A standard
metric and scenarios are most welcome.

> > possible to allow the discussion to go in this direction?

I wouldn't mind any discussion as long as it is related to MANET on this
list. Whether that is the direction (main focus?) that this research group
should take is debatable (as is most things).

> focus on ADDRESSING MECHANISM.

Another focus.

> Any discussion which may lead to better scalable network are welcome.

The punch line.

- Sukanta

---

From: Einar Vollset <[email-masked]>
Date: Tue, 8 Apr 2003 13:59:19 +0100

Sukanta,

On Tuesday, Apr 8, 2003, at 13:12 Europe/London, Sukanta Kumar Hazra 
wrote:
> were discussed in the BAR BOF.

Unfortunately I was unable to attend the BOF, and have been unable to 
find any
description of what was discussed. I base most of my assumptions about 
the
subgroup's research goals from the charter:
http://www.flarion.com/ans-research

> Except for security, I can't remember any
> other topic being shown a red flag.

Forgive my ignorance, but do you mean red flag as in: Not in scope of 
ANS?

> Maybe we should not take

If this is the case, then you're right, there isn't a need for another 
forum, however
reliability and scalability in my limited experience tends to (at least 
initially)
be orthogonal issues, so providing reliability doesn't necessarily 
enhance
scalability, quite the contrary. I think the same might be the case 
with security,etc.
It would at the very least be constraining if the only research into 
reliability, Qos,
security, etc that can be discussed is that which enhances scalability.

I'd like to hear the chairs' opinions on this?

Cheers,

Einar

---

From: Sukanta Kumar Hazra <[email-masked]>
Date: Tue, 8 Apr 2003 21:43:53 +0800

I support any work that would define scalability and provide a
scalability metric along with a set of scenarios to evaluate scalability 
of MANET routing protocols. I see that as the first step towards
scalability research.

- Sukanta

---

From: Richard Ogier <[email-masked]>
Date: Tue, 08 Apr 2003 09:11:02 -0700

> end-to-end delay with the increase in the node density.

Or we could define a protocol to be scalable if it achieves (on the order of)
the theoretically best achievable scalability. For example, to achieve
scalability with hierarchical routing, we would need O(log N) levels.
A 2-level hierarchy is "more scalable" than a 1-level hierarchy but
is not scalable in the above sense. 

On another topic, I don't think that the total amount of traffic (or the
number of streams) is an independent scalability parameter.  
For example, maybe it should be assumed to be proportional to the number 
of nodes in the network (to simplify the definition).
Someone mentioned that AODV has been shown to be scalable with
light traffic.  If that means keeping the number of streams constant
while increasing the number of nodes, then I would not call that
scalable. 

Richard

---

From: Shubhranshu <[email-masked]>
Date: Wed, 09 Apr 2003 20:00:27 -0800

Dear Mr. Sukanta

> metric and scenarios are most welcome.

You may like to check "S.J. Lee et al" paper.
As pointed out by Mr. Anders Nilsson  on 8th April ----
" S.J. Lee et al. showed that AODV could scale to very larger network. 
When the amount of traffic was fairly low. Pure proactive schemes, 
except maybe LANMAR,  all tend to scale poorly."

Warm Regards
Shubhranshu Singh