KR20070085208A - 큐 제어와 단방향 지연 측정을 이용한 망 혼잡 제어 방법및 장치 - Google Patents

Abstract

본 발명은 망 혼잡(network congestion)을 감소시키기 위해 스케일가능 큐 크기(scalable queue size) 및 단방향 큐 지연 측정(one-way queueing delay measurement)을 포함한 지연 기반 방식(delay based scheme)인 혼잡 제어 방식(congestion control scheme)을 제공한다. 큐 크기는 큐 제어, 스케일가능(scalable) 유틸리티 함수, 다이내믹 알파 동조(tuning), 무작위(randomized) 알파 동조, 식-기반(equation-based) 알파 동조에 의해 처리된다. 단방향 큐 지연은 다양한 방법의 수신기 클록 주기(receiver clock period) 추정을 이용한 역방향(backward) 지연 처리를 측정함으로서 실행된다. 실시예는 단일 샘플 및 다중 샘플 주기를 사용한 수신기 클록 주기를 추정하는 단계를 포함한다. 이 시스템은 라우트(route) 변화 감지를 위한 방법을 포함한다.

Description

큐 제어와 단방향 지연 측정을 이용한 망 혼잡 제어 방법 및 장치{METHOD AND APPARATUS FOR NETWORK CONGESTION CONTROL USING QUEUE CONTROL AND ONE-WAY DELAY MEASUREMENTS}

본 발명은 네트워크 분야(the field of networks) 및 혼잡 제어(congestion control)를 위한 방법(method)과 장치(apparatus)에 관련된다.

이 특허 서류의 공개된 부분은 저작권의 보호를 받는 소재(material)를 담고 있다. 저작권 소유자는 특허청(Patent and Trademark Office) 파일이나 기록에 나타난 특허서류 또는 특허 공개대로의 임의의 사람에 의한 팩시밀리 재생도 반대하지 않으나, 그 밖의 어떠한 모든 권리도 유보된다.

본 출원은 미합중국에 출원중인,

"Methods to Improve Delay Based TCP"라 명명되며, 2004년 8월 30일 제출된 U.S. Provisional Patent Application No. 60/605,458,

"Fast TCP Queue Control"이라 명명되며, 2004년 8월 19일 제출된 U.S. Provisional Patent Application No. 60/602,987,

"Method for measuring One-Way delay Changes for TCP/IP Networks"라 명명되며, 2004년 8월 17일 제출된 U.S. Provisional Patent Application No. 60/602,111,

전체가 참조로 인용되는 선출원의 이익을 주장한다.

기술의 배경

컴퓨터 망(networks)은 하나 이상의 컴퓨터 간에 통신을 가능케 한다. 망은 근거리통신망(local area networks, LAN), 광역통신망(wide area networks, WANs), 인터넷(Internet), 무선망(wireless networks), 복합장치망(mixed device networks) 및 기타를 포함한다. 망의 효율적 이용에 있어 하나의 한계는, 망이 효율적으로 다룰 수 있는 것보다 메시지 소스와 수신지의 수 및 메시지 트래픽 양이 많을 때 발생하는 망 혼잡(network congestion)이다. 종래 기술에서 이 같은 혼잡 문제는 혼잡 제어(congestion control)을 실행하여 다루어진다.

혼잡 제어는 경쟁하는 사용자 간에 망 자원을 공유하는 일종의 분산 알고리즘(distributed algorithm)이다. 이것은 자원의 사용가능여부(availability)와, 경쟁하는 사용자들의 세트가 시간에 따라 예측 불가능하게 바뀌는 상황에서 사용되나, 그럼에도 불구하고 효율적인 공유는 바람(desire)일 뿐이다. 예측 불가능한 공급과 수요 그리고 효율적인 동작과 같은 제약 요소들은 종전 기술에서 피드백 제어(feedback control)로 해결해 왔다. "폐 루프(closed loop)"로도 불리는 피드백 제어는 최적의 결과를 시스템에 제공하기 위한 동적이고 전형적으로 실시간인 시스 템의 조정(adjustment)을 결정하는 소정의 메트릭(metric) 사용을 포함한다. 이런 시스템은 피드백이 없는 소위 "개방 루프(open loop)"와 구분된다(예를 들면, 고기 온도계를 사용하지 않고 터키를 요리하면 개방 루프 시스템이고 고기 온도계를 사용하여 요리하면 폐 루프 시스템이다).

종래 기술의 접근법은, 트래픽 소스(traffic sources)들이 경로상의 혼잡에 응답하여 그들의 속도(rates)를 동적으로 적응시킨다. 혼잡 제어를 위해 피드백 제어를 사용하는 망의 한 예가 인터넷(데이터 전송에 연루된 소스와 목적지 컴퓨터에서 전송 제어 프로토콜(Transmission Control Protocol, TCP)을 사용함)이다. 우리가 인터넷에 대해 논의하지만, 본 출원은 다른 망에도 적용된다는 점에 유의하여야 한다.

"Reno"라고도 불리는, 현재 TCP에서의 혼잡 제어 알고리즘은 1988년 개발되었고, 이후 몇 가지 변화가 이루어져 왔다. 현재 연구에 의하면, 대역폭 지연(bandwidth-delay) 제품이 계속 늘어남에 따라 TCP Reno는 결국 성능의 병목(performance bottleneck)이 될 것으로 예측한다. 즉, 비록 망(인터넷)은 계속적으로 높은 대역폭과 성능을 제공하더라도 혼잡을 처리하기 위해 사용되는 현재 제어 시스템으로는 망의 비효율적 사용을 초래할 것이다. 다음 4가지의 어려움이 큰 대역폭 지연을 가진 제품이 사용되는 망에 있어서 TCP Reno가 초라한 성능을 갖는데 기여한다.

1. 패킷 레벨에서, 왕복 시간(Round-Trip Time, RTT) 당 한 패킷의 선형(linear) 증가는 너무 느리고, 손실 이벤트(loss event) 당 승산적으 로(multiplicative) 감소하는 것은 너무 크다. 현재의 방식(scheme)은 "가속은 느리게/감속은 빠르게(speed up slowly/ down quickly)" 접근법을 패킷 트래픽 제어에 사용하고, 이는 고 대역폭 시스템에서 효과적이지 않다.

2. 흐름(flow) 레벨에서, 큰 평균 혼잡 창(large average congestion windows)을 유지하려면 극단적으로 작은 평형상태 손실 확률(small equilibrium loss probabilities)이 요구되는 바, 이러한 작은 손실은 종래 기술 시스템에 실용적이지 못하다.

3. 패킷 레벨에서, TCP는 2진 혼잡 신호(binary congestion signals)(패킷 손실)를 사용하므로 진동(oscillation)을 피할 수 없다(패킷 손실).

4. 흐름 레벨에서, 다이내믹(dynamic)이 불안정하여 심각한 진동을 초래하는데, 이런 진동은 패킷 손실 확률의 정확한 추정과 흐름 다이내믹의 안정된 설계로만 줄여질 수 있다. 현재의 시스템은 패킷 손실의 충분한 정확한 추정을 허용하지 않는다.

도 1은 발명의 큐 제어 실시예를 설명한 흐름도.

도 2는 다이내믹 알파 동조 실시예를 설명한 흐름도.

도 3은 무작위 알파 동조 실시예를 설명한 흐름도.

도 4는 BQD 계산 실시예를 설명한 흐름도.

