ルーティングアルゴリズムのリアルタイム耐故障化に関する研究

路由算法实时容错研究

基本信息

批准号：
06750400
负责人：
石田賢治
金额：
$ 0.58万
依托单位：
Hiroshima Prefectural University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1994
资助国家：
日本
起止时间：
1994 至无数据
项目状态：
已结题

项目摘要

通信ならびに半導体技術の飛躍的発展に伴い、コンピュータネットワークは飛躍的に拡大しつつある。その結果、離れた場所の多数の計算機をネットワークで有機的に結合した大規模な情報通信システムが現実のものとなってきている。コンピュータネットワークにおける基本的かつ重要な機能にルーティングがある。大規模な情報通信システムの一部で異常が起こり、それがネットワーク全体に波及して甚大な社会的影響を及ぼす状況になってきている。こうした状況を回避し、正常な情報通信サービスを提供し続けるためには、障害の回復をリアルタイムに行う必要がある。これを行うための有力なアプローチの1つとして、ネットワークに論理的な階層構造であるクラスタを導入し、ルーティングを階層的に行う階層ルーティングがある。本研究では、この階層ルーティングをリアルタイム耐故障化する際の基礎的考察を行っている。階層ルーティングが行われる階層ネットワークに対して、リンク障害の波及を小さく抑えることができるネットワーク形状の満足すべき条件、及び、その具体的形状を示している。得られた条件を考慮することにより、ネットワーク内に障害が発生した場合でも、その障害の波及をネットワークの一部に局所化した形で、ネットワークの他の部分における階層ルーティングの継続が可能となる。また、得られた成果は大規模コンピュータネットワークを論理的、あるいは、物理的に分割して、階層的に管理する際に有効である。また、既存のLAN、及び、WANを統合して階層的に管理する際にも有効である。更に、本研究で得られた結果は、VLSI/WSIの回路構成にも応用可能である。例えば、構成部品の障害によりVLSI/WSI内の回路を再構成する際に、得られた結果を用いることにより、再構成の際、性能を維持するために重要である配線距離の増加を低く抑えることができる。

背景技术随着通信和半导体技术的快速发展，计算机网络正在迅速扩展。结果，远程位置的许多计算机通过网络有机连接的大规模信息和通信系统正在成为现实。路由是计算机网络中一项基本且重要的功能。大型信息通信系统局部出现异常，波及全网，产生巨大社会影响。为了避免此类情况的发生并继续提供正常的信息通信服务，需要实时从故障中恢复。实现这一目标的一种有前途的方法是分层路由，它将集群的逻辑分层结构引入网络并分层执行路由。在这项研究中，我们正在进行基本考虑，以使这种分层路由实时容错。对于执行分层路由的分层网络，示出了可以最小化链路故障的传播的网络形状的条件及其具体形状。通过考虑所获得的条件，即使网络内部发生故障，也可以在网络的其他部分继续分层路由，同时将故障的连锁反应局限于网络的一个部分。此外，所获得的结果对于在逻辑上或物理上划分大规模计算机网络并对其进行分层管理是有效的。在集成和分层管理现有 LAN 和 WAN 时，它也很有效。此外，本研究获得的结果也可以应用于VLSI/WSI电路配置。例如，当由于组件故障而重新配置 VLSI/WSI 中的电路时，所获得的结果可用于保持布线距离的增加较低，这对于在重新配置期间保持性能非常重要。