KR100545793B1

KR100545793B1 - 동적 다중 채널 환경에서의 스케쥴링 방법 및 장치

Info

Publication number: KR100545793B1
Application number: KR1020030093462A
Authority: KR
Inventors: 김태연; 김남욱; 윤현호; 유정주; 김병휘
Original assignee: 한국전자통신연구원
Priority date: 2003-12-18
Filing date: 2003-12-18
Publication date: 2006-01-24
Also published as: KR20050061226A

Abstract

본 발명은 WDM/SCM-PON(Wave length Division Multiplex / Sub-Carrier Multiplex - Passive Optical Network)과 같이 파장별로 다중 채널을 갖는 동적 다중 채널 환경에 있어서 서비스 속성별로 요구되는 적절한 서비스 수준을 보장할 수 있으며 망 자원을 효과적으로 운용할 수 있는 동적 다중 채널 환경에서의 스케쥴링 방법 및 장치에 관한 것으로서, 본 발명은 큐의 상태에 따라서 스케줄링 기법을 달리함으로서 트래픽의 유형에 따라 장치의 자원의 활용도를 최소화하고, 대역을 보장할 수 없는 상황에서는 출력 대역의 최우선 서비스를 보장하기 위한 전용채널을 설정함으로서 폭주하는 데이터의 유입이 있는 상황에서도 음성 또는 영상 패킷에 대해서는 일정 수준이상의 전송 속도를 보장할 수 있도록 한다.

동적 다중 채널, WDM/SCM-PON, 큐잉, 스케쥴링, 출력포트, QoS

Description

동적 다중 채널 환경에서의 스케쥴링 방법 및 장치{Scheduling method and apparatus in dynamic multiplex channel network}

도 1은 일반적인 선착순 처리 방식(FCFS) 스케줄링 과정을 나타낸 설명도이다.

도 2는 일반적인 우선순위 큐잉(Priority Queuing) 스케줄링 과정을 나타낸 설명도이다.

도 3은 일반적인 가중치 공정 대기열 처리(WFQ) 방식의 스케줄링 과정을 나타낸 설명도이다.

도 4는 WDM/SCM-PON에 있어서의 다중 채널 구조를 묘사한 모식도이다.

도 5는 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 장치의 구성을 나타낸 블록도이다.

도 6은 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 개념을 설명하는 모식도이다.

도 7은 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 방법을 순차적으로 나타낸 플로우 챠트이다.

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

510 : 패킷 분류 수단

520 : 큐잉 수단

530 : 스케쥴러

540 : 출력수단

550 : QoS 관리수단

본 발명은 WDM/SCM-PON(Wave length Division Multiplex / Sub-Carrier Multiplex - Passive Optical Network)과 같이 대역폭이 가변되고 다중 채널을 갖는 동적 다중 채널 환경에 있어서, 서비스 속성별로 각각의 QoS 수준을 보장할 수 있으며 망 자원을 효과적으로 운용할 수 있는 동적 다중 채널 환경에서의 스케쥴링 방법 및 장치에 관한 것이다.

일반적으로, 스케쥴링 기법은 다중 경로가 존재하는 소정의 데이타 통신망으로 입력된 트래픽을 목적지까지 포워딩하기 위한 경로 및 전달 순서를 결정하는 방식으로서, 현재 대표적으로 사용되는 스케쥴링 기법으로, 선착순 처리방식(First Come First Served, 이하 FCFS라 한다), 우선 순위 대기열 처리방식(Priority Queuing), 가중치 공정 대기열 처리방식(Weigthed fair queuing, 이하 WFQ라 한다)를 들 수 있다.

상기 기법중에서, FCFS는 도 1에 도시된 바와 같이, 단일 FIFO 큐(12)를 사용하여, 모든 클래스의 트래픽을 저장한 후, 패킷의 클래스나 우선순위에 상관없이 먼저 도착한 패킷을 먼저 출력링크(13)로 포워딩하는 단순한 방식으로서, 최선노력전송(Best Effort) 서비스 모델만을 가지고 있는 전통적인 인터넷 망에서 사용된다. 상기 FCFS 스케쥴링 방식을 트래픽의 구분이 존재하지 않기 때문에, 포트나 개별 프레임에 대한 우선순위 설정 및 구분 절차가 필요하지 않다.

이러한 FCFS 스케쥴링 방식은, 패킷들의 순서가 유지될 수 있고, 패킷의 최대 딜레이는 큐의 최대 크기에 의해 결정되는 등의 장점이 있는데 반하여, 트래픽을 서비스 클래스별로 구분하지 않기 때문에, 차등화된 패킷 처리 기능을 제공할 수 없으며, 고속전송이 요구되는 버스트 트래픽 서비스에 부적합하며, 특히, TCP와 UDP 트래픽이 혼재하는 경우 혼잡이 발생하면 TCP 센더는 흐름 제어 알고리즘에 의해 전송 속도를 줄이게 되지만, UDP 센더는 계속해서 트래픽을 보내어, TCP 트래픽의 서비스가 어렵게 된다는 단점이 있다. 따라서, 상기 FCFS 스케쥴링 방식은 출력측 포트의 링크 스피드가 대단히 높아서 큐잉 지연이 거의 발생하지 않는 장치의 경우에만 적합하다.

