JPH10233802A - Ｔｃｐ接続の性能改善方法 - Google Patents

Ｔｃｐ接続の性能改善方法

Info

Publication number
JPH10233802A
JPH10233802A JP2755198A JP2755198A JPH10233802A JP H10233802 A JPH10233802 A JP H10233802A JP 2755198 A JP2755198 A JP 2755198A JP 2755198 A JP2755198 A JP 2755198A JP H10233802 A JPH10233802 A JP H10233802A
Authority
JP
Japan
Prior art keywords
queue
packet
buffer
packets
queues
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
JP2755198A
Other languages
English (en)
Other versions
JP3698884B2 (ja
Inventor
Kamer Chordury Abijitt
カマー チョーデュリー アビジット
V Rakushuman T
ティー．ヴィー．ラクシュマン
Stiriadis Dimitrios
スティリアディス ディミトリオス
Shutter Bernard
シュター バーナード
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.)
Nokia of America Corp
Original Assignee
Lucent Technologies 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 Lucent Technologies Inc filed Critical Lucent Technologies Inc
Publication of JPH10233802A publication Critical patent/JPH10233802A/ja
Application granted granted Critical
Publication of JP3698884B2 publication Critical patent/JP3698884B2/ja
Anticipated expiration legal-status Critical
Expired - Fee Related legal-status Critical Current

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/52—Queue scheduling by attributing bandwidth to queues
    • H04L47/522—Dynamic queue service slot or variable bandwidth allocation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/52—Queue scheduling by attributing bandwidth to queues
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/52—Queue scheduling by attributing bandwidth to queues
    • H04L47/525—Queue scheduling by attributing bandwidth to queues by redistribution of residual bandwidth
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—Queue scheduling characterised by scheduling criteria
    • H04L47/621—Individual queue per connection or flow, e.g. per VC
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—Queue scheduling characterised by scheduling criteria
    • H04L47/622—Queue service order
    • H04L47/623—Weighted service order
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/50—Queue scheduling
    • H04L47/62—Queue scheduling characterised by scheduling criteria
    • H04L47/625—Queue scheduling characterised by scheduling criteria for service slots or service orders
    • H04L47/6255—Queue scheduling characterised by scheduling criteria for service slots or service orders queue load conditions, e.g. longest queue first
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Buffering arrangements
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Buffering arrangements
    • H04L49/9036—Common buffer combined with individual queues
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L49/00—Packet switching elements
    • H04L49/90—Buffering arrangements
    • H04L49/9084—Reactions to storage capacity overflow
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
    • H04L69/16—Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
    • H04L69/163—In-band adaptation of TCP data exchange; In-band control procedures
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L47/00—Traffic control in data switching networks
    • H04L47/10—Flow control; Congestion control
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L69/00—Network arrangements, protocols or services independent of the application payload and not provided for in the other groups of this subclass
    • H04L69/16—Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Computer Security & Cryptography (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Telephonic Communication Services (AREA)
  • Communication Control (AREA)

Abstract

(57)【要約】 【課題】 フィードバック制御ＴＣＰネットワークの性
能を改善する。 【解決手段】 フロー毎にキューイングする装置であ
り、複数の待ち行列に区分けされた所定サイズのバッフ
ァと、所定速度に従って各バッファからパケットを除去
し、ネットワークを介して前記パケットを伝送するスケ
ジューラと、受信パケットを受信することができ、待ち
行列が使用可能である場合、パケットを待ち行列に入力
することができるバッファ内の待ち行列の使用可能性を
決定するためのコントロールデバイスとからなり、コン
トロールデバイスは更に、最長待ち行列ファーストスキ
ームに従って待ち行列を選択し、待ち行列が使用可能で
ない場合、前記受信パケットの入力を可能にするために
前記選択された待ち行列からパケットをドロッピング
し、これにより、リンクによる公平性を高め、パケット
スループットを高める。

Description

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明はＴＣＰプロトコルを
処理する通信ネットワークに関する。更に詳細には、本
発明はフィードバック制御ネットワークトラヒック用の
接続ごとのキューイング(queing)及びバッファ管理スキ
ームに関する。
【０００２】
【従来の技術】データパケットの高信頼トランスポート
を実行するためのトランスポートプロトコル“ＴＣＰ”
処理系は周知である。図１は、ＴＣＰ／ＩＰネットワー
ク（例えば、インターネット、イントラネット）におけ
る従来技術による常用のルータ装置の概要図である。
【０００３】図１において、ローカル・エリア・ネット
ワーク（ＬＡＮ）２０はルータ５０を介して広域ネット
ワーク（ＷＡＮ）６０に接続されている。一般的に、ル
ータ５０のアーキテクチャは、複数のデータストリーム
（例えば、ＬＡＮ２０に接続されたソースデータ端末か
らのもの）が単一のバッファにより受信され、かつ、リ
ンク５５を介してパケットを送信するサーバにより処理
されるようなものである。
【０００４】データパケットがその宛先（例えば、広域
ネットワーク６０に配置されたデータ端末）に到着する
と、パケットの受信機は、受信された各データパケット
について、暗黙的に又は明快に、肯定応答“ＡＣＫ”パ
ケットを発生する。ソース端末からのデータ送信は、先
行データ送信からの受信肯定応答パケットの速度により
制御される。
【０００５】従って、周知のように、ソースからのデー
タパケット送信の制御は、RichardW. Stevens, "TCP/IP
Illustrated", Vols. 1-3, Addison Weseley 1994に概
説されるように、ＴＣＰ−ＲｅｎｏとＴＣＰ−Ｔａｈｏ
ｅの、適応型スライディングウインドウスキームの２つ
の主要変形に従い、受信機からのデータＡＣＫパケット
のフィードバックにより決定される。
【０００６】ＴＣＰは長ラウンドトリップ時間を伴う接
続に対して固有の不公平性(unfairness)を示すことが確
認された。すなわち、短ラウンドトリップ時間接続は、
長ラウンドトリップ時間接続よりも大きな帯域幅を得て
しまう。なぜなら、短ラウンドトリップ時間接続の場合
のＴＣＰウインドウは、長ラウンドトリップ時間接続の
ウインドウよりも速く成長してしまうからである。これ
は、短ラウンドトリップ時間接続では接続肯定応答（Ａ
ＣＫ）がより速く受信されるためである。この固有の不
公平性を解消する効果的な解決策は未だ発見されていな
い。
【０００７】ＴＣＰに固有の別の問題点は、ウインドウ
同期(window synchronization)現象である。例えば、２
つの等しいラウンドトリップ時間接続がリンクにあると
すれば、そのリンクは飽和してしまい、バッファに蓄積
が始まる。或る時点で、そのリンクに接続されたバッフ
ァはオーバーフローしてしまう。そして、これらの接続
はおおよそ同時にパケット損失を経験する。結果的に、
各接続はそのウインドウを事実上同時に縮小し、ネット
ワークスループット速度も同時に低下してしまい、その
結果、ネットワークリンクは十分に活用されない。
【０００８】ＴＣＰ接続ネットワーク性能を低下させる
その他の問題点は、位相効果、ボトルネックリンクによ
る低リバースパスの物理的な帯域幅非対称性、バースト
トラヒックの生成、分離性の欠如、より侵略的なトラン
スポートプロトコル又は悪意的ユーザからの保護性の欠
如などである。
【０００９】ネットワーク性能を改善するために実行さ
れた或る解決法は、ランダム・アーリー・ディテクショ
ン（“ＲＥＤ”）スキームである。このスキームは、バ
ッファが飽和される前に、パケットをドロップするよう
に機能する。バッファはモニターされ、平均バッッファ
占有率が特定の閾値を越えたら、パケットは、例えば、
平均バッファ占有率（移動時間平均）の関数である特定
の確率に従ってランダムにドロップされ、結果的に、Ｔ
ＣＰ接続はそのウインドウをランダムにカットする。
【００１０】これは、ウインドウを非同期化するのに特
に有効である。特に、ＦＩＦＯ−ＲＥＤスキームでは、
リンクを多数使用する接続は、一層多くのパケットをド
ロップし易い。従って、結果的に、その対応ウインドウ
サイズもカットされる。これは、このような高速度接続
のバイアスを低下させる傾向がある。
【００１１】米国特許出願第０８／８５８３１０号明細
書に開示された別のスキームは、リバースパスが混雑し
た時に、公平性とスループットを高める効果を有するＡ
ＣＫパケットに関するフロントストラテジーからのドロ
ップを実行する。
【００１２】非ＴＣＰ開ループトラヒック（例えば、い
わゆる“リーキー・バケット(leaky-bucket)”条件付タ
イプのストリーム）の場合、等しい又は異なる重みに従
い、各入力接続間で帯域幅が共用されるように実行され
るスケジューリングスキームに従って、接続リンクの性
能を最大化するための公平待ち行列スケジューリングス
キームが実行されている。
【００１３】最近の研究努力は、エンド・ツー・エンド
遅延のバウンド(bound)及び分離(isolation)を保証する
手段として、公平待ち行列スキームを使用することに集
中的に向けられている。これに関連する研究は基本的
に、非フィードバック制御リーキーバケット管理トラヒ
ックに関するものであり、重み付公平キューイングスキ
ームによる交換機及びルータが発達した。
【００１４】例えば、A.K. Parekh and R.G. Gallager,
"A Generalized Processor Sharing Approach to Flow
Control in the Single Node Case", Proc. of INFOCO
M '92, pp. 915-924, May 1992及びD. Stiliadis and
A. Varma, "Design and Analysis of Frame-based Queu
ing: A New Traffic Scheduling Algorithm for Packet
-Switched Networks", Proc of ACM SIGMETRICS '96, p
p. 104-115, May 1996参照。
【００１５】交換機における公平キューイング（ＦＱ）
の関心は、様々なバッファ構成（例えば、物理的又は論
理的に分離されたバッファ、共用バッファなどのような
バッファ構成）を処理するためのスケジューラの使用に
集中している。
【００１６】
【発明が解決しようとする課題】トラヒックを制御し、
フィードバック制御ＴＣＰネットワークの性能を改善す
るための公平キューイングスキームの実現が強く望まれ
ている。
【００１７】更に、ＴＣＰ接続に関する相当のスループ
ットを可能にするパケットドロップ機構を実行する公平
キューイングスキームの実現が強く望まれている。
【００１８】
【課題を解決するための手段】前記課題は、本発明によ
る、フィードバック制御ＴＣＰネットワークにおける公
平キューイングスキームと共に併用されるフロー／接続
毎の共用バッファ管理スキームにより解決される。
【００１９】本発明によれば、長ラウンドトリップ時
間を伴う接続に対するＴＣＰの固有の不公平性を軽減す
る、異なるＴＣＰバージョンを用いる接続がボトルネ
ックリンクを共用する場合、分離性を与える、一層侵
略的なトラヒックソース、不品行なユーザ又はリバース
パス輻輳の場合のその他のＴＣＰ接続からの保護性を与
える、両方向トラヒックの存在下におけるＡＣＫ圧縮
作用を軽減する、ＡＣＫ損失（トラヒックのバースト
を起こす）を経験するユーザに顕著な悪影響を及ぼすそ
の他の接続から保護する、及び全体的なリンク利用率
を低下させることなく、“欲張り”接続を伴うボトルネ
ックを共用する双方向接続に対する低待ち時間を与え
る、などのようなＴＣＰの種々の目標を達成することが
できる。
【００２０】更に詳細には、共用バッファアーキテクチ
ャは、各接続のための帯域幅予約保証ｒiにより実行さ
れる。速度ｒiのそのバッファを完全に使用する第１の
接続と、十分に利用されない（無駄使いされる）、速度
ｒ2の第２の接続があり、第１の接続が更に一層の帯域
幅を必要とする場合、共用バッファスキームでは、ｒ2
接続からバッファリング（帯域幅）を借りることもでき
る。
【００２１】第２の接続がそのバッファスペースを矯正
しなければならない場合、別の利用バッファからのデー
タを押し出し、着信データパケットのための場所を空け
なければならない。
【００２２】接続毎の待ち行列（キュー）管理スキーム
は、共用バッファアーキテクチャにおけるパケットドロ
ッピングメカニズム（例えば、最長待ち行列ファースト
（“ＬＱＦ”））をサポートし、ＦＩＦＯ−ＲＥＤバッ
ファ管理スキームよりも優れたＴＣＰ性能を生じる。本
明細書では、公平性は、全リンク容量に対する個々のス
ループットの割合の平均値に対する標準偏差の比により
計算する。
【００２３】
【発明の実施の形態】図２は、様々なソースｓ1，・・
・，ｓ2から発信するパケットトラヒックを処理するＴ
ＣＰネットワーク接続のルータ６５のための接続毎の待
ち行列アーキテクチャを示すブロック図である。
【００２４】ネットワーク接続要素は、汎用の共用バッ
ファメモリＢを有する。このメモリＢは、速度Ｃでリン
ク５５上のデータパケットを処理するスケジューラ７５
と単一（ボトルネック）のリンク５５との接続のため
に、“ｉ”個の複数の待ち行列３０ａ，・・・，ｉに分
割されている。各バッファ接続ｉは、接続ｉの保証バッ
ファサイズである名目バッファ割当てｂiを有する。
“フロー毎のキューイング”又は“接続毎のキューイン
グ”として知られているこのアーキテクチャでは、待ち
行列に入れられるべき到着パケットのきめ細かい動的分
類が必要である。
【００２５】“ソフト状態”アプローチは、潜在的に非
常に多数のおそらく活性な接続（この場合、大多数の接
続は実際には活性ではないであろう）へ導く接続状態を
維持する。ネットワークノード内の関連状態はその他の
ガーベジ・コレクション（ごみ集め）の手段によりタイ
ムアウト（時間切れ）を起こさせるか、矯正させるか又
は遅延させるために待機される。従って、スケーラビリ
ィティ(scalability)及び共用は、接続毎のサーバーの
ための基本的な要件である。必要な全ての操作は、０
（１）複雑さにより実行可能であり、リソース（バッフ
ァ又は帯域幅）は所定の接続には静的に割当てられな
い。
【００２６】操作中、スケジューラー７５は、各待ち行
列について同等であるか又は所定の重みに応じた、ｒi
に等しい速度で各個別待ち行列ｉを処理する。速度ｒi
で広い帯域幅を使用する特定の待ち行列（接続）（例え
ば、待ち行列３０ａ）は、その他の待ち行列よりも長い
待ち行列を有する傾向がある。全ての待ち行列接続が、
それらの各帯域幅割当を完全に利用している場合、待ち
行列３０ａはおそらくバッファオーバーフローを経験す
るであろう。
【００２７】或る割当てメモリ（例えば、３０ｃ）が完
全に利用されていない場合、本発明の公平キューイング
（ＦＱ）スキームは、待ち行列３０ｂに到着するデータ
パケットのために、必要に応じて、十分に利用されてい
ない待ち行列からバッファスペースを利用するか又は借
りることができる。従って、バッファ待ち行列３０ａの
予約割当てｂiを越えることができる。
【００２８】第１の高速バッファ待ち行列３０ａのため
のパケットを受信する第２のバッファが満杯になると、
別の十分に利用されていないバッファ（例えば、待ち行
列３０ｉ）は、待ち行列３０ａに宛てられる新たなデー
タパケットにバッファスペースを貸す。
【００２９】同時に２つ以上の待ち行列がバッファオー
バーフローを経験することもでき、そのため、十分に利
用されていないバッファスペースから借りることもでき
る。従って、２つ以上の待ち行列がその予約割当てｂi
を越えることもできる。本発明は、ＴＣＰ接続ネットワ
ークのフォワード及びリバース接続の両方に適用可能で
あり、また、データ及びＡＣＫトラヒックフローの両方
に同等に適用可能である。
【００３０】接続ｉが（ｂi＋１）個以上のバッファを
必要とする場合、総占有率がＢ未満であるとすれば、使
用可能なプールからスペースが割当てられる。
【００３１】図３（ａ）は、本発明の接続毎の待ち行列
スキームを実行するための一般的な流れ図である。ステ
ップ２０１に示されるように、接続ｉについて宛てられ
たパケットが到着すると、最初のステップ２０３で、バ
ッファＢの現に残っている使用可能なスペースを有する
カウンタをチェックし、新たに到着したパケットを確実
に収容するための十分なメモリスペースがバッファ内に
残存しているか否か決定する。
【００３２】新たに到着したパケットを確実に収容する
ための十分なメモリスペースがバッファ内に残存してい
る場合、ステップ２０８で処理が継続され、到着パケッ
トが属する接続ｉを識別し、そして、ステップ２１１
で、このパケットを、この接続に対応する待ち行列に格
納する。このスキームに潜在的に含まれることは、到着
パケットが適正に分類され、そして、待ち行列のうちの
一つに割当てられることである。
【００３３】ステップ２０３において、新たに到着した
パケットを確実に収容するための十分なメモリスペース
がバッファ内に残存していないと決定される場合（例え
ば、現在の占有率ｑiがｂj未満である待ち行列３０ｊが
バッファを必要とする場合）、ステップ２２５において
追出しスキームが実行され、到着パケットのために場所
を空ける。特に、呼出されたＴＣＰプロトコルの実行に
応じて、追出しが行われる待ち行列を選択するための２
つの方法が使用できる。
【００３４】特に、図４（ｂ）に示されるように、第１
の実施態様における追出しメカニズムは、ＬＱＦスキー
ムであり、別の待ち行列から予約された最大量のメモリ
を借りる待ち行列、すなわち、（ｑi−ｂi）が全ての接
続を通して最大であるような接続ｉを選択する。例え
ば、ステップ２５０に示されるように、バッファ内の各
待ち行列の現在のバッファ割当てに関する決定が行われ
る。
【００３５】次いで、ステップ２６０で、各待ち行列の
現在の待ち行列長さｑiを取得し、ステップ２７０で、
各待ち行列の（ｑi−ｂi）差に関する計算を行う。最後
に、ステップ２７５において、最大の（ｑi−ｂi）差を
有する待ち行列を選択する。従って、その予約割当てｂ
iからの最大偏差は最長待ち行列であり、このため、図
３（ａ）のステップ２２６で示されるように、到着パケ
ットと先入れ相関関係を有する待ち行列からパケットが
ドロップされる。
【００３６】当業者ならば前記の最長待ち行列を最初に
追出すスキーム（ＬＱＦスキーム）を実行するためのそ
の他のアルゴリズムを案出することもできるので、本発
明は図４（ｂ）に示された方法論に限定されない。例え
ば、最長遅延ファースト（“ＬＤＦ”）ドロッピングメ
カニズムは、割当て処理速度ｒiが全て等しい場合、Ｌ
ＱＦスキームと同等に実行できる。なぜなら、待ち行列
が同じ速度で処理される場合、遅延は各接続について同
一だからである。同様に、処理速度が均一でない場合、
待ち行列長さが同一であっても、遅延は異なる。従っ
て、ＬＱＦスキームはＬＤＦの特例である。
【００３７】第２の最長待ち行列よりもかなり長い待ち
行列を有する多数の接続を有するシステムで実行する場
合、最長待ち行列ファースト（ＬＱＦ）は過度のバース
ト損失をもたらすことがある。すなわち、２個以上の非
常に接近したパケットは、その割当てを越える待ち行列
から連続的にドロップされる。例えば、ＴＣＰ−Ｒｅｎ
ｏ型処理系はバースト損失の存在下で不良動作を行うこ
とが知られているので、ＴＣＰ−Ｒｅｎｏアーキテクチ
ャを実行する接続の性能は悪影響を受ける。従って、前
記ＬＱＦにおけるバースト損失量を低下するために、ス
キームは、それぞれの割当てを越えるバッファからラン
ダムに摘出するランダムジェネレータを使用するように
変更されている。
【００３８】特に、第２の実施態様では、各バックロッ
グ接続（backlogged connection:予備接続）ｉは、ｂi
＝Ｂ／ｎ（ここで、ｎはバックロッグ接続の個数であ
る）で示される名目バッファ割当てを有する。図５
（ｃ）に示されるように、ステップ２５５で、各待ち行
列のメモリ割当てｂiを取得する。次いで、ステップ２
６５で、バックロッグ接続を例えば、２個のサブセット
にグループ分けする。一方は、ｂiよりも大きな占有率
ｑiを有するグループであり、他方は、ｑi≦ｂiの関係
を有するグループである。
【００３９】割当てより上（すなわち、ｑi＞ｂi）の待
ち行列群から、ステップ２８５で示されるように、１つ
の待ち行列がランダムに選択され、そして、ステップ２
２６で示されるように、１つのパケットが先頭からドロ
ップされる。
【００４０】異なる接続に関するバッファ占有率を平坦
化し、そして、システムに過負荷をかける接続から最適
に保護するための試みにおいて、L. Georgiadis, I. Ci
don,R. Guerin, and A. Khamisy, "Optimal Buffer Sha
ring," IEEE J. Select. Areas Commun., vol. 13, pp.
1229-1240, Sept. 1995に記載されるような開ループト
ラヒックについて実行されるスキームと同様な方法で、
特定の追出し(pushout)スキームは最長待ち行列の先頭
からパケットをドロップする。
【００４１】図６に示されるように、ハードウエアの観
点から、カウンタ９０ａ，・・・，９０ｉは、それぞれ
の付随待ち行列の占有率ｑiのトラックを保持するよう
にプログラムされたコントロールプロセッサ９２と共
に、各待ち行列３０ａ，・・・，３０ｉに関連するよう
に図示されている。従って、図４（ｂ）及び図５（ｃ）
のステップ２６０及び２６５において、現在の待ち行列
長さは、例えば、ポーリングにより、又は、図６のテー
ブル９９のようなレジスタテーブル（ここで、レジスタ
は最長待ち行列長さを示す）から位置指定することによ
り取得される。
【００４２】別のカウンタ９５は、総バッファ占有率Ｂ
のトラックを保持するために図示されている。従って、
パケットが到着すると、プロセッサ９２は、カウンタ９
５で使用可能な総メモリを決定するために、ステップ２
０３（図３（ａ）参照）におけるチェックを行う。
【００４３】最長待ち行列を決定するために、プロセッ
サ９２はソート済み構造を実行することもできる。例え
ば、各キューに入れる、キューから外す又はドロップ操
作の時点で、待ち行列の対応カウンタがそれに応じて増
分又は減分された後、最長待ち行列構造を常に知ってお
くために、その待ち行列占有率値ｑiを現在の最長待ち
行列占有率値と比較するように、ソート済み構造を実行
する。
【００４４】これらフロー毎のスキームの変法は、指数
関数的に増大するサイズを有する一連のビンを使用する
ことにより効率的に実行することができる。待ち行列が
変更される場合（例えば、キューに入れる、キューから
外す又はドロップする場合）は常に、システムは最高占
有ビンのトラックを保持しながら、適当なビン（例え
ば、現在のビンと同一のビン、一つ上のビン又は一つ下
のビン）に移動させる。
【００４５】バッファが満杯の場合、最高占有ビンから
の待ち行列が選択され、その最初のパケットがドロップ
される。バッファがバイト単位で測定される場合、この
操作は、可変パケットサイズのため、新たに到着したパ
ケットを収容するために十分なスペースが解放されるま
で、繰り返さなければならない。真のＬＱＤを行うため
に、最高占有ビンにおける待ち行列をソート済みリスト
として維持するか、又はいつも最長待ち行列をサーチし
なければならない。
【００４６】ＦＩＦＯ−ＲＥＤ及びＦＱ−ＲＥＤスキー
ムと比較される本発明のバッファ管理スキームの改善さ
れた性能のシミュレーションについて説明する。図７
は、このシミュレーションシステム１１９を示す概要図
である。図７において、ソース１０１ａ，・・・，１０
１ｆはルータ１２０への高速アクセスパスを有する。ル
ータ１２０は唯一のボトルネックであり、本発明の接続
／フロー毎のバッファ管理スキームを実行するものであ
る。
【００４７】比較は、ＴＣＰ−Ｔａｈｏｅ及びＴＣＰ−
Ｒｅｎｏソース、バースト及び欲張りソース（greedy s
ource)、リバースパス輻輳を有する片方向及び両方向ト
ラヒックソース、及び広範囲に異なるラウンドトリップ
時間の混合を用いて行われる。アクセスパス遅延は、様
々なラウンドトリップ時間のモデルを作るために広範囲
にわたって設定され、宛先はパケット毎にＡＣＫと仮定
した。
【００４８】片方向トラヒックの場合、ＡＣＫは非輻輳
パスを介して送信される。両方向トラヒックの場合、リ
ターンパスはルータを経由し、そのため、キューイング
（待合わせ）遅延が生じることがある。特に、ルータが
ＦＩＦＯスケジューリングを使用する場合、ＡＣＫ及び
データパケットは待ち行列内で混合される。公平キュー
イングの場合、ＡＣＫは別のフローとして処理される。
非対称トラヒックの場合、リターンリンクの帯域幅は、
宛先からルータまで低下される。そのため、相当なリバ
ースパス輻輳とＡＣＫ損失が生じる。
【００４９】シミュレーションシステム１１９における
ＴＣＰ−Ｔａｈｏｅ及びＴＣＰ−Ｒｅｎｏの処理系は、
４．３−Ｔａｈｏｅ ＢＳＤ及び４．３−Ｒｅｎｏ Ｂ
ＳＤのＴＣＰフローと輻輳制御挙動とをそれぞれモデル
化する。ＲＥＤモデルは有向パケットであり、最小閾値
としてバッファサイズの２５％を使用し、最大閾値とし
てバッファサイズの７５％を使用する。待ち行列重みは
０．００２である。
【００５０】図８（ａ）及び（ｂ）は、従来技術による
ＦＩＦＯ−ＲＥＤ及びＬＱＦ法と比較されるような、利
用率及び公平性のそれぞれの観点から、擬似ＴＣＰネッ
トワークで公平待ち行列ＬＱＤ及びＲＮＤドロップ法を
実行した場合の、改善された性能を示す特性図である。
【００５１】特に、図８（ａ）及び（ｂ）は、図７の擬
似ネットワークにおける１０Ｍｂｐｓ／１００ｋｂｐｓ
容量（ＴＣＰ−Ｔａｈｏｅ及びＴＣＰ−Ｒｅｎｏの２０
ｍｓ−１６０ｍｓラウンドトリップ時間）を有する非対
称ボトルネックリンクによる２０個のＴＣＰ接続のため
のバッファサイズ（で表したリンク速度）の関数とし
て、スループット（図８（ａ））及び公平性係数（図８
（ｂ））により評価される改善されたＴＣＰ性能を示
す。
【００５２】図示されているように、ライン１３７ａ及
び１３８ａでそれぞれ示されるＦＱ（公平キューイン
グ）−ＲＥＤ及びＦＩＦＯ−ＲＥＤの両戦略は、ライン
１３９及び１４０で示されるＦＱ−ＬＱＦ及びＦＱ−Ｒ
ＮＤドロップ法よりも非常に低いスループットを有す
る。なぜなら、再送パケットに対応するＡＣＫが、擬似
非対称値が３（これは帯域幅非対称ではない）の場合の
時間が６６％も喪失されるからである。これは、ＴＣＰ
サイクルの少なくとも６６％でタイムアウト（時間切
れ）を生じ、スループットを著しく低下させる。
【００５３】フォワードパスにおける多数の損失及びフ
ォワードパスにおける再送パケットの損失のために、そ
の他のタイムアウトも起こる。一方、リバースパスにお
ける先頭からのドロップはこれらのタイムアウトを殆ど
完全に除去する。タイムアウトは不経済なので、両方の
ＲＥＤスキームとも、ＦＩＦＯ−ＬＱＤを含むその他の
スキームよりも著しく低いスループットを有する。
【００５４】更に、図８（ｂ）に示されるように、ＦＱ
−ＲＮＤ及びＦＱ−ＬＱＤワークの両方とも非常に良好
である。なぜなら、これらは、フロー毎の待ち行列の効
果と、先頭からのドロップのタイムアウト除去効果とを
併有するからである。ＦＱ−ＬＱＤは、再送パケットの
ドロップに対する組込みバイアスを有するという別の効
果も有する。これは、ソースが最初の重複ＡＣＫの受信
による損失を検出したときに、パケットの送信を中止す
るからである。
【００５５】第３の重複ＡＣＫが受信された後にだけ、
再送パケットが送信される。介入間隔中、ソースがＴＣ
Ｐにより強制的に不活動化される場合、フローに対応す
る待ち行列は、少なくともその最小保証速度で排出され
る。従って、再送パケットが到着する場合、最長待ち行
列であることは殆どない。従って、再送パケットのドロ
ッピングに対する固有バイアスである。このバイアスは
非対称ネットワークに限定されないが、低速リバースチ
ャネル膨張のために、非対称要因、第１の重複ＡＣＫ受
信と第３の重複ＡＣＫ受信との間の間隔により、バイア
スは非対称ネットワークにおいて高められる。
【００５６】再送パケットの損失は不経済なタイムアウ
トを起こすので、このバイアスは、図８（ｂ）において
ライン１４１で示されるように、ＦＱ−ＬＱＤの性能を
改善する。ライン１４２で示されるＦＱ−ＲＮＤも同様
にこのバイアスを有するが、著しく低い。その理由は、
ＦＱ−ＬＱＤに対するものと若干類似している。
【００５７】第１の重複ＡＣＫ受信と第３の重複ＡＣＫ
受信との間の間隔中に、フローの待ち行列は、（ソース
は不活動化されているので）少なくともその保証速度と
等しい速度で流出し、待ち行列占有率はこのフローの予
約パラメーター以下にまで落ちるであろう。この場合、
再送パケットが到着すると、集合バッファが満杯であっ
たとしても、再送パケットは失われない。これらの効果
より、ＦＱ−ＬＱＤ及びＦＱ−ＲＮＤは最高の性能を有
する。
【００５８】
【発明の効果】以上説明したように、本発明によれば、
長ラウンドトリップ時間を伴う接続に対するＴＣＰの
固有の不公平性を軽減する、異なるＴＣＰバージョン
を用いる接続がボトルネックリンクを共用する場合、分
離性を与える、一層侵略的なトラヒックソース、不品
行なユーザ又はリバースパス輻輳の場合のその他のＴＣ
Ｐ接続からの保護性を与える、両方向トラヒックの存
在下におけるＡＣＫ圧縮作用を軽減する、ＡＣＫ損失
（トラヒックのバーストを起こす）を経験するユーザに
顕著な悪影響を及ぼすその他の接続から保護する、及び
全体的なリンク利用率を低下させることなく、“欲張
り”接続を伴うボトルネックを共用する双方向接続に対
する低待ち時間を与える、などのようなＴＣＰの種々の
目標を達成することができる。
【図面の簡単な説明】
【図１】従来技術によるＴＣＰネットワーク接続を示す
ブロック図である。
【図２】多数のＴＣＰ接続のための共用バッファアーキ
テクチャのブロック図である。
【図３】（ａ）はバッファ割当て及びパケットドロッピ
ングスキームを行うために履行される方法を示す流れ図
であり、図３、図４、図５で１つの流れ図を形成する。
【図４】（ｂ）はＬＱＦパケットドロップ法を示す流れ
図である。
【図５】（ｃ）はＲＮＤパケットドロップ法を示す流れ
図である。
【図６】各バッファ待ち行列に関連するハードウエアを
示すブロック図である。
【図７】公平キューイングを処理するルータを有するＴ
ＣＰ／ＩＰネットワークのシミュレーションを示すブロ
ック図である。
【図８】（ａ）は図７の擬似ネットワークにおけるボト
ルネックリンクによる２０個のＴＣＰ接続のためのバッ
ファサイズ（で表したリンク速度）の関数として、スル
ープットにより評価される改善されたＴＣＰ性能を示す
特性図である。（ｂ）は図７の擬似ネットワークにおけ
るボトルネックリンクによる２０個のＴＣＰ接続のため
のバッファサイズの関数として、公平性係数（全リンク
容量に対する個々のスループットの割合の平均値に対す
る標準偏差の比）により評価される改善されたＴＣＰ性
能を示す特性図である。
【符号の説明】
３０ 待ち行列（キュー） ５５ ルータ ６５ ルータ ７５ スケジューラ ９２ コントロールプロセッサ ９５ カウンタ ９９ レジスタテーブル １０１ ソース １１９ シミュレーションシステム １２０ ルータ
───────────────────────────────────────────────────── フロントページの続き (71)出願人 596077259 600 Ｍｏｕｎｔａｉｎ Ａｖｅｎｕｅ, Ｍｕｒｒａｙ Ｈｉｌｌ， Ｎｅｗ Ｊｅ ｒｓｅｙ 07974−0636Ｕ．Ｓ．Ａ. (72)発明者 ティー．ヴィー．ラクシュマン アメリカ合衆国，07724 ニュージャージ ー，イートンタウン，ヴィクトリア ドラ イブ 118 (72)発明者 ディミトリオス スティリアディス アメリカ合衆国，07030 ニュージャージ ー，ホボケン，パーク アヴェニュー 106 (72)発明者 バーナード シュター アメリカ合衆国，07747 ニュージャージ ー，アバーディーン，アイダホ レイン 12

