KR100542433B1

KR100542433B1 - 패킷 스케줄링 장치 및 패킷 스케줄링 방법

Info

Publication number: KR100542433B1
Application number: KR1020030037146A
Authority: KR
Inventors: 김성희; 김영섭
Original assignee: 한국전자통신연구원
Priority date: 2003-06-10
Filing date: 2003-06-10
Publication date: 2006-01-11
Anticipated expiration: 2023-06-10
Also published as: KR20040105973A

Abstract

본 발명은 패킷 스케줄링 장치 및 패킷 스케줄링 방법에 관한 것이다.

본 발명의 실시예에 따른 패킷 스케줄러는 외부로부터 입력되어 저장하고자 하는 패킷이 해당 세션의 첫 번째 패킷이면, 그 해당 세션의 서비스 레이트(service rate)를 참조하여 출력 시간을 계산한 후, 계산된 출력 시간을 본 발명의 실시예에 따른 캘린더 메모리에 등록한다. 그 후, 패킷 스케줄러는 단일 블록 크기의 레지스터(register)와 별도의 제어 메모리 및 캘린더 메모리를 이용하여 출력하고자 하는 특정 패킷들을 검색해서 순차적으로 출력한다.

이를 통하여, 계산된 출력 시간에 따른 패킷의 정렬 및 출력 패킷 검색시 소요되는 하드웨어 논리회로의 양을 줄일 수 있을 뿐만 아니라, 단시간 내에 정렬 및 출력 패킷 검색을 수행할 수 있다.

패킷 스케줄러, 캘린더 메모리, 레지스터, 출력 시간 계산, 정렬, 등록/출력

Description

패킷 스케줄링 장치 및 패킷 스케줄링 방법{PACKET SCHEDULING DEVICE AND PACKET SCHEDULING METHOD}

도 1은 본 발명의 실시예에 따른 패킷 스케줄링 장치 구성을 세부적으로 도시한 도면이다.

도 2는 도 1에 도시된 제어 메모리의 구성을 세부적으로 도시한 도면이다.

도 3은 도 2에 도시된 제어 메모리로부터 읽어들이는 세션 정보를 도시한 도면이다.

도 4는 본 발명의 실시예에 따른 캘린더 메모리의 구성을 도시한 도면이다.

도 5는 본 발명의 실시예에 따른 패킷 스케줄러의 패킷 수신 과정을 순차적으로 도시한 흐름도이다.

도 6은 본 발명의 실시예에 따른 패킷 스케줄러의 출력 패킷 처리 과정을 순차적으로 도시한 흐름도이다.

도 7은 본 발명의 실시예에 따라 새로운 세션을 캘린더 메모리에 등록하는 과정을 개념적으로 도시한 도면이다.

도 8a와 도 8b는 도 7에 따른 세션 등록 과정을 순차적으로 도시한 흐름도이다.

도 9는 본 발명의 실시예에 따른 출력 세션 검색 과정을 개념적으로 도시한 도면이다.

도 10a와 도 10b는 도 9에 따른 출력 세션 검색 과정을 순차적으로 도시한 흐름도이다.

본 발명은 패킷 스케줄링 장치 및 패킷 스케줄링 방법에 관한 것으로, 보다 상세하게는, 외부로부터 입력되는 패킷을 저장하여 저장된 패킷의 출력을 스케줄링하는 패킷 스케줄링 장치 및 패킷 스케줄링 방법에 관한 것이다.

근래 들어, 유한한 망 자원을 효율적으로 활용하기 위한 방안으로서, 망 자원을 다수의 사용자들에게 공평하게 분배하는 패킷 스케줄러(Packet Scheduler)에 대한 연구가 활발히 진행되고 있다. 즉, 다양한 서비스 품질을 요구하는 멀티미디어 서비스가 실현됨에 따라, 제한된 망 자원을 효율적으로 이용할 수 있는 패킷 스케줄러의 출력 링크의 대역폭을 공정하게 할당하기 위한 여러 가지 방법들이 제안되고 있다.

제안된 방법 중에서, 입력되는 패킷의 길이 및 이전에 해당 세션(session)이 시스템으로부터 받은 서비스의 양을 계산하여 해당 세션에 대기 중인 패킷의 출력 시간을 계산한 후, 계산된 각 세션의 출력 시간을 정렬하여 가장 출력 시간이 작은 세션의 패킷을 선택하여 출력하는 것이 가장 일반적이다.

그런데, 통신망의 속도가 빨라지고 세션의 수가 많아짐에 따라, 이러한 일반 적인 방법을 사용하는 기존의 패킷 스케줄러는 실시간으로 패킷의 출력 시간을 계산하고, 그 계산된 출력 시간에 따라 세션을 정렬할 수 있는 하드웨어를 구비해야만 한다. 뿐만 아니라, 이러한 기존의 패킷 스케줄러는 구비된 하드웨어를 통한 패킷의 출력 시간 계산시, 소정의 계산 방식과 정렬 방법이 필요하다.

이러한 패킷의 출력 시간 계산 및 세션 정렬을 통한 망 자원의 공평한 분배 방법 중의 하나가 바로 페어 큐잉(Fair Queuing)인데, 이러한 페어 큐잉에 대한 연구는 GPS(Generalized Processor Sharing, 이하 'GPS' 라 함)를 시작으로 하여, WFQ(Weighted Fair Queuing, 이하 'WFQ' 라 함) 및 SCFQ(Self Clocked Fair Queuing, 이하 'SCFQ' 라 함) 등과 같은 많은 결과들이 나오고 있다.

이중, GPS는 패킷 서비스 시스템을 유체 흐름으로 해석하고 적용하기 위한 수학적 접근 방법을 이용하고 있는데, 패킷을 무한히 작게 나누어 유체 흐름의 이론을 적용한다는 것은 계산량이 많기 때문에, GPS는 현실적으로 실현이 불가능한 것으로 판단되고 있다.

