Synthesis Lectures on Learning, Networks, and Algorithms – serie

This book provides an introduction to the theory and practice of cyber insurance. Insurance as an economic instrument designed for risk management through risk spreading has existed for centuries. Cyber insurance is one of the newest sub-categories of this old instrument. It emerged in the 1990s in response to an increasing impact that information security started to have on business operations. For much of its existence, the practice of cyber insurance has been on how to obtain accurate actuarial information to inform specifics of a cyber insurance contract. As the cybersecurity threat landscape continues to bring about novel forms of attacks and losses, ransomware insurance being the latest example, the insurance practice is also evolving in terms of what types of losses are covered, what are excluded, and how cyber insurance intersects with traditional casualty and property insurance. The central focus, however, has continued to be risk management through risk transfer, the key functionality of insurance. The goal of this book is to shift the focus from this conventional view of using insurance as primarily a risk management mechanism to one of risk control and reduction by looking for ways to re-align the incentives. On this front we have encouraging results that suggest the validity of using insurance as an effective economic and incentive tool to control cyber risk. This book is intended for someone interested in obtaining a quantitative understanding of cyber insurance and how innovation is possible around this centuries-old financial instrument.

This book provides a comprehensive treatment of the Poisson line Cox process (PLCP) and its applications to vehicular networks. The PLCP is constructed by placing points on each line of a Poisson line process (PLP) as per an independent Poisson point process (PPP). For vehicular applications, one can imagine the layout of the road network as a PLP and the vehicles on the roads as the points of the PLCP. First, a brief historical account of the evolution of the theory of PLP is provided to familiarize readers with the seminal contributions in this area. In order to provide a self-contained treatment of this topic, the construction and key fundamental properties of both PLP and PLCP are discussed in detail. The rest of the book is devoted to the applications of these models to a variety of wireless networks, including vehicular communication networks and localization networks. Specifically, modeling the locations of vehicular nodes and roadside units (RSUs) using PLCP, the signal-to-interference-plus-noise ratio (SINR)-based coverage analysis is presented for both ad hoc and cellular network models. For a similar setting, the load on the cellular macro base stations (MBSs) and RSUs in a vehicular network is also characterized analytically. For the localization networks, PLP is used to model blockages, which is shown to facilitate the characterization of asymptotic blind spot probability in a localization application. Finally, the path distance characteristics for a special case of PLCP are analyzed, which can be leveraged to answer critical questions in the areas of transportation networks and urban planning. The book is concluded with concrete suggestions on future directions of research.Based largely on the original research of the authors, this is the first book that specifically focuses on the self-contained mathematical treatment of the PLCP. The ideal audience of this book is graduate students as well as researchers in academia and industry whoare familiar with probability theory, have some exposure to point processes, and are interested in the field of stochastic geometry and vehicular networks. Given the diverse backgrounds of the potential readers, the focus has been on providing an accessible and pedagogical treatment of this topic by consciously avoiding the measure theoretic details without compromising mathematical rigor.

With the explosive growth of mobile computing and Internet of Things (IoT) applications, as exemplified by AR/VR, smart city, and video/audio surveillance, billions of mobile and IoT devices are being connected to the Internet, generating zillions of bytes of data at the network edge. Driven by this trend, there is an urgent need to push the frontiers of artificial intelligence (AI) to the network edge to fully unleash the potential of IoT big data. Indeed, the marriage of edge computing and AI has resulted in innovative solutions, namely edge intelligence or edge AI. Nevertheless, research and practice on this emerging inter-disciplinary field is still in its infancy stage. To facilitate the dissemination of the recent advances in edge intelligence in both academia and industry, this book conducts a comprehensive and detailed survey of the recent research efforts and also showcases the authors' own research progress on edge intelligence. Specifically, the book first reviewsthe background and present motivation for AI running at the network edge. Next, it provides an overview of the overarching architectures, frameworks, and emerging key technologies for deep learning models toward training/inference at the network edge. To illustrate the research problems for edge intelligence, the book also showcases four of the authors' own research projects on edge intelligence, ranging from rigorous theoretical analysis to studies based on realistic implementation. Finally, it discusses the applications, marketplace, and future research opportunities of edge intelligence. This emerging interdisciplinary field offers many open problems and yet also tremendous opportunities, and this book only touches the tip of iceberg. Hopefully, this book will elicit escalating attention, stimulate fruitful discussions, and open new directions on edge intelligence.

