Multiterminal net routing for partial crossbar-based multi-FPGA systems

Multi-FPGA (field-programmable gate arrays) systems are used as custom computing machines to solve compute-intensive problems and also in the verification and prototyping of large circuits. In this paper, we address the problem of routing multiterminal nets in a multi-FPGA system that uses partial crossbars as interconnect structures. First, we model the multiterminal routing problem as a partitioned bin-packing problem and formulate it as an integer linear programming problem where the number of variables is exponential. A fast heuristic is applied to compute an upper bound on the routing solution. Then, a column generation technique is used to solve the linear relaxation of the initial master problem in order to obtain a lower bound on the routing solution. This is followed by an iterative branch-and-price procedure that attempts to find a routing solution somewhere between the two established bounds. In this regard, the proposed algorithm guarantees an exact-routing solution by searching a branch-and-price tree. Due to the tightness of the bounds, the branch-and-price tree is small resulting in shorter execution times. Experimental results are provided for different netlists and board configurations in order to demonstrate the algorithms performance. The obtained results show that the algorithm finds an exact routing solution in a very short time.     

A novel and efficient routing architecture for multi-FPGA systems

Multi-FPGA systems (MFSs) are used as custom computing machines, logic emulators and rapid prototyping vehicles. A key aspect of these systems is their programmable routing architecture which is the manner in which wires, FPGAs and field-programmable interconnect devices (FPIDs) are connected. Several routing architectures for MFSs have been proposed, and previous research has shown that the partial crossbar is one of the best existing architectures. In this paper, we propose a new routing architecture, called the hybrid complete-graph and partial-crossbar (HCGP) which has superior speed and cost compared to a partial crossbar. The new architecture uses both hard-wired and programmable connections between the FPGAs. We compare the performance and cost of the HCGP and partial crossbar architectures experimentally, by mapping a set of 15 large benchmark circuits into each architecture. A customized set of partitioning and interchip routing tools were developed, with particular attention paid to architecture-appropriate interchip routing algorithms. We show that the cost of the partial crossbar (as measured by the number of pins on all FPGAs and FPIDs required to fit a design), is on average 20% more than the new HCGP architecture and as much as 25% more. Furthermore, the critical path delay for designs implemented on the partial crossbar were on average 20% more than the HCGP architecture and up to 43% more. Using our experimental approach, we also explore a key architecture parameter associated with the HCGP architecture-the proportion of hard-wired connections versus programmable connections-to determine its best value     

Efficient routing in network-on-chip for 3D topologies

With the increasing of the integration capability intra-chip, nowadays numerous integrated systems explore a set of processing elements, such as in multicore processors. An efficient interconnection of those elements can be obtained via the use of Network on chip (NoC). This approach is similar to the traditional computer networks where, not restricted to multiprocessors, it is possible to interconnect several dedicated devices. Like other networks, NoCs can be arranged in different topologies, such as ring, mesh and torus. It has shared links that can be used in the transmission of packets of different nodes. Thus, the network congestion is an issue and must be treated to reduce delays. Algorithms based on ant colony optimisation have proven to be effective in static routing in systems designed to perform a fixed set of tasks, or where the communication pattern is known. This article introduces 3D ant colony routing (3D-ACR) and applies it as routing policy of NoCs having three different 3D topologies: mesh, torus and hypercube. Experimental results show that 3D ant colony routing performs consistently better compared with the previously proposed routing strategies.     

Efficient visualization of large routing topologies

As the Internet grows in size and complexity, network managers face a significant challenge in trying to understand the behaviour of routing protocols in large networks. In this paper, we present a tool called VLNT (visualizing large network topologies), which helps network managers to analyse complex routing topologies. A key contribution of our system is a novel hybrid layout algorithm, which significantly reduces the computation time required to layout large network topologies in comparison to conventional layout approaches. In addition our algorithm includes a novel termination criterion that avoids unnecessary iterations when optimizing the network layout. We demonstrate how the visualization features of VLNT can be used to analyse and improve BGP routing topologies, and provide examples using real‐life routing data. Copyright © 2004 John Wiley & Sons, Ltd.     