이에 따라, 하드웨어 논리 회로를 통한 실시간 계산 및 이를 통한 실제 구현이 가능하도록 접근한 페어 큐잉 알고리즘들이 제안되었는데, 이것이 바로 앞서 언급한 SCFQ나 WFQ 등이다.

이러한 페어 큐잉 알고리즘과 관련된 논문의 내용을 살펴보면, SCFQ와 WFQ 등은 계산량이 적고, GPS와 비교시 성능 저하가 없다는 것을 확인하였다고 언급하고 있다. 또한, 논문에는 SCFQ와 WFQ 등이 입력되는 패킷의 양에 따라 입력 패킷이 언제 출력되어야만 유한한 망 자원이 다수의 사용자들에게 공평하게 분배되느냐를 계산한 후, 이에 기초하여 패킷의 출력 순서를 정렬하여 해당 패킷을 망에 전송한다고 언급하고 있다.

그러나, 효율적인 시스템 실현을 위해, 제안된 페어 큐잉 알고리즘을 실제적으로 어떻게 적용할 것인가에 관한 연구가 필요한 실정이다. 주 연구 대상으로는, 예를 들어 입력 패킷의 출력 시간을 하드웨어 논리 회로를 이용하여 계산하는 방법이나, 또는 많은 양의 패킷을 저장하고 그 출력 순서에 따라 패킷의 출력 순서를 정렬하는 방법 등을 들 수 있다. 이 중, 패킷을 출력 순서에 따라 정렬하는 것을 하드웨어로 구현하기 위한 방법으로는, 캘린더 큐(calendar queue)를 사용하거나 또는 서비스 클래스(service class)와 서비스 레이트(service rate)에 따라 몇 개의 그룹으로 묶어서 처리하는 방식 등이 있다.

먼저, 캘린더 큐를 사용하여 패킷을 출력 순서에 따라 정렬하는 방식이란, 캘린더 메모리(calendar memory)에 패킷의 출력 타임 슬롯에 출력될 패킷이 있음을 표시하고, 패킷 버퍼에 이미 저장된 패킷의 포인터를 저장해 두었다가 해당 타임 슬롯(time slot)이 되었을 때 패킷을 출력시키는 것을 말한다.

그런데, 이러한 캘린더 큐를 사용한 정렬 방식은 캘린더 메모리에 충돌이 발생할 경우, 이를 해결하기 위해 비어 있는 타임 슬롯을 찾아내야만 하는데, 그 찾아내는 방법에 따라서 서비스 성능에 큰 영향을 주게 된다. 그래서, 이러한 충돌 을 사전에 방지하기 위해, 캘린더 메모리에 버킷 큐를 추가한 후, FIFO(First-In First-Out : 선입선출) 형태로 구현하여 충돌을 방지하고 패킷을 스케줄링하는 알고리즘이 제안된 바 있다.

또한, 충돌 방지를 위한 관련 기술로는 특허권자가 한국 전기 통신 공사 및 한국 전자 통신 연구원인 [명칭 : 버킷 칼렌다를 이용한 셀 스페이서 및 그 제어 방법, 등록번호 : 100276079호, 등록년도 : 2000년]의 특허가 있는데, 이 역시 캘린더 메모리의 충돌을 회피하기 위해 각 슬롯에 버킷이라는 별도의 메모리를 둔다. 하지만, 이러한 방법은 캘린더 메모리가 작을 경우에 적용되는 방법으로서, 캘린더 메모리를 확장할 경우, 메모리가 너무 많이 소요된다는 단점이 있다.

한편, 기존의 패킷 스케줄러를 FPGA(Field Programmable Gate Array)나 ASIC(Application Specific Integrated Circuit)으로 구현하고자 할 경우, 캘린더 메모리를 메모리 소자로 이용하기도 하는데, 이때 타임 슬롯 하나 하나를 검색할 때마다 메모리 소자로부터 해당 데이터를 읽어 와야만 한다. 이는 곧 검색하는 시간 외에 메모리 소자로부터 데이터를 읽어오는 시간이 추가되어 빠른 검색을 수행할 수 없게 한다.

이로 인해, 캘린더 메모리를 메모리 소자를 사용하지 않고 레지스터(register)를 이용하여 검색을 수행하기도 하는데, 이는 빠른 시간 안에 캘린더 메모리를 검색할 수 있도록 한다.

그러나, 레지스터를 사용하게 되면 하나의 레지스터가 10개의 논리 소자로 구성된다고 가정할 경우, 캘린더 메모리를 구성 하는데만 640K(-캘린더 메모리의 용량이 64Kbit일 경우-)의 논리 소자가 소요된다.

따라서, 캘린더 메모리의 구성 요소인 논리 소자의 양을 줄임과 동시에, 앞서 언급한 캘린더 메모리에서 유휴한 타임 슬롯을 검색하는데 소요되는 시간을 줄 일 수 있는 방안이 절실히 요구되고 있는 실정이다.

본 발명이 이루고자 하는 기술적 과제는 이러한 문제점을 해결하기 위한 것으로서, 외부로부터 입력되는 다수의 패킷을 단일 블록 크기의 레지스터와 내장 메모리를 공동으로 사용하여 계산된 출력 시간에 따라 정렬한 후 출력시킴으로써, 정렬 및 출력 패킷 검색시 소요되는 하드웨어 논리회로의 양을 줄일 수 있을 뿐만 아니라, 단시간 내에 정렬 및 패킷 출력을 수행할 수 있는 캘린더 메모리를 이용한 패킷 스케줄러와 그 구동 방법을 제공하기 위한 것이다.

