A framework for designing deadlock-free wormhole routing algorithms

This paper presents a framework to design fully-adaptive, deadlock-free wormhole algorithms for a variety of network topologies. The main theoretical contributions are: (a) design of new wormhole algorithms using store-and-forward algorithms, (b) a sufficient condition for deadlock free routing by the wormhole algorithms so designed, and (c) a sufficient condition for deadlock free routing by these wormhole algorithms with centralized flit buffers shared among multiple channels. To illustrate the theory, several wormhole algorithms based on store-and-forward hop schemes are designed. The hop-based wormhole algorithms can be applied to a variety of networks including torus, mesh, de Brujin, and a class of Cayley networks, with the best known bounds on virtual channels for minimal routing on the last two classes of networks. An analysis of the resource requirements and performances of a proposed algorithm, called negative-hop algorithm, with some of the previously proposed algorithms for torus and mesh networks is presented     

Link-state routing without broadcast storming for multichannel mesh networks

A link-state routing protocol tailored for multichannel mesh networks is proposed. One drawback of using multichannel communications is the high overhead involved in broadcast operations: a transmitter should transmit a broadcast packet to all channels that may be occupied by receivers. This makes certain broadcast-intensive mechanisms, such as link-state routing, difficult to implement. The link-state routing protocol proposed in this paper is tailored for multichannel mesh networks by minimizing the broadcast overheads. This is achieved by a special set of nodes, called cluster-heads. We have implemented our protocol on a multichannel mesh network test bed and compared its performance with an AODV-like reactive routing protocol, also tailored for multichannel mesh networks. The measurements show that the proposed link-state routing protocol provides transient communications with comparable or better performance. Ways to improve the performance of the proposed routing with infrastructure access is also discussed.     

Deadlock-free dynamic reconfiguration schemes for increased network dependability

Network-based parallel computing systems often require the ability to reconfigure the routing algorithm to reflect changes in network topology if and when voluntary or involuntary changes occur. The process of reconfiguring a network's routing capabilities may be very inefficient and/or deadlock-prone if not handled properly. We propose efficient and deadlock-free dynamic reconfiguration schemes that are applicable to routing algorithms and networks which use wormhole, virtual cut-through, or store-and-forward switching, combined with hard link-level flow control. One requirement is that the network architecture use virtual channels or duplicate physical channels for deadlock-handling as well as performance purposes. The proposed schemes do not impede the injection, transmission, or delivery of user packets during the reconfiguration process. Instead, they provide uninterrupted service, increased availability/reliability, and improved overall quality-of-service support as compared to traditional techniques based on static reconfiguration.     

Deadlock free routing algorithms for irregular mesh topology NoC systems with rectangular regions

The simplicity of regular mesh topology Network on Chip (NoC) architecture leads to reductions in design time and manufacturing cost. A weakness of the regular shaped architecture is its inability to efficiently support cores of different sizes. A proposed way in literature to deal with this is to utilize the region concept, which helps to accommodate cores larger than the tile size in mesh topology NoC architectures. Region concept offers many new opportunities for NoC design, as well as provides new design issues and challenges. One of the most important among these is the design of an efficient deadlock free routing algorithm. Available adaptive routing algorithms developed for regular mesh topology cannot ensure freedom from deadlocks. In this paper, we list and discuss many new design issues which need to be handled for designing NoC systems incorporating cores larger than the tile size. We also present and compare two deadlock free routing algorithms for mesh topology NoC with regions. The idea of the first algorithm is borrowed from the area of fault tolerant networks, where a network topology is rendered irregular due to faults in routers or links, and is adapted for the new context. We compare this with an algorithm designed using a methodology for design of application specific routing algorithms for communication networks. The application specific routing algorithm tries to maximize adaptivity by using static and dynamic communication requirements of the application. Our study shows that the application specific routing algorithm not only provides much higher adaptivity, but also superior performance as compared to the other algorithm in all traffic cases. But this higher performance for the second algorithm comes at a higher area cost for implementing network routers.     