두번째로, 우선순위 대기열 처리방식은 Strict Priority Queuing이라고도 불리는 것으로서, 도 2 에 나타난 바와 같이, FIFO 방식의 다수의 클래스 큐(22a~22c)를 각각 서로 다른 서비스 클래스에 매핑시키고, 입력된 트래픽을 분류기(classifier)(21)에 의해 서비스 클래스별로 분류하여, 대응하는 제1~제3 클래스 큐(22a~22c)에 각각 저장시킨 후, 우선순위가 높은 큐에 저장되어 있는 패킷들을 모두 서비스한 후, 그 다음 우선순위의 큐에 저장된 패킷들을 서비스하는 방식이다.

제1,제2,제3클래스 큐(22a~22c) 순으로 우선순위가 설정된다고 할때, 이론적으로는 하위 우선순위를 갖는 제3클래스 큐(22c)에 저장되어 있는 패킷이 서비스 되는 도중 보다 앞선 우선순위의 제1클래스 큐(22a)에 패킷이 입력되면, 제3클래스 큐(22c)에 저장된 패킷의 서비스를 잠시 중단하고, 제1클래스 큐(22a)에 새로 도착한 패킷을 먼저 서비스해주게 되어 있으나, 패킷 기반의 처리의 경우 일반적으로 현재 서비스되고 있는 제3클래스 큐(22c)의 패킷 처리를 완료한 후에, 제1 클래스 큐(22a)에 도착한 패킷을 서비스한다.

이러한 WFQ 방식은, 간단한 방법으로 차등화된 서비스를 제공할 수 있고, 실시간 어플리케이션을 지원할 수 있다는 장점이 있는데 반하여, 높은 우선순위 큐에 패킷이 계속해서 입력되는 경우에는 낮은 우선순위 큐에 저장된 패킷은 서비스되지 못하는 대역 기근 현상(Starvation)이 발생할 수 있고, 단순히 클래스별로 서비스하기 때문에 여러 트래픽 플로우가 하나의 동일한 큐에 저장되는 경우, 버스트하게 입력되는 트래픽이 다른 플로우들을 압도하게 되는 문제가 발생한다.

세번째로, WFQ 스케쥴링 방식은 상기 도 2에 보인 우선순위 대기열 처리방식에서 발생하는 대역 기근현상을 해결함과 동시에 일반적인 공정 대기열 처리 방식에서 상위 클래스 버퍼에 차등화 된 서비스를 제공하지 못하는 문제점을 해결한 것으로서, 도 3에 도시된 바와 같이, 각각 클래스별로 매핑 된 다수의 클래스 큐(32a~32c)에 정책적으로 사전에 결정된 가중치(weight)를 할당하여, 상기 클래스 큐(32a~32c)에 저장된 패킷에 대하여 우선순위 별로, 각각 할당된 가중치에 비례하도록 스케쥴링한다.

예를 들어, 도 3의 구조에서, 제1클래스 큐(32a)에 50%, 제2 클래스 큐(32b)와 제3클래스 큐(32c)에 각각 25%의 가중치를 할당한다고 가정하면, 상기 출력링크에는 상기 클래스큐(32a~32c)별로 할당된 가중치에 비례하여, 각 제1,2,3 클래스큐(32a~32c)의 패킷이 50 : 25 : 25 비율로 존재하게 된다. 만일, 최상위 클래스 버퍼인 제1 클래스 큐(32a)에 패킷이 없을 경우, 잔여 가중치는 하위의 제2,3 클래스 큐(32b,32c)에 동일 비율로 나뉘어져 서비스되고, 반대로 하위의 제3 클래스 큐(32c)가 비었을 경우 상위의 제1,2 클래스 큐(32a,32b)들이 잔여 가중치를 분할하여 사용한다.

상기 WFQ 방식은 단순히 가중치만을 할당하기보다는 반드시 보장되어야 하는 대역폭을 설정할 수도 있다. 예를 들어, 제1 클래스 큐(32a)에 대해서는 전체 대역폭의 25%를, 제2 클래스 큐(32b)에 대해서는 전체 대역폭의 15%를 반드시 보장해 줄 필요가 있는 경우, 상기의 요구 대역폭 만큼의 가중치를 제1,2 클래스(32a,32b)에 우선적으로 할당한 후, 나머지 60%에 해당하는 대역폭을 가중치(50:25:25)에 따라서 제1~제3 클래스 큐(32a~32c)에 할당한다. 상기 예의 경우, 최종적으로, 제1,2,3클래스 큐(32a~32c)에 할당되는 가중치 비율은 55% : 30% : 15%가 된다.

즉, WFQ 방식에 있어서, 전체적인 동작은 일반적 프로세서 제어(Generalized Processor Sharing) 방식에 의한 가상 종료시간 (Virtual Finishing Time) 계산에 의해 이루어지며, 할당된 가중치를 고려하여 패킷의 가상 종료시간이 가장 빠른 순 서대로 서비스함으로써 적절한 스케줄링을 가능케 한다.

그러나, 이 방법은 우선순위 보장보다는 효율적 대역 자원분할의 의미가 더 크고, 큐 간의 서비스 공정성 (Service Fairness)이 낮다는 단점이 있다.

더불어 상술한 기존의 방식 모두, 단일 출력링크인 경우만을 고려한 것으로서, 출력링크가 다중 채널로 된 경우, 적용할 수 없다.

