Inquiry Into Chaotic Routing

混沌路由器是一种非最小的自适应消息路由器，它在路由和取消路由决策中使用随机化。随机化的使用充分简化了路由器，推测混沌路由可以与遗忘路由竞争，实现同等或更好的平均情况性能，极大地提高了最坏情况性能和容错性。虽然混沌路由的原理在某种程度上适用于任何节点之间有多条路径的拓扑结构，但目前正在研究二元n-立方体的混沌路由器。这项研究的目标是建立一个令人信服的案例来构建一个超立方体混沌路由器的实验版本。为此目的，目前正在进行一系列研究。1. 该方案的理想路由器正在转化为实际工程设计；正在指定混沌路由逻辑的细节。替代方案包括顺序和并行通道匹配算法、存储并转发提议的虚拟直通替代方案、异步通道的各种替代方案、各种队列大小等。已经创建了一个详细的模拟器（具有大约六个门延迟的粒度）。实验正在256个节点的超立方体上进行，以比较不同的混沌路由器设计与各种替代路由器，如遗忘和优先级路由器。3. 正在进行模拟以分析多队列大小对网络延迟和吞吐量的影响。还分析了消息长度对延迟和吞吐量的影响。4. 去年夏天完成的概率分析表明，理想的超立方体混沌路由器在确定性上是无死锁的，在概率上是无活锁和饥饿的。新的工程设计正在被抽象和分析，以确保它们符合这一理论的理想模型。5. 自定义CMOS通道设计的第一个版本已从制造中返回并正在进行测试。6. 除了定制CMOS之外，正在研究其他实现策略。7. 在不同的拓扑环境下，分析了混沌路由原理的通用性。特别是，各种形式的网格拓扑正在被研究作为交替。8. 从理论基础与定时策略无关的角度出发，分析了定时逻辑和自定时逻辑在混沌路由中的作用。

A chaotic router is a non-minimal, adaptive message router that uses randomization in routing and derouting decisions. The use of randomization simplifies the router sufficiently that it's conjectured chaotic routing can be competitive with oblivious routing, achieving equivalent or better average-case performance, greatly improved worst-case performance and fault tolerance. Though the principles of chaotic routing apply to some degree to any topology with multiple paths between nodes, chaotic routers for binary n-cubes are presently under investigation. The goal of the research is to establish a compelling case for constructing an experimental version of a hypercube chaotic router. Towards that end a series of studies are presently underway. 1. The idealized router of the proposal is being converted to practical engineering designs; the details of the chaotic routing logic are being specified. Alternatives include sequential and parallel channel match algorithms, a virtual cut-through alternative to the store-and- forward of the proposal, various alternates for asynchronous channels, various queue sizes, etc. 2. A detailed simulator (with a granularity of approximately a half-dozen gate delays) has been created. Experiments are being run on a 256 node hypercube to compare the different chaotic router designs with various alternative routers, such as oblivious and priority routers. 3. Simulations are being run to analyze the effect of multiqueue size on the latency and throughput of the network. The role of message length on latency and throughput is also being analyzed. 4. Probabilistic analysis, completed last summer, shows that an idealized hypercube chaotic router is deterministically deadlock free and probabilistically livelock and starvation free. The new engineering designs are being abstracted and analyzed to assure that they are consistent with the idealized model of this theory. 5. The first version of a custom CMOS channel design is back from fabrication and is being tested. 6. Alternate implementation strategies, besides custom CMOS, are being investigated. 7. The generality of the chaotic routing principles are being analyzed in the context of different topologies. In particular, various forms of the mesh topology are being studied as alternates. 8. The role of clocked and self-timed logic in chaotic routing is being analyzed in light of the fact theoretical foundations are independent of the timing policy.