Dynamic broadcasting in parallel computing

We consider the problem where broadcast requests are dynamically generated at random time instants at each node of a multiprocessor network. In particular, in our model packets arrive at each node of a network according to a Poisson process, and each packet has to be broadcast to all the other nodes. We propose an on-line, distributed routing scheme to execute the broadcasts in this dynamic environment. Our scheme consists of repeated execution of a partial multinode broadcast task, which is a static communication task where any M⩽N arbitrary nodes of an N-processor network broadcast a packet to all the other nodes. The dynamic broadcasting scheme that we propose can be used in any topology, regular or not, for which partial multinode broadcast algorithms with certain properties can be found. We derive such an algorithm and we analyze the corresponding dynamic broadcasting scheme for the hypercube network. We show that its stability region tends to the maximum possible as the number of nodes of the hypercube tends to infinity. Furthermore, for any fixed load in the stability region, the average delay is of the order of the diameter of the hypercube. Our analysis does not use any approximating assumptions     

Dynamic end-to-end capacity in IEEE 802.16 wireless mesh networks

The IEEE 802.16 standard defines mesh mode as one of its two operational modes in medium access control (MAC). In the mesh mode, peer-to-peer communication between subscriber stations (SSs) is allowed, and transmissions can be routed via other SSs across multiple hops. In such an IEEE 802.16 mesh network, accurate and reliable determination of dynamic link capacity and end-to-end capacity of a given multi-hop route is crucial for robust network control and management. The dynamic capacities are difficult to determine in a distributed system due to decentralized packet scheduling and interference between communicating nodes caused by the broadcast nature of radio propagation. In this paper, we first propose a method for computing the dynamic link capacity between two mesh nodes, and extend that to determine the dynamic end-to-end capacity bounds of a multi-hop route based on the concept of Bottleneck Zone. The physical deployments of networks are also considered in the capacity estimation. We demonstrate the effectiveness and accuracy of our methods for computing dynamic link capacity and end-to-end capacity bounds through extensive simulations.     

Time-Step Optimal Broadcasting in 3-D Meshes with Minimum Total Communication Distance

In this paper we propose a new minimum total communication distance (TCD) algorithm and an optimal TCD algorithm for broadcast in a 3-dimensional mesh (3-D mesh). The former generates a minimum TCD from a given source node, and the latter guarantees a minimum TCD among all the possible source nodes. These algorithms are based on a divide-and-conquer approach where a 3-D mesh is partitioned into eight submeshes of equal size. The source node sends the broadcast message to a special node called an eye in each submesh. The above procedure is then recursively applied in each submesh. The proposed approach can be generalized to a d-dimensional mesh or torus. In addition, the proposed approach can potentially be used to solve optimization problems in other collective communication operations.     

Optimal Embedding of Multiple Directed Hamiltonian Rings into d-dimensional Meshes

In this paper, we consider the embedding of multiple directed Hamiltonian rings into d-dimensional meshes M_d. Assuming two adjacent nodes in M_d are connected by two directed links with opposite directions, we aim to embed as many directed Hamiltonian rings as possible in a way that they are link-disjoint. In particular, we construct d link-disjoint directed Hamiltonian rings in d-dimensional N₁×…×N_d mesh, where each N_i⩾2d is even.     

"Hypermeshes": Optical Interconnection Networks for Parallel Computing

A formal model for a class of optical mesh-based interconnection networks called "hypermeshes" is proposed and characterized. Hypermeshes are based on the concept of orthogonal crossbar switches, with N nodes arranged in n-dimensional mesh structure where all nodes aligned along a dimension are interconnected with an optical multichannel switch. The optical multichannel switches can be modeled as hypergraph "hyperedges" which can perform multiple data transfers over their members simultaneously. The hyperedges can be implemented with space division multiplexing (SDM) in the electrical or optical domains or with wavelength division multiplexing (WDM) over a single fiber in the optical domain. The use of WDM over a fiber also reduces the hypermesh "interconnection complexity" to rival that of a 2D mesh. An architectural characterization is performed and the combinatorial properties, including rearrangeability, permutation capability, partitionability, embedding capability, and bisection bandwidth, are characterized. It is shown that every algorithm which can execute conflict-free on an omega network can execute conflict-free on a hypermesh and that every graph which can be embedded into a hypercube with dilation k can be embedded into a hypermesh with dilation ≤ k. Hypermeshes are shown to have high bisection bandwidths, thereby minimizing the time for many common algorithms such as parallel sorting. It is shown that under the constraint of equivalent aggregate bandwidth the hypermeshes are considerably more powerful computational models than meshes, generalized hypercubes, and other orthogonal graphs. Two attractive optical implementations of hypermeshes using optical technology recently advocated in the literature are also proposed.     

无线传感网络的广播时效性研究

