KR100475783B1 - 계층적 우선 순위화 라운드 로빈 스케쥴링 - Google Patents

Abstract

HPRR 방법은 각 개별 패킷이 흐름을 위한 트래픽 사양에 부합하는지 아닌지로서 표시하기 위해 토큰 버킷 레이트 분류기들을 사용한다(흐름별 큐들 1, 2, 3, 4). 흐름들은 단일 서비스 클래스(클래스 A, B, D)내에 있는 것으로 간주된다. 하나의 이러한 클래스는 디폴트 "최선형" 서비스 클래스(D)로서 구분된다. 각 서비스 클래스는 모든 클래스들이 활성화중일 때 클래스에 승인된 대역폭의 부분에 대응하는 가중이 할당된다. HPRR 방법은 흐름으로부터의 패킷이 두가지 방식 중 하나, 즉, 그 클래스의 할당된 대역폭의 부분이나 최선형 대역폭의 부분으로서 포워딩될 수 있게 한다. 그 패킷들을 전송하기 위해 흐름에 대하여 항상 두 개의 경로들을 제공함으로써, 흐름에는 두가지 상이한 클래스들, 즉, 그 일차 또는 구성 클래스와, 최선형 클래스의 그 공정한 몫이 항상 주어진다.

Description

계층적 우선 순위화 라운드 로빈 스케쥴링{HIERARCHICAL PRIORITIZED ROUND ROBIN(HPRR) SCHEDULING}

관련 출원에 대한 상호 참조

본 출원은 본 출원인에 의해 1999년 9월 25일자로 출원된 발명의 명칭이 "계층적 우선 순위화 라운드 로빈(HPRR) 스케쥴링"인 미국 가출원 제 60/156,123 호를 우선권으로 주장한다.

발명의 분야

본 발명은 일반적으로 컴퓨터 네트워크에 관한 것이며, 보다 구체적으로는, 데이터 트래픽을 데이터 전송 링크상으로 스케줄링하는 것에 관한 것이다.

링크 공유를 위한 한가지 요건은 다수의 조직(organization)들 사이의 링크상에서 대역폭을 공유하는 것이며, 이때, 각 조직은 폭주(congestion) 동안 링크 대역폭의 보증된 몫을 수신하기를 원하지만, 하나의 조직에 의해 사용되고 있지 않는 대역폭은 그 링크를 공유하는 다른 조직들에게 사용가능해야 한다. 그 대표적인 예는 트랜스 아틀랜틱 FAT 파이프를 공유하면서, 단일 ISDN 회선을 공유하는 개체들에 대한 비용들 중 고정된 몫을 각각 지불하고 있는 다수의 중계사들이다. 링크 공유의 다른 예는 상이한 프로토콜 패밀리들(예컨대, IP 및 SNA) 사이의 링크상의 공유된 대역폭이며, 이때, 폭주에 대해 상이한 프로토콜 패밀리들이 상이한 응답을 가지기 때문에, 링크 공유의 제어가 필요하다. 링크 공유의 세 번째 예는 텔넷, ftp 또는 실시간 오디오 및 비디오 같은 상이한 트래픽 형태들 사이의 링크상의 대역폭을 공유하는 것이다.

네트워크 자원의 제어는 접속당 단대단 요건(per-connection end-to-end requirements)의 고려뿐만 아니라, 사용에 대한 로컬 결정(local decisions)을 수반한다. 링크 공유 메카니즘의 한가지 기능은 순수한 로컬 요구에 응답하여 로컬 링크들상의 대역폭의 분배를 제어하도록 게이트웨이를 이네이블하는 것이다.

공유된 링크들상의 실시간 서비스들을 포함하는 상이한 트래픽 유형들을 수반하는 것에 대한 요구는 트래픽의 클래스들을 가진 계층적 링크 공유에 대한 요구를 초래한다. 링크 공유 서비스들과, 실시간 서비스들은 게이트웨이에서 만족되어야할 구속들의 등시성 세트들을 수반한다. 또한, 링크 공유 요건들을 충족시키는 동시에, 보다 높은 우선 순위를 가진 트래픽의 요구들을 만족시키면서, 보다 낮은 우선 순위의 트래픽의 기아상태(starvation)를 방지하는 것에 대한 요구도 존재한다.

현재의 스케쥴링 방법들은 우선 순위화 클래스별 큐잉(CBQ; Class Based Queuing) 또는 가중 공정 큐잉(WFQ; Weighted Fair Queuing) 방식의 변형을 사용하는 차별화된 서비스 품질(QOS)을 지원한다. 종래 기술의 CBQ와 WFQ 방법은 두가지 중요한 팩터들, 즉, 1) 오버리미트 트래픽, 즉, 흐름의 보증 트래픽 레이트 사양을 초과하는 흐름으로부터의 트래픽과, 2) 대역폭 및 딜레이의 보장된 보증이 아닌 통계학적 보증을 제공하기 위한 흐름들의 고의적 초과 예약(deliberate overbooking)을 무시한다. 흐름의 초과 예약은 모든 흐름들이 동시에 활성화될 때, 그 대역폭을 제공하기에 용량이 불충분하다 해도, 예약된 최소 대역폭 요건들을 가진 흐름이 허용된다는 것을 의미한다.

CBQ 알고리즘은 활성화 흐름들을 급속하게 변화시키는 환경이 아닌 항상 활성 상태인 것으로 간주되는 고정된 흐름들의 세트에 의존한다. 상기 CBQ 알고리즘은 오버리미트로서 이를 분류하기 위해 서행성 흐름당 평균 레이트(slow-acting average rate per flow)를 사용한다. 상기 CBQ 알고리즘은 클래스가 트래픽 한계를 초과하는지 미만인지를 결정하기 위해 산출된 클래스 평균 레이트에 의존하기 때문에, 비교적 느리게 동작한다. 그것은 클래스 오버리미트를 표시하기 위해 서행성 흐름(또는 클래스)당 평균 레이트에 의존하며, 그리고 오버리미트 클래스에 대해 어떤 공정 대역폭을 할당해야 하는지를 결정하기 위한 비교적 복잡한 알고리즘에 의존한다. 결국, 이는 클래스내의 흐름의 초과 예약을 위해 어떠한 대책도 없게 만든다. 즉, 보증된 최소 서비스 레이트들을 가진 흐름이 고의로 과허용되는 경우에, 통계학적으로 소수의 허용된 흐름들이 동시에 백로그(backlogged)되게 된다. CBQ 알고리즘은 초과 예약의 존재시 클래스 대역폭 강조를 검토하지 않는다.

CBQ 알고리즘에서는, 각 클래스는 그 할당된 평균 대역폭에 한정될 수 있지만, 언더리미트 클래스들에 대한 순간적 대역폭 손실에 대해서는 어떠한 보호조치도 없다. 이것은 상술한 바와 같은 CBQ 알고리즘이 클래스가 오버리미트인지 아닌지를 결정하기 위해 비교적 느리게 변화하는 평균 레이트에 의존하기 때문이다.

신호 레벨 WFQ 방법은 초과 예약된 흐름들의 세트가 독단적으로 대역폭의 큰 부분을 점유할 수 있기 때문에, 초과 예약의 문제점을 가지고 있다. 각 흐름은 그 수가 너무 많은 경우에도 그들이 그 공정한 몫을 소모한다. 초과 예약의 문제점은 WFQ 스케쥴러의 계층의 개념에 의해 완화된다. 그러나, WFQ 알고리즘은 각 흐름이 그 트래픽 사양을 준수하는 것으로 가정하며, 상술된 알고리즘은 트래픽 사양 한계를 초과하는 개별 흐름들에 대한 어떠한 대책도 없다. 하나의 클래스 내의 흐름을 위한 계층적 WFQ 방법에는 최선형 클래스(best effort class)로 대역폭을 공유하기 위한 어떠한 개념도 존재하지 않는다. 보다 높은 레벨의 하나의 흐름이 오버리미트인 경우, 이는 그 클래스에 할당된 대역폭에 그 자체를 담아야만 하며, 디폴트 클래스내의 다른 최선형 흐름들을 완성할 수는 없다. 예로서, 대역폭 중 50%를 할당받은 보증된 클래스내에, 각각 대역폭의 10%를 할당받는 5개의 흐름이 있고, 대역폭의 50%가 할당된 디폴트 클래스내에 단 하나의 흐름이 존재하는 경우를 고려한다. 하나의 디폴트 흐름은 지속적으로 백로그되고, 그래서, 대역폭의 50%를 취득한다. 보증된 흐름들 중 하나가 갑자기 가능한 많은 대역폭을 필요로하게 될 때, 이는 링크 대역폭의 단 10%, 즉 계층적 WFQ를 사용하는 보증된 클래스에 할당된 50% 중 1/5만을 계속 받게된다.

WFQ 스케쥴링 알고리즘에서, 초과 예약된 흐름들은 대역폭 중 그 가중의 가치를 계속 사용하게 되며, 실제로, 현저한 예약 초과 상태에서 독단적으로 상기 대역폭의 큰 부분들을 소모할 수 있다. 상기 WFQ 알고리즘은 흐름들의 클래스를 대역폭의 비율에 대해 한정하고, 초과 예약의 존재시에도 그 대역폭을 집행하기 위한 어떠한 대책도 제공하지 않는다. 초과 예약은 상업적 대역폭 공급자들에게 중요한 경제적 요건이다. WFQ 알고리즘은 디피싯 라운드 로빈(deficit round robin; DRR) 알고리즘보다 더 양호한 최악의 경우에서의 딜레이를 제공하는 반면에, 또한, 다수의 연산적 복잡성을 가지고 있다. 주요한 문제점들은 패킷의 종결 시간을 산출하기 위한 분할 작업과, 종결 시간에 기초하여 배열된 큐을 유지하는 것이 복잡하다는 것이다. 이들 복잡성들은 일반적으로 N 개의 가능 흐름들에 대하여 O(log N)의 수준인 것으로 고려된다.

도 1은 본 발명의 원리에 따른 계층적 우선 순위화 라운드 로빈(HPRR) 스케쥴링의 부분 개략 흐름도.

도 2는 도 1의 시스템 및 HPRR 방법에 의해 사용되는 데이터 구조들의 블록 다이어그램.

도 3은 도 2의 데이터 구조의 일 예시적 상태의 블록 다이어그램.

도 4 및 도 5는 도 1의 방법 및 시스템에 따라 새로운 패킷을 수신하는 프로세스의 동작의 흐름도.

