Subject: [LL12] [LL20] and a possible solution

From: Robert Elz <[email-masked]>
Date: Sat, 05 Apr 2003 20:36:45 +0700

The problem that these two are trying to deal with are the totally
inappropriate timer values specified in the draft.

The timers that are there now satisfy no-one, they're not long enough
to cope with switches blocking packets while running the spanning tree
algorithm (to decide if it is safe to allow the link to be brought up
and process packets).

But they're too long to satisfy nodes that know there's not going to
be any of that happening, and want to be connected and working as
quickly as possible.

The problem is that there's no way (that I'm aware of) for a node to
know whether or not packets it sends are being received by other nodes
or not.

We could just wait for IEEE to define one, and then hope that the NIC
makers (chip makers, and then board vendors) incorporate that quickly.
And in the meantime we wait (after all, that could probably all happen
quicker than this doc is going to emerge from this WG...)

Or we could just adopt the conservative safe approach, and specify timers
long enough that they're guaranteed to work (which means something
of the order of 45 seconds from when the link has come up at a hardware
level).

Or we could adopt the risky, works frequently, occasionally self destructs
method, and wish spanning tree algorithms into non-existence (require that
network operators disable spanning tree on any switch interfaces where a
node that might want to use LL addresses is to be connected), pick low
timers, and simply live with the occasional address conflicts that
result (even in the worst circumstances, they won't happen often, and
nodes have to be able to deal with them in the case of partitioned
networks rejoining).

Or, we could just fix the problem ourselves.

That is, we could make the algorithm be

	Send probe
	Wait short interval (randomised, 80-100 ms max) for a reply.
	If there's a reply, pick a new random address goto A:
	If there's no reply, retransmit the probe, and also broadcast
		an ARP request for 169.254.0.0
	Wait for a reply (for up to 60 seconds, with occasional
		retransmits of the address probe (every 5 secs or so),
		and frequent retransmits (every 300 ms or so, randomised)
		of the 169.254.0.0 ARP query).
	If no reply (at all, after 60 secs), take the address, and defend it.
	If there's a reply to the selected address probe,
		pick a new random address, goto A:
	If there's a reply to the 169.254.0.0 request, or if
		there's an ARP reply/request for any other address,
		keep the same address selected, goto A:
	/* NOT REACHED */

   A:	send probe for selected address
	wait short interval for reply (randomised, 40-80 ms).
	if a reply comes, pick a new random address (unless we
		have tried too many times already - abort in that case)
		goto A:
	if no reply, and less than 5 (or 3 or something) probes
		for this address have been sent (since point A),
		keep same addr, goto A:
	Assign the probed address to the interface.

Then, the ARP listener, that runs the whole time this is going on
and forever after, handles ARP just as now (in the doc) for all cases,
except for when an ARP request for 169.254.0.0 is received.

When that happens, the node picks a random interval, in the range
1-200 ms, and waits,  While waiting, if it sees an ARP reply for
169.254.0.0, it cancels its timer, and forgets it ever saw the
169.254.0.0 ARP request.

If it sees no reply, then after its timer expires, it broadcasts
an ARP reply (to everyone) claiming to own the 169.254.0.0 address
for itself (other nodes can, and probably should, choose to ignore
this reply, other than to cancel any timer they have running).

The idea of this is for the node to be able to discover whether its
packets are going anywhere or not.

While they're being blocked, no-one is going to see the 169.254.0.0
ARP request, there will be no reply, and the node will remain in the
"I have to wait 60 seconds" mode.

On the other hand, if packets are being transmitted, some other node
(and usually just one other node) will reply to the 169.254.0.0 ARP
request - getting that reply allows the node to know that it is
connected to a net, the connection works, and so, it can use short
timers instead of long slow ones.

The one remaining case is where the node is connected to a link which
is working, but where there are no nodes on the link that understand
LL addresses (note that any node that understands the spec will reply
to the 169.254.0.0 ARP probe - not only one that has a LL address assigned
on the interface).   In that case, the node that is trying to assign
itself a LL address will remain on the slow path, when it need not.
But it doesn't matter - there's no-one out there to talk to anyway
(no-one who will understand the LL address if it is assigned).  So,
it really doesn't matter how quickly the first node to connect to
this link acquires its LL address (if that slow assignment slows down
availability of the node for other, non networking, functions, then
that's a poor implementation - the non-net part of the node should be
getting itself running in parallel with all of this, the networking
part of it is useless with no peers to communicate with, and so may
as well wait an extra minute during its config, just to be safe).

If we do this, we can rid ourselves of the "too long but not long enough"
timers that are currently in the draft, allow most nodes to assign themselves
a LL address very quickly (since the 169.254.0.0 probe will be answered, by
someone, quite quickly), while still working correctly in the presence of
spanning tree algorithms being left enabled in switches (it also
dynamically detects just how quickly the switch is available, as soon as
it unblocks the port, someone will reply to the next probe for that address,
and the algorithm will switch into fast mode).