Provisioning of adaptability to variable topologies for routing schemes in MANETs

Frequent changes in network topologies caused by mobility in mobile ad hoc networks (MANETs) impose great challenges to designing routing schemes for such networks. Various routing schemes each aiming at particular type of MANET (e.g., flat or clustered MANETs) with different mobility degrees (e.g., low, medium, and high mobility) have been proposed in the literature. However, since a mobile node should not be limited to operate in a particular MANET assumed by a routing scheme, an important issue is how to enable a mobile node to achieve routing performance as high as possible when it roams across different types of MANETs. To handle this issue, a quantity that can predict the link status for a time period in the future with the consideration of mobility is required. In this paper, we discuss such a quantity and investigate how well this quantity can be used by the link caching scheme in the dynamic source routing protocol to provide the adaptability to variable topologies caused by mobility through computer simulation in NS-2.     

On-demand coding-aware routing in wireless Mesh networks

Network coding,which exploits the broadcast nature of wireless medium,is an effective way to improve network performance in wireless multi-hop networks,but the first practical wireless network coding system COPE cannot actively detect a route with more coding opportunities and limit the coding structure within two-hop regions.An on-demand coding-aware routing scheme(OCAR)for wireless Mesh networks is proposed to overcome the limitations specified above by actively detecting a route with more coding opportunities along the entire route rather than within two-hop regions.Utilizing more coding opportunities tends to route multiple flows 'close to each other' while avoiding interference requires routing multiple flows 'away from each other'.OCAR achieves a tradeoff by adopting RCAIA as routing metric in route discovery,which is not only coding-aware but also considers both inter and intra flow interference.Simulation results show that,compared with Ad-hoc on-demand distance vecfor routing(AODV)and AODV+COPE,OCAR can find more coding opportunities,thus effectively increase network throughput,reduce end to end delay and alleviate network congestion.     

Evaluating a cross-layer approach for routing in Wireless Mesh Networks

Routing in Wireless Mesh Networks is challenging due to the unreliable characteristics of the wireless medium. Traditional routing paradigms are not able to propose an efficient solution to this problem. Further, Gupta et al. demonstrated that the average throughput capacity per node of a wireless multi-hop network decreases as 1/n, where n is the number of nodes in the network. Recent studies have shown that a cross-layer approach is a promising solution to get closer to the theoretic throughput capacity bound. Cross-layer solutions have been already proposed either for specific TDMA/CDMA networks or for power-efficient routing protocols. These proposals are strongly MAC dependent, or suffer from targeting a steady state offering the best trade-off performance. In this paper, the problem we tackle in a more general context, disregarding the specific MAC and Physical layers technologies, can be formulated as follows: How to design a routing algorithm able to increase the average throughput capacity experienced by Wireless Mesh Networks? Starting from a theoretic result, we analyze the gain that a cross-layer approach can deliver, the metrics suitable to improve throughput capacity, and the power control policy that reduces interference. We take a MAC independent approach, focusing on the general characteristics of wireless links, targeting the improvement of throughput capacity in Wireless Mesh Networks. Our proposal performs path selection and power optimization based on three metrics, namely physical transmission rate, interference, and packet error rate. Performances are thoroughly analyzed and evaluated by extensive simulations, with both TCP and UDP traffic, and compared to other multi-hop routing protocols. For both kind of traffic, the simple heuristic we propose here allows to double the average throughput the network is able to route.     

一种基于信道利用状况的无线Mesh路由判据

无线Mesh网络,又称无线因特网,融合了无线局域网和移动Ad Hoe网络的优势,它已经成为下一代无线网络的关键技术之一.路由技术对Mesh网络性能起着至关重要的作用.现有用于Ad Hoc的路由协议不能充分体现WlVlN的特殊性,在现有WCETT及CCM判据的基础上,提出一种新的用于Mesh网络的多信道路径判据Weighted Cumulative CCM-L(WCCCM-L),该判据主要根据信道利用状况选择干扰低的路径发送消息.     

