Subject: WG ACTION: 1 week to discuss [LL37] Aggressive Time-outs

From: Erik Guttman <[email-masked]>
Date: Mon, 15 Dec 2003 14:08:25 +0100

Please send your comments to the working group mailing list.  Unless
there is an objection due to lack of time to work on this before the
holidays, the discussion will conclude on December 23.

Please see: http://www.merit.edu/mail.archives/zeroconf/msg00001.html
And: http://www.drizzle.org/~aboba/ZEROCONF/ll37.html

Regards,

Erik

---

From: "Philip Nye" <[email-masked]>
Date: Tue, 16 Dec 2003 09:29:26 -0000

LL37 part 1)

It is quite right that the arithmetic in the document should be correct! I therefore support revising any inaccuracies. However, my interpretation of the text agrees with Thomas Narten:

+-PROBE_TIME-+-PROBE_TIME-+-PROBE_TIME-+-PROBE_MAX-+
  probe here-^       here-^   and here-^      done-^

This gives a time from 5-8 seconds (When PROBE_MIN=1s and PROBE_MAX=2s). Not as in the proposed change!

Philip

---

From: "Philip Nye" <[email-masked]>
Date: Tue, 16 Dec 2003 10:07:43 -0000

LL37 part 3)
I support the proposed change.

If we are to keep the existing text we need a convincing use-case for a network with shorter timeouts.

The current reference to "future versions of the IEEE 802 Spanning Tree Protocol" seems entirely spurious in the light of Erik's comments on "The motivation for the 1-2 second delay..." which has nothing to do with Spanning Tree.

Philip

---

From: Mika Liljeberg <[email-masked]>
Date: Tue, 16 Dec 2003 23:27:16 +0200

Instead of trying to figure out how long it takes to send three probes,
I would like to step back a little and ask the question WHY exactly do
we have to send THREE PROBES? What exactly in v4LL necessitates sending
three DAD probes when IPv6 can get away with only one? Here's the
relevant bit from RFC2462:

...
5.1.  Node Configuration Variables

   A node MUST allow the following autoconfiguration-related variable to
   be configured by system management for each multicast interface:

      DupAddrDetectTransmits

                     The number of consecutive Neighbor Solicitation
                     messages sent while performing Duplicate Address
                     Detection on a tentative address. A value of zero
                     indicates that Duplicate Address Detection is not
                     performed on tentative addresses. A value of one
                     indicates a single transmission with no follow up
                     retransmissions.

                     Default: 1, but may be overridden by a link-type
                     specific value in the document that covers issues
                     related to the transmission of IP over a particular
                     link type (e.g., [IPv6-ETHER]).

                     Autoconfiguration also assumes the presence of the
                     variable RetransTimer as defined in [DISCOVERY].
                     For autoconfiguration purposes, RetransTimer
                     specifies the delay between consecutive Neighbor
                     Solicitation transmissions performed during
                     Duplicate Address Detection (if
                     DupAddrDetectTransmits is greater than 1), as well
                     as the time a node waits after sending the last
                     Neighbor Solicitation before ending the Duplicate
                     Address Detection process.
...

Here's my proposal (three fold):
     1. Let's specify DAD probe in the same way as in IPv6, defaulting
        to a single probe packet
     2. In the event of a conflict (slightly more probable with v4LL
        compared to IPv6), allow the node to select a new v4LL and retry
        up to, e.g., AddrSelectRetries times
     3. Let's get rid of the text describing shorter timeouts. If we
        default to a single probe, DAD only takes 1..2 seconds (with a
        high probability). That is good enough from the usability point
        of view.

Regards,

	MikaL

---

From: Robert Elz <[email-masked]>
Date: Wed, 17 Dec 2003 17:07:16 +0700

Date:        Tue, 16 Dec 2003 23:27:16 +0200
    From:        Mika Liljeberg <[email-masked]>
    Message-ID:  <1071610036.12327.17.camel@hades>

  | Instead of trying to figure out how long it takes to send three probes,
  | I would like to step back a little and ask the question WHY exactly do
  | we have to send THREE PROBES? What exactly in v4LL necessitates sending
  | three DAD probes when IPv6 can get away with only one?

v6 has 64 bits of address space, it is incredibly unlikely that something
doing random address assignment (which is what is relevant here) is ever
going to clash with something else - so one check, no reply, and all is OK.