도 6, 7, 8, 9 및 10은 도 1의 방법 및 시스템에 따른 전송 대상 패킷들의 스케쥴링의 흐름도.

패킷들을 데이터 전송 링크에 스케쥴링하는 것의 문제점들은 계층적 우선 순위화 라운드 로빈 스케쥴링의 본 발명에 의해 해결된다.

데이터 네트워킹 장치에서 차별화된 서비스 품질(QOS)을 제공하기 위한 중요한 콤포넌트는 아웃고잉 전송 인터페이스로 라우팅된 패킷들을 위한 스케쥴링 방법이다. 본 발명은 트래픽의 상이한 클래스들에 할당된 대역폭을 제공하는 전송 인터페이스상에 패킷들을 스케쥴링하기 위한 방법이며, 여기서, 각 클래스는 다수의 흐름들로 구성된다. 이는 초과 예약된 흐름들, 즉, 허용된 흐름들의 트래픽 레이트들의 합이 흐름들의 클래스들을 위한 할당된 용량을 초과하는 경우의 효과적이고 공정한 취급을 제공한다. 본 발명은 각 클래스의 대역폭을 용량의 할당된 부분으로 한정하기 위한 DRR 메카니즘을 유지하면서, 각 클래스를 위한 우선 순위의 개념을 가진 패킷들의 우선 순위화된 포워딩을 제공하도록 디피싯 라운드 로빈(DRR) 알고리즘을 강화하는 것을 포함한다. 본 발명의 핵심 특성은 하나의 클래스를 디폴트 클래스로서 식별하는 것이며, 여기서, 그 클래스의 트래픽 레이트를 초과하는 흐름들은 여전히 디폴트 클래스의 할당된 대역폭내의 패킷들을 포워딩할 수 있다.

HPRR에서, 전자의 예의 버스팅 보증 클래스 흐름은 총 35%의 대역폭에 대하여, 그 10% 보증 부분에 최선형 대역폭(25%)의 1/2를 더한 것을 취득하게 된다. HPRR 방법은 그 트래픽 사양 한계를 초과하는 소정의 차별화된 클래스 흐름들에 대하여 효율적이고 용이하게 디폴트 또는 최선형 대역폭을 할당한다.

HPRR 방법은 각 개별 패킷을 흐름을 위한 트래픽 사양에 부합하는 또는 부합하지 않는 것으로서 표시하기 위해 즉시 정확한 토큰 버킷 레이트 분류기를 사용한다. 본 발명의 핵심은 흐름이 두 상이한 클래스들, 즉, 흐름의 할당된 클래스와 디폴트 또는 최선형 클래스의 부분으로 고려된다는 것이다. HPRR 방법은 흐름으로부터의 패킷이 두가지 방식들 중 하나, 즉, 그 클래스의 할당된 대역폭의 일부 또는 최선형 대역폭의 일부 중 어느 한쪽으로서 포워딩되게 하는 것이다. CBQ와는 달리, HPRR 방법은 오버리미트인지 아닌지로서 클래스들을 표시하거나, 오버리미트 클래스들이 그 패킷들을 차단 또는 포워딩하도록 허가되었는지 아닌지를 결정하려고 시도하지 않는다는 것이다. 모든 피어(peer) 클래스들의 오버리미트 또는 언더리미트를 시험하는 소정의 알고리즘을 처리할 필요가 없다. 대신, 하나의 흐름에 대하여 그 패킷들을 전송하기 위해서, 항상 두 개의 경로들을 제공함으로써, 하나의 흐름에는 두 개의 상이한 클래스들, 즉, 그 일차 또는 구성된 클래스와 최선형 클래스 중 그의 공정한 몫이 항상 주어지게 된다.

HPRR 방법은 초과 예약된 클래스들을 취급하기에 단순하면서 효과적인 알고리즘이다. 초과 예약된 클래스는 상기 클래스에 할당된 불충분한 대역폭에 비견하는 그 각각의 흐름들을 갖지만, 각각의 흐름이 최선형 대역폭을 사용할 수 있기 때문에, 다른 클래스들이 비활성 상태일 때 클래스들의 대역폭 보증을 허용하는 대역폭의 공정한 몫을 취득할 수 있다.

HPRR 방법은 패킷 자체가 트래픽 레이트 토큰 버킷에 부합하는지 아닌지를 패킷 단위로 결정한다. 흐름의 트래픽 사양 토큰 버킷에 부합하지 않는 유지된 패킷들은 흐름의 클래스 대역폭을 경유하여 포워딩하기에 부적절하지만, 디폴트 클래스 대역폭을 경유하여 포워딩하기에는 여전히 적합하다. HPRR 방법은 신규한 우선 순위화 DRR 방법을 사용함으로써, 보다 높은 최악의 경우의 딜레이 한계의 허용 대가로, 분할 작업들 및 배열된 큐의 O(log N) 메인테넌스를 회피한다.

정의

일반적 스케쥴러 : 링크 공유 가이드라인에 무관한 리프 클래스들로부터 패킷들을 스케쥴링함.

링크 공유 스케쥴러 : 폭주시 링크 공유 할당들을 초과하는 일부 리프 클래스들로부터 패킷들을 스케쥴링함.

규제 클래스 : 그 클래스로부터의 패킷들이 게이트웨이에서 링크 공유 스케쥴러에 의해 스케쥴링되는 경우.

비규제 클래스 : 그 클래스로부터의 트래픽이 일반적 스케쥴러에 의해 스케쥴링되는 경우.

오버리미트, 언더리미트, 엣리미트(at-limit) : 클래스가 최근 그 할당된 링크 공유 대역폭(특정 시간 간격에 걸쳐 평균화됨, bytes/sec)보다 더 많이 사용된 경우 그 클래스를 오버리미트라 지칭하고, 그 링크 공유 대역폭의 특정 부분보다 작게 사용되는 경우를 언더리미트라하며, 그 이외의 경우를 엣리미트라함.

도면에 예시된 본 발명의 실시예에 대한 하기의 상세한 설명으로부터 상술한 바 및 다른 장점들과 함께 본 발명을 더욱 명확하게 이해할 수 있을 것이다.

도 1은 본 발명의 원리에 따른 계층적 우선 순위화 라운드 로빈 스케쥴링 방법의 부분 개략 흐름도이다. 본 발명은 데이터 전송 링크상으로 패킷들의 전송을 스케쥴링하기 위한 장치 및 방법을 포함한다. 전송 링크상에서 전송되는 패킷들은 스케쥴러에 주어지고, 상기 스케쥴러는 상기 패킷들을 큐에 넣고, 사전설정된 조건들에 부합되어야할 필요가 있는 경우에는 상기 패킷들을 재배열한다.

본 명세서에 설명된 스케쥴링 방법 및 장치(스케쥴러라 칭함)는 우선 순위 레벨 기반별 대역폭 분할과 각 우선 순위 레벨에서의 최대 버스트(burst) 양자 모두를 제한하는, 흐름별 큐잉(per-flow queuing)과 우선 순위화 서비스의 조합을 수반한다. 본 발명은 가중 공정 큐잉(WFQ)과 클래스별 큐잉(CBQ) 패킷 스케쥴링 방법 양자 모두의 핵심 특성들을 조합한다. 부가적으로, 개선된 디피싯 라운드 로빈 서비스 방법이 본 스케쥴링 방법 및 장치에 포함된다. 개선된 디피싯 라운드 로빈 서비스 방법은 우선 순위화 큐의 복잡성과, SFQ 종료 시간 계산의 분할 작업을 회피한다.

도 1을 참조하면, 본 발명의 스케쥴러는 상기 스케쥴러내의 다수의 단계에서 패킷들을 프로세싱한다.

1. 패킷들은 먼저 흐름들로 분류된다. 인터넷 프로토콜(IP)에 대해, 흐름 분류는 패킷들의 소스 및 착신 IP 어드레스들, IP 프로토콜 유형 및 사용자 데이터그램 프로토콜(UDP) 또는 패킷내의 전송 제어 프로토콜(TCP) 포트 번호의 함수인 것이 적합하다. 스케쥴러에서, 패킷들은 먼저 흐름별 큐로 집어넣어진다. 각 흐름은 그 위에 큐잉될 수 있는 최대 버퍼수를 가지는 것이 적합하다. 흐름 분류의 예로서, IP 전화법(즉, 캡슐화된 음성)은 흐름 번호 1로서 분류되고, 모든 다른 패킷들은 흐름 번호 4(디폴트 흐름 클래스)로서 분류될 수 있다.

각각의 흐름은 흐름에 제공된 데이터 포워딩 서비스의 세트를 기술하는 단일 서비스 클래스의 멤버인 것으로 간주된다.

2. 그후, 패킷들은 최대 레이트 토큰 버킷 리미터를 통과하여야만 하며, 상기 리미터는 흐름별로 포워딩 레이트를 제한한다. 패킷들이 그 최대 레이트 리미터를 통과하고나면, 이들은 두 개의 클래스들, 즉, 흐름의 구성 클래스 또는 디폴트 클래스 중 어느 한쪽의 포워딩에 적합하다.

3. 그후, 패킷들은 그 논리적 클래스별 큐로의 포워딩을 위해 적합해지도록 트래픽 레이트 토큰 버킷 리미터를 통과하여야만 한다. 트래픽 레이트는 흐름 소스가 네트워크내로 트래픽을 주입하는 데 동의하는 최대 레이트이다. 네트워크와 트래픽 소스 사이의 서비스 계약은 상기 트래픽 레이트 보다 적게 전송된 패킷들만이 네트워크에 의한 차별화된 서비스를 받게 되도록 되어 있다. 프레임 릴레이 네트워크들에서 제공되는 것 같은 규정 정보 전송 속도(CIR; Committed Information Rate) 서비스에 대하여, 트래픽 레이트는 CIR 레이트에 대응한다. 네트워크가 트래픽 레이트보다 빠르게 패킷들을 받지만, 이들은 단지 최선형에 맞게만 포워딩하게되는 것이 적합하다. 본 발명의 양호한 실시예의 스케쥴러에서, 트래픽 레이트 보다 빠르게 도달한 패킷들은 그 서비스 클래스에 할당된 대역폭의 일부로서 포워딩되는 것이 저지되며, 디폴트 클래스에 할당된 대역폭의 일부로서만 포워딩될 수 있다.