예를 들어, WDM/SCM-PON은 국사로부터 광섬유가 파장 및 SCM(Sub-carrier multiplexing) 채널 단위로 다중화되어 분배되는 간선망 구조를 가지며, 접속망에서는 파장 단위로 역-다중화 되고, 파장 단위로 분기된 후에는 수동형 광 분배기를 통하여 가정에 분배되는 구조를 갖는다. 이때, 파장은 이미 국사로부터 분기된 SCM 채널 단위로 다중화 되어 있으므로 각 가정에서는 SCM 채널 단위의 서비스 인터페이스를 가진다. 이러한 WDM/SCM-PON은 기본적으로 비대칭으로 상향과 하향 트래픽을 분리한다. 즉, 이더넷(Ethernet)의 양방향 대칭 구조가 통계적으로 볼 때 가입자 망의 서비스에 부합되지 않는다는 점을 보완하기 위하여 상향과 하향의 채널의 분리를 통하여 사용자 별로 상향 혹은 하향 대역을 별도로 보장 한다. 단, 상향에 있어서는 수동형 광분배기에서의 충돌현상을 방지하기 위하여 SCMA 방식으로 지정된 채널을 사용하며, 하향 트래픽은 독립 채널 혹은 필요한 경우 공유 채널을 사용할 수 있으며, 서비스 채널의 개수를 가입자 별로 다르게 운용이 가능하다.

따라서, 상술한 WDM/SCM-PON와 같이 다중 채널로 이루어진 출력링크로 다수 트래픽을 효율적으로 스케쥴링할 수 있는 기술이 요구되며, 더불어, 동적 다중 링크를 효율적으로 사용하여, 트래픽의 서비스 속성별로 요구되는 QoS 수준을 보장할 수 있는 새로운 방식의 스케쥴링 기술이 필요하다.

본 발명은 상술한 종래의 문제점을 해결하기 위하여 제안된 것으로서, 그 목적은 WDM/SCM-PON(Wave length Division Multiplex / Sub-Carrier Multiplex - Passive Optical Network)과 같은 대역폭이 가변되고 다중 채널을 갖는 동적 다중 채널 환경에서 서비스 속성별로 각각의 QoS를 보장할 수 있으며 망자원을 효과적으로 운용할 수 있는 동적 다중 채널 환경에서의 스케쥴링 방법 및 장치를 제공하는 것이다.

본 발명의 다른 목적은 파장 별로 SCM 채널을 다중화 하여 트래픽을 전송하는 WDM/SCM-PON 망에 있어서, 가입자의 ONT에 접속되는 채널의 동적 변경을 통하여, 사용자가 요구하는 서비스 품질을 대역 확보를 통하여 보장 할 수 있는 동적 다중 채널 환경에서의 스케쥴링 방법 및 장치를 제공하는 것이다.

상술한 본 발명의 목적을 달성하기 위한 구성수단으로서, 본 발명은 다중 채널에 각각 연결되는 다수의 출력포트를 구비한 종단 장치에서 이루어지는 동적 다중 채널 환경에서의 스케쥴링 방법에 있어서, 상기 종단장치로 입력되는 트래픽을 패킷단위로 수신하는 단계; 상기 수신된 패킷을 서비스 클래스별로 분류하여 저장하는 단계; 상기 저장된 서비스 클래스별 패킷량이 기설정된 임계값을 초과하는 지 를 감시하는 단계; 상기 감시결과, 어떤 서비스 클래스의 패킷량도 임계값을 초과하지 않으면, 선착순 처리방식(FCFS)에 의해 가장 먼저 수신된 패킷순으로 포워딩할 패킷을 선택하고, 소정 서비스 클래스의 패킷량이 임계값을 초과하면, 가중치 공정 대기열 처리 방식(WFQ)에 의하여 서비스 클래스별로 일정 비율로 포워딩할 패킷을 선택하는 단계; 상기 단계에서 선택된 패킷의 서비스클래스별로 전송될 플로우를 분류하는 단계; 상기 단계에서 분류된 플로우에 따라서 선택된 패킷을 포워딩할 출력포트를 선택하는 단계; 및, 상기 선택된 출력포트로 상기 선택된 패킷을 포워딩하는 단계로 이루어지는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 방법은, 상기 감시결과 소정 서비스 클래스의 패킷량이 임계값을 초과하면, 패킷의 선택전에 출력포트에 신규 채널을 추가할 수 있는지를 판단하는 단계; 및 상기 판단결과 채널 추가가 가능하면, 신규 채널을 추가한 후 해당 채널을 소정의 출력포트와 결합시키는 단계를 더 포함하는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 방법은 상기 서비스 클래스별 플로우를 분류하는 단계에서, 다중 채널에 각각 대응하는 출력포트중 소정 출력 포트는 고정 속도 서비스(CBR)용으로 설정하고, 최상위 우선순위를 갖는 서비스 클래스의 패킷은 상기 고정 속도 서비스(CBR)용 출력포트로 포워딩되도록 정의하는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 방법은 상기 서비스 클래스별 플로우를 분류하는 단계에서, 다중 채널에 각각 대응하는 다수의 출력 포트중 임의의 출력포트에 대해서, 무지정 전송 속도 서비스(UBR)용으로 정의하고, 하위 우선순위의 서비스 클래스로 분류된 패킷은 상기 무지정 전송속도 서비스(UBR)용 출력 포트로 포워딩되도록 정의하는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 방법은, 상기 출력 포트 선택 단계에서 상기 무지정 전송속도 서비스(UBR)용 출력포트들중 하나를 순환 처리 방식(Round-robin)에 의하여 선택되는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 방법은 선착순 처리 방식(FCFS)에 의한 패킷 선택시, 각 서비스 클래스별로 처음 유입된 패킷들의 타임 스탬프(TimeStamp)를 비교하여, 가장 작은 타임 스탬프를 갖는 패킷을 포워딩할 패킷으로 선택하는 것을 특징으로 한다.