基于InfiniBand的多链路mesh/torus大规模并行系统互连网络

在大规模并行系统中,系统级互连网络的设计至关重要.InfiniBand作为一种高性能交换式网络被广泛应用于大规模并行处理系统中.mesh/torus拓扑结构相较于目前普遍应用于InfiniBand网络的胖树拓扑结构拥有更好的性能与可扩展性.尽管如此,研究发现,用传统的mesh/torus拓扑结构构建InfiniBand互连网络存在诸多问题.分析了传统网络拓扑结构的缺陷,并提出了一种基于InfiniBand的多链路mesh/torus互连网络.这种改进型的拓扑结构通过充分利用交换机间的多链路可以获得比传统mesh/torus网络更高的带宽.另外,同时给出了与该网络拓扑结构相配套的高效路由算法.最后,通过网络仿真技术对提出的算法进行了评估,实验结果显示提出的路由算法相较于其他路由算法拥有更好的性能与可扩展性.     

Enhancing multi-hop communication over multi-radio multi-channel wireless mesh networks: A cross-layer approach

The multi-channel multi-radio technology represents a straightforward approach to expand the capacity of wireless mesh networks (WMNs) in broadband wireless access scenarios. However, the effective leveraging of this technology in WMNs requires (i) enhanced MAC protocols, to coordinate the access to multiple channels with a limited number of radio interfaces, and (ii) efficient channel allocation schemes, to mitigate the impact of co-channel interference. The design of channel assignment schemes and MAC protocols is strictly interrelated, so that joint design should be considered to optimize the mesh network performance. In this paper, a channel assignment and fast MAC architecture (CAFMA) is proposed, which exploits the benefits provided by the multi-channel multi-radio technology to (i) enhance the performance of multi-hop communications, (ii) maximize the resource utilization, and (iii) support differentiation of traffic classes with different quality of service (QoS) requirements. CAFMA is designed with a cross-layer approach and includes (1) a novel MAC scheme, which provides multi-channel coordination and fast data relaying over multi-hop topologies, and (2) a distributed channel allocation scheme, which works in cooperation with the routing protocol. Simulation results confirm the effectiveness of CAFMA when compared with other single-layer and cross-layer solutions for multi-radio multi-channel WMNs.     

认知无线mesh网中联合路由的分布式信道分配算法*

多信道技术通过对数据流量进行分流,能够减少链路间干扰,从而提升网络容量。首先针对认知无线mesh网络提出一种有效的联合路由的分布式信道分配策略,该信道分配策略主要宗旨是维持邻域内信道差异。仿真结果表明,新的信道分配算法相比于无线多信道网络中基于链接的信道分配算法,平均吞吐量大约提高了50%,平均时延降低了约50%。在信道约束的情况下,进一步引入了信道合并算法。仿真结果表明,执行信道合并算法后,网络平均吞吐量、时延性能得到了进一步改善。     

结合混合式信道分配的无线MESH多路径路由协议

为了优化无线Mesh网络中的多接口多信道网络资源,对单接口多路径路由协议和单路径信道分配策略进行了深入的分析研究,提出了与混合式信道分配方式相结合的多路径路由协议(AODV-MP),实现了网络中多条路径的并行传输,从而提高网络的整体吞吐率。并根据多路径路由协议自身的特性,结合与邻居节点干扰相关的因素——信噪比(SNR),提出了多路径路由的路由度量判决WCETTSNR,同时将该路由度量作为负载流量分配的比例标准。利用NS2网络仿真平台对该多路径路由协议进行测试,结果显示AODV-MP在网络吞吐率上提高了45%,并在高负载情况下,较大幅度地减少了网络延时。     

一种动态分配虚拟输出队列结构的片上路由器