도 5(a)는 ACK 송신과 수신 시간에 수신기와 송신기 클록 값을 설명한 타이 밍도.

도 5(b)는 샘플들로부터 받은 수신기 클록 주기의 상한(upper bound) 및 하한(lower bound)을 설명한 타이밍도.

도 6은 발명의 실시예에서 일어난 혼잡 손실 감지를 설명한 흐름도.

도 7은 발명 실시예의 적응 알고리즘을 설명한 흐름도.

도 8은 발명에서 라우트 변화 감지 실시예의 흐름도.

도 9는 발명에서 알파 동조 실시예의 흐름도.

혼잡 제어를 위한 방법 및 장치가 설명된다. 다음의 설명에서는, 좀 더 완전한 본 발명의 설명을 위하여 수많은 디테일(details)이 설명된다. 그러나 당업자는 이러한 디테일이 없이도 본 발명을 실행할 수 있다는 것은 분명하다. 다른 경우에 있어서는, 본 발명을 불필요하게 모호하게 하지 않도록 잘 알려진 특징은 자세하게 설명하지 않았다.

본 발명은 지연 기반 모델로, 사실은 큐 지연을 혼잡 측정으로 사용하여 손실 기반 시스템인 종래 기술을 능가하는 장점을 제공한다. 한 가지 장점은 큐 지연(queuing delay)이 손실 확률(loss probability)보다 더 정확히 추정될 수 있다는 점이다. 이것은 망에서 큰 대역폭 지연 제품의 패킷 손실은 TCP Reno와 그것의 변형(variants)(10^-7 또는 그보다 작은 확률)하에서 거의 볼 수 없는 이벤트이기 때문이고, 손실 샘플은 큐 지연 샘플보다 거친 정보를 제공하기 때문이다. 실제로, 지연 측정은 손실 확률 측정과 마찬가지로 잡음이 많다. 그래서, 본 발명의 다른 장점은, 각 패킷 손실 측정(패킷이 손실되었는지 아닌지)이 잡음을 필터링하기 위해 하나의 정보 비트만 제공하지만 큐 지연의 각 측정은 다수의 비트(multi-bit) 정보를 제공하는 점이다. 이것은 식 기반 구현(equation-based implementation)이, 목표한 공평성과 고 활용과 더불어, 망을 정상 상태로 안정시키기 쉽게 한다. 또한, 큐 지연의 다이내믹은 망 용량(network capacity)에 관한 스케일링(scaling)을 제공한다. 이것은 용량에 있어 망 스케일이 올라갈 때 안정성을 유지하는데 도움이 된다. 하나의 지연 기반 방식이 "Method and Apparatus for Network Congestion Control"이라 명명되며, 2004년 6월 14일 제출된 미합중국 특허출원 제 10/868,564 호에 설명되어 있고, 본 발명의 양수인에게 양도되어 있으며, 그 전체가 본 명세서에 참조로써 합체(incorporated)된다. 이 언급 및 합체된 특허 출원에 설명된 기술은 본 명세서에서 "지연 기반 TCP(Delay Based TCP)"로 참조된다.

본 발명은 버퍼 오버플로(buffer overflow) 조건 및 큐 지연 측정 기술을 다룬다. 첫째, 버퍼 오버플로 조건이 논의된다.

위에 인용된 출원에서 밝히듯, 접속 상태의 평형(equilibrium of the state of the connection)을 결정하는데 쓰이는 매개변수(parameter)중 하나는 알파(α)다. 평형에서, 각 각의 접속은 중간 라우터 버퍼내에 총 알파개의 패킷을 유지한다. 일 실시예에서, 알파는 잡음 지연 측정을 극복하여 단일 흐름이 공유되지 않고 고속 링크를 완전히 이용할 수 있도록 기가비트(Gigabit) 망(Gigabit networks)상에서 200으로 맞추어진다. 그러나 다수의 높은 볼륨 흐름이 링크를 공유하려 할 때, 버퍼가 평형 상태에 도달하기 전에 버퍼 오버플로가 발생할 수 있다. 필요한 버퍼링을 제공하기 위해서는 N 흐름이 있을 때 Nα 만큼의 메모리를 필요로 한다. 그러나 망상에서 유용한 버퍼 메모리의 양은 그 같은 요구를 만족시키기에 항상 충분치 않다. 버퍼 크기가 불충분 할 때 오버플로가 일어나고 패킷이 결과적으로 손실된다.

본 발명은 버퍼 용량이 너무 작거나 또는 흐름의 수가 너무 많을 때 버퍼 오버플로를 다루는 다수의 방법을 제시한다. 이들 기술은 큐 제어, 스케일가능 유틸리티 함수, 다이내믹 알파 동조, 무작위(randomized) 알파 동조, 그리고 식 기반 알파 동조를 포함한다.

알파 동조는 지연 기반 TCP(Delay Based TCP)가 변하는(그리고 아마 알려지지 않은) 버퍼 한계를 지닌 망에서 거의 손실이 없고 높은 활용성을 가질 것임을 보증한다. 예를 들면, 몇 몇 시나리오에서는, 망이 다수의 지연 기반 TCP를 지원하기에 충분한 버퍼링을 갖지 못할 것이다. 알파 동조가 없다면, 모든 지연 기반 TCP는 계속되는 패킷 손실에 시달릴 것이다. 알파 동조는 적절한 알파 값을 골라 각 각의 지연 기반 TCP를 도울 수 있고 망이 평형상태에 도달하도록 허용할 수 있다.

큐 제어(Queue Control)

지연 기반 TCP는 평형상태에 이르는 경로의 각 병목 라우터(흐름의 경로에 둘 이상의 병목 라우터가 있을 수 있다)에 큐잉된 그 자신의 패킷 총합인 매개변수 α를 갖고 있다. 큐 제어 기술은 지연 기반 TCP가 좀 더 작은 α값을 사용케 허용하면서 동시에 잡음 지연 측정에 대해 내성을 갖을 수 있도록 한다. 수학적으로, 큐 상태인 패킷의 수는 평형 조건으로 표현된다.

큐잉된 패킷의 수 = x·q =α

여기서 x는 달성된 처리량 그리고 q는 측정된 왕복 큐 지연

그러므로, α값은 평형 큐 지연 q(equilibrium queuing delay)를 결정한다. 실제에 있어서, α는 큐 지연 q가 지연 측정에서의 잡음 레벨 이상인 결과가 나오도록 충분히 크게 선택되어야만 한다. 예를 들면, 우리는 망에 단일 흐름이 있을 때 큐 지연이 적어도 5ms가 되도록 α를 전형적으로 선택한다.

큰 α는 그러나 공유하는 동일 망 흐름 수가 크다면 문제를 만들어 낼 수 있다. α는 패킷 손실을 피하기 위해 지연 기반 TCP로부터 패킷을 공급하는데 필요한 최소한의 버퍼링 양이기 때문에, 지수 i=1, 2, ..., N에 의해 인덱싱되는 N 흐름이 있고 매개변수 α일때, 전체 버퍼링 요구는

망 버퍼링 요구 =

이다.

모든 흐름이 동일 매개변수 값을 쓰는 특수한 경우, 예를 들면 α_i=α(모든 I=1,...,N 에 대해)이면

망 버퍼링 요구 =

이 된다.

이 식으로부터, 버퍼링 요구가 N과 더불어 천천히 커지도록 작은 α가 바람직하다.

