KR20040052012A

KR20040052012A - 고속 패킷 망을 위한 패킷 스케줄링 시스템 및 방법

Info

Publication number: KR20040052012A
Application number: KR1020020079730A
Authority: KR
Inventors: 고남석; 곽동용
Original assignee: 한국전자통신연구원
Priority date: 2002-12-13
Filing date: 2002-12-13
Publication date: 2004-06-19
Also published as: US20040114602A1; US7394836B2; JP2004201304A; JP3830937B2

Abstract

본 발명은 비동기 전송 모드(asynchronous transfer mode ; ATM) 또는 인터넷 등과 같은 고속 패킷 교환망에서의 노드의 입력 인터페이스 및 출력 인터페이스에서 동일한 출력 링크로의 전송을 요구하는 여러 세션들간의 공정한 링크 자원 배분을 수행할 수 있는 패킷 스케줄링 시스템 및 방법에 관한 것으로, 상기 패킷 스케줄링 시스템은, 복수 개의 입력 링크들로부터 입력된 트래픽들을 각 세션별로 분류하는 트래픽 분류기; 상기 각 세션에 대한 협약 속도 및 시스템의 가상시간을 관리하는 중앙관리부; 상기 협약 속도 및 상기 시스템 가상시간에 응답해서 상기 트래픽에 대해 패킷별 가상종료시간을 계산하고, 계산된 상기 가상종료시간을 상기 패킷의 헤더에 타임 스탬프로 덧붙이는 가상종료시간 계산부; 상기 가상종료시간 계산부로부터 전달되는 상기 패킷을 세션별로 저장하는 패킷 큐; 및 상기 패킷 큐에 저장된 상기 패킷 중 상기 가상종료시간이 가장 작은 패킷을 선택하여 출력하는 패킷 전송부를 포함한다.

Description

고속 패킷 망을 위한 패킷 스케줄링 시스템 및 방법{Packet scheduling system and method for high-speed packet networks}

본 발명은 패킷 스케줄링 시스템 및 방법에 관한 것으로, 특히 비동기 전송 모드(asynchronous transfer mode ; ATM) 또는 인터넷 등과 같은 고속 패킷 교환망에서의 노드, 즉 ATM 교환기(ATM switch) 또는 라우터(router) 등의 입력 인터페이스 및 출력 인터페이스에서 동일한 출력 링크로의 전송을 요구하는 여러 세션들간의 공정한 링크 자원 배분을 수행할 수 있는 패킷 스케줄링 시스템 및 방법에 관한 것이다.

일반적으로, 패킷 스케줄링 알고리즘은 서버의 동작 모드에 따라 크게 두 가지로 방식으로 구분하는데, 그 중 하나는 큐(queue) 내에 서비스를 대기하는 패킷이 존재하는 한 서버가 계속적으로 서비스를 제공하는 작업보존(work-conserving) 방식이고, 또 다른 하나는 큐 내에 서비스를 받기 위해 대기하는 패킷이 존재하더라도 일정 기준에 부합되지 않으면 서버가 서비스를 제공하지 않고 대기 상태를 유지하는 비 작업보존(non work-conserving) 방식이다. 후자의 방식은 대기하는 패킷이 있음에도 불구하고 서버가 서비스를 제공하지 않으므로, 서버의 이용 효율이 상대적으로 낮은 반면, 사전에 약속된 지연 바운드 또는 지연 지터 한계 등과 같은 성능 요구사항이 정확히 보장될 수 있는 특징을 가진다. 반면, 전자의 방식은 서버의 이용 효율은 높지만, 세션별 최소 성능을 타 세션의 동작과 무관하게 보장해 주어야 하고, 서버의 유휴 자원을 사용하려는 복수의 요청에 대해 세션별 계약 속도 등을 공정하게 분배해 줄 수 있는 메커니즘이 고려되어야 한다.

작업보존 방식 알고리즘의 근간이 되는 이론은, 1993년 6월, Abhay K. Parekh와 Robert G. Gallager에 의해 IEEE/ACM Transactions on Networking, vol. 1, pp. 344-357에 실린 논문, "A generalized processor sharing approach to flow control in integrated services networks: The single node case"에 개시되어 있는 GPS(Generalized Processor Sharing) 알고리즘이 있다. 상기 논문에서는 모든 입력 트래픽을 유체의 흐름으로 모델링하고, 서버가 서비스를 요청하는 모든 연결에 대하여 동시에 서비스를 제공하는 스케줄링 시스템으로 사용되어, 이상적인 공정성(fairness) 및 최적의 지연 바운드(delay bound) 값을 제공한다는 가설적인 이론을 제시하고 있다. 그러나, 실제 패킷망 환경에서는 트래픽의 최소단위가 패킷이고, 특정 순간에 서버는 하나의 패킷만을 전송할 수 있기 때문에, 상기 논문에서 제시하고 있는 시스템을 실제적으로 구현하는 것은 불가능하고, 단지 모든 공정 스케줄링 알고리즘이 지향하는 개념적인 성능 기준만을 제공한다.

