Computer Networks 54 (2010) 879–880
Contents lists available at ScienceDirect
Computer Networks journal homepage: www.elsevier.com/locate/comnet
Guest Editorial
Special issue on ‘‘New Network Paradigms” During the last few years we have witnessed an explosion in networking research that makes use of methodologies, paradigms, and models that come from disparate areas of science. There is a variety of reasons for this. In many cases, such as in research in wireless sensor networks, the network is expected to consist of a large number of interacting nodes. This suggests making simplifications in the description of network operation in terms of macroscopic quantities, such as node density and traffic flow, instead of the usual microscopic ones, such as the data arrival rate and the location of a particular node. Some specific disciplines that are well adapted to exploit this different approach are statistical mechanics of complex systems and population dynamics in biology. In addition to common tools, there are also several features and problems that arise both in biology and network engineering. The decentralized nature of the system, the many energy issues related to autonomous architecture, mobility, and self organization. In particular, there is much we can learn from the mathematical theory of the spread of epidemics, which is relevant to both the dissemination of information in networks and the spread of computer viruses. The need for decentralized decision making in networks calls for methodologies from game theory which until recently had only a marginal application in networking. This special issue of Computer Networks focuses on applying some of the above as well as of some other paradigms to specific networking problems. Some papers are not only useful and innovative in the context of communications networks, but make important contributions in the original scientific fields themselves. In many ways, this special issue is based on the belief that this cross-fertilization of ideas and methods can be a catalyst for progress in all associated scientific fields. The issue starts with two survey papers focusing on bio-inspired research in computer networking. The first survey, by Falko Dressler and Ozgur B. Akan, summarizes the similarities between biological systems and systems encountered in networking. It then presents biological models inspiring communication network design followed by a large number of bio-inspired approaches related to networking. The second survey, by Michael Meisel, Vasileios Pappas, and Lixia Zhang, discusses in depth why biology is an 1389-1286/$ - see front matter Ó 2010 Elsevier B.V. All rights reserved. doi:10.1016/j.comnet.2010.01.002
appealing and appropriate place to find inspiration for computer networking research. In contrast with the first survey, this paper focuses on some central research areas that not only are bio-inspired but also have similarities with biological systems. The survey covers routing methodologies inspired by the behavior of social insects, intrusion and misbehavior detection inspired by the immune system, network services modelled on the interactions and evolution of populations of organisms and research that applies techniques from epidemiology. In recent years, statistical-physics-inspired ideas have been introduced to networking and communications. For example, the field of CDMA multiuser detection has seen a flurry of progress based on the so-called replica method, including groundbreaking work by Toshiyuki Tanaka. The third paper in this issue is contributed by this author together with Koichiro Kitagawa, who applies this method to the problem of the optimization of CDMA sequences for overloaded systems with arbitrary inputs. Interestingly, they find that the so-called ‘‘Welch bound equality” spreading sequences are indeed optimal. Very different aspects of wireless networking are the subject of the fourth paper that studies spectrum allocation in the context of Cognitive Radio by Yuedong Xu, John C.S. Liu, and Dah-Ming Chiu. In order to model decision making in a distributed and decentralized context, game theory is used and a Nash equilibrium is sought. Several algorithms are proposed for dynamic convergence, some of which are shown to converge whereas others are shown to result in chaotic behaviour. Daniele Miorandi, Lidia Yamamoto, and Francesco de Pellegrini provide a survey entitled ‘‘Evolutionary and Embryogenic Approaches to Autonomic Networking”. Examining network-level software systems capable of self-management, they present a review of the state-ofthe art in techniques for the automated creation and evolution of software, with application to network-level functionalities. Focusing on biologically inspired techniques, their survey covers Evolutionary Computing and Chemical Computing, as well as approaches inspired by embryology, in which artificial entities undergo a developmental process. The paper concludes with a forward looking view of the technical challenges to be faced when applying the surveyed techniques to autonomic systems.
880
Guest Editorial / Computer Networks 54 (2010) 879–880
The subject of how to simultaneously optimize a wireless sensor network for both maximum coverage and maximum lifetime is considered by Andreas Konstantinidis, Kun Yang, and Qingfu Zhang in the work titled ‘‘A MultiObjective Evolutionary Algorithm for the Deployment and Power Assignment Problem in Wireless Sensor Networks”. In contrast to the majority of studies which tackle these objectives individually, they use a multi-objective evolutionary algorithm to optimize decision variables, decomposing the problem into scalar sub-problems and utilising adaptive evolutionary operators. They find that in several network instances, a diverse set of high quality network designs can be found, which are superior to those found by state-of-the-art single objective algorithms, and facilitate the decision maker’s choice. In the work titled ‘‘Traceband: A Fast, Low Overhead and Accurate Tool for Available Bandwidth Monitoring,” Guerrero and Labrador present a method for performing Bandwidth Estimation (BE), using the theory of Hidden Markov Models (HMMs) to derive accurate models for the behavior of the links under investigation. Already available state-ofthe-art protocols, such as Spruce and Pathload, are more empirical in nature, whereas the use of HMMs is more systematic, therefore leading to noticeable improvements in terms of speed of convergence and overhead. This work advances the state-of-the-art significantly, as demonstrated by analysis, simulation, and experiment. The efficiency of this method opens the doors for the use of BE in areas outside its traditional domain of application. In the work titled ‘‘Signal Reconstruction in Sensor Networks with Flat and Clustered Topologies,” Nordio, Chiasserinni, and Muscariello study the problem of signal reconstruction in the context of wireless sensor networks. The unique conditions of sensor networks, notably their energy constraints, the need for multihop communication, the potential (or necessity) for clustering, and their distributed nature create a unique situation in which network theory and estimation theory are fused together by the authors in a very convincing way. The authors explore the various tradeoffs that exist, evaluating, among other topics, the advantages of using clustering versus a flat topology, and the effects of having information regarding the node locations at the fusion center. In the work titled ‘‘Continuum Equilibria for Routing in Dense Static Ad Hoc Networks,” Silva, Altman, Bernhard, and Debbah study massively dense networks, i.e., networks with so many nodes that a macroscopic view can be adopted. With this framework, microscopic details of the network such as the location of individual nodes is ignored, and the quantities on which optimization are performed are macroscopic ones, such as the node density and the flow of traffic as functions of the location. This approach allows the use of mathematical tools that are not common in networking, such as Partial Differential Equations and Optimal Control. In this context, various contributions are made: (a) the viscosity solution of the Hamilton–Jacobi–Bellman equation is given for a global optimization problem, (b) a method is given for solving the least-cost-problem of an individual, and, finally, (c) a
solution to the Wardrop equilibrium problem is given using a transformation into an equivalent global optimization problem. In the work ‘‘Overhead Reduction in Distributed Path Management System”, the authors (P.E. Heegaard and O.J. Wittner) present an ant-based system for path management in communication networks, able to perform adaptive multi-path load sharing and stochastic routing with fast restoration of link failures. In particular, the overhead generated by the path management system is analysed. Techniques for achieving an effective trade-off between management overhead (number of management packets) and path recovery times are introduced, and their performance is evaluated by means of numerical simulations. The techniques introduced are shown to provide a consistent overhead reduction without notably affecting the system’s performance, making ant-based path management systems a viable solution for large-scale dynamic networks. Finally, in the paper entitled ‘‘Sampling networks by the union of m shortest path trees”, the authors (H. Wang and P. Van Wieghem) address the problem of sampling bias emerging in network topology measurements. In particular, they propose a sampling approach that uses the union of a given number of shortest paths and propose a way to apply this method, in order to reduce this sampling bias. We wish to thank all the authors and referees for their contributions toward making this issue possible. We also thank the many authors of papers that we could not include in this issue. We thank in particular Harry Rudin who gave the authors and us valuable feedback on all the papers that appear in this special issue as well as on various papers that we have not been able to include. Guest Editors Eitan Altman INRIA, France E-mail address:
[email protected] Tamer Basßar UIUC, United States E-mail address:
[email protected] Emma Hart Edinburgh Napier University, United Kingdom E-mail address:
[email protected] Daniele Miorandi CREATE-NET, Italy E-mail address:
[email protected] Aris L. Moustakas National Kapodistrian University of Athens, Greece E-mail address:
[email protected] Stavros Toumpis Athens University of Economics and Business (AUEB), Greece E-mail address:
[email protected] Available online 6 January 2010
