Subject: RE: [manet] IP addresses in MANET

From: "Manfredi, Albert E" <[email-masked]>
Date: Tue, 25 Jun 2002 12:43:28 -0400

I've heard this concept before, to use unrelated IP addresses in a MANET.

Two problems come to mind, unless I'm missing something.

1. If the MANET becomes connected to the Internet, how will that work?

2. This appears to be a flat address space in effect, just like creating a Layer 2 catenet. Not sure how this differs from IEEE 802.11 in ad-hoc mode, for example.

Bert

> -----Original Message-----
> From: Dario Bottazzi [mailto:[email-masked]]
> Sent: Tuesday, June 25, 2002 12:24 PM
> To: [email-masked]
> Subject: [manet] IP addresses in MANET
> 
> 
> In my opinion some addressing scheme inspired from Virtual IP 
> would be really 
> useful in MANET framework: we might think to bind real IP 
> addresses to the 
> locality (or to a cluster) and this could reduce most of the 
> network traffic 
> related to routing management. (Routing tables would change 
> with a lower 
> frequency) 
> If the Virtual IP (the name of the node) doesn't change even 
> iin the case of 
> a migration it is possible for the others to track its 
> movement and to use 
> the services it shows as soon as it reconnects somewhere into 
> the MANET.  
> Is it meaningfull? I'd like to have your opinion...
> regards 
>      Dario

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

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 07:28:55 -0600

Hi Dario,

I agree that using some form of hierarchal addressing scheme can improve
routing efficiency in moderately large MANETs.

The IP address in the Internet is hierarchal.  Each node is given an address
that reflects its position in the topology of the Internet, much as State
and City reflects a person's location within the US.  This allows for
efficient routing, as you point out, by reducing the need for propagating
local detail to other routers.  

Because Internet nodes do not typically move a lot, a node can be given a
permanent address.  The problem with the MANET is that because the nodes are
in motion, any hierarchal clustering would have to be dynamic in order to
aid routing.  If MANET nodes have permanent addresses, it is simple to know
which node to look for, but not where to look for it.  On the other hand, if
a node is given an address that reflects its location in the net, then the
system has to resolve that address with a more permanent label.

The analogy I use is that you are trying to find someone who is staying in a
hotel.  You may know the city and the hotel name, but at some point you end
up talking to the front desk to find out which room Joe Smith is staying in.
Joe's name (plus some other information) is a permanent label, but you need
to know more information to find him.  The desk clerk performs the final
"address" resolution.

Another way to look at this is the IP addresses perform two functions:  1)
they uniquely identify a node, and 2) they allow efficient routing by
encoding a clustering scheme.  In a MANET, these two functions are distinct.

In the general MANET, we are not able to bind a real IP address to a
cluster.  A cluster reflects a configuration of the dynamic topology.  It
has no permanent identity or even assurance of existence.  As the nodes
within the MANET move, clusters split and merge.  The roles of a given node
change.  A node may be a cluster head one minute and a guest in a different
cluster the next.  If we assign a IP address to a location, then what
happens if two clusters move into that location?  What if no clusters are in
a location?  (If we have fixed locations we can reference, we do have a
simpler problem, but this is not guaranteed in a MANET).  Worse than that, a
specific node will be given different IP addresses as it moves through the
topology.  This complicates the problem of identification.

So far, one scheme I've seen involves giving each node a permanent IP
address plus a MANET suffix.  The suffix is used to find the node and the IP
address to identify it.  Alternatively, one can propagate throughout the net
(either proactively or on demand) a cross-reference table that matches up IP
and MANET addresses.

This is not to say that binding IP addresses to a cluster or locality will
not work in some situations.  However, that would be a special situation
and, some would say, not a MANET, but a stub network, instead.

John Mullen

-----Original Message-----
From: Dario Bottazzi [mailto:[email-masked]]
Sent: Tuesday, June 25, 2002 10:24 AM
To: [email-masked]
Subject: [manet] IP addresses in MANET

In my opinion some addressing scheme inspired from Virtual IP would be
really 
useful in MANET framework: we might think to bind real IP addresses to the 
locality (or to a cluster) and this could reduce most of the network traffic