이러한 목적을 달성하기 위한 본 발명의 특징에 따른 패킷 스케줄링 장치는, 외부로부터 입력되는 패킷을 저장하여 저장된 패킷의 출력을 스케줄링하는 패킷 스케줄링 장치로서, 저장되는 패킷의 세션(session)이 등록되면, 세션 등록에 따른 각 타임 슬롯의 유휴 및 점유 타임 슬롯 주소를 저장하는 캘린더 메모리, 해당 세션의 서비스 레이트(service rate)를 참고로 각 패킷의 출력시간을 계산하고, 상기 캘린더 메모리를 단일 블록 레지스터에 로딩하여, 유휴 타임 슬롯을 검색하고, 계산된 출력시간 및 유휴 타임 슬롯이 있는 경우의 해당 패킷 세션을 상기 캘린더 메모리에 등록하고, 유휴 타임 슬롯에 해당 출력 패킷을 출력하도록 하는 캘린더 메모리 제어부를 포함하는 패킷 스케줄러를 포함한다.

이때, 본 발명의 특징에 따른 캘린더 메모리(calendar memory)는, 일정한 구간으로 나뉘어져 적어도 한 개 이상의 2차원 블록 배열을 갖는 블록 캘린더 메모리; 상기 각 블록의 첫 번째 유휴 타임 슬롯의 위치를 나타내는 유휴 어드레스 메모리; 해당 블록에 유휴 타임 슬롯이 있음을 나타내는 유휴 플래그; 상기 각 블록의 첫 번째 점유 타임 슬롯의 주소를 저장하는 점유 어드레스 메모리; 및 상기 해당 블록에 점유된 타임 슬롯이 있음을 나타내는 점유 플래그를 포함하는 것을 특징으로 한다.

또한, 본 발명의 특징에 따른 패킷 스케줄링 방법은, 외부로부터 입력되는 패킷을 저장하여 저장된 패킷 출력을 스케줄링하는 패킷 스케줄링 방법으로서, a)저장된 패킷에 대해 해당 세션(session)의 서비스 레이트(service rate)를 참조하여 출력 시간을 계산한 후, 캘린더 메모리(calender memory)를 단일 블록 레지스터에 로딩(loading)하여 로딩된 캘린더 메모리에서 유휴 타임 슬롯을 검색하여, 상기 계산된 출력 시간 및 유휴 타임 슬롯이 있는 경우 해당 패킷 세션을 캘린더 메모리에 등록하는 단계; b)상기 등록에 따른 캘린더 메모리의 각 타임 슬롯의 유휴 및 점유 타임 슬롯 주소를 상기 캘린더 메모리에 저장하는 단계; c)상기 캘린더 메모리를 단일 블록의 레지스터에 로딩하여 출력하고자 하는 패킷을 검색하는 단계; 및 d)상기 검색된 출력 패킷의 세션 아이디(ID)를 이용하여 저장된 출력 패킷을 읽어와 출력시키는 단계를 포함한다.

삭제

아래에서는 첨부한 도면을 참고로 하여 본 발명의 실시예에 대하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였다. 명세서 전체를 통하여 유사한 부분에 대해서는 동일한 도면 부호를 붙였다.

도 1은 본 발명의 실시예에 따른 캘린더 메모리를 이용한 패킷 스케줄러의 구조를 세부적으로 도시한 도면이다.

도시되어 있듯이, 본 발명의 실시예에 따른 패킷 스케줄러(100)는 입력 패킷 처리부(110)와 캘린더 메모리 제어부(120), 출력 패킷 처리부(130) 및 캘린더 메모리(140)를 포함하고 있으며, 외부의 패킷 버퍼(150)와 제어 메모리(160)를 더 포함한다. 이때, 패킷 버퍼(150)와 제어 메모리(160)는 상용 메모리 소자를 이용해 구성할 수 있다. 그리고, 본 발명의 실시예에 따른 패킷 스케줄러(100)는 FPGA(Field Programmable Gate Array : 필드 프로그래머블 게이트 어레이, 이하'FPGA'라 함) 또는 ASIC(Application Specific Integrated Circuit : 주문형 반도체, 이하 ASIC라 함)을 이용하여 하나의 소자로 구성될 수 있다.

도 1에서, 입력 패킷 처리부(110)는 외부의 입력 링크(10)를 통해 패킷을 수신하면, 수신한 패킷의 세션(session) 식별자를 이용하여 제어 메모리(160)로부터 해당 패킷의 세션 정보를 읽어온다. 그리고, 입력 패킷 처리부(110)는 제어 메모리(160)로부터 유휴 버퍼 포인터를 읽어와 유휴 버퍼 포인터가 가리키는 패킷 버퍼(150)에 해당 패킷을 저장한다.

도 2는 도 1에 도시된 제어 메모리의 구성을 도시한 도면이며, 도 3은 도 2에 도시된 제어 메모리로부터 읽어들이는 세션 정보를 도시한 도면이다.

먼저, 도 2에 도시되어 있듯이 본 발명의 실시예에 따른 제어 메모리(160)는 유휴 버퍼 포인터(161)와 세션 정보 메모리(162), 캘린더 정보 메모리(163) 및 버퍼 포인터(164)를 포함한다.

그리고, 이러한 구성의 제어 메모리(160) 중 세션 정보 메모리(162)부터 읽어들이는 세션 정보는 첨부한 도 3과 같은데, 그 구성은 서비스 레이트(165)와 세션의 첫 번째 패킷이 저장되어 있는 패킷 버퍼 포인터를 가리키는 시작 포인터(166), 마지막 패킷이 저장되어 있는 버퍼 포인터를 나타내는 끝 포인터(167) 및, 세션의 큐에 저장되어 있는 패킷의 수를 나타내는 패킷 카운터(168)를 포함한다.

한편, 입력 패킷 처리부(110)가 해당 패킷을 패킷 버퍼(150)에 저장하는 경 우에는 64바이트의 크기로 잘라서 저장하는데, 만일 해당 패킷이 64바이트보다 큰 경우에는 유휴 버퍼 포인터를 64바이트 단위별로 읽어 와서 이를 참조하여 패킷 버퍼(150)에 해당 패킷을 저장한다.

