Adaptive Routing in Network-on-Chips Using a Dynamic-Programming Network
2011
Dynamic routing is desirable because of its substantial improvement in communication bandwidth and intelligent adaptation to faulty links and congested traffic. However, implementation of adaptive routing in a network-on-chip system is not trivial and is further complicated by the requirements of deadlock-free and real-time optimal decision making. In this paper, we present a deadlock-free routing architecture which employs a dynamic programming (DP) network to provide on-the-fly optimal path planning and network monitoring for packet switching. Also, a new routing strategy called k -step look ahead is introduced. This new strategy can substantially reduce the size of routing table and maintain a high quality of adaptation which leads to a scalable dynamic-routing solution with minimal hardware overhead. Our results, based on a cycle-accurate simulator, demonstrate the effectiveness of the DP network, which outperforms both the deterministic and adaptive-routing algorithms in average delay on various traffic scenarios by 22.3%. Moreover, the hardware overhead for DP network is insignificant, based on the results obtained from the hardware implementations.
Keywords:
- Routing table
- Policy-based routing
- DSRFLOW
- Dynamic Source Routing
- Hazy Sighted Link State Routing Protocol
- Multipath routing
- Equal-cost multi-path routing
- Real-time computing
- Static routing
- Computer science
- Distributed computing
- Link-state routing protocol
- Computer network
- Enhanced Interior Gateway Routing Protocol
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
39
References
68
Citations
NaN
KQI