There could probably be a better algorithm than the one above (which needs
fleshing out in some of the details anyway) - but even if that ends up
being it, I think it is simple enough to understand, and implement, and
cheap enough to actually use (even with thousands of nodes all booting
on the same link at the same time) that it is a workable solution.

kre

---

From: Mika Liljeberg <[email-masked]>
Date: 05 Apr 2003 16:55:42 +0300

Hi,

I propose a simple approach [not fully fleshed out].

Let's specify that a newly picked LL address is "tentative" for the
first 60 seconds. The host is allowed to use it immediately but will
also be sending DAD probes (possibly with exponential backoff) while the
address is in "tentative" state.

If a conflict is detected, the node with the tentative address is
required to yield immediately and pick a new address.

	MikaL

---

From: Robert Elz <[email-masked]>
Date: Sat, 05 Apr 2003 22:33:10 +0700

Date:        05 Apr 2003 16:55:42 +0300
    From:        Mika Liljeberg <[email-masked]>
    Message-ID:  <1049550941.20483.48.camel@devil>

  | Let's specify that a newly picked LL address is "tentative" for the
  | first 60 seconds. The host is allowed to use it immediately but will
  | also be sending DAD probes (possibly with exponential backoff) while the
  | address is in "tentative" state.

That's not a productive approach.   If the immediate use of the address
works (actually achieves something), then there's no need to keep probing.
You know the net is working, you know you have the address, you also are
pretty sure there can't be a conflict (at the very most one more probe
might be required).

That is, all we need is to get some indication that the net works, and then
we can do fast probing, and allocate an address with almost no delay.

On the other hand, if the net didn't work (blocked port), and we allocate
an address, then start sending packets from it, and the net unblocks,
then we keep sending packets, we can achieve things like TCP reset sent to
the "other" user of the address (if there happened to be a conflict).
Having the node that incorrectly probed and allocated the address that it
must give up the address in this case doesn't help the other node that
has been trodden all over.

kre

---

From: Mika Liljeberg <[email-masked]>
Date: 06 Apr 2003 14:27:40 +0300

On Sat, 2003-04-05 at 18:33, Robert Elz wrote:
> That's not a productive approach.

It's certainly a different approach but I think it could be made to
work.

>    If the immediate use of the address
> You know the net is working,

That's true. You don't have to keep DADding for the full 60 seconds 
once you get confirmation that the link is responsive. You just have to
send a few more quick DADs and, if there is no response, move your LL
address from "tentative" to "assigned".

>  you know you have the address, you also are

That's not true. You are trying to communicate with a tentative LL
source address and have ARPed for some destination address. You have not
yet completed DAD on the your own LL address. At this point you still
have to send a few rapid DADs in order to validate your LL address.

> we can do fast probing, and allocate an address with almost no delay.

True, I agree (see above).

Letting the host ARP for a real destination address, rather than
169.254.0.0, solves the problem where the link does not have any other
LL-compliant nodes. Note that there may be non-LL compliant nodes with a
configured 169.254/16 on-link route (people seemed to want this
earlier), which you would like to communicate with. Your solution would
keep spamming the link with ARP broadcasts to 169.254.0.0 for the full
60 seconds (you can't use backoff if you want rapid link responsiveness
detection).

> the "other" user of the address (if there happened to be a conflict).

There is not much difference to your solution in this respect. The
address only becomes allocated after 60 seconds, after which the node
starts to defend it. While the address is tentative you can minimize 
collision hazards with the following simple rules:

1) Delay ARP response for a tentative address by a small delay, e.g. one
second, (and yield immediately if you hear an ARP response from another
node for the same address, as required by conflict resolution)
2) Only send unicast ARP responses for a tentative address. This will
avoid triggering conflict resolution in other nodes.

> has been trodden all over.

It's not quite as unworkable as that, I think. :-)

	MikaL

---

From: Robert Elz <[email-masked]>
Date: Mon, 07 Apr 2003 17:57:12 +0700

Date:        06 Apr 2003 14:27:40 +0300
    From:        Mika Liljeberg <[email-masked]>
    Message-ID:  <1049628459.20483.1034.camel@devil>

  | That's not true. You are trying to communicate with a tentative LL
  | source address and have ARPed for some destination address.

Yes, and after that, you've most likely sent packets and received
replies.   All of that working correctly is pretty strong evidence
that the address isn't used by anyone else, which is all the extra
probes are intended to discover (neither is proof, just a better
indication).  Doing extra probes, for no better reason that we would
want to do them if we had no other evidence, is dumb.

The only reason for not just going ahead and doing all of this, is the
potential for standing on someone else who is using your tentative
address (just doing an ARP query for some address has your IP/MAC
address mapping in the request, and supplies that to the destination
node, possibly overwriting the mapping for some other node that was
previously using the address).

  | Letting the host ARP for a real destination address, rather than
  | 169.254.0.0, solves the problem where the link does not have any other
  | LL-compliant nodes.

