大規模分散ネットワーク網における効率の良い情報通信技法に関する研究

大规模分布式网络中高效信息通信技术研究

• 批准号: 12780234
• 负责人: 宮野 英次
• 金额: $ 1.34万
• 依托单位: Kyushu Institute of Technology (2001)九州芸術工科大学 (2000)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-12780234/
• 关键词: メッシュネットワーク網; パケット通信; ラウティングンアルゴリズム; 無情報ラウティング; 送信制御方式; 近傍情報; バス通信; ラウティングアルゴリズム

並列・分散ネットワーク環境での最も基本的な要求は,データパケットを目的のノードまで正しく,高速に伝達することである.本研究の目標は,2次元メッシュ網,3次元メッシュ網,ハイパーキューブ網,そのような規則正しい構造を部分構造として持つような大規模ネットワーク網を対象にして,効率の良いパケット移動経路選択アルゴリズム(ラウティングアルゴリズム)の設計とその実用化技術の開発を行うことであり,以下のような結果を得た.1.3次元メッシュ結合網の直径がΩ(N^<1/3>)であるにも関わらず,単純な経路選択アルゴリズムでは,少なくとも0(N^<2/3>)のラウティング時間を必要とすることを示した.この結果は,Journal of Algorithmsにおいて公表した.2.無情報ラウティングに対して,送信制御無情報方式の有効性について検証した.2次元メッシュ結合網におけるラウティングに対して,それぞれのノードが一度に保持できるパケットのサイズを定数にした場合の0(N^<3/4>)時間のアルゴリズムを示した.また,3次元メッシュネットワーク網に対して,1.16N^<1/2>+o(N^<1/2>)時間の上限を示した.この結果は,Journal of Graph Algorithms and Applicationsにおいて公表した.3.送信制御無情報方式の改善を行った.2次元メッシュ結合網上で,各ノードの近傍情報用いることにより,最適な0(N^<1/2>)時間のラウティングアルゴリズムを開発した.この結果をJournal of Algorithmsにおいて公表した.4.2次元メッシュバス通信網上でのラウティングに関しては,送信制御の際に確率を利用することが有効であることを示し,Theoretical Computer Scienceにおいて公表した.

Juxtapose and disperse the environment, the most basic requirements, and the purpose of the environment.ドまで正しく,HIGHWAY 伝达することである. The target of this study, 2D メッシュ网, 3 times元メッシュ网, ハイパーキューブ网, そのようなrules positive structure をpart structure としてholdつようなLarge-scale ネットワーク网を対 resembles にして, efficient の好いパケットmobile 経路选択アルゴリズム(ラウティングアルゴリズム)のDesign and Application of Chemical Technologyの开発を行うことであり, the following のような results are obtained. 1.3-dimensional メッシュ combined network diameter がΩ (N^<1/3> )であるにも关わらず,単正な経路选択アルゴリズムでは,小なくとも0(N^<2 /3>) のラウティングtimeを必とすることをshowした.このRESULTは,Journal of Algorithms において公典 した.2. No information ラウティングに対して, the effectiveness of the message control method without information について検证した.2D メッシュcombination network におけるラウティングに対して,それぞれのノードが once, keep it, できるパケットのサイズをdetermined number にしたoccasion 0(N^<3/4>) time のアルゴリズムをshow した.また, 3-dimensional メッシュネットワーク网に対して,1.16N^<1/2>+o(N^<1/2>) Timeの Upper limitをshowした.このRESULTは,Journal of Graph Algorithms and Applicationsにおいてpublic tableした.3. Improvement of the method of sending messages without information. 2-dimensional information combined with the Internet, each method Nearby information uses いることにより, optimal 0(N^<1/2>) time のラウティングアルゴリズムを开発した.このRESULTSJournal of Algorithmsにおいて公表した.4.2 Dimensional Communication Network でのラウティングにTheoretical Computer Scienceにおいて公报した.

项目成果

Iwama, Kazuo: "New bounds for oblivious mesh routing"Journal of Graph Algorithms and Applications. 5・5. 17-38 (2001)

Iwama，Kazuo：“遗忘网格路由的新界限”图算法与应用杂志 5・5（2001 年）。

Iwama,Kazuo: "A (2.954+ε) n oblivious routing algorithms on 2D meshes"Proceedings of 12^<th> ACM Symposium on Parallel Algorithms and Architectures (SPAA2000). 186-195 (2000)

Iwama, Kazuo：“2D 网格上的 (2.954+ε) n 不经意路由算法”第 12 届 ACM 并行算法和架构研讨会论文集 (SPAA2000) (SPAA2000)。

Iwama, Kazuo: "Efficient randomized routing algorithms on the two-dimensional mesh of buses"Theoretical Computer Science. 261・2. 227-239 (2001)

Iwama，Kazuo：“总线二维网格上的高效随机路由算法”理论计算机科学 261・2（2001）。

Iwama,Kazuo: "A lower bound for elementary oblivious routing on three-dimensional meshes"Journal of Algorithms. (発表予定).

Iwama，Kazuo：“三维网格上基本不经意路由的下界”算法杂志（待出版）。

Iwama, Kazuo: "A lower bound for elementary oblivious routing on three dimensional meshes"Journal of Algorithms. 39・2. 145-161 (2001)

Iwama，Kazuo：“三维网格上的基本不经意路由的下界”算法杂志 39・2（2001）。