KR100817798B1

KR100817798B1 - 인터넷 제어 메시지 프로토콜의 타임스탬프 기능을 이용한네트워크 링크 가용 대역폭 추정 방법

Info

Publication number: KR100817798B1
Application number: KR1020060102378A
Authority: KR
Inventors: 정태인; 차명석; 김형종; 심원태; 김우한
Original assignee: 한국정보보호진흥원
Priority date: 2006-10-20
Filing date: 2006-10-20
Publication date: 2008-03-31
Also published as: US20080095187A1

Abstract

본 발명은 인터넷 제어 메시지 프로토콜(ICMP)의 타임스탬프 기능을 이용하여 작은 크기의 탐사 패킷을 발송하고, 돌아온 탐사 패킷의 시간 정보를 사용하여, 네트워크 링크의 가용 대역폭을 추정하는 방법에 관한 것이다.

본 발명에 의하면, 라우터에 별도의 프로그램이나 기능을 활성화하지 아니하더라도, 운용 중인 네트워크와 연결된 외부 네트워크 링크의 가용 대역폭을 용이하게 추정하여 모니터링할 수 있다. 따라서, 보다 안정적으로 네트워크를 운용할 수 있고, 네트워크의 이상 징후를 조기에 탐지하여 신속하게 대응할 수 있다. 또한, 네트워크에 과도한 트래픽이나 부하가 유발되는 것을 방지할 수 있다.

Description

인터넷 제어 메시지 프로토콜의 타임스탬프 기능을 이용한 네트워크 링크 가용 대역폭 추정 방법 {A method for estimating available bandwidth of network link using time stamp function of Internet Control Message Protocol}

도 1은 본 발명에 따른 네트워크 가용 대역폭 추정 방법이 적용되는 네트워크 구조를 설명하기 위한 개념도.

도 2는 본 발명에 따른 네트워크 가용 대역폭 추정 방법에 사용되는 k개의 탐사 패킷 및 제로 큐 지연을 가지는 패킷의 수 N(k)를 설명하기 위한 도면.

도 3은 본 발명에서 3개의 패킷을 이용하여 링크의 가용 대역폭을 추정하는 방법을 설명하기 위한 도면.

도 4는 본 발명에 따라 다중 노드 사이의 가용 대역폭을 추정하는 방법을 설명하기 위한 도면.

도 5는 본 발명에 따른 네트워크 링크의 가용 대역폭 추정 과정을 나타낸 순서도.

본 발명은 인터넷 제어 메시지 프로토콜(ICMP, Internet Control Message Protocol)의 타임스탬프 기능을 이용하여 네트워크 링크의 가용 대역폭을 추정하는 방법에 관한 것이다.

인터넷의 발달로 인하여 네트워크의 용량 및 크기는 크게 증가하였으며, 데이터 전송의 핵심적인 역할을 수행하는 라우터도 다양한 기종과 성능의 제품들이 설치되어 운용되고 있다. 이러한 네트워크 기반구조(infrastructure)의 발전과 동시에 이를 안정적으로 운용하기 위한 기술들도 발전하였다.

이러한 네트워크를 안정적으로 운용하기 위해서는 링크 사이에서 가용 대역폭(available bandwidth)을 측정하고, 이를 지속적으로 모니터링하여, 적정한 가용 대역폭을 유지하는 것이 중요하다. 상기 가용 대역폭은 물리적인 사고로 인한 회선 장애, 트래픽 급증으로 인한 네트워크 혼잡, 및 DDoS(분산 서비스 거부, Distribute Denial of Service) 공격 등에 의해서 영향을 많이 받게 된다.

따라서, 가용 대역폭을 측정함으로써 네트워크의 이상 징후를 탐지할 수 있다. 최근의 바이러스 및 웜 등은 자기 전파를 위하여 취약점이 있는 대상을 스캐닝하며, 이러한 스캐닝을 위하여 과도한 트래픽을 발생시키는 경우가 많다. 따라서, 과도한 트래픽을 조기에 탐지하면 네트워크의 안정적인 운용이 가능할 뿐만 아니라, 바이러스 및 웜의 전파를 초기에 방지할 수 있다. 또한, 악성 봇(Bot) 등을 이용한 DoS(서비스 거부, Denial of Service) 공격의 경우, 공격 대상이 속하여 있는 네트워크 뿐만 아니라 경유지에 해당하는 다른 네트워크에도 과도한 트래픽을 유발한다. 따라서, 네트워크를 관리하는 관리자가 자신의 네트워크와 연동된 네트 워크의 주요 링크를 모니터링함으로써, DoS 공격을 탐지할 수 있다.

가용 대역폭을 지속적으로 모니터링하기 위해서는 네트워크의 핵심 장비인 라우터에 이러한 가용 대역폭 모니터링 기능을 추가하고, 이 기능을 활성화하여야 한다. 또한, 네트워크의 가용 대역폭을 계산하려면, 대상 네트워크 노드에 해당 기능을 가지는 프로그램을 추가로 설치하여 작동시키거나, 이미 보유하고 있는 기능을 작동시켜야 한다.

