Game Theory for Control of Optical Networks

Inhaltsverzeichnis

1. Frontmatter

2. Chapter 1. Introduction

   Lacra Pavel

   Abstract

   This chapter provides an introduction and overview of the monograph, which is aimed at understanding how control algorithms can be designed for optical networks from a game-theoretic perspective. The first section gives a review of work in game theory for networks, followed by a brief introduction to the area of optical networks. The last section presents the scope of the monograph, followed by a chapter by chapter description of the monograph.

3. Game Theory Essentials

   1. Frontmatter

   2. Chapter 2. Basics of Game Theory

      Lacra Pavel

      Abstract

      This chapter provides a brief overview of basic concepts in game theory. These include game formulations and classifications, games in extensive vs. in normal form, games with continuous action (strategy) sets vs. finite strategy sets, mixed vs. pure strategies, and games with uncoupled (orthogonal) vs. coupled action sets. The next section reviews basic solution concepts, among them Nash equilibria being of most relevance. The chapter is concluded with some remarks on the rationality assumption and learning in classical games. The following chapters will introduce these concepts formally.

   3. Chapter 3. Matrix Games

      Lacra Pavel

      Abstract

      This chapter considers normal-form games with finite action sets, hence matrix games. Two-player bimatrix cases are treated first, followed by m-player matrix games, both introducing pure- and mixed-strategy Nash equilibrium concepts. The concepts of dominance and best replies are reviewed, as well as Nash equilibria theorem and Nash equilibria refinements. Results are mostly adapted from (Basar and Olsder in Dynamic Noncooperative Game Theory. SIAM Series Classics in Applied Mathematics, 1999; Owen in Game Theory, Academic Press, San Diego, 1995).

   4. Chapter 4. Games with Continuous Action Spaces

      Lacra Pavel

      Abstract

      This chapter focuses on Nash games with continuous kernel, i.e., games with continuous action spaces and cost functions. Basic concepts and results are reviewed focused on game formulations, Nash equilibria, reaction curves, and existence results. These are mostly adapted from (Basar and Olsder in Dynamic Noncooperative Game Theory. SIAM Series Classics in Applied Mathematics, 2nd edn., 1999). For more in-depth treatment the reader is referred to this and other more extensive references on the subject.

   5. Chapter 5. Computational Results for Games with Coupled Constraints

      Lacra Pavel

      Abstract

      This chapter provides some results for Nash games with coupled constraints, i.e., coupled action sets. Work on games with coupled action spaces has been going on for more than 50 years. These are also called generalized Nash games, games with coupled constraints, or social equilibria. Game theoretical formulations of problems and computational approaches towards solving coupled or generalized Nash games have been areas of much recent interest. We present some new results mainly based on the Lagrangian approach extension proposed in Pavel (Automatica 43(2):226–237, 2007). We review a relaxation via an augmented optimization, the Lagrangian extension in a game setup, followed by duality and hierarchical decomposition in a game setup.