This book provides a quick reference and insights into modeling and optimization of software-defined networks (SDNs). It covers various algorithms and approaches that have been developed for optimizations related to the control plane, the considerable research related to data plane optimization, and topics that have significant potential for research and advances to the state-of-the-art in SDN. Over the past ten years, network programmability has transitioned from research concepts to more mainstream technology through the advent of technologies amenable to programmability such as service chaining, virtual network functions, and programmability of the data plane. However, the rapid development in SDN technologies has been the key driver behind its evolution. The logically centralized abstraction of network states enabled by SDN facilitates programmability and use of sophisticated optimization and control algorithms for enhancing network performance, policy management, and security.Furthermore, the centralized aggregation of network telemetry facilitates use of data-driven machine learning-based methods. To fully unleash the power of this new SDN paradigm, though, various architectural design, deployment, and operations questions need to be addressed. Associated with these are various modeling, resource allocation, and optimization opportunities.The book covers these opportunities and associated challenges, which represent a ``call to arms'' for the SDN community to develop new modeling and optimization methods that will complement or improve on the current norms.

Networks naturally appear in many high-impact domains, ranging from social network analysis to disease dissemination studies to infrastructure system design. Within network studies, network connectivity plays an important role in a myriad of applications. The diversity of application areas has spurred numerous connectivity measures, each designed for some specific tasks. Depending on the complexity of connectivity measures, the computational cost of calculating the connectivity score can vary significantly. Moreover, the complexity of the connectivity would predominantly affect the hardness of connectivity optimization, which is a fundamental problem for network connectivity studies. This book presents a thorough study in network connectivity, including its concepts, computation, and optimization. Specifically, a unified connectivity measure model will be introduced to unveil the commonality among existing connectivity measures. For the connectivity computation aspect, the authors introduce the connectivity tracking problems and present several effective connectivity inference frameworks under different network settings. Taking the connectivity optimization perspective, the book analyzes the problem theoretically and introduces an approximation framework to effectively optimize the network connectivity. Lastly, the book discusses the new research frontiers and directions to explore for network connectivity studies. This book is an accessible introduction to the study of connectivity in complex networks. It is essential reading for advanced undergraduates, Ph.D. students, as well as researchers and practitioners who are interested in graph mining, data mining, and machine learning.

This book addresses the urgent issue of massive and inefficient energy consumption by data centers, which have become the largest co-located computing systems in the world and process trillions of megabytes of data every second. Dynamic provisioning algorithms have the potential to be the most viable and convenient of approaches to reducing data center energy consumption by turning off unnecessary servers, but they incur additional costs from being unable to properly predict future workload demands that have only recently been mitigated by advances in machine-learned predictions.This book explores whether it is possible to design effective online dynamic provisioning algorithms that require zero future workload information while still achieving close-to-optimal performance. It also examines whether characterizing the benefits of utilizing the future workload information can then improve the design of online algorithms with predictions in dynamic provisioning. The book specifically develops online dynamic provisioning algorithms with and without the available future workload information. Readers will discover the elegant structure of the online dynamic provisioning problem in a way that reveals the optimal solution through divide-and-conquer tactics. The book teaches readers to exploit this insight by showing the design of two online competitive algorithms with competitive ratios characterized by the normalized size of a look-ahead window in which exact workload prediction is available.

This book addresses the urgent issue of massive and inefficient energy consumption by data centers, which have become the largest co-located computing systems in the world and process trillions of megabytes of data every second. Dynamic provisioning algorithms have the potential to be the most viable and convenient of approaches to reducing data center energy consumption by turning off unnecessary servers, but they incur additional costs from being unable to properly predict future workload demands that have only recently been mitigated by advances in machine-learned predictions.This book explores whether it is possible to design effective online dynamic provisioning algorithms that require zero future workload information while still achieving close-to-optimal performance. It also examines whether characterizing the benefits of utilizing the future workload information can then improve the design of online algorithms with predictions in dynamic provisioning. The book specifically develops online dynamic provisioning algorithms with and without the available future workload information. Readers will discover the elegant structure of the online dynamic provisioning problem in a way that reveals the optimal solution through divide-and-conquer tactics. The book teaches readers to exploit this insight by showing the design of two online competitive algorithms with competitive ratios characterized by the normalized size of a look-ahead window in which exact workload prediction is available.