related to routing management. (Routing tables would change with a lower 
frequency) 
If the Virtual IP (the name of the node) doesn't change even iin the case of

a migration it is possible for the others to track its movement and to use 
the services it shows as soon as it reconnects somewhere into the MANET.  
Is it meaningfull? I'd like to have your opinion...
regards 
     Dario

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 09:12:11 -0600

Thanks Dario,

But, I'm no expert.  I'm just trying to figure this stuff out myself.

John Mullen

-----Original Message-----
From: Dario Bottazzi [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 8:39 AM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

Dr. Mullen
     thank you for the clear and deep answer you have given me. I agree that

my approach isn't general but I think that it maight fit many real life 
situations.  I think that the approach I have expressed (it's only an 
idea...) shows two interesting points:

- We have to think to cluster (o locality aware) solutions
- It might be possible to bind the IP to the location (and assign it 
dynamically) and to keep "something" (a second address) fixed. If I search 
for Mario Rossi in any hotel in Bologna, I know that he can change hotel... 
but the person I am looking for is always Mario. 

Anyway I will read again the answer you gave me. 

many thanks 
     dario

> The analogy I use is that you are trying to find someone who is staying in
> a hotel.  You may know the city and the hotel name, but at some point you
> end up talking to the front desk to find out which room Joe Smith is
> staying in. Joe's name (plus some other information) is a permanent label,
> but you need to know more information to find him.  The desk clerk
performs
> the final "address" resolution.
>
> happens if two clusters move into that location?  What if no clusters are
> in a location?  (If we have fixed locations we can reference, we do have a
> simpler problem, but this is not guaranteed in a MANET).  Worse than that,
> a specific node will be given different IP addresses as it moves through
> the topology.  This complicates the problem of identification.
>
> address plus a MANET suffix.  The suffix is used to find the node and the
> IP address to identify it.  Alternatively, one can propagate throughout
the
> net (either proactively or on demand) a cross-reference table that matches
> up IP and MANET addresses.
>

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 09:12:11 -0600

Thanks Dario,

John Mullen

-----Original Message-----
From: Dario Bottazzi [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 8:39 AM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

Dr. Mullen

many thanks 
     dario

performs
the

---

From: "Su, William" <[email-masked]>
Date: Thu, 27 Jun 2002 14:23:32 -0400

I would think that one possible factor that determines whether to use
cluster or not is the mobility rate.  Hierarchical cluster schemes would
reduce network traffic if all the nodes within the locality are fairly
stable, but if they tends to move around different clusters a lot then there
could be significant routing overhead.  

Typical non-cluster routing schemes like AODV, DSR and such are good for
small to medium size networks that are fast moving, although they are
probably not as scaleable as the cluster or hierarchical approach.  It would
seem like as the network size becomes larger and larger, something like ZRP
or Fisheye would have to be used.

-Bill

---

From: "Su, William" <[email-masked]>
Date: Thu, 27 Jun 2002 14:23:32 -0400

-Bill

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 13:08:56 -0600

Hi Bill,

As I understand it, hierarchical clustering can help manage an unstable
topology.  

The idea in clustering is that a cluster becomes a supernode.  The details
of what goes on within that supernode are hidden from the rest of the
network as much as possible.  Consequently, changes in topology of local
interest remain within the cluster, reducing the OH associated with routing
updates.  

For example, suppose Node A, along with four or five other nodes, is in
Cluster 1.  If I want to send a packet to Node A, all I need to know is it
is in Cluster 1.  Once it hits the cluster, the local mechanism gets the
packet to A.  So, A can move around within the cluster all it wants to and
the only thing that is affected is local (one hop) routing.  There is no
need to advise the rest of the net of these changes.  

Of course, some changes are of general interest.  Any time a node leaves or
joins a cluster, for example.  However, these changes are usually less
frequent, and given the instability of connections in some wireless nets,
this can greatly reduce the number of net wide updates.

Furthermore, under next-hop routing, even some cluster changes need not be
propagated network wide.  For example, suppose I reach Node A via cluster 7,
which goes to Cluster 4, then Cluster 1.  If Node A moves to Cluster 2,
which is also reachable from Cluster 4, then my next hop doesn't change and
the update need not go beyond the controller for Cluster 4.

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 12:24 PM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

-Bill

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 13:08:56 -0600

Hi Bill,

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 12:24 PM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

-Bill

---

From: "Yasser A. Lotfy" <[email-masked]>
Date: Thu, 27 Jun 2002 16:54:38 -0400

Good day everybody,

I've been following on the IP addressing proplem, and want to contribute some thoughts
1) I believe ad hoc will adopt IPv6. Since no comercial solution is available for ad-hoc, it makes absolute sense to use IPv6 for addressing. This solve the problem of "Internet running out of space" and introduce the problem of "Personal IP" which is global vs local IP

2) Assigning "pool of addresses" for an ad-hoc network is so difficult in the absense of central authority. This means that nodes will have to announce an IP address when joining the network, get authenticated (how the authentication could be done is a different issue), then the nodes can move within the same ad-hoc freely by keeping their IP.

