Skip to main content
main-content

Über dieses Buch

Algorithmic discrete mathematics plays a key role in the development of information and communication technologies, and methods that arise in computer science, mathematics and operations research – in particular in algorithms, computational complexity, distributed computing and optimization – are vital to modern services such as mobile telephony, online banking and VoIP.

This book examines communication networking from a mathematical viewpoint. The contributing authors took part in the European COST action 293 – a four-year program of multidisciplinary research on this subject. In this book they offer introductory overviews and state-of-the-art assessments of current and future research in the fields of broadband, optical, wireless and ad hoc networks. Particular topics of interest are design, optimization, robustness and energy consumption.

The book will be of interest to graduate students, researchers and practitioners in the areas of networking, theoretical computer science, operations research, distributed computing and mathematics.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Graphs and Algorithms in Communication Networks on Seven League Boots

This chapter provides an introduction to the mathematical techniques used to provide insight and decision support in the design and operaton of communication networks. Techniques discussed include graph-theoretical concepts, (integer) linear programming, and complexity theory. To illustrate the importance of these techniques, classical applications in the area of communication networks are discussed. The wide variety and depth of the mathematics involved does not allow an exposition highlighting all details. References for further reading are provided. The chapter is closed with a brief description of the applications discussed in the consecutive chapters.
Arie M. C. A. Koster, Xavier Muñoz

Studies in Broadband and Optical Networks

Frontmatter

Chapter 2. Traffic Grooming: Combinatorial Results and Practical Resolutions

In an optical network using the wavelength division multiplexing (WDM) technology, routing a request consists of assigning it a route in the physical network and a wavelength. If each request uses 1/g of the bandwidth of the wavelength, we will say that the grooming factor is g. That means that on a given edge of the network we can groom (group) at most g requests on the same wavelength. With this constraint the objective can be either to minimize the number of wavelengths (related to the transmission cost) or minimize the number of Add/Drop Multiplexers (shortly ADM ) used in the network (related to the cost of the nodes).
Here, we first survey the main theoretical results obtained for different grooming factors on various topologies: complexity, (in)approximability, optimal constructions, approximation algorithms, heuristics, etc. Then, we give an ILP formulation for multilayer traffic grooming and present some experimental results.
Tibor Cinkler, David Coudert, Michele Flammini, Gianpiero Monaco, Luca Moscardelli, Xavier Muñoz, Ignasi Sau, Mordechai Shalom, Shmuel Zaks

Chapter 3. Branch-and-Cut Techniques for Solving Realistic Two-Layer Network Design Problems

We study a planning problem arising in SDH/WDM multilayer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation for a predefined set of admissible logical links that takes many practical side constraints into account, including node hardware, several bit rates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing, MIPbased heuristics, and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these ingredients can be very useful to reduce the optimality gaps in the multilayer context.
Sebastian Orlowski, Christian Raack, Arie M. C. A. Koster, Georg Baier, Thomas Engel, Pietro Belotti

Chapter 4. Routing and Label Space Reduction in Label Switching Networks

This chapter is devoted to the analysis and modeling of some problems related to the optimal usage of the label space in label switching networks. Label space problems concerning three different technologies and architectures – namely Multi-protocol Label Switching (MPLS), Ethernet VLAN-Label Switching (ELS) and All-Optical Label Switching (AOLS) – are discussed in this chapter. Each of these cases yields to different constraints of the general label space reduction problem. We propose a generic optimization model and, then, we describe some adaptations aiming at modeling each particular case. Simulation results are briefly discussed at the end of this chapter.
Fernando Solano, Luis Fernando Caro, Thomas Stidsen, Dimitri Papadimitriou

Chapter 5. Network Survivability: End-to-End Recovery Using Local Failure Information

This chapter presents an advanced shared protection approach called Failure Dependent Path Protection (FDPP). Under this approach, several protection paths can be assigned to connections in the context of a shared protection framework. After formalizing the survivable online routing problem, two possible implementations are compared, one based on heuristics and the other on ILP. Building upon the concepts of routing already exposed, the chapter then presents two case studies. The first one employs Shortcut Span Protection to examine how different protection strategies affect resource provisioning, while the second is a thorough analysis of the performance of path protection in terms of connection availability, both for dedicated and shared path protection in heterogeneous network topologies.
José L. Marzo, Thomas Stidsen, Sarah Ruepp, Eusebi Calle, Janos Tapolcai, Juan Segovia

Chapter 6. Routing Optimization in Optical Burst Switching Networks: a Multi-path Routing Approach

