A new scalable multicast routing algorithm for interactive real-time applications

Quality of service (QoS) provisioning generally assumes more than one QoS measure that implies that QoS routing can be categorized as an instance of routing subject to multiple constraints: delay jitter, bandwidth, cost, etc. We study the problem of constructing multicast trees to meet the QoS requirements of real-time interactive applications where it is necessary to provide bounded delays and bounded delay variation among the source and all destinations while keeping overall cost of the multicast tree low. The main contribution of our work is a new strategy for constructing multiconstrained multicast trees. We first derive mathematically a new delay-variation estimation scheme and prove its efficiency. Thereafter, we propose a simple and competitive (in terms of running time) heuristic algorithm, for delay and delay variation constrained routing problem based on the proposed delay-variation estimation scheme and using the Extended Prim-Dijkstra tradeoffs’ algorithm. Our contribution also extends previous works in providing some properties and analyses of delay bounded paths satisfying delay variation constraints. Extensive simulation results show that our algorithm outperforms DVDMR in terms of multicast delay variation with the same time complexity as DVDMR.     

A scalable framework for mobile real-time group communication services

A scalable framework for mobile real-time group communication services is developed in this paper. Examples for possible applications of this framework are mobile social networks, mobile conference calls, mobile instant messaging services, and mobile multi-player on-line games. A key requirement for enabling a real-time group communication service is the tight constraint imposed on the call delivery delay. Since establishing such communication service for a group of independent mobile users under a tight delay constraint is NP-hard, a two-tier architecture is proposed, that can meet the delay constraint imposed by the real-time service requirement for many independent mobile clients in a scalable manner. This goal is achieved by two dimensional partition of the space, first by organization and then geographically. Both the time and memory complexity associated with the location management of N mobile users are O(N) for the location management provided by the proposed framework, while a distributed scheme requires O(N²) for both time and memory complexity.     

An efficient anonymous authentication protocol in multiple server communication networks (EAAM)

In a multi-server authentication environment, a user only needs to register once at a central registration place before accessing the different services on the different registered servers. Both, from a user point of view as for the management and maintenance of the infrastructure, these types of environments become more and more popular. Smartcard- or smartphone-based approaches lead to more secure systems because they offer two- or three-factor authentication, based on the strict combination of the user’s password, the user’s biometrics and the possession of the device. In this paper, we propose an efficient anonymous authentication protocol in multiple server communication networks, called the EAAM protocol, which is able to establish user anonymity, mutual authentication, and resistance against known security attacks. The novelty of the proposed scheme is that it does not require a secure channel during the registration between the user and the registration center and is resistant to a curious but honest registration system. These features are established in a highly efficient way with the minimum amount of communication flows between user and server during the establishment of the secret shared key and by using light-weight cryptographic techniques such as Chebyshev chaotic map techniques and symmetric key cryptography. The performance and security of the protocol are analyzed and compared with the latest new proposals in this field.     

SoMR: A scalable distributed QoS multicast routing protocol

Many Internet multicast applications such as teleconferencing and remote diagnosis have Quality-of-Service (QoS) requirements. The requirements can be additive (end-to-end delay), multiplicative (loss rate), or of a bottleneck nature (bandwidth). Given such diverse requirements, it is a challenging task to build QoS-constrained multicast trees in a large network where no global network state is available. This paper proposes a scalable QoS multicast routing protocol (SoMR) that supports all three QoS requirement types. SoMR is scalable due to small communication overhead. It achieves favorable tradeoff between routing performance and routing overhead by carefully selecting the network sub-graph in which it searches for a path that can support the QoS requirements. The scope of search is automatically tuned based on the current network conditions. An early-warning mechanism helps detect and route around the long-delay paths in the network. The operations of SoMR are completely decentralized. They rely only on the local state stored at each router.     

M2ASR——新型多径匿名源路由协议*

针对无线Ad hoc网络通信的安全与效率问题,提出一个高效并有较好匿名能力的多径匿名源路由协议M2ASR。在DSR协议的基础上,使用标签机制,对源路由的工作过程进行了修改,实现了能够应用于大规模无线网络的多径匿名路由;并在协议中首次使用IDA算法,利用Ad hoc网络的节点转发和协议本身提供的多径性质,提高了无线Ad hoc的通信效率;从理论和仿真角度对M2ASR协议的匿名性和使用IDA算法之后所带来的效率进行了分析和总结。     

知性Cord逻辑:验证Ad Hoc网络匿名路由协议

为形式化验证移动自主网的匿名路由协议,提出了基于知性Cord逻辑的模块化验证方法.首先将协议分解为针对不同子安全功能的组件,然后分别利用知性Cord逻辑证明是否满足安全属性的规范.在这个框架下路径匿名的安全属性得到了规范.     

