Subject: Re: [DNA] Scope of solutions discussion document

From: Sathya Narayanan <[email-masked]>
Date: Wed, 23 Feb 2005 22:48:09 -0500

Brett -

<snip>
> The basic asssumptions that we made were that:
> - hints from layer 2 would be available to trigger router solicitations
I was thinking about this particular assumption we made while driving to work today. I checked 2461 and in section 6.3.7, the following statements are made:

"To obtain Router Advertisements quickly, a host SHOULD transmit up to MAX_RTR_SOLICITATIONS Router Solicitation messages each separated by at least RTR_SOLICITATION_INTERVAL seconds."

and
"
Before a host sends an initial solicitation, it SHOULD delay the transmission for a random amount of time between 0 and MAX_RTR_SOLICITATION_DELAY.  This serves to alleviate congestion when many hosts start up on a link at the same time, such as might happen   after recovery from a power failure."

What does 'initial solicitation' mean in ,'Before a host sends an initial solicitation ...'? - does this refer to the RS sent when 'The interface is initialized at system startup time' or 'The host re-attaches to a link after being detached for some time'?

The values for these three variables are:
MAX_RTR_SOLICITATION_DELAY        1 second
RTR_SOLICITATION_INTERVAL         4 seconds
MAX_RTR_SOLICITATIONS             3 transmissions

The MAX_RTR_SOLICITATIONS limit is alright. But, the requirment to delay between 0..1 seconds before sending RS, and maintain inter-RS delay of 4 seconds, I think, will have a negative impact on rapid DNA. BTW, both the restrictions are 'SHOULD's. 

Does it make sense to consider relaxing these conditions? 0..1 seconds delay restriction is useful though in avoiding congestion if many hosts change their points of attachment at the same time.

with regards,
Sathya

---

From: Brett Pentland <[email-masked]>
Date: Thu, 24 Feb 2005 15:20:21 +1100

Hi Sathya,

I seem to remember some discussion on this on the old mobile-ip list
some time ago, but I don't think there were any concrete conclusions.

As you say, they are all "SHOULDs" so there's no immediate show
stoppers, but all should be considered carefully.

MAX_RTR_SOLICITATIONS is not really an issue, since the section also
says later:

    Once the host sends a Router Solicitation, and receives a valid
    Router Advertisement with a non-zero Router Lifetime, the host MUST
    desist from sending additional solicitations on that interface, until
    the next time one of the above events occurs.  Moreover, a host

where the "above events" include attaching to a link for the first time.

RTR_SOLICITATION_INTERVAL could potentially slow things down if a host
is moving rapidly between links (less than 4 sec on a link), however the
text doesn't seem to say that "a host can never send RSs spaced closer
RTR_SOLICITATION_INTERVAL".  The implication seems to be that when a
host is trying to get an RA on a link, it should space its RSs by
RTR_SOLICITATION_INTERVAL until it gets an RA and then stop.  If it
got a hint that it had moved to a new link, it could start the whole
process again.  At least that's my interpretation.

MAX_RTR_SOLICITATION_DELAY is a trickier one.  As you note it is a
"SHOULD" delay.  Perhaps on power-up a host might delay, but not when
movement is detected, but still doesn't address the issue of a whole
lot of mobile nodes in a fast moving vehicle.  I think Greg has done
some simulations on groups of nodes moving at once and may have some
comment to add.

Cheers,
Brett.

Sathya Narayanan wrote:
> Brett -
> 
> <snip>
> 
>> The basic asssumptions that we made were that: - hints from layer 2
>> would be available to trigger router solicitations
> 
> I was thinking about this particular assumption we made while driving
> to work today. I checked 2461 and in section 6.3.7, the following
> statements are made:
> 
> "To obtain Router Advertisements quickly, a host SHOULD transmit up
> to MAX_RTR_SOLICITATIONS Router Solicitation messages each separated
> by at least RTR_SOLICITATION_INTERVAL seconds."
> 
> and " Before a host sends an initial solicitation, it SHOULD delay
> the transmission for a random amount of time between 0 and
> MAX_RTR_SOLICITATION_DELAY.  This serves to alleviate congestion when
> many hosts start up on a link at the same time, such as might happen
> after recovery from a power failure."
> 
> What does 'initial solicitation' mean in ,'Before a host sends an
> initial solicitation ...'? - does this refer to the RS sent when 'The
> interface is initialized at system startup time' or 'The host
> re-attaches to a link after being detached for some time'?
> 
> The values for these three variables are: MAX_RTR_SOLICITATION_DELAY
> 1 second RTR_SOLICITATION_INTERVAL         4 seconds 
> The MAX_RTR_SOLICITATIONS limit is alright. But, the requirment to
> delay between 0..1 seconds before sending RS, and maintain inter-RS
> delay of 4 seconds, I think, will have a negative impact on rapid
> DNA. BTW, both the restrictions are 'SHOULD's.
> 
> Does it make sense to consider relaxing these conditions? 0..1
> seconds delay restriction is useful though in avoiding congestion if
> many hosts change their points of attachment at the same time.
> 
> with regards, Sathya
>

---

From: Sathya Narayanan <[email-masked]>
Date: Thu, 24 Feb 2005 10:47:51 -0500

Hello Brett -

I agree - they are all 'SHOULDs' - but some information on the 
implementations will be useful?

