Streets of Byzantium: Network Architectures for Fast Reliable Broadcasts

A site broadcasting its local value to all other sites ina fault-prone environment is a fundamental paradigm in constructing reliable distributed systems. Time complexity lower bounds and network connectivity requirements for reliable broadcast protocols in point-to-point communication networks are well known. In this paper, we consider the reliable broadcast problem in distributed systems with broadcast networks (for example, Ethernets) as the basic communication architecture. We show how properties of such network architectures can be used to effectively restrict the externally visible behavior of faulty processors. We use these techniques to derive simple protocols that implement reliable broadcast in only two rounds, independent of the failure upper bounds.     

Visual Exploration of Dynamic Multichannel EEG Coherence Networks

Electroencephalography (EEG) coherence networks represent functional brain connectivity, and are constructed by calculating the coherence between pairs of electrode signals as a function of frequency. Visualization of such networks can provide insight into unexpected patterns of cognitive processing and help neuroscientists to understand brain mechanisms. However, visualizing dynamic EEG coherence networks is a challenge for the analysis of brain connectivity, especially when the spatial structure of the network needs to be taken into account. In this paper, we present a design and implementation of a visualization framework for such dynamic networks. First, requirements for supporting typical tasks in the context of dynamic functional connectivity network analysis were collected from neuroscience researchers. In our design, we consider groups of network nodes and their corresponding spatial location for visualizing the evolution of the dynamic coherence network. We introduce an augmented timeline‐based representation to provide an overview of the evolution of functional units (FUs) and their spatial location over time. This representation can help the viewer to identify relations between functional connectivity and brain regions, as well as to identify persistent or transient functional connectivity patterns across the whole time window. In addition, we introduce the time‐annotated FU map representation to facilitate comparison of the behaviour of nodes between consecutive FU maps. A colour coding is designed that helps to distinguish distinct dynamic FUs. Our implementation also supports interactive exploration. The usefulness of our visualization design was evaluated by an informal user study. The feedback we received shows that our design supports exploratory analysis tasks well. The method can serve as a first step before a complete analysis of dynamic EEG coherence networks.     

Network sampling and classification: An investigation of network model representations

Methods for generating a random sample of networks with desired properties are important tools for the analysis of social, biological, and information networks. Algorithm-based approaches to sampling networks have received a great deal of attention in recent literature. Most of these algorithms are based on simple intuitions that associate the full features of connectivity patterns with specific values of only one or two network metrics. Substantive conclusions are crucially dependent on this association holding true. However, the extent to which this simple intuition holds true is not yet known. In this paper, we examine the association between the connectivity patterns that a network sampling algorithm aims to generate and the connectivity patterns of the generated networks, measured by an existing set of popular network metrics. We find that different network sampling algorithms can yield networks with similar connectivity patterns. We also find that the alternative algorithms for the same connectivity pattern can yield networks with different connectivity patterns. We argue that conclusions based on simulated network studies must focus on the full features of the connectivity patterns of a network instead of on the limited set of networkmetrics for a specific network type. This fact has important implications for network data analysis: for instance, implications related to the way significance is currently assessed.     

On the emergence of chaos in dynamical networks

We investigate how changes of specific topological features result on transitions among different bounded behaviours in dynamical networks. In particular, we focus on networks with identical dynamical systems, synchronised to a common equilibrium point, then a transition into chaotic behaviour is observed as the number of nodes and the strength of their coupling changes. We analyse the network's transverse Lyapunov exponents (tLes) to derive conditions for the emergence of bounded complex behaviour on different basic network models. We find that, for networks with a given number of nodes, chaotic behaviour emerges when the coupling strength is within a specific bounded interval; this interval is reduced as the number of nodes increases. Furthermore, the endpoints the emergence interval depend on the coupling structure of network. We also find that networks with homogeneous connectivity, such as regular lattices and small-world networks are more conducive to the emergence of chaos than networks with heterogeneous connectivity like scale-free and star-connected graphs. Our results are illustrated with numerical simulations of the chaotic benchmark Lorenz systems, and to underline their potential applicability to real-world systems, our results are used to establish conditions for the chaotic activation of a network of electrically coupled pancreatic β-cell models.     

MANET与Internet互联时的自适应增强机制