This chapter concerns routing optimization in optical burst switching (OBS) networks. OBS is a photonic network technology aiming at efficient transport of IP traffic. OBS architectures are in general bufferless and therefore sensitive to burst congestion. An overall burst loss probability (BLP) which adequately represents the congestion state of the entire network is the primary metric of interest in an OBS network. The network congestion can be reduced by using proper routing. We consider multi-path source routing and aim at optimal distribution of traffic over the network. In this context, we study three network loss models, a well-known loss model of an OBS network and two original approximate models. Since the objective function of each model is nonlinear, either linear programming formulations with piecewise linear approximations of this function or nonlinear optimization gradient methods can be used. The presented solution is based on nonlinear optimization; for this purpose we provide the formulas for calculation of partial derivatives. The main goal of this chapter is to show that the use of approximate models allows us to speed up significantly the optimization procedure without losing much accuracy. Moreover we show that our method effectively distributes the traffic over the network, and the overall BLP can be reduced compared with both shortest path routing and alternative routing.
Mirosław Klinkowski, Marian Marciniak, Michał Pióro

Chapter 7. Problems in Dynamic Bandwidth Allocation in Connection Oriented Networks

In this chapter, the analysis of the problems emerging from dynamic bandwidth allocation in connection-oriented packet networks is considered in a multilayer scenario, considering IP protocols on top of an MPLS network over an OBS optical network. The issue (and problem) is to maintain and ensure the end-to-end in-sequence routing of packets, combining load balancing in packet switching architectures and bandwidth/flow allocation in MPLS-based architectures to establish the ordering of packets. If load balancing can be achieved by switches or routers, this can greatly facilitate applying load balancing across the network. Traffic characteristics such as QoS (delay bounds, throughput) and burstiness are considered.
Xavier Hesselbach, Christos Kolias, Ramón Fabregat, Mónica Huerta, Yezid Donoso

Chapter 8. Optimization of OSPF Routing in IP Networks

The Internet is a huge world-wide packet switching network comprised of more than 13,000 distinct subnetworks, referred to as Autonomous Systems (ASs) . They all rely on the Internet Protocol (IP) for transport of packets across the network. And most of them use shortest path routing protocols , such as OSPF or IS-IS, to control the routing of IP packets within an AS. The idea of the routing is extremely simple — every packet is forwarded on IP links along the shortest route between its source and destination nodes of the AS. The AS network administrator can manage the routing of packets in the AS by supplying the so-called administrative weights of IP links, which specify the link lengths that are used by the routing protocols for their shortest path computations. The main advantage of the shortest path routing policy is its simplicity, allowing for little administrative overhead. From the network engineering perspective, however, shortest path routing can pose problems in achieving satisfactory traffic handling efficiency. As all routing paths depend on the same routing metric , it is not possible to configure the routing paths for the communication demands between different pairs of nodes explicitly or individually; the routing can be controlled only indirectly and only as a whole by modifying the routing metric. Thus, one of the main tasks when planning such networks is to find administrative link weights that induce a globally efficient traffic routing configuration of an AS. It turns out that this task leads to very difficult mathematical optimization problems. In this chapter, we discuss and describe exact integer programming models and solution approaches as well as practically efficient smart heuristics for such shortest path routing problems .
Andreas Bley, Bernard Fortz, Eric Gourdin, Kaj Holmberg, Olivier Klopfenstein, Michał Pióro, Artur Tomaszewski, Hakan Ümit

Chapter 9. Game-Theoretic Approaches to Optimization Problems in Communication Networks

In this chapter we consider fundamental optimization problems arising in communication networks. We consider scenarios where there is no central authority that coordinates the network users in order to achieve efficient solutions. Instead, the users act in an uncoordinated and selfish manner and reach solutions to the above problems that are consistent only with their selfishness. In this sense, the users act aiming to optimize their own objectives with no regard to the globally optimum system performance. Such a behavior poses several intriguing questions ranging from the definition of reasonable and practical models for studying it to the quantification of the efficiency loss due to the lack of users’ cooperation. We present several results we achieved recently in this research area and propose interesting future research directions.
Vittorio Bilò, Ioannis Caragiannis, Angelo Fanelli, Michele Flammini, Christos Kaklamanis, Gianpiero Monaco, Luca Moscardelli

Chapter 10. Permutation Routing and (ℓ, k)-Routing on Plane Grids