그러나, 자신이 운용하는 네트워크와 연동된 네트워크의 주요 링크를 모니터링하기 위해서 새로운 프로그램을 설치하는 경우, 많은 시간과 비용이 소요된다. 또한, 라우터에 네트워크 대역폭을 모니터링하는 기능을 활성화하는 경우, 라우터에 상당한 부하(load)가 유발된다. 또한, 보안 상 문제가 발생할 수도 있기 때문에 가용 대역폭 정보는 대부분 외부에 공개되지 않는 실정이다. 따라서, 라우터에 네트워크 대역폭을 모니터링하는 기능을 활성화하더라도, 다른 네트워크의 가용 대역폭 정보를 얻을 수 없다.

실제 대상 노드가 아닌 원격 노드에서 가용 대역폭을 계산하는 기술로서, ICMP 에코 패킷을 발송하고, 이의 라운드 트립 시간(round trip time)을 측정하여 네트워크의 특정 링크간의 지연(delay) 시간을 계산하는 핑(ping) 기술이 알려져 있다. 그러나, 이 기술은 패킷이 대상 노드까지 전달되는 포워드 경로와 되돌아오는 리턴 경로가 서로 상이한 경우 정확성이 떨어진다.

본 발명은 상기한 바와 같은 문제를 해결하기 위하여 안출된 것으로서, 본 발명에서는 인터넷 제어 메시지 프로토콜(ICMP)의 타임스탬프 기능을 이용하여 작은 크기의 탐사 패킷을 발송하고, 돌아온 탐사 패킷의 시간 정보를 사용하여, 네트워크 링크의 가용 대역폭을 추정한다.

따라서, 본 발명의 목적은 ICMP의 타임스탬프 기능을 이용하여 네트워크 링크의 가용 대역폭을 추정하는 방법을 제공하기 위한 것이다.

본 발명은 ICMP의 타임스탬프 기능을 이용하여 네트워크 링크의 가용 대역폭을 추정하는 방법에 관한 것이다. 본 발명에 따른 가용 대역폭 추정 방법은, 상기 가용 대역폭을 추정하고자 하는 네트워크 링크의 뒷 노드인 노드 b에 첫 번째 패킷(패킷 1)을 전송하는 단계(a); 상기 네트워크 링크의 앞 노드인 노드 a에 두 번째 패킷(패킷 2) 및 세 번째 패킷(패킷 3)을 전송하는 단계(b); 및 상기 전송한 패킷 1 내지 3에 기록된 타임스탬프의 시간 정보로부터 상기 네트워크 링크의 가용 대역폭을 계산하는 단계(c)를 포함한다.

이하에서는, 도면을 참조하여 본 발명에 따른 침입 탐지 시스템 및 방법의 실시예를 구체적으로 설명한다. 그러나, 본 발명이 하기 실시예에 의하여 제한되는 것은 아니다.

본 발명에서 가용 대역폭은 네트워크의 특정 링크에서 전체 대역폭 중 현재 이용 가능한 대역폭을 의미한다. 상기 가용 대역폭은 노드의 대역폭에 대한 비율(가용 대역폭 비율)로 표현될 수도 있다. 일반적으로, 네트워크 장비인 라우터는 자신이 속한 링크의 전체 대역폭을 알고 있으며, 자신이 처리하는 트래픽의 통계를 알 수 있다. 따라서, 상기 두 가지 정보를 사용하여 쉽게 가용 대역폭을 계산할 수 있다. 하기 수학식 1은 가용 대역폭, 부하 및 대역폭의 관계를 나타낸다:

[수학식 1]

a=c(1-ρ)

상기식에서,

a: 가용 대역폭 [bit/sec]

c: 노드의 대역폭 [bit/sec]

ρ : 노드의 부하(load)

상기 수학식 1에 의하면, 가용 대역폭은 노드에 가해지는 부하에 따라 0에서 대역폭 c까지의 값을 가지게 된다.

도 1은 본 발명에 따른 네트워크 가용 대역폭 추정 방법이 적용되는 네트워크 구조를 설명하기 위한 개념도이다.