4. 언제든, 클래스는 순간적으로 초과 예약될 수 있으며, 이는 클래스에 할당된 전송 채널의 구성 용량을 초과한 도입 대상 트래픽 레이트를 가진 흐름들이 허용되었다는 것을 의미한다. 이 상태에서, 스케쥴러는 흐름들이 그 클래스의 대역폭에 추가하여 디폴트 클래스 대역폭을 사용하여 패킷들을 포워딩하도록 허용한다.

5. 트래픽 레이트 리미터를 통과한 패킷들은 동일 클래스내의 모든 흐름들을 위해 패킷들을 유지하는 클래스별 큐상으로 스케쥴링된다.

패킷들은 단지 흐름별 큐상으로만 물리적으로 들어가게 된다. 도 1의 클래스별 큐은 본 발명의 방법의 동작을 설명하기 위해 사용되는 가상 큐이다. 또한, 흐름의 최대 레이트 토큰 버킷 리미터에 부합하는 모든 패킷들은 클래스의 대역폭과 디폴트 클래스 대역폭 양자 모두로부터의 포워딩에 적합하다.

실제 흐름별 큐들은 개념적으로 흐름들의 할당된 서비스 클래스들을 위한 클래스별 큐를 공급한다. 동일 클래스내의 흐름들로부터의 패킷들이 클래스별 큐로 포워딩되는 방식은 본 발명과 무관하지만, 그러나, 디피싯 라운드 로빈 스케쥴링 같은 공정 큐잉 알고리즘의 형태인 것이 적합하다.

각 흐름은 스케쥴러내의 최대 레이트 리미터를 사용하여 구축되며, 그래서, 흐름을 위해 구축된 최대 레이트를 초과하는 경우 패킷을 포워딩하지 않는다. 버퍼 관리는 흐름별로 수행되며, 클래스별로 수행되지 않는다.

또한, 각 흐름은 흐름의 트래픽 레이트를 초과하는 패킷들을 그 서비스 클래스 큐상으로 포워딩하는 것을 방지하는 트래픽 레이트 리미터를 구비하고 있다. 각 흐름은 그 흐름 클래스에 할당된 대역폭을 수신하기 위해서 부합되어야한하는 트래픽 레이트 리미터를 사용하여 구축되어야만 한다. 흐름은 트래픽 레이트보다 빨리 데이터를 보낼 수 있도록 허용되지만, 그것은 흐름별 큐상에서 뒤로 유지되며, 디폴트 클래스에 할당된 대역폭의 일부로서만 포워딩될 수 있다.

스케쥴러는 흐름 큐들로부터 패킷들을 스름의 서비스 클래스를 위한 가상 큐로 포워딩한다. 이는 클래스별 큐잉을 위한 물리적 큐잉(예로서, 링크된 리스트)을 실행할 필요가 없기 때문에, 가상 큐이다. 대신, 상기 스케쥴러는 단지 클래스별 리스트상의 상단 흐름 큐에 대한 포인터를 유지하기만 하면 된다. 가상 우선 순위 큐로부터의 상단 패킷 또는 패킷들은 큐로부터 빠져나오는 경우에, 이들은 (실제)흐름 큐로부터 제거되며, 클래스 큐의 다음 상단이 그 클래스내의 활성 흐름 큐을 스캐닝함으로써 결정된다. 상기 스케쥴러는 정렬되지 소정의 소정의 단일 큐내의 패킷들을 포워딩하지 않는 것이 적합하다.

각 서비스 클래스는 스케쥴링 우선 순위가 할당된다. 클래스별 큐들은 우선 순위 순서로 서비스되며, 대역폭 제한을 받는다. 유리하게는, 디피싯 라운드 로빈(DRR) 알고리즘이 각 클래스로부터 패킷들을 스케쥴링하기 위해 사용될 수도 있다. 본 발명은 우선 순위화 스케쥴링을 구현하기 위해 DRR 알고리즘에 대한 개선을 포함한다. 가장 높은 우선 순위 클래스 큐는 그 퀀텀이 소진될때까지 서비스되며, 이때, 다음번의 보다 높은 우선 순위 클래스가 스캔된다. 모든 클래스들이 그 퀀텀이 소진되었을 때, 새로운 DRR 라운드가 시작된다.

그 우선 순위 DRR 알고리즘을 위한 클래스의 퀀텀은 클래스를 위해 구축된 최대 할당 대역폭(MAB)에 기초하여 스케쥴러에 의해 산출된다. 상기 MAB는 본 발명의 범주내에서 다른 방법들이 사용될 수도 있지만, 1 내지 100의 범위의 정수 백분율 포인트들의 단위로 표현되는 것이 편리하다.

클래스에 할당된 MAB들은 각 클래스들 위한 퀀텀들의 비율이 각 클래스를 위한 MAB들의 비율과 동일해지도록 DRR 목적을 위한 그 퀀텀을 결정한다. MAB로부터 퀀텀을 연산하는 한가지 알고리즘이 하기에 설명된다. 가장 높은 MAB를 가진 클래스가 시스템내에서 허용된 최대 패킷 사이즈인 최대 퀀텀을 부여받는다. IP 라우팅 프로토콜에 대하여, 적절한 최대치는 1600 바이트의 형상이며, 이는 이더넷 로컬 에리어 네트워크들(LANs)을 위한 IP 최대 전송 유니트(MTU)를 초과한다. 다른 클래스들은 최고 MAB에 대한 그 MAB의 비율에 기초한 퀀텀이 할당된다. 예로서, 최고 MAB가 50%인 것으로 가정하면, 이는 1600의 클래스 퀀텀이 할당된다. 10%의 MAB를 가진 클래스는 10/50*1600 또는 320 바이트의 퀀텀을 받는다. 이 퀀텀 할당 알고리즘을 사용하여, 예약된 레이트들의 동적 범위는 1500 내지 1로 한정된다. 이상적으로, 1600 바이트 디피싯을 누산하기 위해 필요한 라운드들의 수를 한정하기 위해서, 상기 동적 범위는 약 100 내지 1로 한정되어야만 한다.

본 발명의 스케쥴러의 중요한 개념은 모든 0이 아닌 우선 순위의 흐름들이 두 번, 즉, 한번은 그 우선 순위 큐 스케쥴러에 의해, 그리고, 한번은 최선형(BE) 우선 순위 레벨 0 DRR 스케쥴러에 의해 스캐닝된다는 것이다. 이것의 목적은 최선형 대역폭에 대해서도 우선 순위화 흐름들에 대해 대역폭을 보증하는 것이다. 예로서, 10kbps 트래픽 레이트를 가진 5개의 우선 순위화 흐름들과, 500kbps 채널을 공유하는 1개의 최선형 흐름을 고려한다. 우선 순위화 흐름들은 가용한 500kbps 중 단지 50kbps만을 예약하지만, 이들은 최선형을 위해 남겨진 450kbps를 공유하기 위한 소정의 메카니즘이 필요하다. 상기 흐름들을 상술한 바와 같이 두 번 스캐닝하는 것은 이 목적을 달성한다.

계속적으로 백로그되는 흐름들의 기간 동안 수신된 흐름의 실제 대역폭은 두 개의 레이트들의 합이다.

1. 흐름의 클래스의 우선 순위 레벨에서 전송되는 흐름의 공시 트래픽 레이트, 및

2. 잔여 최선형 용량의 흐름의 몫.

IP 네트워킹에서, 대부분의 식별된 흐름들은 버스트 상태이며, 대부분의 흐름들은 임의의 주어진 순간에 아이들 상태이다. 소정의 주어진 흐름의 서비스 몫은 모든 할당된 흐름들의 퀀텀들의 합으로 그 퀀텀을 나눈 것이 아니며, 그 퀀텀을 활성 흐름들의 퀀텀들의 합으로 나눈 것이다. "할당된"이라는 용어는 스펙트럼 관리가 특정 RF 채널에 모뎀을 할당할 때, 채널에 할당된 흐름을 지칭하는 것이다. 흐름은 그 흐름당 큐상에 큐 상태가 된 패킷들을 가지거나(즉, 상태가 되거나) 실제 전송되는 패킷을 가질 때만 활성 상태인 것으로 간주된다.

예로서, 채널에 할당된 최선형 또는 우선 순위 0 레벨에 100개의 흐름들이 존재하는 것으로 가정한다. 각각은 1500바이트의 흐름 퀀텀이 주어져 있다. 주어진 폭주 기간(즉, 하나 이상의 패킷이 큐상태가 되는 경우)에 걸쳐, 모뎀들 중 단지 10개만이 소정의 데이터를 전송했다. 단지 10개의 모뎀들만이 활성상태이기 때문에, 활성 퀀텀들의 합은 15000이며, 각 모뎀은 대역폭의 1500/15000 또는 우선 순위 0(최하) 트래픽을 위해 가용화된 대역폭 중 10%를 전송하기 위한 기회를 받는다.

초과 예약시 본 발명 스케쥴러의 동작은 중요하다. 초과 예약은 전송 링크에 도입된 트래픽 레이트가 흐름들의 클래스에 할당된 링크의 할당된 용량을 초과할 때 발생한다. 각 클래스는 독립적으로 스케쥴링되고, 어떠한 클래스도 그 평균 레이트를 초과하는 것이 허용되지 않는다(클래스별 스케쥴링 레벨에 DRR이 사용될 때 퀀텀 할당에 의해 결정되는 바와 같이). 본 발명의 대안적인 실시예에서, 클래스당 스케쥴링 스텝은 WFQ를 사용할 수도 있으며, 이 경우에, 각 클래스도 대역폭의 그 할당된 몫보다 많이 사용하는 것이 차단된다.

본 발명의 변형된 디피싯 라운드 로빈 방법은 우선 순위화 포워딩을 제공한다. 우선 순위화 DRR 방법은 본 발명의 스케쥴러의 최종 클래스별 스케쥴링 단계에서 사용되는 것이 적합하다. 종래 기술의 DRR은 각 스케쥴링된 클래스를 위해 할당된 퀀텀의 개념에 의존하며, 라운드 로빈 방식으로 각 클래스를 방문한다. 본 발명에서는, 각 클래스가 우선 순위를 부여 받는다. 본 발명의 우선 순위화 DRR 방법은 우선 순위의 순서로 각 클래스를 방문하며, 동일한 우선 순위에 있는 클래스들에 대해서는 특정 순서가 없다. 최고 우선 순위 클래스는 그 클래스별 큐상의 모든 패킷들을 포워딩하거나, 그 디피싯 카운트를 소진할때까지 서비스된다. 이 시점에서, 다음의 최고 우선 순위 클래스가 서비스된다. 모든 클래스들이 그 클래스별 큐이 비워지거나, 그 디피싯이 소진되었을 때, 새로운 DRR 라운드가 시작, 즉, 모든 백로그 상태의 클래스들이 새로운 퀀텀을 부여받는다. DRR 알고리즘에서와 마찬가지로, 퀀텀 할당의 비율은 클래스에 할당된 전송 링크 대역폭의 장기 비율(long-term ratio)을 결정한다.

