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

路由算法实时容错研究

基本信息

批准号：
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和WANS以及通过层次管理它们进行管理时也有效。此外，本研究中获得的结果可以应用于VLSI/WSI的电路配置。例如，当由于组件故障引起的VLSI/WSI内重新配置电路时，可使用的结果可用于减少布线距离的增加，这对于在重新配置过程中保持性能很重要。