Channel Assignment Strategies for Multiradio Wireless Mesh Networks: Issues and Solutions

Next-generation wireless mobile communications will be driven by converged networks that integrate disparate technologies and services. The wireless mesh network is envisaged to be one of the key components in the converged networks of the future, providing flexible high- bandwidth wireless backhaul over large geographical areas. While single radio mesh nodes operating on a single channel suffer from capacity constraints, equipping mesh routers with multiple radios using multiple nonoverlap- ping channels can significantly alleviate the capacity problem and increase the aggregate bandwidth available to the network. However, the assignment of channels to the radio interfaces poses significant challenges. The goal of channel assignment algorithms in multiradio mesh networks is to minimize interference while improving the aggregate network capacity and maintaining the connectivity of the network. In this article we examine the unique constraints of channel assignment in wireless mesh networks and identify the key factors governing assignment schemes, with particular reference to interference, traffic patterns, and multipath connectivity. After presenting a taxonomy of existing channel assignment algorithms for WMNs, we describe a new channel assignment scheme called MesTiC, which incorporates the mesh traffic pattern together with connectivity issues in order to minimize interference in multi- radio mesh networks.     

The impact of IXPs on the AS-level topology structure of the Internet

The AS-level topology of the Internet has been quite a hot research topic in the last few years. However, only a small number of studies have been developed that give a structural interpretation of this graph. Such an interpretation is crucially important in order to test protocols and optimal routing algorithms, to design efficient networks, and for failure detection purposes. Moreover, most research does not highlight the role that IXPs have on the AS-level structure of the Internet, although their role is recognized as fundamental.The initial contribution of this study is an analysis of the most important AS-level topologies that are publicly found on the web and an analysis of the topology obtained when they are merged. We compiled structural information from this topology making considerable use of the k-core decomposition technique to delineate various particular classes of nodes. Next, we associated node properties with a reasonable modus operandi of the ASs on the Internet. The second contribution is a study of the impact that ASs connected to IXPs and BGP connections crossing IXPs have on the AS-level topology. To achieve this, we developed a procedure to gather reliable information related to IXPs and their participants.     

Team Automata for Security: – A Survey –

In [Kleijn, J., Team Automata for CSCW – A Survey –, Petri Net Technology for Communication-Based Systems—Advances in Petri Nets, LNCS 2472, Springer, 2003, 295–320], Kleijn presented a survey of the use of team automata for the specification and analysis of phenomena from the field of computer supported cooperative work, in particular notions related to groupware systems. In this paper we present a survey of the use of team automata for the specification and analysis of some issues from the field of security. In particular, we show how team automata can adequately be used to model and verify various access control policies, multicast/broadcast communication protocols, and general (cryptographic) communication protocols.     

Real-time applications in a CRMA network: a performance analysis

This paper analyses bandwidth allocation schemes for managing real-time applications (Variable Bit Rate video and voice) in a CRMA network. A methodology to compute the Quality of Service (QoS) experienced by variable bit rate (VBR) video and voice sources is proposed. As VBR video applications only tolerate extremely low packet loss rates (< 10⁻⁸), we need a computational approach to estimate very low tail probabilities. Studying the QoS with a simulation technique is not feasible, because computational costs make it almost impossible to estimate tail distribution probabilities lower than 10⁻²−10⁻³. Therefore, to achieve this target, we propose a model which represents a CRMA network's worst case behaviour (i.e. a scenario with maximum network congestion), and which can be solved analytically. By solving this model for different bandwidth allocation schemes, we can obtain the corresponding bounds on the QoS experienced by VBR video users. Finally, for those bandwidth allocation schemes which provide an acceptable QoS for VBR video traffic, we also estimate (via a trace-driven simulation) the QoS achieved by voice users.     

A genetic approach to joint routing and link scheduling for wireless mesh networks

Wireless mesh networks are an attractive technology for providing broadband connectivity to mobile clients who are just on the edge of wired networks, and also for building self-organized networks in places where wired infrastructures are not available or not deemed to be worth deploying. This paper investigates the joint link scheduling and routing issues involved in the delivery of a given backlog from any node of a wireless mesh network towards a specific node (which acts as a gateway), within a given deadline. Scheduling and routing are assumed to be aware of the physical interference among nodes, which is modeled in the paper by means of a signal-to-interference ratio. Firstly, we present a theoretical model which allows us to formulate the task of deriving joint routing and scheduling as an integer linear programming problem. Secondly, since the problem cannot be dealt with using exact methods, we propose and use a technique based on genetic algorithms. To the best of our knowledge, these algorithms have never been used before for working out these kinds of optimization problems in a wireless mesh environment. We show that our technique is suitable for this purpose as it provides a good trade-off between fast computation and the overall goodness of the solution found. Our experience has in fact shown that genetic algorithms would seem to be quite promising for solving more complex models than the one dealt with in this paper, such as those including multiple flows and multi-radio multi-channels.     