그리고, 입력 패킷 처리부(110)는 링크 리스트를 구성하기 위해 해당 패킷이 저장된 패킷 버퍼(150)의 포인터가 가리키는 버퍼 포인터(164)에 다음 패킷이 저장된 포인터를 저장함으로써, 가상의 세션 큐(session queue)를 구성한다. 이처럼, 입력 패킷 처리부(110)는 패킷을 저장한 후, 패킷 카운터(168)를 증가시키고, 패킷의 최종 데이터가 저장된 버퍼 포인터를 끝 포인터(167)에 기록한다.

그런데, 이러한 패킷 저장에 있어, 저장하고자 하는 패킷이 특정 세션의 첫 번째 패킷이면, 입력 패킷 처리부(100)는 해당 세션의 서비스 레이트(165)를 캘린더 메모리 제어부(120)로 전달한다.

그러면 캘린더 메모리 제어부(120)는 수신된 서비스 레이트(165)를 참조하여 해당 패킷의 출력 시간을 계산한 후, 계산한 출력 시간을 본 발명의 실시예에 따른 캘린더 메모리(140)에 등록한다. 이후, 캘린더 메모리 제어부(120)는 적어도 한 개 이상의 세션이 등록되어 있는 캘린더 메모리(140)에서 출력하고자 하는 세션의 특정 패킷을 단시간 내에 검색하여 출력하도록 하는데, 이때 캘린더 메모리 제어부 (120)는 본 발명의 실시예에 따른 캘린더 메모리(140)와 단일 블록 크기의 레지스터(register)를 이용하여 단시간 내에 검색한다. 이러한 캘린더 메모리 제어부 (120)의 동작 과정은 첨부된 도면을 통해 추후 자세히 언급하기로 한다.

다음으로, 출력 패킷 처리부(130)는 캘린더 메모리 제어부(120)로부터 전달 되는 세션 식별자를 통해 해당 세션의 정보를 제어 메모리(160)에서 읽어 들인 후, 읽어 들인 세션 정보에 기초하여 해당 패킷을 패킷 버퍼(150)에서 읽어와 출력 링크(20)로 출력시킨다.

참고로, 제어 메모리(160)는 적어도 3개의 메모리 페이지 이상(실시예에서는 4개의 메모리 페이지 구성, 도 2에 도시함)으로 구성된 상용 SDRAM(Synchronous DRAM)을 사용하여 구성하는데, 이때 메모리의 첫 번째 페이지는 패킷 버퍼(150)에 비어 있는 패킷 버퍼 블록의 어드레스를 저장하는 유휴 버퍼 포인터(161)로 구성되어 있으며, 두 번째 페이지는 세션 정보를 저장하는 세션 정보 메모리(162), 세 번째 페이지는 캘린더 메모리에 등록된 세션 정보를 관리하는 캘린더 정보 메모리(163) 및, 네 번째 페이지는 패킷 버퍼(150)에 저장된 패킷의 링크 리스트를 구성하기 위한 버퍼 포인터(164)로 구성되어 있다.

그러면, 이러한 구조로 이루어진 패킷 스케줄러의 동작 과정에 대해 언급하기에 앞서, 본 발명의 실시예에 따른 캘린더 메모리(140)에 대해 첨부된 도면을 통해 자세히 알아보면 다음과 같다.

그런데 이하 본 발명의 실시예에서는 검색 시간을 줄임과 동시에 논리 소자의 양을 줄이기 위한 방안으로서, 64Kbit 용량의 캘린더 메모리를 일정 구간으로 나누어 소정 크기의 메모리와 소정 개수의 레지스터로 구현하는 방법을 제시한다.

하지만, 이와 같은 64Kbit 용량의 캘린더 메모리 및 이를 이용한 패킷 스케줄러는 본 발명에 한정되는 것이 아니고, 경우에 따라서는 그 이하 또는 그 이상의 용량을 가진 캘린더 메모리를 구현할 수도 있다.

도 4는 본 발명의 실시예에 따른 캘린더 메모리를 도시한 도면으로서, 도시되어 있듯이 캘린더 메모리(140)는 일정한 구간으로 나뉘어져 2차원 배열을 갖는 블록 캘린더 메모리(block calendar memory, 141)와, 각 블록의 첫 번째 유휴 타임 슬롯의 위치를 나타내는 유휴 어드레스 메모리(Idle address, 142), 해당 블록에 유휴 타임 슬롯이 있음을 나타내는 유휴 플래그(Idle flag, 143), 각 블록의 첫 번째 점유 타임 슬롯의 주소를 저장하기 위한 점유 어드레스 메모리(busy address memory, 144), 해당 블록에 점유된 타임 슬롯이 있음을 나타내는 점유 플래그(busy flag, 145)를 포함한다.

자세히 설명하면, 먼저 블록 캘린더 메모리(141)는 각 블록의 타임 슬롯 상태를 저장하고, 점유 어드레스 메모리(144)는 각 블록의 캘린더 메모리 중, 점유되어 있는 첫 번째 점유 타임 슬롯의 주소를 저장하고, 해당 블록에 점유되어 있는 슬롯이 있으면 점유 메모리(145)의 상태를 '1'로 셋팅한다. 그리고, 유휴 어드레스 메모리(142)는 각 블록의 캘린더 메모리 중에서 첫 번째 유휴 타임 슬롯의 위치를 저장하고, 해당 블록에 유휴 메모리가 있으면 유휴 메모리(143)의 상태를 '1'로 셋팅한다.

이와 같이, 본 발명의 실시예에 따른 캘린더 메모리는 이차원 배열로 정의한 블록 캘린더 메모리(141)에 각 블록의 모든 타임 슬롯 상태를 저장하며, 그 외 다른 메모리(142 내지 145)에는 유휴 타임 슬롯과 점유 타임 슬롯의 위치 및 해당 메모리의 상태를 저장함으로써, 캘린더 메모리 제어부(120)의 출력 패킷의 검색시, 검색 시간을 줄일 수 있도록 한다.