Efficient routing and centralized scheduling algorithms for IEEE 802.16 Mesh Networks

An IEEE 802.16 wireless system can provide broadband wireless access to subscriber stations and operate in mesh mode. The communication between a subscriber station and a base station can pass through one or more intermediate subscriber stations. The IEEE 802.16 standard provides a centralized scheduling mechanism that supports contention‐free and resource‐guarantee transmission services in mesh mode. However, the corresponding algorithm to this schedule is quite primitive in the standard. In this paper, we propose a more efficient way to realize this schedule by maximizing channel utilization. Our designs are divided into two phases: routing and scheduling. First, a routing tree topology is constructed from a given mesh topology by our proposed tree construction algorithm. Secondly, we allocate channel resources to the edges in the routing tree by our proposed scheduling algorithm. To further support the quality‐of‐service schedule, we extend our designs by addressing some issues such as service class, admission control and fairness. Simulation results show the superiority of our proposed algorithms over others. Copyright © 2011 John Wiley & Sons, Ltd.     

Power-efficient routing mechanism for ODMA systems

Opportunity driven multiple access (ODMA), a cellular multihop method proposed for Universal Mobile Telecommunications Systems, potentially allows reduction in power consumption of user equipment (UE), extending Node B's coverage and supporting higher user data rate. However, ODMA requires extra power for discovering relaying nodes and introduces additional transmission latency in data transfer. This paper offers enlightenment to these ODMA implementation problems. A power-efficient routing (PER) mechanism is proposed to identify a minimum-power path for ODMA communication. Prior to the route (or path) discovery, the PER mechanism utilizes an analytical solution to estimate the total power and number of intermediate UEs required in the minimum-power path. With the estimation, route discovery procedures originating from nonattainable ODMA requests can be prevented. For those attainable ODMA requests that require a route discovery procedure to locate intermediate UEs, the PER mechanism further provides a method to set the transmission power and maximum hop count. Hence, the power consumption of each UE during route discovery is significantly reduced. Simulation results coincided with the analysis, and the results demonstrate the performance improvement of PER over dynamic source routing.     

无线Mesh网络中跨层协作的路由策略

网络编码可以提高无线Mesh网络的吞吐量,但是网络编码在无线Mesh网络中实际应用获得最大网络利用率是需要解决的问题。提出一种多路径策略,能够通过将网络编码和TCP进行最大化融合提高网络的利用率。网络编码被加入到现有的网络系统,通过解决速率控制问题和分组调度问题,调整源节点的数据编码分块,降低数据包重传的次数,提高网络的吞吐量。     

Wireless Mesh network secure routing mechanism based on dynamic reputation

Aiming at the problem that the wireless Mesh network (WMN) security routing mechanism was scarce and internal malicious nodes drop data packets during data transmission,a secure routing mechanism based on dynamic reputation (SRMDR) for wireless Mesh network was proposed.Firstly,the dynamic reputation mechanism was used to evaluate the node’s behavior,the node’s comprehensive reputation value was calculated according to the node’s direct reputation value and the recommended reputation value,and the node’s dynamic reputation value was calculated according to the node’s historical comprehensive reputation value and the current comprehensive reputation value.Then,the dynamic reputation was combined with the routing mechanism to establish secure routing paths,the nodes with a dynamic reputation value less than the threshold were determined to be malicious nodes,which were isolated during the routing process.Experimental results show that compared with HWMP and SHaRP,SRMDR has higher malicious node recognition rates,and SRMDR can effectively reduce packet loss rate and improve network throughput.     

The COBRA-ABS high-level synthesis system for multi-FPGA customcomputing machines