상술한 GPS 알고리즘의 개념을 가장 근접하게 실제 망 환경에서 구현한 알고리즘으로는, 인입 트래픽의 기본 단위를 패킷으로 가정한 WFQ (Weighted Fair Queueing) 알고리즘이 있다. WFQ 알고리즘에서는 유체의 흐름으로 모델링 된 트래픽이 마치 동시에 서비스되는 것처럼 GPS 서버의 동작을 모방하여야 하기 때문에, GPS 서버의 동작 상태를 표시하기 위해 가상시간(virtual time) 이라는 개념을 도입한다. 시스템 가상시간은 GPS 시스템 상에서 발생하는 새로운 패킷의 도착, 또는 서비스중인 패킷의 서비스 종료 이벤트마다 GPS 서버에서 행해진 일의 양으로 갱신되며, 갱신된 가상종료시간을 패킷의 타임 스탬프(time stamp)로 사용한다. 이 알고리즘은 GPS 알고리즘에 근접한 성능을 제공할 수는 있으나, 최악의 경우 하나의 패킷이 전송되는 동안 모든 연결로부터 새로운 패킷이 도착할 수 있으므로, 연결의 수만큼 가상시간의 계산 및 갱신이 반복될 수 있다. 따라서, 패킷에 대해 고속의 전송순서 결정이 요구되는 고속망 환경에서는 사실상 구현이 어렵다 할 수 있다.

이와 같은 WFQ 알고리즘이 가지고 있는 구현상의 복잡성을 개선하기 위해 제안된 스케줄링 알고리즘으로 SCFQ(Self Clocked Fair Queuing) 알고리즘이 있다. 이 알고리즘은 WFQ 알고리즘과 달리 연속적인 GPS 시뮬레이션을 거치지 않고, 새로운 패킷 도착시 서비스 중인 패킷의 타임 스탬프를 가상시간으로 간주한다. 그 결과, 하나의 전송 중에 도착한 패킷은 모두 동일한 가상시간을 공유하게 되어, 가상시간의 계산에 따르는 복잡성을 대폭 줄일 수 있다. 그러나, 최악의 경우 임의의 패킷 도착시 모든 세션이 서비스중인 타임 스탬프와 동일한 시간을 가질 수 있기 때문에, 새로 도착한 패킷은 트래픽 약속 준수 여부와 무관하게 모든 세션의 패킷이 전송될 때까지 대기하여야 한다. 이 경우, 대기 시간은 연결된 세션의 수에 비례하게 된다. 이와 같이, SCFQ 알고리즘은 가상시간 계산에 따르는 복잡성은 개선되었으나, 보장 가능한 지연 바운드는 WFQ 알고리즘 보다 열화되는 단점이 있다.

이와 같은 SCFQ 알고리즘의 단점을 개선하기 위한 방안으로 SPFQ(Starting Potential Fair Queueing) 알고리즘이 있다. 이 알고리즘은 매 패킷의 전송이 끝날 때마다 각 큐의 헤드에 있는 패킷들의 가상시작시간 값 중 가장 작은 값을 가상시간으로 재 설정하는 알고리즘으로서, 우수한 성능을 유지하는 장점이 있으나, 가상시작시간에 대한 정렬 과정이 부가적으로 필요한 단점이 있다.

SCFQ 알고리즘과 유사한 관점에서 WFQ 알고리즘의 계산 복잡성을 개선하기 위한 방안으로 MD-SCFQ(Minimum-Delay Self-Clocked Fair Queueing) 알고리즘이 있다. 이 알고리즘은 SCFQ 알고리즘과 같이 GPS를 별도 시뮬레이션하지 않고 큐에서 대기 중인 선두 패킷에 관한 정보를 이용하여 시스템 가상시간을 계산함으로써, WFQ 알고리즘에 비해 계산의 복잡성을 줄이고 SCFQ 알고리즘에 비해 지연특성을 개선하려는 알고리즘이다. 그러나, 이 알고리즘은 시스템 가상시간을 계산하는 순간 큐에서 대기하는 패킷의 정보를 지속적으로 수집하고 관리하여야 하는 오버헤드가 수반되는 단점이 있다.