본 발명의 양호한 실시예에서, 흐름들은 초과 예약의 구축된 레벨에 기초하여 전송 채널로 도입된다. 한가지 접근 방식은 서비스 클래스내에 가정 비율 활성 흐름들을 구축하는 것이다. 예로서, 단지 10%의 흐름들만이 동시에 활성화될 것으로 기대되는 경우에, 이 경우를 위한 구축 활성율(CAP) 구축은 10%이다.

각 흐름은 트래픽 레이트 토큰 버킷을 위한 트래픽 레이트 및 트래픽 버스트 파라미터들을 제공하는 식별 트래픽 사양을 가진다. 상기 흐름으로부터의 패킷들이 트래픽 사양에 정합되는지 비정합되는지가 결정된다. 각 클래스는 이와 연계된 최소 예약 대역폭을 가진다. 이는 ATM 네트워크를 위한 최소 셀 레이트의 프레임 릴레이 네트워크들의 규정 정보 전송 속도와 유사하다. 최소 예약 레이트는 본 발명의 방법의 트래픽 레이트 토큰 버킷을 위한 트래픽 사양으로서 사용된다.

그후, 초과 예약 도입 제어 방법은 채널상의 클래스를 위해 배치된 MAB 백분율보다 도입된 흐름의 예약 레이트들의 합과 CAP 백분율의 곱이 작도록 흐름들을 도입시킨다. 예로서, CAP가 10%로 설정되는 경우에, 클래스는 1Mbps 채널의 50%의 MAB를 갖도록 구축되며, 상기 클래스는 100 Kbps의 예약 트래픽 레이트를 가지며, 도입된 흐름의 수는 하기와 같다.

도입된 흐름들의 수

(MAB*용량)/CAP*예약 대역폭)

= 0.50*1,000,000/(0.10*100, 000)

=50 도입된 흐름들

흐름들이 예약 초과상황에서 도입될 때, CAP 기대 활성 흐름들의 수 보다 많은 흐름들이 실제로 활성화될 수 있다. 본 발명의 스케쥴링 방법은 각각 그 대역폭의 "규정된" 레이트 보다 작게 수신하도록, 그리고, 어떠한 다른 클래스도 영향을 받지 않도록 초과예약된 도입 흐름들 모두들 사이에서 균등하게 상기 클래스를 위한 구축 용량을 분할한다. 모든 흐름들은 최선형 대역폭을 사용하게 되지만, 그러나, 다른 최선형 흐름들이 비활성화된 경우에, 흐름들이 그 규정된 대역폭을 받는 것이 여전히 가능하다. 또한, 그 클래스에 대해 초과 예약된 상황을 발견하기 위해, 즉, 흐름들의 CAP 구축 활성 백분율이 동시에 지연될때를 발견하기 위해 시스템내로 도달되는 패킷들의 수를 보고하는 것이 바람직하다. 이는 CAP 파라미터를 설정하는 방식에 대한 지침을 제공하며, 서비스 레벨 계약의 기초로서 사용될 수 있다.

트래픽 사양과 도입 정책을 변경함으로써, 대부분의 QOS 서비스 개념이 본 발명을 사용하여 구현될 수 있다.

보증된 서비스는 0이 아닌 트래픽 버킷과 0의 초과 예약을 가진(즉, 100%의 CAP가 동시에 활성화되는) 최고 우선 순위를 가지는 클래스를 제공할 수 있다. 이 조합은 최소 딜레이들과 최대 대역폭들을 보증할 수 있다.

규정 정보 전송 속도(CIR) 서비스 클래스는 0이 아닌 트래픽 레이트와, 보증된 클래스 보다 낮은 우선 순위 및 허용된 초과 예약으로 구현될 수 있다. 초과 예약을 허용함으로써, 통상적인 데이터 통신의 버스트형 트래픽이 높은 링크 활용도를 유지하면서 통계학적으로 보증된 서비스를 받을 수 있다.

우선 순위화 최선형 서비스 클래스는 무한 트래픽 레이트 버킷과 무한 초과 예약(CAP=0)과, CIR 클래스 보다 낮지만 디폴트 서비스 클래스 보다 양호한 클래스 우선 순위로 제공될 수 있다.

디폴트 서비스 클래스는 무제한 트래픽 레이트 버킷과, 무제한 초과 예약 및 우선 순위화 최선형 클래스 보다 낮은 우선 순위를 가질 수 있다.

벌크 또는 낮은 저순위 서비스 클래스는 무제한 트래픽 레이트와 무제한 초과 예약을 가지며, 디폴트 클래스 보다 낮은 우선 순위를 가진다.

도 2는 본 발명의 상술한 실시예에서 사용된 핵심 FLOW 구조들을 도시하고 있다. FLOW 구조(100)는 패킷들의 단일 흐름와 연계된 모든 정보를 포함하고 있다. 각 흐름은 PacketQ로 명명된 큐 구조를 포함하며, 상기 PacketQ는 전송 대상 패킷들의 큐의 시작과 종료에 대한 포인터들을 포함한다.

QITEM 구조(110)는 그를 포함하는 구조들이 이중 링크식 리스트에 링크되는 것을 허용한다. QUEUE 구조(120)는 그 리스트내의 아이템들의 카운트와 함께, 주어진 리스트의 헤드 및 테일 QITEM들에 대한 포인터들을 포함하고 있다.

SLICONF 구조(130)는 특정 인터페이스(Intf 150)상에서 동작할 때 특정 서비스 클래스(SCLASS 140)의 동작을 위해 구축되는 것으로 간주되는 파라미터들을 포함한다. 이는 예로서 파라미터 초과 예약을 포함하며, 상기 파라미터 초과예약은 용량을 초과하는 예약 레이트들을 가진 인터페이스에 대해 실제 대역폭의 몇배수가 도입된 흐름들에 의해 초과 예약될 수 있는지를 나타낸다.

DRRITEM 구조(160)는 디피싯 라운드 로빈(DRR) 알고리즘을 사용하여 흐름(또는 서비스 클래스)을 스케쥴링하는데 소요되는 파라미터들을 포함한다. DRR 알고리즘은 초기에 각 아이템에 고정된 퀀텀을 할당함으로써 동작한다. 흐름들은 그 퀀텀 할당의 상대 비율에 따라 대역폭이 할당된다. 퀀텀 할당은 각 흐름에 대하여 고정되며, 흐름이 생성될 때 결정된다.

흐름을 위한 퀀텀은 DRRITEM의 U32 퀀텀 필드(162)에 저장된다. 소정의 주어진 시점에서, 흐름이 그 DRRITEM의 디피싯 카운트에 저장된 바이트들의 양을 전송하게 된다. DRR 큐의 각 DRR 라운드의 시작시, 그 큐내의 모든 DRRITEM은 그 퀀텀의 양만큼 그 디피싯 카운트가 증가된다. 각 DRRITEM이 처리될때(도 6 내지 10에 관하여 설명된 NextBurst 방법에 의해), 그 디피싯값이 그 흐름을 위한 다음 패킷에 의해 보내질 바이트들의 수에 대하여 비교된다. 디피싯 카운트내의 바이트들의 카운트가 불충분한 경우에, 흐름은 그 DRR 큐의 끝으로 이동되어 그 디피싯이 증분되게 되는 다음 DRR 라운드를 기다린다. 디피싯에 충분한 바이트들이 존재하는 경우에, 패킷이 송신되고, 디피싯 카운트가 보내진 바이트들의 수만큼 감소된다. 장시간의 구동에 걸쳐, DRR 알고리즘은 그 퀀텀 할당들의 비율에 기반하여, DRR 큐내의 모든 흐름들에 공정하게 대역폭을 제공한다. 이는 통상적인 단일 전송 큐의 선입 선수행(FCFS) 서비스보다 공정하며, 그 이유는 보다 적고 보다 작은 패킷들을 가진 흐름들이 많고 큰 패킷들을 가진 흐름들의 패킷 뒤에서 백로그하지 않아도 되기 때문이다.

서비스 레벨 인터페이스(SLI) 구조(170)는 상기 스케쥴링을 제어하며, 단일 인터페이스(Intf)상에서 동작하는 단일 서비스 클래스(SCLASS)의 동작의 통계치들을 포함한다. 본 발명의 스케쥴링 방법은 SLI를 위해 구축된 가중에 따라 각 SLI에 대한 인터페이스의 대역폭의 부분들을 논리적으로 제공하는 것을 요구한다. 그 할당된 대역폭내에서, 상기 실시예는 동일 서비스 클래스내의 모든 활성 흐름들에 대해 균등 가중 부분들을 제공한다.

SLI들은 서비스 클래스(SCLASS 140)의 우선 순위 필드에 관하여 배열되어 있는 것으로 간주된다. INTF 구조(150)의 p_classes 필드는 SLI 구조들(170)의 링크된 리스트를 이끌며, SLI내에 있는 우선 순위라 명명된 QITEM 구조(110)를 통해 링크되어 있다.

본 발명은 세 개의 분리된 DRR 큐들을 사용한다.

흐름 우선 순위 DRR 큐 : 흐름 구조(100)는 동일 서비스 클래스에(그리고, 따라서, 동일 우선 순위 레벨에) 속하는 모든 흐름들을 링크하는 pq라 지칭되는 DRRITEM을 포함한다. 이 큐의 헤드 및 테일은 SLI 구조(170)내에서 흐름 리스트라 명명된 QUEUE 구조(120)이다.

흐름 최선형 DRR 큐 : 흐름 구조(100)는 인터페이스상의 모든 활성 흐름들을 링크하는 bq라 지칭되는 DRRITEM(160)을 포함한다. 인터페이스 구조(Inft 150)는 흐름들의 링크된 리스트의 헤드와 테일을 제공하는 QUEUE 구조(120)를 포함한다.

클래스 DRR 큐 : 인터페이스상에서 활성 상태인 서비스 레벨 인터페이스(SLI) 구조(170)는 SLI 자체의 DRR 큐의 일부가 되는 것으로 간주된다. 스케쥴링의 이 클래스 레벨을 위한 상기 DRRITEM(160)은 SLI(170)의 cq 오브젝트내에 저장된다.

