Subject: [magma] MLDv2: operation without state change reports: include list

From: Erik Nordmark <[email-masked]>
Date: Fri, 14 Feb 2003 18:02:51 +0100 (CET)

To try to comprehend this complex protocol I first tried to understand
how things work when the link is broken while a bunch of listeners change state
(so that all state change reports are lost) and then the link starts working
to see how the router build state from the IS_IN and IS_EX messages only.

Looking at the INCLUDE case (the router is in INCLUDE state and so is
all the LISTENERS), then the EXCLUDE case, and finally the mixed case
I'm utterly confused.

Part of the confusion is due to the definition of the source lists A and B
in section 6.4.1.

I interpret (A) to mean that this is the list of sources that listeners
in INCLUDE state have reported. That interpretation seems consistent with the
text in appendix A.3 (keep the source list for those in INCLUDE state
so that it is quick to switch to INCLUDE state on the router when the
last EXCLUDE listener goes away).

But that seems inconsistent with the rules in the tables in in the mixed case.
Section 6.4.1:
    INCLUDE (A)       IS_EX (B)     EXCLUDE (A*B, B-A)

This modifies A to A*B even though there is no change in the 
source list for any of the listeners in INCLUDE state.
Should be EXCLUDE (A, B-A) to be consistent.

    EXCLUDE (X,Y)     IS_EX (A)     EXCLUDE (A-Y, Y*A) (A-X-Y)=MALI 

This changes X to A-Y, even though there is no change in the
source list for any of the listeners in INCLUDE state.
Should be EXCLUDE(X, Y*A) to be consistent.

Section 6.4.2
   INCLUDE (A)     TO_EX (B)      EXCLUDE (A*B,B-A)    (B-A)=0

This changes A to A*B even though there is no change in the 
source list for any of the listeners in INCLUDE state.
Should be EXCLUDE (A, B-A) to be consistent.

   EXCLUDE (X,Y)   ALLOW (A)      EXCLUDE (X+A,Y-A)    (A)=MALI

This is OK *if* the ALLOW was sent by a listener in INCLUDE
state if sent by a listener in EXCLUDE state the result
should be EXCLUDE (X, ...).

   EXCLUDE (X,Y)   TO_EX (A)      EXCLUDE (A-Y,Y*A)    (A-X-Y)=Multicast

This changes X to A-Y even though there is no change in the 
source list for any of the listeners in INCLUDE state.
Should be EXCLUDE (X, Y*A) to be consistent.

The next to last example above points out that in order to maintain the
source list for the listeners in INCLUDE state properly it is necessary
that the ALLOW message indicate whether the sender is in INCLUDE or EXCLUDE
state which seems impossible in the current packet format and sending rules.

It seems like the definition of set (A) in 6.4.1 has somehow evolved
from being the union of the source list from all listeners in INCLUDE
state, to being a list of sources that are explicitly ALLOWed.
But with that definition it is no longer possible to use this
list for rapid and correct change from EXCLUDE to INCLUDE state
on the router when the last EXCLUDE listener goes away.

Did I misunderstand something?

  Erik

_______________________________________________
magma mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/magma

---

From: "Rolland Vida" <[email-masked]>
Date: Fri, 14 Feb 2003 22:31:25 +0100

Erik,

> Should be EXCLUDE (A, B-A) to be consistent.

I will try to explain our reasoning step by step:

  1. There is receiver Rec1 in INCLUDE (A). Its report turnes the router in
INCLUDE (A)
  2. Now the router receives an IS_EX (B) report. It could be sent by a
different receiver (Rec2), or by Rec1, that switched in the meantime to
EXCLUDE (B), but its TO_EX(B) change report has been lost.
  3. What is sure for the router, is that sources in B-A should be blocked
  4. There is a "conflict" only about sources in A*B, as these were
explicitely asked to be allowed previously, and explicitely asked to be
blocked now. So the router keeps them for the moment (they will be
forwarded, until their timers will expire). If no receiver confirms
explicitly that it wants to receive them, they will migrate in the second
list (together with B-A).
  5. There is no conflict about the sources in A - (A*B), i.e. A - B. They