이와 같은 작업보존 방식의 스케줄링 알고리즘들은, 각 시스템별 가상시간 함수 및 타임 스탬프를 계산하고 유지하는 방식에 차이를 가지고 있다. 고속 망 환경을 대상으로 하는 스케줄링 시스템 있어서 가장 중요한 성능 파라미터는, 고속의 전송순서 결정과 관련된 시스템의 단순성이라는 점을 고려할 때, 이러한 단순성을 유지하면서도 작업보존 스케줄링 시스템의 기본적인 요구 조건인 공정성 및 지연 특성을 GPS와 가장 근접되게 유지할 수 있는 시스템일수록 우수하다고 할 수 있다. 그러므로, 고속 패킷 교환망에서 교환기 또는 라우터에 대해 WFQ 수준의 지연 바운드 및 공정성 지수를 보장하면서, 시스템 가상시간 계산 복잡성은 O(1)의 복잡도를 유지할 수 있는 새로운 패킷 스케줄링 시스템 및 방법이 요구된다.

본 발명이 이루고자 하는 기술적 과제는, 고속 패킷 교환망상의 교환기 또는 라우터에서 WFQ 수준의 지연 바운드 및 공정성 지수를 보장하되, 시스템 가상시간 계산의 복잡성은 O(1)의 복잡도를 유지할 수 있는 패킷 스케줄링 시스템 및 방법을 제공하는데 있다.

본 발명이 이루고자 하는 다른 기술적 과제는, 패킷의 전송 순서 결정시 공정하고 최적의 지연 바운드를 제공할 수 있는 패킷 스케줄링 시스템 및 방법을 제공하는데 있다.

본 발명이 이루고자 하는 또 다른 기술적 과제는, 상기 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하는데 있다.

도 1은 본 발명에 따른 패킷 스케줄링 시스템이 구비된 고속 패킷 교환 노드의 기본 구조를 보여주는 블록도이다.

도 2는 도 1에 도시된 입력 인터페이스 내에 구성되는, 본 발명에 따른 패킷 스케줄링 시스템의 상세 구성을 보여주는 블록도이다.

도 3은 도 2에 도시된 가상종료시간 계산부의 상세 블록도이다.

도 4는 새로운 패킷이 도착할 때 도 3에 도시된 가상종료시간 계산부에서 수행되는 시스템 가상시작시간 및 시스템 가상종료시간 계산 과정을 보여주는 흐름도이다.

도 5는 도 4에 도시된 1450 단계에서 수행되는 가상시작시간() 및 가상종료시간() 계산에 대한 상세 흐름도이다.

도 6은 도 2에 도시된 패킷 전송부의 상세 블록도이다.

도 7은 도 6에 도시된 패킷 전송부에서 수행되는 패킷 전송 과정을 보여주는 흐름도이다.

< 도면의 주요 부분에 대한 부호의 설명 >

10 : 입력 인터페이스부11 : 트래픽 분류기

12 : 그래픽 스케줄러14 : 가상종료시간 계산부

15 : 중앙관리부16 : 패킷 큐

17 : 패킷 전송부20 : 스위치 패브릭

30 : 출력인터페이스부

상기의 과제를 이루기 위하여 본 발명에 의한 패킷 스케줄링 시스템은, 복수 개의 입력 링크들로부터 입력된 트래픽들을 각 세션별로 분류하는 트래픽 분류기; 상기 각 세션에 대한 협약 속도 및 시스템의 가상시간을 관리하는 중앙관리부; 상기 협약 속도 및 상기 시스템 가상시간에 응답해서 상기 트래픽에 대해 패킷별 가상종료시간을 계산하고, 계산된 상기 가상종료시간을 상기 패킷의 헤더에 타임 스탬프로 덧붙이는 가상종료시간 계산부; 상기 가상종료시간 계산부로부터 전달되는상기 패킷을 세션별로 저장하는 패킷 큐; 및 상기 패킷 큐에 저장된 상기 패킷 중 상기 가상종료시간이 가장 작은 패킷을 선택하여 출력하는 패킷 전송부를 포함하는 것을 특징으로 한다.

