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

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

基本信息

批准号：
12780234
负责人：
宮野英次
金额：
$ 1.34万
依托单位：
Kyushu Institute of Technology (2001)九州芸術工科大学 (2000)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
2000
资助国家：
日本
起止时间：
2000 至 2001
项目状态：
已结题

项目摘要

並列・分散ネットワーク環境での最も基本的な要求は,データパケットを目的のノードまで正しく,高速に伝達することである.本研究の目標は,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において公表した.

并行和分布式网络环境中最基本的要求是正确，快速地将数据包传输到目标节点。这项研究的目的是设计有效的数据包旅行路线选择算法（路由算法），并针对具有诸如部分结构等规则结构的大型网络网络开发实用技术。 We obtained the following results: 1. Despite the diameter of the 3D mesh networks (Ohm (N^<1/3>), a simple route selection algorithm requires at least 0 (N^<2/3>). This result is a Journal of the Journal of the Journal of the 3D mesh coupling network. Published in Algorithms.2. The effectiveness of the transmission-controlled non-information method was verified for the routing in a 2D网络的网络。当每个节点可以在2D网格耦合网络中以1.16n^<1/2>+O（N^<1/2）的纽约，以3^<1/2> <1/2的时间显示了3个网络，显示了每个节点可以立即保持的算法（n^<3/4>）时间。图3。最佳0（n^<1/2>）时间是通过使用2D网格耦合网络上的每个节点的相邻信息开发的。该结果在算法中发布的杂志中显示了。 4。关于二维网状总线通信网络的路由，这表明在控制传输时使用概率是有效的，并发表在理论计算机科学中。

项目成果

期刊论文数量（20）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

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

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

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

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

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

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

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

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

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

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

Iwama, Kazuo: "An O(√<N>) oblivious routing algorithm for two-dimensional meshes of constant queue-size"Journal of Algorithms. 41. 262-279 (2001)

Iwama, Kazuo：“用于恒定队列大小的二维网格的 O(√<N>) 不经意路由算法”《算法杂志》41. 262-279 (2001)。

DOI：
发表时间：
期刊：
影响因子：
0
作者：
通讯作者：

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

宮野英次其他文献

最大・最小支配ツアー問題の計算複雑さ

最大-最小支配旅游问题的计算复杂度

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次
通讯作者：
野々上夏葵，江藤宏，宮野英次

重複無し最長共通部分列問題の計算時間

无重复的最长公共子序列问题的计算时间

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆
通讯作者：
歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆

最小ブロック転送問題について

关于最小块传输问题

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次;寺原一平，江藤宏，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，斎藤寿樹，鈴木顕，八木田剛;八木田剛，朝廣雄一，宮野英次
通讯作者：
八木田剛，朝廣雄一，宮野英次

C5フリー正則グラフ上での誘導マッチング問題に対する近似アルゴリズム

C5自由正则图引导匹配问题的逼近算法

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次
通讯作者：
柳植竜，朝廣雄一，Guohui Lin，宮野英次

無色グラフに対する彩色ハッピー集合問題について

关于无色图的有色快乐集问题

DOI：
发表时间：
2018
期刊：
影响因子：
0
作者：
朝廣雄一;Guohui Lin;Zhilong Liu;宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;寺原一平，江藤宏，Guohui Lin，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;林田将敬，宮野英次;吉瀬紘平，宮野英次;税所航平，宮野英次;歌島侃勇，朝廣雄一，Jesper Janssen，Guohui Lin，宮野英次，小野廣隆;寺原一平，朝廣雄一，江藤宏，土中哲秀，Guohui Lin，宮野英次;小林賢也，Guohui Lin，宮野英次，八木田剛;朝廣雄一，ジャンソンジェスパー，宮野英次，小野廣隆，T.P.サディヤ;朝廣雄一，ジャンソンジェスパー，宮野英次，ニクパイヘサム，小野廣隆;江藤宏，土中哲秀，宮野英次，西島歩美，小野廣隆，大舘陽太，斎藤寿樹，上原隆平，ヴァンデルザンデントム;八木田剛，朝廣雄一，宮野英次;野々上夏葵，江藤宏，宮野英次;柳植竜，朝廣雄一，Guohui Lin，宮野英次;寺原一平，江藤宏，Guohui Lin，宮野英次
通讯作者：
寺原一平，江藤宏，Guohui Lin，宮野英次