This book presents Internet transport economics as a new approach to understanding the packet-switching paradigm of Internet infrastructure as a global transport system for data packets. It is a prescient view of the Internet’s evolution into a content-centric service platform where the quality of services (QoS) cannot be guaranteed due to the tens of thousands of autonomous systems that enact business decisions on peering, routing, and pricing in a way that determines aspects of the Internet ecosystem like network topology, latency and throughput of traffic flows, and performance of network applications. The trafficking issues created in this environment are a critical concern and barrier for user applications that require real-time responses, such as telesurgery and teleoperation of autonomous vehicles, and the book presents the Internet transport economics model as the solution.                While engineering and business are the prevailing lenses through which the Internet is viewed, the book builds its methodological framework around transport. Further delving into economics, it establishes how the Internet can be understood as providing transport services for data packets, whose demand and supply are driven by the QoS metrics of delay and loss, which can be regarded as congestion costs that result in equilibrium rates of traffic flows sent by content providers (CPs). The book goes on to present a stylized model of content provider-to-access provider (CP–AP) service as well as congestion equilibrium and rate equilibrium solution concepts under the Internet transport economics framework. These are used to analyze the problem domains of service differentiation, market structure, and data pricing. Finally, it discusses various potential future applications. This book will be of interest to graduate students and researchers in areas of computer networking and performance evaluation.

This book presents Internet transport economics as a new approach to understanding the packet-switching paradigm of Internet infrastructure as a global transport system for data packets. It is a prescient view of the Internet’s evolution into a content-centric service platform where the quality of services (QoS) cannot be guaranteed due to the tens of thousands of autonomous systems that enact business decisions on peering, routing, and pricing in a way that determines aspects of the Internet ecosystem like network topology, latency and throughput of traffic flows, and performance of network applications. The trafficking issues created in this environment are a critical concern and barrier for user applications that require real-time responses, such as telesurgery and teleoperation of autonomous vehicles, and the book presents the Internet transport economics model as the solution.                While engineering and business are the prevailing lenses through which the Internet is viewed, the book builds its methodological framework around transport. Further delving into economics, it establishes how the Internet can be understood as providing transport services for data packets, whose demand and supply are driven by the QoS metrics of delay and loss, which can be regarded as congestion costs that result in equilibrium rates of traffic flows sent by content providers (CPs). The book goes on to present a stylized model of content provider-to-access provider (CP–AP) service as well as congestion equilibrium and rate equilibrium solution concepts under the Internet transport economics framework. These are used to analyze the problem domains of service differentiation, market structure, and data pricing. Finally, it discusses various potential future applications. This book will be of interest to graduate students and researchers in areas of computer networking and performance evaluation.

This book discusses state-of-the-art stochastic optimization algorithms for distributed machine learning and analyzes their convergence speed. The book first introduces stochastic gradient descent (SGD) and its distributed version, synchronous SGD, where the task of computing gradients is divided across several worker nodes. The author discusses several algorithms that improve the scalability and communication efficiency of synchronous SGD, such as asynchronous SGD, local-update SGD, quantized and sparsified SGD, and decentralized SGD. For each of these algorithms, the book analyzes its error versus iterations convergence, and the runtime spent per iteration. The author shows that each of these strategies to reduce communication or synchronization delays encounters a fundamental trade-off between error and runtime.

This book discusses state-of-the-art stochastic optimization algorithms for distributed machine learning and analyzes their convergence speed. The book first introduces stochastic gradient descent (SGD) and its distributed version, synchronous SGD, where the task of computing gradients is divided across several worker nodes. The author discusses several algorithms that improve the scalability and communication efficiency of synchronous SGD, such as asynchronous SGD, local-update SGD, quantized and sparsified SGD, and decentralized SGD. For each of these algorithms, the book analyzes its error versus iterations convergence, and the runtime spent per iteration. The author shows that each of these strategies to reduce communication or synchronization delays encounters a fundamental trade-off between error and runtime.