상기의 과제를 이루기 위하여 본 발명에 의한 패킷 스케줄링 방법은, (a) 복수 개의 입력 링크들로부터 입력된 트래픽들을 각 세션별로 분류하는 단계; (b) 중앙관리부로부터 제공되는 각 세션별 협약 속도 및 시스템의 가상시간에 응답해서 상기 트래픽에 대해 패킷별 가상종료시간을 계산하고, 계산된 상기 가상종료시간을 상기 패킷의 헤더에 타임 스탬프로 덧붙이는 단계; (c) 상기 가상종료시간이 덧붙여진 상기 패킷을 패킷 큐에 세션별로 저장하는 단계; 및 (d) 상기 패킷 큐에 저장된 상기 패킷 중 상기 가상종료시간이 가장 작은 패킷을 선택하여 출력하는 단계를 포함하는 것을 특징으로 한다.

이하에서, 첨부된 도면을 참조하여 본 발명의 바람직한 실시예에 대하여 상세히 설명한다.

도 1은 본 발명에 따른 패킷 스케줄링 시스템이 구비된 고속 패킷 교환 노드의 기본 구조를 보여주는 블록도이다. 도 1에는 본 발명이 적용되는 ATM 또는 인터넷 등의 고속 패킷 교환망에서, 다수의 입력 링크들로부터 임의의 속도로 인입되는 패킷들을 스케줄링하고, 스케줄링된 패킷들을 순차적으로 다중화하여 전송하는 고속 패킷 교환 노드(예를 들면, ATM 교환기, 라우터 시스템 등)의 기본적인 구성이 도시되어 있다. 본 발명에 따른 패킷 스케줄링 시스템은 고속 패킷 교환 노드의 입력 인터페이스부(10) 및/또는 출력 인터페이스부(30)에 구비된다.

도 1을 참조하면, 고속 패킷 교환 노드는 크게 입력 인터페이스부(10), 스위치 패브릭(20), 및 출력 인터페이스부(30)로 구성된다. 입력 인터페이스부(10)는 m개의 입력 인터페이스들(10a-10m)을 포함하고, 출력 인터페이스부(30)는 n개의 출력 인터페이스들(30a-30n)을 각각 포함한다.

입력 인터페이스부(10)에 구비된 각각의 입력 인터페이스(10a-10m)는 복수 개의 입력 링크로부터 입력되는 복수 개의 트래픽에 대해 본 발명에 따른 패킷 스케줄링을 수행하고, 스케줄링 결과를 스위치 패브릭(20)의 입력포트(17)를 통해 스위치 패브릭(20)에게 전달한다. 스위치 패브릭(20)은 입력 인터페이스부(10)로부터 제공되는 입력 트래픽을 스위칭한 후, 이를 스위치 패브릭(20)의 출력포트(27)를 통해 출력 인터페이스부(30)에게 전달한다. 출력 인터페이스부(30)에 구비된 각각의 출력 인터페이스(30a-30n)는 스위치 패브릭(20)을 통해 제공되는 트래픽을 받아들여 본 발명에 따른 패킷 스케줄링을 수행하고, 그 결과를 출력 링크로 출력한다.

도 2는 도 1에 도시된 입력 인터페이스(10a) 내에 구성되는, 본 발명에 따른 패킷 스케줄링 시스템(100)의 상세 구성을 보여주는 블록도이다. 도 2를 참조하면, 본 발명에 따른 패킷 스케줄링 시스템(100)은, 트래픽 분류기(11)와 트래픽 스케줄러(12)를 포함한다. 그리고, 트래픽 스케줄러(12)는 가상종료시간 계산부(14), 중앙관리부(15), 패킷 큐(16), 및 패킷 전송부(17)를 포함한다.

트래픽 분류기(11)는 복수 개의 입력 링크(101)로부터 입력된 트래픽들에 대한 다중 필드 기반 트래픽 분류를 수행한다. 트래픽 스케줄러(12)의 가상종료시간 계산부(14)는 분류된 트래픽에 대해서 각 패킷별 가상종료시간을 계산하고, 계산된가상종료시간을 각 패킷의 헤더에 타임 스탬프로 덧붙인다. 패킷 큐(16)는 패킷의 각 헤더에 가상종료시간이 덧붙여진 상기 패킷을 각 세션별로 저장한다. 패킷 전송부(17)는 패킷에 대한 실제적인 전송을 담당한다. 그리고, 중앙 관리부(15)는 가상종료시간 계산부(14), 패킷 큐(16) 및 패킷 전송부(17)에 연결되어, 각 세션에 대한 협약 속도 및 시스템의 가상시간 등을 관리한다.

