Graphs and Algorithms in Communication Networks

Studies in Broadband, Optical, Wireless and Ad Hoc Networks

By: Arie Koster (Editor), Xavier Muaoz (Editor), Xavier Munoz (Editor)

Write A Review

Hardcover | 30 November 2009

At a Glance

Hardcover
456 Pages

Dimensions(cm)
24.77 x 16.51 x 2.54

Hardcover

$249.00

or 4 interest-free payments of $62.25 with

Ships in 5 to 7 business days

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.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

Other Editions and Formats

Paperback

Published: 14th March 2012

View Product

Graphs and Algorithms hi Communication Networks on Seven League Boots	p. 1
Introduction	p. 1
Mathematical Modeling	p. 3
Sets and Parameters	p. 3
Graphs and Networks	p. 4
Mathematical Problems	p. 7
Distributed Problems	p. 9
Online Decision Problems	p. 10
Computational Complexity	p. 11
Combinatorial Optimization Methods	p. 13
Linear-Programming-Based Methods	p. 14
Graph Theory	p. 22
Combinatorial Algorithms	p. 23
Approximation Algorithms	p. 23
Heuristics Without Solution Guarantee	p. 24
Nonlinear Programming	p. 24
Selected Classical Applications in Communication Networks	p. 25
Design of Network Topologies	p. 25
Network Routing Problems	p. 29
Network Planning Problems	p. 38
A Randomized Cost Smoothing Approach for Optical Network Design	p. 40
Wireless Networking	p. 46
Emerging Applications in Communication Networks	p. 53
Broadband and Optical Networks	p. 53
Wireless and Ad Hoc Networks	p. 55
References	p. 56
Studies in Broadband and Optical Networks
Traffic Grooming: Combinatorial Results and Practical Resolutions	p. 63
Introduction	p. 64
Problem Definition and Examples	p. 66
Minimizing the Usage of Light Termination Equipment	p. 70
Path	p. 70
Ring	p. 71
General Topology	p. 71
Online Traffic	p. 72
Price of Anarchy	p. 72
Minimizing the Number of Add/Drop Multiplexers	p. 73
Complexity and Inapproximability Results	p. 74
Approximation Results	p. 75
Specific Constructions	p. 76
A Priori Placement of the Equipment	p. 77
Multilayer Traffic Grooming for General Networks	p. 78
Multilayer Mesh Networks	p. 79
On Grooming in Multilayer Mesh Networks	p. 80
Graph Models for Multilayer Grooming	p. 81
Conclusion	p. 87
References	p. 88
Branch-and-Cut Techniques for Solving Realistic Two-Layer Network Design Problems	p. 95
Introduction	p. 96
Mathematical Model	p. 98
Mixed-Integer Programming Model	p. 98
Preprocessing	p. 101
MIP-Based Heuristics Within Branch-and-Cut	p. 103
Computing Capacities over a Given Flow	p. 103
Rerouting Flow to Reduce Capacities	p. 104
Cutting Planes	p. 105
Cutting Planes on the Logical Layer	p. 105
Cutting Planes on the Physical Layer	p. 108
Computational Results	p. 109
Test Instances and Settings	p. 109
Unprotected Demands	p. 110
Protected Demands	p. 113
Preprocessing and Heuristics	p. 114
Conclusions	p. 116
References	p. 116
Routing and Label Space Reduction in Label Switching Networks	p. 119
Introduction to Label Switching	p. 119
Functional Description of the Technologies	p. 121
Multi-protocol Label Switching Traffic Engineering (MPLS-TE)	p. 121
All-Optical Label Switching (AOLS)	p. 122
Ethernet VLAN-Label Switching (ELS)	p. 122
Methods for Scaling the Usage of the Label Space	p. 123
Label Merging	p. 123
Label Stacking	p. 124
Considering Routing	p. 126
Generic Model	p. 128
Parameters and Variables	p. 128
Integer Linear Program for the Network Design Problem	p. 129
Traffic Engineering Formulation	p. 130
No Label Stacking	p. 131
Simulation Results	p. 131
MPLS-TE	p. 131
AOLS	p. 132
ELS	p. 134
Conclusions and Future Work	p. 135
References	p. 136
Network Survivability: End-to-End Recovery Using Local Failure Information	p. 137
Basic Concepts on Network Survivability	p. 138
Protection and Restoration	p. 138
The Scope of Backup Paths	p. 139
Shareability of Protection Resources	p. 140
The Failure-Dependent Path Protection Method	p. 141
Recovery Based on the Failure Scenario	p. 141
Path Assignment Approaches	p. 143
General Shared Risk Groups (SRG)	p. 143
The Input of the Problem	p. 144
Two-Step Approaches	p. 145
Joint Optimization: The Greedy Approach	p. 146
Multi-commodity Connectivity (MCC)	p. 147
Complexity of the Multi-commodity Connectivity Problem	p. 148
The SPH Approach	p. 149
ILP of the Multi-commodity Connectivity Problem	p. 150
Examples	p. 151
Case Studies	p. 151
First Case Study: Shortcut Span Protection	p. 152
The Shortcut Span Protection Model	p. 153
Results	p. 154
Second Case Study: Connection Availability Under Path Protection	p. 156
References	p. 160
Routing Optimization in Optical Burst Switching Networks: a Multi-path Routing Approach	p. 163
Introduction	p. 164
OBS Technology	p. 165
Routing Methods	p. 165
Network Modeling	p. 166
Link Loss Calculation	p. 167
Network Loss Calculation	p. 168
Multi-path Source Routing	p. 169
Resolution Methods and Numerical Examples	p. 170
Formulation of the Optimization Problem	p. 170
Calculation of Partial Derivatives	p. 171
Numerical Results	p. 173
Discussion	p. 174
Accuracy of Loss Models	p. 174
Properties of the Objective Function	p. 175
Computational Effort	p. 176
Conclusions	p. 177
References	p. 177
Problems in Dynamic Bandwidth Allocation in Connection Oriented Networks	p. 179
Introduction	p. 180
Technological Perspective and Challenges	p. 180
Definitions and Concepts Overview	p. 181
Node Model for Packet Networks with Traffic Prioritization	p. 183
QoS in IP/DiffServ/MPLS and in OBS Networks	p. 183
Optical Burst Switching Using MPLS	p. 184
Load Balancing Strategies in a Multi-path Scenario	p. 185
Load Balancing in Packet Networks in Multicast Multi-path Scenarios	p. 189
Model for Traffic Partitioning	p. 191
Intelligent Bandwidth Allocation Algorithms for Multilayer Traffic Mapping with Priority Provision	p. 193
QoS Algorithms for OBS	p. 194
Conclusions	p. 197
References	p. 197
Optimization of OSPF Routine in IP Networks	p. 199
Introduction	p. 200
Problem Description	p. 202
Basic Notions and Notations	p. 203
Informal Formulation	p. 203
Discussion	p. 205
Integer Programming Approach	p. 207
Optimizing the Routing Paths	p. 207
Finding Compatible Routing Weights	p. 209
Shortest Path Routing Inequalities	p. 211
Combinatorial Cuts	p. 212
Valid Cycles	p. 214
General Inequalities	p. 217
Heuristic Methods	p. 221
Local Search	p. 222
Other Algorithms	p. 223
Effectiveness Issues	p. 224
Numerical Results	p. 225
Integer Programming Approach	p. 225
Heuristic Methods	p. 227
Selected Extensions	p. 229
General MIP Formulation	p. 229
Additional Routing Constraints and Other Objective Functions	p. 231
Resource Dimensioning	p. 232
Resilient Routing	p. 232
Historical any Literature Notes	p. 233
Concluding Remarks	p. 236
References	p. 237
Game-Theoretic Approaches to Optimization Problems in Communication Networks	p. 241
Introduction	p. 242
Preliminary Notions	p. 243
Congestion Games	p. 247
Multicast Cost Sharing Games	p. 251
Communication Games in All-Optical Networks	p. 254
Beyond Nash Equilibria: An Alternative Solution Concept for Non-cooperative Games	p. 255
Coping with Incomplete Information	p. 257
Open Problems and Future Research	p. 259
References	p. 261
Permutation Routing and (l, k)-Routing on Plane Grids	p. 265
Introduction	p. 265
General Results on Packet Routing	p. 266
Routing Problems	p. 269
Topologies	p. 270
Optimal Permutation Routing Algorithm	p. 273
Preliminaries	p. 273
Description of the Algorithm for Hexagonal Networks	p. 274
Correctness, Running Time and Optimality	p. 275
Extensions and Open Problems	p. 276
References	p. 277
Studies in Wireless and Ad Hoc Networks
Mathematical Optimization Models for WLAN Planning	p. 283
Introduction	p. 284
Technical Background	p. 285
Physical Layer	p. 286
Architecture	p. 286
Medium Access Control	p. 287
Planning Tasks and Performance Aspects	p. 289
Related Work	p. 290
Notation and Definitions	p. 290
AP Location Optimization	p. 292
Minimum-Overlap Channel Assignment	p. 293
Maximum-Efficiency Channel Assignment	p. 295
A Hyperbolic Model and Linear Reformulations	p. 296
An Enumerative Integer Linear Model	p. 297
Integrated Planning of AP Location and Channel Assignment	p. 298
AP Location and Minimum-Overlap Channel Assignment	p. 298
AP Location and Maximum-Efficiency Channel Assignment	p. 299
Experimental Results	p. 301
Conclusions and Perspectives	p. 306
References	p. 307
Time-Efficient Broadcast in Radio Networks	p. 311
Introduction	p. 311
The Problem	p. 311
Model Parameters	p. 314
Efficient Schedules and Bounds on b(G) and &bcirc;(n, D)	p. 316
Distributed Broadcasting Algorithms	p. 318
Deterministic Distributed Algorithms	p. 318
Randomized Distributed Algorithms	p. 319
Randomized Broadcasting: Main Techniques	p. 320
Using Selective Families in deterministic Distributed Broadcasting	p. 324
Other Variants	p. 326
Directed Graphs	p. 326
Unit Disk Graphs	p. 327
Related Work	p. 329
References	p. 331
Energy Consumption Minimization in Ad Hoc Wireless and Multi-interface Networks	p. 335
Introduction	p. 336
Minimum Energy Broadcast Routing	p. 336
Definitions and Notation	p. 337
The Geometric Version of MBBR	p. 338
An 8-Approximation Upper Bound for the MST Heuristic	p. 340
Experimental Studies with the MST Heuristic	p. 343
Solving More General Instances of MEBR	p. 344
Cost Minimization in Multi-interface Networks	p. 347
Definitions and Notation	p. 348
Results for k-CMI	p. 349
Results for CMI	p. 351
Conclusion and Future Work	p. 352
References	p. 353
Data Gathering in Wireless Networks	p. 357
Introduction	p. 358
The Mathematical Model	p. 360
Complexity and Lower Bounds	p. 361
Minimizing Makespan	p. 361
Minimizing Flow Times	p. 364
Online Algorithms	p. 367
Minimizing Makespan	p. 367
Minimizing Flow Times	p. 374
Conclusion	p. 375
References	p. 376
Tournament Methods for WLAN: Analysis and Efficiency	p. 379
Introduction and Related Works	p. 379
Description of the Tournament Method	p. 381
Mathematical Analysis	p. 383
Practical Implementation	p. 393
Setting the Approximation Points	p. 393
Defining Varying Number of Rounds	p. 393
Numerical Result	p. 394
Tuning of the Probabilities	p. 394
Comparative Bandwidth	p. 397
Fairness Considerations	p. 398
Conclusion	p. 399
References	p. 399
Topology Control and Routing in Ad Hoc Networks	p. 401
Introduction	p. 401
Reducing Interference in Ad Hoc Networks	p. 404
Energy Aware Scatternet Formation and Routing	p. 407
Bandwidth-Constrained Clustering?	p. 411
Localizing Using Arrival Times	p. 412
Conclusions	p. 415
References	p. 416
Index	p. 419
Table of Contents provided by Ingram. All Rights Reserved.