그런데, 이와 같은 기능의 캘린더 메모리(140)는 앞서 언급한 그 구성에서도 알 수 있듯이, 각 타임 슬롯에 등록되어 있는 세션의 아이디(ID, 식별자)를 저장하는 메모리가 포함되어 있지 않다. 따라서, 캘린더 메모리 제어부(120)는 출력하고자 하는 세션이 등록되어 있는 타임 슬롯 번호만을 캘린더 메모리(140)를 이용하여 찾아낸 후, 찾아낸 타임 슬롯에 등록되어 있는 세션의 아이디는 제어 메모리(160)의 캘린더 정보 메모리(163)로부터 읽어온다.

한편, 본 발명의 실시예에 따른 패킷 스케줄러(100)를 앞서 언급한 것과 같이 FPGA나 ASIC로 구현한다면, 메모리 소자를 이용할 경우에는 타임 슬롯 하나 하나를 검색할 때마다 캘린더 메모리에서 읽어 와야 하기 때문에 검색하는 시간 외에 캘린더 메모리로부터 해당 데이터를 읽어오는 시간이 추가로 소요된다.

따라서, 본 발명의 실시예에서는 캘린더 메모리(140) 내의 출력 패킷 검색시, 레지스터로 이루어진 패킷 스케줄러를 사용하고자 하는데, 이 역시 640Kbit 용량의 캘린더 메모리 검색시, 640K의 논리 소자(logic gate)가 사용되어 너무나 많은 논리 소자들을 소비하게 된다.

그래서, 본 발명의 실시예에서는 패킷 스케줄러(100)를 FPGA(또는 ASIC)로 구현하고자 할 경우, 그 FPGA 내의 내장 메모리(Embedded memory)를 캘린더 메모리로 이용하며, 전체 회로 내의 로컬 레지스터(local register) 중, 그 일부인 단일 블록 크기의 레지스터만을 본 발명의 레지스터로 이용한다. 이를 통해, 본 발명의 실시예에서는 적은 개수의 논리 소자만으로도 패킷 스케줄러를 구현할 수 있다.

그러면, 이러한 구조로 이루어진 캘린더 메모리 및 레지스터를 이용한 패킷 스케줄러의 패킷 수신 및 세션 등록, 출력 과정을 첨부된 도면을 통해 자세히 알아보면 다음과 같다.

먼저, 캘린더 메모리 제어부(120)의 패킷 수신 과정에 대해 알아보면, 도 5는 본 발명의 실시예에 따른 패킷 스케줄러의 패킷 수신 과정을 순차적으로 도시한 흐름도이다.

입력 패킷 처리부(110)는 입력 링크(10)를 통해 해당 패킷을 수신(S510)하면, 수신한 패킷을 패킷 버퍼(150) 내의 세션 큐에 저장(S520)하는데, 이때 저장하고자 하는 패킷이 해당 세션의 첫 번째 패킷인지를 확인한다(S530).

확인 결과, 첫 번째 패킷이면, 입력 패킷 처리부(110)는 해당 세션의 서비스 레이트(165)를 캘린더 메모리 제어부(120)로 전달하는데, 캘린더 메모리 제어부(120)는 수신된 서비스 레이트(165)를 참조하여 해당 패킷이 저장되어 있는 세션의 출력 시간을 계산(S540)한 후, 계산된 출력 시간을 캘린더 메모리(140)에 등록한다(S550).

다음으로, 캘린더 메모리에서 출력하고자 하는 패킷을 단 시간 내에 검색하여 출력되도록 하는 과정에 대해 알아본다.

도 6은 본 발명의 실시예에 따른 패킷 스케줄러의 출력 패킷 검색 과정을 순차적으로 도시한 흐름도이다.

도 6에 도시되어 있듯이, 먼저 캘린더 메모리 제어부(120)는 임의의 타임 슬롯에 새로운 패킷을 출력하기 위해 캘린더 메모리(140)를 검색(S610)하는데, 검색시 출력하고자 하는 패킷이 저장되어 있는 출력 세션이 존재하는지를 확인한다(S620). 이때, 캘린더 메모리 제어부(120)는 본 발명의 실시예에 따른 캘린더 메모리(140) 뿐만 아니라, 단일 블록 크기의 레지스터와 캘린더 정보 메모리(163)를 동시에 이용하여 단시간 내에 그 출력 패킷의 존재를 확인한다.

확인 결과, 출력 세션이 존재하지 않으면, 캘린더 메모리 제어부(120)는 해당 타임 슬롯에서는 아무런 조치를 취하지 않고 현재 시간을 한 슬롯 증가(S630)시키는 반면, 검색 결과 출력 세션이 존재하면, 해당 패킷을 출력 링크(20)를 통해 출력되도록 하고, 현재 시간을 해당 패킷의 출력 시간으로 변경한다(S640).

이후, 캘린더 메모리 제어부(120)는 출력시킨 패킷이 해당 세션의 마지막 패킷인지를 확인(S650)한 후, 확인 결과 해당 패킷이 세션의 마지막 패킷이 아닌 경우에는 해당 세션의 출력 시간을 다시 계산(S660)하여 캘린더 메모리(140)에 등록한다(S670).

다음으로, 본 발명의 실시예에 따른 캘린더 메모리에 새로운 세션을 등록하는 과정을 첨부된 도면을 통해 자세히 살펴본다.

도 7은 본 발명의 실시예에 따라 새로운 세션을 캘린더 메모리에 등록하는 과정을 개념적으로 도시한 도면이며, 도 8a와 도 8b는 그러한 과정을 순차적으로 도시한 흐름도이다.

먼저, 새로운 세션을 캘린더 메모리(140)에 등록하고자 할 경우, 캘린더 메모리(140)의 크기가 64Kbit이면, 해당 세션의 출력 시간은 16비트의 이진수로 계산되는데, 캘린더 메모리 제어부(120)는 이 16비트의 타임 슬롯 어드레스를 상위 8비트와 하위 8비트로 나누어, 상위 8비트는 캘린더 메모리(140)의 블록을 나타내는 상위 슬롯 어드레스(Upper Slot Address, 17)에 저장하는 반면, 하위 8비트는 캘린더 메모리 블록 내의 타임 슬롯을 나타내는 하위 슬롯 어드레스(Lower Slot Address, 19)에 저장한다(S801).