그러므로, 지연 측정에서 잡음에 대해 내성을 갖게 하기 위해서는 큰 α가 필요하나 망 버퍼링 요구를 작게 하기 위해 작은 α가 필요하다는 딜레마가 있을 수 있다. 큐 제어는 이런 상충하는 목표를 조화시키는 기술이다.

큐 제어의 실시예를 설명하는데 있어, 우리는 모든 흐름은 동일 매개변수 값, 예를 들어 모든 i에 대해 α=α을 갖는다고 가정한다. 도 1은 본 발명의 큐 제어 방식 실시예를 예시한 흐름도이다.

본 발명의 실시예는 상술한 평형 조건을 다음과 같이 수정한다.

q₀는 지연 측정(스텝 (101))의 에러에 대해 내성을 갖게 하기 위해 종단에서 종단으로의 각 경로(each end to end path)에 유지시키고자 희망하는 최소 큐 지연(예를 들면, 5ms)이다. q₀ 를 넘어서 각 지연 기반 TCP 접속은 α 패킷에 기여한다. 최소 지연 q₀ 를 포함시킴으로써 우리는, 그 다음, 버퍼링 요구가 N 과 더불어 천천히 커지도록 작은 α를 선택할 수 있다. 예를 들면, α는 기가비트 망에 조차도 (5ms가 아닌) 0.5ms와 같이 작은 큐 지연을 일으키도록 선택될 수 있다. 이것을 분명히 보기 위해, 공통 매개변수 α와 N=1인 흐름에 의해 공유되는 용량 c 와 처리량 x=c/N인 단일 링크를 보자. 상기 수정된 평형 조건으로부터 큐 지연은 다음과 같이 주어진다.

측정된 큐 지연 = q=q₀+Nα/c(스텝 (104))

최소 지연 q₀를 포함시킴으로써, 측정 큐 지연 q는 우리가 스텝 (102)에서 작은 α를 선택하더라도 (그리고 N=1 이더라도) 잡음 레벨과 비교하여 아직도 충분히 클 수 있다. N(elephant) 흐름이 있을 때 버퍼링 총량은

망 버퍼링 요구 Nxq=cq₀+Nα이다(스텝 (103)).

그러므로, 작은 α는 N에 있어 버퍼링 요구의 느린 성장을 가져온다(cq₀의 0이 아닌 최소 버퍼링 요구를 유발하는 비용을 지불하고).

요약하면, 스텝 (104)으로부터 우리는 큐 지연이 흐름의 수 N과 관계없이 적어도 최소 큐 지연 q₀를 항상 포함할 것이라는 것을 본다. 예를 들어, 우리가 q₀ 를 5ms로 선택하면, 버퍼는 Nα 더하기 상수 5ms 큐잉 지연을 수용할 필요가 있다. q₀가 이미 지연 측정에서 잡음에 대한 면역성을 제공하므로, α는 작게 선택될 수 있고 스텝 (103)에서 N의 버퍼링 요구의 더욱 느린 성장을 가져온다. 그러므로, 망 내부에서 고정 버퍼 크기가 주어졌더라면, 이 큐 제어 기술은 동시에 발생하는 다수의 지연 기반 TCP 흐름을 허용한다. 스텝 (105)에서, 선택된 α가 (예를 들면, 풀 링크 활용성 및 패킷 손실의 부재를 관찰하여) 흐름의 수 N을 위한 적절한 버퍼 크기를 가져왔는지 결정한다. 그렇다면, 큐 제어는 스텝 (107)에서 실행된다. 그렇지 않다면, 다른 α값이 스텝 (103)에서 선택된다.

시간 K에서 큐 지연 q_k일 때 하나의 지연 기반 TCP 윈도우 갱신 알고리즘은

이다.

여기서 w_k 및 w_k+1는 각 각 시간 k 및 k+1에서 윈도우 크기이고 d는 전파지연 또는 베이스 RTT이다. 큐 제어가 적용되면 윈도우 갱신 알고리즘은

이다.

새로운 평형상태는 진정한 베이스 RTT 측정과 비교하여 q₀에 의하여 상승(elevate)된 수정 베이스 RTT를 보는 각 지연 기반 TCP로서 해석 될 수 있다. 베이스 RTT의 에러로 인해 지연 기반 TCP 알고리즘이 아직 유틸리티 최대화 문제를 푸는 것을 알 수 있다.

스케일 가능 유틸리티 함수(Scalable utility function)

두 번째 기술은 큐 제어가 지연 기반 TCP의 유틸리티 함수를 수정하는 감시를 일반화한다. 이 실시예는 임의의 복수 α값에 대하여 링크상에 경로의 수 N과 더불어 버퍼 요구의 제어된 그리고 느려진 성장을 가져오는 유틸리티 함수를 수정한다. 평형 조건을 고려하면

이다.

u(x)는 한계 유틸리티 함수이다. 용량 c=Nx 인 단일 링크를 공유하는 N개의 동일한 흐름과 동일시되는 N에 대한 평형 백로그(backlog)는

이다.

u는 감소 함수이기 때문에, 총 백로그 B(N)은 N과 함께 증가하나, 우리는 N에서 u(c/N)의 성장을 제어하도록 u를 선택할 수 있다. 하나의 지연 기반 TCP 방식은 u(x)=α/x 이므로 B(N)=αN이며 이는 N에서 선형(linear)이다. N에서 B(N)의 성장률을 줄이기 위해, X가 피크율이고 β가 특별한 환경에서 동조 될 수 있는 소정의 양의 상수면 우리는

를 선택할 수 있다. 그러면

이다.

이것은, 선형과 상반되게, N이 증가함에 따라 B(N)의 느린 대수적(logarithmic) 증가를 결과한다. 스케일가능 유틸리티 함수의 장점은 다수의 β 값을 사용하면서 버퍼 오버플로를 제어할 수 있다는 점이다. 예를 들면, 우리가 β=5ms를 취하면, cβ는 큐의 5ms를 수용할 수 있게 하는 버퍼 용량이다. B(N)은 N에서 대수적으로 증가함을 주목하자.

일단 스케일가능 한계 유틸리티 함수 u(x)가 선택되면, 윈도우 조정(adjustment)은 다음 형태를 띨 수 있다.

로그 함수 외에 U(X)의 다른 함수가 N과 더불어 B(N)의 느린 증가를 얻기 위해 사용될 수 있음을 주목하여야 한다. 실제로, u(x) 부선형(sublinear) 감소율을 갖는 임의의 양의 감소 함수일 수 있다. 하나의 그런 예는: X가 피크율이라면,

이고 그러면

이 된다.

즉, B(N)은 N과 더불어 선형으로 보다는

처럼 성장한다.

마지막으로, 버퍼 오버플로를 막기 위해 전장에서 설명된 큐 제어 기술과 위에 설명된 스케일가능 유틸리티 함수 기술을 결합할 수도 있다. 예를 들면, 큐 제어 기술과 u(x)=α/x 를 결합하면, 새로운 한계 유틸리티 함수: u(x)=α/x+q₀를 얻는다. 이 방법에서, 버퍼링 요구는

이고

이므로, 버퍼링 요구는

이 된다.

