(57)【特許請求の範囲】
【請求項１】
入力ポートによって受信されたデータパケットの宛先アドレスを取得するステップと、
前記宛先アドレスに基づいて複数の利用可能出力ポートを決定するステップと、
前記複数の利用可能出力ポートの各々のビジー度を決定し、前記複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに前記複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを前記複数の利用可能出力ポートからターゲット出力ポートとして選択するステップであって、前記フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、前記受信されたデータパケットの前記宛先アドレスと同じである、ステップと、
前記ターゲット出力ポートにおける複数のキューのそれぞれのビジー度を決定し、前記ターゲット出力ポートにおいて非ビジーキューがあるときに前記非ビジーキューをターゲット出力キューとして選択するステップと
を備えるデータ処理方法。
【請求項２】
前記複数の利用可能出力ポートの中に複数の非ビジー利用可能出力ポートがあるとき、非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するステップをさらに備える、請求項1に記載の方法。
【請求項３】
非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択する前記ステップが、
前記複数の非ビジー利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するステップを備える、
請求項2に記載の方法。
【請求項４】
最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを前記ターゲット出力ポートとして選択する前記ステップが、
前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートが複数あるときに、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートの各々におけるデータパケットまたは残存帯域幅の数量を決定し、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートから、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートを前記ターゲット出力ポートとして選択するステップを備える、
請求項3に記載の方法。
【請求項５】
前記ターゲット出力ポートにおいて非ビジーキューがないとき、前記ターゲット出力ポートにおけるフットプリントキューを前記ターゲット出力キューとして選択するステップをさらに備える、請求項1から4のいずれか一項に記載の方法。
【請求項６】
前記複数の利用可能出力ポートの各々のビジー度を決定する前記ステップが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、前記複数の利用可能出力ポートの各々におけるキューの総数量の中での非ビジーキューの前記数量のパーセンテージを取得し、第1のしきい値よりも大きいパーセンテージを有する利用可能出力ポートが非ビジー利用可能出力ポートであることを決定するステップを備える、
請求項1から5のいずれか一項に記載の方法。
【請求項７】
前記複数の利用可能出力ポートのビジー度を決定する前記ステップが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、最大数量の非ビジーキューを伴う利用可能出力ポートを非ビジー利用可能出力ポートとして決定するステップを備える、
請求項1から5のいずれか一項に記載の方法。
【請求項８】
入力ポートによって受信されたデータパケットの宛先アドレスを取得するステップと、
前記宛先アドレスに基づいて複数の利用可能出力ポートを決定するステップと、
前記複数の利用可能出力ポートの各々のビジー度を決定し、前記複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに前記複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを前記複数の利用可能出力ポートからターゲット出力ポートとして選択するステップであって、前記フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、前記受信されたデータパケットの前記宛先アドレスと同じである、ステップと、
前記ターゲット出力ポートにおける複数のキューのそれぞれのビジー度を決定し、前記ターゲット出力ポートにおいて非ビジーキューがないときに前記ターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択するステップと
を備えるデータ処理方法。
【請求項９】
前記複数の利用可能出力ポートの中に複数の非ビジー利用可能出力ポートがあるとき、非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するステップをさらに備える、請求項8に記載の方法。
【請求項１０】
非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択する前記ステップが、
前記非ビジー利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するステップを備える、
請求項9に記載の方法。
【請求項１１】
最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを前記ターゲット出力ポートとして選択する前記ステップが、
前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートが複数あるときに、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートの各々におけるデータパケットまたは残存帯域幅の数量を決定し、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートから、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートを前記ターゲット出力ポートとして選択するステップを備える、
請求項10に記載の方法。
【請求項１２】
前記複数の利用可能出力ポートの各々のビジー度を決定する前記ステップが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、前記複数の利用可能出力ポートの各々におけるキューの総数量の中での非ビジーキューの前記数量のパーセンテージを取得し、第1のしきい値よりも大きいパーセンテージを有する利用可能出力ポートが非ビジー利用可能出力ポートであることを決定するステップを備える、
請求項8から11のいずれか一項に記載の方法。
【請求項１３】
前記複数の利用可能出力ポートの各々のビジー度を決定する前記ステップが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、最大数量の非ビジーキューを伴う利用可能出力ポートを非ビジー利用可能出力ポートとして決定するステップを備える、
請求項8から11のいずれか一項に記載の方法。
【請求項１４】
入力ポートによって受信されたデータパケットの宛先アドレスを取得するように構成された宛先アドレス取得モジュールと、
前記宛先アドレスに基づいて複数の利用可能出力ポートを決定するように構成された利用可能出力ポート決定モジュールと、
前記複数の利用可能出力ポートの各々のビジー度を決定し、前記複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに前記複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを前記複数の利用可能出力ポートからターゲット出力ポートとして選択するように構成されたターゲット出力ポート選択モジュールであって、前記フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、前記受信されたデータパケットの前記宛先アドレスと同じである、ターゲット出力ポート選択モジュールと、
前記ターゲット出力ポートにおける複数のキューのそれぞれのビジー度を決定し、前記ターゲット出力ポートにおいて非ビジーキューがあるときに前記非ビジーキューをターゲット出力キューとして選択するように構成されたターゲット出力キュー選択モジュールと
を備えるデータ処理装置。
【請求項１５】
前記ターゲット出力ポート選択モジュールが、
前記複数の利用可能出力ポートの中に複数の非ビジー利用可能出力ポートがあるとき、非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するようにさらに構成される、
請求項14に記載のデータ処理装置。
【請求項１６】
前記ターゲット出力ポート選択モジュールが、
前記複数の非ビジー利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するようにさらに構成される、
請求項15に記載のデータ処理装置。
【請求項１７】
前記ターゲット出力ポート選択モジュールが、
前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートが複数あるときに、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートの各々におけるデータパケットまたは残存帯域幅の数量を決定し、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートから、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートを前記ターゲット出力ポートとして選択するようにさらに構成される、
請求項16に記載のデータ処理装置。
【請求項１８】
前記ターゲット出力キュー選択モジュールが、
前記ターゲット出力ポートにおいて非ビジーキューがないとき、前記ターゲット出力ポートにおけるフットプリントキューを前記ターゲット出力キューとして選択するようにさらに構成される、
請求項14から17のいずれか一項に記載のデータ処理装置。
【請求項１９】
前記ターゲット出力ポート選択モジュールが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、前記複数の利用可能出力ポートの各々におけるキューの総数量の中での非ビジーキューの前記数量のパーセンテージを取得し、第1のしきい値よりも大きいパーセンテージを有する利用可能出力ポートが非ビジー利用可能出力ポートであることを決定するように特に構成される、
請求項14から18のいずれか一項に記載のデータ処理装置。
【請求項２０】
前記ターゲット出力ポート選択モジュールが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、最大数量の非ビジーキューを伴う利用可能出力ポートを非ビジー利用可能出力ポートとして決定するように特に構成される、
請求項14から18のいずれか一項に記載のデータ処理装置。
【請求項２１】
入力ポートによって受信されたデータパケットの宛先アドレスを取得するように構成された宛先アドレス取得モジュールと、
前記宛先アドレスに基づいて複数の利用可能出力ポートを決定するように構成された利用可能出力ポート決定モジュールと、
前記複数の利用可能出力ポートの各々のビジー度を決定し、前記複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに前記複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを前記複数の利用可能出力ポートからターゲット出力ポートとして選択するように構成されたターゲット出力ポート選択モジュールであって、前記フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、前記受信されたデータパケットの前記宛先アドレスと同じである、ターゲット出力ポート選択モジュールと、
前記ターゲット出力ポートにおける複数のキューのそれぞれのビジー度を決定し、前記ターゲット出力ポートにおいて非ビジーキューがないときに前記ターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択するように構成されたターゲット出力キュー選択モジュールと
を備えるデータ処理装置。
【請求項２２】
前記ターゲット出力ポート選択モジュールが、
前記複数の利用可能出力ポートの中に複数の非ビジー利用可能出力ポートがあるとき、非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するようにさらに構成される、
請求項21に記載のデータ処理装置。
【請求項２３】
前記ターゲット出力ポート選択モジュールが、
前記非ビジー利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを前記複数の非ビジー利用可能出力ポートから前記ターゲット出力ポートとして選択するようにさらに構成される、
請求項22に記載のデータ処理装置。
【請求項２４】
前記ターゲット出力ポート選択モジュールが、
前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートが複数あるときに、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートの各々におけるデータパケットまたは残存帯域幅の数量を決定し、前記最大数量のフットプリントキューを伴う前記非ビジー利用可能出力ポートから、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートを前記ターゲット出力ポートとして選択するようにさらに構成される、
請求項23に記載のデータ処理装置。
【請求項２５】
前記ターゲット出力ポート選択モジュールが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、前記複数の利用可能出力ポートの各々におけるキューの総数量の中での非ビジーキューの前記数量のパーセンテージを取得し、第1のしきい値よりも大きいパーセンテージを有する利用可能出力ポートが非ビジー利用可能出力ポートであることを決定するように特に構成される、
請求項21から24のいずれか一項に記載のデータ処理装置。
【請求項２６】
前記ターゲット出力ポート選択モジュールが、
前記複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、最大数量の非ビジーキューを伴う利用可能出力ポートを非ビジー利用可能出力ポートとして決定するように特に構成される、
請求項21から24のいずれか一項に記載のデータ処理装置。
【請求項２７】
入力ポート、出力ポート、プロセッサ、メモリ、およびバスを備えるスイッチングデバイスであって、前記入力ポート、前記出力ポート、前記プロセッサ、および前記メモリが各々、前記バスに接続され、前記メモリがプログラム命令を記憶し、前記プロセッサが、以下のステップ、すなわち、
前記入力ポートによって受信されたデータパケットの宛先アドレスを取得することと、
前記宛先アドレスに基づいて複数の利用可能出力ポートを決定することと、
前記複数の利用可能出力ポートの各々のビジー度を決定し、前記複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに前記複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを前記複数の利用可能出力ポートからターゲット出力ポートとして選択することであって、前記フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、前記受信されたデータパケットの前記宛先アドレスと同じである、ことと、
前記ターゲット出力ポートにおける複数のキューのそれぞれのビジー度を決定し、前記ターゲット出力ポートにおいて非ビジーキューがあるときに前記非ビジーキューをターゲット出力キューとして選択することとを実行するために、前記プログラム命令を動作させる、
スイッチングデバイス。
【請求項２８】
入力ポート、出力ポート、プロセッサ、メモリ、およびバスを備えるスイッチングデバイスであって、前記入力ポート、前記出力ポート、前記プロセッサ、および前記メモリが各々、前記バスに接続され、前記メモリがプログラム命令を記憶し、前記プロセッサが、以下のステップ、すなわち、
前記入力ポートによって受信されたデータパケットの宛先アドレスを取得することと、
前記宛先アドレスに基づいて複数の利用可能出力ポートを決定することと、
前記複数の利用可能出力ポートの各々のビジー度を決定し、前記複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに前記複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを前記複数の利用可能出力ポートからターゲット出力ポートとして選択することであって、前記フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、前記受信されたデータパケットの前記宛先アドレスと同じである、ことと、
前記ターゲット出力ポートにおける複数のキューのそれぞれのビジー度を決定し、前記ターゲット出力ポートにおいて非ビジーキューがないときに前記ターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択することとを実行するために、前記プログラム命令を動作させる、
スイッチングデバイス。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、情報技術の分野に関し、詳細には、データ処理方法および装置ならびにスイッチングデバイスに関する。
【背景技術】
【０００２】
ロスレスネットワーク(lossless network)は、データセンターネットワーク、高性能コンピュータ相互接続ネットワーク、およびマルチ・コア・プロセッサ・ネットワーク・オン・チップの現在の研究焦点である。高性能コンピュータ相互接続ネットワークおよびマルチ・コア・プロセッサ・ネットワーク・オン・チップの場合、ネットワークの中でパケット損失が発生しないことを保証するために、通常は信用ベース(credit-based)フロー制御メカニズムが使用される。データセンターネットワークの場合、ネットワークの中でパケット損失が発生しないことを保証するために、通常は優先度ベース(priority-based)フロー制御メカニズムが使用される。しかしながら、いかなるシナリオにおいても、ロスレスネットワークの特性に起因してネットワークブロッキングが発生する。
【発明の概要】
【課題を解決するための手段】
【０００３】
本出願は、ロスレスネットワークにおけるネットワークブロッキングを緩和するための、データ処理方法および装置ならびにスイッチングデバイスを開示する。
【０００４】
第1の態様によれば、本出願はデータ処理方法を提供する。方法は、以下のステップ、すなわち、第1に、入力ポートによって受信されたデータパケットの宛先アドレスを取得することと、第2に、宛先アドレスに基づいて複数の利用可能出力ポートを決定することと、次いで、複数の利用可能出力ポートの各々のビジー度を決定し、複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに利用可能出力ポートにおけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを複数の利用可能出力ポートからターゲット出力ポートとして選択することと、ただし、フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、受信されたデータパケットの宛先アドレスと同じであることに留意されたく、最後に、ターゲット出力ポートにおけるキューのビジー度を決定し、ターゲット出力ポートにおいて非ビジーキューがあるときに非ビジーキューをターゲット出力キューとして選択することとを含む。
【０００５】
利用可能出力ポートの中に非ビジー利用可能出力ポートがないとき、最大数量のフットプリントキューを伴う利用可能出力ポートがターゲット出力ポートとして選択される。このようにして、データパケットが、最大数量のフットプリントキューを伴う利用可能出力ポートを通じて転送されることが保証され得、同じ宛先アドレスを搬送するデータパケットが、同じ利用可能出力ポートにおいて一緒に配置されることが保証され得る。輻輳が発生しても、別の利用可能出力ポート上のデータパケットは影響を受けない。加えて、非ビジーキューの中で輻輳が発生しないので、非ビジーキューをターゲット出力キューとして使用することは、ターゲット出力キューの中でデータパケットが輻輳しないことを保証することができる。
【０００６】
本出願の一実装形態では、方法は、以下のステップ、すなわち、利用可能出力ポートの中に複数の非ビジー利用可能出力ポートがあるとき、非ビジー利用可能出力ポートを複数の非ビジー利用可能出力ポートからターゲット出力ポートとして選択することをさらに含む。
【０００７】
本出願では、非ビジー利用可能出力ポートがターゲット出力ポートとして選択される。このようにして、データパケットが好ましくは非ビジー利用可能出力ポートを通じて転送されることが保証され得る。
【０００８】
本出願の別の実装形態では、非ビジー利用可能出力ポートを複数の非ビジー利用可能出力ポートからターゲット出力ポートとして選択することは、非ビジー利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを複数の非ビジー利用可能出力ポートからターゲット出力ポートとして選択することを含む。
【０００９】
データパケットが非ビジーキューまたはフットプリントキューに沿って前方へ移動することを可能にするために、フットプリントキューの数量がさらに比較され得る。データパケットが非ビジーキューまたはフットプリントキューに沿って前方へ移動する機会を有するように、最大数量のフットプリントキューを伴う利用可能出力ポートが選択される。このようにして、データパケットブロッキングの確率が効果的に低減される。
【００１０】
本出願の別の実装形態では、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択することは、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートにおけるデータパケットまたは残存帯域幅の数量を決定し、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択することを含む。
【００１１】
最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートがあり、さらに最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートの中に最大数量のフットプリントキューを伴う少なくとも2つの利用可能出力ポートがあるとき、1つの利用可能出力ポートしかターゲット出力ポートとして使用されることを必要とせず、データパケットが上記のポートのうちのいずれか1つにおいて送られるとき、データパケットが非ビジーキューまたはフットプリントキューに沿って前方へ移動することが保証され得る。したがって、ターゲット出力ポートは、データパケットまたは残存帯域幅の総数量を比較することによって選択された少なくとも2つの利用可能出力ポートから選択されてよい。このようにして、データパケットブロッキングの確率がさらに低減される。
【００１２】
本出願の別の実装形態では、方法は、以下のステップ、すなわち、ターゲット出力ポートにおいて非ビジーキューがないとき、ターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択することをさらに含む。
【００１３】
ターゲット出力ポートにおいて非ビジーキューがないとき、ターゲット出力ポートにおけるフットプリントキューがターゲット出力キューとして選択される。フットプリントキューの中で輻輳が発生しても、別のキューの中のデータパケットは送られることを妨害されない。したがって、ネットワークリソースが適切に使用され、ロスレスネットワークにおけるネットワークブロッキングが緩和される。
【００１４】
本出願の別の実装形態では、利用可能出力ポートのビジー度を決定することは、複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、複数の利用可能出力ポートの各々におけるキューの総数量の中での非ビジーキューの数量のパーセンテージを取得し、第1のしきい値よりも大きいパーセンテージを有する利用可能出力ポートが非ビジー利用可能出力ポートであることを決定することを特に含む。
【００１５】
第1のしきい値は0%から100%までであり、50%であってよい。利用可能出力ポートのビジー度は、第1のしきい値を設定することによって規定され得る。
【００１６】
本出願の別の実装形態では、利用可能出力ポートのビジー度を決定することは、複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、最大数量の非ビジーキューを伴う利用可能出力ポートを非ビジー利用可能出力ポートとして決定することを特に含む。
【００１７】
本出願の別の実装形態では、ターゲット出力ポートにおけるキューのビジー度を決定することは、キューの中のデータパケットによって占有されるキャッシュ空間を決定し、キューのキャッシュ容量に対する、データパケットによって占有されるキャッシュ空間のパーセンテージが第2のしきい値以下であるときにキューが非ビジーキューであることを決定することを特に含む。
【００１８】
キューは、複数のデータパケットを収容してよく、データパケットの数量がキュー深度である。第2のしきい値は、キュー深度を規定するための要件に従って設定され、その結果、アプリケーションフレキシビリティが高められ得る。第2のしきい値は0であってよく、この場合、キューの中にデータパケットがあるとすればキューは非ビジーキューである。データパケットは、好ましくはデータパケットがその中にないキューを使用することによって送信される。したがって、パケット送信速度が大幅に高められ、データパケットブロッキングの確率が低減される。
【００１９】
第2の態様によれば、本出願はデータ処理方法を提供する。方法は、入力ポートによって受信されたデータパケットの宛先アドレスを取得することと、第2に、宛先アドレスに基づいて複数の利用可能出力ポートを決定することと、複数の利用可能出力ポートの各々のビジー度を決定し、複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを複数の利用可能出力ポートからターゲット出力ポートとして選択することであって、ここで、フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、受信されたデータパケットの宛先アドレスと同じであることと、ターゲット出力ポートにおけるキューのビジー度を決定し、ターゲット出力ポートにおいて非ビジーキューがないときにターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択することとを含む。
【００２０】
利用可能出力ポートの中に非ビジー利用可能出力ポートがないとき、最大数量のフットプリントキューを伴う利用可能出力ポートがターゲット出力ポートとして選択される。このようにして、データパケットが、最大数量のフットプリントキューを伴う利用可能出力ポートを通じて転送されることが保証され得、同じ宛先アドレスを搬送するデータパケットが、同じ利用可能出力ポートにおいて一緒に配置されることが保証され得る。輻輳が発生しても、別の利用可能出力ポート上のデータパケットは影響を受けない。加えて、ターゲット出力ポートにおいて非ビジーキューがないとき、ターゲット出力ポートにおけるフットプリントキューがターゲット出力キューとして選択される。フットプリントキューの中で輻輳が発生しても、別のキューの中のデータパケットは送られることを妨害されない。したがって、ネットワークリソースが適切に使用され、ネットワークブロッキングがロスレスネットワークにおいて緩和される。
【００２１】
本出願の一実装形態では、方法は、複数の利用可能出力ポートの中に複数の非ビジー利用可能出力ポートがあるとき、非ビジー利用可能出力ポートを複数の非ビジー利用可能出力ポートからターゲット出力ポートとして選択することをさらに含む。
【００２２】
本出願では、非ビジー利用可能出力ポートがターゲット出力ポートとして選択される。このようにして、データパケットが好ましくは非ビジー利用可能出力ポートを通じて転送されることが保証され得る。
【００２３】
本出願の別の実装形態では、非ビジー利用可能出力ポートを複数の非ビジー利用可能出力ポートからターゲット出力ポートとして選択することは、非ビジー利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートを複数の非ビジー利用可能出力ポートからターゲット出力ポートとして選択することを特に含む。
【００２４】
データパケットが非ビジーキューまたはフットプリントキューに沿って前方へ移動することを可能にするために、フットプリントキューの数量がさらに比較され得る。データパケットが非ビジーキューまたはフットプリントキューに沿って前方へ移動する機会を有するように、最大数量のフットプリントキューを伴う利用可能出力ポートが選択される。このようにして、データパケットブロッキングの確率が効果的に低減される。
【００２５】
本出願の別の実装形態では、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択することは、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートの各々におけるデータパケットまたは残存帯域幅の数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートから、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択することを特に含む。
【００２６】
最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートがあり、さらに最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートの中に最大数量のフットプリントキューを伴う少なくとも2つの利用可能出力ポートがあるとき、1つの利用可能出力ポートしかターゲット出力ポートとして使用されることを必要とせず、データパケットが上記のポートのうちのいずれか1つにおいて送られるとき、データパケットが非ビジーキューまたはフットプリントキューに沿って前方へ移動することが保証され得る。したがって、ターゲット出力ポートは、データパケットまたは残存帯域幅の総数量を比較することによって選択された少なくとも2つの利用可能出力ポートから選択されてよい。このようにして、データパケットブロッキングの確率がさらに低減される。
【００２７】
本出願の別の実装形態では、複数の利用可能出力ポートの各々のビジー度を決定することは、複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、複数の利用可能出力ポートの各々におけるキューの総数量の中での非ビジーキューの数量のパーセンテージを取得し、第1のしきい値よりも大きいパーセンテージを有する利用可能出力ポートが非ビジー利用可能出力ポートであることを決定することを特に含む。
【００２８】
第1のしきい値は0%から100%までであり、50%であってよい。利用可能出力ポートのビジー度は、第1のしきい値を設定することによって規定され得る。
【００２９】
本出願の別の実装形態では、複数の利用可能出力ポートの各々のビジー度を決定することは、複数の利用可能出力ポートの各々における非ビジーキューの数量を決定し、最大数量の非ビジーキューを伴う利用可能出力ポートを非ビジー利用可能出力ポートとして決定することを特に含む。
【００３０】
本出願の別の実装形態では、ターゲット出力ポートにおけるキューのビジー度を決定することは、キューの中のデータパケットによって占有されるキャッシュ空間を決定し、キューのキャッシュ容量に対する、データパケットによって占有されるキャッシュ空間のパーセンテージが第2のしきい値以下であるときにキューが非ビジーキューであることを決定することを特に含む。
【００３１】
キューは、複数のデータパケットを収容してよく、データパケットの数量がキュー深度である。第2のしきい値は、キュー深度を規定するための要件に従って設定され、その結果、アプリケーションフレキシビリティが高められ得る。第2のしきい値は0であってよく、この場合、キューの中にデータパケットがあるとすればキューは非ビジーキューである。データパケットは、好ましくはデータパケットがその中にないキューを使用することによって送信される。したがって、パケット送信速度が大幅に高められ、データパケットブロッキングの確率が低減される。
【００３２】
第3の態様によれば、本出願はデータ処理装置を提供する。装置は、入力ポートによって受信されたデータパケットの宛先アドレスを取得するように構成された宛先アドレス取得モジュールと、宛先アドレスに基づいて複数の利用可能出力ポートを決定するように構成された利用可能出力ポート決定モジュールと、複数の利用可能出力ポートの各々のビジー度を決定し、複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに利用可能出力ポートにおけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを複数の利用可能出力ポートからターゲット出力ポートとして選択するように構成されたターゲット出力ポート選択モジュールであって、ここで、フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、受信されたデータパケットの宛先アドレスと同じである、ターゲット出力ポート選択モジュールと、ターゲット出力ポートにおけるキューのビジー度を決定し、ターゲット出力ポートにおいて非ビジーキューがあるときに非ビジーキューをターゲット出力キューとして選択するように構成されたターゲット出力キュー選択モジュールとを含む。
【００３３】
第3の態様または第3の態様の実装形態のうちのいずれか1つは、第1の態様または第1の態様の実装形態のうちのいずれか1つに対応する装置実装形態である。第1の態様または第1の態様の実装形態のうちのいずれか1つにおける説明は、第3の態様または第3の態様の実装形態のうちのいずれか1つに適用可能である。詳細は本明細書で再び説明しない。
【００３４】
第4の態様によれば、本発明の一実施形態はデータ処理装置を提供する。装置は、入力ポートによって受信されたデータパケットの宛先アドレスを取得するように構成された宛先アドレス取得モジュールと、宛先アドレスに基づいて複数の利用可能出力ポートを決定するように構成された利用可能出力ポート決定モジュールと、複数の利用可能出力ポートの各々のビジー度を決定し、複数の利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに複数の利用可能出力ポートの各々におけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートを複数の利用可能出力ポートからターゲット出力ポートとして選択するように構成されたターゲット出力ポート選択モジュールであって、ここで、フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスが、受信されたデータパケットの宛先アドレスと同じである、ターゲット出力ポート選択モジュールと、ターゲット出力ポートにおけるキューのビジー度を決定し、ターゲット出力ポートにおいて非ビジーキューがないときにターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択するように構成されたターゲット出力キュー選択モジュールとを含む。
【００３５】
第4の態様または第4の態様の実装形態のうちのいずれか1つは、第2の態様または第2の態様の実装形態のうちのいずれか1つに対応する装置実装形態である。第2の態様または第2の態様の実装形態のうちのいずれか1つにおける説明は、第4の態様または第4の態様の実装形態のうちのいずれか1つに適用可能である。詳細は本明細書で再び説明しない。
【００３６】
第5の態様によれば、本出願はスイッチングデバイスを提供する。スイッチングデバイスは、上記の方法実施形態におけるスイッチングデバイスを実施する機能を有する。機能は、ハードウェアによって実装されてよく、または対応するソフトウェアを実行することによってハードウェアによって実施されてもよい。ハードウェアまたはソフトウェアは、上記の機能に対応する1つまたは複数のモジュールを含む。随意に、スイッチングデバイスは、スイッチ機能を実施するスイッチまたは物理的サーバなどのネットワーク側デバイスであってよい。
【図面の簡単な説明】
【００３７】
【図１】本発明の一実施形態によるネットワークシステムの概略トポロジー図である。
【図２】本発明の一実施形態によるスイッチングデバイスの装置構造の概略図である。
【図３】本発明の一実施形態によるデータ処理方法のフローチャートである。
【図４】本発明の一実施形態によるデータ処理方法のデータ相互作用図である。
【図５】本発明の一実施形態によるデータ処理方法のサブフローチャートである。
【図６】本発明の一実施形態によるデータ処理方法の別のサブフローチャートである。
【図７】本発明の一実施形態によるスイッチングデバイスの装置構造の概略図である。
【図８】本発明の一実施形態によるスイッチングデバイスの装置構造の別の概略図である。
【図９】本発明の一実施形態による、データパケットを転送する前のスイッチングデバイスの装置構造の概略図である。
【図１０】本発明の一実施形態による、データパケットを転送した後のスイッチングデバイスの装置構造の概略図である。
【図１１】本発明の一実施形態による、データパケットを転送する前のスイッチングデバイスの装置構造の別の概略図である。
【図１２】本発明の一実施形態による、データパケットを転送した後のスイッチングデバイスの装置構造の別の概略図である。
【図１３】本発明の一実施形態によるデータ処理装置の装置構造の概略図である。
【図１４】本発明の一実施形態によるスイッチングデバイスの装置構造の概略図である。
【発明を実施するための形態】
【００３８】
本発明の実施形態による技術的解決策が、添付図面を参照しながら以下で明瞭かつ完全に説明される。明らかに、説明する実施形態は本発明の実施形態の全部ではなく一部にすぎない。
【００３９】
まず、図1は本発明の一実施形態によるネットワークシステムの概略トポロジー図である。図1に示すように、ネットワークシステムは、ソースノード21、宛先ノード22、ならびに複数のスイッチングデバイス20、23、24、25、26、および27を含む。
【００４０】
ソースノード21はスイッチングデバイス23に接続されている。宛先ノード22はスイッチングデバイス27に接続されている。ソースノード21は、データパケットをスイッチングデバイス23へ送る。データパケットは宛先アドレスを搬送し、宛先アドレスは宛先ノード22のネットワークアドレスである。図1に示すように、データパケットがスイッチングデバイス23に到着した後、スイッチングデバイス23は、データパケットの中で搬送された宛先アドレスに基づいてルートを計算して、次のホップのスイッチングデバイスが、それぞれ、スイッチングデバイス20、スイッチングデバイス24、およびスイッチングデバイス25であり得ることを学習する。
【００４１】
スイッチングデバイス23が次のホップとしてスイッチングデバイス20を選択する場合、スイッチングデバイス20は、スイッチングデバイス23によって送られたデータパケットを受信するとともにデータパケットの中で搬送された宛先アドレスに基づいてルートを計算して、次のホップのスイッチングデバイスが、それぞれ、スイッチングデバイス25およびスイッチングデバイス26であり得ることを学習する。スイッチングデバイス20が次のホップとしてスイッチングデバイス26を選択する場合、データパケットを受信した後、スイッチングデバイス26は、次のホップのスイッチングデバイスがスイッチングデバイス27であることを、ルートを計算することによって学習し得る。スイッチングデバイス27である、次のホップのスイッチングデバイスが1つしかないので、スイッチングデバイス26はデータパケットをスイッチングデバイス27へ送り、スイッチングデバイス27がデータパケットを宛先ノード22へ送る。
【００４２】
上記の例では、データパケットは、経路a-b-g-j-kを通って宛先ノード22に到着する。同様に、データパケットは、代替として、経路a-b-f-i-k、経路a-c-e-h-j-k、経路a-d-i-k、または別の経路を通って宛先ノード22に到着してもよい。ソースノード21によって送られたデータパケットが宛先ノード22に到着することがルートを計算することによって保証されるとき、データパケットが複数の異なる経路を通って宛先ノード22に送られてよいことが学習され得る。複数の出力ポートを有するスイッチングデバイスに対して、データパケットの宛先アドレスに基づいてルートが計算された後、利用可能出力ポートが複数の出力ポートから選択され得る。利用可能出力ポートから出力された後、データパケットは、データパケットの宛先アドレスにルーティングされ得る。複数の利用可能出力ポートがあるとき、異なる利用可能出力ポートに接続されているネットワークのネットワークステータスに基づいて、利用可能出力ポートが選択される。利用可能出力ポートにおいて輻輳が発生することがあり、データパケットは、輻輳がそこで発生している利用可能出力ポートを通じて送られるときに輻輳することがある。
【００４３】
本発明のこの実施形態で提供されるスイッチングデバイスによれば、データパケットが輻輳することを防止するために、比較的使用されていない利用可能出力ポートが、データパケットを送るために選択され得る。
【００４４】
図2を参照しながら、以下は一例を使用することによってスイッチングデバイス20の構造を説明する。図2は、本発明のこの実施形態によるスイッチングデバイスの装置構造の概略図である。図2に示すように、スイッチングデバイス20は、複数の入力ポート201、202、および203、複数の出力ポート211、212、および213、スイッチングデバイス220、ならびにデータ処理装置230を含む。
【００４５】
データ処理装置230は、各入力ポート、各出力ポート、およびスイッチングデバイス220に別個に接続されている。入力ポート201、202、および203の各々は、スイッチングデバイス220に接続されている。出力ポート211、212、および213の各々は、スイッチングデバイス220に接続されている。複数のキューが、各入力ポートおよび各出力ポートにおいて設定されている。詳細には、キュー2011、2012、および2013が、入力ポート201において設定され、キュー2021、2022、および2023が、入力ポート202において設定され、キュー2031、2032、および2033が、入力ポート203において設定され、キュー2111、2112、および2113が、出力ポート211において設定され、キュー2121、2122、および2123が、出力ポート212において設定され、キュー2131、2132、および2133が、出力ポート213において設定される。
【００４６】
いくつかの例では、入力ポートおよび出力ポートの数量が、図2に示すものに限定されず、要件に基づいて任意に設定されてよいことに留意されたい。このことは本発明のこの実施形態において限定されない。ただし、出力ポートにおいて2つ以上のキューが設定される必要がある。
【００４７】
加えて、随意の実施形態では、2つ以上のキューの代わりに1つのキューしか設定される必要がない。
【００４８】
加えて、この実施形態では、各入力ポートおよび各出力ポートに対してポート番号が設定され、各入力ポートにおけるキューおよび各出力ポートにおけるキューに対してキュー番号が設定され、データ処理装置230はその番号を記録する。
【００４９】
さらに、入力ポートおよび出力ポートにおける各キューの中にそれに対応してキャッシュが設定され、キャッシュは、先入れ先出し(FIFO、First Input First Output)キューの中に設定される。データ処理装置230は、すべてのキューのキュー先頭におけるデータパケットに任意の方法で(たとえば、同時に、ポーリングによって、優先度順序で、入力ポートをいくつかのグループに分割し各グループをポーリングすることによって、または優先度に基づいて)アクセスし、データパケットの宛先アドレスを取得し、宛先アドレスに基づいてルートを計算して、利用可能出力ポートの番号を取得する。
【００５０】
この例では、出力ポート211のポート番号は1であり、出力ポート212のポート番号は2であり、出力ポート213のポート番号は3である。加えて、出力ポート211におけるキュー2111のキュー番号は1であり、出力ポート211におけるキュー2112のキュー番号は2であり、出力ポート211におけるキュー2113のキュー番号は3であり、出力ポート212におけるキュー2121のキュー番号は1であり、出力ポート212におけるキュー2122のキュー番号は2であり、出力ポート212におけるキュー2123のキュー番号は3であり、出力ポート213におけるキュー2131のキュー番号は1であり、出力ポート213におけるキュー2132のキュー番号は2であり、出力ポート213におけるキュー2133のキュー番号は3である。
【００５１】
加えて、図2に示すように、入力ポート201におけるキュー2011の中にデータパケット241、242、243、および244があり、入力ポート201における他のキュー、入力ポート202におけるすべてのキュー、および入力ポート203におけるすべてのキューの中にはデータパケットがなく、出力ポート211におけるキュー2112の中にデータパケット245があり、出力ポート211におけるキュー2113の中にデータパケット246があり、出力ポート213におけるキュー2132の中にデータパケット247があり、出力ポート213におけるキュー2133の中にデータパケット248があり、出力ポート211におけるキュー2111、出力ポート212におけるすべてのキュー、および出力ポート213におけるキュー2131の中にはデータパケットがない。
【００５２】
データパケットがキューのキュー先頭もしくはキュー末尾に、またはキューのキュー先頭とキュー末尾との間の中間に位置してよいことに留意されたい。たとえば、キュー2011の中で、データパケット241はキュー先頭に位置し、データパケット244はキュー末尾に位置し、データパケット242および243はキューの中間に位置する。キューは先入れ先出しキューであり、キュー先頭に位置するデータパケットはキューに入るべき最初のデータパケットであり、キュー末尾に位置するデータパケットはキューに入るべき最後のデータパケットである。キュー先頭に位置するデータパケットが好ましくは処理され、キュー末尾に位置するデータパケットは徐々にキュー先頭へシフトし得る。
【００５３】
加えて、本発明のこの実施形態では、キューのキャッシュ容量に対する、出力ポートにおける1つのキューの中のデータパケットによって占有されるキャッシュ空間のパーセンテージが第2のしきい値以下であることをデータ処理装置230が決定すると、データ処理装置230はそのキューを非ビジーキューとして規定する。第2のしきい値の値は0%から100%までに及び、たとえば、50%である。説明しやすいように、この実施形態では、第2のしきい値は0に設定される。言い換えれば、キューは、キューの中にデータパケットがない(言い換えれば、キューが使用されていない)とすれば非ビジーキューとして決定され得る。
【００５４】
さらに、本発明のこの実施形態では、出力ポートにおけるキューのキュー末尾に位置するデータパケットの宛先アドレスが受信されたデータパケットの宛先アドレスと同じであることをデータ処理装置230が決定すると、データ処理装置230はそのキューをフットプリントキューとして規定する。同じ宛先アドレスに向けられたデータパケットは一緒にフットプリントキューへ送られるので、別の宛先アドレスに向けられたデータパケットは、フットプリントキューの中で輻輳が発生するときに影響を受けない。
【００５５】
さらに、データパケット241の中で搬送される宛先アドレスは宛先アドレス1であり、データパケット242の中で搬送される宛先アドレスは宛先アドレス4であり、データパケット244の中で搬送される宛先アドレスは宛先アドレス3であり、データパケット244の中で搬送される宛先アドレスは宛先アドレス2であり、データパケット245の中で搬送される宛先アドレスは宛先アドレス1であり、データパケット246の中で搬送される宛先アドレスは宛先アドレス2であり、データパケット247の中で搬送される宛先アドレスは宛先アドレス3であり、データパケット248の中で搬送される宛先アドレスは宛先アドレス4である。
【００５６】
随意に、宛先アドレスはIPアドレスまたはメディアアクセス制御(MAC、Media Access Control)アドレスであってよい。
【００５７】
まず、図3は本発明の一実施形態によるデータ処理方法のフローチャートである。図3に示すように、データ処理方法は以下のステップを含む。
【００５８】
ステップ501:データ処理装置230は、入力ポート201によって受信されたデータパケットの宛先アドレスを取得する。
【００５９】
詳細には、データ処理装置230は、入力ポート201におけるキュー2011のキュー末尾におけるデータパケット242の宛先アドレス1を取得する。
【００６０】
ステップ502:データ処理装置230は、宛先アドレスに基づいて利用可能出力ポートを決定する。
【００６１】
詳細には、データ処理装置230は、宛先アドレスに基づいて利用可能出力ポート211および213を決定する。
【００６２】
ステップ503:データ処理装置230は、各利用可能出力ポートのビジー度を決定し、利用可能出力ポートの中に非ビジー利用可能出力ポートがあるときに非ビジー利用可能出力ポートをターゲット出力ポートとして選択し、または利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに各利用可能出力ポートにおけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートをターゲット出力ポートとして選択する。
【００６３】
このステップにおいて、データ処理装置230は、各キューの中のデータパケットのキャッシュ空間を決定し得、キューのキャッシュ容量に対する、データパケットによって占有されるキャッシュ空間のパーセンテージが第2のしきい値以下であるときに現在のキューが非ビジーキューであることを決定し得る。
【００６４】
このステップにおいて、データ処理装置230は、各利用可能出力ポートにおける非ビジーキューの数量を決定し得、各利用可能出力ポートにおけるキューの総数量の中での各利用可能出力ポートにおける非ビジーキューの数量のパーセンテージを取得し得、そのパーセンテージが第1のしきい値よりも大きいときに現在の利用可能出力ポートを非ビジー利用可能出力ポートとして決定し得、またはそのパーセンテージが第1のしきい値よりも小さいかもしくはそれに等しいときに現在の利用可能出力ポートをビジー利用可能出力ポートとして決定し得る。第1のしきい値の値は0%から100%までに及び、第1のしきい値は50%であってよい。
【００６５】
利用可能出力ポート211において、利用可能出力ポート211において3であるキューの総数量の中での、1である非ビジーキューの数量のパーセンテージは、50%よりも小さい。この場合、利用可能出力ポート211がビジーでないことが決定される。
【００６６】
同様に、利用可能出力ポート211はビジーでなく、この場合、利用可能出力ポート211におけるフットプリントキューの数量が、さらに利用可能出力ポート213におけるフットプリントキューの数量と比較される。利用可能出力ポート211におけるフットプリントキューの数量は1であり、利用可能出力ポート213におけるフットプリントキューの数量は0である。したがって、最大数量のフットプリントキューを伴う利用可能出力ポート211がターゲット出力ポートとして選択される。
【００６７】
随意の実施形態では、最大数量の非ビジーキューを伴う利用可能出力ポートが非ビジー利用可能出力ポートとして直ちに決定されてよい。
【００６８】
いくつかの例では、少なくとも2つの非ビジー利用可能出力ポートがあるとき、データ処理装置230は、非ビジー利用可能出力ポートにおけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択する。
【００６９】
いくつかの例では、少なくとも2つの非ビジー利用可能出力ポートがあり、かつ少なくとも2つの非ビジー利用可能出力ポートが最大数量のフットプリントキューを伴う少なくとも2つの非ビジー利用可能出力ポートを含むとき、データ処理装置230は、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートにおけるデータパケットまたは残存帯域幅の数量を決定し、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択する。
【００７０】
ステップ504:データ処理装置230は、ターゲット出力ポート211における各キューのビジー度を決定し、ターゲット出力ポート211において非ビジーキューがあるときに非ビジーキューをターゲット出力キューとして選択し、またはターゲット出力ポート211において非ビジーキューがないときにターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択し、ここで、フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスは、受信されたデータパケットの宛先アドレスと同じである。
【００７１】
ターゲット出力ポート211において非ビジーキュー2111があるので、非ビジーキュー211がターゲット出力キューとして選択される。
【００７２】
本出願では、非ビジー利用可能出力ポートがターゲット出力ポートとして選択される。このようにして、データパケットが非ビジー利用可能出力ポートを通じて転送されることが保証され得る。加えて、ターゲット出力ポートにおいて非ビジーキューがないとき、ターゲット出力ポートにおけるフットプリントキューがターゲット出力キューとして選択される。フットプリントキューの中で輻輳が発生しても、別のキューの中のデータパケットは送られることを妨害されない。したがって、ネットワークリソースが適切に使用され、ネットワークブロッキングが効果的に緩和され得る。利用可能出力ポートの中に非ビジー利用可能出力ポートがないとき、最大数量のフットプリントキューを伴う利用可能出力ポートがターゲット出力ポートとして選択される。このようにして、データパケットが、最大数量のフットプリントキューを伴う利用可能出力ポートを通じて転送されることが保証され得、同じ宛先アドレスを搬送するデータパケットが、同じ利用可能出力ポートにおいて一緒に配置されることが保証され得る。輻輳が発生しても、別の利用可能出力ポート上のデータパケットは影響を受けない。非ビジーキューの中で輻輳が発生しないので、非ビジーキューをターゲット出力キューとして使用することは、ターゲット出力キューの中でデータパケットが輻輳しないことを保証することができる。
【００７３】
まず、図4は本発明の一実施形態によるデータ処理方法のデータ相互作用図である。図4に示すように、データ処理方法は以下のステップを含む。
【００７４】
ステップ301:入力ポート201は、データパケット241、242、243、および244を連続的に受信する。
【００７５】
詳細には、入力ポート201は、データパケット241、242、243、および244を先入れ先出し方式でキュー2011の中に配置する。
【００７６】
ステップ302:データ処理装置230は、入力ポート201におけるキュー2011からデータパケット241の宛先アドレス1を取得する。
【００７７】
詳細には、データ処理装置230は、データパケット241のヘッダを分析してそのヘッダから宛先アドレス1を取得する。
【００７８】
ステップ303:データ処理装置230は、宛先アドレス1に基づいて複数の出力ポート211、212、および213から利用可能出力ポート211および213を選択し、ここで、データパケット241は、利用可能出力ポート211または利用可能出力ポート213のいずれかを通じて宛先アドレス1へルーティングされ得る。
【００７９】
随意に、データ処理装置230は、最短経路アルゴリズムに従って利用可能出力ポート211および213を取得してよい。
【００８０】
加えて、利用可能出力ポート211および213を取得した後、データ処理装置230は、利用可能出力ポート211のポート番号1を記録し、利用可能出力ポート213のポート番号3を記録する。
【００８１】
いくつかの例では、利用可能出力ポートを決定するための基準は、以下のうちの1つまたはそれらの組合せであってよい。
a.データパケットを送るために出力ポートが選択されるときにデッドロックが発生しているかどうか。デッドロックが発生している場合、出力ポートは非利用可能出力ポートであり、またはデッドロックが発生していない場合、出力ポートは利用可能出力ポートである。
b.データパケットを送るために出力ポートが選択されるときにライブロックが発生しているかどうか。ライブロックが発生している場合、出力ポートは非利用可能出力ポートであり、またはライブロックが発生していない場合、出力ポートは利用可能出力ポートである。
c.データパケットを送るために出力ポートが選択されるときに取り決めに違反しているかどうか。取り決めに違反している場合、出力ポートは非利用可能出力ポートであり、または取り決めに違反していない場合、出力ポートは利用可能出力ポートである。「取り決め」はアドミニストレータによって設定されてよく、たとえば、取り決めは、ノード1に向けられたすべてのデータパケットが出力ポート212を通過することを許容されないことであってよい。
【００８２】
デッドロックとは、複数のデータパケットが互いに依存するとともに互いをブロッキングしてリングを形成し、その結果として、リングの中のすべてのデータパケットが前方へ移動できず決して宛先ノードに到達できないことを意味する。ライブロックとは、データパケットが輻輳しておらず移動し続けることができるが決して宛先ノードに移動できない、たとえば、前方へ1ステップ移動した後、データパケットが後方へ1ステップ移動する状態である。
【００８３】
ステップ304:データ処理装置230は、利用可能出力ポート211および213における非ビジーキューの数量およびフットプリントキューの数量を取得する。
【００８４】
このステップにおいて、データ処理装置230は、利用可能出力ポート211および213における各キューのステータスを決定し、利用可能出力ポート211において1つの非ビジーキュー2111および1つのフットプリントキュー2113があること、ならびに利用可能出力ポート213において1つの非ビジーキュー2131がありフットプリントキューがないことを決定する。
【００８５】
ステップ305:データ処理装置230は、各利用可能出力ポートにおける非ビジーキューの数量およびフットプリントキューの数量に基づいて、利用可能出力ポートからターゲット出力ポートを選択する。
【００８６】
このステップにおいて、少なくとも2つの利用可能出力ポートしかないとき、データ処理装置230は、好ましくは最大数量の非ビジーキューを伴う利用可能出力ポートを選択するが、各利用可能出力ポートにおいて非ビジーキューがないとき、データ処理装置230は、最大数量のフットプリントキューを伴う利用可能出力ポートをターゲット出力ポートとして選択する。
【００８７】
他の例では、1つの利用可能出力ポートしかないとき、データ処理装置230は、その利用可能出力ポートをターゲット出力ポートとして直ちに使用する。
【００８８】
少なくとも2つの利用可能出力ポートがあるシナリオが、図5を参照しながらさらに説明される。図5は、本発明のこの実施形態によるデータ処理方法のサブフローチャートである。図5の中のステップ305は、詳細には以下のサブステップを含む。
【００８９】
ステップ3051:データ処理装置230は、最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートがあるかどうかを決定し、最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートがある場合、ステップ3052が実行され、または最大数量の非ビジーキューを伴う2つ未満の利用可能出力ポートしかない場合、ステップ3054が実行される。
【００９０】
ステップ3052:データ処理装置230は、最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートにおけるフットプリントキューの数量が同じであるかどうかを決定し、最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートにおけるフットプリントキューの数量が同じである場合、ステップ3053が実行され、または最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートにおけるフットプリントキューの数量が同じでない場合、ステップ3055が実行される。
【００９１】
随意に、このステップにおいて、データ処理装置230は、すべての利用可能出力ポートにおけるフットプリントキューの数量が同じであるかどうかを決定してよく、すべての利用可能出力ポートにおけるフットプリントキューの数量が同じである場合、ステップ3053が実行され、またはすべての利用可能出力ポートにおけるフットプリントキューの数量が同じでない場合、ステップ3055が実行される。
【００９２】
ステップ3054:データ処理装置230は、最大数量の非ビジーキューを伴う利用可能出力ポートをターゲット出力ポートとして選択する。
【００９３】
ステップ3053:データ処理装置230は、取り決めアルゴリズムに従って、利用可能出力ポートをターゲット出力ポートとして選択する。
【００９４】
詳細には、このステップにおける取り決めアルゴリズムは、限定はしないが以下を含む。
【００９５】
1.ランダム選択。
【００９６】
2.データパケットの宛先アドレスに関してハッシュアルゴリズムに従って演算を実行し、演算値に基づいてターゲット出力ポートを選択し、たとえば、演算値のパリティに基づいてターゲット出力ポートを選択する。
【００９７】
3.最小数量のデータパケットを伴う利用可能出力ポートを複数の出力ポートから選択する。
【００９８】
4.最大の残存帯域幅を伴う利用可能出力ポートを選択する。
【００９９】
本発明のこの実施形態では、データ処理装置230は、最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートがあること、および最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートにおけるフットプリントキューの数量が同じであることを決定する。この場合、これらの利用可能出力ポートにおける非ビジーキューの数量とフットプリントキューの数量の両方が同じであるので、いかなる利用可能出力ポートも最適な選択である。
【０１００】
ステップ3055:データ処理装置230は、最大数量のフットプリントキューを伴う利用可能出力ポートを、最大数量の非ビジーキューを伴う少なくとも2つの利用可能出力ポートからターゲット出力ポートとして選択する。
【０１０１】
上記の手順に基づくと、図2に示す実施形態では、利用可能出力ポート211において1つの非ビジーキュー2111があり、また利用可能出力ポート213において1つの非ビジーキュー2131があるので、データ処理装置230は、最大数量の非ビジーキューを伴う2つの利用可能出力ポート211および213があることを決定する。さらに、利用可能出力ポート211において1つのフットプリントキュー2113があり、また利用可能出力ポート213においてフットプリントキューがないので、データ処理装置230は、利用可能出力ポート211におけるフットプリントキューの数量が利用可能出力ポート213におけるフットプリントキューの数量とは異なることを決定する。この場合、データ処理装置230は、最大数量のフットプリントキューを伴う利用可能出力ポート211をターゲット出力ポートとして選択し、利用可能出力ポート211のポート番号1を記録する。
【０１０２】
ステップ306:データ処理装置230は、ターゲット出力ポートにおける非ビジーキューの数量およびフットプリントキューの数量に基づいてターゲット出力キューを選択する。
【０１０３】
説明しやすいように、図6は本発明のこの実施形態によるデータ処理方法の別のサブフローチャートである。図6に示すように、図4の中のステップ306は、詳細には以下のサブステップを含む。
【０１０４】
ステップ3061:データ処理装置230は、ターゲット出力ポートにおけるキューの総数量の中でのターゲット出力ポートにおける非ビジーキューの数量のパーセンテージが第1のしきい値よりも大きいかどうかを決定し、そのパーセンテージが第1のしきい値よりも大きい場合、ステップ3065が実行され、またはそのパーセンテージが第1のしきい値よりも小さいかもしくはそれに等しい場合、ステップ3062が実行される。
【０１０５】
第1のしきい値は、ターゲット出力ポートの輻輳度を示すために使用され、第1のしきい値の値は0%から100%00%までに及ぶ。随意に、この実施形態では、第1のしきい値は50%に設定される。ターゲット出力ポートにおけるキューの総数量の中でのターゲット出力ポートにおける非ビジーキューの数量のパーセンテージが第1のしきい値よりも大きいとき、ターゲット出力ポートにおいて輻輳が発生しないことが決定される。ターゲット出力ポートにおけるキューの総数量の中でのターゲット出力ポートにおける非ビジーキューの数量のパーセンテージが第1のしきい値よりも小さいかまたはそれに等しいとき、ターゲット出力ポートにおいて輻輳が発生することが決定される。
【０１０６】
ステップ3062:データ処理装置230は、ターゲット出力ポートにおいて非ビジーキューがあるかどうかを決定し、ターゲット出力ポートにおいて非ビジーキューがある場合、ステップ3066が実行され、またはターゲット出力ポートにおいて非ビジーキューがない場合、ステップ3063が実行される。
【０１０７】
ステップ3062:データ処理装置230は、ターゲット出力ポートにおいてフットプリントキューがあるかどうかを決定し、ターゲット出力ポートにおいてフットプリントキューがある場合、ステップ3064が実行され、またはターゲット出力ポートにおいてフットプリントキューがない場合、ステップ3067が実行される。
【０１０８】
ステップ3064:データ処理装置230は、任意のフットプリントキューをターゲット出力キューとして選択する。
【０１０９】
ステップ3065:データ処理装置230は、任意の非ビジーキューをターゲット出力キューとして選択する。
【０１１０】
ステップ3066:データ処理装置230は、任意の非ビジーキューをターゲット出力キューとして選択する。
【０１１１】
ステップ3067:データ処理装置230は、任意のキューをターゲット出力キューとして選択する。
【０１１２】
上記の手順に基づくと、図2に示す実施形態では、ターゲット出力ポート211において、キューの総数量は3であり非ビジーキューの数量は1である。この場合、ステップ3061において、データ処理装置230は、1/3が50%よりも小さいことを決定し、ターゲット出力ポート211において輻輳が発生することを決定し、さらに、ステップ3062が実行される。ステップ3062において、利用可能出力ポート211において1つの非ビジーキュー2111があるので、データ処理装置230は、ターゲット出力ポート211において非ビジーキュー2111があることを決定し、さらに、ステップ3066が実行される。ステップ3066において、データ処理装置230は、非ビジーキュー2111をターゲット出力キューとして選択し、第1の出力ポート211におけるターゲット出力キュー211のキュー番号1を記録する。
【０１１３】
ステップ307:データ処理装置230は、ターゲット出力ポート211のポート番号1およびターゲット出力キュー2111のキュー番号1をスイッチングデバイス220へ送る。
【０１１４】
ステップ308:スイッチングデバイス220は、ポート番号1およびキュー番号1に基づいて、入力ポート201におけるキュー2011の中のデータパケット242をターゲット出力ポート211におけるターゲット出力キュー2111へ送る。
【０１１５】
詳細には、スイッチングデバイス220は、データパケット242をターゲット出力キュー2111のキュー末尾へ送る。
【０１１６】
説明のさらなる明快のために、図7に参照が行われてよい。図7は、本発明の一実施形態によるスイッチングデバイス220の装置構造の概略図である。図7に示すように、スイッチングデバイス220は、選択的に接続され得る複数の入力データライン40および複数の出力データライン50を含む。各入力データラインは、入力ポートのキューに接続されており、そのキューのキュー先頭においてデータパケットを受信するように構成され、各出力データラインは、出力ポートのキューに接続されている。
【０１１７】
本発明のこの実施形態では、データ処理装置230は、キュー2011の中のデータパケット241から宛先アドレス1を取得し、同時に、キュー2011の中のデータパケット241が送られるべきであることをスイッチングデバイス220に通知するための通知をスイッチングデバイス220へ送る。この場合、スイッチングデバイス220は、キュー2011に接続されている入力データラインを選択する。ターゲット出力ポートのポート番号1およびターゲット出力キューのキュー番号1を取得した後、データ処理装置230は、ポート番号1およびキュー番号1をスイッチングデバイス220へ送る。スイッチングデバイス220は、ターゲット出力キュー2111に接続された出力データラインをポート番号1およびキュー番号1に基づいて選択し、先に選択されておりキュー2011に接続されている入力データラインをターゲット出力キュー2111に接続された出力データラインに接続し、キュー2011のキュー先頭におけるデータパケット241をターゲット出力キュー2111のキュー末尾へ送る。図8は、本発明の一実施形態によるスイッチングデバイスの装置構造の別の概略図である。図8は、データパケット241がターゲット出力キュー2111のキュー末尾に入力されることを示す。
【０１１８】
本発明のこの実施形態では、出力ポートにおけるキューは、ローカルな番号付け方式で番号付けされる。したがって、データ処理装置230は、出力データラインを選択するために、出力ポートの番号および出力ポートにおけるターゲット出力キューの番号をスイッチングデバイス220へ送る必要がある。他の例では、出力ポートにおけるキューは、グローバルな番号付け方式で番号付けされてもよい。この場合、データ処理装置230は、ターゲット出力キューのグローバルな番号しかスイッチングデバイス220へ送る必要がなく、スイッチングデバイス220は、グローバルな番号に基づいて出力データラインを選択し得る。グローバルな番号は、すべての出力ポートのキューを区別するために使用され得る。
【０１１９】
データ処理装置230およびスイッチングデバイス220が入力ポート201におけるキュー2011の中の他のデータパケット242、243、および244の各々に対して類似の処理を実行してよく、別の出力ポートにおけるキューの中のデータパケットに対して類似の処理を実行してよく、その結果、入力ポート上のデータパケットが、好ましくは比較的使用されていない出力ポートにおけるキューへ送られることに留意されたい。したがって、ネットワークブロッキングが効果的に緩和される。さらに、本発明のこの実施形態では、出力ポートおよび入力ポートにおけるキューの数量は、ターゲットノードの数量とは無関係であり要件に従って任意に設定されてよい。したがって、本発明のこの実施形態は、いかなるサイズのネットワークシステムにも適用可能である。
【０１２０】
したがって、本発明のこの実施形態では、ネットワークの使用されていないリソースが適切に使用され、その結果、ネットワークブロッキングが大規模ネットワークシステムにおいて効果的に緩和され得る。
【０１２１】
さらに、以下において、図9および図10は、ネットワークブロッキングが発生するときに利用可能出力ポートにおいて非ビジーキューがないシナリオを示す。図9は、本発明の一実施形態による、データパケット241を転送する前のスイッチングデバイスの装置構造の概略図である。図10は、本発明の一実施形態による、データパケット241を転送した後のスイッチングデバイスの装置構造の概略図である。
【０１２２】
図9に示すように、データ処理装置230は、キュー211からデータパケット241の宛先アドレス1を取得し、宛先アドレス1に基づいてルートを計算することによって利用可能出力ポート211および213を取得する。データ処理装置230は、利用可能出力ポート211において、非ビジーキューの数量が0でありフットプリントキューの数量が1であることを取得し、利用可能出力ポート213において、非ビジーキューの数量が0でありフットプリントキューの数量が0であることを取得する。
【０１２３】
図4に示す手順によれば、利用可能出力ポート211において0である非ビジーキューの数量が、利用可能出力ポート213において0である非ビジーキューの数量と同じであるので、データ処理装置230は、最大数量のビジーキューを伴う少なくとも2つの利用可能出力ポートがあることを決定する。この場合、データ処理装置230は、利用可能出力ポート211において1であるフットプリントキューの数量が、利用可能出力ポート213において0であるフットプリントキューの数量とは異なることをさらに決定する。フットプリントキューの数量が異なるので、データ処理装置230は、最大数量のフットプリントキューを伴う利用可能出力ポート211をターゲット出力ポートとして選択する。
【０１２４】
さらに、図6に示す手順によれば、データ処理装置230は、ターゲット出力ポートにおいて3であるキューの総数量の中での、ターゲット出力ポート211において0である非ビジーキューの数量のパーセンテージが、第1のしきい値50%よりも大きいかどうかを決定する。0は50%よりも小さいので、データ処理装置230は、ターゲット出力ポート211において非ビジーキューがあるかどうかをさらに決定する。ターゲット出力ポート211において非ビジーキューがないので、データ処理装置230は、ターゲット出力ポートにおいてフットプリントキューがあるかどうかをさらに決定する。ターゲット出力ポート211においてフットプリントキュー22112があるので、フットプリントキュー2112がターゲット出力キューとして選択される。データ処理装置230は、ポート番号1、およびターゲット出力キュー2112のキュー番号2をスイッチングデバイス220へ送る。スイッチングデバイス220は、ポート番号1およびキュー番号2に基づいて、入力ポート201におけるキュー2011のキュー先頭に位置するデータパケット241をターゲット出力キュー2112へ送る。データパケット241を送った後のスイッチングデバイスのステータスが図10に示される。
【０１２５】
この実施形態では、利用可能出力ポートにおいて非ビジーキューがないとき、最大数量のフットプリントキューを伴う利用可能出力ポートがターゲット出力ポートとして選択され、フットプリントキューはデータパケットを送るべきターゲット出力ポートから選択される。フットプリントキューの最後のデータパケットが、転送されるべきデータパケットの宛先アドレスと同じであるので、フットプリントキューの中でブロッキングが発生しても入力ポートにおける別の宛先アドレスに向けられたデータパケットの転送は影響を受けない。したがって、ネットワークブロッキングが効果的に緩和され得る。
【０１２６】
以下において、図11および図12は、ネットワークブロッキングが発生しないときに利用可能出力ポートにおいて非ビジーキューがあるシナリオを示す。図11は、本発明の一実施形態による、データパケット241を転送する前のスイッチングデバイスの装置構造の別の概略図である。図12は、本発明の一実施形態による、データパケット241を転送した後のスイッチングデバイスの装置構造の別の概略図である。
【０１２７】
図11に示すように、データ処理装置230は、キュー211からデータパケット241の宛先アドレス1を取得し、宛先アドレス1に基づいてルートを計算することによって利用可能出力ポート211および213を取得する。データ処理装置230は、利用可能出力ポート211において、非ビジーキューの数量が0でありフットプリントキューの数量が1であることを取得し、利用可能出力ポート213において、非ビジーキューの数量が2でありフットプリントキューの数量が0であることを取得する。
【０１２８】
図5に示す手順によれば、利用可能出力ポート211において0である非ビジーキューの数量が、利用可能出力ポート213において2である非ビジーキューの数量とは異なるので、データ処理装置230は、最大数量の非ビジーキューを伴う2つ未満の利用可能出力ポートしかないことを決定する。この場合、データ処理装置230は、最大数量の非ビジーキューを伴う利用可能出力ポート213をターゲット出力ポートとして選択する。
【０１２９】
さらに、図6に示す手順によれば、データ処理装置230は、ターゲット出力ポート213において3であるキューの総数量の中での、ターゲット出力ポート213において2である非ビジーキューの数量のパーセンテージが、第1のしきい値50%よりも大きいかどうかを決定する。2/3は50%よりも大きいので、データ処理装置230は、任意の非ビジーキュー(2131または2132)をターゲット出力キューとして選択する。
【０１３０】
データ処理装置230が非ビジーキュー2132をターゲット出力キューとして選択すると仮定すると、データ処理装置230は、ターゲット出力ポートのポート番号3、およびキュー番号2をスイッチングデバイス220へ送る。スイッチングデバイス220は、ポート番号3およびキュー番号2に基づいて、入力ポート201におけるキュー2011のキュー先頭に位置するデータパケット241データパケットをターゲット出力キュー2132へ送る。データパケット241を送った後のスイッチングデバイスのステータスが図12に示される。
【０１３１】
この実施形態では、最大数量の非ビジーキューを伴う利用可能出力ポートがターゲット出力ポートとして選択され、非ビジーキューはターゲット出力ポートからターゲット出力キューとして選択される。非ビジーキューの中でブロッキングが発生しないので、ネットワークブロッキングが効果的に緩和され得る。
【０１３２】
以下において、図13は本発明の一実施形態によるデータ処理装置の装置構造の概略図である。図13に示すように、データ処理装置20は、
入力ポートによって受信されたデータパケットの宛先アドレスを取得するように構成された宛先アドレス取得モジュール601と、
宛先アドレスに基づいて利用可能出力ポートを決定するように構成された利用可能出力ポート決定モジュール602と、
各利用可能出力ポートのビジー度を決定し、利用可能出力ポートの中に非ビジー利用可能出力ポートがあるときに非ビジー利用可能出力ポートをターゲット出力ポートとして選択するように構成されたターゲット出力ポート選択モジュール603と、
ターゲット出力ポートにおける各キューのビジー度を決定し、ターゲット出力ポートにおいて非ビジーキューがないときにターゲット出力ポートにおけるフットプリントキューをターゲット出力キューとして選択するように構成されたターゲット出力キュー選択モジュール604とを含み、ここで、フットプリントキューのキュー末尾におけるデータパケットの宛先アドレスは、受信されたデータパケットの宛先アドレスと同じである。
【０１３３】
随意に、ターゲット出力ポート選択モジュール603は、
利用可能出力ポートの中に非ビジー利用可能出力ポートがないときに各利用可能出力ポートにおけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う利用可能出力ポートをターゲット出力ポートとして選択するようにさらに構成される。
【０１３４】
随意に、ターゲット出力キュー選択モジュール604は、
ターゲット出力ポートにおいて非ビジーキューがあるとき、非ビジーキューをターゲット出力キューとして選択するようにさらに構成される。
【０１３５】
随意に、ターゲット出力ポート選択モジュール603は、
非ビジー利用可能出力ポートにおけるフットプリントキューの数量を決定し、最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択するようにさらに構成される。
【０１３６】
随意に、ターゲット出力ポート選択モジュール603は、
最大数量のフットプリントキューを伴う非ビジー利用可能出力ポートにおけるデータパケットまたは残存帯域幅の数量を決定し、最小数量のデータパケットまたは最大の残存帯域幅を伴う非ビジー利用可能出力ポートをターゲット出力ポートとして選択するようにさらに構成される。
【０１３７】
随意に、ターゲット出力ポート選択モジュール603は、
各利用可能出力ポートにおける非ビジーキューの数量を決定し、各利用可能出力ポートにおけるキューの総数量の中での各利用可能出力ポートにおける非ビジーキューの数量のパーセンテージを取得し、そのパーセンテージが第1のしきい値よりも大きいときに現在の利用可能出力ポートが非ビジー利用可能出力ポートであることを決定するように特に構成される。
【０１３８】
随意に、ターゲット出力キュー選択モジュール604は、
各キューの中のデータパケットのキャッシュ空間を決定し、キューのキャッシュ容量に対する、データパケットによって占有されるキャッシュ空間のパーセンテージが第2のしきい値以下であるときに現在のキューが非ビジーキューであることを決定するように特に構成される。
【０１３９】
本発明の一実施形態は、スイッチングデバイスをさらに提供する。図14は、本発明の一実施形態によるスイッチングデバイスの装置構造の概略図である。図14に示すように、スイッチングデバイスは、入力ポート201、出力ポート211、212、および213、プロセッサ701、メモリ702、ならびにバス703を含む。入力ポート201、出力ポート211、212、および213、プロセッサ701、ならびにメモリ702は各々、バス703に接続されている。メモリ702はプログラム命令を記憶し、プロセッサ701は図3に示すステップを実行するために、プログラム命令を動作させる。
【０１４０】
本発明のこの実施形態は、データセンターネットワーク、高性能コンピュータ相互接続ネットワーク、マルチ・コア・プロセッサ・ネットワーク・オン・チップを含む、すべてのロスレスネットワークに適用され得る。ネットワークブロッキングが発生するとき、ブロッキングの確率を効果的に低減するために、データパケットはフットプリントキューに沿って前方へ移動することを必要とされる場合がある。ネットワークブロッキングが発生しないとき、ネットワーク性能を改善するために、好ましくは非ビジーキューが選択される。実験結果は、ネットワーク飽和スループットレートが最大で約50%だけ高められ得ることを示す。
【０１４１】
本発明のこの実施形態におけるデータ処理装置は、マルチコアプロセッサチップおよびネットワークスイッチングチップを使用することによって実装され得る。
【０１４２】
上記で説明したいかなる装置実施形態も一例にすぎないことに留意されたい。別個の部分として説明したユニットは物理的に別個であってもなくてもよく、ユニットとして表示した部分は、物理的なユニットであってもなくてもよく、1つの位置に配置されてよく、または複数のネットワークユニット上に分散されてもよい。一部または全部のモジュールは、本実施形態の解決策の目的を達成するための実際の必要に従って選択されてよい。加えて、本発明によって提供される装置実施形態の添付図面では、モジュール間の接続関係は、モジュールが互いとの通信接続を有することを示し、通信接続は1つまたは複数の通信バスまたは信号ケーブルとして特に実装され得る。当業者は、創造的な取組みを伴わずに本発明の実施形態を理解および実施し得る。
【０１４３】
上記の実装形態の説明に基づくと、本発明が、必要な汎用ハードウェアに加えてソフトウェアによって、または専用集積回路、専用CPU、専用メモリ、専用部品などを含む専用ハードウェアによって実装され得ることを、当業者は明確に理解し得る。一般に、コンピュータプログラムによって実行され得るいかなる機能も、対応するハードウェアを使用することによって容易に実施され得る。その上、同じ機能を達成するために使用される特定のハードウェア構造は、様々な形態のものであってよく、たとえば、アナログ回路、デジタル回路、専用回路などの形態をなしてよい。しかしながら、本発明については、たいていの場合、ソフトウェアプログラム実装形態がよりよい実装形態である。そのような理解に基づくと、本質的に本発明の技術的解決策、または従来技術に寄与する部分は、ソフトウェア製品の形態で実装され得る。ソフトウェア製品は、コンピュータのフロッピーディスク、USBフラッシュドライブ、リムーバブルハードディスク、読取り専用メモリ(ROM、Read-Only Memory)、ランダムアクセスメモリ(RAM、Random Access Memory)、磁気ディスク、または光ディスクなどの可読記憶媒体の中に記憶され、本発明の実施形態で説明した方法を実行するように(パーソナルコンピュータ、サーバ、ネットワークデバイスなどであってよい)コンピュータデバイスに命令するためのいくつかの命令を含む。
【０１４４】
上記のシステム、装置、およびユニットの詳細な動作プロセスが、上記の方法実施形態における対応するプロセスを参照することが、当業者によって明確に理解されてよく、詳細は本明細書で再び説明しない。
【０１４５】
上記の説明は、本発明の特定の実装形態にすぎず、本発明の保護範囲を限定するものではない。本発明において開示する技術的範囲内の、当業者によって容易に解明されるいかなる変形または置換も、本発明の保護範囲内に入るものとする。したがって、本発明の保護範囲は、特許請求の範囲の保護範囲を受けるものとする。
【符号の説明】
【０１４６】
20  スイッチングデバイス
21  ソースノード
22  宛先ノード
23、24、25、26、27  スイッチングデバイス
40  入力データライン
50  出力データライン
201、202、203  入力ポート
211、212、213  出力ポート
220  スイッチングデバイス
230  データ処理装置
241、242、243、244、245、246、247、248  データパケット
601  宛先アドレス取得モジュール
602  利用可能出力ポート決定モジュール
603  ターゲット出力ポート選択モジュール
604  ターゲット出力キュー選択モジュール
701  プロセッサ
702  メモリ
703  バス
2011、2012、2013  キュー
2021、2022、2023  キュー
2031、2032、2033  キュー
2111、2112、2113  キュー
2121、2122、2123  キュー
2131、2132、2133  キュー
【図１】
0006932793.tif 000002
【図２】
0006932793.tif 000003
【図３】
0006932793.tif 000004
【図４】
0006932793.tif 000005
【図５】
0006932793.tif 000006
【図６】
0006932793.tif 000007
【図７】
0006932793.tif 000008
【図８】
0006932793.tif 000009
【図９】
0006932793.tif 000010
【図１０】
0006932793.tif 000011
【図１１】
0006932793.tif 000012
【図１２】
0006932793.tif 000013
【図１３】
0006932793.tif 000014
【図１４】
0006932793.tif 000015