또한, 본 발명은 상기 목적을 달성하기 위한 다른 구성수단으로서, 다중 채널에 각각 연결되는 다수의 출력포트를 구비한 종단 장치에 구비되는 동적 다중 채널 환경에서의 스케쥴링 장치에 있어서, 트래픽을 패킷단위로 입력받아, 서비스 클래스별로 분류하는 패킷 분류 수단; 상기 패킷 분류 수단에 의해 분류된 각 서비스 속성별 패킷을 저장하는 큐잉 수단; 상기 큐잉 수단에 저장된 다수 패킷들을 선착순 처리방식(FCFS) 또는 가중치 공정 대기열 처리방식(WFQ)에 따라서 선택하여 포워딩시키는 스케쥴링 수단; 상기 스케쥴링 수단에서 선택된 패킷을 다중채널에 각각 대응하는 다수의 출력포트중 선택된 출력포트로 인가하는 출력 수단; 및 상기 큐잉수단으로 유입된 서비스 클래스별 패킷량이 임계값을 초과하는지를 감시하여, 임계값 초과여부에 따라서 상기 스케쥴링 수단이 선착순 처리방식 또는 가중치 공 정 대기열 처리방식중 하나로 동작하도록 제어하는 QoS 관리 수단을 포함하여 이루어지는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 장치에 있어서, 상기 패킷 분류 수단은, 입력된 패킷을 서비스 클래스별로 분류하여 큐잉수단으로 인가하는 패킷분류기; 계층별 어드레스 룩업 테이블이 저장된 데이터베이스; 및 입력된 패킷의 목적지 MAC 주소에 따라 상기 데이터베이스를 룩업하여 상기 패킷 분류기를 제어하는 MAC제어기로 이루어지는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 장치에 있어서, 상기 큐잉 수단은, 각각 서비스 속성별로 할당되어 상기 패킷 분류 수단으로부터 분류된 대응하는 패킷을 순서대로 저장하는 다수의 클래스 버퍼; 및 제어용 패킷용으로 할당되어 상기 패킷 분류 수단으로부터 분류된 제어용 패킷을 저장하는 콘트롤 버퍼로 이루어지는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 장치에 있어서, 상기 출력수단은 다중 채널에 각각 대응하는 다수의 출력 포트와 상기 스케쥴링 수단의 출력을 각각 연결하는 다수의 스위칭수단을 포함하고, 상기 다수 스위칭수단을 온/오프함으로서 상기 스케쥴링 수단의 출력 패킷을 선택된 출력포트로 포워딩처리하는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 장치에 있어서, 상기 QoS 관리수단은, 상기 큐잉수단에 저장된 패킷량이 임계값을 초과하는지 여부에 따라서 스케쥴링 방식을 제어하는 QoS 관리자; 상기 큐잉수단에 저장된 패킷량이 임계값을 초과하는지를 감시하는 버퍼 감시부; 및 상기 QoS 관리자에 의해 선택된 스케쥴링 방식으로 동작하도록 상기 스케쥴링 수단을 제어하는 스케쥴러 제어부를 포함하여 이루어지는 것을 특징으로 한다.

더하여, 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 장치에 있어서, 상기 QoS 관리수단은 상기 QoS 관리자의 요구에 따라서 신규 채널을 할당하여 동적 대역폭을 제어하는 동적대역 제어부; 및 상기 동적대역 제어부의 제어에 따라서 출력수단의 출력포트선택을 제어하는 채널 제어부를 더 포함하여, 상기 QoS관리자가 큐잉수단의 패킷량이 임계값을 초과할때, 상기 동적대역 제어부로 신규 채널 추가를 요구하고, 그 수행결과에 따라서 스케쥴링 방식을 결정하도록 하는 것을 특징으로 한다.

이하, 첨부한 도면을 참조하여 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 방법 및 장치에 대하여 실시예를 들어 설명한다.

도 4는 본 발명이 적용될 수 있는 동적 다중 환경의 예로서, WDM/SCM-PON의 다중 채널 구성을 보인 것이다. 도시된 바와 같이, WDM/SCM-PON에 있어서, 망의 시작점인 광선로종단장치(Optical Line Terminal ; 이하 OLT라 한다)(40)의 파장대역은 n개의 SCM 채널로 분기되어 상/하향 전송이 되며, SCM 채널의 집합으로 구성이 된다. 따라서, 상기 OLT(40)의 한 파장대역에 접속되는 광망종단장치(Optical Network Terminal, 이하 ONT라 한다)(41~4N)의 수 N은 최대 n개가 될 수 있으며, N=n인 경우는 하나의 SCM채널이 각각 하나의 ONT(41~4N)에 배정된 경우라고 볼 수 있으며, N<n인 경우, 일부 ONT는 둘 이상의 SCM 채널을 할당받을 수도 있다.

상기 OLT(40)에서 관리되는 채널 그룹 집선기(Aggregator)는 단일 채널이 아닌 둘 이상의 채널 그룹이 하나의 ONT에 할당이 되는 경우, 데이터 전송시 채널 그룹을 분배 및 수집하는 기능을 수행하며, 따라서 집선기의 총수 k는 최대 n/2을 넘을 수 없다.

결과적으로 하나의 ONT가 하나의 SCM 채널로 연결이 될 수도 있고, 몇 개의 채널 그룹으로 하나의 ONT가 연결이 될 수도 있으므로 Aggregator의 수(k)는 동적으로 변동이 된다.

이와 같이, WDM/SCM-PON에서는, 동적으로 채널의 변경이 가능하며, 이는 곧, 채널 다중화를 통하여 특정 ONT와 OLT와의 상하향 출력 대역 폭의 동적 변경이 가능하다는 결론에 이른다.