If the link has no other LL aware nodes, the whole issue is irrelevant,
as having obtained our LL address, there will be no-one to communicate
with.

  | Note that there may be non-LL compliant nodes with a
  | configured 169.254/16 on-link route (people seemed to want this
  | earlier), which you would like to communicate with. Your solution would
  | keep spamming the link with ARP broadcasts to 169.254.0.0 for the full
  | 60 seconds (you can't use backoff if you want rapid link responsiveness
  | detection).

Yes, but if you're willing to configure a node to know that 169.254/16 is
on link (which is certainly not impossible) you can easily also configure it
to respond to those ARP requests (even if it just does a unicast reply,
which in this scenario would be fine).

But you do point out one minor disadvantage to my proposal, in that if a
link has one LL aware node (exactly one) and perhaps large numbers of
non LL aware nodes, they're all going to be bothered by several ARP packets
a second (2 or 3, depending upon the final values of the timers) for
a minute, when that LL aware node connects.   I think I could live with
that (150-200 ARP requests in a minute, occasionally), but it is something
worth bearing in mind.

The other reason why "just go ahead and ARP for a real address" as a solution
is (for many implementations anyway) not useful, is that while they're in
the stages of configuring interfaces, they have no-one else with whom they
want to communicate.  Interface config is one of the very early parts of
getting started, way before any applications are running (many apps prefer to
have interfaces configured before they start, as they want to extract the
information from the interface config so they know the local environment).

In any case, as I think (hope) I said in my first message, the algorithm I
came up with isn't what's important here - what matters for now is to
decide whether nodes should attempt do do the right thing when connected
to switches that are blocking ports while doing spanning tree processing
(loop detection), or whether we want to simply define some numbers as
"good enough".

It looks to me as if you're agreeing that having the nodes attempt to
work out that the link is functional - from which point relatively small
timer numbers are good enough for the algorithm's purposes.

I think my main point is that the numbers in the draft currently aren't
right for anyone - except perhaps by some fluke of some implementation,
where LL address configuration is being delayed already by several seconds,
perhaps while attempting to get a DHCP response, which fails because the
port is blocked, then once that is done with, it just happens that the
numbers in the draft are what is needed (on that implementation) to get
past the port block time.

kre

---

From: Mika Liljeberg <[email-masked]>
Date: 07 Apr 2003 22:50:20 +0300

> that (150-200 ARP requests in a minute, occasionally), but it is something

Maybe it wouldn't be so bad to use exponential backoff here? Start with
an initial delay of a few hundred milliseconds (tuned according to the
link-layer latency), and double the interval with every transmission. I
could live with that.

Also, I would suggest that ANY packet received from the link is a signal
that the link is responsive, so even if there are no nodes that
recognize 169.254.0.0, it would be likely that the algorithm would
terminate before the maximum timeout.

> information from the interface config so they know the local environment).

Um, yeah. There are devices with on-demand interfaces, but even so the
first packet is likely to be a multicast generated by e.g. the LLMNR
responder. So scrap that idea.

> timer numbers are good enough for the algorithm's purposes.

Well, I would welcome an approach that spends less than 10 seconds
configuring a LL address (barring those damnable switches).

	MikaL

---

From: Scott Lawrence <[email-masked]>
Date: 08 Apr 2003 12:26:11 -0400

Robert Elz <[email-masked]> writes:

> [...]

I favor the simplest of approaches - use short timers (which means the
whole thing works quickly in the unsegmented LAN case), and just let
the collision detection work to resolve conflicts when the port
unblocks (or other temporary partition ends).

I think that the thing to keep in mind is that the probability of the
problem occuring is low so long as everyone is making good random
address choices.  Further, it only causes a problem when the address
had actually come into active use (used to set up a TCP connection or
made known to some other node).  If my node is behind a blocked port,
I will be able to put the address into use only on my own segment -
further reducing the likelyhood that I can get to the problem of
discovering a conflict with an active address.  Since the time window
is not long even in the case of a slow spanning tree bridge, these two
things have to happen quickly.

Further, all the code to deal with conflicts on an active address
still needs to be there regardless of what we do during the selection
process. 

I think the complexity cost is not justified by the frequency (low)
and severity (not very) of the problem.

-- 
Scott Lawrence        
  Actively seeking work 
  http://skrb.org/scott/
  [ <[email-masked]> is deprecated ]

---

From: Erik Guttman <[email-masked]>
Date: Fri, 11 Apr 2003 14:54:27 +0200 (CEST)

Folks,

Please help try and close these issues by Apr 17.

Aside from the authors of the proposed text it appears no one supports
these issue formulations.  Given that there are millions of hosts using
LL right now with fixed timer values - successfully - this cannot be a
very hard problem to get right for a general case.  If it doesn't work
in some cases, well gee, we will get conflicts we will have to resolve.

Please either support or reject these issues or offer a *simple and
complete alternative.*

Erik Guttman
Zeroconf WG chair