Adaptive Wormhole Routing in Mesh-connected Bidirectional K-ary 2-Cubes
An algorithm that extends the Minimum-hop routing algorithm as presented in Garcia-Luna-Aceves 1989 to adaptively route messages around congested areas of a mesh-connected bidirectional K-ary 2-cube is presented. According to the enhancement, information describing the degree of congestion is propagated away from congested areas and is used to route messages around the congestion. Congestion factors are computed and stored at each node in the network. Their value is determined based on a node's current loading and each of its neighbor's previous congestion factors, scaled by a global decay constant. In the absence or reduction of network congestion, the congestion factors decay to zero and messages are routed according to the Minimum-hop routing algorithm. A network simulator is used to test the effectiveness of the routing enhancement for traffic patterns that are categorized by the locality of each message's destination to its source node. Traffic patterns are generated, as described in Exum 1990, based on a probability distribution curve that indicates the probability a message will be routed a certain distance away from its source node. The distribution curve, which essentially categorizes the locality of the message destination, is applied to each of the nodes in the network in turn to generate sets of messages. The probability a given node will send a message is also varied to generate different traffic patterns and the affect of using congestion factors on the number of static blocks, moving blocks, and network throughput is investigated. It is shown that by propagating congestion information away from heavily loaded areas and then using this information to route messages away from the congestion, both the network latency and message blocking decrease.
This item is only available in print in the UCF Libraries. If this is your thesis or dissertation, you can help us make it available online for use by researchers around the world by downloading and filling out the Internet Distribution Consent Agreement. You may also contact the project coordinator Kerri Bottorff for more information.
Master of Science (M.S.)
College of Engineering
Length of Campus-only Access
Masters Thesis (Open Access)
Dissertations, Academic -- Engineering; Engineering -- Dissertations, Academic
Carey, John Austin, "Adaptive Wormhole Routing in Mesh-connected Bidirectional K-ary 2-Cubes" (1991). Retrospective Theses and Dissertations. 3803.