Re: [RRG] NTP and various proposals.

["William Herrin" <bill@herrin.us>]

On Wed, Feb 27, 2008 at 8:01 PM, Noel Chiappa <jnc@mercury.lcs.mit.edu> wrote:
>  I claim that trying to do mobility (or much of *anything*) with the timeout
>  field in the binding is inappropriate. My reasoning is simple: to get
>  reponsesiveness within N seconds, you'd have to set the timeout on the
>  binding to N seconds, and that means you radically jack up the amount of
>  queries/updates (which depends on whether you are in a pull or push model).
>  This is clearly nonsensical.

Noel,

If the overhead is 10% it's nonsensical? Other widely popular systems
have dedicated 20% or more overhead to enablers. What if the overhead
is only 1%? Or a tenth of a percent? What if the endpoint can adjust
the overhead so that if it knows it's likely to need a fast change it
accepts 10% and if it knows it can tolerate a slow change it backs off
to only consuming a tenth of a percent?

You've rejected this approach too quickly.


>  Clearly the right thing is for timeouts on bindings to be longer, and when a
>  binding *changes*, entities using that binding have to have some way of
>  finding out that the binding has changed. That's economy of effort: if the
>  binding doesn't change, there's *zero* overhead, and if it does change, only
>  the people using it pay (once) to get the new binding. So how do we do that?

The chip makers have been struggling with this one for decades. In an
MPP system, how to you propagate the knowledge that a potentially
cached page of memory has changed?

Thus far, the answer is: you don't. You break up the task and send the
components off to subsystems which don't interact with memory space
that isn't exclusively tasked to them.

If you can figure out a novel approach to this problem then whatever
you're being paid, it's not enough.


>  One - the 'owner' of the binding remembers who has a copy, and tells them
>  when it's changed. That requires us to maintain a lot of state (who has a
>  copy of the binding), it's brittle, subject to failure if that state is
>  damaged or lost. So I reject that one out of hand.

Again, you've rejected this approach too quickly. I agree that it is
not reliable, thus it can't serve as the primary notification system.
It could, however, serve to accelerate the propagation of that
knowledge in a majority of cases using only a moderate amount of
state.


>  To use an EID->RLOC_of_ETR binding, the packet has to pass through the ETR.
>  All that has to happen is that the ETR (which is *forwarding* packets, so
>  it's by definition selecting a next-hop for them) has to have a table of
>  (EID, next-hop) bindings (the table may be notional, in that in some designs
>  it is currently just a mapping, not an actual table of tuples, but I propose
>  we make it an explicit table). Now the solution is obvious: if a packet
>  arrives at an ETR, and there's no EID->next_hop binding (or it's marked
>  "moved to a new ETR"), the source (ITR, etc) are sent a "not here" message.
>  *Then*, and only then, does it query the resolution system to see where the
>  destination has moved too.

If I understand, you're talking about negative-acknowledgment (NAK).

NAK has seen use in a number of protocols, but they share a
commonality that isn't present here: In NAK-based protocols there's a
sideband whose continued presence signals, "yes I'm still listening."
An example would be a modem file transfer protocol where the receiver
says nothing until a CRC fails and then responds that packet #X must
be resent. In the example, the sideband is the modem carrier whose
presence indicates that the receiver is still there.

NAK has value as a secondary mechanism through which the ITR can learn
early that a cached map is no longer valid. In fact, I use NAK that
way in TRRP both in the core and in optional PCN. But as a primary
mechanism it isn't valid without the sideband.


>  (If you want even more efficiency, the old ETR can redirect the ITR to the
>  new ETR. More complex, because the destination has to update all its old
>  ETRs, etc, but faster - it can even triangle-route data packets instead of
>  dumping them.)
>
>  The exact details I'm hazy on, because I don't know exactly what the
>  performance/etc targets are, and we're back in that
>  complexity/overhead/performance vector-space.

This is explicitly contemplated in TRRP-Via. It's a fine secondary
mechanism that has a decent probability of closing the gap between
actual change and cache change. But it's only a probability, not a
certainty. Can't have a channel that dies and stays dead when this
doesn't work.

So, returning to your original question: That's why you can't just
keep the map cached for as long as it's convenient.

Regards,
Bill Herrin



-- 
William D. Herrin                  herrin@dirtside.com  bill@herrin.us
3005 Crane Dr.                        Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

--
to unsubscribe send a message to rrg-request@psg.com with the
word 'unsubscribe' in a single line as the message text body.
archive: <http://psg.com/lists/rrg/> & ftp://psg.com/pub/lists/rrg