이후, 캘린더 메모리 제어부(120)는 상위 슬롯 어드레스(17)가 나타내는 메모리 블록의 256비트를 로컬 레지스터(18)에 로딩(S802)한 후, 하위 슬롯 어드레스(19)를 이용하여 하위 슬롯 어드레스(19) 이후의 타임 슬롯 중에서 유휴 타임 슬롯이 있는지를 검색한다(S803).

이후, 검색 결과 유휴 타임 슬롯이 검색되면, 캘린더 메모리 제어부(120)는 상위 슬롯 어드레스(17)를 SUA(Searched Upper Address, 이하 SUA 라 함)에 저장한 후, SLA(Searched Lower Address, 이하 SLA 라 함)에는 검색된 어드레스를 저장(S804)하는 반면, 검색에 실패한 경우에는 로컬 레지스터(18)에 다시 유휴 플래그 메모리의 내용을 로드한다(S805).

이후, 캘린더 메모리 제어부(120)는 로컬 레지스터의 UA(상위 슬롯 어드레스)+1 번째 비트부터 255번째 비트까지 상태가 '1'인 비트가 있는지를 검색한다(S806). 검색에 성공한 경우에는 SUA에 검색된 어드레스를 저장하고, SLA에는 SUA가 가리키는 유휴 어드레스 메모리(142)의 내용을 저장하는 반면, 검색에 실패한 경우에는 다시 로컬 레지스터의 0번째 비트부터 UA 번째 비트까지 상태가 '1'인 비트가 있는지를 검색한다(S807).

이후, 검색에 성공하면 캘린더 메모리 제어부(120)는 SUA에 검색된 어드레스를 저장하고, SLA에 SUA가 가리키는 유휴 어드레스 메모리(142)의 내용을 저장(S808)하는 반면, 검색에 실패한 경우에는 등록에 실패한 것으로 간주한다(S809). 그런데, 시스템에 동시에 서비스 중인 세션이 64K 이하이면 등록에 실패하는 경우는 대부분 없다.

이후, 캘린더 메모리 제어부(120)는 다시 로컬 레지스터에 SUA가 가리키는 캘린더 메모리의 내용을 저장(S810)한 후, 로컬 레지스터의 SLA번째 비트를 '1'로 설정(S611)하고, SUA가 가리키는 캘린더 메모리(140)를 갱신한다(S812).

이후, 캘린더 메모리 제어부(120)는 점유 플래그 메모리의 SUA 번째 비트가 '1'인지를 확인(S813)하여, 확인 결과 상태가 '1'인 경우에는 SUA가 가리키는 점유 어드레스 메모리(144)에 저장된 점유 어드레스가 SLA보다 큰지를 검사(S814)하고, SLA가 더 작은 경우에는 SUA가 가리키는 점유 어드레스 메모리(144)에 저장된 내용을 SLA로 변경한다(S815).

한편, 점유 플래그 메모리의 SLA 번째 비트가 '0'인 경우에는 이것을 '1'로 변경(S816)한다.

이후, 캘린더 메모리 제어부(120)는 유휴 플래그와 유휴 메모리를 갱신하기 위해 다시 로컬 레지스터의 0번째 비트부터 255번째 비트까지의 내용에 상태가 '0'인 비트가 있는지 다시 검색한다(S817). 검색에 성공하면 캘린더 메모리 제어부(120)는 검색된 어드레스를 TLA(Temporal Lower Address, 이하 TLA라 함)에 저장하고(S818), SUA가 가리키는 유휴 플래그의 상태를 '1'로 변경(S819)한 후, SUA가 가리키는 유휴 어드레스 메모리의 내용을 TLA로 변경한다(S820).

한편, 검색에 실패한 경우에는 해당 블록에는 유휴 타임 슬롯이 없는 것이기 때문에 유휴 플래그를 '0'으로 변경한다(S821).

이후, 상기와 같은 세션 등록 과정을 거쳐 최종적으로 등록된 캘린더 어드레스(CA)는 상위 8비트는 SUA가 되고, 하위 8비트는 SLA가 되는데, 캘린더 메모리 제어부(120)는 이것을 출력(S822)한 후 처리 과정을 종료하게 된다.

다음으로, 첨부된 도면을 통해 본 발명의 실시예에 따른 캘린더 메모리에서 출력 세션을 검색하는 과정을 첨부된 도면을 통해 자세히 알아본다.

도 9는 본 발명의 실시예에 따른 출력 세션 검색 과정을 개념적으로 도시한 도면이고, 도 10a와 도 10b는 그러한 과정을 순차적으로 도시한 흐름도인데, 도 10에 나타낸 출력 세션 검색 과정은 앞서 언급한 캘린더 메모리에 세션을 등록하는 과정과 유사하므로, 첨부된 도 10a와 도 10b를 위주로 설명하고자 한다.

캘린더 메모리 제어부(120)는 하나의 패킷 전송을 마치면, 16비트로 구성된 현재의 시스템 시간을 상위 8비트와 하위 8비트로 나누어 상위 슬롯 어드레스(25)와 하위 슬롯 어드레스(27)로 사용하여 해당 타임 슬롯 이후에 점유되어 있는 타임 슬롯이 있는지를 검색한다.

그래서 먼저, 캘린더 메모리 제어부(120)는 상위 슬롯 어드레스(25)를 이용하여 캘린더 메모리(400)의 타임 슬롯 점유 상태를 로컬 레지스터(26)에 로딩(loading)하는데, 이때 본 발명의 실시예에 따라, 캘린더 메모리 제어부(120)는 단일 블록의 레지스터만을 로딩한다.