移动自组网(MANET)与Internet的互联能有效扩展Internet覆盖和MANET应用范围。针对既有互联协议无法适应MANET动态变化的网络条件,在网关发现过程中形成广播风暴以及将全局路由建立于单向链路上等原因所导致的互联性能恶化,提出了一种具有自适应增强机制的互联协议,该协议一方面依据实际网络条件与Internet访问需求自动调整网关通告分组在MANET中的覆盖范围;另一方面,基于网络条件自适应调整发送间隔的HELLO分组可同时避免全局路由计算过程引入单向链路以及形成广播风暴。仿真结果表明,此自适应增强协议能够以合理的开销,在复杂而多变的应用环境下为MANET提供优化的互联性能。     

Bandwidth Efficient All-to-All Broadcast on Switched Clusters

Clusters of workstations employ flexible topologies: regular, irregular, and hierarchical topologies have been used in such systems. The flexibility poses challenges for developing efficient collective communication algorithms since the network topology can potentially have a strong impact on the communication performance. In this paper, we consider the all-to-all broadcast operation on clusters with cut-through and store-and-forward switches. We show that near-optimal all-to-all broadcast on a cluster with any topology can be achieved by only using the links in a spanning tree of the topology when the message size is sufficiently large. The result implies that increasing network connectivity beyond the minimum tree connectivity does not improve the performance of the all-to-all broadcast operation when the most efficient topology specific algorithm is used. All-to-all broadcast algorithms that achieve near-optimal performance are developed for clusters with cut-through and clusters with store-and-forward switches. We evaluate the algorithms through experiments and simulations. The empirical results confirm our theoretical finding.     

Building an IP-based community wireless mesh network: Assessment of PACMAN as an IP address autoconfiguration protocol

Wireless mesh networks are experiencing rapid progress and inspiring numerous applications in different scenarios, due to features such as autoconfiguration, self-healing, connectivity coverage extension and support for dynamic topologies. These particular characteristics make wireless mesh networks an appropriate architectural basis for the design of easy-to-deploy community or neighbourhood networks. One of the main challenges in building a community network using mesh networks is the minimisation of user intervention in the IP address configuration of the network nodes. In this paper we first consider the process of building an IP-based mesh network using typical residential routers, exploring the options for the configuration of their wireless interfaces. Then we focus on IP address autoconfiguration, identifying the specific requirements for community mesh networks and analysing the applicability of existing solutions. As a result of that analysis, we select PACMAN, an efficient distributed address autoconfiguration mechanism originally designed for ad-hoc networks, and we perform an experimental study – using off-the-shelf routers and assuming worst-case scenarios – analysing its behaviour as an IP address autoconfiguration mechanism for community wireless mesh networks. The results of the conducted assessment show that PACMAN meets all the identified requirements of the community scenario.     

移动自组网中一种网络生存时间最优的广播算法

移动自组网中广播操作的网络生存时间问题一直是备受关注的热点研究问题.现有的研究已经证明,基于最小生成树算法的广播算法能够最优地解决网络生存时间问题.但是,这些研究工作都是基于静止的网络拓扑,从而不适用于一些实际的网络拓扑动态变化的应用场景,如军事通信应用等.因此,针对节点移动导致的网络拓扑变化的场景,本文提出了一种移动...     

一类层次双环网络的构造及其路由算法

高效互联网络的拓扑结构一直是人们关注的热点问题。提出了一类层次双环互联网络HDRN（k）,给出了HDRN（k）网络的构造方法,研究了它的性质,并且通过与相关网络的比较,证实了HDRN（k）具有好的连接性、短的直径以及简单的拓扑结构,是一种实用的互联网络。另外,讨论了HDRN（k）网络的路由性质,设计了点点路由和Broadcast路由算法,证明了这两种路由算法的通信效率与层次环网络上对应算法的通信效率相比均有明显的提高。综上所述,HDRN（k）是一种具有良好拓扑性质的新型互联网络。     

二进制递归网络的连通性

二进制递归网络是超立方体的一类特殊变体,它具有很多良好的网络特性。网络的连通性是衡量网络结构通信能力的一个重要性能,虽然到目前为止已知的一些二进制递归网 络的连通性都已被研究过,但这些研究只是针对个体进行的,并不能代表所有二进制递归网络的连通特性。本文通过证明任何一个二进制递归网络中的每对顶点之间只能存在在”条顶点不交路,得到了整个二进制递归网络的点和边连通度皆为”的重要结论。     