TOKBKT 구조(180)는 흐름들이 그 서비스 클래스 대역폭을 사용하도록 허용될 때를 결정하도록 사용되는 트래픽 레이트 토큰 버킷과, 흐름 최대 허용 포워딩 레이트 보다 빠르게 도달할 때 그 흐름 큐상에 흐름 패킷들을 유지하도록 사용되는 최대 레이트 토큰 버킷 양자 모두를 설명한다.

도 3은 도 2의 구조들의 예시적 상태를 도시하고 있다. 상기 구조들 중 관련 필드들 만이 도시되어 있다. 데이터 통신 디바이스의 특정 전송 인터페이스에 대하여, 단일 Intf 구조는 우선 순위 순서가 감소하는 SLI의 링크된 리스트들을 이끄는 QUEUE 구조를 포함한다. 예로서, 두 개의 서비스 클래스들, 즉, 골드, SCLASS = "gold" 구조(200)와, 디폴트 서비스 클래스 구조(260)를 위한 디폴트, SCLASS = "default" 구조(210)가 존재한다. 디폴트 서비스 클래스를 위한 SLI 구조가 항상 존재한다.

1. 흐름 1(220)은 골드 SCLASS내의 두 개의 활성 흐름들 중 하나이다. 모든 활성 흐름들과 마찬가지로, 이는 흐름상으로 보내기 위한 패킷들(224, 226)의 링크된 리스트를 이끄는 PacketQ(222)라 명명된 QUEUE 구조를 가진다. 본 발명의 스케쥴링 방법은 항상 동일한 흐름으로부터의 패킷들을 순서대로 송신한다. 도 3에서, 단지 흐름 1만이 그 PacketQ상에 패킷들을 갖는 것으로 도시되어 있지만, 본 실시예에서, 모든 활성 흐름들은 이런 패킷들을 가진다. PacketQ와 패킷들은 간략화를 위해 다른 흐름들에는 도시되어 있지 않다.

흐름 1(220)은 두 개의 DRR 큐들상에 존재하는 것으로 간주된다. 흐름 우선 순위 큐는 이 인터페이스상의 골드 클래스를 위한 SLI(230)내의 플로우리스트(FlowList)라 명명된 QUEUE 구조에 의해 인도된다. 흐름 1내의 pq라 명명된 DRRITEM은 그 SLI 플로우리스트상의 다른 흐름, 즉, 흐름 2(235)에 대한 링크를 포함한다. 또한, 흐름 1은 최선형 DRR 큐상에 있는 것으로 간주되며, 상기 최선형 DRR 큐은 Intf 인터페이스 구조(240)내의 beq라 명명된 QUEUE 구조에 의해 인도된다. 최선형 DRR 큐상의 모든 흐름들은 흐름 구조내의 "bq"라 명명된 DRRITEM을 경유하여 링크된다. 도 3의 모든 흐름들(220, 235, 245, 250)은 Intf.beq(240)에 의해 인도되는 링크된 리스트상에 존재하며, 그 bq DRRITEM 구조들을 경유하여 링크되어 있다는 것을 주목하여야 한다.

2. 흐름 2(235)는 흐름 1과 함께 활성화되는 골드 서비스 클래스내의 다른 흐름이다. 활성화라는 용어는 흐름 또는 SLI에 적용될 때 전송 대기 패킷을 가지는 것을 의미한다.

3. 흐름 3(245)은 최선형 흐름이다. 비록 이들이 도시되어 있지는 않지만, 이는 송신하기 위한 패킷들을 가진 PacketQ를 포함하며, 디폴트 서비스 클래스(미도시)의 동작을 위해 SLI에 대한 후위를 지시하는 sli 포인터를 포함한다. 도 3은 그 pq DRRITEM을 사용하지 않으며, 이는 bq DRRITEM을 사용하며, 최선형 DRR 큐상에만 존재하는 것으로 간주된다.

4. 흐름 4(250)는 흐름 3(245)과 유사하다. 이는 디폴트 서비스 클래스하에서만 스케쥴링된 대역폭인 최선형 흐름이다.

각 흐름은 그들이 분류되는 서비스 클래스(SCLASS) 구조를 지시하는 S255라 명명된 포인터를 가진다. 모든 흐름들은 하나의 클래스내에 있는 것으로 고려된다. 디폴트 클래스는 분류되지 않은 흐름들을 포함한다.

디폴트 서비스 클래스(210)에 속하는 것으로 간주되는 흐름(흐름 3(245) 및 흐름 4(250))은 pq DRRITEM을 경유하여 링크되지 않는다. 대신, 디폴트 클래스 SLI가 NextBurst 절차에 의해 대역폭이 제공될 때, 그 위의 흐름들은 디폴트 클래스 SLI(260)의 플로우리스트 QUEUE가 아닌 Inft 구조(240)의 beq 리스트 오프로부터 얻어진다.

또한, 모든 흐름들은 인터페이스상의 그 동작을 제어하는 SLI 구조를 지시하는 포인터 sli를 포함한다. 도 3에서는, 간략화를 위해, 흐름 2(235)를 위한 sli 백 포인터만이 도시되어 있다.

도 4 및 도 5는 본 발명의 스케쥴링 방법에 대한 새로운 패킷의 도착을 프로세싱하기 위한 절차의 동작을 도시한다. 도 4의 단계들은 도 2에 설명된 바와 같은 필드들을 사용하여 C 컴퓨터 언어의 선언들로 표현되어 있지만, 본 발명이 이 컴퓨터 언어에 한정되는 것은 아니다.

도 4를 참조하면, 데이터 통신 장치가 인터페이스의 스케쥴러에 대한 패킷의 도달을 프로세싱할 때, 이는 스텝 300에서 처리 PktArrival()을 호출한다.

Pkt는 패킷의 포인터와 길이를 포함하는 송신 대상 패킷이다.

F는 패킷이 분류된 FLOW 구조에 대한 포인터이다.

I는 패킷이 송신되도록 그 위로 라우팅되는 INTF 구조에 대한 포인터이다.

스텝 305에서, 상기 방법은 흐름 F의 패킷상의 큐된 패킷들의 수가 흐름 F의 서비스 클래스를 위해 허용된 최대 버퍼수를 초과하는지를 체크한다. 그런 경우에는, 스텝 310에서 증분되고, 상기 패킷은 스텝 315에서 버려진다.

그렇지 않은 경우에는 스텝 320에서, 새로 도달된 패킷이 흐름 F의 PacketQ 큐상에 큐된다. 본 방법의 q_enq() 함수는 그 제 2 독립 변수로서 QITEM에 대한 포인터를 취한다. 스텝 320의 경우에, Pkt 구조는 그 제 1 엘리먼트로서 QITEM을 가지는 것으로 가정한다.

스텝 325에서, 흐름 F의 bActive boolean이 체크된다. 흐름이 이미 활성 상태로 표시된 경우에, 패킷 도착시 어떠한 부가적인 처리도 필요하지 않으며, 처리는 스텝 380(도 5)으로 건너뛴다. 그렇지 않은 경우에, 흐름은 활성 상태로 만들어질 필요가 있으며, 스텝 330에서 도 3과 유사한 데이터 구조내로 도입되게 된다.

도 5를 참조하면, 스텝 335에서, 흐름이 디폴트 서비스 클래스에 속하는지가 체크된다. 그렇지 않으면, 상기 방법은 스텝 340으로 진행하며, 그곳에서, 흐름이 그 (비디폴트, 우선 순위화) SLI의 플로우리스트 QUEUE상에 큐된다. 상기 흐름의 pq DRRITEM내의 QITEM이 동일 SLI의 흐름들을 함께 링크하도록 사용되는 경우에, 우선 순위화 SLI도 스텝 345에서 활성 상태로 표시되며, 활성 흐름들의 카운트(SLI 구조 170의 nflow 필드)가 증분된다.

스텝 345에 이어서, 스텝 350, 355 및 360에서, 상기 방법은 새로 흐름을 활성화시키는 것이 서비스 클래스의 초과예약 상태가 되게 하는지를 체크한다. 각 흐름은 초당 비트들로 표시되는 정규화된 예약 레이트(nrr)와 연계된다. 이는 흐름을 위해 예약된 대역폭이다. 상기 방법은 조작자가 초과 예약, 즉, 도입 흐름 예약 레이트들의 합이 상기 서비스 클래스에 할당된 용량을 초과하는 상태의 흐름들을 구축 및 도입시킬 수 있게 한다. 상기 용량은 백분율로 서비스 클래스별로 할당된다. 서비스 클래스를 위해 할당된 초당 비트들은 SLI의 필드내의 정규화된 최대 할당 레이트 또는 nmar에 저장된다. 소정의 주어진 시점에, 활성 흐름들의 예약 레이트들의 합이 스텝 350에서 SLI의 sumrev 필드에 저장된다. 이것이 스텝 355에서 상기 클래스(nmar)를 위해 할당된 레이트를 초과할 때 스텝 360에서 상기 SLI가 초과예약 상태인 것으로 표시된다. 동작은 스텝 365에서 재시작된다.

흐름을 새로이 활성화시키는 것이 pq DRR 큐상에서 이루어지든 아니든, 처리는 스텝 365로 진행하며, 그곳에서, 상기 흐름은 Intf I의 beq QUEUE 구조에 의해 인도되는 최선형 큐상에 큐된다. 흐름의 bq DRRITEM내의 QITEM은 최선형 흐름 리스트상의 흐름들을 링크시키도록 사용된다.

스텝 370에서, 흐름은 그 디피싯 세트가 퀀텀이 할당된 흐름과 동일한 상태로 현재 DRR 라운드내에서 그 점유를 시작한다. 본 실시예에서, bq(최선형 큐)내의 모든 흐름들과, pq(우선 순위 큐)내의 모든 흐름들은 동일한 퀀텀을 갖는 것으로 간주된다. 예로서, 적합한 퀀텀은 512바이트일 수 있다. 상기 퀀텀은 최대 에터넷 패킷 레이트(1500바이트)보다 작게 선택되어야만 하지만, 패킷의 사이즈에 대한 디피싯을 증분시키기 위해 과도한 수의 DRR 라운드들이 필요하지 않도록 너무 작아서는 안된다. 우선 순위화 SLI들내의 흐름은 두 개의 상이한 DRR 큐들, 즉, 그 자체 클래스 우선 순위화 큐(pq를 경유하여 링크됨)와 최선형 DRR 큐(bq를 경유하여 링크됨)내에 있는 것으로 간주된다는 것을 주목하여야 한다. DR 큐들 양자 모두를 위한 디피싯이 초기화된다.

