draft-ietf-tictoc-multi-path-synchronization-00.txt   draft-ietf-tictoc-multi-path-synchronization-01.txt 
Network Working Group A. Shpiner Network Working Group A. Shpiner
Internet Draft Technion - Israel Institute of Technology Internet Draft Technion - Israel Institute of Technology
Intended status: Experimental R. Tse Intended status: Experimental R. Tse
Expires: January 2015 C. Schelp Expires: April 2015 C. Schelp
PMC-Sierra PMC-Sierra
T. Mizrahi T. Mizrahi
Marvell Marvell
July 27, 2014 October 22, 2014
Multi-Path Time Synchronization Multi-Path Time Synchronization
draft-ietf-tictoc-multi-path-synchronization-00.txt draft-ietf-tictoc-multi-path-synchronization-01.txt
Abstract Abstract
Clock synchronization protocols are very widely used in IP-based Clock synchronization protocols are very widely used in IP-based
networks. The Network Time Protocol (NTP) has been commonly deployed networks. The Network Time Protocol (NTP) has been commonly deployed
for many years, and the last few years have seen an increasingly for many years, and the last few years have seen an increasingly
rapid deployment of the Precision Time Protocol (PTP). As time- rapid deployment of the Precision Time Protocol (PTP). As time-
sensitive applications evolve, clock accuracy requirements are sensitive applications evolve, clock accuracy requirements are
becoming increasingly stringent, requiring the time synchronization becoming increasingly stringent, requiring the time synchronization
protocols to provide high accuracy. Slave Diversity is a recently protocols to provide high accuracy. Slave Diversity is a recently
introduced approach, where the master and slave clocks (also known as introduced approach, where the master and slave clocks (also known as
server and client) are connected through multiple network paths, and server and client) are connected through multiple network paths, and
the slave combines the information received through all paths to the slave combines the information received through all paths to
obtain a higher clock accuracy compared to the conventional one-path obtain a higher clock accuracy compared to the conventional one-path
approach. This document describes a multi-path approach to PTP and approach. This document describes a multi-path approach to PTP and
NTP over IP networks, allowing the protocols to run concurrently over NTP over IP networks, allowing the protocols to run concurrently over
multiple communication paths between the master and slave clocks. The multiple communication paths between the master and slave clocks. The
multi-path approach can significantly contribute to clock accuracy, multi-path approach can significantly contribute to clock accuracy,
security and fault protection. The Multi-Path Precision Time Protocol security and fault tolerance. The Multi-Path Precision Time Protocol
(MPPTP) and Multi-Path Network Time Protocol (MPNTP) define an (MPPTP) and Multi-Path Network Time Protocol (MPNTP) define an
additional layer that extends the existing PTP and NTP without the additional layer that extends the existing PTP and NTP without the
need to modify these protocols. MPPTP and MPNTP also allow backward need to modify these protocols. MPPTP and MPNTP also allow backward
compatibility with nodes that do not support the multi-path compatibility with nodes that do not support the multi-path
extension. extension.
Status of this Memo Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
skipping to change at page 2, line 16 skipping to change at page 2, line 16
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt. http://www.ietf.org/ietf/1id-abstracts.txt.
The list of Internet-Draft Shadow Directories can be accessed at The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This Internet-Draft will expire on January 27, 2015. This Internet-Draft will expire on April 22, 2015.
Copyright Notice Copyright Notice
Copyright (c) 2014 IETF Trust and the persons identified as the Copyright (c) 2014 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 2, line 41 skipping to change at page 2, line 41
described in the Simplified BSD License. described in the Simplified BSD License.
Table of Contents Table of Contents
1. Introduction ................................................. 3 1. Introduction ................................................. 3
2. Conventions Used in this Document ............................ 5 2. Conventions Used in this Document ............................ 5
2.1. Abbreviations ........................................... 5 2.1. Abbreviations ........................................... 5
2.2. Terminology ............................................. 5 2.2. Terminology ............................................. 5
3. Multiple Paths in IP Networks ................................ 5 3. Multiple Paths in IP Networks ................................ 5
3.1. Load Balancing .......................................... 5 3.1. Load Balancing .......................................... 5
3.2. Using Multiple Paths Concurrently ....................... 5 3.2. Using Multiple Paths Concurrently ....................... 6
3.3. Two-Way Paths ........................................... 6 3.3. Two-Way Paths ........................................... 6
4. Solution Overview ............................................ 6 4. Solution Overview ............................................ 6
4.1. Path Configuration and Identification ................... 6 4.1. Path Configuration and Identification ................... 6
4.2. Combining ............................................... 7 4.2. Combining ............................................... 7
5. Multi-Path Time Synchronization Protocols over IP Networks ... 7 5. Multi-Path Time Synchronization Protocols over IP Networks ... 7
5.1. Single-Ended Multi-Path Synchronization ................. 8 5.1. Single-Ended Multi-Path Synchronization ................. 8
5.1.1. Single-Ended MPPTP Synchronization Message Exchange 8 5.1.1. Single-Ended MPPTP Synchronization Message Exchange 8
5.1.2. Single-Ended MPNTP Synchronization Message Exchange 9 5.1.2. Single-Ended MPNTP Synchronization Message Exchange 9
5.2. Dual-Ended Multi-Path Synchronization .................. 10 5.2. Dual-Ended Multi-Path Synchronization .................. 10
5.2.1. Dual-Ended MPPTP Synchronization Message Exchange . 10 5.2.1. Dual-Ended MPPTP Synchronization Message Exchange . 10
5.2.2. Dual-Ended MPNTP Synchronization Message Exchange . 11 5.2.2. Dual-Ended MPNTP Synchronization Message Exchange . 11
5.3. Using Traceroute for Path Discovery .................... 12 5.3. Using Traceroute for Path Discovery .................... 12
5.4. Using Unicast Discovery for MPPTP ...................... 12 5.4. Using Unicast Discovery for MPPTP ...................... 12
6. Combining Algorithm ......................................... 13 6. Combining Algorithm ......................................... 13
6.1. Averaging .............................................. 13 7. Security Considerations ..................................... 13
6.2. Switching / Dynamic Algorithm .......................... 13 8. IANA Considerations ......................................... 13
6.3. NTP-like Filtering-Clustering-Combining Algorithm ...... 13 9. Acknowledgments ............................................. 13
7. Security Considerations ..................................... 14 10. References ................................................. 13
8. IANA Considerations ......................................... 14 10.1. Normative References .................................. 13
9. Acknowledgments ............................................. 14 10.2. Informative References ................................ 14
10. References ................................................. 14
10.1. Normative References .................................. 14
10.2. Informative References ................................ 15
1. Introduction 1. Introduction
The two most common time synchronization protocols in IP networks are The two most common time synchronization protocols in IP networks are
the Network Time Protocol [NTP], and the Precision Time Protocol the Network Time Protocol [NTP], and the Precision Time Protocol
(PTP), defined in the IEEE 1588 standard [IEEE1588]. (PTP), defined in the IEEE 1588 standard [IEEE1588].
The accuracy of the time synchronization protocols directly depends The accuracy of the time synchronization protocols directly depends
on the stability and the symmetry of propagation delays on both on the stability and the symmetry of propagation delays on both
directions between the master and slave clocks. Depending on the directions between the master and slave clocks. Depending on the
nature of the underlying network, time synchronization protocol nature of the underlying network, time synchronization protocol
skipping to change at page 3, line 38 skipping to change at page 3, line 35
(e.g. [ASSYMETRY], [ASSYMETRY2]). As time sensitive applications (e.g. [ASSYMETRY], [ASSYMETRY2]). As time sensitive applications
evolve, accuracy requirements are becoming increasingly stringent. evolve, accuracy requirements are becoming increasingly stringent.
Using a single network path in a clock synchronization protocol Using a single network path in a clock synchronization protocol
closely ties the slave clock accuracy to the behavior of the specific closely ties the slave clock accuracy to the behavior of the specific
path, which may suffer from temporal congestion, faults or malicious path, which may suffer from temporal congestion, faults or malicious
attacks. Relying on multiple clock servers as in NTP solves these attacks. Relying on multiple clock servers as in NTP solves these
problems, but requires active maintenance of multiple accurate problems, but requires active maintenance of multiple accurate
sources in the network, which is not always possible. The usage of sources in the network, which is not always possible. The usage of
Transparent Clocks (TC) in PTP solves the congestion problem by Transparent Clocks (TC) in PTP solves the congestion problem by
eliminating the queueing time from the delay calculations, but eliminating the queueing time from the delay calculations, but does
requires the intermediate routers and switches to support the TC not address security or fault-tolerance aspects.
functionality, which is not always the case.
____ ____
______/ \_____ ______/ \_____
___/ \____ ___/ \____
____/ \ ____/ \
____ / path 1 / ___ ____ / path 1 / ___
/ \ / ________________________ \ / \ / \ / ________________________ \ / \
/Master\____\___/ \____\________/Slave\ /Master\____\___/ \____\________/Slave\
\Clock / / \________ _______________/ \ \Clock/ \Clock / / \________ _______________/ \ \Clock/
\____/ \ / \__ / \____/ \ / \__ /
skipping to change at page 4, line 42 skipping to change at page 4, line 42
layer and do not require any changes in the PTP or in the NTP layer and do not require any changes in the PTP or in the NTP
protocols. protocols.
MPPTP and MPNTP are defined over IP networks. As IP networks MPPTP and MPNTP are defined over IP networks. As IP networks
typically combine ECMP routing, this property is leveraged for the typically combine ECMP routing, this property is leveraged for the
multiple paths used in MPPTP and MPNTP. The key property of the multiple paths used in MPPTP and MPNTP. The key property of the
multi-path extension is that clocks in the network can use more than multi-path extension is that clocks in the network can use more than
one IP address. Each {master IP, slave IP} address pair defines a one IP address. Each {master IP, slave IP} address pair defines a
path. Depending on the network topology and configuration, the IP path. Depending on the network topology and configuration, the IP
combination pairs can form multiple diverse paths used by the multi- combination pairs can form multiple diverse paths used by the multi-
path synchronization protocols. path synchronization protocols. It has been shown [MULTI] that using
multiple IP addresses over the wide Internet indeed allows two end-
points to attain multiple diverse paths.
This document introduces two variants for each of the two multi-path This document introduces two variants for each of the two multi-path
protocols; a variant that requires both master and slave nodes to protocols; a variant that requires both master and slave nodes to
support the multi-path protocol, referred to as the dual-ended support the multi-path protocol, referred to as the dual-ended
variant, and a backward compatible variant that allows a multi-path variant, and a backward compatible variant that allows a multi-path
clock to connect to a conventional single-path clock, referred to as clock to connect to a conventional single-path clock, referred to as
the single-ended variant. the single-ended variant.
2. Conventions Used in this Document 2. Conventions Used in this Document
2.1. Abbreviations 2.1. Abbreviations
BMC Best Master Clock [IEEE1588]
ECMP Equal Cost Multiple Path ECMP Equal Cost Multiple Path
LAN Local Area Network LAN Local Area Network
MPNTP Multi-Path Network Time Protocol MPNTP Multi-Path Network Time Protocol
MPPTP Multi-Path Precision Time Protocol MPPTP Multi-Path Precision Time Protocol
NTP Network Time Protocol NTP Network Time Protocol [NTP]
PTP Precision Time Protocol PTP Precision Time Protocol [IEEE1588]
2.2. Terminology 2.2. Terminology
In the NTP terminology, a time synchronization protocol is run In the NTP terminology, a time synchronization protocol is run
between a client and a server, while PTP uses the terms master and between a client and a server, while PTP uses the terms master and
slave. Throughout this document, the sections that refer to both PTP slave. Throughout this document, the sections that refer to both PTP
and NTP generically use the terms master and slave. and NTP generically use the terms master and slave.
3. Multiple Paths in IP Networks 3. Multiple Paths in IP Networks
skipping to change at page 7, line 22 skipping to change at page 7, line 25
possible to create diverse paths for each of the IP address pairs possible to create diverse paths for each of the IP address pairs
between two clocks in the network. However, in public and provider between two clocks in the network. However, in public and provider
networks the load balancing behavior is hidden from the end users. In networks the load balancing behavior is hidden from the end users. In
this case the actual number of paths may be less than the number of this case the actual number of paths may be less than the number of
IP address pairs, since some of the address pairs may share common IP address pairs, since some of the address pairs may share common
paths. paths.
4.2. Combining 4.2. Combining
Various methods can be used for combining the time information Various methods can be used for combining the time information
received from the different paths. This document surveys several received from the different paths. The output of the combining
combining methods in Section 5.4. The output of the combining algorithm is the accurate time offset. Combining methods are further
algorithm is the accurate time offset. discussed in Section 6.
5. Multi-Path Time Synchronization Protocols over IP Networks 5. Multi-Path Time Synchronization Protocols over IP Networks
This section presents two variants of MPPTP and MPNTP; single-ended This section presents two variants of MPPTP and MPNTP; single-ended
multi-path time synchronization and dual-ended multi-path time multi-path time synchronization and dual-ended multi-path time
synchronization. In the first variant, the multi-path protocol is run synchronization. In the first variant, the multi-path protocol is run
only by the slave and the master is not aware of its usage. In the only by the slave and the master is not aware of its usage. In the
second variant, all clocks must support the multi-path protocol. second variant, all clocks must support the multi-path protocol.
The dual-ended protocol provides higher path diversity by using The dual-ended protocol provides higher path diversity by using
skipping to change at page 13, line 9 skipping to change at page 13, line 9
The unicast discovery option can be used in networks that do not The unicast discovery option can be used in networks that do not
support multicast or in networks in which the master clocks are known support multicast or in networks in which the master clocks are known
in advance. In particular, unicast discovery avoids multicasting in advance. In particular, unicast discovery avoids multicasting
Announce messages. Announce messages.
6. Combining Algorithm 6. Combining Algorithm
Previous sections discussed the methods of creating the multiple Previous sections discussed the methods of creating the multiple
paths and obtaining the time information required by the slave paths and obtaining the time information required by the slave
algorithm. This section discusses the algorithm used to combine this algorithm. Once the time information is received through each of the
information into a single accurate time estimate. Note that the paths, the slave should use a combining algorithm, which consolidates
choice of the combining algorithm is local to the slave, and does not the information from the different paths into a single clock.
affect the interoperability of the protocol. Various methods have been suggested for combining information from
Several combining methods are examined next. different paths or from different clocks, e.g., [NTP], [SLAVEDIV],
[HIGH-AVAI], [KALMAN]. The choice of the combining algorithm is local
6.1. Averaging to the slave, and does not affect the interoperability of the
protocol. Hence, this document does not define a specific method to
In the first method the slave performs an autonomous time computation be used by the slave.
for each of the master-slave paths, and obtains the combined time by
simply averaging the separate instances. This method can be further
enhanced by adding weights to each of the paths. For example, a
reasonable weighting choice is to use an inverse of the round-trip
delay between the peers. Another option is to use the inverse of the
path delay variance, which is approximately the maximum likelihood
estimator under certain assumptions [WEIGHT-MEAN].
6.2. Switching / Dynamic Algorithm
The switching and dynamic algorithms are presented in [SLAVEDIV]. The
switching algorithm periodically chooses a primary path, and performs
all time computations based on the protocol packets received through
the primary path. The primary path is defined as the path with the
minimal distance between the sampled delay and the average delay. The
dynamic algorithm dynamically chooses between the result of the
switching algorithm and the averaging.
6.3. NTP-like Filtering-Clustering-Combining Algorithm
NTP ([NTP], [NTP2]) provides an efficient algorithm of combining
offset samples from multiple peers. The same approach can be used in
MPPTP and MPNTP.
In the MPNTP, the selection and combining algorithms treat the offset
samples from multiple paths as NTP treats samples from distinct
peers. The rest of the selection and combining algorithms, as well as
clock control logic is the same as in conventional NTP. In MPPTP, a
similar approach to NTP can be adopted.
The combining algorithm [NTP3] contains three steps: filtering,
selection and clustering.
In the filtering step, the best of the last n (usually n=8) samples
of each peer is chosen. The choice criterion is the combination of a
round trip delay estimate of the sample and the distance from the
average offset of all n samples of a peer.
In the selection step the peers are divided into two groups: true-
chimers and false tickers.
The clustering step chooses a subset of the true-chimers, whose peer
jitter (the variance of peer offset samples) is smaller than the
total select jitter of all selected peer offsets (the variance of the
best offset of the selected peers).
The offset samples that passed through the three steps are combined
by a weighted average into a single offset estimate. Detailed
explanations are provided in [NTP2],[NTP3].
7. Security Considerations 7. Security Considerations
The security aspects of time synchronization protocols are discussed The security aspects of time synchronization protocols are discussed
in detail in [TICTOCSEC]. The methods describe in this document in detail in [TICTOCSEC]. The methods describe in this document
propose to run a time synchronization protocol through redundant propose to run a time synchronization protocol through redundant
paths, and thus allow to detect and mitigate man-in-the-middle paths, and thus allow to detect and mitigate man-in-the-middle
attacks, as described in [DELAY-ATT]. attacks, as described in [DELAY-ATT].
8. IANA Considerations 8. IANA Considerations
skipping to change at page 15, line 23 skipping to change at page 14, line 23
asymmetry in the internet", IEEE Globecom, 2005. asymmetry in the internet", IEEE Globecom, 2005.
[ASSYMETRY2] Abhinav Pathak, Himabindu Pucha, Ying Zhang, Y. [ASSYMETRY2] Abhinav Pathak, Himabindu Pucha, Ying Zhang, Y.
Charlie Hu, and Z. Morley Mao, "A measurement study of Charlie Hu, and Z. Morley Mao, "A measurement study of
internet delay asymmetry", PAM'08, 2008. internet delay asymmetry", PAM'08, 2008.
[DELAY-ATT] T. Mizrahi, "A Game Theoretic Analysis of Delay [DELAY-ATT] T. Mizrahi, "A Game Theoretic Analysis of Delay
Attacks against Time Synchronization Protocols", Attacks against Time Synchronization Protocols",
ISPCS, 2012. ISPCS, 2012.
[HIGH-AVAI] P. Ferrari, A. Flammini, S. Rinaldi, G. Prytz, "High
availability IEEE 1588 nodes over IEEE 802.1 aq
Shortest Path Bridging networks" ISPCS, 2013.
[KALMAN] G. Giorgi, C. Narduzzi, "Kalman filtering for multi-
path network synchronization" ISPCS, 2014.
[MULTI] A. Shpiner, Y. Revah, T. Mizrahi, "Multi-path Time
Protocols" ISPCS, 2013.
[NTP2] Mills, D.L., "Internet time synchronization: the [NTP2] Mills, D.L., "Internet time synchronization: the
Network Time Protocol", IEEE Trans. Communications Network Time Protocol", IEEE Trans. Communications
COM-39, 10 (October 1991), 1482-1493. COM-39, 10 (October 1991), 1482-1493.
[NTP3] Mills, D.L., "Improved algorithms for synchronizing [NTP3] Mills, D.L., "Improved algorithms for synchronizing
computer network clocks", IEEE/ACM Trans. Networks 3, computer network clocks", IEEE/ACM Trans. Networks 3,
3(June 1995), 245-254. 3(June 1995), 245-254.
[PARIS] Brice Augustin, Timur Friedman and Renata Teixeira, [PARIS] Brice Augustin, Timur Friedman and Renata Teixeira,
"Measuring Load-balanced Paths in the Internet", IMC, "Measuring Load-balanced Paths in the Internet", IMC,
skipping to change at page 16, line 5 skipping to change at page 15, line 18
[TICTOCSEC] T. Mizrahi, K. O'Donoghue, "Security Requirements of [TICTOCSEC] T. Mizrahi, K. O'Donoghue, "Security Requirements of
Time Protocols in Packet Switched Networks", IETF, Time Protocols in Packet Switched Networks", IETF,
draft-ietf-tictoc-security-requirements, work in draft-ietf-tictoc-security-requirements, work in
progress, 2013. progress, 2013.
[TRACEFLOW] J. Narasimhan, B. V. Venkataswami, R. Groves and P. [TRACEFLOW] J. Narasimhan, B. V. Venkataswami, R. Groves and P.
Hoose, "Traceflow", IETF, draft-janapath-intarea- Hoose, "Traceflow", IETF, draft-janapath-intarea-
traceflow, work in progress, 2012. traceflow, work in progress, 2012.
[WEIGHT-MEAN] http://en.wikipedia.org/wiki/Weighted_mean#Dealing_wi
th_variance
Authors' Addresses Authors' Addresses
Alex Shpiner Alex Shpiner
Department of Electrical Engineering Department of Electrical Engineering
Technion - Israel Institute of Technology Technion - Israel Institute of Technology
Haifa, 32000 Israel Haifa, 32000 Israel
Email: shalex@tx.technion.ac.il Email: shalex@tx.technion.ac.il
Richard Tse Richard Tse
 End of changes. 16 change blocks. 
85 lines changed or deleted 43 lines changed or added

This html diff was produced by rfcdiff 1.41. The latest version is available from http://tools.ietf.org/tools/rfcdiff/