그러므로, 최소 큐 지연 q₀로, 매우 작은 β를 선택할 수 있고 B(N)에서 성장은 cβlogN의 정도(order)가 된다. 비록 로그 함수가 여기 쓰였지만, 발명의 범주와 정신을 벗어나지 않고 다른 함수도 대신 사용될 수 있다. 예를 들면, 제곱근 함수가 쓰일 수 있다.

다이내믹 α 동조(Dynamic α tuning)

이 기술은 느린 시간스케일(timescale)에 또한 분산 방식으로 α를 동적으로 적응시키려 한다. 이 기술의 실시예는 도 2의 흐름도에 설명되어 있다. 큐 지연 대신에, 이 실시예는 패킷 손실(스텝 (201))을 각 호스트 기계(each host machine)의 α를 제어하기 위한 신호로 사용한다. 호스트 기계(스텝 (202))에 의해 감시(observe)되는 각 혼잡 손실 이벤트(예를 들면, 각 RTT에 적어도 8 버스트 또는 cwnd/10 패킷 손실)에 대해, 알고리즘은 현재 값에 비례하는 해당하는 양(스텝 (203))만큼 α를 줄인다(승산적 감소 또는 MD). 각 제어 구간에서, 알고리즘은 상수 값으로 αfmf 증가시킨다(스텝 (204))(덧셈 증가(additive increase, AI)). 즉, 이 기술의 실시예에 반응하여 α는 느리게 증가하나 빠르게 감소한다(AIMD로 지칭함). 실제로 α는 미리 지정된 범위 내에서 수정되며 각 수정의 크기에는 상한(cap)이 있다.

AIMD 접근법이 손실 기반 알고리즘의 혼잡 윈도우를 제어하는데 사용된다. 여기서 AIMD 접근법은 지연 기반 일고리듬에서 α 동조에 사용된다. 이 기술로 글로벌 협력 없이도 공평성과 효율성이 달성될 수 있다.

종전 기술인 손실 기반 혼잡 제어 알고리즘은 패킷 손실의 잡음으로 어려움을 겪어왔다. 이것은 고속 장거리 망 및 무선망에서 매우 분명하다. 이들 알고리즘은 혼잡 윈도우를 줄임으로서 패킷 손실에 반응한다. 무작위 패킷 손실이 지배하는 시나리오에서는, 무작위 패킷 손실이 그 같은 변화를 요구하지 않아야 하는데 알고리즘은 계속적으로 혼잡 윈도우를 줄임으로서 제대로 작동하지 않는다.

혼잡 신호로 패킷 손실을 사용하는 대신, 이 실시예는 α 동조의 신호로 혼잡 손실 이벤트를 사용하려 시도한다. 혼잡 손실 이벤트는 혼잡으로 인해 패킷이 탈락하는 이벤트로 정의된다. 대조적으로, 무작위 패킷 손실은 무작위 링크 에러 및 혼잡과 관련 없는 다른 효과로 인해 패킷이 탈락하는 이벤트다. TCP 혼잡 제어 알고리즘은 혼잡 손실 이벤트에만 반응해야 한다. 측정으로부터, 다중 패킷 손실은 보통 혼잡 손실 이벤트에서 나타난다. 단일 패킷 손실은 무작위 손실 이벤트에서 나타난다. 본 발명은 혼잡 손실 이벤트를 결정하기 위한 특정한 매개변수를 이용한다.

P=8 패킷: 혼잡 손실 이벤트 탐지의 임계(threshold). 한 윈도우에 P 이상의 패킷 손실이 있으면, 탐지 알고리즘은 패킷 손실이 혼잡 때문이라고 추정한다. P는 양의 정수여야 한다.

counter(계수기): 현재 윈도우에서 탐지되는 패킷 손실을 위한 계수기(음이 아닌 정수).

cwnd : 혼잡 윈도우(혼잡 제어 알고리즘으로부터, 이들 알고리즘을 위한 입력 변수임)

매개변수 P 는 혼잡 윈도우 cwnd의 선형 함수일 수 있다. 예를 들면, k≥100일 때 P=cwnd/k이다. 그것은 패킷 손실 이벤트가 매 k 패킷마다 하나가 손실될 때만 혼잡 손실 이벤트로 탐지 된다는 것을 의미한다. 그 같은 변형은 무작위 손실율이 높을 수 있는 무선망에서의 접속에 유용할 수 있다.

도 6은 본 발명의 혼잡 손실 이벤트 탐지의 일 실시예의 동작을 설명한 흐름도이다. 스텝 (601)에서 시스템은 초기화되고 계수기가 0에 맞추어진다. 결정 블록(decision block) (602)에서 패킷 손실이 탐지 되었는지 결정된다. 탐지되지 않았다면, 시스템은 패킷 손실을 점검하는 상태로 돌아간다. 탐지되었다면, 계수기는 스텝 (603)에서 증분(예를 들면 1씩)된다.

결정 블록 (604)에서, 계수기가 임계값 이상인지 결정된다. 실시예에 설명된(예로서) 계수기는 임계값이 {cwnd/10, p}보다 큰지 점검된다. 크지 않다면, 시스템은 스텝 (602)의 싸이클로 되돌아간다. 크다면, 혼잡 이벤트는 스텝 (605)에서 트리거된다. 결정 블록 (606)에서 현재 RTT가 완료됐는지 결정된다. 완료되지 않았다면, 시스템은 스텝 (602)으로 돌아간다. 완료 됐다면, 계수기는 스텝 (601)에서 영으로 리셋된다.

적응성 알고리즘(Adaptive Algorithm)

본 발명의 실시예는 α 값을 제어하기 위한 적응적 알고리즘을 제공한다. 이 알고리즘은 제시된 값과 다음 매개변수를 갖는다.

T=20 (sec): 정상 제어 구간. 가장 큰 RTT보다 커야만 한다.

A=1 (패킷): 각 제어 구간의 증가분 α값. 양의 정수여야만 한다.

B=1/8: 각 혼잡 손실 이벤트의 감소분 α. 분수로 (0,1) 안에 있어야 한다.

β1/2: 각 제어 구간의 감소분 α 분수 상한. (B, 1) 및 (0,1) 안에 있어야 한다.

: α의 하한(실시예). 양의 정수이어야만 한다.

: α의 상한(실시예).

보다 큰 양의 정수이어야만 한다.

현재 시간(current_time): 로컬 머신으로부터의 실시간으로 이 알고리즘의 입력 변수다.

차기 갱신 시간(next_update_time): 차기 정기 제어 이벤트 시간;

최종 알파(last_alpha): 최종 정기 제어 이벤트 직후의 α값

도 7은 이 실시예의 적응성 알고리즘을 설명한 흐름도이다. 이 알고리즘은 ACK 또는 혼잡 손실 이벤트가 일어났느냐 여부에 따라 다르게 반응한다. 시스템은 next_upgrade_time=current_time+T 및 last_alpha=α로 초기화한다. 스텝 (701)에서 ACK를 수신하기 위해, 시스템은 결정블록 (702)을 점검하여 현재 시간이 차기 갱신 시간보다 큰지 본다. 크지 않다면, 시스템은 다음 ACK를 기다린다. 크다면, 매개변수를 갱신할 시간이다. 스텝 (704)에서 차기 갱신 시간은 T 만큼 증가하고 α는 α+A로 맞추어진다. 결정 블록 (705)에서 α값은 상한 값

를 초과하는지 보기 위해 점검된다. 초과한다면, α값은 스텝 (706)의