LRTWR：区域实时车流量感知路由协议

城市环境下,车载自组网路由协议性能受交通车流量变化的影响,如何有效分析车流量与通信质量的关系是提高路由性能的关键,基于交通流量-时延模型,提出区域实时车流量感知路由协议（LRTWR）。该协议通过在路口设置RSU节点,统计区域范围内车流量变化,并以此建立区域时延模型,选择具有最小时延的传播路径,并通过贪婪转发和携带转发来完成路段内转发。实验结果表明,该协议在城市环境下,使车载自组网在不同交通状况下都能保持较低的丢包率和端到端时延。     

KNEM: A generic and scalable kernel-assisted intra-node MPI communication framework

The multiplication of cores in today’s architectures raises the importance of intra-node communication in modern clusters and their impact on the overall parallel application performance. Although several proposals focused on this issue in the past, there is still a need for a portable and hardware-independent solution that addresses the requirements of both point-to-point and collective MPIoperations inside shared-memory computing nodes.     

CuNoC: A dynamic scalable communication structure for dynamically reconfigurable FPGAs

The growing complexity of integrated circuits imposes to the designers to change and direct the traditional bus-based design concepts towards NoC-based. Networks on-chip (NoCs) are emerging as a viable solution to the existing interconnection architectures which are especially characterized by high level of parallelism, high performances and scalability. The already proposed NoC architectures in the literature are destined to System-on-chip (SoCs) designs. For a FPGA-based system, in order to take all benefits from this technology, the proposed NoCs are not suitable. In this paper, we present a new paradigm called CuNoC for intercommunication between modules dynamically placed on a chip for the FPGA-based reconfigurable devices. The CuNoC is based on a scalable communication unit characterized by unique architecture, arbitration policy base on the priority-to-the-right rule and modified XY adaptive routing algorithm. The CuNoC is namely adapted and suited to the FPGA-based reconfigurable devices but it can be also adapted with small modifications to all other systems which need an efficient communication medium. We present the basic concept of this communication approach, its main advantages and drawbacks with regards to the other main already proposed NoC approaches and we prove its feasibility on examples through the simulations. Performance evaluation and implementation results are also given.     

Modeling real-time communication systems: Practices and experiences in Motorola

Visual modeling languages and techniques have been increasingly adopted for software specification, design, development, and testing. With the major improvements of UML 2.0 and tools support, visual modeling technologies have significant potential for simplifying design, facilitating collaborations, and reducing development cost. In this paper, we describe our practices and experiences of applying visual modeling techniques to the design and development of real-time wireless communication systems within Motorola. A model-driven engineering approach of integrating visual modeling with development and validation is described. Results, issues, and our viewpoints are also discussed.     

CARRADS: Cross layer based adaptive real-time routing attack detection system for MANETS

Routing behavior in ad hoc networks is highly transient. Thus, dynamically adapting the routing attack detection system at real-time to new attacks and changing network conditions is critical in ad hoc networks. Conventional incremental learning methods are computationally expensive for resource-constrained nodes in ad hoc networks. In this paper, we propose CARRADS, a computationally efficient methodology for adapting the intrusion detection model at real-time. The adaptation process consists of two major stages. In the first stage, the main task is to identify occurrence of new patterns in the routing control traffic and prioritize them based on their information content. The second stage of adaptation is to incrementally update the detection model using the new patterns with minimum computational overhead. CARRADS uses SVM algorithm for its superior detection abilities. However, using some innovative techniques the computational overhead of incremental update is reduced by a factor of 20 to 30 times at the cost of a negligible decrease in detection accuracy. This makes CARRADS a viable approach for real-time IDS in ad hoc networks.     

Dynamic routing of real-time jobs among parallel EDF queues: A performance study

This paper introduces an analytical method for approximating the performance of a firm real-time system consisting of a number of parallel infinite-capacity single-server queues. The service discipline for the individual queues is earliest-deadline-first (EDF). Real-time jobs with exponentially distributed relative deadlines arrive according to a Poisson process. Jobs either all have deadlines until the beginning of service or deadlines until the end of service. Upon arrival, a job joins a queue according to a state-dependent stationary policy, where the state of the system is the number of jobs in each queue. Migration among the queues is not allowed. An important performance measure to consider is the overall loss probability of the system. The system is approximated by a Markovian model in the long run. The resulting model can then be solved analytically using standard Markovian solution techniques. Comparing numerical and simulation results for at least three different stationary policies, we find that the existing errors are relatively small.     