This book provides an accessible yet rigorous first reference for readers interested in learning how to model and analyze cellular network performance using stochastic geometry. In addition to the canonical downlink and uplink settings, analyses of heterogeneous cellular networks and dense cellular networks are also included. For each of these settings, the focus is on the calculation of coverage probability, which gives the complementary cumulative distribution function (ccdf) of signal-to-interference-and-noise ratio (SINR) and is the complement of the outage probability. Using this, other key performance metrics, such as the area spectral efficiency, are also derived. These metrics are especially useful in understanding the effect of densification on network performance. In order to make this a truly self-contained reference, all the required background material from stochastic geometry is introduced in a coherent and digestible manner.This Book:Provides an approachable introduction to the analysis of cellular networks and illuminates key system dependenciesFeatures an approach based on stochastic geometry as applied to cellular networks including both downlink and uplinkFocuses on the statistical distribution of signal-to-interference-and-noise ratio (SINR) and related metrics

This book introduces the Learning-Augmented Network Optimization (LANO) paradigm, which interconnects network optimization with the emerging AI theory and algorithms and has been receiving a growing attention in network research. The authors present the topic based on a general stochastic network optimization model, and review several important theoretical tools that are widely adopted in network research, including convex optimization, the drift method, and mean-field analysis. The book then covers several popular learning-based methods, i.e., learning-augmented drift, multi-armed bandit and reinforcement learning, along with applications in networks where the techniques have been successfully applied. The authors also provide a discussion on potential future directions and challenges.

This book introduces the Learning-Augmented Network Optimization (LANO) paradigm, which interconnects network optimization with the emerging AI theory and algorithms and has been receiving a growing attention in network research. The authors present the topic based on a general stochastic network optimization model, and review several important theoretical tools that are widely adopted in network research, including convex optimization, the drift method, and mean-field analysis. The book then covers several popular learning-based methods, i.e., learning-augmented drift, multi-armed bandit and reinforcement learning, along with applications in networks where the techniques have been successfully applied. The authors also provide a discussion on potential future directions and challenges.

This book provides an accessible yet rigorous first reference for readers interested in learning how to model and analyze cellular network performance using stochastic geometry. In addition to the canonical downlink and uplink settings, analyses of heterogeneous cellular networks and dense cellular networks are also included. For each of these settings, the focus is on the calculation of coverage probability, which gives the complementary cumulative distribution function (ccdf) of signal-to-interference-and-noise ratio (SINR) and is the complement of the outage probability. Using this, other key performance metrics, such as the area spectral efficiency, are also derived. These metrics are especially useful in understanding the effect of densification on network performance. In order to make this a truly self-contained reference, all the required background material from stochastic geometry is introduced in a coherent and digestible manner.This Book:Provides an approachable introduction to the analysis of cellular networks and illuminates key system dependenciesFeatures an approach based on stochastic geometry as applied to cellular networks including both downlink and uplinkFocuses on the statistical distribution of signal-to-interference-and-noise ratio (SINR) and related metrics

This book provides a comprehensive overview of reinforcement learning for ridesharing applications. The authors first lay out the fundamentals of the ridesharing system architectures and review the basics of reinforcement learning, including the major applicable algorithms. The book describes the research problems associated with the various aspects of a ridesharing system and discusses the existing reinforcement learning approaches for solving them. The authors survey the existing research on each problem, and then examine specific case studies. The book also includes a review of two of methods closely related to reinforcement learning: approximate dynamic programming and model-predictive control.

This book provides a comprehensive overview of reinforcement learning for ridesharing applications. The authors first lay out the fundamentals of the ridesharing system architectures and review the basics of reinforcement learning, including the major applicable algorithms. The book describes the research problems associated with the various aspects of a ridesharing system and discusses the existing reinforcement learning approaches for solving them. The authors survey the existing research on each problem, and then examine specific case studies. The book also includes a review of two of methods closely related to reinforcement learning: approximate dynamic programming and model-predictive control.