와 동일하게 맞추어진다. 초과하지 않는다면, 최종 알파값이 스텝 (707)의 새로운 α값과 동일하게 맞추어진다. 이 알고리즘의 동작에서 볼 수 있듯이, 알파값은 ACK 신호가 수신되는 한, 상한 알파값까지 느리게 증가된다.

혼잡 이벤트가 스텝 (708)에서 일어나면, 알파값은 α=(1-β)^*α로 맞추어 스텝 (709)에서 감소된다. 스텝 (710)에서 이 값이 (1-β)^*last_alpha 보다 작은지 보기 위해 점검된다. 작다면, 알파값은 스텝 (711)의 (1-β)^*last_alpha와 동일하게 맞추어진다. 만약 결정 블록 (710) 또는 후속 스텝 (711)이 거짓이라면, 알파값은 결정블록 (712)에서 하한 알파값보다 작은지 보기 위해 점검된다. 작다면, 알파값은 하한 알파값 α에 맞추어진다. 작지 않다면, 종료(end) (714)로 진행된다.

라우트 변화 감지(Route Change Detection)

지연 기반 TCP는 왕복 시간(round-trip time, RTT)에서 왕복 전파 지연(round-trip propagation delay, pRTT)을 차감하여 왕복 큐 지연을 측정하는데, 여기서 왕복 전파 지연은 관찰된 최소 RTT를 취한다. 흐름이 더 긴 전파 지연을 갖는 새로운 경로로 변하면, RTT에서의 증가는 라우트 변화보다는 혼잡으로 해석될 것이고, 처리량의 감소를 가져온다. 그런 라우트 변화 전, α가 증가할 때, 증가된 큐 지연 때문에 RTT는 증가 되어야만 한다. 그 같은 라우트 변화 후, 큐가 비었으므로 RTT는 증가하지 않는다. 그러므로, 만일 다중 제어 구간에서

이 0에 가깝다면, 라우트 변화가 일어났을 것이다. 일 실시예에서, 시스템은 1/G를 사용하는데, 여기서 G는, c중/minRTT에 가깝고,

의 임계점과 같은, 흐름에 의해 달성된 처리량이다.

라우트 변화 감지 알고리즘(Algorithm of Route Change Detection)

본 발명의 실시예는 라우트 변화를 감지하는 알고리즘을 포함한다. 이 실시예의 매개변수와 변수는 다음을 포함한다.

매개변수(Parameter)

RC_Threshold=10: 라우트 변화 감지를 위한 임계. 만일

가 RC_Threshold 순차 제어 구간(각 구간은 길이 T를 갖는다)을 위한 1/G보다 작으면, 일고리즘은 라우트 변화 이벤트를 감지한다.

변수(Variables)

minRTT: 패킷 최종 윈도우에서 관찰되는 모든 RTT의 최소값. 이것은 혼잡 제어 알고리즘으로부터의 입력(input) 변수다.

cwnd: 패킷 최종 윈도우의 혼잡 윈도우. 이것은 혼잡 제어 알고리즘으로부터의 입력 변수다.

re_count:

가 1/G보다 작을 때 순차적 구간 수의 계수기

last_rtt:

가 1/G보다 작을 때 현재 순차적 구간의 첫 번째 구간에서 minRTT

last_alpha:

가 1/G보다 작을 때 현재 순차적 구간의 첫 번째 구간에서 알파값

도 8은 본 발명의 라우트 변화 감지 실시예의 흐름도이다. re_count=0, last_rtt=minRTT, 그리고 last_alpha=α로 초기화 한다. 각 제어 구간 T(스텝 (801))에 대하여 혼잡 손실 이벤트(스텝 (802))가 있는 지 결정한다. 있으면, 스텝 (807)에서 재 초기화한다. 없으면, 스텝 (803)에서 ((α-last_alpha)/(minRTT-last_RTT))≤(cwnd/minRTT)인지 결정한다. 성립되면, 스텝 (807)에서 재 초기화한다. 성립하지 않으면, 스텝 (804)에서 re_count를 증분(예를 들면, 1씩 증분)한다. 스텝 (805)에서 re_count가 rc_Threshold를 초과하는지 점검한다. 초과하면, 스텝 (806)에서 pRTT를 minRTT와 동일하게 맞추고 스텝 (807)에서 재 초기화한다.

무작위 α 동조(Randomized α tuning)

적응적 α 동조의 장점은 유연성에 있다. 장점중 하나는 AIMD는 항상 느린 시간스케일에서 큐를 채운다는 것이다. 보완 기술(complementary technique) 은 미리 결정된 일련의 값들 중 α 선택을 무작위로 하는 것이다. 이 기술은 버퍼가 충분히 크면 큐을 채우지 않으나, 공평성은 제어하기 힘들다. 무작위화는 통계적으로 긴 기간에 걸쳐 결과적으로(in the long run) 공평성을 달성하기 위해 사용되며, 도 3에 설명되어 있다.

예를 들면, α=8,20,200 패킷의 세가지 값이 대략 10 Mbps, 100 Mbps, 1 Gbps인 경로에 제 각기 선택된다. 흐름이 그것의 현재 α값(스텝 (302))에 상응하는 처리량 지역과는 다른 처리량(스텝 (301))을 최종 갱신 구간에 걸쳐 얻는다면, 다음 레벨(스텝 (304))로 α값을 증가시키거나 또는 감소시킨다. 아니면 α값은 동일(스텝 (303))하게 남는다. 예를 들면, α=200 패킷 및 얻어진 처리량이 9Mbps라면 α는 다음레벨 α=20 패킷으로 감소한다.

큰 α값을 가진 흐름이 작은 α값을 갖는 흐름에 해를 끼치면서 자원을 독점하는 것을 방지하고자, 각 흐름은, 큰 시간스케일에서, 무작위하게 그리고 독립적으로 그의 α값(스텝 (305))을 초기화하고, 위 알고리즘을 그의 α값을 다시 섞는데(reshuffle) 적용한다.

식 기반 알파 동조(Equation-Based Alpha Tuning)

지연 기반 TCP에서 식 기반 알파 동조의 목적은, 두 혼잡 피드백 값을, 즉, 종단-종단 큐 지연 q 및 손실 확률 p를, q 및 p의 함수로, 예를 들어, q/p/K 상수를 평형 상태로 모는 것처럼 미리 결정된 목표로 몰아가는 형태로, 동등하게 만드는 것이다. 손실 확률은 정확하게 잡아내기 어렵기 때문에, 한 실시예에서, 크기 S인 링 버퍼(ring buffer)가 손실 히스토리를 유지하는데 사용된다. 시스템은 최종 S개의 구간을 보고 S 구간에서 잃어버린 패킷의 수의 총합을 결정하고 그것을 S 구간에 보낸 패킷의 수의 총합으로 나눈다. 이 값은 손실 확률을 대표하고 p로 사용된다.

많은 경우에, 지연 기반 TCP는 망에서 손실 기반 혼잡 제어 프로토콜(예를 들면, Reno)과 동시에 사용될 것이다. 본 발명은 지연 기반 프로토콜과 손실 기반 프로토콜 양자가 적절한 처리량을 갖도록 K를 선택한다. K값은 대량의 실험 데이터에 기반하여 오프라인에서 계산될 수 있다. 본 발명에 예시로 사용될 K값의 예는 10이다.