are not in the second list of the Exclude expression, so they will be
forwarded. The router does not have to keep them anymore in its state. The
only problem is how to recover them, if someone is explicitely interested in
them, and the router switches in the INCLUDE mode in the meantime.
  6. To answer that, we should note that on the reception of the IS_EX
message, the multicast address timer is set to MALI. So the switch to the
INCLUDE mode is delayed. In the meantime, if there is indeed a receiver that
is in INCLUDE (A), it will send its regular report (which is certainly
scheduled before the expiration of the multicast address timer). In this
case, the router will switch to Exclude ((A*B) + A, (B-A) - A), i.e. Exclude
(A, B-A). This is what you wanted to obtain in the first place. So if the
exclude-include switch occurs, the router state will be correctly updated.
  7. The advantage of this complicated mechanism is that we reduce the
router state with A-B source addresses.

> Should be EXCLUDE(X, Y*A) to be consistent.

The same reasoning applies. The router cannot be sure that there was no
change in the source list for the listeners in Include state, as the change
report might have been lost.
What is sure, is that there is no conflict for the sources in Y*A (they
should be blocked), but there is a conflict for the sources in A-Y (they
were not blocked before, but they are asked to be blocked now). The sources
in X can be deleted from the router state. If there is someone interested in
them, it will confirm its interest anyway, before the multicast address
timer expires.

> Should be EXCLUDE (A, B-A) to be consistent.

The same reasoning.

> should be EXCLUDE (X, ...).

I do not follow you here. The first and the third column of the table
represent the old and the new router state, not the state of the listener.
The router only knows that it received an Allow (A) report. Thus, someone
wants to listen to those sources. It will update its state accordingly.
Sources in Y-A stay blocked, those in A should be added to X.

In this case, the multicast address timer is not updated. So if it expires,
the router switches to Include (X+A), which is ok.

> Should be EXCLUDE (X, Y*A) to be consistent.

The same reasoning as for the first two cases.

> state which seems impossible in the current packet format and

As I explained, this is not necessary.

> on the router when the last EXCLUDE listener goes away.

I hope that now I clarified that the multicast address timer is always
updated when an IS_EX or a TO_EX report is received. So the switch to the
INCLUDE mode cannot occur immediately, giving the receivers in INCLUDE mode
the time to send their reports, and update the router state accordingly...

Thanks,
Rolland

-------------------------------------------------------------
"The optimist claims that we live in the best of all possible
 worlds, and the pessimist fears this is true." - J.B. Cabell

  Rolland VIDA, Ph.D.
  Researcher, Budapest University of Technology and Economics
  Department of Telecommunications and Telematics
  Magyar Tudosok krt. 2, Room E324, H-1117, Budapest, Hungary
  Tel: +36 1 463 11 02        E-mail: [email-masked]
-------------------------------------------------------------

---

From: "Rolland Vida" <[email-masked]>
Date: Fri, 14 Feb 2003 22:31:25 +0100

Erik,

The same reasoning.

Thanks,
Rolland

  Rolland VIDA, Ph.D.

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 18 Feb 2003 16:14:40 +0100 (CET)

>   3. What is sure for the router, is that sources in B-A should be blocked

Agreed.

> list (together with B-A).

Yes, but if all the EXCLUDE listeners go away in the mean-time
you'll do the quick switch back to INCLUDE (A*B), when
in fact the conservative thing would be INCLUDE (A).
("Conservative" because if there is only one listener which switches
between IS_IN(A), IS_EX(B), and no interest you'd overestimate
the interest for a while.)

The X in EXCLUDE(X,Y) is stated to be the union of the source lists of INCLUDE 
listeners to allow for this quick switch. The above doesn't satisfy that
statement.

> exclude-include switch occurs, the router state will be correctly updated.

Sorry, but my complexity meter just got overloaded and broke :-)

