Special issue: New technologies in distributed systems

Vol. 61, n° 11-12, November-December 2006
Content available on Springerlink

Guest editors
Kamel Adi, Université du Québec en Outaouais, Canada
Daniel Amyot, University of Ottawa, Canada
Luigi Logrippo, Université du Québec en Outaouais, Canada


Kamel Adi, Daniel Amyot, Luigi Logrippo

BALLS: a structured peer-to-peer system with integrated load balancing

Viet Dung LE*, Gilbert BABIN**, Peter KROPF***

* Département d’informatique et de recherche opérationnelle – Université de Montréal ; C.P. 6128, Succursale Centre-Ville, Montréal, (Québec) Canada H3C 3J7
** Technologies de l’information, HEC Montréal – 3000, ch. de la Côte-Sainte-Catherine, Montréal (Québec) Canada H3T 2A7
*** Institut d’informatique, Université de Neuchâtel – Rue Emile Argand 11, CH 2009 Neuchâtel, Switzerland

Abstract Load balancing is an important problem for structured peer-to-peer systems. We are particularly interested in the consumption of network bandwidth for routing traffic and in the usage of computer resources for object storage. In this paper, we investigate the possibility to simultaneously balance these two types of load. We present a structured peer-to-peer overlay that efficiently performs such simultaneous load balancing. The overlay is constructed by partitioning the nodes of a de Bruijn graph and by allocating the partitions to the peers. Peers balance network bandwidth consumption by repartitioning the nodes. Balancing of computer resources for storage is enabled by dissociating the actual storage location of an object from the location of its search key. The paper presents and analyzes the protocols required to maintain the overlay structure and perform load balancing. We demonstrate their efficiency by simulation. We also compare our proposed overlay network with other approaches.

Keywords Networking, Peer to peer networking, Balancing, Network routing, Distributed system, Resource sharing

Solution for gateway selection in ad hoc networks

Kaouthar SETHOM*, Olfa HAMZA*, Hossam AFIFI*, Guy PUJOLLE**

* GET/INT – 9, rue Charles Fourier, 91011 Evry Cedex, France
** LIP6, UPMC – 8, rue du Capitaine Scott, 75015 Paris, France

Abstract In the past few years, Internet has raised increasing interest in various areas including research, education, and business. The number of people accessing the Internet at work or at home has increased considerably, just like the number of services offered (email, e-commerce, search engines, e-learning, e-government, etc.). Ad hoc networks were generally viewed as stand-alone networks, where communications are only supported between nodes in the network such as in military and rescue operations. The lack of connectivity to the wired infrastructure enables simple management and deployment, but limits the applicability of ad hoc networks to today’s scenarios, which require connectivity outside the ad hoc network and particularly to the Internet. However, to reach this goal, a number of problems need to be resolved because of the dynamic nature of such environment. In this article, we describe a new solution for dynamic gateway selection based on quality of service (QoS) criteria. The underlying architecture is based on a pro-active routing protocol.

Keywords Radiocommunication, Ad hoc network, Internet, Network routing, Network gateway.

Rogue-base station detection in WiMax/802.16 wireless access networks

Michel BARBEAU*, Jean-Marc ROBERT**

* School of Computer Science, Carleton University – 1125 Colonel By Drive, Ottawa, ON, Canada K1S 5B6
** Alcatel, CTO Security Research and Competence Center – 600 March Rd., Ottawa, ON, Canada K2K 2E6;

Abstract We address the problem of detecting a rogue base station (BS) in WiMax/802.16 wireless access networks. A rogue BS is a malicious station that impersonates a legitimate access point (AP). The rogue BS attack represents a major denial-of-service threat against wireless networks. Our approach is based on the observation that inconsistencies in the signal strength reports received by the mobile stations (MSs) can be seen if a rogue BS is present in a network. These reports can be assessed by the legitimate base stations, for instance, when a mobile station undertakes a handover towards another BS. Novel algorithms for detecting violations of received signal strength reports consistency are described in this paper. These algorithms can be used by an intrusion detection system localized on the legitimate BSs or on a global network management system operating the BSs.