v4LL has only 16 bits to play in (slightly less because of the exclusions of
the first and last /24's from contention) - the birthday paradox tells us
that with perfect random assignments we're going to get a clash as soon as
the number of hosts on the link gets to around 256 (2^8 being sqrt(2^16) which
is a very rough approximation of the point where probability goes > 50%).

256 hosts is not at all implausible on a link (2^32 is), so v4LL has to
actually expect to get duplicates, where in v6 they are only likely to occur
due to human stupidity.   v4LL simply has to try harder to detect those
duplicates.

kre

---

From: Mika Liljeberg <[email-masked]>
Date: Wed, 17 Dec 2003 20:54:20 +0200

> is a very rough approximation of the point where probability goes > 50%).

You're missing the point. The spec is telling us to probe the SAME
ADDRESS three times. The retransmissions might make sense if the link
has a high loss probability, but address collision probability has
nothing to do with it.

Please read this bit again:

Regards,

	MikaL

---

From: Robert Elz <[email-masked]>
Date: Thu, 18 Dec 2003 03:43:14 +0700

Date:        Wed, 17 Dec 2003 20:54:20 +0200
    From:        Mika Liljeberg <[email-masked]>
    Message-ID:  <1071687260.15146.3.camel@hades>

  | You're missing the point.

I don't think so.

  | The spec is telling us to probe the SAME ADDRESS three times.

Yes, that (or twice, at an absolute minimum) is what needs to happen.

  | The retransmissions might make sense if the link
  | has a high loss probability, but address collision probability has
  | nothing to do with it.

Not true.

What matters is the probability of failure to detect a duplicate address
(that could be detected - ones owned by nodes that are disconnected we can
do nothing about).

That is (approximately) the product of the probability of packet loss
(of either the query, or the reply), and the probability that there is
in fact a duplicate to detect.

For v6, the second of those is a much smaller (MUCH smaller) number than
on v4 (v4 is not just "slightly more probable" to have a conflict, it is
in fact likely there, and almost unimaginable on v6).

That number we cannot do anything about, it is controlled by the number of
available addresses from which to make our random choice.