종래 라우터의 가용 대역폭 모니터링 기능을 이용하는 경우에는, 자신이 관 리하는 네트워크에 속해 있는 링크만을 모니터링할 수 있다. 따라서, 자신의 네트워크와 연동된 다른 네트워크(ISP(인터넷 서비스 제공자, Internet Service Provider) #A, #B 및 #C)의 특정 링크(도 1에서 ?로 표시한 부분)의 가용 대역폭을 측정하는 것은 불가능하다.

그러나, 본 발명에서는 라우터의 가용 대역폭 정보를 사용하지 아니하며, 대신 원격에서 ICMP의 타임스탬프 정보를 사용한다. 즉, 본 발명에서는 ICMP 탐사 패킷을 발송하고, 가용 대역폭을 알고자 하는 링크의 양 끝단의 라우터가 이 패킷에 반응하면, 이 패킷에 있는 타임스탬프 정보를 활용하여 가용 대역폭을 추정한다. 따라서, 직접 접속하고 있지 아니한 다른 네트워크의 링크이더라도, 상기 링크의 양 끝단의 라우터가 ICMP 패킷에 반응하여 타임스탬프 기능을 지원하면, 가용 대역폭을 추정하는 것이 가능하다.

상기 ICMP 타임스탬프 기능은 특정 노드에서 패킷을 수신하여 처리한 후, 다음 노드로 전달할 때, 패킷 헤더에 시간 정보를 기록할 수 있는 기능이다.

하기 수학식 2는 ICMP의 타임스탬프 정보로부터 어떠한 방법으로 가용 대역폭을 구할 수 있는지를 설명하는 식이다(여기에서, 라우터는 출력이 큐를 통해서 처리되는 아웃풋-큐 스위치(output-queued switch) 모델인 것으로 가정하였다):

[수학식 2]

상기식에서,

k: 패킷 수,

N(k): k개의 탐사 패킷 중에서 제로 큐 지연을 가지는 패킷 수.

즉, k개의 탐사 패킷을 보낸 후에, 제로 큐 지연을 가지는 패킷의 수 N(k)를 측정하면, 상기 수학식 2를 이용하여 가용 대역폭을 구할 수 있다.

도 2는 상기 k개의 탐사 패킷과 제로 큐 지연을 가지는 패킷의 수 N(k)를 설명하기 위한 도면이다. 가용 대역폭을 구하고자 하는 대상 링크의 양 끝 노드를 각각 a 및 b라고 가정한다. 노드 a에서 큐 지연을 가지지 않는 패킷의 수를 알면, 상기 수학식 2를 이용하여 노드 a의 로드 ρ를 추정할 수 있고, 이를 통하여 상기 노드 a에서 노드 b까지의 가용 대역폭을 계산할 수 있다.

여기에서, 패킷의 지연 여부를 확인할 수 있도록 패킷의 정확한 타임스탬프 값을 얻으려면, 탐사 패킷 사이에 크로스 트래픽이 끼어들지 않도록 하여야 한다. 본 발명에서는 크로스 트래픽이 발생하지 않도록, 3개의 탐사 패킷을 사용한다.

우선, 본 발명에 따라 가용 대역폭을 추정하기 위해서는 다음의 2가지 조건이 만족되어야 한다:

(i) 대상 링크의 양 끝 노드의 라우터가 모두 ICMP 타임스탬프 패킷에 반응하여야 하고;

(ii) 3개의 탐사 패킷을 보내는 동안, 대상 링크까지의 경로(route)가 동일해야 한다.

도 3은 3개의 패킷을 이용하여 링크의 가용 대역폭을 추정하는 방법을 설명하기 위한 도면이다.

가용 대역폭을 구하고자 하는 대상 링크의 양 끝 노드를 i 및 j라고 가정한다. 본 발명에서는 탐사 노드에서 3개의 ICMP 패킷을 발송하는데, 첫 번째 패킷은 노드 j로 발송하고, 두 번째 및 세 번째 패킷은 노드 i로 발송한다. 여기에서, 상기 3개의 패킷 사이에 다른 패킷들이 들어오게 되면 가용 대역폭 추정의 정확도가 떨어지게 된다. 따라서, 본 발명에서는 다음과 같은 명제 1을 이용하여, 탐사 기간 중에 3개의 패킷 사이에 크로스 트래픽(cross traffic)이 들어오지 못하도록 한다.

[명제 1]

노드 n+1에는 패킷 k를 보내고, 노드 n에는 패킷 k+1 및 k+2를 보낸다. 상기 세 개의 패킷을 연속(back-to-back)으로 노드 0에서 보낸다. 이 때, 하기 수학식 3의 조건이 만족되면 노드 j까지(j≤n) 패킷 k와 k+1 사이, 및 패킷 k+1과 k+2 사이에 크로스 트래픽이 발생하지 않는다:

[수학식 3]

상기식에서,

L_k: 패킷 k의 크기 [byte]

max(.) : 함수 (.)의 최대값

C_m: 노드 m의 대역폭 [byte/sec]

상기 수학식 3의 부등식이 만족되는 경우, 하기 수학식 4의 등식이 성립한다:

[수학식 4]

상기식에서,

D_0,i(k): 패킷 k가 노드 0에서 노드 i까지 전달시에 가지는 지연 [sec]

즉, 패킷 k와 패킷 k+1의 크기 비율이 노드 m과 노드 m-1의 대역폭 비율의 2배보다 큰 경우(수학식 3을 만족하는 경우), 크로스 트래픽이 없게 된다(수학식 4의 등식 성립). 예를 들어, 노드 m의 대역폭이 100Mbps이고, 노드 m-1의 대역폭이 10Mbps인 환경에서, 패킷 k의 크기를 1500바이트, 패킷 k+1의 크기를 40바이트로 설정하면, 상기 수학식 3의 부등식이 하기 수학식 5와 같이 성립된다:

[수학식 5]

따라서, 3개의 패킷을 연속으로 발송하고, 첫 번째 패킷의 크기를 매우 크게 하고(통상적으로 허용 가능한 최대 패킷 크기인 1500 바이트), 두 번째와 세 번째 패킷의 크기는 매우 작게 하여(통상적으로 허용 가능한 최소 패킷 크기인 40바이트) 수학식 3을 만족하면, 테스트 패킷 사이에 크로스 트래픽이 들어오지 않게 된다. 이와 같이 패킷 크기를 설정하는 경우, 상기 수학식 3의 좌변값은 37.5가 되므로, 우변의 대역폭 비 C_m/C_m-1 값이 18.75 미만의 값을 갖는다면 상기 수학식 3의 부등식을 만족하게 된다.

즉, 상기 수학식 3에서 노드의 구체적인 대역폭 값을 알지 못하더라도, 가용 대역폭을 추정하려는 노드가 직전의 노드에 비하여 18배 이하의 대역폭을 가진다면, 전술한 바와 같이 첫 번째 패킷의 크기를 1500 바이트로 설정하고, 두 번째와 세 번째 패킷의 크기는 각 40바이트로 설정하는 경우, 테스트 패킷 사이에 크로스 트래픽이 들어오지 않을 것이다. 네트워크는 병목현상이 생기지 않도록 계층적인 구조로 구성되어 있기 때문에, 일반적으로 상기 가정은 타당하다.

마찬가지 이유로, 네트워크 링크 사이의 대역폭 값이 크게 다르지 않기 때문에, 첫 번째 패킷의 크기를 두 번째 및 세 번째 패킷의 크기보다 약 8배 이상(바람직하게는 약 20배 이상) 크게 설정한다면, 상기 패킷 크기의 관계가 상기 수학식 3을 만족하여, 테스크 패킷 사이에 크로스 트래픽이 들어오지 않을 것이다.

보다 정확한 결과 값을 얻기 위해서는, 탐사 패킷 발송을 여러 차례 반복하 고, 이 결과 값을 이용하여 가용 대역폭을 확률적으로 표현하는 것이 바람직하다.

하기 수학식 6은 노드 i까지 패킷 2와 패킷 1에 의한 지연의 차 및 패킷 3과 패킷 2에 의한 지연의 차를 각각 의미하는 I_i(1,2) 및 I_i(2,3)를 나타내는 식이다:

[수학식 6]

또한, 본 발명에서는 3개의 패킷 k, k+1 및 k+2 사이에 각각 크로스 트래픽이 없고, 패킷 k의 도착 시간에서부터 패킷 k+2의 도착시간까지 해당 큐는 비어있지 않는다고 가정한다. 이 경우에 하기 수학식 7이 성립한다:

[수학식 7]

또한, 다음의 수학식 8도 역시 성립한다:

[수학식 8]

즉, 노드 i에서의 k+1번째 및 k번째 패킷에 의한 지연의 차이와 k+2번째 및 k+1번째 패킷에 의한 지연의 차이가 거의 근사하다는 것을 알 수 있다. 또한, 이것은 노드 i+1에서도 성립한다.

한편,

는 상기 수학식 6 내지 8에 의하여

로 쓸 수 있다. 또한,

이라고 가정하면, 패킷 1에 의하여 노드 0으로부터 노드 i까지의 추정된 지연 값을 하기 수학식 9와 같이 유도할 수 있다:

[수학식 9]

상기식에서,

: 패킷 k가 노드 0에서 노드 i까지 전달시에 가지는 지연의 추정값 [msec]

또한, 상기 수학식 9를 이용하여 노드 i로부터 노드 j까지의 추정된 지연을 하기 수학식 10과 같이 유도할 수 있다:

[수학식 10]

여기서

는

의 추정값으로서 적당하지만, 오류항 v_i만큼의 차이를 가지게 된다. 상기 오류항을 v_i = I_i(1,2) - I_i(2,3)라 정의하고, fv_i는 v_i의 확률 밀도 함수(probability density function)라고 정의한다. 상기 확률 밀도 함수는 상기 테스트 탐사 패킷을 수회 반복하여 전송함으로써 얻은 데이터로부터 구할 수 있다.

I_i(1,2)와 I_i(2,3)이 서로 독립적이고, 각각 구간 [δ1, δ2](단, δ1 < δ2)의 범위 내에서 유한하다고 가정한다. 그러면, 하기 수학식 11과 같이 fv_i(x)가 x = 0에 대하여 대칭이라는 것을 보일 수 있다:

[수학식 11]

또한,

인 경우, fv_i(x)=0이다.

이고,

로 정의한다. 여기에서,

는 v_i와 독립적이라고 가정하면,

에 대하여,

의 분포는 하기 수학식 12와 같이 표현된다:

[수학식 12]

δ의 크기는 지연

에 비하여 매우 작고,

의 누적 확률 분포(cumulative probability distribution)는

에 대하여 하기 수학식 13과 같은 선형 특성을 보이는 것으로 가정하였다:

[수학식 13]

수학식 12 및 13에 의하여

에 대하여 다음의 수학식 14를 얻는다:

[수학식 14]

수학식 13으로부터 도착한 탐사 패킷이 제로 큐 지연의 확률

로 비어있는 큐 시스템(노드)에 도달할 확률은 하기 수학식 15와 같이 표현된다:

[수학식 15]

와

인 두 가지 경우를 고려하면 다음의 수학식 16을 얻는다:

[수학식 16]

수학식 15 및 16을 합치면 다음의 수학식 17을 얻는다:

[수학식 17]

따라서, 상기 수학식 17로부터, 노드 i와 j사이에서 패킷 1이 가지는 지연(D_i,j(1))이 최소 지연(

)보다 작을 확률(

)은 노드 i와 j사이에서 패킷 1이 가지는 추정된 지연(

)을 이용하여 계산하여도 근사한 결과를 얻을 수 있음을 알 수 있다.

여기에서,

는 노드 i에서의 첫 번째 패킷이 큐 지연을 가지지 않을 확률을 의미한다. 즉, 이 값이 1이면 첫 번째 패킷이 노드 i에서 큐 지연을 가지지 않을 확률이 100%이므로, 노드 i의 부하가 0을 의미한다. 한편, 이 값이 0.3이면, 노드 i에서 큐 지연을 가지지 않을 확률이 30%이므로, 노드 i의 부하가 0.7이라는 것을 의미한다. 즉, 큐 지연이 있으면 이는 해당 노드에 부하가 있어서 대역폭을 사용하고 있는 것이며, 큐 지연이 없으면 이는 해당 노드에 부하가 없는 것을 의미한다.

한편,

이면, 하기 수학식 18의 부등식이 성립한다:

[수학식 18]

상기식에서, Ω는 ICMP 타임스탬프에서 제공하는 가장 작은 시간 단위(예를 들어, 1msec)이다.

즉,

의 분포는

의 확률 분포에 의해서 상한과 하한이 정해진다.

한편

의 확률은 하기 수학식 19로 표현 가능하다.

[수학식 19]

이 때,

이고, n≥1인 경우에

이 선형이라는 가정에 의하여,

가 성립한다.

의 크기는 지연

에 비하여 매우 작고,

의 누적 확률 분포(cumulative probability distribution)는

에 대하여 수학식 13의

과 같은 선형 특성을 보이는 것으로 가정하였기 때문에,

이 성립한다. 즉, 1차 함수의 경우, x축인 Ω의 증가에 따른 y의 증가분은 일정하다.

상기 식들로부터 하기 수학식 20을 얻는다:

[수학식 20]

또한, 위 식들에 의하여,

가 된다. 따라서,

은 다음 수학식 21로 정의된다:

[수학식 21]

최종적으로 상기 수학식 21을 이용하여, 가용 대역폭 비율을 추정할 수 있다. 상세한 추정 과정은 후술한다.

가용 대역폭을 알고자 하는 링크가 단일 노드가 아닌 다중 노드인 경우에도 유사한 방식으로 링크간의 총 가용 대역폭 총량을 추정할 수 있다.

도 4는 다중 노드 사이의 가용 대역폭을 추정하는 방법을 설명하기 위한 도면이다. 도 4에서 가용 대역폭을 알고자 하는 대상 링크 중에서 ICMP 패킷에 응답하는 양 끝 노드를 노드 a 및 b라고 정의할 때, 단일 노드인 경우와 동일한 방식을 이용하여 노드 a에서 노드 b까지의 총 가용 대역폭을 추정할 수 있다. 하기 수학식 22는 상기 도 4에서 노드 a와 노드 b 사이의 총 가용 대역폭을 나타낸다:

[수학식 22]

도 5는 본 발명에 따른 네트워크 링크의 가용 대역폭 추정 과정을 나타낸 순서도이다.

본 발명에서는 우선 측정하려는 링크의 양 끝 노드(노드 a 및 노드 b)가 ICMP 패킷에 응답하며 타임스탬프 기능을 제공하는지를 확인하다(S10). 상기 단계 S10에서 대상 노드의 타임스탬프 기능 지원 여부 확인을 위해서, 대상 노드에 핑(ping)이란 명령어 사용시에 타임스탬프 정보를 기록하는 옵션을 설정하여 패킷 을 발송한다. 대상 노드에서의 응답 패킷에 타임스탬프 정보가 있다면, 이를 통해서 상기 노드가 타임스탬프 기능을 제공함을 확인할 수 있다.

이후, 노드 a까지의 경로가 일정한지를 확인한다(S20). 상기 단계 S20에서 탐사 기간 중 앞 노드까지의 경로가 동일한지 여부 확인을 위해서는 대상 노드에 tracert란 명령어를 수 회 사용하여 이를 비교하면 된다. 대부분의 ISP에서는 ISP 내부에서의 경로 설정과 상이한 ISP 간의 경로설정을 위해서 BGP라는 라우팅 프로토콜을 사용한다. 이는 정책기반의 라우팅 프로토콜이기 때문에, 대부분 일정한 경로를 유지하며, 경로가 변경되더라도 일정한 시간이 경과한 후에 변경된 경로가 반영된다. 따라서, 본 발명과 같이 3개의 패킷을 짧은 시간에 연속으로 발송하는 경우에는, 대상 노드의 앞 노드까지의 경로가 동일하다고 가정할 수 있다.

상기 두 가지 조건(즉, 노드가 타임스탬프 기능을 제공하고, 노드 a까지의 경로가 일정하다는 조건)은 본 발명이 적용되기 위한 조건이다.

이후, 한 개의 패킷(패킷 1)을 상기 링크의 뒷 노드인 노드 b에 발송하고(S30), 두 개의 패킷(패킷 2, 패킷 3)을 링크의 앞 노드인 노드 a에 발송한다(S40). 상기 3개의 패킷은 연속(back-to-back)으로 발송하여야 한다.

상기 3개의 패킷이 되돌아오면(S50), 상기 패킷들의 타임스탬프 정보를 이용하여 가용 대역폭을 계산한다(S60).

이하에서는, 상기 패킷들의 타임스탬프에 의하여 기록된 시간 정보를 이용하여 가용 대역폭을 추정하는 과정을 설명한다. 본 발명에서는 수신한 패킷의 시간 정보를 활용하여 추정한 지연 값과 최소 지연 값을 계산한다. 이를 수회 반복하여 누적 확률 분포를 만들고, 최종적으로 추정한 지연 값과 최소 지연 값을 비교하여 탐사 패킷의 지연 여부를 판정하며, 이를 통하여 가용 대역폭의 범위를 추정한다.

실제 네트워크 환경에서 ICMP 타임스탬프에서 제공하는 가장 작은 단위를 Ω라 한다. 현재의 네트워크 환경에서 Ω의 값은 통상적으로 1msec이다. 패킷 p에 의한 노드 0에서 i까지의 타임스탬프 기반 지연을

로 정의한다. 여기에서,

는 노드 i에서의 패킷 p의 도착 시간이고,

는 노드 0에서의 패킷 p의 도착시간이다. 이러한 경우, 현재 ICMP 타임스탬프의 제한된 해상도때문에

의 정확한 값을 아는 것은 불가능하다. 대신에, 다음과 같이 타임스탬프의 최소 단위를 이용하여

로 구할 수 있다. 여기에서,

는 타임스탬프의 최소 단위를 이용하여 얻은 지연 값이다. 또한, 수학식 6의 I _i (1,2)와 I _i (2,3)를 위의

를 이용하여, 타임스탬프의 최소 단위를 반영한 I' _i (1,2)와 I' _i (2,3)를 얻는다.

위에서 얻은 I' _i (2,3)와 I' _i (1,2)의 차이(X)를

로 정의한다. 이 때 x가 Ω일 확률 Pr(X=Ω)은 하기 수학식 23과 같이 계산한다:

[수학식 23]

상기식에서, Ω는 타임스탬프에서 제공하는 지연의 최소 단위이다.

한편, x가 0일 확률(즉, 지연의 차이가 없을 확률) Pr(X=0)은 하기 수학식 24와 같다:

[수학식 24]

최소 지연값(

)는 하기 수학식 25와 같다:

[수학식 25]

상기식에서,

a_Ω=Pr(X=Ω)이고,

는 각 패킷에 기록된 타임스탬프로부터 계산하여 측정된 지연 값이다.

따라서, 상기 수학식 23에서 계산된 a_Ω 값 및 측정된 지연 값

를 사용하여, 상기 수학식 25의 부등식을 만족하는 최소 n값을 구하여, 최소 지연 값(

)을 추정한다. 실제로, 상기 추정된 최소 지연 값(

)은 최소 지연 값(

)의 상한이지만, 이 값을 최소 지연값으로 사용하여도 무방하다.

상기 수학식 25에서 추정한 최소 지연 값을 이용하여 가용 대역폭을 추정한다. 가용 대역폭은 하기 수학식 1a와 같이 가용 대역폭 비율로 표현할 수 있다. 본 발명에서는 가용 대역폭 비율을 추정한 후에, 노드의 대역폭을 곱하여 가용 대역폭을 얻는다.

[수학식 1a]

상기식에서,

a: 가용 대역폭 [bit/sec]

c: 노드의 대역폭 [bit/sec]

ρ : 노드의 부하(load)

a/c = 1-ρ : 노드의 가용 대역폭 비율

상기 대역폭 비율(1-ρ)은

과 같고, 이는 수학식 21과 같다:

[수학식 21]

상기식에서, Ω는 ICMP 타임스탬프에서 제공하는 지연의 최소단위이다(본 실시예의 실제 계산에서는 통상적인 네트워크의 환경에 적합한 값인 1msec을 사용한다).

실제 가용 대역을 추정할 때는 관측을 한번만 하는 것이 아니고, 여러 관측 구간을 두어서 반복하여 가용 대역을 추정한다.

수학식 25를 통하여 구한

를 사용하고, 다른 변수들을 다음과 같이 계산하여, 상기 수학식 21의 우항을 계산한다.

먼저, 3개의 탐사 패킷의 타임 스탬프값으로부터 D' ₀ _,j(1), D' ₀ _,i(2), D' ₀ _,i(3)를 얻는다. 그리고 이 값들을 이용하여, 패킷 1이 가지는 노드 i와 j간의 지연(

)을 다음 수학식 26을 사용하여 계산한다:

