Subject: Re: [manet] Comments on draft-jelger

From: [email-masked]
Date: Tue, 02 Sep 2003 17:19:11 -0700

Christophe,

I want to add one thought regarding how to handle nodes that
are too far from all gateways.  These can be treated like
"drifters" in LANMAR (where gateways assume the role of landmarks):

  http://www.watersprings.org/pub/id/draft-ietf-manet-lanmar-05.txt

Thus, a node that is too far from all gateways can select the nearest
gateway (since gateway advertisements can be propagated such that every
node knows at least one gateway), and the method in the above draft 
can be used to maintain a path from the selected gateway to the 
faraway node, using distance-vector routing.

The other method (mentioned below) is for the faraway node to increase
the number of hops that its routing advertisements propagate, to ensure 
that the gateway knows a route to the node.  The LANMAR "drifter" 
approach might be more efficient, but the other method might be simpler 
and more robust, and can use the underlying proactive routing protocol 
instead of introducing an additional distance-vector mechanism. 
Note that, unlike in the LANMAR draft, we do not expect a "drifter"
to very far from the gateway, since it can select the nearest gateway.

Regards,
Richard

<SNIP>

> > > The idea of a hop-radius (or "routing scope") from Landmark routing 
> > > can also be applied to the problem we are considering.
> > > For example, suppose there is one huge manet (say with a diameter
> > > of 100 hops), which has several internet-gateways.
> > > Thus, even though one manet node may be be able to reach another
> > > manet node using a 100-hop path, it would be desirable to limit
> > > the routing scope to K hops (where K might be 5), such that
> > > every node is within K hops of some internet-gateway.
> > > Then, each manet node would select a gateway that is within
> > > K hops and use the prefix advertised by that gateway.
> > > The node would have to change its prefix only if it moves
> > > more than K hops from the gateway it selected.
> > 
> > This idea is also quite good, we thought about such thing but finally decided
> > not to incorporate this in this version of the draft, mainly because we could
> > not find a solution for nodes that were "too far" from all gateways. If we 
> > limit the distance to, say K hops, what happens for a node that is K+1 hops
> > from all possible gateways ? I think it is not acceptable to ignore such a 
> > node, so the "K hops" rule has to be broken ... and if we can find exceptions, 
> > maybe it is because the rule is too strict. Well I cannot find an easy 
> > solution for the K+1 node ... :-(
> 
> I agree that we should not ignore a node that is too far from all
> gateways, but I don't think it is difficult to handle such exceptions.  
> For example, a manet node that is not within range of any gateway can 
> increase its routing scope (distance that its routing advertisements 
> propagate, whether link-state or distance-vector) until it is within
> range of some gateway, so that the gateway will know a route to the node.
> In the reverse direction, gateway advertisements can be propagated in a 
> manner that ensures every node knows about at least one gateway 
> (no matter how far), but also knows all gateways that are within K hops.
> 
> Regards,
> Richard
> 
> > > It is also possible for a manet node to select multiple gateways
> > > that are within K hops, and to have multiple prefixes.  
> > > Note that the above approach makes it unnecessary to divide
> > > the manet into well-defined areas or clusters:
> > > The set of all nodes affiliated with a given gateway need
> > > not be contiguous. All nodes within K hops of a gateway receive 
> > > advertisements from the gateway, but may decide to use the prefix 
> > > advertised by another gateway that is also within K hops.
> > > 
> > > Regards,
> > > Richard
> > > 
> > 

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

---

From: [email-masked]
Date: Sat, 06 Sep 2003 08:38:59 -0700

To Christophe and all,

I thought more about the solution in your draft, and the benefits 
of "prefix continuity".  One of the benefits of prefix continuity 
that I did not consider before is that it allows hop-by-hop default 
routing, without using a routing header to specify the gateway.
(This is because the default next-hop router has the same prefix 
and thus has a consistent default route.)

Also, I understand that your method minimizes the number of prefix 
changes, given that you want to maintain prefix continuity.  
(For example, it requires fewer changes than if a manet node was 
required to always select a nearest gateway and use its prefix.)  
I think it would be better to allow changing the prefix if 
another gateway becomes *much* closer, but my main point in
this message is whether or not prefix continuity should be
required.

I see three possible solutions, depending on whether prefix continuity 
is required, and on whether a packet routed to the internet must go 
thru a gateway having the same prefix as the sender.
I hope people will comment on which of these three solution
is preferable, and whether any of them (particularly the first one)
is unacceptable.  

1. The default route always uses the nearest gateway, regardless of
   its prefix. Prefix continuity is not maintained.

  Benefit: Hop-by-hop default routing is easy (without routing header).
  Benefit: A manet node does not need to change its prefix to
    maintain prefix continuity.
  Drawback: Gateway prefix may be different from sender prefix,
    which could cause a problem with source address filtering, and 
    the reverse route could go thru a different gateway with a 
    different prefix. (Are these drawbacks acceptable?)

2. The default route is required to use a gateway with the same prefix 
   as the sending node, even if there is a closer gateway, but prefix
   continuity is not maintained. 

  Benefit: Gateway prefix is same as sender prefix.
  Benefit: A manet node does not need to change its prefix to
    maintain prefix continuity.
  Drawback: A routing header (to reach gateway) is required for default 
    routing.  Hop-by-hop default routing is not possible.
   
3. Same as 2, but prefix continuity is maintained.

  Benefit: Gateway prefix is same as sender prefix.
  Benefit: Hop-by-hop default routing is possible (without routing header).
  Drawback: A manet node may need to change its prefix to maintain
    prefix continuity, unlike the first two solutions.

In my opinion, the first solution is best if it is OK to route
the packet thru a gateway with a different prefix, otherwise the 
second solution is best if using a routing header is not considered
a significant drawback, otherwise the third solution is best.

Regards,
Richard

---

From: [email-masked]
Date: Tue, 02 Sep 2003 13:27:57 -0700

Christophe,

Thanks for your response. Please see my futher comments below.

> Hi Richard and thanks for your comments,
> 
> Please check below within your text for my comments. In general, your points 
> make sense and we already considered most of them but we decided to insist on
 
> prefix continuity. There are of course pros and cons in any solution. We 
> decided to favor prefix continuity because the hop-by-hop propagation method 
> that we use naturaly leads to prefix continuity. I think there is no "best 
> method", because topological changes are unpredictable and it is difficult to
 
> simulate and compare different solutions. Well it would be nice to gather 
> comments and ideas from other MANET members, so more comments are very 
> welcome !
> 
> Regards,
> Christophe
> 
> Quoting [email-masked]:
> 
> > 
> > Hi Christophe,
> > 
> > Regarding your new draft, I am not sure that "prefix continuity"
> > is necessary. That is, I am not sure that the set of nodes having 
> > the same prefix needs to be contiguous.  Please consider the 
> > following, and let me know if I am missing something.
> > 
> > It is only necessary for each node to have a route to the
> > gateway(s) it is affiliated with, and for each gateway to have 
> > a route to each node that is affiliated with it.
> 
> - I agree, but that means ad hoc routing must be allowed between nodes with 
> different prefixes. Well that seems ok for me, but in certain cases (for 
> administrative reasons) one might want to forbid routing between "ad hoc 
> subnets".

>From previous discussions on the manet list, I think want to allow
routing between nodes with different prefixes.

> - Prefix continuity also impresses some sort of coherence in the network, with 
> contiguous "prefix islands", and I like organized networks ! ;-)
> - Also when a network partition occurs, it means that nodes that are still on
> the gateway side won't have to change their address.