Traffic routing in a computer network

This paper presents a technique for tuning Decnet networks so as to minimize the average end-to-end packet delay for the entire network. It represent an adaptation of theoretical work on network flows to the realistic case of Decnet. Using this technique to configure hypothetical networks, it then discusses the behaviour of the Decnet routing algorithm with respect to network size, topological connectivity and traffic configuration.     

Scalable network-on-chip architecture for configurable neural networks

Providing highly flexible connectivity is a major architectural challenge for hardware implementation of reconfigurable neural networks. We perform an analytical evaluation and comparison of different configurable interconnect architectures (mesh NoC, tree, shared bus and point-to-point) emulating variants of two neural network topologies (having full and random configurable connectivity). We derive analytical expressions and asymptotic limits for performance (in terms of bandwidth) and cost (in terms of area and power) of the interconnect architectures considering three communication methods (unicast, multicast and broadcast). It is shown that multicast mesh NoC provides the highest performance/cost ratio and consequently it is the most suitable interconnect architecture for configurable neural network implementation. Routing table size requirements and their impact on scalability were analyzed. Modular hierarchical architecture based on multicast mesh NoC is proposed to allow large scale neural networks emulation. Simulation results successfully validate the analytical models and the asymptotic behavior of the network as a function of its size.     

基于秘密共享的无线传感器网络广播密钥分发协议

在无线传感器网络中,能量消耗主要集中在节点之间的通信上,节点计算所消耗的能量远小于通信所消耗的能量。由于无线传感器网络的"一对多"和"多对一"通信模式,广播是节约能量的主要通信方式。为了保证广播实体和消息的合法性和保密性,必须首先解决无线传感器网络广播密钥安全分发问题。本文在充分考虑无线传感器网络自身特点的基础上,基于Shamir的门限秘密共享方案,提出了椭圆曲线双线性对上的无线传感器网络广播密钥分发协议,并对其进行安全性和性能分析。分析发现,该协议不仅满足安全性要求,同时,能够适合无线传感器网络的特殊应用要求。     

Semantic partitioning of peer-to-peer search space

Peer-to-peer (P2P) networks are beginning to form the infrastructure of future applications. Computers are organized in P2P overlay networks to facilitate search queries with reasonable cost. So, scalability is a major aim in design of P2P networks. In this paper, to obtain a high factor of scalability, we partition network search space using a consistent static shared upper ontology. We name our approach semantic partition tree (SPT). All resources and queries are annotated using the upper ontology and queries are semantically routed in the overlay network. Also, each node indexes addresses of other nodes that possess contents expressible by the concept it maintains. So, our approach can be conceived as an ontology-based distributed hash table (DHT). Also, we introduce a lookup service for the network which is very scalable and independent of the network size and just depends on depth of the ontology tree. Further, we introduce a broadcast algorithm on the network. We present worst case analysis of both lookup and broadcast algorithms and measure their performance using simulation. The results show that our scheme is highly scalable and can be used in real P2P applications.     

Connectivity and concentration in airline networks: a complexity analysis of Lufthansa's network

Information, communication and transport networks have always been in a state of flux, while they also influence each other. Extensive research efforts have been made to investigate the dynamics in the structure and use of networks, for example, by means of network geometries, Small-World effects and Scale-Free phenomena. We will illustrate these new developments on the basis of airline network evolution. Using Lufthansa's networks as an example, this paper aims to show the empirical relevance of various network indicators – such as connectivity and concentration – for understanding changing patterns in airline network configurations. After an extensive discussion of various statistical results, a decision-aid method, viz. multi-criteria analysis, is used to investigate the robustness of our findings. The results highlight the actual strategic choices made by Lufthansa for its own network, as well in combination with its partners in Star Alliance.     

Self-organized synchronous oscillations in a network of excitable cells coupled by gap junctions