알파 동조 알고리즘은 일 실시예에서 각 지연 기반 TCP 송신기에만 실행될 것이고, 반복적으로 평형상태 q와 p를 계산하고, q/p 비율을 K를 향해 조심스럽게 -전체 시스템과 처리량에 불안정을 일으키지 않고 지연 기반 TCP 혼잡 알고리즘의 알파 매개변수를 다이내믹하게 갱신함으로써- 일치시킨다. 알파 동조 알고리즘은 패킷 손실이 있을 때 작동되므로, 0이 아닌 손실 확률을 생성한다. 모든 지연 기반 TCP 흐름과 더불어 잘 규정된 망에서, 알파의 합을 적응시키는 충분한 버퍼링이 있는 한, 알파 동조는 작동되지 않고 평형 상태는 알파 동조가 없는 경우와 동일하다. 도 9에 알고리즘이 설명되어 있다. 초기 조건은

이고 초기 α 값은 alpha_O다. 스텝 (901)에서 주기적으로 시간 t에서 q_t 및 p_t 를 계산한다. 스텝 (902)에서 λ_t=q_y/p_t/k(p_t는 0이 아닐 때)를 계산한다. 스텝 (903)에서

를 계산한다. 스텝 (904)에서 새로운 알파 값

를 계산한다. λ_t가 증가함에 따라 새로운 α_t 값도 증가된다. 유사하게, λ_t가 감소함에 따라 새로운 α_t값도 감소된다. λ_t는 이론적으로 0에서 무한대까지 변할 수 있지만 실제 범위는 초기 값 α 및 α의 상한, 하한에 의존한다.

함수 f는 그것의 현재값

및 λ에 기초하여 새로운 평균

을 계산한다. f를 위해 임의의 합리적인 지수 움직임 평균화 함수(reasonable exponential moving averaging function)가 사용될 수 있다.

일 실시예에서, 부동 소수점(floating point) 연산을 실행하는 것이 가능하지 않을 수 있고 또는 바람직하지 않을 수 있다. 따라서, 부동 소수점 동작은 제한(limited)된 정확성을 가진 정수를 사용하여 근사치화 된다. 정수 데이터 형(type)이 커질수록, 부동 소수점 근사치화는 정확해진다. 본 발명은 부동 소수점 연산과 실행될 수도 있다.

알파의 급작스런 큰 증가를 방지하고자, 현재 알파값에 기초하여 알파의 성장에 제한을 가하며, 이것은 위 AIMD 방식에 설명된 것과 같은 것이다. 본 명세서에서 설명된 다른 실시예에도 주목되듯이, 알파의 낮은 임계점은 알파가 그 이하로는 가지 않을 저점(below)으로 설정될 수 있다.

단방향 큐 지연 측정(One-way queueing delay measurement)

지연 기반 계획에서, 지연 측정은 왕복 지연(RTT)에 기초하여 이루어진다. 이것은 큐 지연 및 혼잡 제어 수정 측정의 적용과 연관되는 전방 경로(forward path) 및 역방향 경로(backward path) 양자로부터의 지연을 초래한다. RTT 지연이 높으면, 혼잡이 추정되고 패킷율은 감소된다. 이것은 소정의 경우에 바람직하지 않을 수 있다. 예를 들면, 전방 경로가 혼잡하지 않고 회귀 경로(return path)가 혼잡하다면, RTT 지연은 혼잡을 제한할 것이고 감소시킬 필요가 없는데도 불구하고 전방 경로는 감소될 것이다. 전방 경로와 역경로(reverse path)는 각 각의 지연이 대칭적이 아닐 수 있으므로 역경로 혼잡은 무시하는 것이 적당할 것이다. 본 발명은 평형상태에 이르기 위해 혼잡 윈도우 크기를 변화하는데 전방 경로만 사용되도록 역방향 큐 지연을 측정하고 차감하는 방법을 제공한다.

역방향 경로의 혼잡에 대해 영향을 받지 않기 위해, 본 발명의 실시예는 역방향 경로 지연을 측정하고, 전방 큐 지연을 얻기 위한 RTT 측정으로부터 그것을 빼는 기술을 포함하는데, 이는 그 다음에 윈도우 크기를 결정하는데 사용된다. 한 실시예에서, 패킷이 송신될 때 송신기 TCP 엔진에 있는, 그리고 패킷이 수신될 때 수신기 TCP 엔진에 있는 패킷에 타임스탬프(timestamp)가 찍힌다. 이 타임스탬프의 차이가 전방 경로 지연을 대표한다. 송신기와 수신기 클록(receiver clock)이 동조화(synchronized)되어 있지 않고 타임스탬프를 생성할 때 클록 구간(clock period)이 다를 수 있어 어려움이 생긴다.

역방향 큐 지연 측정(Backward Queueing delay Measurement)

역방향 큐 지연(BQD) 측정 알고리즘은 송신기가 p₁의 클록 구간, 수신기가 p₂의 클록 구간을 갖고 p₁Dp₂인 것을 필요로 한다. p₂ 클록은 수신기의 RFC1323 타임스탬프 구간에 의해 고정되며, 송신기 구간 p₁은 시간 측정을 위한 송신기의 능력에 의하여만 제한 받는다. 다음 알고리즘은 한 소스 클록 구간 p₁내까지 BQD 측정 방법을 제공한다. 정확한 측정이 1/p₂ 비율로 이루어진다. 알고리즘이 양쪽 종단-호스트(end-host) 클록에 비동기화(desynchronized)를 허용하는 동안, 그 페이즈(phase)는 정확한 측정을 위해 안정적이어야만 한다. 일 실시예에서 p₂는 알고 있는 것으로 추정하고, 다른 실시예에서는 p₂를 추정하는 방법을 제시한다.

알려진 수신기 클록 주기(Receiver Clock Period Known)

도 4는 수신기 클록 주기를 알고 있을 때 BQD 계산을 위한 실시예를 설명한 흐름도다. 스텝 (401)에서 수신기 클록 주기 p₂가 결정된다. 스텝 (402)에서 샘플 ACKS는 수신기 클록이 변화한 후에 취해진다. BQD의 과대추정 및 과소추정은 스텝 (403)에서 계산된다. 스텝 (404)에서 BQD는 스텝 (403)에서 생성된 과대추정 및 과소추정을 사용하여 결정된다. 스텝 (405)에서 BQD는 전방 큐 지연 FQD를 생성하기 위해 총 큐 지연으로부터 차감된다. 스텝 (406)에서 FQD는 적절한 혼잡 제어 반응을 계산하기 위해 사용된다.

도 5(a)는 아래 설명을 참조하여 수신기 및 송신기 클록 신호의 소정의 타이밍 관계를 설명한다. j^th번째 전송된 패킷의 역방향 경로 지연의 총합은 역방향 전파 지연 d_BPd_BQj 및 역방향 큐 지연 d_BQj의 합이다.

t_0j를 패킷 j의 전송 시간이라 하자. j^th번째 나간 패킷은 목적지 호스트에 시간 t_1j에 수신되고, 수신기는 송신기에게 시간 t_2j에 도달하는 ACK를 즉시 보낸다. k^th번째 수신된 패킷의 긍정응답(acknowledgement)은

의 타임스탬프 값을 갖고,

j^th번째 긍정응답이 도래(arrive)하면 송신기 클록은

의 값을 갖는다.

여기서, e는 두 종단 호스트의 타임스탬프 클록간의 본질적(inherent) 오프셋이다. 패킷 j 및 k 로부터 정보로 두 시간 측정의 차이를 정의하면

