Query: A survey of routing algorithm for mesh Network-on-Chip

Candidate papers:

abstract: With the rapid development of semiconductor industry, the number of cores integrated on chip increases quickly, which brings tough challenges such as bandwidth, scalability and power into on chip interconnection. Under such background, Network on Chip (NoC) is proposed and gradually replacing the traditional on chip interconnections such as sharing bus and crossbar. For the convenience of physical layout, mesh is the most used topology in NoC design. Routing algorithm, which decides the paths of packets, has significant impact on the latency and throughput of network. Thus routing algorithm plays a vital role in a wellperformed network. This study mainly focuses on the routing algorithms of mesh NoC. By whether taking network information into consideration in routing decision, routing algorithms of NoC can be roughly classified into oblivious routing and adaptive routing. Oblivious routing costs less without adaptiveness while adaptive routing is on the contrary. To combine the advantages of oblivious and adaptive routing algorithm, half adaptive algorithms were proposed. In this paper, the concepts, taxonomy and features of routing algorithms of NoC are introduced. Then the importance of routing algorithms in mesh NoC is highlighted, and representative routing algorithms with respective features are reviewed and summarized. Finally, we try to shed light upon the future work of NoC routing algorithms.
author_names: Yue Wu

Chao-bo Lu

Yunji Chen
title: A survey of routing algorithm for mesh Network on Chip
venue: Frontiers of Computer Science
year: 2016

abstract: In this paper we present a reconfigurable routing algorithm for a 2D mesh network on chip (NoC) dedicated to fault tolerant, massively parallel multi processors systems on chip (MP2 SoC) The routing algorithm can be dynamically reconfigured, to adapt to the modification of the micro network topology caused by a faulty router. This algorithm has been implemented in a reconfigurable version of the DSPIN micro network, and evaluated from the point of view of performance (penalty on the network saturation threshold) and cost (extra silicon area occupied by the reconfigurable version of the router)
author_names: Zhen Zhang

Alain Greiner

Sami Taktak
title: A reconfigurable routing algorithm for a fault tolerant 2D Mesh Network on Chip
venue: 2008 45th ACM/IEEE Design Automation Conference
year: 2008

abstract: 1 Introduction 32 Routing on NoC 52.1 Network Topologies 52.2 Problems on Routing 72.2.1 Deadlock. 82.2.2 Livelock. 82.2.3 Starvation. 92.3 Network Flow Control 93 Oblivious Routing Algorithms 103.1 Dimension Order Routing 103.1.1 XY routing 103.2 Turn Models 113.3 Deterministic Routing Algorithms 123.3.1 Shortest Path Routing 133.3.2 Source Routing 133.3.3 Destination tag Routing 143.3.4 Topology Adaptive Routing 143.4 Stochastic Routing Algorithms 143.4.1 Flooding Algorithms 143.5 Summary 164 Adaptive Routing Algorithms 174.1 Minimal Adaptive Routing 174.2 Fully Adaptive Routing 174.2.1 Congestion Look Ahead 174.3 Turnaround Routing 174.4 Other Adaptive Routing Algorithms 184.5 Summary 205 Router Architectures 215.1 Oblivious Routers 215.1.1 Virtual Channel Router 215.1.2 Xpipes 225.1.3 AEthereal 235.1.4 Proteo 245.1.5 MANGO 255.1.6 SoCBUS 255.1.7 Arteris 265.1.8 STNoC 265.2 Adaptive Routers 261
author_names: Ville Rantala

Teijo Lehtonen

Juha Plosila
title: Network on Chip Routing Algorithms
year: 2006

abstract: The scaling of microchip technologies has enabled large scale systems on chip (SoC) Network on chip (NoC) research addresses global communication in SoC, involving (i) a move from computation centric to communication centric design and (ii) the implementation of scalable communication structures. This survey presents a perspective on existing NoC research. We define the following abstractions: system, network adapter, network, and link to explain and structure the fundamental concepts. First, research relating to the actual network design is reviewed. Then system level design and modeling are discussed. We also evaluate performance analysis techniques. The research shows that NoC constitutes a unification of current trends of intrachip communication rather than an explicit new alternative.
author_names: Tobias Bjerregaard

Shankar Mahadevan
title: A survey of research and practices of Network on chip
venue: CSUR
year: 2006

abstract: Wireless mesh networks (WMNs) consist of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs. They provide network access for both mesh and conventional clients. The integration of WMNs with other networks such as the Internet, cellular, IEEE 802.11, IEEE 802.15, IEEE 802.16, sensor networks, etc. can be accomplished through the gateway and bridging functions in the mesh routers. Mesh clients can be either stationary or mobile, and can form a client mesh network among themselves and with mesh routers. WMNs are anticipated to resolve the limitations and to significantly improve the performance of ad hoc networks, wireless local area networks (WLANs) wireless personal area networks (WPANs) and wireless metropolitan area networks (WMANs) They are undergoing rapid progress and inspiring numerous deployments. WMNs will deliver wireless services for a large variety of applications in personal, local, campus, and metropolitan areas. Despite recent advances in wireless mesh networking, many research challenges remain in all protocol layers. This paper presents a detailed study on recent advances and open research issues in WMNs. System architectures and applications of WMNs are described, followed by discussing the critical factors influencing protocol design. Theoretical network capacity and the state of the art protocols for WMNs are explored with an objective to point out a number of open research issues. Finally, testbeds, industrial practice, and current standard activities related to WMNs are highlighted.
author_names: Ian F Akyildiz