본 발명은, 이러한 가변적인 다중 채널 환경의 종단 장치에서, 사용자가 원하는 서비스를 수행할 수 있는 스케줄링 방식을 제안한 것이다.

더불어, WDM/SCM-PON에서 QoS를 보장하기 위해서는, 각 종단장치의 세부 대역할당 및 망 운용기능이 대단히 중요하다. 먼저 QoS가 효율적으로 보장되기 위해서는 망내로 유입되는 가입자 트래픽의 세부특성 및 실제 서비스 품질에 대한 요구사항에 대한 사전정의가 필요하며, 이에 따라 각 가입자별 관리기능을 담당하는 수단이 필요하다. 객관적인 QoS 기준값은 QoS 요구의 실시간 처리를 위한 계약지수로 사용되며 망 서비스 사업자와 각 가입자간에 선행적으로 이루어지는 추상적인 품질 을 망 내의 전송 알고리즘에 사용되는 파라미터로 객관화한 값이다.

도 5는 본 발명에 의한 동적 다중 채널 환경에서의 스케쥴링 장치를 나타낸 블럭구성도로서, 상기 도 4에 도시된 OLT 혹은 ONT의 집선기에 적용되어, QoS를 보장하는 패킷의 포워딩을 수행한다.

먼저, 그 구성을 살펴보면, 본 발명의 스케쥴링 장치는, 트래픽(500)을 패킷단위(Pi,Pi+1)로 입력받아 해당 패킷을 서비스 속성별로 분류하는 패킷 분류 수단(510)과, 상기 패킷 분류 수단(510)에 의해 분류된 각 서비스 속성별 패킷을 입력순으로 일시 저장하는 큐잉 수단(520)과, 선착순 처리방식(FCFS) 또는 가중치 공정 대기열 처리방식(WFQ)에 따라서 상기 큐잉 수단(520)에 저장된 다수 패킷중 우선순위를 패킷을 선택하여 포워딩처리하는 스케쥴러(530)와, 다중채널에 각각 대응하는 다수의 출력포트(Port1~PortN)를 구비하고 상기 스케쥴러(530)에 의해서 포워딩된 패킷을 선택된 출력포트로 인가하는 출력 수단(540)과, 상기 큐잉수단(520)의 패킷량을 감시하여, 정상시에는 상기 스케쥴러(530)가 선착순 처리방식(FCFS)로 스케쥴링 동작하고 오버플로우발생시에는 가중치 공정 대기열 처리방식(WFQ)에 의하여 스케쥴링 동작하도록 제어하는 QoS 관리 수단(550)을 포함하여 구성된다.

구체적으로, 상기 패킷 분류 수단(510)은, 입력된 패킷을 서비스 속성별로 분류하여 큐잉수단으로 인가하는 패킷분류기(511)와, 계층별 어드레스 룩업 테이블이 저장된 데이터베이스(513)와, 입력된 패킷의 목적지 MAC 주소에 따라 상기 데이터베이스(513)를 룩업하여 상기 패킷 분류기를 제어하는 MAC제어기(512)로 이루어 진다.

그리고, 상기 큐잉수단(520)은, 제어용 패킷용으로 할당되어 상기 패킷 분류 수단(510)으로부터 분류된 제어용 패킷을 저장하는 콘트롤 버퍼(521)와 각각 서비스 속성별로 할당되어 상기 패킷 분류 수단(510)으로부터 분류된 대응하는 패킷을 순서대로 저장하는 다수의 클래스 버퍼(522~524)로 이루어진다.

그리고, 상기 출력수단(540)은, 다중 채널(channel1~channelN)에 각각 대응하는 다수의 출력 포트(Port1~PortN)와 상기 스케쥴러(530)를 각각 선택 연결하는 다수의 스위칭수단(sw1~sw3)을 구비하여 이루어진다.

그리고, 상기 QoS 관리수단(550)은 상기 큐잉수단(520)의 오버플로우 발생여부에 따라서 스케쥴링 방식을 제어하는 QoS 관리자(551)와, 상기 큐잉수단(520)에 저장된 패킷량이 임계값 이상인지를 비교하여 오버플로우발생여부를 감시하는 버퍼 감시부(552)와, 상기 QoS 관리자(551)에 의해 선택된 스케쥴링 방식으로 동작하도록 상기 스케쥴러(530)를 제어하는 스케쥴러 제어부(553)와, 상기 QoS 관리자(551)의 요구에 따라서 신규 채널을 할당하여 동적 대역폭을 제어하는 동적대역 제어부(554)와, 상기 출력수단(540)의 포워딩 패킷에 대한 출력 포트 선택을 제어하는 채널 제어부(555)를 포함하여 이루어진다.

상기와 같은 구성에 있어서, OLT나 ONT로 유입 되는 트래픽이 패킷 단위로 구성되어 상기 도 5에 보인 스케쥴링 장치로 입력된다.

상기 분류기(511)는 상기 데이터베이스(513)를 룩업하여 알아낸 목적 집선기(Aggregator)에 대응하는 버퍼(522~524)로 입력 패킷을 전달한다.

상기 큐잉수단(520)의 버퍼(522~524)에서는 일차로 패킷의 속성을 분류하여 각 분류별 우선 순위에 맞추어 패킷을 클래스 버퍼(522~524)에 FIFO 방식으로 관리한다.

이때, 상기 클래스 버퍼(522~524)들의 상태는 버퍼감시부(552)에 의하여 계속적으로 모니터링되며, 패킷의 분류 및 스케쥴링을 관리하는 QoS 관리자(551)는 분류된 패킷을 해당 집선기에 배정된 출력포트로 포워딩하기 위해, 스케쥴러 제어부(553)와 동적대역 제어부(554) 및 채널 제어부(555)를 제어한다.

