Network-on-Chip (NoC) is a developing and promising on-chip communication paradigm that improves scalability and performance of System-on-Chips. NoC design flow contains many problems from different areas, for example networking, embedded design and computer architecture. Application mapping is one of these problems, which is well studied in literature but generally considered as a communication energy minimization problem. The present study discusses the effect of application mapping on network parameters such as average queuing delay or packet loss rates of routers. On the other hand, self similarity is a phenomenon that is used to characterize Ethernet and/or wide area network traffic, as well as most of on-chip network traffic. The main concern of this study is to analyze the effect of application mapping on network related parameters by using an on-chip traffic characterization that contains self similarity. The results of our computational study show that mapping of cores may have a significant degenerative effect on network performance, and so adding network related terms to application mapping problem may improve the overall on-chip network performance considerably.

This paper proposes a novel high throughput internet protocol (IP) lookup engine, which is built upon a recently proposed multiple pipeline array architecture that has parallel two-dimensional circular search capabilities on intersecting and variable length pipelines. Our new engine is composed of specially designed processing elements (PEs) including dual input/output static random access memory units and bidirectional links, hence allowing search to proceed in all directions and admitting search requests from all PEs at the boundary of the array. We propose a novel data structure called compact clustered trie (CCT), which is better than traditional binary trie in terms of memory requirement and number of memory accesses. We develop novel approaches including a CCT forwarding table construction method, a mapping strategy and a suitable IP lookup algorithm. Our new lookup engine achieves a much higher average case throughput and a much lower average delay compared with existing IP lookup solutions making, for example, an 8 Tbps high-speed router front end possible. The engine is also well suited for the IPv6 addressing scheme.

Network router virtualization has recently gained much interest in the research community, as it allows multiple virtual router instances to run on a common physical router platform. The key metrics in designing network virtual routers are (1) number of supported virtual router instances, (2) total number of prefixes, and (3) ability to quickly update the virtual table. Existing merging algorithms use leaf pushing and a shared next hop data structure to eliminate the large memory bandwidth requirement. However, the size of the shared next hop table grows linearly with the number of virtual routers. Due to the limited amount of on-chip memory and the number of I/O pins of Field Programmable Gate Arrays (FPGAs), existing designs cannot support large number of tables and/or large number of prefixes. This paper exploits the abundant parallelism and on-chip memory bandwidth available in the state-of-the-art FPGAs, and proposes a compact trie representation and a hybrid data structure to reduce the memory requirement of virtual routers. The approach does not require leaf-pushing; therefore, reduces the size of each entry of the data structure. Our algorithm demonstrates substantial reduction in the memory footprint compared with the state-of-the-art. Also, it eliminates the shared next hop information data structure and simplifies the table updates in virtual routers. Using a state-of-the-art FPGA, the proposed architecture can support up to 3.1M IPv4 prefixes. Employing the dual-ported memory available in the current FPGAs, we map the proposed data structure on a novel SRAMbased linear pipeline architecture to achieve high throughput. The post place-and-route result shows that our architecture can sustain a throughput of 394 million lookups per second, or 126 Gbps (for the minimum packet size of 40 Bytes).

Virtualization allows heterogeneous networks to share same underlying physical substrate. A single router fulfills the roles of multiple virtual routers by maintaining all the forwarding tables. Therefore, multiple virtual routers can run on a single substrate router, and multiple organizations share this single physical router. A single router plays the role of multiple independent virtual routers while providing the necessary isolation and resource management. Hence, a virtual router should fulfill the following requirements:\begin{itemize} \item \emph{Fair resource usage}: Router resources should be fairly shared among the virtual routers. \item \emph{Fault isolation}: A fault occurring in a particular virtual network should not affect the operation of other virtual networks. \item \emph{Security}: Traffic from one virtual network should not be mixed with the traffic from any other virtual network. \end{itemize}Storing these virtual routing tables separately leads to a large memory requirement and poor resource sharing. Therefore, merging emerges to be a desirable solution. Existing merging algorithms use leaf pushing technique and a shared next hop data structure to eliminate the large memory bandwidth requirement. However, the size of the shared next hop table grows linearly with the number of virtual routers. Due to the limited on-chip memory and the number of I/O pins of Field Programmable Gate Arrays (FPGAs), existing designs cannot support large number of virtual routing tables and/or large number of prefixes. We propose a compact trie representation and a hybrid data structure to reduce the memory consumption of a single virtual router. Our data structure achieves substantial memory compression without the need for backtracking. The proposed hybrid data structure is also used to merge different virtual routing tables. The approach does not require leaf-pushing and reduces the size of each entry of the data structure. Our data structure achieves a substantial memory reduction of $2\times$ over the state-of-the-art solutions. Additionally, it eliminates the shared next hop information structure and simplifies the table updates in virtual routers. Using a state-of-the-art FPGA, the proposed architecture can support up to 3.1M IPv4 prefixes, employing both on-chip BRAM and external SRAM. Our implementation on FPGA shows a sustained throughput of $394$ million lookups per second. In summary, this paper makes the following contributions:\begin{enumerate} \item A compact trie representation and a hybrid data structure for IP lookup that reduces the memory consumption without backtracking. \item A merging algorithm that eliminates leaf pushing and simplifies the table updates in virtual routers. \item A linear pipelined SRAM-based architecture on FPGAs that can support up to $3.1$M prefixes, while achieving a sustained throughput of $394$ million lookups per second.\end{enumerate}

Rectilinear Steiner minimal tree (RSMT) problem finds a minimum length tree that interconnects a given set of points by only horizontal and vertical line segments and by using extra points if necessary. In this paper, to speedup the RSMT construction, two recently developed successful heuristic algorithms, namely rectilinear steiner tree (RST) by Zhou and batched greedy algorithm (BGA) by Kahng , have been used as the basis. Following a slight modification on RST, which led to a nonrecursive and a considerably faster version, a partially parallelized and distributed form of this modified algorithm is proposed. Computational tests using large random data sets have shown the advantage of the modification on RST, and tests conducted on a cluster of workstations have proven the proposed distributed approach to be very promising particularly for large problem instances.