JPH11234309A - 非同期転送モード・セル送信スケジューリング - Google Patents
非同期転送モード・セル送信スケジューリングInfo
- Publication number
- JPH11234309A JPH11234309A JP33072298A JP33072298A JPH11234309A JP H11234309 A JPH11234309 A JP H11234309A JP 33072298 A JP33072298 A JP 33072298A JP 33072298 A JP33072298 A JP 33072298A JP H11234309 A JPH11234309 A JP H11234309A
- Authority
- JP
- Japan
- Prior art keywords
- channel
- time stamp
- value
- time
- transmission
- 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
Links
Classifications
-
- 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
- H04L12/5602—Bandwidth control in ATM Networks, e.g. leaky bucket
-
- 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/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)
- Communication Control (AREA)
Abstract
(57)【要約】
【目的】 非同期転送モード（ＡＴＭ）データ通信にお
いて、ＡＴＭセル送信を公平にスケジュールする。 【構成】 ネットワーク・ハブおよびＡＴＭトランスレ
ータ・システム５は、トランスレータ・カード１５とイ
ンターフェースするホスト・コントローラ１０を備え
る。トランスレータ・カード１５のＳＡＲデバイス１２
は、トランシーバ２２と通信するＳＯＮＥＴ送受信回路
２０と接続され、通信設備ＦＯを介してＡＴＭパケット
・セルを送受信する。スケジューラ１４は、ソートされ
たエントリのリストをオンチップ・パラメータ・メモリ
とオフチップ・パラメータ・メモリ１８にヒープ状に保
持するヒープ・ソート状態マシンを備える。スケジュー
ラ１４は、そのセルに対して発行した送信クレジットを
ＳＡＲデバイス１２に知らせ、送信させる。
いて、ＡＴＭセル送信を公平にスケジュールする。 【構成】 ネットワーク・ハブおよびＡＴＭトランスレ
ータ・システム５は、トランスレータ・カード１５とイ
ンターフェースするホスト・コントローラ１０を備え
る。トランスレータ・カード１５のＳＡＲデバイス１２
は、トランシーバ２２と通信するＳＯＮＥＴ送受信回路
２０と接続され、通信設備ＦＯを介してＡＴＭパケット
・セルを送受信する。スケジューラ１４は、ソートされ
たエントリのリストをオンチップ・パラメータ・メモリ
とオフチップ・パラメータ・メモリ１８にヒープ状に保
持するヒープ・ソート状態マシンを備える。スケジュー
ラ１４は、そのセルに対して発行した送信クレジットを
ＳＡＲデバイス１２に知らせ、送信させる。
Description
【０００１】
【発明の属する技術分野】本発明は、データ通信分野に
関し、特に、非同期転送モード（ＡＴＭ）データ通信に
関する。
関し、特に、非同期転送モード（ＡＴＭ）データ通信に
関する。
【０００２】
【従来の技術および発明が解決しようとする課題】デジ
タル通信の分野、音声，ビデオまたはデータの通信の分
野において、ネットワークを介して接続されたノードま
たはプロセッサ間でメッセージをやり取りするための様
々な通信技術が開発されている。そのための１つのアプ
ローチとして、パケット・スイッチングがある。そこで
は、いくつかのネットワーク・ノードが集信装置として
動作して、パケットとなっているメッセージのある部分
を送信ユニットから受け取る。これらのパケットは、集
信装置で格納され、パケット・アドレスによって指定さ
れた受信ユニットが結合された指定集信装置へ送り出さ
れる。パケットのサイズは、集信装置間で（つまり、店
および行き先ノード間で）通信可能な情報の上限に相当
し、典型的には、メッセージまたはファイル１つ分であ
る。各パケットは、ソース・ネットワーク・アドレスお
よび指定ネットワーク・アドレスに関するヘッダ情報を
含み、これにより、メッセージ・パケットの適切なルー
ティングができる。パケット・スイッチングを行うこと
により、長い個々のメッセージによってルーティング・
パスが不当に塞がることを避けることができるので、店
−行き先・ノードにおける送信遅延を減らすことにな
る。高速パケット・スイッチングは、１秒間に数百メガ
ビット以上の高速データ速度で動作するパケット・スイ
ッチング技術を指す。
タル通信の分野、音声，ビデオまたはデータの通信の分
野において、ネットワークを介して接続されたノードま
たはプロセッサ間でメッセージをやり取りするための様
々な通信技術が開発されている。そのための１つのアプ
ローチとして、パケット・スイッチングがある。そこで
は、いくつかのネットワーク・ノードが集信装置として
動作して、パケットとなっているメッセージのある部分
を送信ユニットから受け取る。これらのパケットは、集
信装置で格納され、パケット・アドレスによって指定さ
れた受信ユニットが結合された指定集信装置へ送り出さ
れる。パケットのサイズは、集信装置間で（つまり、店
および行き先ノード間で）通信可能な情報の上限に相当
し、典型的には、メッセージまたはファイル１つ分であ
る。各パケットは、ソース・ネットワーク・アドレスお
よび指定ネットワーク・アドレスに関するヘッダ情報を
含み、これにより、メッセージ・パケットの適切なルー
ティングができる。パケット・スイッチングを行うこと
により、長い個々のメッセージによってルーティング・
パスが不当に塞がることを避けることができるので、店
−行き先・ノードにおける送信遅延を減らすことにな
る。高速パケット・スイッチングは、１秒間に数百メガ
ビット以上の高速データ速度で動作するパケット・スイ
ッチング技術を指す。
【０００３】高速パケット・スイッチング・プロトコル
の公知例は、パケット・スイッチングの能力を回路スイ
ッチングの予測と結びつけたもので、非同期転送モード
（一般には、「ＡＴＭ」と呼ばれる。）であり、ここで
は、メッセージ長やデータ種類（すなわち、音声，デー
タまたはビデオ）に関係なく、パケット長および組織化
が固定されている。ＡＴＭプロトコルによる固定パケッ
トは「セル」と呼ばれ、各ＡＴＭセルは５３バイトから
なり、そのうち５バイトがヘッダに使われ、残りの４８
バイトがペイロードになる。このプロトコルによれば、
大きなパケットは、多数の固定長ＡＴＭセルからなる。
固定長セル・フォーマットにより、ＡＴＭセル・スイッ
チングは、ソフトウェアに対するハードウェアに導入さ
れ、その結果、１秒に数ギガバイトという範囲の送信速
度になる。さらに、パケットではなくセルを切り換える
ことによって、ネットワークに対してスケーラブル・ユ
ーザ・アクセスが可能となり、アプリケーションにより
数メガｂｐｓから数ギガｂｐｓまで対応できる。非同期
送信であるため、ＡＴＭセルを使用して、遅延可能（de
lay-tolerant）データ・トラフィックを、音声やビデオ
のような時間厳守（time-sensitive）トラフィックと混
ぜて、同じバックボーン機能を使って送信することがで
きる。これらの様々のアプリケーションをより効率良く
利用するために、現在では、時間厳守トラフィックを遅
延可能トラフィックに優先させるトラフィック管理技術
が使用されている。
の公知例は、パケット・スイッチングの能力を回路スイ
ッチングの予測と結びつけたもので、非同期転送モード
（一般には、「ＡＴＭ」と呼ばれる。）であり、ここで
は、メッセージ長やデータ種類（すなわち、音声，デー
タまたはビデオ）に関係なく、パケット長および組織化
が固定されている。ＡＴＭプロトコルによる固定パケッ
トは「セル」と呼ばれ、各ＡＴＭセルは５３バイトから
なり、そのうち５バイトがヘッダに使われ、残りの４８
バイトがペイロードになる。このプロトコルによれば、
大きなパケットは、多数の固定長ＡＴＭセルからなる。
固定長セル・フォーマットにより、ＡＴＭセル・スイッ
チングは、ソフトウェアに対するハードウェアに導入さ
れ、その結果、１秒に数ギガバイトという範囲の送信速
度になる。さらに、パケットではなくセルを切り換える
ことによって、ネットワークに対してスケーラブル・ユ
ーザ・アクセスが可能となり、アプリケーションにより
数メガｂｐｓから数ギガｂｐｓまで対応できる。非同期
送信であるため、ＡＴＭセルを使用して、遅延可能（de
lay-tolerant）データ・トラフィックを、音声やビデオ
のような時間厳守（time-sensitive）トラフィックと混
ぜて、同じバックボーン機能を使って送信することがで
きる。これらの様々のアプリケーションをより効率良く
利用するために、現在では、時間厳守トラフィックを遅
延可能トラフィックに優先させるトラフィック管理技術
が使用されている。
【０００４】最近、ＡＴＭデータ通信で使用するための
閉ループ・トラフィック管理方式が開発された。閉ルー
プ・トラフィク管理は、２つのネットワーク・ノード間
でフィードバック信号を使用して、チャンネルのデータ
・レートを支配し、帯域幅利用の効率を改善することを
目的とする。この効率改善が特に必要となるのは、リア
ルタイム音声／ビデオ情報の通信が含まれる場合であ
る。これらのチャンネルの時間厳守が、大きなバースト
の時間に影響されないデータの送信によって乱されるこ
とがあるからである。
閉ループ・トラフィック管理方式が開発された。閉ルー
プ・トラフィク管理は、２つのネットワーク・ノード間
でフィードバック信号を使用して、チャンネルのデータ
・レートを支配し、帯域幅利用の効率を改善することを
目的とする。この効率改善が特に必要となるのは、リア
ルタイム音声／ビデオ情報の通信が含まれる場合であ
る。これらのチャンネルの時間厳守が、大きなバースト
の時間に影響されないデータの送信によって乱されるこ
とがあるからである。
【０００５】現在のトラフィック管理方式は、様々な送
信カテゴリーを利用して、ＡＴＭ通信に帯域幅を割り当
てる。優先順位が上位にあるカテゴリーの１つに、定ビ
ット・レート（ＣＢＲ）があり、ここでは、送信が一定
速度で行われる。可変ビット・レート（ＶＢＲ）送信に
は２つのカテゴリーがあり、１つはリアルタイム・デー
タ、もう１つは非リアルタイム・データである。優先順
位が低いカテゴリーには、非スケジュール・ビット・レ
ート（Unscheduled Bit Rate：ＵＢＲ）があり、ここで
は、送信速度の保証なしに、ソースによってデータが送
信される。
信カテゴリーを利用して、ＡＴＭ通信に帯域幅を割り当
てる。優先順位が上位にあるカテゴリーの１つに、定ビ
ット・レート（ＣＢＲ）があり、ここでは、送信が一定
速度で行われる。可変ビット・レート（ＶＢＲ）送信に
は２つのカテゴリーがあり、１つはリアルタイム・デー
タ、もう１つは非リアルタイム・データである。優先順
位が低いカテゴリーには、非スケジュール・ビット・レ
ート（Unscheduled Bit Rate：ＵＢＲ）があり、ここで
は、送信速度の保証なしに、ソースによってデータが送
信される。
【０００６】相対的に新しいトラフィック管理カテゴリ
ーは、アベイラブル・ビット・レート（ＡＢＲ）と呼ば
れる。このカテゴリーでは、受信側ネットワーク・ノー
ドからのフィードバックは、リソース管理（ＲＭ）セル
を介してまたはデータ・セル内での明示フロー制御指示
によって、ソース・ネットワーク・ノードにより使用さ
れて、現在のネットワーク条件に応じてその送信レート
を動的に制御する。この制御は、送信チャンネルを開設
するときに指定されるいくつかの送信パラメータ内で行
われる。典型的には、ソース・ノードと指定ノードと
が、ピーク・セル・レート（ＰＣＲ）および最小セル・
レート（ＭＣＲ）について折り合いをつけ、ＡＢＲ通信
用送信の上限および下限を設定する。これらの上下限が
設定されると、フロー制御アルゴリズムが行われる。こ
れは、典型的には、指定ノードで行われ、各チャンネル
について所望の送信レートを画定する。当業者には公知
のように、所与の２つのネットワーク・ノードの間に
は、数千もの接続が同時に開設される。これに応じて、
トラフィック管理もかなり複雑な操作であり、特に、Ａ
ＢＲカテゴリー通信の制御は複雑である。
ーは、アベイラブル・ビット・レート（ＡＢＲ）と呼ば
れる。このカテゴリーでは、受信側ネットワーク・ノー
ドからのフィードバックは、リソース管理（ＲＭ）セル
を介してまたはデータ・セル内での明示フロー制御指示
によって、ソース・ネットワーク・ノードにより使用さ
れて、現在のネットワーク条件に応じてその送信レート
を動的に制御する。この制御は、送信チャンネルを開設
するときに指定されるいくつかの送信パラメータ内で行
われる。典型的には、ソース・ノードと指定ノードと
が、ピーク・セル・レート（ＰＣＲ）および最小セル・
レート（ＭＣＲ）について折り合いをつけ、ＡＢＲ通信
用送信の上限および下限を設定する。これらの上下限が
設定されると、フロー制御アルゴリズムが行われる。こ
れは、典型的には、指定ノードで行われ、各チャンネル
について所望の送信レートを画定する。当業者には公知
のように、所与の２つのネットワーク・ノードの間に
は、数千もの接続が同時に開設される。これに応じて、
トラフィック管理もかなり複雑な操作であり、特に、Ａ
ＢＲカテゴリー通信の制御は複雑である。
【０００７】ソース・ネットワーク・ノードでは、分節
化および再構築（ＳＡＲ）デバイス若しくは操作が使用
されて、フロー制御アルゴリズムによって設定された所
望のビットレートに応じて、ＡＴＭセルが準備され送信
される。従来のＳＡＲデバイスがしばしば含む「トラフ
ィク・シェイパ」機能は、「穴の開いたバケツ」として
知られている。というのは、バーストの間に手早くセル
・データを満たすけれど、ネットワークに対して確実に
データを「漏らす」または送信するバッファを備えるか
らである。このようなバッファからの送信のスケジュー
ル管理は、扱うチャンネル数が増えるにつれて急激に複
雑になり、特に、ＡＢＲ通信が含まれる場合は複雑にな
る。
化および再構築（ＳＡＲ）デバイス若しくは操作が使用
されて、フロー制御アルゴリズムによって設定された所
望のビットレートに応じて、ＡＴＭセルが準備され送信
される。従来のＳＡＲデバイスがしばしば含む「トラフ
ィク・シェイパ」機能は、「穴の開いたバケツ」として
知られている。というのは、バーストの間に手早くセル
・データを満たすけれど、ネットワークに対して確実に
データを「漏らす」または送信するバッファを備えるか
らである。このようなバッファからの送信のスケジュー
ル管理は、扱うチャンネル数が増えるにつれて急激に複
雑になり、特に、ＡＢＲ通信が含まれる場合は複雑にな
る。
【０００８】穴の開いたバケツに代わるアプローチとし
て、いくつかの従来のソース・ノードＳＡＲデバイスの
導入には、多数のチャンネル間でのＡＴＭセルのスケジ
ュールを扱うプログラムがなされた高性能マイクロプロ
セッサが使用されることがある。ただし、そのようなマ
イクロプロセッサの使用は、典型的には、ＲＩＳＣコプ
ロセッサとしてであるが、これは、非常に本質的なもの
であり、特に、プログラムの記憶，送信データのキャッ
シュ化およびバス・インターフェース機能の提供に必要
な外部メモリの実質的量を考えると、非常に本質的なも
のである。たとえば、２０４８個のチャンネルの各々に
多数の送信セルを記憶するバッファを提供し、各チャン
ネルが、そのチャンネルの最後の送信からいくつの周期
が経過したかをカウントするカウンタ（これにより、次
のセルがいつ送信できるかを決める。）を装備するとな
ると、この機能のために非常に大きなメモリ・リソース
が必要となる。
て、いくつかの従来のソース・ノードＳＡＲデバイスの
導入には、多数のチャンネル間でのＡＴＭセルのスケジ
ュールを扱うプログラムがなされた高性能マイクロプロ
セッサが使用されることがある。ただし、そのようなマ
イクロプロセッサの使用は、典型的には、ＲＩＳＣコプ
ロセッサとしてであるが、これは、非常に本質的なもの
であり、特に、プログラムの記憶，送信データのキャッ
シュ化およびバス・インターフェース機能の提供に必要
な外部メモリの実質的量を考えると、非常に本質的なも
のである。たとえば、２０４８個のチャンネルの各々に
多数の送信セルを記憶するバッファを提供し、各チャン
ネルが、そのチャンネルの最後の送信からいくつの周期
が経過したかをカウントするカウンタ（これにより、次
のセルがいつ送信できるかを決める。）を装備するとな
ると、この機能のために非常に大きなメモリ・リソース
が必要となる。
【０００９】上述した状況を鑑みて、本発明は、アベイ
ラブル・ビット・レート（ＡＢＲ）非同期転送モード
（ＡＴＭ）送信に有効なスケジューリング機能を提供す
ることを目的とする。
ラブル・ビット・レート（ＡＢＲ）非同期転送モード
（ＡＴＭ）送信に有効なスケジューリング機能を提供す
ることを目的とする。
【００１０】また、本発明は、穏やかなメモリ要件で導
入することのできるスケジューリング機能を提供するこ
とを目的とする。
入することのできるスケジューリング機能を提供するこ
とを目的とする。
【００１１】本発明のその他の目的および利点は、以下
の明細書および添付図面を参照することにより、当業者
にとって明らかとなるであろう。
の明細書および添付図面を参照することにより、当業者
にとって明らかとなるであろう。
【００１２】
【課題を解決するための手段】本発明は、ローカル・エ
リア・ネットワーク（ＬＡＮ）からＡＴＭ通信へのメッ
セージをやりとりするための転送システムに導入するこ
とができる。この転送システムは、ＡＢＲスケジューリ
ング機能と組み合わされて動作する分節化および再構築
（ＳＡＲ）機能を備える。ＡＢＲスケジューラは、ヒー
プ（積み上げ）データ構造を維持する回路を備え、そこ
では、各エントリーがタイム・スタンプと関連するチャ
ンネル識別子を含む。タイム・スタンプとは、当該関連
チャンネルに対するセルが送信される次の時刻を示すタ
イマー値である。ヒープ・ソートは、ヒープ・データ構
造内のルート・エレメントが次に送信予定のセルと対応
するように行われる。本発明の一態様によれば、ヒープ
・データ構造は、オンチップ・メモリ・リソースおよび
外部メモリに記憶することができ、そこでは、最新のヒ
ープ・ソート結果がオンチップ記憶される。
リア・ネットワーク（ＬＡＮ）からＡＴＭ通信へのメッ
セージをやりとりするための転送システムに導入するこ
とができる。この転送システムは、ＡＢＲスケジューリ
ング機能と組み合わされて動作する分節化および再構築
（ＳＡＲ）機能を備える。ＡＢＲスケジューラは、ヒー
プ（積み上げ）データ構造を維持する回路を備え、そこ
では、各エントリーがタイム・スタンプと関連するチャ
ンネル識別子を含む。タイム・スタンプとは、当該関連
チャンネルに対するセルが送信される次の時刻を示すタ
イマー値である。ヒープ・ソートは、ヒープ・データ構
造内のルート・エレメントが次に送信予定のセルと対応
するように行われる。本発明の一態様によれば、ヒープ
・データ構造は、オンチップ・メモリ・リソースおよび
外部メモリに記憶することができ、そこでは、最新のヒ
ープ・ソート結果がオンチップ記憶される。
【００１３】
【発明の実施の形態】図１は、本発明を実施することの
できる通信システムの一例を示すもので、これを参照し
て説明を行う。図１の例は、以下の説明から明らかにな
るように、ＬＡＮにおけるコンピュータのようなデータ
処理装置が他のデータ処理装置と非同期転送モード（Ａ
ＴＭ）で通信を行う方法に関する。他のデータ処理装置
は、それ自体が別のＬＡＮにあるコンピュータ，スタン
ド・アロン型のコンピュータまたは所望の通信を行いた
い他のシステムであってもよい。当業者にとっては明ら
かなように、本発明は、図１に示されたのとは異なるア
ーキテクチャの通信システムにも実施することができ、
図１のシステムは一例にすぎない。その他の実施も、本
発明の範囲に入るものと考えられる。
できる通信システムの一例を示すもので、これを参照し
て説明を行う。図１の例は、以下の説明から明らかにな
るように、ＬＡＮにおけるコンピュータのようなデータ
処理装置が他のデータ処理装置と非同期転送モード（Ａ
ＴＭ）で通信を行う方法に関する。他のデータ処理装置
は、それ自体が別のＬＡＮにあるコンピュータ，スタン
ド・アロン型のコンピュータまたは所望の通信を行いた
い他のシステムであってもよい。当業者にとっては明ら
かなように、本発明は、図１に示されたのとは異なるア
ーキテクチャの通信システムにも実施することができ、
図１のシステムは一例にすぎない。その他の実施も、本
発明の範囲に入るものと考えられる。
【００１４】図１に示され通信システムの一例におい
て、ＬＡＮに配設されたコンピュータ２の１つと遠隔地
に配設されたコンピュータ６の１つとの間で通信を行う
とする。この例におけるコンピュタ２は、エーテルネッ
ト（Ethernet）型のＬＡＮに配設され、各コンピュータ
２はネットワーク・ハブおよびＡＴＭトランスレータ５
と通信状態にある。もちろん、コンピュータ２は、トー
クン・リングＬＡＮなど他のＬＡＮに配設されてもかま
わない。エーテルネットＬＡＮにおいては、ネットワー
ク・ハブおよびＡＴＭトランスレータ５の制御下で、２
０４８個の個別の通信チャンネルを設定することができ
る。ネットワーク・ハブおよびＡＴＭトランスレータ５
の構成や動作について以下詳細に説明するが、これは、
ファイバ光設備ＦＯに接続され、コンピュータ２の１つ
およびＬＡＮの外のコンピュータと通信のやり取りを行
うことができる。ファイバ光設備ＦＯは、１つまたは２
つ以上の中央局スイッチ７のネットワークによって受信
され、ネットワークハブおよびＡＴＭトランスレータ５
と通信で指定された目的地との間を接続する。
て、ＬＡＮに配設されたコンピュータ２の１つと遠隔地
に配設されたコンピュータ６の１つとの間で通信を行う
とする。この例におけるコンピュタ２は、エーテルネッ
ト（Ethernet）型のＬＡＮに配設され、各コンピュータ
２はネットワーク・ハブおよびＡＴＭトランスレータ５
と通信状態にある。もちろん、コンピュータ２は、トー
クン・リングＬＡＮなど他のＬＡＮに配設されてもかま
わない。エーテルネットＬＡＮにおいては、ネットワー
ク・ハブおよびＡＴＭトランスレータ５の制御下で、２
０４８個の個別の通信チャンネルを設定することができ
る。ネットワーク・ハブおよびＡＴＭトランスレータ５
の構成や動作について以下詳細に説明するが、これは、
ファイバ光設備ＦＯに接続され、コンピュータ２の１つ
およびＬＡＮの外のコンピュータと通信のやり取りを行
うことができる。ファイバ光設備ＦＯは、１つまたは２
つ以上の中央局スイッチ７のネットワークによって受信
され、ネットワークハブおよびＡＴＭトランスレータ５
と通信で指定された目的地との間を接続する。
【００１５】この例において、コンピュータ６は遠隔地
に配置されている。この例において、遠隔地コンピュー
タ６はそれぞれ、ＡＴＭ構内（premises）スイッチ８に
接続される。ＡＴＭ構内スイッチ８により、ワーク・グ
ループまたは部署におけるコンピュータ６間でのＡＴＭ
通信が可能となる。この例において、ＡＴＭ構内スイッ
チ８は、外部ファイバ光機能ＦＯにも接続され、そのロ
ーカルＡＴＭワーク・グループ内のコンピュータ６はＡ
ＴＭメッセージをそのワーク・グループ外の目的地に通
信することもできる。ＡＴＭ構内スイッチ８は、転送は
行なわず、（ファイバ光機能ＦＯを介してまたはコンピ
ュータ６のワーク・グループ内で）ＡＴＭ通信だけを行
う。あるいはまた、コンピュータ６がＬＡＮにも配設さ
れている場合、ＡＴＭ構内スイッチ８の代わりに、別の
ネットワーク・ハブおよびＡＴＭトランスレータ５を導
入することができる。図１のコンピュータ６の配置は単
なる一例にすぎない。
に配置されている。この例において、遠隔地コンピュー
タ６はそれぞれ、ＡＴＭ構内（premises）スイッチ８に
接続される。ＡＴＭ構内スイッチ８により、ワーク・グ
ループまたは部署におけるコンピュータ６間でのＡＴＭ
通信が可能となる。この例において、ＡＴＭ構内スイッ
チ８は、外部ファイバ光機能ＦＯにも接続され、そのロ
ーカルＡＴＭワーク・グループ内のコンピュータ６はＡ
ＴＭメッセージをそのワーク・グループ外の目的地に通
信することもできる。ＡＴＭ構内スイッチ８は、転送は
行なわず、（ファイバ光機能ＦＯを介してまたはコンピ
ュータ６のワーク・グループ内で）ＡＴＭ通信だけを行
う。あるいはまた、コンピュータ６がＬＡＮにも配設さ
れている場合、ＡＴＭ構内スイッチ８の代わりに、別の
ネットワーク・ハブおよびＡＴＭトランスレータ５を導
入することができる。図１のコンピュータ６の配置は単
なる一例にすぎない。
【００１６】上述したように、ネットワーク・ハブおよ
びＡＴＭトランスレータ５は、エーテルネットＬＡＮを
介してコンピュータ２のインターフェースを行うととも
に、ＡＴＭ通信用のファイバ光機能ＦＯにもインターフ
ェースを行う。このようなネットワーク・ハブおよびＡ
ＴＭトランスレータ５は、そのハブ管理機能に加えて、
エーテルネット・パケットを転送しなければならず、そ
の長さはおよそ１５００バイトになり、ファイバ光機能
ＦＯを介したコンピュータ２からの通信用の固定長ＡＴ
Ｍセルに入れられる。受信の場合は、この逆になる。
びＡＴＭトランスレータ５は、エーテルネットＬＡＮを
介してコンピュータ２のインターフェースを行うととも
に、ＡＴＭ通信用のファイバ光機能ＦＯにもインターフ
ェースを行う。このようなネットワーク・ハブおよびＡ
ＴＭトランスレータ５は、そのハブ管理機能に加えて、
エーテルネット・パケットを転送しなければならず、そ
の長さはおよそ１５００バイトになり、ファイバ光機能
ＦＯを介したコンピュータ２からの通信用の固定長ＡＴ
Ｍセルに入れられる。受信の場合は、この逆になる。
【００１７】次に、図２を参照して、本発明の好ましい
実施の形態によるネットワーク・ハブおよびＡＴＭトラ
ンスレータの構成について説明する。本発明のこの実施
の形態によれば、ネットワーク・ハブおよびＡＴＭトラ
ンスレータ５は、ホスト・コントローラ１０を備える。
ホスト・コントローラ１０は、コンピュータ２からのエ
ーテルネット通信用のエーテルネット・ハブ機能を扱う
ための従来のコンピュータ・ワークステーションであ
り、ホスト・コントローラ１０は、この厳しい性能にお
いて動作する充分な性能をもつものとする。この例にお
いて、ホスト・コントローラ１０は、そのデータ処理機
能とともに、公知のＰＣＩバス規格により動作する高性
能ローカル・バスＰＣＩＢＵＳを備える。ホスト・コン
トローラ１０と組み合わされ、ネットワーク・ハブおよ
びＡＴＭトランスレータ５は、トランスレータ・カード
１５を備える。トランスレータ・カード１５は、図示さ
れているように、ローカル・バスＰＣＩＢＵＳとのイン
ターフェースを行い、かつ、ＬＡＮからＡＴＭへの転送
を行うとともにファイバ光機能ＦＯへのインターフェー
スを行う回路を備える。このように、ホスト・コントロ
ーラ１０は、遠隔目的地向けのコンピュータ２の１つか
らの通信を認識し、これらの通信をローカル・バスＰＣ
ＩＢＵＳを介してトランスレータ・カード１５に送るの
に必要な機能を備える。
実施の形態によるネットワーク・ハブおよびＡＴＭトラ
ンスレータの構成について説明する。本発明のこの実施
の形態によれば、ネットワーク・ハブおよびＡＴＭトラ
ンスレータ５は、ホスト・コントローラ１０を備える。
ホスト・コントローラ１０は、コンピュータ２からのエ
ーテルネット通信用のエーテルネット・ハブ機能を扱う
ための従来のコンピュータ・ワークステーションであ
り、ホスト・コントローラ１０は、この厳しい性能にお
いて動作する充分な性能をもつものとする。この例にお
いて、ホスト・コントローラ１０は、そのデータ処理機
能とともに、公知のＰＣＩバス規格により動作する高性
能ローカル・バスＰＣＩＢＵＳを備える。ホスト・コン
トローラ１０と組み合わされ、ネットワーク・ハブおよ
びＡＴＭトランスレータ５は、トランスレータ・カード
１５を備える。トランスレータ・カード１５は、図示さ
れているように、ローカル・バスＰＣＩＢＵＳとのイン
ターフェースを行い、かつ、ＬＡＮからＡＴＭへの転送
を行うとともにファイバ光機能ＦＯへのインターフェー
スを行う回路を備える。このように、ホスト・コントロ
ーラ１０は、遠隔目的地向けのコンピュータ２の１つか
らの通信を認識し、これらの通信をローカル・バスＰＣ
ＩＢＵＳを介してトランスレータ・カード１５に送るの
に必要な機能を備える。
【００１８】トランスレータ・カード１５は、ＳＡＲデ
バイス１２を備える。ＳＡＲデバイス１２は、トランス
レータ・カード１５が扱う通信のための分節化および再
構築機能を行い、そのために、ホスト・コントローラ１
０のローカル・バスＰＣＩＢＵＳに接続されている。本
発明の好ましい実施の形態に関連して使用される適当な
ＳＡＲデバイス１２の例としては、テキサス・インスツ
ルメンツ社（本発明の譲受人）から出されているＴＥＮ
ＴＡ１５７５ＡＴＭ分節化および再構築デバイスがあ
る。ＳＡＲデバイス１２は、ローカル・バスＬＢＵＳを
介して、公知のＳＯＮＥＴ規格により通信のエンコード
およびデコードを行うＳＯＮＥＴ送受信回路２０に接続
されている。ＳＯＮＥＴ送受信（Ｒｘ／Ｔｘ）回路２０
は、トランスシーバ２２に接続され、トランスシーバ２
２は、従来の方法で、ファイバ光設備ＦＯ上へ信号を送
信し、そこから信号を受信する。
バイス１２を備える。ＳＡＲデバイス１２は、トランス
レータ・カード１５が扱う通信のための分節化および再
構築機能を行い、そのために、ホスト・コントローラ１
０のローカル・バスＰＣＩＢＵＳに接続されている。本
発明の好ましい実施の形態に関連して使用される適当な
ＳＡＲデバイス１２の例としては、テキサス・インスツ
ルメンツ社（本発明の譲受人）から出されているＴＥＮ
ＴＡ１５７５ＡＴＭ分節化および再構築デバイスがあ
る。ＳＡＲデバイス１２は、ローカル・バスＬＢＵＳを
介して、公知のＳＯＮＥＴ規格により通信のエンコード
およびデコードを行うＳＯＮＥＴ送受信回路２０に接続
されている。ＳＯＮＥＴ送受信（Ｒｘ／Ｔｘ）回路２０
は、トランスシーバ２２に接続され、トランスシーバ２
２は、従来の方法で、ファイバ光設備ＦＯ上へ信号を送
信し、そこから信号を受信する。
【００１９】本発明の好ましい実施の形態によるネット
ワーク・ハブおよびＡＴＭトランスレータ５におけるト
ランスレータ・カード１５は、スケジューラ１４を備え
る。スケジューラ１４は、コプロセッサ・バスＣＯＰＢ
ＵＳによってＳＡＲデバイス１２と制御メモリ１６とに
接続されている。本発明の好ましい実施の形態によれ
ば、スケジューラ１４は１個の集積回路デバイスに導入
される。制御メモリー１６は、システム・ソフトウェア
によってアクセスされる構成空間を備え、それが、構
成，初期設定およびエラー操作機能を提供する。また、
スケジューラ１４は、制御バスＣＯＰＩを介してＳＡＲ
デバイス１２に接続され、それにより、同期のためのク
ロックがスケジューラ１４に提供される。また、制御バ
スＣＯＰＩは、ＡＴＭセルが受信または送信されたこと
をスケジューラ１４に知らせるための制御信号を搬送す
る。制御信号は、スケジューラ１４に対するリセット信
号、また、ＦＩＦＯリソースの状態についてのスケジュ
ーラ１４からＳＡＲデバイス１２への信号として機能
し、また、そこへの割り込みを提供する信号として機能
する。また、スケジューラ１４は、ＡＴＭ（ＵＴＯＰＩ
Ａ）バス・プロトコル用の従来のユニバーサル・テスト
および動作・物理インターフェースにおけるラインに対
応するバスＲＸＵＴＯＰＩＡを介して信号を受信する。
スケジューラ１４は、ラインＲＸＵＴＯＰＩＡを介した
オブザーバとしてのみ動作し、到来するＡＴＭセルの受
信を認識する。
ワーク・ハブおよびＡＴＭトランスレータ５におけるト
ランスレータ・カード１５は、スケジューラ１４を備え
る。スケジューラ１４は、コプロセッサ・バスＣＯＰＢ
ＵＳによってＳＡＲデバイス１２と制御メモリ１６とに
接続されている。本発明の好ましい実施の形態によれ
ば、スケジューラ１４は１個の集積回路デバイスに導入
される。制御メモリー１６は、システム・ソフトウェア
によってアクセスされる構成空間を備え、それが、構
成，初期設定およびエラー操作機能を提供する。また、
スケジューラ１４は、制御バスＣＯＰＩを介してＳＡＲ
デバイス１２に接続され、それにより、同期のためのク
ロックがスケジューラ１４に提供される。また、制御バ
スＣＯＰＩは、ＡＴＭセルが受信または送信されたこと
をスケジューラ１４に知らせるための制御信号を搬送す
る。制御信号は、スケジューラ１４に対するリセット信
号、また、ＦＩＦＯリソースの状態についてのスケジュ
ーラ１４からＳＡＲデバイス１２への信号として機能
し、また、そこへの割り込みを提供する信号として機能
する。また、スケジューラ１４は、ＡＴＭ（ＵＴＯＰＩ
Ａ）バス・プロトコル用の従来のユニバーサル・テスト
および動作・物理インターフェースにおけるラインに対
応するバスＲＸＵＴＯＰＩＡを介して信号を受信する。
スケジューラ１４は、ラインＲＸＵＴＯＰＩＡを介した
オブザーバとしてのみ動作し、到来するＡＴＭセルの受
信を認識する。
【００２０】また、スケジューラ１４は、パラメータ・
メモリ１８に接続されている。パラメータ・メモリ１８
はメモリ・リソースであって、スケジューラ１４からの
オフチップで、ネットワーク・ハブおよびＡＴＭトラン
スレータ５が扱う各エーテルネット・チャンネルについ
ての情報を記憶する。このパラメータ・メモリ１８は、
各チャンネルについて、そのチャンネルで行われる通信
の様々なセル・レートに関するインジケータを記憶し、
また、そのチャンネルについての識別子（たとえば、仮
想パス識別子（ＶＰＩ）または仮想チャンネル識別子
（ＶＣＩ））を記憶する。本発明の好ましい実施の形態
によれば、パラメータ・メモリ１８は、チャンネルのい
くつかについて、各エーテルネット・チャンネルと関連
するタイム・スタンプ・オフセットおよびベース値を記
憶するとともに、そのチャンネルに対する次のセルがフ
ァイバ光設備ＦＯを介する通信のために処理される時刻
を示すタイム・スタンプの値を記憶する。本発明のこの
実施の形態において、パラメータ・メモリ１８は、６４
ｋのオーダーで３２ビット・ワードを含む。
メモリ１８に接続されている。パラメータ・メモリ１８
はメモリ・リソースであって、スケジューラ１４からの
オフチップで、ネットワーク・ハブおよびＡＴＭトラン
スレータ５が扱う各エーテルネット・チャンネルについ
ての情報を記憶する。このパラメータ・メモリ１８は、
各チャンネルについて、そのチャンネルで行われる通信
の様々なセル・レートに関するインジケータを記憶し、
また、そのチャンネルについての識別子（たとえば、仮
想パス識別子（ＶＰＩ）または仮想チャンネル識別子
（ＶＣＩ））を記憶する。本発明の好ましい実施の形態
によれば、パラメータ・メモリ１８は、チャンネルのい
くつかについて、各エーテルネット・チャンネルと関連
するタイム・スタンプ・オフセットおよびベース値を記
憶するとともに、そのチャンネルに対する次のセルがフ
ァイバ光設備ＦＯを介する通信のために処理される時刻
を示すタイム・スタンプの値を記憶する。本発明のこの
実施の形態において、パラメータ・メモリ１８は、６４
ｋのオーダーで３２ビット・ワードを含む。
【００２１】図３を参照して、本発明の好ましい実施の
形態による、ソース操作を行うスケージュラ１４の部分
の構成について、以下に詳細に説明する。スケジューラ
１４は、図３に示された部分の他に、制御信号によって
選択されたＡＴＭモードまたはＰＨＹモードで、ＵＴＯ
ＰＩＡインターフェース（つまり、ＲＸＵＴＯＰＩＡバ
ス）を介したセルの受信をモニタする目的地処理回路を
備える。ＡＴＭモードでは、スケジューラ１４の受信側
が、到来するセルを受信し、それらをＳＡＲデバイス１
２の再構築インターフェースに転送する。ＰＨＹモード
では、スケジューラ１４の受信側が、ＰＨＹデバイスの
ＴＸＵＴＯＰＩＡとして動作し、到来するセルが切換え
エレメントによってＳＡＲデバイス１２の再構築インタ
ーフェースに適用されるとき、到来するセルをモニタす
る。
形態による、ソース操作を行うスケージュラ１４の部分
の構成について、以下に詳細に説明する。スケジューラ
１４は、図３に示された部分の他に、制御信号によって
選択されたＡＴＭモードまたはＰＨＹモードで、ＵＴＯ
ＰＩＡインターフェース（つまり、ＲＸＵＴＯＰＩＡバ
ス）を介したセルの受信をモニタする目的地処理回路を
備える。ＡＴＭモードでは、スケジューラ１４の受信側
が、到来するセルを受信し、それらをＳＡＲデバイス１
２の再構築インターフェースに転送する。ＰＨＹモード
では、スケジューラ１４の受信側が、ＰＨＹデバイスの
ＴＸＵＴＯＰＩＡとして動作し、到来するセルが切換え
エレメントによってＳＡＲデバイス１２の再構築インタ
ーフェースに適用されるとき、到来するセルをモニタす
る。
【００２２】図３に示されたように、スケジューラ１４
のソース側では、以下に詳細に説明するように、ソース
挙動プロセッサ２４が、ファイバ光設備ＦＯを介してＡ
ＴＭセルを送信するスケジュールを行うスケジューラ１
４の一次操作ロジックを構成する。ソース挙動プロセッ
サ１４は、アベイラブル・ビット・レート（ＡＢＲ）送
信を実行し、バスＣＯＰＩ上の制御信号に基づきコプロ
セッサ・バスＣＯＰＢＵＳを介してＳＡＲデバイス１２
と通信を行い、スケジューラ１４内の他の機能を介して
高レベル制御を提供する。ソース挙動プロセッサ２４
は、ヒープ・ソート状態マシン３６のように、外部パラ
メータ・メモリ１８とインターフェースを行う。
のソース側では、以下に詳細に説明するように、ソース
挙動プロセッサ２４が、ファイバ光設備ＦＯを介してＡ
ＴＭセルを送信するスケジュールを行うスケジューラ１
４の一次操作ロジックを構成する。ソース挙動プロセッ
サ１４は、アベイラブル・ビット・レート（ＡＢＲ）送
信を実行し、バスＣＯＰＩ上の制御信号に基づきコプロ
セッサ・バスＣＯＰＢＵＳを介してＳＡＲデバイス１２
と通信を行い、スケジューラ１４内の他の機能を介して
高レベル制御を提供する。ソース挙動プロセッサ２４
は、ヒープ・ソート状態マシン３６のように、外部パラ
メータ・メモリ１８とインターフェースを行う。
【００２３】以下に更に詳細に説明するように、ヒープ
・ソート状態マシン３６は、外部パラメータ・メモリ１
８およびオンチップ・パラメータ・メモリ（ＰＭ）４４
の両方とインターフェースする。以下の説明から明らか
になるように、オンチップ・パラメータ・メモリ４４
は、次に送信される予定のＡＴＭセル（たとえば、送信
される次の２５６個のＡＴＭセル）についてのタイム・
スタンプ情報を含み、一方、オフチップ・パラメータ・
メモリ１８は、すべてのセルに関してソース挙動プロセ
ッサ２４が使用する送信パラメータと、残りのＡＴＭセ
ル（たとえば、現在の送信待ち行列内のＡＴＭセル２５
６〜２０４７）についてのタイム・スタンプ情報とを含
む。オンチップ・パラメータ・メモリ４４とオフチップ
・パラメータ・メモリ１８とがこのように構成されるこ
とは、スケジューラ１４およびＳＡＲデバイス１２にと
って有利である。というのは、オンチップ・メモリの方
が普通アクセスが早く、また、スケジューラ１４がスケ
ジュールすべきＬＡＮチャンネルの数は、オフチップ・
パラメータ・メモリ１８のサイズを大きくするだけで簡
単にスケールできるからである。
・ソート状態マシン３６は、外部パラメータ・メモリ１
８およびオンチップ・パラメータ・メモリ（ＰＭ）４４
の両方とインターフェースする。以下の説明から明らか
になるように、オンチップ・パラメータ・メモリ４４
は、次に送信される予定のＡＴＭセル（たとえば、送信
される次の２５６個のＡＴＭセル）についてのタイム・
スタンプ情報を含み、一方、オフチップ・パラメータ・
メモリ１８は、すべてのセルに関してソース挙動プロセ
ッサ２４が使用する送信パラメータと、残りのＡＴＭセ
ル（たとえば、現在の送信待ち行列内のＡＴＭセル２５
６〜２０４７）についてのタイム・スタンプ情報とを含
む。オンチップ・パラメータ・メモリ４４とオフチップ
・パラメータ・メモリ１８とがこのように構成されるこ
とは、スケジューラ１４およびＳＡＲデバイス１２にと
って有利である。というのは、オンチップ・メモリの方
が普通アクセスが早く、また、スケジューラ１４がスケ
ジュールすべきＬＡＮチャンネルの数は、オフチップ・
パラメータ・メモリ１８のサイズを大きくするだけで簡
単にスケールできるからである。
【００２４】スケジューラ１４の内部では、ソース挙動
プロセッサ２４が、アドレス・バスＡＤＤＲ上のアドレ
ス情報を提供し、データ・バスＤＡＴＡ上のデータを双
方向に通信する。スケジューラ・コマンド・レジスタ２
６は、バスＡＤＤＲ，ＤＡＴＡに接続され、新規ＡＴＭ
セルの待ち行列を送信待ち行列に繋げるためのソース挙
動プロセッサ２４からの通信を扱い、そこには、セルが
送信予定にあるまたは送信スケジュールされたと宣言さ
れる時刻の決定も含まれる。スケジューラ・コマンド・
レジスタ２６は、ソース挙動プロセッサ２４からそのよ
うなコマンドを受け取り、ヒープ・ソート状態マシン３
６にコマンド信号を送るとともに、ラインＡＣＲ上の許
可されたセル・レート値をデバイダ２８へ送る。
プロセッサ２４が、アドレス・バスＡＤＤＲ上のアドレ
ス情報を提供し、データ・バスＤＡＴＡ上のデータを双
方向に通信する。スケジューラ・コマンド・レジスタ２
６は、バスＡＤＤＲ，ＤＡＴＡに接続され、新規ＡＴＭ
セルの待ち行列を送信待ち行列に繋げるためのソース挙
動プロセッサ２４からの通信を扱い、そこには、セルが
送信予定にあるまたは送信スケジュールされたと宣言さ
れる時刻の決定も含まれる。スケジューラ・コマンド・
レジスタ２６は、ソース挙動プロセッサ２４からそのよ
うなコマンドを受け取り、ヒープ・ソート状態マシン３
６にコマンド信号を送るとともに、ラインＡＣＲ上の許
可されたセル・レート値をデバイダ２８へ送る。
【００２５】送信スケジュールされる各新規ＡＴＭセル
についてタイム・スタンプを決定する回路は、デバイダ
２８を備える。デバイダ２８は、スケジューラ・コマン
ド・レジスタ２６からラインＡＣＲ上のセル用の許可さ
れたセル・レート値を受け取り、また、ラインＣＬＫ上
のクロック信号を受信する。図３には示されていない
が、ラインＣＬＫ上のクロック信号は、スケジューラ１
４の他の同期回路にも入力され、スケジューラ１４が行
うすべての同期操作はこのクロック信号に基づくことが
好ましい。一般に、デバイダ２８は、ラインＣＬＫ上の
クロック信号のサイクル数に対応する値を生成し、それ
がラインＡＣＲ上でやり取りされる許可されたセル・レ
ート値に対する周期になり、この周期値が浮動小数点・
整数回路３０に供給される。この浮動小数点・整数回路
３０は、この周期値を整数値に変換し、加算器３１への
ラインＯＦＦＳＥＴ上の信号を生成する。ラインＯＦＦ
ＳＥＴ上の信号の値は、セルに「送信クレジット」が発
行される（つまり、送信がスケジュールされる）までに
経過したラインＣＬＫ上のクロック信号のサイクル数に
対応する。この操作のより詳細な説明は、以下に行う。
についてタイム・スタンプを決定する回路は、デバイダ
２８を備える。デバイダ２８は、スケジューラ・コマン
ド・レジスタ２６からラインＡＣＲ上のセル用の許可さ
れたセル・レート値を受け取り、また、ラインＣＬＫ上
のクロック信号を受信する。図３には示されていない
が、ラインＣＬＫ上のクロック信号は、スケジューラ１
４の他の同期回路にも入力され、スケジューラ１４が行
うすべての同期操作はこのクロック信号に基づくことが
好ましい。一般に、デバイダ２８は、ラインＣＬＫ上の
クロック信号のサイクル数に対応する値を生成し、それ
がラインＡＣＲ上でやり取りされる許可されたセル・レ
ート値に対する周期になり、この周期値が浮動小数点・
整数回路３０に供給される。この浮動小数点・整数回路
３０は、この周期値を整数値に変換し、加算器３１への
ラインＯＦＦＳＥＴ上の信号を生成する。ラインＯＦＦ
ＳＥＴ上の信号の値は、セルに「送信クレジット」が発
行される（つまり、送信がスケジュールされる）までに
経過したラインＣＬＫ上のクロック信号のサイクル数に
対応する。この操作のより詳細な説明は、以下に行う。
【００２６】加算器３１によって、ラインＯＦＦＳＥＴ
上の値が、マルチプレクサ３２から受信されるラインＢ
ＡＳＥ上の信号の値に加算される。マルチプレクサ３２
は、ラインＲＫＥＹ上のヒープ・ソート状態マシン３６
の出力から、当該チャンネルが最後に使用された（matu
red ）時刻であるルート・キー値に対応する１つの入力
を受信し、また、基準タイマー３８から、タイマーの現
在値に対応するもう１つの入力を受信する。このタイマ
ーの現在値が、デュー・コンパレータ４０によって、セ
ル・タイム・スタンプと比較される。マルチプレクサ制
御機能３３によってマルチプレクサ３２への制御入力が
生成される。マルチプレクサ制御機能３３は、ラインＲ
ＫＥＹ上のヒープ・ソート状態マシン３６の出力と、基
準タイマー３８からの現在グローバル時刻と、浮動小数
点・整数回路３０からのラインＯＦＦＳＥＴ上のオフセ
ット値とを受け取る。マルチプレクサ３２が選択するベ
ース値の選択について、以下、詳細に説明する。加算器
３１からの結果として得られる和は、ラインＫＥＹ上
に、新たにスケジュールされるセルについてのタイム・
スタンプ（ＢＡＳＥ＋ＯＦＦＳＥＴ）としてヒープ・ソ
ート状態マシン３６に提供される。以下に詳細に説明す
るように、ヒープ・ソート状態マシン３６は、それらの
タイム・スタンプによりすべての現時点でアクティブな
セルをソートし、セルが送信クレジットを受け取る順序
を設定する。ヒープ・ソート状態マシン３６からの制御
信号は、スケジューラ出力レジスタ４２に提供される。
これらの制御信号は、ヒープ・ソート状態マシン３６が
現在ソート処理中であることを示すラインＳＯＲＴＢＵ
ＳＹ上の信号を含む。このソート期間中、ソース挙動プ
ロセッサ２４はスケジュール用に新規セルを送り出すこ
とはない。ラインＣＨＡＮおよびラインＶＡＬＩＤ上の
信号は、ルート・セル（すなわち、以下に述べるよう
に、次の”デュー”セル）の識別および有効性を示し、
それらの信号は当該チャンネル用のラインＲＫＥＹ上の
デュー・コンパレータ４０に提示され、そのタイム・ス
タンプ値を伝える。
上の値が、マルチプレクサ３２から受信されるラインＢ
ＡＳＥ上の信号の値に加算される。マルチプレクサ３２
は、ラインＲＫＥＹ上のヒープ・ソート状態マシン３６
の出力から、当該チャンネルが最後に使用された（matu
red ）時刻であるルート・キー値に対応する１つの入力
を受信し、また、基準タイマー３８から、タイマーの現
在値に対応するもう１つの入力を受信する。このタイマ
ーの現在値が、デュー・コンパレータ４０によって、セ
ル・タイム・スタンプと比較される。マルチプレクサ制
御機能３３によってマルチプレクサ３２への制御入力が
生成される。マルチプレクサ制御機能３３は、ラインＲ
ＫＥＹ上のヒープ・ソート状態マシン３６の出力と、基
準タイマー３８からの現在グローバル時刻と、浮動小数
点・整数回路３０からのラインＯＦＦＳＥＴ上のオフセ
ット値とを受け取る。マルチプレクサ３２が選択するベ
ース値の選択について、以下、詳細に説明する。加算器
３１からの結果として得られる和は、ラインＫＥＹ上
に、新たにスケジュールされるセルについてのタイム・
スタンプ（ＢＡＳＥ＋ＯＦＦＳＥＴ）としてヒープ・ソ
ート状態マシン３６に提供される。以下に詳細に説明す
るように、ヒープ・ソート状態マシン３６は、それらの
タイム・スタンプによりすべての現時点でアクティブな
セルをソートし、セルが送信クレジットを受け取る順序
を設定する。ヒープ・ソート状態マシン３６からの制御
信号は、スケジューラ出力レジスタ４２に提供される。
これらの制御信号は、ヒープ・ソート状態マシン３６が
現在ソート処理中であることを示すラインＳＯＲＴＢＵ
ＳＹ上の信号を含む。このソート期間中、ソース挙動プ
ロセッサ２４はスケジュール用に新規セルを送り出すこ
とはない。ラインＣＨＡＮおよびラインＶＡＬＩＤ上の
信号は、ルート・セル（すなわち、以下に述べるよう
に、次の”デュー”セル）の識別および有効性を示し、
それらの信号は当該チャンネル用のラインＲＫＥＹ上の
デュー・コンパレータ４０に提示され、そのタイム・ス
タンプ値を伝える。
【００２７】基準タイマー３８は、ラインＣＬＫ上のク
ロック信号が１サイクル進むごとに進む単純なカウンタ
であり、スケジューリング操作の時刻ベースとなる。デ
ュー・コンパレータ４０は、ヒープ・ソート状態マシン
３６からのラインＲＫＥＹ上のタイム・スタンプ値と一
緒に基準タイマー３８の出力を受け取る。ソート処理の
結果としてルート・チャンネルが見つかったことを知ら
せるＶＡＬＩＤ信号をヒープ・ソート状態マシン３６か
ら受け取ると、コンパレータ４０は、当該ルート・チャ
ンネル用のタイム・スタンプを基準タイマー３８からの
現在値と比較して、このセルの送信クレジットを発行す
べき時刻になったかどうかを決定し、もしそうであれ
ば、それをスケジューラ出力レジスタ４２にラインＤＵ
Ｅラインを介して知らせる。スケジューラ出力レジスタ
４２は、ソート回路からソース挙動プロセッサ２４への
通信を扱う。この通信には、たとえば、送信クレジット
が発行されるべきセルを有するチャンネルの指示や、パ
ラメータ・メモリ１８，４４を更新するためのデータな
どが含まれる。
ロック信号が１サイクル進むごとに進む単純なカウンタ
であり、スケジューリング操作の時刻ベースとなる。デ
ュー・コンパレータ４０は、ヒープ・ソート状態マシン
３６からのラインＲＫＥＹ上のタイム・スタンプ値と一
緒に基準タイマー３８の出力を受け取る。ソート処理の
結果としてルート・チャンネルが見つかったことを知ら
せるＶＡＬＩＤ信号をヒープ・ソート状態マシン３６か
ら受け取ると、コンパレータ４０は、当該ルート・チャ
ンネル用のタイム・スタンプを基準タイマー３８からの
現在値と比較して、このセルの送信クレジットを発行す
べき時刻になったかどうかを決定し、もしそうであれ
ば、それをスケジューラ出力レジスタ４２にラインＤＵ
Ｅラインを介して知らせる。スケジューラ出力レジスタ
４２は、ソート回路からソース挙動プロセッサ２４への
通信を扱う。この通信には、たとえば、送信クレジット
が発行されるべきセルを有するチャンネルの指示や、パ
ラメータ・メモリ１８，４４を更新するためのデータな
どが含まれる。
【００２８】スケジューラ１４の構成およびその全体的
動作は以上の通りであり、次に、図４を参照して、本発
明の好ましい実施の形態による、送信用のＡＴＭセルを
スケジュールするスケジューラ１４の動作について、詳
細に説明する。図４に示された動作は、一方では、ソー
ス挙動プロセッサ２４によって行われものであり、また
他方において、スケジューラ１４内のソート回路（ヒー
プ・ソート状態マシン３６およびそれと関連する上述し
た回路）によって行われる。スケジューラ１４のこれら
の２つの部分の動作は、図４のフロー・ダイアグラムに
おける２つの部分に対応し、相互に協調的に行われる。
動作は以上の通りであり、次に、図４を参照して、本発
明の好ましい実施の形態による、送信用のＡＴＭセルを
スケジュールするスケジューラ１４の動作について、詳
細に説明する。図４に示された動作は、一方では、ソー
ス挙動プロセッサ２４によって行われものであり、また
他方において、スケジューラ１４内のソート回路（ヒー
プ・ソート状態マシン３６およびそれと関連する上述し
た回路）によって行われる。スケジューラ１４のこれら
の２つの部分の動作は、図４のフロー・ダイアグラムに
おける２つの部分に対応し、相互に協調的に行われる。
【００２９】ソース挙動プロセッサ２４は、最後に送信
動作をスケジュールしたＡＴＭチャンネル（チャンネル
ＣＨn ）用のスケジュール動作を開始する。プロセス４
８において、ソース挙動プロセッサ２４は、パラメータ
・メモリ１８またはＳＡＲデバイス１２からチャンネル
ＣＨn 用の許可されたセル・レート（ＡＣＲ）値を検索
して、このＡＣＲ値を必要に応じて更新する。なお、通
信システムにおけるアクティブ・チャンネル用のＡＣＲ
値の更新は、セル送信要求が受け取られるたびに行われ
る必要はなく、チャンネル条件が変更されたとき（たと
えば、ＡＴＭ送信が終了したとき、または、新しいＡＴ
Ｍチャンネルが開設されたとき）にのみ行われる。条件
に変更がない場合、プロセス４８でソース挙動プロセッ
サ２４が行うことは、パラメータ・メモリ１８からチャ
ンネルＣＨn 用の現在のＡＣＲ値を検索し、ラインＡＣ
Ｒ上のこの値をデバイダ２８に送るだけである。
動作をスケジュールしたＡＴＭチャンネル（チャンネル
ＣＨn ）用のスケジュール動作を開始する。プロセス４
８において、ソース挙動プロセッサ２４は、パラメータ
・メモリ１８またはＳＡＲデバイス１２からチャンネル
ＣＨn 用の許可されたセル・レート（ＡＣＲ）値を検索
して、このＡＣＲ値を必要に応じて更新する。なお、通
信システムにおけるアクティブ・チャンネル用のＡＣＲ
値の更新は、セル送信要求が受け取られるたびに行われ
る必要はなく、チャンネル条件が変更されたとき（たと
えば、ＡＴＭ送信が終了したとき、または、新しいＡＴ
Ｍチャンネルが開設されたとき）にのみ行われる。条件
に変更がない場合、プロセス４８でソース挙動プロセッ
サ２４が行うことは、パラメータ・メモリ１８からチャ
ンネルＣＨn 用の現在のＡＣＲ値を検索し、ラインＡＣ
Ｒ上のこの値をデバイダ２８に送るだけである。
【００３０】ソース挙動プロセッサ２４は、次に、判定
４９を行い、ヒープ・ソート状態マシン３６がソート処
理の最中であるかどうかをスケジューラ出力レジスタ４
２に決定させる。上述したように、このビジー状態は、
ヒープ・ソート状態マシン３６が制御ラインＳＯＲＴＢ
ＵＳＹ上のアクティブ信号をスケジューラ出力レジスタ
４２へ発行することによって示される。ヒープ・ソート
状態マシン３６がビジー（判定４９がＹＥＳ）であれ
ば，ソース挙動プロセッサ２４は、ヒープ・ソート状態
マシン３６がビジーでなくなるまで、待ち状態５０にな
り、この間、ソート回路に新しいコマンドを発行するこ
とはない。ヒープ・ソート状態マシン３６がビジーでな
いと判定４９が決定する（判定４９がＮＯ）と、制御は
チャンネルＣＨn の処理用のプロセス５２にパスされ
る。
４９を行い、ヒープ・ソート状態マシン３６がソート処
理の最中であるかどうかをスケジューラ出力レジスタ４
２に決定させる。上述したように、このビジー状態は、
ヒープ・ソート状態マシン３６が制御ラインＳＯＲＴＢ
ＵＳＹ上のアクティブ信号をスケジューラ出力レジスタ
４２へ発行することによって示される。ヒープ・ソート
状態マシン３６がビジー（判定４９がＹＥＳ）であれ
ば，ソース挙動プロセッサ２４は、ヒープ・ソート状態
マシン３６がビジーでなくなるまで、待ち状態５０にな
り、この間、ソート回路に新しいコマンドを発行するこ
とはない。ヒープ・ソート状態マシン３６がビジーでな
いと判定４９が決定する（判定４９がＮＯ）と、制御は
チャンネルＣＨn の処理用のプロセス５２にパスされ
る。
【００３１】プロセス５２で、ソース挙動プロセッサ２
４は、現在のＡＴＭチャンネルＣＨ n のチャンネル番号
および関連ＡＣＲ値をスケジューラ・コマンド・レジス
タ２６に書き込む。その後、ソース挙動プロセッサ２４
は待ちループに入り、（ＡＴＭセルが満期になる次のチ
ャンネル（以下に説明されるように、普通は、異なった
チャンネルＣＨm ）に対して、ヒープ・ソート状態マシ
ン３６がアクティブＶＡＬＩＤ信号を発行したのに対応
して）有効ビットがセットされたかどうかをスケジュー
ラ出力レジスタ４２に決定させる。まだである（判定５
３がＮＯ）場合には、ソース挙動プロセッサ２４は、こ
の有効ビットがセットされるまで待ち状態５４に入る。
４は、現在のＡＴＭチャンネルＣＨ n のチャンネル番号
および関連ＡＣＲ値をスケジューラ・コマンド・レジス
タ２６に書き込む。その後、ソース挙動プロセッサ２４
は待ちループに入り、（ＡＴＭセルが満期になる次のチ
ャンネル（以下に説明されるように、普通は、異なった
チャンネルＣＨm ）に対して、ヒープ・ソート状態マシ
ン３６がアクティブＶＡＬＩＤ信号を発行したのに対応
して）有効ビットがセットされたかどうかをスケジュー
ラ出力レジスタ４２に決定させる。まだである（判定５
３がＮＯ）場合には、ソース挙動プロセッサ２４は、こ
の有効ビットがセットされるまで待ち状態５４に入る。
【００３２】スケジューラ・コマンド・レジスタ２６が
コマンドおよびＡＣＲ値を受け取ると、プロセス６２
で、スケジューラ・コマンド・レジスタ２６がＡＣＲ値
をデバイダ２８に渡し、チャンネルＣＨn 用のタイム・
スタンプを以下のように決定する。本発明の本好ましい
実施の形態によれば、ソース挙動プロセッサ２４によっ
て引き出されるＡＣＲレート（セル／秒の単位）は、ラ
インＣＬＫ上のクロック信号のサイクル数に変換され
る。プロセス６４で、デバイダ２８は、ラインＣＬＫ上
のクロック信号の周波数をチャンネルＣＨn 用のライン
ＡＣＲ上の許可されたセル・レート値で割って、チャン
ネルＣＨn のセル送信の期間を表す値をクロック・サイ
クル数／セルの単位で引き出す。この値は、浮動小数点
・整数回路３０によって浮動小数点値から整数に変換さ
れ、プロセス６４の結果はオフセット値としてラインＯ
ＦＦＳＥＴ上で加算器３１に供給される。このオフセッ
ト値は、チャンネルＣＨn に対して送信クレジットが満
期になる「未来の」時刻までのＣＬＫサイクル数に対応
する。
コマンドおよびＡＣＲ値を受け取ると、プロセス６２
で、スケジューラ・コマンド・レジスタ２６がＡＣＲ値
をデバイダ２８に渡し、チャンネルＣＨn 用のタイム・
スタンプを以下のように決定する。本発明の本好ましい
実施の形態によれば、ソース挙動プロセッサ２４によっ
て引き出されるＡＣＲレート（セル／秒の単位）は、ラ
インＣＬＫ上のクロック信号のサイクル数に変換され
る。プロセス６４で、デバイダ２８は、ラインＣＬＫ上
のクロック信号の周波数をチャンネルＣＨn 用のライン
ＡＣＲ上の許可されたセル・レート値で割って、チャン
ネルＣＨn のセル送信の期間を表す値をクロック・サイ
クル数／セルの単位で引き出す。この値は、浮動小数点
・整数回路３０によって浮動小数点値から整数に変換さ
れ、プロセス６４の結果はオフセット値としてラインＯ
ＦＦＳＥＴ上で加算器３１に供給される。このオフセッ
ト値は、チャンネルＣＨn に対して送信クレジットが満
期になる「未来の」時刻までのＣＬＫサイクル数に対応
する。
【００３３】本発明の好ましい実施の形態によれば、ラ
インＯＦＦＳＥＴ上のこのオフセット値は、ベース時刻
に加算され、チャンネルＣＨn 用の実際のタイム・スタ
ンプを引き出す。プロセス６６で、マルチプレクサ３２
はマルチプレクサ制御機能３３によって制御されて、ベ
ース時刻を選択する。ベース時刻は、典型的には、当該
チャンネルが最後に送信クレジットを受け取った時刻で
ある。チャンネルＣＨ n に対して送信クレジットが発行
されたばかりであっても、上述したプロセスの潜伏時間
がセル・レートに対して実質的相関にあることを考慮す
ると、この選択は有益である。本発明の好ましい実施の
形態によれば、ベース時刻は現在のグローバル時刻（す
なわち、基準タイマ３８の出力）であってもよい。マル
チプレクサ３２によってどちらのベース時刻を選択すべ
きかの決定について、以下に詳細に述べる。というの
は、この決定は、スケジューラ１４によって扱われる各
ＡＢＲチャンネルの最終セル・レートにとって決定的な
ものだからである。
インＯＦＦＳＥＴ上のこのオフセット値は、ベース時刻
に加算され、チャンネルＣＨn 用の実際のタイム・スタ
ンプを引き出す。プロセス６６で、マルチプレクサ３２
はマルチプレクサ制御機能３３によって制御されて、ベ
ース時刻を選択する。ベース時刻は、典型的には、当該
チャンネルが最後に送信クレジットを受け取った時刻で
ある。チャンネルＣＨ n に対して送信クレジットが発行
されたばかりであっても、上述したプロセスの潜伏時間
がセル・レートに対して実質的相関にあることを考慮す
ると、この選択は有益である。本発明の好ましい実施の
形態によれば、ベース時刻は現在のグローバル時刻（す
なわち、基準タイマ３８の出力）であってもよい。マル
チプレクサ３２によってどちらのベース時刻を選択すべ
きかの決定について、以下に詳細に述べる。というの
は、この決定は、スケジューラ１４によって扱われる各
ＡＢＲチャンネルの最終セル・レートにとって決定的な
ものだからである。
【００３４】図３に示されたマルチプレクサ制御機能３
３は別個の回路であるが、マルチプレクサ制御機能３３
は、必要なら、デュー・コンパレータ４０とヒープ・ソ
ート状態マシン３６とともにソース挙動プロセッサ２４
内に設けられてもよい。
３は別個の回路であるが、マルチプレクサ制御機能３３
は、必要なら、デュー・コンパレータ４０とヒープ・ソ
ート状態マシン３６とともにソース挙動プロセッサ２４
内に設けられてもよい。
【００３５】いずれにせよ、定ビット・レート（ＣＢ
Ｒ）サービスは、保証された固定のビット・レートで通
信されることが必要であり、ＣＢＲチャンネルと関連す
るＡＴＭセル用のＡＣＲ値は変化しない。一方、ＡＢＲ
チャンネルのＡＣＲ値は、使用可能な帯域幅に従って設
定される。本発明の好ましい実施の形態によれば、ＣＢ
Ｒチャンネルは、ＳＡＲデバイス１２によってのみ扱わ
れ、そのスケジューリングにはスケジューラ１４の動作
が関与しない。スケジューラ１４がスケジュールするの
は、ＡＢＲチャンネル用のセルだけであり、そのような
セルは時間的に可能な範囲でＳＡＲデバイス１２によっ
て送信されるだけである。
Ｒ）サービスは、保証された固定のビット・レートで通
信されることが必要であり、ＣＢＲチャンネルと関連す
るＡＴＭセル用のＡＣＲ値は変化しない。一方、ＡＢＲ
チャンネルのＡＣＲ値は、使用可能な帯域幅に従って設
定される。本発明の好ましい実施の形態によれば、ＣＢ
Ｒチャンネルは、ＳＡＲデバイス１２によってのみ扱わ
れ、そのスケジューリングにはスケジューラ１４の動作
が関与しない。スケジューラ１４がスケジュールするの
は、ＡＢＲチャンネル用のセルだけであり、そのような
セルは時間的に可能な範囲でＳＡＲデバイス１２によっ
て送信されるだけである。
【００３６】しかしながら、本発明の好ましい実施の形
態によれば、高データ・レートのチャンネル（たとえ
ば、ＣＢＲチャンネルやその他のアクティビティ）が満
期になった低データ・レート・チャンネルを先取する
と、「公平（fairness）」の発行が生じ得ることが観察
されている。本発明の好ましい実施の形態によりベース
選択プロセス６６で行われるマルチプレクサ３２の制御
では、タイム・スタンプ値の割り当ては必ず公平に行わ
れ、オーバー・スケジュール条件においては、高データ
・レートのＡＢＲチャンネルが残りの帯域幅を公平に分
割する間、低データ・レートのチャンネルが先取りされ
ることはない。次に、プロセス６６の全体的結果につい
て説明するが、そこでは、本発明の好ましい実施の形態
によるスケジューラ１４内で行われるプロセス６６につ
いて詳細に述べる。
態によれば、高データ・レートのチャンネル（たとえ
ば、ＣＢＲチャンネルやその他のアクティビティ）が満
期になった低データ・レート・チャンネルを先取する
と、「公平（fairness）」の発行が生じ得ることが観察
されている。本発明の好ましい実施の形態によりベース
選択プロセス６６で行われるマルチプレクサ３２の制御
では、タイム・スタンプ値の割り当ては必ず公平に行わ
れ、オーバー・スケジュール条件においては、高データ
・レートのＡＢＲチャンネルが残りの帯域幅を公平に分
割する間、低データ・レートのチャンネルが先取りされ
ることはない。次に、プロセス６６の全体的結果につい
て説明するが、そこでは、本発明の好ましい実施の形態
によるスケジューラ１４内で行われるプロセス６６につ
いて詳細に述べる。
【００３７】一般的に、ＡＢＲ送信に使用可能な帯域幅
は、本質的に、ＡＢＲチャンネル数で割られ、１チャン
ネルにつき等しく割られたビット・レートが得られる。
この等しく割られたビット・レートがどのＡＢＲチャン
ネルにとっても十分に満足させるものであれば（１また
はそれ以上の比較的低いビット・レートのＡＢＲチャン
ネルに対して真であり得る）、これらの満足されたチャ
ンネルは、それらの要求されたビット・レートに実質的
に設定されたＡＣＲ値を有し、それ以上の考慮はされな
い。（ＣＢＲ要求および十分に満足されたＡＢＲチャン
ネルの両方を引き算した後の）残りの帯域幅は、再度、
まだ満足されていないＡＢＲチャンネルの数によって割
られ、そこで満足されたチャンネルは、ビット・レート
が再び割り当てられ、それ以上の考慮は必要なくなり、
このプロセスが繰り返される。
は、本質的に、ＡＢＲチャンネル数で割られ、１チャン
ネルにつき等しく割られたビット・レートが得られる。
この等しく割られたビット・レートがどのＡＢＲチャン
ネルにとっても十分に満足させるものであれば（１また
はそれ以上の比較的低いビット・レートのＡＢＲチャン
ネルに対して真であり得る）、これらの満足されたチャ
ンネルは、それらの要求されたビット・レートに実質的
に設定されたＡＣＲ値を有し、それ以上の考慮はされな
い。（ＣＢＲ要求および十分に満足されたＡＢＲチャン
ネルの両方を引き算した後の）残りの帯域幅は、再度、
まだ満足されていないＡＢＲチャンネルの数によって割
られ、そこで満足されたチャンネルは、ビット・レート
が再び割り当てられ、それ以上の考慮は必要なくなり、
このプロセスが繰り返される。
【００３８】残りの帯域幅の分割によって満足されるＡ
ＢＲチャンネルが１つもなくなると、等しく分割された
ビット・レートは、これらの残りのＡＢＲチャンネルの
それぞれのＡＣＲ値となる。もちろん、この時点ですべ
てのチャンネルが満足された場合（すなわち、残ってい
るチャンネルがない場合）、この条件はアンダー・ディ
マンド条件となり、その場合、すべてのＡＢＲチャンネ
ルがそれらの要求されたビット・レートに対応するＡＣ
Ｒを受け取る。ただし、十分に満足されないＡＢＲチャ
ンネルが少なくとも１つでもあれば、等しく分割された
ビット・レートは、これらのチャンネルに対する帯域幅
のかなり公平な分割を提供することになる。
ＢＲチャンネルが１つもなくなると、等しく分割された
ビット・レートは、これらの残りのＡＢＲチャンネルの
それぞれのＡＣＲ値となる。もちろん、この時点ですべ
てのチャンネルが満足された場合（すなわち、残ってい
るチャンネルがない場合）、この条件はアンダー・ディ
マンド条件となり、その場合、すべてのＡＢＲチャンネ
ルがそれらの要求されたビット・レートに対応するＡＣ
Ｒを受け取る。ただし、十分に満足されないＡＢＲチャ
ンネルが少なくとも１つでもあれば、等しく分割された
ビット・レートは、これらのチャンネルに対する帯域幅
のかなり公平な分割を提供することになる。
【００３９】このＡＢＲ帯域幅の分割の操作の一例を示
し、この操作の説明の一助とする。この例には、次のよ
うなオーバー・スケジュール条件がある。
し、この操作の説明の一助とする。この例には、次のよ
うなオーバー・スケジュール条件がある。
【００４０】
【表１】
【００４１】この例では、帯域幅が大量にオーバー・ス
ケジュールされている。すべてのチャンネルＣＨ１〜Ｃ
Ｈ６のビット・レート要求の合計が帯域幅全体の２９０
％になっている。したがって、すべてのチャンネルのＡ
ＣＲが単にそれらの要求されたビット・レートに設定さ
れることはない。
ケジュールされている。すべてのチャンネルＣＨ１〜Ｃ
Ｈ６のビット・レート要求の合計が帯域幅全体の２９０
％になっている。したがって、すべてのチャンネルのＡ
ＣＲが単にそれらの要求されたビット・レートに設定さ
れることはない。
【００４２】前述のごとく、使用可能帯域幅のうちでＣ
ＢＲチャンネルＣＨ１，ＣＨ２が要求する帯域幅の５０
％が全体の帯域幅から引き算され、要求された２５％Ｃ
ＢＲ値がチャンネルＣＨ１，ＣＨ２に割り当てられる。
残りの帯域幅（全体の帯域幅の５０％）は、処理される
べき４つのＡＢＲチャンネルＣＨ３〜ＣＨ６が残ってい
るので、“４”で割り算される。その結果、全体の帯域
幅の１２．５％に当たるビット・レート値Ｑに等しく分
割される。この１２．５％レートは、２つのＡＢＲチャ
ンネルＣＨ３，ＣＨ４を満足させる。この場合、全体の
帯域幅の５％のＡＣＲ値がチャンネルＣＨ３に割り当て
られ、全体の帯域幅の１０％のＡＣＲ値がチャンネルＣ
Ｈ４に割り当てられる。次に、残りの帯域幅（全体の帯
域幅の３５％）が、懸案となっている残りの２つのＡＢ
Ｒチャンネルによって再度分割される。その結果、全体
の帯域幅の１７．５％のビット・レートに等しく分割さ
れる。この２回目の等分割は残りのＡＢＲチャンネルＣ
Ｈ５，ＣＨ６のどちらも満足させないが、これらのチャ
ンネルに対するＡＣＲ値は、この等分割された１７．５
％のビット・レートに設定される。以上をまとめると、
次のようになる。
ＢＲチャンネルＣＨ１，ＣＨ２が要求する帯域幅の５０
％が全体の帯域幅から引き算され、要求された２５％Ｃ
ＢＲ値がチャンネルＣＨ１，ＣＨ２に割り当てられる。
残りの帯域幅（全体の帯域幅の５０％）は、処理される
べき４つのＡＢＲチャンネルＣＨ３〜ＣＨ６が残ってい
るので、“４”で割り算される。その結果、全体の帯域
幅の１２．５％に当たるビット・レート値Ｑに等しく分
割される。この１２．５％レートは、２つのＡＢＲチャ
ンネルＣＨ３，ＣＨ４を満足させる。この場合、全体の
帯域幅の５％のＡＣＲ値がチャンネルＣＨ３に割り当て
られ、全体の帯域幅の１０％のＡＣＲ値がチャンネルＣ
Ｈ４に割り当てられる。次に、残りの帯域幅（全体の帯
域幅の３５％）が、懸案となっている残りの２つのＡＢ
Ｒチャンネルによって再度分割される。その結果、全体
の帯域幅の１７．５％のビット・レートに等しく分割さ
れる。この２回目の等分割は残りのＡＢＲチャンネルＣ
Ｈ５，ＣＨ６のどちらも満足させないが、これらのチャ
ンネルに対するＡＣＲ値は、この等分割された１７．５
％のビット・レートに設定される。以上をまとめると、
次のようになる。
【００４３】
【表２】 このような分配により、ＡＣＲ値は比較的公平になり、
（一般的には、プレミアム料金を支払う）ＣＢＲチャン
ネルと比較的低いビット・レートを要求しているＡＢＲ
チャンネルとは満足し、一方、（プレミアム料金を支払
わずに）使用可能帯域幅のうち法外な量を要求するＡＢ
Ｒチャンネルには、使用可能帯域幅によって提供される
分だけが割り当てられる。また、このプロセスによれ
ば、各チャンネルが要求する帯域幅以上の帯域幅を割り
当てることは避けられる。たとえば、使用可能帯域幅の
２００％を要求するチャンネルＣＨ６は、帯域幅の２５
％しか要求していないチャンネルＣＨ５以上の帯域幅を
もらうことはできない。
（一般的には、プレミアム料金を支払う）ＣＢＲチャン
ネルと比較的低いビット・レートを要求しているＡＢＲ
チャンネルとは満足し、一方、（プレミアム料金を支払
わずに）使用可能帯域幅のうち法外な量を要求するＡＢ
Ｒチャンネルには、使用可能帯域幅によって提供される
分だけが割り当てられる。また、このプロセスによれ
ば、各チャンネルが要求する帯域幅以上の帯域幅を割り
当てることは避けられる。たとえば、使用可能帯域幅の
２００％を要求するチャンネルＣＨ６は、帯域幅の２５
％しか要求していないチャンネルＣＨ５以上の帯域幅を
もらうことはできない。
【００４４】しかしながら、上述したＡＣＲレート所望
の調整が実際の回路に導入された場合、反復される分割
および割り当て操作を行うために多数のマシン・サイク
ルが必要になる。特に、本例におけるスケジューラ１４
では２０４８ものチャンネルが扱われるのであるから、
大変なマシン・サイクルになる。本発明と関連して、次
のようなことが発見された。セルの１つ手前のルート・
キー値，現在のオンラインＲＫＥＹまたは当該チャンネ
ル用の次のセルがすでに満期を過ぎていれば基準タイマ
３８からのグローバル時刻を選択的に使用することによ
って、上述した公平なセル・レート決定を行うための適
切なタイム・スタンプ値を決定することができる。
の調整が実際の回路に導入された場合、反復される分割
および割り当て操作を行うために多数のマシン・サイク
ルが必要になる。特に、本例におけるスケジューラ１４
では２０４８ものチャンネルが扱われるのであるから、
大変なマシン・サイクルになる。本発明と関連して、次
のようなことが発見された。セルの１つ手前のルート・
キー値，現在のオンラインＲＫＥＹまたは当該チャンネ
ル用の次のセルがすでに満期を過ぎていれば基準タイマ
３８からのグローバル時刻を選択的に使用することによ
って、上述した公平なセル・レート決定を行うための適
切なタイム・スタンプ値を決定することができる。
【００４５】次に、図３と組み合わせて図５を参照し
て、本発明の好ましい実施の形態によるプロセス６６に
おけるマルチプレクサ制御機能３３の動作について詳細
に説明する。プロセス６６は、プロセス７８で始まり、
そこでは、マルチプレクサ制御機能３３が、浮動小数点
・整数回路３０からのラインＯＦＦＳＥＴ上のオフセッ
ト値を、ヒープ・ソート状態マシン３６によりラインＲ
ＫＥＹ上に提示される現在値に加算する。上述したよう
に、このラインＲＫＥＹ上の値は、送信クレジットが最
後に発行されたルート・チャンネル用のタイム・スタン
プであり、このルート・チャンネルは、新しいタイム・
スタンプ値が現在決定されている同じチャンネルと関連
している。このようなラインＲＫＥＹ上の値は、１つ前
のセルが送信用にスケジュールされた時刻に対応する
（この時刻は、潜伏その他の介在する事象により、当該
セルが実際に送信された時刻とは異なるのがふつうであ
る。）。プロセス７８の結果は、未来の保証時刻ＦＣＴ
であり、これは、このチャンネルで次に送信が行われる
（基準タイマ３８のサイクル内の）時点での第１の予測
であり、この予測はソース挙動プロセッサ２４が提供す
るオフセットを使用して行われ、オーバー・スケジュー
ル条件は考慮されない。
て、本発明の好ましい実施の形態によるプロセス６６に
おけるマルチプレクサ制御機能３３の動作について詳細
に説明する。プロセス６６は、プロセス７８で始まり、
そこでは、マルチプレクサ制御機能３３が、浮動小数点
・整数回路３０からのラインＯＦＦＳＥＴ上のオフセッ
ト値を、ヒープ・ソート状態マシン３６によりラインＲ
ＫＥＹ上に提示される現在値に加算する。上述したよう
に、このラインＲＫＥＹ上の値は、送信クレジットが最
後に発行されたルート・チャンネル用のタイム・スタン
プであり、このルート・チャンネルは、新しいタイム・
スタンプ値が現在決定されている同じチャンネルと関連
している。このようなラインＲＫＥＹ上の値は、１つ前
のセルが送信用にスケジュールされた時刻に対応する
（この時刻は、潜伏その他の介在する事象により、当該
セルが実際に送信された時刻とは異なるのがふつうであ
る。）。プロセス７８の結果は、未来の保証時刻ＦＣＴ
であり、これは、このチャンネルで次に送信が行われる
（基準タイマ３８のサイクル内の）時点での第１の予測
であり、この予測はソース挙動プロセッサ２４が提供す
るオフセットを使用して行われ、オーバー・スケジュー
ル条件は考慮されない。
【００４６】判定７９では、マルチプレクサ制御機能３
３は、基準タイマ３８からの現在のグローバル時刻に対
する未来の保証時刻ＦＣＴの値をテストして、同じチャ
ンネルに対する最後に送信クレジットを受け取った新し
いセルがすでに満期を過ぎているかどうかを決定する。
もしなっていなければ（判定７９がＮＯ、すなわち、こ
のチャンネル用の次のセルがまだ満期を過ぎていなけれ
ば）、プロセス８２に移り、そこで、マルチプレクサ制
御機能３３がラインＲＫＥＹ上の値をベースとして選択
し、これらのラインを加算器３１に渡して、新しタイム
・スタンプを決定させる。このような状況が起きるの
は、帯域幅がオーバー・スケジュールされていない間で
あり、その結果、次のラインＲＫＥＹ上の値（すなわ
ち、最後の送信クレジットに対応するラインＲＫＥＹ上
の値をＲＫＥＹn とした場合のＲＫＥＹn+1 ）は、この
チャンネルに対する要求されたＡＣＲ値に対応する。こ
れにより、送信クレジットの発行が遅れても、所与のチ
ャンネルで遅延が蓄積されることはない。基準タイマ３
８からのグローバル（現在の）時刻がベースとして使用
されると、このようなことが起きる可能性がある。
３は、基準タイマ３８からの現在のグローバル時刻に対
する未来の保証時刻ＦＣＴの値をテストして、同じチャ
ンネルに対する最後に送信クレジットを受け取った新し
いセルがすでに満期を過ぎているかどうかを決定する。
もしなっていなければ（判定７９がＮＯ、すなわち、こ
のチャンネル用の次のセルがまだ満期を過ぎていなけれ
ば）、プロセス８２に移り、そこで、マルチプレクサ制
御機能３３がラインＲＫＥＹ上の値をベースとして選択
し、これらのラインを加算器３１に渡して、新しタイム
・スタンプを決定させる。このような状況が起きるの
は、帯域幅がオーバー・スケジュールされていない間で
あり、その結果、次のラインＲＫＥＹ上の値（すなわ
ち、最後の送信クレジットに対応するラインＲＫＥＹ上
の値をＲＫＥＹn とした場合のＲＫＥＹn+1 ）は、この
チャンネルに対する要求されたＡＣＲ値に対応する。こ
れにより、送信クレジットの発行が遅れても、所与のチ
ャンネルで遅延が蓄積されることはない。基準タイマ３
８からのグローバル（現在の）時刻がベースとして使用
されると、このようなことが起きる可能性がある。
【００４７】しかしながら、オーバー・スケジュール条
件では、最後に送信クレジットを受け取ったそのチャン
ネル用の次のセルが既に満期を過ぎていることもある。
この状況は、未来のクレジット時刻ＦＣＴが現在のグロ
ーバル時刻より小さいこと（判定７９がＹＥＳ）に対応
する。この場合、プロセス８０に移り、そこで、マルチ
プレクサ制御機能３３は、新しいタイム・スタンプの生
成に使用するベースとして基準タイマ３８からのグロー
バル時刻を選択して、その値を加算器３１に供給する。
ラインＲＫＥＹ上の前の値ではなくグローバル時刻を使
用することにより、そのセル用のタイム・スタンプを効
果的に遅らせ、それにより、オーバー・スケジュール状
況に対処することができる。
件では、最後に送信クレジットを受け取ったそのチャン
ネル用の次のセルが既に満期を過ぎていることもある。
この状況は、未来のクレジット時刻ＦＣＴが現在のグロ
ーバル時刻より小さいこと（判定７９がＹＥＳ）に対応
する。この場合、プロセス８０に移り、そこで、マルチ
プレクサ制御機能３３は、新しいタイム・スタンプの生
成に使用するベースとして基準タイマ３８からのグロー
バル時刻を選択して、その値を加算器３１に供給する。
ラインＲＫＥＹ上の前の値ではなくグローバル時刻を使
用することにより、そのセル用のタイム・スタンプを効
果的に遅らせ、それにより、オーバー・スケジュール状
況に対処することができる。
【００４８】オーバー・スケジュール条件でＡＢＲセル
を公平にスケジュールする本発明の好ましい実施の形態
による方法における操作方法の一例について以下に詳細
に説明するが、その前に、図４の方法についての説明を
終わらせる。
を公平にスケジュールする本発明の好ましい実施の形態
による方法における操作方法の一例について以下に詳細
に説明するが、その前に、図４の方法についての説明を
終わらせる。
【００４９】図４に戻り、プロセス６８で、ラインＢＡ
ＳＥおよびラインＯＦＦＳＥＴ上の値が加算器３１によ
り加算されて、ラインＫＥＹ上の新しいタイム・スタン
プ値が生成され、ヒープ・ソート状態マシン３６に送ら
れる。スケジューラ・コマンド・レジスタ２６からのラ
インＣＭＤ上の適当な制御信号と組み合わされてライン
ＫＥＹ上のこの新しい値に応答して、ヒープ・ソート状
態マシン３６は、ＰＵＳＨ−ＰＯＰ操作を実行する。こ
のＰＵＳＨ−ＰＯＰ操作は、チャンネルＣＨnと関連す
るラインＫＥＹ上の現在値をプロセス７０におけるソー
ト用のヒープ（山積み）に押し込む動作を含む。これに
ついて、図６（Ａ）および図６（Ｂ）を参照しながら説
明する。図６（Ａ）および図６（Ｂ）はそれぞれ、チャ
ンネル情報およびタイム・スタンプ情報を山積み的に記
憶するオンチップ・パラメータ・メモリ４４およびオフ
チップ・パラメータ・メモリ１８を示す。
ＳＥおよびラインＯＦＦＳＥＴ上の値が加算器３１によ
り加算されて、ラインＫＥＹ上の新しいタイム・スタン
プ値が生成され、ヒープ・ソート状態マシン３６に送ら
れる。スケジューラ・コマンド・レジスタ２６からのラ
インＣＭＤ上の適当な制御信号と組み合わされてライン
ＫＥＹ上のこの新しい値に応答して、ヒープ・ソート状
態マシン３６は、ＰＵＳＨ−ＰＯＰ操作を実行する。こ
のＰＵＳＨ−ＰＯＰ操作は、チャンネルＣＨnと関連す
るラインＫＥＹ上の現在値をプロセス７０におけるソー
ト用のヒープ（山積み）に押し込む動作を含む。これに
ついて、図６（Ａ）および図６（Ｂ）を参照しながら説
明する。図６（Ａ）および図６（Ｂ）はそれぞれ、チャ
ンネル情報およびタイム・スタンプ情報を山積み的に記
憶するオンチップ・パラメータ・メモリ４４およびオフ
チップ・パラメータ・メモリ１８を示す。
【００５０】図６（Ａ）に示すように、本発明の好まし
い実施の形態によるオンチップ・パラメータ・メモリ４
４は、アドレス００〜ＦＦh に２５６個の４０ビット・
データ・ワードを含む。アドレス００のデータ・ワード
は保存され、この例では使用されない。オンチップ・パ
ラメータ・メモリ４４内のアドレス０１は、本実施の形
態において、次に満期になるＡＴＭセルと関係するチャ
ンネルであるルート・チャンネルと関係する。オンチッ
プ・パラメータ・メモリ４４の連続するアドレスは、そ
れらのタイム・スタンプの順序で並んだチャンネルと関
連づけられ、アドレスＦＦh は、次に満期になる２５５
番目のチャンネルと関係する。オンチップ・パラメータ
・メモリ４４内の各ワードは、タイム・スタンプを記憶
する部分とチャンネル番号を記憶する部分とを含む。
い実施の形態によるオンチップ・パラメータ・メモリ４
４は、アドレス００〜ＦＦh に２５６個の４０ビット・
データ・ワードを含む。アドレス００のデータ・ワード
は保存され、この例では使用されない。オンチップ・パ
ラメータ・メモリ４４内のアドレス０１は、本実施の形
態において、次に満期になるＡＴＭセルと関係するチャ
ンネルであるルート・チャンネルと関係する。オンチッ
プ・パラメータ・メモリ４４の連続するアドレスは、そ
れらのタイム・スタンプの順序で並んだチャンネルと関
連づけられ、アドレスＦＦh は、次に満期になる２５５
番目のチャンネルと関係する。オンチップ・パラメータ
・メモリ４４内の各ワードは、タイム・スタンプを記憶
する部分とチャンネル番号を記憶する部分とを含む。
【００５１】図６（Ｂ）から明らかなように、オフチッ
プ・パラメータ・メモリ１８は、少し異なった構成にな
る。この例では、オフチップ・パラメータ・メモリ１８
の最小アドレス部分は、次に満期になるチャンネルと関
係する。２５５個のチャンネルがオンチップ・パラメー
タ・メモリ４４に記憶された後、残りのチャンネルはオ
フチップ・パラメータ・メモリ１８に順番に記憶された
パラメータを有する。オフチップ・パラメータ・メモリ
１８では、各チャンネルがＡＴＭ送信と関連した状態パ
ラメータの多くを記憶する部分を持ち、その後に、その
タイム・スタンプを記憶する３２ビット・ワードが続
き、その後に、チャンネル番号を記憶するワードが続
く。オフチップ・パラメータ・メモリ１８内のチャンネ
ル・エントリ間には未使用ワードが保持される。また、
オフチップ・パラメータ・メモリ１８は、タイム・スタ
ンプがオンチップ・パラメータ・メモリ４４に記憶され
ているチャンネルと関連したパラメータも記憶する。と
いうのは、これらのＡＴＭパラメータはオンチップ・パ
ラメータ・メモリ４４には記憶されないからである。
プ・パラメータ・メモリ１８は、少し異なった構成にな
る。この例では、オフチップ・パラメータ・メモリ１８
の最小アドレス部分は、次に満期になるチャンネルと関
係する。２５５個のチャンネルがオンチップ・パラメー
タ・メモリ４４に記憶された後、残りのチャンネルはオ
フチップ・パラメータ・メモリ１８に順番に記憶された
パラメータを有する。オフチップ・パラメータ・メモリ
１８では、各チャンネルがＡＴＭ送信と関連した状態パ
ラメータの多くを記憶する部分を持ち、その後に、その
タイム・スタンプを記憶する３２ビット・ワードが続
き、その後に、チャンネル番号を記憶するワードが続
く。オフチップ・パラメータ・メモリ１８内のチャンネ
ル・エントリ間には未使用ワードが保持される。また、
オフチップ・パラメータ・メモリ１８は、タイム・スタ
ンプがオンチップ・パラメータ・メモリ４４に記憶され
ているチャンネルと関連したパラメータも記憶する。と
いうのは、これらのＡＴＭパラメータはオンチップ・パ
ラメータ・メモリ４４には記憶されないからである。
【００５２】図３および図４を参照すると、ヒープ・ソ
ート状態マシン３６が（スケジューラ・コマンド・レジ
スタ２８からの）チャンネル番号と（加算器３１からの
ラインＫＥＹ上の）タイム・スタンプとを押し込むと、
ヒープ・ソート・プロセス７０が開始される。プロセス
７０は、多数ある従来のヒープ・ソート・アルゴリズム
のいずれかにより実行され、その間、ヒープ・ソート状
態マシン３６はパラメータ・メモリ１８，４４内のヒー
プ（山積み）の現在のメンバーのタイム・スタンプを尋
ね、これらのタイム・スタンプをオンチップ・パラメー
タ・メモリ４４の最小アドレス（０１）に記憶して、現
在のチャンネルＣＨn に新しいタイム・スタンプを使用
するとともに従来のヒープ・ソート・アルゴリズムに従
ってタイム・スタンプによるチャンネルのソートを継続
する。ヒープ・ソートを使用する方法は、本発明に関し
ては、とりわけ有効である。というのは、ヒープ・ソー
ト技術は、記憶されるべき要素の数が本例（たとえば、
２０４８個のチャンネル・タイム・スタンプ値）のよう
に非常に大きい場合でも、パラメータ（つまり、ルー
ト）の最小値を素早く見つけるのに適しているからであ
る。
ート状態マシン３６が（スケジューラ・コマンド・レジ
スタ２８からの）チャンネル番号と（加算器３１からの
ラインＫＥＹ上の）タイム・スタンプとを押し込むと、
ヒープ・ソート・プロセス７０が開始される。プロセス
７０は、多数ある従来のヒープ・ソート・アルゴリズム
のいずれかにより実行され、その間、ヒープ・ソート状
態マシン３６はパラメータ・メモリ１８，４４内のヒー
プ（山積み）の現在のメンバーのタイム・スタンプを尋
ね、これらのタイム・スタンプをオンチップ・パラメー
タ・メモリ４４の最小アドレス（０１）に記憶して、現
在のチャンネルＣＨn に新しいタイム・スタンプを使用
するとともに従来のヒープ・ソート・アルゴリズムに従
ってタイム・スタンプによるチャンネルのソートを継続
する。ヒープ・ソートを使用する方法は、本発明に関し
ては、とりわけ有効である。というのは、ヒープ・ソー
ト技術は、記憶されるべき要素の数が本例（たとえば、
２０４８個のチャンネル・タイム・スタンプ値）のよう
に非常に大きい場合でも、パラメータ（つまり、ルー
ト）の最小値を素早く見つけるのに適しているからであ
る。
【００５３】本発明の好ましい実施の形態のよれば、ヒ
ープ・ソート・プロセス７０は、まず、ヒープ中の新し
いルート・チャンネルを識別する。特に、本発明による
オーバー・スケジュール条件での帯域幅の公平な割り当
てを行う場合、新規ヒープ・エントリが以前にスケジュ
ールされたエントリと同じタイム・スタンプを持ってい
れば、新規ヒープ・エントリが以前に置かれたエントリ
の後のヒープに置かれる。この決定の有効性は、以下の
説明から明らかになる。
ープ・ソート・プロセス７０は、まず、ヒープ中の新し
いルート・チャンネルを識別する。特に、本発明による
オーバー・スケジュール条件での帯域幅の公平な割り当
てを行う場合、新規ヒープ・エントリが以前にスケジュ
ールされたエントリと同じタイム・スタンプを持ってい
れば、新規ヒープ・エントリが以前に置かれたエントリ
の後のヒープに置かれる。この決定の有効性は、以下の
説明から明らかになる。
【００５４】ヒープ中の新規ルート・チャンネルが識別
されると、ヒープ・ソート状態マシン３６は、プロセス
７２を実行して、この新規ルート・チャンネル（Ｃ
Ｈm ）のチャンネル番号をスケジューラ出力レジスタ４
２に渡し、この新規ルート・チャンネルＣＨm のタイム
・スタンプをラインＲＫＥＹ上のデュー・コンパレータ
４０に渡し、デュー・コンパレータ４０およびスケジュ
ーラ出力レジスタ４２へのラインＶＡＬＩＤ上の制御信
号をアクティブにしてそこに有効ビットをセットする。
本発明の好ましい実施の形態によれば、ルート・チャン
ネルは、たとえそのタイム・スタンプ値がどんなに古い
ものであっても、常に送信クレジットを得る。つまり、
オーバー・スケジュール条件では、ルート・チャンネル
のタイム・スタンプは、基準タイマ３８によって提示さ
れるグローバル時刻よりずっと「古い」（つまり、小さ
い）可能性がある。次に、ヒープ・ソート・プロセス７
０は、新しいルート・チャンネルＣＨm の処理と並行し
て、残りのアクティブ・チャンネルのソートを続ける。
ソート・プロセス７０が完了すると、小さいタイム・ス
タンプ値を持つチャンネルはそのエントリがオンチップ
・パラメータ・メモリ４４に記憶され、大きい（つま
り、遅い）タイム・スタンプ値を持つチャンネルに関連
するエントリは外部パラメータ・メモリ１８に記憶され
る。この間、スケジューラ制御レジスタ４２への制御ラ
インＳＯＲＴＢＵＳＹはアクティブのままである。
されると、ヒープ・ソート状態マシン３６は、プロセス
７２を実行して、この新規ルート・チャンネル（Ｃ
Ｈm ）のチャンネル番号をスケジューラ出力レジスタ４
２に渡し、この新規ルート・チャンネルＣＨm のタイム
・スタンプをラインＲＫＥＹ上のデュー・コンパレータ
４０に渡し、デュー・コンパレータ４０およびスケジュ
ーラ出力レジスタ４２へのラインＶＡＬＩＤ上の制御信
号をアクティブにしてそこに有効ビットをセットする。
本発明の好ましい実施の形態によれば、ルート・チャン
ネルは、たとえそのタイム・スタンプ値がどんなに古い
ものであっても、常に送信クレジットを得る。つまり、
オーバー・スケジュール条件では、ルート・チャンネル
のタイム・スタンプは、基準タイマ３８によって提示さ
れるグローバル時刻よりずっと「古い」（つまり、小さ
い）可能性がある。次に、ヒープ・ソート・プロセス７
０は、新しいルート・チャンネルＣＨm の処理と並行し
て、残りのアクティブ・チャンネルのソートを続ける。
ソート・プロセス７０が完了すると、小さいタイム・ス
タンプ値を持つチャンネルはそのエントリがオンチップ
・パラメータ・メモリ４４に記憶され、大きい（つま
り、遅い）タイム・スタンプ値を持つチャンネルに関連
するエントリは外部パラメータ・メモリ１８に記憶され
る。この間、スケジューラ制御レジスタ４２への制御ラ
インＳＯＲＴＢＵＳＹはアクティブのままである。
【００５５】ソース挙動プロセッサ２４は、判定５３
（ループ方法で）を行っている間に、スケジューラ出力
レジスタ４２内の有効ビットがプロセス７２によってセ
ットされることを認識する。この結果が出る（判定５３
がＹＥＳ）と、ソース挙動プロセッサ２４は、プロセス
５６を実行して、パラメータ・メモリ１８からチャンネ
ルＣＨm 用のチャンネル状態情報の読み出しを開始す
る。これは、送信クレジットを正しく発行し、それ用の
ＡＴＭセルの送信をスケジュールするために必要であ
る。これらのパラメータを検索した後、ソース挙動プロ
セッサ２４は、判定５７を行い、スケジューラ出力レジ
スタ４２にチャンネルＣＨm が満期になったかどうかを
見させる。まだ（判定５７がＮＯ）なら、ソース挙動プ
ロセッサ２４は待ち状態５８に入り、判定５７を繰り返
す。
（ループ方法で）を行っている間に、スケジューラ出力
レジスタ４２内の有効ビットがプロセス７２によってセ
ットされることを認識する。この結果が出る（判定５３
がＹＥＳ）と、ソース挙動プロセッサ２４は、プロセス
５６を実行して、パラメータ・メモリ１８からチャンネ
ルＣＨm 用のチャンネル状態情報の読み出しを開始す
る。これは、送信クレジットを正しく発行し、それ用の
ＡＴＭセルの送信をスケジュールするために必要であ
る。これらのパラメータを検索した後、ソース挙動プロ
セッサ２４は、判定５７を行い、スケジューラ出力レジ
スタ４２にチャンネルＣＨm が満期になったかどうかを
見させる。まだ（判定５７がＮＯ）なら、ソース挙動プ
ロセッサ２４は待ち状態５８に入り、判定５７を繰り返
す。
【００５６】そうこうするうちに、デュー・コンパレー
タ４０がヒープ・ソート状態マシン３６からラインＶＡ
ＬＩＤ上のアクティブ信号を受け取り、デュー・コンパ
レータ４０は、チャンネルＣＨm が満期になったかどう
かを決める判定７３の実行を開始する。判定７３は、最
も単純な場合、チャンネルＣＨm と関連する（かつ、ヒ
ープ・ソート状態マシン３６からラインＲＫＥＹ上で通
信される）タイム・スタンプを基準タイマ３８から通信
されているグローバル時刻と比較する。まだグローバル
時刻がルート・チャンネルＣＨm 用のタイム・スタンプ
値に達していなければ（判定７３がＮＯなら）、デュー
・コンパレータ４０はプロセス７４でラインＣＬＫ上の
クロック信号の次のサイクルを待ち、判定７３を繰り返
す。グローバル時刻がラインＲＫＥＹ上のタイム・スタ
ンプ値に到達するか過ぎていれば（判定７３がＹＥ
Ｓ）、デュー・コンパレータ４０は、プロセス７６でラ
インＤＵＥ上にスケジューラ出力レジスタ４へのデュー
信号を発行する。
タ４０がヒープ・ソート状態マシン３６からラインＶＡ
ＬＩＤ上のアクティブ信号を受け取り、デュー・コンパ
レータ４０は、チャンネルＣＨm が満期になったかどう
かを決める判定７３の実行を開始する。判定７３は、最
も単純な場合、チャンネルＣＨm と関連する（かつ、ヒ
ープ・ソート状態マシン３６からラインＲＫＥＹ上で通
信される）タイム・スタンプを基準タイマ３８から通信
されているグローバル時刻と比較する。まだグローバル
時刻がルート・チャンネルＣＨm 用のタイム・スタンプ
値に達していなければ（判定７３がＮＯなら）、デュー
・コンパレータ４０はプロセス７４でラインＣＬＫ上の
クロック信号の次のサイクルを待ち、判定７３を繰り返
す。グローバル時刻がラインＲＫＥＹ上のタイム・スタ
ンプ値に到達するか過ぎていれば（判定７３がＹＥ
Ｓ）、デュー・コンパレータ４０は、プロセス７６でラ
インＤＵＥ上にスケジューラ出力レジスタ４へのデュー
信号を発行する。
【００５７】しかしながら、本発明の好ましい実施の形
態によれば、基準タイマー３８は、ラインＣＬＫ上のク
ロック信号の各サイクルごとに進む単純なカウンタであ
り、フル・カウント状態に到達すると、循環（wrap ar
ound）する。デュー・コンパレータ４０がラインＲＫＥ
Ｙ上のタイム・スタンプの値を基準タイマ３８の出力と
比較するだけであれば、チャンネルＣＨm が満期になっ
ても、基準タイマ３８が循環してゼロに戻ってしまえ
ば、気づかれないこともあり得る。本発明と関連してわ
かったことであるが、基準タイマからの出力のワード幅
をラインＲＫＥＹ上のタイム・スタンプの幅に対してか
つラインＯＦＦＳＥＴ上のオフセット部分の幅に対して
相対的に選択することによって、循環に由来する多くの
中間的状態を避けることができる。
態によれば、基準タイマー３８は、ラインＣＬＫ上のク
ロック信号の各サイクルごとに進む単純なカウンタであ
り、フル・カウント状態に到達すると、循環（wrap ar
ound）する。デュー・コンパレータ４０がラインＲＫＥ
Ｙ上のタイム・スタンプの値を基準タイマ３８の出力と
比較するだけであれば、チャンネルＣＨm が満期になっ
ても、基準タイマ３８が循環してゼロに戻ってしまえ
ば、気づかれないこともあり得る。本発明と関連してわ
かったことであるが、基準タイマからの出力のワード幅
をラインＲＫＥＹ上のタイム・スタンプの幅に対してか
つラインＯＦＦＳＥＴ上のオフセット部分の幅に対して
相対的に選択することによって、循環に由来する多くの
中間的状態を避けることができる。
【００５８】本発明の好ましい実施の形態によれば、ラ
インＲＫＥＹ上のタイム・スタンプのワード幅は、最上
位ビット部分で、基準タイマ３８の出力でのワード幅よ
り１ビット多くなるよう選択される。図３の例では、基
準タイマ３８の出力はｋビット幅であり、ラインＲＫＥ
Ｙはｋ＋１になる。この関係により、タイム・スタンプ
値の範囲は基準タイマの出力範囲を２倍にすることがで
きる。たとえば、クロック時刻を参照して、ラインＲＫ
ＥＹ上のタイム・スタンプは２４時間クロック値（たと
えば、１３：３０は午後１：３０を表す。）であると考
えることができ、一方、基準タイマ３８の出力は２４時
間クロック値に対応する。このような基準タイマ３８に
おける循環が、デュー・コンパレータ４０により実行さ
れる比較において簡単に考えられる。
インＲＫＥＹ上のタイム・スタンプのワード幅は、最上
位ビット部分で、基準タイマ３８の出力でのワード幅よ
り１ビット多くなるよう選択される。図３の例では、基
準タイマ３８の出力はｋビット幅であり、ラインＲＫＥ
Ｙはｋ＋１になる。この関係により、タイム・スタンプ
値の範囲は基準タイマの出力範囲を２倍にすることがで
きる。たとえば、クロック時刻を参照して、ラインＲＫ
ＥＹ上のタイム・スタンプは２４時間クロック値（たと
えば、１３：３０は午後１：３０を表す。）であると考
えることができ、一方、基準タイマ３８の出力は２４時
間クロック値に対応する。このような基準タイマ３８に
おける循環が、デュー・コンパレータ４０により実行さ
れる比較において簡単に考えられる。
【００５９】次に、基準タイマ３８の出力におけるワー
ド幅は、ラインＯＦＦＳＥＴ上のオフセット（この例で
は、ｋ−１）より１ビット広くなっている。これによ
り、チャンネルをスケジュールするのに、基準タイマ３
８の値から基準タイマ３８の範囲の半分以上離れること
はない。したがって、デュー・コンパレータ４０は、現
在のグローバル時刻から基準タイマ３８の範囲の半分し
か後ろを見ない。この考え方が、次のような特徴と組み
合わせて使用される。ヒープ・ソート状態マシン３６が
タイム・スタンプのソートを行う場合、基準タイマ３８
がその範囲の前半の値を出力するときには、最上位タイ
ム・スタンプ・ビットを使用せず、基準タイマ３８がそ
の範囲の後半の値を出力するとき（つまり、ＭＳＢ＝
１）には、最上位タイム・スタンプ・ビットを使用す
る。各タイム・スタンプは各セル処理が終了するごとに
ヒープ・ソート状態マシン３６によってソートされるの
で、このような考え方によって、基準タイマの循環が間
違った結果をもたらすことを確実になくすことができ
る。
ド幅は、ラインＯＦＦＳＥＴ上のオフセット（この例で
は、ｋ−１）より１ビット広くなっている。これによ
り、チャンネルをスケジュールするのに、基準タイマ３
８の値から基準タイマ３８の範囲の半分以上離れること
はない。したがって、デュー・コンパレータ４０は、現
在のグローバル時刻から基準タイマ３８の範囲の半分し
か後ろを見ない。この考え方が、次のような特徴と組み
合わせて使用される。ヒープ・ソート状態マシン３６が
タイム・スタンプのソートを行う場合、基準タイマ３８
がその範囲の前半の値を出力するときには、最上位タイ
ム・スタンプ・ビットを使用せず、基準タイマ３８がそ
の範囲の後半の値を出力するとき（つまり、ＭＳＢ＝
１）には、最上位タイム・スタンプ・ビットを使用す
る。各タイム・スタンプは各セル処理が終了するごとに
ヒープ・ソート状態マシン３６によってソートされるの
で、このような考え方によって、基準タイマの循環が間
違った結果をもたらすことを確実になくすことができ
る。
【００６０】これらの操作の結果、デュー・コンパレー
タ４０の操作により、基準タイマ３８の出力におけるｋ
ビット値とラインＲＫＥＹ上のルート・チャンネルＣＨ
m のタイム・スタンプのｋ＋１ビットとの比較の信頼度
を高くすることができる。判定７３の結果、ルート・チ
ャンネルＣＨm が満期（判定７３がＹＥＳ）であれば、
デュー・コンパレータ４０は、スケジューラ出力レジス
タ４２に対してラインＤＵＥ上にアクティブ信号を発行
し、そこにビットをセットし、それが次のパスで判定５
７においてソース挙動プロセッサ２４によって問われ
る。チャンネルＣＨm 用のデュー信号が発行されたこと
（判定５７がＹＥＳ）が検出されると、ソース挙動プロ
セッサ２４は、チャンネルＣＨm に対する送信クレジッ
トをプロセス６０で発行し、チャンネルＣＨm 用のチャ
ンネル識別子をプロセス５６で検索されたそのＡＴＭ送
信パラメータと一緒に従来方法でＳＡＲデバイス１２に
供給する。
タ４０の操作により、基準タイマ３８の出力におけるｋ
ビット値とラインＲＫＥＹ上のルート・チャンネルＣＨ
m のタイム・スタンプのｋ＋１ビットとの比較の信頼度
を高くすることができる。判定７３の結果、ルート・チ
ャンネルＣＨm が満期（判定７３がＹＥＳ）であれば、
デュー・コンパレータ４０は、スケジューラ出力レジス
タ４２に対してラインＤＵＥ上にアクティブ信号を発行
し、そこにビットをセットし、それが次のパスで判定５
７においてソース挙動プロセッサ２４によって問われ
る。チャンネルＣＨm 用のデュー信号が発行されたこと
（判定５７がＹＥＳ）が検出されると、ソース挙動プロ
セッサ２４は、チャンネルＣＨm に対する送信クレジッ
トをプロセス６０で発行し、チャンネルＣＨm 用のチャ
ンネル識別子をプロセス５６で検索されたそのＡＴＭ送
信パラメータと一緒に従来方法でＳＡＲデバイス１２に
供給する。
【００６１】次のプロセス６０で、ソース挙動プロセッ
サ２４がチャンネルＣＨm に対する送信クレジットを発
行し、プロセス４８からのプロセスが繰り返される。ソ
ース挙動プロセッサ２４は、必要なら、チャンネルＣＨ
m 用のＡＣＲ値を検索して更新する。このプロセスが繰
り返され、プロセス７７でヒープ・ソート状態マシン３
６によるヒープ・ソートが終了し、関連する制御ライン
ＳＯＲＴＢＵＳＹがクリアされ、これにより、判定４９
から再度プロセス５２に制御が移る。
サ２４がチャンネルＣＨm に対する送信クレジットを発
行し、プロセス４８からのプロセスが繰り返される。ソ
ース挙動プロセッサ２４は、必要なら、チャンネルＣＨ
m 用のＡＣＲ値を検索して更新する。このプロセスが繰
り返され、プロセス７７でヒープ・ソート状態マシン３
６によるヒープ・ソートが終了し、関連する制御ライン
ＳＯＲＴＢＵＳＹがクリアされ、これにより、判定４９
から再度プロセス５２に制御が移る。
【００６２】上述したようにソース挙動プロセッサ２４
によって送信クレジットが発行されると、ソース挙動プ
ロセッサ２４は、ＡＢＲセル用の送信機会が出るときに
ＳＡＲデバイス１２によって提示されるかも知れない指
示をセットする。たとえば、ソース挙動プロセッサ２４
は、送信されるべきセルと関連して、発行された送信ク
レジットを含む「次のセル・レジスタ」を含むことが好
ましい。ＡＢＲチャンネル用の送信機会がＳＡＲデバイ
ス１２によって検出されると、ＳＡＲデバイス１２は、
この次のセル・レジスタに、ＡＢＲセルがスケジューラ
１４によって送信用にスケジュールされているかを決め
させる。そうであるなら、ＳＡＲデバイス１２はＡＴＭ
プロトコルに従ってこのセルの送信を行わせることがで
きる。もちろん、送信機会が来なければ（たとえば、使
用可能帯域幅がすべてＣＢＲチャンネルによって占めら
れていれば）、スケジューラ１４のこの状態がしばらく
続く。
によって送信クレジットが発行されると、ソース挙動プ
ロセッサ２４は、ＡＢＲセル用の送信機会が出るときに
ＳＡＲデバイス１２によって提示されるかも知れない指
示をセットする。たとえば、ソース挙動プロセッサ２４
は、送信されるべきセルと関連して、発行された送信ク
レジットを含む「次のセル・レジスタ」を含むことが好
ましい。ＡＢＲチャンネル用の送信機会がＳＡＲデバイ
ス１２によって検出されると、ＳＡＲデバイス１２は、
この次のセル・レジスタに、ＡＢＲセルがスケジューラ
１４によって送信用にスケジュールされているかを決め
させる。そうであるなら、ＳＡＲデバイス１２はＡＴＭ
プロトコルに従ってこのセルの送信を行わせることがで
きる。もちろん、送信機会が来なければ（たとえば、使
用可能帯域幅がすべてＣＢＲチャンネルによって占めら
れていれば）、スケジューラ１４のこの状態がしばらく
続く。
【００６３】上述したように、本発明の好ましい実施の
形態により、タイム・スタンプの決定のための適当なベ
ース値を選択することによって、オーバー・スケジュー
ル条件において帯域幅を公平に割り当てることができ
る。まとめると、この帯域幅の公平な割り当ては、３つ
の規則を使うことによってもたらされる。すなわち、 １）タイム・スタンプ値が現在のグローバル時刻より古
い（つまり、小さい）チャンネルとして定義される「オ
ーバー・ デュー」送信が、決して落ちない。ルート・チ
ャンネルは、そのタイム・スタンプ値に関係なく、常に
送信クレジットを得ることができる。 ２）ヒープ・データ構造のソートが次のように行われ
る。より古い（つまり、より早い時点で押し込まれた）
チャンネルと同じタイム・スタンプを持つ新しい（つま
り、より最近ヒープに押し込まれた）チャンネルが、ヒ
ープにおいて、より古いチャンネルの後に置かれる。 ３）有効セル送信レートが、タイム・スタンプ値の計算
にオフセット値がベースとされるＡＣＲ値より少なくな
る。それは、オフセット値と合計されるベースが選択さ
れて、新しいタイム・スタンプ値が決定されるからであ
る。このような選択が行われることによって、生成され
た時点で既に満期が過ぎたタイム・スタンプを前進させ
ることができる。 これらの規則は、図４および図５の方法による動作に関
連して上述したように、オーバー・スケジュール条件に
おいても、帯域幅の公平な割り当てをする結果となる。
この結果について、３つのＡＢＲチャンネルＣＨ１，Ｃ
Ｈ２，ＣＨ３がオーバー・スケジュール条件にある例を
用いて、１００クロック・サイクルごとの速さで送信ク
レジットが新しいセルに発行されるシステムに対して、
以下に説明する。この例において、チャンネルＣＨ１
は、そのセル・レートとして帯域幅の１００％を要求し
ており、これは、本例において、１００クロック・サイ
クルのタイム・スタンプ・オフセットに対応する。チャ
ンネルＣＨ２は帯域幅の２００％を要求している。これ
は、５０クロック・サイクル（１００サイクル・レート
の２倍の速さ）のオフセットに対応する。そして、チャ
ンネルＣＨ３は、ライン・レートの２０％しか要求して
おらず、そのタイム・スタンプ・オフセットは５００サ
イクル（１００サイクル・レートの５分の１の遅さ）で
ある。
形態により、タイム・スタンプの決定のための適当なベ
ース値を選択することによって、オーバー・スケジュー
ル条件において帯域幅を公平に割り当てることができ
る。まとめると、この帯域幅の公平な割り当ては、３つ
の規則を使うことによってもたらされる。すなわち、 １）タイム・スタンプ値が現在のグローバル時刻より古
い（つまり、小さい）チャンネルとして定義される「オ
ーバー・ デュー」送信が、決して落ちない。ルート・チ
ャンネルは、そのタイム・スタンプ値に関係なく、常に
送信クレジットを得ることができる。 ２）ヒープ・データ構造のソートが次のように行われ
る。より古い（つまり、より早い時点で押し込まれた）
チャンネルと同じタイム・スタンプを持つ新しい（つま
り、より最近ヒープに押し込まれた）チャンネルが、ヒ
ープにおいて、より古いチャンネルの後に置かれる。 ３）有効セル送信レートが、タイム・スタンプ値の計算
にオフセット値がベースとされるＡＣＲ値より少なくな
る。それは、オフセット値と合計されるベースが選択さ
れて、新しいタイム・スタンプ値が決定されるからであ
る。このような選択が行われることによって、生成され
た時点で既に満期が過ぎたタイム・スタンプを前進させ
ることができる。 これらの規則は、図４および図５の方法による動作に関
連して上述したように、オーバー・スケジュール条件に
おいても、帯域幅の公平な割り当てをする結果となる。
この結果について、３つのＡＢＲチャンネルＣＨ１，Ｃ
Ｈ２，ＣＨ３がオーバー・スケジュール条件にある例を
用いて、１００クロック・サイクルごとの速さで送信ク
レジットが新しいセルに発行されるシステムに対して、
以下に説明する。この例において、チャンネルＣＨ１
は、そのセル・レートとして帯域幅の１００％を要求し
ており、これは、本例において、１００クロック・サイ
クルのタイム・スタンプ・オフセットに対応する。チャ
ンネルＣＨ２は帯域幅の２００％を要求している。これ
は、５０クロック・サイクル（１００サイクル・レート
の２倍の速さ）のオフセットに対応する。そして、チャ
ンネルＣＨ３は、ライン・レートの２０％しか要求して
おらず、そのタイム・スタンプ・オフセットは５００サ
イクル（１００サイクル・レートの５分の１の遅さ）で
ある。
【００６４】下の表は、本発明の好ましい実施の形態に
よるスケジューラ１４の動作を示す。
よるスケジューラ１４の動作を示す。
【００６５】
【表３】
【００６６】上の例において、グローバル時刻値（Ｇ
Ｔ）は、ＧＴ＝０（クロックサイクル数で）から始ま
る。ＧＴ＝５０になるまでは、単にチャンネルＣＨ１〜
ＣＨ３をセットアップするだけであり、送信クレジット
は発行されない。この例において、セルが送信クレジッ
トを受け取る頻度は、上述したように１００クロック・
サイクルを越えない。ＧＴ＝０において、チャンネルＣ
Ｈ１は、その最初のタイム・スタンプを受け取り、この
例では１００である（セットアップ中、ベースはゼ
ロ）。ＧＴ＝５において、チャンネルＣＨ２が、その最
初のタイム・スタンプ（この例では、５０）を受け取る
（ここでも、セットアップ中につきベースはゼロであ
る。）。ＧＴ＝５におけるルート・チャンネルはＣＨ１
であり、タイム・スタンプは１００である。というの
は、このチャンネルがタイム・スタンプを持つ唯一のチ
ャンネルである（したがって、このチャンネルが最小の
タイム・スタンプ値を持つ）からである。同様に、ＧＴ
＝１０において、チャンネルＣＨ３がそのタイム・スタ
ンプ“５００”を受け取る。この時点のルート・チャン
ネルはＣＨ２である。というのは、そのタイム・スタン
プ値が最小だからである。このようにして、本例では、
各チャンネルＣＨ１，ＣＨ２，ＣＨ３が、所望のＡＣＲ
に対応する各オフセットに等しい初期タイム・スタンプ
を受け取る。ＧＴ＝０，ＧＴ＝５，ＧＴ＝１０におい
て、送信クレジットは発行されない。というのは、どの
タイム・スタンプも満期になっていないから（ルート・
タイム・スタンプは、これらのどの場合においても、グ
ローバル時刻より大きい）からである。
Ｔ）は、ＧＴ＝０（クロックサイクル数で）から始ま
る。ＧＴ＝５０になるまでは、単にチャンネルＣＨ１〜
ＣＨ３をセットアップするだけであり、送信クレジット
は発行されない。この例において、セルが送信クレジッ
トを受け取る頻度は、上述したように１００クロック・
サイクルを越えない。ＧＴ＝０において、チャンネルＣ
Ｈ１は、その最初のタイム・スタンプを受け取り、この
例では１００である（セットアップ中、ベースはゼ
ロ）。ＧＴ＝５において、チャンネルＣＨ２が、その最
初のタイム・スタンプ（この例では、５０）を受け取る
（ここでも、セットアップ中につきベースはゼロであ
る。）。ＧＴ＝５におけるルート・チャンネルはＣＨ１
であり、タイム・スタンプは１００である。というの
は、このチャンネルがタイム・スタンプを持つ唯一のチ
ャンネルである（したがって、このチャンネルが最小の
タイム・スタンプ値を持つ）からである。同様に、ＧＴ
＝１０において、チャンネルＣＨ３がそのタイム・スタ
ンプ“５００”を受け取る。この時点のルート・チャン
ネルはＣＨ２である。というのは、そのタイム・スタン
プ値が最小だからである。このようにして、本例では、
各チャンネルＣＨ１，ＣＨ２，ＣＨ３が、所望のＡＣＲ
に対応する各オフセットに等しい初期タイム・スタンプ
を受け取る。ＧＴ＝０，ＧＴ＝５，ＧＴ＝１０におい
て、送信クレジットは発行されない。というのは、どの
タイム・スタンプも満期になっていないから（ルート・
タイム・スタンプは、これらのどの場合においても、グ
ローバル時刻より大きい）からである。
【００６７】ＧＴ＝５０において、ルート・チャンネル
ＣＨ２が満期になる。というのは、そのタイム・スタン
プがグローバル時刻と等しくなるからである。このよう
に、チャンネルＣＨ２は、ＧＴ＝５０において送信クレ
ジットを受け取り、また、新しいタイム・スタンプを受
け取る。図５において、プロセス６６を実行することに
よって、新しいタイム・スタンプを生成する際の正しい
ベースを決定する。まず、プロセス７８が、未来のクレ
ジット時刻ＦＣＴを最後のタイム・スタンプ値＋オフセ
ットの合計として決定する。合計は１００（５０＋５
０）である。この未来のクレジット時刻ＦＣＴは、現在
のグローバル時刻より小さくはないので、以前のタイム
・スタンプ値がベースとして使用されて、新しいタイム
・スタンプ“１００”（５０＋５０）が生成される。表
に示された通りである（もちろん、この場合は、グロー
バル時刻ＧＴを使用しても同じ結果になる。）。送信ク
レジットが満期になるＧＴ＝１５０において、ルート・
チャンネルはチャンネルＣＨ１であり、タイム・スタン
プは１００である。一方、チャンネルＣＨ２も、ＧＴ＝
５０で決定されたようにタイム・スタンプ“１００”を
持つ。チャンネルＣＨ１がルートになる。なぜなら、先
に述べたように、同じタイム・スタンプを持つ新しくオ
ーダーされたチャンネルは、その前にオーダーされたチ
ャンネルの後に置かれるからである。したがって、ＧＴ
＝１５０において、チャンネルＣＨ１は送信クレジット
と新しいタイム・スタンプ“２００”とを受け取る（先
のタイム・スタンプ“１００”＋チャンネルＣＨ１のオ
フセット“１００”、それはグローバル時刻ＧＴ＝１５
０より大きいので、先のタイム・スタンプ“１００”が
ベースとして使用される）。
ＣＨ２が満期になる。というのは、そのタイム・スタン
プがグローバル時刻と等しくなるからである。このよう
に、チャンネルＣＨ２は、ＧＴ＝５０において送信クレ
ジットを受け取り、また、新しいタイム・スタンプを受
け取る。図５において、プロセス６６を実行することに
よって、新しいタイム・スタンプを生成する際の正しい
ベースを決定する。まず、プロセス７８が、未来のクレ
ジット時刻ＦＣＴを最後のタイム・スタンプ値＋オフセ
ットの合計として決定する。合計は１００（５０＋５
０）である。この未来のクレジット時刻ＦＣＴは、現在
のグローバル時刻より小さくはないので、以前のタイム
・スタンプ値がベースとして使用されて、新しいタイム
・スタンプ“１００”（５０＋５０）が生成される。表
に示された通りである（もちろん、この場合は、グロー
バル時刻ＧＴを使用しても同じ結果になる。）。送信ク
レジットが満期になるＧＴ＝１５０において、ルート・
チャンネルはチャンネルＣＨ１であり、タイム・スタン
プは１００である。一方、チャンネルＣＨ２も、ＧＴ＝
５０で決定されたようにタイム・スタンプ“１００”を
持つ。チャンネルＣＨ１がルートになる。なぜなら、先
に述べたように、同じタイム・スタンプを持つ新しくオ
ーダーされたチャンネルは、その前にオーダーされたチ
ャンネルの後に置かれるからである。したがって、ＧＴ
＝１５０において、チャンネルＣＨ１は送信クレジット
と新しいタイム・スタンプ“２００”とを受け取る（先
のタイム・スタンプ“１００”＋チャンネルＣＨ１のオ
フセット“１００”、それはグローバル時刻ＧＴ＝１５
０より大きいので、先のタイム・スタンプ“１００”が
ベースとして使用される）。
【００６８】ＧＴ＝２５０において、ルート・チャンネ
ルＣＨ２が満期になる。タイム・スタンプが１００であ
るので、送信クレジットを受け取る。この時点で、チャ
ンネルＣＨ２は新しいタイム・スタンプを受け取る。上
述したように、ベースがまず選ばれなければならない。
この場合、プロセス７８が、まず、未来のクジット時刻
ＦＣＴを１５０（１００＋５０）と決める。この未来の
クレジット時刻ＦＣＴは、現在のグローバル時刻（ＧＴ
＝２５０）より小さいので、グローバル時刻ＧＴがベー
スとして使用されて、表に示されたように、新しいタイ
ム・スタンプ３００（２５０＋５０）が生成される。
ルＣＨ２が満期になる。タイム・スタンプが１００であ
るので、送信クレジットを受け取る。この時点で、チャ
ンネルＣＨ２は新しいタイム・スタンプを受け取る。上
述したように、ベースがまず選ばれなければならない。
この場合、プロセス７８が、まず、未来のクジット時刻
ＦＣＴを１５０（１００＋５０）と決める。この未来の
クレジット時刻ＦＣＴは、現在のグローバル時刻（ＧＴ
＝２５０）より小さいので、グローバル時刻ＧＴがベー
スとして使用されて、表に示されたように、新しいタイ
ム・スタンプ３００（２５０＋５０）が生成される。
【００６９】送信クレジットの発行の動作および新規タ
イム・スタンプ値の引き出しがこのように１００クロッ
ク・サイクルごとに続く結果、表のようになる。表に示
されたように、たとえば、ＧＴ＝６５０において、チャ
ンネルＣＨ３がルート・チャンネルになり、満期にな
る。というのは、そのタイム・スタンプ値がその時点
“５００”で、（より遅く、ＧＴ＝４５０に生成され
た）チャンネルＣＨ２のタイム・スタンプより先の順番
にあるからである。
イム・スタンプ値の引き出しがこのように１００クロッ
ク・サイクルごとに続く結果、表のようになる。表に示
されたように、たとえば、ＧＴ＝６５０において、チャ
ンネルＣＨ３がルート・チャンネルになり、満期にな
る。というのは、そのタイム・スタンプ値がその時点
“５００”で、（より遅く、ＧＴ＝４５０に生成され
た）チャンネルＣＨ２のタイム・スタンプより先の順番
にあるからである。
【００７０】本発明の好ましい実施の形態による方法が
公平であることは、時間を追いながら表の「クレジット
・チャンネル」欄を見ればわかることである。この表か
ら明らかなように、各チャンネルは時間に従ってクレジ
ットされ（ＧＴ＝２５０で始まる、初期遷移の後）、Ｃ
Ｈ２，ＣＨ１，ＣＨ２，ＣＨ１，ＣＨ３というシーケン
スとなる。このシーケンスに従って、チャンネルＣＨ３
は、送信クレジットを５回に１回受け取り、これはライ
ン・レートの２０％（ＣＨ３の要求されたライン・レー
ト）となる。他のチャンネルＣＨ１，ＣＨ２は（それぞ
れライン・レートの１００％および２００％を要求して
おり）使用可能帯域幅で満足できない。これらのチャン
ネルは、チャンネルＣＨ３への割り当ての後に残ったラ
イン・レートを分け合うことになり、チャンネルＣＨ
１，ＣＨ２はそれぞれ、使用可能帯域幅の４０％を受け
取る。このようなやり方が公平であることは、上述の全
体の説明に従うものであり、当業者にとって明らかであ
ろう。
公平であることは、時間を追いながら表の「クレジット
・チャンネル」欄を見ればわかることである。この表か
ら明らかなように、各チャンネルは時間に従ってクレジ
ットされ（ＧＴ＝２５０で始まる、初期遷移の後）、Ｃ
Ｈ２，ＣＨ１，ＣＨ２，ＣＨ１，ＣＨ３というシーケン
スとなる。このシーケンスに従って、チャンネルＣＨ３
は、送信クレジットを５回に１回受け取り、これはライ
ン・レートの２０％（ＣＨ３の要求されたライン・レー
ト）となる。他のチャンネルＣＨ１，ＣＨ２は（それぞ
れライン・レートの１００％および２００％を要求して
おり）使用可能帯域幅で満足できない。これらのチャン
ネルは、チャンネルＣＨ３への割り当ての後に残ったラ
イン・レートを分け合うことになり、チャンネルＣＨ
１，ＣＨ２はそれぞれ、使用可能帯域幅の４０％を受け
取る。このようなやり方が公平であることは、上述の全
体の説明に従うものであり、当業者にとって明らかであ
ろう。
【００７１】したがって、本発明の好ましい実施の形態
のよれば、スケジューラ１４がＳＡＲデバイスと組み合
わされて行うＡＴＭ送信のスケジューリングは、ＡＴＭ
通信を行う上で非常に有利である。第１に、本発明は、
アベイラブル・ビット・レート（ＡＢＲ）非同期転送モ
ード（ＡＴＭ）送信を効率よく公平にスケジュールする
ことを提供する。たとえば、本発明の好ましい実施の形
態の例として、近代的ファイバ光設備で得られる１５５
Ｍビットのライン・レートに簡単に合わせることがで
き、工業規格を十分に満足させることができる。第２
に、ヒープ記憶技術を使用することによって、メモリ・
リソースをかなり減らすことができる。この技術がなけ
れば、扱われるべき可能なチャンネルのそれぞれにカウ
ンタを装備しなければならない。
のよれば、スケジューラ１４がＳＡＲデバイスと組み合
わされて行うＡＴＭ送信のスケジューリングは、ＡＴＭ
通信を行う上で非常に有利である。第１に、本発明は、
アベイラブル・ビット・レート（ＡＢＲ）非同期転送モ
ード（ＡＴＭ）送信を効率よく公平にスケジュールする
ことを提供する。たとえば、本発明の好ましい実施の形
態の例として、近代的ファイバ光設備で得られる１５５
Ｍビットのライン・レートに簡単に合わせることがで
き、工業規格を十分に満足させることができる。第２
に、ヒープ記憶技術を使用することによって、メモリ・
リソースをかなり減らすことができる。この技術がなけ
れば、扱われるべき可能なチャンネルのそれぞれにカウ
ンタを装備しなければならない。
【００７２】また、本発明の好ましい実施の形態によっ
て提供されるスケジューリング機能は、高度のスケーラ
ビリティ（scalability ）を提供する。すなわち、間も
なく満期になるチャンネル用にはオンチップ・パラメー
タ・メモリを使用し、より遅くスケジュールされるチャ
ンネルにはオフチップ・パラメータ・メモリを使用する
ので、オフチップ・パラメータ・メモリのサイズを拡張
するだけでチャンネルの追加を簡単に行うことができ
る。さらにまた、本発明をＡＴＭセルのスケジューリン
グに導入すれば、チャンネルに対するセルの実際のスケ
ジューリングにおける遅延が同じチャンネルの複数のセ
ルに渡って蓄積されることがない。
て提供されるスケジューリング機能は、高度のスケーラ
ビリティ（scalability ）を提供する。すなわち、間も
なく満期になるチャンネル用にはオンチップ・パラメー
タ・メモリを使用し、より遅くスケジュールされるチャ
ンネルにはオフチップ・パラメータ・メモリを使用する
ので、オフチップ・パラメータ・メモリのサイズを拡張
するだけでチャンネルの追加を簡単に行うことができ
る。さらにまた、本発明をＡＴＭセルのスケジューリン
グに導入すれば、チャンネルに対するセルの実際のスケ
ジューリングにおける遅延が同じチャンネルの複数のセ
ルに渡って蓄積されることがない。
【００７３】また、本発明の好ましい実施の形態は、Ａ
ＢＲチャンネルに対する許可されたセル・レートを割り
当てる際に、多数のＡＢＲチャンネルからの要求を考慮
し、また、一定ビット・レート・チャンネルのように固
定ビット・レート・チャンネルを考慮し、特に、所望さ
れる送信容量が通信設備の帯域幅を越える場合に、公平
に割り当てを行う。この公平さが得られるのは、各チャ
ンネルに対して要求されるＡＣＲオフセットに加算され
るべきベース値を選択することによって、サイクルを効
率的に使用できること、また、従来のＡＴＭネットワー
クにおいて行われるフロー制御アルゴリズムにおいて考
慮されていないことを考慮しているからである。
ＢＲチャンネルに対する許可されたセル・レートを割り
当てる際に、多数のＡＢＲチャンネルからの要求を考慮
し、また、一定ビット・レート・チャンネルのように固
定ビット・レート・チャンネルを考慮し、特に、所望さ
れる送信容量が通信設備の帯域幅を越える場合に、公平
に割り当てを行う。この公平さが得られるのは、各チャ
ンネルに対して要求されるＡＣＲオフセットに加算され
るべきベース値を選択することによって、サイクルを効
率的に使用できること、また、従来のＡＴＭネットワー
クにおいて行われるフロー制御アルゴリズムにおいて考
慮されていないことを考慮しているからである。
【００７４】このように、本発明は、複数の通信チャン
ネルと関連するパケット・セルの送信をスケジュールす
る方法であって、複数のチャンネル・エントリをヒープ
・メモリ内にソートするステップであって、前記各チャ
ンネル・エントリが、各チャンネルと関連するタイム・
スタンプ値を含み、該タイム・スタンプ値が、関連チャ
ンネルに対するセルの送信が次に満期になる時刻を示
し、前記ソート・ステップが、次の満期になるチャンネ
ルに対応するルート・チャンネル・エントリを識別す
る、ステップと、前記ルート・チャンネル・エントリの
タイム・スタンプ値を基準タイマによって生成されたグ
ローバル時刻と比較するステップと、該比較ステップに
応答して、前記グローバル時刻が少なくとも前記ルート
・チャンネル・エントリのタイム・スタンプ値に達した
ことを決定し、前記ルート・チャンネル・エントリと関
連するチャンネルに対して送信クレジットを発行するス
テップと、を含む。
ネルと関連するパケット・セルの送信をスケジュールす
る方法であって、複数のチャンネル・エントリをヒープ
・メモリ内にソートするステップであって、前記各チャ
ンネル・エントリが、各チャンネルと関連するタイム・
スタンプ値を含み、該タイム・スタンプ値が、関連チャ
ンネルに対するセルの送信が次に満期になる時刻を示
し、前記ソート・ステップが、次の満期になるチャンネ
ルに対応するルート・チャンネル・エントリを識別す
る、ステップと、前記ルート・チャンネル・エントリの
タイム・スタンプ値を基準タイマによって生成されたグ
ローバル時刻と比較するステップと、該比較ステップに
応答して、前記グローバル時刻が少なくとも前記ルート
・チャンネル・エントリのタイム・スタンプ値に達した
ことを決定し、前記ルート・チャンネル・エントリと関
連するチャンネルに対して送信クレジットを発行するス
テップと、を含む。
【００７５】上述した方法は、送信クレジットを発行す
るステップの後に、前記ルート・チャンネル・エントリ
と関連する前記チャンネルに対して、許可されたセル・
レート値をパラメータ・メモリから検索するステップ
と、 前記ルート・チャンネル・エントリと関連する前
記チャンネルに対する新規タイム・スタンプ値を引き出
すステップと、前記ソート・ステップ，前記比較ステッ
プおよび前記発行ステップを反復するステップと、をさ
らに含む、
るステップの後に、前記ルート・チャンネル・エントリ
と関連する前記チャンネルに対して、許可されたセル・
レート値をパラメータ・メモリから検索するステップ
と、 前記ルート・チャンネル・エントリと関連する前
記チャンネルに対する新規タイム・スタンプ値を引き出
すステップと、前記ソート・ステップ，前記比較ステッ
プおよび前記発行ステップを反復するステップと、をさ
らに含む、
【００７６】上述した方法では、前記引き出しステップ
が、スケジューラ・クロック周波数を前記許可されたセ
ル・レート値で割った値に基づいてオフセット・タイム
・スタンプ値を生成するステップと、前記オフセット・
タイム・スタンプ値をベース・タイム・スタンプ値に加
算して前記新規タイム・スタンプ値を生成するステップ
と、をさらに含む。
が、スケジューラ・クロック周波数を前記許可されたセ
ル・レート値で割った値に基づいてオフセット・タイム
・スタンプ値を生成するステップと、前記オフセット・
タイム・スタンプ値をベース・タイム・スタンプ値に加
算して前記新規タイム・スタンプ値を生成するステップ
と、をさらに含む。
【００７７】上述した方法では、前記ベース・タイム・
スタンプ値が前記ルート・チャンネル・エントリのタイ
ム・スタンプ値と等しい。
スタンプ値が前記ルート・チャンネル・エントリのタイ
ム・スタンプ値と等しい。
【００７８】上述した方法では、前記ベース・タイム・
スタンプ値が前記グローバル時刻と等しい。
スタンプ値が前記グローバル時刻と等しい。
【００７９】上述した方法では、前記ソート・ステップ
が、前記複数のチャンネルの第１および第２のグループ
を識別するステップであって、前記複数のチャンネルの
前記第１のグループが、前記複数のチャンネルの前記第
２のグループのタイム・スタンプ値より早く満期になる
タイム・スタンプ値を有する、ステップと、前記複数の
チャンネルの前記第１のグループに対するチャンネル・
エントリを第１のパラメータ・メモリに記憶するステッ
プと、前記複数のチャンネルの前記第２グループに対す
るチャンネル・エントリを第２のパラメータ・メモリに
記憶するステップと、を含む。
が、前記複数のチャンネルの第１および第２のグループ
を識別するステップであって、前記複数のチャンネルの
前記第１のグループが、前記複数のチャンネルの前記第
２のグループのタイム・スタンプ値より早く満期になる
タイム・スタンプ値を有する、ステップと、前記複数の
チャンネルの前記第１のグループに対するチャンネル・
エントリを第１のパラメータ・メモリに記憶するステッ
プと、前記複数のチャンネルの前記第２グループに対す
るチャンネル・エントリを第２のパラメータ・メモリに
記憶するステップと、を含む。
【００８０】上述した方法では、前記ソート・ステップ
がスケジューラ集積回路内の回路によって実行され、前
記第１のパラメータ・メモリが前記スケジューラ集積回
路内に設けられ、前記第２のパラメータ・メモリが前記
スケジューラ集積回路の外部メモリに設けられている。
がスケジューラ集積回路内の回路によって実行され、前
記第１のパラメータ・メモリが前記スケジューラ集積回
路内に設けられ、前記第２のパラメータ・メモリが前記
スケジューラ集積回路の外部メモリに設けられている。
【００８１】上述した方法は、送信クレジットを発行す
るステップの後に、前記ルート・チャンネル・エントリ
と関連する複数のチャンネルの１つに対する許可された
セル・レート値を検索するステップと、前記ルート・チ
ャンネル・エントリと関連する前記チャンネルに対する
新規タイム・スタンプ値を引き出すステップと、前記ソ
ート・ステップ，前記比較ステップおよび前記発行ステ
ップを反復するステップと、をさらに含む。
るステップの後に、前記ルート・チャンネル・エントリ
と関連する複数のチャンネルの１つに対する許可された
セル・レート値を検索するステップと、前記ルート・チ
ャンネル・エントリと関連する前記チャンネルに対する
新規タイム・スタンプ値を引き出すステップと、前記ソ
ート・ステップ，前記比較ステップおよび前記発行ステ
ップを反復するステップと、をさらに含む。
【００８２】上述した方法では、前記引き出しステップ
が、スケジューラ・クロック周波数を前記許可されたセ
ル・レート値で割った値に基づいてオフセット・タイム
・スタンプ値を生成するステップと、前記ルート・チャ
ンネル・エントリと関連する前記チャンネルに対する前
記タイム・スタンプ値を前記オフセット・タイム・スタ
ンプ値に加算して未来のクレジット時刻値を引き出すス
テップと、前記未来のクレジット時刻値を前記グローバ
ル時刻と比較するステップと、該比較ステップに応答し
て、前記未来のクレジット時刻値が前記グローバル時刻
より遅いことを決定し、前記新規タイム・スタンプ値を
前記未来のクレジット時刻値に設定するステップと、前
記比較ステップに応答して、前記未来のクレジット時刻
値が前記グローバル時刻より早いことを決定し、前記オ
フセット・タイム・スタンプ値を前記グローバル時刻に
加算して前記新規タイム・スタンプ値を生成するステッ
プと、を含む。
が、スケジューラ・クロック周波数を前記許可されたセ
ル・レート値で割った値に基づいてオフセット・タイム
・スタンプ値を生成するステップと、前記ルート・チャ
ンネル・エントリと関連する前記チャンネルに対する前
記タイム・スタンプ値を前記オフセット・タイム・スタ
ンプ値に加算して未来のクレジット時刻値を引き出すス
テップと、前記未来のクレジット時刻値を前記グローバ
ル時刻と比較するステップと、該比較ステップに応答し
て、前記未来のクレジット時刻値が前記グローバル時刻
より遅いことを決定し、前記新規タイム・スタンプ値を
前記未来のクレジット時刻値に設定するステップと、前
記比較ステップに応答して、前記未来のクレジット時刻
値が前記グローバル時刻より早いことを決定し、前記オ
フセット・タイム・スタンプ値を前記グローバル時刻に
加算して前記新規タイム・スタンプ値を生成するステッ
プと、を含む。
【００８３】本発明は、ローカル通信を受信するインタ
ーフェースを有するホスト・コントローラと、ＡＴＭト
ランスレータ・サブシステムとを備える、ネットワーク
・ハブおよびＡＴＭトランスレータ・システムであっ
て、 高データ・レート通信設備に結合されたトランシ
ーバ・インターフェースと、該トランシーバ・インター
フェースおよび前記ホスト・コントローラに結合された
分節化・再構築回路と、複数のＡＴＭ通信チャンネルの
各々と関連するエントリを記憶するパラメータ・メモリ
と、該パラメータ・メモリおよび前記分節化・再構築回
路に結合された、前記複数のＡＴＭ通信チャンネルと関
連するパケット・セルの送信を一連の操作によってスケ
ジュールするスケジューラと、を具備し、前記スケジュ
ーラが、前記パラメータ・メモリ内にチャンネル・エン
トリをソートするヒープ・ソート回路であって、前記各
チャンネル・エントリが、各チャンネルと関連するタイ
ム・スタンプ値を有し、該タイム・スタンプ値が、前記
関連チャンネルに対するセルの送信が次に満期になる時
刻を示し、前記ヒープ・ソート回路が、次に満期になる
チャンネルに対応するルート・チャンネル・エントリを
識別する、前記ヒープ・ソート回路と、グローバル時刻
を生成する基準タイマと、前記ルート・チャンネル・エ
ントリの前記タイム・スタンプ値を前記グローバル時刻
と比較するコンパレータと、前記分節化・再構築回路に
結合された、前記ルート・チャンネル・エントリと関連
する前記チャンネルに対する送信クレジットを発行する
ソース挙動プロセッサ回路と、を備える。
ーフェースを有するホスト・コントローラと、ＡＴＭト
ランスレータ・サブシステムとを備える、ネットワーク
・ハブおよびＡＴＭトランスレータ・システムであっ
て、 高データ・レート通信設備に結合されたトランシ
ーバ・インターフェースと、該トランシーバ・インター
フェースおよび前記ホスト・コントローラに結合された
分節化・再構築回路と、複数のＡＴＭ通信チャンネルの
各々と関連するエントリを記憶するパラメータ・メモリ
と、該パラメータ・メモリおよび前記分節化・再構築回
路に結合された、前記複数のＡＴＭ通信チャンネルと関
連するパケット・セルの送信を一連の操作によってスケ
ジュールするスケジューラと、を具備し、前記スケジュ
ーラが、前記パラメータ・メモリ内にチャンネル・エン
トリをソートするヒープ・ソート回路であって、前記各
チャンネル・エントリが、各チャンネルと関連するタイ
ム・スタンプ値を有し、該タイム・スタンプ値が、前記
関連チャンネルに対するセルの送信が次に満期になる時
刻を示し、前記ヒープ・ソート回路が、次に満期になる
チャンネルに対応するルート・チャンネル・エントリを
識別する、前記ヒープ・ソート回路と、グローバル時刻
を生成する基準タイマと、前記ルート・チャンネル・エ
ントリの前記タイム・スタンプ値を前記グローバル時刻
と比較するコンパレータと、前記分節化・再構築回路に
結合された、前記ルート・チャンネル・エントリと関連
する前記チャンネルに対する送信クレジットを発行する
ソース挙動プロセッサ回路と、を備える。
【００８４】また、上述したシステムにおいて、スケジ
ューラは単一集積回路に集積されてもよい。
ューラは単一集積回路に集積されてもよい。
【００８５】また、上述したシステムにおいて、スケジ
ューラは、スケジューラと同じ集積回路に設けられた、
複数のチャンネルの第１のグループと関連するタイム・
スタンプ値を記憶するオンチップ・パラメータ・メモリ
をさらに備え、このパラメータメモリは、スケジューラ
集積回路に対して外部であり、複数のチャンネルの第２
のグループと関連するタイム・スタンプ値を記憶する。
複数のチャンネルの第１のグループは、複数のチャンネ
ルの第２のグループより近い満期になるタイム・スタン
プ値を持っている。
ューラは、スケジューラと同じ集積回路に設けられた、
複数のチャンネルの第１のグループと関連するタイム・
スタンプ値を記憶するオンチップ・パラメータ・メモリ
をさらに備え、このパラメータメモリは、スケジューラ
集積回路に対して外部であり、複数のチャンネルの第２
のグループと関連するタイム・スタンプ値を記憶する。
複数のチャンネルの第１のグループは、複数のチャンネ
ルの第２のグループより近い満期になるタイム・スタン
プ値を持っている。
【００８６】また、上述したシステムにおいて、ソース
挙動プロセッサ回路は、送信クレジットを発行した後
に、ルート・チャンネルと関連するチャンネル用にパラ
メータ・メモリから許可されたセルレート値を検索し、
前記スケジューラは、ヒープ・ソート回路と結合され
た、ルート・チャンネル・エントリと関連するチャンネ
ルに対する新規タイム・スタンプ値を引き出す回路を備
える。
挙動プロセッサ回路は、送信クレジットを発行した後
に、ルート・チャンネルと関連するチャンネル用にパラ
メータ・メモリから許可されたセルレート値を検索し、
前記スケジューラは、ヒープ・ソート回路と結合され
た、ルート・チャンネル・エントリと関連するチャンネ
ルに対する新規タイム・スタンプ値を引き出す回路を備
える。
【００８７】また、上述したシステムにおいて、引き出
し回路は、スケジューラ・クロック周波数を許可された
セル・レート値で割った値に基づくオフセット・タイム
・スタンプ値を生成するデバイダと、そのオフセット・
タイム・スタンプ値をベース・タイム・スタンプ値に加
算して新規タイム・スタンプ値を生成する加算器とを備
える。
し回路は、スケジューラ・クロック周波数を許可された
セル・レート値で割った値に基づくオフセット・タイム
・スタンプ値を生成するデバイダと、そのオフセット・
タイム・スタンプ値をベース・タイム・スタンプ値に加
算して新規タイム・スタンプ値を生成する加算器とを備
える。
【００８８】また、上述したシステムにおいて、ベース
・タイム・スタンプ値は、ルート・チャンネル・エント
リのタイム・スタンプ値と等しい。
・タイム・スタンプ値は、ルート・チャンネル・エント
リのタイム・スタンプ値と等しい。
【００８９】また、上述したシステムにおいて、引き出
し回路は、マルチプレクサとマルチプレクサ制御機能と
を備える。このマルチプレクサは、基準タイマからグロ
ーバル時刻を受け取るための第１の入力と、ルート・チ
ャンネル・エントリのタイム・スタンプ値を受け取る第
２の入力と、前記加算器に結合されてベース・タイム・
スタンプ値をそこへ供給する出力と、グローバル時刻ま
たはベース・タイム・スタンプ値用のルート・チャンネ
ル・エントリのタイム・スタンプ値を選択する制御入力
とを備える。前記マルチプレクサ制御機能は、以下の操
作を実行することによって、マルチプレクサの制御入力
に供給される選択信号を生成する。スケジューラ・クロ
ック周波数を許可されたセル・レート値で割った値に基
づいてオフセット・タイム・スタンプ値を生成し、ルー
ト・チャンネル・エントリと関連するチャンネル用のタ
イム・スタンプ値をオフセット・タイム・スタンプ値に
加算して、未来のクレジット時刻値を引き出し、この未
来のクレジット時刻をグローバル時効と比較し、この比
較の結果に応答して、未来のクレジット時刻がグローバ
ル時刻より遅いことを決定し、新規タイム・スタンプ値
を未来のクレジット時刻に設定し、前記比較の結果に応
答して、未来のクレジット時刻がグローバル時刻より早
いことを決定し、オフセット・タイム・スタンプ値をグ
ローバル時刻に加算して新規タイム・スタンプ値を生成
する。
し回路は、マルチプレクサとマルチプレクサ制御機能と
を備える。このマルチプレクサは、基準タイマからグロ
ーバル時刻を受け取るための第１の入力と、ルート・チ
ャンネル・エントリのタイム・スタンプ値を受け取る第
２の入力と、前記加算器に結合されてベース・タイム・
スタンプ値をそこへ供給する出力と、グローバル時刻ま
たはベース・タイム・スタンプ値用のルート・チャンネ
ル・エントリのタイム・スタンプ値を選択する制御入力
とを備える。前記マルチプレクサ制御機能は、以下の操
作を実行することによって、マルチプレクサの制御入力
に供給される選択信号を生成する。スケジューラ・クロ
ック周波数を許可されたセル・レート値で割った値に基
づいてオフセット・タイム・スタンプ値を生成し、ルー
ト・チャンネル・エントリと関連するチャンネル用のタ
イム・スタンプ値をオフセット・タイム・スタンプ値に
加算して、未来のクレジット時刻値を引き出し、この未
来のクレジット時刻をグローバル時効と比較し、この比
較の結果に応答して、未来のクレジット時刻がグローバ
ル時刻より遅いことを決定し、新規タイム・スタンプ値
を未来のクレジット時刻に設定し、前記比較の結果に応
答して、未来のクレジット時刻がグローバル時刻より早
いことを決定し、オフセット・タイム・スタンプ値をグ
ローバル時刻に加算して新規タイム・スタンプ値を生成
する。
【００９０】以上、本発明を好ましい実施の形態におい
て述べてきたが、本発明はこれらの実施の形態の他にも
様々な形態が可能であり、また、それらの変形も本発明
の範囲に入るものであり、そのことは、当業者にとって
は、本明細書及び図面から明らかであろう。そのような
変形、あるいは別の形態も、本発明の請求の範囲に入る
ものである。
て述べてきたが、本発明はこれらの実施の形態の他にも
様々な形態が可能であり、また、それらの変形も本発明
の範囲に入るものであり、そのことは、当業者にとって
は、本明細書及び図面から明らかであろう。そのような
変形、あるいは別の形態も、本発明の請求の範囲に入る
ものである。
【００９１】以上の説明に関して更に以下の項を開示す
る。 （１）複数の通信チャンネルと関連するパケット・セル
の送信をスケジュールする方法であって、複数のチャン
ネル・エントリをヒープ・メモリ内にソートするステッ
プであって、前記各チャンネル・エントリが、各チャン
ネルと関連するタイム・スタンプ値を含み、該タイム・
スタンプ値が、関連チャンネルに対するセルの送信が次
に満期になる時刻を示し、前記ソート・ステップが、次
の満期になるチャンネルに対応するルート・チャンネル
・エントリを識別する、ステップと、前記ルート・チャ
ンネル・エントリのタイム・スタンプ値を基準タイマに
よって生成されたグローバル時刻と比較するステップ
と、該比較ステップに応答して、前記グローバル時刻が
少なくとも前記ルート・チャンネル・エントリのタイム
・スタンプ値に達したことを決定し、前記ルート・チャ
ンネル・エントリと関連するチャンネルに対して送信ク
レジットを発行するステップと、を含む、方法。
る。 （１）複数の通信チャンネルと関連するパケット・セル
の送信をスケジュールする方法であって、複数のチャン
ネル・エントリをヒープ・メモリ内にソートするステッ
プであって、前記各チャンネル・エントリが、各チャン
ネルと関連するタイム・スタンプ値を含み、該タイム・
スタンプ値が、関連チャンネルに対するセルの送信が次
に満期になる時刻を示し、前記ソート・ステップが、次
の満期になるチャンネルに対応するルート・チャンネル
・エントリを識別する、ステップと、前記ルート・チャ
ンネル・エントリのタイム・スタンプ値を基準タイマに
よって生成されたグローバル時刻と比較するステップ
と、該比較ステップに応答して、前記グローバル時刻が
少なくとも前記ルート・チャンネル・エントリのタイム
・スタンプ値に達したことを決定し、前記ルート・チャ
ンネル・エントリと関連するチャンネルに対して送信ク
レジットを発行するステップと、を含む、方法。
【００９２】（２）送信クレジットを発行するステップ
の後に、前記ルート・チャンネル・エントリと関連する
前記チャンネルに対して、許可されたセル・レート値を
パラメータ・メモリから検索するステップと、前記ルー
ト・チャンネル・エントリと関連する前記チャンネルに
対する新規タイム・スタンプ値を引き出すステップと、
前記ソート・ステップ，前記比較ステップおよび前記発
行ステップを反復するステップと、をさらに含む、第１
項記載の方法。 （３）前記引き出しステップが、スケジューラ・クロッ
ク周波数を前記許可されたセル・レート値で割った値に
基づいてオフセット・タイム・スタンプ値を生成するス
テップと、前記オフセット・タイム・スタンプ値をベー
ス・タイム・スタンプ値に加算して前記新規タイム・ス
タンプ値を生成するステップと、をさらに含む、第２項
記載の方法。 （４）前記ベース・タイム・スタンプ値が前記ルート・
チャンネル・エントリのタイム・スタンプ値と等しい、
第３項記載の方法。 （５）前記ベース・タイム・スタンプ値が前記グローバ
ル時刻と等しい、第３項記載の方法。 （６）前記ソート・ステップが、前記複数のチャンネル
の第１および第２のグループを識別するステップであっ
て、前記複数のチャンネルの前記第１のグループが、前
記複数のチャンネルの前記第２のグループのタイム・ス
タンプ値より早く満期になるタイム・スタンプ値を有す
る、ステップと、前記複数のチャンネルの前記第１のグ
ループに対するチャンネル・エントリを第１のパラメー
タ・メモリに記憶するステップと、前記複数のチャンネ
ルの前記第２グループに対するチャンネル・エントリを
第２のパラメータ・メモリに記憶するステップと、を含
む、第１項記載の方法。
の後に、前記ルート・チャンネル・エントリと関連する
前記チャンネルに対して、許可されたセル・レート値を
パラメータ・メモリから検索するステップと、前記ルー
ト・チャンネル・エントリと関連する前記チャンネルに
対する新規タイム・スタンプ値を引き出すステップと、
前記ソート・ステップ，前記比較ステップおよび前記発
行ステップを反復するステップと、をさらに含む、第１
項記載の方法。 （３）前記引き出しステップが、スケジューラ・クロッ
ク周波数を前記許可されたセル・レート値で割った値に
基づいてオフセット・タイム・スタンプ値を生成するス
テップと、前記オフセット・タイム・スタンプ値をベー
ス・タイム・スタンプ値に加算して前記新規タイム・ス
タンプ値を生成するステップと、をさらに含む、第２項
記載の方法。 （４）前記ベース・タイム・スタンプ値が前記ルート・
チャンネル・エントリのタイム・スタンプ値と等しい、
第３項記載の方法。 （５）前記ベース・タイム・スタンプ値が前記グローバ
ル時刻と等しい、第３項記載の方法。 （６）前記ソート・ステップが、前記複数のチャンネル
の第１および第２のグループを識別するステップであっ
て、前記複数のチャンネルの前記第１のグループが、前
記複数のチャンネルの前記第２のグループのタイム・ス
タンプ値より早く満期になるタイム・スタンプ値を有す
る、ステップと、前記複数のチャンネルの前記第１のグ
ループに対するチャンネル・エントリを第１のパラメー
タ・メモリに記憶するステップと、前記複数のチャンネ
ルの前記第２グループに対するチャンネル・エントリを
第２のパラメータ・メモリに記憶するステップと、を含
む、第１項記載の方法。
【００９３】（７）前記ソート・ステップがスケジュー
ラ集積回路内の回路によって実行され、前記第１のパラ
メータ・メモリが前記スケジューラ集積回路内に設けら
れ、前記第２のパラメータ・メモリが前記スケジューラ
集積回路の外部メモリに設けられた、第６項記載の方
法。 （８）送信クレジットを発行するステップの後に、前記
ルート・チャンネル・エントリと関連する複数のチャン
ネルの１つに対する許可されたセル・レート値を検索す
るステップと、前記ルート・チャンネル・エントリと関
連する前記チャンネルに対する新規タイム・スタンプ値
を引き出すステップと、前記ソート・ステップ，前記比
較ステップおよび前記発行ステップを反復するステップ
と、をさらに含む、第１項記載の方法。 （９）前記引き出しステップが、スケジューラ・クロッ
ク周波数を前記許可されたセル・レート値で割った値に
基づいてオフセット・タイム・スタンプ値を生成するス
テップと、前記ルート・チャンネル・エントリと関連す
る前記チャンネルに対する前記タイム・スタンプ値を前
記オフセット・タイム・スタンプ値に加算して未来のク
レジット時刻値を引き出すステップと、前記未来のクレ
ジット時刻値を前記グローバル時刻と比較するステップ
と、該比較ステップに応答して、前記未来のクレジット
時刻値が前記グローバル時刻より遅いことを決定し、前
記新規タイム・スタンプ値を前記未来のクレジット時刻
値に設定するステップと、前記比較ステップに応答し
て、前記未来のクレジット時刻値が前記グローバル時刻
より早いことを決定し、前記オフセット・タイム・スタ
ンプ値を前記グローバル時刻に加算して前記新規タイム
・スタンプ値を生成するステップと、を含む、第８項記
載の方法。
ラ集積回路内の回路によって実行され、前記第１のパラ
メータ・メモリが前記スケジューラ集積回路内に設けら
れ、前記第２のパラメータ・メモリが前記スケジューラ
集積回路の外部メモリに設けられた、第６項記載の方
法。 （８）送信クレジットを発行するステップの後に、前記
ルート・チャンネル・エントリと関連する複数のチャン
ネルの１つに対する許可されたセル・レート値を検索す
るステップと、前記ルート・チャンネル・エントリと関
連する前記チャンネルに対する新規タイム・スタンプ値
を引き出すステップと、前記ソート・ステップ，前記比
較ステップおよび前記発行ステップを反復するステップ
と、をさらに含む、第１項記載の方法。 （９）前記引き出しステップが、スケジューラ・クロッ
ク周波数を前記許可されたセル・レート値で割った値に
基づいてオフセット・タイム・スタンプ値を生成するス
テップと、前記ルート・チャンネル・エントリと関連す
る前記チャンネルに対する前記タイム・スタンプ値を前
記オフセット・タイム・スタンプ値に加算して未来のク
レジット時刻値を引き出すステップと、前記未来のクレ
ジット時刻値を前記グローバル時刻と比較するステップ
と、該比較ステップに応答して、前記未来のクレジット
時刻値が前記グローバル時刻より遅いことを決定し、前
記新規タイム・スタンプ値を前記未来のクレジット時刻
値に設定するステップと、前記比較ステップに応答し
て、前記未来のクレジット時刻値が前記グローバル時刻
より早いことを決定し、前記オフセット・タイム・スタ
ンプ値を前記グローバル時刻に加算して前記新規タイム
・スタンプ値を生成するステップと、を含む、第８項記
載の方法。
【００９４】ローカル通信を受信するインターフェース
を有するホスト・コントローラと、ＡＴＭトランスレー
タ・サブシステムとを備える、ネットワーク・ハブおよ
びＡＴＭトランスレータ・システムであって、高データ
・レート通信設備に結合されたトランシーバ・インター
フェースと、該トランシーバ・インターフェースおよび
前記ホスト・コントローラに結合された分節化・再構築
回路と、複数のＡＴＭ通信チャンネルの各々と関連する
エントリを記憶するパラメータ・メモリと、該パラメー
タ・メモリおよび前記分節化・再構築回路に結合され
た、前記複数のＡＴＭ通信チャンネルと関連するパケッ
ト・セルの送信を一連の操作によってスケジュールする
スケジューラと、を具備し、前記スケジューラが、前記
パラメータ・メモリ内にチャンネル・エントリをソート
するヒープ・ソート回路であって、前記各チャンネル・
エントリが、各チャンネルと関連するタイム・スタンプ
値を有し、該タイム・スタンプ値が、前記関連チャンネ
ルに対するセルの送信が次に満期になる時刻を示し、前
記ヒープ・ソート回路が、次に満期になるチャンネルに
対応するルート・チャンネル・エントリを識別する、前
記ヒープ・ソート回路と、グローバル時刻を生成する基
準タイマと、前記ルート・チャンネル・エントリの前記
タイム・スタンプ値を前記グローバル時刻と比較するコ
ンパレータと、前記分節化・再構築回路に結合された、
前記ルート・チャンネル・エントリと関連する前記チャ
ンネルに対する送信クレジットを発行するソース挙動プ
ロセッサ回路と、を備える、ネットワーク・ハブおよび
ＡＴＭトランスレータ・システム。
を有するホスト・コントローラと、ＡＴＭトランスレー
タ・サブシステムとを備える、ネットワーク・ハブおよ
びＡＴＭトランスレータ・システムであって、高データ
・レート通信設備に結合されたトランシーバ・インター
フェースと、該トランシーバ・インターフェースおよび
前記ホスト・コントローラに結合された分節化・再構築
回路と、複数のＡＴＭ通信チャンネルの各々と関連する
エントリを記憶するパラメータ・メモリと、該パラメー
タ・メモリおよび前記分節化・再構築回路に結合され
た、前記複数のＡＴＭ通信チャンネルと関連するパケッ
ト・セルの送信を一連の操作によってスケジュールする
スケジューラと、を具備し、前記スケジューラが、前記
パラメータ・メモリ内にチャンネル・エントリをソート
するヒープ・ソート回路であって、前記各チャンネル・
エントリが、各チャンネルと関連するタイム・スタンプ
値を有し、該タイム・スタンプ値が、前記関連チャンネ
ルに対するセルの送信が次に満期になる時刻を示し、前
記ヒープ・ソート回路が、次に満期になるチャンネルに
対応するルート・チャンネル・エントリを識別する、前
記ヒープ・ソート回路と、グローバル時刻を生成する基
準タイマと、前記ルート・チャンネル・エントリの前記
タイム・スタンプ値を前記グローバル時刻と比較するコ
ンパレータと、前記分節化・再構築回路に結合された、
前記ルート・チャンネル・エントリと関連する前記チャ
ンネルに対する送信クレジットを発行するソース挙動プ
ロセッサ回路と、を備える、ネットワーク・ハブおよび
ＡＴＭトランスレータ・システム。
【００９５】（１１）ＬＡＮ通信システムにおいて使用
されるネットワーク・ハブおよびＡＴＭトランスレータ
・システム５が開示される。ネットワーク・ハブおよび
ＡＴＭトランスレータ・システム５は、ＬＡＮのハブと
なるホスト・コントローラ１０を備え、それがトランス
レータ・カード１５とインターフェースする。トランス
レータ・カードは、分節化・再構築デバイス１２を備
え、それがトランシーバ２２と通信するＳＯＮＥＴ送受
信回路２０と接続されて、通信設備（ＦＯ）を介してＡ
ＴＭパケット・セルを送受信する。トランスレータ・カ
ード１５は、スケジューラ１４を備え、スケジューラ
は、ソートされたエントリ・リストをオンチップ・パラ
メータ・メモリとオフチップ・パラメータ・メモリ１８
とにヒープ状に保持するヒープ・ソート状態マシンを備
える。エントリは、各ＡＴＭチャンネルに対して、チャ
ンネル識別子と、そのチャンネルに対する次のセルが転
送されることになっている時刻を示すタイム・スタンプ
とを含む。デュー・コンパレータは、ヒープ内のルート
値のタイム・スタンプ（つまり、次に送信されるべきセ
ルをもつチャンネル）を基準タイマによって生成された
グローバル時刻と比較し、セルが転送されることになっ
ている時刻になったことをスケジューラ１４内のソース
挙動プロセッサに示す。スケジューラは、そのセルに対
する送信クレジットを発行し、これをＳＡＲデバイス１
２に知らせ、送信させる。
されるネットワーク・ハブおよびＡＴＭトランスレータ
・システム５が開示される。ネットワーク・ハブおよび
ＡＴＭトランスレータ・システム５は、ＬＡＮのハブと
なるホスト・コントローラ１０を備え、それがトランス
レータ・カード１５とインターフェースする。トランス
レータ・カードは、分節化・再構築デバイス１２を備
え、それがトランシーバ２２と通信するＳＯＮＥＴ送受
信回路２０と接続されて、通信設備（ＦＯ）を介してＡ
ＴＭパケット・セルを送受信する。トランスレータ・カ
ード１５は、スケジューラ１４を備え、スケジューラ
は、ソートされたエントリ・リストをオンチップ・パラ
メータ・メモリとオフチップ・パラメータ・メモリ１８
とにヒープ状に保持するヒープ・ソート状態マシンを備
える。エントリは、各ＡＴＭチャンネルに対して、チャ
ンネル識別子と、そのチャンネルに対する次のセルが転
送されることになっている時刻を示すタイム・スタンプ
とを含む。デュー・コンパレータは、ヒープ内のルート
値のタイム・スタンプ（つまり、次に送信されるべきセ
ルをもつチャンネル）を基準タイマによって生成された
グローバル時刻と比較し、セルが転送されることになっ
ている時刻になったことをスケジューラ１４内のソース
挙動プロセッサに示す。スケジューラは、そのセルに対
する送信クレジットを発行し、これをＳＡＲデバイス１
２に知らせ、送信させる。
【００９６】関連特許の開示 本出願は、米国特許法第１１９条（ｅ）（１）の下で、
１９９７年１１月２１に出願され、本明細書に組み込ま
れている仮出願番号第６０／０６６，３２８号を含む。
本出願は、「オーバースケジュール条件でのＡＴＭセル
送信の公平なスケジューリング」と題する米国出願（Ｔ
Ｉ−２６０３５）にも関連する。
１９９７年１１月２１に出願され、本明細書に組み込ま
れている仮出願番号第６０／０６６，３２８号を含む。
本出願は、「オーバースケジュール条件でのＡＴＭセル
送信の公平なスケジューリング」と題する米国出願（Ｔ
Ｉ−２６０３５）にも関連する。
【図１】本発明の好ましい実施の形態による通信システ
ムの電気的接続のブロック図である。
ムの電気的接続のブロック図である。
【図２】本発明の好ましい実施の形態による図１の通信
システムにおけるネットワーク・ハブおよび非同期転送
モード（ＡＴＭ）トランスレータの電気的接続を示すブ
ロック図である。
システムにおけるネットワーク・ハブおよび非同期転送
モード（ＡＴＭ）トランスレータの電気的接続を示すブ
ロック図である。
【図３】本発明の好ましい実施の形態による図２のネッ
トワーク・ハブおよび非同期転送モード（ＡＴＭ）トラ
ンスレータ内のスケジューラの電気的接続を示すブロッ
ク図である。
トワーク・ハブおよび非同期転送モード（ＡＴＭ）トラ
ンスレータ内のスケジューラの電気的接続を示すブロッ
ク図である。
【図４】本発明の好ましい実施の形態による図３のスケ
ジューラの動作を示すフローチャートである。
ジューラの動作を示すフローチャートである。
【図５】本発明の好ましい実施の形態による図３のスケ
ジューラ内のソース挙動プロセッサがＡＴＭチャンネル
用の許可されたセル・レート値を調整する動作を示すフ
ローチャートである。
ジューラ内のソース挙動プロセッサがＡＴＭチャンネル
用の許可されたセル・レート値を調整する動作を示すフ
ローチャートである。
【図６】（Ａ）および（Ｂ）はそれぞれ、本発明の好ま
しい実施の形態による図２のネットワーク・ハブおよび
ＡＴＭトランスレータ内のオンチップ・パラメータ・メ
モリおよびオフチップ・パラメータ・メモリの構成を示
すメモリマップである。
しい実施の形態による図２のネットワーク・ハブおよび
ＡＴＭトランスレータ内のオンチップ・パラメータ・メ
モリおよびオフチップ・パラメータ・メモリの構成を示
すメモリマップである。
２，６ コンピュータ ５ ハブおよびＡＴＭトランスレータ ７ センター局スイッチ ８ ＡＴＭプレミス・スイッチ １０ ホスト・コントローラ １２ ＳＡＲデバイス １５ トランスレータ・カード １４ スケジューラ １６ 制御メモリ １８ パラメータ・メモリ ２０ ＳＯＮＥＴ送受信Ｒｘ／Ｔｘ回路 ２４ ソース挙動プロセッサ ２６ スケジューラ・コマンド・レジスタ ２８ デバイダ ３０ 浮動少数点・整数回路 ３３ マルチプレクサ制御機能 ３６ ヒープソート状態マシン ３８ 基準タイマ ４０ デュー・コンパレータ
───────────────────────────────────────────────────── フロントページの続き (72)発明者 シャラト プラサド アメリカ合衆国 テキサス州プラノ，モン ティセロ サークル 2109
Claims (2)
- 【請求項１】 複数の通信チャンネルと関連するパケッ
ト・セルの送信をスケジュールする方法であって、 複数のチャンネル・エントリをヒープ・メモリ内にソー
トするステップであって、前記各チャンネル・エントリ
が、各チャンネルと関連するタイム・スタンプ値を含
み、該タイム・スタンプ値が、関連チャンネルに対する
セルの送信が次に満期になる時刻を示し、前記ソート・
ステップが、次の満期になるチャンネルに対応するルー
ト・チャンネル・エントリを識別する、ステップと、 前記ルート・チャンネル・エントリのタイム・スタンプ
値を基準タイマによって生成されたグローバル時刻と比
較するステップと、 該比較ステップに応答して、前記グローバル時刻が少な
くとも前記ルート・チャンネル・エントリのタイム・ス
タンプ値に達したことを決定し、前記ルート・チャンネ
ル・エントリと関連するチャンネルに対して送信クレジ
ットを発行するステップと、 を含む、方法。 - 【請求項２】 ローカル通信を受信するインターフェー
スを有するホスト・コントローラと、ＡＴＭトランスレ
ータ・サブシステムとを備える、ネットワーク・ハブお
よびＡＴＭトランスレータ・システムであって、 高データ・レート通信設備に結合されたトランシーバ・
インターフェースと、 該トランシーバ・インターフェースおよび前記ホスト・
コントローラに結合された分節化・再構築回路と、 複数のＡＴＭ通信チャンネルの各々と関連するエントリ
を記憶するパラメータ・メモリと、 該パラメータ・メモリおよび前記分節化・再構築回路に
結合された、前記複数のＡＴＭ通信チャンネルと関連す
るパケット・セルの送信を一連の操作によってスケジュ
ールするスケジューラと、 を具備し、 前記スケジューラが、 前記パラメータ・メモリ内にチャンネル・エントリをソ
ートするヒープ・ソート回路であって、前記各チャンネ
ル・エントリが、各チャンネルと関連するタイム・スタ
ンプ値を有し、該タイム・スタンプ値が、前記関連チャ
ンネルに対するセルの送信が次に満期になる時刻を示
し、前記ヒープ・ソート回路が、次に満期になるチャン
ネルに対応するルート・チャンネル・エントリを識別す
る、前記ヒープ・ソート回路と、 グローバル時刻を生成する基準タイマと、 前記ルート・チャンネル・エントリの前記タイム・スタ
ンプ値を前記グローバル時刻と比較するコンパレータ
と、 前記分節化・再構築回路に結合された、前記ルート・チ
ャンネル・エントリと関連する前記チャンネルに対する
送信クレジットを発行するソース挙動プロセッサ回路
と、を備える、ネットワーク・ハブおよびＡＴＭトラン
スレータ・システム。
Applications Claiming Priority (4)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US6632897P | 1997-11-21 | 1997-11-21 | |
| US08/993,801 US6205151B1 (en) | 1997-11-21 | 1997-12-18 | ATM cell scheduler which uses a heap memory and associates timestamps with each channel |
| US993801 | 1997-12-18 | ||
| US066328 | 1997-12-18 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11234309A true JPH11234309A (ja) | 1999-08-27 |
Family
ID=26746624
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP33072298A Pending JPH11234309A (ja) | 1997-11-21 | 1998-11-20 | 非同期転送モード・セル送信スケジューリング |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US6205151B1 (ja) |
| EP (1) | EP0939573B1 (ja) |
| JP (1) | JPH11234309A (ja) |
| DE (1) | DE69817756T2 (ja) |
Families Citing this family (72)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6377550B1 (en) * | 1997-10-28 | 2002-04-23 | Texas Instruments Incorporated | Nested measurement period switch algorithm for flow control of available bit rate ATM communications |
| US6272131B1 (en) * | 1998-06-11 | 2001-08-07 | Synchrodyne Networks, Inc. | Integrated data packet network using a common time reference |
| US6549514B1 (en) * | 1998-07-07 | 2003-04-15 | Nokia Corporation | Method and apparatus for shaping traffice for a SIMA network |
| US6765911B1 (en) * | 1999-02-03 | 2004-07-20 | International Business Machines Corporation | Communications adapter for implementing communications in a network and providing multiple modes of communications |
| US7016337B1 (en) * | 1999-03-02 | 2006-03-21 | Cisco Technology, Inc. | System and method for multiple channel statistical re-multiplexing |
| US7593433B1 (en) * | 1999-03-02 | 2009-09-22 | Cisco Technology, Inc. | System and method for multiple channel statistical re-multiplexing |
| US6728265B1 (en) * | 1999-07-30 | 2004-04-27 | Intel Corporation | Controlling frame transmission |
| US7156301B1 (en) | 1999-09-07 | 2007-01-02 | American Express Travel Related Services Company, Inc. | Foldable non-traditionally-sized RF transaction card system and method |
| US7093767B2 (en) | 1999-09-07 | 2006-08-22 | American Express Travel Related Services Company, Inc. | System and method for manufacturing a punch-out RFID transaction device |
| US7889052B2 (en) | 2001-07-10 | 2011-02-15 | Xatra Fund Mx, Llc | Authorizing payment subsequent to RF transactions |
| US7239226B2 (en) | 2001-07-10 | 2007-07-03 | American Express Travel Related Services Company, Inc. | System and method for payment using radio frequency identification in contact and contactless transactions |
| US7837116B2 (en) | 1999-09-07 | 2010-11-23 | American Express Travel Related Services Company, Inc. | Transaction card |
| US7070112B2 (en) | 1999-09-07 | 2006-07-04 | American Express Travel Related Services Company, Inc. | Transparent transaction device |
| US7306158B2 (en) | 2001-07-10 | 2007-12-11 | American Express Travel Related Services Company, Inc. | Clear contactless card |
| US7172112B2 (en) | 2000-01-21 | 2007-02-06 | American Express Travel Related Services Company, Inc. | Public/private dual card system and method |
| US8429041B2 (en) | 2003-05-09 | 2013-04-23 | American Express Travel Related Services Company, Inc. | Systems and methods for managing account information lifecycles |
| US8543423B2 (en) | 2002-07-16 | 2013-09-24 | American Express Travel Related Services Company, Inc. | Method and apparatus for enrolling with multiple transaction environments |
| US7268668B2 (en) | 2003-05-09 | 2007-09-11 | American Express Travel Related Services Company, Inc. | Systems and methods for managing multiple accounts on a RF transaction instrument |
| US6748445B1 (en) * | 2000-02-01 | 2004-06-08 | Microsoft Corporation | System and method for exchanging data |
| JP2001230810A (ja) * | 2000-02-16 | 2001-08-24 | Fujitsu Ltd | パケット流量制御装置および方法 |
| WO2001067355A2 (en) | 2000-03-07 | 2001-09-13 | American Express Travel Related Services Company, Inc. | System for facilitating a transaction |
| US20020126690A1 (en) * | 2001-02-26 | 2002-09-12 | Maple Optical Systems, Inc. | Packet transmission scheduling in a data communication network |
| US7650314B1 (en) | 2001-05-25 | 2010-01-19 | American Express Travel Related Services Company, Inc. | System and method for securing a recurrent billing transaction |
| US7542942B2 (en) | 2001-07-10 | 2009-06-02 | American Express Travel Related Services Company, Inc. | System and method for securing sensitive information during completion of a transaction |
| US7059531B2 (en) | 2001-07-10 | 2006-06-13 | American Express Travel Related Services Company, Inc. | Method and system for smellprint recognition biometrics on a fob |
| US8294552B2 (en) | 2001-07-10 | 2012-10-23 | Xatra Fund Mx, Llc | Facial scan biometrics on a payment device |
| US7121471B2 (en) | 2001-07-10 | 2006-10-17 | American Express Travel Related Services Company, Inc. | Method and system for DNA recognition biometrics on a fob |
| US7360689B2 (en) | 2001-07-10 | 2008-04-22 | American Express Travel Related Services Company, Inc. | Method and system for proffering multiple biometrics for use with a FOB |
| US9031880B2 (en) | 2001-07-10 | 2015-05-12 | Iii Holdings 1, Llc | Systems and methods for non-traditional payment using biometric data |
| US7746215B1 (en) | 2001-07-10 | 2010-06-29 | Fred Bishop | RF transactions using a wireless reader grid |
| US7228155B2 (en) | 2001-07-10 | 2007-06-05 | American Express Travel Related Services Company, Inc. | System and method for remotely initializing a RF transaction |
| US7668750B2 (en) | 2001-07-10 | 2010-02-23 | David S Bonalle | Securing RF transactions using a transactions counter |
| US7463133B2 (en) | 2001-07-10 | 2008-12-09 | American Express Travel Related Services Company, Inc. | Systems and methods for providing a RF transaction device operable to store multiple distinct calling card accounts |
| US20040233037A1 (en) * | 2001-07-10 | 2004-11-25 | American Express Travel Related Services Company, Inc. | Method and system for iris scan recognition biometrics on a fob |
| US8538863B1 (en) | 2001-07-10 | 2013-09-17 | American Express Travel Related Services Company, Inc. | System and method for facilitating a transaction using a revolving use account associated with a primary account |
| US7119659B2 (en) | 2001-07-10 | 2006-10-10 | American Express Travel Related Services Company, Inc. | Systems and methods for providing a RF transaction device for use in a private label transaction |
| US8635131B1 (en) | 2001-07-10 | 2014-01-21 | American Express Travel Related Services Company, Inc. | System and method for managing a transaction protocol |
| US7543738B1 (en) | 2001-07-10 | 2009-06-09 | American Express Travel Related Services Company, Inc. | System and method for secure transactions manageable by a transaction account provider |
| US7154375B2 (en) | 2001-07-10 | 2006-12-26 | American Express Travel Related Services Company, Inc. | Biometric safeguard method with a fob |
| US7493288B2 (en) | 2001-07-10 | 2009-02-17 | Xatra Fund Mx, Llc | RF payment via a mobile device |
| US20040236699A1 (en) | 2001-07-10 | 2004-11-25 | American Express Travel Related Services Company, Inc. | Method and system for hand geometry recognition biometrics on a fob |
| US7303120B2 (en) | 2001-07-10 | 2007-12-04 | American Express Travel Related Services Company, Inc. | System for biometric security using a FOB |
| US7827106B2 (en) | 2001-07-10 | 2010-11-02 | American Express Travel Related Services Company, Inc. | System and method for manufacturing a punch-out RFID transaction device |
| US7312707B1 (en) | 2001-07-10 | 2007-12-25 | American Express Travel Related Services Company, Inc. | System and method for authenticating a RF transaction using a transaction account routing number |
| US8279042B2 (en) | 2001-07-10 | 2012-10-02 | Xatra Fund Mx, Llc | Iris scan biometrics on a payment device |
| US8548927B2 (en) | 2001-07-10 | 2013-10-01 | Xatra Fund Mx, Llc | Biometric registration for facilitating an RF transaction |
| US7925535B2 (en) | 2001-07-10 | 2011-04-12 | American Express Travel Related Services Company, Inc. | System and method for securing RF transactions using a radio frequency identification device including a random number generator |
| US7429927B2 (en) | 2001-07-10 | 2008-09-30 | American Express Travel Related Services Company, Inc. | System and method for providing and RFID transaction device |
| US7805378B2 (en) | 2001-07-10 | 2010-09-28 | American Express Travel Related Servicex Company, Inc. | System and method for encoding information in magnetic stripe format for use in radio frequency identification transactions |
| US7762457B2 (en) | 2001-07-10 | 2010-07-27 | American Express Travel Related Services Company, Inc. | System and method for dynamic fob synchronization and personalization |
| US7705732B2 (en) | 2001-07-10 | 2010-04-27 | Fred Bishop | Authenticating an RF transaction using a transaction counter |
| US9454752B2 (en) | 2001-07-10 | 2016-09-27 | Chartoleaux Kg Limited Liability Company | Reload protocol at a transaction processing entity |
| US8960535B2 (en) | 2001-07-10 | 2015-02-24 | Iii Holdings 1, Llc | Method and system for resource management and evaluation |
| US7503480B2 (en) | 2001-07-10 | 2009-03-17 | American Express Travel Related Services Company, Inc. | Method and system for tracking user performance |
| US7996324B2 (en) | 2001-07-10 | 2011-08-09 | American Express Travel Related Services Company, Inc. | Systems and methods for managing multiple accounts on a RF transaction device using secondary identification indicia |
| US8001054B1 (en) | 2001-07-10 | 2011-08-16 | American Express Travel Related Services Company, Inc. | System and method for generating an unpredictable number using a seeded algorithm |
| US9024719B1 (en) | 2001-07-10 | 2015-05-05 | Xatra Fund Mx, Llc | RF transaction system and method for storing user personal data |
| US7249112B2 (en) | 2002-07-09 | 2007-07-24 | American Express Travel Related Services Company, Inc. | System and method for assigning a funding source for a radio frequency identification device |
| US7284111B1 (en) | 2002-04-17 | 2007-10-16 | Dinochip, Inc. | Integrated multidimensional sorter |
| US7587756B2 (en) | 2002-07-09 | 2009-09-08 | American Express Travel Related Services Company, Inc. | Methods and apparatus for a secure proximity integrated circuit card transactions |
| US7529276B1 (en) | 2002-09-03 | 2009-05-05 | Cisco Technology, Inc. | Combined jitter and multiplexing systems and methods |
| US6805287B2 (en) | 2002-09-12 | 2004-10-19 | American Express Travel Related Services Company, Inc. | System and method for converting a stored value card to a credit card |
| US7268667B2 (en) | 2003-05-09 | 2007-09-11 | American Express Travel Related Services Company, Inc. | Systems and methods for providing a RF transaction device operable to store multiple distinct accounts |
| US7317727B2 (en) * | 2003-05-21 | 2008-01-08 | International Business Machines Corporation | Method and systems for controlling ATM traffic using bandwidth allocation technology |
| US7362765B1 (en) * | 2003-12-15 | 2008-04-22 | Dinochip, Inc. | Network traffic management system with floating point sorter |
| US7474638B2 (en) * | 2003-12-15 | 2009-01-06 | Agilent Technologies, Inc. | Method and system for distributed baseband measurements |
| US7352697B1 (en) | 2004-06-23 | 2008-04-01 | Dinochip, Inc. | Network processing using fractional time stamp values |
| US7314165B2 (en) | 2004-07-01 | 2008-01-01 | American Express Travel Related Services Company, Inc. | Method and system for smellprint recognition biometrics on a smartcard |
| US7318550B2 (en) | 2004-07-01 | 2008-01-15 | American Express Travel Related Services Company, Inc. | Biometric safeguard method for use with a smartcard |
| US8169891B2 (en) * | 2005-03-31 | 2012-05-01 | Agere Systems Inc. | Apparatus and method for handling lost cells in a communications system |
| US7623539B2 (en) * | 2005-03-31 | 2009-11-24 | Agere Systems Inc. | Apparatus and method for processing cells in an ATM adaptation layer device in a communications system that exhibits cell delay variation |
| US7596147B2 (en) | 2006-06-28 | 2009-09-29 | Agere Systems Inc. | Apparatus and method for fractional processing of cells in a communications system |
Family Cites Families (10)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US5796735A (en) * | 1995-08-28 | 1998-08-18 | Integrated Device Technology, Inc. | System and method for transmission rate control in a segmentation and reassembly (SAR) circuit under ATM protocol |
| US5917822A (en) * | 1995-11-15 | 1999-06-29 | Xerox Corporation | Method for providing integrated packet services over a shared-media network |
| US5751709A (en) | 1995-12-28 | 1998-05-12 | Lucent Technologies Inc. | Adaptive time slot scheduling apparatus and method for end-points in an ATM network |
| US5812527A (en) * | 1996-04-01 | 1998-09-22 | Motorola Inc. | Simplified calculation of cell transmission rates in a cell based netwook |
| US6128303A (en) | 1996-05-09 | 2000-10-03 | Maker Communications, Inc. | Asynchronous transfer mode cell processing system with scoreboard scheduling |
| US5926459A (en) * | 1996-06-27 | 1999-07-20 | Xerox Corporation | Rate shaping in per-flow queued routing mechanisms for available bit rate service |
| JP2930020B2 (ja) * | 1996-07-18 | 1999-08-03 | 日本電気株式会社 | 通信制御装置 |
| US5844890A (en) * | 1997-03-25 | 1998-12-01 | International Business Machines Corporation | Communications cell scheduler and scheduling method for providing proportional use of network bandwith |
| US6028843A (en) * | 1997-03-25 | 2000-02-22 | International Business Machines Corporation | Earliest deadline first communications cell scheduler and scheduling method for transmitting earliest deadline cells first |
| US6115360A (en) * | 1997-11-21 | 2000-09-05 | Texas Instruments Incorporated | Fair scheduling of ATM cell transmissions during overscheduled conditions |
-
1997
- 1997-12-18 US US08/993,801 patent/US6205151B1/en not_active Expired - Lifetime
-
1998
- 1998-11-20 JP JP33072298A patent/JPH11234309A/ja active Pending
- 1998-11-23 EP EP98204004A patent/EP0939573B1/en not_active Expired - Lifetime
- 1998-11-23 DE DE69817756T patent/DE69817756T2/de not_active Expired - Lifetime
Also Published As
| Publication number | Publication date |
|---|---|
| EP0939573A2 (en) | 1999-09-01 |
| EP0939573B1 (en) | 2003-09-03 |
| DE69817756D1 (de) | 2003-10-09 |
| US6205151B1 (en) | 2001-03-20 |
| EP0939573A3 (en) | 1999-11-10 |
| DE69817756T2 (de) | 2004-07-29 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH11234309A (ja) | 非同期転送モード・セル送信スケジューリング | |
| JPH11252127A (ja) | オーバースケジュール条件でのａｔｍセル送信の公平なスケジューリング | |
| US6914881B1 (en) | Prioritized continuous-deficit round robin scheduling | |
| US5818815A (en) | Method and an apparatus for shaping the output traffic in a fixed length cell switching network node | |
| US6389019B1 (en) | Time-based scheduler architecture and method for ATM networks | |
| US6414963B1 (en) | Apparatus and method for proving multiple and simultaneous quality of service connects in a tunnel mode | |
| US5926459A (en) | Rate shaping in per-flow queued routing mechanisms for available bit rate service | |
| US5446726A (en) | Error detection and correction apparatus for an asynchronous transfer mode (ATM) network device | |
| US6483839B1 (en) | Apparatus and method for scheduling multiple and simultaneous traffic in guaranteed frame rate in ATM communication system | |
| US6813249B1 (en) | System and method for prefetching data | |
| US6049526A (en) | Enhanced integrated rate based available bit rate scheduler | |
| US6292491B1 (en) | Distributed FIFO queuing for ATM systems | |
| US6262989B1 (en) | Apparatus and method for providing different quality of service connections in a tunnel mode | |
| JPH07321822A (ja) | マルチキャスティング機能を備えた装置 | |
| WO2000001120A9 (en) | Cbr/vbr traffic scheduler | |
| JPH07321823A (ja) | マルチキャスティング機能を備えた装置 | |
| JPH08181703A (ja) | 仮想チャネルのセルの伝送を調整する方法及び装置 | |
| US5940397A (en) | Methods and apparatus for scheduling ATM cells | |
| JPH05304534A (ja) | 複数の実体中での資源を時分割多重化する装置及びその方法 | |
| WO2002003612A2 (en) | Technique for assigning schedule resources to multiple ports in correct proportions | |
| US20050010676A1 (en) | Time-based transmission queue for traffic management of asynchronous transfer mode virtual circuits on a multi-threaded, multi-processor system | |
| JPH0818576A (ja) | 通信システム | |
| JP3157113B2 (ja) | トラヒックシェイパー装置 | |
| JP2001285362A (ja) | 動的ビットマップジェネレータスケジューラの方法及び装置 | |
| Tyan | A rate-based message scheduling paradigm |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20051108 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20070813 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20070817 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20071119 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20071122 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20071217 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20071220 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20080314 |