传统虚通道流控技术的片上路由器通过增加虚通道缓解排头阻塞引起的链路吞吐率下降以及网络拥塞的同时,面临缓冲区低利用率、仲裁开销较大等问题.而动态虚通道流控的片上路由器虽可通过动态管理缓冲单元,提高缓冲区利用率与链路吞吐率,但却不可避免流控与仲裁逻辑复杂度与开销的快速增长.为了提高链路吞吐率与缓冲区利用率,获得较好的性能与开销折中,提出一种动态分配虚拟输出队列结构的片上路由器DAVOQ,该结构通过快速链表动态组织虚拟输出队列,同时使用超前路由机制以简化仲裁逻辑,优化流水线.模拟与综合的结果表明,相比传统虚通道路由器,DAVOQ路由器改善报文传输延迟与吞吐率的同时,在0.13μm CMOS工艺下,节省了15.1%的标准单元面积与12.9%的漏电流功耗;而相比动态虚通道路由器,DAVOQ路由器能够以较小的吞吐率损失获得可观的延迟改善,同时节约15.6%的标准单元面积与20.5%的漏电流功耗.     

XCHARM: A routing protocol for multi-channel wireless mesh networks

Recent experimental results have pointed out the impact of physical layer multi-path fading and co-channel interference as the key factors influencing packet delivery among mesh routers (MRs) in wireless mesh networks. In addition, in a multi-channel environment, there exists significant power spectral overlap among channels used by MRs, leading to adjacent channel interference. In this paper, a cross-layer multi-radio, multi-channel routing protocol, XCHARM, is proposed in which the key contribution is the selection of the next hop, channel and transmission rate based on fading and interference concerns. The key features of our proposed protocol are as follows: (i) Routes are chosen based on the availability of channels that support high data rates, exhibit acceptable interference levels and long term resilience to fading related losses, (ii) The path latency is analytically calculated in advance for the candidate routes, accounting for channel induced errors, link layer contention, forward error correcting (FEC) codes, and the allowed data rates over the chosen channels, (iii) The route maintenance is performed by first attempting to identify and correct the point of failure before undertaking a global recovery action. An extensive performance evaluation, spanning the network, link and physical layers, reveals the benefits of adopting our cross-layer routing solution for wireless mesh networks.     

TM: a new and simple topology for interconnection networks

The selection of a topology is essential to the performance of interconnection networks, so designing a new, cost-effective topology is very significant. 2D mesh is one of the most popular topologies. However, the diameter and average distance of a 2D mesh are large enough to greatly influence the performance of the network. This paper presents a novel topology called TM, which combines the advantages of both a 2D torus and a 2D mesh. For an n×n network, the total number of links in a TM is the same as that in a mesh, while the diameter of a TM is extremely close to that of a torus. Besides, the average distance of a TM is at the middle of that of a torus and that of a mesh. To prevent deadlocks in TMs, a virtual network partitioning scheme is adopted into the TM network. Moreover, both of the deterministic and fully-adaptive routing techniques in TMs are proposed in this paper. Compared to mesh, the TM network provides average distance and diameter reduction, which contributes to the performance enhancement. Sufficient simulation results are presented to show the effectiveness of the TM network, and the new routing schemes proposed for it, by comparing with the mesh network. Compared to the torus, which requires at least 3 virtual channels to support fully-adaptive routing, the TM network can support fully-adaptive routing with only 2 virtual channels. Seen from the experimental results, in most cases, the performance of TM is worse than the torus, while in some cases, the performance of TM is comparable to torus or even better than the torus.     

How to Effectively Use Multiple Channels in Wireless Mesh Networks