Claims (20)

    【特許請求の範囲】
  1. 【請求項１】 (i)所定サイズのバッファを複数個の待
    ち行列に区分けするステップと、 ここで、各待ち行列は、情報パケットを受信し、一時的
    に格納するための占有率ｂiが割り当てられ、また、各
    バッファからパケットを除去し、そして、前記パケット
    をＴＣＰ接続を介して伝送するためのスケジューラによ
    り処理される、 (ii)パケットが到着すると、前記パケットを受信するた
    めの待ち行列の使用可能性を決定し、前記待ち行列が使
    用可能である場合、前記パケットを待ち行列に入力する
    ステップと、 (iii)前記待ち行列が使用可能でない場合、前記パケッ
    トの入力を可能にするため、待ち行列を選択し、そし
    て、前記選択された待ち行列からパケットを解放するス
    テップとからなり、これによりＴＣＰ接続の利用率を高
    めることを特徴とするＴＣＰ接続の性能改善方法。
  2. 【請求項２】 パケット到着時又は離脱時に、各待ち行
    列の現在の長さｑiをトラッキングするステップを更に
    有する請求項１の方法。
  3. 【請求項３】 トラッキングステップは、パケットが前
    記待ち行列に入力されるたびに、前記待ち行列に付随す
    るカウンタを増分するか、又は、パケットが前記待ち行
    列から解放されるときに、前記カウンタを減分するステ
    ップを有する請求項２の方法。
  4. 【請求項４】 前記スケジューラは所定の速度で前記各
    バッファからパケットを除去することができる請求項１
    の方法。
  5. 【請求項５】 前記バッファ待ち行列が満杯の場合、前
    記満杯待ち行列に宛てられたパケットが到着すると、満
    杯ではない１つ以上の待ち行列からバッファスペースを
    一時的に借りるステップを有し、前記満杯待ち行列の前
    記現在の長さはその名目的な占有率ｂiを越える請求項
    ２の方法。
  6. 【請求項６】 待ち行列の使用可能性を決定する前記ス
    テップは、所定サイズの前記バッファが満杯であるか否
    かを決定するステップを有する請求項５の方法。
  7. 【請求項７】 前記選択された待ち行列から解放される
    べき前記パケットは、前記待ち行列に内在する最も古い
    パケットである請求項２の方法。
  8. 【請求項８】 待ち行列を選択する前記ステップは、 (a)各待ち行列について現在の割当てｂiを確立するステ
    ップと、 (b)前記各待ち行列の現在の待ち行列長さの値ｑiを取得
    するステップと、 (c)現在の待ち行列長さの値ｑiと、各待ち行列の割当て
    られたバッファ占有率ｂiとの間の差を計算するステッ
    プと、 (d)計算された差で最も大きな値を有する前記待ち行列
    を選択するステップとを有する請求項２の方法。
  9. 【請求項９】 待ち行列を選択する前記ステップは、 (a)各待ち行列について現在の割当てｂiを確立するステ
    ップと、 (b)現在の待ち行列長さの値ｑiが各待ち行列の割当てら
    れたバッファ占有率ｂiを越える一連の待ち行列を計算
    するステップと、 (c)前記一連の待ち行列からランダムに待ち行列を選択
    するステップとを有する請求項２の方法。
  10. 【請求項１０】 前記スケジューラは異なる所定速度に
    従って各バッファからパケットを除去し、待ち行列を選
    択する前記ステップは、 (a)そのそれぞれの待ち行列長さｑiとその所定のサービ
    ス速度から各待ち行列に格納されたパケットにより経験
    されるキューイング遅延を計算するステップと、 (b)最も長いキューイング遅延を経験する待ち行列を選
    択するステップとを有する請求項２の方法。
  11. 【請求項１１】 前記選択ステップは、 (a)１つ以上のビンを確立するステップと、ここで各ビ
    ンは所定の長さの１つ以上の待ち行列に結合される、 (b)最長長さを有する１つ以上の待ち行列に結合された
    ビンから待ち行列をランダムに選び取るステップを更に
    有する請求項２の方法。
  12. 【請求項１２】 複数のソースからの情報パケットをＴ
    ＣＰ／ＩＰネットワーク内の単一の通信リンクへ通信す
    るルータであり、 (a)複数個の待ち行列に区分けされた所定サイズのバッ
    ファと、ここで、各待ち行列は、情報パケットを受信
    し、一時的に格納するための占有率ｂiが割り当てられ
    る、 (b)各バッファからパケットを除去し、また、前記接続
    を介して前記パケットを伝送するためのスケジューラ
    と、 (c)前記バッファの前記待ち行列が使用可能である場
    合、前記待ち行列に受信バッファを入力し、更に、前記
    バッファの前記待ち行列が使用可能でない場合、待ち行
    列を選択し、前記受信パケットの入力を可能にするた
    め、前記スケジューらが前記選択された待ち行列からパ
    ケットを解放できるようにするための、前記バッファ内
    の待ち行列に使用可能性を決定するコントロール手段
    と、からなること特徴とするルータ。
  13. 【請求項１３】 パケットが入力されるたびに、又は前
    記待ち行列から解放されるたびに、前記待ち行列の現在
    の長さｑiをトラッキングするための、前記各待ち行列
    に結合された手段を更に有する請求項１２のルータ。
  14. 【請求項１４】 前記トラッキング手段は、前記待ち行
    列に結合されたカウンタデバイスを有し、前記カウンタ
    デバイスは、パケットが前記待ち行列に入力されるたび
    に増分し、パケットが前記待ち行列から解放されるとき
    は減分する請求項１３のルータ。
  15. 【請求項１５】 前記コントロール手段は、 (a)前記各待ち行列の現在の待ち行列長さの値ｑiを取得
    する手段と、 (b)現在の待ち行列長さの値ｑiと、各待ち行列について
    割当てられたバッファ占有率ｂiとの間の差を計算する
    手段とを有し、計算された差で最大の値を有する前記待
    ち行列を選択する請求項１３のルータ。
  16. 【請求項１６】 前記コントロール手段は、 (a)現在の待ち行列長さの値ｑiが各待ち行列について割
    当てられたバッファ占有率ｂiを越える一連の待ち行列
    を計算する手段と、 (b)前記一連の待ち行列からランダムに待ち行列を選択
    する手段とを更に有する請求項１３のルータ。
  17. 【請求項１７】 前記選択された待ち行列から解放され
    るべき前記パケットは、前記待ち行列に内在する最も古
    いパケットである請求項１２のルータ。
  18. 【請求項１８】 前記スケジューラは異なる所定速度に
    従って各バッファからパケットを除去し、前記コントロ
    ール手段は、 (a)そのそれぞれの待ち行列長さｑiとその所定のサービ
    ス速度から各待ち行列に格納されたパケットにより経験
    されるキューイング遅延を計算する手段と、 (b)最も長いキューイング遅延を経験する待ち行列を選
    択する手段とを更に有する請求項１３のルータ。
  19. 【請求項１９】 １つ以上のソースからの情報パケット
    をリンクを介して宛先へ流すことができるフィードバッ
    ク制御ＴＣＰ接続からトラヒックを搬送するＩＰネット
    ワークのためのフロー毎のキューイング装置であり、 (a)複数個の待ち行列に区分けされた所定サイズのバッ
    ファと、ここで、各待ち行列は、情報パケットを受信
    し、一時的に格納するための占有率ｂiが割当てられ
    る、 (b)所定の速度に従って各バッファからパケットを除去
    し、また、前記ネットワークを介して前記パケットを伝
    送するためのスケジューラと、 (c)前記受信パケットを受信することができ、前記待ち
    行列が使用可能である場合、前記パケットを前記待ち行
    列に入力することができる前記バッファ内の待ち行列の
    使用可能性を決定するためのコントロールデバイスとか
    らなり、前記コントロールデバイスは更に、最長待ち行
    列ファーストスキームに従って待ち行列を選択し、そし
    て、前記待ち行列が使用可能でない場合、前記受信パケ
    ットの入力を可能にするために前記選択された待ち行列
    からパケットをドロッピングし、これにより、前記リン
    クによる公平性を高め、パケットスループットを高める
    ことを特徴とするフロー毎のキューイング装置。
  20. 【請求項２０】 １つ以上のソースからの情報パケット
    をリンクを介して宛先へ流すことができるフィードバッ
    ク制御ＴＣＰ接続からトラヒックを搬送するＩＰネット
    ワークのためのフロー毎のキューイング方法であり、 (a)複数個の待ち行列に区分けされた所定サイズのバッ
    ファを提供するステップと、ここで、各待ち行列は、情
    報パケットを受信し、一時的に格納するための占有率ｂ
    iが割当てられる、 (b)所定の速度に従って各バッファからパケットを除去
    し、また、前記ネットワークを介して前記パケットを伝
    送するためのスケジューラを提供するステップと、 (c)前記受信パケットを受信することができ、前記待ち
    行列が使用可能である場合、前記パケットを前記待ち行
    列に入力することができる前記バッファ内の待ち行列の
    使用可能性を決定するためのコントロールデバイスを提
    供するステップとからなり、前記コントロールデバイス
    は更に、最長待ち行列ファーストスキームに従って待ち
    行列を選択し、そして、前記待ち行列が使用可能でない
    場合、前記受信パケットの入力を可能にするために前記
    選択された待ち行列からパケットをドロッピングし、こ
    れにより、前記リンクによる公平性を高め、パケットス
    ループットを高めることを特徴とするフロー毎のキュー
    イング方法。