This paper describes the column oriented butted regular architecture-algorithmic behavioral synthesis (COBRA-ABS) high-level synthesis tool which has been designed to synthesize DSP algorithms, specified in C, onto multi-field programmable gate array (FPGA) custom computing machines (FCCMs). COBRA-ABS performs synthesis using a new simulated annealing-based methodology, which maps the specified behavior into a four-dimensional (4-D) space and then optimizes the implied architecture. COBRA-ABS synthesizes custom very long instruction word (VLIW) style architectures partitioned across the FPGAs of the FCCM and has been used to compile C algorithms down to FPGA configuration bit-streams. This paper describes the tool and synthesis concepts and presents simulation results from a number of synthesized fast Fourier transform (FFT) related algorithms     

Directional MAC and routing schemes for power controlled Wireless Mesh Networks with adaptive antennas

Wireless Mesh Networks (WMNs) have emerged recently as a technology for next-generation wireless networking. Several approaches that exploit directional and adaptive antennas have been proposed in the literature to increase the performance of WMNs. However, while adaptive antennas can improve the wireless medium utilization by reducing radio interference and the impact of the exposed nodes problem, they can also exacerbate the hidden nodes problem. Therefore, efficient MAC protocols are needed to fully exploit the features offered by adaptive antennas. Furthermore, routing protocols that were designed for omnidirectional communications can be redesigned to exploit directional transmissions and the cross-layer interaction between the MAC and the network layer.In this paper we first propose a novel Power-Controlled Directional MAC protocol (PCD-MAC) for adaptive antennas. PCD-MAC uses the standard RTS–CTS–DATA–ACK exchange procedure. The novel difference is the transmission of the RTS and CTS packets in all directions with a tunable power while the DATA and ACK are transmitted directionally at the minimal required power.We then propose the Directional Deflection Routing (DDR), a routing algorithm that exploits multiple paths towards the destination based on the MAC layer indication on channel availability in different directions.We measure the performance of PCD-MAC and DDR by simulation of several realistic network scenarios, and we compare them with other approaches proposed in the literature. The results show that our schemes increase considerably both the total traffic accepted by the network and the fairness among competing connections.     

Type-of-service routing in datagram delivery systems

The Internet is expected to support various services, including best-effort services and guaranteed services. For best-effort services, we propose a new approach to achieving type-of-service (TOS) classes with adaptive next-hop routing. We consider two TOS classes, namely, delay-sensitive and throughput-sensitive. As in routing protocols such as OSPF and integrated IS-IS, each node has a different next-hop for each destination and TOS class. Traditionally, a node has a single FCFS queue for each outgoing link, and the next-hops are computed using link measurements. In our approach, we attempt to isolate the two traffic classes by using for each outgoing link a separate FCFS queue for each TOS class; the link is shared cyclicly between its TOS queues. The next-hops for the delay-sensitive traffic adapts to link delays of that traffic. The next-hops for the throughput-sensitive traffic adapts to overall link utilizations. We compare our approach with the traditional approach using discrete-event simulation and Lyapunov analysis (for stability of routes). Our approach offers lower end-to-end delay to the delay-sensitive traffic. A related property is that the routes for the delay-sensitive traffic are more stable, i.e., less oscillations. An unexpected property is that the overall end-to-end delay is lower, because the throughput-sensitive traffic moves away to under-utilized routes     

Capacity dimensioning and routing for hybrid satellite and terrestrial systems

Satellite network architecture plays an important role in the success of a satellite business. For future commercial broadband data satellite networks integrated with the terrestrial network, satellite network topology, link capacity, and routing have major impacts on the cost of the network and the amount of revenue the network can generate. To find the most cost-effective satellite network topology, we propose a unified mathematical framework using a two-stage stochastic programming formulation. The solution to the stochastic programming formulation gives optimal link capacities and an optimal routing strategy for different network topologies, taking into account uncertainties in long-term aggregate traffic statistic estimation. Using a simple satellite network example, we show the feasible topology regions for three different satellite topologies and show that, for some parameter values, the hybrid topology is more cost effective than nonhybrid topologies. In the limit of high traffic rejection cost, stochastic dimensioning reduces to static dimensioning. We study worst case static dimensioning for a general geosynchronous earth orbit satellite network and show the feasible topology regions, as well as effective cost comparisons for different topologies. We conclude with a discussion on network cost and architectural flexibility relating to satellite network design.     

