インターネットの設計に関する研究
信頼性の高い大規模ネットワーク設計法
情報通信ネットワークは,需要状況に応じて,コストを抑制しつつ必要な信頼性や通信品質を満たすものとして設計されなければならない.しかし,イン ターネット時代では,考慮すべき制約条件や目的が多種多様なものとなっており,新たな設計問題が次から次へと現れている.情報通信ネットワークを適切に設 計するためには,様々な最適化問題を扱う必要がある.これらは統一的な方法で解くことはできず,個別に高性能なアルゴリズムを考えなければならない.研究 室では,設計問題の適切な定式化,その数理的な性質の解明,高性能アルゴリズムの設計と性能評価を通して,実際のネットワーク設計に適用できる設計法につ いて研究開発している.
例えば,一部のリンクやノードの信頼性を高めることにより,ネットワーク全体の信頼性を効率よく高めることができる.これは,一般にネットワークの トポロジにおける脆弱な箇所だけを集中的に守るというイメージである.これは,最適化問題として定式化できる.様々なバリエーションが考えられるが,それ らに対して理論的な性質の解明だけでなく,高性能アルゴリズムの設計も行ってきた.
オーバレイネットワークの設計とQoSルーティング
オーバーレイネットワークを用いた通信において,特定のノードに負荷が集中するという問題がある.この問題を回避し,さらに信頼性を高めるためのオーバーレイネットワーク設計法,オーバーレイネットワーク上の通信経路設計法などを,分散システムの観点から研究している.
<主な外部発表成果>
N. Maeda, H. Miwa, “Detecting Critical Links for Keeping Shortest Distance from Clients to Servers during Failures,” Proc. SAINT2012, Izmir, Turkey, Jul.16-20, 2012.
N. Katayama, T. Fujimura, H. Miwa, N. Kamiyama, T. Hasegawa, H. Yoshino, “Network Design Methods for Minimizing Number of Links Added to a Network to Alleviate Performance Degradation following a Link Failure,” IEICE Trans. Fundamentals, Vol.E94-B(6), pp.1630-1639, 2011.
A. Noguchi, T. Fujimura, H. Miwa, “Network Design Method by Link Protection for Network Load Alleviation Against Failures,” Proc. IEEE INCoS, pp.581-586, Fukuoka, Japan, Nov.30-Dec.2, 2011.
K. Imagawa, T. Fujimura, H. Miwa, “Approximation Algorithms for Finding Protected Links to Keep Small Diameter Against Link Failures,” Proc. IEEE INCoS, 575 – 580, Fukuoka, Japan, Nov.30-Dec.2, 2011.
R. Nakamura, H. Miwa, “Method of Locating Mirror Servers to Alleviate Load on Servers and Links,” Proc. SAINT2011, pp.513-518, Munich, Germany, Jul.18-22, 2011.
T. Fujimura and H. Miwa, “Critical links detection to maintain small diameter against link failures,” Proc. International Conference on Intelligent Networking and Collaborative Systems , pp.339-343, Thessaloniki, Greece, Nov.24-26, 2010.
N. Katayama, T. Fujimura, H. Miwa, N. Kamiyama, H. Hasegawa, H. Yoshino, “Design method of smallest robust networks against performance deterioration during failures,” Proc. International Conference on Intelligent Networking and Collaborative Systems, pp.386-391, Thessaloniki, Greece, Nov.24-26, 2010.
R. Nakamura, A. Hashimoto, H. Miwa, “Methods of locating mirror servers with high connectivity and small distances,” Proc. International Conference on Intelligent Networking and Collaborative Systems, pp.353-356, Barcelona, Spain, Nov. 4-6, 2009.
N. Katayama, T. Fujimura, H. Miwa, N. Kamiyama, H. Hasegawa, H. Yoshino, “Design method of robust networks against performance deterioration during failures,” Proc. IEEE Globecom2009, Honolulu, Hawaii, U.S.A., Nov.30,-Dec.4, 2009.
R. Amano, H. Miwa, A reliable and effcient routing and spare capacity allocation method for backup paths, The 22nd European Conference on Operational Research EURO XXII, MC-23-1, Prague, Czech, Jul.8-11, 2007.
H. Miwa, H. Ito, “NA-Edge-Connectivity Augmentation Problems by Adding Edges,” Journal of the Operations Research Society of Japan, Vol. 47, No. 4, pp. 224-243, Dec., 2004.
インターネットの制御に関する研究
負荷分散を目的としたリンクメトリック決定法
ネットワーク上の負荷を軽減させるために,リンクに割り振られた値(メトリック)を変更することにより,適切な経路選択をするような制御アルゴリズムを研究している.
コンテンツ指向ネットワーク制御
コンテンツのキャッシュ配置場所情報を利用しながら,サーバへのアクセス負荷の軽減や通信遅延を抑制する制御法を研究している.
P2Pネットワークにおけるオーバーレイネットワーク構成
ネットワーク上に仮想的に構成されるオーバーレイネットワークと呼ばれるものの制御方式について研究開発している.これは,P2P(Peer- to- Peer)通信の技術基盤の一つでもある.本研究室では,グラフ理論の知見を利用し,性能の高いオーバーレイネットワーク制御アルゴリズムを研究してい る.
サーバ負荷分散ルーティング制御技術
サーバへのアクセス負荷の軽減や通信遅延の抑制のために,複数のミラーサーバをネットワーク上に配置し,サーバへのアクセスを適切に振り分ける制御アルゴリズムを研究している.
<主な外部発表成果>
A. Noguchi, T. Fujimura, H. Miwa, “Traffic engineering by polynomially solvable link metric optimization,” Proc. International Conference on Intelligent Networking and Collaborative Systems, pp.259-260, Barcelona, Spain, Nov. 4-6, 2009.
Y. Hanazawa, Y. Sasaki, H. Miwa, “Efficient degree constrained broadcast method on P2P networks,” Proc. International Conference on Intelligent Networking and Collaborative Systems, pp.347-352, Baecelona, Spain, Nov. 4-6, 2009.
Y. Sasaki, H. Miwa, “A control method of a P2P network with small degree and diameter,” Proc. 7th International Conference on Hybrid Intelligent Systems (HIS 2007), pp.253-258, Kaiserlautern, Germany, Sep. 17-19, 2007.
インターネットの性能評価に関する研究
サンプリングに基づくフロー統計推定法
インターネット上を流れるデータは膨大であり,その状況をすべてモニタリングすることは非現実的である.しかし,通信品質を高めるためには,ネット ワークの状況を把握することが必要不可欠である.本研究室では,通信のある種の統計情報をサンプリングという方法によって推定する方法について研究してい る.
<主な外部発表成果>
H. Hashimoto, M. Uchida, H. Miwa, An algorithm for estimating flow size distribution by packet sampling, The 22nd European Conference on Operational Research EURO XXII, TC-39-3, Prague, Czech, Jul.8-11, 2007.
橋本, 内田, 巳波, サンプリングに基づくフローサイズ分布推定法, 信学技報, vol. 106, no. 578, IN2006-265, pp. 507-512, 2007.