입력 링크(101)로부터 입력된 트래픽은 트래픽 분류기(11)에 의하여 각 세션을 구분한다. 트래픽 분류에 사용되는 패킷의 필드가 인터넷 프로토콜과 같은 3 계층 프로토콜인 경우, IP의 소스 주소, 목적지 주소, 프로토콜 필드, 포트 번호 등과 같은 다중 필드를 기반으로 하여 세션을 구분한다. 그리고, ATM의 경우 VPI(Virtual Path Identifier) 및 VCI(Virtual Channel Identifier)값을 기반으로 하여 세션을 구분하고, MPLS(Multiprotocol Label Switching)의 경우는 MPLS 헤더의 레이블 값을 기반으로 하여 세션을 구분한다.

각 세션으로 구분된 트래픽은 가상종료시간 계산부(14)로 입력되는데, 가상종료시간 계산부(14)는 중앙 관리부(15)에 의해 관리되는 시스템가상시간과 해당 세션의 이전 패킷의 가상종료시간을 기반으로 하여 각 패킷 별 가상종료시간을 계산하고, 계산된 결과를 해당 세션에 해당하는 패킷 큐(16)에 저장한다. 패킷 전송부(17)는 패킷 큐(16)에 저장된 패킷 중 각 세션의 가상 종료 시간이 가장 작은 패킷을 우선적으로 선택하여 출력링크에게 전송한다.

각 입력 링크로부터 입력된 트래픽이 트래픽 분류기(11)를 통과하여 각 세션 별로 구분된 후, 가상종료시간 계산부(14) 및 패킷 전송부(17)에서 수행되는 상세동작은 다음과 같다.

도 3은 도 2에 도시된 가상종료시간 계산부(14)의 상세 블록도이다. 도 3을 참조하면, 가상종료시간 계산부(14)는 시스템 가상시작시간 계산기(142)와 시스템 가상종료시간 계산기(144)로 구성된다.

시스템 가상시작시간 계산기(142)는 중앙 관리부(15)로부터 세션에 대한 협약속도 및 시스템 가상시간을 가져와서, 패킷이 속한 세션의 이전 도착 패킷의 가상종료시간 및 현재 시점의 시스템 가상시간 중 큰 값을 시스템 가상시작시간으로 결정한다. 시스템 가상종료시간 계산기(144)는 가상시작시간 계산기(142)에 의해 계산된 가상시작시간과, 패킷이 속한 세션의 속도 및 패킷의 길이에 의해 시스템 가상종료시간을 계산한다.

도 4는 새로운 패킷이 도착할 때 도 3에 도시된 가상종료시간 계산부(14)에서 수행되는 시스템 가상시작시간 및 시스템 가상종료시간 계산 과정을 보여주는 흐름도이다. 도 4를 참조하면, 가상종료시간 계산부(14)는 새로운 패킷이 시간 t에 도착하게 되면(1410 단계), 패킷 분류 작업을 통해 각 패킷이 속한 세션을 구분하고, 구분된 세션의 예약 속도를 계산한다(1430 단계). 이어서, 중앙 관리부(15)로부터 입력된 시스템 가상시간(v()) 및 이전 패킷의 길이를 기반으로 하여 현재 패킷(예를 들면, k번째 패킷)에 대한 가상시작시간() 및 가상종료시간()을 계산한다(1450 단계). 그리고, 1450 단계에서 계산된 가상종료시간()을 타임 스탬프로 하여 각 패킷의 헤더에 덧붙이고, 상기 패킷을 각 세션의 패킷 큐(16)에게 전송한다(1470 단계).

도 5는 도 4에 도시된 1450 단계에서 수행되는 가상시작시간() 및 가상종료시간() 계산에 대한 상세 흐름도이다. 도 5를 참조하면, 패킷이 시간 t에 도착하였을 경우, 해당 세션의 이전 패킷(즉, (k-1)번째 패킷)의 가상종료시간()을 가져온다(1451 단계). 그리고, 현재 서비스 중인 패킷의 서비스 시작시점(즉, 직전 패킷의 서비스 종료시점 ;)에서 갱신된 시스템 가상시간()과,시점에서 현재시간 t 까지의 경과 시간()을 합하여, 새로운 패킷의 도착순간(즉, 시점 t)에 대한 시스템 가상시간()을 계산한다(1452 단계). 이 때 계산되는 시스템 가상시간()은 아래의 [수학식 1]과 같다.

이어서, 가상종료시간 계산부(14)의 시스템 가상시작시간 계산부(142)는, [수학식 1]에 의해 계산된 시스템 가상시간 값()과, 이전 패킷의 가상종료시간()을 비교하고, 두 값 중 큰 값을 패킷의 가상시작시간()으로 설정한다(1453 단계). 이를 수학식으로 나타내면 다음과 같다.

