Muutke küpsiste eelistusi

E-raamat: Linear Programming and Algorithms for Communication Networks: A Practical Guide to Network Design, Control, and Management [Taylor & Francis e-raamat]

(Communication and Computer Engineering, Grad School of Informatics, Kyoto University)
  • Formaat: 208 pages, 11 Tables, black and white; 95 Illustrations, black and white
  • Ilmumisaeg: 16-Nov-2016
  • Kirjastus: CRC Press
  • ISBN-13: 9780429165160
  • Taylor & Francis e-raamat
  • Hind: 184,65 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
  • Tavahind: 263,78 €
  • Säästad 30%
  • Formaat: 208 pages, 11 Tables, black and white; 95 Illustrations, black and white
  • Ilmumisaeg: 16-Nov-2016
  • Kirjastus: CRC Press
  • ISBN-13: 9780429165160

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.

Preface ix
1 Optimization problems for communications networks
1(4)
1.1 Shortest path problem
2(1)
1.2 Max flow problem
2(1)
1.3 Minimum-cost flow problem
3(2)
2 Basics of linear programming
5(20)
2.1 Optimization problem
5(2)
2.2 Linear programming problem
7(7)
2.3 Simplex method
14(4)
2.4 Dual problem
18(2)
2.5 Integer linear programming problem
20(5)
3 GLPK (GNU Linear Programming Kit)
25(6)
3.1 How to obtain GLPK and install it
25(1)
3.2 Usage of GLPK
26(5)
4 Basic problems for communication networks
31(34)
4.1 Shortest path problem
31(14)
4.1.1 Linear programming problem
31(9)
4.1.2 Dijkstra's algorithm
40(3)
4.1.3 Bellman-Ford algorithm
43(2)
4.2 Max flow problem
45(9)
4.2.1 Linear programming problem
45(5)
4.2.2 Ford-Fulkerson algorithm
50(3)
4.2.3 Max flow and minimum cut
53(1)
4.3 Minimum-cost flow problem
54(8)
4.3.1 Linear programming problem
54(5)
4.3.2 Cycle-canceling algorithm
59(3)
4.4 Relationship among three problems
62(3)
5 Disjoint path routing
65(28)
5.1 Basic disjoint path problem
65(6)
5.1.1 Integer linear programming problem
65(4)
5.1.2 Disjoint shortest pair algorithm
69(1)
5.1.3 Suurballe's algorithm
70(1)
5.2 Disjoint paths with shared risk link group
71(9)
5.2.1 Shared risk link group (SRLG)
71(2)
5.2.2 Integer linear programming
73(4)
5.2.3 Weight-SRLG algorithm
77(3)
5.3 Disjoint paths in multi-cost networks
80(13)
5.3.1 Multi-cost networks
80(1)
5.3.2 Integer linear programming problem
81(1)
5.3.3 KPA: k-penalty with auxiliary link costs matrix
82(5)
5.3.4 KPI: k-penalty with initial link costs matrix
87(1)
5.3.5 Performance comparison of KPA and KPI
87(6)
6 Optical wavelength-routed network
93(10)
6.1 Wavelength assignment problem
93(3)
6.2 Graph coloring problem
96(1)
6.3 Integer linear programming
96(3)
6.4 Largest degree first
99(4)
7 Routing and traffic-demand model
103(20)
7.1 Network model
103(1)
7.2 Pipe model
104(1)
7.3 Hose model
105(3)
7.4 HSDT model
108(5)
7.5 HLT model
113(10)
8 IP routing
123(22)
8.1 Routing protocol
123(1)
8.2 Link weights and routing
124(7)
8.2.1 Tabu search
126(5)
8.3 Preventive start-time optimization (PSO)
131(7)
8.3.1 Three policies to determine link weights
131(1)
8.3.2 PSO model
132(1)
8.3.3 PSO-L
133(4)
8.3.4 PSO-W
137(1)
8.3.5 PSO-W algorithm based on tabu search
137(1)
8.4 Performance of PSO-W
138(7)
9 Mathematical puzzles
145(22)
9.1 Sudoku puzzle
145(4)
9.1.1 Overview
145(1)
9.1.2 Integer linear programming problem
146(3)
9.2 River crossing puzzle
149(12)
9.2.1 Overview
149(1)
9.2.2 Integer linear programming approach
150(9)
9.2.3 Shortest path approach
159(2)
9.2.4 Comparison of two approaches
161(1)
9.3 Lattice puzzle
161(6)
9.3.1 Overview
161(1)
9.3.2 Integer linear programming
162(5)
A Derivation of Eqs. (7.6a)-(7.6c) for hose model 167(2)
B Derivation of Eqs. (7.12a)-(7.12c) for HSDT model 169(4)
C Derivation of Eqs. (7.16a)-(7.16d) for HLT model 173(4)
Answers to Exercises 177(16)
Index 193
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.