Subject: Re: [manet] Default Routes

From: [email-masked]
Date: Wed, 3 Mar 2004 20:11:10 +0100 (CET)

Hello,

Let me see if I understood the draft correctly.

> However, I have another question. How do you handle "contention" between
> the announcements at the edges of bordering prefix islands?

An upstream node chooses a new or different gateway if it is 1 hop closer
than the one it is currently using.

> I guess that
> borderline nodes have the ability to select gateway by themselves, but
> that could potentially affect many downstream nodes that previously used
> another prefix. A node could also cut off and isolate islands of nodes
> if it chooses to change prefix/gateway.

I think that depends on whether the network is using a reactive or
proactive protocol. If a reactive protocol is used, the routing protocol
is still responsisble for establishing a route to the gateway. In that
case the downstream node would at least not be isolated, it can continue
to use the old gateway. The question is whether the downstream have to
configure a new address when the prefix announced by the upstream node
changes. If that is the case, we might have some problems. As the network
can be very mobile, borderline nodes receiveing announcements about two
different gateways, from two different neighbors, might choose two to
switch back forth between the two gateways. This easily happens when a
node chooses a new gateway when it is 1 hop closer than its current one,
and the network have mobility that causes frequent topology changes.

> What are the convergence times
> for situations like that? Is it desirable that borderline nodes could
> have such a big effect on lots of downstream nodes?
>

I do not think the convergence time is that big, as nodes "almost
immediately" rebroadcasts the message. Before updating it. However, if
nodes have to configure a new address upon receipt of the announcement,
the result can be very bad. I have simulated this, and it helps a lot if
the condition to switch is increased to 2 hops, but that would of course
create non optimal routes.

I am not sure if the draft actually says that nodes should reconfigure a
new  address when your upstream tells you to. If that is so, I am not so
sure that is a wise thing to do. Christophe, please correct me if anything
I say here is wrong.

/Anders