Keywords Mobile radiocommunication, Access network, Wireless local loop, Base station, Communication security.

Timed secure colored Petri net based analysis of information flow


Department of Computer Engineering, École Polytechnique de Montréal, P.O. Box 6079, Station Centre-ville, Montréal, Québec;

Abstract: We present in this paper a novel framework named Timed Secure Colored Petri Net (TSCPN) to carry out security verification in a formal and systematic manner. TSCPN is a security policy model to both express time constraints on information (availability) and specify a wide range of information flow security requirements (through multilevel security policies such as Bell-LaPadula) in a decentralized way. We also propose a suitable analysis method to verify security properties by constructing and examining the state space of the constructed model. However as timed models are generally infinite, applying this method must pass by contracting its state space into a finite graph (state class graph) preserving properties of interest. According to this graph, it is possible to verify confidentiality and integrity, enforce control on information flow security, specify temporal access control and information availability. By using this formal method, many security drawbacks can be eliminated in advance during the system design.

Keywords Petri net, Graph coloration, Communication security, State space method, Relaxation method, Information transfer, Time analysis, Formal method, Temporal logic.

A UML-based framework for distributed system design

Ludovic APVRILLE1, Pierre de SAQUI-SANNES2,3 Renaud PACALET1, Axelle APVRILLE4

1. GET/Télécom Paris, Laboratoire System-On-Chip, 2229 routes des crêtes, B.P. 193, 06904 Sophia-Antipolis Cedex, France
2. LAAS-CNRS, 7 avenue du Colonel Roche – 31077 Toulouse Cedex 4, France.
3. ENSICA, 1 place Emile Blouin, 31056 Toulouse Cedex 5, France, desaqui  at ensica.fr.
4. MISC Magazine, Éditions Diamond, BP 20142, 67603 Célestat cedex, France ; axellec  at miscmag.com

Abstract This paper introduces a new environment for developing distributed systems. It is based on the TURTLE UML profile. Analysis and design phases, described in previous papers, have been extended with an additional deployment phase. In this new step, TURTLE components are deployed over hardware execution nodes, and nodes are connected together throughout links. TURTLE deployment diagrams are given a formal semantics in RT-LOTOS, therefore following the approach used for TURTLE analysis and design diagrams. Moreover, the paper presents a Java code generator which outputs appropriate Java code for TURTLE deployment diagrams. This code is automatically deployable on networks because it implements node communication using network protocols such as UDP or RMI. TTool, the TURTLE toolkit has been extended to support these new diagrams and code generators. The attack of protected data exchanged throughout secured HTTP sessions serves as example.

Keywords Distributed system, System design, Formal method, System description, UML, Semantics, Programming, Internet security, Computer deployment.

Platform for the cooperative context-aware deployment


* LAAS-CNRS, 7 avenue du Colonel Roche, 31077 Toulouse, France.

Abstract Application deployment in sessions composed of several users is now a hot topic. These users communicate together with heterogeneous terminals. Deployed applications on these nodes must fit to the execution environment and must be interoperable with applications already installed on the others nodes of the session. In this paper, we propose an architecture, which provides a user with missing applications according to the session requirements while respecting compatibility and interoperability constraints. This decentralized and distributed architecture is based on a context-aware deployment algorithm running on each node. After discovering applications scattered on a peer-to-peer network, the algorithm generates deployment configurations needed for any deployment node. Then, the algorithm performs the necessary downloads and instantiations. We present our context-aware deployment platform composed of generic modules. These modules include APIs to build deployment services according to this architecture.

Keywords Computer application, Cooperation, Interoperability, Network architecture, Peer to peer communication, Adaptive method, Ad hoc network, Computer deployment.

Open Topics

