From: Marc M. <ma...@co...> - 2002-06-24 20:20:39
|
I think what it comes down to is what constitutes a 'link break'. The thing that is special about the scenario below is that the 'link break' does not invalidate the destination of the link break: the route to Z is still perfectly valid. Only the destinations that used the broken link link as a next hop are 'broken'. It is not obvious from the draft that if a route is updated by creating a reverse route for a RREQ or is updated based on a RREP that moving a 1-hop node to a multi-hop node constitutes a 'broken link to a next-hop'. That is how I am interpreting it, but it's not at all clear from the draft that it should be this way. Section 6.10 on Maintaining Local Connectivity -- an entirely optional section (word MUST does not appear anywhere) -- is also unclear on this issue. Section 6.10 is unhelpful in that it redefines 'active' in the context of 'active next hop' to mean one that has actually forwarded a data packet, not just one with a finite hop count (as 'active' is defined in section 3). One could read in to section 6.10 that if the active route to a next hop switches to become a multi-hop route that suffices as 'detecting' a link break. But, I think this should be done for all 1-hop neighbors, not just those that have forwarded data packets. Marc Mosko U.C. Santa Cruz Luke Klein-Berndt wrote: > Whoops... definately monday... > > I could be wrong but when Z moves wouldn't it break the route to A? In 6.11 > item 1 of the list, if it detects a broken next hop it iniates RERR stuff. > The 2nd list of routes should never occur. Then again I am in need of > another cup of coffee so I am going to go look it over again. > > -Luke Klein-Berndt > > >>-----Original Message----- >>From: Marc Mosko [mailto:ma...@co...] >>Sent: Monday, June 24, 2002 4:01 PM >>To: Luke Klein-Berndt; AODV LIST >>Subject: Re: [Aodvimpl] Increasing path length for 1-hop neighbors >> >> >>(Luke's reply did not go to the AODV list, but is repeated below) >> >>I see that AODV might eventually do the 'right thing', but it >>seems dubious for a node to keep an improper route in it's >>routing table. >> >>For instance, if the routing table at node Y originally was: >> >>dst nexthop hops flags >>Y Y 0 active >>X X 1 active >>Z Z 1 active >>A Z 4 active >> >>And if Z moves and the table is updated to >> >>dst nexthop hops flags >>Y Y 0 active >>X X 1 active >>Z X 2 active >>A Z 4 active >> >>a question is what should node Y do if >>it receives a RREQ for node A? I would say >>that at this instant, Y does not have a valid route >>to A. Can it correctly issue a RREP for A? >> >>I suspect the worst that will happen is that it >>will issues a RREP then get an actual data packet >>that will get dropped and many RERRs issued, or >>the hello timeout on Z will happen and many RERRs >>get issued. >> >>Note that if you keep the hello timeout on Z, >>you do two sub-optimal things: send a RREP for >>A when you don't have an route, and timeout Z >>when you do have a route. >> >>It seems more reasonable to me for the 2nd routing >>table to look like: >> >>dst nexthop hops lasthop flags >>X X 1 active >>Y Y 0 active >>Z X 2 active >>A Z 255 4 broken repairable >> >>Marc Mosko >> >>Luke Klein-Berndt wrote: >> >> >>>I am not quite sure how this is a problem... >>> >>>If Y truly is two hops away from Z then the HELLO timer for Z >>> >>will timeout >> >>>and Y will follow the procedure in the draft. If Y is only one >>> >>hop from Z >> >>>and just missed a RREQ, Y will update its table when it gets >>> >>the next HELLO >> >>>message from Z. >>> >>>In either case you could be throwing packets out into the ether >>> >>for up to 3 >> >>>seconds. This is the correct behavior though. Y should not >>> >>change its route >> >>>to A, once Y can confirm that the link is actaully broken then it should >>>worry about the route. Until then it should keep sending >>> >>packets to A with Z >> >>>as the next hop. It is quite possible they might not make it. >>> >>>This really is a problem with Hello messages, you are never sure of your >>>connection with your neighbors. You are also never sure if you neighbors >>>recieved the message. In the real world implementations it is >>> >>very difficult >> >>>to tell if a packet was actaully recieved by a neighbor because the >>>information is locked at the hardware level. >>> >>>So really I think this is a symptom of a large problem >>> >>invloving neighbor >> >>>sensing, and one that is not limited to AODV. >>> >>>-Luke Klein-Berndt >>> >>> >>> >>> >>> >>>>-----Original Message----- >>>>From: aod...@li... >>>>[mailto:aod...@li...]On Behalf Of Marc >>>>Mosko >>>>Sent: Saturday, June 22, 2002 4:14 AM >>>>To: aod...@li... >>>>Subject: [Aodvimpl] Increasing path length for 1-hop neighbors >>>> >>>> >>>>Here's an interesting situation I've come accross. This may >>>>happen when creating a reverse route or when adding a route >>>> >>>>from a RREP as an intermediate node. In both cases, it >>> >>>>is possible that an active 1-hop neighbor becomes an active >>>>multi-hop destination. >>>> >>>>Imagine nodes X, Y, and Z are all 1-hop neighbors, and >>>>all nodes have Z's sequence number as 1. Z sends a RREQ >>>>with sequence number 2, which X receives but Y does not. >>>>X rebroadcasts it, and Y hears that broadcast. Y >>>>makes X the next hop to get to Z. >>>> >>>>Suppose Y had a route to A via Z. It obviously cannot >>>>keep Z as the next hop to A, because the routing table >>>>shows that Z is now two hops away. (well, maybe not >>>>too obviously) >>>> >>>>What should node Y do? >>>> >>>>1) Break the route to A and possibly mark it repairable. >>>> >>>>2) Change the next hop to be X, even though X might not >>>> have a route to A. >>>> >>>>3) something else? >>>> >>>>Clearly, whenever a node has a neighbor change from >>>>being 1-hop to multi-hop, it must scan it's routing >>>>table and invalidate/update any routes that no >>>>longer have a valid next-hop. >>>> >>>>The draft, however, is silent on this condition and >>>>should bring it to the attention of implementors. >>>> >>>>In simulation, this situation is largely masked. >>>>Continuing the above example, either Z is still >>>>really a 1-hop neighbor and when Y tries to >>>>forward a packet to A via Z, Z hears it and forwards, >>>>or there is an RTS/CTS drop notification and >>>>Y immediately invalidates the route, only to have >>>>it repaired quickly. >>>> >>>>Along the same lines, when a 1-hop neighbor >>>>becomes a multi-hop destination, one should >>>>stop Hello timeouts if using Hellos. >>>> >>>>Marc Mosko >>>>U.C. Santa Cruz >>>> >>>> >>>>------------------------------------------------------- >>>>Sponsored by: >>>>ThinkGeek at http://www.ThinkGeek.com/ >>>>_______________________________________________ >>>>Aodvimpl-public mailing list >>>>Aod...@li... >>>>https://lists.sourceforge.net/lists/listinfo/aodvimpl-public >>>> >>>> >>>> >>>> >>>> >> >> >> |