The problem with RTR_SOLICITATION_INTERVAL is not only when a node is 
moving rapidly between links, it will also cause problems when there is 
packet loss. If the packet loss probability is p, then the prob of  a 4 
second delay being added will be (p + p^NR) where NR is the number of 
routers on the link that can respond. If NR is 1, the prob is 2p. I 
don't know if this is acceptable, so we can ignore this. My gut feeling 
is that we can not. We must be a bit more resilient to packet loss 
problems, 4 seconds is too much. I think it will be useful to 
differentiate the delay between re-transmission of RS becasue RA was not 
received, from delay between RS with a corresponding RA  and another 
following RS due to link trigger. In the later case, 4 second delay 
could avoid too many RS message due to fluctuating wireless link signal.

And, I agree,  MAX_RTR_SOLICITATION_DELAY is the trickier one.

rgds,
Sathya

---

From: Greg Daley <[email-masked]>
Date: Fri, 25 Feb 2005 12:07:35 +1100

Hi Sathya,

RFC2461bis seems to indicate that in the furture it
may be possible to ignore MAX_RTR_SOLICITATION_DELAY.
It's really our task to guess or show if/where it can be done.

> And, I agree,  MAX_RTR_SOLICITATION_DELAY is the trickier one.

Here's the text (page 3: draft-ietf-ipv6-2461bis-02.txt):

"...

    In some cases, the random delay MAY be omitted if necessary. For
    instance, a mobile node, using [MIPv6], moving to a new link would
    need to discover such movement as soon as possible to minimize the
    amount of packet losses resulting from the change in its topological
    movement. Router Solicitations provide a useful tool for movement
    detection in Mobile IPv6 as they allow mobile nodes to determine
    movement to new links. Hence, if a mobile node received link layer
    information indicating that movement might have taken place, it MAY
    send a Router Solicitation immediately, without random delays. The
    strength of such indications should be assessed by the mobile node's
    implementation depending on the level of certainty of the link layer
    hints and is outside the scope of this specification. Note that using
    this mechanism inappropriately (e.g. based on weak or transient
    indications) may result in Router Solicitation storms. Furthermore,
    simultaneous mobility of a large number of mobile nodes that use this
    mechanism can result in a large number of solicitations sent
    simultaneously.

..."

So there has to be management of link-layer indication->RS requirement
within the host, and potential application of delays on certain link
layers.

Below is a rough overview of some work I did a while ago using a locally
created OMNeT++ 802.11 simulation (the simulation has since been
published, but doesn't have the test scenario).

I have to apologise that I've left this on the side for a while and
don't have published results to display.

 From my experience with simulations of up to 30 alike MNs simultaneously
changing cell (hard handover threshold, super-imposed hosts receiving
an 802.11 beacon below the threshold), there were MAC collision bands
for RS's sent to the network.

In a lot of these cases, there were L2 probing collisions when scanning
channels, which meant that some of the MNs didn't know about the base
station's presence because they were unaware of the collision (the probe
is a multicast frame, with no ACK).

These devices found the same base station (since no other valid one was
nearby) on the second probe pass.  This meant that there were tiers of
successful probe responses, and subsequent authentication and association.
It is notable that probe responses weren't being snooped regardless of
MAC address.  This would have tightened things up considerably.

Across all the tiers, there was a lot of contention in the MAC and
delay was experienced in responses to the RS's.   Each bridged RS
received a unicast RA.

Mostly the cause of the delay in RA responses through the AP was the
nodes still attempting to get onto the link through 802.11 procedures.
This caused a queue backlog issue to arise so that around 20ms delay
was experienced for the RTT for the RS/RA pairs.

The spread in delays of hosts changing cells increased fairly steadily
until 30 nodes.

Here's the 30 hosts incidence plot for the delay after RS that an RA
was received using one millisecond buckets. The incidences were
summed over the simulation runs. Please be aware that the values are for
the middle of the millisecond range (so it works for box plots).

The actual delay for beginning to probe until the reception of the RA
was much more spread out. I can send similar data to individuals
in order to get an impression, but I'd prefer not to send larger
attachments.

As you can see, this data is not really ready for publication,
but may give an indication of what occurs on one of the interesting 
link-layers.

There's a lot more to actually test (for example the effect on other
hosts within a cell).

The (rough) impression I got was that there wasn't much harm in having
no additional RS serialization delay in 802.11b.

Greg

RS/RA exchange delay
-------------------
0.004500 1
0.005500 2
0.006500 2
0.007500 2
0.014500 1
0.015500 12
0.016500 2
0.017500 3
0.018500 153
0.019500 855

---

From: Brett Pentland <[email-masked]>
Date: Fri, 25 Feb 2005 12:54:55 +1100

Hi Sathya,

Using your approximation, then the order of magnitude of the probability
of encountering the 4 second delay is the same as the probablility of
packet loss.  Whether this is a problem or not depends on what cost is
applied to a slow detection.  What's a reasonable packet loss rate to
consider?  10^-3?  A slow detection every thousand or so.  Is that too
bad?  It may be for some applications; I'm not sure.

As Greg mentioned, there may be scope to modify the behavior.  Perhaps
some kind of exponential backoff rather than a fixed 4 second delay?

Brett.

-- 
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  Brett Pentland                  [email-masked]
  CTIE - Centre for Telecommunications and Information Engineering
  Department  of  Electrical  and   Computer  Systems  Engineering
  Monash University, VIC, 3800,                          Australia
  Phone : +61 3 9905-5245                    Fax : +61 3 9905-3454
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

---

From: Radhakrishnan Suryanarayanan <[email-masked]>
Date: Fri, 25 Feb 2005 12:25:38 +0530

Hi Brett, Satya,Greg,

<snip>
> process again.  At least that's my interpretation.

=> IMHO, thats quite a valid interpretation.