That's true.  But I think that what I am proposing results in nodes 
changing their prefix less often, since nodes do not have to change 
their prefix in order to maintain prefix continuity.  Also, what I 
am proposing might result in faster recovery from a partition, since a 
node will typically have information for multiple gateways, whereas in 
your method I think that a node typically knows only about one gateway 
unless it is on the boundary between two "prefix islands".
Thus, in your method, a node that is not on the boundary might have to 
wait for gateway information to propagate via Hello messages.

> > One might argue that if the set of nodes with a given prefix 
> > is contiguous, then it is easier to flood a message to all 
> > nodes having that prefix, but I think it is sufficient for a 
> > gateway to be able to perform the following types of flooding:
> > 
> > (a) Flooding to all nodes in the manet.
> > (b) Flooding to all nodes in the manet that are within K hops
> >     of the gateway (where K is such that any node affiliated with 
> >     the gateway is required to be within K hops of that gateway).
> > 
> > Thus, I am not sure it is necessary to go through the trouble to
> > ensure "prefix continuity".
> > A node can simply select the nearest gateway (which can be determined
> > from the information provided by a proactive routing protocol),
> > and use the prefix advertised by that gateway.  The node can keep 
> > that prefix until it no longer has a route to that gateway, or becomes 
> > more than K hops from that gateway, or finds another gateway that is 
> > much closer.
> 
> That's interesting, but with unpredictable topological changes we have 
> prefered to favor prefix stability : don't forget that each time a node 
> changes its address, all transport connections are lost (if nothing like 
> Mobile IPv6 is used).

As I indicated above, it seems to me that prefix stability will be 
improved if nodes do not have to change their prefixes in order to 
maintain prefix continuity. It would be good to conduct simulations to 
compare the two different approaches (with and without prefix continuity).  
Also, it would be good to get comments from other MANET members!

> 
> > My reasoning is influenced by the original paper on Landmark Routing
> > (Paul Tsuchiya, 1987), which I re-read recently.
> > A node can select any landmark node (a landmark is like a gateway)
> > that is within a certain hop-radius of the node, and use the 
> > prefix advertised by that landmark.  There is no requirement that 
> > the set of nodes affiliated with a given landmark be contiguous.
> > A node would have to change its prefix only if it moves too far
> > from the landmark it has selected. It could then select another
> > landmark, or another landmark could be elected, or the hop-radius
> > could be increased.  (Note that I am not suggesting to use
> > landmark routing to deal with internet-gateways in manets.)
> > 

Regards,
Richard