JP02755198A 1997-02-07 1998-02-09 Ｔｃｐ接続の性能改善方法 Expired - Fee Related JP3698884B2 (ja)

Applications Claiming Priority (4)

Application Number Priority Date Filing Date Title
US3784397P 1997-02-07 1997-02-07
US60/037843 1997-10-30
US08/961,122 US6092115A (en) 1997-02-07 1997-10-30 Method for supporting per-connection queuing for feedback-controlled traffic
US08/961122 1997-10-30

Related Child Applications (1)

Application Number Title Priority Date Filing Date
JP2005135986A Division JP2005295581A (ja) 1997-02-07 2005-05-09 Ｔｃｐ接続の性能改善方法

Publications (2)

Publication Number Publication Date
JPH10233802A true JPH10233802A (ja) 1998-09-02
JP3698884B2 JP3698884B2 (ja) 2005-09-21

Family

ID=26714552

Family Applications (3)

Application Number Title Priority Date Filing Date
JP02755198A Expired - Fee Related JP3698884B2 (ja) 1997-02-07 1998-02-09 Ｔｃｐ接続の性能改善方法
JP2005135986A Abandoned JP2005295581A (ja) 1997-02-07 2005-05-09 Ｔｃｐ接続の性能改善方法
JP2009144932A Pending JP2009207208A (ja) 1997-02-07 2009-06-18 Ｔｃｐ接続の性能改善方法