Operating on a frequency band occupying several nonoverlapping channels, IEEE 802.11 is now widely used in wireless mesh networks (WMNs). Many multichannel MAC protocols are proposed to improve the spatial reuse in the network under the assumption that the transmissions on nonoverlapping channels do not interfere with each other. Some joint routing and channel assignment algorithms are also designed to increase the network throughput based on the premise that we can switch between different channels freely. Although simulations show that great improvements on network throughput can be observed in both cases, two fundamental questions remain: 1) Can we really use multiple nonoverlapping channels freely in WMNs? 2) If we can, what will be the cost when we switch channels dynamically and frequently? In this paper, by conducting extensive experiments on our testbed, we attempt to answer these questions. We find that in spite of interference between both overlapping and nonoverlapping channels, we can still use multiple channels in mesh networks under certain conditions but with care. We also show that the channel switching cost is actually very significant in WMNs. We recommend not to switch the channels too frequently when designing the channel assignment algorithms, and those channel assignment algorithms selecting one channel for each packet are not really beneficial.     

OLSR-aware channel access scheduling in wireless mesh networks

Wireless mesh networks (WMNs) have emerged as a key technology having various advantages, especially in providing cost-effective coverage and connectivity solutions in both rural and urban areas. WMNs are typically deployed as backbone networks, usually employing spatial TDMA (STDMA)-based access schemes which are suitable for the high traffic demands of WMNs. This paper aims to achieve higher utilization of the network capacity and thereby aims to increase the application layer throughput of STDMA-based WMNs. The central idea is to use optimized link state routing (OLSR)-specific routing layer information in link layer channel access schedule formation. This paper proposes two STDMA-based channel access scheduling schemes (one distributed, one centralized) that exploit OLSR-specific information to improve the application layer throughput without introducing any additional messaging overhead. To justify the contribution of using OLSR-specific information to the throughput, the proposed schemes are compared against one another and against their non-OLSR-aware versions via extensive ns-2 simulations. Our simulation results verify that utilizing OLSR-specific information significantly improves the overall network performance both in distributed and in centralized schemes. The simulation results further show that OLSR-aware scheduling algorithms attain higher end-to-end throughput although their non-OLSR-aware counterparts achieve higher concurrency in slot allocations.     

A scalable multimedia QoS architecture for ad hoc networks

Communication demands have grown from separate data and voice to integrated multimedia, paving the way to converging fixed, mobile and IP networks. Supporting Multimedia is a challenging task for wireless ad hoc network designers. Multimedia forms high data rate traffic with stringent Quality of Service (QoS) requirements. Wireless ad hoc networks are characterized by frequent topology changes, unreliable wireless channel, network congestion and resource contention. Providing scalable QoS is the most important challenge for multimedia delivery over ad hoc networks. We introduce here a provisioning and routing architecture for ad hoc networks which scales well while provisioning QoS. The proposed architecture is analysed using a mix of HTTP, voice and video streaming applications over 54 Mbps 802.11 g-based ad hoc networks. The architecture is simulated and compared to well-known routing protocols using the OPNET Modeller. The results show that our architecture scales well with increase in the network size, and outperforms well-known routing protocols.     

Alleviating consumption channel bottleneck in wormhole routed k-aryn-cube systems

This paper identifies performance degradation in wormhole routed k-ary n-cube networks due to limited number of router-to-processor consumption channels at each node. Many recent research in wormhole routing have advocated the advantages of adaptive routing and virtual channel flow control schemes to deliver better network performance. This paper indicates that the advantages associated with these schemes cannot be realized with limited consumption capacity. To alleviate such performance bottlenecks, a new network interface design using multiple consumption channels is proposed. To match virtual multiplexing on network channels, we also propose each consumption channel to support multiple virtual consumption channels. The impact of message arrival rate at a node on the required number of consumption channels is studied analytically. It is shown that wormhole networks with higher routing adaptivity, dimensionality, degree of hot-spot traffic, and number of virtual lanes have to take advantage of multiple consumption channels to deliver better performance. The interplay between system topology, routing algorithm, number of virtual lanes, messaging overheads, and communication traffic is studied through simulation to derive the effective number of consumption channels required in a system. Using the ongoing technological trend, it is shown that wormhole-routed systems can use up to two-four consumption channels per node to deliver better system performance     

Route Maintenance in IEEE 802.11 wireless mesh networks