3) Local traffic (within the same ad-hoc) can be routed easly. Internet traffic will be subject to (gateway address resolution). Since many gateways may work for the same ad-hoc, we need to guarantee consistency between all gateways.

This way no central authority is needed which is very consistent with the MANET charter. Also, if an individual nodes has a static IP it should be able to use it. The authentication process can elementate the possibility of IP address conflict.

Hope I made my point clear, any input?

Yasser

Carleton U
Ottawa Canada

____________________________________________________________
Win a first-class trip to New Orleans and vacation Elvis Style!.
Enter NOW!
http://r.lycos.com/r/sagel_mail/http://www.elvis.lycos.com/sweepstakes/

---

From: "Manfredi, Albert E" <[email-masked]>
Date: Thu, 27 Jun 2002 17:06:42 -0400

I agree with the thrust of what Yasser says below, which is why I initially offered that MANET addressing would in effect be a flat address space, at least as long as the packets remain within the MANET.

IPv6 would be nice because it supports autoconfiguration. Perhaps, for example, an IP address prefix could be added to the IP addresses used in the MANET by whatever gateway(s) might connect the MANET to the Internet. Meanwhile, a unique MAC address embedded in the IPv6 address would guarantee address uniqueness within the MANET, and then in the Internet.

But these are just words. Exactly how one keeps multiple gateways from sending duplicate packets to the Internet, for instance, is not clear to me. As well as a host of other issues.

Bert

> From: Yasser A. Lotfy [mailto:[email-masked]]
> Sent: Thursday, June 27, 2002 4:55 PM
> To: Rex Buddenberg; Kuldip Singh Pabla; Charles E. Perkins
> Cc: [email-masked]
> 1) I believe ad hoc will adopt IPv6. Since no comercial 
> solution is available for ad-hoc, it makes absolute sense to 
> use IPv6 for addressing. This solve the problem of "Internet 
> running out of space" and introduce the problem of "Personal 
> IP" which is global vs local IP
> 
> 2) Assigning "pool of addresses" for an ad-hoc network is so 
> difficult in the absense of central authority. This means 
> that nodes will have to announce an IP address when joining 
> the network, get authenticated (how the authentication could 
> be done is a different issue), then the nodes can move within 
> the same ad-hoc freely by keeping their IP.
> 
> 3) Local traffic (within the same ad-hoc) can be routed 
> easly. Internet traffic will be subject to (gateway address 
> resolution). Since many gateways may work for the same 
> ad-hoc, we need to guarantee consistency between all gateways.
> 
> This way no central authority is needed which is very 
> consistent with the MANET charter. Also, if an individual 
> nodes has a static IP it should be able to use it. The 
> authentication process can elementate the possibility of IP 
> address conflict.
>

---

From: "Manfredi, Albert E" <[email-masked]>
Date: Thu, 27 Jun 2002 17:49:48 -0400