无线传感网络的节点采用时隙CSMA/CA协议获取信道并广播数据.为了度量信息广播的时效性,提出了广播信息年龄(broadcast age of information,bAoI)的概念.广播信息年龄等于当前时刻减去刚刚广播成功的那个数据包的生成时刻.bAoI量化了每个节点的数据包的新鲜度,并且描述了节点在网络上快速广播...     

A Scalable Interconnection Network Architecture for Petaflops Computing

Extrapolating technology advances in the near future, a computer architecture capable of petaflops performance will likely be based on a collection of processing nodes interconnected by a high-performance network. One possible organization would consist of thousands of inexpensive, low-power symmetric multiprocessor (SMP) nodes. Each node will inject data into the interconnection network at a very large rate and consequently, the interconnect scheme is one of the most crucial design issues affecting system performance. This paper describes the 2D simultaneous optical multiprocessor exchange bus (2D SOME-Bus) which has the potential to become the basis of a high-end computer architecture capable of petaflops performance. It consists of N horizontal, N vertical 1D SOME-Bus networks, and N ² nodes. Each node is connected to one horizontal and one vertical 1D SOME-Bus. Each of N nodes connected to one 1D SOME-Bus has a dedicated broadcast channel and an input channel interface based on an array of N receivers monitoring all N channels and allowing multiple simultaneous broadcasts. In the 2D SOME-Bus, messages being broadcast on one Bus can be broadcast in a cut-through manner on one or more Buses in the other dimension. This paper describes the optoelectronic devices and technology which make the 2D SOME-Bus possible, and the network interface organization. It also presents simulation results which compare the performance of the 2D SOME-Bus, the 1D SOME-Bus, the crossbar and the torus under the message-passing paradigm.     

New bounds for the controller problem

The (M, W)-controller, originally studied by Afek, Awerbuch, Plotkin, and Saks, is a basic distributed tool that provides an abstraction for managing the consumption of a global resource in a distributed dynamic network. The input to the controller arrives online in the form of requests presented at arbitrary nodes. A request presented at node u corresponds to the ??desire?? of some entity to consume one unit of the global resource at u and the controller should handle this request within finite time either by granting it with a permit or by denying it. Initially, M permits (corresponding to M units of the global resource) are stored at a designated root node. Throughout the execution permits can be transported from place to place along the network??s links so that they can be granted to requests presented at various nodes; when a permit is granted to some request, it is eliminated from the network. The fundamental rule of an (M, W)-controller is that a request should not be denied unless it is certain that at least M ? W permits are eventually granted. The most efficient (M, W)-controller known to date has message complexity ${O (N\log^{2} N \log \frac{M}{W + 1})}$ , where N is the number of nodes that ever existed in the network (the dynamic network may undergo node insertions and deletions). In this paper we establish two new lower bounds on the message complexity of the controller problem. We first prove a simple lower bound stating that any (M, W)-controller must send ${\Omega (N \log \frac{M}{W + 1})}$ messages. Second, for the important case when W is proportional to M (this is the common case in most applications), we use a surprising reduction from the (centralized) monotonic labeling problem to show that any (M, W)-controller must send ??(N log N) messages. In fact, under a long lasting conjecture regarding the complexity of the monotonic labeling problem, this lower bound is improved to a tight ??(N log² N). The proof of this lower bound requires that N =?O(M) which turns out to be somewhat inevitable due to a new construction of an (M, M/2)-controller with message complexity O(N log² M).     

不可靠通信环境下无线传感器网络最小能耗广播算法

在实际的通信环境中,由于噪声、报文冲突、信号衰减等因素的影响,无线传感器网络节点间信息交换往往是不可靠的.广播是无线传感器网络中广泛使用的操作,如何在不可靠通信环境下实现能量高效的广播算法,对提高整个无线传感器网络的性能具有重要的理论和应用价值.研究了不可靠通信环境下的无线传感器网络最小能耗广播问题,首先,分析了相邻节点之间最小能耗通信模型,并给出了保证节点接收概率不低于P^*的最优发送半径;然后,讨论了多跳转发策略与节点位置信息之间的关系.在此基础上,提出了一种基于PSO的最小生成树广播算法,通过优化各节点的发送半径,在保证所有节点都能以不低于P^*的概率接收到广播数据包的前提下,实现广播操作的总能耗最小.实验结果表明：所提出的广播算法不仅可使每一个节点的接收概率不小于P^*,而且广播总能耗比改进后的BIP算法要小,具有较好的性能.     

Routing schemes for multiple random broadcasts in arbitrary networktopologies