This book presents algorithms and tools that are designed to model and extract information from personal contact networks, which represent which individuals in a population are physically in contact with one another. The authors developed these tools based on research they conducted during the COVID-19 pandemic, with the goal of improving responses to epidemics in the future. The book provides methods for modelling the transmission of infection across a population. The authors explain how an epidemic model can be used to strategically distribute vaccines and minimize the spread of a virus. The book shows how evolutionary computation, graph compression, and network induction can be utilized to manage issues that arise from an epidemic.

This book presents algorithms and tools that are designed to model and extract information from personal contact networks, which represent which individuals in a population are physically in contact with one another. The authors developed these tools based on research they conducted during the COVID-19 pandemic, with the goal of improving responses to epidemics in the future. The book provides methods for modelling the transmission of infection across a population. The authors explain how an epidemic model can be used to strategically distribute vaccines and minimize the spread of a virus. The book shows how evolutionary computation, graph compression, and network induction can be utilized to manage issues that arise from an epidemic.

Traditional network optimization focuses on a single control objective in a network populated by obedient users and limited dispersion of information. However, most of today's networks are large-scale with lack of access to centralized information, consist of users with diverse requirements, and are subject to dynamic changes. These factors naturally motivate a new distributed control paradigm, where the network infrastructure is kept simple and the network control functions are delegated to individual agents which make their decisions independently ("selfishly"). The interaction of multiple independent decision-makers necessitates the use of game theory, including economic notions related to markets and incentives.This monograph studies game theoretic models of resource allocation among selfish agents in networks. The first part of the monograph introduces fundamental game theoretic topics. Emphasis is given to the analysis of dynamics in game theoretic situations, which is crucial for design and control of networked systems. The second part of the monograph applies the game theoretic tools for the analysis of resource allocation in communication networks. We set up a general model of routing in wireline networks, emphasizing the congestion problems caused by delay and packet loss. In particular, we develop a systematic approach to characterizing the inefficiencies of network equilibria, and highlight the effect of autonomous service providers on network performance. We then turn to examining distributed power control in wireless networks. We show that the resulting Nash equilibria can be efficient if the degree of freedom given to end-users is properly designed.Table of Contents: Static Games and Solution Concepts / Game Theory Dynamics / Wireline Network Games / Wireless Network Games / Future Perspectives

NS-2 is an open-source discrete event network simulator which is widely used by both the research community as well as by the people involved in the standardization protocols of IETF. The goal of this book is twofold: on one hand to learn how to use the NS-2 simulator, and on the other hand, to become acquainted with and to understand the operation of some of the simulated objects using NS-2 simulations. The book is intended to help students, engineers or researchers who need not have much background in programming or who want to learn through simple examples how to analyse some simulated objects using NS-2. Simulations may differ from each other in many aspects: the applications, topologies, parameters of network objects (links, nodes) and protocols used, etc. The first chapter is a general introduction to the book, where the importance of NS-2 as a tool for a good comprehension of networks and protocols is stated. In the next chapters we present special topics as TCP, RED, etc., using NS-2 as a tool for better understanding the protocols. We provide in the appendices a review of Random Variables and Confidence Intervals, as well as a first sketch for using the new NS-3 simulator. Table of Contents: Introduction / NS-2 Simulator Preliminaries / How to work with trace files / Description and simulation of TCP/IP / Routing and network dynamics / RED: Random Early Discard / Differentiated Services / Mobile Networks and Wireless Local Area Networks / Classical queueing models / Tcl and C++ linkage

Packet delay and energy consumption are important considerations in wireless and sensor networks as these metrics directly affect the quality of service of the application and the resource consumption of the network; especially, for a rapidly growing class of real-time applications that impose strict restrictions on packet delays. Dynamic rate control is a novel technique for adapting the transmission rate of wireless devices, almost in real-time, to opportunistically exploit time-varying channel conditions as well as changing traffic patterns. Since power consumption is not a linear function of the rate and varies significantly with the channel conditions, adapting the rate has significant benefits in minimizing energy consumption. These benefits have prompted significant research in developing algorithms for achieving optimal rate adaptation while satisfying quality of service requirements. In this book, we provide a comprehensive study of dynamic rate control for energy minimizationunder packet delay constraints. We present several formulations and approaches adopted in the literature ranging from discrete-time formulations and dynamic programming based solutions to continuous-time approaches utilizing ideas from network calculus and stochastic optimal control theory. The goal of this book is to expose the reader to the important problem of wireless data transmission with delay constraints and to the rich set of tools developed in recent years to address it. Table of Contents: Introduction / Transmission Rate Adaptation under Deadline Constraints / Average Delay Constraints