Fred L. Templin wrote:
>
> Hi Bert,
> 
> Manfredi, Albert E wrote:
> > But these are just words. Exactly how one keeps multiple
> > gateways from sending duplicate packets to the Internet,
> 
> I'm not sure I'm interpreting your concern correctly, but
> I don't think there should be any such issue when multiple
> IPv6 gateways within the MANET peer with the Internet. Nodes
> that send packets (and/or intermediate forwarding hops) will
> eventually pick one such gateway as the final next hop before
> the packet leaves the MANET. The unicast MAC address of the
> gateway is then placed as the destination MAC address in the
> forwarded packet, so only one border gateway will do the
> forwarding and duplicates should not arise.

Hmmm. I was thinking that the IP DA of the packet destined to the Internet would be the IP DA of that host out there, in the Internet. And that there would be a good likelihood that several gateways to the Internet could see that packet, and add their own prefix to the IP SA, before sending it on. So the packets would seem different out there, within the wired Internet.

Are you saying that the packet transmitted by the MANET host is encapsulated in another packet, with the gateway's MANET address on it? I suppose you could establish that sort of initial transaction, before transmitting to the outside world. As the MANET host moves, it would have to be aware of changes to the gateway to the Internet.

Bert

---

From: "Su, William" <[email-masked]>
Date: Thu, 27 Jun 2002 17:55:14 -0400

John,

Very good point. I think I totally agree with you on the benefit of
hierchical scheme :)

The scenario I was thinking is the situation when all nodes in the field are
moving very rapidly in different random directions.  For this case, it would
seem that a lot of clusters would have to be created/modified.  Therefore
the bulk of overhead actually becomes cluster maintainence (cluster head
election, gateway nodes selection, .etc) rather than routing updates.
Although the routing info probably also needed to be propagated more
frequently to keep up with the fast changing clusters.

I guess I may be thinking of an "extreme" case that the mobility speed is so
high each cluster stays intact for only a very short amount of time, and all
its members are constantly joining/dropping rapidly.  Although I'm not so
sure at what mobility threshold using cluster in this case will generate too
much cluster maintainence overhead.  Perhaps there are some MANET papers
that have insights in this area?  

IMHO, I think cluster based approach would definitely work very well in a
situation when the mobility pattern for a certain cluster or group is
similar (i.e. a squad based cluster).  If there are no group mobility
behavior, there is a possibility that cluster maintaince might actually
congest the network.

I would also suspect that factors such as cluster size, radius, and the
efficiency of cluster maintenance scheme are important.  I think it would
probably be an interesting study? :)

-Bill

-----Original Message-----
From: Mullen, John P. (Contractor)
[mailto:[email-masked]]
Sent: Thursday, June 27, 2002 3:09 PM
To: Su, William; [email-masked]
Subject: RE: [manet] IP addresses in MANET

Hi Bill,

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 12:24 PM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

-Bill

---

From: "Su, William" <[email-masked]>
Date: Thu, 27 Jun 2002 17:55:14 -0400

John,

-Bill

-----Original Message-----

Hi Bill,

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 12:24 PM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

-Bill

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 16:32:24 -0600

Hi Bert,

Well, this is something I'm not too familiar with, but I suspect the
Originator will send out a request for information and then select one of
the possible paths after getting replies (in ad-hoc routing).  Details vary
by protocol, but this is the usual situation within the MANET.  

For a MANET to work, you must have sufficient hosts in an area to have
connectivity.  To have a stable MANET, you need more hosts than absolutely
necessary.  Otherwise, your MANET will be frequently partitioned due to a
lack of redundancy.  As a result, it is a routine MANET problem to prevent
multiple paths by selecting from among the available hosts, the hosts to
use.

I am assuming here that the gateway nodes would appear to be MANET nodes
from the MANET side, so they would probably be treated as any other MANET
node in this respect.  The originator would see each reachable gateway as a
candidate node and simply pick one.  The others, being well-behaved MANET
nodes, would simply discard packets not intended for them.

I'm also assuming that, from the perspective of the MANET, every Internet
gateway is about as good as every other Internet gateway on the Internet
side.  That is, the capacity of Internet links would be so much greater than
those within the MANET, that the control scheme could consider the gateway
as the next-to-last node.

John Mullen

P.S.

I must sign off for now, but will be back tomorrow.

