تجزیه و تحلیل عملکرد از مسیریابی کرم چاله تطبیقی ​​در یک حلقه سه بعدی - دو بعدی

This paper presents an analytical evaluation of the performance of adaptive wormhole routing in a two-dimensional torus. Our analysis focuses on minimal and fully adaptive wormhole routing that allows a message to use any shortest path between source and destination. A validation of the analysis through simulation is presented to demonstrate the accuracy of the obtained results. Finally, we remark that no theoretical limitation prevents the extension of our analytical approach to the evaluation of the performance of adaptive wormhole routing in hypercubes or other symmetric topologies with wrap-around connections.

Wormhole routing is the most adopted and efficient technique for communications in parallel machines [28]. This policy makes the latency insensitive to the diameter of the interconnection network in case of light traffic and allows the reduction of the channel buffer size. Even if commercial multicomputers employ wormhole combined with deterministic routing, several studies have demonstrated the usefulness of adaptive strategies [5], [6], [13], [15] and [22]. Deterministic routing does not have the ability to cope with dynamic network conditions such as faults and congestion because the path between source and destination is determined statically. These drawbacks are avoided by adaptive routing that, in case of channel unavailability, looks for alternative paths. In this paper we propose an analytical approach to evaluate performance of minimal and fully adaptive wormhole. We present the model for a two-dimensional torus with bi-directional links. However, our analysis can be extended to other symmetric k-ary n-cubes with wrap-around connections (especially with low dimensional topologies which were demonstrated to achieve best performance [2] and [10]). In the literature, most of the results about adaptive wormhole have been obtained through simulation studies (e.g., [6], [15], [16], [20] and [22]), whereas analytical models are usually restricted to deterministic wormhole [1], [7], [8], [10], [12] and [19] or to different techniques such as circuit-switching [9] and virtual-cut-through [21] and [24]. To the best of our knowledge there are two papers related to our work [23] and [26], which present analytical evaluations for the case of adaptive wormhole routing. Finally, we note that the dynamic choice of paths proper of adaptive routing makes an analytical treatment of the wormhole technique very difficult. Many equations of our performance model show mutual dependencies that prevent a closed form solution and motivate the recursive form equation for the mean latency time. The remainder of the paper is organized as follows. In Section 2 we describe the operational features of minimal and fully adaptive wormhole routing in a two-dimensional torus. In Section 3 we present the model. In Section 4 we propose a solution for the estimation of the mean latency time. In Section 5 we validate the analytical results against time values obtained from simulations.

In this paper we propose a modeling approach to evaluate the message latency time of minimal and fully adaptive wormhole routing in two-dimensional torus. The assumptions that render the model analytically tractable are commonly accepted in literature. Due to the complexity of the investigated routing strategy, a closed form solution for the latency time is impracticable. Our analysis achieves recursive formulas that give the average latency time in a few iterative steps. We validate our analysis through simulations that demonstrate the accuracy of the results. As a final point, we would like to remark that no theoretical limitation prevents the extension of our analysis to hypercubes and other symmetric topologies with wrap-around connections.