With the explosive increase in the number of mobile devices and applications, it is anticipated that wireless traffic will increase exponentially in the coming years. Moreover, future wireless networks all carry a wide variety of flows, such as video streaming, online gaming, and VoIP, which have various quality of service (QoS) requirements. Therefore, a new mechanism that can provide satisfactory performance to the complete variety of all kinds of flows, in a coherent and unified framework, is needed.In this book, we introduce a framework for real-time wireless networks. This consists of a model that jointly addresses several practical concerns for real-time wireless networks, including per-packet delay bounds, throughput requirements, and heterogeneity of wireless channels. We detail how this framework can be employed to address a wide range of problems, including admission control, packet scheduling, and utility maximization.Table of Contents: Preface / Introduction / A Study of the Base Case / Admission Control / Scheduling Policies / Utility Maximization without Rate Adaptation / Utility Maximization with Rate Adaptation / Systems with Both Real-Time Flows and Non-Real-Time Flows / Broadcasting and Network Coding / Bibliography / Authors' Biographies

This monograph presents a concise mathematical approach for modeling and analyzing the performance of communication networks with the aim of introducing an appropriate mathematical framework for modeling and analysis as well as understanding the phenomenon of statistical multiplexing. The models, techniques, and results presented form the core of traffic engineering methods used to design, control and allocate resources in communication networks.The novelty of the monograph is the fresh approach and insights provided by a sample-path methodology for queueing models that highlights the important ideas of Palm distributions associated with traffic models and their role in computing performance measures. The monograph also covers stochastic network theory including Markovian networks. Recent results on network utility optimization and connections to stochastic insensitivity are discussed. Also presented are ideas of large buffer, and many sources asymptotics that play an important role in understanding statistical multiplexing. In particular, the important concept of effective bandwidths as mappings from queueing level phenomena to loss network models is clearly presented along with a detailed discussion of accurate approximations for large networks.

Today's wireless communications and networking practices are tightly coupled with economic considerations, to the extent that it is almost impossible to make a sound technology choice without understanding the corresponding economic implications. This book aims at providing a foundational introduction on how microeconomics, and pricing theory in particular, can help us to understand and build better wireless networks. The book can be used as lecture notes for a course in the field of network economics, or a reference book for wireless engineers and applied economists to understand how pricing mechanisms influence the fast growing modern wireless industry.This book first covers the basics of wireless communication technologies and microeconomics, before going in-depth about several pricing models and their wireless applications. The pricing models include social optimal pricing, monopoly pricing, price differentiation, oligopoly pricing, and network externalities, supported by introductory discussions of convex optimization and game theory. The wireless applications include wireless video streaming, service provider competitions, cellular usage-based pricing, network partial price differentiation, wireless spectrum leasing, distributed power control, and cellular technology upgrade. More information related to the book (including references, slides, and videos) can be found at ncel.ie.cuhk.edu.hk/content/wireless-network-pricing.

Resource Allocation lies at the heart of network control. In the early days of the Internet the scarcest resource was bandwidth, but as the network has evolved to become an essential utility in the lives of billions, the nature of the resource allocation problem has changed. This book attempts to describe the facets of resource allocation that are most relevant to modern networks. It is targeted at graduate students and researchers who have an introductory background in networking and who desire to internalize core concepts before designing new protocols and applications.We start from the fundamental question: what problem does network resource allocation solve? This leads us, in Chapter 1, to examine what it means to satisfy a set of user applications that have different requirements of the network, and to problems in Social Choice Theory. We find that while capturing these preferences in terms of utility is clean and rigorous, there are significant limitations to this choice. Chapter 2 focuses on sharing divisible resources such as links and spectrum. Both of these resources are somewhat atypical -- a link is most accurately modeled as a queue in our context, but this leads to the analytical intractability of queueing theory, and spectrum allocation methods involve dealing with interference, a poorly understood phenomenon. Chapters 3 and 4 are introductions to two allocation workhorses: auctions and matching. In these chapters we allow the users to game the system (i.e., to be strategic), but don't allow them to collude. In Chapter 5, we relax this restriction and focus on collaboration. Finally, in Chapter 6, we discuss the theoretical yet fundamental issue of stability. Here, our contribution is mostly on making a mathematically abstruse subdiscipline more accessible without losing too much generality.