[수학식 26]

D ^* _i,j를, 측정으로 얻을 수 있는 노드 i와 j사이의 최소 지연이라고 정의하면, p₀, p_Ω, p₂ _Ω는 다음 수학식 27과 같이 정의되고, 측정을 통해서 그 값을 예측할 수 있다:

[수학식 27]

또한, n(n=1,2,3,...)번째 관측 구간에서 관측한 p₀, p_Ω, p_2Ω의 값을 각각 p₀(n), p_Ω(n), p_2Ω(n)라고 정의한다. n(n=1,2,3,...)번째 관측 구간에서의 수학식 21의 우항은 다음 수학식 28을 이용하여 계산한다:

[수학식 28]

여기에서, ξ(n)은 최소 지연의 위상을 나타내는 파라미터로 n=1인 경우, 즉 ξ(1)은 하기 수학식 29의

로 추정된다:

[수학식 29]

여기서 x'은 하기 수학식 30과 같다:

[수학식 30]

또한, C1', C2', C3'은 각각 하기 수학식 31과 같다:

[수학식 31]

한편, n>1인 경우에 ξ(n)의 값은 하기 수학식 32를 이용하여 추정한다:

[수학식 32]

여기에서,

a_Ω(n)는 n번째 관측 구간에서 얻어진 a_Ω의 값을 의미하고,

