[go: up one dir, main page]

JP2001504316A - System, apparatus and method for performing scheduling in a communication network - Google Patents

System, apparatus and method for performing scheduling in a communication network

Info

Publication number
JP2001504316A
JP2001504316A JP51318499A JP51318499A JP2001504316A JP 2001504316 A JP2001504316 A JP 2001504316A JP 51318499 A JP51318499 A JP 51318499A JP 51318499 A JP51318499 A JP 51318499A JP 2001504316 A JP2001504316 A JP 2001504316A
Authority
JP
Japan
Prior art keywords
component
scheduling
rate
job
speed
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.)
Pending
Application number
JP51318499A
Other languages
Japanese (ja)
Inventor
ラスズシジク，チェスター・エー
リー，ファイ・チョウ
クラムタック，イムリッチ
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Motorola Solutions Inc
Original Assignee
Motorola Inc
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 Motorola Inc filed Critical Motorola Inc
Publication of JP2001504316A publication Critical patent/JP2001504316A/en
Pending legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04Q—SELECTING
    • H04Q11/00—Selecting arrangements for multiplex systems
    • H04Q11/04—Selecting arrangements for multiplex systems for time-division multiplexing
    • H04Q11/0428—Integrated services digital network, i.e. systems for transmission of different types of digitised signals, e.g. speech, data, telecentral, television signals
    • H04Q11/0478—Provisions for broadband connections
    • 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]
    • H04L12/2801—Broadband local area networks
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5603—Access techniques
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5603—Access techniques
    • H04L2012/5604—Medium of transmission, e.g. fibre, cable, radio
    • H04L2012/5605—Fibre
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5603—Access techniques
    • H04L2012/5604—Medium of transmission, e.g. fibre, cable, radio
    • H04L2012/5606—Metallic
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5629—Admission control
    • H04L2012/5631—Resource management and allocation
    • H04L2012/5632—Bandwidth allocation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5638—Services, e.g. multimedia, GOS, QOS
    • H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
    • H04L2012/5649—Cell delay or jitter
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5638—Services, e.g. multimedia, GOS, QOS
    • H04L2012/5646—Cell characteristics, e.g. loss, delay, jitter, sequence integrity
    • H04L2012/5651—Priority, marking, classes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5672—Multiplexing, e.g. coding, scrambling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L12/00—Data switching networks
    • H04L12/54—Store-and-forward switching systems 
    • H04L12/56—Packet switching systems
    • H04L12/5601—Transfer mode dependent, e.g. ATM
    • H04L2012/5678—Traffic aspects, e.g. arbitration, load balancing, smoothing, buffer management
    • H04L2012/5679—Arbitration or scheduling

Landscapes

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

Abstract

(57)【要約】 通信ネットワーク内でスケジューリングを行うためのシステム，装置および方法は、各スケジューリング・ジョブを、スケジューリング・ジョブに関連するサービス・クラスにより、速度委託構成部分と速度可変構成部分とに分類する。所定の周期的間隔で反復されると、各速度委託構成部分に対して、その所定の遅延およびジター制約内で必要数の送信機会を提供する送信機会マップを作成することにより、速度委託構成部分がスケジューリングされる。マップ内の未使用送信機会を所定の方法で速度可変構成部分に割り当てることにより、速度可変構成部分がスケジューリングされる。 (57) [Summary] A system, apparatus, and method for performing scheduling in a communication network, wherein each scheduling job is divided into a rate commissioning component and a variable speed component by a service class related to the scheduling job. Classify. By creating a transmission opportunity map that, when repeated at predetermined periodic intervals, provides for each rate commitment component the required number of transmission opportunities within its predetermined delay and jitter constraints, the rate commitment component Is scheduled. The variable rate component is scheduled by assigning unused transmission opportunities in the map to the variable rate component in a predetermined manner.

Description

