Networking Reference
In-Depth Information
5. ROUTING
5.3.1 VALIANT'S ALGORITHM (VAL)
VAL routing [ 66 ] uses randomization and non-minimal routing to exploit the path diversity of a
topology and achieve load-balancing. VAL is a two-phase routing algorithm with a random node in
the network initially selected. In the first phase, minimal routing is used to route the packet to the
intermediate node. Once the packet reaches the intermediate node, in the second phase, the packet
is routed to the destination. If the random node happens to be either the source or the destination,
VAL degenerates into minimal routing as only one phase of the VAL routing is needed.
By using randomization to load-balance the traffic, high throughput can be achieved on
adversarial traffic patterns as VAL can provide optimal performance on adversarial traffic pattern,
or 50% throughput of capacity [ 63 ]. However, by converting all traffic pattern into two phases of
uniform random traffic, VAL causes higher zero-load latency and loss of traffic locality. Thus, on
benign traffic pattern such as uniform random traffic, network throughput is reduced by a factor of
2 compared to minimal routing. In the following sections, we discuss how adaptive routing can be
used to adaptively decide between minimal and nonminimal routing to maximize performance to
overcome the limitations of VAL routing.
5.3.2 UNIVERSAL GLOBAL ADAPTIVE LOAD-BALANCING (UGAL)
UGAL routing [ 58 ] was proposed to adapt between minimal and nonminimal routing on a per-
packet basis based on the congestion information of the network. If nonminimal routing is chosen,
packet is routed as VAL routing - otherwise, minimal routing is used. For benign traffic patterns,
UGAL attempts to approach the performance of minimal routing to exploit traffic locality or benign
traffic patterns. For adversarial traffic patterns, UGAL sends most of its traffic nonminimally using
VAL to load-balance the channels.
The UGAL routing decision is based at the source router - i.e., the router connected to the
source node of the packet - and once the routing decision is made, the routing decision is not revisited
as the packet follows either the minimal or the nonminimal path. The congestion information used
by the UGAL routing algorithm is the product of the queue depth ( q ) and the hop count ( H ) for a
minimal and a nonminimal path. The minimal queue depth ( q m ) represents the congestion on the
output port which is used for minimal routing and minimal hop count ( H m ) is the minimal hop
count between source and destination. With a randomly chosen intermediate node, nonminimal
queue depth ( q nm ) represents the congestion on the output port which is used for minimal routing
to reach the randomly selected intermediate node while nonminimal hop count ( H nm ) is the sum of
the hop count from the source to the intermediate node and the hop count from the intermediate
node to the destination. Thus, UGAL can be summarized as follows:
if
( q m H m q nm H nm )
route minimally;
else
route nonminimally;
Search MirCeyron ::




Custom Search