G_m(x)는 m번째 탐사 기간에 대해서 아래 수학식 33과 같이 정의되며,

G_m(Ω)는 x=Ω일 때 G_m(x)의 값을 의미하고,

x''는 f^m ₁(x), f^m ₂(x) 두 함수의 교차점에서의 지연 값을 의미한다:

[수학식 33]

여기서, f^m ₁(x), f^m ₂(x)는 각각 하기 수학식 34와 같다:

[수학식 34]

또한, s^m ₁, s^m ₂는 각각 하기 수학식 35와 같다:

[수학식 35]

상기 수학식 26 내지 35를 이용하면 수학식 21의 가용 대역폭 비율을 구할 수 있다. 이 때, 상기 노드의 대역폭을 아는 경우에는 상기 가용 대역폭 비율에 상기 대역폭을 곱하여, 상기 노드의 가용 대역폭을 구할 수 있다.

본 발명에 의하면, 라우터에 별도의 프로그램이나 기능을 활성화하지 아니하더라도, 운용 중인 네트워크와 연결된 외부 네트워크 링크의 가용 대역폭을 용이하게 추정하여 모니터링할 수 있다.

따라서, 보다 안정적으로 네트워크를 운용할 수 있고, 네트워크의 이상 징후를 조기에 탐지하여 신속하게 대응할 수 있다. 또한, 네트워크에 과도한 트래픽이나 부하가 유발되는 것을 방지할 수 있다.