【発明の詳細な説明】 通信ネットワーク内でスケジューリングを 行うシステム，装置および方法 背景 発明の分野 本発明は、一般に通信システムに関し、さらに詳しくは、通信ネットワークに おける送信機会のスケジューリング（スケジュール決定）に関する。 関連技術の説明 今日の情報時代においては、増大し続ける通信消費者に対してサービス品質（ QoS:quality of service）を保証する高速通信の必要性が増加しつつある。その ために、通信ネットワークおよび技術は、現在および将来の需要に応えるために 進化しつつある。特に、より多数のエンド・ユーザに到達する新しいネットワー クが展開され、これらのネットワークの追加された帯域幅を効率的に利用するた めにプロトコルが開発されつつある。 すでに広く採用されており、当面は重要であり続けるで あろう技術の１つに共有媒体ネットワークがある。共有媒体ネットワークとは、 １つの通信チャネル（共有チャネル）が、複数のエンド・ユーザにより共有され るネットワークであり、異なるエンド・ユーザからの未調整の送信が互いに干渉 することがある。通信ネットワークは通信チャネルの数が限られることが多いの で、共有媒体ネットワークにより、単独の通信チャネル上に多くのエンド・ユー ザがアクセスを得ることができ、それにより、残りの通信チャネルは他の目的の ために用いることが可能になる。しかし、共有媒体ネットワークは、各エンド・ ユーザがデータを間欠的に送信することで、他のエンド・ユーザが無音期間の間 に送信することができるようにする場合にのみ実行可能である。 共有媒体ネットワークにおける問題の１つは、各エンド・ユーザにQoSを保証 しつつ共有チャネル上での衝突を回避するようにエンド・ユーザの送信をスケジ ューリング（スケジュール決定）することである。このスケジューリングの問題 は、多数のエンド・ユーザに対応する場合に極めて複雑になる。かくして、スケ ジューリングの複雑性を軽減するスケジューリング・アーキテクチャが依然とし て必要である。 図面の簡単な説明 第１図は、本発明の好適な実施例による共有媒体ネットワークの一例を示すブ ロック図である。 第２図は、本発明の好適な実施例によるヘッドエンド・ユニットおよびアクセ ス・インタフェースを示すブロック図である。 第３図は、本発明の好適な実施例によるヘッドエンド・スケジューラ・アーキ テクチャを示すブロック図である。 第４図は、本発明の好適な実施例によるヘッドエンド・スケジューラの構成部 分を示すブロック図である。 第５Ａ図は、本発明の実施例によるタスク・フレーム・マップの一例を示す図 である。 第５Ｂ図は、本発明の好適な実施例によるタスク・フレーム・マップの一例を 示す図である。 第６図は、本発明の好適な実施例により複数のビンとして概念化されたタスク ・フレーム・マップの一例を示す図である。 第７図は、本発明の好適な実施例による要求，ジョブおよびタスク間の関係を 総括するブロック図である。 第８図は、本発明による送信機会スケジューリング論理を示す流れ図である。 第９図は、本発明による速度委託構成部分のスケジューリング論理を示す流れ 図である。 詳細説明 第１図は、本発明の好適な実施例による共有媒体ネットワーク１００の一例を 示すブロック図である。共有媒体ネットワーク１００により、複数のエンド・ユ ーザ１１０LLL1LLL〜１１０LLLNLLLは、インターネットなどの遠隔の外部ネット ワーク１０８にアクセスすることができる。共有媒体ネットワーク１００は、エ ンド・ユーザ１１０と外部ネットワーク１０８との間に情報を伝える導管として 機能する。 共有媒体ネットワーク１００は、外部ネットワーク１０８に結合されるヘッド エンド・ユニット（HU:HeadendUnit）１０２を備える。HU１０２は、共有される 物理的媒体１０６により、複数のアクセス・インタフェース・ユニツト１０４LL L1LLL〜１０４LLLNLLL（AIU（Access Interface Unit）１０４と集合的に称する ）と通信する。各エンド・ユーザ１１０は、AIU１０４を介して共有媒体ネット ワーク１００とインタフェースする。１つのAIU１０４が１箇所または複数箇所 のエンド・ユーザ１１０に対応する。 共有物理媒体１０６は複数のチャネルを備え、そのチャネル上でHU１０２とAI U１０４との間に情報を転送することができる。好適な実施例においては、各チ ャネルは単方向である。すなわち、特定のチャネルがHU１０２からAIU１０４へ 、あるいはAIU１０４からHU１０２へのいずれか に情報を伝える。HU１０２からAIU１０４に情報を伝えるチャネルを通常「ダウ ンストリーム・チャネル」と呼ぶ。AIU１０４からHU１０２に情報を伝えるチャ ネルを通常「アップストリーム・チャネル」と呼ぶ。代替の実施例においては、 これら種々のアップストリームおよびダウンストリーム・チャネルはもちろん、 たとえば、時分割多重／二重を介する同一の物理的チャネルの場合も、あるいは たとえば周波数分割多重／二重を介する異なる物理的チャネルの場合もある。 好適な実施例においては、共有媒体ネットワーク１００は、共有物理媒体１０ ６が双方向のハイブリッド光ファイバ同軸ケーブル（HFC:hybrid fiber-optic a nd coaxial cable）ネットワークであるデータ・オーバ・ケーブル（DOC:data o ver cable）通信システムである。HU１０２は、通常「ケーブル・ルータ」と呼 ばれるヘッドエンド装置である。AIU１０４は、ケーブル・モデムである。他の 実施例においては、共有物理媒体１０６は、同軸ケーブル，光ファイバ・ケーブ ル，撚り線対ワイヤなどであり、さらにワイヤレスおよび衛星通信のための空中 ，大気または宇宙空間を含むこともある。 共有媒体ネットワーク１００においては、ダウンストリーム・チャネルは約５ ０ＭＨｚ超の周波数帯域に位置する。特定のダウンストリーム・チャネル上にHU １０２により送信される情報はすべて、すべてのAIU１０４に到達するの で、ダウンストリーム・チャネルはブロードキャスト・チャネルとして分類され る。特定のダウンストリーム・チャネルにおいて受信するよう同調されるAIU１ ０４はいずれも情報を受信することができる。 共有媒体ネットワーク１００において、アップストリーム・チャネルは約５な いし４２ＭＨｚの周波数帯域に位置する。各アップストリーム・チャネルは、連 続する時間スロットに分割されるので、「スロット化チャネル」と呼ばれること が多い。スロットはユーザまたは制御情報を含むプロトコル・データ単位を伝え るために用いられ、さらにより小さな情報の単位を伝えるために用いられるミニ スロットに分割されることがある。アップストリーム・チャネルは、特定の時刻 に１つのスロットまたはミニスロット内で１つのAIU１０４しか送信を成功させ ることができないので共有チャネルとして分類され、そのためにアップストリー ム・チャネルは複数のAIU１０４の間で共有しなければならない。特定のアップ ストリーム・チャネル上に２つ以上のAIU１０４が同時に送信すると衝突が起こ り、それにより同時に送信するすべてのAIU１０４からの情報が変造される。 複数のAIU１０４が単独のアップストリーム・チャネルを共有することができ るようにするために、HU１０２およびAIU１０４は媒体アクセス制御（MAC:mediu m access control）プロトコルに参入する。MACプロトコ ルは、AIU１０４によるアクセスを調整するためのルールおよび手順の集合を共 有チャネルに提供する。各AIU１０４はそのエンド・ユーザに代わりMACプロトコ ルに参入する。便宜上、MACプロトコルの各参入者を「MACユーザ」と呼ぶ。 MACユーザは、通常、特定のエンド・ユーザのアプリケーションに対応する接 続を表す。詳述はしないが、MACユーザは同様のトラフィック特性を共有する接 続の集合を表すこともある。多くの現在の通信ネットワークにおいては、各MAC ユーザは特定のトラフイック・パラメータとQoS要件とを有し、これらはMACユー ザがネットワーク内で接続を開設すると承認されて、ネットワークにより保証さ れる。たとえば、MACユーザは帯域幅の最小量の保証，送信するデータに関する 最大転送遅延の保証またはHU１０２により与えられる送信機会の間の最小時間変 動を必要とすることがある。非同期転送モード（ATM:Asynchronous Transfer Mo de）ネットワークなどのセル準拠ネットワークにおいては、各MACユーザの帯域 幅要件を特徴化するためにいくつかのパラメータを用いる。特に、MACユーザに より生成されるトラフィックの種類を特徴化するためにATMトラフイック・デス クリプタの集合が用いられ、MACユーザにより要求されるネットワーク・サービ スを特定するためにQoSパラメータの集合が用いられる。 ATMトラフイック・デスクリプタには、ピーク・セル速 度（PCR:Peak Cell Rate），維持可能セル速度（SCR:Sustainable Cell Rate） ，最小セル速度（MCR:Minimum Cell Rate）および最大バースト寸法（MBS:Maxim um Burst Size）が含まれる。PCRは、MACユーザが生成する最大データ速度（セ ル数毎秒）の指標である。SCRは、MACユーザが生成する長期的な平均データ速度 を表す。MCRは、MACユーザが必要とする最小データ速度（セル数毎秒）である。 MBSはMACユーザが生成するバーストの最大寸法（セル数）である。 QoSパラメータは、最大セル転送遅延（MaxCTD:Maximum Cell Transfer Delay ），セル遅延変動（CDV:Cell Delay Variation）およびセル損失率（CLR:Cell L oss Ratio）が含まれる。MaxCTDは、MACユーザが許容する最大遅延（下部構造の 通信ネットワークのアクセス遅延および伝播遅延を含む）を特定する。CDVは、M ACユーザが許容するデータ送信機会間の最大時間変動を指定する。CLRは、MACユ ーザにより送信される全セルに対する損失セルの比として、MACユーザが許容す る範囲でネットワークが失うことのできるセルを指定する。 同様のトラフィック特性を有するMACユーザがサービス・カテゴリに分類され る。ATMは、５つのサービス・カテゴリ、すなわち連続ビット速度（CBR:continu ous bitorate），リアルタイム可変ビット速度(RT-VBR:real-time variable bit rate），非リアルタイム可変ビッ ト速度（NRT-VBR:non-real-time variable bit rate），使用可能ビット速度（A BR:available bit rate）および未指定ビット速度（UBR:unspecified bit rate ）を定義する。各MACユーザは、いずれかのサービス・カテゴリに分類される。 CBR接続は、固定ビット速度を有し、セルのリアルタイム配信を必要とするト ラフィックにより特徴化される。CBRサービス・カテゴリのためのATMトラフイッ ク・デスクリプタはPCRである。CBRサービス・カテゴリのためのQoSパラメータ はMaxCTD，CDVおよびCLRである。 RT-VBR接続は、可変ビット速度を有し、セルのリアルタイム配信を必要とする トラフイックにより特徴化される。典型的なRT-VBR接続においては、接続上のト ラフイックはPCRにおいてセルがバースト状に生成される期間と、セルが生成さ れない無音期間とを有する（音声およびリアルタイム・ビデオがRT-VBRトラフィ ックの良い例である）。RT-VBRサービス・カテゴリのためのATMトラフィック・ デスクリプタはPCR，SCRおよびMBSである。RT-VBRサービス・カテゴリのためのQ oSパラメータはMaxCTD，CDVおよびCLRである。 NRT-VBR接続は、可変ビット速度（RT-VBR接続と同様の）を有するがセルのリ アルタイム配信を必要としないトラフイックにより特徴化される。NRT-VBR接続 は、通常は、低CLRを必要とする。 ABR接続は、最小セル速度を必要とするが、追加帯域幅が使用可能な場合には それを受け入れようとするトラフィックにより特徴化される。ABRサービス・カ テゴリのためのATMトラフイック・デスクリプタはMCRおよびPCRである。MCRは、 接続が必要とする保証最小セル速度である。PCRは、ネツトワークにより許され る場合にその接続で送信することのできる最大セル速度である。その結果、ABR 接続の送信速度は、MCRとPCRとの間のどこかにある。ABRサービス・カテゴリに 関しては、QoSパラメータは定義されない。ABR接続は、帰還を伴う流れ制御メカ ニズムに従属することが多い。このメカニズムは、ATM層転送特性の変化に応じ てその速度を適応するための接続源を必要とする。 UBR接続は、いかなる帯域幅も保証されず、QoS要件を持たない。UBRサービス ・カテゴリのためのATMトラフィック・デスクリプタはPCRである。PCRは、ネッ トワークにより許される場合にその接続で送信することのできる最大セル速度で ある。 共有媒体ネットワーク１００で用いるためにいくつかの異なるMACプロトコル が開発された。これらのプロトコルは、一般に、無競合（contention-free）プ ロトコルと競合準拠（contention-based）プロトコルとして分類される。時分割 多重接続（TDMA:time-division multiple-access）および円卓ポーリング（ round-robin polling）などの無競合プロトコルは、種々のスケジューリング方 法により、アップストリーム・チャネル上で一度に１つのMACユーザにのみ送信 することを許可することによって衝突を回避する。特定のリザベーション準拠プ ロトコルなどの競合準拠プロトコルは衝突を回避することはしないが、共有チャ ネル上で起こるすべての衝突を解消する。 好適な実施例においては、MACプロトコルは、ポーリングおよび競合準拠リザ ベーションを組み合わせて用いてアップストリーム送信をスケジューリングする 。競合準拠リザベーションは、HU１０２がMACユーザに帯域幅を割り振る前にリ ザベーションを行うことを要求する。HU１０２は、特殊な制御メッセージ（「エ ントリ・ポール・メッセージ」と呼ぶ）をダウンストリーム・チャネル上にAIU １０４に対して定期的に送信することにより、リザベーション機会を競合ミニス ロットの形でMACユーザに提供する。MACユーザは、HU１０２により提供されるリ ザベーション機会に応じてリザベーション要求メッセージを送信することにより リザベーションを行う。それぞれのリザベーション機会は、通常、複数のMACユ ーザが競合ミニスロット内で送信することを許可するので、MACユーザはリザベ ーションを行うために競争しなければならない。すべてのMACユーザがリザベー ションを行うことを求められるわけではない。リザベーションを行わずに定期的 に帯域幅を割り当てられ るMACユーザもある。 第２図は、HU１０２とAIU１０４とをより詳細に示すブロック図２００である 。ブロック図２００は、ダウンストリーム・チャネル２３０およびアップストリ ーム・チャネル２４０を介してAIU１０４の１つと通信状態にあるHU１０２を示 す。AIU１０４は、少なくとも１箇所のエンド・ユーザ１１０を支援する。HU１ ０２はダウンストリーム・チャネル２３０を介してデータおよび制御メッセージ をAIU１０４に送信し、アップストリーム・チャネル２４０を介してリザベーシ ョン要求およびデータをAIU１０４から受信する。 HU１０２は接続マネージャ（CM:Connection Manager）２１５を備える。CM２ １５はネットワークの接続参加制御の責を負う。さらに詳しくは、CM２１５は、 ネツトワーク内で接続を開設しそれを終了する責を負う。 エンド・ユーザ１１０などのエンド・ユーザがネットワーク上で通信すること ができるようにするには接続開設を行わねばならない。従って、エンド・ユーザ １１０がネットワークへの参加を要求すると、接続要求メッセージがCM２１５に 転送される。接続要求メッセージは、接続に関する帯域幅およびQoS要件を、ATM サービス・カテゴリと、関連するATMトラフイック・デスクリプタおよびQoSパラ メータの形で指定する。CM２１５は、接続を開設するか否かを決定し、それによ って、ネットワークがエンド・ユー ザ１１０の帯域幅およびQoS要件を満足することができるか否かに基づいて、エ ンド・ユーザ１１０がネットワークに参加することを許可する。 HU１０２はヘッドエンド・スケジューラ（HES:Headend Scheduler）２１４も 備え、これはCM２１５と適応リザベーション・マネージャ（ARM:Adaptive Reser vation Manager）２１１とに結合される。HES２１４はCM２１５によりネットワ ークへの参加を許可されたエンド・ユーザに対する送信機会のスケジューリング を行う責を負う。CM２１５が接続を開設すると、CM２１５は、開設された接続に 関する接続識別子と、ATMサービス・カテゴリと関連のATMトラフイック・デスク リプタおよびQoSパラメータとを含む接続設定メッセージをHES２１４に送る。同 様にCM２１５が接続を終了させると、CM２１５は終了された接続に関する接続識 別子を含む接続解放メッセージをHES２１４に送る。HES２１４は、CM２１５から 受信される接続情報を、ARM２１１から受信される帰還情報と共に用いて、ARM２ １１により送信される制御メッセージのタイミングを制御する。 ARM２１１は、HU１０２内にMACプロトコルを実現する責を負う。ARM２１１は リザベーション・マネージャ（RM:Reservation Manager）２１２および帰還コン トローラ（FC:Feedback Controller）２１３を備える。RM２１２は、アップスト リーム・チャネル２４０上で競合 ミニスロットを監視して、各競合ミニスロットの競合の結果を判断する。RM２１ ２は、競合結果をFC２１３とHES２１４とに送る。FC２１３は、各優先度クラス に関する状態情報を維持し（異なるサービス品質に対応するために複数の優先度 クラスが実現される場合）、各競合サイクルに関する競合ミニスロットの割当を 決定し、ダウンストリーム・チャネル２３０上に送信される制御メッセージをフ ォーマットする。FC２１３は、特に、HES２１４から受信されるタイミング情報 に基づき、制御メッセージ送信のタイミングを決定する。 AIU１０４は、エンド・ユーザ１１０とインタフェースするためのユーザ・イ ンタフェース（UI:User Interface）２２５を備える。エンド・ユーザ１１０に より送信されるデータはUI２２５により受信され、メモリ２２４に格納される。 UI２２５は、メモリ２２４内に、データの到着時刻を表示する時刻スタンプも格 納する。 AIU１０４は、メモリ２２４に結合される制御メッセージプロセッサ（CMP:Con trol Messega Processor）２２２も備える。CMP２２２は、受信機２１１によりH U１０２から受信されるデータおよび制御メッセージを処理する責を負う。CMP２ ２２は、エンド・ユーザ１１０を代表してMACプロトコルにMACユーザとして参入 する。 第３図は、本発明の好適な実施例によるHES２１４アーキテクチヤを示すブロ ック図である。第３図に示されるよ うに、HES２１４は要求待行列３０２を備える。HES２１４は、それぞれのATMサ ービス・カテゴリについて１つの要求待行列を維持する。CM２１５がMACユーザ の参加を許可すると、CM２１５はHES２１４に要求を送る。この要求には、要求 明細とサービス・カテゴリとが含まれる。要求明細には、要求に関わるMACユー ザを識別する識別子と、送信機会を待つMACユーザの滞留セル数を標示する待行 列深さとが含まれる。サービス・カテゴリは、MACユーザに関するATMサービス・ カテゴリを標示する。要求は、サービス・カテゴリに応じて要求待行列内に入れ られる。 MACユーザのリザベーションが成功する（あるいはリザベーションを行わずにM ACユーザに送信機会が与えられる）と、HES２１４はその要求をジョブに変換す る。ジョブとは、基本的には、HES２１４によるスケジューリングを必要とする 要求である。ジョブは、要求からの要求明細を含むジョブ明細が含まれ、さらに MACユーザに関するQoSパラメータも含まれる。ジョブは、ジョブ・バッファ３０ ４内の待行列に入れられる。 また、HU１０２によって内部でエントリ・ポーリング・ジョブが作成される。 エントリ・ポーリング・ジョブは、競合準拠リザベーション・メカニズムに対応 する送信機会を必要とする。このような送信機会の各々について、HES１０２は １箇所以上のMACユーザがリザベーション要求（データではなく）を送信するこ とを許可する。これらの リザベーション機会は定期的に与えられるので、送信すベきデータを有する各MA Cユーザは時宜を得てリザベーションを行うことができる。他のジョブと同様に 、エントリ・ポーリング・ジョブもジョブ・バッファ３０４内の待行列に入れら れる。 ジョブ・バッフア３０４内の各ジョブは、対応するジョブ明細に標示されるサ ービス・カテゴリ，帯域幅およびQoS要件に基づきタスクまたはタスクの集合に 変換される。各タスクは、アップストリーム・チャネル内で送信機会の割当を待 つデータ単位（たとえばATMセル）に対応する。各タスクには関連するタスク明 細があり、これが好適な送信スロットとタスクに関するCDV許容値を指定する。 HES２１４が、許可された各MACユーザがその帯域幅，遅延およびジター制約を 満足させるための充分な送信機会を確保し受信することができるように、いくつ かのタスクに送信機会を割り振らねばならない場合にスケジューリングの問題が 起こる。異なる帯域幅とQoS要件を有する多くのMACユーザに対応する場合は、ス ケジューリングの問題は極めて複雑になる。 HES２１４は、アップストリーム・チャネル２４０を連続するデータ・スロッ トに分割し、各データ・スロットを特定のタスクに割り当てることによりデータ 送信のスケジューリングを行う。従って、HES２１４は、各エントリ・ポール・ メッセージ内に、特定のタスクに各データ・スロッ トを割り当てるフィールドを含む。便宜上、このフィールドを送信フレーム３０ ６と称する。 送信フレーム３０６は、複数の連続スロットからなる。送信フレーム３０６内 の各スロットは、アップストリーム・チャネル２４０上のデータ・スロットに対 応する。送信フレーム３０６内の各スロットは、対応するデータ・スロットがMA Cユーザ情報の送信またはエントリ・ポーリングに関して予約（リザベーション ）されるか否かを標示する。データ・スロットがMACユーザ情報の送信のために 予約される場合は、送信フレーム３０６内のスロットは、さらに、どのMACユー ザがデータ・スロット内に送信することを許されるかを標示する。 第３図に示されるように、HES２１１４を簡略にする方法の１つは、スケジュ ーリング問題を２つの副次的問題、すなわち帯域幅委託構成部分（committed ba ndwidth component）のスケジューリングを扱う問題と、帯域幅可変構成部分（v ariable bandwidth component）のスケジューリングを扱う問題とに分割するこ とである。帯域幅委託構成部分とは、特定の期間内に所定量の送信機会を必要と する構成部分である。場合によっては、これらの送信機会を周期的な間隔で提供 しなければならない。CBRトラフイックは、帯域幅委託アプリケーションの良い 例であるが、これはHESがCVD制約内でPCRにおいてスロットの安定したストリー ムを提供しなければならないためである。 CDV制約は、一定の間隔でスロット（すなわち定期的な送信機会）を提供するこ とにより満足することができる。帯域幅可変構成部分とは、送信機会に対する需 要に融通がきき、特定の期間内に所定量の送信機会を必要としない構成部分であ る。UBRトラフィックが、帯域幅可変アプリケーションの良い例であるが、これ はHES２１４がMACユーザに対して、いかなる帯域幅をも保証せず、そのためにMA Cユーザは余剰の帯域幅が使用可能な場合にHES２１４の便宜なときに帯域幅を割 り振ってもらうことができるためである。 好適な実施例は、各要求を速度委託構成部分（committed-rate component）と 速度可変構成部分（variable-rate component）とに分けることによってこのア ーキテクチャの利点を活かす。要求によっては、１つの構成部分（すなわち速度 委託または速度可変）のみを有するものと、両構成部分を有するものとがある。 速度委託構成部分は、速度委託ジョブ３０８に変換され、速度可変構成部分は速 度可変ジョブ３１０に変換される。速度委託構成部分スケジューラ３１２を用い て速度委託ジョブ３０８のスケジューリングを行い、速度可変構成部分スケジュ ーラ３１４を用いて速度可変ジョブ３１０のスケジューリングを行う。各スケジ ューラは、個別の構成部分に適するスケジューリング規則を適応する。ポール発 生器３１６は、速度委託構成部分スケジューラ３１２および速度可変構成 部分スケジューラ３１４からのタスクを、送信フレーム３０６に配置する。速度 委託ジョブは送信フレーム３０６内にスロットを保証される。速度可変ジョブに は、速度委託ジョブに割り当てられない送信フレーム３０６内の余分なスロット が提供される。 CBRサービス・カテゴリは、速度委託構成部分のみを含む。CBR MACユーザは、 CBR接続が終了するまでPCRにおいて連続的に定期的な送信機会を割り振られる。 送信機会はMACユーザの遅延およびジター制約内で割り振られる。 RT-VBRサービス・カテゴリには速度委託構成部分のみが含まれる。本明細書に 全文が参考文献として含まれる、１９９７年８月１４日出願の米国暫定特許出願 第６０／０５５，６５８号「System，Device，And Method For Scheduling In A Communication Network」に、RT-VBRトラフイックをスケジューリングするため のいくつかの代替実施例が開示される。１１ページ１６行目から始まる１つの実 施例は、特定のRT-VBR接続をCBR接続であるかのように取り扱う。これは、特定 のRT-VBR接続、詳しくは所定の閾値を超えるSCRのPCRに対する比率を伴う接続（ 「CBR状」接続と称する）には適切であるが、他のRT-VBR接続（「バースト状」 接続と称する）には不充分である。「バースト状」RT-VBRトラフイックをスケジ ューリングする２つの方法が開示される。１２ページ１５行目から始まる第１実 施例においては、MACユーザがアクティ ブである間はRT-VBR MACユーザには、PCRにおいて定期的な送信機会が割り振ら れ、MACユーザが非アクティブの場合はゼロ速度において割り振られる。１４ペ ージ１３行目から始まる第２実施例においては、RT-VBR MACユーザには、MACユ ーザがアクテイブの間はPCRにおいて定期的な送信機会が割り振られ、MACユーザ が非アクティブの間は低速度（好ましくはSCR）において割り振られる。「バー スト状」RT-VBR接続に関する帯域幅要件は可変するが、「バースト状」RT-VBR接 続は速度可変構成部分を含まないことに注目すべきである。これは、RT-VBRMAC ユーザが依然として、特定の期間内に所定量の送信機会を必要とするためである 。送信機会はMACユーザの遅延およびジター制約内で割り振られる。 NRT-VBRサービス・カテゴリは速度委託構成部分と速度可変構成部分の両方を 含む。NRT-VBR MACユーザには、SCRにおいて（すなわち速度委託構成部分）送信 機会が割り振られ、MACユーザによる送信のための待行列に入れられたデータ量 が所定の閾値を超える（すなわち速度可変構成部分）場合は、追加の送信機会が 割り振られる。MACユーザによるHES２１４に対する待行列深さ情報の信号化は、 たとえば、状況情報をデータ送信と共に含める（「ピギーバッキング」と呼ばれ ることが多い）ことにより行うことができる。NRT-VBRについては、速度委託構 成部分に関する特定の遅延およびジター制約はない。 ABRサービス・カテゴリは速度委託構成部分と速度可変構成部分の両方を含む 。ABRユーザには、MCRにおいて（すなわち速度委託構成部分）送信機会が割り振 られ、速度委託ジョブに対する割当後に使用可能な送信機会があれば、追加の送 信機会が割り振られる（すなわち速度可変構成部分）。ABRについては、速度委 託構成部分に関する特定の遅延およびジター制約はない。 UBRサービス・カテゴリは速度可変構成部分のみを含む。UBRユーザには、「残 りの」送信機会がある場合には、それが割り振られる。 ユーザ要求と同様に、エントリ・ポーリング・ジョブも速度委託構成部分と速 度可変構成部分とに分類される。好適な実施例においては、エントリ・ポーリン グ・ジョブは定期的なリザベーション機会を提供する速度委託構成部分と、追加 のリザベーション機会を提供する速度可変構成部分の両方を含む。この追加のリ ザベーション機会は、衝突解消中のMACプロトコル性能を改善することができる がオプションである。代替の実施例においては、エントリ・ポーリング・ジョブ は速度委託構成部分のみを含む。 異なる帯域幅とQoS要件を持つ多重クラス・ユーザに関するスケジューリング 方法の１つがVaitzblit他（以下Vaitzblitと称する）により１９９６年６月１８ 日に出願された米国特許第５，５２８，５１３号「Scheduling and Admission C ontrol Policy for a Continuous Media Server」に教示される。連続媒体ファイル・サーバーに適応するVaitzbli tの特許によれば、３つのクラスのユーザが対応される：すなわち汎用，リアル タイムおよび等時（isochronous）である。汎用クラスは優先度の低いバックグ ランド処理に適する差替タスク（preemptivetasks）を支援する。しかし、この クラスには最小限のCPU処理量が保証されるだけである。リアルタイム・クラス は、処理能力の保証と遅延の制限とを必要とするユーザを表す。このクラスは差 し替えられはしないが、より優先度の高いユーザをスケジューリングする差替ウ ィンドウが提供される。等時クラスは、定期的な送信と処理能力に関する性能保 証と待ち時間の制限と低ジターとを必要とするユーザを表す。 Vaitzblitによれば、等時タスクに最高優先度が与えられ、最初にスケジュー リングされる。それにリアルタイム・クラスと、汎用クラスとが続く。等時タス クは周期的に実行され、各タスクに関して設定されるタイマ割込によって起動さ れる。等時タスクがスケジューリングされた後で、スケジューラは、重み付け円 卓法（weighted round-robinscheme）を用いてリアルタイム・タスクと汎用タス クとを交互に行う。 異なる速度を必要とするユーザに関係する等時タスクには、速度単調的にさら に優先権が与えられる。すなわち、より高い速度を有するユーザにより高い優先 権がある。こ れらのタスクは周期的に実行され、対応する時間的期間に関して設定されるタイ マ割込により起動される。スケジューラは等時タスクが優先度が下がる順に配列 される準備済み待行列から等時タスクを実行する。等時タスクがサーバーに到着 すると、準備済み待行列内の適当な場所に挿入される。等時タスクは周期タイマ が経過する毎に到着する。参加を許可された等時タスクのすべてについて個別期 間毎に独自の周期タイマが存在する。同一の期間を持つすべての等時タスクは、 その期間に関連するタイマが経過すると実行される。 等時タスクがサーバーに到着すると、スケジューラは現在実行中のタスクを差 し替える必要があるか否かを判定する。現在実行中のタスクが到着したタスクよ りも優先度が低い場合は、待行列の先頭から着信するタスクにより、次の差替ウ ィンドウにおいて差し替えられる。差し替えられたタスクは、そのタスクに関す る待行列の先頭に入れられる。これは、以前に実行されていた速度委託タスクで あるために、待行列内で待機する全タスクのうち最高の優先度を持つとされるか らである。 データ単位保留送信に対応するVaitzblitによるタスクのスケジューリングは 、そのリアルタイムの差替に欠点を持つ。とりわけ、差替が行われると帯域幅と QoS保証を行うことが困難になる。また、各速度が異なるタイマを用いるために 多数の異なる速度が存在する場合、等時タスクのス ケジューリングに関するタイマ管理が煩わしくなることがある。 本発明の好適な実施例は、タスクのスケジューリングを行うのに非差替スケジ ューリング法を用いる。詳しくは、速度委託構成部分スケジューラ３１２が送信 機会のマップを作成する。これは、周期的間隔で繰り返されると各速度委託ジョ ブに任意の遅延およびジター制約内で要求される帯域幅を提供する。このマップ は、速度委託ジョブの帯域幅およびQoS要件に基づき初期化されるいくつかのス ロットによって構成される。特定のジョブ集合に関して作成されると、マップは ジョブが追加されるか、ジョブが削除される、あるいは既存のジョブの帯域幅お よび／またはQoS要件が変更されるまで変わらないのが普通である。送信機会の マップを作成することにより、速度委託ジョブをリアルタイムではなく、フレー ム毎に演繹的にスケジューリングすることができる。 通常、マップ内のすべてのスロットが速度委託ジョブのスケジューリングに用 いられるわけではない。速度委託ジョブのスケジューリングに用いられないスロ ットは、速度可変ジョブの割振に使用することができる。送信機会マップは、定 義により、スロット割当の反復可能パターンを有する。長い送信サイクルを避け るために最も小さな反復可能パターンを用いることが望ましい。最も小さな反復 可能パターンが１つのエントリ・ポール・メッセージ内に伝える には大きすぎる場合は、マップをより小さい等しい部分（タスク・フレームと称 する）に分割することができる。ポール発生器は、各送信フレーム３０６内に１ つのタスク・フレームを備える。 第４図は、本発明の好適な実施例によるHES２１４の構成部分を示すブロック 図である。第４図に示されるように、速度委託構成部分スケジューラ３１２は、 マッパ４０２と複数のタスク・フレーム４０４とを備える。マッパ４０２は、速 度委託ジョブ３０８をタスクに変換し、そのタスクをタスク・フレーム４０４内 に配置する。その方法については下記に詳述する。 速度可変成分スケジューラ３１４は、優先度決定装置（Prioritizer）４０６ とタスク待行列４０８とを備える。優先度決定装置４０６は速度可変ジョブ３１ ０をタスクに変換し、タスクをタスク待行列４０８内に配置する。優先度決定装 置４０６は、好ましくは、重み付け円卓法規則を用いて速度可変ジョブ３１０の 優先度を決定する。重み付け円卓法スケジューリングに用いられる重みは、ATM サービス・カテゴリ，待行列深さおよび速度可変ジョブ３１０の他の関連特性の 関数とすることができ、時間の経過と共に変化する。 ポール発生器３１６は、各送信フレーム３０６内に１つのタスク・フレーム４ ０４を備える。ポール発生器３１６は、厳格な円卓法に基づき複数のタスク・フ レーム４０４ から１つのタスク・フレーム４０４を選択する。次にポール発生器３１６は、送 信フレーム３０６内の任意の空きスロットをタスク待行列４０８からの速度可変 タスクで、好ましくは早いもの順に埋める。 本発明の主要な要素は、速度委託ジョブ３０８をタスク・フレーム４０４内に スケジューリングすることである。マップを構成するスロット数は、一般に、シ ステムが支援する個別の帯域幅要件の集合の関数である。帯域幅要件が最も低い ジョブが、システムが支援する互いに異なる期間の整数倍である期間を有すると き、最低帯域幅のジョブがマップ内でスロットの反復パターンのための最も長い 期間を有することになり、他のすべてのジョブは同じ期間内に反復可能なパター ンを有することになる。ある実施例においては、反復可能パターンを集合的に構 成するタスク・フレーム４０４の数は、最も高い帯域幅要件を有するタスク・フ レーム４０４の数によって決まり、好ましくは、各速度委託ジョブ３０８が１つ のタスク・フレーム４０４につき１つ以内のスロットを割り振られるように選択 される。 毎秒セル数の形の各速度委託ジョブ３０８に関する速度Ｒを、送信スロット数 の形の送信期間Ｓに変換することができる（すなわち１つのセルがＳスロット毎 に送信されなければならない。ただしＳは整数でなくともよい）。ｔを、１つの 送信スロット内に１つのセルを送信するのにかかる時間を秒で示す値とすると、 期間をＳ＊ｔ（秒）とすること ができる。速度Ｒを正確に満足するためには、１つのセルを各期間で送信しなけ ればならない。従って、R*S*t＝１である。すなわち期間Ｓは1/(R*t)から導かれ る。1/(R*t)が整数であるとすると、周期的各セル送信は直接スロット境界に一 致する。しかし、1/(R*t)が整数でない場合は、セル送信は1/(R*t)の期間でスケ ジューリングすることはできない。これは周期的各セル送信がスロット境界と直 接一致しないためである。 １つの代替例はＳを1/(R*t)の「最低値」に等しく設定することである（すな わち1/(R*t)より小さい最大整数）。この結果として、送信機会は速度Ｒに対応 するのに必要とされるよりも頻繁にスケジューリングされる。この概算誤差の示 すものは、セルによってはデータの全負荷を伝えないものがあり、従って適当に 「アイドル・ビット」を埋め込まねばならないということである。 第２の代替例はＳを1/(R*t)の「最高値」に等しく設定することである（すな わち1/(R*t)より大きい最小整数）。この結果として、送信機会は速度Ｒに対応 するのに必要とされるよりも低い頻度でスケジューリングされる。この概算誤差 の示すものは、セルによってはその遅延およびジター制約内にバッファされ、あ るいは送信されないとなくなることがあるということである。好適な実施例は、 1/(R*t)が整数でない場合はＳを1/(R*t)の「最低値」になるよう選択する。 本発明により、すべての速度委託ジョブ３０８が共通の送信速度Ｒを有する場 合、上記により決定される寸法Ｓのマップをスケジューリングに用いることがで きる。この場合、各ユーザはマップ内に１つのスロットを必要とする（すなわち 各ユーザが１期間につき１つのスロットを要する）。ユーザに割り当てられるス ロットの位置は、その遅延およびジター制約に依存する。すべてのユーザが同じ 周期性を共有するので、寸法Ｓのタスク・フレーム４０４が１つしか必要とされ ない。 上記の非差替スケジューリング法を用いて、異なる送信速度を有するユーザに 対応することができる。速度委託ジョブに関わる異なる速度はそれぞれ上記の方 法で期間に書き換えることができる。速度委託ジョブに関わる異なる速度の集合 を｛R1,R2,...Rm｝とし、対応する異なる期間を｛S1,S2,...Sm｝とする。ここで S＊をSi（ただしi=1,2,...m）の最小公倍数（LCM）とする。寸法S＊のタスク・ フレームが用いられると、タスク・フレーム４０４内の送信パターンは反復可能 パターンであり、しかも最小の反復可能パターンであることが保証される。 各個別の期間が最大期間S_maxの整数除数であるとすると、S_maxは単に個別期 間の集合のLCMとなり、寸法Sのタスク・フレームを用いることができる。一般に 、個別期間の集合間のLCMであるS＊はS_maxよりかなり大きくなる。寸法S＊のタ スク・フレームを用いると、一部のユー ザの遅延制約を満足することができなくなる。好適な実施例の１つは、Si（ただ しi=1,2,...m）の最小数である寸法S_minのフレームを用いて、各タスク・フレ ーム内に少なくとも１つの割当が依然としてあるようにすることである。この方 法で、不必要に遅延するユーザがなくなる。より小さなフレームを用いると、マ ップ内のタスク・フレーム４０４の数はＫ＝S*/S_minとなる。 上記のスケジューリング法を例を挙げて実証することができる。この例では、 スケジューリングすべきジョブが３つある。ジョブ番号１は期間４を有する。ジ ョブ番号２は期間８を有する。ジョブ番号３は期間１６を有する。上記の記数法 を用いると、スケジューリングの問題をS_max=16，S_min=4およびS*=16（すなわ ち４，8,１６のＬCM）とモデル化することができる。 第５Ａ図に示されるある実施例においては、寸法S*=16の単独のタスク・フレ ームが用いられる。これにより、タスク・フレーム内の送信パターンが反復可能 パターンであり、しかも最小の反復可能パターンであることが保証される。この 場合、ジョブ番号１にはタスク・フレーム内の４つのスロットが割り振られ、ジ ョブ番号２にはタスク・フレーム内の２つのスロットが割り振られ、ジョブ番号 ３にはタスク・フレーム内の１つのスロットが割り振られる。 第５Ｂ図に示される好適な実施例においては、寸法S_min=4のタスク・フレー ムが用いられる。最小反復パタ ーンはS*=16スロットであるので、K=4個のタスク・フレームが必要である。この 場合、ジョブ番号１には各タスク・フレーム内の１つのスロットが、ジョブ番号 ２には１つおきのタスク・フレーム内の１つのスロットが、ジョブ番号３には５ つおきのタスク・フレーム内の１つのスロットが割り振られる。 速度委託ジョブ３０８をタスク・フレーム４０４内にスケジューリングする場 合、遅延およびジター制約を有するジョブをスケジューリングすることは、遅延 およびジター制約のないジョブをスケジューリングするよりも困難である。これ は、遅延およびジター制約によって、マップ内のどのスロットを特定のタスクに 用いることができるかあるいはできないか（すなわちどのスロットが遅延および ジター制約に関わり、どのスロットが関わらないか）が決定されるためである。 また、速度委託ジョブ３０８をタスク・フレーム４０４内にスケジューリングす る場合に、帯域幅の高いジョブをスケジューリングすることは帯域幅の低いジョ ブをスケジューリングすることよりも一般的に難しい。 従って、第４図に示されるように、好適な実施例は速度委託ジョブ３０８をＱ ＯＳジョブ４１０（すなわち遅延およびジター制約を有するジョブ）と非ＱＯＳ ジョブ４１２（すなわち遅延およびジター制約のないジョブ）とに分類する。Ｑ ＯＳジョブ４１０は、そのデータ速度要件に応じて優先度が決定され、速度の最 も高いジョブに最も高い優先権が与 えられる。同様に非QOSジョブ４１２はそのデータ速度要件に応じて優先度が決 定され、速度の最も高いジョブに最も高い優先権が与えられる。このような速度 単調的な待行列規則は、等時タスクのスケジューリングに関するVaitzblitの方 法における準備済み待行列に関する速度単調的な待行列規則と同様である。 速度委託構成部分スケジューラ３１２は、まず、最も優先度の高いジョブから 、各ジョブが、必要とされる遅延およびジター制約内でその必要とする帯域幅を 割り振られるようにQOSジョブ４１０をスケジューリングする。これらのジョブ に関しては、タスク・フレーム４０４内でスロットを割り振る問題を、１種のビ ン・パッキング問題としてモデル化することができる。第６図に示されるように 、複数のタスク・フレーム４０４をいくつかのビンと概念化することができる。 ジターが許されない場合は、各タスク・フレーム４０４の１つのスロットで構成 される各「列」が１つのビンに相当する。ジターが許される場合は、複数の隣接 する「列」が１つのビンに相当する。 D.S.Johnson，A.Demers，J.D.Ullman,M.R.Garey，R.L.GrahamによるWorst-Cas e Performance Bounds For Simple One-Dimensional Packing Algorithm（Socie ty for Industrial and Applied Mathematics Journal of Computing，Vol.3，N o.4）（１９７４年１２月発 行）に一次元パッキング・アルゴリズムが論じられる。ダイナミック・パッキン グに対応する、より複雑なビン・パッキング問題はE.G.Coffman,Jr.，M.R.Carey ,D.S.JohnsonによるDynamic Bin Packing（Society for Industrial and Applie d Mathematics Journal of Computing，Vol．12，No.2）（１９８３年５月発行 ）に論じられる。要するに、ビン・パッキングの問題は、通常、寸法の異なる複 数の品物を一定の空間内にパッキングする問題である。一般に、まず最も大きな 品物をパッキングし、それから、より小さなもので埋めてゆくことにより満足の ゆく結果が得られる。（時間費用がかかり、複雑になっても）品物を取り出し、 再配置し、再パックすることを可能にすることによって改善された結果が得られ る。 速度委託構成部分スケジューラ３１２が直面するビン・パッキング問題は、ダ イナミック・ビン・パッキング問題と匹敵する。これは異なる帯域幅要件を有す る複数のジョブを一定数のスロット内に「パッキングする」ことを必要とする。 速度委託構成部分スケジューラ３１２は、通常、最も優先度の高いジョブの帯域 幅およびQoS要件を満たすようにビンをパッキングし、帯域幅要件が下がる順に 残りのジョブで埋める。タスク・フレーム４０４内でスロットを割り振る場合、 スロットはタスク・フレーム４０４の各列に均等に分配されることが好ましい。 速度委託構成部分スケジューラ３１２が使用可能なスロットを用いてジョブ の遅延およびジター要件を満たすことができないことがあれば、速度委託構成部 分スケジューラ３１２はスロットの割振を変更する。たとえば、速度委託構成部 分スケジューラ３１２は、１スロットから既存の割振を許容される近隣のスロッ ト（すなわち対応するジョブの遅延およびジター制約内のスロット）に移動させ て、スケジューリングされるジョブのジター制約内にあるスロットを解放するこ とがある。最悪の場合、速度委託構成部分スケジューラ３１２はジョブの一部ま たは全部を取り出して、再配置し、再パッキングしなければならない。上記のパ ッキング問題と実践的解決策の詳細な公式化は本発明の範囲を超える。 QOSジョブ４１０がスケジューリングされると、速度委託構成部分スケジュー ラ３１２は、優先度の最も高いジョブから、各ジョブに必要とされる帯域幅が割 り振られるように非QOSジョブ４１２をスケジューリングする（遅延およびジタ ーは問題とならない）。非QOSジョブ４１２に関するスロットの分布はあまり重 要ではないが、非QOSジョブもタスク・フレーム４０４全体に均等に分布される ことが好ましい。これにより、速度可変ジョブ３１０に使用することのできる均 等に一定数の空きスロットを各送信フレーム３０６に提供する。 ポール発生器３１６により生成される各送信フレーム３０６がエントリ・ポー ル・メッセージ内でMACユーザに対し送信される。送信すべきデータを有するMAC ユーザは、 指定されるデータ・スロット内に送信することを許される。HU１０２はデータ・ スロットを監視して、MACユーザの状況を判断する。 送信機会を与えられるとデータを送信するMACユーザは、通常「アクティブ」 であると考えられる。送信機会を与えられてもデータを送信しないMACユーザは 、通常「非アクティブ」であると考えられる（MACユーザがリザベーションを行 うことを求められない場合は、MACユーザは「アクティブ」であると見なされ、 この限りではない）。しかし、HU１０２には追加のMACユーザ状況情報が使用可 能である。たとえば、データを送信するMACユーザは、送信すべきデータをさら に有するか（「ピギーバッキング」と称されることが多い）否かの指標を備える ことがある。MACユーザが送信すべきデータを持たないという指標を用いて、MAC ユーザがデータを送信しても「非アクティブ」状況であることを標示することが ある。 HES２１４は、通常、「アクティブ」MACユーザに送信機会を提供し続ける。HE S２１４は、「非アクティブ」MACユーザには送信機会の提供を停止するのが普通 である。後者の場合、HES２１４は、関連ジョブが「達成された（達成済み）」 と見なし、ジョブ・バッファ３０４から関連ジョブを排除（削除）する。MACユ ーザに関連のジョブは、一定のアイドル条件が満たさせると「達成された」と見 なされる。このアイドル条件は、ATMサービス・カテゴ リおよびジョブのQoS要件に関して定義される。 CBR，NRT-VBRおよびABRジョブに関しては、対応する接続が終了すると、また その場合に限り、「達成された」と見なさされる。そうでない場合は、ジョブ（ またはジョブ群）はジョブ・バッファ３０４内に留まり、MACユーザは引き続き 帯域幅の割振を受ける。 RT-VBRジョブは、上記のようにRT-VBRジョブに対応するために用いられる方法 に応じて、削除を必要とする場合としない場合とがある。ある実施例においては 、RT-VBRジョブは「アクティブ」である間はPCRにおいて、「非アクティブ」の ときはゼロにおいて帯域幅を割り振られる。このようなRT-VBRジョブは、MACユ ーザがリザベーションに成功すると「アクティブ」と見なされ、MACユーザが所 定数の連続送信機会（たとえば２つ）に応答してデータを送信することに失敗す ると、「非アクティブ」と見なされる。さらに、このようなRT-VBRジョブはMAC ユーザが「非アクティブ」の場合は「達成済み」と見なされる。本実施例におい ては、RT-VBRジョブは、MACユーザが「アクティブ」になるとジョブ・バッファ ３０４に動的に追加され、MACユーザが「非アクティブ」になるとジョブ・バッ ファ３０４から削除される。 代替の実施例においては、RT-VBRジョブには、「アクティブ」の間はPCRにお いて、「非アクティブ」の場合はより低い（ゼロではない）速度において帯域幅 が割り振ら れる。このようなRT-VBRジョブは常に（接続が存在する限り）「アクティブ」と 見なされる。本実施例においては、RT-VBRジョブは無期限にジョブ・バッファ３ ０４内に留まるが、このようなRT-VBRジョブの相対的優先度（上記の帯域幅要件 に基づく）は速度が変わるたびに変わることがある。このような速度変更により 、速度委託構成部分スケジューラ３１２は新しい速度情報に基づきタスク・フレ ーム４０４を更新することを促される。 UBRユーザに関しては、ジョブは滞留データがない場合は「達成された」と見 なされる。 エントリ・ポーリング・ジョブは常にアクティブであるので、削除されること はない。 ジョブがジョブ・バッフア３０４から削除されると、要求に再変換され、適切 な要求待行列３０２内に入れられる。同時に、ジョブに対応するすべてのタスク がタスク・フレーム４０４および／またはタスク待行列２０８から削除される。 たとえば接続が終了するなど、要求そのものが「達成された」場合は、その要求 は要求待行列３０２から削除される。 第７図は、本発明の好適な実施例による要求，ジョブおよびタスク間の関係を 総括するブロック図である。CM２１５からの新規要求７０２は、要求待行列３０ ２内に入れられる。要求７０２は新規ジョブ７０４に変換され、ジョブ・バッフ ァ３０４に格納される。また、エントリ・ポーリン グ・ジョブ７０６がジョブ・バッファ３０４に格納される。ジョブ７０４，７０ ６は、タスク７０８に変換され、これに送信機会が割り振られる。達成済みジョ ブ７１０はジョブ・バッファ３０４から削除され、要求に再変換されて、要求待 行列３０２内に入れられる。達成済み要求７１２が要求待行列３０２から削除さ れる。 第８図は、本発明により送信機会をスケジューリングする論理を示す流れ図で ある。この論理は段階８０２で始まり、段階８０４において、複数のスケジュー リング・ジョブの各々を速度委託構成部分と速度可変構成部分とに分類する。速 度委託構成部分は、特定の時間量内に所定数の送信機会を必要とし、速度可変構 成部分は特定の時間量内に不定数の送信機会を必要とする。論理は、所定の周期 的間隔で反復されると各速度委託構成部分に、その所定の遅延およびジター制約 内で必要数の送信機会を提供する送信機会マップを作成することにより速度委託 構成部分のスケジューリングを行う。これが段階８０６である。論理は、段階８ ０８において、所定の方法により速度可変構成部分にマップ内の未使用送信機会 を割り当てることにより、速度可変構成部分のスケジューリングを行う。論理は 段階８９９で終了する。 第９図は、本発明により速度委託構成部分をスケジューリングする論理を示す 流れ図である。論理は段階９０２で始まり、段階９０４において、速度委託構成 部分を遅延お よびジター制約を必要とする速度委託構成部分と、遅延およびジター制約を必要 としない速度委託構成部分とに分類する。本論理は、段階９０６において帯域幅 要件に基づき、遅延およびジター制約を必要とする速度委託構成部分の優先度を 決定し、段階９０８において帯域幅要件に基づき遅延およびジター制約を必要と しない速度委託構成部分の優先度を決定する。次に論理は段階９１０において、 遅延およびジター制約を必要とする速度委託構成部分を、優先度の順にマップ内 に割り付け、次に段階９１２において遅延およびジター制約を必要としない速度 委託構成部分を優先度の順にマップ内に割り付ける。論理は段階９９９で終了す る。 本明細書に説明されるすべての論理は、個別の構成部品，集積回路構成，電界 プログラミング可能ゲート・アレイ（FPGA:Field Programmable Gate Array）ま たはマイクロプロセッサなどのプログラミング可能論理素子と組み合わせて用い られるプログラミング可能論理を用いて、あるいはこれらの組合せを含むその他 の任意の手段により具現化することができる。プログラミング可能論理は、読取 専用メモリ・チップ，コンピュータ・メモリ，ディスクなどの有形の媒体または その他の格納媒体に一時的あるいは恒久的に固定することができる。プログラミ ング可能論理は、搬送波内に実現されるコンピュータ・データ信号内に固定して 、プログラミング可能論理をコンピュータ・バ スまたは通信ネットワークなどのインタフェースを介して送信することもできる 。これらすべての実施例は、本発明の範囲に入るものとする。 本発明は、本質または本質的特性から逸脱せずに他の特定の形態において実現 することもできる。開示される実施例は、あらゆる観点において、説明のための ものに過ぎず、制約するものではない。DETAILED DESCRIPTION OF THE INVENTION A system for performing scheduling in a communication network, BACKGROUND OF THE INVENTION Field of the Invention Generally regarding communication systems, For more information, The present invention relates to scheduling (scheduling) of transmission opportunities in a communication network. Description of Related Technology In today's information age, Quality of service (QoS: The need for high-speed communication that guarantees quality of service) is increasing. for that reason, Communication networks and technologies Evolving to meet current and future demands. In particular, New networks are deployed to reach more end users, Protocols are being developed to efficiently utilize the added bandwidth of these networks. Already widely adopted, One technology that will remain important for the foreseeable future is a shared media network. What is a shared media network? One communication channel (shared channel) A network shared by multiple end users, Uncoordinated transmissions from different end users can interfere with each other. Communication networks often have a limited number of communication channels, With a shared media network, Many end users can gain access on a single communication channel, Thereby, The remaining communication channels can be used for other purposes. But, The shared media network Each end user sends data intermittently, It is only feasible if you want other end users to be able to transmit during silence periods. One of the problems with shared media networks is that Scheduling the end user's transmissions so as to guarantee QoS for each end user and avoid collisions on the shared channel. The problem with this scheduling is It becomes extremely complicated when dealing with a large number of end users. Thus, There remains a need for a scheduling architecture that reduces scheduling complexity. BRIEF DESCRIPTION OF THE DRAWINGS FIG. FIG. 1 is a block diagram illustrating an example of a shared media network according to a preferred embodiment of the present invention. Fig. 2 FIG. 4 is a block diagram illustrating a headend unit and an access interface according to a preferred embodiment of the present invention. FIG. FIG. 2 is a block diagram illustrating a headend scheduler architecture according to a preferred embodiment of the present invention. FIG. FIG. 3 is a block diagram showing components of a headend scheduler according to a preferred embodiment of the present invention. FIG. 5A shows FIG. 4 is a diagram illustrating an example of a task frame map according to the embodiment of the present invention. FIG. 5B FIG. 4 is a diagram illustrating an example of a task frame map according to a preferred embodiment of the present invention. FIG. FIG. 4 is a diagram illustrating an example of a task frame map conceptualized as a plurality of bins according to a preferred embodiment of the present invention. FIG. Requirements according to a preferred embodiment of the invention, FIG. 3 is a block diagram summarizing the relationship between jobs and tasks. FIG. 5 is a flowchart illustrating transmission opportunity scheduling logic according to the present invention. Fig. 9 5 is a flowchart illustrating the scheduling logic of the rate commit component according to the present invention. Detailed description Fig. 1 FIG. 1 is a block diagram illustrating an example of a shared media network 100 according to a preferred embodiment of the present invention. With the shared medium network 100, The plurality of end users 110LLL1LLL to 110LLLNLLL are A remote external network 108, such as the Internet, can be accessed. The shared media network 100 It functions as a conduit for conveying information between the end user 110 and the external network 108. The shared media network 100 A head-end unit (HU: HeadendUnit) 102. HU102 With the shared physical medium 106, It communicates with a plurality of access interface units 104LL L1LLL to 104LLLNLLL (collectively referred to as AIU (Access Interface Unit) 104). Each end user 110 Interfaces with the shared media network 100 via the AIU 104. One AIU 104 corresponds to one or more end users 110. The shared physical medium 106 includes a plurality of channels, Information can be transferred between HU 102 and AI U 104 on that channel. In a preferred embodiment, Each channel is unidirectional. That is, A specific channel from HU102 to AIU104, Alternatively, information is transmitted from AIU 104 to HU 102. A channel for transmitting information from the HU 102 to the AIU 104 is usually called a “downstream channel”. A channel for transmitting information from the AIU 104 to the HU 102 is usually called an “upstream channel”. In an alternative embodiment, These various upstream and downstream channels, of course, For example, For the same physical channel via time division multiplex / duplex, Or, for example, there may be different physical channels via frequency division multiplex / duplex. In a preferred embodiment, The shared media network 100 The shared physical medium 106 is a bidirectional hybrid optical fiber coaxial cable (HFC: Data over cable (DOC: hybrid fiber-optic and coaxial cable) network data over cable) Communication system. HU102 It is a head-end device usually called a “cable router”. AIU104 is It is a cable modem. In other embodiments, The shared physical medium 106 coaxial cable, Optical fiber cable, Stranded wire vs. wire, etc. Aerial for wireless and satellite communications, May include air or space. In the shared medium network 100, Downstream channels are located in the frequency band above about 50 MHz. All information transmitted by HU 102 on a particular downstream channel, As we reach all AIUs 104, Downstream channels are classified as broadcast channels. Any AIU 104 that is tuned to receive on a particular downstream channel can receive the information. In the shared medium network 100, The upstream channel is located in a frequency band of about 5 to 42 MHz. Each upstream channel is Divided into consecutive time slots, Often referred to as "slotted channels." Slots are used to convey protocol data units containing user or control information, It may be further divided into minislots used to convey smaller units of information. The upstream channel is Classified as a shared channel since only one AIU 104 can be successfully transmitted in one slot or minislot at a particular time, To do so, the upstream channel must be shared among multiple AIUs 104. A collision occurs when two or more AIUs 104 transmit simultaneously on a particular upstream channel, Thereby, information from all the AIUs 104 to be transmitted at the same time is forged. To allow multiple AIUs 104 to share a single upstream channel, The HU 102 and the AIU 104 perform medium access control (MAC: mediu m access control) protocol. The MAC protocol is A set of rules and procedures for coordinating access by the AIU 104 is provided to the shared channel. Each AIU 104 enters the MAC protocol on behalf of its end user. For convenience, Each participant in the MAC protocol is called a "MAC user". MAC users Normal, Represents a connection corresponding to a particular end user application. I will not elaborate, MAC users may represent a collection of connections that share similar traffic characteristics. In many current communication networks, Each MAC user has specific traffic parameters and QoS requirements, These are approved by the MAC user to open a connection in the network, Guaranteed by the network. For example, MAC users guarantee a minimum amount of bandwidth, It may be necessary to guarantee a maximum transfer delay for the data to be transmitted or a minimum time variation between transmission opportunities provided by HU 102. Asynchronous transfer mode (ATM: Asynchronous Transfer Mode) and other cell-based networks, Several parameters are used to characterize the bandwidth requirements of each MAC user. In particular, A set of ATM traffic descriptors is used to characterize the type of traffic generated by MAC users, A set of QoS parameters is used to specify the network service required by the MAC user. ATM traffic descriptors include: Peak cell speed (PCR: Peak Cell Rate), Sustainable cell rate (SCR: Sustainable Cell Rate), Minimum cell rate (MCR: Minimum Cell Rate and Maximum Burst Size (MBS: Maxim um Burst Size). PCR is This is an index of the maximum data rate (the number of cells per second) generated by the MAC user. SCR is Represents the long-term average data rate generated by MAC users. MCR is This is the minimum data rate (number of cells per second) required by the MAC user. MBS is the maximum size (number of cells) of a burst generated by a MAC user. QoS parameters are Maximum cell transfer delay (MaxCTD: Maximum Cell Transfer Delay), Cell delay variation (CDV: Cell Delay Variation and Cell Loss Ratio (CLR: Cell Loss Ratio). MaxCTD is Identify the maximum delay allowed by the MAC user (including access delay and propagation delay of the underlying communication network). CDV is Specifies the maximum time variation between data transmission opportunities allowed by the MAC user. The CLR is As a ratio of lost cells to all cells transmitted by MAC users, Specify cells that the network can lose as long as the MAC user allows. MAC users with similar traffic characteristics are classified into service categories. ATM is 5 service categories, That is, continuous bit rate (CBR: continu ous bitorate), Real-time variable bit rate (RT-VBR: real-time variable bit rate), Non real-time variable bit rate (NRT-VBR: non-real-time variable bit rate), Available bit rate (A BR: available bit rate) and unspecified bit rate (UBR: unspecified bit rate). Each MAC user It falls into one of the service categories. CBR connection Has a fixed bit rate, Characterized by traffic requiring real-time delivery of cells. The ATM traffic descriptor for the CBR service category is PCR. The QoS parameter for the CBR service category is MaxCTD, CDV and CLR. RT-VBR connection Has a variable bit rate, Characterized by traffic requiring real-time delivery of cells. In a typical RT-VBR connection, The traffic on the connection is the period during which cells are generated in bursts in PCR, (With audio and real-time video being good examples of RT-VBR traffic). The ATM traffic descriptor for the RT-VBR service category is PCR, SCR and MBS. The QoS parameters for the RT-VBR service category are MaxCTD, CDV and CLR. NRT-VBR connection It is characterized by traffic having a variable bit rate (similar to an RT-VBR connection) but not requiring real-time delivery of cells. NRT-VBR connection Normally, Requires low CLR. ABR connection Requires a minimum cell rate, If additional bandwidth is available, it is characterized by traffic trying to accept it. ATM traffic descriptors for the ABR service category are MCR and PCR. MCR is Guaranteed minimum cell rate required by the connection. PCR is The maximum cell rate that can be transmitted on the connection if allowed by the network. as a result, The transmission speed of the ABR connection is Somewhere between MCR and PCR. For the ABR service category, No QoS parameters are defined. ABR connection Often dependent on a flow control mechanism with feedback. This mechanism is It requires a connection source to adapt its speed according to changes in ATM layer transfer characteristics. UBR connection No bandwidth is guaranteed, Has no QoS requirements. The ATM traffic descriptor for the UBR service category is PCR. PCR is The maximum cell rate that can be transmitted on the connection if allowed by the network. Several different MAC protocols have been developed for use in the shared media network 100. These protocols are In general, It is classified as a contention-free protocol and a contention-based protocol. Time Division Multiple Access (TDMA: Contention-free protocols, such as time-division multiple-access and round-robin polling, By various scheduling methods, Avoid collisions by allowing transmission to only one MAC user at a time on the upstream channel. Competing compliant protocols, such as certain reservation compliant protocols, do not avoid collisions, Eliminate all conflicts that occur on shared channels. In a preferred embodiment, The MAC protocol is Schedule upstream transmissions using a combination of polling and contention-based reservations. Competition-based reservations Requests that the HU 102 make a reservation before allocating bandwidth to the MAC user. HU102 By periodically sending special control messages (referred to as "entry poll messages") on the downstream channel to the AIU 104, Provide reservation opportunities to MAC users in the form of competing minislots. MAC users The reservation is performed by transmitting a reservation request message according to the reservation opportunity provided by the HU 102. Each reservation opportunity, Normal, Because it allows multiple MAC users to transmit in the contention minislot, MAC users must compete to make reservations. Not all MAC users are required to make a reservation. Some MAC users can be allocated bandwidth on a regular basis without reservations. Fig. 2 FIG. 2 is a block diagram 200 illustrating the HU 102 and the AIU 104 in more detail. The block diagram 200 is HU 102 is in communication with one of the AIUs 104 via a downstream channel 230 and an upstream channel 240. AIU104 is Support at least one end user 110. HU 102 sends data and control messages to AIU 104 via downstream channel 230, Reservation requests and data are received from AIU 104 via upstream channel 240. HU102 is a connection manager (CM: Connection Manager) 215. The CM 215 is responsible for network connection participation control. For more information, CM 215 Responsible for opening and terminating connections within the network. To enable end users, such as end user 110, to communicate on the network, a connection must be opened. Therefore, When end user 110 requests to join the network, The connection request message is transferred to CM 215. The connection request message is Bandwidth and QoS requirements for connections ATM service categories, It is specified in the form of the relevant ATM traffic descriptor and QoS parameters. CM 215 Decide whether to open a connection, Thereby, Based on whether the network can meet the bandwidth and QoS requirements of the end user 110, Authorize the end user 110 to join the network. HU102 is a head-end scheduler (HES: Headend Scheduler) 214, This is the CM215 and the Adaptive Reservation Manager (ARM: Adaptive Response Manager) 211. HES 214 is responsible for scheduling transmission opportunities for end users authorized to join the network by CM 215. When CM 215 opens a connection, CM 215 A connection identifier for the established connection; A connection setup message containing the ATM service category and the associated ATM traffic descriptor and QoS parameters is sent to the HES 214. Similarly, when the CM 215 terminates the connection, CM 215 sends a connection release message to HES 214 containing a connection identifier for the terminated connection. HES214 is The connection information received from CM 215 Used together with the feedback information received from ARM 211, The timing of the control message transmitted by the ARM 211 is controlled. ARM211 Responsible for implementing the MAC protocol in HU 102. ARM211 is a Reservation Manager (RM: Reservation Manager) 212 and feedback controller (FC: Feedback Controller) 213. RM212 Monitoring contention minislots on upstream channel 240, Determine the outcome of the conflict in each conflict minislot. RM21 2 The competition result is sent to FC 213 and HES 214. FC213 Maintain state information for each priority class (if multiple priority classes are implemented to accommodate different quality of service), Determine contention minislot assignments for each contention cycle, Format the control message sent on the downstream channel 230. FC213 In particular, Based on the timing information received from HES 214, Determine the timing of control message transmission. AIU104 is A user interface (UI) for interfacing with the end user 110 User Interface) 225. Data sent by the end user 110 is received by the UI 225, It is stored in the memory 224. UI 225 In the memory 224, A time stamp indicating the arrival time of the data is also stored. AIU104 is A control message processor (CMP: A Control Messega Processor 222 is also provided. CMP 222 is Responsible for processing data and control messages received from HU 102 by receiver 211. CMP2 22 2. Enter the MAC protocol on behalf of the end user 110 as a MAC user. FIG. FIG. 2 is a block diagram illustrating a HES214 architecture according to a preferred embodiment of the present invention. As shown in FIG. The HES 214 has a request queue 302. HES214 is Maintain one request queue for each ATM service category. When CM 215 allows MAC users to join, CM 215 sends a request to HES 214. This request includes: The request details and the service category are included. The request details include An identifier identifying the MAC user involved in the request; And a queue depth indicating the number of staying cells of the MAC user waiting for a transmission opportunity. The service category is Marks the ATM service category for MAC users. Request is, It is placed in the request queue according to the service category. If the reservation of the MAC user succeeds (or the MAC user is given a transmission opportunity without reservation), HES 214 converts the request into a job. What is a job? Basically, This is a request that requires scheduling by the HES 214. The job is Includes a job statement that includes the request statement from the request, It also includes QoS parameters for MAC users. The job is It is queued in job buffer 304. Also, An entry polling job is created internally by the HU 102. The entry polling job is Requires a transmission opportunity corresponding to the contention-based reservation mechanism. For each of these transmission opportunities, HES 102 allows one or more MAC users to send reservation requests (not data). Since these reservation opportunities are given regularly, Each MAC user with data to be transmitted can make a reservation in a timely manner. Like other jobs, Entry polling jobs are also queued in job buffer 304. Each job in the job buffer 304 is Service category indicated in the corresponding job description, Converted to a task or set of tasks based on bandwidth and QoS requirements. Each task is This corresponds to a data unit (for example, an ATM cell) waiting for transmission opportunity allocation in the upstream channel. Each task has an associated task description, This specifies the CDV tolerance for the preferred transmission slot and task. HES214, Each authorized MAC user has its bandwidth, To ensure and receive enough transmission opportunities to satisfy delay and jitter constraints, Scheduling problems arise when transmission opportunities have to be allocated to some tasks. To accommodate many MAC users with different bandwidth and QoS requirements, The scheduling problem becomes extremely complicated. HES214 is Dividing the upstream channel 240 into contiguous data slots; Data transmission is scheduled by assigning each data slot to a specific task. Therefore, HES214 is In each entry poll message, Contains fields that assign each data slot to a particular task. For convenience, This field is called a transmission frame 306. The transmission frame 306 is Consists of multiple consecutive slots. Each slot in the transmission frame 306 is It corresponds to a data slot on the upstream channel 240. Each slot in the transmission frame 306 is Indicates whether the corresponding data slot is reserved for transmission of MAC user information or entry polling. If the data slot is reserved for transmission of MAC user information, The slot in the transmission frame 306 is further, Indicates which MAC users are allowed to transmit in the data slot. As shown in FIG. One way to simplify HES2114 is The scheduling problem is divided into two sub-problems, That is, the problem of scheduling the committed bandwidth component, The problem is to deal with the scheduling of the variable bandwidth component. What is the bandwidth commissioning component? It is a component that requires a certain amount of transmission opportunities within a specific period. In some cases, These transmission opportunities must be provided at periodic intervals. CBR Traffic is A good example of a bandwidth commissioning application is This is because HES must provide a stable stream of slots in PCR within CVD constraints. The CDV constraint is It can be satisfied by providing slots (ie, periodic transmission opportunities) at regular intervals. What is a variable bandwidth component? The demand for transmission opportunities is flexible, This is a component that does not require a predetermined amount of transmission opportunities within a specific period. UBR traffic A good example of a variable bandwidth application is This is because HES 214 Without guaranteeing any bandwidth, Therefore, the MAC user can have the HES 214 allocate bandwidth when the surplus bandwidth is available. The preferred embodiment is Take advantage of this architecture by splitting each request into a committed-rate component and a variable-rate component. Depending on your request, One having only one component (ie speed commissioning or variable speed); Some have both components. The speed commissioning component is Converted to a speed commission job 308, The variable speed component is converted to a variable speed job 310. Scheduling a rate commission job 308 using the rate commission component scheduler 312; The variable speed job 310 is scheduled using the variable speed component scheduler 314. Each scheduler Apply the scheduling rules that are appropriate for the individual components. The pole generator 316 Tasks from the rate commit component scheduler 312 and the variable speed component scheduler 314 are: It is arranged in the transmission frame 306. The rate commission job is guaranteed a slot in the transmission frame 306. For variable speed jobs, Extra slots in the transmit frame 306 that are not assigned to the rate commission job are provided. The CBR service category is Includes only the speed commissioning component. CBR MAC users Until the CBR connection is terminated, a periodic transmission opportunity is continuously allocated in the PCR. Transmission opportunities are allocated within the delay and jitter constraints of the MAC user. The RT-VBR service category contains only the rate commission component. The entire text is incorporated herein by reference. US Provisional Patent Application No. 60/055, filed August 14, 1997. Issue 658, “System, Device, And Method For Scheduling In A Communication Network '' Several alternative embodiments for scheduling RT-VBR traffic are disclosed. One example, starting on page 11, line 16, is Treat certain RT-VBR connections as if they were CBR connections. this is, Specific RT-VBR connection, Specifically, it is appropriate for connections with a ratio of SCR to PCR that exceeds a predetermined threshold (referred to as "CBR-like" connections), Insufficient for other RT-VBR connections (referred to as "bursty" connections). Two methods for scheduling "bursty" RT-VBR traffic are disclosed. In the first embodiment starting from page 12, line 15, While a MAC user is active, RT-VBR MAC users Regular transmission opportunities are allocated in PCR, If the MAC user is inactive, it is allocated at zero speed. In the second embodiment, which starts on page 14, line 13, For RT-VBR MAC users, While the MAC user is active, periodic transmission opportunities are allocated in the PCR, Allocated at low speed (preferably SCR) while the MAC user is inactive. Bandwidth requirements for "bursty" RT-VBR connections vary, It should be noted that "bursty" RT-VBR connections do not include a variable speed component. this is, RT-VBRMAC users still This is because a predetermined amount of transmission opportunity is required within a specific period. Transmission opportunities are allocated within the delay and jitter constraints of the MAC user. The NRT-VBR service category includes both rate committed and variable rate components. For NRT-VBR MAC users, Transmission opportunities are allocated in the SCR (ie the rate commission component), If the amount of data queued for transmission by the MAC user exceeds a predetermined threshold (ie, a variable speed component), Additional transmission opportunities are allocated. Signaling of queuing depth information for HES 214 by the MAC user is: For example, This can be done by including status information along with the data transmission (often referred to as "piggybacking"). About NRT-VBR, There are no specific delay and jitter constraints for the rate commissioning component. The ABR service category includes both rate committed and variable rate components. For ABR users, Transmission opportunities are allocated in the MCR (ie the rate commissioning component), If there is a transmission opportunity available after the assignment for the speed commission job, Additional transmission opportunities are allocated (ie, variable speed components). About ABR, There are no specific delay and jitter constraints for the rate commissioning component. The UBR service category contains only variable speed components. For UBR users, If you have a "remaining" submission opportunity, It is allocated. As with user requests, Entry polling jobs are also classified into a rate commissioning component and a variable speed component. In a preferred embodiment, The entry polling job has a rate commissioning component that provides regular reservation opportunities, Includes both rate variable components that provide additional reservation opportunities. This additional reservation opportunity MAC protocol performance during collision resolution can be improved but is optional. In an alternative embodiment, The entry polling job contains only the rate commit component. One scheduling method for multi-class users with different bandwidth and QoS requirements is disclosed in U.S. Patent No. 5, filed June 18, 1996 by Vaitzblit et al. 528, No. 513, "Scheduling and Admission Control Policy for a Continuous Media Server". According to Vaitzblit's patent for a continuous media file server, Three classes of users are supported: Ie general purpose, Real-time and isochronous. The generic class supports preemptive tasks that are suitable for low priority background processing. But, This class only guarantees minimal CPU processing. The real-time class is Represents a user who needs guaranteed processing power and limited delay. This class is not replaced, A replacement window is provided for scheduling higher priority users. Isochronous classes are Represents users who need performance assurance on periodic transmissions and processing power, limited waiting time and low jitter. According to Vaitzblit, Isochronous tasks have the highest priority, Scheduled first. And a real-time class, A general class follows. Isochronous tasks are executed periodically, It is started by a timer interrupt set for each task. After the isochronous task has been scheduled, The scheduler Alternate real-time tasks and general-purpose tasks using a weighted round-robinscheme. Isochronous tasks involving users requiring different speeds include: Further priority is given in a monotonic manner. That is, A user with a higher speed has a higher priority. These tasks are performed periodically, Triggered by a timer interrupt set for the corresponding temporal period. The scheduler executes the isochronous tasks from a prepared queue in which the isochronous tasks are arranged in order of decreasing priority. When an isochronous task arrives at the server, It is inserted at an appropriate place in the prepared queue. An isochronous task arrives every time the periodic timer elapses. Each of the isochronous tasks permitted to participate has its own periodic timer for each individual period. All isochronous tasks with the same duration Executed when the timer associated with that period elapses. When an isochronous task arrives at the server, The scheduler determines whether the currently running task needs to be replaced. If the currently running task has a lower priority than the arriving task, Depending on the task coming from the head of the queue, It will be replaced in the next replacement window. The replaced task is It is placed at the head of the queue for that task. this is, To be a previously commissioned speed commission task, This is because it is assumed to have the highest priority among all tasks waiting in the queue. Scheduling tasks by Vaitzblit for data unit pending transmission Its real-time replacement has its drawbacks. Above all, When the replacement is performed, it becomes difficult to guarantee the bandwidth and the QoS. Also, If there are many different speeds because each speed uses a different timer, Timer management for isochronous task scheduling may be cumbersome. Preferred embodiments of the present invention are: Non-replacement scheduling is used to schedule tasks. For more information, The rate delegation component scheduler 312 creates a map of transmission opportunities. this is, Repeated at periodic intervals, each rate commissioning job provides the required bandwidth within arbitrary delay and jitter constraints. This map is It consists of a number of slots that are initialized based on the bandwidth and QoS requirements of the rate commission job. When created for a particular set of jobs, The map will be added to the job, Job is deleted, Alternatively, it typically does not change until the bandwidth and / or QoS requirements of existing jobs change. By creating a map of transmission opportunities, Speed commission jobs in real time, It can be scheduled a priori for each frame. Normal, Not all slots in the map are used for scheduling rate commission jobs. Slots that are not used for scheduling a speed commission job It can be used for allocating variable speed jobs. The transmission opportunity map is By definition, It has a repeatable pattern of slot allocation. It is desirable to use the smallest repeatable pattern to avoid long transmission cycles. If the smallest repeatable pattern is too large to convey in one entry poll message, The map can be divided into smaller equal parts (called task frames). The pole generator is Each transmission frame 306 has one task frame. FIG. FIG. 2 is a block diagram illustrating components of a HES 214 according to a preferred embodiment of the present invention. As shown in FIG. The rate commissioning component scheduler 312 It comprises a mapper 402 and a plurality of task frames 404. The mapper 402 Convert the speed commission job 308 to a task, Place the task in task frame 404. The method will be described in detail below. The speed variable component scheduler 314 includes: A priority determining device (Prioritizer) 406 and a task queue 408 are provided. The priority determining device 406 converts the variable speed job 310 into a task, Place the task in the task queue 408. The priority determining device 406 Preferably, The priority of the variable speed job 310 is determined using the weighted round table rule. The weights used for weighted round table scheduling are: ATM service category, Queue depth and variable speed job 310 may be a function of other relevant characteristics, It changes over time. The pole generator 316 One task frame 404 is provided in each transmission frame 306. The pole generator 316 One task frame 404 is selected from the plurality of task frames 404 based on a strict round table method. Next, the pole generator 316 An arbitrary empty slot in the transmission frame 306 is used as a variable speed task from the task queue 408, Preferably, fill in the order of earliest. The main elements of the present invention are: Scheduling the speed commission job 308 in the task frame 404. The number of slots that make up the map is In general, It is a function of the set of individual bandwidth requirements supported by the system. The job with the lowest bandwidth requirement is When having periods that are integer multiples of different periods supported by the system, The job with the lowest bandwidth will have the longest period for the repeating pattern of slots in the map, All other jobs will have a repeatable pattern within the same time period. In some embodiments, The number of task frames 404 that collectively constitute a repeatable pattern is Determined by the number of task frames 404 having the highest bandwidth requirements, Preferably, Each rate commission job 308 is selected to be able to allocate no more than one slot per task frame 404. The rate R for each rate commission job 308 in the form of cells per second is It can be converted to a transmission period S in the form of a transmission slot number (ie one cell must be transmitted every S slots). However, S need not be an integer.) t Assuming that the time required to transmit one cell in one transmission slot is a value in seconds, The period can be S * t (seconds). In order to satisfy the speed R accurately, One cell must be transmitted in each period. Therefore, R * S * t = 1. That is, the period S is 1 / (R * derived from t). 1 / (R * Assuming that t) is an integer, each periodic cell transmission directly coincides with a slot boundary. However, 1 / (R * If (t) is not an integer, cell transmission is 1 / (R * It is not possible to schedule during period t). This is because each periodic cell transmission does not directly coincide with a slot boundary. One alternative is to substitute S for 1 / (R * t) is set equal to the "lowest value" of (i.e., 1 / (R * t) the largest integer less than). As a result, transmission opportunities are scheduled more frequently than required to accommodate rate R. An indication of this estimation error is that some cells do not convey the full data load, and therefore must properly pad the "idle bit". A second alternative is to set S to 1 / (R * t) equal to the "highest value" of (i.e., 1 / (R * t) the smallest integer greater than). As a result, transmission opportunities are scheduled less frequently than required to accommodate rate R. An indication of this estimation error is that some cells may be buffered within their delay and jitter constraints, or may go away if not transmitted. A preferred embodiment is 1 / (R * If t) is not an integer, S is 1 / (R * Select to be the "lowest value" of t). According to the present invention, when all the speed commission jobs 308 have a common transmission speed R, the map of the dimension S determined as described above can be used for scheduling. In this case, each user requires one slot in the map (ie, each user requires one slot per period). The location of the slot assigned to a user depends on its delay and jitter constraints. Since all users share the same periodicity, only one task frame 404 of size S is needed. The above non-replacement scheduling method can be used to accommodate users having different transmission rates. The different speeds associated with the speed commissioning job can each be rewritten to a period in the manner described above. A set of different speeds related to the speed commission job is {R1, R2,... Rm}, and corresponding different periods are {S1, S2,. Here, S * is the least common multiple (LCM) of Si (i = 1, 2,... M). When a task frame of size S * is used, the transmission pattern in the task frame 404 is a repeatable pattern and is guaranteed to be the smallest repeatable pattern. Assuming that each individual period is an integer divisor of the maximum period S_max, S_max is simply the LCM of the set of individual periods and a task frame of size S can be used. In general, S *, the LCM between sets of individual periods, is much larger than S_max. The use of a task frame of size S * makes it impossible to meet the delay constraints of some users. One preferred embodiment uses a frame of dimension S_min, which is the minimum number of Si, where i = 1,2, ... m, so that there is still at least one assignment within each task frame. It is to be. In this way, no users are unnecessarily delayed. Using smaller frames, the number of task frames 404 in the map is K = S * / S_min. The above scheduling method can be demonstrated with an example. In this example, there are three jobs to be scheduled. Job number 1 has period 4. Job number 2 has period 8. Job number 3 has a period 16. Using the above number system, the scheduling problem becomes S_max = 16, S_min = 4 and S * = 16 (ie, 4, 8, 16 LCMs). In one embodiment shown in FIG. 5A, a single task frame of size S * = 16 is used. This guarantees that the transmission pattern in the task frame is a repeatable pattern and is also the smallest repeatable pattern. In this case, job number 1 is assigned four slots in the task frame, job number 2 is assigned two slots in the task frame, and job number 3 is assigned one slot in the task frame. Is allocated. In the preferred embodiment shown in FIG. 5B, a task frame of size S_min = 4 is used. The minimum repeating pattern is S * = 16 slots, so K = 4 task frames are required. In this case, job number 1 has one slot in each task frame, job number 2 has one slot in every other task frame, and job number 3 has every five task frames. Is allocated. When scheduling the rate-commissioned job 308 in the task frame 404, scheduling jobs with delay and jitter constraints is more difficult than scheduling jobs without delay and jitter constraints. It determines which slots in the map can or cannot be used for a particular task by delay and jitter constraints (ie, which slots are involved in delay and jitter constraints and which are not). That's why. Also, when scheduling the rate commission job 308 within the task frame 404, scheduling high bandwidth jobs is generally more difficult than scheduling low bandwidth jobs. Thus, as shown in FIG. 4, the preferred embodiment includes a rate commission job 308 with a QOS job 410 (ie, a job with delay and jitter constraints) and a non-QOS job 412 (ie, a job without delay and jitter constraints). Classified as The QOS job 410 is prioritized according to its data rate requirements, with the job with the highest speed given the highest priority. Similarly, non-QOS jobs 412 are prioritized according to their data rate requirements, with the job with the highest speed given the highest priority. Such a speed-monotonous queuing rule is similar to the speed-monotone queuing rule for the prepared queue in the Vaitzblit method for isochronous task scheduling. The rate commission component scheduler 312 first schedules the QOS jobs 410 from the highest priority job such that each job is allocated its required bandwidth within the required delay and jitter constraints. For these jobs, the problem of allocating slots within task frame 404 can be modeled as a type of bin packing problem. As shown in FIG. 6, multiple task frames 404 can be conceptualized as a number of bins. If jitter is not allowed, each "row" consisting of one slot in each task frame 404 corresponds to one bin. If jitter is allowed, multiple adjacent "rows" correspond to one bin. Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithm by DS Johnson, A. Demers, JDUllman, MRGarey, RLGraham (Society for Industrial and Applied Mathematics Journal of Computing, Vol. 3, No. 4) (December 1974) Monthly publication) discusses the one-dimensional packing algorithm. A more complex bin packing problem corresponding to dynamic packing is described in Dynamic Bin Packing by EGCoffman, Jr., MR Carey, DS Johnson (Society for Industrial and Applied Mathematics Journal of Computing, Vol. 12, No. 2) (1983). May issue). In short, the problem of bin packing is usually the packing of a plurality of items of different dimensions in a certain space. In general, satisfactory results are obtained by packing the largest items first and then filling in smaller ones. Improved results are obtained by allowing items to be removed, rearranged, and repacked (even when time consuming and complex). The bin packing problem faced by the rate commit component scheduler 312 is comparable to the dynamic bin packing problem. This requires "packing" multiple jobs with different bandwidth requirements into a fixed number of slots. The rate commit component scheduler 312 typically packs bins to meet the bandwidth and QoS requirements of the highest priority job and fills the remaining jobs with decreasing bandwidth requirements. When allocating slots within the task frame 404, the slots are preferably distributed evenly among the columns of the task frame 404. If the rate commissioning component scheduler 312 cannot meet the job delay and jitter requirements using available slots, the rate commissioning component scheduler 312 changes the slot allocation. For example, the rate commissioning component scheduler 312 moves the existing allocation from one slot to an allowed neighboring slot (ie, the slot within the corresponding job delay and jitter constraint) to reduce the jitter constraint of the scheduled job. May release a slot at In the worst case, the rate commit component scheduler 312 must retrieve, relocate, and repack some or all of the jobs. The detailed formulation of the above packing problem and practical solution is beyond the scope of the present invention. When the QOS job 410 is scheduled, the rate commission component scheduler 312 schedules the non-QOS jobs 412 such that the bandwidth required for each job is allocated from the highest priority job (delay and jitter). Does not matter). The distribution of slots for non-QOS jobs 412 is not very important, but it is preferable that non-QOS jobs are also distributed evenly throughout task frame 404. As a result, a uniform number of empty slots that can be used for the variable speed job 310 is provided to each transmission frame 306. Each transmit frame 306 generated by the poll generator 316 is transmitted to the MAC user in an entry poll message. MAC users with data to transmit are allowed to transmit in the specified data slot. HU 102 monitors the data slots to determine the status of the MAC user. MAC users that transmit data when given the opportunity to transmit are usually considered "active". MAC users that do not transmit data when given a transmission opportunity are usually considered "inactive" (if a MAC user is not required to make a reservation, a MAC user is considered "active"). Made, but not limited to this). However, additional MAC user status information is available for HU 102. For example, a MAC user transmitting data may have an indicator of whether it has more data to transmit (often referred to as "piggybacking"). An indicator that a MAC user has no data to send may indicate an "inactive" situation when the MAC user sends data. HES 214 typically continues to provide “active” MAC users with transmission opportunities. HE S 214 typically stops providing transmission opportunities to "inactive" MAC users. In the latter case, HES 214 considers the associated job "achieved (achieved)" and removes (deletes) the associated job from job buffer 304. A job associated with a MAC user is considered "achieved" if certain idle conditions are met. This idle condition is defined in terms of the ATM service category and the QoS requirements of the job. For CBR, NRT-VBR and ABR jobs, it is considered "achieved" when and only if the corresponding connection is terminated. Otherwise, the job (or jobs) remains in job buffer 304 and the MAC user continues to receive bandwidth allocation. The RT-VBR job may or may not need to be deleted depending on the method used to respond to the RT-VBR job as described above. In one embodiment, the RT-VBR job is allocated bandwidth at PCR while "active" and at zero when "inactive". Such an RT-VBR job is considered "active" if the MAC user succeeds in the reservation, and if the MAC user fails to transmit data in response to a predetermined number of consecutive transmission opportunities (e.g., two), Considered "inactive". Further, such an RT-VBR job is considered "achieved" if the MAC user is "inactive". In this embodiment, the RT-VBR job is dynamically added to the job buffer 304 when the MAC user becomes “active” and is deleted from the job buffer 304 when the MAC user becomes “inactive”. In an alternative embodiment, the RT-VBR job is allocated bandwidth at PCR during "active" and at a lower (non-zero) rate when "inactive". Such RT-VBR jobs are always considered "active" (as long as a connection exists). In this embodiment, the RT-VBR job stays in the job buffer 304 indefinitely, but the relative priority of such RT-VBR jobs (based on the bandwidth requirements described above) changes as the speed changes. May change to Such a rate change prompts the rate commit component scheduler 312 to update the task frame 404 based on the new rate information. For UBR users, a job is considered "achieved" if there is no dwell data. Entry poll jobs are always active and will not be deleted. When a job is deleted from the job buffer 304, it is reconverted into a request and placed in the appropriate request queue 302. At the same time, all tasks corresponding to the job are deleted from task frame 404 and / or task queue 208. If the request itself is "fulfilled", for example, the connection is terminated, the request is deleted from the request queue 302. FIG. 7 is a block diagram summarizing the relationship between requests, jobs and tasks according to a preferred embodiment of the present invention. A new request 702 from CM 215 is placed in request queue 302. The request 702 is converted to a new job 704 and stored in the job buffer 304. Also, the entry polling job 706 is stored in the job buffer 304. Jobs 704 and 706 are converted to tasks 708 to which transmission opportunities are assigned. The accomplished job 710 is deleted from the job buffer 304 and reconverted into a request and placed in the request queue 302. The fulfilled request 712 is deleted from the request queue 302. FIG. 8 is a flowchart illustrating the logic for scheduling transmission opportunities according to the present invention. The logic begins at step 802, and at step 804, classifies each of the plurality of scheduling jobs into a rate commit component and a variable rate component. The rate commitment component requires a predetermined number of transmission opportunities within a certain amount of time, and the variable speed component requires an infinite number of transmission opportunities within a certain amount of time. The logic is such that when repeated at predetermined periodic intervals, each rate commit component has a transmit opportunity map that provides the required number of transmit opportunities within its predetermined delay and jitter constraints. Perform scheduling. This is step 806. Logic performs scheduling of the variable rate component in step 808 by allocating unused transmission opportunities in the map to the variable rate component in a predetermined manner. Logic ends at step 899. FIG. 9 is a flowchart illustrating the logic for scheduling the rate commit component in accordance with the present invention. The logic begins at step 902 and at step 904, classifies the rate commit components into those that require delay and jitter constraints and those that do not require delay and jitter constraints. The logic determines, in step 906, the priority of rate delegation components that require delay and jitter constraints based on bandwidth requirements, and in step 908 rate delegation that does not require delay and jitter constraints based on bandwidth requirements. Determine the priority of the components. Next, the logic assigns, in step 910, the speed commissioning components that require delay and jitter constraints into the map in order of priority, and then in step 912 prioritizes the speed commissioning components that do not require delay and jitter constraints. Assign them in the map in order of degree. The logic ends at step 999. All logic described herein may be implemented in conjunction with discrete components, integrated circuit configurations, programmable logic elements such as field programmable gate arrays (FPGAs) or microprocessors. It can be embodied using possible logic or by any other means, including combinations thereof. The programmable logic may be temporarily or permanently fixed to a tangible medium such as a read-only memory chip, a computer memory, a disk, or other storage medium. The programmable logic may be fixed in a computer data signal embodied in a carrier wave and transmitted via an interface such as a computer bus or a communication network. All of these examples fall within the scope of the present invention. The present invention may be embodied in other specific forms without departing from its essence or essential characteristics. The disclosed embodiments are illustrative in all respects and are not restrictive.

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＣＹ， ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，Ｉ Ｔ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＧＷ，ＭＬ， ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＧＭ，Ｋ Ｅ，ＬＳ，ＭＷ，ＳＤ，ＳＺ，ＵＧ，ＺＷ)，ＥＡ(ＡＭ ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ，ＲＵ，ＴＪ，ＴＭ) ，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ，ＢＡ，ＢＢ，ＢＧ， ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＵ，ＣＺ，ＤＥ，Ｄ Ｋ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＥ，ＧＨ，ＧＭ，ＨＲ ，ＨＵ，ＩＤ，ＩＬ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ， ＫＲ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，Ｌ Ｖ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ， ＳＫ，ＳＬ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＵＡ，ＵＧ，Ｕ Ｚ，ＶＮ，ＹＵ，ＺＷ (72)発明者 クラムタック，イムリッチ アメリカ合衆国テキサス州ダラス、ナンバ ー325，フランクフォード・ロード7575────────────────────────────────────────────────── ─── Continuation of front page    (81) Designated country EP (AT, BE, CH, CY, DE, DK, ES, FI, FR, GB, GR, IE, I T, LU, MC, NL, PT, SE), OA (BF, BJ , CF, CG, CI, CM, GA, GN, GW, ML, MR, NE, SN, TD, TG), AP (GH, GM, K E, LS, MW, SD, SZ, UG, ZW), EA (AM , AZ, BY, KG, KZ, MD, RU, TJ, TM) , AL, AM, AT, AU, AZ, BA, BB, BG, BR, BY, CA, CH, CN, CU, CZ, DE, D K, EE, ES, FI, GB, GE, GH, GM, HR , HU, ID, IL, IS, JP, KE, KG, KP, KR, KZ, LC, LK, LR, LS, LT, LU, L V, MD, MG, MK, MN, MW, MX, NO, NZ , PL, PT, RO, RU, SD, SE, SG, SI, SK, SL, TJ, TM, TR, TT, UA, UG, U Z, VN, YU, ZW (72) Inventor Clamtack, Imrich             Dallas, Texas, United States             -325, 7575 Frankford Road