Family Applications After (2)

Application Number Title Priority Date Filing Date
JP2005135986A Abandoned JP2005295581A (ja) 1997-02-07 2005-05-09 Ｔｃｐ接続の性能改善方法
JP2009144932A Pending JP2009207208A (ja) 1997-02-07 2009-06-18 Ｔｃｐ接続の性能改善方法

Country Status (5)

Country Link
US (1) US6092115A (ja)
EP (1) EP0872988B1 (ja)
JP (3) JP3698884B2 (ja)
CA (1) CA2227244C (ja)
DE (1) DE69834763T2 (ja)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2005020523A1 (ja) * 2003-08-20 2005-03-03 Nec Corporation セッション中継装置及び中継方法
JP2008136176A (ja) * 2006-10-10 2008-06-12 Mitsubishi Electric Information Technology Centre Europa Bv メモリブロックの割り当てを管理する方法及びデバイス、データ伝送ネットワークシステム、コンピュータ可読媒体、並びにコンピュータプログラム製品

Families Citing this family (79)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6252851B1 (en) * 1997-03-27 2001-06-26 Massachusetts Institute Of Technology Method for regulating TCP flow over heterogeneous networks
US6591299B2 (en) * 1997-11-25 2003-07-08 Packeteer, Inc. Method for automatically classifying traffic with enhanced hierarchy in a packet communications network
US6412000B1 (en) * 1997-11-25 2002-06-25 Packeteer, Inc. Method for automatically classifying traffic in a packet communications network
US6438101B1 (en) * 1997-12-23 2002-08-20 At&T Corp. Method and apparatus for managing congestion within an internetwork using window adaptation
JP3927714B2 (ja) * 1997-12-31 2007-06-13 ユーティースターコム コリア リミテッド 予想型／保障型サービスを提供するためのトラフィック制御方法
US6363069B1 (en) * 1998-06-30 2002-03-26 At&T Corp. Complete packet discarding
SE514302C2 (sv) * 1998-12-01 2001-02-05 Ericsson Telefon Ab L M Köhantering i paketkopplade nät
US6606301B1 (en) * 1999-03-01 2003-08-12 Sun Microsystems, Inc. Method and apparatus for early random discard of packets
US6278995B1 (en) * 1999-03-02 2001-08-21 Nms Communications Corporation Apparatus and method for providing a binary range tree search
US6295532B1 (en) * 1999-03-02 2001-09-25 Nms Communications Corporation Apparatus and method for classifying information received by a communications system
SE514313C2 (sv) 1999-04-07 2001-02-12 Telia Ab Förbättringar av, eller med avseende på, datapaketförmedling
US6721309B1 (en) * 1999-05-18 2004-04-13 Alcatel Method and apparatus for maintaining packet order integrity in parallel switching engine
US7149664B1 (en) * 1999-06-02 2006-12-12 Nortel Networks Limited Method and apparatus for queue modeling
US6678271B1 (en) * 1999-07-12 2004-01-13 Nortel Networks Limited High performance system and method having a local bus and a global bus
US7054267B2 (en) * 1999-09-10 2006-05-30 Lucent Technologies Inc. Method and apparatus for scheduling traffic to meet quality of service requirements in a communication network
US20020048277A1 (en) * 2000-05-01 2002-04-25 Bennett Jon C.R. Packetized data discard
US7032023B1 (en) * 2000-05-16 2006-04-18 America Online, Inc. Throttling electronic communications from one or more senders
WO2001089174A2 (en) * 2000-05-16 2001-11-22 America Online, Inc. E-mail sender identification
US7725587B1 (en) * 2000-08-24 2010-05-25 Aol Llc Deep packet scan hacker identification
US7711790B1 (en) * 2000-08-24 2010-05-04 Foundry Networks, Inc. Securing an accessible computer system
US6975638B1 (en) * 2000-10-13 2005-12-13 Force10 Networks, Inc. Interleaved weighted fair queuing mechanism and system
CN100420250C (zh) * 2000-11-29 2008-09-17 英国电讯有限公司 通信设备操作方法、数据呈现方法和设备
US6856596B2 (en) * 2000-12-01 2005-02-15 Marconi Communications, Inc. Approximation of the weighted random early detection buffer admittance algorithm
US7149187B1 (en) * 2000-12-28 2006-12-12 Cisco Technology, Inc. Random early detection policer using randomization of packet drops
US7542419B2 (en) * 2001-04-02 2009-06-02 International Business Machines Corporation Method and apparatus for managing aggregate bandwidth at a server
US6901046B2 (en) * 2001-04-03 2005-05-31 Nokia Corporation Method and apparatus for scheduling and modulation and coding selection for supporting quality of service in transmissions on forward shared radio channels
US20020176359A1 (en) * 2001-05-08 2002-11-28 Sanja Durinovic-Johri Apparatus for load balancing in routers of a network using overflow paths
US20020176363A1 (en) * 2001-05-08 2002-11-28 Sanja Durinovic-Johri Method for load balancing in routers of a network using overflow paths
US7206282B1 (en) * 2001-05-29 2007-04-17 F5 Networks, Inc. Method and apparatus to balance flow loads in a multipurpose networking device
GB2372172B (en) * 2001-05-31 2002-12-24 Ericsson Telefon Ab L M Congestion handling in a packet data network
JP3908483B2 (ja) * 2001-06-28 2007-04-25 富士通株式会社 通信装置
US7406041B2 (en) * 2001-07-31 2008-07-29 Brocade Communications Systems, Inc. System and method for late-dropping packets in a network switch
JP2005503722A (ja) * 2001-09-21 2005-02-03 ブリティッシュ・テレコミュニケーションズ・パブリック・リミテッド・カンパニー 輻輳制御用に伝送レートを計算するためにバッファサイズの受領を用いるデータ通信方法とシステム
US7020080B1 (en) * 2001-10-09 2006-03-28 Cisco Technology, Inc. Method and apparatus for prevention of flow starvation with weighted fair queuing
US7317683B2 (en) * 2001-11-01 2008-01-08 International Business Machines Corporation Weighted fair queue serving plural output ports
US7187684B2 (en) 2001-11-01 2007-03-06 International Business Machines Corporation Weighted fair queue having extended effective range
US7046676B2 (en) 2001-11-01 2006-05-16 International Business Machines Corporation QoS scheduler and method for implementing quality of service with cached status array
US7280474B2 (en) 2001-11-01 2007-10-09 International Business Machines Corporation Weighted fair queue having adjustable scaling factor
US6973036B2 (en) 2001-11-01 2005-12-06 International Business Machines Corporation QoS scheduler and method for implementing peak service distance using next peak service time violated indication
US7103051B2 (en) * 2001-11-01 2006-09-05 International Business Machines Corporation QoS scheduler and method for implementing quality of service with aging time stamps
US7310345B2 (en) 2001-11-01 2007-12-18 International Business Machines Corporation Empty indicators for weighted fair queues
US6982986B2 (en) * 2001-11-01 2006-01-03 International Business Machines Corporation QoS scheduler and method for implementing quality of service anticipating the end of a chain of flows
KR100954253B1 (ko) * 2001-11-30 2010-04-23 브리티쉬 텔리커뮤니케이션즈 파블릭 리미티드 캄퍼니 데이터 전송 시스템, 동작 방법 및 디지털 미디어 캐리어
KR100429897B1 (ko) * 2001-12-13 2004-05-03 한국전자통신연구원 공유 버퍼형 스위치의 적응 버퍼 배분 방법 및 이에사용되는 스위치
EP1322074A1 (de) * 2001-12-20 2003-06-25 Siemens Aktiengesellschaft Verfahren für eine ausgewogene Aufnahme von Datenpaketen in eine Warteschlange
US7197612B1 (en) 2002-01-17 2007-03-27 Juniper Networks, Inc. Flexible queue and stream mapping systems and methods
US7711910B1 (en) 2002-01-17 2010-05-04 Juniper Networks, Inc. Flexible queue and stream mapping systems and methods
US7286543B2 (en) * 2002-02-27 2007-10-23 International Business Machines Corporation Memory system with apparatus and method to enable balanced bandwidth utilization
US7680043B2 (en) * 2002-03-20 2010-03-16 International Business Machines Corporation Network processor having fast flow queue disable process
US7257124B2 (en) * 2002-03-20 2007-08-14 International Business Machines Corporation Method and apparatus for improving the fairness of new attaches to a weighted fair queue in a quality of service (QoS) scheduler
EP1488644B1 (en) * 2002-03-27 2007-05-30 British Telecommunications Public Limited Company Data structure for data streaming system
EP1359722A1 (en) * 2002-03-27 2003-11-05 BRITISH TELECOMMUNICATIONS public limited company Data streaming system and method
US7382782B1 (en) 2002-04-12 2008-06-03 Juniper Networks, Inc. Packet spraying for load balancing across multiple packet processors
US20040032826A1 (en) * 2002-08-02 2004-02-19 Kamakshi Sridhar System and method for increasing fairness in packet ring networks
US20040184462A1 (en) * 2003-03-17 2004-09-23 Network Equipment Technologies Sliding window implementation for regulating packets for protocol-based connections
US20050021842A1 (en) * 2003-03-17 2005-01-27 Network Equipment Technologies Real-time packet classification and rate-limiting control packets in a network processor based data-plane
GB0306296D0 (en) * 2003-03-19 2003-04-23 British Telecomm Data transmission
US20040213264A1 (en) * 2003-04-25 2004-10-28 Nortel Networks Limited Service class and destination dominance traffic management
US7835953B2 (en) * 2003-09-29 2010-11-16 International Business Machines Corporation Method and structure for monitoring moving objects
US8972380B2 (en) * 2003-09-29 2015-03-03 International Business Machines Corporaton System and method for monitoring events against continual range queries
US7417981B2 (en) * 2003-10-15 2008-08-26 Vonage Holdings Corp. Method and apparatus for enhanced Internet Telephony
US7730137B1 (en) 2003-12-22 2010-06-01 Aol Inc. Restricting the volume of outbound electronic messages originated by a single entity
US7548956B1 (en) 2003-12-30 2009-06-16 Aol Llc Spam control based on sender account characteristics
US8036135B2 (en) * 2005-10-21 2011-10-11 Qualcomm Incorporated Mac performance of a mesh network using both sender-based and receiver-based scheduling
US20070192215A1 (en) * 2006-02-10 2007-08-16 Taylor Thomas B Computer-implemented registration for providing inventory fulfillment services to merchants
US8190698B2 (en) * 2006-06-30 2012-05-29 Microsoft Corporation Efficiently polling to determine completion of a DMA copy operation
US8004991B1 (en) * 2006-10-11 2011-08-23 Qlogic, Corporation Method and system for processing network information
US8054847B2 (en) * 2006-10-31 2011-11-08 Hewlett-Packard Development Company, L.P. Buffer management in a network device
US7853480B2 (en) * 2007-05-21 2010-12-14 Amazon Technologies, Inc. System and method for providing export services to merchants
US7814243B2 (en) * 2007-06-01 2010-10-12 Sonics, Inc. Shared storage for multi-threaded ordered queues in an interconnect
US7911948B2 (en) * 2007-10-17 2011-03-22 Viasat, Inc. Methods and systems for performing TCP throttle
US8509074B1 (en) * 2008-03-31 2013-08-13 Saisei Networks Pte Ltd System, method, and computer program product for controlling the rate of a network flow and groups of network flows
EP2247044A1 (en) * 2009-04-29 2010-11-03 Alcatel Lucent Packet network processing node and method
US8972995B2 (en) 2010-08-06 2015-03-03 Sonics, Inc. Apparatus and methods to concurrently perform per-thread as well as per-tag memory access scheduling within a thread and across two or more threads
US8705357B2 (en) * 2011-11-29 2014-04-22 Hughes Network Systems, Llc Method and system for controlling TCP traffic with random early detection and window size adjustments
US20140064079A1 (en) * 2012-08-30 2014-03-06 Broadcom Corporation Adaptive congestion management
EP3055958B1 (en) * 2013-10-07 2017-06-28 Telefonaktiebolaget LM Ericsson (publ) Downlink flow management
US10922250B2 (en) * 2019-04-30 2021-02-16 Microsoft Technology Licensing, Llc Monitoring and steering service requests to acceleration components
US20230254259A1 (en) * 2022-02-08 2023-08-10 Enfabrica Corporation System And Method For Using Dynamic Thresholds With Route Isolation For Heterogeneous Traffic In Shared Memory Packet Buffers

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS60229552A (ja) * 1984-04-27 1985-11-14 Nec Corp 可変待合せキユ−長によるフロ−制御方式
JPH06132986A (ja) * 1992-10-16 1994-05-13 Fujitsu Ltd 蓄積伝送におけるデータ制御装置
JPH0766845A (ja) * 1993-08-24 1995-03-10 Matsushita Electric Ind Co Ltd 情報流量制限装置
JP3151103B2 (ja) * 1994-03-30 2001-04-03 株式会社日立製作所 通信システムおよび通信方法
US5541912A (en) * 1994-10-04 1996-07-30 At&T Corp. Dynamic queue length thresholds in a shared memory ATM switch
JPH08221371A (ja) * 1995-02-15 1996-08-30 Oki Electric Ind Co Ltd 共有メモリ制御方法とその制御回路
JPH09238142A (ja) * 1996-02-29 1997-09-09 Toshiba Corp 網リソース割り当て方法及び装置
US5881245A (en) * 1996-09-10 1999-03-09 Digital Video Systems, Inc. Method and apparatus for transmitting MPEG data at an adaptive data rate

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2005020523A1 (ja) * 2003-08-20 2005-03-03 Nec Corporation セッション中継装置及び中継方法
US7675898B2 (en) 2003-08-20 2010-03-09 Nec Corporation Session relay apparatus for relaying data, and a data relaying method
JP2008136176A (ja) * 2006-10-10 2008-06-12 Mitsubishi Electric Information Technology Centre Europa Bv メモリブロックの割り当てを管理する方法及びデバイス、データ伝送ネットワークシステム、コンピュータ可読媒体、並びにコンピュータプログラム製品