4. Game Theory in Optical Networks

   1. Frontmatter

   2. Chapter 6. Optical Networks: Background and Modeling

      Lacra Pavel

      Abstract

      This chapter provides an overview of basic background on transmission in optical networks and on general topologies to be studied. Most of the material is adapted from Agrawal (Fiber-optic Communication Systems, 3rd edn. Wiley, New York, 2002) and Ramaswami and Sivarajan (Optical Networks: A Practical Perspective, 2nd edn., Academic Press, San Diego, 2002), and the reader is referred to these references for more in-depth material. The concepts of OSNR and link power capacity constraint in optical networks are introduced as a preface to the remaining chapters.

   3. Chapter 7. Games in Point-to-Point Topologies

      Lacra Pavel

      Abstract

      This chapter provides the basic formulation of a game framework towards solving the OSNR optimization problem in optical networks. We restrict the analysis to single point-to-point optical links, as the simplest network topology. A Nash game played among channels is employed towards maximizing OSNR firstly without coupled link capacity constraint. Then for incorporating the coupled power constraint, two approaches are considered—an indirect and a direct one, based on Lagrangian pricing and duality extension. Sufficient conditions are derived for the existence and uniqueness of an NE solution for both approaches. Two convergent iterative algorithms are developed towards finding the NE solution.

   4. Chapter 8. Games in Network Topologies

      Lacra Pavel

      Abstract

      This chapter provides approaches on how to deal with games in more complicated network topologies, starting from the basic games in single point-to-point WDM fiber links studied in Chap. 7. The multi-link topologies studied are representative for selected paths extracted from a mesh configuration in which no closed loops are being formed by channel optical paths. In network configurations, coupled constraints are propagated along fiber links and constraint functions become complicated from the end-to-end point of view. The non-convexity introduces additional complexities for analysis. In this chapter, we present a partition approach. More precisely, we partition the general multi-link structure into stages each stage being a single link. Then we formulate a partitioned Nash game for general multi-link topologies composed of ladder-nested stage Nash games. We also show that convexity is ensured in single-sink topologies, so that a partition approach could be based on single-sink stages.

   5. Chapter 9. Nash Equilibria Efficiency and Numerical Studies

      Lacra Pavel

      Abstract

      This chapter provides an alternative constrained OSNR optimization approach. This framework can be used to investigate the effects of parameters in the game-theoretic approach, i.e., the efficiency of Nash equilibria. A system optimization problem is formulated towards achieving an OSNR target for each channel while satisfying the link capacity constraint. In the game case we show that OSNR targets can be achieved and efficiency can be possibly improved by appropriate selection of game parameters.

   6. Chapter 10. Simulations and Experimental Studies

      Lacra Pavel

      Abstract

      This chapter provides simulation and experimental results for various algorithms studied in previous chapters. The first section describes the physical setup. This is followed by simulations and experimental results based on implementing iterative algorithms in Chap. 7 for a Nash game with two, three, and five channels, respectively, in a point-to-point link topology. The last section presents results for partitioned Nash game framework in a multi-link topology and a quasi-ring topology, based on implementing the hierarchal algorithms studied in Chap. 8. Full use of the flexibility of channel power adjustment at each optical switch is assumed and the multi-link is partitioned into stages with single links. Simulation and experimental results are given for each type of network topology.

5. Robustness, Delay Effects and Other Problems

   1. Chapter 11. Robustness and Delay Effects on Network Games

      Lacra Pavel

      Abstract

      This chapter presents results on robustness of network control algorithms derived from game-theoretic formulations in the presence of time delay. Mesh optical networks are distributed over large surface areas. Any realistic OSNR model must account for these delays. Sufficiently large time delays may destabilize the closed-loop systems that implement these game-theoretic-inspired control algorithms. These algorithms need to have been appropriately adjusted so as to ensure closed-loop stability in the presence of time delays. We consider delay effects in network games without constraints, followed by games with constraints. Then we study a delayed primal–dual algorithm and perform a two time-scale stability analysis. We conclude by considering robustness and delay effects combined.

   2. Chapter 12. Games for Routing and Path Coloring

      Lacra Pavel

      Abstract

      This chapter provides and overview of routing and path coloring problems in all-optical networks as noncooperative games. We focus on oblivious payment functions, that is, functions that charge a player according to its own strategy only. We review results on the relation between such games and online routing and path coloring. In particular, these results show that the Price of Anarchy of such games is lower-bounded by, and in several cases precisely equal to, the competitive ratio of appropriate modifications of the First Fit algorithm.

   3. Chapter 13. Summary and Conclusions

      Lacra Pavel

      Abstract

      This chapter provides an overview of the monograph. In the first part a brief review of game formulation setup in optical networks is presented. This is followed by a description of the material presented in each chapter, as well as by the progressive linkage between them. The last part outlines some possible directions for future research in the area of games for optical networks.

6. Backmatter