The packet routing problem plays an essential role in communication networks. It consists in transferring data from some origins to some destinations within a reasonable amount of time. In the (, k)-routing problem, each node can send at most packets and receive at most k packets. Permutation routing is the particular case = k = 1. In the r-central routing problem, all nodes at distance at most r from a fixed node v want to send a packet to v. Here, we survey the results on permutation routing, the r-central routing, and the general (, k)-routing problems on regular plane grids, that is, square grids, triangular grids, and hexagonal grids. We assume the store-and-forward Δ-port model with synchronous transmission, and we consider both full and half-duplex networks.
Ignasi Sau, Janez Žerovnik

Studies inWireless and Ad Hoc Networks

Chapter 11. Mathematical Optimization Models for WLAN Planning

Wireless Local Area Networks (WLANs) based on the Ieee 802.11 standard family are used widely for wireless broadband Internet access. The performance aspects of WLANs range from deployment cost, coverage, capacity, interference, and data throughput to efficiency of radio resource utilization. In this chapter, we summarize some recent advances in applying mathematical optimization models for solving planning problems arising in placing access points (APs) and assigning channels in WLANs. For AP location, we present an optimization model aimed at maximizing the average user throughput. For channel assignment, we present two modeling approaches that use different performance metrics. We also discuss integrated models for joint optimization of AP location and channel assignment. We report computational experiments with real-life data, and show the advantages of mathematical optimization in WLAN planning.
Sandro Bosio, Andreas Eisenblätter, Hans-Florian Geerdes, Iana Siomina, Di Yuan

Chapter 12. Time-Efficient Broadcast in Radio Networks

Broadcasting is a basic network communication task, where a message initially held by a source node has to be disseminated to all other nodes in the network. Fast algorithms for broadcasting in radio networks have been studied in a wide variety of different models and under different requirements. Some of the main parameters giving rise to the different variants of the problem are the accessibility of knowledge about the network topology, the availability of collision detection mechanisms, the wake-up mode, the topology classes considered, and the use of randomness. This chapter introduces the problem, reviews the literature on time-efficient broadcasting algorithms for radio networks under a variety of models and assumptions, and illustrates some of the basic techniques.
David Peleg, Tomasz Radzik

Chapter 13. Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks

This chapter deals with energy consumption issues in wireless networks. In such networks, energy is a scarce resource and, hence, it must be used efficiently. Under these circumstances, we consider two interesting combinatorial optimization problems: Minimum Energy Broadcast Routing and Cost Minimization in Multi-interface Networks. The goal of the first problem is to perform broadcasting from a given source while minimizing the overall energy required for communication. The second problem refers to the choice of activating a set of available communication interfaces at the network nodes in order to satisfy the required connections in a wireless multi-interface network with minimum total cost. While Minimum Energy Broadcast Routing has been studied extensively during recent years, Cost Minimization in Multi-interface Networks is rather new. For both problems we survey recent complexity results and approximation algorithms under different assumptions.
Alfredo Navarra, Ioannis Caragiannis, Michele Flammini, Christos Kaklamanis, Ralf Klasing

Chapter 14. Data Gathering in Wireless Networks

In this chapter, we address the problem of gathering information in a specific node of a radio network when interference constraints are present. Nodes can communicate data using a radio device; we consider a synchronous time model, where time is divided into rounds. The interference constraints limit the possibility of simultaneous data communication of nodes to the same region of the network. The survey focuses on two interference models, the general interference model and the distance-2 interference model. We survey recent complexity results and approximation algorithms for several variants of the problem. We consider several interference scenarios, the uniform and non-uniform data models, different optimization parameters, and the off-line and online settings of the problem. The objective functions we consider are the minimization of maximum completion time, maximum flow time, and average flow time.
Vincenzo Bonifaci, Ralf Klasing, Peter Korteweg, Leen Stougie, Alberto Marchetti-Spaccamela

Chapter 15. Tournament Methods for WLAN: Analysis and Efficiency

In the context of radio distributed networks, we present a generalized approach for Medium Access Control (MAC) with a fixed congestion window. Our protocol is quite simple to analyze and can be used in a lot of different situations. We give mathematical evidence showing that our performance is asymptotically tight. We also place ourselves in the WiFi and WiMAX frameworks, and discuss experimental results showing acollision reduction of 14% to 21% compared to the best-known methods. We discuss channel capacity improvement and fairness considerations.
Jérôme Galtier

Chapter 16. Topology Control and Routing in Ad Hoc Networks

Mobile nodes with the ability to communicate with radio signals may form an ad hoc network. In this chapter special problems arising for these ad hoc networks are considered. These include range control, the reduction of interferences, regulation of power consumption, and localization.
Lenka Carr-Motyckova, Alfredo Navarra, Tomas Johansson, Walter Unger

Backmatter

Weitere Informationen

Premium Partner

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!

Bildnachweise