로딩한 후, 하위 슬롯 어드레스(27)를 이용하여 하위 슬롯 어드레스(27) 이후의 타임 슬롯 중에서 점유되어 있는 타임 슬롯이 있는지를 검색한다. 이때, 점유 되어 있는 타임 슬롯이 발견되면 해당 타임 슬롯에 등록되어 있는 세션의 큐에서 첫 번째 패킷을 선택하여 서비스 한다.

반면, 점유되어 있는 슬롯이 발견되지 않을 경우에는 세션 등록 과정에서와 마찬가지로 점유 플래그 메모리(29)를 로컬 레지스터(26)에 로딩하고, 상위 슬롯 어드레스(25)+1번째 레지스터에서부터 레지스터 끝까지 점유되어 있는 블록이 있는지를 검색한다. 이때, 빠른 검색을 위해 라운드 로빈(Round-Robin, 또는 순환 순서) 방식을 이용한다.

이후, 끝까지 점유되어 있는 블록을 찾지 못할 경우, 다시 레지스터의 처음부터 상위 어드레스까지 점유되어 있는 블록이 있는지를 검색한다. 이렇게 해서 점유되어 있는 블록이 발견되면, 해당 블록의 점유 어드레스를 가져와서 출력 타임 슬롯의 하위 어드레스로 사용하고, 블록 어드레스를 상위 어드레스로 사용하여 출력 슬롯 어드레스(28)로 사용하며, 해당 타임 슬롯에 등록되어 있는 세션의 첫 번째 패킷을 서비스한다.

이후, 점유되어 있는 타임 슬롯이 검색되어 패킷이 서비스 되면, 캘린더 메모리 제어부(120)는 해당 타임 슬롯을 유휴 타임 슬롯으로 변경하고 점유 블록 어드레스 및 유휴 블록 어드레스를 갱신한다. 그리고, 시스템 가상 시간을 서비스 된 타임 슬롯으로 변경하고, 해당 세션에 서비스 대기 중인 패킷이 더 있는 경우, 그 패킷의 출력 시간을 다시 계산하여 유휴 타임 슬롯을 검색하여 출력 세션으로 다시 등록한다.

이처럼, 본 발명의 실시예에 따른 캘린더 메모리를 이용한 패킷 스케줄러와 그 구동 방법은, 외부로부터 입력되는 다수의 패킷을 계산된 출력 시간에 따라 캘린더 메모리에 등록하고 출력되도록 함에 있어, 단일 블록 크기의 레지스터와 캘린더 메모리(140) 및 제어 메모리(160)를 공동으로 사용함으로써, 경제적이고 효율적인 패킷 스케줄러를 제공할 수 있도록 한다.

도면과 발명의 상세한 설명은 단지 본 발명의 예시적인 것으로서, 이는 단지 본 발명을 설명하기 위한 목적에서 사용된 것이지 의미한정이나 특허청구범위에 기재된 본 발명의 범위를 제한하기 위하여 사용된 것은 아니다. 그러므로 본 기술 분야의 통상의 지식을 가진 자라면 이로부터 다양한 변형 및 균등한 타 실시예가 가능하다는 점을 이해할 것이다. 따라서, 본 발명의 진정한 기술적 보호 범위는 첨부된 특허청구범위의 기술적 사상에 의해 정해져야 할 것이다.

본 발명에 따른 캘린더 메모리를 이용한 패킷 스케줄러와 그 구동 방법은 외부로부터 입력되는 다수의 패킷을 단일 블록 크기의 레지스터와 내장 메모리를 공동으로 사용하여 정렬한 후 출력시킴으로써, 계산된 출력 시간에 따른 패킷 정렬 및 출력 패킷 검색시 소요되는 하드웨어 논리회로의 양을 줄일 수 있고, 단시간 내에 정렬 및 패킷 출력을 수행할 수 있는 효과가 있다.

Claims

외부로부터 입력되는 패킷을 저장하여 저장된 패킷의 출력을 스케줄링하는 패킷 스케줄링 장치에 있어서,

저장되는 패킷의 세션(session)이 등록되면, 세션 등록에 따른 각 타임 슬롯의 유휴 및 점유 타임 슬롯 주소를 저장하는 캘린더 메모리,

해당 세션의 서비스 레이트(service rate)를 참고로 각 패킷의 출력시간을 계산하고, 상기 캘린더 메모리를 단일 블록 레지스터에 로딩(loading)하여, 유휴 타임 슬롯을 검색하고, 계산된 출력시간 및 유휴 타임 슬롯이 있는 경우의 해당 패킷 세션을 상기 캘린더 메모리에 등록하고, 유휴 타임 슬롯에 해당 출력 패킷을 출력하도록 하는 캘린더 메모리 제어부

를 갖는 패킷 스케줄러

를 포함하는 패킷 스케줄링 장치.
제1 항에 있어서,

외부로부터 입력되는 하나 이상의 패킷을 저장하는 패킷 버퍼;

입력 패킷이 상기 패킷 버퍼의 특정 포인터에 저장되도록 하는 입력 패킷 처리부; 및

상기 캘린더 메모리 제어부로부터 상기 출력 패킷의 세션 아이디가 수신되면, 상기 출력 패킷을 상기 패킷 버퍼로부터 읽어와 출력링크로 출력시키는 출력 패킷 처리부를 더 포함하는 패킷 스케줄링 장치.
제1항 또는 제2항에 있어서,

상기 캘린더 메모리는,

일정한 구간으로 나뉘어져 하나 이상의 2차원 블록 배열을 갖는 블록 캘린더 메모리;

상기 각 블록의 첫 번째 유휴 타임 슬롯의 위치를 나타내는 유휴 어드레스 메모리;

해당 블록에 유휴 타임 슬롯이 있음을 나타내는 유휴 플래그;

상기 각 블록의 첫 번째 점유 타임 슬롯의 주소를 저장하는 점유 어드레스 메모리; 및

상기 해당 블록에 점유된 타임 슬롯이 있음을 나타내는 점유 플래그