가 되고 확장하면

이 된다.

여기서

이다.

우리는 다른 항을 가능한 많이 소거할 수 있도록 적절한 패킷 j와 k를 고른 방정식 (5)를 사용하여 수신기와 송신기 사이의 오프셋과 전파 지연을 추정할 수 있다.

이 정수라 가정하면, k=j일 때, C_Bjk는 동일한 패킷에 속하는 도래(arrival) 시간과 수신기 타임스탬프를 사용하여 계산되며, 식(5)는

로 단순화된다.

수신기 클록(스텝 (402))의 증가 후에 보내진 첫 번째 긍정응답이 되도록 k가 선택된다면 최종 항은 최소화 될 수 있음을 주목하라. k^th번째 패킷의 긍정응답이 도래하는 시간에 모든 C_Bkk 측정 중 최소를

라 하면,

(7)

이다.

정확히

의 하한을 샘플링 하기 위한 조건은, 수신기 클록이 증가하는 시간에 승인이 보내질 때 그리고 역방향 큐 지연이 없고

일때인 것을 주목하라. 그 값은 최소값

에 의해 한계지어 지는데,

이것은 클록 오프셋 및 역방향 전파 지연만 포함한다. 우리가 실제로 C_Bkk의 최소값을 샘플링했다고 가정해 보자. 만일 A_k=A_k-1+1일 때, 수신기 클록이 증가한 후에 첫 번째 패킷이 되도록 k를 선택하면, 식 (6)과 (8)을 써서 BQD의 과대추정(over-estimate)은 구성될 수 있다.

p₁이 작으면,

는 대략

이고,

2번째 항에 의해 생긴 에러는 항상 과대추정을 초래한다.

BQD의 과소추정(스텝 (403))을 얻기 위해, 우리가 기간 A_j에 보내진 최종 긍정응답을 j로, 차기 기간 A_k에 최초 긍정응답을 k로, 즉 k=j+1 및 A_k=A_j+1로, 로, 선택해 보자. 이 경우 식 (5)는,

로 단순화 된다.

최종 긍정응답을 고름으로 해서 최종 두개 항 때문에 생긴 에러를 최소화 한다는 것을 주목하라. 우리는 BQD의 과소추정을

로 쓸 수 있다.

여기서 k=j+1이고 A_k=A_j+1이다. 재차, p₁이 작으면,

는 대략

최종 항에 의해 도입된 에러는 과소추정을 초래한다.

최소값 8이 샘플로 추출되고, 수신기 클록이 증가하기 전 최종 승인과 수신기 클록이 증가한 후 최초 긍정응답의 차이가 작고(t_1j-t_1k→0), 송신기 클록 기간이 작으면(p₁→0), 과소 및 과대추정은 역방향 큐 지연에 접근한다.

단일 BQD 추정은 과소 및 과대추정과 다른 여러 방법으로 계산(스텝 (404))될 수 있다. 일 실시예는 다른 ACK 간격화(spacing)에 내성이 있는 방법이다. 과소 및 과대추정은 ACK의 송신 시간에 따라 변할 수 있다는 것을 주목하라. 수신기 클록이 증가한 후 소정의 시간 동안 ACK가 없다면, 과대추정은 에러를 가질 수 있고, 유사하게 증가 전 최종 ACK가 증가 전에 곧 이루어지지 않으면, 과소추정은 에러를 가질 수 있다. ACK 간격화가 신뢰하기 어려운 환경에서는, 수 개의 과소 및 과대추정의 가장 타이트한 한계(the tightest bound)에 맞는 값을 BQD로 추정할 수 있다. 그 같은 추정 BQD

는

(16)

이다.

수신기 클록 주기 추정 - 단일 주기 샘플(Receiver Clock Period Estimation - Single Period Sample)

본 발명은 수신기 클록 주기의 단일 샘플로부터 p₂를 결정하기 위한 실시예를 포함한다. 이 방법은 BQD 측정을 위해 p₂를 결정하기에는 너무 부정확할 수 있다. 그러나, 이 방법은 p₂의 크기(magnitude)를 결정하는데 이용될 수 있고, 그 다음, 그 주기를 이용하는 모든 운영 체제(operating system)와 호환성이 있는, 알려진 보수적 추정치(conservative estimates) 표에서 추정치를 선택하는데 이용될 수 있다.

도 5(b)의 타이밍도에서 보듯, ACK의 송신 시간이 수신기 클록 증가 전후에 각 각 알려지고(t_1(j-1) 및 t_1j), ACK의 송신 시간이 차기 클록 증가 전후에 각 각 알려지면(t_1(k-1) 및 t_1k) 및 t_1k), 수신기 클록 주기의 상한 및 하한 범위는 계산될 수 있다. 이 실시예에서, 송신기는 ACK 송신 시간을 모르나, j^th번째 패킷의 도래 시간인 t_2j만 알며 여기서 t_2j=t_1j+d_Bj 이다. 따라서, ACK 도래 시간을 클록 주기를 추정하기 위해 사용하면, 큐 지연 또한 주기 한계 추정치(period bound estimates)에 잡음을 더한다. 클록이 증가하는 전후의 ACK 도래를 사용하여, 주기 하한의 추정치를 계산할 수 있다.

그리고 상한의 추정치를 계산할 수 있다.

그러므로 단일 주기의 측정으로부터 수신기 클록에 대한 우리의 지식은 ACK 패킷의 간격화와 각 ACK가 경험하는 큐 지연의 차이 양자에 의해 제한 될 수 있다.

다중 샘플을 평균하는 수신기 클록 주기 추정(Receiver Clock Period Estimation Averaging Multiple Samples)

우리는 다중 주기에 걸쳐 클록 주기 측정을 평균함으로서 단일 샘플 기술의 정확성 이슈를 제기할 수 있다. 주기 추정을 구성하는데 사용되는 평균 연산자(operator)를 정의하면

이다.

여기서 X(j)는 시간 t_2j까지 일련의 모든 샘플인데, 샘플 X_i는 시간 t₂에서 취해지고, N_(s,e)는 주기 s<t_2i<e 내의 샘플 수이다. t₂(j)를 j^th번째 ACK의 도래 시간에 모든 ACK 도래 시간의 세트라 하고, A(j)를 t₂(j)에서 각 ACK 도래에 연관된 모든 수신기 타임스탬프의 세트라 하자.

수신기 주기를 추정이 가능한 한 가지 방법은 접속 시작에서부터와 가장 최근 패킷의 시간을 두 구역(region)으로 나누고, 그리고 이 두 지역간에 수신기 클록의 평균 증가에 상대적인 송신기 클록의 평균 증가를 계산한다.

라면, 식(18)을, p₂ 더하기 ACK 전송 간 시간(inter-transmission time)으로 인한 에러항 및 p₂ 더하기 큐 지연에서 변화로 인한 에러항으로 분리할 수 있다.

여기서

그리고

최대 역방향 큐 지연이 d_BQmax라면, 식(22)과 식(23)에서 분자는 p₂와 d_BQmax 각 각에 의해 한계 짓게 된다. 따라서

와 같다. 이것은 ACK 전송 시간 분포나 큐 지연 변화와 관계없이

는 결국 p₂로 수렴된다는 것을 의미한다.

