A New Worst-Case Throughput Bound for Oblivious Routing in Odd Radix Mesh Network
Networks-on-Chip (NoC) has been proposed as a new intra-chip communication infrastructure. Regular topologies, especially the mesh topology, have been widely deployed. The choice of oblivious routing algorithm, which is oblivious of the network state when determining a route, has a significant impact on the network performance, such as the throughput and the latency. Average case throughput provides an average performance metric, whereas worst-case throughput provides a performance guarantee. It is well-known and has been shown that the optimal worst-case throughput for oblivious routing in two-dimensional mesh networks is 1/2 of the network capacity when the radix is even.