를 포함하는 패킷 스케줄링 장치.
제1항 또는 제2항에 있어서,

상기 점유 타임 슬롯에 등록된 세션 아이디를 저장하는 제어 메모리를 더 포함하는 패킷 스케줄링 장치.
제4항에 있어서,

상기 제어 메모리는

상기 패킷 버퍼 내 비어 있는 블록의 어드레스를 저장하는 유휴 버퍼 포인터;

상기 세션 관련 정보를 저장하는 세션 정보 메모리;

상기 캘린더 메모리에 등록한 세션 관련 정보를 관리하는 캘린더 정보 메모리;

상기 패킷 버퍼에 저장한 하나 이상의 패킷에 대한 링크 리스트 구성을 위한 포인터 정보를 저장하는 버퍼 포인터를 포함하는

패킷 스케줄링 장치.
제5항에 있어서,

상기 제어 메모리는 상기 패킷 스케줄러 외부에 마련된

패킷 스케줄링 장치.
제6항에 있어서,

상기 세션 정보 메모리는,

상기 외부로부터 입력되는 각 패킷 세션의 서비스 레이트, 상기 세션의 첫 번째 패킷이 저장되어 있는 버퍼 포인터를 가리키는 시작 포인터, 마지막 패킷이 저장된 버퍼 포인터를 가리키는 끝 포인터 및 상기 세션의 큐에 저장된 패킷의 수를 나타내는 패킷 카운터를 포함하는 패킷 스케줄링 장치.
제1항 또는 제2항에 있어서,

상기 캘린더 메모리 제어부는,

상기 계산된 출력 시간의 상위 비트인 상위 타임 슬롯 어드레스를 이용하여 상기 캘린더 메모리를 상기 레지스터에 로딩(loading)하고, 상기 로딩된 캘린더 메모리에서 상기 계산된 출력 시간의 하위 비트인 하위 타임 슬롯 어드레스를 이용하여 유휴 타임 슬롯을 검색한 후, 상기 검색된 유휴 타임 슬롯에 점유 표시를 하여 해당 패킷의 세션을 등록하는 패킷 스케줄링 장치.
제8항에 있어서,

상기 캘린더 메모리 제어부는,

상기 상위 타임 슬롯 어드레스를 이용하여 상기 캘린더 메모리로부터 각 타임 슬롯의 점유 상태를 읽어와 상기 레지스터에 로딩하고, 상기 하위 타임 슬롯 어드레스 이후의 타임 슬롯 중 점유된 타임 슬롯이 있는 경우, 상기 점유 타임 슬롯에 등록된 세션의 첫번째 패킷을 출력하도록 하는 패킷 스케줄링 장치.
제2 항에 있어서,

상기 입력 패킷 처리부 및 상기 출력 패킷 처리부는 상기 패킷 스케줄러에 포함되고, 상기 패킷 스케줄러는 FPGA(Field Programmable Gate Array) 또는 ASIC(Application Specific Integrated Circuit)를 이용하여 단일 소자로 구성되는 패킷 스케줄링 장치.
외부로부터 입력되는 패킷을 저장하여 저장된 패킷 출력을 스케줄링하는 패킷 스케줄링 방법에 있어서,

a)저장된 패킷에 대해 해당 세션(session)의 서비스 레이트(service rate)를 참조하여 출력 시간을 계산한 후, 캘린더 메모리(calender memory)를 단일 블록 레지스터에 로딩(loading)하여 유휴 타임 슬롯을 검색하고, 상기 계산된 출력 시간 및 유휴 타임 슬롯이 있는 경우 해당 패킷 세션을 캘린더 메모리에 등록하는 단계;

b)상기 등록에 따른 캘린더 메모리의 각 타임 슬롯의 유휴 및 점유 타임 슬롯 주소를 상기 캘린더 메모리에 저장하는 단계;

c)상기 캘린더 메모리를 단일 블록의 레지스터에 로딩하여 출력하고자 하는 패킷을 검색하는 단계; 및

d)상기 검색된 출력 패킷의 세션 아이디(ID)를 이용하여 저장된 출력 패킷을 읽어와 출력시키는 단계

를 포함하는 패킷 스케줄링 방법.
제11항에 있어서,

상기 a)단계는,

상기 계산된 출력 시간의 상위 비트는 상기 캘린더 메모리의 블록을 나타내는 상위 타임 슬롯 어드레스로 사용하고, 상기 계산된 출력 시간의 하위 비트는 상기 캘린더 메모리 블록 내의 타임 슬롯을 나타내는 하위 타임 슬롯 어드레스로 사용하는 단계;

상기 상위 타임 슬롯 어드레스를 이용하여 상기 캘린더 메모리를 상기 단일 블록의 레지스터에 로딩(loading)한 후, 상기 로딩된 캘린더 메모리에서 유휴 타임 슬롯이 있는지를 검색하는 단계; 및

상기 유휴 타임 슬롯이 있으면, 상기 유휴 타임 슬롯에 점유 표시를 하여 해당 패킷의 세션을 등록하는 단계

를 포함하는 패킷 스케줄링 방법.
제12항에 있어서,

상기 c)단계는,

상기 상위 타임 슬롯 어드레스를 이용하여 상기 캘린더 메모리로부터 타임 슬롯의 점유 상태를 읽어와 상기 레지스터에 로딩하는 단계;

상기 하위 타임 슬롯 어드레스 이후의 타임 슬롯 중에서 점유되어 있는 타임 슬롯이 있는지를 검색하는 단계; 및

점유 타임 슬롯이 검색되면, 상기 점유 타임 슬롯에 등록되어 있는 세션의 첫 번째 패킷을 선택하여 출력하도록 하는 단계

를 포함하는 패킷 스케줄링 방법.
제11항에 있어서,

상기 타임 슬롯 검색 단계는,

모든 타임 슬롯에 대해 순서적으로 검사하는 라운드 로빈(Round-Robin) 방식을 이용하여 각각 검색하는 패킷 스케줄링 방법.