Question on Loosely Synchronized Router Clocks
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. Thanks, Xin Liu
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.) -- R. Kevin Oberman, Network Engineer Energy Sciences Network (ESnet) Ernest O. Lawrence Berkeley National Laboratory (Berkeley Lab) E-mail: oberman@es.net Phone: +1 510 486-8634 Key fingerprint:059B 2DDF 031C 9BA3 14A4 EADA 927D EBB3 987B 3751
On Mon, 17 Sep 2007 14:28:45 PDT, Kevin Oberman said:
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.)
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.. ;)
i conversed offline with the OP. he was reading a sigcomm research paper and confusing it with the internet. randy
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 On 9/17/07, Randy Bush <randy@psg.com> wrote:
i conversed offline with the OP. he was reading a sigcomm research paper and confusing it with the internet.
randy
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 On 9/17/07 3:54 PM, "Xin Liu" <smilerliu@gmail.com> wrote:
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
On 9/17/07, Randy Bush <randy@psg.com> wrote:
i conversed offline with the OP. he was reading a sigcomm research paper and confusing it with the internet.
randy
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 On 9/17/07, Bora Akyol <bora.akyol@aprius.com> wrote:
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
You can check freshness of a message by means of sequence numbers, no? Bora On 9/18/07 8:55 AM, "Xin Liu" <smilerliu@gmail.com> wrote:
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
On 9/17/07, Bora Akyol <bora.akyol@aprius.com> wrote:
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
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 On 9/18/07, Bora Akyol <bora.akyol@aprius.com> wrote:
You can check freshness of a message by means of sequence numbers, no?
Bora
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 On 9/18/07 9:25 AM, "Xin Liu" <smilerliu@gmail.com> wrote:
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
On 9/18/07, Bora Akyol <bora.akyol@aprius.com> wrote:
You can check freshness of a message by means of sequence numbers, no?
Bora
On Tue, 18 Sep 2007 09:27:32 PDT, Bora Akyol said:
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.
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.
On Tue, 18 Sep 2007 13:51:55 -0400 Valdis.Kletnieks@vt.edu wrote:
On Tue, 18 Sep 2007 09:27:32 PDT, Bora Akyol said:
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.
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.
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
On Tue, Sep 18, 2007, Xin Liu wrote:
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?
Not without specifying it in the design. adrian
On 9/18/07, Xin Liu <smilerliu@gmail.com> wrote:
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.
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 -- William D. Herrin herrin@dirtside.com bill@herrin.us 3005 Crane Dr. Web: <http://bill.herrin.us/> Falls Church, VA 22042-3004
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
Stephen Sprunk wrote:
... 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.
Kerberos. -- Jeff McAdams "They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -- Benjamin Franklin
Kerberos does not assume clock synchronization. Kerberos requires reasonable clock synchronization. And, as near as I can tell, clock synchronization is not part of the Kerberos protocol. Kick me if I err in this. Cutler At 9/19/2007 08:14 AM -0400, Jeff McAdams wrote: Stephen Sprunk wrote:
... 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.
Kerberos. -- Jeff McAdams "They that can give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -- Benjamin Franklin - James R. Cutler james.cutler@consultant.com
On 9/20/07, James R. Cutler <james.cutler@consultant.com> wrote:
Kerberos does not assume clock synchronization. Kerberos requires reasonable clock synchronization. And, as near as I can tell, clock synchronization is not part of the Kerberos protocol.
Kick me if I err in this.
Cutler
http://en.wikipedia.org/wiki/Kerberos_%28protocol%29#Kerberos_drawbacks<http://en.wikipedia.org/wiki/Kerberos_%2528protocol%2529#Kerberos_drawbacks> "Kerberos requires the clocks of the involved hosts to be synchronized. The tickets have time availability period and, if the host clock is not synchronized with the clock of Kerberos server, the authentication will fail. The default configuration requires that clock times are no more than 10 minutes apart. In practice, NTP<http://en.wikipedia.org/wiki/Network_Time_Protocol>daemons are usually employed to keep the host clocks synchronized."
On Thu, 20 Sep 2007 14:41:16 -0500 "Brandon Galbraith" <brandon.galbraith@gmail.com> wrote:
On 9/20/07, James R. Cutler <james.cutler@consultant.com> wrote:
Kerberos does not assume clock synchronization. Kerberos requires reasonable clock synchronization. And, as near as I can tell, clock synchronization is not part of the Kerberos protocol.
Kick me if I err in this.
Cutler
"Kerberos requires the clocks of the involved hosts to be synchronized. The tickets have time availability period and, if the host clock is not synchronized with the clock of Kerberos server, the authentication will fail. The default configuration requires that clock times are no more than 10 minutes apart. In practice, NTP<http://en.wikipedia.org/wiki/Network_Time_Protocol>daemons are usually employed to keep the host clocks synchronized."
That's correct, though I believe some versions use an offset hack. The initial exchange with the Kerberos server is strongly authenticated. It's used to issue a ticket-granting ticket; replay of TGTs (and service tickets obtained via TGTs) partially relies on synchronized clocks. The offset hack has the Kerberos server -- a universally trusted party -- note and seal in the tickets -- the client's time offset from KDC reality. Any services that accept the tickets can use this value to correct for clock skew. --Steve Bellovin, http://www.cs.columbia.edu/~smb
Kerberos does not assume clock synchronization. Kerberos requires reasonable clock synchronization.
To be more precise, Kerberos requires those systems for which it is providing (authentication) services to agree, within a configured (usually) 5-10 minutes. There is no requirement that those systems have to agree with anything else outside of their realm. If a particular set of servers all agree that it is currently Jan 10th, 1980, at 0913, Kerberos can be fine with that. Of course, usually, NTP (or something like that) is used to keep all the servers "near" UTC, but keeping clocks at UTC is not a Kerberos requirement.
And, as near as I can tell, clock synchronization is not part of the Kerberos protocol.
It is not, but note that some localized distributions of Kerberos clients did, indeed, ship with various time synchronization tools before they were common on platforms such as Windows and Mac, so some users may have thought that installing Kerberos meant they got clock synchronization.
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.
"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
Thank you for all the replies.
Best Regards,
Xin Liu
On 9/17/07, Randy Bush <randy@psg.com> wrote:
i conversed offline with the OP. he was reading a sigcomm research paper and confusing it with the internet.
randy
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
top posting to keep you alert! there are folks who syncronize clocks so that logs make sense. and those that do, tend to pick a common TZ... there is nothing like syncronizing logs from routers in Nepal, India, China, and LA UTC can be your friend... wrt acces to clock source - i'd be happy to have the httpd server code pulled out and adding a GPS/802.11 timesource to the platform of joy. of course presuming that a router clock is ammenable to an external discipline source. Many PC's are not... --bill On Tue, Sep 18, 2007 at 02:40:16PM -0500, Stephen Sprunk wrote:
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
Valdis.Kletnieks@vt.edu wrote:
On Mon, 17 Sep 2007 14:28:45 PDT, Kevin Oberman said:
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.)
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.
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
Date: Mon, 17 Sep 2007 18:22:12 -0400 From: Deepak Jain <deepak@ai.net>
Valdis.Kletnieks@vt.edu wrote:
On Mon, 17 Sep 2007 14:28:45 PDT, Kevin Oberman said:
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.)
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.
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 ;)].
True atomic clocks are only of value for disciplining time, but atomic time references tend to be a bit more accurate than GPS or anything else of which I am aware. CDMA actually gets its time reference from GPS, gut it is pretty accurate. I believe the spec calls for <1 usec error, although the receiver still needs to allow for propagation delay to be REALLY accurate. I have a mesh of NTP servers spread across the US that keep time within 5 usec based on CDMA clocks, but the operators of the CDMA clocks (cell phone providers) are often rather slow in handling leap seconds. Took weeks before the 1 second offset disappeared from all of them. -- R. Kevin Oberman, Network Engineer Energy Sciences Network (ESnet) Ernest O. Lawrence Berkeley National Laboratory (Berkeley Lab) E-mail: oberman@es.net Phone: +1 510 486-8634 Key fingerprint:059B 2DDF 031C 9BA3 14A4 EADA 927D EBB3 987B 3751
participants (17)
-
Adrian Chadd -
bmanning＠vacation.karoshi.com -
Bora Akyol -
Brandon Galbraith -
Buhrmaster, Gary -
Deepak Jain -
James R. Cutler -
Janet Sullivan -
Jeff McAdams -
Kevin Oberman -
Randy Bush -
Robert E. Seastrom -
Stephen Sprunk -
Steven M. Bellovin -
Valdis.Kletnieks＠vt.edu -
William Herrin -
Xin Liu