We consider the problem where packets are generated at each node of a network according to a Poisson process with rate λ, and each of them has to be broadcast to all the other nodes. The network topology is assumed to be an arbitrary bidirectional graph. We derive upper bounds on the maximum achievable broadcast throughput, and lower bounds on the average time required to complete a broadcast. These bounds apply to any network topology, independently of the scheme used to perform the broadcasts. We also propose two dynamic broadcasting schemes, called the indirect and the direct broadcasting scheme, that can be used in a general topology, and we evaluate analytically their throughput and average delay. The throughput achieved by the proposed schemes is equal to the maximum possible, if a half-duplex link model is assumed, and is at least equal to one half of the maximum possible, if a full-duplex model is assumed. The average delay of both schemes is of the order of the diameter of the trees used to perform the broadcasts. The analytical results obtained do not use any approximating assumptions     

Realizing and benchmarking broadcast algorithms in wireless mesh networks

Broadcasting by flooding causes the broadcast storm problem in multi-hop wireless networks. This problem becomes more likely in a wireless mesh network (WMN) because WMNs can bridge wired LANs, increasing broadcast traffic and collision probability. Since the network control, routing, and topology maintenance of a WMN highly rely on layer-2 broadcasting, unreliable broadcast algorithms directly destabilize a WMN. Researchers have developed many algorithms for efficient and reliable broadcast in multi-hop wireless networks. However, real-world systems rarely verify or compare these approaches, especially in a WMN. This paper examines six representative broadcast algorithms: simple flooding, dynamic probabilistic, efficient counter-based broadcast, scalable broadcast, domain pruning, and connected-dominating-set based algorithms. This study addresses both common and algorithm-specific implementation in a real-world IEEE 802.11s WMN testbed. Experiments under various topologies and packet lengths reveal the reliability, forwarding ratio, and efficiency of these six algorithms. Quantitative survey results indicate that the scalable broadcast algorithm possesses the best reliability due to its lower collision probability. The domain-pruning algorithm is the most efficient algorithm when considering both reliability and the forwarding ratio.     

Ad hoc node connectivity improvement analysis – Why not through mesh clients?

A mobile ad-hoc network (MANET) is a complex distributed system with unpredictable node movements, which results in frequent node disconnectivity. In a MANET, each node works independently, using the resources based on individual need. The main problem with this arises during the movement of the nodes and random utilization of network resources. This work attempts to solve the mobility maintenance issues using three mesh structures; (i) mesh tree (M_T), (ii) mesh backbone (M_B) and (iii) mesh cluster (M_C). The mobility maintenance architectures are formed based on a localized connectivity analysis and the node degree as a key parameter for network construction. The performance of the proposed work is analysed through mathematical models and simulation results.     

Optimal Communication Algorithms on Star Graphs Using Spanning Tree Constructions

In this paper we consider three fundamental communication problems on the star interconnection network: the problem of simultaneous broadcasting of a message from every node to all other nodes, or multinode broadcasting, the problem of a single node sending distinct messages to each one of the other nodes, or single-node scattering, and finally the problem of each node sending distinct messages to every other node, or total exchange. All of these problems are studied under two different assumptions: the assumption that each node can transmit a message of fixed length to one of its neighbors and simultaneously receive a message of fixed length from one of its neighbors (not necessarily the same one) at each time step, or single-link availability, and the assumption that each node can exchange messages of fixed length with all of its neighbors at each time step, or multiple-link availability. In both cases communication is assumed to be bidirectional. The cases where the originating processor wishes to send only one or more than one message to each one of the other processors are distinguished when necessary. Lower bounds are derived for these problems under the stated assumptions, and optimal algorithms are designed in terms of both time and number of message transmissions. Although the algorithms derived for the first two problems require the minimum amount of the above resources, the algorithm designed for the total exchange problem is optimal only to within a multiplicative factor. All the communication algorithms presented in this paper are based on the construction of spanning trees with special properties on the star graph to fit different communication needs. A special framework is developed to facilitate the construction of these trees. The scheduling disciplines that lead to optimal results in each case are described.     

DTSMA: Distributed time-spread multiple access for wireless mesh networks with IEEE 802.16d MAC protocol

This paper studies the use of IEEE 802.16d mesh MAC protocol for multi-hop networking in an indoor domestic environment. The mesh network is expected to support time-sensitive audio–video applications with stringent QoS requirement. In the literature, time-spread multiple access (TSMA) is a promising technology to provide a minimum throughput guarantee in a multi-hop mesh network with dynamic topology. However, existing TSMA schemes require the number of nodes in the entire network and their global maximum node degree, be known a priori to a central controller. The requirement is not practical. In view of this problem, this paper proposes a distributed time-spread multiple access (DTSMA) scheme. The proposed DTSMA has the following main contributions: (a) A method for each node to determine locally its polynomial coefficients without a priori global knowledge of node number and maximum node degree, and (b) A method to distribute to neighbours the locally determined polynomial coefficients, and to resolve collision between two sets of identical polynomial coefficients from two neighbouring nodes. The proposed DTSMA has been evaluated through extensive simulations to confirm that it can indeed preserve the capability of providing a minimum throughput guarantee in the absence of the a priori global knowledge. In benchmark against the de facto distributed coordinated scheduling (DCS) in the original IEEE 802.16d mesh MAC protocol under various domestic wireless channel conditions, DTSMA outperforms in terms of packet delivery ratio and average end-to-end packet delay which are important metrics for time-sensitive audio–video applications. Simulation results also show that DTSMA outperforms TSMA in terms of average end-to-end packet delay and average delay jitter when the severity of propagation impairment is high.     

