Graphs and Algorithms in Communication Networks

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.