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

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

Info

Publication number
KR20070106940A
KR20070106940A KR1020070042542A KR20070042542A KR20070106940A KR 20070106940 A KR20070106940 A KR 20070106940A KR 1020070042542 A KR1020070042542 A KR 1020070042542A KR 20070042542 A KR20070042542 A KR 20070042542A KR 20070106940 A KR20070106940 A KR 20070106940A
Authority
KR
South Korea
Prior art keywords
transmission
scheduling
scheduler
timeslot
scaled
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
KR1020070042542A
Other languages
English (en)
Other versions
KR101384910B1 (ko
Inventor
크리스토퍼 더블유 해밀톤
노이 씨 쿠쿡
진후이 리
크리스틴 이 세번스-윌리엄스
Original Assignee
에이저 시스템즈 인크
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 에이저 시스템즈 인크 filed Critical 에이저 시스템즈 인크
Publication of KR20070106940A publication Critical patent/KR20070106940A/ko
Application granted granted Critical
Publication of KR101384910B1 publication Critical patent/KR101384910B1/ko
Assigned to 엘에스아이 코포레이션 reassignment 엘에스아이 코포레이션 권리의 전부이전등록 Assignors: 에이저 시스템즈 엘엘시
Assigned to 인텔 코포레이션 reassignment 인텔 코포레이션 권리의 전부이전등록 Assignors: 엘에스아이 코포레이션
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04B—TRANSMISSION
    • H04B7/00—Radio transmission systems, i.e. using radiation field
    • H04B7/24—Radio transmission systems, i.e. using radiation field for communication between two or more posts
    • H04B7/26—Radio transmission systems, i.e. using radiation field for communication between two or more posts at least one of which is mobile
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/28—Data switching networks characterised by path configuration, e.g. LAN [Local Area Networks] or WAN [Wide Area Networks]
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L65/00—Network arrangements, protocols or services for supporting real-time applications in data packet communication

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Multimedia (AREA)
  • Mobile Radio Communication Systems (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

스케줄러는 통신 시스템에서 타임슬롯 내의 복수의 전송 구성요소로부터의 전송을 위한 패킷 또는 다른 데이터 블록을 스케줄링하는 데 적합하다. 스케줄러는 전송 구성요소 각각에 대해 스케일링된 용량 측정치를 결정하는데, 스케일링된 용량 측정치 각각은 전송 구성요소 중 대응하는 하나에 대한 대기 시간 및 점유도의 조합에 의해 스케일링된다. 스케줄러는 스케일링된 용량 측정치에 기초하여, 타임슬롯 중 주어진 하나에서 스케줄링할 하나 이상의 전송 구성요소를 선택한다. 예시적인 실시예에서 스케줄러는 네트워크 프로세서 집적 회로 또는 통신 시스템의 다른 프로세싱 장치에서 구현될 수 있다.

Description

데이터 블록 스케줄링 방법과 장치 및 이를 포함하는 집적 회로{WIRELESS NETWORK SCHEDULING METHODS AND APPARATUS BASED ON BOTH WAITING TIME AND OCCUPANCY}
도 1은 본 발명의 예시적인 실시예에서 무선 네트워크를 포함하는 통신 시스템의 개략적인 블록도이다.
도 2는 도 1의 통신 시스템 중 적어도 일부의 가능한 하나의 구현예를 도시한다.
도 3은 본 발명의 일 실시예에서 도 1의 통신 시스템의 스케줄러 내에 구현되는 개선된 무선 스케줄링 알고리즘의 흐름도이다.
도 4는 도 3의 스케줄링 알고리즘의 다른 버전을 도시하는 흐름도이다.
도 5는 HSDPA 애플리케이션에서 도 3 및 도 4의 무선 스케줄링 알고리즘의 동작의 예를 도시하는 표이다.
도 6은 도 1의 통신 시스템 중 적어도 일부의 가능한 다른 구현예를 도시한다.
도 7은 라우터 또는 스위치의 회선 카드 상에 설치된 집적 회로로 도시된 도 6의 시스템의 네트워크 프로세서의 블록도이다.
도 8은 본 발명의 기술에 따라 구성된 도 6의 시스템의 네트워크 프로세서의 보다 상세한 도면이다.
도면의 주요부분에 대한 부호의 설명
100 : 통신 시스템 102 : 스케줄러
104 : 송신기 106 : 채널 상태
110-1 내지 110-N : 큐 112-1 내지 112-N : 모바일 사용자 장치
관련 출원
본 출원은 "High-Throughput Scheduler with Guaranteed Fairness for Wireless Networks and Other Applications"라는 명칭으로 동시에 출원된 미국 특허 출원 대리인 관리 번호 해밀턴 6-2-4-3에 관한 것으로, 그 개시내용은 본 명세서에서 참조로써 인용된다.
본 발명은 일반적으로 원격통신 분야에 관한 것으로, 보다 구체적으로, 제한된 리소스에 대한 제어 액세스에 사용되는 스케줄러(scheduler)에 관한 것이다.
다수의 원격 통신 애플리케이션에서, 스케줄러는 제한된 리소스에 대해 경쟁하는 다수의 태스크 사이의 경합을 해결하는 데 사용된다. 예컨대, 이러한 스케줄러는 일반적으로 네트워크 프로세서에서 사용되어, 특정 전송 대역폭을 통한 전송 에 대한 다수의 트래픽 흐름을 스케줄링한다.
네트워크 프로세서는 일반적으로 네트워크의 물리층 부분과 같은 물리적 전송 매체와 라우터 또는 다른 유형의 스위치 내의 스위치 패브릭 사이의 데이터 흐름을 제어한다. 네트워크 프로세서의 중요한 기능은 네트워크의 물리적 전송 매체로부터 스위치 패브릭까지의 전송에 대한 다수의 트래픽 흐름에 관련된 셀, 패킷 또는 다른 데이터 블록을 스케줄링하는 것을 포함하며, 반대의 경우도 또한 같다. 네트워크 프로세서 스케줄러는 이러한 기능을 수행한다.
다수의 스케줄링 알고리즘을 지원할 수 있는 효율적이고 융통성 있는 스케줄러 아키텍처는 발명자 Asif Q. Khan 등에 의해 "Processor with Scheduler Architecture Supporting Multiple Distinct Scheduler Algorithms"라는 명칭으로 2003년 11월 26일에 출원된 미국 특허 출원 번호 제 10/722,933 호에 개시되어 있으며, 이는 본 출원과 공동으로 양도되고 본 명세서에서 참조로써 인용된다.
흔히 네트워크 프로세서 또는 다른 프로세싱 장치에서 구현되는 정해진 스케줄링 알고리즘은 간단하고 공정한 것이 바람직하다. 프로세싱 장치 하드웨어는 일반적으로 소정 스케줄링을 결정하는 데 많은 시간을 가지지 않으므로, 특히 높은 데이터 레이트 환경하에서는 간단함은 중요하다. 좋은 스케줄러는 공정하기도 해야 한다. 예컨대, 스케줄러는 우선순위가 높은 사용자가 우선순위가 낮은 사용자보다 대역폭이 더 많아지는 것으로 사용자의 가중치에 따라 대역폭을 할당할 수 있다.
간단하고 공정한 스케줄링 알고리즘의 예는 WRR(Weighted round-Robin) 스케 줄링 알고리즘이다. 각각의 타임슬롯에서 하나의 데이터 블록을 처리할 수 있는 주어진 원격통신 애플리케이션에서 하나의 리소스에 대해 경쟁하는 다수의 사용자가 존재한다고 가정한다. 스케줄러는 각각의 타임슬롯에서 어떤 사용자가 하나의 데이터 블록을 서버에 전달할 수 있는지 결정해야 한다. 각각의 사용자는 우선순위를 식별하기 위한 가중치를 가진다. 가중치가 큰 사용자는 우선순위가 높다. 이상적인 조건 하에서, 사용자에 의해 수신된 서비스는 그들의 가중치에 비례해야 한다. WRR 스케줄러는 라운드-로빈 방식으로 사용자의 가중치에 비례하여 사용자에게 서비스를 제공한다.
WRR의 문제점은 긴 버스티성(burstiness) 구간을 야기할 수 있다는 것이다. 이는 긴 버스티성이 사용자 통신 장치의 버퍼를 범람할 수 있으므로, 원격통신 시스템에서 명백히 바람직하지 않다. 총 사용자 수가 수백 개 이상일 수 있는 실제 애플리케이션에서 이러한 버스티성은 점점 문제가 된다.
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 스케줄링 알고리즘보다 뛰어난 처리량을 제공한다.
이상에 인용된 미국 특허 출원 대리인 번호 해밀턴 6-2-4-3은 특히, 무선 네트워크 애플리케이션에서 처리량과 공정성 사이의 더 나은 균형을 나타내는 개선된 스케줄링 알고리즘을 제공한다. 예시적인 실시예에서, 알고리즘은 무선 RR(WiRR) 스케줄링 알고리즘으로 지칭된다. 이러한 실시예에서, 모든 전송 구성요소는 초기에 주어진 프레임 내의 서비스에 적격인 것으로 지정되지만, 특정 전송 구성요소가 주어진 프레임의 타임슬롯에서 서비스를 제공받으면, 그 프레임의 임의의 다음 타임슬롯 내의 서비스에 부적격인 것으로 간주한다. 프로세스는 다른 프레임에 대해 반복되고, 각각의 새로운 프레임마다, 전송 구성요소는 모두 초기에 그 프레임 내의 하나 이상의 데이터 블록을 전송하기에 적격인 것으로 지정된다.
WiRR 스케줄링 알고리즘 및 이의 변형에 의해 제공되는 상당한 개선에도 불구하고, 특히, 무선 네트워크 애플리케이션에서의 다른 개선이 필요하다. 예컨대, 상술한 M-LWDF 알고리즘은 일반적으로 (용인할 수 있는 도달이 제한되지만) 꽤 길 수 있는 큐 길이를 가지므로, 이 큐는 네트워크 프로세서 집적 회로 또는 다른 유형의 하드웨어에서 구현하기가 어려울 수 있다. 메모리 또는 다른 하드웨어 리소스를 적게 사용하여 구현될 수 있는 관련 큐를 가진 변형 알고리즘이 바람직할 것이다.
하나 이상의 예시적인 실시예에서 본 발명은 짧은 큐를 사용하여 구현되므로 상술한 M-LWDF 스케줄링 알고리즘과 같은 종래의 스케줄링 알고리즘에 비해 메모리 및 다른 하드웨어 리소스의 양이 감소하는 무선 스케줄링 알고리즘을 제공한다.
본 발명의 일 측면에 따르면, 스케줄러는 통신 시스템에서 타임슬롯 내의 복수의 전송 구성요소로부터의 전송을 위한 패킷 또는 다른 데이터 블록을 스케줄링하는 데 적합하다. 스케줄러는 전송 구성요소 각각에 대해 스케일링된 용량 측정치를 결정하는데, 스케일링된 용량 측정치 각각은 전송 구성요소 중 대응하는 하나에 대한 대기 시간 및 점유도의 조합에 의해 스케일링된다. 스케줄러는 스케일링된 용량 측정치에 기초하여, 타임슬롯 중 주어진 하나에서 스케줄링할 하나 이상의 전송 구성요소를 선택한다. 프로세스는 하나 이상의 다른 타임슬롯에 대해 반복될 수 있다. 타임슬롯은 통신 시스템 내의 프레임의 타임슬롯일 수 있지만, 그러할 필요는 없다.
예시적인 제 1 실시예에서, 스케일링된 용량 측정치는 i의 값이 1 내지 N인 (αiWi+βiOi)ri로 주어지되, N은 전송 구성요소의 개수를 나타내고, αi 및 βi는 전송 구성요소 i에 대한 상수이며, Wi는 전송 구성요소 i의 특정 데이터 블록의 대기 시간이고, Oi는 전송 구성요소 i의 점유도이며, ri는 전송 구성요소 i의 채널 용량이다. 전송 구성요소 i는 Wi가 큐 i 내의 HOL 패킷의 대기 시간인 큐를 포함할 수 있다.
제 2 예시적인 실시예에서, 스케일링된 용량 측정치는 i의 값이 1 내지 N인 (αiΔi+βi)Oiri로 주어지되, N은 전송 구성요소의 개수를 나타내고, αi 및 βi는 전송 구성요소 i에 대한 상수이며, Δi는 전송 구성요소 i의 대기 시간이고, Oi는 전송 구성요소 i의 점유도이며, ri는 전송 구성요소 i의 채널 용량이다. 양 Δi는 Tc-Tlast로 정의되되, Tc는 현재 시간이고 Tlast는 전송 구성요소 i가 스케줄링되는 최후 시간이다.
스케줄링 알고리즘은 특히 무선 네트워크 애플리케이션에서 사용하기에 적합하지만, 다수의 다른 애플리케이션에서도 이용될 수 있다.
본 발명의 다른 측면에 따르면, 2개 이상의 전송 구성요소는 실질적으로 동일한 스케일링된 용량 측정치를 가진 선택된 전송 구성요소에 기초하여 주어진 타임슬롯에서 스케줄링하기 위해 선택될 수 있다. 이러한 "타이(tie)" 상태에서, 2개 이상의 선택된 전송 구성요소는 모두 선택된 전송 구성요소 중 상이한 전송 구성요소에 이용가능한 코드 세트의 서로 다른 서브세트를 할당함으로써 주어진 타임슬롯에서 스케줄링될 수 있다. 예컨대, 타임슬롯은 각기 이용가능한 코드 세트를 가진 HSDPA 타임슬롯을 포함할 수 있다. 이러한 배치에서, 다수의 사용자는 사용자들에게 서로 다른 코드를 할당함으로써 HSDPA 타임슬롯 중 주어진 하나에서 스케줄링될 수 있다.
예시적인 실시예에서 스케줄러는 광범위하게 다양한 다른 스케줄링 회로 배치를 사용하여, 네트워크 프로세서 집적 회로 또는 통신 시스템의 다른 프로세싱 장치에서 구현될 수 있다.
유리하게는, 예시적인 실시예에 관하여 설명된 스케줄링 알고리즘은 종래의 M-LWDF 스케줄링 알고리즘에 관련된 과도한 큐 길이 문제점을 해결함으로써, 다수의 하드웨어 구현이 유효해진다. 또한, 예시적인 실시예는 예컨대, 시간 스탬핑 요청을 감소시키고 단일 타임슬롯 내에 다수의 사용자를 수용하여 타이를 보다 효율적으로 처리함으로써, 복잡성을 감소시킬 수 있다.
본 발명은 예시적인 무선 네트워크 및 다른 유형의 통신 시스템에 관하여 설명될 것이다. 예시적인 시스템은 본 발명의 기술을 설명하기 위해 특정 방식으로 구성된 각각의 스케줄러를 포함한다. 그러나, 본 발명은 상술한 종래의 스케줄링 알고리즘에 비해 개선된 성능을 제공하는 것이 바람직한 임의의 통신 시스템 스케줄러에 보다 일반적으로 적용가능함을 알아야 한다.
도 1은 본 발명의 예시적인 실시예에 따른 통신 시스템(100)의 개략도를 도시한다. 시스템(100)은 송신기(104) 및 채널 상태 구성요소(106)에 결합된 스케줄러(102)를 포함한다. 스케줄러는 이 실시예에서 N개의 사용자 각각에 대한 각각의 큐(queue)(110-1, 110-2 내지 110-N)를 포함하는 전송 구성요소에 결합된다. 이러한 예에서, N개의 사용자는 시스템(100)의 무선 네트워크의 모바일 사용자이고, 종래의 방식으로 송신기(104)와 통신하는 각각의 모바일 사용자 장치(112-1, 112-2 내지 112-N)에 관련된다. 송신기(104)는 예컨대, 무선 네트워크의 기지국 또는 액세스 포인트 중 적어도 일부를 포함할 수 있다.
무선 네트워크는 송신기(104)와 모바일 사용자 장치(112) 사이의 패킷 또는 다른 데이터 배열의 통신을 위해 형성된다. 이러한 모든 데이터 배열은 본 명세서에서 사용된 일반 용어 "데이터 블록"에 포함된다. 본 발명은 데이터 블록의 임의의 특정 크기 또는 구성을 필요로 하지 않음을 알아야 한다. 간단하고 명확한 설명을 위해, 도면은 송신기(104)와 모바일 사용자 장치(112) 사이의 다운링크 통신만을 도시하지만, 유사한 기술이 다른 유형의 전송에 사용될 수 있음을 알아야 한다.
이러한 실시예에서 시스템(100)은 각각의 모바일 사용자(112)에 대한 하나의 큐(110)를 관리하지만, 다른 유형의 큐잉 배열이 사용될 수 있다. 다운링크 전송은 타임슬롯 내에서 발생하는 것으로 가정된다. 타임슬롯은 프레임의 타임슬롯일 수 있지만, 본 발명은 이 타임슬롯이 프레임의 타임슬롯인 것을 요구하지 않는다. 각각의 타임슬롯 동안에, 스케줄러(102)는 하나 이상의 사용자에게 서비스를 제공한다. 이러한 실시예에서 스케줄러가 각각의 모바일 사용자에 관련된 무선 채널 용량을 인식하도록 가정된다. 이 인식은 채널 상태 구성요소(106)에 의해서나 다른 기술을 사용하여 스케줄러에 제공될 수 있다. 상술한 바와 같이, 모바일 사용자에 관련된 채널 용량은 전형적으로 시변적이고 예측하기 어렵다. 도 3 내지 도 5에 관하여 이하에 보다 상세히 설명되는 바와 같이, 스케줄러는 스케줄링 결정시에 실제 측정된 채널 상태 및 다른 파라미터에 기초한다. 주어진 타임슬롯에 있어서, 스케줄러는 각각 그 타임슬롯 동안 패킷을 전송하도록 스케줄링될 하나 이상의 사용자 큐(110)를 선택한다. 주어진 패킷은 송신기(104)를 통해 모바일 사용자 장치(112) 중 대응하는 하나에 전송된다.
도 1의 시스템(100)은 예컨대, 다른 통상적인 UMTS(Universal Mobile Telecommunications System) 또는 WCDMA(Wideband Code Division Multiple Access) 무선 셀룰러 통신 시스템으로서 구현될 수 있다. 이러한 구현예에서, 도시된 바와 같이, 도 2에 도시된 시스템(100')은 기지국(122,124,126)에 결합된 무선 네트워크 제어기(RNC:radio network controller)(120)를 포함한다. 기지국(122,124,126)은 잘 알려져 있는 UMTS 및 WCDMA 전문어에 따라 노드 B 구성요소로 지칭된다. 이들 구성요소는 UMTS 및 WCDMA 환경 내의 사용자 장비(UE:user eauipment) 구성요소로 지칭되는 모바일 사용자 장치(112)와 통신한다. 도 1의 시스템의 스케줄러(102) 및 채널 상태 구성요소(106)는 RNC(120) 내에 통합되거나, 노드 B 구성요소(122,124,126) 각각으로 복제될 수 있다. 예컨대, UMTS 또는 WCDMA 시스템(100')이 고속 다운링크 패킷 액세스(HSDPA) 특성을 제공하도록 구성되면, 스케줄러는 전형적으로 각각의 노드 B 구성요소 내에 배치되어 빠른 스케줄링을 허용한다.
상술한 HSDPA 특성은 전송 시간 간격(TTIs:transmission time intervals)으로 지칭되는 타임슬롯을 이용하고, 하나 이상의 사용자는 각각의 TTI 내에서 서비스를 제공받을 수 있다. HSDPA 특징부는 주파수 분할 듀플렉스(FDD:frequency division duplex) 모드 또는 시분할 듀플렉스(TDD:time diviision duplex) 모드로 제공될 수 있다. FDD 모드에서, 주어진 TTI는 2 ms의 지속기간을 가지지만, TDD 모드에서, 주어진 TTI는 5 ms 또는 10 ms일 수 있다. 이들 및 다른 TTI는 본 명세서에서 사용되는 일반 용어 "타임슬롯"에 포함된다.
UMTS 또는 WCDMA 환경에서, 전형적으로 HSDPA에서 주어진 노드 B로부터 UE로 데이터를 전달하는 데 사용되는 통신 시스템 채널은 고속 다운링크 공유 채널(HS-DSCH:high speed downlink shared channel)로 지칭된다.
간단하고 명확한 설명을 위해, 이하에 설명되는 바와 같이, 스케줄러(102)는 타임슬롯 당 단일 사용자에게 서비스를 제공하도록 가정될 것이지만, 도 5에 관하여 설명되는 바와 같이, 설명된 기술이 다수의 사용자가 단일 타임슬롯에서 스케줄링될 수 있는 HSDPA 및 다른 배치를 수용하도록 간단한 방식으로 확장될 수 있음을 알아야 한다.
도 1 및 도 2에 나타낸 구성요소의 특정 배치가 예로써만 도시되었음도 지적되어야 한다. 보다 구체적으로, 상술한 바와 같이, 본 발명은 임의의 유형의 무선 네트워크 또는 통신 시스템에서 구현될 수 있고, 임의의 특정 통신 애플리케이션으로 제한되지 않는다.
스케줄러(102)는 타임슬롯 내에서 사용자 큐(110)로부터의 전송을 위한 패킷 또는 다른 데이터 블록을 스케줄링하도록 구성된다. 예시적인 실시예에서 스케줄러는 대기 시간과 큐 점유도를 동시에 고려하여 큐 크기가 유리하게 감소함으로써, 메모리 및 다른 하드웨어 리소스를 보존하는 스케줄링 알고리즘을 구현한다.
일반적으로, 스케줄러(102)는 도 1의 N개의 큐(110) 중 각각의 큐에 대한 스케일링된 용량 측정치를 결정하는데, 스케일링된 용량 측정치 각각은 큐들 중 대응하는 큐에 대한 대기 시간과 점유도 양자 모두의 조합에 의해 스케일링된다. 이어서 스케줄러는 스케일링된 용량 측정치에 기초하여 타임슬롯 중 주어진 하나에서 스케줄링할 하나 이상의 큐를 선택한다. 이들 동작은 전형적으로 다른 타임슬롯에 대해 반복된다. 다른 실시예에서, 큐 이외의 전송 구성요소가 사용될 수 있다. 이하의 예시적인 스케줄링 알고리즘을 설명하는 데 있어서 전송 구성요소는 본 명세서에서 "사용자"로도 지칭될 수 있다. 따라서, 사용자에 관련하여 수행되는 이하에 설명되는 동작은 관련 전송 구성요소에 관련하여 수행되는 것으로 간주할 수 있으며, 반대의 경우도 또한 같다.
예시적인 실시예에서 스케줄링 알고리즘은 상술한 종래의 M-LWDF 스케줄링 알고리즘과 몇몇 측면에서 유사하다. M-LWDF 스케줄링 알고리즘은 IEEE Communication Magazine, Vol. 39, pp. 150-154, 2001년 2월, M. Andrews 등의 "Providing Quality of Service over a Shared Wireless Link"에 보다 상세히 설명되며, 이는 본 명세서에서 참조로써 인용된다.
각각의 타임슬롯에서, M-LWDF 스케줄링 알고리즘은 최대 (αiWiri)를 가진 사용자를 선택하며, 여기서 αi는 사용자 i에 대한 대역폭 할당 상수이고, Wi는 큐 i 내의 HOL(head-of-line) 패킷의 대기 시간이며, ri는 사용자 i에 관련된 채널 용량이다. 종래의 M-LWDF 스케줄링 알고리즘이 한정된 또는 유한 큐 길이를 보증할 수 있음을 의미하는 "처리량 최적"임은 알려져 있다. 이러한 처리량 최적 특성은 Wi가 Oi, 큐의 점유도로 대체되면 유지된다. 상술한 바와 같이, M-LWDF로 인한 문제점은 (제한은 없지만) 큐 길이가 종종 상당히 길어서, 주어진 구현에서 메모리 및 다른 하드웨어 리소스를 과도하게 소비할 수 있다는 것이다.
예시적인 실시예에서 본 발명은 스케줄링 결정시에 대기 시간과 큐 점유도 양자 모두를 동시에 고려함으로써 이러한 종래의 M-LWDF의 문제점을 해결한다. 상술한 바와 같이, 이것은 큐 크기가 감소하게 함으로써, 메모리 및 다른 하드웨어 리소스를 보존한다.
이제 도 3 및 도 4의 흐름도를 참조하여 개선된 스케줄링 알고리즘에 대한 보다 구체적인 예를 설명할 것이다. 이들 실시예에서 스케줄링 알고리즘은 실질적으로 종래의 M-LWDF 스케줄링 알고리즘과 공정성 및 처리량 성능은 동일하지만, 큐 길이는 감소하였음을 나타낸다.
도 3 및 도 4에 관하여 설명되는 예에서, 타임슬롯은 제한 없이 프레임의 타임슬롯이 되는 것으로 가정된다. 그러나, 상술한 바와 같이, 타임슬롯이 프레임의 일부일 필요는 없으며, 대신에 완전히 별개이고 독립적인 타임슬롯일 수 있다. 예시적인 실시예의 스케줄링 알고리즘에서, 스케줄링 결정은 각각의 타임슬롯에 대해 독립적으로 이루어지므로, 그 타임슬롯은 임의의 유형의 프레임화를 필요로 하지 않는다.
도 3을 처음으로 참조하면, 도 1의 시스템(100) 내의 스케줄러(102)에 의해 구현되는 개선된 제 1 스케줄링 알고리즘 버전이 도시된다.
단계(300)에서, 스케줄링 프로세스는 새로운 프레임에 대해 시작한다.
단계(302)에서, 프레임의 다음 이용가능한 타임슬롯에 있어서, 스케줄 러(102)는 i의 값은 1 내지 N이고, αi 및 βi는 큐 i에 대한 상수이며, Wi는 큐 i 내의 HOL 패킷의 대기 시간이고, Oi는 큐 i의 점유도이며, ri는 큐 i의 채널 용량인 최대 (αiWi+βiOi)ri를 가진 N개의 사용자 중 특정 사용자를 선택한다.
본 명세서에서 설명된 이들 및 다른 예에서, 간단하고 명료한 설명을 위해, 모든 N개의 사용자는 언제나 백로깅(backlogged)되는 것으로 가정한다. 사용자는 그들이 전송되는 적어도 하나의 패킷을 가지면 백로깅되는 것으로 간주한다. 도 1의 도면을 참조하면, 도시된 각각의 사용자, 즉, 사용자 1, 2, 3 및 N은 각각 관련 큐 내에 적어도 하나의 패킷을 가진다는 점에서 백로깅된 것으로 볼 수 있다.
여기서 이루어진 상술한 백로깅된 사용자 가정 및 다른 가정은 다른 실시예에 적용할 필요는 없다. 당업자에 의해 인식되는 바와 같이, 예컨대, 다른 실시예에서, 당업자에 의해 알게 되는 바와 같이, 현재의 타임슬롯에서 백로깅되지 않은 사용자는 그 타임슬롯에 대한 스케줄링 프로세스에서 고려할 사항에서 제거될 수 있다. 그러나, 현재의 타임슬롯에서 백로깅되지 않은 사용자는 다음 타임슬롯에서 백로깅될 수 있으므로, 현재의 타임슬롯에서의 스케줄링시에 고려할 사항에서 이러한 사용자를 제거한다는 것은 나머지 프레임에 대한 고려 사항에서 이들을 제거하는 것으로 해석되어서는 안 된다.
단계(304)에서, 선택된 사용자는 이용가능한 타임슬롯에서 서비스를 제공받는다. 이러한 예에서, 선택된 사용자는 이용가능한 타임슬롯에서의 전송을 위한 대응하는 사용자 큐(110)로부터의 패킷을 스케줄링함으로써 "서비스를 제공받는 다".
단계(306)에서, 스케줄링에 이용가능한 다른 백로깅되고 적격인 사용자가 있는지를 판단한다. 만일 없다면, 프로세스는 단계(300)로 리턴하여 새로운 프레임을 시작한다. 그러나, 현재 프레임에서 이용가능한 다른 타임슬롯이 존재하면, 프로세스는 단계(302)로 리턴하여 현재 프레임의 다른 타임슬롯에서 하나 이상의 사용자를 스케줄링한다.
상술한 바와 같이, 단계(302)에서의 스케줄링 결정은 각각의 타임슬롯에 대해 독립적으로 이루어지고, 타임슬롯이 프레임으로 조직화될 필요가 없다. 따라서, 단계(300,306)는 다른 실시예에서 삭제되거나, 프레임은 프레임 크기가 1로써 각각의 프레임이 단일 타임슬롯만을 포함하는 것처럼 보일 수 있다.
주어진 단계(302)에서 스케줄러(102)에 의해 2개 이상의 사용자가 동일한 최대 (αiWi+βiOi)ri를 가지는 것으로 결졍되면, 타이(tie)가 임의로 깨지거나, 작은 지수 i를 가진 사용자가 선택될 수 있다. 다수의 사용자가 주어진 타임슬롯에서 서비스를 제공받을 수 있는 상술한 HSDPA 환경 또는 다른 환경에서 사용하기에 적합한 것으로 이러한 타이를 처리하는 다른 기술은 도 5에 관하여 설명되는 바와 같이, 주어진 타임슬롯에서 사용자들에게 동시에 서비스를 제공하는 것이다.
도 3의 스케줄링 알고리즘에서 상수 βi가 0으로 설정되면, 도 3의 알고리즘은 종래의 M-LWDF 알고리즘으로 감소한다. 상술한 바와 같이, 도 3의 알고리즘은 종래의 M-LWDF 알고리즘의 공정성 및 처리량 성능과 실질적으로 동일한 공정성 및 처리량 성능을 제공하지만, 필요한 큐 길이의 이로운 감소도 제공한다. 감소한 큐 길이는 평균 큐 길이, 즉, 도 1의 시스템의 N개의 큐(110) 양단에 요구되는 평균 길이의 감소를 나타낼 수 있다. 도 3의 알고리즘도 처리량 최적이다.
상술한 실시예에서 양 (αiWi+βiOi)ri은 본 명세서에서 보다 일반적으로 스케일링된 용량 측정치로 지칭되는 것의 예이다. 당업자는 대기 시간과 점유도 양자 모두에 기초하는 스케일링을 포함하는 다른 유형의 스케일링된 용량 측정치가 사용될 수 있음을 알 것이다. 다른 예는 도 4의 흐름도를 참조하여 설명될 것이다.
예시된 구현예에서 사용된 αi 및 βi의 특정값은 구현예의 스케줄링 요청에 따라 변할 수 있고, 적합한 값은 간단한 방법으로 결정될 수 있다. 예로써, αi 및 βi는 둘 다 1 또는 0.5로 설정될 수 있지만, 다른 값도 물론 사용될 수 있다. 동일한 αi 및 βi 값 세트는 모든 i값에 대해 사용되거나, i값 중 적어도 일부에 대해 다른 값이 설정될 수 있다.
상술한 바와 같이, 도 3의 알고리즘에서, Wi는 큐 i 내의 HOL 패킷의 대기 시간이다. HOL 패킷이 시간 Tin에 인큐잉되었다고 가정한다. 주어진 현재 시간 Tc에, 패킷의 대기 시간은 Tc-Tin으로 주어진다. 이에 따라, 도 3의 알고리즘은 일반적으로 모든 패킷이 그들 각각의 큐에 도달하면 시간 스탬핑되어 대기 시간 Wi이 결정되는 것을 필요로 한다. 도 4의 알고리즘은 각각의 패킷을 시간 스탬핑해야할 필요성을 방지하는 도 3의 알고리즘을 간소화한 버전이다.
도 4의 알고리즘은 양 Δi=Tc-Tlast을 정의하며, 여기서 Tlast는 큐 i가 스케줄링되는 최후 시간이다. 양 Δi는 큐 i의 대기 시간의 표현이지만, 이들 중 어떤 것은 모든 도달 패킷의 시간 스탬핑을 필요로 하지 않는다. 대신에, 단일 시간 스탬프만이 각각의 큐에 관련될 필요가 있다. 도 4의 간단한 알고리즘은 도 3의 알고리즘의 Wi를 대체하도록 곱 ΔiOi을 사용한다. 따라서, 각각의 타임슬롯에서, 스케줄러는 최대 (αiΔi+βi)Oiri를 가진 사용자를 선택한다. 각각의 및 모든 패킷이 아니라, 큐들만이 시간 스탬핑되므로, 복잡성이 상당히 감소한다.
이제 도 4를 참조하면, 도 1의 시스템(100) 내의 스케줄러(102)에 의해 구현되는 개선된 스케줄링 알고리즘의 간단한 버전의 동작이 도시된다.
단계(400)에서, 스케줄링 프로세스는 새로운 프레임에 대해 시작한다.
단계(402)에서, 프레임의 다음 이용가능한 타임슬롯에 있어서, 스케줄러(102)는 i의 값은 1 내지 N이고, αi 및 βi는 큐 i에 대한 상수이며, Δi는 상술한 큐 i의 대기 시간이고, Oi는 큐 i의 점유도이며, ri는 큐 i의 채널 용량인 최대 (αiΔi+βi)Oiri를 가진 N개의 사용자 중 특정 사용자를 선택한다.
단계(404)에서, 선택된 사용자는 이용가능한 타임슬롯에서 서비스를 제공받는다. 다시 말하면, 이 예에서 선택된 사용자는 이용가능한 타임슬롯에서의 전송을 위한 대응하는 사용자 큐(110)로부터의 패킷을 스케줄링함으로써 "서비스를 제 공받는다".
단계(406)에서, 현재의 프레임에서 이용가능한 다른 타임슬롯이 있는지를 판단한다. 만일 없다면, 프로세스는 단계(400)로 리턴하여 새로운 프레임을 시작한다. 그러나, 현재 프레임에서 이용가능한 다른 타임슬롯이 존재하면, 프로세스는 단계(402)로 리턴하여 현재 프레임의 다른 타임슬롯에서 하나 이상의 사용자를 스케줄링한다.
도 3에 도시된 바와 같이, 단계(402)에서의 스케줄링 결정은 각각의 타임슬롯에 대해 독립적으로 이루어지고, 타임슬롯은 프레임으로 조직화될 필요가 없다. 따라서, 단계(400,406)는 다른 실시예에서 삭제되거나, 프레임은 프레임 크기가 1로써 각각의 프레임이 단일 타임슬롯만을 포함하는 것처럼 보일 수 있다.
다시 말하면, 주어진 단계(402)에서, 발생하는 타이는 상술한 기술을 사용하여 처리될 수 있다.
도 4의 스케줄링 알고리즘의 다른 버전은 상수 βi를 0으로 설정함으로써 발생할 수 있다. 이러한 변형에서, 단계(402)에서 스케줄링 결정에 이용되는 스케일링된 용량 측정치는 (αiΔiOiri)이다. 이것은 대기 시간 및 점유도 양자 모두에 의해 스케일링되는 스케일링된 용량 측정치의 또 다른 예이다.
상술한 바와 같이, 특정 실시예에서 타이는 동일한 타임슬롯에서 다수의 사용자를 스케줄링함으로써 처리될 수 있다. 예컨대, 주어진 단계(302,402)에서 2개 이상의 사용자가 실질적으로 동일한 스케일링된 용량 측정치를 가지는 것으로 결정 되면, 스케줄링에 대해 2개 이상의 사용자가 선택될 수 있고, 이러한 선택된 모든 사용자는 선택된 사용자 중 상이한 사용자에 이용가능한 코드 세트의 상이한 서브세트를 할당함으로써 주어진 타임슬롯에서 스케줄링될 수 있다. 이용가능한 코드 세트는 HSDPA 코드 세트를 포함할 수 있다.
도 5는 다수의 상이한 HSDPA 타임슬롯 각각에서의 다수의 사용자의 스케줄링의 예를 도시한다. 이 예에서, 이용가능한 코드 세트는 코드 1 내지 코드 10을 나타내는 10개의 코드를 포함한다. 각 타임슬롯은 2 ms의 지속기간을 가지는 FDD 모드 TTI를 포함한다. 도면에서 상이한 음영은 서로 다른 사용자를 나타낸다. 사용자 각각에 하나 이상의 코드를 할당함으로써, 타임슬롯들 중 주어진 하나에서 서로 다른 사용자가 10개까지 스케줄링될 수 있다.
이 예에서 사용된 코드의 특정 개수는 예시하기 위한 것일 뿐이며, 다른 실시예에서 보다 많거나 보다 적은 코드가 사용될 수 있다. 상술한 바와 같이, HS-DSCH 채널은 전형적으로 HSDPA에서 사용되어, 주어진 노드 B에서 모바일 사용자로 데이터를 전달한다. 이 채널에 코드는 15개까지 할당될 수 있다. 따라서, 도 5에 도시된 10개의 코드는 단지 사용될 수 있는 코드 세트의 일례일 뿐이다.
도면에 도시된 제 1 타임슬롯에서, 3개의 사용자가 스케줄링되는데, 하나는 4개의 코드에 할당되고 다른 2개는 각각 3개의 코드에 할당된다. 제 2 및 제 3 타임슬롯에서, 단일 사용자만이 스케줄링되며, 각 타임슬롯에서 10개의 코드 전부에 할당된다. 제 4 타임슬롯에서, 2개의 사용자가 스케줄링되는데, 각각 10개의 이용가능한 코드 중 5개에 할당된다. 도시된 나머지 타임슬롯은 동일한 방법으로 스케 줄링된다.
상술한 단일 타임슬롯 내의 다수의 사용자의 스케줄링은 HSDPA와 다른 환경에 적용될 수 있고, 다른 타임슬롯 및 코드 배열을 사용하여 구현될 수 있다.
전형적인 무선 네트워크에서, 모바일 사용자는 네트워크 또는 특정 셀 또는 네트워크의 다른 커버리지 영역으로부터 빈번히 제거되거나 이에 추가된다. 스케줄러(102)는 주어진 프레임 동안에 제거되거나 이와 달리 추가된 사용자를 처리하도록 구성될 수 있다. 제거된 사용자에 있어서, 스케줄러는 이들 사용자를 비적격이라고 간단히 지정하거나, 이와 달리 스케줄링 프로세서에서 고려할 사항으로부터 그 사용자를 제거할 수 있다. 추가되는 새로운 사용자에 있어서, 스케줄러는 예로써, 새로운 프레임이 시작할 때까지 대기하거나, 새로운 사용자의 적격성 상태를 비례적으로, 임의로 또는 다른 기술을 사용하여 설정할 수 있다.
유리하게는, 도 3 및 도 5의 예시적인 실시예에 관하여 설명된 스케줄링 알고리즘은 종래의 M-LWDF 스케줄링 알고리즘에 관련된 과도한 큐 길이 문제점을 해결함으로써, 다수의 하드웨어 구현이 유효해진다. 또한, 예시적인 실시예는 예컨대, 시간 스탬핑 요청을 감소시키고 단일 타임슬롯 내에 다수의 사용자를 수용하여 타이를 보다 효율적으로 처리함으로써, 복잡성을 감소시킬 수 있다.
이하에 보다 상세히 설명되는 바와 같이, 스케줄러(102)는 집적 회로의 형태로 적어도 일부 구현될 수 있다. 이러한 집적 회로는 도 1의 시스템의 송신기(104)에 관련된 기지국이나 액세스 포인트 또는 도 2의 시스템의 RNC나 노드 B 구성요소와 같은 주어진 통신 시스템 구성요소에서 구현되는 네트워크 프로세서 또 는 다른 유형의 프로세서 또는 프로세싱 장치를 포함할 수 있다.
스케줄러(102)는 이상에 인용된 미국 특허 출원 번호 제 10/903,954 호 및 제 10/998,686 호에 설명된 유형, 예컨대, 프레임 매핑 스케줄러일 수 있다. 이들 기술의 사용은 저장된 매핑 테이블을 요청하는 황금 비율 정책 또는 기타 정책에 대하여 매핑 테이블을 저장하는 데 필요한 메모리 양을 실질적으로 감소시킬 수 있다.
또한 또는 그 대신에, 본 발명의 스케줄링 기술은 이상에 인용된 미국 특허 출원 번호 제 10/722,933 호에 개시된 것과 같은 다수의 스케줄링 알고리즘을 지원할 수 있는 융통성있는 스케줄러 아키텍처와 관련하여 사용될 수 있다.
상술한 바와 같이, 본 명세서에 설명된 스케줄링 알고리즘은 다수의 다른 유형의 통신 시스템에서 구현될 수 있다. 이제 도 6 및 도 8을 참조하여 다른 예시적인 시스템이 설명될 것이다. 이들 도면에서, 스케줄링 알고리즘은 네트워크 프로세서의 스케줄러에서 구현된다. 이러한 네트워크 프로세서는 도 1 및 도 2에 도시된 무선 네트워크를 포함하는 시스템에서 사용될 수 있지만, 도 6에 도시된 통신 시스템(600)과 같은 다른 유형의 시스템에서도 사용될 수 있다.
시스템(600)은 내부 메모리(604)를 가진 네트워크 프로세서(602)를 포함한다. 네트워크 프로세서(602)는 도시된 바와 같이 외부 메모리(606)에 결합되고, 네트워크(608)와 스위치 패브릭(610) 사이의 패킷 또는 다른 데이터 배열 통신을 위한 인터페이스를 제공하도록 구성된다. 상술한 바와 같이, 이러한 모든 데이터 배열은 본 명세서에서 사용된 일반 용어 "데이터 블록"에 포함된다. 네트워 크(608)는 도 1 및 도 2의 시스템 내의 무선 네트워크들 중 하나의 일부분에 대응하는 무선 네트워크일 수 있지만, 네트워크 프로세서(602) 및 스위치 패브릭(610)은 기지국, 네트워크 제어기 또는 시스템과 같은 다른 구성요소에서 구현될 수 있다.
네트워크 프로세서(602) 및 관련 외부 메모리(606)는 예컨대, 라우터, 스위치 또는 다른 시스템 구성요소의 회선 카드 또는 포트 카드 상에 설치된 하나 이상의 집적 회로로서 구현될 수 있다.
도 7은 도 6의 시스템(600)의 일부인 예시적인 회선 카드 실시예를 도시한다. 이러한 실시예에서, 시스템은 자체 상에 설치된 적어도 하나의 집적 회로(702)를 가진 회선 카드(700)를 포함한다. 집적 회로(702)는 외부 메모리(604)를 가진 네트워크 프로세서(602)를 포함한다. 네트워크 프로세서(602)는 회선 카드(700) 상의 외부 메모리(606)와 상호작용한다. 외부 메모리(606)는 예컨대, SRAM 또는 DRAM으로서 네트워크 프로세서 집적 회로(702)에 서비스를 제공할 수 있다. 이러한 메모리는 종래의 방식으로 구성될 수 있고, 상술한 스케일링된 용량 측정치 또는 관련 스케일링 계수와 같은 스케줄링 정보를 저장하는 데 사용될 수 있다. 적합한 호스트 프로세서도 회선 카드(700) 상에 설치될 수 있으며, 회선 카드(700) 상의 하나 이상의 네트워크 프로세서 집적 회로의 동작을 프로그래밍하고 제어하는 데 사용될 수 있다.
도 6 및 도 7에 도시된 통신 시스템의 일부는 명료한 설명을 위해 상당히 간단해진다. 그러나, 시스템이 도 7에 도시된 것과 같은 다수의 회선 카드를 포함하 는 라우터, 스위치 또는 다른 구성요소를 포함할 수 있으며, 각각의 회선 카드는 다수의 집적 회로를 포함할 수 있음을 알아야 한다. 이와 유사한 실시예는 포트 카드의 형태로 구현될 수 있다. 그러나, 본 발명은 라우터, 스위치 또는 다른 구성요소 내에 이러한 카드 기반 구현을 필요로 하지 않는다.
도 6 및 도 7에 도시된 구성요소의 특정 배열이 단지 예시적일 뿐이라는 것도 알아야 한다. 보다 구체적으로, 상술한 바와 같이, 본 발명은 임의의 유형의 프로세서 또는 다른 통신 시스템 프로세싱 장치에서 구현될 수 있으며, 임의의 특정 네트워크 기반 프로세싱 애플리케이션으로 제한되지 않는다.
본 명세서에서 사용된 용어 "프로세서"는 제한 없이 예로써 마이크로프로세서, 중앙 처리 장치(CPU), 디지털 신호 프로세서(DSP), ASIC 또는 다른 유형의 데이터 프로세싱 장치와 같은 구성요소뿐만 아니라 이러한 구성요소의 일부 및 조합을 이용하여 구현될 수 있다.
또한, 도 6 및 도 7에 도시된 바와 같이 시스템(600) 및 네트워크 프로세서(602)는 이러한 시스템 및 네트워크 프로세서의 종래 구현에서 일반적으로 발견되는 유형인 하나 이상의 구성요소를 포함하는 구체적으로 도시된 구성요소 이외에 또는 대신에 다른 구성요소를 포함한다. 예컨대, 네트워크 프로세서는 분류기, 큐잉 및 배정 로직, 하나 이상의 메모리 제어기, 네트워크 프로세서와 네트워크(608)를 연결하는 인터페이스 회로, 스위치 패브릭(610), 호스트 프로세서 또는 다른 외부 장치(들)뿐만 아니라, 도면에 명백하게 도시되지 않은 다른 종래의 구성요소도 포함할 수 있다. 당업자가 잘 알고 있는 이들 및 다른 종래의 구성요소는 본 명세 서에서 상세히 설명되지 않는다.
본 명세서에서 설명된 네트워크 프로세서(602)의 기능은 소프트웨어 프로그램 코드의 형태로 적어도 일부 구현될 수 있다. 예컨대, 네트워크 프로세서 내의 스케줄링 동작의 성능에 관련된 구성요소는 외부 호스트 프로세서 또는 다른 적합한 메커니즘을 통해 네트워크 프로세서에 공급될 수 있는 인스트럭션 또는 다른 소프트웨어를 통해 프로그램가능한 구성요소를 이용하여 적어도 일부 구현될 수 있다. 예컨대, 특정 스케줄링 알고리즘의 특성을 나타내는 정보 또는 관련 트래픽 형성 정보는 관련 호스트 프로세서 또는 다른 적합한 메커니즘으로부터 네트워크 프로세서에 제공될 수 있다.
도 8은 본 발명의 예시적인 실시예에서 네트워크 프로세서(602)의 보다 상세한 도면을 도시한다. 이 실시예에서 네트워크 프로세서(602)는 스케줄러(800), 전송 큐(802), 트래픽 형성기(804), 가중치 테이블(810) 및 매핑 테이블(812)을 포함한다. 동작시에, 스케줄러(800)는 명백히 도시되지 않은 하나 이상의 전송 매체를 통한 전송에 대하여 전송 큐(802)에 관련된 데이터 블록을 스케줄링한다. 전송을 위한 전송 큐(802)에 관련된 데이터 블록을 스케줄링할 때, 이 스케줄링은 트래픽 형성기(804)로부터의 트래픽 형성 정보에 관련하여 또는 이러한 정보 없이, 가중치 테이블(810) 및 매핑 테이블(812)을 이용한다.
상술한 바와 같이, 네트워크 프로세서(602)는 예컨대, 이상에 인용된 미국 특허 출원에 설명된 유형 또는 당업자에게 알려져 있는 종래의 유형과 같은 추가 구성요소를 포함할 수 있으며, 이러한 구성요소는 본 명세서에서 더 설명되지 않으 며, 다른 명세서에서 설명된다.
가중치 테이블(810) 및 매핑 테이블(812)은 네트워크 프로세서(602)의 내부 메모리(604)에 적어도 일부 저장될 수 있으며, 이와 달리 네트워크 프로세서(602)의 외부 메모리(606)에도 적어도 일부 저장될 수 있다. 내부 메모리를 사용하여 저장될 때, 이러한 메모리 중 적어도 일부는 스케줄러(800) 또는 다른 스케줄링 회로에 내장될 수 있다.
테이블 구성요소(810,812) 이외에, 스케줄러(800)는 이에 관련된 다수의 다른 타임슬롯 테이블 또는 이상에 인용된 미국 특허 출원에 설명된 유형인 정적 또는 동적 테이블 기반 스케줄링 또는 종래의 실시에 알려져 있는 유형에서 사용하기에 적합한 다른 유형의 테이블 구성요소를 포함하거나 가질 수 있다.
전송 큐(802)는 복수의 전송 구성요소를 포함하는 것처럼 보일 수 있다. 예컨대, 전송 큐는 복수의 전송 큐 및 관련 제어 로직을 포함할 수 있으며, 각각의 전송 큐는 전송 구성요소에 대응한다. 그러나, 본 명세서에서 사용된 용어 "전송 구성요소"는 보다 일반적으로 하나 이상의 데이터 블록의 임의의 소스, 또는 네트워크 프로세서(602) 내의 전송에 대해 스케줄링 가능한 다른 구성요소를 포함하는 것으로 해석된다는 것에 유의해야 한다.
패킷 또는 다른 데이터 블록은 관련된 네트워크 프로세서 데이터 경로로부터 전송 큐(802)의 전송 구성요소 내에 인큐잉(enqueued)될 수 있으며, 이는 도면에 명백히 도시되지 않는다. 이것은 이러한 데이터 경로로부터 수신된 관련 데이터 블록 및 패킷 인큐 메시지에 관련하여 발생할 수 있다. 이와 유사하게, 예컨대, 데이터 경로로 전달되는 관련 데이터 블록 및 패킷 디큐 메시지에 관련하여 전송시에 패킷 또는 다른 데이터 블록은 전송 구성요소로부터 데이터 경로로 디큐잉(dequeued)될 수 있다.
트래픽 형성기(804)는 예로써, 전송 큐(802)의 전송 구성요소로부터의 데이터 블록 전송에 대한 하나 이상의 트래픽 형성 요구조건을 알려진 방식으로 설정하는 종래의 다른 트래픽 형성 엔진으로서 구현될 수 있다. 트래픽 형성기(804)는 스케줄러(800)를 통해 전송 큐(802)로부터 큐 및 스케줄러 상태에 대한 정보를 수신할 수 있다. 트래픽 형성기는 큐 전송 간격 및 CoS(class of service)를 설정하는 우선순위 매김 또는 하나 이상의 전송 구성요소 또는 그들의 대응하는 네트워크 접속에 대한 다른 바람직한 서비스 레벨과 같은 트래픽 형성 정보를 생성할 수 있다.
상술한 바와 같이, 네트워크 프로세서 상태에서, 전송 구성요소, 즉, 스케줄링되는 엔트리는 큐를 포함할 수 있다. 그러나, 본 발명은 데이터 블록이 전송되는 임의의 유형의 구성요소, 보다 일반적으로, 통신 시스템 프로세싱 장치 내의 임의의 유형의 스케줄링 가능한 구성요소를 스케줄링하는 데 사용될 수 있다. 이러한 구성요소는 본 명세서에서 사용된 일반 용어 "전송 구성요소"에 포함되고, 본 명세서에서 "사용자"로도 지칭될 수 있다.
도 8의 실시예에서 스케줄러(800)는 도 3 및 도 4의 상술한 WiRR 스케줄링 알고리즘 또는 이의 가중화 버전과 같은 스케줄링 알고리즘을 구현하도록 구성된다.
스케줄러(102,800)는 본 명세서에서 "스케줄링 회로"로서 보다 일반적으로 지칭되는 것들의 예를 예시한다. 다른 실시예에서, 스케줄링 회로는 하나 이상의 테이블 또는 본 명세서에서 설명된 스케줄링 기술을 구현할 수 있는 하나 이상의 하드웨어, 소프트웨어 및 펌웨어의 다른 배치를 포함할 수 있다. 따라서, 도면에서는 스케줄러(800)로부터 분리된 것으로 도시되었지만, 가중 테이블(810) 및 매핑 테이블(812) 또는 이들의 적절한 일부는 스케줄링 회로 또는 본 발명에 따른 관련된 메모리 내에 적어도 부분적으로 통합될 수 있다.
스케줄러(102,800)는 임의의 로직 게이트, 프로세싱 구성요소 또는 본 명세서에서 설명된 유형의 스케줄링 기능을 제공할 수 있는 다른 회로의 배치를 이용할 수 있다. 따라서 본 발명에 따른 스케줄링 회로는 본 발명에 따른 스케줄링 기능 중 적어도 일부를 제공하도록 소프트웨어 제어 하에서 적응가능한 종래의 범용 네트워크 프로세서 회로를 포함할 수 있다. 이러한 다수의 회로 배치는 당업자에게 쉽게 자명해질 것이므로, 본 명세서에서 설명하지 않는다.
상술한 바와 같이, 본 발명의 주어진 실시예는 하나 이상의 집적 회로로 구현될 수 있다. 이러한 배치에서, 복수의 동일한 다이는 전형적으로 웨이퍼의 표면 상에 반복 패턴으로 형성된다. 각 다이는 본 명세서에서 설명된 장치를 포함할 수 있고, 다른 구조 또는 회로를 포함할 수 있다. 각각의 다이는 웨이퍼로부터 절단되거나 다이싱(diced)되고, 이어서 집적 회로로 패키징된다. 당업자는 집적 회로를 산출하기 위해 웨이퍼를 다이싱하고 다이를 패키징하는 방법을 알 것이다. 따라서 제조된 집적 회로는 본 발명의 일부로 간주된다.
다시 말하면, 상술한 본 발명의 실시예가 예시적일 뿐이라는 것이 강조되어야 한다. 예컨대, 도 8의 예시적인 실시예는 관련된 테이블 또는 테이블들로부터 분리된 스케줄러를 이용하지만, 이들 구성요소 또는 이들의 일부는 본 발명에 따른 스케줄링 회로에 통합될 수 있다. 이와 유사하게, 전송 큐(802) 및 트래픽 형성기(804)는 도 8의 실시예에 관련하여 스케줄러(800)로부터 분리된 것으로 설명되지만, 관련 기능은 본 발명에 따른 스케줄링 회로 내에서 적어도 일부 구현될 수 있다. 다른 실시예는 설명된 기능을 구현하는 프로세싱 구성요소의 다른 유형 및 배치를 사용할 수 있다. 예컨대, 테이블은 내부 메모리, 외부 메모리 또는 내부 및 외부 메모리의 조합 내에 구현될 수 있다. 내부 메모리의 경우에, 이러한 메모리의 적어도 일부는 스케줄링 회로에 내장될 수 있다. 변형 WRR 스케줄링과 다른 다양한 유형의 가중 기반 스케줄링이 사용될 수 있다. 또한, 광범위하게 다양한 다른 스케줄링 정책이 지원될 수 있다. 후속하는 특허청구범위 내의 이들 및 다른 다수의 실시예는 당업자에게 자명할 것이다.
본 발명에 따르면, 데이터 블록 스케줄링 방법과 장치 및 이를 포함하는 집적 회로를 제공할 수 있다.

Claims (10)

  1. 통신 시스템에서 타임슬롯 내의 복수의 전송 구성요소로부터의 전송을 위한 데이터 블록을 스케줄링하는 방법에 있어서,
    상기 전송 구성요소에 대해, 상기 전송 구성요소 중 대응하는 하나에 대한 대기 시간 및 점유도(an occupancy)의 조합에 의해 스케일링되는 각각의 스케일링된 용량 측정치(scaled capacity measures)를 결정하는 단계와,
    상기 스케일링된 용량 측정치에 기초하여, 상기 타임슬롯 중 주어진 하나에서 스케줄링할 상기 하나 이상의 전송 구성요소를 선택하는 단계를 포함하는
    데이터 블록 스케줄링 방법.
  2. 제 1 항에 있어서,
    상기 스케일링된 용량 측정치는 i의 값이 1 내지 N인 (αiWi+βiOi)ri로 주어지되, N은 상기 전송 구성요소의 개수를 나타내고, αi 및 βi는 상기 전송 구성요소 i에 대한 상수이며, Wi는 상기 전송 구성요소 i의 특정 데이터 블록의 대기 시간이고, Oi는 상기 전송 구성요소 i의 점유도이며, ri는 상기 전송 구성요소 i의 채널 용량인
    데이터 블록 스케줄링 방법.
  3. 제 2 항에 있어서,
    상기 전송 구성요소 i는 큐(queue)를 포함하고, Wi는 큐 i 내의 HOL(head-of-line) 패킷의 대기 시간인
    데이터 블록 스케줄링 방법.
  4. 제 1 항에 있어서,
    상기 스케일링된 용량 측정치는 i의 값이 1 내지 N인 (αiΔi+βi)Oiri로 주어지되, N은 상기 전송 구성요소의 개수를 나타내고, αi 및 βi는 상기 전송 구성요소 i에 대한 상수이며, Δi는 상기 전송 구성요소 i의 대기 시간이고, Oi는 상기 전송 구성요소 i의 점유도이며, ri는 상기 전송 구성요소 i의 채널 용량인
    데이터 블록 스케줄링 방법.
  5. 제 4 항에 있어서,
    Δi는 Tc-Tlast로 정의되되, Tc는 현재 시간이고 Tlast는 전송 구성요소 i가 스케줄링되는 최후 시간인
    데이터 블록 스케줄링 방법.
  6. 제 1 항에 있어서,
    상기 스케일링된 용량 측정치는 i의 값이 1 내지 N인 (αiΔiOiri)로 주어지되, N은 상기 전송 구성요소의 개수를 나타내고, αi는 상기 전송 구성요소 i에 대한 상수이며, Δi는 상기 전송 구성요소 i의 대기 시간이고, Oi는 상기 전송 구성요소 i의 점유도이며, ri는 상기 전송 구성요소 i의 채널 용량인
    데이터 블록 스케줄링 방법.
  7. 제 6 항에 있어서,
    Δi는 Tc-Tlast로 정의되되, Tc는 현재 시간이고 Tlast는 전송 구성요소 i가 스케줄링되는 최후 시간인
    데이터 블록 스케줄링 방법.
  8. 제 1 항에 있어서,
    실질적으로 동일한 스케일링된 용량 측정치를 가지는 상기 선택된 전송 구성요소에 기초하여 2개 이상의 전송 구성요소가 상기 주어진 타임슬롯에서 스케줄링하기 위해 선택되되, 상기 선택된 전송 구성요소 중 상이한 전송 구성요소에 이용가능한 코드 세트의 서로 다른 서브세트를 할당함으로써 상기 선택된 전송 구성요소 모두가 상기 주어진 타임슬롯에서 스케줄링되는
    데이터 블록 스케줄링 방법.
  9. 통신 시스템에서 타임슬롯 내의 복수의 전송 구성요소로부터의 전송을 위한 데이터 블록을 스케줄링하는 장치에 있어서,
    상기 전송 구성요소에 결합되는 스케줄러를 포함하되,
    상기 스케줄러는 상기 전송 구성요소에 대해, 상기 전송 구성요소 중 대응하는 하나에 대한 대기 시간 및 점유도의 조합에 의해 스케일링되는 각각의 스케일링된 용량 측정치를 결정하고, 상기 스케일링된 용량 측정치에 기초하여, 상기 타임슬롯 중 주어진 하나에서 스케줄링할 상기 하나 이상의 전송 구성요소를 선택하기에 적합한
    데이터 블록 스케줄링 장치.
  10. 집적 회로에 있어서,
    통신 시스템에서 타임슬롯 내의 복수의 전송 구성요소로부터의 전송을 위한 데이터 블록을 스케줄링하도록 구성되는 스케줄러를 구비한 프로세싱 장치를 포함하되,
    상기 스케줄러는 상기 전송 구성요소에 결합되고,
    상기 스케줄러는 상기 전송 구성요소에 대해, 상기 전송 구성요소 중 대응하는 하나에 대한 대기 시간 및 점유도의 조합에 의해 스케일링되는 각각의 스케일링된 용량 측정치를 결정하고, 상기 스케일링된 용량 측정치에 기초하여, 상기 타임슬롯 중 주어진 하나에서 스케줄링할 상기 하나 이상의 전송 구성요소를 선택하기에 적합한
    집적 회로.
KR1020070042542A 2006-05-01 2007-05-02 데이터 블록 스케줄링 방법과 장치 및 이를 포함하는 집적회로 Expired - Fee Related KR101384910B1 (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US11/415,831 US7769038B2 (en) 2006-05-01 2006-05-01 Wireless network scheduling methods and apparatus based on both waiting time and occupancy
US11/415,831 2006-05-01

Publications (2)

Publication Number Publication Date
KR20070106940A true KR20070106940A (ko) 2007-11-06
KR101384910B1 KR101384910B1 (ko) 2014-04-11

Family

ID=37875489

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020070042542A Expired - Fee Related KR101384910B1 (ko) 2006-05-01 2007-05-02 데이터 블록 스케줄링 방법과 장치 및 이를 포함하는 집적회로

Country Status (4)

Country Link
US (1) US7769038B2 (ko)
EP (1) EP1853017B1 (ko)
JP (1) JP5208445B2 (ko)
KR (1) KR101384910B1 (ko)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8965440B2 (en) * 2005-05-31 2015-02-24 Alcatel Lucent Method of estimating a current channel condition in a wireless communications network
US8228920B2 (en) * 2006-05-01 2012-07-24 Agere Systems Inc. High-throughput scheduler with guaranteed fairness for wireless networks and other applications
US7769038B2 (en) 2006-05-01 2010-08-03 Agere Systems Inc. Wireless network scheduling methods and apparatus based on both waiting time and occupancy
FR2910200A1 (fr) * 2006-12-18 2008-06-20 Commissariat Energie Atomique Recepteur a decodage conditionnel
US9401867B2 (en) * 2009-01-13 2016-07-26 Alcatel Lucent Method of handling transmission of data to a mobile device through multiple channels
US8681609B2 (en) * 2009-08-21 2014-03-25 Ted H. Szymanski Method to schedule multiple traffic flows through packet-switched routers with near-minimal queue sizes
CA2964861A1 (en) 2013-10-30 2015-07-30 Massachusetts Institute Of Technology Chemical and physical sensing with a reader and rfid tags
CN114338523B (zh) 2014-12-30 2023-04-11 华为技术有限公司 一种报文转发方法和装置

Family Cites Families (23)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6046981A (en) * 1997-02-28 2000-04-04 Nec Usa, Inc. Multi-class connection admission control method for Asynchronous Transfer Mode (ATM) switches
US6014545A (en) * 1997-03-27 2000-01-11 Industrial Technology Research Institute Growable architecture for high-speed two-way data services over CATV networks
HRP980536B1 (en) * 1998-10-05 2006-04-30 O�egovi� Julije Arrangements for window - time - space flow control
US7054267B2 (en) * 1999-09-10 2006-05-30 Lucent Technologies Inc. Method and apparatus for scheduling traffic to meet quality of service requirements in a communication network
US6700869B1 (en) 1999-10-01 2004-03-02 Lucent Technologies Inc. Method for controlling data flow associated with a communications node
US6501733B1 (en) 1999-10-01 2002-12-31 Lucent Technologies Inc. Method for controlling data flow associated with a communications node
US6590890B1 (en) * 2000-03-03 2003-07-08 Lucent Technologies Inc. Method of packet scheduling, with improved delay performance, for wireless networks
AU2002314411A1 (en) * 2001-06-25 2003-01-08 Nokia Corporation Optimization of mcs and multicode with tfci signaling
IL150281A0 (en) 2002-06-18 2002-12-01 Teracross Ltd Method and system for multicast and unicast scheduling
US7330433B2 (en) * 2003-02-28 2008-02-12 Mitsubishi Electric Research Laboratories, Inc. Dynamic resource control for high-speed downlink packet access wireless channels
US7535841B1 (en) * 2003-05-14 2009-05-19 Nortel Networks Limited Flow-rate-regulated burst switches
JP2005045561A (ja) * 2003-07-22 2005-02-17 Matsushita Electric Ind Co Ltd パケット送信スケジューリング装置、その方法及び無線基地局装置
JP4335619B2 (ja) * 2003-09-04 2009-09-30 株式会社エヌ・ティ・ティ・ドコモ パケット優先制御装置及びその方法
US7522657B2 (en) * 2003-10-20 2009-04-21 William Marsh Rice University Throughput maximization in wireless communication systems
US7656899B2 (en) * 2003-11-06 2010-02-02 Interdigital Technology Corporation Access points with selective communication rate and scheduling control and related methods for wireless local area networks (WLANs)
AU2003280933A1 (en) * 2003-11-14 2005-06-06 Zte Corporation A packet scheduling method for wireless communication system
US7477636B2 (en) 2003-11-26 2009-01-13 Agere Systems Inc. Processor with scheduler architecture supporting multiple distinct scheduling algorithms
US7680124B2 (en) 2004-07-30 2010-03-16 Agere Systems Inc. Frame mapping scheduler for scheduling data blocks using a mapping table and a weight table
US7362741B2 (en) * 2004-08-10 2008-04-22 Nec Corporation Method and apparatus for wireless communication network operating in compressed mode
CN100394826C (zh) * 2004-09-02 2008-06-11 上海贝尔阿尔卡特股份有限公司 信道质量内插方法
US7292825B2 (en) * 2004-10-19 2007-11-06 Ipwireless, Inc. Retransmission scheme in a cellular communication system
US7352752B2 (en) * 2004-11-29 2008-04-01 Agere Systems Inc. Frame mapping scheduler with compressed mapping table
US7769038B2 (en) 2006-05-01 2010-08-03 Agere Systems Inc. Wireless network scheduling methods and apparatus based on both waiting time and occupancy

Also Published As

Publication number Publication date
EP1853017B1 (en) 2011-08-03
JP5208445B2 (ja) 2013-06-12
JP2007300643A (ja) 2007-11-15
EP1853017A1 (en) 2007-11-07
KR101384910B1 (ko) 2014-04-11
US7769038B2 (en) 2010-08-03
US20070253425A1 (en) 2007-11-01

Similar Documents

Publication Publication Date Title
KR101384910B1 (ko) 데이터 블록 스케줄링 방법과 장치 및 이를 포함하는 집적회로
KR101118339B1 (ko) 무선 베어러에 서비스를 매핑하여 가중치에 따라 무선 베어러에 대역폭을 할당하는 장치 및 방법
KR101382979B1 (ko) 무선 통신 시스템에서 서비스 품질 (ＱｏＳ) 송신의 스케줄링을 위한 방법 및 장치
US8379518B2 (en) Multi-stage scheduler with processor resource and bandwidth resource allocation
CN1498472A (zh) 用于实时自适应容量调度的系统与方法
KR101303390B1 (ko) 데이터 블록 스케줄링 방법과 장치 및 이를 포함하는 집적회로
EP2057797B1 (en) Scheduling methods and apparatus based on adjusted channel capacity
EP1817878B1 (en) Fair air-time transmission regulation without explicit traffic specifications for wireless networks
US7680124B2 (en) Frame mapping scheduler for scheduling data blocks using a mapping table and a weight table
EP1653683B1 (en) Dynamic setting of transmission scheduler algorithms
US7830857B2 (en) Credit-based wireless network scheduling
US7724723B2 (en) High-throughput scheduler with integer-based eligible number initialization
KR100520608B1 (ko) 고속 데이터 전송을 위한 이동통신 시스템에서 패킷스케쥴링 방법
JP4750331B2 (ja) 無線通信システムにおけるパケット割り当ての方法

Legal Events

Date Code Title Description
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

R17-X000 Change to representative recorded

St.27 status event code: A-3-3-R10-R17-oth-X000

A201 Request for examination
P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

PN2301 Change of applicant

St.27 status event code: A-3-3-R10-R13-asn-PN2301

St.27 status event code: A-3-3-R10-R11-asn-PN2301

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R11-asn-PN2301

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R14-asn-PN2301

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R11-asn-PN2301

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R14-asn-PN2301

R17-X000 Change to representative recorded

St.27 status event code: A-5-5-R10-R17-oth-X000

FPAY Annual fee payment

Payment date: 20170330

Year of fee payment: 4

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20180408

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20180408