The concept of physical-layer network coding (PNC) was proposed in 2006 for application in wireless networks. Since then it has developed into a subfield of communications and networking with a wide following. This book is a primer on PNC. It is the outcome of a set of lecture notes for a course for beginning graduate students at The Chinese University of Hong Kong. The target audience is expected to have some prior background knowledge in communication theory and wireless communications, but not working knowledge at the research level. Indeed, a goal of this book/course is to allow the reader to gain a deeper appreciation of the various nuances of wireless communications and networking by focusing on problems arising from the study of PNC. Specifically, we introduce the tools and techniques needed to solve problems in PNC, and many of these tools and techniques are drawn from the more general disciplines of signal processing, communications, and networking: PNC is used as a pivot to learn about the fundamentals of signal processing techniques and wireless communications in general. We feel that such a problem-centric approach will give the reader a more in-depth understanding of these disciplines and allow him/her to see first-hand how the techniques of these disciplines can be applied to solve real research problems. As a primer, this book does not cover many advanced materials related to PNC. PNC is an active research field and many new results will no doubt be forthcoming in the near future. We believe that this book will provide a good contextual framework for the interpretation of these advanced results should the reader decide to probe further into the field of PNC.

The last decade has seen an unprecedented growth in the demand for wireless services. These services are fueled by applications that often require not only high data rates, but also very low latency to function as desired. However, as wireless networks grow and support increasingly large numbers of users, these control algorithms must also incur only low complexity in order to be implemented in practice. Therefore, there is a pressing need to develop wireless control algorithms that can achieve both high throughput and low delay, but with low-complexity operations. While these three performance metrics, i.e., throughput, delay, and complexity, are widely acknowledged as being among the most important for modern wireless networks, existing approaches often have had to sacrifice a subset of them in order to optimize the others, leading to wireless resource allocation algorithms that either suffer poor performance or are difficult to implement. In contrast, the recent results presented inthis book demonstrate that, by cleverly taking advantage of multiple physical or virtual channels, one can develop new low-complexity algorithms that attain both provably high throughput and provably low delay. The book covers both the intra-cell and network-wide settings. In each case, after the pitfalls of existing approaches are examined, new systematic methodologies are provided to develop algorithms that perform provably well in all three dimensions.

The congestion control mechanism has been responsible for maintaining stability as the Internet scaled up by many orders of magnitude in size, speed, traffic volume, coverage, and complexity over the last three decades. In this book, we develop a coherent theory of congestion control from the ground up to help understand and design these algorithms. We model network traffic as fluids that flow from sources to destinations and model congestion control algorithms as feedback dynamical systems. We show that the model is well defined. We characterize its equilibrium points and prove their stability. We will use several real protocols for illustration but the emphasis will be on various mathematical techniques for algorithm analysis.Specifically we are interested in four questions:1. How are congestion control algorithms modelled?2. Are the models well defined?3. How are the equilibrium points of a congestion control model characterized?4. How are the stability of these equilibrium points analyzed?For each topic, we first present analytical tools, from convex optimization, to control and dynamical systems, Lyapunov and Nyquist stability theorems, and to projection and contraction theorems. We then apply these basic tools to congestion control algorithms and rigorously prove their equilibrium and stability properties. A notable feature of this book is the careful treatment of projected dynamics that introduces discontinuity in our differential equations.Even though our development is carried out in the context of congestion control, the set of system theoretic tools employed and the process of understanding a physical system, building mathematical models, and analyzing these models for insights have a much wider applicability than to congestion control.