이상과 같이 구성된 본 발명에 의한 스케쥴링 장치에서 이루어지는 본 발명에 의한 스케쥴링 방법을 도 6 및 도 7을 참조하여 이하에 설명한다.

도 6은 본 발명에 의한 스케쥴링 절차에 의해 패킷이 처리되어 전달되는 과정을 나타낸 모식도이고, 도 7은 본 발명에 의한 스케쥴링 방법을 순차적으로 나타낸 플로우챠트이다.

패킷이 수신되면(710), 목적지에 대응하는 집선기(Aggregator)가 결정되고, 상기 분류기(511)에 의하여 서비스 속성에 따른 우선순위별로 분류되어 큐잉수단(520)의 대응하는 클래스 버퍼(522~524)에 쌓이게 된다(720).

이와 같이, 패킷을 저장하는 클래스 버퍼(522~524)들의 상태는 패킷이 유입될때마다 상기 버퍼감시부(552)에 의하여 모니터 되고 있으며, 상기 클래스 버퍼(522~524)에 쌓인 데이터 패킷의 양이 기 설정된 임계값을 초과 하지 않는 범위에서 스케줄러(530)에 의해, 해당 클래스 버퍼(522~524)에서 선택 인출된다(730).

즉, 상기 버퍼감시부(552)의 감시결과, 클래스버퍼(522~524)로 유입된 패킷의 양이, 현재의 대역폭에서 충분히 수용할 수 있는 범위에 있다고 판단되면, 즉, 상기 클래스버퍼(522~524)에 유입된 패킷량이 상기 기설정된 임계값을 초과하지 않으며(731), 상기 QoS 관리자(551)에 의해 FCFS 스케쥴링 방식이 채택되고, 이에 스케쥴러(530)가 FCFS 방식에 의해 패킷을 선택한다(732).

앞서 설명한 바와 같이, FCFS 방식이 플로우(Flow)의 특성을 고려하지 못한다는 단점이 있지만, 대역폭이 충분히 보장이 되어 있는 상황에서는 WFQ방식보다 지연 효과를 줄일 수 있고, 공정한 최선 노력 전송(Best Effort) 서비스를 충분히 제공할 수 있다. 여기서, 각 QoS 방안별로 버퍼를 따로 구성할 경우 메모리의 낭비가 심하고, 동적 QoS를 위한 처리 절차가 복잡해지기 때문에, QoS 방안이 다르더라도 클래스 버퍼(522~524)를 그대로 이용하게 된다.

상기 스케쥴러(530)는 FCFS 방식에 의한 스케쥴링 처리시, 각 클래스 버퍼(522~524)에 처음으로 유입된 패킷을 상호 비교하여, 가장 작은 타임 스탬프(TimeStamp) 값을 갖는 패킷을 선택한다.

상기와 같이, 스케쥴러(530)에 의하여 서비스하고자 하는 패킷이 선택되면, 해당 패킷의 플로우를 분류한다(740). 여기서, 플로우(Flow)를 분류하는 이유는 실시간 서비스와 같은 확실한 대역을 보장 받고자 하는 최우선 처리 패킷과 같은 경우, 플로우별로 대역을 보장하기 위해서이고, 또한, 다중-채널 전송에서 발생할 수 있는 패킷의 Mis-ordering을 최소화하기 위해서 컨버세이션(Conversation)별로 동 일 채널을 사용하기 위해서이다.

상기와 같이, 플로우 분류가 끝나면, 상기 분류된 플로우의 정의 또한 순환 순서방식(round robin)에 의하여 최종적으로 출력되어야 하는 출력포트(port1~portN)를 결정한다(750). 이는, 동일 목적지에 대하여 다중-채널 경로를 갖는 환경에서 단순히 패킷을 선택하고, 패킷의 플로우를 결정하는 것 뿐만 아니라, 채널을 선택하여 선택된 채널로 패킷을 전송하여야 하기 때문이다.

이때, 앞에서 분류한 플로우에 따라서, 이미 포트가 선택되어 있는 플로우라면 해당 포트를 선택하면 된다. 반대로, 상기 분류된 플로우에서 플로우와 포트와의 관계가 정의가 되어 있지 않았거나, 이미 에이징(Aging) 되어 있는 경우에는 순환처리방식으로 출력포트(Port1~PortN)를 선택하여 새로운 플로우와 선택된 포트와의 관계를 기록하고, 에이징되어 사라지기 전에 같은 플로우가 오면 정의된 포트로 포워딩한다(760).

이상은 할당된 대역폭에서 유입된 패킷을 수용할 수 있는 정상적인 상태에서의 처리이다.

그리고, 상기 버퍼감시부(552)에서 특정 클래스 버퍼(522~524)의 패킷량이 임계값을 초과하여, 현재 할당된 대역폭으로는 수용이 불가능하다고 판단되면, 상기 QoS 관리자(551)는 최우선적으로 동적대역 제어부(554)에 새로운 채널 할당을 요구한다(733).

상기 요구가 동적대역 제어부(554)를 통해서 받아들여, 새로운 채널의 추가를 통해 대역이 확보 되면, 채널제어부(555)에 의해 새로 추가된 채널을 해당 집선 기, 즉, 패킷량이 임계값을 넘긴 클래스버퍼(522~524)의 포트로 결합시켜, 새로운 포트 맵(Port-Map)이 구성 된다.