Can you provide a correct and succinct statement of what X and Y
in EXCLUDE (X, Y) actually mean? And names for X and Y would also
help having this discussion. (The document calls them "A" and "B"
but those are not 

You seem to be saying that X will over time converge towards the union
of the INCLUDE mode listeners but at any given time
it might have more as well as less members than this union.
And though some (to me incomprehensible) dependency
on time constants the fact that X in some cases is less than this union
will not cause the protocol to fail.

What is the definition of Y?

> router state with A-B source addresses.

The disadvatage is that the protocol is extremely hard to validate
and understand.
And the above state reduction only applies until the INCLUDE lister
fixes the state to be EXCLUDE (A, B-A).
If it is a single listerner that switches from INCLUDE(A) to EXCLUDE(B)
then the long-term result will be a router state of EXCLUDE (0, B)
thus you are not immediately reaching this target state. My point is
that the claimed benefits of this scheme do not seem significant.

So I don't see the harm in simplifying the semantics of the retained
address list(s) in the routers to 

What I can understand is a model where you instead 
define X and Y in EXCLUDE (X, Y) as
X = include list: 
   the union of the source address lists for listeners in INCLUDE mode.
   If all else fails the elements in
   this list time out using the source address timer.
   If all else fails new elements are added to this list due current 
   state reports in response to periodic general queries.
Y = exclude list:
   the intersection of the source address lists for listeners in EXCLUDE
   mode.
   If all else fails entries are removed from this list due to current 
   state reports in response to periodic general queries.
   If all else fails entries are added to this list by computing a new
   intersection set across the set of responses to a periodic general query.

Then the routing protocol can express disinterest in Y-X.

> them, it will confirm its interest anyway, before the multicast address

I assume you mean source address timer and not multicast
address timer.
And the same complexity concern of depending on the timers
to correct the temporary inconsistency before a router can switch to INCLUDE
state applies here as well.

> the router switches to Include (X+A), which is ok.

My point is that the above ALLOW from an exclude mode
listener makes the first set (do you have a name for "X" in EXCLUDE (X, Y)??)
is larger than it needs to be.
Thus if you believe your own point #7 about limiting the size of
the source address lists at the router then having EXCLUDE(X, Y-A)
when receiving an ALLOW from a exclude mode listener would make sense.

> the time to send their reports, and update the router state accordingly...

How many people on the mailing list understood this?

Please respond with yes or no.

   Erik

---

From: Erik Nordmark <[email-masked]>
Date: Tue, 18 Feb 2003 16:14:40 +0100 (CET)

Agreed.

   Erik

---

From: "Rolland Vida" <[email-masked]>
Date: Wed, 19 Feb 2003 19:27:46 +0100

[...]

> in fact the conservative thing would be INCLUDE (A).

As I explained, the exclude timer cannot expire so quickly, as it has just
been set to MALI by the received IS_EX report. If there is a host in
INCLUDE(A) mode, it should confirm its interest (by sending a report) before
that exclude timer expires. If it does so, then the "include list" of the
router will be set again to A. So when the switch occurs, the router
correctly transitions to INCLUDE (A).

> the interest for a while.)

If a listener switches from any state to no interest (i.e., it does a soft
leave), there's no way to avoid the overestimation of the interest for a
while. That's the basic idea of a soft state protocol, like MLD. You cannot
decide that the listener is not there anymore until the timer has not
expired. So you are obliged to forward packets, even knowing that the only
listener might have left right after having sent his report.

> listeners to allow for this quick switch. The above doesn't satisfy that

I think it does.
You are sure that, at the moment when the quick switch occurs, X is the
union of the source lists of INCLUDE listeners. However, you cannot be sure
of that at a given moment in time, while the exclude timer is still running.
I explain:
- suppose that at time t, X really represents the union of the source lists
of INCLUDE listeners.
- now at time t+1, the router receives an IS_EX (A) report. The router
cannot decide if that report was sent by a listeners previously being in
INCLUDE state or in EXCLUDE state, as state change reports might have been
lost. The "include list" will now be modified, and you cannot be sure
anymore that it represents the union of the source liste of INCLUDE
listener, as you are not sure about whether the IS_EX report was sent by a
previously INCLUDE listener or not. Nevertheless, the exclude timer is set
to MALI
- before that timer expires, at any point t+2 in time, if there still are
INCLUDE listeners, they will send reports. Thus, the include list will be
updated.