So, if we want to get the overall probability of failure of v4 LL allocation
down somewhere near what it is for v6, the only thing we can alter to achieve
that is to make the probability of packet loss much smaller - that's done
by simply retransmitting, if the probability of the loss of 1 packet is
0.01% (probably a little high for an ethernet, but not too far away I suspect)
then the probability of either of 2 (query&reply) being lost is a bit more
than that (but I think, if I remember that formula, less than 0.02% - or
was it more?  Doesn't matter much)   The probability of all 3 of 3 attempts
suffering a lost packet is then something like 0.0000000008% if I did the
arithmetic right (which I probably didn't, but it is small anyway).

While not getting us to the overall confidence level of v6, this at least
gets us a lot closer.

  | Please read this bit again:

I read it the first time...

  | Here's my proposal (three fold):
  |      1. Let's specify DAD probe in the same way as in IPv6, defaulting
  |         to a single probe packet

No, that's what we cannot do.   The probability of undetected failure then
is too high.

  |      2. In the event of a conflict (slightly more probable with v4LL
  |         compared to IPv6), allow the node to select a new v4LL and retry
  |         up to, e.g., AddrSelectRetries times

That's not any kind of change.  But the "slightly" should be "much".

  |      3. Let's get rid of the text describing shorter timeouts. If we
  |         default to a single probe, DAD only takes 1..2 seconds (with a
  |         high probability). That is good enough from the usability point
  |         of view.

Since (1) is already ruled out, this becomes irrelevant.

This is no longer important, but ages ago I argued that the timer values
make no sense as they are - 1-2 seconds is way too long to wait for a
reply from a local 802.x style network - if a reply doesn't arrive in (well
under really) 100ms, then it isn't coming.   On the other hand, if the
spanning tree algorithm may be running in a connected switch (which is
actually very likely, every time the address assignment algorithm needs
to run, if connected to a switch port that runs spanning tree), then the
timer values are way too short (at least, the first one).   Either way,
the values specified make no real sense (we could have 3 transmits and be
done in 0.5 seconds if we ignore spanning tree delays).

The WG decided to ignore this - partly I believe out of a desire to spread
out probes, if a large net all happens to start at the same time, which is
a valid concern.   They also decided to ignore spanning trees - because
specifying a timer long enough to cope would irritate lots of people, and
specifying an algorithm to dynamically detect whether a long delay is
needed or not seemed too complex (though several reasonable suggestions were
made).

This isn't something important enough to fight over.   A few more years
(one hopes) and v4 will be header for the scrap heap anyway.

kre

---

From: "Philip Nye" <[email-masked]>
Date: Wed, 17 Dec 2003 21:04:40 -0000

> From: "Robert Elz" <[email-masked]>
> 

In addition to this, it is probably the case that IPv4 systems do not cope so well as IPv6 with clashes and changing addresses, so having a higher confidence level that the address you have picked is unique on the link is probably going to make life that bit easier for the user.

The final and probably strongest argument against Mika's suggestion is that it is way too late in the process to be re-opening this algorithm at this point. Unless you can show that three probes will break where one won't (which I doubt) then we should tidy up the arithmetic so at least we get the answer to 2+2 right, and get it out of the door.

Philip

---

From: Mika Liljeberg <[email-masked]>
Date: Wed, 17 Dec 2003 23:51:58 +0200

I see what you and kre are saying, but I don't buy the number game. The
fact remains that three is a wholly arbitrary number and likely to be
wrong for most environments. Who is to say one probe is not enough? It
all depends on the link error rate and the number of nodes supported by
the link.

For instance, a Bluetooth PAN piconet (radio range 10 meters) supports a
maximum of 7 nodes and the link layer is reliable. Three probes is
completely unnecessary and at the same time constitute a usability
problem, since many of the use cases involve quick ad-hoc interactions. 

My objection to three probes is as I have stated before: 5..8 seconds is
too long from the usability point of view. The feedback gathered from
users of data services in GSM/GPRS networks is overwhelming on this. A
user expects to see results within a few seconds of the first button
press. Address configuration is just one of the initial steps that needs
to take place in a typical use case.

I think we can pretty well start out with the assumption that v4LL
address collisions will sometimes happen. What could be spelled out is,
what is an acceptable probability for failing to detect one? Knowing
that, the number of probe retransmissions can be adjusted accordingly
for a particular environment. IPv6 allows adjusting the number of probes
transmitted. Why should v4LL be any different?

As for it being too late, the last time I raised this point no-one
seemed inclined to discuss it. I must say two responses are a distinct
improvement.

	MikaL

---

From: "Philip Nye" <[email-masked]>
Date: Wed, 17 Dec 2003 23:45:29 -0000

> From: "Mika Liljeberg" <[email-masked]>
> 
> The feedback gathered from

I must completely misunderstand what GPRS is all about if users are depending to any significant extent on IPv4 LL addresses.

Philip

---

From: Mika Liljeberg <[email-masked]>
Date: Thu, 18 Dec 2003 02:08:45 +0200

> I must completely misunderstand what GPRS is all about if users are depending to any significant extent on IPv4 LL addresses.

No, you just misunderstood my comment. I was using GSM/GPRS as an
example of where address configuration time for a handset is a usability
issue. We've found that it has to be squeezed down to 2..3 seconds in
order to make end users happy. v4ll configuration in handsets has to
meet the same user expectations.

	MikaL

---

From: Erik Guttman <[email-masked]>
Date: Thu, 18 Dec 2003 08:38:56 +0100

The fundamental assumption which leads us to long time outs is the
required support for link-layer technologies which "have a round-trip
latency of at most one second."

If this latency were redefined as 375 ms (just to make up a value),
then three retries would take 1.875-3 seconds.  The questions (for
you experts out there) are

  - why are we required to support link-layer technologies with a
    latency of at most one second instead of a lower value?

  - what is the lowest value we could choose and still support most
    (if not all) link-layer technologies?  Which technologies can
    expose hosts to several hundred millisecond latencies?

  - are there other considerations (such as set up time for network
    infrastructure) before ARP requests and replies would propogate to
    hosts?  (Does 5-8 seconds of start up work better for these than
    would, say, 1.875-3 seconds would?)

Thanks,

Erik

-- 
  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
    Erik Guttman   -   N1 Manageability   -   Sun Microsystems
       cell: +49 172 865 5497   -   time zone: CET (GMT+1)

---

From: Erik Guttman <[email-masked]>
Date: Thu, 18 Dec 2003 10:14:56 +0100

Mika,

Please see http://www.drizzle.com/~aboba/ZEROCONF/ll31.html
This issue was accepted.  It argues that 3 tries are needed
for reliability guarantees.  It states that IPv6 uses 1 second
timeouts and suggests we do the same without motivating that
choice.  Retries are needed for robustness, he asserts, because
there is a real, though small collision chance on 802 technologies.

If there are certain technologies without collisions or with a lower
maximum latency, why not create an additional document entitled
"Timer settings for IPv4 Link Local Autoconfiguration on Foo"?
As discussed previously in this WG there are problems with this
approach.

1 Foo may be bridged to a slower, collision-prone link-layer.  We
   cannot assume interoperation will succeed between the two links
   using values appropriate to Foo but inappropriate to 802.
2 IETF standards have not specified different timer settings for
   different link-layers to my knowledge.
3 Until your specific example of bluetooth, no one had submitted
   specific examples of link-layer technology which would require
   special treatment.

I still think the best way forward is to have knowledgeable folks
inform us as to the maximum latency expectations for link-layers
we are concerned about.  I will contact folks involved with PILC
for their input.

Regards,

Erik

---

From: Bill Rees <[email-masked]>
Date: Thu, 18 Dec 2003 01:26:47 -0800

As I understand this thread, the latency comes from waiting for a 
spanning tree routine to run which to me implies a wan, no?  So a bit 
off kilter here, what is the likelihood that the llv4 situation occurs 
in such a congested, logically disparate locations?  Is it likely that 
linklocal will show up in such an environment?  Given all the discussion 
surrounding moving off of the llv4 address as quickly as possible, even 
in a congested environment what is the likelihood that the number of 
llv4 devices will exist on the network at the same time isd 2 or more?

So in summary I'm wondering what the mean lifetime of a llv4 address is, 
what the probability of two llv4 users occurring at the same time is, 
and the likelihood they'll pick the same address.  The number of probes 
required to uniqueify a llv4 address is in here somewhere I just am 
beginning to doubt the likelihood of a collision.

Bill Rees

Erik Guttman wrote:

>>> In addition to this, it is probably the case that IPv4 systems do 
>>> not cope so well as IPv6 with clashes and changing addresses, so 
>>> having a higher confidence level that the address you have picked is 
>>> unique on the link is probably going to make life that bit easier 
>>> for the user.
>>>
>>> The final and probably strongest argument against Mika's suggestion 
>>> is that it is way too late in the process to be re-opening this 
>>> algorithm at this point. Unless you can show that three probes will 
>>> break where one won't (which I doubt) then we should tidy up the 
>>> arithmetic so at least we get the answer to 2+2 right, and get it 
>>> out of the door.
>>>
>>> Philip
>>>
>>
>
>

---

From: "Philip Nye" <[email-masked]>
Date: Thu, 18 Dec 2003 10:09:04 -0000

> problem, since many of the use cases involve quick ad-hoc interactions.

Link layer reliability is not the issue. Experience shows that in many networks the single most common cause of lost packets is busy hosts dropping them on input. A reliable link layer just ensures that both hosts know that the packet was received. There is no guarantee that a packet delivered is a packet processed. Either the new host sending the ARP probe, or the holder of a conflicting address could miss a packet this way.

Does Bluetooth's link layer reliability extend to broadcast probes?

I would accept that the number of probes could be a symbolic parameter NUM_PROBES rather than a hard coded number, but for this spec NUM_PROBES=3 is appropriate. A subsequent document for Bluetooth piconets (or whatever), could then specify NUM_PROBES=0 or 666 or anything appropriate.

Philip

---

From: "Philip Nye" <[email-masked]>
Date: Thu, 18 Dec 2003 10:26:26 -0000

> From: "Bill Rees" <[email-masked]>
> 
> spanning tree routine to run which to me implies a wan, no?

It seems that spanning tree can take quite a bit longer so the difference between 2 and 8 seconds is little help.

>  So a bit 

The answer to this was discussed a long time ago. If the network has a DHCP server, which refuses to hand you an address or if it is primarily a statically configured network, you can still go ahead and configure a LL address and use it to whatever extent it works (e.g. to talk to a printer or another ad-hoc user). This could easily apply on a large multiply bridged network.

Philip

---

From: Mika Liljeberg <[email-masked]>
Date: Thu, 18 Dec 2003 20:10:37 +0200

On Thu, 2003-12-18 at 12:09, Philip Nye wrote:

> I would accept that the number of probes could be a symbolic parameter
> NUM_PROBES rather than a hard coded number, but for this spec
> NUM_PROBES=3 is appropriate.

I would agree to that. I'm fine with a default of 3, as long as the
number of probes can be adjusted where another value makes more sense
for a particular environment.

>  A subsequent document for Bluetooth piconets (or whatever), could
> then specify NUM_PROBES=0 or 666 or anything appropriate.

I doubt a separate document for each possible environment is feasible.
Just make NUM_PROBES a configurable system parameter, recommend a
default of 3, and leave it at that.

Regards,

	MikaL