(57)【要約】  コンピュータネットワークを介してメッセージをルーティングする際の安定性を強化し、予測可能性を増大し、伝送コストを低減し、帯域幅を節約するシステムおよび方法を提供する。さらに、メッセージをターゲット配信ノードに最も近いノードへ伝送する、メッセージ伝送を改良するシステムおよび方法を提供する。ターゲットノードへの配信が可能なときに、メッセージの伝送はネットワーク上の障害のポイントで中断する。この場合、ターゲットノードへの配信が後に達成されるか、またはメッセージを送信者に返送することになる。
2008546276.tif 000002
【特許請求の範囲】
【請求項１】
カレントノード、ターゲットノード、および前記カレントノードと前記ターゲットノードとの間のネットワークに接続された１または複数の中間ノードを有するコンピュータネットワークを介してメッセージを伝送するコンピュータ実装された方法であって、
前記カレントノードの、前記ターゲットノードまでの伝送コストより小さい、前記ターゲットノードまでの伝送コストを有する、前記ネットワーク上に配置された中間ノードの宛先代替ノードテーブルを作成するステップであって、前記中間ノードは、それらの最小伝送コストに従って優先付けされる、宛先代替ノードテーブルを作成するステップと、
前記ターゲットノードへ前記メッセージの伝送を試みるステップと、
前記ターゲットノードへの前記メッセージの伝送が失敗した場合に、前記宛先代替テーブルにて識別された当該優先順位に応じて、少なくとも１つの中間ノードへ前記メッセージの伝送を試みるステップと
を備えることを特徴とするコンピュータ実装された方法。
【請求項２】
前記ターゲットノードへの前記メッセージ伝送の試みが失敗した場合に、最高優先順位を有する前記中間ノードへメッセージの伝送を試みるステップと、
前記最高順位中間ノードへの前記メッセージ伝送の試みが失敗した場合に、次に低い優先順位の中間ノードへ前記メッセージの伝送を試みるステップと
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記メッセージは、コンピュータネットワークを介して前記カレントノードから少なくとも２つのターゲットノードへ伝送され、
前記方法は、
前記カレントノードをルートとする前記ネットワークの最小スパニングツリーを作成するステップと、
異なるノードに存在する少なくとも２つの受信者の前記最小スパニングツリーから、分岐点の最終ノードを判断するステップと、
分岐点の最終ノードに従って受信者をグループ化するステップと、
分岐点の最終ノードへ前記メッセージを伝送するステップと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項４】
分岐点の前記最終ノードが前記メッセージを前記ターゲットへ伝送可能か否かを判断するステップと、
分岐点の前記最終ノードが前記ターゲットノードへ伝送不可能であると判断された時に、前記ターゲットノードへの伝送のために、前記カレントノードから前記メッセージを分岐するステップと
をさらに備えることを特徴とする請求項３に記載の方法。
【請求項５】
前記メッセージ用のノード間の伝送の数を追跡するステップと、
伝送の数が最小閾値を超えると、整定期間のための追加の伝送を遅延させるステップと、
伝送の数が最大閾値を越えると、配信不能として前記メッセージを返送するステップと、
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項６】
前記ターゲットノードへの前記メッセージの伝送が失敗した場合、
ネットワークノードの利用可能な伝送スケジュールを判断するステップと、
前記宛先代替テーブル内で識別された優先順位と、当該利用可能な伝送スケジュールと、に従って、中間ノードへ前記メッセージの伝送を試みるステップと
をさらに備えることを特徴とする請求項１に記載の方法。
【請求項７】
１または複数のコンピュータ可読媒体が、請求項１に記載のコンピュータ実行可能な方法を実施するためのコンピュータ実行可能命令を有することを特徴とする請求項１に記載の方法。
【請求項８】
メッセージ通信ネットワーク上に、カレントサーバ、ターゲットサーバ、および前記カレントサーバと前記ターゲットサーバとの間のネットワークに接続された１または複数の中間サーバを有する、メッセージを伝送するためのメッセージ通信システムであって、
前記ターゲットサーバまでの伝送コストを有する、前記ネットワーク上に配置された前記中間サーバの宛先代替テーブルであって、前記中間サーバはその最小伝送コストに従って優先順位付けされる宛先代替テーブルと、
コンピュータ実行可能命令を実行するよう構成されるカレントサーバであって、
前記ターゲットサーバへのメッセージの伝送を試み、
前記ターゲットサーバへのメッセージの伝送が失敗した場合、前記宛先代替テーブル内で識別された当該優先順位に応じて、少なくとも１つの中間サーバへ前記メッセージの伝送を試みる、カレントサーバと
を備えることを特徴とするシステム。
【請求項９】
前記カレントサーバは、さらに
前記ターゲットノードへの前記メッセージ伝送の試みが失敗した場合に、最高優先順位を有する前記中間ノードへ前記メッセージの伝送を試み、
前記最高順位中間ノードへの前記メッセージ伝送の試みが失敗した場合に、次に低い優先順位の中間ノードへ前記メッセージの伝送を試みる、
ためのコンピュータ実行可能命令を実行するよう構成されることを特徴とする請求項８に記載のシステム。
【請求項１０】
前記メッセージは、コンピュータネットワークを介して、前記メッセージを前記カレントサーバから少なくとも２つのターゲットサーバへ伝送され、
前記カレントサーバは、さらに
前記カレントサーバをルートとするネットワークサーバの最小スパニングツリーを作成し、
異なるサーバに存在する少なくとも２つの受信者の最小スパニングツリーから分岐点の最終サーバを判断し、
分岐点の最終サーバに従って受信者をグループ化し、
分岐点の最終ノードへ前記メッセージを伝送する
ためのコンピュータ実行可能命令を実行するよう構成されることを特徴とする請求項８に記載のシステム。
【請求項１１】
分岐点の前記最終ノードが前記ターゲットノードへ前記メッセージを伝送可能であるかを判断し、
分岐点の前記最終ノードが前記ターゲットノードへ前記メッセージを伝送不可能であると判断したとき、前記ターゲットノードへの伝送のために前記カレントノードから前記メッセージを分岐させること
をさらに備えることを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記メッセージ用のノード間の伝送の数を追跡することをさらに備え、
伝送の数が最小閾値を超えると、整定期間のために追加の伝送を遅延させ、
伝送の数が最大閾値を超えると、配信不能として前記メッセージを返送すること
を特徴とする請求項８に記載のシステム。
【請求項１３】
前記ターゲットノードへの前記メッセージの伝送が失敗した場合、
ネットワークノードの利用可能な伝送スケジュールを判断し、
前記宛先代替テーブル内で識別された優先順位と、当該利用可能な伝送スケジュールと、に従って、中間ノードへ前記メッセージの伝送を試みること
をさらに備えることを特徴とする請求項８に記載のシステム。
【請求項１４】
カレントノード、ターゲットノード、および前記カレントノードと前記ターゲットノードとの間に接続された１または複数の中間ノードを有する、コンピュータネットワークを介してメッセージを伝送するためのコンピュータ実行可能命令を有する、１または複数のコンピュータ可読媒体であって、
前記中間ノードから前記ターゲットノードまでの伝送コストを判断し、その関連伝送コストに従って、前記中間ノードを優先順位付けする命令と、
前記ターゲットノードへ前記メッセージの伝送を試みて、前記ターゲットノードへの前記メッセージの伝送が失敗した場合に、前記宛先代替テーブルにて識別された当該優先順位に応じて、少なくとも１つの中間ノードへ前記メッセージの伝送を試みる命令と
を備えることを特徴とするコンピュータ可読媒体。
【請求項１５】
前記ターゲットノードへの前記メッセージ伝送の試みが失敗した場合に、最高優先順位を有する前記中間ノードへ前記メッセージの伝送を試みる命令と、
前記最高優先順位中間ノードへの前記メッセージ伝送の試みが失敗した場合に、次に低い優先順位の中間ノードへ前記メッセージの伝送を試みる命令と
をさらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１６】
前記メッセージは、コンピュータネットワークを介して前記カレントノードから少なくとも２つのターゲットノードへ伝送され、
前記コンピュータ可読媒体は、
前記カレントノードをルートとするネットワークの最小スパニングツリーを作成する命令と、
異なるノードに存在する少なくとも２つの受信者の最小スパニングツリーから分岐点の最終ノードを判断する命令と、
分岐点の最終ノードに従って受信者をグループ化する命令と、
分岐点の前記最終ノードへ前記メッセージの伝送を試みる命令と
をさらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１７】
分岐点の前記最終ノードが前記ターゲットノードへ前記メッセージの伝送が可能か否かを判断し、分岐点の前記最終ノードが前記ターゲットノードへ前記メッセージの伝送が不可能であると判断したとき、前記ターゲットノードへの伝送のために、前記カレントノードから前記メッセージを分岐させる命令を
さらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１８】
前記メッセージ用のノード間の伝送の数を追跡する命令と、
伝送の数が最小閾値を超える場合、整定期間のための追加の伝送を遅延させる命令と、
伝送の数が最大閾値を超える場合、配信不能として前記メッセージを返送する命令と
をさらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項１９】
前記ターゲットノードへの前記メッセージの伝送が失敗した場合、
ネットワークノードの利用可能な伝送スケジュールを判断する命令と、
前記宛先代替テーブルにて識別された優先順位と、当該利用可能な伝送スケジュールと、に従って、中間ノードへ前記メッセージの伝送を試みる命令と
をさらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【請求項２０】
最近接続が失敗した全ノードのキャッシュを保持する命令であって、前記キャッシュは、最近失敗したノードへの前記メッセージの伝送の試みを回避するために利用される、キャッシュを保持する命令を
さらに備えることを特徴とする請求項１４に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ネットワークを介する、１または複数の受信者へのメッセージのルーティングの分野に関する。より詳細には、本発明の実施形態は、ネットワークを介して電子メールを最小の転送コストで確実にルーティングするシステムおよび方法に関し、特に、単一のシステム間転送が複数の受信者に対する責任を取らせることができるとき、さらには、責任をストア＆フォワード方式で転送することを含むシステムにおけるものである。また本発明の実施形態は、有益なことに、異なるノードに存在する複数の受信者宛てのメールを転送する際のネットワークトラフィックを最小化し、管理的なネットワークトラフィックの量を最小化し、ネットワークの不整合ビューのために生じる無限ループを防止する観点から、コストを低減するシステムおよび方法を提供する。
【背景技術】
【０００２】
いくつかの従来のシステムおよび方法は、ネットワークを構成する異なるノードが合意したネットワークコストに基づいて、ネットワークを介してメールをルーティングすることを提供するものである。しかし、これらのシステムは、転送コストが異なる場合、あるいは転送コストが変動する場合に、安定性に欠ける。これは、メールを転送するよりも前に、ノードがその転送コストに合意しなければならないためである。これらのシステムは、ネットワークトポロジのノードビューの差を解消するために、複雑性あるいはネットワークトラフィックの観点から、非常に高いコストも必要となる。したがって、コストが合意されるまでに、メールが不必要に遅延されることがある。
【０００３】
他のシステムおよび方法は、複数のメール受信者へのルーティングのために、受信者までの個々の最短のパスに基づいてルーティングパスを計算することを提供する。しかし、これらの方法は、複数の受信者への複数のリンクを介して、同一のメールファイルを送信することにより、不必要に帯域幅を使用する場合がある。
【０００４】
ネットワークトポロジに関してアプリケーションレベルでの合意に依存するシステムは、管理者にとっては予測できないものである。本システムは、システムの振る舞いがより広範なネットワーク状態に渡り予測可能であるので、システムの判断をより容易にする。本発明のシステムおよび方法は、メッセージがその最終宛先に届けられない場合、対象宛先のできる限り近くに届くようにすることを保障する。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
したがって、１または複数の上述の不都合及び他の不都合に対処するため、１または複数の受信者にネットワークを介してメールを確実にルーティングするシステムおよび方法が望まれる。
【課題を解決するための手段】
【０００６】
本発明は、送信ノードと受信ノードとの間の伝送コストの完全な合意を必要としないで、ネットワークを介してメッセージをルーティングするシステムおよび方法を提供することで、周知の技術の欠点を克服するものである。本システムおよび方法において、このメッセージは、伝送コストの点から、受信ノードに最も近い使用可能なノードに中継される。また、本システムおよび方法は、異なるノードに存在する複数の受信者にネットワークを介してメッセージをルーティングする時に、ネットワークに共通である分岐点の最終ノードが同一のトポロジビューを保持する範囲で受信者にルーティングするまでメッセージが分岐するのを遅延させることにより、ネットワークの帯域幅を最適化する。また、ノードの利用可能なスケジュールに基づいて、受信者ノードに最も近いノードにメールをルーティングすることにより、信頼性を改善する。さらに、本発明のシステムおよび方法は、メッセージを伝送すべき１または複数の利用可能なノードを判断することにより、受信者にメッセージをルーティングするスピードを最適化し、あるノードが使用不可能である場合、メッセージを伝送すべき次の最適なノードを選択する。
【０００７】
本発明によれば、一実施態様は、カレントノード、ターゲットノードおよび、カレントノードとターゲットノードとの間のネットワークに接続された１または複数の中間ノードを有するコンピュータネットワークを介してメッセージを伝送する、コンピュータ実装方法を提供する。本方法は、カレントノードのターゲットノードまでの伝送コストより小さいターゲットノードまでの伝送コストを有する、ネットワーク上に位置する中間ノードの宛先代替テーブルを作成することを備える。ここで、中間ノードは、最小伝送コストに従って、優先順位付けされる。ターゲットノードへメッセージの伝送を試みる。ターゲットノードへのメッセージの伝送に失敗した場合、メッセージの伝送は、宛先代替テーブルにおいてその識別された優先順位に応じて、少なくとも１つの中間ノード宛てに試みる。
【０００８】
本発明のもう一つの態様は、メッセージ通信ネットワーク上のカレントサーバとターゲットサーバとの間でメッセージを伝送するメッセージ通信システムを含む。本システムは、カレントサーバ、ターゲットサーバおよび、ネットワークに接続された１または複数の中間サーバを備える。また、本システムは、ターゲットサーバまでの伝送コストを有する、ネットワーク上に位置する中間サーバの宛先代替テーブルを含み、中間サーバは、その最小伝送コストに従って、優先順位付けされる。カレントサーバは、ターゲットサーバへメッセージの伝送を試みるコンピュータ実行可能命令を実行するよう構成される。ターゲットサーバへのメッセージの伝送が失敗した場合、カレントサーバが、宛先代替テーブルにおいて識別された優先順位に応じて、少なくとも１つの中間サーバへメッセージの伝送を試みる。
【０００９】
本発明のもう一つの態様は、コンピュータネットワークを介してメッセージを伝送するコンピュータ実行可能命令を有する１または複数のコンピュータ可読媒体を含む。ネットワークは、カレントノード、ターゲットノードおよび、カレントノードとターゲットノードとの間のネットワークに接続された１または複数の中間ノードを備える。コンピュータ実行可能命令は、中間ノードからターゲットノードまでの伝送コストを判断し、その関連する伝送コストに従って、中間ノードを順位付けする命令を含む。該命令は、またターゲットノードへメールの伝送を試みる命令を含み、ターゲットノードへのメッセージの伝送が失敗した場合、宛先代替テーブル内において識別された優先順位に応じて、少なくとも１つの中間ノードへメッセージの伝送を試みる。
【００１０】
あるいは、本発明は、複数の他の方法および装置を備えてもよい。
【００１１】
他の特徴は、以下の説明で明らかにし、明示する。
【００１２】
対応する参照番号は、全図面にわたり対応する部分を示す。
【発明を実施するための最良の形態】
【００１３】
まず、図１は、本発明を実装するメッセージルーティングネットワークにおける、ノードのネットワークおよびノード間のリンクを例示的に説明する図である。コンピュータネットワーク１００は、多数のノード、またはノードを接続するリンクを介して電子メッセージ、電子メール、パケット等のメッセージを送受信するメッセージ転送エージェント（ＭＴＡ）を備える。各ノードは、送信ノードから受信者がいるターゲットノードへネットワークを介してルーティングされるメッセージあるいはメールを受信する受信者を含んでもよい。ネットワーク１００のさまざまなノードを接続するラインに隣接する太字番号は、複数のリンクにわたるメッセージの伝送に関連付けられた仮説伝送コストを示す。本実施例において、ノード１０２（ハワイ）からノード１０４（シアトル）へのメッセージ送信に関連付けられた伝送コストは、２００となる。コストは、ネットワーク使用可能性に反比例するとも考えられる。したがって、リンクを使用する機会コストと見ることができる。本実施例では、例示のために固定コストを使用しているが、より高度な実装においては、帯域幅が割り当てられ、消費されると、実際のコストは動的に更新される。
【００１４】
ネットワークを介するメッセージのルーティングを説明すると、ノード１０２（ハワイ）に位置するメッセージの送信者が、英国・グリニッチのノード１０８に位置する第１受信者およびフランス・パリのノード１１２に位置する第２受信者へメールを送信する。該メッセージが２つの別個のメッセージとして、ハワイからグリニッチおよびハワイからパリへ個々に送信される予定である場合、２人の受信者へファイルを送信する全伝送コストは、７４０（例えば２００＋８０＋９０（ハワイからグリニッチ）および２００＋８０＋９０（ハワイからパリ））となる。しかし、該メッセージを単一ファイルとして、異なる受信者までのパス上の２つの経路に共通であるノードリンクを介して送信する場合、伝送コストは低減され、ネットワークの帯域幅は節約される。したがって、該メッセージが単一ファイル伝送として、ノード１０２（ハワイ）からノード１０４（シアトル）およびノード１０４（シアトル）からノード１０６（ニューヨーク）への共通経路に沿って送信され、該メッセージがノード１０６（ニューヨーク）において、ノード１０８（グリニッチ）およびノード１１２（パリ）へ送信される２つのメッセージに分岐される場合、メールの伝送の全コストは４６０（例えば２００＋８０（ハワイからニューヨーク）および９０＋９０（ニューヨークからグリニッチおよびニューヨークからパリ））となる。ニューヨークの帯域幅は、介在ノードが分岐点にない場合およびネットワーク障害がない場合、介在ノードへのアプリケーションレベルの転送を回避ことすることにより、維持される。例えば、メッセージをハワイからニューヨークへ直接伝送する。しかし、ハワイがニューヨークに届く範囲ではない場合、ハワイからシアトルへメッセージを送信するよう試みる。
【００１５】
メッセージが、あるノードで分岐されると、該ノードは、ターゲットノードまでの経路に沿って次ノードへメッセージを伝送する責任を負う。したがって、例えば、メッセージがあるノードで分割され、３つの異なるノードへ送信される予定であれば、そのカレントノードはメッセージの伝送を継続する責任を維持する。受信ノードがメッセージを受取ると、受信ノードは、ターゲットノードがメッセージを受取るまで、ターゲットノードまでの経路に沿って次ノードへメッセージを伝送するなどの責任を負う。
【００１６】
本発明のシステムおよび方法の一実施態様では、２人の受信者の最終共通ノードまでメッセージの分岐を遅延させることにより、ネットワークを介するメッセージのルーティングを最適化する。本実施態様は、伝送コストの点から、受信者のターゲットノードに最も近い分岐点の共通ノードへメッセージを中継することにより、有益に伝送コストを低減し、利用可能なネットワークの帯域幅を節約し、またメッセージを受信する受信者の信頼性およびスピードを改善する。上述の図面によると、本発明のシステムおよび方法は、ノード１０６（ニューヨーク）においてメッセージの分岐を遅延させ、２人の受信者の分岐点の最終共通ノード（図１では、ノード１１０（ロンドン））にファイルを転送する。ノード１１０（ロンドン）において、最後にメッセージは分岐され、ノード１０８（グリニッチ）およびノード１１２（パリ）へ伝送される。したがって、２人の受信者へメッセージを伝送する伝送コストは４００（例えば２００＋８０＋１００（ハワイからロンドン）および１０＋１０（ロンドンからグリニッチおよびロンドンからパリ））となる。
【００１７】
本明細書で使用されているように、あるノードに対する近接性あるいは距離を説明したものを、１ノードからターゲットノードへメッセージを送信するのに必要な伝送コストと呼ぶ。したがって、ターゲットノードに最も近いノードは、ターゲットノードへファイルを送信するための最小の伝送コストあるいは、以上で概説した機会コストなどの他の概念的なコストを有するノードとなる。
【００１８】
ネットワークにおいてメッセージを受信者に最も近いノードへ伝送することは、ネットワーク上でメッセージの伝送を遅延させる可能性がある障害が生じる場合に有効である。受信者にできる限り近くにメッセージを伝送することにより、ネットワーク障害のイベント時に、ターゲットノードに向かう動作を進めることができる。そのようなイベント時には、該ネットワークが利用可能になった時に、メッセージを迅速に伝送することができる。これは、また同時に必ずしも全てのリンクが利用可能ではない場合に対処することができる。例えば、開始ノードからターゲットノードへのエンドツーエンド接続は、実際には利用可能ではないこともある。しかし、本発明の方法およびシステムを利用すれば、それでも動作を進行することができ、最終的にはメッセージは通過することになる。さらに、ネットワークノードはより改善された、より信頼できるコストを有することが多い。またネットワークノードは、遠隔ノードよりも、そのネットワークノードにより近接するノードに関するルーティング情報を有することが多い。したがって、受信者のターゲットノードの近くで障害が生じた場合、近接したノードが受信者までの代替パスを識別することができる。この代替パスは、コスト効率が良く、送信者に配信不能メッセージとして返送されるのではなく、受信者が確実にメッセージを受信できるようにする。
【００１９】
ファイルがターゲットノードに直接送信できないイベント時に、どのノードにメッセージを送信すべきかを判断するのに、いくつかの方法を用いることができる。
【００２０】
一実施態様において、カレントノードに始まりターゲットノードで終わり、カレントノードとターゲットノードとの間のネットワークに接続された１または複数の中間ノードを含む、直線パスを識別する。ターゲットノードが利用不可能である場合、ターゲットノードに最も近い中間ノードにファイルの伝送を試みる。その中間ノードが利用不可能である場合、ターゲットノードに２番目に近い中間ノードにメッセージの送信を試みるなど、まだ試されていない他の中間ノードが残っていない状態まで、あるいは試みが所定回数の閾値になるまで行う。そのようなイベント時に、メッセージを、後で再送するために遅延させ、あるいは配信不能メッセージとして送信者に返送させることもある。
【００２１】
他の実施態様では、ターゲットノードまでの指定された伝送コスト範囲内のノードを識別する。該ノードは、それから、最小の伝送コストが最高の優先順位を有するというように、伝送コストの優先順位順で編成される。したがって、ターゲットノードへの伝送の試みに失敗した場合、次は最高順位のノード、すなわち最小の伝送コストを有するノードへの伝送を試みる。その伝送の試みも失敗した場合、次の最高順位のノード（すなわち、２番目に小さい伝送コストを有するノード）への３回目の伝送を試みる。このプロセスを、指定コスト範囲内の他のノードが残っていない状態まで、あるいは試みが所定回数の閾値になるまで繰り返す。上述したように、そのようなイベント時に、メッセージを、後で再送するために遅延させ、あるいは配信不能メッセージとして送信者に返送させることもある。他の実施態様においては、第１のコスト範囲の周りに同心円を形成する、第２の最小伝送コスト範囲を識別する。最小のコスト範囲に関して上述したのと同様の第２の範囲内のノードへの伝送を試みる。さらに他の実施態様は、追加の伝送コスト範囲の同心円を含むことができる。
【００２２】
他の実施態様では、「再処理半減（halving retreat）」プロセスが続き、カレントノードとターゲットノードとの間で直線状に並ぶ中間ノードを識別する。ターゲットノードへの伝送の試みが失敗した場合、中間ノード、例えば「ノードＤ」へメッセージの伝送を試みる。ノードＤへの伝送が失敗した場合、カレントノードとノードＤの中間に位置する中間ノードへメッセージの伝送を試みる。このプロセスは、他のノードが残っていない状態になるまで、または、試みが所定回数の閾値になるまで続ける。上述したように、そのようなイベント時に、メッセージを、後で再送するために遅延させ、あるいは配信不能メッセージとして送信者に返送させることもある。
【００２３】
他の実施態様では、メッセージを伝送すべき可能性のある代替ノードを識別するのに、加速再処理（accelerated retreat）プロセスを利用してもよい。ターゲットノードが利用不可能である場合、加速再処理プロセスはノード、例えば、ターゲットノードからの４つのノードを識別してもよい。該ノードへのファイルの送信が失敗した場合、例えば、離れた１２個のノードへのファイルの送信を試みるなど、他のノードが残っていない状態まで、あるいは試みが所定回数の閾値になるまで行う。上述したように、そのようなイベント時に、メッセージを、後で再送するために遅延させ、あるいは配信不能メッセージとして送信者に返送させることもある。
【００２４】
さらに他の実施態様では、個々のノードのスケジュールに従って、できる限りターゲットノードに近くにメッセージを送信するよう試みる。この方法は、ターゲットノードに直接メッセージを伝送できない場合、メッセージを伝送するための再処理方策に関して上述したパターンのいずれかと組み合わせてもよい。例えば、カレントノードとターゲットノードとの間のパスは中間ノードＡ、ＢおよびＣからなる。ここで、ノードＡはターゲットノードから最も遠く、ノードＣはターゲットノードに最も近い。現在の時刻が午後３時３０分で、ノードＡが午後１時から４時までの間にファイルを受取り、ノードＢが午後３時から６時までの間にファイルを受取り、ノードＣが午後６時から１０時までの間にファイルを受取る場合、まず動作スケジュールに従って、ターゲットノードに最も近い利用可能なノードＢにメッセージを伝送するよう試みる。
【００２５】
本発明の他の態様は、ネットワークの異なるノードにより識別できる伝送コストが変動的である、あるいは全体的に整合性が不十分である、あるいは不整合であるに関わらず、メッセージを安定してルーティングするものである。ネットワークノード間でメッセージをルーティングする伝送コストは、ノードのオペレータあるいはＭＴＡに第三者から提供されることが多い。しかし、特に時間内のある一時点で、２つのノードが同一の伝送コスト情報を備えていないことも多い。したがって、受信者ノードが、ターゲットノードまでの異なるパスが、送信ノードが判断するパスよりもより短い、すなわち、よりコストが小さいことを判断してもよい。例えば、送信ノードＡが、ターゲットノードＤまでの最小伝送コストの経路で、ＡからＢ、Ｃそして最終Ｄまでメッセージを送信すべきであると判断する。伝送コストは合意されないこともたまにあるので、ノードＣがＤまでの最短パスで、最初にＢまでメッセージを返送すべきであるとのコスト情報を有してもよい。したがって、メッセージがノードＢとノードＣとの間を往復する時に、循環する問題が生じる可能性がある。
【００２６】
本発明は、ノードが伝送コストに合意するまでメッセージの送信を遅延させるのではなく、ターゲットノードまでのパス上でファイルが通過するノード数を管理、追跡するものである。例えば、電子メール文書では、送信者ノードからターゲットノードまでのパス上でファイルが通過するノードは、ＳＭＴＰヘッダあるいは他のシステムの他の機能に加えられる。例えば、Ｘ．４００はこの目的のためにエンベロープ（Ｅｎｖｅｌｏｐｅ）の考えを利用したものである。したがって、ターゲットノードまでのパス上でファイルが通過するノード数が最小閾値を超える場合、ノードはある期間（整定期間）、更なる伝送を休止し、伝送コストを承認してネットワーク全体を安定する。整定期間が過ぎると、最短パス（最小伝送コスト）に従って、ターゲットノードへのメッセージの伝送を試みる。そして、ファイルが通過するノード数の監視を継続する。整定期間が経過した後に伝送コストが安定すれば、ファイルは受信者が受信するターゲットノードに首尾よく送信される。しかし、伝送コストがまだ安定せず、ファイルの循環が続けば、ターゲットノードまでのパス上でファイルが通過するノード数が最大閾値に達する時、ファイルの循環は終了する。最大閾値に達する場合、該ファイルは配信不能ファイルとして記録され、及び／または、配信不能レポートがファイルに添付されて送信者に返送される。
【００２７】
一実施態様では、最小閾値は１０個以上のノードである。他の実施態様では、最小閾値は１０個から１５個のノードである。
【００２８】
一実施態様では、整定期間は１時間以下である。他の実施態様では、整定期間は３０分以下で、さらに他の実施態様では、１５分以下である。
【００２９】
一実施態様では、最大閾値は２０個以上のノードである。他の実施態様では、最大閾値は２５個から３５個のノードである。
【００３０】
一実施態様では、本発明のコンピュータネットワークは、インターネットに接続されたノードを備える。他の実施態様では、本発明のコンピュータネットワークは、複数の国にまたがる企業あるいは大学のネットワークである。他の実施態様では、本発明のコンピュータネットワークは、複数の州にまたがる企業あるいは大学のネットワークである。他の実施態様では、本発明のコンピュータネットワークは、複数の都市にまたがる企業あるいは大学のネットワークである。また他の実施態様では、本発明のコンピュータネットワークは、一都市、一企業あるいは一大学のキャンパスの複数の建物にまたがる企業あるいは大学のネットワークである。
【００３１】
コストが完全に安定するまでメッセージの送信を遅延させるのではなく、ファイルが通過するノード数を監視あるいは追跡することで、ネットワーク全体で小さい伝送コストのばらつきがあるイベント時に、遅延なしに受信者にメッセージを伝送する、より安定したルーティングシステムおよび方法となる。したがって、本発明のシステムおよび方法は、全ノードがコストに合意するまでメッセージの伝送を遅延させないで、むしろターゲットノードにより近いノードにファイルを伝送する。上述したように、ノードは、より遠隔のノードよりも、近接近したノードに関してより有利な伝送コスト情報およびネットワーク状態情報を有する。したがって、ターゲットノードにより近いノードにメッセージを伝送することにより、ファイルは遅延されず、ターゲットノードにより近いノードは、より的確なコストおよびネットワーク状態情報を有し、首尾よくターゲットノードにファイルを伝送できる可能性が高い。
【００３２】
次に図２は、本発明の一実施態様の例示的プロセスを示すフローチャートである。このプロセスでネットワークを介して伝達されるメッセージが１人もしくは複数の受信者へ伝送される。フローチャートは、あるノード（以下、「カレントノード」と呼ぶ）により実行されるプロセスを示している。２０２において、カレントノードが、そのカレントノード以外の１または複数のターゲットノードに存在する１人または複数の受信者に送信されるべきメッセージを、受信する。このカレントノードは、メッセージを送信するオリジナルノードであるか、もしくは最初の送信ノードとターゲットノードとの間のネットワークに接続された中間ノードである。
【００３３】
２０３において、ネットワーク上の最小コストパスとノードの分岐点を計算する。これらの方法は当技術分野周知であり、任意の特定の計算に限定されない。システム構成における変化の監視を継続し、システム構成が変化した時に、最小コストパスと分岐点を再計算する。
【００３４】
２０４において、メッセージがＭＩＮ数のノードに転送されたか否かを判断する。ＭＩＮは、所定の最小閾値の数である。送信された宛先のノード数が最小閾値数を超える場合、２０６においてファイルを所定整定期間（Ｓｅｔｔｌｉｎｇ  Ｐｅｒｉｏｄ）保留しておき、伝送コストを安定させる。
【００３５】
２０８において、メッセージがＭＡＸ数のノードに転送されたか否かを判断する。ＭＡＸは、所定の最大閾値の数である。送信された宛先のノード数が最大閾値数に等しい場合、２１０においてファイルを送信者に返送し、配信不能ファイルとして記録する。一実施態様では、さらにファイルの配信失敗を記述する配信不能レポートを送信者に提供する。
【００３６】
２１２において、カレントノードが宛先テーブル（Ｄｅｓｔｉｎａｔｉｏｎ  Ｔａｂｌｅ）を構築する。宛先テーブルは、ネットワークに存在するノードへのメッセージ送信に関連付けられた伝送コストを識別する。宛先代替テーブル（Ｄｅｓｔｉｎａｔｉｏｎ  Ａｌｔｅｒｎａｔｉｖｅ  Ｔａｂｌｅ）は、さらにネットワーク上のノードを優先順位付けする。この優先順位付けは、カレントノードからそのノードへのメッセージ伝送に関連付けられた最小伝送コストに基づく。２１４において、単一ノードに存在する１人または複数の受信者にメッセージを送信すべきか否か、あるいは２個以上のノードに存在する２人以上の受信者にファイルを送信すべきか否かを判断する。
【００３７】
単一ノードに存在する１人または複数の受信者にメッセージを送信すべきであると判断した場合、２１６において宛先ノードへ送信するためにメッセージをキューに加える。
【００３８】
２１８において、接続マネージャのアルゴリズムが、メールを宛先ノードに送信すべきであると判断する。接続マネージャのアルゴリズムは、最初に２２０において、メッセージ上にて識別されたターゲットノードに直接メッセージを伝送するよう試みる。直接接続がないため、もしくはターゲットノードが何らかの理由（例えば、コンポーネント障害、帯域幅制限、ネットワーク障害、構成エラー、低レベルのシステムポリシーなど）でファイルを受領できないためにファイルがターゲットノードに直接送信されない場合には、カレントノードがまだ試みていない、宛先代替テーブル内で識別された最高優先順位のノードにファイルを送信する。２２２において、Ｘ回数内でファイルが宛先ノードへ首尾よく伝送されるか否かを、カレントノードが判断する。ここで、Ｘはカレントノードが伝送を試みる所定回数である。あるいは、伝送を試みる所定回数以外に、Ｘはメッセージを送信しなければならない所定制限時間を含んでもよい。ファイルが宛先ノードに首尾よく伝送される場合、カレントノードの責任は果たされ、プロセスは終了する。
【００３９】
２２２において、Ｘ回数内でファイルが宛先ノードへ首尾よく伝送されなかった（あるいはＸ制限時間が経過した）とカレントノードが判断する場合、２２４において、カレントノードは、宛先代替テーブル内の識別された全ての宛先ノードへメールを伝送する試みがなされたか否かを判断する。識別された全ての宛先ノードへの伝送が試みられなかった場合、２２０において、カレントノードは、まだ試みていない最高優先順位のノードへメッセージの送信を試みる。識別された全ての宛先ノードへの配信が試みられた場合、２２６において、カレントノードは、全ノードへの配信がＹ回試みられたか否かを判断する。ここで、Ｙはカレントノードが伝送を試みる所定回数である。あるいは、伝送を試みる所定回数以外に、Ｙはメッセージを送信しなければならない所定制限時間を含んでもよい。カレントノードがＹ回配信を試みなかった場合（あるいは、Ｙ制限時間を超えた場合）、２２８において特定時間の間、メッセージを保留しておき、ネットワークを復興させる。指定時間が経過した後、２１８において、接続マネージャが再度、メールを宛先ノードに送信すべきかを判断する。
【００４０】
カレントノードがＹ回配信を試みた場合、あるいはカレントノードがメッセージを配信しなければならない所定制限時間を超えた場合、２３０において、カレントノードは、メッセージが分岐点の共通ノードを有する複数の宛先に宛てたものであるか否かを判断する。そうであれば、２３２において、ファイルは、分岐点のノード以外の個々の宛先に対して再キューイングされ、２１６においてキューに加えられる。
【００４１】
２３０において、メッセージが単一ターゲットノードに存在する１人または複数の受信者に宛てたものであることをカレントノードが判断する場合、２１０において、ファイルは送信者に返送され、配信不能ファイルとして記録される。一実施態様では、さらにそのファイルに関して配信失敗を記述する配信不能レポートを送信者に提供する。
【００４２】
２１４において、メッセージが２つ以上のターゲットノードに存在する複数の受信者に宛てたものであるとカレントノードが判断する場合、２３４において、カレントノードをルートとする最小スパニングツリー（Ｍｉｎｉｍａｌ  Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ）を作成する。一実施態様では、最小スパニングツリーは予め計算され、複数の異なるメッセージを送信するのに使用される。２３６において、スパニングツリーローカルパーティションテーブル（Ｓｐａｎｎｉｎｇ  Ｔｒｅｅ  Ｌｏｃａｌ  Ｐａｒｔｉｔｉｏｎ  Ｔａｂｌｅ）を作成する。ネットワークに関する最小コストスパニングツリーをエンコードするのが、最小スパニングツリーである。最小スパニングツリーは、分岐点を見つけるのに使用される。最小スパニングツリーおよびスパニングツリーローカルパーティションテーブルを利用して、２３８において、カレントノードは受信者の分岐点の最終ノードを識別する。２４０において、カレントノードが受信者の分岐点の最終ノードであると判断された場合、２４２において、メッセージは受信者のターゲットノードまで分岐され、２１６においてメッセージはキューに置かれる。
【００４３】
カレントノードが分岐点のノードでない場合、２４４において、各グループの分岐点の最終ノードに従って受信宛先ノードをグループ化し、２１６においてグループ化された宛先をキューに置く。
【００４４】
本発明の一実施態様では、図２で説明したように、分岐点の最終ノードは利用可能でなくてもよいし、そこへの送信を試みるメッセージを受領できなくてもよい。そのような場合、本発明はカレントノードでメッセージを分岐させ、追加の伝送コストおよび帯域幅を使って、確実に受信者にメッセージを首尾よく送信するようにする。したがって、分岐点の最終ノードまでファイルの分岐を遅延させる方法でメッセージの最初の送信を試みるが、一方で、分岐を遅延させることによって、むしろファイルの配信が遅延し、ファイルが配信不能になる場合には、本システムおよび方法は、代わりにメッセージをもっと早くに分岐させて、受信者にファイルを伝送する。一般には、受信者がメッセージを受信する方が、分岐点の最終ノードでファイルを遅延させたり分岐させたりすることに関連付けられた追加の伝送コストや帯域幅を節約するよりも、有益だと考えられるので、ファイルをもっと早くに分岐させる。この例を図１で説明する。カレントノードはノード１０６（ニューヨーク）で、メッセージをノード１１０（ロンドン）への転送を試みている。ノード１１０（ロンドン）は、ノード１０８（グリニッチ）およびノード１１２（パリ）に存在する受信者までの分岐点の最終ノードである。ノード１０６（ニューヨーク）がノード１１０（ロンドン）へメッセージを転送できない場合、２３０でメッセージ受信者を分岐させ、キューに２つメッセージを置く。ここで１つのメッセージはノード１０８（グリニッチ）へ、他方のメッセージはノード１１２（パリ）へ伝送される。したがって、伝送コストが１２０から１８０に増加するが、メッセージを遅延させないで、あるいは送信者に配信不能ファイルとしてファイルを返送しないで、ノード１０８（グリニッチ）およびノード１１２（パリ）の受信者ノードへ直接ファイルを送信する。
【００４５】
他の実施態様は、本システムおよび方法は、最近失敗した全接続のキャッシュを保持する。他の実施態様では、本システムおよび方法は、そこを通過した隣接ノードによりグループ化された、最近失敗した全接続のキャッシュを保持する。これらの実施態様は、最近失敗したノードへのメッセージの伝送の試みを回避し、それによりファイルの伝送の遅延を回避するのに利用される。一実施態様では、所定時間内で発生した接続失敗に関して、キャッシュを保持する。一実施態様では、該時間は直近の６時間である。他の実施態様では、直近の１時間以内に発生した接続失敗に関して、キャッシュを保持する。他の実施態様は、直近の３０分以内に発生した接続失敗に関して、キャッシュを保持する。
【００４６】
一実施態様では、代替ノードへの接続を１つずつ開始しないで、複数の代替ノードへのメッセージの一斉伝送を試みる。この実施態様では、最終ターゲットに最も近く、所定時間内、例えば１秒以内で成功するノードを選択する。所定時間内で成功するノードが無ければ、最初に首尾よくメッセージを受領するノードを使用する。それでも成功するノードが無ければ、より長い所定時間にしてもよい。
【００４７】
一実施態様では、現在の接続が「遅い」、すなわちバイト／秒が平均よりもかなり小さい場合、「より近い」ノードへの接続の開始を試みて、２番目のメッセージを伝送する。「より近い」ノードのスピードが「普通」であるか、あるいは「普通」より速い場合、「より近い」ノードを容認して、「遅い」ノードへのメッセージ送信は中止するべきである。
【００４８】
図３は、コンピュータ１３０の形で、汎用コンピューティングデバイスの一例を示す。本発明の一実施態様では、コンピュータ１３０などのコンピュータは、本明細書内の他の図で例示および説明するのに好適である。コンピュータ１３０は、１または複数のプロセッサ、あるいは処理ユニット１３２、およびシステムメモリ１３４を有する。図示した実施態様では、システムバス１３６は、システムメモリ１３４を含むさまざまなシステムコンポーネントをプロセッサ１３２に結合させる。バス１３６は、メモリバス、メモリコントローラ、周辺バス、加速グラフィックス・ポート（ＡＧＰ）を含む数種類のバス構造のうちのいずれかの１つまたは複数、およびプロセッサ、あるいは任意のさまざまなバス構成を使用するローカルバスを示す。例として、バス構成には、業界標準アーキテクチャ（ＩＳＡ）バス、マイクロチャネル・アーキテクチャ（ＭＣＡ）バス、エンハンストＩＳＡ（ＥＩＳＡ）バス、ビデオエレクトロニクス規格協会（ＶＥＳＡ）ローカルバス、メザニン（Ｍｅｚｚａｎｉｎｅ）・バスとしても知られる周辺コンポーネント相互接続（ＰＣＩ）バスなどがあるが、これらに限定されない。
【００４９】
コンピュータ１３０は、典型的に少なくともある種のコンピュータ可読媒体を有する。コンピュータ可読媒体は、揮発性および不揮発性媒体、取外式および固定式媒体を含み、コンピュータ１３０がアクセスできる利用可能ないずれの媒体であってもよい。例として、コンピュータ可読媒体には、コンピュータ記憶媒体および通信媒体があるが、これらに限定されない。コンピュータ記憶媒体には、揮発性および不揮発性媒体、取外式および固定式媒体などがある。コンピュータ記憶媒体は、コンピュータ可読命令、メッセージ構造、プログラムモジュール、あるいは他のメッセージなどの情報を格納する任意の方法および技術により実現される。例えば、コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、あるいは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、あるいは他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置、あるいは他の磁気記憶装置、あるいは所望の情報を格納するのに使用でき、コンピュータ１３０がアクセスできるその他の媒体がある。通信媒体は典型的に、コンピュータ可読命令、メッセージ構造、プログラムモジュール、あるいは他のメッセージを、搬送波あるいは他の搬送メカニズムなどの変調メッセージ信号で具現化し、任意の情報配信媒体を含む。当技術分野では、変調されたメッセージ信号は周知であり、該信号は１または複数の特性集合を有し、信号内に情報をエンコードする方式で変換される。有線ネットワークおよび直接有線接続などの有線媒体や、音響、ＲＦ、赤外線および他の無線媒体などの無線媒体は、通信媒体の例である。上述の任意の組み合わせも、コンピュータ可読媒体の範囲に含まれる。
【００５０】
システムメモリ１３４は、取外式および／または固定式メモリ、揮発性および／または不揮発性メモリの形のコンピュータ記憶媒体を含む。図示した実施態様では、システムメモリ１３４は、リード・オンリ・メモリ（ＲＯＭ）１３８およびランダム・アクセス・メモリ（ＲＡＭ）１４０を含む。基本入出力システム１４２（ＢＩＯＳ）は、スタートアップ期間などにコンピュータ１３０内の要素間で情報を転送するのを助ける基本ルーチンを含み、典型的にはＢＩＯＳはＲＯＭ１３８内に格納されている。ＲＡＭ１４０は、典型的にメッセージおよび／またはプログラムモジュールを含む。該モジュールは、処理ユニット１３２により、即座にアクセス可能および／または現在動作中のものである。例として、図３は、オペレーティングシステム１４４、アプリケーションプログラム１４６、他のプログラムモジュール１４８およびプログラムメッセージ１５０を示すが、これらに限定されない。
【００５１】
またコンピュータ１３０は、他の取外式および／または固定式、揮発性および／または不揮発性コンピュータ記憶媒体を含んでもよい。例えば、図３は、固定式で不揮発性の磁気媒体に対して読み出しおよび／または書き込みを行うハードディスクドライブ１５４を示す。また図３は、取外式で不揮発性の磁気ディスク１５８に対して読み出しおよび／または書き込みを行う磁気ディスクドライブ１５６、ＣＤ−ＲＯＭあるいは他の光媒体などの、取り出し可能で不揮発性の光ディスク１６２に対して読み出しおよび／書き込みを行う光ディスクドライブ１６０を示す。例示的なオペレーティング環境で使用してもよい、他の取外式／固定式な、揮発性／不揮発性のコンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタル多用途ディスク、デジタルビデオテープ、固体ＲＡＭ、固体ＲＯＭなどがあるが、これらに限定されない。ハードディスクドライブ１５４、磁気ディスクドライブ１５６および光ディスクドライブ１６０は典型的に、インターネット１６６などの不揮発性メモリインタフェースにより、システムバス１３６に接続されている。
【００５２】
図３で上述、および例示した、ドライブあるいは大容量記憶装置、およびその関連コンピュータ記憶媒体は、コンピュータ可読命令、メッセージ構造、プログラムモジュールおよび他のコンピュータ１３０のメッセージの記憶を提供する。例えば、図３において、ハードディスクドライブ１５４は、格納オペレーティングシステム１７０、アプリケーションプログラム１７２、他のプログラムモジュール１７４およびプログラムメッセージ１７６のように示されている。これらのコンポーネントは、オペレーティングシステム１４４、アプリケーションプログラム１４６、他のプログラムモジュール１４８およびプログラムメッセージ１５０と同一であっても、異なっていてもよいことに留意されたい。オペレーティングシステム１７０、アプリケーションプログラム１７２、他のプログラムモジュール１７４およびプログラムメッセージ１７６は、ここでは異なる番号を付けて、少なくとも異なるものであることを示している。
【００５３】
ユーザが、キーボード１８０およびポインティング装置１８２（例えば、マウス、トラックボール、ペンあるいはタッチパッド）などの入力装置あるいはユーザインタフェース選択装置を介して、コンピュータ１３０にコマンドおよび情報入力する。他の入力デバイス（図示せず）は、マイクロフォン、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナなどを含んでもよい。図示した入力装置および他の入力装置は、システムバス１３６に結合したユーザ入力インタフェース１８４を介して、処理ユニット１３２に接続するが、他のインタフェースおよび、パラレルポート、ゲームパッド、あるいはユニバーサルシリアルバス（ＵＳＢ）などのバス構造により接続してもよい。モニタ１８８あるいは他のタイプのディスプレイ装置も、ビデオインタフェース１９０などのインタフェースを介してシステムバス１３６に接続する。モニタ１８８に加え、コンピュータは、プリンタおよびスピーカなどの他の周辺出力装置（図示せず）を含むことが多く、出力周辺インタフェース（図示せず）を介して接続してもよい。
【００５４】
コンピュータ１３０は、遠隔コンピュータ１９４などの１または複数の遠隔コンピュータに対する論理接続を使用するネットワーク環境で動作してもよい。遠隔コンピュータ１９４は、パーソナルコンピュータ、サーバ、ルータ、ネットワークＰＣ、ピア装置あるいは他の共通ネットワークノードであってもよい。また典型的にコンピュータ１３０に関連して上述した多くの要素、あるいは全ての要素を含んでもよい。図３に表した論理接続は、ローカルエリアネットワーク（ＬＡＮ）１９６、広域ネットワーク（ＷＡＮ）１９８を含むが、他のネットワークを含んでもよい。ＬＡＮ１３６および／またはＷＡＮ１３８は有線ネットワーク、無線ネットワーク、これらの組み合わせなどであってもよい。該ネットワーキング環境は、オフィス、企業規模のコンピュータネットワーク、イントラネット、およびグローバルコンピュータネットワーク（例えば、インターネット）において、一般的である。
【００５５】
ローカルエリアネットワーキング環境で使用する時に、コンピュータ１３０は、ネットワークインタフェースあるいはアダプタ１８６を介してＬＡＮ１９６に接続する。広域ネットワーキング環境で使用する時は、コンピュータ１３０は典型的にモデム１７８あるいは、インターネットなどのＷＡＮ１９８を介する通信を確立する他の手段を含む。モデム１７８は、内付け型であってもあるいは外付け型であってもよく、ユーザ入力インタフェース１８４を介して、あるいは他の適切なメカニズムを介して、システムバス１３６に接続する。ネットワーク環境では、コンピュータ１３０に関連して表したプログラムモジュール、あるいはその一部は、遠隔メモリ記憶装置（図示せず）に格納してもよい。例として、図３は、メモリ装置に存在するものとして、遠隔アプリケーションプログラム１９２を示しているが、これに限定されない。表示したネットワーク接続は例示的であって、コンピュータ間の通信リンクを確立する他の手段を用いてもよい。
【００５６】
一般に、コンピュータ１３０のメッセージプロセッサは、コンピュータのさまざまなコンピュータ可読媒体に、それぞれ異なった時間に格納された命令によって、プログラミングされる。プログラムおよびオペレーティングシステムは、典型的に、例えば、フロッピーディスクあるいはＣＤ−ＲＯＭに分散される。そこから、プログラムおよびオペレーティングシステムはインストールされ、コンピュータの二次メモリにロードされる。そして実行時に、プログラムおよびオペレーティングシステムはコンピュータの一次電子メモリに、少なくとも部分的にロードされる。本明細書で説明した本発明が、上述の、および他のさまざまなタイプのコンピュータ可読記憶媒体を含むのは、マイクロプロセッサあるいは他のメッセージプロセッサに関連して後述するステップを実装する命令あるいはプログラムを、該媒体が含む場合である。さらに本発明には、本明細書で説明する方法および技術に従ってプログラミングされた時は、コンピュータ自身も含まれる。
【００５７】
説明のために、ここではオペレーティングシステムなどのプログラムおよび他の実行可能なプログラムコンポーネントは、別個のブロックとして示す。しかし、該プログラムおよびコンポーネントは、さまざまな時間に、コンピュータの異なる記憶コンポーネントに存在し、コンピュータのメッセージプロセッサ（１つまたは複数）により実行されることは理解される。
【００５８】
コンピュータ１３０を含む、例示的コンピューティング環境に関して説明するが、本発明は、多数の他の汎用あるいは特殊目的コンピューティングシステム環境あるいは構成において使用できる。コンピューティングシステム環境は、本発明の使用の範囲あるいは機能に関して何ら限定するものではない。さらに、コンピューティングシステム環境は、例示的オペレーティング環境において説明したコンポーネントのいずれか、あるいはその組み合わせに関して何か依存性を有する、あるいは要件を有すると解釈すべきではない。本発明での使用に適切であると思われる周知のコンピューティングシステム、環境および／または構成の例には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドあるいはラップトップ装置、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な家庭用電化製品、携帯電話、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上述のシステムおよび装置のいずれかを含む分散コンピューティング環境などがあるが、これらに限定されない。
【００５９】
本発明は、一般的なプログラムモジュールなどの、１または複数のコンピュータあるいは他の装置により実行されるコンピュータ実行可能命令に関連して、説明してもよい。一般に、プログラムモジュールは、ルーチン、プログラム、オブジェクト、コンポーネント、特定のタスクを実行する、あるいは特定の抽象的なメッセージタイプを実装するメッセージ構造を含むが、これらに限定されない。また本発明は、通信ネットワークを介してリンクされた遠隔プロセッシング装置によりタスクを実行する、分散コンピューティング環境で実施してもよい。分散コンピューティング環境では、プログラムモジュールは、メモリ記憶装置を含む、ローカルコンピュータ記憶媒体と遠隔コンピュータ記憶媒体の両方に配置してもよい。
【００６０】
ソフトウェアアーキテクチャとの関連から、インタフェースは、ソフトウェアモジュール、コンポーネント、コード部分、あるいは他のコンピュータ実行可能命令のシーケンスを含む。例えば、インタフェースは、第２モジュールにアクセスする第１モジュールを含み、第１モジュールの代わりにコンピューティングタスクを実行する。一例として、第１および第２モジュールは、オペレーティングシステムにより提供されるようなアプリケーションプログラミングインタフェース（ＡＰＩ）、コンポーネントオブジェクトモデル（ＣＯＭ）インタフェース（例えば、ピアツーピアアプリケーション通信用）、および拡張マークアップ言語メタメッセージ交換フォーマット（ＸＭＩ）インタフェース（例えば、ウェブサービス間通信用）を含む。
【００６１】
インタフェースはしっかりと結合され、Ｊａｖａ  ２  プラットフォームエンタープライズエディション（Ｊ２ＥＥ）、ＣＯＭ、分散ＣＯＭの例などの同期実装であってよい。代替として、もしくは同期実装に加えて、インタフェースは緩く結合し、ウェブサービス（例えば、簡易オブジェクトアクセスプロトコル）などの非同期実装であってよい。一般に、インタフェースは、しっかりと結合、緩く結合、同期的、非同期的のうちの特性の任意の組み合わせを含む。さらに、インタフェースは、標準プロトコル、専用プロトコル、あるいは標準プロトコルと専用プロトコルの任意の組み合わせに準拠してもよい。
【００６２】
本明細書で説明したインタフェースは、全て単一のインタフェースの一部であってもよく、あるいは、内部に別個のインタフェースとして、あるいは任意の組み合わせで実装してもよい。インタフェースは、ローカルにあるいは遠隔に実行して、機能性を提供してもよい。さらに、インタフェースは、追加の機能性を含んでもよいし、本明細書で図示、あるいは説明したものより少ない機能性を含んでもよい。
【００６３】
さらに、以下の実施例に従って、本発明を説明する。  
＜実施例−ネットワークを介する電子メールのルーティング＞
＜初期化＞
初期化中に、２つのメッセージ構造が計算される。該メッセージ構造は、プロセスを実行する間中、使用される。基礎となるメッセージが変化すると、該メッセージ構造は簡単に再計算され、その時点から先で使用される。
【００６４】
＜宛先代替テーブル＞
組織内のどのノードに関しても、現在のマシーンにより近い配信ノードが判断され、リストあるいはテーブル（宛先代替テーブル）に置かれる。リストは、問題のターゲットまでのそれぞれの最小伝送コストに従って、順序付けされる。これには、カレントノードとターゲットノードとの間の最小コストパス上のノードが全て含まれる。また、発信元からターゲットまでの他のパス上の他のノードも、ターゲットまでの最小コストがカレントノードから宛先ノードまでの伝送コストよりも小さければ、含まれる。結局、ターゲットまでのパス上のノードが含まれるのであって、カレントノードからターゲットまでのパス上のノードが含まれるということではない。ここで、距離は、ノード間つまりリンクブリッジ間で定義されたリンクコストに従う。
【００６５】
そのアルゴリズムがどのくらい包括的であるかは、ヒューリスティック判断である。より大きなセットを含むことで、システムが目標を達成するのに、できるだけ多くの代替ステップを試みることができる。これにより、成功する機会は増加するが、リンク障害が生じれば全体効率を低減させてしまう。より包括的であることで、基礎となるノードリンクレコードが、単なる基礎となるトポロジのモデルであり、物理ネットワークトポロジの各側面を表さない、という公算を説明することを可能にする。
【００６６】
＜最小スパニングツリー＞
最小スパニングツリーは、カレントノードをルートとするネットワークノード／リンクに対して計算される。さらに、スパニングツリーローカルパーティションテーブルを構築する。各宛先Ｄに関して、次ホップ（カレントノードからターゲットＤまでの最小スパニングツリーのパスにある最初の隣接ノードＮ）を判断する。
【００６７】
＜不整合な全体メッセージの処理＞
アルゴリズムが、ネットワークノード／リンクメッセージが全体的に不整合であると仮定する。実際に、これは事実であることが多い。メッセージが積極的に複製されるため、そしてオペレータの制御のみの下で徐々にメッセージが変化するためである。しかし、複製レイテンシにより、事実であるとは言えなくなる。
【００６８】
本システムは、例えば、ＳＭＴＰ  Ｒｅｃｅｉｖｅｄ：ヘッダを使用して、メッセージがノードからノードへ転送された回数を追跡する。転送回数が第１閾値を越える場合、複製を安定する機会が与えられ、メールは遅延する。転送回数が最大閾値を越える場合、本システムは中断すべきであると見なされ、メールは配信不能レポート（ＮＤＲ）などの配信失敗に関する情報と共に送信者に返送される。
【００６９】
本アルゴリズムの利点は、離れたノードに関するわずかな情報を必要とすることである。結果として、全体ノード／リンクメッセージの不整合性による影響が少ない。
【００７０】
＜単一宛先の場合＞
単一宛先の場合、メールは個別の受信者のアドレスにルーティングされる。受信者が１人だけなので、複数のノードにおける受信者の拡散（fan-out）の問題の心配がない。ルーティングは、メールがもともと個別の受信者に宛てたものなので発生する場合もあれば、あるいは、メールがもともと複数の受信者に宛てたもので、メールが拡散したので発生する場合もある。
【００７１】
ルーティング時に、メッセージを宛先ノードへの配信のためのキューに置く。
【００７２】
中継時に（本システムが、ローカルマシーンから遠隔マシーンへメールを移動させたい時）、接続マネージャアルゴリズムが、メールを宛先Ｔに中継すべきであるかを判断する。
【００７３】
まずメールを受信者のノードの宛先に伝送するよう試みる。宛先ノードへの伝送が失敗した場合、次に宛先代替テーブル内の全ての代替中間ノードに対する最小の転送コストに応じて、メールを伝送するよう試みる。この追加の転送の試みは、中間ノードと宛先ノードとの間の最小転送コストの優先順位に従って行われる。この追加の試みは、宛先そのものに到達できない場合に、宛先に最も近いノードへメールを移動させる効果がある。
【００７４】
宛先に到達できない場合、ＴＣＰが、所定時間内に接続が行われるかを判断することになる。例えば、接続が２０秒間で行われず、各サイトが平均して２つのブリッジヘッドを有し、ネットワーク直径は１０以下である場合、全ての代替サイトを試みるのに４００秒、あるいは７分のレイテンシが必要になる。これは、最近試みて失敗した（例えば、最後の３０分での失敗）接続のキャッシュを保持し、それらのサイトに接続を試みないことで、さらに最適化することができる。
【００７５】
接続が行われない場合、単一宛先の場合では、後刻にネットワークが回復されることを見込んで、メッセージのキューを保留しておき、後でキューへの伝送を試みる。
【００７６】
＜複数宛先の場合＞
いくつかの場合では、メールは、異なるノードに存在する２人以上の受信者に宛てられる。この場合、ネットワークトラフィックの最適方法は、本システムが開始する時に計算された最小スパニングツリー内のリンクにわたりメールを中継することである。
【００７７】
メール受信者は、受信者ノードまでのパスが最初に分岐する最終ノードに応じて、グループ化される。このノードは、宛先代替テーブルにおいて最高優先順位（例えば、分岐ノードと宛先ノードとの間の最小コスト）を有する分岐ノードである。メッセージの分岐は、分岐ノードで行われ、メールは、該パスをたどる受信者に対する分岐ノードのキューに置かれる。メッセージは、２人の受信者がカレントノードにおいて唯一並行であるパスを有する場合に分岐されなければならない。できる限りメッセージの分岐を遅延させるのが有利であるので、受信者が３人とすると、メールは追加の分岐を回避するために、より近い「次ホップ」に伝送される。
【００７８】
ノードは、初期化の項で説明したスパニングツリーローカルパーティションテーブルを使用して、効率的に計算される。パーティションテーブルを使用して、メールの受信者は、受信者の宛先までの最小スパニングツリー内の次ホップに応じてグループ化される。メッセージの分岐は、メッセージのグループのそれぞれに対して行われる。メールは、カレントノードからターゲットノードまでの最小スパニングツリー内のパスに現れるノード、つまりカレントノードから最も遠いノード（すなわち、宛先ノード（１つまたは複数）までの最小コストを有するノード）に対してキューイングされる。
【００７９】
メールがキューイングされると、上述の単一宛先の場合で説明したように、伝送が進む。
【００８０】
接続が２つ以上のターゲットに対する分岐ノード代替案のいずれにも行われない場合、メッセージの分岐はカレントノードで行われ、メールは分岐により現れる新規ターゲットにキューングされる。このように、ノードが利用不可能である場合、メッセージをカレントノードで分岐して、メールが配信される機会をより増加させることができる。これは、ノードが利用不可能である場合、効率を低減させるが、メールのいくつか、あるいは全てを首尾よく伝送させることができる。
【００８１】
本明細書で図示および説明した方法の実行あるいはパフォーマンスの順序は、特に別の指定がなければ、必須ではない。すなわち、特に別の指定がなければ、本方法の要素は任意の順序で実施してもよい。しかも本方法は、本明細書で説明した要素より多い、あるいは少ない要素を含んでもよい。例えば、特定の要素を実行あるいは実施するのは、他の要素より前、他の要素と同時、あるいは他の要素の後であっても、本発明の範囲内であると考えられる。
【００８２】
本発明の要素、あるいは本発明の実施態様を導入する場合、項目の「１つの（ａ、ａｎ）」「その（ｔｈｅ）」「前記（ｓａｉｄ）」は、１または複数の要素を意味するものである。「備える（ｃｏｍｐｒｉｓｉｎｇ）」「含む（ｉｎｃｌｕｄｉｎｇ）」「有する（ｈａｖｉｎｇ）」は、挙げた要素以外に追加の要素があってもよいことを含み、意味するものである。
【００８３】
以上の点から、本発明のいくつかの目的が達成され、他の利点が得られることが理解されよう。
【００８４】
上述の構造、製品および方法は、本発明の範囲を逸脱しなければ、さまざまな変形もありうる。上述の説明に含まれ、添付図面に示した全ての内容は、例示的なものであって、限定するものではないと解釈されるべきである。
【図面の簡単な説明】
【００８５】
【図１】複数のノードのネットワークおよびメッセージルーティグネットワークにおけるノード間のリンクを例示的に説明する図である。
【図２Ａ】ネットワークを介して伝達されるメッセージが、１人または複数の受信者に伝送される、本発明の一態様の例示的プロセスを示すフローチャートである。
【図２Ｂ】ネットワークを介して伝達されるメッセージが、１人または複数の受信者に伝送される、本発明の一態様の例示的プロセスを示すフローチャートである。
【図３】本発明を実装できる適切なコンピューティングシステム環境の一例を示すブロック図である。
【図１】
2008546276.tif 000003
【図２Ａ】
2008546276.tif 000004
【図２Ｂ】
2008546276.tif 000005
【図３】
2008546276.tif 000006