그 다음의 절차는 앞서 설명한 바와 마찬가지로, 스케쥴러(530)에 의해서, FCFS 방식에 의하여 다수 클래스 버퍼(522~524)에서 순차적 패킷이 선택되고(732), 해당 패킷의 플로우를 분류하여, 출력포트를 선택한 후, 선택된 출력포트로 포워딩시킨다(740~760).

그런데, 상기 버퍼 감시부(552)에 의해 오버플로우가 감시되어, 동적대역제어부(554)로 새로운 채널 할당을 요구하였지만, 상기 동적 대역 제어부(554)에서 더 채널을 할당할 수 없는 경우, 현재 할당되어 있는 대역을 가지고 서비스를 하여야 하기 때문에, 데이터의 유실이나 지연 현상이 발생할 수 있다.

이때 상기 클래스 버퍼(522~524)에 저장된 패킷은 앞서 분류기(511)의 서비스 분류를 통하여 이미 우선순위가 가려진 상태이므로, 상기 QoS관리자(551)는 WFQ 방식으로 스케쥴링 하도록 스케쥴러 제어부(553)에 지시하고, 이에, 상기 스케쥴러(530)는 다수 클래스 버퍼(522~524)에 기할당된 가중치에 따라서, WFQ방식으로 패킷을 선택한다(735).

상기 WFQ 방식은 공정한 방식인 반면에 지연에 민감한 실시간성 서비스의 처리에 있어서 지연이나 지터 지연을 발생시킬 여지가 있다.

따라서, 본 발명에서는 이러한 실시간성 서비스를 보장하기 위해서 출력 포트를 서비스별로 분류하여 할당한다(736).

예를 들어, 고정 전송속도 서비스(Constant Bit Rate, CBR)에 의한 고정 대 역을 항상 요구하는 음성이나 영상 서비스 같은 경우, 최상위의 우선순위를 가지며, WFQ 방식을 사용하여 확실한 서비스의 보장이 어렵다고 판단이 되면, 출력포트 그룹의 특정 포트를 상기 CBR 포트로 지정하고, CBR로 분류된 서비스는 해당 포트로 항상 포워딩되도록 한다. 그리고, 기타 하위 우선순위를 갖는 무지정 전송속도 서비스(Unspecified Bit Rate, UBR)로 분류된 서비스는 BE(Best Effort) 포트로 지정이 되어 있는 채널에 대응하는 출력포트 중에서 순환 처리 방식(Round-Robin 방식)으로 선택하여 포워딩시키게 한다.

이 때, 상기 클래스 버퍼(522~524)의 상태에 따라서 출력포트를 동적으로 분류 및 설정할 수 있다.

따라서, 패킷이 선택되면, 해당 패킷의 플로우를 분류하고, 상기 플로우에 따라서 해당하는 출력 포트를 선택하여, 해당 패킷을 포워딩시킨다(740~760).

도 6에 도시된 예를 들면, 제1 클래스 버퍼(632)는 최상부의 출력포트에 고정 할당되어, 제1클래스버퍼(632)에 유입된 패킷은 순서대로 최상부의 출력링크로 인가되고, 제2클래스버퍼(631)와 제3클래스버퍼(630)에 유입된 패킷은 UBR 서비스로 분류되어, 대응하는 두번째 출력포트와 세번째 출력포트에 순환처리방식에 의하여 선택적으로 출력된다.

상술한 바에 의하면, 본 발명은 다중 채널을 통하여 출력 대역의 변경이 가능한 WDM/SCM-PON 망과 같은 동적 다중 채널 환경에서, 대역의 동적인 변경에 따라 서 서비스에 따른 대역 보장을 통하여 서비스별 요구되는 QoS를 만족시킬 수 있는 효과가 있으며, 패킷 유입량에 따라서 스케줄링 기법을 달리함으로서 트래픽의 유형에 따른 장치의 자원을 최소화 하고, 대역을 보장할 수 없는 상황에서도 출력 대역의 최우선 서비스를 보장하기 위한 전용채널을 설정함으로서 폭주하는 데이터의 유입이 있는 상황에서도 CBR 서비스는 확실히 보장할 수 있는 우수한 효과가 있다.

Claims

다중 채널에 각각 연결되는 다수의 출력포트를 구비한 종단 장치에서 이루어지는 동적 다중 채널 환경에서의 스케쥴링 방법에 있어서,

상기 종단장치로 입력되는 트래픽을 패킷단위로 수신하는 단계;

상기 수신된 패킷을 서비스 클래스별로 분류하여 저장하는 단계;

상기 저장된 서비스 클래스별 패킷량이 기설정된 임계값을 초과하는 지를 감시하는 단계;

상기 감시결과, 어떤 서비스 클래스의 패킷량도 임계값을 초과하지 않으면, 선착순 처리방식(FCFS)에 의해 가장 먼저 수신된 패킷순으로 포워딩할 패킷을 선택하고, 소정 서비스 클래스의 패킷량이 임계값을 초과하면, 가중치 공정 대기열 처리 방식(WFQ)에 의하여 서비스 클래스별로 일정 비율로 포워딩할 패킷을 선택하는 단계;

상기 단계에서 선택된 패킷의 서비스클래스별로 전송될 플로우를 분류하는 단계;

상기 단계에서 분류된 플로우에 따라서 선택된 패킷을 포워딩할 출력포트를 선택하는 단계; 및

상기 선택된 출력포트로 상기 선택된 패킷을 포워딩하는 단계로 이루어지는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 방법.
제 1 항에 있어서, 상기 방법은

상기 감시결과 소정 서비스 클래스의 패킷량이 임계값을 초과하면, 패킷의 선택전에 출력포트에 신규 채널을 추가할 수 있는지를 판단하는 단계; 및