In this paper, we propose a novel Route Maintenance scheme for IEEE 802.11 wireless mesh networks. Despite lack of mobility and energy constraints, reactive routing protocols such as AODV and DSR suffer from frequent route breakages in 802.11 based infrastructure wireless mesh networks. In these networks, if any intermediate node fails to successfully transmit a packet to the next hop node after a certain number of retransmissions, the link layer reports a transmission problem to the network layer. Reactive routing protocols systematically consider this as a link breakage (and therefore a route breakage). Transmission failures can be caused by a number of factors e.g. interference or noise and can be transient in nature. Frequent route breakages result in significant performance degradation. The proposed mechanism considers multiple factors to differentiate between links with transient transmission problems from those links which have permanent transmission problems and takes a coherent decision on link breakage. The proposed mechanism is implemented in AODV for single-radio single-channel mesh network and an extension is incorporated in multi-radio multi-channel scenarios. Simulation results show substantial performance improvement compared to classical AODV and local route repair schemes.     

无线网状网的QoS研究

作为下一代无线通信网络的关键技术,无线网状网能够融合异构网络,满足多类型的业务需求,因此必须提供一定的服务质量(QoS)保证.对目前各种QoS体系结构进行了分析,讨论了无线网状网的QoS体系结构.针对无线网状网网络层以下各层的QoS问题,对近年来国内外在功率控制、无线环境感知、支持QoS的MAC协议、QoS路由以及跨层QoS设计等方向所取得的研究成果进行了全面的概括总结和比较分析.最后对未来的研究发展趋势提出了自己的观点.     

Survivable millimeter-wave mesh networks

Millimeter-wave mesh networks have the potential to provide cost-effective high-bandwidth solutions to many current bandwidth-constrained networks including cellular backhaul. However, the availability of such networks is severely limited due to their susceptibility to weather, such as precipitation and humidity. In this paper, we present a rigorous approach to survivable millimeter-wave mesh networks based on experimentation, modeling, and simulation. Individual link performance is characterised using frame error-rate measurements from millimeter-wave transmissions on test links over a period of one year. A geometric model based on radar-reflectivity data is used to characterise rain storms and determine their impact on spatially correlated links of a mesh network. To mitigate the impact of link impairments on network services, we present two cross-layered routing protocols to route around the failures: P-WARP (predictive weather-assisted routing protocol) and XL-OSPF (cross-layered open shortest-path first). We conduct a performance analysis of the proposed mesh network under the presence of actual weather events as recorded by the US National Weather Service. Results show that the proposed approach yields the highest dependability when compared against existing routing methods.     

配置流驱动计算体系结构指导下的ASIP设计

为了兼顾嵌入式处理器设计中的灵活性与高效性,提出配置流驱动计算体系结构.在体系结构设计中将软/硬件界面下移,使功能单元之间的互连网络对编译器可见,并由编译器来完成传输路由,从而支持复杂但更为高效的互连网络.在该体系结构指导下,提出一种支持段式可重构互连网络的专用指令集处理器(ASIP)设计方法.该方法应用到密码领域的3类ASIP设计中表明,与简单总线互连相比,在不影响性能的前提下,可平均节约53%的互连功耗和38.7%的总线数量,从而达到减少总线数量、降低互连功耗的目的.     

Links organization for channel assignment in multi-radio wireless mesh networks

It is one key issue in the wireless mesh networks to provide various scenarios such as multimedia and applications. Links in the network can be organized and assigned to orthogonal channels so as to minimize the co-channel interference. In this paper we focus on the channel assignment problem for links in the mesh networks and aim at minimizing the overall network interference. The problem is proved to be NP-hard. We have first formulated an approach based on the Particle Swarm Optimization (PSO) algorithm which can be used to find the approximate optimized solution in small-size networks and as a baseline that other algorithms can be compared with. We also have proposed a centralized heuristic as well as a distributed heuristic algorithm for the channel assignment problem. Extensive simulation results have demonstrated that our schemes have good performance in both dense and sparse networks compared with related works.