Linear Programming and Algorithms for Communication Networks

Linear Programming and Algorithms for Communication Networks: A Practical Guide to Network Design, Control, and Management

Published:
Content:
Author(s):
Free Standard Shipping

Purchasing Options

Hardback
$125.95 $100.76
ISBN 9781466552630
Cat# K15229
Add to cart
SAVE 20%
eBook (VitalSource)
$125.95 $88.17
ISBN 9781466552647
Cat# KE20102
Add to cart
SAVE 30%
eBook Rentals
Other eBook Options:
 
 

Features

  • Fills the gap between the theory of mathematical programming and its practical implementation in network design and control
  • Provides an understanding of the fundamentals of mathematical programming for communication networks
  • Uses the GNU Linear Programming Kit (GLPK) package, which is designed for solving linear programming and mixed integer programming problems
  • Examines typical problems and suggests solutions for use in modern communication networks
  • Includes practical algorithms and programs to encourage GLPK usage

Summary

Explaining how to apply to mathematical programming to network design and control, Linear Programming and Algorithms for Communication Networks: A Practical Guide to Network Design, Control, and Management fills the gap between mathematical programming theory and its implementation in communication networks. From the basics all the way through to more advanced concepts, its comprehensive coverage provides readers with a solid foundation in mathematical programming for communication networks.

Addressing optimization problems for communication networks, including the shortest path problem, max flow problem, and minimum-cost flow problem, the book covers the fundamentals of linear programming and integer linear programming required to address a wide range of problems. It also:

  • Examines several problems on finding disjoint paths for reliable communications
  • Addresses optimization problems in optical wavelength-routed networks
  • Describes several routing strategies for maximizing network utilization for various traffic-demand models
  • Considers routing problems in Internet Protocol (IP) networks
  • Presents mathematical puzzles that can be tackled by integer linear programming (ILP)

Using the GNU Linear Programming Kit (GLPK) package, which is designed for solving linear programming and mixed integer programming problems, it explains typical problems and provides solutions for communication networks. The book provides algorithms for these problems as well as helpful examples with demonstrations. Once you gain an understanding of how to solve LP problems for communication networks using the GLPK descriptions in this book, you will also be able to easily apply your knowledge to other solvers.

Table of Contents

Optimization Problems for Communications Networks
Shortest path problem
Max flow problem
Minimum-cost flow problem

Basics of Linear Programming
Optimization problem
Linear programming problem
Simplex method
Dual problem
Integer linear programming problem

GLPK (GNU Linear Programming Kit)
How to obtain GLPKand install it
Usage of GLPK

Basic Problems for Communication Networks
Shortest path problem
     Linear programming problem 
     Dijkstra’s algorithm 
     Bellman-Ford algorithm
Max flow problem 
     Linear programming problem 
     Ford-Fulkerson algorithm 
     Max flow and minimum cut
Minimum-cost flow problem 
     Linear programming problem 
     Cycle-canceling algorithm
Relationship among three problems

Disjoint Path Routing
Basic disjoint path problem 
     Integer linear programming problem 
     Disjoint shortest pair algorithm 
     Suurballe’s algorithm
Disjoint paths with shared risk link group 
     Shared risk link group (SRLG) 
     Integer linear programming
     Weight-SRLG algorithm
Disjoint paths in multi-cost networks 
     Multi-cost networks 
     Integer linear programming problem 
     KPA: k-penalty with auxiliary link costs matrix
     KPI: k-penalty with initial link costs matrix 
     Performance comparison of KPA and KPI

Optical Wavelength-Routed Network
Wavelength assignment problem
Graph coloring problem
Integer linear programming
Largest degree first

Routing and Traffic-Demand Model
Networkmodel
Pipemodel
Hosemodel
HSDT model
HLT model

IP Routing
Routing protocol
Link weights and routing 
     Tabu search
Preventive start-time optimization (PSO) 
     Three policies to determine link weights 
     PSOmodel 
     PSO-L 
     PSO-W 
     PSO-W algorithm based on tabu search
Performance of PSO-W

Mathematical Puzzles
Sudoku puzzle 
     Overview 
     Integer linear programming problem
River crossing puzzle 
     Overview 
     Integer linear programming approach 
     Shortest path approach
     Comparison of two approaches
Lattice puzzle 
     Overview 
     Integer linear programming

A. Derivation of Eqs. (7.6a)–(7.6c) for hose model
B. Derivation of Eqs. (7.12a)–(7.12c) for HSDT model
C. Derivation of Eqs. (7.16a)–(7.16d) for HLT model

Answers to Exercises

Index

Author Bio(s)

Eiji Oki is an Associate Professor at the University of Electro-Communications, Tokyo, Japan. He received the B.E. and M.E. degrees in instrumentation engineering and a Ph.D. degree in electrical engineering from Keio University, Yokohama, Japan, in 1991, 1993, and 1999, respectively. In 1993, he joined Nippon Telegraph and Telephone Corporation (NTT) Communication Switching Laboratories, Tokyo, Japan. He has been researching network design and control, traffic-control methods, and high-speed switching systems. From 2000 to 2001, he was a Visiting Scholar at the Polytechnic Institute of New York University, Brooklyn, New York, where he was involved in designing terabit switch/router systems. He was engaged in researching and developing high-speed optical IP backbone networks with NTT Laboratories. He joined the University of Electro-Communications, Tokyo, Japan, in July 2008.

He has been active in THE standardization of path computation element (PCE) and GMPLS in IETF. He wrote more than ten IETF RFCs and drafts. He served as a Guest Co-Editor for the Special Issue on "Multi-Domain Optical Networks: Issues and Challenges," June 2008, in IEEE Communications Magazine; a Guest Co-Editor for the Special Issue on Routing, "Path Computation and Traffic Engineering in Future Internet," December 2007, in the Journal of Communications and Networks; a Guest Co-Editor for the Special Section on "Photonic Network Technologies in Terabit Network Era," April 2011, in IEICE Transactions on Communications; a Technical Program Committee (TPC) Co-Chair for the Workshop on High-Performance Switching and Routing in 2006, 2010 and 2012; a Track Co-Chair on Optical Networking for ICCCN 2009; a TPC Co-Chair for the International Conference on IP+Optical Network (iPOP 2010); and a Co-Chair of Optical Networks and Systems Symposium for IEEE International Conference on Communications (ICC 2011).

Prof. Oki was the recipient of the 1998 Switching System Research Award and the 1999 Excellent Paper Award presented by IEICE, the 2001 Asia-Pacific Outstanding Young Researcher Award presented by IEEE Communications Society for his contribution to broadband network, ATM, and optical IP technologies, and the 2010 Telecom System Technology Prize by the Telecommunications Advanced Foundation.

He has co-authored three books, Broadband Packet Switching Technologies, published by John Wiley, New York, in 2001, GMPLS Technologies, published by CRC Press, Boca Raton, FL, in 2005, and Advanced Internet Protocols, Services, and Applications, which will be published by Wiley in March 2012. He is an IEEE Senior Member.

Downloads / Updates

Resource OS Platform Updated Description Instructions
lpbookprograms.zip Cross Platform August 29, 2012 Additional Materials

 
Textbooks
Other CRC Press Sites
Featured Authors
STAY CONNECTED
Facebook Page for CRC Press Twitter Page for CRC Press You Tube Channel for CRC Press LinkedIn Page for CRC Press Google Plus Page for CRC Press Pinterest Page for CRC Press
Sign Up for Email Alerts
© 2014 Taylor & Francis Group, LLC. All Rights Reserved. Privacy Policy | Cookie Use | Shipping Policy | Contact Us