| Interconnection networks enable fast data communication between components of a digital system. Today, interconnection networks are used in a variety of applications such as switch and router fabrics, processor-memory interconnect, I/O interconnect, and on-chip networks, to name a few.; The design of an interconnection network has three aspects---the topology, the routing algorithm used, and the flow control mechanism employed. The topology is chosen to exploit the characteristics of the available packaging technology to meet the requirements (bandwidth, latency, scalability, etc.) of the application, at a minimum cost. Once the topology of the network is fixed, so are the bounds on its performance. For instance, the topology determines the maximum throughput (in bits/s) and zero-load latency (in hops) of the network. The routing algorithm and flow control must then strive to achieve these performance bounds.; The function of a routing algorithm is to select a path to route a packet from its source to its destination. In this thesis, we demonstrate the significance of the routing algorithm used in the network towards achieving the performance bounds set by the topology. Central to this thesis, is the idea of load-balancing the network channels. A naive routing algorithm that does not distribute load evenly over all channels, stands to suffer from sub-optimal worst-case performance. However, unnecessary load-balancing is overkill. Spreading traffic over all channels when there is no uneven distribution of traffic, leads to sub-optimal best-case and average-case performance. This thesis explores routing algorithms that strive to achieve high worst-case efficiency without sacrificing performance in the average or best-case.; While performance metrics such as average latency and worst-case throughput are key parameters in evaluating a network, there are several other important measures such as amount of packet reordering, statistical guarantees on delay and network buffer occupancy, to name a few. In the last part of this thesis, we propose a method to analyze the performance of a class of load-balanced networks over these performance metrics. |
