Question on Loosely Synchronized Router Clocks

Kevin_Oberman · September 17, 2007, 9:28pm

Date: Mon, 17 Sep 2007 14:03:33 -0700
From: "Xin Liu" <smilerliu@gmail.com>
Sender: owner-nanog@merit.edu

Dear Nanogers,

We are a bunch of academic researchers interested in Internet
security. We notice that some research papers require that BGP router
clocks be globally synchronized to a 5-minute granularity. If a
router's clock is off by more than 5 minutes, it cannot forward
packets, but there's no other side effect. From an operational point
of view, do you think it is a practical requirement? If not, what are
the potential problems that prevent router clocks from being loosely
synchronized? If you consider 5-minute too small, what do you consider
as a practical clock skew requirement for BGP routers on the Internet?

We'd appreciate your input very much. It will help us understand
what's practical and what's not in our work. Please reply to us
directly.

What papers? I can assure you that BGP has no such requirement. I
suspect sBGP and SoBGP might have such a requirement, but that's not
"real world".

I had a router that lost it's NTP servers and was off by about 20
minutes. The only obvious problem was the timestamps in syslog. (That's
what alarmed to cause us to notice and fix it.)

Valdis_Kletnieks · September 17, 2007, 10:02pm

Trying to correlate logfiles with more than a several-second offset is
good and sufficient reason in itself to make sure everything is NTP-synched.

Of course, if your network runs so well that you never *notice* the offsets
because you never have to correlate logfiles, you're probably either a better
net admin than I, or merely more oblivious..

Bandy_Rush1 · September 17, 2007, 10:17pm

i conversed offline with the OP. he was reading a sigcomm research
paper and confusing it with the internet.

randy

Deepak_Jain · September 17, 2007, 10:22pm

So to bring the conversation to something more sequitur and relevant.

1) Its not hard <tm> to keep all of your devices in your network sync'd to the same clock. Especially if you use standardized configuration control.

2) And a reasonable number is on the order of seconds (or ~1 second) rather than minutes which is almost the same as being unsynch'd.

3) It is not guaranteed, but not hard to be sync'd to a level of precision on the order of a second or two using globally-available NTP sources to every other network you might directly connect with.

I'm slightly suspicious of all the CDMA/atomic clock other NTP sources (for "higher precision") people point their IP gear at -- simply because IP doesn't need the same level of precision as SONET, at least, not yet.

[exclusions for my suspicion include any NTP sources I run, but that's merely hubris ;)].

Deepak Jain

Xin_Liu · September 17, 2007, 10:54pm

Sorry for the confusion. Let me clarify.

We are interested in a number of questions:
1. Can we assume loosely synchronized router clocks in the Internet,
or we have to make absolutely no assumption about router clocks at
all?
2. If the router clocks are indeed loosely synchronized, what is the
granularity we can assume? Particularly, we are interested in whether
we can assume router clocks are synchronized within 10 minutes.
3. It's always possible that a router's clock goes wrong. In practice,
how often does this happen?

Thank you for all the replies.

Best
Regards,

Xin Liu

Bora_Akyol2 · September 17, 2007, 11:21pm

IMHO:

What ever solution you end up proposing should able to handle (3) and should
work with arbitrary boundaries for (1) & (2).

We don't want to add another failure mode to the network that depends on
time synchronization.

You don't want to shift the problem from BGP to NTP.

Regards

Bora

Janet_Sullivan · September 18, 2007, 12:46am

Xin Liu wrote:

1. Can we assume loosely synchronized router clocks in the Internet,
or we have to make absolutely no assumption about router clocks at
all?

Make no assumption. I've seen plenty of routers who aren't even on the correct year. Routers can work just fine while thinking its 1999.

Rob_Seastrom2 · September 18, 2007, 12:48am

"Xin Liu" <smilerliu@gmail.com> writes:

Sorry for the confusion. Let me clarify.

We are interested in a number of questions:
1. Can we assume loosely synchronized router clocks in the Internet,
or we have to make absolutely no assumption about router clocks at
all?

Make no assumption.

2. If the router clocks are indeed loosely synchronized, what is the
granularity we can assume? Particularly, we are interested in whether
we can assume router clocks are synchronized within 10 minutes.

It's not even a fair assumption that all routers have clocks (as in
wall time / time of day or year clocks, not CPU clocks).

3. It's always possible that a router's clock goes wrong. In practice,
how often does this happen?

Let's suppose you were writing software for a router and you wanted it
to behave in a certain fashion if its clock were out of sync with some
time standard, say for the sake of argument, TAI. How would the
software in this router go about determining that it was out of sync
with standard time?

---Rob

Xin_Liu · September 18, 2007, 3:55pm

Ideally, yes, a protocol should not rely on clock synchronization at
all. However, to ensure freshness of messages, we don't have many
choices, and clock synchronization seems to be the least painful one.
So we asked about router clocks on the current Internet. If normally
router clocks are synchronized and we have a mechanism to detect and
fix out-of-sync clocks, is it reasonable to assume clock
synchronization in the rest of our design?

Best
Regards,

Xin Liu

Bora_Akyol2 · September 18, 2007, 4:09pm

You can check freshness of a message by means of sequence numbers, no?

Bora

Adrian_Chadd · September 18, 2007, 4:16pm