[수학식 2]에 의해 가상시작시간()이 계산되고 나면, 가상종료시간 계산부(14)의 시스템 가상종료시간 계산부(144)는, 1453 단계에서 계산된 가상시작시간()과, 패킷의 길이(), 및 패킷이 해당되는 세션의 세션 속도()를 이용하여, 다음 [수학식 3]과 같이 가상종료시간()을 계산한다(1454 단계).

[수학식 3]에 의해 가상종료시간()이 계산되고 나면, 가상종료시간 계산부(14)는 계산된 가상종료시간()을 각 패킷의 헤더에 타임 스탬프로서 덧붙이고, 상기 패킷을 각 세션의 패킷 큐(16)에게 전송한다(도 4의 1470 단계 참조).

앞에서 설명한 바와 같이, 현재 전송 중인 패킷이 전송 완료되는 경우, 패킷 전송부(17)는 패킷의 전송이 완료되는 시점에서 다음에 전송할 패킷을 선택하여 출력하고, 시스템 가상시간을 재조정하는 동작을 수행한다. 이에 대한 상세 구성 및 동작은 다음과 같다.

도 6은 도 2에 도시된 패킷 전송부(17)의 상세 블록도이다. 도 6을 참조하면, 패킷 전송부(17)는 패킷 리스트 관리기(172)와, 패킷 전송기(174)로 구성된다.

패킷 리스트 관리기(172)는, 가상종료시간 계산부(14)에 의해 계산된 패킷의 가상종료시간을 근거로 하여, 패킷 큐(16)에 저장되어 있는 패킷 리스트를 관리한다. 패킷 전송기(174)는, 패킷 리스트 관리기(172)에 의해 관리되는 패킷 리스트 중 가상종료시간이 가장 작은 패킷을 선택하여 출력링크로 전송하고, 중앙관리부(15)로 시스템 가상시간 업데이트 인터럽트를 발생하여 시스템 가상시간을 재조정하도록 한다.

도 7은 도 6에 도시된 패킷 전송부(17)에서 수행되는 패킷 전송 과정을 보여주는 흐름도이다. 도 7을 참조하면, 패킷 전송부(17)는 현재 전송 중인 패킷의 전송이 완료되고 나면(시간=)(1701 단계), [수학식 4]와 같이 이전 패킷의 전송이 완료된 시간()에서의 시스템 가상시간()에 상기 패킷을 전송하는 데 실제 소요된 시간()을 더해줌으로써, 현재 전송 중인 패킷의 전송이 완료된 순간(시간=)의 시스템 가상시간()을 구하게 된다(1702 단계).

이어서, 패킷 전송부(17)는 패킷 큐(16)에 저장되어 있는 패킷 중 가장 작은 가상 종료 시간을 가지는 패킷을 선택하여 전송한다(1703 단계). 그리고, 이 패킷의 가상종료시간을라고 할 때 [수학식 5]와 같은 시스템 가상시간 재조정 동작을 수행한다(1704 단계).

여기서,는 세션 i의 패킷의 최대 크기이며,는시점에서 보낼 패킷이 있는 세션들의 집합이다.

앞에서 설명한 바와 같이, 본 발명에 따른 패킷 스케줄링 방법에 따르면, 하나의 패킷 전송 중 새로 도착하는 패킷은 모두 동일한 기준에 의하여 타임 스탬프를 계산하므로, 시스템 가상시간 계산에 따른 복잡성이 O(1) 값으로 개선된다. 이는, WFQ 패킷 스케줄링 시스템에서 시스템 가상시간(즉, 가상시간)의 갱신이 세션의 수(N)에 의존하여 O(N)로 표시되는 것과 비교할 때, N배 개선된 것이라 할 수 있다.

그러나, 기존의 SCFQ 패킷 스케줄링 시스템 역시 하나의 패킷 처리 중 도착한 모든 패킷이 서비스 중인 패킷의 타임 스탬프(즉, 시스템 가상시간)에 의거하여 자신의 타임 스탬프를 계산하기 때문에, O(1)의 복잡성을 갖는다. 하지만, SCFQ 패킷 스케줄링 시스템에서는 복잡성은 개선되었지만 임의의 패킷이 도착하여 전송될 때까지 겪는 지연의 최대 값이 세션의 수에 의존하는 특성을 갖게되므로, 많은 인입 트래픽이 존재하는 노드에 적용하기 어려운 단점이 있다. 그리고, SPFQ 패킷 스케줄링 시스템은 가상시작시간에 의해서 정렬된 순서를 유지하는 단점이 있고, 그로 인해 가상시간의 계산의 복잡도가 O(log N)이 된다.