스텝 375에서, 디폴트(SLI)는 흐름이 최선형 흐름 리스트에 추가되었기 때문에 활성상태인 것으로 표시된다. 디폴트(SLI)상의 활성 흐름들의 카운트가 증분된다.

스텝 380에서, 흐름이 초과 예약 상태에 있는지가 체크된다. 흐름이 활성화되고, 그곳에 이미 그 예약된 레이트들이 그 서비스 클래스를 위한 링크의 할당된 용량을 초과하는 흐름 서비스 클래스내의 다른 활성 흐름들이 존재할 때, 흐름은 초과 예약 상태에 있게 된다. 본 발명의 방법은 이런 흐름들의 초과예약 상태를 유지하고, 초과 예약 상태에서 패킷들의 도착들을 계수한단느 점에서 특유하다.

서비스 클래스들이 초과 예약 상태에 있는지를 발견하기 위해 도착한 패킷은 스텝 30에서 "초과 예약 패킷 도착"의 카운트가 증분되게 한다.

스텝 395는 패킷 도착 프로세싱을 종결한다.

패킷이 분류되는 흐름은 이제 도 3에 예시된 데이터 구조로 삽입된다.

도 6, 7, 8, 9 및 10은 송신될 패킷들 또는 바이트들의 NextBurst의 스케쥴링 방법을 도시하고 있다. NextBurst 작업은 하나 이상의 패킷들의 송신이 완료되고, 데이터 통신 송신기가 다음 패킷 또는 패킷들의 그룹을 선택하도록 스케쥴러를 요청할 때, 시동된다. 알고리즘은 NextBurst의 호출자가 전송될 바이트들의 최대수(maxBurst) 또는 송신될 패킷들의 최대수(maxPkts)를 특정지을수 있도록 표현된다. 이들 두 파라미터들은 다음 버스트가 송신될 INTF 인터페이스에 대한 포인터와 함께 NextBurst 작업(400)에 대한 파라미터들을 형성한다.

NextBurst 루틴은 다수의 로컬 변수들을 가지고 있다.

active_classes는 활성 상태인 SLI들의 수의 카운트이다.

overlimit_classes는 "오버리미트"인 SLI들의 수의 카운트이다. 오버리미트 SLI는 모든 흐름들이 "오버리미트"인 것이다. 오버리미트 흐름은 초과된 그 트래픽 토큰 버킷을 가지는 것이다. 트래픽 토큰 버킷은 흐름이 그 예약 최소 레이트를 초과하는지를 측정한다.

nover은 특정 서비스 클래스내의 오버리미트 흐름들의 수의 카운트이다.

bReturn은 상기 방법이 NextBurst 루틴이 리턴되어야만 한다는 것을 결정할 때, TRUE(즉, 1로 설정되는) 제어 플래그이다.

P는 대역폭을 제공받는 현 SLI 구조에 대한 포인터이다.

F는 대역폭을 제공받는 현 흐름(P 내에서)에 대한 포인터이다.

Pkt는 시험되는 F의 현 패킷에 대한 포인터이다.

스텝 405에서, 상기 방법은 로컬 변수들을 초기화하고, 모든 SLI들을 통해 스캔하며(INTF내의 p_classes QUEUE를 경유하여), 상기 클래스의 bOverlimit 비트를 0(즉, FALSE)으로 설정한다.

스텝 410은 "우선 순위 DRR 큐"의 다음 DRR 라운드를 시작한다. 이는 로컬 SLI 포인터(P)를 INTF의 p_classes 큐의 헤드로 설정한다. "q_head(QUEUE)" 작업은 큐의 헤드에 대한 포인터를 반환하지만, 이를 상기 큐로부터 제거하지는 않는다는 것을 주목하여야 한다.

스텝 415는 모든 클래스들이 현재의 우선 순위 클래스 DRR 라운드에서 대역폭을 제공받았는지를 체크한다. 그런 경우에, P 포인터는 0이되며, 다음 클래스 DRR 라운드가 스텝 420에서 시작된다. 이 스텝에서, 스텝 425가 상기 인터페이스내의 각 클래스(즉, bExhausted==1인 INTF 구조의 P-classes QUEUE를 경유하여 링크된 모든 SLI들)에 대해 실행된다. 이는 이들이 그 클래스 DRR 디피싯을 소진한다는 것을 의미한다. 그 디피싯은 스텝 430에서 전용 퀀텀에 의해 증가되며, bExhausted 플래그는 다음 클래스 DRR 라운드를 위한 SLI를 준비하도록 클리어된다.

바로 완료된 라운드, "오버리미트" 클래스들의 수는 로컬 카운터 "overlimit_classes"에서 누산되었다. 이들은 흐름들 중 소정의 것을 패킷을 포워딩하기에 적합하게 하기 위해 NextBurst에 대한 추후 호출까지 기다려야만 하는 클래스들이다. 스텝 435에서, 이 overlimit_classes카운트가 활성 클래스들의 수와 비교되며, 모든 클래스들이 오버리미트인 경우에, NextBurst는 어떠한 패킷도 포워딩할 수 없으며, 스텝 445에서 sent==0으로 복귀한다.

스텝 440에서, 마지막 클래스 DRR 라운드가 더 이상 어떠한 활성 클래스들도 없도록 모든 큐된 패킷들을 비워버린 경우에, NextBurst도 스텝 445로 복귀한다. 그러나, 여전히 활성 클래스들이 존재하는 경우에, 스텝 410으로 다시 천이함으로써 새로운 클래스 DRR 라운드가 시작한다.

다시 스텝 415에서, 현 클래스 DRR 라운드가 끝나지 않은 경우, 처리는 스텝 450으로 진행한다. 스텝 450에서, 현 SLI가 활성 상태로 표시되지 않은 경우, 이는 활성 상태인 흐름을 갖지 않는다는 것을 의미하며, 생략될 수 있다는 것을 의미한다. 이 경우에, 상기 방법은 스텝 455로 진행하여 인터페이스의 p_classes 큐상의 다음 하위 우선 순위 SLI를 취하며, 그후, 스텝 415로 후행한다.

현 SLI(P로 어드레스됨)가 활성 상태인 경우, 상기 방법은 스텝 450으로 이행하며, 그곳에서, active_classes의 수가 1만큼 증분된다.

후속하는 스텝 460에서, SLI는 현 우선 순위 DRR 라운드내의 그 디피싯이 소진되었는지가 체크된다. 상기 P->bExhaysted 플래그가 이 목적을 위해 사용된다. 이런 경우에, 이 SLI는 현 우선 순위 DRR 라운드에서 대역폭을 받을 수 없으며, 다음 SLI가 스텝 455에서 체크되어야만 한다.

그렇지 않은 경우에, 상기 방법은 스텝 470으로 이어지고, 그곳에서, 현 SLI의 bOverlimit 플래그가 체크된다. 이 플래그는 SLI의 모든 흐름들이 오버리미트일 때 설정된다. 이 경우에, 우선 순위 SLI에 대역폭이 주어지지 않으며, 다음 SLI가 스텝 455를 통해 체크되어야만 한다.

그렇지 않은 경우에, 상기 방법은 스텝 475, 480 및 485로 이어지고, 그곳에서, 현 클래스가 "디폴트" 클래스인지 아닌지에 따라 로컬 변수 "FlowQP"가 설정되게 된다. 현 CLI(P)가 디폴트인 경우에, 대역폭이 제공될 흐름들의 관련 큐은 흐름의 I->beq "최선형" 큐이다. 현 CLI(P)가 우선 순위 큐인 경우에, 그때, 적합한 흐름들만이 상기 CLI의 플로우리스트 큐로부터 링크된 것들이다. FlowQP는 전용 QUEUE 구조에 대한 포인터로 설정된다.

어느 한쪽의 경우에, 상기 방법은 스텝 490으로 이어지며, 그곳에서, 현 클래스내의 오버리미트 흐름들의 수(nover)가 0으로 초기화된다.

스텝 495는 현 서비스 클래스의 "Next Flow"에 대해 대역폭을 제공하기 위해 공통 프로세싱 포인트를 표시한다. "Next Flow"로 라벨링된 오프시트 커넥터 오브젝트(off-sheet connector object) "505"가 도 6으로부터 참조된다. 스텝 495에서, 로컬 포인터 F는 FlowQP 큐의 헤드로 설정된다(그러나, 상기 흐름은 큐 해지되지 않는다).

다음에, 상기 방법은 스텝 500에서 현 SLI의 모든 흐름들이 그 패킷들이 비워졌는지, 즉, F가 눌(null)인지를 체크한다. 그렇지 않으면, 상기 방법은 도 7의 스텝 525로 이어진다.

스텝 500에서, 주어진 서비스 클래스의 모든 흐름들이 소진 것으로 결정된 경우에(즉, F==0), 상기 서비스 클래스는 스텝 510에서 비활성 상태로 표시되며, 활성 서비스 클래스들의 총수가 감소된다. 스텝 515에서, 상기 방법은 NextBurst 방법의 현재의 시도가 패킷들의 양호한 최대수를 송신하였을 때 스텝 795에서 설정된 bReturn 플래그를 체크한다. 만약 그런 경우에, NextBurst 방법은 스텝 520에서 종결된다. 그렇지 않으면, 다음 서비스 클래스의 처리가 스텝 455에서 이어진다.

스텝 525에서, 상기 방법은 현 서비스 클래스내의 모든 흐름들이 오버리미트인지를 체크한다. 그런 경우에, 상기 방법은 스텝 530으로 이행하고, 그곳에서, 상기 클래스 자체가 오버리미트로 표시되며, 다음 서비스 클래스들을 체크하기 위한 스텝 455로의 NextBurst 방법의 이 시도의 이행을 위해 오버리미트 클래스들의 수가 검출된다.

클래스 자체가 오버리미트가 아닌 경우에, 상기 방법은 스텝 525로부터 스텝 535로 이행한다. 이는 현 흐름상의 다음 패킷의 "Next Packet 처리를 시작한다. 로컬 포인터 Pkt가 현 흐름의 패킷 큐(PacketQ)의 헤드로 설정되지만, 패킷 자체는 큐로부터 제거되지 않는다.