유한 추정 주기에 걸쳐, 주기추정에서 최악의 에러 경우를 고려해 보자. 주기 추정의 상한 및 하한 범위는 계산될 수 있다.

가 최대인 최대 큐 크기 구역이

인 최소 큐 크기 구역으로 이어질 때 가장 큰 양의 주기 에러가 일어난다. 주기 추정 상한은

인 최소 큐 크기 구역이

가 최대인 최대 큐 크기 구역으로 이어질 때 가장 큰 음의 주기 에러가 일어난다. 주기 추정 하한은

r(s1,e1,s2,e2)항에 따른 추정 에러는 수신기 클록 증가 후 최초 패킷만을 선택하여 샘플 A(j)의 세트 및 t₂(j)가 A_j=A_j-1+1 과 같은 패킷만 포함하도록 함으로써 줄여질 수 있다. e(s1,e1,s2,e2)항에 따른 추정 에러 또한 두 구역간의 큐 지연 차이에 관한 정보가 이용가능하다면 줄여질 수 있다.

BQD 감지가 있는 지연 기반 TCP(Delay Based TCP with BQD detection)

한 번 BQD가 결정되면, 그 것은 지연 기반 TCP 알고리즘으로 합체될 수 있다. qdelay > 0이고

인 경우 지연 기반 TCP 윈도우 제어 법칙을 기억해 보면

평형상태에서 식(26)은

이 된다.

이것은 평형상태 소스율이, α 그리고 전방 및 역방향 큐, 양자에 의존한다는 것을 제시한다.

우리는 baseRTT¹ = baseRTT+D_BQ와 같이 BQD 추정을 baseRTT 추정에 합산함으로서 BQD 측정과 지연 기반 TCP 제어 법칙을 통합했다. baseRTT 대신 baseRTT를 사용함으로써 이 평형상태 속성(property)이 변할 것이고, 소스율은 더 이상 역방향 큐에 종속되지 않고

그러므로, 전방 큐 지연만이 혼잡 제어를 위한 윈도우와 알파 조정을 결정하는데 사용된다.

Claims (23)

1. 망(network)의 혼잡 제어(congestion control)를 위한 방법에 있어서,

   최소 큐 지연(minimum queueing delay) q₀를 결정하는 단계,

   최소 큐 지연 q₀를 포함하는 평형상태(equilibrium) 조건을 정의하는 단계,

   평형상태 조건을 만족시키는 α값을 선택하는 단계

   를 포함하는 방법.
2. 제 1 항에 있어서,

   상기 망이 TCP 망인 방법.
3. 제 2 항에 있어서,

   혼잡 제어가 지연 기반(delay based) TCP 혼잡 제어 방식(scheme)인 방법.
4. 제 1 항에 있어서,

   q=q₀+Nα/c에서, N은 망 트래픽 흐름(traffic flows)의 수, q는 망 지연, 그 리고 c는 망 용량인 방법.
5. 망 혼잡 제어를 위한 방법에 있어서,

   망 패킷 손실(packet loss)을 탐지하는 단계,

   패킷 손실이 임계점(threshold)을 초과하는지 결정하는 단계,

   패킷 손실이 임계점을 초과하지 않았을 때 α값을 증가하는 단계,

   패킷 손실이 임계점을 초과했을 때 α값을 감소하는 단계

   를 포함하는 방법.
6. 제 5 항에 있어서,

   α값이 가산적으로(additively) 증가되고 승산적으로(multiplicatively) 감소되는 방법.
7. 제 5 항에 있어서,

   임계값(threshold value)이 혼잡 손실을 대표하는 방법.
8. 제 5 항에 있어서,

   임계값이 8이상인 방법.
9. 망 혼잡 제어를 위한 방법에 있어서,

   망 처리량(throughput)을 결정하는 단계,

   현재 α값이 그 처리량과 연관되는지 결정하는 단계,

   현재 α값이 처리량과 상응하지 않을 때 α값을 증분하는(incrementing) 단계

   를 포함하는 방법.
10. 제 9 항에 있어서,

    가능한 α값의 복수성(plurality)으로부터 α값을 무작위로(randomly) 할당하는 단계를 포함하는 방법.
11. 제 10 항에 있어서,

    α값을 무작위로 할당하는 단계가 미리 결정된 시간 주기 후에 발생하는 방 법.
12. 망 혼잡 제어를 위한 방법에 있어서,

    망에서 보내진 메시지의 전방 큐 지연(Forward Queueing Delay, FQD)을 결정하는 단계,

    FQD를 사용하여 망 큐 지연을 조정하는 단계

    를 포함하는 방법.
13. 제 12 항에 있어서 전방 지연을 결정하는 단계가,

    왕복 시간(Round-Trip Time, RTT) 지연을 결정하는 단계,

    역방향 큐 지연(Backward Queueing Delay, BQD)을 결정하는 단계,

    FQD를 결정하기 위해 RTT 지연서 BQD를 차감하는 단계를 포함하는 방법.
14. 제 13 항에 있어서 BQD를 결정하는 단계가,

    수신기 클록 주기(receiver clock period) p₂를 결정하는 단계,

    수신기 클록의 변화 후에 샘플링을 승인(sampling acknowledgements, ACKs) 하는 단계,

    p₂ 및 ACKs에 기초하여 BQD를 계산하는 단계를 포함하는 방법.
15. 망 혼잡 제어를 위해,

    유틸리티 함수 u(x) 및 데이터 흐름의 수 N을 포함한 잔량(backlog) 평형상태 조건을 정의하는 단계,

    N이 증가함에 따라 잔량이 낮은 비율로 증가하도록 u(x)를 정의하는 단계를 포함하는 방법.
16. 제 15 항에 있어서,

    u(x)가 조정 가능한(tunable) 상수 β에 의해 수정되는 방법.
17. 제 16 항에 있어서,

    

    , 여기서

    

    는 피크율(peak rate)인 방법.
18. 제 17 항에 있어서,

    최소 큐 지연 q₀가 포함되어

    

    인 방법.
19. 망 혼잡 제어를 위해,

    평형상태 손실 확률(equilibrium loss probability) p 를 계산하는 단계,

    평형상태 큐 지연(equilibrium queueing delay) q 를 계산하는 단계,

    미리 결정된 목표값(target value)으로 p 와 q 함수를 맞추는 단계를 포함한 방법.
20. 제 19 항에 있어서 p 를 계산하는 단계에서,

    구간(interval) S에서 손실된 패킷의 수를 S 동안에 송신된 패킷 수의 총합으로 나누는 단계를 포함한 방법.
21. 제 19 항에 있어서 p 와 q 함수를 같게 맞추는 단계가,

    α 값을 갱신하여 K 값으로 q/p 비율을 맞춤으로서 실행되는 방법.
22. 제 21 항에 있어서 α 값을 갱신하는 단계가,

    p_t 및 q_t 를 계산함으로서,

    λ_t 값 =q_t/p_t/K 를 생성함으로서,

    

    를 계산함으로서,

    새로운 α_t 값 =η_t ^*α0 을 생성함으로서 실행되는 방법.
23. 망 라우트(route) 변화를 감지하는데 있어,

    하나의 값을 △α 만큼 증분하는 단계,

    그 하나의 값을 증분한 후 왕복 시간 변화(△RTT)를 결정하는 단계,

    그 △RTT/△α 가 0에 가까울 때 발생하는 라우트 변화를 정의하는 단계를 포함한 방법.

Images