-----Original Message-----
From: Manfredi, Albert E [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 4:11 PM
To: 'Mullen, John P. (Contractor)'
Subject: RE: [manet] IP addresses in MANET

John,

I think that as long as everyone is in the MANET, what you describe probably
works. But how are hosts told what the available gateways are?

Bert

> Sent: Thursday, June 27, 2002 6:02 PM
> To: Manfredi, Albert E
> Well, I can help you with the last point.
> 
> The trick in a MANET is that each node has the potential to 
> be a router, but
> the protocol selects just certain nodes to act as routers.  
> As the topology
> changes, different nodes become or cease being routers, as 
> needed.  What
> each protocol tries to do is maintain the minimum number of 
> active routers
> necessary to provide the required level of service.  
> Otherwise, too many
> nodes will transmit and channel utilization will go up.
> 
> The same is true for messages to the Internet.  Whatever 
> protocol is used,
> its job will be to assure that just one Internet gateway, of those
> available, is selected as the gateway to use.
> 
> As for the mechanism, there are two basic ways: route 
> specification, as in
> DSR, or routing tables, as in AODV.  In the first case, the 
> packet contains
> the complete path from source to destination.  In the second, 
> each node
> maintains a table of actions for each source and destination.
> 
> Suppose the path A-B-C-F is to be used.  (F can be the 
> gateway).  Under DSR,
> the path A-B-C-F is in the packet.  When a node receives a 
> packet, there are
> just three possible actions (ignoring the complication of 
> broken links).
>    1.  Process the information in the packet because it is 
> addressed to it
> (Node F),
>    2.  Rebroadcast the packet, if both 
>           a.  The node is on the path, but not the 
> destination (Nodes B, C)
> and
>           b.  The packet has not been received before.
>    3.  Discard the packet, if either
>           a.  The node is not on the list, or
>           b.  The node is on the list, but previously 
> broadcast the packet.
> As you can see, each node on the path will (assuming connectivity)
> re-broadcast the packet once and only once.  Furthermore, 
> only Node F will
> accept the packet as intended for it.  Any other gateway in 
> the area will
> just discard the packet.
> 
> Now, with routing tables, each node maintains an entry for 
> each possible
> destination.  So, at Node B is the entry "C" for Destination 
> F.  When Node B
> receives the packet, it places C's address in the next-hop 
> position and
> re-broadcasts it.  Any other node in the area will discard the packet
> because it is not the next node.  At Node C, the next node is 
> F, the process
> is repeated with "F" as the next-node, and F gets the 
> message.  In this
> case, the rules are:
>    1.  Process the information in the packet if the node is 
> the destination
> (Node F),
>    2.  Rebroadcast the packet with an appropriate next-node 
> entry, if both 
>           a.  The node is the "next-Node," but not the 
> destination (Nodes B,
> C) and
>           b.  There is an entry for that destination in the 
> Node's routing
> table (if not, it is broken link time).
>    3.  Discard the packet, if the packet is not addressed to the node.
> Again, only one gateway will get the packet and all is well 
> with the world.
> 
> John Mullen
> 
> From: Manfredi, Albert E [mailto:[email-masked]]
> Sent: Thursday, June 27, 2002 3:07 PM
> To: [email-masked]'
> Cc: [email-masked]
> I agree with the thrust of what Yasser says below, which is 
> why I initially
> offered that MANET addressing would in effect be a flat 
> address space, at
> least as long as the packets remain within the MANET.
> 
> IPv6 would be nice because it supports autoconfiguration. Perhaps, for
> example, an IP address prefix could be added to the IP 
> addresses used in the
> MANET by whatever gateway(s) might connect the MANET to the Internet.
> Meanwhile, a unique MAC address embedded in the IPv6 address 
> would guarantee
> address uniqueness within the MANET, and then in the Internet.
> 
> But these are just words. Exactly how one keeps multiple gateways from
> sending duplicate packets to the Internet, for instance, is 
> not clear to me.
> As well as a host of other issues.
> 
> Bert
> 
>

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 16:32:24 -0600

Hi Bert,

John Mullen

P.S.

-----Original Message-----
From: Manfredi, Albert E [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 4:11 PM
To: 'Mullen, John P. (Contractor)'
Subject: RE: [manet] IP addresses in MANET

John,

Bert

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 16:33:51 -0600

Hi Bill,

I think it could go either way, depending on the nature of the MANET.

The advantage of clustering is that you can keep some information local.
Even in a very dynamic situation, not all changes need be propagated
throughout the net.  However, there is a certain amount of OH involved and
it could be that under certain circumstances, the OH would cut into
available BW.

However, in checking this out, we would have to consider the total effect of
clustering.  It is not just that one keeps local changes more-or-less local,
but also that the resulting hierarchal structure makes routing more
efficient.

There is also another factor.  Some protocols (e.g. AODV) maintain only
active routes.  In a very dynamic network of n nodes in which only a few of
the n-squared possible routes are used, clustering might have less value
than in a network in which a large fraction of possible source-destination
pairs are active.  

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 3:55 PM
To: Mullen, John P. (Contractor); [email-masked]
Subject: RE: [manet] IP addresses in MANET

John,

-Bill

-----Original Message-----

Hi Bill,

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 12:24 PM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

-Bill

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Thu, 27 Jun 2002 16:33:51 -0600

Hi Bill,

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 3:55 PM
To: Mullen, John P. (Contractor); [email-masked]
Subject: RE: [manet] IP addresses in MANET

John,

-Bill

-----Original Message-----

Hi Bill,

John Mullen

-----Original Message-----
From: Su, William [mailto:[email-masked]]
Sent: Thursday, June 27, 2002 12:24 PM
To: [email-masked]
Subject: Re: [manet] IP addresses in MANET

-Bill

---

From: "����" <[email-masked]>
Date: Fri, 28 Jun 2002 12:02:38 +0800 (CST)

Hi John:

  I think what Bill referred is the clustering problem of hierarchical MANET. In some situation, bad parameterized cluster maintenance such as cluster-split, cluster-merge may induce more OH than routing protocol. However, I see no reasonable default parameter such as cluster size, cluster merge/split threshold can be fitted for all real networks. So a hierarchical MANET’s performance is not promising. Am I right? Or is there any reference parameter for hierarchical MANET implementation?
  There is another question aroused in my brain: Is there a nodes-limit for MANET? That is: can MANET support more than thousands of nodes or even tens of thousands of nodes? I heard that UBC has build a Ad hoc sensor network of 800 nodes; however, I think there is difference between sensor network and MANET, for sensor network has little message to transfer on the net, OH is not a big problem. In a very big MANET, with its mobility nature, I doubt any scheme , neither flat nor hierarchical, would work. If there is a limit, do we have a value this society agreed on?  With this in mind, I think it will be better for us to discuss the hierarchical or flat MANET.

BR
Hai Wang

---

From: "����" <[email-masked]>
Date: Fri, 28 Jun 2002 12:02:38 +0800 (CST)

Hi John:

BR
Hai Wang

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Fri, 28 Jun 2002 08:12:40 -0600

Hi Hai Wang,
 
You have a lot of statements here, so I'll comment on them one at a time.
 
[Hai Wang] I think what Bill referred is the clustering problem of
hierarchical MANET. In some situation, bad parameterized cluster maintenance
such as cluster-split, cluster-merge may induce more OH than routing
protocol. 

[John M]  Regardless of what protocol we pick, there will be a set of
circumstances under which it will not perform well.  In Computer Science,
people tend to look at the worst case and ask if that is tolerable.  In
Industrial Engineering (my field), we also look at average performance.
This involves a bit more understanding of the situation in that we have to
figure out how likely the worst case (and other cases) are.  So, if there is
a set of circumstances under which a protocol will do badly, but those
circumstances are very very rare, we may still use the protocol.  
 
Any form of organization will work best when it coincides with the situation
and worst when it does not.  Essentially, a set of instructions is trying to
guess which organization will be best, based on the observed network state.
Every once in a while, it will be wrong.  However, if it is better than the
alternatives, including no clustering, we would still tend to use it.
 
[Hai Wang] However, I see no reasonable default parameter such as cluster
size, cluster merge/split threshold can be fitted for all real networks. So
a hierarchical MANET’s performance is not promising. Am I right? Or is
there any reference parameter for hierarchical MANET implementation?
 
[John M]  The term "MANET" describes a tremendous variety of rather messy
networks.  Additionally, the equipment in use has some impact on cluster
size and design.  In a large MANET, local conditions can vary, so in some
regions, a larger cluster size might be advisable.  Finally, traffic
patterns interact with clustering.  It is unlikely that a single default
parameter would be acceptable for all MANETs.  However, it is likely that a
single initial value will be good starting point and that heuristics can be
found to locally optimize cluster size.  After all, we have to find
something for hungry graduate students to do.
:-)

Also, there are a number of clustering schemes, so parameters for one would
differ from those of another. Martha Steenstrup discusses a number of these
in "Cluster-Based Networks," [Ad Hoc Networking, by Charles Perkins, Chapter
4].  Her discussion does a good job of describing the protocols and showing
how technology, traffic patterns, and geographical dispersion impact and are
impacted by different clustering methods.
 
[Hai Wang]  There is another question aroused in my brain: Is there a
nodes-limit for MANET? That is: can MANET support more than thousands of
nodes or even tens of thousands of nodes? I heard that UBC has build a Ad
hoc sensor network of 800 nodes; however, I think there is difference
between sensor network and MANET, for sensor network has little message to
transfer on the net, OH is not a big problem. 

[John M] I have heard of working MANETS up to 1000 nodes in size.  This is
1000 hosts, almost all of which are operated by people communicating with
each other.  Conceptually, there is no limit, though practically speaking
there probably is one.  Of course, special circumstances can reduce the
complexity of the problem.  For example, if a MANET consists of ten teams of
100 hosts, each team of which is organized into five units, and if these
teams and units tend to travel together, say as in an emergency relief
operation, then a clustering by organizational unit seems logical and would
probably work.  Given a "nice" situation, there would be no practical limit
to the MANET, though purists would probably call it a very tame one.
 
[Hai Wang] In a very big MANET, with its mobility nature, I doubt any scheme
, neithe! r flat nor hierarchical, would work. If there is a limit, do we
have a value this society agreed on? With this in mind, I think it will be
better for us to discuss the hierarchical or flat MANET.

[John M]  There are probably circumstances under which a flat MANET is
preferable to a hierarchical one, but I think you have the size factor
backwards.  Hierarchal clustering tends to localize the impact of state
changes, so it tends to be more useful in larger nets than in smaller ones.
If each node is one or two hops away from every other node, probably
clustering is not worth the OH.  However, if the net diameter is ten or
twenty hops, something is needed to reduce the size of the routing problem
and clustering seems to be one way to do it.  If there is a limit to MANET
size, it will be a practical one, set by limitations of the media and
technology.  I think that is too much of a moving target to set a value at
this point.

BR
Hai Wang

> There is also anot! her factor. Some protocols (e.g. AODV) maintain only
> active r outes. In a very dynamic network of n nodes in which only a few
of

---

From: "Mullen, John P. (Contractor)" <[email-masked]>
Date: Fri, 28 Jun 2002 08:12:40 -0600

Hi Hai Wang,

 

 

BR
Hai Wang

of

---

From: "����" <[email-masked]>
Date: Sat, 29 Jun 2002 16:48:46 +0800 (CST)

Hi John:
 Thanks for your detailed explaining. I agree with you in most part, except:
[John M]  …Given a "nice" situation, there would be no practical limit to the MANET,....

  I think there is a limit to the MANET.  Wireless is different from wired, its bandwidth is limited, and it can hardly to make a breakthrough. No matter what structure, what algorithm you use, when the number of nodes increases, the routing OH or clustering OH will increase steadily(except we use autonomous region concept in MANET :) ). At last, the OH will eat up the bandwidth. Just before that, when there is some point where the link quality is bad, the OH will choke the traffic too, make the performance unacceptable. So, I think that the size limit of a MANET may depend on smallest link bandwidth in a network. For hierarchical scheme, the bandwidth of links among cluster heads will be of great concern. Perkins has shown that there is a 10000 nodes network under test, however, he did not show us the bandwidth he use. 10000 is a rather astonishing number to me :) 

BR.
Hai Wang