O(n) routing in rearrangeable networks

In (2n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω(n²) compared to its propagation delay O(n) only. Here, we attempt to identify the sets of permutations, which are routable in O(n) time in these networks. We define four classes of self-routable permutations for Benes network. An O(n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O(n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent.     

Next Branch Multicast (NBM) routing protocol

It is well known that IP multicast suffers from deployment issues. The problem mainly originates from the multicast routing complexities in the inter-domain level and state-full nature of current solutions. To cope with the problem, many alternative group communication methods have been proposed. Among them, branching point (BP) based approaches have promising features like incremental deployment, high tree availability, low memory requirement and, hence, high scalability. However, current BP-based methods suffer from two major inefficiencies namely the tree construction difficulties and presence of excessive lookups in the forwarding process of unicast and multicast data packets. We propose a new BP-based protocol named NBM (Next Branch Multicast) to avoid the existing drawbacks. NBM constructs the multicast distribution tree in the forward direction and has a fault-detection and repair mechanism which protects the tree against BPs failures. NBM detects the failure of a higher level BP in the tree sooner than a lower level BP. NBM does not maintain any type of control state in non-branching routers. Our simulation results show that NBM memory requirement for maintaining multicast forwarding states is approximately less than half when compared to the traditional approach. In addition, the NBM tree is more available than the traditional one at least by a factor of 2.     

S2DIO: an extended scalable 2D mesh network-on-chip routing reconfiguration for efficient bypass of link failures

The Journal of Supercomputing - The paradigm of computing has shifted from computation-centric to communication-centric designs. Network-on-chip has emerged as an alternative interconnect mechanism...     

Dynamic Routing System (DRS): fault tolerance in network routing

We present a novel proactive routing algorithm that continuously searches for failures via frequent ICMP echo requests. Our approach differs from its predecessors in that it is proactive instead of reactive. That is, we continuously search for failures before they affect message transmissions. When a failure is detected, an alternative route is identified and used. The Dynamic Routing System (DRS) is currently deployed commercially by one of the top-three United States telecommunications companies in over 27 major cities nationwide. In production use, the use of DRS has improved availability by 13%.     

Multi-hop cellular networks: Architecture and protocols for best-effort and real-time communication

Until recently, research on cellular networks concentrated only in single-hop cellular networks. The demand for high throughput has driven to architectures that use multiple hops in the presence of infrastructure. We propose an architecture for multihop cellular networks (MCNs). MCNs combine the benefits of having a fixed infrastructure of base stations and the flexibility of Ad hoc networks. They are capable of achieving much higher throughput than current cellular systems, which can be classified as single-hop cellular networks (SCNs). In this work, we propose an extended architecture for MCN using the IEEE 802.11 standard for wireless LANs for connection-less service and a TDMA-based solution for real-time support. We provide a general overview of the architecture and the issues involved in the design of MCNs, in particular the challenges to be met in the design of a routing protocol, a channel assignment scheme, and a mobility management scheme. We also propose a routing protocol called Base-Assisted Ad hoc Routing (BAAR) protocol for use in such networks and a model for the performance analysis of MCNs and SCNs. We also conduct extensive experimental studies on the performance of MCNs and SCNs under various load (TCP, UDP, and real-time sessions) and mobility conditions. These studies clearly indicate that MCNs with the proposed architecture and routing protocol are viable alternatives for SCNs, in fact they provide much higher throughput. MCNs are very attractive for best-effort packet radio where they can achieve an increase in throughput up to four when compared to similar SCNs. But for real-time traffic, even though they do outperform SCNs, they also suffer from a few disadvantages such as frequent hand-offs and throughput degradation at high mobility. We also present results from a detailed comparison study of our architecture for MCN with the Hybrid Wireless Network (HWN) architecture and Integrated Cellular Ad hoc Relaying (iCAR) Architecture.     

Promondia: a Java-based framework for real-time group communication in the Web

The World Wide Web has evolved from a distributed hypertext system to a platform-independent graphical user interface that integrates many network services. So far, its technology has restricted it mainly to applications for information retrieval.As networks become ubiquitious and more and more users have a permanent connection, there is an increasing demand for other network services, such as real-time data feeds, group communication, and teleconferencing. So far, these services have been provided by various proprietary software systems, which were hard to set up and use, and thus not very successful.Integrating real-time group communication services into the World Wide Web is a natural way to make them more accessible and will take the Web a step further on its way to becoming the universal network application.In this paper, we describe functionalities required for these services and present an implementation based on Sun Microsystem's Java² programming language. We focus on the high-level functionalities and abstractions, but also describe an object-oriented programming model for group communication systems.