Xudong Wang

Weilin Wang
title: Wireless mesh networks: a survey
venue: Comput. Networks
year: 2005

abstract: Recent advances in wireless sensor networks have led to many new protocols specifically designed for sensor networks where energy awareness is an essential consideration. Most of the attention, however, has been given to the routing protocols since they might differ depending on the application and network architecture. This paper surveys recent routing protocols for sensor networks and presents a classification for the various approaches pursued. The three main categories explored in this paper are data centric, hierarchical and location based. Each routing protocol is described and discussed under the appropriate category. Moreover, protocols using contemporary methodologies such as network flow and quality of service modeling are also discussed. The paper concludes with open research issues. 2003 Elsevier B.V. All rights reserved.
author_names: Kemal Akkaya

Mohamed F Younis
title: A survey on routing protocols for wireless sensor networks
venue: Ad Hoc Networks
year: 2005

abstract: Wireless mesh networks (WMNs) have emerged as a key technology for next generation wireless networking. Because of their advantages over other wireless networks, WMNs are undergoing rapid progress and inspiring numerous applications. However, many technical issues still exist in this field. In order to provide a better understanding of the research challenges of WMNs, this article presents a detailed investigation of current state of the art protocols and algorithms for WMNs. Open research issues in all protocol layers are also discussed, with an objective to spark new research interests in this field.
author_names: Ian F Akyildiz

Xudong Wang
title: A survey on wireless mesh networks
venue: IEEE Communications Magazine
year: 2005

abstract: Vehicular ad hoc network (VANET) is an emerging new technology integrating ad hoc network, wireless LAN (WLAN) and cellular technology to achieve intelligent inter vehicle communications and improve road traffic safety and efficiency. VANETs are distinguished from other kinds of ad hoc networks by their hybrid network architectures, node movement characteristics, and new application scenarios. Therefore, VANETs pose many unique networking research challenges, and the design of an efficient routing protocol for VANETs is very crucial. In this article, we discuss the research challenge of routing in VANETs and survey recent routing protocols and related mobility models for VANETs.
author_names: Fan Li

Yu Wang
title: Routing in vehicular ad hoc networks: A survey
venue: IEEE Vehicular Technology Magazine
year: 2007

abstract: Wireless sensor networks consist of small nodes with sensing, computation, and wireless communications capabilities. Many routing, power management, and data dissemination protocols have been specifically designed for WSNs where energy awareness is an essential design issue. Routing protocols in WSNs might differ depending on the application and network architecture. In this article we present a survey of state of the art routing techniques in WSNs. We first outline the design challenges for routing protocols in WSNs followed by a comprehensive survey of routing techniques. Overall, the routing techniques are classified into three categories based on the underlying network structure: flit, hierarchical, and location based routing. Furthermore, these protocols can be classified into multipath based, query based, negotiation based, QoS based, and coherent based depending on the protocol operation. We study the design trade offs between energy and communication overhead savings in every routing paradigm. We also highlight the advantages and performance issues of each routing technique. The article concludes with possible future research areas.
author_names: Jamal N Al-Karaki

Ahmed E Kamal
title: Routing techniques in wireless sensor networks: a survey
venue: IEEE Wireless Communications
year: 2004

abstract: We propose a packet switched platform for single chip systems which scales well to an arbitrary number of processor like resources. The platform, which we call Network on Chip (NOC) includes both the architecture and the design methodology. The NOC architecture is a m/spl times/n mesh of switches and resources are placed on the slots formed by the switches. We assume a direct layout of the 2 D mesh of switches and resources providing physical and architectural level design integration. Each switch is connected to one resource and four neighboring switches, and each resource is connected to one switch. A resource can be a processor core, memory, an FPGA, a custom hardware block or any other intellectual property (IP) block, which fits into the available slot and complies with the interface of the NOC. The NOC architecture essentially is the onchip communication infrastructure comprising the physical layer, the data link layer and the network layer of the OSI protocol stack. We define the concept of a region, which occupies an area of any number of resources and switches. This concept allows the NOC to accommodate large resources such as large memory banks, FPGA areas, or special purpose computation resources such as high performance multi processors. The NOC design methodology consists of two phases. In the first phase a concrete architecture is derived from the general NOC template. The concrete architecture defines the number of switches and shape of the network, the kind and shape of regions and the number and kind of resources. The second phase maps the application onto the concrete architecture to form a concrete product.
author_names: Shashi Kumar

Axel Jantsch

Mikael Millberg

Johnny Oberg

Juha-Pekka Soininen

Martti J Forsell

Kari Tiensyrja

Ahmed Hemani
title: A network on chip architecture and design methodology
venue: Proceedings IEEE Computer Society Annual Symposium on VLSI. New Paradigms for VLSI Systems Design. ISVLSI 2002
year: 2002