Claims (1)

【特許請求の範囲】 １．共有媒体通信ネットワーク内に分布するユーザの集団により生成される複 数のスケジューリング・ジョブに関して送信機会をスケジューリングする方法で あって、送信機会は中央コントローラを介して予約され、本方法が： 複数のスケジューリングジョブの各々を、一定の時間量内に所定数の送信機会 を必要とする速度委託構成部分と、前記一定の時間量内に不定数の送信機会を必 要とする速度可変構成部分とに分類する段階； 所定の周期的間隔で反復されると、その所定の遅延およびジター制約内で必要 数の送信機会を各速度委託構成部分に提供する送信機会マップを作成することに よって前記速度委託構成部分のスケジューリングを行う段階；および 前記マップ内の未使用送信機会を、所定の方法により前記速度可変構成部分に 割り当てることによって、前記速度可変構成部分のスケジューリングを行う段階 ； によって構成されることを特徴とする方法。 ２．前記速度委託構成部分をスケジューリングする前記段階が； 前記速度委託構成部分を遅延およびジター制約を必要とする速度委託構成部分 と、遅延およびジター制約を必要としない速度委託構成部分とに分類する段階； 帯域幅要件に基づき、遅延およびジター制約を必要とす る前記速度委託構成部分の優先度を決定する段階； 帯域輻要件に基づき、遅延およびジター制約を必要としない前記速度委託構成 部分の優先度を決定する段階； 遅延およびジター制約を必要とする前記速度委託構成部分を、優先度の順に前 記マップ内に割り付ける段階；および 続いて、遅延およびジター制約を必要としない前記速度委託構成部分を、優先 度の順に前記マップ内に割り付ける段階； によって構成されることを特徴とし、 前記速度可変構成部分のスケジューリングを行う前記段階が： 前記速度可変構成部分を前記マップ内の未使用スロット内に、重み付け円卓法 スケジューリング規則を用いて割り付ける段階であって、前記重み付け円卓スケ ジューリングに用いられる前記重みがATMサービス・カテゴリ，待行列深さおよ び前記速度可変構成部分の他の関連特性の関数であり、時間と共に変化すること を特徴とする請求項１記載の方法。 ３．分類およびスケジューリングを行う前記段階が： 各連続ビット速度スケジューリング・ジョブを、遅延およびジター制約を必要 とする速度委託構成部分のみに分類し、各連続ビット速度スケジューリング・ジ ョブの前記速度委託構成部分に関する送信機会を、その所定の遅延およ びジター制約内の所定のピーク・セル速度においてスケジューリングする段階； 各リアルタイム可変ビット速度スケジューリングジョブを、遅延およびジター 制約を必要とする速度委託構成部分のみに分類する段階；および 各リアルタイム可変ビット速度スケジューリング・ジョブの前記速度委託構 成部分に関する送信機会をその所定の遅延およびジター制約内で所定のピーク・ セル速度においてスケジューリングする段階； 各リアルタイム可変ビット速度スケジューリング・ジョブの前記速度委託構 成部分に関する送信機会を、前記速度委託構成部分がアクティブのときはその所 定の遅延およびジター制約内の所定のピーク・セル速度において、また前記速度 委託構成部分が非アクティブの場合はゼロ速度においてスケジューリングする段 階；および 各リアルタイム可変ビット速度スケジューリング・ジョブの前記速度委託構 成部分に関する送信機会を、前記速度委託構成部分がアクティブのときはその所 定の遅延およびジター制約内の所定のピーク・セル速度において、また前記速度 委託構成部分が非アクティブの場合はそれよりも低い（非ゼロの）速度において スケジューリングする段階； のうち１つの段階によって構成される段階； 非リアルタイム可変ビット速度スケジューリング・ジョブを、遅延およびジタ ー制約を必要としない速度委託構成 部分と速度可変構成部分とに分類し、各非リアルタイム可変ビット速度スケジュ ーリング・ジョブの前記速度委託構成部分に関する送信機会を、その所定の維持 可能セル速度においてスケジューリングし、送信すべきデータの滞留に基づいて その所定の維持可能セル速度を超える追加の送信機会が必要とされる場合はいつ でも、各非リアルタイム可変ビット速度スケジューリング・ジョブの前記速度可 変構成部分に関する送信機会をスケジューリングする段階； 使用可能ビット速度スケジューリング・ジョブの各々を遅延およびジター制約 を必要としない速度委託構成部分と速度可変構成部分とに分類し、使用可能ビッ ト速度スケジューリング・ジョブの各々の前記速度委託構成部分に関する送信機 会を、その所定の最小セル速度においてスケジューリングし、使用可能なビット 速度スケジューリング・ジョブの各々の前記速度可変構成部分に関する送信機会 を、その所定のピーク・セル速度までスケジューリングする段階 各未指定ビット速度スケジューリング・ジョブを速度可変構成部分のみに分類 し、送信機会が使用可能な場合はいつでも、各未指定ビット速度スケジューリン グ・ジョブの前記速度可変構成部分に関する送信機会をスケジューリングする段 階；および 各エントリ・ポーリング・スケジューリング・ジョブを速度委託構成部分およ び速度可変構成部分の両方に分類し、前記エントリ・ポーリング・スケジューリ ング・ジョブの 前記速度委託構成部分に関する送信機会を定期的間隔でスケジューリングし、送 信機会が使用可能な場合はいつでも、前記エントリ・ポーリング・スケジューリ ング・ジョブの前記速度可変構成部分に関する送信機会をスケジューリングする 段階； によって構成されることを特徴とする請求項２記載の方法。 ４．各速度委託構成部分が送信期間を有し、前記マップが異なる速度委託構成 部分に関する前記送信期間の最小公倍数に少なくとも等しい所定数のスロットに よって構成されることを特徴とする請求項１記載の方法。 ５．前記マップが所定寸法の複数のタスク・フレームによって構成され、各速 度委託ジョブが１つのタスク・フレームにつき２つ以上のスロットを割り振られ ず、未使用スロットが一度に１タスク・フレームずつ速度可変構成部分に割り振 られることを特徴とする請求項４記載の方法。 ６．送信機会の割当を含むエントリ・ポール・メッセージを生成する段階によ ってさらに構成され、前記マップが複数のタスク・フレームを備え、前記エント リ・ポール・メッセージを生成する前記段階が： 前記エントリ・ポール・メッセージ内の前記数のタスク・フレームのうちの１ つを備える段階；および 前記タスク・フレーム内の未使用送信機会を、所定の方法により前記速度可変 構成部分に割り当てる段階； によって構成されることを特徴とする請求項１記載の方法。 ７．コンピュータ使用可能な媒体内にコンピュータ読取可能なプログラム・コ ード手段を有する前記媒体によって構成され、共有媒体通信ネットワーク内に分 布するユーザの集団により生成される複数のスケジューリング・ジョブに関して 送信機会をスケジューリングする装置であって、送信機会が中央コントローラに より予約され、前記コンピュータ読取可能プログラム・コード手段が： 複数のスケジューリング・ジョブの各々を一定の時間量内に所定数の送信機会 を必要とする速度委託構成部分と前記一定の時間量内に不定数の送信機会を必要 とする速度可変構成部分とに分類するコンピュータ読取可能プログラム・コード 手段； 所定の周期的間隔で反復されると、その所定の遅延およびジター制約内で必要 数の送信機会を各速度委託構成部分に提供する送信機会マップを作成することに よって前記速度委託構成部分のスケジューリングを行うコンピュータ読取可能プ ログラム・コード手段；および 前記マップ内の未使用送信機会を、所定の方法により前記速度可変構成部分に 割り当てることによって、前記速度可変構成部分のスケジューリングを行うコン ピュータ読取可能プログラム・コード手段； によって構成されることを特徴とする装置。 ８．搬送波内に具現化されるコンピュータ・データ信号であって、通信ネット ワークにおいて送信機会をスケジューリングするコンピュータ読取可能プログラ ム・コード手段が前記コンピュータ・データ信号内に具現され、前記コンピュー タ読取可能プログラム・コード手段が： 複数のスケジューリング・ジョブの各々を一定の時間量内に所定数の送信機会 を必要とする速度委託構成部分と前記一定の時間量内に不定数の送信機会を必要 とする速度可変構成部分とに分類するコンピュータ読取可能プログラムコード手 段； 所定の周期的間隔で反復されると、その所定の遅延およびジター制約内で必要 数の送信機会を各速度委託構成部分に提供する送信機会マップを作成することに よって前記速度委託構成部分のスケジューリングを行うコンピュータ読取可能プ ログラム・コード手段；および 前記マップ内の未使用送信機会を、所定の方法により前記速度可変構成部分に 割り当てることによって、前記速度可変構成部分のスケジューリングを行うコン ピュータ読取可能プログラム・コード手段； によって構成されることを特徴とするコンピュータ・データ信号。 ９．通信ネットワーク内で送信機会をスケジューリングするスケジューラであ って： 複数のスケジューリング・ジョブの各々を一定の時間量 内に所定数の送信機会を必要とする速度委託ジョブと前記一定の時間量内に不定 数の送信機会を必要とする速度可変ジョブとに分類する論理を含む分類論理； 前記分類論理に動作可能に結合される速度委託構成部分スケジューラであって 、前記速度委託構成部分スケジューラは、所定の周期的間隔で反復されると、そ の所定の遅延およびジター制約内で必要数の送信機会を各速度委託ジョブに提供 する送信機会マップを作成する論理を含むマッパによって構成される速度委託構 成部分スケジューラ；および 前記分類論理に動作可能に結合され、前記速度可変ジョブの優先度を決定する 論理を含む優先度決定装置によって構成される速度委託構成部分スケジューラ； によって構成されることを特徴とするスケジューラ。 １０．共有媒体を介してアクセス・インタフェース・ユニットと通信を行うヘ ッドエンド・ユニットであって、送信機会をスケジューリングするスケジューラ を有し、前記スケジューラが： 複数のスケジューリング・ジョブの各々を一定の時間量内に所定数の送信機会 を必要とする速度委託ジョブと前記一定の時間量内に不定数の送信機会を必要と する速度可変ジョブとに分類する論理を含む分類論理； 前記分類論理に動作可能に結合される速度委託構成部分スケジューラであって 、所定の周期的間隔で反復されると、 その所定の遅延およびジター制約内で必要数の送信機会を各速度委託ジョブに提 供する送信機会マップを作成する論理を含むマッパによって構成される前記速度 委託構成部分スケジューラ；および 前記分類論理に動作可能に結合され、前記速度可変ジョブの優先度を決定する 論理を含む優先度決定装置によって構成される速度委託構成部分スケジューラ； によって構成されることを特徴とするシステム。[Claims]   1. A complex generated by a group of users distributed in a shared media communication network In a way to schedule transmission opportunities for a number of scheduling jobs There, transmission opportunities are reserved via the central controller, and the method includes:   Each of a plurality of scheduling jobs is assigned a predetermined number of transmission opportunities within a certain amount of time. And a variable number of transmission opportunities within the fixed amount of time. Classifying the required speed variable components;   Repeated at a given periodic interval, required within its given delay and jitter constraints To create a transmission opportunity map that provides a number of transmission opportunities to each rate commissioning component Thus scheduling said rate commissioning component; and   Unused transmission opportunities in the map are sent to the variable speed component by a predetermined method. Scheduling the variable speed component by assigning ;   A method characterized by comprising:   2. Scheduling the rate commissioning component;   A speed commissioning component that requires delay and jitter constraints Categorizing into speed commissioning components that do not require delay and jitter constraints;   Require delay and jitter constraints based on bandwidth requirements Determining the priority of said rate commissioning component;   The rate commissioning configuration that does not require delay and jitter constraints based on bandwidth requirements Determining the priority of the part;   The speed consignment components requiring delay and jitter constraints are preceded by priority. Assigning in the map; and   Subsequently, the rate commissioning component that does not require delay and jitter constraints is given priority. Assigning in the map in order of degree;   It is characterized by comprising   The step of scheduling the variable speed component comprises:   Weighting the variable speed component into unused slots in the map Allocating using a scheduling rule, wherein the weighted round table The weights used in the juling are ATM service category, queuing depth and And is a function of other relevant characteristics of the variable speed component and varies with time. The method of claim 1, wherein:   3. The steps of classifying and scheduling include:   Each continuous bit rate scheduling job requires delay and jitter constraints Of each continuous bit rate scheduling The transmission opportunity for the rate commissioning component of the Scheduling at a predetermined peak cell rate within jitter and jitter constraints;   Delay and jitter each real-time variable bit rate scheduling job Classifying only those velocity commissioning components that require constraints; and     The rate commissioning scheme for each real-time variable bit rate scheduling job The transmission opportunity for the component within a given peak and within a given delay and jitter constraint. Scheduling at the cell rate;     The rate commissioning scheme for each real-time variable bit rate scheduling job The transmission opportunity for the component, if the rate commissioning component is active, At a given peak cell rate within a given delay and jitter constraint, and Schedule at zero rate if commission component is inactive Floor; and     The rate commissioning scheme for each real-time variable bit rate scheduling job The transmission opportunity for the component, if the rate commissioning component is active, At a given peak cell rate within a given delay and jitter constraint, and At lower (non-zero) speeds if the commissioning component is inactive Scheduling;     A stage consisting of one of the following:   Non-real-time variable bit rate scheduling jobs with delay and jitter -Speed commissioning configuration that does not require restrictions Classification into non-real-time variable bit rate schedules The transmission opportunity for the rate commissioning component of the Scheduling at possible cell rates and based on the dwell of data to be transmitted When additional transmission opportunities beyond that predetermined sustainable cell rate are needed However, each non-real-time variable bit rate scheduling job Scheduling transmission opportunities for the variant;   Delay and jitter constraints on each of the available bit rate scheduling jobs Are classified into speed consignment components that do not require Transmitter for each of said rate commissioning components of a speed scheduling job The session is scheduled at its predetermined minimum cell rate and the available bits Transmission Opportunities for Each of the Variable Speed Components of a Speed Scheduling Job Scheduling to a predetermined peak cell rate   Classify each unspecified bit rate scheduling job into variable rate components only And each unspecified bit rate scheduler whenever a transmission opportunity is available. Scheduling a transmission opportunity for the variable speed component of a logging job Floor; and   Each entry poll scheduling job is And variable speed components, and the entry polling schedule Job Scheduling transmission opportunities for the rate commissioning component at regular intervals, Whenever an opportunity is available, the entry polling schedule Scheduling transmission opportunities for the variable speed component of a scheduling job Stage;   3. The method according to claim 2, comprising:   4. Each speed commission component has a transmission period, and the map has a different speed commission configuration A predetermined number of slots at least equal to the least common multiple of said transmission period for the part The method of claim 1, wherein the method comprises:   5. The map is composed of a plurality of task frames of a predetermined size, Jobs are allocated more than one slot per task frame Unused slots are allocated to variable speed components one task frame at a time 5. The method of claim 4, wherein the method is performed.   6. Generating an entry poll message including an allocation of transmission opportunities; Wherein the map comprises a plurality of task frames and the The steps of generating a re-pol message include:   One of the number of task frames in the entry poll message Providing one; and   Unused transmission opportunities in the task frame are variable according to a predetermined method. Assigning to components;   The method of claim 1, wherein the method comprises:   7. A computer readable program code stored on a computer usable medium. And a shared medium communication network. On Multiple Scheduling Jobs Generated by a Population of Users A device for scheduling transmission opportunities, wherein transmission opportunities are provided to a central controller. Wherein the computer readable program code means is:   A certain number of transmission opportunities within a certain amount of time for each of multiple scheduling jobs Requires a speed consignment component and an infinite number of transmission opportunities within the certain amount of time Computer readable program code classified as variable speed components means;   Repeated at a given periodic interval, required within its given delay and jitter constraints To create a transmission opportunity map that provides a number of transmission opportunities to each rate commissioning component Thus, a computer readable program that schedules the speed commissioning component. Program code means; and   Unused transmission opportunities in the map are sent to the variable speed component by a predetermined method. By assigning, a component for scheduling the variable speed component is Computer readable program code means;   An apparatus characterized by comprising:   8. A computer data signal embodied in a carrier, comprising: a communication network; Computer-readable program for scheduling transmission opportunities in a work Computer code means embodied in the computer data signal, Data readable program code means:   A certain number of transmission opportunities within a certain amount of time for each of multiple scheduling jobs Requires a speed consignment component and an infinite number of transmission opportunities within the certain amount of time Computer readable program code classified as speed variable components Step;   Repeated at a given periodic interval, required within its given delay and jitter constraints To create a transmission opportunity map that provides a number of transmission opportunities to each rate commissioning component Thus, a computer readable program that schedules the speed commissioning component. Program code means; and   Unused transmission opportunities in the map are sent to the variable speed component by a predetermined method. By assigning, a component for scheduling the variable speed component is Computer readable program code means;   A computer data signal comprising:   9. A scheduler that schedules transmission opportunities in a communication network. What:   A fixed amount of time for each of multiple scheduling jobs A speed commission job that requires a predetermined number of transmission opportunities within Classification logic including logic for classifying into variable speed jobs requiring a number of transmission opportunities;   A rate commissioning component scheduler operatively coupled to said classification logic, The rate commit component scheduler, when repeated at predetermined periodic intervals, Provide the required number of transmission opportunities to each rate commission job within the specified delay and jitter constraints Rate consignment scheme configured by a mapper that includes logic to create a transmission opportunity map Component scheduler; and   Operablely coupled to the classification logic to determine a priority of the variable speed job Speed commissioning component scheduler configured by a priority determining device including logic;   A scheduler comprising:   10. To communicate with the access interface unit via a shared medium Scheduler for scheduling transmission opportunities Wherein the scheduler comprises:   A certain number of transmission opportunities within a certain amount of time for each of multiple scheduling jobs Requires a speed commissioned job and an infinite number of transmission opportunities within the certain amount of time Classification logic including logic for classifying the variable speed job to be performed;   A rate commissioning component scheduler operatively coupled to said classification logic, , Repeated at predetermined periodic intervals, Provide the required number of transmission opportunities to each speed commission job within its predetermined delay and jitter constraints. Said speed constituted by a mapper including logic for creating a transmission opportunity map to serve Delegated component scheduler; and   Operablely coupled to the classification logic to determine a priority of the variable speed job A speed commissioning component scheduler configured by a priority determining device including logic;   A system characterized by comprising:
JP51318499A 1997-08-14 1998-07-17 System, apparatus and method for performing scheduling in a communication network Pending JP2001504316A (en)