Once again, what is sure, is that when the exclude timer expires, the
include list of the router will correctly represent the union of the source
lists of INCLUDE listeners.

> in EXCLUDE (X, Y) actually mean?

The draft defines X as:
  Sources that at least one node has requested to be forwarded
As explained above, X represents the union of the source lists of INCLUDE
listeners only when the include switch occurs.

The draft defines also Y:
  Sources that MLD will suggest to the routing protocol not to forward
This means that sources from Y were asked to be blocked by all the listeners
on the link.

> And names for X and Y would also

You mean changing X and Y to "include list" and "exclude list"?
The document uses A and B for the definition, but then in the tables we are
obliged to use X and Y as well, as there are more then two source lists to
use. We could use A, B, C and D as well, instead of A, B, X and Y.

But you are probably right that we could make the text clearer by defining
separately the roles of the source lists when in include or in exclude mode.
The following paragraph should then be rephrased/replaced:
   Note that there will be two sets only when a router's filter mode for
   a multicast address is EXCLUDE.  When the filter mode is INCLUDE, a
   single set is used to describe the set of sources requested to be
   forwarded (e.g. simply ( A ) ).

> it might have more as well as less members than this union.

Right.

> will not cause the protocol to fail.

Right.

> What is the definition of Y?

I specified it above.

> The disadvatage is that the protocol is extremely hard to validate

You agreed that the protocol functions correctly. There are already several
implementations of it up and running (LIP6, KAME, Cisco?). Now if i would be
a router vendor, and there would be an algorithm that functions correctly,
is of the same complexity (in number of operations) as another algorithm,
but it significantly reduces router state, I would buy it, even if it is
hard to understand why is a list set to A and not to B.

As I said, by using the mechanism proposed by the protocol, router state is
reduced with A-B IPv6 addresses. This is done during MALI, i.e. 2*125+10 =
260 seconds by default. So I can reduce router state for more than 4
minutes, with maybe tens of IPv6 source addresses, for each multicast
address that has listeners on the link.

> fixes the state to be EXCLUDE (A, B-A).

If there is no receive in INCLUDE mode, than the reduction applies until the
exclude timer fires, i.e. MALI (260 seconds, as stated above)

> thus you are not immediately reaching this target state.

If I would apply your proposed mechanism, the final state would be EXCLUDE
(0, A+B), until the exclude timer expires. So there are still A-B states
that are saved, as I stated already.

> > If there is someone interested in

No, I meant multicast address timer (or what you called "exclude timer").
The include switch occurs when this timer fires, so an interested listener
should confirm its state before that occurs.

> to correct the temporary inconsistency before a router can switch
> to INCLUDE state applies here as well.

Again, it is a tradeoff between router state and temporary inconsistency, if
you wish. But that temporary inconsistency with the common understanding of
what a source set should represent does not affect in any way the
correctness of the protocol.

Maybe Bill or Isidor could comment on this (if they had the patience to
follow this discussion this far :-)), as the same trade-off applies for IGMP
as well.

> when receiving an ALLOW from a exclude mode listener would make sense.

The point is that the router knows nothing about whether the listener who
sent the Allow (A) is in Include or Exclude mode. Thus, it cannot handle the
two cases separately.
Assume now that it handles it as you say, by transitioning in EXCLUDE (X,
Y-A). Now suppose that the listener who sent the report was actually in
Include mode. As the Allow message does not update the exclude timer, an
include mode switch could occur. Thus, the router tansitions to INCLUDE (X).
therefore, source from A-X will be blocked, even though there is a listener
who asked them explicitly. This would be a flaw in the protocol.

As far as i see, my point #7 about reducing the routing state applies only
for the cases where such flaws will not be obtained.

Rolland

---

From: "Rolland Vida" <[email-masked]>
Date: Wed, 19 Feb 2003 19:27:46 +0100

[...]

I think it does.

The draft defines X as:

Right.

Right.

I specified it above.

Rolland