Subject: [RRG] NTP and various proposals.

From: Randall Atkinson <[email-masked]>
Date: Mon, 25 Feb 2008 16:06:35 -0800

I must be missing something in this recent exchange...

How is it different for NTP in some future proposal than
for current NTP in today's Internet along a path that has
very high degrees of path variability over time ?

Paths can vary a great deal today, either the actual path,
the transit latency, or both concurrently.  NTP performs
better on stable paths, sure, but it isn't obvious how any
of the new proposals is different than running NTP along
a more variable path in today's IPv4 Internet.

Ran

--
to unsubscribe send a message to [email-masked] 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

---

From: "William Herrin" <[email-masked]>
Date: Mon, 25 Feb 2008 22:11:45 -0500

>  very high degrees of path variability over time ?

Ran,

NTP works by measuring the behavior of the network between the client
and the server in order to estimate the amount of time it took for the
timestamped packet to reach the client so that the client can set the
correct time. NTP is killed by jitter: whatever the round trip times
are, they have to be fairly consistent from attempt to attempt. Some
paths on the network today will have higher jitter than others. This
is one of the reasons you configure a number of servers for the
client: so that if the path to a server has a high jitter then the NTP
client can exclude it and synchronize with the rest.

Every caching map-encap scheme where every ITR does not have a full
map will experience a delay (some small, some large) during the cache
pull. The NTP client will experience this as jitter: one packet has a
round trip of 400 ms and the next has a round trip of 30 ms. The
client will assume that means it can't accurately estimate the time it
takes to get a packet back to it from the server so it will mark that
server as ineligible for synchronization until the network path clears
up.

If the NTP client regularly communicated with the server, this
wouldn't be a problem. It would see high jitter on the initial attempt
which would settle right down. But NTP is a well behaved protocol.
When the server is responding well and it's in sync, NTP backs off to
where it sends only a single query every thousand seconds or so.
That's more than enough time for the ITR to expire and remove the
cached ETR entry so that on the next attempt NTP sees: jitter.

NTP is really a great litmus test. Every map-encap proposal should
have an explanation for how NTP works during and following deployment.

Regards,
Bill Herrin

-- 
William D. Herrin                  [email-masked]  [email-masked]
3005 Crane Dr.                        Web: <http://bill.herrin.us/>
Falls Church, VA 22042-3004

---

From: Tony Li <[email-masked]>
Date: Mon, 25 Feb 2008 20:46:40 -0800

> cached ETR entry so that on the next attempt NTP sees: jitter.

What this simply requires is that the cache be large enough to hold  
18 minutes worth of correspondents.  This does NOT seem impossible by  
any means.

Alternately, the scheme could have an application aware cache.  Ugly,  
but not impossible.

Tony

---

From: "William Herrin" <[email-masked]>
Date: Tue, 26 Feb 2008 00:48:09 -0500

>  18 minutes worth of correspondents.  This does NOT seem impossible by

Tony,

Plug it in to your favorite map-encap scheme and and factor for the
need to keep the cache entry current and accurate during that 18
minute span of inactivity. Now ask the right question: not is it
possible in general but is it possible for that inactive cache
increase to be cost-effective?

Regards,
Bill Herrin

---

From: Tony Li <[email-masked]>
Date: Mon, 25 Feb 2008 23:58:11 -0800

On Feb 25, 2008, at 9:48 PM, William Herrin wrote:

> Plug it in to your favorite map-encap scheme

That would be the null set.  ;-)

However, to be fair, the issue that you have is with ALL mapping  
schemes, not just map-n-encap.  Everything that relies on a cache is  
going to have a working set and size issues.

> and and factor for the

Entirely possible.  The real question is how much state needs to be  
stored.  That depends on the scope of the mapping resolution box.   
Having a DNS server with a cache that's more than 18 minutes deep  
doesn't sound so horrible to me, if the scope of that server is  
constrained to some smallish [say O(1000)] number of hosts.

Tony

---

From: "William Herrin" <[email-masked]>
Date: Wed, 27 Feb 2008 14:09:22 -0500

>  constrained to some smallish [say O(1000)] number of hosts.

Hi Tony,

It's not just state, it's churn. It's 18 minutes that you have to keep
receiving and asking to receive map updates for the destination even
though there's no associated user-level traffic.

That or the ITR has to do some sort of probability assessment as to
whether the expired data is still valid so that it can use the expired
data for the next NTP packet while it goes out and refreshes the
cache. I've explored this possibility a little with TRRP. It gets
hairy fast.

You can't simply extend the cache validity of course. 18 minutes is
too long for multihoming, let alone mobility.

Regards,
Bill Herrin

---

From: [email-masked] (Noel Chiappa)
Date: Wed, 27 Feb 2008 20:01:47 -0500 (EST)

> From: "William Herrin" <[email-masked]>

    > It's 18 minutes that you have to keep receiving and asking to receive
    > map updates for the destination even though there's no associated
    > user-level traffic.