그리고, MD-SCFQ 패킷 스케줄링 시스템은 가상시간 계산의 복잡도를 O(1)로줄이며 지연 및 공정성 지수의 성능을 개선하였지만, 여전히 가상시간의 계산을 위한 부가적인 복잡도가 존재하는 문제점을 여전히 가지고 있다.

따라서, 본 발명에 따른 패킷 스케줄링 시스템 및 방법은 상기와 같은 기존의 패킷 스케줄링 시스템이 가지고 있는 문제점들을 개선하여, 복잡성은 O(1)로 유지하면서도 최대 지연 한도를 WFQ 패킷 스케줄링 시스템 수준으로 보장할 수 있으며, WFQ 패킷 스케줄링 시스템의 공정성 지수에 상응하는 공정성 지수의 값을 가진다. 그러므로, 본 발명에 따른 패킷 스케줄링 시스템 및 방법은, 고속 패킷 교환노드에 적용 가능한 장점을 가지며, 인터넷 망과 같이 가변적인 패킷 뿐 아니라 ATM과 같이 고정크기의 패킷에도 적용될 수 있는 장점을 가진다.

본 발명은 또한 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피디스크, 광데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어, 분산방식으로 컴퓨터가 읽을 수 있는 코드로 저장되고 실행될 수 있다.

이상에 설명한 바와 같이, 본 발명에 의한 패킷 스케줄링 시스템 및 방법에 의하면, 고속 패킷 교환망상에 있는 교환기 또는 라우터에서 WFQ 수준의 지연 바운드 및 공정성 지수를 보장하면서 시스템 가상시간 계산의 복잡성은 O(1)의 복잡도를 유지할 수 있게 된다. 따라서, 패킷의 전송 순서 결정시 공정하고 최적의 지연 바운드를 제공할 수 있다.

Claims

복수 개의 입력 링크들로부터 입력된 트래픽들을 각 세션별로 분류하는 트래픽 분류기;

상기 각 세션에 대한 협약 속도 및 시스템의 가상시간을 관리하는 중앙관리부;

상기 협약 속도 및 상기 시스템 가상시간에 응답해서 상기 트래픽에 대해 패킷별 가상종료시간을 계산하고, 계산된 상기 가상종료시간을 상기 패킷의 헤더에 타임 스탬프로 덧붙이는 가상종료시간 계산부;

상기 가상종료시간 계산부로부터 전달되는 상기 패킷을 세션별로 저장하는 패킷 큐; 및

상기 패킷 큐에 저장된 상기 패킷 중 상기 가상종료시간이 가장 작은 패킷을 선택하여 출력하는 패킷 전송부를 포함하는 것을 특징으로 하는 패킷 스케줄링 시스템.
제 1 항에 있어서, 상기 가상종료시간 계산부는

상기 패킷이 속한 세션의 이전 도착 패킷의 가상종료시간 및 현재 시점의 시스템 가상시간 중 큰 값을 시스템 가상시작시간으로 결정하는 시스템 가상시작시간 계산기; 및

상기 가상시작시간 계산기에 의해 계산된 상기 시스템 가상시작시간, 상기 패킷이 속한 세션의 속도, 및 상기 패킷의 길이에 응답해서 시스템 가상종료시간을 계산하는 시스템 가상종료시간 계산기를 포함하는 것을 특징으로 하는 패킷 스케줄링 시스템.
제 1 항에 있어서,

상기 시스템 가상시간은, 현재 전송되고 있는 패킷의 전송 완료시, 이전 패킷의 전송이 완료된 시점의 시스템 가상시간에 현재 패킷을 출력 링크 속도로 실제 전송하는데 걸리는 시간을 더해줌으로써 계산되는 것을 특징으로 하는 패킷 스케줄링 시스템.
제 2 항에 있어서,

상기 시스템 가상종료시간는, 상기 시스템 가상시작시간이이고, 상기 패킷이 속한 세션의 세션 속도가이고, 상기 패킷의 길이가일 때,의 값을 가지는 것을 특징으로 하는 패킷 스케줄링 시스템.
제 1 항에 있어서, 상기 패킷 전송부는