Claims

외부 네트워크에 속하여 있는 네트워크 링크의 가용 대역폭을 추정하는 방법으로서,

상기 네트워크 링크의 뒷 노드인 노드 j에 첫 번째 패킷(패킷 1)을 전송하는 단계(a);

상기 네트워크 링크의 앞 노드인 노드 i에 두 번째 패킷(패킷 2) 및 세 번째 패킷(패킷 3)을 전송하는 단계(b); 및

상기 전송한 패킷 1 내지 3에 기록된 타임스탬프의 시간 정보로부터 상기 네트워크 링크의 가용 대역폭을 계산하는 단계(c)를 포함하되,

상기 패킷 1 내지 3의 크기와 노드 i 및 j의 대역폭 사이에는 하기 수학식 3의 관계가 성립하도록, 상기 패킷 1 내지 3의 크기가 설정되는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법:

[수학식 3]

상기식에서,

L_k: 패킷 k의 크기 [byte]

max(.) : 함수 (.)의 최대값

C_m: 노드 m의 대역폭 [byte/sec]
제 1 항에 있어서, 상기 노드 i 및 노드 j는 서로 이웃하여 있거나, 하나 이상의 다른 노드에 의하여 서로 연결되어 있는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법.
제 1 항에 있어서, 상기 노드 i 및 노드 j가 인터넷 제어 메시지 프로토콜의 타임스탬프 기능을 지원하는지 여부를 조사하는 단계를 더 포함하는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법.
제 1 항에 있어서, 복수 개의 패킷을 상기 노드 i까지 전송할 때, 각 패킷이 상기 노드 i까지 전송되는 경로가 서로 동일한지 여부를 판단하는 단계를 더 포함하는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법.
제 1 항에 있어서, 상기 단계 (b) 및 (c)에서 패킷 1 내지 3은 연속적으로 전송되는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법.
삭제
제 1 항에 있어서, 상기 패킷 1의 크기는 상기 패킷 2 또는 패킷 3의 크기에 비하여 8배 이상이 되도록, 상기 패킷 1 내지 3의 크기가 설정되는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법.
제 1 항에 있어서, 상기 패킷 1의 크기는 허용 가능한 최대 패킷 크기가 되도록 설정되고, 패킷 2 또는 패킷 3의 크기는 허용 가능한 최소 패킷 크기가 되도록 설정되는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법.
제 1 항에 있어서, 상기 단계(c)는