The impact of interference-aware routing metrics on video streaming in Wireless Mesh Networks

Wireless Mesh Networks form a wireless backbone that provides ubiquitous Internet access and support of multimedia services. In this scenario, traffic crosses multi-hop paths, through mesh routers and gateways, causing high levels of interference. To address this problem, the use of schemes that introduce routing metrics that take into account the characteristics of the interference have been made to improve the application performance. Given the diversity of interference-aware routing metrics for Wireless Mesh Networks, it is necessary to assess the impact of employing these routing metrics on multimedia traffic performance, and in particular, on video streaming. This paper seeks to fill this gap, by using simulation to evaluate the video streaming performance when the most relevant interference-aware routing metrics are used. The degree of video quality can be evaluated from two perspectives, the network viewpoint and the standpoint of the user perception. At the network level, video streaming quality is assessed through IP measures, that is, throughput, delay, jitter and routing overhead. At the user level, ‘Quality of Experience’ metrics are employed to measure the user perception with regard to the video quality. The evaluation of the performance takes account of outdoor and indoor environments. The results of the simulation study have shown that routing metrics based on the information that detects interference using accurate measures achieve a better network and user perception performance. However, depending on the environment (i.e., whether it is indoor or outdoor), all the routing metrics result in a different performance being achieved. Although interference-aware routing metrics affect the performance of both the network and the user levels, there are some cases where they have less impact on the user level, because the user perception parameters are less influenced by the behaviour of the network.     

分布式发布/订阅通信系统中的事件路由研究

侧重研究并介绍发布,订阅通信系统(P/S系统)的体系结构及其路由方法,包括基本通信对象的寻找方法、优化的路由方法以及支持拓扑变化和客户移动的路由方法等;在路由方法上对著名的P/S系统进行了分析和比较:针对P/S系统的可扩展性,提出了未来进一步研究的思路.     

Analysis of multipath routing, part 2: mitigation of the effects of frequently changing network topologies

In this paper, we extend the analysis of multipath routing presented in our previous work, so that the basic restrictions on the evaluation and optimization of that scheme can be dropped (e.g., disjoint paths and identical paths in terms of failure probability). In that work, we employed diversity coding in order to provide increased protection against frequent route failures by splitting data packets and distributing them over multiple disjoint paths. Motivated by the high increase in the packet delivery ratio, we study the increase we can achieve through the usage of multiple paths in the general case, where the paths are not necessarily independent and their failure probabilities vary. For this reason, a function that measures the probability of successful transmission is derived as a tight approximation of the evaluation function P/sub succ/. Given the failure probabilities of the available paths and their correlation, we are able to find in polynomial time the set of paths that maximizes the probability of reconstructing the original information at the destination.     

基于IEEE802.11s的多射频多信道无线mesh网络路由判据的探究

无线mesh网络是下一代无线网络技术中人们研究与关注的热点技术之一。根据最新IEEE 802.11s协议,其路由判据是基于无线感知的空时链路判据(airtime link metric,ALM)。这种路由判据比传统的以跳数作为判据要好,但是当多信道或多射频条件下时,这种判据会引起信道容量的衰减,不足以满足如今的网络需求。因此,有许多新的路由判据被提出。例如,加权累计期望传输时间,干扰及信道切换,归一化的瓶颈链路容量等。本文主要定性的比较这些判据的特点,然后通过NS-2进行网络仿真,根据IEEE 802.11s协议中默认的路由协议,将这些多信道条件下的路由判据进行相互比较。由此,得出结论,明确各种路由判据所适用的不同的场合。