상기 판단결과 채널 추가가 가능하면, 신규 채널을 추가한 후 해당 채널을 소정의 출력포트와 결합시키는 단계를 더 포함하는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 방법.
제 1 항에 있어서, 상기 방법은

상기 서비스 클래스별 플로우를 분류하는 단계에서, 다중 채널에 각각 대응하는 출력포트중 소정 출력 포트는 고정 속도 서비스(CBR)용으로 설정하고, 최상위 우선순위를 갖는 서비스 클래스의 패킷은 상기 고정 속도 서비스(CBR)용 출력포트로 포워딩되도록 정의하는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 방법.
제 1 항에 있어서, 상기 방법은

상기 서비스 클래스별 플로우를 분류하는 단계에서,

다중 채널에 각각 대응하는 다수의 출력 포트중 임의의 출력포트에 대해서, 무지정 전송 속도 서비스(UBR)용으로 정의하고, 하위 우선순위의 서비스 클래스로 분류된 패킷은 상기 무지정 전송속도 서비스(UBR)용 출력 포트로 포워딩되도록 정의하는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 방법.
제 4 항에 있어서, 상기 방법은

상기 출력 포트 선택 단계에서 상기 무지정 전송속도 서비스(UBR)용 출력포트들중 하나를 순환 처리 방식(Round-robin)에 의하여 선택되는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 방법.
제 1 항에 있어서, 상기 방법은

선착순 처리 방식(FCFS)에 의한 패킷 선택시, 각 서비스 클래스별로 처음 유입된 패킷들의 타임 스탬프(TimeStamp)를 비교하여, 가장 작은 타임 스탬프를 갖는 패킷을 포워딩할 패킷으로 선택하는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 방법.
다중 채널에 각각 연결되는 다수의 출력포트를 구비한 종단 장치에 구비되는 동적 다중 채널 환경에서의 스케쥴링 장치에 있어서,

트래픽을 패킷단위로 입력받아, 서비스 클래스별로 분류하는 패킷 분류 수단;

상기 패킷 분류 수단에 의해 분류된 각 서비스 속성별 패킷을 저장하는 큐잉 수단;

상기 큐잉 수단에 저장된 다수 패킷들을 선착순 처리방식(FCFS) 또는 가중치 공정 대기열 처리방식(WFQ)에 따라서 선택하여 포워딩시키는 스케쥴링 수단;

상기 스케쥴링 수단에서 선택된 패킷을 다중채널에 각각 대응하는 다수의 출력포트중 선택된 출력포트로 인가하는 출력 수단; 및

상기 큐잉수단으로 유입된 서비스 클래스별 패킷량이 임계값을 초과하는지를 감시하여, 임계값 초과여부에 따라서 상기 스케쥴링 수단이 선착순 처리방식 또는 가중치 공정 대기열 처리방식중 하나로 동작하도록 제어하는 QoS 관리 수단을 포함하여 이루어지는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 장치.
제 7 항에 있어서, 상기 패킷 분류 수단은

입력된 패킷을 서비스 클래스별로 분류하여 큐잉수단으로 인가하는 패킷분류기;

계층별 어드레스 룩업 테이블이 저장된 데이터베이스; 및

입력된 패킷의 목적지 MAC 주소에 따라 상기 데이터베이스를 룩업하여 상기 패킷 분류기를 제어하는 MAC제어기로 이루어지는 것을 특징으로 하는 동적 다중 채 널 환경에서의 스케쥴링 장치.
제 7 항에 있어서, 상기 큐잉 수단은

각각 서비스 속성별로 할당되어 상기 패킷 분류 수단으로부터 분류된 대응하는 패킷을 순서대로 저장하는 다수의 클래스 버퍼; 및

제어용 패킷용으로 할당되어 상기 패킷 분류 수단으로부터 분류된 제어용 패킷을 저장하는 콘트롤 버퍼로 이루어지는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 장치.
제 7 항에 있어서, 상기 출력수단은

다중 채널에 각각 대응하는 다수의 출력 포트와 상기 스케쥴링 수단의 출력을 각각 연결하는 다수의 스위칭수단을 포함하고,

상기 다수 스위칭수단을 온/오프함으로서 상기 스케쥴링 수단의 출력 패킷을 선택된 출력포트로 포워딩처리하는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 장치.
제 7 항에 있어서, 상기 QoS 관리수단은

상기 큐잉수단에 저장된 패킷량이 임계값을 초과하는지 여부에 따라서 스케쥴링 방식을 제어하는 QoS 관리자;

상기 큐잉수단에 저장된 패킷량이 임계값을 초과하는지를 감시하는 버퍼 감시부; 및

상기 QoS 관리자에 의해 선택된 스케쥴링 방식으로 동작하도록 상기 스케쥴링 수단을 제어하는 스케쥴러 제어부를 포함하여 이루어지는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 장치.
제 11 항에 있어서, 상기 QoS 관리수단은

상기 QoS 관리자의 요구에 따라서 신규 채널을 할당하여 동적 대역폭을 제어하는 동적대역 제어부; 및

상기 동적대역 제어부의 제어에 따라서 출력수단의 출력포트선택을 제어하는 채널 제어부를 더 포함하여,

상기 QoS관리자가 큐잉수단의 패킷량이 임계값을 초과할때, 상기 동적대역 제어부로 신규 채널 추가를 요구하고, 그 수행결과에 따라서 스케쥴링 방식을 결정하도록 하는 것을 특징으로 하는 동적 다중 채널 환경에서의 스케쥴링 장치.