A study of fault-tolerant and adaptive routing networks

1.提出了一种容错自适应路由算法Detour-UD。它集成了适用于规则k元n立方网络拓扑的自适应路由算法和适用于不规则网络的死锁恢复路由算法。结果表明，该算法具有良好的通信性能和灵活的容错能力。我们还提出了一种低开销的动态网络重构协议。我们的协议支持选择性消息抽取。排水消息的选择是通过识别请求禁止的输出通道以用于底层死锁恢复路由功能的消息来执行的。即使在网络重构过程中，也不需要停止消息注入。我们设计了一个通信性能自动调优机制。该机制通过根据网络状态限制新数据包注入来管理流量负载。当路由器检测到拥塞和流量不平衡时，它还决定发起非最小路由。我们开发了一个网络模拟器来评估Detour-UD路由算法及其网络重构协议的性能。该仿真器还支持通信性能的自动调优机制。通过实验验证了Detour-UD和动态网络重构协议的性能。Detour-UD不仅在无故障的网络上，而且在有故障节点和通道的网络上，都能显示出高带宽和低延迟的通信性能。由于故障数量的增加而导致的性能下降是优雅的。提出的动态网络重构协议减少了引流报文的数量，有效地实现了网络的无缝运行。我们还证实，通信性能的自动调优机制可以很好地避免各种网络环境下的网络饱和。

1.We proposed a fault-tolerant adaptive routing algorithm Detour-UD. It integrates an adaptive routing algorithm for regular k-ary n-cube network topology and a deadlock-recovery routing algorithm for irregular networks. As a result, the proposed routing algorithm attains efficient communication performance as well as very flexible fault tolerance.2.We also proposed a low-overhead dynamic network reconfiguration protocol. Our protocol supports selective message drainage. The selection of drainage messages is performed by identifying messages which request prohibited output channels for an underlying deadlock-recovery routing function. It does not require stopping message injection even during the process of network reconfiguration.3.We designed an automatic tuning mechanism for communication performance. This mechanism manages traffic load by throttling new packet injection depending on network status. It also decides initiation of non-minimal routing when routers detect congestion and traffic imbalance.4.We developed a network simulator to evaluate performance of the Detour-UD routing algorithm and its network reconfiguration protocols. The automatic tuning mechanism for communication performance is also supported by this simulator.5.We experimentally clarified the performance of Detour-UD and the dynamic network reconfiguration protocol. Detour-UD shows high-bandwidth and low-latency communication performance not only on a non-faulty network but also on a network with faulty nodes and channels. Performance degradation for increase of the number of faults is graceful. The proposed dynamic network reconfiguration protocol reduces the number of drainage messages, and it is effective for seamless operation. We also confirmed that the automatic tuning mechanism for communication performance works well to avoid network saturation in various network circumstances.