상기 단계(a) 및 (b)를 복수회 반복하는 단계(c1);

노드 i에서 패킷 3과 패킷 2의 지연의 차인 I'_i (2,3)과 패킷 2와 패킷 1의 지연의 차인 I'_i (1,2) 차이
가 Ω일 확률 Pr(X=Ω)을 하기 수학식 23으로부터 구하는 단계(c2);

상기 수학식 23에서 계산된 a_Ω 값 및 측정된 지연 값
를 사용하여, 하기 수학식 25의 부등식을 만족하는 최소 n값을 구하여, 최소 지연 값(
)을 추정하는 단계(c3); 및

하기 수학식 21을 이용하여 대역폭 비율(a/c=
)을 구하는 단계(c4)를 포함하는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법:

[수학식 23]

[수학식 25]

[수학식 21]

상기식에서,

Ω는 타임스탬프에서 제공하는 지연의 최소 단위이고,

a_Ω=Pr(X=Ω)이고,

는 각 패킷에 기록된 타임스탬프로부터 계산하여 측정된 지연 값으로서 하기 수학식 26과 같고,

는
로서 상기 오차항 X를 고려한 노드 i 및 j간의 패킷 1에 의한 지연이고,

상기 수학식 21의 우항의 변수들은 하기 수학식 26 내지 35를 사용하여 구한다:

[수학식 26]

여기에서, D' _0,j(1), D' _0,i(2), D' _0,i(3)는 상기 3개의 탐사 패킷의 타임 스탬프로부터 얻은 값이고;

n(n=1,2,3,...)번째 관측 구간에서의 수학식 21의 우항은 하기 수학식 28을 이용하여 계산하고:

[수학식 28]

여기에서, p₀(n), p_Ω(n), p_2Ω(n)은 n(n=1,2,3,...)번째 관측 구간에서 관측한 p₀, p_Ω, p_2Ω의 값으로 정의되고,

p₀, p_Ω, p_2Ω는 다음 수학식 27과 같이 정의되고, 측정을 통해서 그 값을 예측할 수 있으며:

[수학식 27]

는, 측정으로 얻을 수 있는 노드 i와 j사이의 최소 지연이며,

ξ(n)는 최소 지연의 위상을 나타내는 파라미터로서 ξ(1)은 하기 수학식 29의
로 추정되고:

[수학식 29]

여기서 x'은 하기 수학식 30과 같고:

[수학식 30]

C1', C2', C3'은 각각 하기 수학식 31과 같고:

[수학식 31]

n>1인 경우에 ξ(n)의 값은 하기 수학식 32를 이용하여 추정하고:

[수학식 32]

여기에서,

a_Ω(n)는 n번째 관측 구간에서 얻어진 a_Ω의 값을 의미하고,

G_m(x)는 m번째 탐사 기간에 대해서 아래 수학식 33과 같이 정의되며,

G_m(Ω)는 x=Ω일 때 G_m(x)의 값을 의미하고,

x''는 f^m ₁(x), f^m ₂(x) 두 함수의 교차점에서의 지연 값을 의미하며:

[수학식 33]

여기서, f^m ₁(x), f^m ₂(x)는 각각 하기 수학식 34와 같고:

[수학식 34]

또한, s^m ₁, s^m ₂는 각각 하기 수학식 35와 같다:

[수학식 35]
제 9 항에 있어서, 상기 대역폭 비율에 해당 노드의 대역폭을 곱하여 해당 노드의 가용 대역폭을 구하는 단계(c5)를 더 포함하는 것을 특징으로 하는, 네트워크 링크의 가용 대역폭 추정 방법.