Adaptive Wormhole Routing in Mesh-connected Bidirectional K-ary 2-Cubes

Abstract

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.

Notes

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 STARS for more information.

Graduation Date

1991

Semester

Fall

Advisor

Wills, Scott

Degree

Master of Science (M.S.)

College

College of Engineering

Department

Computer Engineering

Degree Program

Computer Engineering

Format

PDF

Pages

74 p.

Language

English

Length of Campus-only Access

None

Access Status

Masters Thesis (Open Access)

Identifier

DP0027981

Subjects

Dissertations, Academic -- Engineering; Engineering -- Dissertations, Academic

This document is currently not available here.

Share

COinS