후속 단계 545에서, Pkt 포인터가 체크된다. 이것이 NULL인 경우, 현 흐름내의 모든 패킷들이 송신되고, 상기 방법은 스텝 585로 이행한다. 스텝 585는 흐름이 비활성 상태가 될 때 상기 케이스를 위해 도 2의 데이터 구조와 통계치들을 갱신한다. 상기 흐름은 우선 순위 DRR 큐(즉, SLI 플로우리스트 QUEUE)와 최선형 DRR 큐(INTF의 "beq" QUEUE로부터) 양자 모두로부터 제거된다. 또한, 스텝 585는 클래스내의 모든 활성 흐름들의 예약 레이트들의 합의 카운트, 즉, "P->sumresv" 카운트를 감소시킨다. 스텝 590에서, P->sumrev가 "정규화된 최대 할당 레이트(P->nmar)" 아래로 떨어지는 경우에, 상기 클래스는 더 이상 초과 예약 상태에 있는 것으로 간주되지 않는다. 이 경우에, P->Overbooked 플래그는 스텝 595에서 클리어된다. 각 경우에, 스텝 590에서의 체크 이후, 상기 방법은 스텝 495에서 현 SLI내의 다음 흐름으로 이어진다.

다시 스텝 545에서, 현 Pkt 포인터가 눌이 아닌 경우에, 상기 방법은 스텝 550으로 이행한다. 이 스텝에서, bReturn 플래그가 스텝 765에 의해 설정되었는지가 체크되며, 이 경우에, 상기 방법은 스텝 560으로 복귀된다. bReturn 플래그가 아직 설정되지 않은 경우에, 처리는 스텝 555로 이어진다.

스텝 555는 패킷을 전송하는 것이 상기 NextBurst 루틴이 NextBurst 루틴 호출에서 허용된 최대 바이트수를 초과하게 만드는지를 체크한다. 현재 실행중인 송신된 총 바이트들은 "sent" 로컬 변수로 유지된다. 이 경우에, 현 패킷을 송신하지 않고 NextBurst는 스텝 560으로 리턴한다.

스텝 555가 루틴 호출당 최대 버스트가 초과되지 않은 것을 검출하지 못하는 경우에, 상기 방법은 스텝 565로 이어지며, 여기서, 우선 순위 DRR 큐 "디피싯"가 체크된다. 패킷 길이가 우선 순위 "클래스" DRR 아이템의 디피싯 카운트(즉, P->cq. 디피싯)를 초과하는 경우에, 현 클래스는 본 우선 순위 DRR 라운드에서 그 허용된 전송이 소진된다. 이 경우에, 서비스 클래스는 bExhausted 플래그가 1(참)로 설정된 상태로 표시되며, 상기 방법은 스텝 455에서 다음 서비스 클래스를 체크하도록 진행한다.

그러나, 서비스 클래스 DRR 디피싯이 스텝 565에서 소진되지 않은 경우에, 상기 방법은 스텝 575에서 다시 시작하며, 여기서, 상기 흐름을 위한 최대 레이트 토큰 버킷이 갱신된다. 토큰 버킷을 갱신시키기 위한 처리(tokbkt_update())는 그 최근 갱신으로부터 경과된 CPU 프로세서 틱들(ticks)의 두에 기초하여 토큰 버킷 카운트에 토큰들의 적절한 수를 가산한다. 토큰 버킷내의 각 "토큰"은 일 바이트를 전송하기 위한 권리를 부여한다.

스텝 580에서, 상기 방법은 패킷 길이를 바로 갱신된 최대 레이트 토큰 버킷내의 토큰들의 수(F->maxBkt)와 비교한다. 토큰들이 불충분한 경우에, 상기 방법은 스텝 600으로 이행한다. 여기에서, 상기 방법은 이런 "overMaximum" 패킷 스케쥴링 시도의 카운트를 증분하고, 현 서비스 클래스내의 "오버리미트" 흐름들의 수(로컬 변수 "nover")를 증분한다. 스텝 605에서, 작업 "MoveFlowToEnd()"가 상기 오버리미트 흐름을 그 현 흐름 큐의 끝으로 이동시키기 위해 시도된다. 상기 흐름은 그 최대 레이트 토큰 버킷에 보다 많은 토큰들을 추가하기 위해 충분한 시간이 경과될 수 있는 NextBurst에 대한 후속하는 호출까지 패킷들을 전송하는 것이 허용되지 않는다. 상기 방법은 스텝 605로부터 스텝 495에서 현 클래스내의 다음 흐름을 취급하도록 이행된다.

상기 방법이 스텝 580에서 최대 레이트 토큰 버킷 리미터를 통과하는 경우에, 이는 스텝 610으로 이어지고, 이는 도 8 및 도 9의 NextBurst 처리로 이어지는 커넥터이다.

스텝 620은 도 7로부터의 NextBurst 처리의 연속이다.

도 625는 대역폭을 제공받은 현 클래스가 디폴트 클래스인지를 체크한다. 그렇지 않은 경우에, 스텝 630은 흐름을 위한 예약 레이트 "트래픽" 토큰 버킷을 갱신하고, 스텝 635는 상기 흐름이 현재 그 예약 레이트 아래인지를 체크한다. 그렇지 않은 경우에, 상기 방법은 스텝 640에서 상기 패킷이 그 트래픽 레이트를 초과한 것으로 표시하고, 상기 흐름을 스텝 645의 그 우선 순위 DRR 리스트의 끈으로 이동시켜, 스텝 700 내지 720에서 설명한 바와 같은 MoveFlowToEnd() 하위 방법을 시도한다. 상기 흐름은 그 우선 순위화 서비스 클래스에 제공된 대역폭내의 그 트래픽 레이트 토큰 버킷을 초과하는 트래픽을 전송하는 것이 허용되지 않는다. 이는 상기 대역폭이 디폴트 서비스 클래스에 제공될 때에만 전송할 수 있다. 상기 흐름을 그 CLI의 플로우리스트의 끝으로 이동시킨 이후에, 스텝 650은 현 클래스내의 다음 흐름을 처리하기 위해 스텝 495로 이행한다.

스텝 635가 상기 흐름이 그 예약 트래픽 레이트 한계를 초과하지 않은 것으로 결정한 경우, 이는 스텝 655로 이행한다. 이 스텝은 상기 흐름을 위한 현 패킷이 흐름별 DRR 라운드를 위한 디피싯, 즉, F->pq.deficit를 초과하는지를 체크한다. 그런 경우에, 상기 흐름이 다음 흐름별 DRR 라운드까지 백로그되어야만 하기 때문에, 상기 루틴은 스텝 660으로 이행한다. 스텝 660에서, 상기 흐름의 "pq"DRR 아이템 디피싯은 퀀텀 만큼 증가된다. 스텝 665에서, MoveFlowToEnd 하위 방법이 시도되어 상기 흐름을 현 클래스의 플로우리스트의 전방으로부터 후방으로 이동시키며, 처리는 스텝 495에서 다음 흐름으로 이어진다.

스텝 625에서, 대역폭을 제공받는 현 클래스가 실제 디폴트 클래스인 경우에, 상기 방법은 스텝 675로 이어진다. 스텝 675 내지 690은 비 디폴트 클래스에 대해 사용된 방법과 유사하다. 스텝 675는 상기 패킷의 길이를 상기 최선형 DRR 리스트상의 흐름의 디피싯(F->bq.deficit)과 비교한다. 패킷 길이가 흐름의 디피싯 보다 작은 경우에, 상기 방법은 스텝 725로 이어진다. 그러나, 다음 패킷의 길이가 최선형 DRR 디피싯을 초과하는 경우에, 상기 방법은 스텝 680으로 이어진다. 스텝 680에서, 상기 흐름의 최선형 DRR 디피싯은 흐름의 최선형 DRR 퀀텀(F->bq.quantum)만큼 증가된다. 스텝 685에서, 흐름은 스텝 700 내지 720에서 설명된 바와 같이, MoveFlowToEnd 방법을 시도함으로써, 상기 클래스의 흐름 리스트의 끝으로 이동된다. 스텝 685 이후에, 상기 방법은 스텝 495에서 다음 흐름을 처리하기 위해 "Next Flow" 라벨 505를 경유하여 복귀된다.

스텝 700은 위의 스텝 605, 645, 665 및 695에 의해 시도된 MoveFlowToEnd 하위 방법의 시작이다. MoveFlowToEnd 방법은 특정 흐름(F)에 대하여, 그리고, 특정 DRR 큐 FlowPQ에 대하여 시도된다. 흐름이 두 개의 상이한 DRR 큐들의 일원일 수 있으며, 마찬가지로, 두 개의 상이한 DRRITEM들(160, F->pq 및 F->bq)을 가진다는 것을 상기하기 바란다. MoveFlowToEnd 방법은 단순히 변경될 적절한 DRRITEM을 선택한다. 스텝 705에서, DRR 큐 포인터 FlowPQ가 그것이 최선형 큐인지를 검사하기 위해 체크된다. 그런 경우에, 상기 방법은 스텝 715로 이행하며, 그곳에서, 상기 흐름은 먼저 최선형 DRR 큐의 시작으로부터 큐 해제되고(q_remove(FlowPQ, &P->bq)), 그후, 그 DRR 큐의 테일에 큐 상태가 된다(q_enq(FlowPQ, &P->bq)). 상기 MoveFlowToEnd 하위 방법은 그후 스텝 720에서 종결된다. 스텝 705가 우선 순위 DRR 큐이 최선형 DRR 큐 대신 변경된 것을 걸정하는 경우에, 상기 방법은 스텝 710으로 이행하며, 그곳에서, 상기 흐름은 먼저 우선 순위 DRR 큐의 헤드로부터 제거되고, 그후 테일에 다시 큐 상태가 된다.

이제, MextBurst 방법의 도10을 참조하면, 스텝 655 또는 스텝 675가 상기 흐름이 현 패킷을 송신하기 위해 상기 현 흐름 DRR 라운드내에 충분한 디피싯을 가지고 있는 것으로 결정한 경우에, 제어는 스텝 725(도 9)로 이행한다. 상기 패킷은 실제로 스텝 725에서 상기 흐름 패킷 큐의 헤드로부터 큐 해제되게 된다.

스텝 730은 실제로 상기 패킷을 전송 링크상으로 전송하기 위해 작업 "send()"를 시도한다. 상기 로컬 변수 sent는 상기 "send()" 작업을 경유하여 송신된 바이트들의 수를 누산한다.