Graphs and Algorithms in Communication Networks

Studies in Broadband, Optical, Wireless and Ad Hoc Networks

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

Other Editions and Formats

Paperback

More in Computer Science

Python Crash Course

3rd Edition - A Hands-On, Project-Based Introduction to Programming

Nexus

A Brief History of Information Networks from the Stone Age to AI

Microsoft 365 Excel For Dummies

For Dummies (Computer/Tech)

The Tech Coup

How to Save Democracy from Silicon Valley

The New Age of Sexism

How the AI Revolution is Reinventing Misogyny

The AI Con

How To Fight Big Tech's Hype and Create the Future We Want

Creative Machines

AI, Art & Us

Empire of AI

Inside the reckless race for total domination

Microsoft 365 Excel All-in-One For Dummies

Excel for Dummies

The AI-Driven Leader

Harnessing AI to Make Faster, Smarter Decisions

Python All-in-One For Dummies

3rd Edition

Artificial Intelligence and Human Rights, Democracy, and the Rule of Law

Computational Intelligence Techniques

Scary Smart

The Future of Artificial Intelligence and How You Can Save Our World

The Shortest History of AI

Digital Daily Management

Transforming Data to Improvement

Application of Computational Techniques in Power Systems for Power Quality Improvement

Knowledge-based Engineering for Innovation

Transforming Cybersecurity with Machine Learning

Transforming Cybersecurity with Machine Learning

Ideal Subjects Volume 76

The Abstract People of AI

Ideal Subjects Volume 76

The Abstract People of AI

Hands-On Machine Learning with Scikit-Learn and PyTorch

Concepts, Tools, and Techniques to Build Intelligent Systems

Proceedings of the International Conference on AI and Robotics

AIR 2025, Volume 1

ICT Systems and Sustainability

Proceedings of ICT4SD 2025, Volume 6

Storytelling with Data

A Data Visualization Guide for Business Professionals, 10th Anniversary Edition

This product is categorised by