NTP 한글자료
Author: 이윤수 [ http://juno.cs.pusan.ac.kr/TechnicalReport/ntp/ntp-tr.html ]
Date: 2002-08-07 오전 7:11:17 from '66.200.203.167' of '66.200.203.167'
NTP한글자료입니다.
http://juno.cs.pusan.ac.kr/TechnicalReport/ntp/ntp-tr.html
Network Time Protocol
Introduction
시각 동기가 필요한 이유
분산 시스템은 통신망을 통하여 메시지를 서로 주고 받는 처리 요소들의 집합이다. 분산 시스템에서 발생하는 사건 시각을 정확히 설정할 수 있다는 것은 제반 기능의 동기화, 순서화 및 일관성 유지에 큰 영향을 준다. 분산처리 기술 및 클라이언트-서버 컴퓨팅 기술은 정보 처리 분야의 생산성 향상과 컴퓨터 네트워크 등 컴퓨터 관련 산업의 많은 기술적인 진보를 가져왔고, 특히 마이크로 프로세스와 같은 하드웨어의 급속한 발전에 따라 더욱 고속의 컴퓨팅이 가능하게 되었다. 이에 따라 분산된 시스템 자원이 하나의 전체적인 시스템을 이루는 경우 각 자원간에는 더욱 정밀한 시각 동기 방법이 요구되게 되었다.
모든 컴퓨터는 현재 시간의 흐름을 유지하거나 CPU utilization이나 disk I/O와 같이 process에 의해 소요된 시간을 측정하는 등의 용도로 사용되어지는 timer mechanism을 필요로 한다. 분산 system에 있어서, application은 시스템의 여러 node에서 concurrent하게 수행되어지는 많은 process를 가지게 될 것이다. 올바른 결과를 얻기 위해서는 분산 application은 각각의 노드간에 clock 동기가 반드시 필요하게 된다. 이러한 동기화 되어진 clock을 통해서만 분산 시스템에서 빈번히 일어나는 하나의 노드에서 시작하고 다른 노드에서 끝이 나게 되는 분산 activities의 수행 기간 측정이 가능하게 된다.
시각 동기는 예측 불가능한 전송시간 및 신뢰성 없는 컴퓨터 통신망에서 더욱 어려움을 가진다. 이러한 어려움을 해소하기 위해 보다 정확한 시각 동기화 방법이 분산으로 인한 지연 및 신뢰성 없는 컴퓨터 통신망에서 분산처리 및 병렬 처리 구성 요소간의 동기 유지에 필요하다.
NTP(Network Time Protocol)
시각 동기를 위한 방법론은 여러 가지가 존재할 수 있지만 부가적인 하드웨어 장치의 장착 없이도 수 ms 정도의 동기화를 이룰 수 있는 동기화 기법이 NTP에 대해서 본 Technical Report(이하 TR)에서 자세하게 알아보도록 할 것이다
여러 시각 동기 protocol중에서 NTP를 선택한 이유는 신뢰성 없는 Internet 환경에서 사용하기 적합하고 다른 Daytime protocol이나 Time protocol에 비해 높은 동기화 효과를 가져오기 때문이다
본 TR은 Network Time Protocol (version 3) Specification, Implementation and Analysis(RFC 1305)의 내용을 중심으로 설명함을 밝혀둔다.
전체 구성
시각 동기 관련 요소
NTP 전체 개요 및 Data Format
NTP 개요 및 전체 동작
NTP configuration
NTP architecture
NTP protocol header and Timestamp format
NTP operation - 주요 알고리즘
Mode of operation
NTP process decomposition
Clock Filtering algorithm
Clock Selection algorithm
Clock Combining algorithm
Public service sever statistics
결론
Reference
시각 동기 관련 요소
NTP에 대한 설명에 앞서 이러한 시각 동기 protocol에서 사용되는 시각 동기 관련 요소들에 대해 살펴보겠다.
(동기 성능 측정 용어)
클럭의 안정도(stability) : 일정한 주파수를 유지하는 정도, 장기간의 동기 성능 평가의 주요소
클럭의 정확도(accuracy) : 일정한 주파수와 시각이 국가 표준과 비교되어지는 정도, 단기간의 동기 성능 평가에 중요한 요소.
클럭의 정밀도(precision) : 특수한 시각 유지 시스템에서 정확하게 측정 가능한 정도, 해상도의 동기 성능 평가 요소
(시각 오류 관련 용어)
Offset
Offset
Time offset
Frequency offset
상대적
일반적인 두 개의 clock의 정해진 순간의 시간 차이
일반적인 두 개의 clock간의 정해진 순간의 주파수 차이
절대적
절대 시각과의 정해진 순간의 시간 차
절대 시각과의 정해진 순간의 주파수 차이
Jitter : 연속적인 time offset의 측정 시 현 time offset과 이전 time offset의 차이, 주파수에서 단기간의 변이(10Hz 이상)
Wander : 계속적인 frequency offset 측정 시 현재의 frequency offset 값과 이전 값과의 차이, 주파수에서 장기간의 변이(10Hz보다 작은 경우)
Skew : 주파수차이에 대한 같은 의미의 다른 용어
Drift : 연속적인 skew값간의 차이, Wander와 같은 용어
Aging : 오프셋이 일정하지 않아서 시간에 따라 주파수가 점진적으로 변화는 결과
time offset의 1차 미분 = frequency offset
time offset의 2차 미분 = frequency offset의 1차 미분 = drift
(NTP protocol에 사용되는 시각 용어)
분산(dispersion) : 기준 클럭에 대한 지역 클럭의 최대 오류 표시
일주 지연(roundtrip delay) : 특정 시간에 기준 클럭 메시지가 도착하는데 걸리는 시간의 양을 표시
두 클럭의 차이(offset) : 기준 클럭과 비교하여 지역 클럭이 수정되어야 할 양을 표시
휨(skew) : 두 개의 클럭 간의 주파수의 차이(시간에 대한 1차 미분)
표류(drift) : 연속적인 휨 값의 차이를 의미(시간에 대한 2차 미분), NTP에서는 이 값을 0으로 간주함(즉 skew difference는 없는 것으로 가정)
여기에서 안정도, 정확도, 정밀도는 시각 동기화에 있어서 성능 평가 요소이다. 그리고 클럭 차이, 일주 지연 시간, 분산 등은 시각 동기의 고정밀도를 이루는 중요 요소로서 작용한다. 휨과 표류는 등은 시각 에러 요인으로 간주된다.
NTP 전체 개요 및 Data Format
( NTP 개요 및 전체 동작 )
미국의 Delaware University에서 주로 개발된 인터네트를 통한 computer clock의 시각 동기를 위한 시스템이다. NTP는 분산된 시간 서버와 클라이언트간의 시각을 동기화 하는데 사용된다. Phase-lock method와 비슷한 방법으로 서버들간에 또는 많은 subnet 동료들과 시각 소인 메시지를 교환하여 신뢰성 있는 오류 범위 하에서 클럭을 동기 시키는 방법이다. NTP version 1은 RFC-958에서 처음 기술되었고, 매우 빠르게 발전하여 RFC-1119에서 NTP version 2에 이르렀다. 이것은 비연결형(connectionless) 수송 메커니즘을 제공하는 인터네트 규약(IP)과 사용자 데이터 그램 규약(UDP)의 한 부분으로 만들어졌다. 본 TR의 주요소인 RFC-1305에서 NTP version 3에 대한 정의가 이루어 졌다. 현재는 RFC로는 아직까지 전체적인 내용이 정리되지는 않았지만 Local discipline algorithm의 개선과 IP ver 6를 지원하는 것을 골자로 하는 NTP version 4에 대한 정의가 이루어지고 있다.
NTP의 전체적인 동작을 설명하면 아래와 같다.
우선 clock filter 에서는 동료에서의 지연과 클럭 차이 (clock offset : θ)의 부수적인 time jitter를 감소시킨다. 그리고, 최소의 지연 시간을 가진 값을 선택하여 출력한다. 즉 동기화의 기본적인 요소 측정 방법이 여기에 적용되며, 보다 정확한 클럭의 동기를 위해서는 여기서 더욱 정확한 클럭 구성 요소 계산이 요구된다. 그리고, clock selection algorithm에서는 가장 정확하고, 믿을만한 시간을 선택한다. clock combining에서 interval intersection algorithm등을 사용하여 더욱 정확한 시각 소인을 구하고, 가중치를 주어 정밀도를 높인다. 이는 다시 NCO (Numeric-controlled oscillator) frequency를 제어하기 위해서 loop filter로 돌아가 클럭을 조절한다.
( NTP configuration)
NTP의 구성은 Primary Time Server와 Secondary Time Server, Client 그리고 상호 연결 전송 경로로 이루어진 연결된 망이다. 주 시간 서버는 직접 무선 클럭과 같은 최고 기준 원천에 연결된다. 보조 시간 서버는 다른 보조 시간 서버와 주 시간 서버 등을 이용해서 동기화 한다. 다른 서버들이 이 주 시간 서버를 공유한다. 정상적인 환경에서 주 서버와 보조 서버의 동기화 하부망은 루트에 주 서버를 가지고 말단 계층으로 갈수록 보조 서버의 정확도가 감소하는 구조적 Master-Slave 구성이라고 가정한다.
전화 회사에서 만든 협정에 따라 각 서버의 정확도는 그 계층을 지칭하는 수에 의해 정의되는데 주서버가 있는 가장 높은 계층이 1이고, 밑의 계층으로 내려갈수록 1씩 증가한다. 현재의 기술과 사용 가능한 무선클럭으로 단일 표본 10-3단위의 정확도는 주 서버의 망 접속부(interface)에서 이루어진다. 이 이상의 정확도를 이루기 위해서는 운영 시스템 및 지역 클럭 메커니즘의 설계 및 구현에 있어서 특별한 고려가 요구된다.
계층이 증가할 때, 이룰 수 있는 단일 표본 정확도는 망 경로와 지역 클럭 안정도에 따라 감소할 것이다. 각 특성 구성에서 오류를 평가하는데 필요한 지루한 계산을 피하기 위해서 동기화 하부망의 루트에서 측정된 지연과 분포에 비례하는 평균 측정 오류 축적을 가정한다.
일반적으로 동기화 하부망 토폴로지는 가장 높은 정확도를 갖도록 조직되어야 하고, 루프를 형성해서는 안된다. 계층이 증가함에 따라, 잠재적으로 신뢰할 수 없는 시간 서버를 포함하여 측정 오류가 증가한다는 사실을 고려해야 한다. NTP에서 사용된 선택 알고리즘은 주 서버에 루트를 둔 최소 가중 구간 트리를 계산하기 위해서 변경된 Bellman-Ford distributed 라우팅 알고리즘을 사용한다.
이러한 NTP에서의 실제적인 망 구성에 관해서 [Figure 1]로 살펴보면 아래와 같다.
[Figure 1]
신뢰성을 위해 3개 이상의 Department 서버를 가지고 multicast mode로 동기화를 이루는 최고 말단의 시각 동기 client의 모습을 나타낸다.
최하위 client에 동기화를 제공하는 Department 서버가 상위의 Campus server와 client/server mode로 동작하면서 동시에 각 Department 서버간의 symmetric mode로 동작하는 모습을 보여준다.
마지막으로 Campus 서버가 6개의 외부 Primary Time 서버와 client/server mode로 동기화하고 각 Campus 서버간에 symmetric mode로 동작하고 외부의 secondary server(buddy)를 이용하는 것을 표시한다.
( NTP architecture )
[Figure 2]
[Figure 2]는 NTP의 전체적인 구조를 나타낸 것이다. 일반적으로 NTP 구성에서 3개 이상의 서버를 가지도록 하는데 위의 그림에서 처럼 3개의 서버를 이용해서 시각 정보를 담고 있는 NTP message를 주고 받으면서 동기화를 위한 원천 정보를 얻게 된다. 이렇게 3개 이상의 서버를 가지도록 해서 신뢰할 수 없는 Internet 환경에서 여러 요인에 의해 한 서버와 시각 정보를 주고 받지 못하더라도 계속해서 일정한 동기를 이룰 수가 있도록 설계되었다.
이러한 서버들로부터 받은 시각 정보를 NTP에서는 각 서버마다 8개의 clock offset sample을 가지도록 했는데 각 서버로부터 이 8개중에서 가장 좋은 시각 정보를 가진 sample을 하나씩 선택하도록 하는 것이 clock filter algorithm의 주요한 작업이다.
Clock filter를 거친 각 서버로부터의 시각 정보들은 다시 selection algorithm을 거치게 된다. 이 selection algorithm은 Intersection과 Clustering이라는 크게 두 가지 동작으로 나누어 지게 된다. Selection 이라는 말 그대로 여러 서버들로부터 받은 각각의 시각 정보를 비교해서 잘못된 것을 가려내고(intersection) 남은 나머지 값들을 정렬해서 가장 괜찮은 시각 정보를 일정 수 남기는 과정을 하게 된다.
앞선 두 filtering과 selection을 거친 시각 정보들은 일정 가중치를 곱한 평균 offset을 구해서 최적의 time offset을 산출하게 된다.
이러한 값을 가지고 시각을 보정하게 되고 Loop filter와 Local Clock Oscillator(LCO)를 통해 jitter와 wander를 최소화하게 된다. 위의 전체적인 과정을 계속해서 반복하면서 동기화를 지속하게 된다.
앞서 약간의 언급이 있었지만 이러한 구조를 가진 NTP를 이용해서 시각 동기를 이루고자 하는 경우는 긴 주기와 다중 비교를 필요로 한다는 것을 인식해야 한다. 몇 개의 측정치만으로는 1초나 그쯤 만에 신뢰성 있는 지역 시간을 결정하는데 적당한 반면, 많은 시간 주기와 많은 측정치는 발진기 휨을 해결하고, 지역 시간이 수ms 단위로 유지할 수 있게 해준다. 그러므로 NTP에 있어서 정확도는 이것을 이루기 위해서 걸린 시간에 따라 결정된다.
( NTP protocol header and Timestamp Format )
데이터 형식
NTP에서 사용되는 모든 수학적 연산들은 2의 보수로 표현되고 고정 소수점 연산을 한다. 데이터는 정수 또는 고정 소수점 숫자로 지정되는데, 왼쪽에서 0으로 시작하여 큰 수로 끝나는 형식으로 비트 번호가 매겨진다. 소수점 위치나 정밀도를 지정하지 않고 내부적 사용을 위해, 외부에서 입력된 수를 바꾸기 위해 구현된 것이 많이 있다. 달지 지정하지 않으면 모든 수는 부호가 없는 수이고 0을 사용하여 비어있는 모든 비트를 채운다. 부호 있는 수를 다루기 위한 하드웨어 및 소프트웨어는 MSB(부호 비트)가 설정되어 있을 때 동작한다. 시각소인과 같이 외부에서 온, 부호 없는 고정소수점 숫자는 오른쪽으로 한 비트 이동시킨 후 내부적으로 사용한다.
NTP timestamp는 일종의 데이터이고 이 규약의 주요 결과이므로, 특별한 timestamp 형식이 제정되어 왔다. NTP timestamp는 64비트 부호 없는 고정 소수점 숫자로 1900년 1월 1일을 0h초로하여 초단위로 나타낸다. 첫 32비트는 정수부분 이고, 나머지 32비트는 소수 부분이다. 이 형식은 다중 정밀 연산을 하고 시간 규약 표시(초)로 바꾸는데 편리하지만 ICMP timestamp 메시지 표시(milliseconds)로 바꾸는 데는 복잡하다. 이 표시는 약 200 * 10-12초의 정확도를 갖는다. 이것은 대부분의 정밀한 응용의 요구 사항도 수용할 수 있다.
Timestamp는 메시지 도착과 같은 중요한 사건이 발생했을 때, 지역 클럭의 현재 값을 복사함으로써 결정된다. 가장 높은 정확도를 유지하기 위해서, 사건에 관련된 하드웨어나 소프트웨어 구동기에 가능한 한 근접해 있어야 한다. 특히 출발 timestamp를 연결 계층 재전송마다 재결정 되어야 한다. 호스트를 재 부팅시키거나 NTP를 처음 실행시킬 경우에는 특별한 timestamp를 이용할 수 있다. 이러한 경우에 64비트 필드는 0으로 설정되어야 한다. 이 값은 부적절하거나 정의되지 않았음을 의미한다. 1968년의 어느 시점에 MSB(정수부분의 비트 0)가 설정되었으면, 2036년에는 오버플로우 될 것이다. 2036년에 NTP가 사용된다면, 어떤 부가적인 방법으로 1900년에 대한 시간과 2036년(136년 차이의 다른 시간)에 대한 시간을 구분해야 한다. 이러한 구분을 필요로 하는 시각소인 데이터는 매우 중요하므로 항상 사용 가능해야 한다. 매 136년마다 64비트 필드가 0이므로 이것이 정의되지 않은 값으로 간주되어 200-picosecond의 차이가 있을 것이다.
아래는 NTP version 3와 4에서 사용되는 NTP timestamp header와 timestamp format을 정리한 그림이다. NTP 메시지 자료 영역은 UDP 바로 뒤에 위치한다. 아래에 이 영역에 대한 설명을 한다.
[Figure 3 ]
NTP protocol format description
Leap Indicator(LI) : 이것은 그 날의 마지막 일 분에 삽입 또는 삭제될 도약 시간을 알리는 두 비트 코드이다. 다음과 같이 비트 0과 비트 1을 사용한다.
00, 경고 없음
01, 지난 시간은 61초였음
10, 지난 시간은 59초였음.
11, 경고 조건(클럭이 동기화 안됐음)
Version Number(VN) : NTP 버전 번호를 표시하는 3비트 정수이다.
Mode : 모드를 표시하는 3비트 정수이다. 다음과 같은 값으로 정의된다.
0, 지정되지 않았음
1, 대칭 능동
2. 대칭 수동
3, 클라이언트
4, 서버
5, 방송
6, NTP 제어 메시지를 위해 예약됨
7, 사적인 사용을 위해 예약됨
Stratum : 이것은 지역 클럭의 계층을 표시하는 8비트 정수이다. 다음과 같은 값으로 정의된다.
0, 지정되지 않았음
1, 최고 기준(예: 무선 클럭)
2 ? 255, 2등 기준(NTP를 통하여)
이 값은 0에서 NTP.INFIN까지 범위에 한정된다.
Poll Interval : 연속적인 메시지들 사이에 있을 수 있는 구간의 최대값을 가지는 8비트 부호 있는 정수이다. 초 단위로 이 값에 가장 가까운 2의 급수로 표시된다. 이 영역은 NTP.MINPOLL에서 NTP.MAXPOLL까지의 값을 갖는다.
Precision : 지역 클럭의 정밀도를 나타내는 8비트 부호 있는 정수이다. 초 단위로 가장 가까운 시간에 대한 2의 급수로 나타낸다.
Root delay ; 최고 기준 원천에 대한 전체 일주 지연을 표시하는 32비트 부호 있는 고정 소수점 숫자이다. 비트 15와 비트 16사이에 분할 점이 있고, 초단위로 표시된다. 이 변수는 클럭 정밀도와 휨 값에 따라 양수 또는 음수일 수 있다.
Root dispersion : 최고 기준 원천에 대한 최대 오류를 표시하는 32비트 부호 있는 고정 소수점 숫자이다. 비트 15와 비트16사이에 분할 점이 있고 초단위로 표시된다. 이 변수의 값은 양수만 가능하다.
Reference Identifier : 특정 기준 클럭을 표시하는 32비트 코드이다. 계층 0또는 계층 1인 경우, 이것은 네 개의 8진수, 왼쪽 정렬된 0을 채운 아스키 문자열이다. NTP 명세에는 열거하지는 않았지만 다음과 같은 아스키 표시자가 있다.
계층
코드
의미
0
DCN
DCN 경로 설정 규약
0
NIST
NIST 공용 모뎀
0
TSP
TSP 시간 규약
0
DTS
디지털 시간 서비스
1
ATOM
원자 클럭
1
VLF
VLF 라디오
1
Callsign
일반 라디오
1
LORC
LORAN-C 무선 항법
1
GOES
GOES 환경위성
1
GPS
GPS UHF 위성 위치
[Table 1]
계층 2와 그 이상의 계층인 경우에 이것은 최고 기준 호스트의 인터네트 주소이다. 4개의 8진수로 표시된다.
Reference Timestamp : 지역 클럭이 마지막으로 설정 또는 정정될 때의 지역 시간이다. 64비트 timestamp 형식을 갖는다.
Originate Timestamp : 메시지가 서비스 호스트를 향해 클라이언트 호스트를 떠날 때의 지역 시간이다. 이는 64비트 timestamp 형식을 갖는다.
Transmit Timestamp : 응답이 클라이언트 호스트를 향해 서비스 호스트를 떠나는 지역 시간이다. 이는 64비트 timestamp 형식을 갖는다.
Authenticator(optional) : NTP authentication이 구현될 때 이러한 정보를 가지게 된다.
+ NTP 제어 메시지 형태와 설명은 RFC-1305의 부분에서 발췌해서 부록에 첨가한다.
NTP operation 및 주요 알고리즘
( Modes of Operation)
방송 모드를 제외하고, NTP 연계는 두 동료가 메시지를 교환하고, 둘 모두 또는 한 쪽이 규약 기계의 값 설정을 하고 유지 관리할 때, 생성된다. 이러한 관계가 성립되는 것을 NTP에서는 association이라고 한다. 연계는 호스트 모드 변수(peer.mode)에서 지정된 것과 같은 5개의 모드(대칭 능동, 대칭 수동, 클라이언트 서버 그리고 방송)에서 동작한다. 각 모드는 다음과 같이 정의된다.
대칭 능동(1) : 이 모드에서 동작하는 호스트는 도달 가능성 상태나 동료의 계층에 관계없이 주기적인 메시지를 보낸다. 이 모드에서의 동작에 의해서 호스트는 동기화하는 신호를 보내고 동료에 의해 동기화 된다.
대칭 수동(2) : 이 형식의 연계는 보통 대칭 능동 모드에서 동작하는 동료로부터의 메시지의 동작에 따라 생성되고 동료가 도달 가능하고 호스트와 같거나 작은 계층에서 동작할 때까지 유지된다. 그러나 연게는 적어도 응답을 보낼 때까지는 유지된다. 이 모드에서의 동작에 의해서, 호스트는 동기화하는 신호를 보내고 동료에 의해 동기화 된다..
클라이언트(3) : 이 모드에서 동작하는 호스트는 도달 가능성 상태나 동료의 계층에 관계없이 주기적인 메시지를 보낸다. 이 모드에서의 동작에 의해서 호스트(대개 근거리 지역 통신망 워크스테이션)는 동기화 되려는 신호를 보내지만 동료를 동기화 시키지는 않는다.
서버(4) : 이 형식의 연계는 대개 클라이언트 요청 메시지가 도착하면 생성되고 도착된 요청에 대답하기 위해서 존재한다. 대답한 후 이것은 해체된다. 이 모드에서의 동작에 의해서 호스트는 동기화 하려는 신호를 보내지만 동료에 의해 동기화 되지는 않는다.
방송(5) : 이 모드에서 동작하는 호스트는 도달 가능성 상태나 동료의 계층에 관계없이 주기적인 메시지를 보낸다. 이 모드에서의 동작에 의해서 호스트는 모든 동료를 동기화 하려는 신호를 보내지만, 이들 동료에 의해서 동기화 되지는 않는다.
종종 클라이언트 모드에서 동작하는 호스트는 대개 재 부팅한 후 도는 각 주기 구간에서 NTP 메시지를 서버 모드에서 동작하는 호스트에 보낸다. 서버는 주소와 포트를 교환하고 필요한 정보를 담아서 메시지를 클라이언트에게 돌려보낸다. 서버는 클라이언트 요청간의 상태 정보를 보관하지 않는다. 반면, 클라이언트는 지역 조건에 알맞은 NTP 메시지를 보내는 구간을 자유롭게 관리할 수 있다. 이 모드에서 본 표준에서 기술한 규약 기계는 특히 고속 근거리 지역 통신망에서 동작할 때, 정확도나 견고함을 잃지 않고 원격 프로시저 호출 방식으로 간단화 된다.
대칭 모드에서 클라이언트/서버 구별은 거의 없다. 대칭 수동 모드는 동기화 하부망의 루트 노드(가장 낮은 노드) 근처에서 비교적 많은 동료에 대해 동작하는 시간 서버가 사용을 목적으로 한다. 상태 변수와의 연계는 NTP메시지가 도착했을 때 생성되므로 이 모드에서 동료의 확인은 필요 없다. 더욱이 상태 기억 장소는 동료가 도달 불가능해질 때 상위 단계에서 동작하여 동기화 원천으로 부적당할 경우 다시 사용된다.
대칭 능동모드는 동기화 하부망의 끝 노드 근처에서 동작하는 time server에 의해 사용되어지도록 의도된 방식이다. 믿을 만한 시간 서버는 다음 하위 단계에서 두 개의 동료와 같은 단계에서 하나의 동료와 함께 유지되므로, 진행 중인 폴 비율은 연결성을 잃고 오류 메시지가 모든 폴에 대해 있을 때도 중요하지 않다.
보통 한 동료는 시작 파일에 의해 구성되어 능동 모드(대칭 능동, 클라이언트, 방송 모드)에서 동작한다. 반면 다른 동료는 선행하는 구성없이 수동 모드(대칭 수동 또는 서버 모드)에서 동작한다. 그러나 두 동료는 대칭 활성 모드에서 동작하도록 구성될 수 있다. 오류 조건은 두 동료 모두가 같은 모드에서 동작할 때 발생한다. 그러나 대칭 활성 모드일 때는 발생하지 않는다. 그러한 경우 각 동료는 다른 동료로부터의 메시지는 무시하고 선행한 연계는 도달성 실패로 인해 복원된다.
방송모드는 여러 워크스테이션을 가진 높은 정확도를 요구하지 않는 고속 근거리 지역 통신망에서 사용함을 목적으로 한다. 대개 한 개 또는 그 이상의 시간 서버가 근거리 지역 통신망에서 주기적인 방송을 워크스테이션으로 보낸다. 그리고 이 워크스테이션은 몇 밀리 초의 단위로 구성 잠복 시간을 결정한다.
( NTP process decomposition )
NTP를 구성하는 각 process에 대해 살펴보면 아래 그림과 같다.
[Figure 4]
전체적으로 동기를 제공하기 위한 remote server의 NTP process가 존재하고 local에서 현 시스템의 clock을 동기화 시키기 위한 local client의 NTP process가 존재해서 계속적으로 동기화 작업을 이루게 된다. 의미상으로 remote server와 local client의 NTP 구성은 같다.
NTP process는 이러한 외부 process와 interface를 하기 위한 Peer Process, 동기화 알고리즘을 지닌 System process, Local clock을 보정하는 Clock Adjust Process로 구성된다.
각각의 Peer Process는 독립적으로 System Process와 Remote Server에 의해 결정된 Poll 간격에서 동작한다.
System Process는 network phase jitter와 local clock oscillator frequency wander에 의해 결정된 Poll 간격으로 동작한다.
Clock Adjust Process는 local clock phase와 frequency를 훈련시키기 위해 1초의 간격으로 동작한다.
그 밖에 그림에 표시된 process외에도 name resolution과 authentication service를 제공하는 Process가 존재한다.
( NTP dataflow analysis )
[Figure 5]
위의 그림은 NTP에서 처리되는 data의 흐름을 나타낸 것이다.
각각의 server들은 server 변수인 동기화 망 구성상에서 최고 원천에 상대적인 offset Q , delay D 와 dispersion E 을 계산한다. 각 서버로부터 NTP message가 도착하는 경우 Peer Process는 timestamp와 clock filter algorithm에서 peer offset q , delay l , phase dispersion e r과 frequency dispersion e f (NTP version 4)을 변경한다. NTP version 3의 경우에는 frequency dispersion e f 은 고려하지 않는다. System Poll 간격으로 clock selection algorithm과 combining algorithm이 system 변수인 Q , D 와 E 을 변경한다.
( 필터링 및 선택 알고리즘 )
시간 분포의 정확도와 신뢰도에 영향을 주는 가장 중요한 요소는 다음과 같다.
통계적 오류를 줄이는 데 사용되는 복잡한 알고리즘
다양한 하부 망 요소
기준 원천 또는 전달 매체의 고장에 기인한 부정확한 시계 타종자
모든 시간 서버 또는 클라이언트가 여기에 명시된 알고리즘을 이용해서 구현될 필요가 없다. .
간단한 여러 워크스테이션은 정확도와 신뢰도 요건을 만족한다면 간결히 하기 위해 그들 중 하나 또는 둘 모두를 없애도 된다.
하지만 대학교 또는 연구 실험실과 같은 크기가 변하는 대상에 대한 동기화를 지원하는 NTP 서버는 이들 알고리즘을 구현하거나 등가의 기능을 제공하는 다른 것을 가지고 있어야 한다.
각 알고리즘의 효과적 동작 지원위해서 각 동료에 기록되는 최근 표본 분산을 측정하는 것이 유용
계산하기 쉽고, 적합한 1차 미분 사용
필터 분산 : e s
선택 분산 : e x
위의 분산 모두 동기화 거리에 따라 정렬된 임시 일람표에서 클럭 오프셋의 가중 합으로써 계산됨
e i = i번째 entry
e ij = j번째 entry에 관련된 i번째 entry의 표본 차이
e ij = | q i - q j|
e j = j번째 entry에 관련된 분산은 아래와 같은 가중 합으로 계산된다.
e j = ,여기서 w는 분산에서 동기화 거리의 영향을 제어하기 위해
선택된 가중 요소이다.
NTP 알고리즘에서 w는 1/2보다 작게 선택되어야 한다.
필터 분산에 대해서는 w = NTP.FILTER이고 선택 분산에 대해서는 w=NTP.SELECT이다.
NTP 알고리즘에서 사용된 분산 e s , e x 은 0번째 엔트리 e 0 에 관련되어 정의된다.
클럭 필터 프로시저 à 주어진 클럭에서 최상의 오프셋 표본을 선택
클럭 선택 프로시저 à 클럭 구조 집합 중 최상의 클럭을 선택하는데 사용
주요 알고리즘이 NTP에서의 차지하는 비중이 높음으로 주요 source code를 통해 살펴보도록 하겠다.
< 클럭 필터 프로시저 >
시기 : 새로운 데이터 sample에 의해 발생한 NTP 메시지나 다른 이벤트가 도착할 때 수행
클럭 필터 프로시저에서 계산되는 Offset과 Delay에 대한 그림은 아래와 같다.
[Figure 6]
인자 : ( q , d , e ) 형태
q : 표본 클럭 오프셋 측정
d : 연계된 일주 지연
e : 연계된 분산
필터링된 클럭 오프셋(peer.offset), 일주 지연(peer.delay) 및 분산(peer.dispersion)을 결정
이미 기록된 표본 분산을 갱신하고 현재 시간(peer.update)를 저장
클럭 필터 프로시저의 기본은 필터 이동 레지스터(peer.filter)이다.
NTP.SHIFT의 단계로 구성
구성 : [q i, d i, e I] (왼쪽에서 0으로 숫자가 붙여지는 색인을 가짐)
필터는 클리어 프로시저에 의해 모든 단계가 [0, 0, NTP.MAXDISPERSE]로 초기화 된다.
새로운 데이터 표본은 필터의 왼쪽 끝에서 이동하여 들어간다.
패킷 프로시저
두 폴 구간이 새로이 갱신할 때 : [ q , d , e ]
두 폴 구간이 새로운 갱신 없이 지나갈 때 : [0, 0, NTP.MAXDISPERSE] 을 전송 프로시저가 제공
의사 코드
begin clock-filter procedure( q , d , e )
필터 레지스터에 있는 모든 필터 값에 대해 분산 e I이 마지막 갱신 이후 축적된 휨 오류를 고려하도록 갱신되어야 한다.
이들 표본은 엔트리 형식 [distance, index]을 갖는 임시 일람표에 저장된다.
레지스터에 있는 표본은 표본 오버플로우를 무시하고 새로운 표본을 가장 왼쪽 단계에 저장하면서 오른쪽으로 한 단계 이동한다.
임시 일람표는 거리 증가에 따라 정렬
일람표에 표본이 남아있지 않으면 프로시저는 동료 변수를 갱신하지 않고 종료함
참고 : 일단 오프셋이 결정되면, 주파수 오프셋 또는 휨으로 오류는 시간에 따라 축적된다. 이것은 휨 확산 j g 라고 불린다. 여기서 j 은 휨비율 상수(NTP 명세에서 NTP.MAXSKEW/NTP.MAXAGE)를 나타내고 g 는 확산이 마지막 갱신된 후의 구간을 나타낸다.
for(i from NTP.SIZE -1 to 1) begin /* update dispersion */
[q i, d i, e i] <- [q i-1, d i-1, e i-1] /* 오른쪽 단계 이동 */
e i = e i + j g ; /* 휨 확산 추가 */
add [l ≡ e + |d i|/2, 0] to temporary list;
endfor
[q 0, d 0, e 0] <- [q , d , e ]; /* 새로운 표본 저장 */
add [l ≡e + |d |/2, 0] to temporary list;
peer.update <- sys.clock; /* 기본 시간을 0으로 설정 */
sort temporary list by increasing [ distance || index];
여기서 [distance || index] 는 거리와 색인 필드를 연결하는 것을 나타내고, 거리는 상위 필드이다. 필터 분산 e s 는 계산되고 동료 분산에 포함된다. 이를 위하여 임시 일람표가 이미 정렬되어야 한다.
e s <- 0;
for(i from NTP.SHIFT -1 to 0) begin /* 필터 분산을 계산 */
if(peer.dispersionindex[i]≥ NTP.MAXDISPERESE OR |q i - q 0| > NTP.MAXDISPERSE)
e <- (e d + NTP.MAXDISPERSE)× NTP.FILTER;
else
e <- (e d + |q i - q 0|)×NTP.FILTER;
동료 오프셋 < q 0 >, 지연 < d 0 > 및 분산 < e i >은 최소 거리 표본에 관련된 값으로써 선택된다. 즉 임시 일람표의 첫 엔트리에 관련된 표본이다. 여기서는 0번째 첨자를 갖는다.
peer.offset <- q 0; /* 동료 변수 갱신 */
peer.delay <- d 0;
peer.dispersion <- min(e 0+e d , NTP.MAXDISPERSE);
end clock-filter procedure
peer.offset과 peer.delay 변수는 동료 클럭에 관련된 지역 클럭의 클럭 오프셋과 일주 지연을 나타낸다. 이들 모두는 정확도를 나타내는 양이고 긴 시간동안 평균을 내어 바이어스 축적없이 정확도와 안정도를 증진한다.
peer.dispersion 변수는 측정 오류, 휨 오류 축적 및 표본 변이에서 기인하는 최대 오류를 나타낸다.
세 변수 모두 클럭 선택 및 동기화를 위해 사용되고 표시의 정확도와 안정도를 최대로 한다.
< 클럭 선택 프로시저 >
클럭 선택 프로시저는 동료 변수 Q , D , E , g 를 사용하고 이들 변수 값이 변경되거나 도달 가능성 상태가 변화할 때 호출된다.
구성
교차 알고리즘
동기화 원천으로 될 수 있는 후보 일람표를 작성
각각에 대한 신뢰구간 계산
마줄로와 오위키에서 채용한 기술을 사용해서 부정확한 시계 타종자 제거
클러스터링 알고리즘
남아있는 후보를 계층과 동기화 거리에 따라 정렬
반복적으로 가장 정확하고, 정밀하고 안정된 후보가 남을 때까지 선택 분산을 근거로 바깥 것을 제거
시스템 변수 sys.peer는 하나가 선택되면 가장 좋은 후보에 대한 포인터를 가지고 없으면 널을 가진다.
- 교차 알고리즘 -
begin clock-selection procedure
각 동료는 차례로 루프 또는 잡음 데이터 사용을 피하도록 설계되어 있는지를 검사하는 테스트를 지나 일람표의 끝에 추가
이 테스트를 통과하는 동료가 없으면 프로시저는 동기화 원천을 찾지 않고 종료
각 m개의 선택된 동료에 [endpoint, type] 형태를 가진 세개의 엔트리가 추가된다.
[Q -L (동기화 거리), -1], [Q , 0], [Q +L , 1]
끝 점으로 가면서 증가하도록 정렬된 일람표에 3m 엔트리가 있을 것이다.
m <- 0;
for (each peer) /* 모든 동료를 호출 */
if(peer.reach ≠ 0 and peer.dispersion < NTP.MAXDISPERSE and (peer.stratum > 1 and peer.refid = peer.hostaddr) begin
L andistance(peer); /* make list entry */
add [Q -L , -1] to endpoint list;
add [Q , 0] to endpoint list;
add [Q +L , 1] to endpoint list;
m <- m+1;
endif
if(m=0) begin
sys.peer <- NULL;
sys.stratum <- 0(undefined);
exit;
endif
sort endpoint list by increasing endpoint||type;
다음 알고리즘은 DTS에서 채용된 것과 유사하지만 mid-point를 두어서 이전의 방법에서 잃을 수 있는 시각 정보들까지 포함하도록 개선되었다.
가장 큰 하나의 정확한 시계 타종자를 포함하는 교점을 생성
f값을 초기화, i와 C를 0으로 만들면서 시작
정렬된 리스트의 끝점에서 시작
각 엔트리 [endpoint, type]에 대해, 형식의 값은 교점의 수를 담고 있는 계수 i에서 찾는다.
형식이 0이면 이것은 부정확한 시계 타종자이므로 c값을 증가시킨다.
어떤 엔트리에 대해서 i ≥m-f이면 그 엔트리의 끝점은 낮은 교점이 된다.
그렇지 않은 경우는 f는 1만큼 증가한다.
이런 방식이 계속해서 반복된다.
Ff 및 c를 다시 0으로 만들지 않으면 형식 값이 계수기에 더해지는 것을 제외하면, 유사한 프로시저가 상위 점에서 사용될 수 있다.
양 끝점이 c≤ f로 결정되면, 프로시저는 계속해서 m-f인 정확한 시계 타종자를 찾는다.
그렇지 않으면 f는 1만큼 증가하고 전체 프로시저를 반복한다.
위에서 설명한 intersection algorithm을 그림으로 표사하면 아래와 같다.
[Figure 7]
- 클러스터링 알고리즘 -
아래의 [Figure 8]은 Clustering algorithm을 설명한 것이다.
[Figure 8]
원래 DTS 알고리즘에서 클럭 선택 프로시저는 계산된 교점 [low, high]에서 중간에서 정확한 시계 타종자 시간으로 생각되는 점에서 종료한다. 그러나 이것은 상당한 장확도 및 안정도를 감소시킬 수 있다. 그러므로 NTP 에서는 앞선 단계에서 제외되지 않은 후보를 더 처리한다. 후보 리스트는 [distance, index] 형태의 엔트리를 가지도록 재구성된다. 여기서 distance는 기준화시킨 동료 계층 및 동기화 거리에서 계산된다. 기준화 요소는 계층 및 거리의 조합에 가중치를 두는 방식을 제공한다. 대개 하나 또는 그 이상의 살아남은 것의 거리가 예외적으로 긴 거리를 가지지 않았으면 계층이 주가 된다. 리스트는 증가하는 거리로 정렬된다.
다음 단계는 다른 후보에 비해서 큰 분산을 나타내는 바깥 것을 제거해서 특히 많은 시간 서버를 갖는 고속 LAN에서 방황하는 것을 최소화 하기위해 설계되었다. 폴 구간은 sys.poll에 고정되어 각 새로운 동료를 선택하고 동기화하고 동료가 더 이상 선택되지 않을 때 천천히 증가하므로, 방황은 필요없는 망 오버헤드의 원인이 된다. 경험적으로 보면 이 점에서 살아남은 후보의 수가 꽤 클 수 있고 안정도와 정확도 증진 없이 프로세서가 반복될 수 있다. 그러므로 후보 리스트는 NTP.MAXCLOCK 엔트리에서 잘려진다.
Intersection algorithm에서 살아남은 후보의 분산이 시스템에서 정의한 최소 분산보다 크거나 살아남은 수가 NTP.MINCLOCK보다 크면 해당 후보는 리스트에서 제거되고 이러한 과정을 반복한다. 현재 동기화 원천이 살아남은 것 중 하나이고 하위 계층에 살아남은 것이 없으면 프로시저는 더 이상 아무것도 하지 않고 종료한다. 그렇지않으면 동기화 원천은 후보 리스트 중 첫번째 살아남은 것이 된다.
알고리즘은 후보 리스트의 머리 부분 근처의 동료를 위해 설계되었다. 이들 동료는 가장 낮은 계층과 거리에 있고 가장 정확하고 안정된 시간을 제공하는 것으로 여겨진다. 적당한 가중 요소 v(NTP.SELECT)를 선택하여, 나머지 엔트리에 현저히 틀린 바깥 것이 없으면, 엔트리는 리스트의 꼬리에서 잘린다. 종료 조건은 통계적으로 결정될 수 없을 때, 낮은 계층과 낮은 거리 동료에 대한 바이어스를 유지하면서 필요 없는 동기화 원천간의 스위칭을 피하기 위해 설계되었다.
( Clock Combining algorithm )
NTP 클럭 선택 프로시저의 결과는 정확한 시계 타종자 또는 정확한 클럭을 대표하는 남은 것의 집합(최소 1개 이상)이다. 클럭 연결이 구현될 때 후보로 선택된 이들 동료 중 하나가 동기화 원천이 되고 이들 계산된 오프셋이 최후 클럭 정정이 된다.
시스템 변수는 이 단계에서 클럭 갱신 프로시저에 의해서 변경된다. 클럭 연결을 구현할 때, 이들 행동은 바뀌지 않고 최후 클럭 정정만이 클럭 연결 프로시저에 의해 계산된다.
클럭 연결 프로시저는 클럭 선택 프로시저에서 호출된다. 모든 남은 동료의 변수로부터 마지막 정정 클럭 오프셋을 구성한다. 이미 기술된 알고리즘에 의해 요구되는 예측된 오류는 거리 프로시저에 의해 계산된 동기화 거리에 기반을 둔다. 동기화 거리의 역수는 최후 클럭 정정에 대한 각 클럭 오프셋 기여 정도이다.
아래는 의사 코드로 프로시저를 기술한 것이다.
Begin clock-combining procedure
temp1 <- 0;
temp2 <- 0;
for each per remaining on the candidate list /* 모든 남은 것을 조사 */
l <- distance(peer);
temp <- 1/ (peer.stratum * NTP.MAXDISPERSE + L );
temp1 <- temp1+temp; /* 가중치와 오프셋 갱신 */
temp2 <- temp2 + temp * peer.offset;
Q <- temp2 / temp1; /* 최후 정정을 계산 */
end clock-combining procedure
( Alternate Modes for NTP )
아래는 NTP version 4 에서 이전 것에 추가된 것으로 여러 항목 중 동작 모드에서 추가된 내용과 그에 따른 새로운 authentication 방식이 더해 진 것을 정리한 것이다.
Alternate modes for NTP
인터넷 상의 호스트들의 대략적인 동기화를 위해서 적합
PC’s, workstations on LANs
Extended LANs
Much less traffic than ordinary modes
In the common bidirectional modes
Four timestamps
Calculates
The clock offset of its partner
The roundtrip delay between the peers
In the broadcast modes
Only two timestamps
server와 clients간의 propagation delay를 측정 할 수 없다.
동기화 거리가 연속된 samples간이나 여러 개의 peer간의 완화에 사용할 수 없다.
U.S. multicast clients can synchronize to European multicast servers within the order of 100ms
A significant fraction of 100,000 servers and clients could use multicast mode without significant reduction in accuracy
Multicast mode
Recognize suitably certified and authenticated servers
Public-key cryptosystmes, message digests, key-distribution protocols
NTP multicast group address
224.0.1.1
in the U.S. and the U.K.
Reasons for Multicasting Time
NTP for providing broadcast service
Use in LANs
Not require the high degree of synchronization available
Synchronization to the millisecond level
Limit the scope of a broadcast
Broadcast mode의 경우 여러 개의 subnets이나 networks을 통해 message를 주고 받는 것이 불가능함
In multicast mode
WAN에서 여러 개의 수신지로 message를 분산하는 것이 가능
broadcast의 동기화 알고리즘을 이용해서 client들은 자신의 local time을 server와 동기화 시킴
some degradation in accuracy
enable efficient distribution of the messages over a network
these messages are delivered only to hosts(특정 multicast 주소를 가진 host)
the number of messages sent out on any network is vastly reduced
the multicast mode of operation
the foundation for peer-discovery
a plug-and-play type of a system
NTP protocol Refinements
Broadcast 방식에서는 peer-to-peer 방식에서 사용한 delay나 offset의 측정이 불가능하므로 default value를 delay 값으로 사용한다.
결과가 좋지 않음
바람직한 결과를 위한 dynamically selection이 불가능함
provide the most accurate time using multicast mode
Temporary bidirectional mode
estimate the message transmission delay
이러한 측정은 session의 시작 시에 이루어짐
측정 동안은 일시적으로 bidirectional mode로 동작됨
문제점
multicast spanning tree path와 unicast paths 간에는 상당한 차이가 있음
A hybrid mode of operation
Client : having overheard a multicast NTP message
Initiate a client/server association
unicast와 multicast mode를 이용해서 결정된 time offset 간의 대칭적 보정 값을 결정하기 위함
보정값은 unicast와 multicast간의 geometry path의 차이점에서 발생된다.
이러한 보정 값이 신뢰할 수 있도록 결정되면 client/server mode에서 broadcast client mode로 전환해서 일반적인 동기화 작업을 하게 된다.
장점
reduce the load on the network and the primary servers
improve the accuracy
Protocol State Machine
NTP broadcast and multicast messages are identical
Except in the destination IP address
No change in the NTP protocol state machine for either broadcast or multicast messages
The propagation delay
Local peers in the same LAN
A constant in the low milliseconds without significant loss in accuracy
Remote peers in the different subnet
Determine the propagation delay separately for each remote peer
Broadcast <address> <poll interval> < time-to-live>
Address
local broadcast address
multicast group address
Time-to-live
Provide a crude mechanism for controlling the scope of delivery of the multicast messages
Fixed at 1 for broadcast
Broadcastclient <broadcast address>
Multicastclient <multicast address>
NTP daemon과 protocol의 동작 절차
주의점
Broadcast server의 broadcast mode와 multicast mode를 구분 해야 함
Broadcast client -> NTP peer
Operation in broadcast client mode -> a state in the protocol machine
동작 절차
configuration file이나 NTP utility인 xntpdc에 따라 client는 local broadcast address를 listen하거나 특정 multicast group에 join한다.
처음으로 broadcast나 multicast message를 받게 되면 broadcast client는 association의 source address로 broadcast server의 IP address를 가지고 일반적인 방법으로 client association을 mobilize한다.
Client-server mode로 동작할 경우는 broadcast client에서 broadcast server에게 NTP client message를 보내고 이에 대한 응답을 받게 된다. 이러한 과정을 통해 local clock을 동기화 시키기 위한 data로 offset과 delay, dispersion을 계산한다. Client mode에서 host poll interval은 broadcast message에 포함되어 있는 8개로 나뉘어진 peer poll interval 값을 사용해서 초기 training process를 빠르게 한다. 8개의 client message 후에 broadcast server가 응답하지 않으면 association이 client mode에서 broadcast client mode로 전환되어서 이 mode에서 계속 동작한다. 이 경우에는 upstream은 존재하지 않으며 NTP client message에도 응답하지 않는다.
위의 3의 과정과 동시에 broadcast client에서 server의 NTP broadcast messages를 모으고 multicast spanning tree를 통한 server와 client간의 propagation delay 측정치를 갱신한다. unicast와 multicast간의 path에는 차이가 있음으로 server에서나 다른 수단을 통해서 local clock이 정해지기 전까지 이러한 추정치는 정확하지 않다.
일반적으로 8개의 client/server message를 주고 받은 후 local clock은 set 되어진다. Local clock이 set되어지면 각각의 association은 client mode에서 broadcast mode로 전환되어지고 단지 server로부터의 message를 수신만하게 된다. 여기까지 아직 server와 client간의 propagation delay는 정확하게 정해지지 않았다는 것을 주목해야 한다.
Local clock이 set 되어진 후 최초의 broadcast message의 수신했을 때 각각의 broadcast client association은 마지막 propagation delay 추정치를 산출하고 이러한 결정을 동일하게 진행한다.
향후 client에서 propagation delay를 refine하기 위해서 client message를 보내는 것을 지원해야 한다.
이전의 filtering, selection, combining algorithm이 broadcast client에도 계속적으로 사용된다.
Multicast의 동작 실험 결과 짧은 roundtirp time을 지닌 server와의 동기화가 더 잘 이루어졌다.
unicast와 multicast의 차이점으로 인한 높은 dispersion 값을 사용하고 있다.
현재 낮은 dispersion 값을 허용하는 적당한 roundtrip time을 결정하는 연구가 진행중이다.
Hierarchical Subnets
Secondary servers located relatively close to the workstations to synchronize
Minimize the load on the networks
Maximize the accuracy and stability of the delivered service
The scaling issues
The spanning tree rooted at each primary server to completely cover all or even most of Internet
이를 해결하기 위한robust algorithm이 요구됨
해결 방법
Routing table을 고치는 방법
NTP messages of lower strata are not forward
Disable forwarding of NTP messages altogether
Inbound NTP multicast messages will land on the router NTP daemon
위의 방법의 문제점
lose backup path
become vulnerable to a loss of diversity
The problem of forwarding NTP multicast messages
Resolved by careful choice of the receivers
Tap into the resources of the sd(Session Director) service
Hierarchical subnets of high stratum servers and their clients
Enforce subnets
The multicast group address space is subdivided based on hierarchy
특정 subnet multicast server의 messages가 다른 낮은 stratum server의 subnet에 침입할 수 없도록 하는 규칙 강화
이러한 규칙은 낮은 stratum의 server가 다른 broadcast를 listen 하는데 유용하다.
Monitor other server’s state of health
A backup for the ordinary client/server backup servers
A server to automatically switch from client/server
The most accurate and stable associations
Multicast for the rest
Switching each association back and forth as a function of estimated error(dispersion)
Multicast Group Address Assignment and Group Address Reuse
A generous number of broadcasters
A large client population may develop
Put strain on the backbone
Burden on the multicast routers
Serious scaling consequences
Each distinct spanning tree to be assigned a unique multicast group address
The size of spanning tree -> MBone에서 사용되어지는 일반적인 관리 절차에 의해 결정됨
Address 할당이 현재의 문제
이미 많은 방법들이 제시됨
domain 계층에 맞추어 addressing 계층을 연결하는 것
예로 모든 server가 하나의 주소를 사용해서 정해진 security와 service model에 따라 group address가 DNS domain에 할당될 수 있도록 하는 것이다.
어떤 특정 임계치 값을 두어서 이러한 주소는 재-사용 가능하도록 정함
각각의 provider를 위한 특별한 server address는 host name을 이용해 DNS를 통해 얻어질 수 있다.
Ntp-1.sura.net -> NTP stratum 1 service in SURAnet
이러한 방법은 구현하기는 어렵지 않지만 관리하기가 힘들고 주소 사용에 있어서 낭비가 있다.
Session 초기화에 사용하는 sd를 DNS대신 이용하는 방법이 있지만 전세계적으로 사용할 수 없고, 모든 client가 sd가 동작하는 Internet상에 있다고 볼 수 없는 문제가 있다.
Authentication
The Digital Time Synchronization Service(DTSS)
Run in an authenticated environment
The protocol itself does not include provisions for authentication
NTP
Include specific provisions for an authentication scheme
Data Encryption Standard(DES)
RSA Message Digest(MD5)
A temporary expedient
The primary purpose of authentication
client가 선택한 server가 신뢰할 수 있는 지를 검사할 수 있도록 하는 것
the secret
DES나 MD5 algorithm을 이용해서 message digest의 형태로 구현되어 전송되는 NTP message에 포함된다.
이러한 secret는 전송측과 수신측에서 공통의 암호화 키의 공유가 유지되는 동안 유효하다.
현재의 authentication scheme은 wide-area multicast에 적합하지 않다.
The purpose of this discussion
Thinking, Discussion, Resolution on engineering changes
Protocol
Infrastructure
The result of these changes
Reduce the degree of black art necessary to manage the informal NTP subnet
Eliminate the need for clients to know anything about the NTP subnet
Authentication in Client-Server Mode
A client
Send message
Time of origin + message digest
Message digest
A particular initialization vector + key
client와 server 모두에게 알려진 값
the server
return message
the time of origin + message digest
client와 동일
the client
recompute the message digest
수신한 data가 신뢰할 수 있는가?
마지막 message가 보내졌을 때 저장된 시간과 현재 수신된 message에 포함된 origin time을 비교
이러한 모델의 특징
only one key is required
the common case of several hundred clients per server
equally trustable
a client can synchronize any member of that subnet
each other의 경우나 낮은 stratum을 지닌 신뢰할 수 있는 다른 server와 synchronize 하는 경우에는 잘 동작
point-to-point modes(unicast)
Authentication in Broadcast Mode
최상의 accuracy를 얻기 위해서는 여러 개의 server를 이용해서 roundtrip delay와 clock offset을 각각 측정해야 한다.
NTP spec에서는 broadcast mode에서도 여러 개의 server로부터 주기적으로 message를 수신하는 것을 지원하고 있다.
Local-net broadcasting
Only to the same subnet
The roundtirp times are relatively low
약간의 jitter 존재
이러한 경우는 roundtrip delay와 추가의 delay를 고정되었거나 외부에서 결정해서 사용한다.
일반적인 client/server mode에서의 client처럼 여러 개의 server 각각에 대해 쌍으로 authenticity를 검사하는 것이 broadcast mode에서는 불가능하다.
어떤 broadcaster를 선택해서 listen하는 것
각각에 다른 key를 할당하는 해서 선택된 server나 subnet을 이러한 key로 신뢰하는 것
broadcast의 복잡한 특성 때문에 broadcasting을 포함한 모든 경우의 authentication의 사용에는 세심한 주의를 필요로 한다.
The use of a public-key cryptosystem
Serve a same purpose
Far less computaion load
현재의 NTP authentication scheme
broadcast client의 key를 제대로 보관하지 않으면 속임수에 취약하게 된다.
특별한 key를 사용한 특정 server를 같은 key를 이용해서 구별하는 신뢰할 수 있는 방법이 없다.
해결 방법
server host address를 message-digest algorithm을 위한 initialization vector로 사용하는 것
server host address의 경우는 내부 kernel의 수정을 거쳐야 하므로 속임수를 쓰이기 어렵다.
이전의 버전과의 호환을 위해서 그 경우 initialization vector를 0으로 해서 사용한다.
Public service sever statistics
아래의 통계치는 지난 98년 5월 3째주간에 행해졌던 Public access를 지원하는 Internet상의 NTP Primary server(stratum 1)와 동기화를 이루는 client에서의 수집된 자료이다. Client는 본 연구실에 있는 486 PC로 운영체제는 Linux (RedHat 5.0)로 동작하며 NTP version 4 daemon으로 동기화를 실험하였다.
[Table 2]는 동기화 server로 사용되는 각 서버에 대한 설명으로 Server name은 해당 서버의 주소를 의미하고, Reference Clock은 외부 시각 원천으로 사용한 종류를 표시하고, Service Area는 권장하는 동기화 지역을 나타낸 것이다. 이들 서버는 모두 외부 시각원을 가지는 Stratum 1으로 동작하는 것들이다.
Server Name
Reference Clock
Service Area
Server 1
cannon.inria.fr
TDF clock
RENATER, France
Server 2
Clock.nc.fukuoka-u.ac.jp
GPS clock
Japan/Pacific Area
Server 3
Navobs1.usnogps.navy.mil
USNO Alternate Master Clock H-maser
USA Pacific and Mountain timezone
Server 4
Navobs1.usnogps.navy.mil
USNO Alternate Master Clock H-maser
USA Pacific and Mountain timezone
[Table 2]
아래의 연속적인 그림은 모두 각 서버와 현재 동기화를 이루려고 하는 client와의 NTP timestamp교환에 의해 얻어진 값들 중 일부분을 표시한 것이다. 각 값들은 하루(5/11) 동안의 data에서 발췌한 것으로 순서대로 delay, offset, error bound, 순간 오류를 나타낸 것이다.
Delay 값의 경우 4개의 서버 모두가 0.3 ~ 0.6(sec.)정도를 나타내는 것을 볼 수 있는 데 이는 거리상 delay가 길어질 경우 특별한 보정 효과를 볼 수 없기 때문에 서버 선택 시 적당한 delay값을 보이는 서버를 의도적으로 선택한 결과이다. 하지만 여기서도 delay가 Internet 환경에서는 유동적임을 알 수 있고 아래 그림에서 표시되지 않는 부분에서는 순간적으로 time expire를 초과할 정도의 delay가 길어지는 경우도 보였다. 이러한 Internet의 신뢰할 수 없는 환경에서 동작하는 time server는 이러한 delay의 유동성을 보장 가능한 것이어야 하는데 여러 가지 protocol중 NTP에서는 이러한 면을 고려해서 설계되었다.
위의 그림은 동기화 시각을 제공하는 server와 동기화 하려고 하는 client간의 시간 차를 표시한 것이다. 경우에 따라서 약간씩 차이 나는 경우도 있지만 4개의 서버가 유사한 값들을 가지고 진행되는 것을 볼 수 있다. 이러한 서버와의 차이가 나는 시각을 일정 처리를 거쳐 local clock을 보정하는 수치로 변환시키는 것이 NTP의 주 작업이라 할 수 있다.
위는 Dispersion(오류 최대치)를 표시한 것이다. 모든 서버가 발생 시간을 달리해서 최대 오차를 4초 정도로 해서 나타내는 것을 알 수 있는데 이러한 오류 최대치는 delay나 local clock의 skew에 의해서 기인하는 것으로 이 값을 근거로 오류 보정 간격을 늘이거나 줄이거나 하는데 사용된다.
아래는 전체적인 local clock 오류 값을 server 측과의 비교에서 나온 것이다. 동기화가 점점 이루어지면서 이러한 값들이 각 서버와 비교해서 점점 작아짐을 알 수 있고 점점 보정이 이루어지고 있음을 나타낸 것이다.
결론
본 TR에서 NTP에 관련된 전체 구조, 전체 동작 주요 알고리즘 설명 그리고 마지막으로 NTP client에서의 통계치 분석 등을 살펴 보았다. 앞에서도 언급했지만 시각 동기를 위한 방법은 여러 가지가 존재하고 실제로 여러 기법들이 사용되고 있으며 이러한 시각 동기를 전문으로 하는 시장도 많이 존재하고 있는 현실이다.
이런 여러 가지 방법론에서 NTP가 가지는 장점은 현재 많은 사용자를 보유하고 있는 Intent을 통해 서비스 가능하고 이러한 Internet 환경에 적합하다는 점이다. 이것은 Internet을 통한 분산 시스템에서도 중요하게 사용될 수 있는 기법임을 의미한다. 또한 여러 유사 프로토콜에 비교해 월등한 동기화 능력과 정밀한 동기가 요구되는 분야에도 자체적으로 높은 precision을 제공하기 때문에 널리 이용 가능하다. 하지만 외부 절대 시각을 계속해서 유지할 필요가 없는 시스템의 경우에도 NTP를 이용해서 동기화를 이루는 경우 전체적인 동기 시각을 유지해야 하는 overhead를 지닌 것이 NTP의 약점이라 할 수 있다.
앞으로 통신망을 통하여 메시지를 서로 주고받는 처리 요소들의 집합인 분산 시스템에서 이러한 동기화 기법을 사용할 경우 분산 시스템의 특성상 발생하는 사건 시각을 정확히 설정해서 제반 기능의 동기화, 순서화 및 일관성 유지가 이루어져야 하므로 기존의 이런 기법들에 대한 연구가 더 진척되고, 각각의 응용 분야에 적합한 기법들이 개발되어야 할 것이다.
Reference
Mills, D,L. Network Time Protocol(version 3) specification, implementation and analysis, RFC-1305
Daytime Protocol, RFC 867
Time Protocol, RFC 868
Mills, D.L. Network Time Protocol(version 2) specification and implementation
Mills, D.L., Ajit Thyagarajan, Network Time Protocol Version 4 Proposed Changes, Electrical Engineering Department University of Delaware Technical Report 94-10-2