스텝 735, 740, 745 및 750은 전용 DRRITEM의 "디피싯" 카운트로부터 바로 송신된 패킷 길이를 결정함으로써 전용 흐름 DRR 큐을 갱신한다. 디폴트 클래스에 대하여, 이는 F->bq(스텝 740)이며, 비디폴트 클래스의 경우에, 이는 F-pq이다. 어느쪽의 경우든지, 처리는 스텝 750에서 재개되며, 클래스 레벨 DRR 큐을 위한 DRR 디피싯(P->cq)가 상기 패킷 길이만큼 감소된다.

스텝 755에서, 통계치들의 수가 갱신된다. 상기 흐름의 트래픽 레이트와 최대 레이트 토큰 버킷들은 각 전송된 바이트에 대해 하나의 제거된 토큰을 갖는다. 간격을 더하는 현 통계치들이 흐름별 통계치들 및 클래스별 통계치들 양자 모두에 대하여 증분된다.

스텝 760은 NextBurst의 이 시도에서 송신된 패킷들의 카운트(sentpkts)를 증분한다. 이것이 송신 요청된 최대 패킷 수(파라미터 maxPackets) 보다 낮은 경우에, 프로세스는 현 흐름에서 다음 패킷에서 재개되며, 이는 스텝 535에 대한 "NextPacket" 커넥터를 경유하여 표시된다. maxPackets 카운트가 도달되는 경우에, 스텝 765에서, 제어 플래그 "bReturn"가 TRUE로 설정된다. 상기 방법의 동작은 그후 스텝 540으로 복귀되어 다음 패킷을 고려한다. 스텝 765내의 "bReturn" 플래그 세트는, 바로 송신된 패킷이 활성 서비스 클래스의 마지막 패킷일 때, 상기 방법이 도 2의 데이터 구조들을 적절하게 갱신한 이후에, 상기 경우에 대하여 시험된다.

상술한 실시예들은 단순히 본 발명의 원리를 예시하는 것이라는 것을 명심하여야 한다. 본 기술 분야의 숙련자들은 본 발명의 원리를 구체화하면서 본 발명의 범위와 개념내에 속하는 다양한 다른 변화들 및 변경들을 구현할 수 있다.

Claims (21)

1. 패킷들의 전송을 데이터 통신 링크상으로 스케쥴링하는 방법에 있어서,

   a) 데이터 흐름의 복수의 패킷들을 수신하는 단계와,

   b) 상기 흐름을 서비스 클래스로 구성하는 단계와,

   c) 상기 서비스 클래스의 전송 대역폭을 선택된 한계로 스케쥴링하는 단계와,

   d) 상기 선택된 한계에 부합하는 상기 흐름의 패킷들을 포워딩하는 단계와,

   e) 디폴트 클래스 대역폭을 가진 디폴트 클래스를 식별하는 단계와,

   f) 상기 서비스 클래스에 할당된 대역폭과, 상기 디폴트 클래스에 할당된 대역폭 양자 모두를 사용하여 패킷들을 포워딩하는 단계를 포함하는, 스케쥴링 방법.
2. 복수의 우선 순위화 패킷 큐들 사이에서 네트워크에서의 전송을 위한 다음 패킷을 선택하는 방법에 있어서,

   a) 상기 복수의 우선 순위화 패킷 큐들내의 각 큐에 공유 대역폭 중 할당된 대역폭의 퀀텀을 할당하는 단계와,

   b) 상기 복수의 우선 순위화 패킷 큐들내의 각 큐에 상기 큐에 의해 포워딩될 허용 데이터량을 나타내는 디피싯(deficit)을 할당하는 단계와,

   c) 높은 우선 순위와, 상기 다음 패킷의 크기를 초과하는 디피싯 값을 갖는 큐로부터 전송을 위한 다음 패킷을 선택하는 단계와,

   d) 상기 선택된 다음 패킷의 크기만큼 상기 c) 단계에서 선택된 상기 큐의 디피싯을 감소시키는 단계와,

   e) 상기 복수의 우선 순위화 패킷 큐들 내의 모든 백로그된(backlogged) 큐들이 다음 패킷을 포워딩 하기에 불충분한 디피싯을 가지는 경우에, 각각의 상기 백로그된 큐에서의 디피싯에 상기 퀀텀의 값을 가산하고, 그에 의해, 우선 순위화 패킷 큐들의 세트 중으로부터의 선택의 새로운 라운드가 시작되는 단계를 포함하는, 선택 방법.
3. 제 2 항에 있어서,

   f) 모든 큐들이 비어있는 경우에, 각각의 상기 빈 큐에서의 상기 퀀텀의 값에 디피싯의 값을 가산하고, 그에 의해, 우선 순위화 패킷 큐들의 세트로부터의 선택의 새로운 라운드가 시작되는 단계를 더 포함하는, 선택 방법.
4. 제 1 항에 있어서,

   상기 흐름의 상기 수신된 패킷들을 흐름별 큐로 스케쥴링하는 단계를 더 포함하는, 선택 방법.
5. 제 1 항에 있어서,

   상기 흐름을 서비스 클래스로 구성하기 이전에, 상기 데이터 흐름이 최대 레이트 리미터 아래인지를 결정하고, 상기 데이터 흐름이 최대 레이트 리미터 아래인 경우 상기 흐름의 패킷들을 스케쥴링하는 단계를 더 포함하는, 선택 방법.
6. 제 5 항에 있어서,

   상기 최대 레이트 리미터를 초과하는 패킷들을 버리는 단계를 더 포함하는, 선택 방법.
7. 제 5 항에 있어서,

   상기 최대 레이트 리미터가 더 이상 초과되지 않을 때까지 상기 최대 레이트 리미터를 초과하는 패킷들을 큐잉하는 단계를 더 포함하는, 선택 방법.
8. 제 1 항에 있어서,

   상기 f) 단계는 상기 디폴트 클래스에 할당된 상기 대역폭상에서 상기 선택된 한계를 초과하는 패킷들만을 포워딩하는 단계를 더 포함하는, 선택 방법.
9. 제 1 항에 있어서,

   상기 f) 단계는 상기 디폴트 클래스에 할당된 상기 대역폭상에서 순간적으로 초과 예약된 상태하에서 패킷들을 포워딩하는 단계를 더 포함하는, 선택 방법.
10. 제 1 항에 있어서,

    상기 d) 단계는 상기 패킷들을 클래스별 패킷 큐로 스케쥴링하는 단계를 더 포함하는, 선택 방법.
11. 제 10 항에 있어서,

    상기 패킷을 클래스별 큐로 스케쥴링하는 상기 단계는 공정 큐잉 알고리즘을 사용하는 단계를 더 포함하는, 선택 방법.
12. 제 11 항에 있어서,

    상기 공정 큐잉 알고리즘은 디피싯 라운드 로빈 알고리즘인, 선택 방법.
13. 제 11 항에 있어서,

    상기 공정 큐잉 알고리즘은 선입 선수행 알고리즘인, 선택 방법.
14. 제 1 항에 있어서, 상기 d) 단계는,

    d-ⅰ) 상기 패킷들을 복수의 클래스별 패킷 큐들 중 하나로 스케쥴링하는 단계와,

    d-ⅱ) 제 2 공정 큐잉 알고리즘에 따라 상기 복수의 클래스별 패킷 큐들 사이에서 상기 전송 링크의 대역폭을 스케쥴링하는 단계를 더 포함하는, 선택 방법.
15. 제 14 항에 있어서,

    상기 제 2 공정 큐잉 알고리즘은 가중 공정 큐잉 알고리즘을 더 포함하는, 선택 방법.
16. 제 1 항에 있어서,

    각 클래스에 스케쥴링 우선 순위를 할당하는 단계를 더 포함하는, 선택 방법.
17. 패킷들의 전송을 데이터 통신 링크상으로 스케쥴링하는 방법에 있어서,

    a) 데이터 흐름의 복수의 패킷들을 수신하는 단계와,

    b) 상기 흐름을 서비스 클래스로 구성하는 단계와,

    c) 흐름 한계가 초과되지 않은 경우에, 서비스 클래스 한계를 가지는 상기 서비스 클래스 큐로 패킷들을 스케쥴링하는 단계와,

    d) 상기 서비스 클래스 한계가 초과되지 않는 동안에 상기 서비스 클래스 큐로부터 패킷들을 전송하는 단계와,

    e) 디폴트 클래스를 정의하는 단계와,

    g) 상기 디폴트 클래스를 위한 큐상에서 상기 서비스 클래스 한계를 초과하는 패킷들을 전송하는 단계를 포함하고,

    이에 의해 상기 흐름의 패킷들이 서비스 클래스 큐 및 디폴트 클래스 큐 양자 모두를 통해 전송되는, 스케쥴링 방법.
18. 패킷들의 전송을 데이터 통신 링크 상으로 스케쥴링하는 스케쥴링 장치에 있어서,

    a) 데이터 흐름의 수신된 패킷들을 흐름별 큐로 스케쥴링하기 위한 수단과,

    b) 상기 스케쥴링 패킷들을 서비스 클래스로 구성하기 위한 수단과,

    c) 상기 서비스 클래스의 전송 대역폭을 선택된 한계로 스케쥴링하기 위한 수단과,

    d) 상기 선택된 한계에 부합하는 상기 흐름의 패킷들을 포워딩하기 위한 수단과,

    e) 디폴트 클래스 대역폭을 가진 디폴트 클래스를 식별하기 위한 수단과,

    f) 상기 서비스 클래스에 할당된 대역폭과, 상기 디폴트 클래스에 할당된 대역폭 양자 모두를 사용하여 패킷들을 포워딩하기 위한 수단을 포함하는, 스케쥴링 장치.
19. 제 18 항에 있어서,

    g) 상기 데이터 흐름이 최대 레이트 리미터 아래인지를 결정하기 위한 수단을 더 포함하고,

    상기 최대 레이트 리미터가 초과되지 않은 경우, 상기 수신된 패킷들이 포워딩되는, 스케쥴링 장치.
20. 제 19 항에 있어서,

    상기 최대 레이트 리미터를 초과하는 패킷들을 버리기 위한 수단을 더 포함하는, 스케쥴링 장치.
21. 제 19 항에 있어서,

    상기 최대 레이트 리미터가 더 이상 초과되지 않을 때까지 상기 최대 레이트 리미터를 초과하는 패킷들을 큐잉하는 수단을 더 포함하는, 스케쥴링 장치.