Subject: RE: ZMAAP changes

From: "Mayer, Jim" <[email-masked]>
Date: Wed, 28 Mar 2001 11:53:05 -0500

Hi,

What was the reasoning behind prohibiting periodic advertisements in the
zmaap-00.txt spec?

It seems to me that a practical protocol along the lines of the following
could be developed:

(1) AIU messages contain an address, an ID, and an "assertion time."

(2) The "assertion time" is a hint indicating that some mini-MAAS believes
that it will need the address for at least the stated time.  An system where
all mini-MASSs advertised an assertion time of zero would be equivalent to
Erik Guttman/Stuart Cheshire proposal.

(3) If a mini-MAAS maintains an AIU cache, and if an AIU for a cached
address/ID is received, then the only effect is to (possibly) extend the
"assertion time" of the cache entry up to some (modest) maximum.

(4) If a mini-MAAS that would normally be defending an address (e.g., "like
the allocator and any mini-MAAS which has had an application register
interest in the allocation") noticed that the "assertion time" was "about
to" expire, it would issue a new AIU.  The definition of "about to" would be
something like "reached a randomly selected percentage (say, from 60 to 90
percent) of the AIU lifetime".

I would think that a protocol such as the one I outlined above would support
caching, avoid the "dueling mini-MASS" problems mentioned in Mr. Guttman's
note, would support conflict detection, and would have a minimal impact on
network traffic.  There is no need for an explicit "cache clearing" message,
as cache entries would simply drop out as their "assertion time" expired.

I have only been monitoring this list a short while, and I'm curious about
how well my assumptions about the problem match reality!

-- Jim Mayer

> -----Original Message-----
> From: Octavian Catrina [mailto:[email-masked]]
> Sent: Wednesday, March 28, 2001 4:09 AM
> To: [email-masked]
> Subject: ZMAAP changes
> 
<snip>

> The minimal protocol outlined above is some kind of baseline. 
> We can try to
> extend it. But as long as we don't accept periodic 
> advertisements, even at a
> lower rate, there is no way to detect conflicts.

<snip>

---

From: "Octavian Catrina" <[email-masked]>
Date: Fri, 30 Mar 2001 11:51:51 +0200

Jim Mayer wrote (http://www.merit.edu/mail.archives/zeroconf/msg00840.html)
>What was the reasoning behind prohibiting periodic advertisements in the

We had a preliminary version with periodic advertisments that maintained the
consistency of the allocation records in all the mini-MAASs (AAP-like). The
periodic advertisments were dropped because the overhead of transmitting and
processing them was considered excessive, an overkill for a relatively low
probability of claiming clashes and even much lower probability of allocation
conflicts.

For example, we can expect the following average numbers of attempts to find a
free address using random selection only:

Already	Average number of attempts
allocated	for new allocation
10%		1.1
20%		1.2
30%		1.4
40%		1.6
50%		2.0
60%		2.5
70%		3.3
80%		5.0
90%	     10.0

Occasionally the number of attempts can be larger than the average, but this
shouldn't be a problem below 20-30% utilization of the address space. For
example, in ZMAAP draft 00 we assumed allocation of IPv4 mc addresses from the
admin local scope, with a size of 64K. I suppose that 20% of them are more than
enough for a zeroconf network. The proposal in my previous e-mail was based on
these assumptions.

According to Erik Guttman's e-mails we still don't have a final decision for the
IPv4 scopes to be used by ZMAAP. It is a quite different problem to design a
ZMAAP able to efficiently allocate 100% of a short range of addresses. We must
clarify which are the address ranges, otherwise we can't really make much
progress.

Anyway, it would be great to find a simple way to enable (an optional) caching
of addresses allocated by the other mini-MAASs.

>It seems to me that a practical protocol along the lines of the
> following could be developed:
> ...

As I understand, your proposal is to maintain a lifetime field in the ZMAAP
messages, but with different semantics, just to enable address caching.

Essentially, you propose:
- to use it "as a hint indicating that some mini-MAAS believes that it will need
the address for at least the stated time".
- and "the only effect is to (possibly) extend the assertion time of the cache
entry up to some (modest) maximum".

This seems quite fine - and compatible with the basic framework in my previous
e-mail. I was mainly interested in changing the meaning of allocation lifetime
in the protocol: let any session participant control how much time an allocation
is defended by its local mini-MAASs and avoid the overhead of maintaining a
single and accurate value in the records/caches of all the mini-MAASs.

With your proposal, the lifetime of owned/monitored addresses remains under the
control of the local app. To further clarify the issues, let's distinguish 2
categories of allocation records maintained by a mini-MAAS:

- Records for addresses used by local apps, created in the following 2 cases
(more details in the previous e-mail): a local app asks (and obtains) a new
allocation from the mini-MAAS; or a local app asks the mini-MAAS to monitor an
address it uses but was allocated elsewhere. The mini-MAAS has accurate
information about the use of these addresses. It is responsible for defending
them for the duration (lifetime) the apps request (unless a conflict is
detected). The owner/monitor states and transitions apply to these records.

- Records of any other addresses about which the mini-MAAS has some information
(from received messages) that they are not available for allocation. This is the
"cache". We can't afford to grant to all the mini-MAASs prompt and accurate
information about the addresses in use. So we can't rely on the accuracy of
these caches. A mini-MAAS may consult the cache when trying to make a new
allocation, but shouldn't defend the cached addresses. The monitoring mechanism
is simple, reliable and should be sufficient.

The AIU that announces lifetime to enable caching needs not be repeated. If it
is lost, the cache entry expires, but the address/owner monitor is there to
defend the address.

When the local app deallocates an address (before the intended end-time), the
mini-MAAS removes its record, but does not send an AIU to cancel the allocation.
This is OK because the session may go on with the remaining participants. When
none are left, the address is no longer defended and can be allocated by the
mini-MAASs of the session participants. However, the cache entries continue to
prevent the other mini-MAASs from trying to allocate the address until they
eventually expire.

The "(modest) maximum" lifetime value can't be too modest, otherwise the AIUs
for its extension would be sort of lower rate AAP periodic AIUs. I wonder how
can we choose a convenient value: 30 minutes, 60 minutes?

I have several reasons to dislike the delayed defense: it's much less reliable,
more complex and increases the allocation delay (these are more annoying for
operation without cache when the probability of claiming clashes increases).
This is why I suggested a simple mechanism to switch from monitor state (delayed
defense) to owner state (immediate defense), when a monitor detects that the
owner (initially the allocator) is no longer active. It could provide immediate
defense after the disappearance of the allocator at practically no cost.
Reception of an AIU for the address would trigger a return to monitor state to
avoid having more than one owner (this could occur in the unlikely case when 2
mini-MAASs make a delayed defense at the same time).

If the AIU message is also used to announce lifetime, not just to defend, the
owner/monitor switching must also be changed. A mini-MAAS could also switch from
monitor to owner when sending an AIU that extends the lifetime.

To conclude, caching would allow ZMAAP to work better when a larger fraction of
the address space in a scope has been allocated. I don't think it is necessary
below 20%, so it can remain optional.

Caching based on lifetime announcement requires the additional transmission of
an AIU at the end of claiming and whenever the lifetime is extended. Its
efficiency (without deallocation) also depends on the choice of a maximum
lifetime value, which determines how fast the cache entry is removed when the
address is no longer used. But I don't see how it can really improve the
detection of allocation conflicts (we have claiming/defense to prevent them),
unless the lifetime extensions become as frequent as AAP periodic advertisments.

Octavian.

---
Dr. Octavian CATRINA
International University in Germany
School of Information Technology