On the approximation of the slot occupancy pattern in a DQDB network

This paper presents a novel approach to DQDB modeling in underload conditions; the innovative aspect lies in the representation of the slot-occupancy-pattern process on the forward bus. In the literature this process has been often modeled as a Bernoulli process, implying that the status (empty/busy) of consecutive slots are independent. Results presented in this paper, however, show that even at light loads the interdependence between slots is significant. Our model captures some of this interdependence by using a discrete-time first-order Markov process for the slot-occupancy-pattern process on the forward bus. In the paper we identify a simplified DQDB network for which we derive a closed formula for the joint probability density function for the slot occupancy pattern of two consecutive slots. The accuracy of our results is investigated via simulation. Finally, an application of our first-order Markov model is shown through an investigation of the performance of a gateway concentrating several DQDB networks in a slotted trunk.     

Optimal joint routing and link scheduling for real-time traffic in TDMA Wireless Mesh Networks

We investigate the problem of joint routing and link scheduling in Time-Division Multiple Access (TDMA) Wireless Mesh Networks (WMNs) carrying real-time traffic. We propose a framework that always computes a feasible solution (i.e. a set of paths and link activations) if there exists one, by optimally solving a mixed integer-nonlinear problem. Such solution can be computed in minutes or tens thereof for e.g. grids of up to 4 × 4 nodes. We also propose heuristics based on Lagrangian decomposition to compute suboptimal solutions considerably faster and/or for larger WMNs, up to about 50 nodes. We show that the heuristic solutions are near-optimal, and we exploit them to gain insight on the schedulability in WMN, i.e. to investigate the optimal placement of one or more gateways from a delay bound perspective, and to investigate how the schedulability is affected by the transmission range.     

k-Dense communities in the Internet AS-level topology graph

In this paper we investigate the structure of the Internet by exploiting an efficient algorithm for extracting k-dense communities from the Internet AS-level topology graph. The analyses showed that the most well-connected communities consist of a small number of ASs characterized by a high level of clusterization, although they tend to direct a lot of their connections to ASs outside the community. In addition these communities are mainly composed of ASs that participate at the Internet Exchange Points (IXPs) and have a worldwide geographical scope. Regarding k-max-dense ASs we found that they play a primary role in the Internet connectivity since they are involved in a huge number of Internet connections (42% of Internet connections). We also investigated the properties of three classes of k-max-dense ASs: Content Delivery Networks, Internet Backbone Providers and Tier-1s. Specifically, we showed that CDNs and IBPs heavily exploit IXPs by participating in many of them and connecting to many IXP participant ASs. On the other hand, we found that a high percentage of connections originated by Tier-1 ASs are likely to involve national ASs which do not participate at IXPs.     

Coordination problem in cognitive wireless mesh networks

Due to their potential to create and extend pervasive communication applications to cognitive environments with distributed control, the emerging technology of cognitive wireless mesh networks is gaining significant attention from a growing research community. However, the major challenge in cognitive networks is the adaptation to time and space variability of the available resources, namely chunks of the frequency spectrum called channels. In particular, this problem is exacerbated in cognitive mesh networks because there exists no direct communication among devices which thereby cannot establish a global (common) control channel to coordinate the entire network. Instead, only local control channels that vary depending on the time instant and location, can be established to coordinate cognitive devices among themselves. This paper first analyzes the underlying challenges and existing approaches to address the absence of a static and global control channel, and then propose a novel Control channel formation protocol, called Connor. Our protocol Connor is a fully distributed coordination scheme where cognitive mesh devices self-organize into clusters based on the similarity of available channels and on topological constraints. Compared with the existing clustering algorithms, which requires synchronization, the proposed Connor performs better in most cases without imposing synchronization.     

HIPERLAN/1 MAC protocol: stability and performance analysis

HIPERLAN Type 1 is a standard for high-speed wireless local area networks, developed by the European Telecommunications Standards Institute (ETSI). It supports directed point-to-point communication based on ad hoc network topology at a data transfer rate on the air interface of 23.5 Mbit/s. The paper deals with an analytical and simulation analysis of the HIPERLAN/1 MAC protocol. General closed formulas are derived for the major channel access performance indexes, which are used both to prove the operational stability of the MAC protocol, and to derive a figure for the maximum channel utilization achievable. A simulation analysis is then carried out, focusing both on the influence of traffic burstiness on protocol performance, and on the capability to manage traffic classes with different quality of service (QoS) requirements. Simulation results show that HIPERLAN/1 is well suited for managing the bursty traffic that is expected to be generated by wireless LAN applications. Furthermore, HIPERLAN/1 provides a good isolation of the delay-sensitive traffic from the best effort traffic