Applications Claiming Priority (5)

Application Number Priority Date Filing Date Title
US5565897P 1997-08-14 1997-08-14
US6198898A 1998-04-17 1998-04-17
US09/061,988 1998-04-17
US60/055,658 1998-04-17
PCT/US1998/014893 WO1999009689A1 (en) 1997-08-14 1998-07-17 System, device, and method for scheduling in a communication network

Publications (1)

Publication Number Publication Date
JP2001504316A true JP2001504316A (en) 2001-03-27

Family

ID=26734492

Family Applications (1)

Application Number Title Priority Date Filing Date
JP51318499A Pending JP2001504316A (en) 1997-08-14 1998-07-17 System, apparatus and method for performing scheduling in a communication network

Country Status (6)

Country Link
JP (1) JP2001504316A (en)
AU (1) AU8496698A (en)
CA (1) CA2268784A1 (en)
DE (1) DE19881333T1 (en)
GB (1) GB2332601A (en)
WO (1) WO1999009689A1 (en)

Families Citing this family (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6434141B1 (en) 1999-05-26 2002-08-13 Bigband Networks, Inc. Communication management system and method
US6501758B1 (en) 1999-06-03 2002-12-31 Fujitsu Network Communications, Inc. Hybrid ATM/TDM transport over a common fiber ring
AU5461600A (en) 1999-06-03 2000-12-28 Fujitsu Network Communications, Inc. Method and system for transmitting traffic in a virtual tunnel of a transmission line
US6665301B1 (en) * 1999-06-03 2003-12-16 Fujitsu Network Communications, Inc. Transmission slot allocation method and map for virtual tunnels in a transmission line
US6760332B1 (en) 1999-06-03 2004-07-06 Fujitsu Network Communications, Inc. ATM multicasting system and method
US6658006B1 (en) 1999-06-03 2003-12-02 Fujitsu Network Communications, Inc. System and method for communicating data using modified header bits to identify a port
US6785285B1 (en) 1999-06-03 2004-08-31 Fujitsu Network Communications, Inc. Method and system for providing broadcast channels over an emulated subnetwork
DE19930228B4 (en) * 1999-06-30 2005-12-08 Siemens Ag Method, communication arrangement and control unit for adapting transmission resources between a central and a plurality of decentralized communication devices
WO2001010084A1 (en) 1999-08-02 2001-02-08 Fujitsu Limited Communication apparatus
FR2806577B1 (en) * 2000-03-16 2002-10-11 Cit Alcatel TELECOMMUNICATION SYSTEM IN WHICH EACH TERMINAL HAS MULTIPLE CONNECTIONS
US8898340B2 (en) 2000-04-17 2014-11-25 Circadence Corporation Dynamic network link acceleration for network including wireless communication devices
AU2001255441A1 (en) 2000-04-17 2001-10-30 Circadence Corporation System and method for implementing application -independent functionality within a network infrastructure
US20110128972A1 (en) 2000-04-17 2011-06-02 Randy Thornton Peer to peer dynamic network link acceleration
US8996705B2 (en) 2000-04-17 2015-03-31 Circadence Corporation Optimization of enhanced network links
US8195823B2 (en) 2000-04-17 2012-06-05 Circadence Corporation Dynamic network link acceleration
US8065399B2 (en) 2000-04-17 2011-11-22 Circadence Corporation Automated network infrastructure test and diagnostic system and method therefor
DE10102110A1 (en) * 2001-01-18 2002-08-14 Marconi Comm Gmbh Method for bidirectional signal transmission in a distributed network
US7411966B2 (en) 2001-03-16 2008-08-12 Siemens Aktiengesellschaft Method and system for coupling data networks
US7822060B2 (en) * 2004-07-14 2010-10-26 Coppergate Communications Ltd. Maximal resource utilization in networks
WO2006063307A2 (en) * 2004-12-10 2006-06-15 Broadcom Corporation Upstream channel bonding in a cable communications system
US7151782B1 (en) 2005-08-09 2006-12-19 Bigband Networks, Inc. Method and system for providing multiple services to end-users
US20250016558A1 (en) * 2022-01-21 2025-01-09 Qualcomm Incorporated Reference signal security

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
DE3788649T2 (en) * 1987-10-20 1994-06-23 Ibm Fast modular switching facility for through-traffic and packet-switched traffic.
US5390184A (en) * 1993-09-30 1995-02-14 Northern Telecom Limited Flexible scheduling mechanism for ATM switches
US5392280A (en) * 1994-04-07 1995-02-21 Mitsubishi Electric Research Laboratories, Inc. Data transmission system and scheduling protocol for connection-oriented packet or cell switching networks

Also Published As

Publication number Publication date
GB2332601A (en) 1999-06-23
AU8496698A (en) 1999-03-08
WO1999009689A1 (en) 1999-02-25
CA2268784A1 (en) 1999-02-25
GB9907893D0 (en) 1999-06-02
DE19881333T1 (en) 1999-09-30

Similar Documents

Publication Publication Date Title
JP2001504316A (en) System, apparatus and method for performing scheduling in a communication network
US5615212A (en) Method, device and router for providing a contention-based reservation mechanism within a mini-slotted dynamic entry polling slot supporting multiple service classes
JP4354711B2 (en) Delay minimization system with guaranteed bandwidth delivery for real-time traffic
US5970062A (en) Method and apparatus for providing wireless access to an ATM network
EP1402689B1 (en) Method and apparatus for providing communications bandwidth to users having a committed data rate based on priority assignment
US6141336A (en) Traffic scheduling method, system and article of manufacture for a wireless access to an asynchronous transfer mode network
US8627320B2 (en) Systems and methods for scheduling applications
EP2585940B1 (en) Node-based quality-of-service management
US20040156367A1 (en) Hierarchically distributed scheduling apparatus and method
US20020095684A1 (en) Methods, systems and computer program products for bandwidth allocation based on throughput guarantees
EP1257514B1 (en) System and method for combining data bandwidth requests by a data provider for transmission of data over an asynchronous communication medium
WO2010096726A1 (en) Flexible reservation request and scheduling mechanisms in a managed shared network with quality of service
EP1214801A1 (en) Method and device for bandwidth allocation in multiple access protocols with contention-based reservation
WO1998054858A1 (en) System, device, and method for sharing contention mini-slots among multiple priority classes
US7106744B2 (en) System and method for a guaranteed delay jitter bound when scheduling bandwidth grants for voice calls via cable network
JP3725724B2 (en) ATM cell multiplexing apparatus and ATM cell multiplexing method
US7822060B2 (en) Maximal resource utilization in networks
JP4335481B2 (en) Adaptive cell scheduling algorithm for wireless asynchronous transmission mode (ATM) systems
US5909444A (en) System, device, and method for aggregating users in a shared-medium network
CN1196145A (en) Device, router, method and system for providing hybrid multiple access protocol for users with multiple priorities
AU743272B2 (en) Offered load estimation and applications for using same in a communication network
KR100503417B1 (en) QoS guaranteed scheduling system in ethernet passive optical networks and method thereof
CA2268794A1 (en) System, device, and method for scheduling variable bit rate traffic in a communication network
Zhenglin et al. An analytical model for the performance of the DOCSIS CATV network
KR20010073656A (en) Poll-based wireless burst scheduling Method in wireless communication System