데이터 블록 스케줄링 방법과 장치 및 이를 포함하는 집적회로 document_id A220623046163

관련 출원 본 출원은 "Wireless Network Scheduling Methods and Apparatus Based on Both Waiting Time and Occupancy"라는 명칭으로 동시에 출원된 미국 특허 출원 대리인 관리 번호 해밀턴 5-1-3-2에 관한 것으로, 그 개시내용은 본 명세서에서 참조로써 인용된다. 본 발명은 일반적으로 원격통신 분야에 관한 것으로, 보다 구체적으로, 제한된 리소스에 대한 제어 액세스에 사용되는 스케줄러(scheduler)에 관한 것이다. 다수의 원격 통신 애플리케이션에서, 스케줄러는 제한된 리소스에 대해 경쟁하는 다수의 태스크 사이의 경합을 해결하는 데 사용된다. 예컨대, 이러한 스케줄러는 일반적으로 네트워크 프로세서에서 사용되어, 특정 전송 대역폭을 통한 전송에 대한 다수의 트래픽 흐름을 스케줄링한다. 네트워크 프로세서는 일반적으로 네트워크의 물리층 부분과 같은 물리적 전송 매체와 라우터 또는 다른 유형의 스위치 내의 스위치 패브릭 사이의 데이터 흐름을 제어한다. 네트워크 프로세서의 중요한 기능은 네트워크의 물리적 전송 매체로부터 스위치 패브릭까지의 전송에 대한 다수의 트래픽 흐름에 관련된 셀, 패킷 또는 다른 데이터 블록을 스케줄링하는 것을 포함하며, 반대의 경우도 또한 같다. 네트워크 프로세서 스케줄러는 이러한 기능을 수행한다. 다수의 스케줄링 알고리즘을 지원할 수 있는 효율적이고 융통성 있는 스케줄러 아키텍처는 발명자 Asif Q. Khan 등에 의해 "Processor with Scheduler Architecture Supporting Multiple Distinct Scheduler Algorithms"라는 명칭으로 2003년 11월 26일에 출원된 미국 특허 출원 번호 제 10/722,933 호에 개시되어 있으며, 이는 본 출원과 공동으로 양도되고 본 명세서에서 참조로써 인용된다. 흔히 네트워크 프로세서 또는 다른 프로세싱 장치에서 구현되는 정해진 스케줄링 알고리즘은 간단하고 공정한 것이 바람직하다. 프로세싱 장치 하드웨어가 전형적으로 정해진 스케줄링을 결정하는 데 많은 시간을 가지지 않으므로 간단함은 중요하다. 좋은 스케줄러는 공정하기도 해야 한다. 예컨대, 스케줄러는 우선순위가 높은 사용자가 우선순위가 낮은 사용자보다 대역폭이 더 많아지는 것으로 사용자의 가중치에 따라 대역폭을 할당할 수 있다. 간단하고 공정한 스케줄링 알고리즘의 예는 WRR(Weighted round-Robin) 스케줄링 알고리즘이다. 각각의 타임슬롯에서 하나의 데이터 블록을 처리할 수 있는 주어진 원격통신 애플리케이션에서 하나의 리소스에 대해 경쟁하는 다수의 사용자가 존재한다고 가정한다. 스케줄러는 각각의 타임슬롯에서 어떤 사용자가 하나의 데이터 블록을 서버에 전달할 수 있는지 결정해야 한다. 각각의 사용자는 우선순위를 식별하기 위한 가중치를 가진다. 가중치가 큰 사용자는 우선순위가 높다. 이상적인 조건 하에서, 사용자에 의해 수신된 서비스는 그들의 가중치에 비례해야 한다. WRR 스케줄러는 라운드-로빈 방식으로 사용자의 가중치에 비례하여 사용자에게 서비스를 제공한다. N개의 사용자가 있다고 가정한다. i번째 사용자, Ui는 정수인 가중치 Wi를 가진다. F는 N개의 사용자에 대한 가중치 Wi의 총합이라고 가정한다. F가 타임슬롯들로 이루어진 프레임 크기이도록 F개의 타임슬롯을 하나의 프레임으로 정의한다. WRR은 각각의 프레임 내의 정확히 Wi개의 타임슬롯 동안 Ui에 서비스를 제공한다. 따라서, 각 사용자는 자신의 공정한 프레임 공유를 획득한다. 예컨대, 가중치가 각각 4, 3, 2 및 1인 4개의 사용자 U1, U2, U3 및 U4가 있다고 가정한다. 이어서, 스케줄러는 프레임 당 순서(U1, U2, U3, U4, U1, U2, U3, U1, U2, U1)를 반복함으로써 이들 4개의 사용자를 제공할 수 있다. 하나의 프레임 내에 10개의 타임슬롯이 존재하고, U1는 각 프레임 내에 4개의 타임슬롯을 획득할 수 있다. WRR의 문제점은 긴 버스티성(burstiness) 구간을 야기할 수 있다는 것이다. 예컨대, U1의 가중치는 10이고 다른 모든 사용자의 가중치는 1인 11개의 사용자가 있는 경우를 고려한다. 이 경우에, 가중치의 총합은 20이므로, 프레임 당 20개의 타임슬롯이 존재한다. WRR은 다음과 같은 사용자(U1, U2, U3, U4, U5, U6, U7, U8, U9, U10, U11, U1, U1, U1, U1, U1, U1, U1, U1, U1)에게 서비스를 제공할 것이다. U1에 의해 수신된 서비스는 상당히 버스티(busty)하다. 이는 긴 버스티성이 사용자 통신 장치의 버퍼를 범람할 수 있으므로, 원격통신 시스템에서 명백히 바람직하지 않다. 총 사용자 수가 수백 개 이상일 수 있는 실제 애플리케이션에서 이러한 버스티성은 점점 문제가 된다. WRR의 버스티성 문제점을 극복하는 다른 스케줄링 알고리즘이 알려져 있다. 이들은 예로써 WFQ(Weighted Fair Queuing) 및 WF2Q(Worst-case Fair Weighted Fair Queueing)를 포함한다. 불행히도, 이들 다른 알고리즘은 일반적으로 WRR보다 상당히 복잡하므로, 네트워크 프로세서 및 고속 데이터 환경에서 동작하는 다른 프로세싱 장치에서 구현하기가 어려울 수 있다. 본 출원과 공동으로 양도되고 본 명세서에서 참조로써 인용되는 2004년 7월 30일에 출원된 발명자 jinhui Li 등의 "Frame Mapping Scheduler"라는 명칭의 미국 특허 출원 번호 제 10/903,954 호가 예시적인 실시예 -WRR에 필적하는 간단함 및 공정함을 제공하지만, WRR에 일반적으로 관련된 버스티성 문제가 없는 프레임 매핑 스케줄러- 에 개시된다. 보다 구체적으로, 여기에 설명된 예시적인 실시예의 프레임 매핑 스케줄러는 가중치 테이블 및 매핑 테이블을 이용하는 스케줄링 회로를 포함한다. 가중치 테이블은 복수의 엔트리를 포함하는데, 엔트리 각각은 전송 구성요소 중 특정한 것을 식별한다. 매핑 테이블은 프레임의 특정 타임슬롯과 가중치 테이블의 엔트리 사이의 매핑을 지정하는 적어도 하나의 엔트리를 포함한다. 스케줄링 회로는 대응하는 매핑 테이블 엔트리에 액세스하고, 결과값을 이용하여 가중치 테이블에 액세스함으로써 주어진 타임슬롯 내에서 스케줄링되도록 특정 전송 구성요소를 결정한다. 매핑 테이블 엔트리는 황금 비율 정책(a golden ratio policy) 또는 다른 유형의 정책에 따라 사전결정될 수 있다. 그러나, 황금 비율 정책, 또는 보다 일반적으로 저장된 매핑 테이블을 필요로 하는 임의의 정책을 이용하는 스케줄러에서, 매핑 테이블은 클 수 있으므로 상당한 메모리 양을 필요로 한다. 일반적으로 이러한 매핑 테이블 메모리는 액세스 시간을 감소시키도록 "온칩", 즉, 스케줄러와 동일한 직접 회로에 배치되는 것이 바람직하다. 예컨대, 이러한 배치는 데이터 블록이 실질적으로 실시간으로 처리될 필요가 있을 수 있는 네트워크 프로세싱 애플리케이션에서 이롭다. 2004년 11월 29일에 출원된 발명자 Jinhui Li 등의 "Frame Mapping Scheduler with Compressed Mapping Table"라는 명칭의 미국 특허 출원 번호 제 10/998,686 호는 테이블을 저장하는 데 필요한 메모리 양을 감소시키기 위해 매핑 테이블을 압축함으로써, 프레임 매핑 스케줄러를 포함하는 네트워크 프로세서 집적 회로 또는 다른 장치에서의 구현이 용이해지는 기술을 개시한다. 상술한 알려진 배치는 무선 네트워크를 수반하는 애플리케이션을 포함하는 다양한 원격통신 애플리케이션에서 이용될 수 있다. 그러나, 무선 네트워크에서의 스케줄링은 무선 네트워크에서의 채널 용량이 전형적으로 시변적이고 예측하기가 어려우므로 특히 문제가 될 수 있다. 이러한 경우에 무선 네트워크 스케줄러는 공정성뿐만 아니라 충분한 처리량도 제공하는 것이 중요하다. 무선 네트워크에서 이용되는 스케줄링 알고리즘의 예는 상술한 WRR 스케줄링 알고리즘 및 비가중화 유사물 라운드 로빈(unweighted counterpart round robin(RR)), Max C/I(maximum carrier-to-interface ratio), PF(Proportional Fairness) 및 M-LWDF(Modified Largest Weighted Delay First)를 포함한다. RR 스케줄링 알고리즘의 단점은 채널 상태를 고려하지 않는다는 것이다. 대신에, RR 스케줄링 알고리즘은 사용자들 각자의 채널 용량에 상관없이, 제 1 사용자는 제 1 타임슬롯에 할당되고, 제 2 사용자는 제 2 타임슬롯에 할당되는 등 백로깅된(backlogged) 사용자를 하나씩 간단히 스케줄링한다. 이러한 방안은 주어진 N개의 타임슬롯 세트에서, N개의 사용자 각각은 서비스를 제공받을 기회를 정확히 한 번 가지므로 공정하다. 그러나, 스케줄링을 결정하기 전에 채널 용량을 체크하지 않으므로 RR 알고리즘의 처리량은 부족하다. WRR 스케줄링 알고리즘도 스케줄링 결정시에 채널 용량을 고려하는 데 유사하게 실패한다. MAX C/I 스케줄링 알고리즘은 주어진 타임슬롯 동안 최상의 채널 용량을 가진 사용자를 선택한다. 이러한 방안은 최대 총 처리량을 획득할 수 있지만, 공정성 성능은 상당히 좋지 않다. 예컨대, 주어진 모바일 사용자의 무선 링크가 항상 약하면, 그 사용자는 스케줄링될 것 같지 않다. PF 스케줄링 알고리즘은 최대 ri/Ri을 가진 사용자를 선택하는데, 여기서 ri는 사용자 i의 채널 용량이고 Ri는 사용자 i에 의해 수신된 평균 레이트이다. 이 알고리즘은 Ri를 적합하게 갱신하다. 따라서, 약한 무선 링크를 가진 모바일 사용자는 스케줄링될 기회가 있을 것이다. PF 스케줄링 알고리즘에 대한 추가 상세사항은 예컨대, Proc. of IEEE VTC 2000, pp. 1854-1858, May 2000, A. Jalali 등의 "Data throughput of CDMA-HDR a high efficiency high data rate personal communication wireless system"에서 찾을 수 있다. PF 스케줄링 알고리즘의 공정성은 Max C/I 스케줄링 알고리즘의 공정성보다 낫지만, RR 또는 WRR 스케줄링 알고리즘의 공정성만큼 뛰어나지는 않다. 또한, PF 스케줄링 알고리즘은 보증된 공정성을 제공할 수 없다. M-LWDF 스케줄링 알고리즘은 긴 대기 시간을 가진 사용자에게 더 높은 우선순위를 부여한다. 그러나, 상술한 PF 스케줄링 알고리즘과 같이, 보증된 공정성을 제공하지는 않는다. 따라서, Max C/I, PF 및 M-LWDF 스케줄링 알고리즘은 공정성을 단념함으로써 무선 상태에서 RR 및 WRR 스케줄링 알고리즘보다 뛰어난 처리량을 제공한다. 특히, 무선 네트워크 애플리케이션에서 처리량과 공정성 사이에 더 나은 균형을 제공하는 개선된 스케줄링 알고리즘이 필요하다.