Huh? Why? I thought Tony mean that you'd just be have to be sure to keep the
binding in the ITR's cache for at least 18 minutes; do that, and the next
NNTP query will reset the timer, and around we go again. No resolution
traffic at all.

    > You can't simply extend the cache validity of course. 18 minutes is too
    > long for multihoming, let alone mobility.

I don't know about multihoming, but let's think about mobility.

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.

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?
Two possible answers that I can see:

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.

Two - there's a cheap/easy way to tell, *when you use a binding*, that it's
incorrect outdated. The only thing is, can we come up with a cheap/easy way
to tell? Asking the resolution system on every tick 'is this binding still
valid' is not cheap/easy. However, there's another way.

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 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.

But this seems to me to be the architectural avenue to work in - find a
cheap/easy way to *tell* when a binding has changed, and do the 'update
everything' actions only when needed.

	Noel

---

From: "William Herrin" <[email-masked]>
Date: Wed, 27 Feb 2008 23:41:01 -0500

>  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.

>  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.

>  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.

>  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.

>  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

---

From: Tony Li <[email-masked]>
Date: Thu, 28 Feb 2008 11:52:11 -0800

> too long for multihoming, let alone mobility.

Bill,

Your assumption here is that all cache entries need to have equal  
validity.  This is not necessary; it's trivial for the cache entry to  
have an associated TTL that tells the ITR exactly how long to retain  
the cache entry.  I'll happily stipulate that interesting NTP servers  
will need a cache entry TTL of more than 18 minutes.  I hope that's  
not an issue to you.

For mobile hosts (i.e., laptops), you crank the TTL down.  For fixed  
hosts, you crank the TTL up.  Straightforward and simple.

Tony

---

From: Dino Farinacci <[email-masked]>
Date: Thu, 28 Feb 2008 11:59:36 -0800

> hosts, you crank the TTL up.  Straightforward and simple.

Not when the ETR is providing the TTL. And the ETR won't know if the  
requester is asking on behalf of a static or mobile host. So all it  
can do is answer with a large TTL and the source-site might have to  
know if it should shorten it. Hmm.

Dino

---

From: "William Herrin" <[email-masked]>
Date: Thu, 28 Feb 2008 15:38:04 -0500

On Thu, Feb 28, 2008 at 2:52 PM, Tony Li <[email-masked]> wrote:
>  the cache entry.

Hi Tony,

That could hardly be my assumption. My horse in this race, TRRP, has
widely variable TTLs for the map cache precisely because I recognize
that one size doesn't fit all.

I do have a couple assumptions though:

* that NTP is a two-way protocol which requires a stable -round trip-.

* that it is desirable for mobile clients to be able to synchronize
their clocks with NTP servers as well, thus the server-side ITR (if
there is one) needs to be able to deal with the client's possibly
frequent ETR changes even if the client's ITR can reasonably expect
the server to stay in the same place.

Regards,
Bill Herrin

---

From: Tony Li <[email-masked]>
Date: Thu, 28 Feb 2008 13:32:12 -0800

> the server to stay in the same place.

If your server side ITR can only learn from mapping changes and your  
mapping function can't keep up with the mobile host, then I'd say  
that your horse isn't cutting the mustard.

Tony

---

From: "William Herrin" <[email-masked]>
Date: Thu, 28 Feb 2008 17:20:36 -0500

Tony,

Then I'd say it's a good thing those "ifs" don't line up with my
horse. If you'd care to read the TRRP proposal, I'd welcome your
insight.

We've veered off onto an unproductive tangent. This thread started
with "Why should NTP be different when ITRs are involved?" to which
the answer is, "Cache expiration causes jitter."

You wondered, "Why not just increase the TTL?" The answer is that
unless you have some other mechanism that -guarantees- a change of
state will reach the cache, the TTL provides the primary guaranteer
that state change does propagate.

If you'd like to propose an alternate guaranteer and explore the
benefits, liabilities and degree to which it satisfies the
requirements of a propagation guaranteer, lets have at it.

Regards,
Bill Herrin

---

From: Markus Stenberg <[email-masked]>
Date: Fri, 29 Feb 2008 13:46:34 +0900

> cached ETR entry so that on the next attempt NTP sees: jitter.

That 2^10 seconds is just default maximum; protocol allows for  
configurations to back off up to 2^17 seconds (day and half).. That  
type of configurations would break in any system that isn't pure push,  
due to potential latency being either the packet roundtrip time, or  
the lookup time + packet transit time.

Of course, NTP would recover from that (I believe; I haven't verified  
by reading the code.. err, 'protocol' draft) by marking the peer  
insane, winding up using someone else for awhile, and then possibly  
restarting using peer with the backoff timer starting from scratch.  
Still, it wouldn't be pretty.

Cheers,

-Markus