Recent evidence suggests that electrical coupling plays a role in generating oscillatory behaviour in networks of neurons; however, the underlying mechanisms have not been identified. Using a cellular automata model proposed by Traub et al (Traub R D, Schmitz D, Jefferys J G and Draguhn A 1999 High-frequency population oscillations are predicted to occur in hippocampal pyramidal neural networks interconnected by axo-axonal gap junctions Neuroscience 92 407-26), we describe a novel mechanism for self-organized oscillations in networks that have strong, sparse random electrical coupling via gap junctions. The network activity is generated by random spontaneous activity that is moulded into regular population oscillations by the propagation of activity through the network. We explain how this activity gives rise to particular dependences of mean oscillation frequency on network connectivity parameters and on the rate of spontaneous activity, and we derive analytical expressions to approximate the mean frequency and variance of the oscillations. In doing so, we provide insight into possible mechanisms for frequency control and modulation in networks of neurons.     

An enhanced framework for providing multimedia broadcast/multicast service over heterogeneous networks

Multimedia broadcast multicast service （MBMS） with inherently low requirement for network resources has been proposed as a candidate solution for using such resources in a more efficient manner. On the other hand, the Next Generation Mobile Network （NGMN） combines multiple radio access technologies （RATs） to optimize overall network performance. Handover performance is becoming a vital indicator of the quality experience of mobile user equipment （UE）. In contrast to the conventional vertical handover issue, the problem we are facing is how to seamlessly transmit broadcast/multicast sessions among heterogeneous networks. In this paper, we propose a new network entity, media independent broadcast multicast service center （MIBM-SC）, to provide seamless handover for broadcast/multicast sessions over heterogeneous networks, by extensions and enhancements of MBMS and media independent information service （MIIS） architectures. Additionally, a network selection scheme and a cell transmission mode selection scheme are proposed for selecting the best target network and best transmission mode. Both schemes are based on a load-aware network capacity estimation algorithm. Simulation results show that the pro- posed approach has the capability to provide MBMS over heterogeneous networks, with improved handover performance in terms of packet loss rate, throughput, handover delay, cell load, bandwidth usage, and the peak signal-to-noise ratio （PSNR）.     

一种基于局部连通性的增强型车载网多跳广播协议

在车载网中,许多应用都依赖于可靠高效的消息广播。由于无线信道共享介质的特性,消息广播不得不面临广播风暴问题。概率广播是一类能抑制广播风暴的简单有效的方法,然而车载网中除DV-CAST以外的概率广播协议均未考虑稀疏节点场景下的网络分割问题。在分析和验证DV-CAST协议固有缺点的基础上,借鉴其利用局部连通性进行转发决策的思想,提出了一种基于局部连通性的增强型多跳广播协议。实验表明,提出的协议能在稠密节点及稀疏节点场景中均取得较好的可靠性并具有较低开销。     

基于主从支配点的无线自组网络广播算法及优化

文中提出了一种分布式主从支配点广播算法，节点利用局部拓扑结构选择支配点并对其进行主从划分，只有主支配点才对广播报文进行转发，从支配点负责监测网络的覆盖情况，当发现有未被覆盖的邻居节点时它就自动转化为主支配点，这样不仅降低了转播节点的数目，而且能够保证对网络的完全覆盖．在此基础上文中又提出了自剪枝规则对广播算法进行优化，自剪枝规则不会影响网络的完全覆盖性，并且能够进一步消除冗余转播节点，提高广播算法的性能．文章对算法的的正确性和有效性进行了理论分析，并通过仿真对它们的性能进行了验证和对比，结果表明它们优于其它广播算法．     

Modeling and performance analysis of ad hoc broadcasting schemes

Broadcasting is a technique widely used for distributing control packets in ad hoc networks. The traditional flooding scheme has been proven to unnecessarily consume network capacity and may lead to severe packet collisions in high-density networks. New schemes have been proposed for alleviating this so-called broadcast storm problem and their efficiencies are usually analyzed and compared by ns-2 simulations. However, little work has been done on mathematical modeling and rigorous analysis. In this paper, we focus on two popular ad hoc broadcasting schemes and provide their detailed analysis in one-dimensional and two-dimensional ideal networks. The statistical results obtained have revealed new relationships between network parameters and the performance metrics. These results are useful for optimally setting network parameters in designing protocols. It is also expected that the analytical methods developed will lay a solid foundation for the development of mathematical models for other ad hoc broadcast and multicast schemes.