Flooding in wireless ad hoc networks

In an ad hoc network, each host assumes the role of a router and relays packets toward final destinations. This paper studies efficient routing mechanisms for packet flooding in ad hoc wireless networks. Because a packet is broadcast to all neighboring nodes, the optimality criteria of wireless network routing are different from that of the wired network routing. We show that the minimum cost flooding tree problem is similar to MCDS (Minimum Connected Dominating Set) problem and prove the NP-completeness of the minimum cost flooding tree problem. Then, we propose two flooding methods: self-pruning and dominant pruning. Both methods utilize the neighbor information to reduce redundant transmissions. Performance analysis shows that both methods perform significantly better than the blind flooding. Especially, dominant pruning performs close to the practically achievable best performance limit.     

Fast gossiping in square meshes/tori with bounded-size packets

Gossiping is a communication problem in which each node has a unique message (token) to be transmitted to every other node. The nodes exchange their tokens by means of packets. A solution to the problem is judged by how many rounds of packet sending are required. In this paper, we consider a version of the problem in which small-sized packets (each carrying exactly one token) are used, the links (edges) of the network are half-duplex (only one packet can flow through a link at a time), and the nodes are all-port (a node's incident edges can all be active at the same time). This is also known as the H* model. We study the model on a 2D square mesh and on a 2D square torus. An improved, asymptotically optimal algorithm for the mesh and an optimal algorithm for the torus are presented     

Traceback in wireless sensor networks with packet marking and logging

In a hostile environment, sensor nodes may be compromised and then be used to launch various attacks. One severe attack is false data injection which is becoming a serious threat to wireless sensor networks. An attacker uses the compromised node to flood the network and exhaust network resources by injecting a large number of bogus packets. In this paper, we study how to locate the attack node using a framework of packet marking and packet logging. We propose a combined packet marking and logging scheme for traceback (CPMLT). In CPMLT, one packet can be marked by up to M nodes, each node marks a packet with certain probability. When one packet is marked by M nodes, the next marking node will log this packet. Through combining packet marking and logging, we can reconstruct the entire attack path to locate the attack node by collecting enough packets. In our simulation, CPMLT achieves fast traceback with little logging overhead.     

Broadcasting on Meshes with Wormhole Routing

We address the problem of broadcasting on two-dimensional mesh architectures with an arbitrary (non-power-of-two) number of nodes in each dimension. It is assumed that such mesh architectures employ cut-through or wormhole routing. The primary focus is on avoiding network conflicts in the various proposed algorithms. We give algorithms for performing a conflict-free minimum-spanning tree broadcast, a pipelined algorithm that is similar to Ho and Johnsson's EDST algorithm for hypercubes, and a novelscatter–collectapproach that is a natural choice for communication libraries due to its simplicity. Results obtained on the Intel Paragon system are included.     

Optimal communication algorithms for hypercubes

We consider the following basic communication problems in a hypercube network of processors: the problem of a single processor sending a different packet to each of the other processors, the problem of simultaneous broadcast of the same packet from every processor to all other processors, and the problem of simultaneous exchange of different packets between every pair of processors. The algorithms proposed for these problems are optimal in terms of execution time and communication resource requirements; that is, they require the minimum possible number of time steps and packet transmissions. In contrast, algorithms in the literature are optimal only within an additive or multiplicative factor.     

Distributed dynamic mobile multicast

Traditional mobile multicast schemes have either high multicast tree reconfiguration cost or high packet delivery cost. The former affects service disruption time while the latter affects packet delivery delay. Although existing region-based mobile multicast schemes offer a trade-off between two costs to some extent, most of them do not determine the size of the service range, which is critical to network performance. In this paper, we propose a novel approach, called Distributed Dynamic Mobile Multicast (D²M²), to dynamically determine the optimal service range according to the mobility and service characteristics of a user. We derive an analytical model to formulate the costs of multicast tree reconfiguration and multicast packet delivery. The model is based on a Markov chain that analyzes a mobile node’s movement in a 2D mesh network. As the complexity of computing steady probability is high, we aggregate the Markov states by leveraging mobility symmetry. Simulation shows that the network performance is enhanced through D²M².