Simulated annealing method coupled with tabu search method for adaptive array antennas optimization problems

Fatima DEBBAT*, Fethi Tarik BENDIMERAD**

* Institut d’Informatique, Centre Universitaire Mustapha Stambouli de Mascara – BP 763, route de Mamounia, 29000 Mascala, Algérie
** Laboratoire de Télécommunications, Département d’Électronique, Faculté des Sciences de l’Ingénieur, Université Abou-Bekr Belkaid – BP 230, Pôle Chetouane, 13000 Tlemcen, Algérie

Abstract The increasing pollution of the electromagnetic environment has prompted the study of array pattern nulling techniques. These techniques are very important in radar, sonar and communication systems for minimising degradation in signal-to-noise ratio performance due to undesired interferences. Adaptive array antennas backed by strong signal processing algorithms are able to automatically change the beam pattern in accordance with the changing signal environment. It not only directs maximum radiation in the direction of the desired mobile user but also introduces nulls for interfering directions while tracking the desired mobile user at the same time. The adaptation is achieved by multiplying the incoming signals with complex weights and then summing them together to obtain the desired radiation pattern. Adaptive array optimization is an NP-hard problem. In this paper, a technique based on the coupling between tabu search and simulated annealing methods is presented to solve this problem. Several illustrative examples of patterns with imposed single and multiple null directions are given to show the versatility of the present method.

Keywords Antenna array, Linear antenna, Signal interference, Phased array electronically steerable antenna, Adaptive antenna, Radiation pattern, Optimization, Heuristic method, Simulated annealing, Adaptive algorithm, Tabu search.

Yield and reliability issues in nanoelectronic technologies


GET/Télécom Paris, CNRS LTCI (UMR 5141), Département Communication et Électronique. 75634 Paris Cedex 13, France

Abstract Integrated circuits have known a constant evolution in the last decades, with increases in density and speed that follow the rates predicted in Moore’s law. The tradeoffs in area, speed and power, allowed by the CMOS technology, and its capacity to integrate analog, digital and mixed components, are key features to its dissemination in the telecommunications field. In fact, the progress of the CMOS technology is an important driver for telecommunications evolution, with the continuous integration of complex functions needed by demanding applications. As integrated circuits evolve, they approach some limits that make further improvements more difficult and even unpredictable. With deep-submicron structures, the yield of manufacturing processes is one of the main challenges of the semiconductor industry, with negative impacts on time-to-market and profitability. With reduced voltages and increased speed and density, the reliability of deep-submicron circuits is another concern for designers, since noise immunity is reduced and thermal noise effects show-up. In this paper we present an overview of the issues related with the scaling of integrated circuits into nanometer technologies, detailing the yield and reliability problems. We present the state of the art in proposed solutions and alternatives that can improve the chances of a large utilization of these nanotechnologies.

Keywords Nanotechnology, CMOS, Microelectronic fabrication, Semiconductor technology, Integrated circuit, Yield, Reliability, Logic circuit, Fault tolerance system, System design, Reconfigurable circuit, State of the art.

Survey of software cache management for tolerating disconnections in mobile environments


GET/INT, CNRS Samovar, 9 rue Charles Fourier, 91011 Évry, France

Abstract Recent years have seen a rapid evolution in the hardware and in networks used in mobile computing environments. This evolution has opened up new opportunities for mobile computing. Mobile computing allows a mobile user to access various kinds of information any time anywhere. However, mobile computing raises the problem of data availability in the presence of disconnections. Thus, distributed applications and middleware in mobile environments must be adapted to cope with disconnections. In this article, we present a state of the art on software caching for tolerating disconnections in mobile environments. The structure of the article follows the type of entities manipulated by the distributed applications : ordinary files, databases, web pages, objects, and components.

Keywords Mobile radiocommunication, Automatic data processing, Cache, State of the art, Computer application, Adaptive system, Storage management, File management, Database, Mobile internet, Object oriented method, Software engineering.