Not without specifying it in the design.

adrian

Xin_Liu · September 18, 2007, 4:25pm

Sequence number has its own problems. Message sources have to remember
sequence numbers even when it reboots or crashes. Message verifiers
have to keep states too, and whenever the states go wrong due to
attack or random errors, it's hard to detect and fix them.

Best
Regards,

Xin Liu

Bora_Akyol2 · September 18, 2007, 4:27pm

It is not dependent on time. You'd like a protocol to be self sufficient if
at all possible.

Moving the vulnerability of one protocol to another is not highly desirable
in general.

Looking forward to reading your research results when available.

Regards

Bora

Valdis_Kletnieks · September 18, 2007, 5:51pm

The interesting failure mode is, of course, what happens when you're not
in time sync, so the routing protocol falls over - and due to the lack of
routing table entries, you become unable to reach your timesource.

Steven_Bellovin · September 18, 2007, 6:10pm

I've been talking with Xin offline, and raised that exact point. That
said, in some security contexts there's little choice: you have to have
some way to assure that a message is fresh. There are other choices in
some environment, such as monotonically increasing counters and
challenge/response protocols; depending on other decisions and the
particular context, these may be worse or not even possible. For
example, if someone several hops away from the origination needs to
examine a signed *object*, a timestamp is probably better than a
counter, and challenge/response isn't even possible. That doesn't make
timestamps good -- and they do have many disadvantages -- but they may
be the only choice.

--Steve Bellovin, http://www.cs.columbia.edu/~smb

herrin · September 18, 2007, 6:15pm

Xin,

Depending on the character of the protocol there are at least two
other options for assuring freshness:

1. Sequence numbers. A higher sequence number is fresher and lowered
numbered messages should be discarded if received.

2. Lifetime decrement counter (aka TTL). Each router that sees the
message decrements the counter. When the counter hits zero the message
is stale and gets discarded.

Like Robert says, its not even fair to assume that a router has a time
of day clock, let alone one that is properly syncronized with
everybody else. Even where they do, there's a bootstrapping problem if
you put Time of Day in the critical path: the routing has to work
before NTP can sync.

Regards,
Bill Herrin

Stephen_Sprunk3 · September 18, 2007, 7:40pm

Thus spake "Xin Liu" <smilerliu@gmail.com>

Sorry for the confusion. Let me clarify.

We are interested in a number of questions:
1. Can we assume loosely synchronized router clocks in the
Internet, or we have to make absolutely no assumption about
router clocks at all?

That assumption is _generally_ true, but not often enough that you can rely on it.

2. If the router clocks are indeed loosely synchronized, what is
the granularity we can assume? Particularly, we are interested in
whether we can assume router clocks are synchronized within
10 minutes.

My experience is they'll either be within a few seconds or off by several days to years. There's not much middle ground.

3. It's always possible that a router's clock goes wrong. In
practice, how often does this happen?

It's unlikely to "go wrong" to any noticeable degree _if it was ever correct in the first place_. However, many people do not bother setting the clocks at all (which will often result in a clock that's off by a decade or more), or intentionally set them to be wrong. A lot of folks had to set their clocks back a few years around Y2k, for instance.

S

Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

Stephen_Sprunk3 · September 18, 2007, 7:52pm

Thus spake "Xin Liu" <smilerliu@gmail.com>

Ideally, yes, a protocol should not rely on clock synchronization
at all. However, to ensure freshness of messages, we don't have
many choices, and clock synchronization seems to be the least
painful one. So we asked about router clocks on the current
Internet. If normally router clocks are synchronized and we have
a mechanism to detect and fix out-of-sync clocks, ...

Your protocol should not attempt to "fix" clocks that aren't in sync unless it's specifically labeled as a time-distribution protocol. If people wanted that, they'd be using NTP. Do not surprise them with unexpected behavior.

... is it reasonable to assume clock synchronization in the rest
of our design?

In general, it is not. I can't think of any existing protocol that does, actually.

There's basically two common methods for determining "freshness": liveness-based and duration-based. BGP, for instance, uses the model where the most recent message regarding a particular route is assumed to be fresh until the peer is detected to be dead, in which case all messages from that peer become stale. RIP, on the other hand, uses the model where a message is fresh (unless updated) for a certain duration and it becomes stale when that duration expires.

Notice that neither requires the sender or receiver to agree on the time. Even in protocols like SIP, which include an explicit validity duration for some messages, that duration is specified as the number of seconds after transmission, not a fixed point in time. You don't need to agree on what time it is to agree when "180 seconds from now" is. The receiver takes the current local time, adds the duration specified, and that's the local expiration time.

HTTP muddles this a bit by allowing absolute time/date expiration; however, it requires the server to send what it thinks the current time/date is. The client should then calculate the difference and uses it as if it were a duration above. (i.e. if the server says it's now 1 Jan 1980 00:00:00 and an object expires on 31 Jan 1980 00:00:00, and my local time is now 18 Sep 2007 19:49:00, my client should actually use an expiration of 17 Oct 2007 19:49:00.) That's ugly.

S

Stephen Sprunk "God does not play dice." --Albert Einstein
CCIE #3723 "God is an inveterate gambler, and He throws the
K5SSS dice at every possible opportunity." --Stephen Hawking

bill3 · September 19, 2007, 8:39am