최소 페어 프로토콜

Minimum-Pairs Protocol

최소 쌍(또는 MP)은 전방 및 후방 단방향 네트워크 지연(OWD) 중 더 적은 양을 실시간으로 추정하기 위한 능동 측정 프로토콜이다.[1] 그것은 3개의 네트워크 노드 집합이 자신들 사이의 상한 OWD와 네 번째 신뢰할 수 없는 노드 사이의 OWD를 추정할 수 있는 적대적인 환경에서 작동하도록 설계되었다. 네 번째 노드의 정직한 협조가 필요하지는 않지만 네 개의 노드는 모두 협력해야 한다. 목표는 신뢰되지 않은 노드를 클럭 동기화에 포함시키지 않고, 왕복 시간(RTT)의 절반보다 더 정확한 방법으로 그러한 추정을 수행하는 것이다. MP 프로토콜은 지연에 민감한 애플리케이션(예: 콘텐츠 전송 네트워크 복제본 배치)이나 안전한 인터넷 위치 지정을 위해 사용될 수 있다.

방법론

MP 프로토콜의 예. 셀의 숫자 <i, j>는 i행에 표시된 노드부터 노드 X까지 계산된 OWD(예: 밀리초 단위)를 나타낸다.

MP 프로토콜은 세 개의 신뢰할 수 있는 네트워크 노드가 시계를 동기화하고, 그들의 공용 키에 안전하게 접근할 수 있도록 요구하는데, 이것은 폐쇄적인 PKI(Public Key Infrastructure) 시스템을 통해 달성될 수 있다. 신뢰할 수 없는 노드는 정직하게 협력한다고 가정되지 않기 때문에 따를 필요가 없다. 노드 A와 신뢰할 수 없는 노드 X 사이의 전방 및 후방 OWD 중 작은 부분에 대한 상한을 추정하기 위해, X는 먼저 세 노드 모두에 대한 애플리케이션 계층 연결을 설정한다. 이것은 예를 들어 WebSockets를 사용하여 브라우저를 통해 투명하게 수행될 수 있다. 그런 다음 세 노드가 교대로 디지털 서명된 타임스탬프를 교환한다.

노드 A가 시작되면 서명된 타임스탬프를 X로 전송한다. 노드 X는 이 메시지를 다른 두 노드에 전달한다. 메시지를 받으면 메시지 수신 시간이 기록된다. 그런 다음 수신 노드는 서명을 확인하고, 신뢰할 수 없는 노드를 통과하는 수신자에게 네트워크를 통과하는 데 메시지가 걸린 시간을 계산한다. 이것은 메시지의 타임스탬프를 수신 시간에서 빼면 된다. 그런 다음 노드 B가 프로세스를 반복하고 노드 C가 그 뒤를 잇는다. 3개 노드가 모두 교대로 배치된 후 링크에 해당하는 6개의 지연 추정치를 사용하여 종료한다.

  • A → X → B → B → X → A
  • A → X → C · C → X → A
  • B → X → C, C → X → B

A, B, C 및 X 사이의 세 개의 네트워크 링크에서 전방 및 후방 OWD 중 더 작은 것을 추정하기 위해 위의 각 쌍을 최소로 취한다(즉, 더 큰 OWD는 폐기한다. 세 쌍 각각은 각 링크의 작은 OWD에 대한 근사치를 나타내며, 이 OWD는 3개의 미지의 방정식으로 구성된 시스템을 생성한다. a, b, c(그림 참조)에 대한 이 두 가지를 동시에 풀면 지연 추정치가 나온다.

숫자 예제

노드 A, B 및 C에서 노드 X에 대한 실제 지연(예: 밀리초 단위)은 다음과 같다고 가정하고, 그 반대의 경우도 다음과 같다.

A B C
노드 X에 연결 5 8 2
원본 노드 X 6 4 4

그것들은 알려지지 않은 지연이다. 우리는 세 개의 링크 각각에서 앞쪽과 뒤쪽으로 작은 것을 추정할 필요가 있다. 이 예제에서 X와 세 개의 신뢰할 수 있는 노드(A, B, C) 사이의 링크에서 각각 5ms, 4ms, 2ms가 작다. 노드가 타임스탬프 메시지를 교환할 때 다음 내용만 볼 수 있다.

  • A → X → B = 9 ms, B → X → A = 14 ms (9 ms는 더 작음)
  • A → X → C = 9 ms 및 C → X → A = 8 ms (8 ms는 더 작음)
  • B → X → C = 12 ms 및 C → X → B = 6 ms (6 ms는 더 작음)

따라서 방정식의 체계는 다음과 같이 된다.

다음과 같은 OWD를 더 작게 추정할 수 있다.

In this case, the absolute errors are , , and on all three links respectively. In comparison, the average RTT would calculate the OWD on all three links as 5.5 ms, 6 ms, and 3 ms, resulting in absolute errors of 0.5 ms, 2 ms, and 1 ms respectively. Therefore, the MP protocol is more accurate in this example.

Analysis

Injecting artificial delays by, e.g., holding onto the message for a little while instead of promptly forwarding it, enables the untrusted node to increase the estimated OWDs. The MP protocol can thus estimate an upper bound for OWDs on all three links collectively between the trusted nodes and the untrusted one. For example, if the estimated delays (forward or reverse) were 30 ms, 40 ms, and 50 ms, the actual cannot be 60 ms, 70 ms and 80 ms because that means the untrusted node managed to reduce all three together, which is hard to achieve since delays are bound by the physical characteristics of the transmission media. Note however that the untrusted node may in some case be able to reduce a subset of the links, but not all, by selectively delaying some of the links.

Compared to the average (i.e., RTT/2), the MP protocol never returns an estimate to the smaller of the forward and reverse OWD that is larger than that returned by the average method. Additionally, the probability distribution of absolute error for the MP protocol has been derived[2] as a function of the underlying delay distribution. This is useful as it enables the calculation of expected error knowing the nature of delays on the links between the untrusted node and the trusted ones.

참고 항목

참조

  1. ^ Abdou, AbdelRahman (2015). "4". Internet Location Verification: Challenges and Solutions (Ph.D.). Carleton University.
  2. ^ Abdou, AbdelRahman; Matrawy, Ashraf; van Oorschot, Paul (May 2015). "Accurate One-Way Delay Estimation with Reduced Client-Trustworthiness". IEEE Communications Letters. 19 (5): 735–738. CiteSeerX 10.1.1.696.7425. doi:10.1109/LCOMM.2015.2411591.