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

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

• 批准号: 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において公表した.

At the same time, the most basic requirements for the environment are listed. The purpose is to achieve high-speed and high-speed performance. The goal of this study is to create a partial model that supports the large size model of the computer network. In order to improve the performance of the system, the following experimental results have been obtained. 1.3 the combination of the diameter factor Ω (N^ & lt) If you want to make sure that you don't need to make sure that you don't need to do so, please check that you need to make sure that you do not need to do so. The results show that Journal of Algorithms is responsible for the public table. 2. There is no intention to send a message, and the message system has a message system. 2 times the combination of the message system and the message system, you can keep the message number in the 0 (N ^ & lt;3/4>) time frame. Online, 3-dimensional online networking, 1.16N ^ & lt;1/2>+o (N^ & lt;1/2>) time limit display. The results show that Journal of Graph Algorithms and Applications is responsible for the public table. 3. The information delivery system improves the performance of the system. The two-dimensional message system is combined with the previous one, and each customer is used for information sharing, and the most recent 0 (N^ & lt;1/2>) time is available to ensure that the system is open. The results show that the Journal of Algorithms message is open in the public table. 4.2 on the meta-communication network, the sending system ensures that the rate of confirmation is displayed in the public table, and the Theoretical Computer Science message is displayed in the public table.

项目成果

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）。