상기 패킷별 가상종료시간을 근거로 하여 상기 패킷 큐에 저장되어 있는 패킷 리스트를 관리하는 패킷 리스트 관리기; 및

상기 패킷 리스트 중 상기 패킷별 가상종료시간이 가장 작은 패킷을 선택하여 출력링크로 전송하고, 상기 중앙관리부에게 시스템 가상시간 업데이트 인터럽트를 발생하는 패킷 전송기를 포함하는 것을 특징으로 하는 패킷 스케줄링 시스템.
제 5 항에 있어서,

상기 패킷의 가상종료시간이이고,시점에서의 상기 시스템 가상시간이 v()이고, 상기 패킷이 속한 세션 i의 세션 속도가이고, 상기 세션 i의 최대 패킷의 길이가이며, 상기시점에서 보낼 패킷이 있는 세션들의 집합이 B()일 때,

상기 시스템 가상시간은, 상기 가상시간 업데이트 인터럽트에 응답해서의 값으로 재조정되는 것을 특징으로 하는 패킷 스케줄링 시스템.
제 1 항에 있어서,

상기 패킷 스케줄링 시스템은, ATM(asynchronous transfer mode) 교환기 및 라우터를 포함하는 고속 패킷 교환망 노드의 입력 인터페이스 및 출력 인터페이스중 어느 하나에 구비되는 것을 특징으로 하는 패킷 스케줄링 시스템.
(a) 복수 개의 입력 링크들로부터 입력된 트래픽들을 각 세션별로 분류하는 단계;

(b) 중앙관리부로부터 제공되는 각 세션별 협약 속도 및 시스템의 가상시간에 응답해서 상기 트래픽에 대해 패킷별 가상종료시간을 계산하고, 계산된 상기 가상종료시간을 상기 패킷의 헤더에 타임 스탬프로 덧붙이는 단계;

(c) 상기 가상종료시간이 덧붙여진 상기 패킷을 패킷 큐에 세션별로 저장하는 단계; 및

(d) 상기 패킷 큐에 저장된 상기 패킷 중 상기 가상종료시간이 가장 작은 패킷을 선택하여 출력하는 단계를 포함하는 것을 특징으로 하는 패킷 스케줄링 방법.
제 8 항에 있어서, (b) 단계는

(b-1) 상기 패킷이 속한 세션의 이전 도착 패킷의 가상종료시간 및 현재 시점의 시스템 가상시간 중 큰 값을 시스템 가상시작시간으로 결정하는 단계; 및

(b-2) 상기 시스템 가상시작시간, 상기 패킷이 속한 세션의 속도, 및 상기 패킷의 길이에 응답해서 시스템 가상종료시간을 계산하는 단계를 포함하는 것을 특징으로 하는 패킷 스케줄링 방법.
제 8 항에 있어서,

상기 시스템 가상시간은, 현재 전송되고 있는 패킷의 전송 완료시, 이전 패킷의 전송이 완료된 시점의 시스템 가상시간에 현재 패킷을 출력 링크 속도로 실제 전송하는데 걸리는 시간을 더해줌으로써 계산되는 것을 특징으로 하는 패킷 스케줄링 방법.
제 9 항에 있어서,

상기 시스템 가상종료시간는, 상기 시스템 가상시작시간이이고, 상기 패킷이 속한 세션의 세션 속도가이고, 상기 패킷의 길이가일 때,의 값을 가지는 것을 특징으로 하는 패킷 스케줄링 방법.
제 8 항에 있어서, 상기 (d) 단계는

(d-1) 상기 패킷별 가상종료시간을 근거로 하여 상기 패킷 큐에 저장되어 있는 패킷 리스트를 관리하는 단계; 및

(d-2) 상기 패킷 리스트 중 상기 패킷별 가상종료시간이 가장 작은 패킷을 선택하여 출력링크로 전송하고, 상기 시스템 가상시간을 재조정하는 단계를 포함하는 것을 특징으로 하는 패킷 스케줄링 방법.
제 12 항에 있어서,

상기 패킷의 가상종료시간이이고,시점에서의 상기 시스템 가상시간이 v()이고, 상기 패킷이 속한 세션 i의 세션 속도가이고, 상기 세션 i의 최대 패킷의 길이가이며, 상기시점에서 보낼 패킷이 있는 세션들의 집합이 B()일 때,

상기 시스템 가상시간은, 상기 가상시간 업데이트 인터럽트에 응답해서의 값으로 재조정되는 것을 특징으로 하는 패킷 스케줄링 방법.
제 8 항 내지 제 13 항 중 어느 한 항의 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체.