Also Published As

Publication number Publication date
US6092115A (en) 2000-07-18
CA2227244C (en) 2001-10-02
CA2227244A1 (en) 1998-08-07
EP0872988A3 (en) 1999-08-11
EP0872988A2 (en) 1998-10-21
EP0872988B1 (en) 2006-06-07
JP3698884B2 (ja) 2005-09-21
DE69834763T2 (de) 2007-06-14
JP2009207208A (ja) 2009-09-10
DE69834763D1 (de) 2006-07-20
JP2005295581A (ja) 2005-10-20

Similar Documents

Publication Publication Date Title
JP3698884B2 (ja) Ｔｃｐ接続の性能改善方法
Suter et al. Design considerations for supporting TCP with per-flow queueing
US7983159B2 (en) Queue-based active queue management process
US9112786B2 (en) Systems and methods for selectively performing explicit congestion notification
JP3556495B2 (ja) パケットスイッチ及びパケット交換方法
US6765905B2 (en) Method for reducing packet data delay variation in an internet protocol network
US7324442B1 (en) Active queue management toward fair bandwidth allocation
Liu et al. Improving explicit congestion notification with the mark-front strategy
JP4523596B2 (ja) ネットワークのためのパケットのフレームへのカプセル化
GB2355374A (en) Packet forwarding device with selective packet discarding when paused
McAlpine et al. An architecture for congestion management in Ethernet clusters
JP2003298638A (ja) パケット伝送装置及びその方法
Yedavalli Using wireless advantage for congestion control in wireless sensor networks
Cheng et al. Improving the ramping up behavior of TCP slow start
Lin et al. A congestion control approach for LAN/MAN interconnection via ATM
Tokuda et al. Analysis and Improvement of the Fairness between Long-lived and Short-lived TCP Connections
Kantawala et al. Intelligent Packet Discard Policies for Improved TCP Queue Management
Yan et al. A stateless active queue management scheme for approximating fair bandwidth allocation and stabilized buffer occupation
Bruno et al. Early fair drop: a new buffer management policy
JP3813473B2 (ja) パケット廃棄装置
Barakat et al. On ACK filtering on a slow reverse channel
Morgan et al. Packet-pair rate control—buffer requirements and overload performance
Patra Improving TCP with Parameterized Forward-Retransmission Time Out
Vaidyanathan Issues in resource allocation and design of hybrid gateways
Wu Performance evaluation of frame discard strategies in ATM networks

Legal Events

Date Code Title Description
A601 Written request for extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A601

Effective date: 20050208

A602 Written permission of extension of time

Free format text: JAPANESE INTERMEDIATE CODE: A602

Effective date: 20050214

A521 Request for written amendment filed

Free format text: JAPANESE INTERMEDIATE CODE: A523

Effective date: 20050509

A61 First payment of annual fees (during grant procedure)

Free format text: JAPANESE INTERMEDIATE CODE: A61

Effective date: 20050706

R150 Certificate of patent or registration of utility model

Free format text: JAPANESE INTERMEDIATE CODE: R150

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20090715

Year of fee payment: 4

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100715

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20100715

Year of fee payment: 5

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20110715

Year of fee payment: 6

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20120715

Year of fee payment: 7

FPAY Renewal fee payment (event date is renewal date of database)

Free format text: PAYMENT UNTIL: 20130715

Year of fee payment: 8

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

R250 Receipt of annual fees

Free format text: JAPANESE INTERMEDIATE CODE: R250

LAPS Cancellation because of no payment of annual fees