> //Erik
>
> On Wed, 2004-03-03 at 19:12, Christophe Jelger wrote:
>> Erik,
>>
>> (please call me Christophe !)
>>
>> You are right when you say that a node within an "island" can't change
>> its prefix. Our objective is to create these islands, so we don't really
>> want to see a node that breaks this organisation. ;-)
>>
>> I also agree with you that the tunnel-based solution is the best one in
>> terms of control overhead (less control packets sent). I think our
>> proposal has a completely different objective. The only point we try to
>> defend is the concept of prefix continuity : this feature might be of
>> real interest for operators who like to have a somehow organised
>> network. This feature can also allow an operator to do some management
>> control and stuff like that.
>>
>> Regards,
>> Christophe
>>
>> PS : we do not implement a separate flooding mechanism, because this is
>> not flooding !!! (I insist on that !) The information disseminates away
>> from gateways, it look like flooding but it's not ! ;-)
>>
>> Erik NordstrÃ¶m wrote:
>>
>> >Jelger,
>> >
>> >I admit that I am not that familiar with your proposal, and probably
>> >should read it more carefully. However, there are some things I
>> >question...
>> >
>> >For example, why implement a seperate flooding mechanism when this is
>> >already provided by the routing protocol (for example OLSR)? You
>> propose
>> >to optionally integrate this with the routing protocol, but I do not
>> see
>> >how that is possible with MPR-based flooding?
>> >
>> >I am not convinced that you have maximum flexibility when building your
>> >prefix islands of nodes. How can nodes part of a prefix island
>> >individually choose another gateway? But, I admit, I need to study your
>> >draft in more detail.
>> >
>> >With tunnels you can simply add a flag in ordinary control messages
>> >announcing some nodes as gateways. Nodes can then individually choose a
>> >gateway and tunnel packets to it. The routing protocol takes care of
>> the
>> >rest transparently. This also works well with reactive protocols.
>> >
>> >/Erik
>> >
>> >
>> >On Wed, 2004-03-03 at 14:51, Christophe Jelger wrote:
>> >
>> >
>> >>Hi Erik,
>> >>
>> >>Well about handovers everything is in the draft, but I have to admit
>> >>that it's not very clear sometimes. I hope to write a new version
>> soon.
>> >>
>> >>To summarise : we propose different algorithms used by each ad hoc
>> node
>> >>to choose (and switch between) a gateway. It can either use the
>> closest
>> >>gateway (whatever prefix it uses), or a gateway that uses the same
>> >>prefix than it currently uses (whatever the distance from the
>> gateway).
>> >>We also proposed slight variants. So first answer to your email is
>> that
>> >>switching between gateways is controled by each ad hoc node
>> independently.
>> >>
>> >>Moreover, and because of our particular (but very simple) way of
>> prefix
>> >>propagation, we can guarantee that a default route is never diverted
>> (in
>> >>the steady-state). By steady-state, I mean that of course topological
>> >>changes can cause trouble during a very small amount of time. The main
>> >>idea behind our draft is prefix continuity : we "build" contiguous
>> >>islands of nodes that share the same prefix/gateway. This can be of
>> high
>> >>interest for providers (e.g. management, services, ...).
>> >>
>> >>We have implemented our solution (IPv6) as an independent daemon and
>> it
>> >>works really well in the presence of multiple gateways and prefixes.
>> We
>> >>will soon integrate it in an IPv6 version of OLSR (Qolyester from LRI
>> in
>> >>France). I am also finishing some simulations in which we evaluate our
>> >>solution : I hope I can submit the results for publication very soon.
>> >>
>> >>Well and before everybody says what's best and what's bad, I
>> personally
>> >>think it's very difficult at this stage to say so. If you have done
>> some
>> >>simulations of the tunnel approach you have probably seen that results
>> >>can greatly vary across different simulation scenarios. I think all
>> >>solutions have pros and cons, and we should be able to find the best
>> >>parts of all solutions.
>> >>
>> >>Regards,
>> >>Christophe
>> >>
>> >>Erik NordstrÃ¶m wrote:
>> >>
>> >>
>> >>
>> >>>Hi,
>> >>>
>> >>>I don't see how you can efficiently handle multiple gateways when
>> using
>> >>>default routes? Especially with reactive protocols that do not have a
>> >>>complete view of the network. Even if you maintain the gateway
>> mapping,
>> >>>how will you deal with hand-overs between gateways? You say  that the
>> >>>solution is to force nodes to use the "same" default route, but I do
>> not
>> >>>think that is a good idea. Individual nodes may know best when to
>> switch
>> >>>gateways, and they should be allowed to do so if they wish. How can
>> you
>> >>>guarantee that a default route is not diverted to another gateway at
>> an
>> >>>intermediate node if a packet carries no mapping between the (final)
>> >>>destination and the gateway? How do you handle control packets (from
>> >>>different gateways) that want to change the default route --> gateway
>> >>>mapping?
>> >>>
>> >>>My experience with AODV-UU is that gateway tunneling has many
>> properties
>> >>>that are prefered in an ad hoc network. Tunnels easily support
>> multiple
>> >>>gateways and are transparent for intermediate nodes that forwards the
>> >>>traffic to the gateway. I have a paper pending that clearly shows the
>> >>>advantages of tunnels in this context.
>> >>>
>> >>>Before proceeding with a merged draft on Internet connectivity, I
>> think
>> >>>that the proposal should be backed up with serious research showing
>> >>>problems or benefits of different strategies. I have implemented
>> gateway
>> >>>connectivity in AODV-UU, and my experience clearly points in the
>> >>>direction of tunnels.
>> >>>
>> >>>Regards,
>> >>>
>> >>>Erik NordstrÃ¶m
>> >>>
>> >>>
>> >>>
>> >>>On Wed, 2004-03-03 at 12:46, Christophe Jelger wrote:
>> >>>
>> >>>
>> >>>
>> >>>
>> >>>>Actually each node knows what gateway it uses because there is a
>> special
>> >>>>field in the packet used to disseminate the prefix information. This
>> >>>>field contains the IPv6 global address of the gateway (and another
>> field
>> >>>>gives the prefix length). Moreover, we "almost" don't need a routing
>> >>>>protocol (of course don't take this statement too strictly), in the
>> >>>>sense that, when a node wants to send data to some node in the
>> Internet,
>> >>>>it only uses a default route with next hop being one of its
>> neighbors.
>> >>>>The ad hoc node does not even need to have a /128 route to the
>> gateway.
>> >>>>Of course on the reverse path this is not the same (i.e. the gateway
>> >>>>must have a /128 route to the ad hoc node).
>> >>>>
>> >>>>Christophe
>> >>>>
>> >>>>Anders Nilsson wrote:
>> >>>>
>> >>>>
>> >>>>
>> >>>>
>> >>>>
>> >>>>>Hello again,
>> >>>>>
>> >>>>>Christophe Jelger wrote:
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>>>Of course as one of the authors of a solution that uses default
>> route
>> >>>>>>I don't agree with your statements. ;-)
>> >>>>>>
>> >>>>>>In our draft each MANET node knows which gateway it uses, and (in
>> the
>> >>>>>>steady-state) it knows that all nodes on the "default route" path
>> use
>> >>>>>>the same gateway. With our solution gateways don't announce
>> routes,
>> >>>>>>they just announce prefixes. If two gateways announce the same
>> >>>>>>prefix, an ad hoc node selects the closest gateway (it can be
>> >>>>>>specified that it should from there use the same gateway). The
>> >>>>>>propagation method used to propagate the prefix information
>> ensures
>> >>>>>>that the path to the gateway is made of nodes that also use the
>> same
>> >>>>>>gateway : there is no need of a routing header, and default routes
>> >>>>>>can be used safely.
>> >>>>>>
>> >>>>>>
>> >>>>>>
>> >>>>>>
>> >>>>>>
>> >>>>>That sounds like a good solution, but the node can't control what
>> >>>>>gateway it is currently using. A scenario where this is neeed is
>> when
>> >>>>>the node is moving from gateway to gateway. The node is then unable
>> to
>> >>>>>know what gateway it is currently communicating through. A node
>> need
>> >>>>>to know this when it switches to a new gateway, and "registers"
>> >>>>>itself. This reason why this needed is because packets from the
>> >>>>>Internet needs to be routed to the correct gateway, which is
>> difficult
>> >>>>>when mobile nodes are unware of its gateway. If a Cellular IP type
>> of
>> >>>>>solution is used, the routing entries in the access network are
>> >>>>>updated by the actual packets flowing through the gateways. But
>> there
>> >>>>>is problems here as well, because oscillations easily occurs that
>> >>>>>causes a lot of updates, especially when the mobile nodes are
>> mobile.
>> >>>>>I have simulated this, and it is harder to maintain than you might
>> >>>>>think. If you rely on proactive gateway discovery, the default
>> routing
>> >>>>>entries have to be maintained during link breaks and mobility,
>> along
>> >>>>>with sequence number maintainence. I have a paper about this, in a
>> >>>>>slightly different context, but during mobility and several hops to
>> >>>>>the gateway, more complex control is needed.
>> >>>>>
>> >>>>>regards,
>> >>>>>
>> >>>>>Anders
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>>
>> >>>>_______________________________________________
>> >>>>manet mailing list
>> >>>>[email-masked]
>> >>>>https://www1.ietf.org/mailman/listinfo/manet
>> >>>>
>> >>>>
>> >>>>
>> >>>>
>> >>>
>> >>>
>> >>>
>> >>>
>> >>
>> >>_______________________________________________
>> >>manet mailing list
>> >>[email-masked]
>> >>https://www1.ietf.org/mailman/listinfo/manet
>> >>
>> >>
>> >
>> >
>> >
>>
>>
>>
>> _______________________________________________
>> manet mailing list
>> [email-masked]
>> https://www1.ietf.org/mailman/listinfo/manet
>
>
> _______________________________________________
> manet mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/manet
>

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

---

From: "HyunWook Cha" <[email-masked]>
Date: Thu, 4 Mar 2004 17:19:46 +0900

Hello, Anders.

Please see my inline comments.

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of [email-masked]
> Sent: Thursday, March 04, 2004 4:11 AM
> To: Erik Nordstr?
> Cc: [email-masked]
> Subject: Re: [manet] Default Routes
> 
> 
> 
> Hello,
> 

Christophe proposes two different algorithms. As for one of them, you
are correct. However, node does not change it's address as long as at
least one neighbor keeps advertising same prefix in algorithm for prefix
stability. Anyway, ping-ponging can be possible.  

> to use the old gateway. 

I do not agree. I am not sure what will happen when link failure to
upstream node is found during forwarding packets. (Please clarify me,
Christophe.) However, why route of gateway should be discovered by
routing protocol? In his draft, packets are forwarded using not host
route for the gateway but default route although some nodes including
sender node on default path have default route entry as well as host
route entry for the gateway. It is because he puts on "prefix
continuity" much more weight than "efficiency". 

> The question is whether the downstream have to

Please think about algorithm for "prefix stability" how long it takes to
change leaf node's address. His idea is not about simple flooding.
 
Regards,

HyunWook

---

From: Christophe Jelger <[email-masked]>
Date: Thu, 04 Mar 2004 10:35:49 +0100

Anders and Erik, see my comments inline.

>than the one it is currently using.
We have proposed two main approaches : either an ad hoc node 
periodically chooses the closest gateway (whatever prefix it uses) or it 
tries to keep its current prefix as long as possible, whatever the 
distance to the gateway. Note that to do so the node must keep a view of 
its one-hop neighborhood, in order to check if it still has neighbors 
that use the same prefix.

So a node at the edges of two or more islands will choose its upstream 
neighbor according to one of these two proposals.

>and the network have mobility that causes frequent topology changes.
I'm afraid this is not correct. Whatever routing protocol, the ad hoc 
node MUST use its upstream neighbor as next hop to the gateway 
(otherwise prefix continuity is not guaranteed, and because packets have 
no routing header they could end-up at another gateway). You are right 
when you say that a change of prefix at a given node can trigger a 
change in prefix at all "downstream" nodes. It of course depends on the 
algorithm used (distance or prefix stability), the topology, the 
mobility etc ... I am doing some simulations in order to evaluate the 
impact of a change, I hope to be able to submit a paper for publication 
very soon. Also not that changes of address are expected to be handled 
by MIPv6 to maintain connectivity at the transport layer. So the address 
obtained in the ad hoc network is a care-of address.

>sure that is a wise thing to do. Christophe, please correct me if anything
Convergence is indeed very quick, because when there is change of prefix 
all "downstream" nodes are impacted almost immediately (the time it 
takes for control packets to propagate).

Christophe