Atjaunināt sīkdatņu piekrišanu

Mathematical Aspects of Network Routing Optimization 2011 ed. [Hardback]

,
  • Formāts: Hardback, 208 pages, height x width: 235x155 mm, weight: 518 g, XXIV, 208 p., 1 Hardback
  • Sērija : Springer Optimization and Its Applications 53
  • Izdošanas datums: 30-Aug-2011
  • Izdevniecība: Springer-Verlag New York Inc.
  • ISBN-10: 1461403103
  • ISBN-13: 9781461403104
Citas grāmatas par šo tēmu:
  • Hardback
  • Cena: 91,53 €*
  • * ši ir gala cena, t.i., netiek piemērotas nekādas papildus atlaides
  • Standarta cena: 107,69 €
  • Ietaupiet 15%
  • Grāmatu piegādes laiks ir 3-4 nedēļas, ja grāmata ir uz vietas izdevniecības noliktavā. Ja izdevējam nepieciešams publicēt jaunu tirāžu, grāmatas piegāde var aizkavēties.
  • Daudzums:
  • Ielikt grozā
  • Piegādes laiks - 4-6 nedēļas
  • Pievienot vēlmju sarakstam
Mathematical Aspects of Network Routing Optimization 2011 ed.Palielināt
  • Formāts: Hardback, 208 pages, height x width: 235x155 mm, weight: 518 g, XXIV, 208 p., 1 Hardback
  • Sērija : Springer Optimization and Its Applications 53
  • Izdošanas datums: 30-Aug-2011
  • Izdevniecība: Springer-Verlag New York Inc.
  • ISBN-10: 1461403103
  • ISBN-13: 9781461403104
Citas grāmatas par šo tēmu:
Permanent link: https://www.kriso.lv/db/9781461403104.html
Keywords:
Before the appearance of broadband links and wireless systems, networks have been used to connect people in new ways. Now, the modern world is connected through large-scale, computational networked systems such as the Internet. Because of the ever-advancing technology of networking, efficient algorithms have become increasingly necessary to solve some of the problems developing in this area."Mathematical Aspects of Network Routing Optimization" focuses on computational issues arising from the process of optimizing network routes, such as quality of the resulting links and their reliability. Algorithms are a cornerstone for the understanding of the protocols underlying multicast routing. The main objective in the text is to derive efficient algorithms, with or without guarantee of approximation. Notes have been provided for basic topics such as graph theory and linear programming to assist those who are not fully acquainted with the mathematical topics presented throughout the book."Mathematical Aspects of Network Routing Optimization" provides a thorough introduction to the subject of algorithms for network routing, and focuses especially on multicast and wireless ad hoc systems. This book is designed for graduate students, researchers, and professionals interested in understanding the algorithmic and mathematical ideas behind routing in computer networks. It is suitable for advanced undergraduate students, graduate students, and researchers in the area of network algorithms.

This book offers an overview of network routing optimization and acts as an introduction to algorithms used to solve network optimization problems. This solid introduction to network routing optimization also presents topics for further advanced research.

Recenzijas

From the reviews:

This book provides first an elementary introduction into algorithms for network routing. In principle, the investigations of this book focus on two major types of problems, namely minimum cost routing and cache placement problems. The book is well-written in an easily understanding form. the book can be recommended to graduate students, researchers and professionals interested in routing in computer networks and network algorithms. (Frank Werner, Zentralblatt MATH, Vol. 1225, 2012)

1 Unicast Routing Algorithms
1(12)
1.1 Unicast Routing Concepts
1(1)
1.2 Flooding Algorithm
2(3)
1.2.1 Implementation
3(1)
1.2.2 Time-To-Live Window Strategy
4(1)
1.3 Routing via Shortest-Paths
5(1)
1.4 Distance-Vector Algorithms
6(2)
1.4.1 The Bellman-Ford Algorithm
6(1)
1.4.2 Implementation
6(1)
1.4.3 Analysis of the Bellman-Ford Algorithm
7(1)
1.4.4 Distributed Implementation
8(1)
1.5 Link-State Algorithms
8(2)
1.5.1 Dijkstra's Algorithm
9(1)
1.5.2 Distributed Implementation of Link-State Algorithms
9(1)
1.6 Additional Resources
10(3)
2 Multicast Routing
13(16)
2.1 Introduction
14(3)
2.1.1 Definitions
15(1)
2.1.2 Applications
16(1)
2.1.3 Optimization Objectives
16(1)
2.2 Multicast Technologies
17(2)
2.3 Major Multicast Implementations
19(1)
2.4 Basic Routing Techniques
20(5)
2.4.1 Graph Theory Terminology
20(1)
2.4.2 Flooding Algorithm
21(1)
2.4.3 Algorithm Classification
22(1)
2.4.4 Shortest Path Problems with Delay Constraints
23(1)
2.4.5 Delay Constrained Minimum Spanning Trees
23(1)
2.4.6 Center-Based Trees and Topological Center
24(1)
2.5 Additional Restrictions
25(1)
2.5.1 Nonsymmetric Links
25(1)
2.5.2 Delay Variation
26(1)
2.6 Additional Resources
26(3)
3 Steiner Trees and Multicast
29(18)
3.1 Basic Concepts
29(1)
3.2 Steiner Trees on Graphs
30(1)
3.3 Modeling Multicast Routing Constraints
31(3)
3.3.1 KMB Algorithm
32(1)
3.3.2 The KMB Algorithm on Multicast Networks
33(1)
3.3.3 Other Algorithms for Steiner Tree
33(1)
3.4 Steiner Tree Problems with Delay Constraints
34(5)
3.4.1 Adapting a Steiner Tree Algorithm
35(1)
3.4.2 Algorithms for Sparse Steiner Trees
35(1)
3.4.3 Combining Cost and Delay Optimization
36(1)
3.4.4 Constrained Shortest Paths
37(1)
3.4.5 Link Capacity Constraints
38(1)
3.4.6 Delay Bounded Paths
38(1)
3.5 Sparsity and Delay Minimization
39(2)
3.5.1 Sparse Groups
40(1)
3.5.2 Minimizing Configuration Time
41(1)
3.6 An IP Formulation for Multicast Routing
41(3)
3.6.1 Minimizing Bandwidth Utilization
43(1)
3.7 The Degree-Constrained Steiner Problem
44(1)
3.8 Conclusion
45(2)
4 Online Multicast Routing
47(10)
4.1 Introduction
47(1)
4.2 Online Multicast and Tree Recalculation
48(1)
4.3 Speeding Up Routing Tree Computations
48(4)
4.3.1 Working with High Complexity Algorithms
49(1)
4.3.2 Random Graph Models
50(1)
4.3.3 Facilitated Inclusion of Group Members
51(1)
4.4 Quality of Service Maintenance for Online Multicast Routing
52(3)
4.4.1 Problem Definition
52(2)
4.4.2 Updating the Routing Tree
54(1)
4.5 OSPF-Based Algorithms for Online Multicast Routing
55(1)
4.6 Conclusion
55(2)
5 Distributed Algorithms for Multicast Routing
57(8)
5.1 Distributed Algorithm Concepts
57(1)
5.2 Distributed Version of the KMB Heuristic
58(1)
5.3 Distributed Algorithm for Audio and Video on Multicast
59(1)
5.4 An Adaptation of Prim's Algorithm
59(1)
5.5 Modifications of Dijkstra's Algorithm
60(1)
5.6 Using Flooding for Path Computation
61(1)
5.7 Algorithms for Sparse Groups
62(1)
5.8 A Comparison of Distributed Approaches
62(2)
5.9 Conclusion
64(1)
6 Center-Based Trees and Multicast Packing
65(12)
6.1 Center-Based Trees
65(6)
6.1.1 Center-Based Tree Concepts
66(1)
6.1.2 The Topological Center Problem
67(1)
6.1.3 Median and Centroid
68(1)
6.1.4 Properties of Centroids
69(1)
6.1.5 The CBT Protocol
70(1)
6.2 The Multicast Packing Problem
71(2)
6.2.1 Problem Description
71(1)
6.2.2 Integer Programming Formulation
72(1)
6.3 Multicast Dimensioning
73(2)
6.4 Conclusion
75(2)
7 Metaheuristics for Multicast Routing
77(18)
7.1 Metaheuristics
77(5)
7.1.1 Genetic Algorithms
78(2)
7.1.2 Tabu Search
80(1)
7.1.3 Simulated Annealing
81(1)
7.1.4 Greedy Randomized Adaptive Search Procedure
81(1)
7.2 A GRASP for Multicast Routing
82(2)
7.2.1 Introduction
82(2)
7.3 Basic Algorithm for the MRP
84(8)
7.3.1 Adapting the Solution to the MRP
84(1)
7.3.2 Metaheuristic Description
85(7)
7.4 Experimental Results
92(2)
7.5 Conclusion
94(1)
8 The Point-to-Point Connection Problem
95(22)
8.1 Introduction
95(1)
8.2 Point-to-Point Connection and Multicast
95(1)
8.3 Problem Formulation
96(3)
8.3.1 Mathematical Programming Formulation
98(1)
8.4 Asynchronous Team Algorithms
99(3)
8.4.1 Formal Definition
99(2)
8.4.2 Characterization of an A-Team
101(1)
8.5 Solving the PPC Problem
102(3)
8.5.1 Global Data Structures
102(1)
8.5.2 Heuristic Strategies
102(3)
8.6 A Partially Synchronous Distributed Model
105(6)
8.6.1 The Partially Synchronous Model
105(1)
8.6.2 Distributed Memory Executions
106(1)
8.6.3 Types of Messages
107(1)
8.6.4 Local Variables
108(1)
8.6.5 Simulating the Partially Synchronous Model
108(3)
8.7 Computational Results
111(4)
8.7.1 Hardware and Software Configuration
111(1)
8.7.2 Sequential Tests
111(2)
8.7.3 Parallel Tests
113(2)
8.8 Concluding Remarks
115(2)
9 Streaming Cache Placement
117(18)
9.1 Introduction
117(3)
9.1.1 Motivation
118(1)
9.1.2 Formal Description of the SCPP
118(1)
9.1.3 Related Work
119(1)
9.2 Types of Cache Placement Problems
120(3)
9.2.1 The Tree Cache Placement Problem
120(2)
9.2.2 The Flow Cache Placement Problem
122(1)
9.3 Complexity of the Cache Placement Problems
123(4)
9.3.1 Complexity of the TSCPP
123(3)
9.3.2 Complexity of the FSCPP
126(1)
9.4 Complexity of Approximation
127(1)
9.5 Hardness of Approximation
128(2)
9.6 Improved Hardness Result for FSCPP
130(3)
9.7 Conclusion
133(2)
10 Algorithms for Cache Placement
135(14)
10.1 Introduction
135(1)
10.2 An Approximation Algorithm for SCPP
136(3)
10.2.1 A Simple Algorithm for TSCPP
136(1)
10.2.2 A Flow-Based Algorithm for FSCPP
137(2)
10.3 Construction Algorithms for the SCPP
139(6)
10.3.1 Connecting Destinations
139(3)
10.3.2 Adding Caches to a Solution
142(3)
10.4 Experimental Results
145(2)
10.5 Conclusion
147(2)
11 Distributed Routing on Ad Hoc Networks
149(14)
11.1 Introduction
149(2)
11.1.1 Graph-Based Model of Ad Hoc Networks
149(1)
11.1.2 Existing Algorithms
150(1)
11.2 Ad Hoc Technology and Concepts
151(2)
11.2.1 Virtual Backbone Computation
152(1)
11.2.2 Unit Disk Graphs
153(1)
11.3 Maximum Connected Dominating Sets
153(1)
11.3.1 Existing Algorithms
154(1)
11.4 An Algorithm for the MCDS Problem
154(3)
11.4.1 A Distributed Implementation
156(1)
11.5 Distributed Heuristic
157(5)
11.5.1 Computational Complexity
158(2)
11.5.2 Experimental Results
160(2)
11.6 Conclusion
162(1)
12 Power-Aware Routing in MANETs
163(14)
12.1 Introduction
163(1)
12.1.1 Power Control Problem
163(1)
12.2 MANETs and Power Management
164(1)
12.2.1 Resource Limitations
164(1)
12.3 MANET Architecture
165(1)
12.4 Related Work
166(1)
12.5 Problem Formulation
167(3)
12.5.1 An Integer Programming Model
168(2)
12.6 Variable Neighborhood Search Algorithm
170(3)
12.6.1 Neighborhood Descriptions
171(1)
12.6.2 Distributed VNS Algorithm
172(1)
12.7 Computational Experiments
173(2)
12.7.1 Experimental Settings
173(1)
12.7.2 Lower Bound on Power Consumption
174(1)
12.7.3 Integer Programming Results
174(1)
12.7.4 Heuristic Results
174(1)
12.8 Conclusion
175(2)
A Concepts in Communication Networks
177(14)
A.1 Computer Networks
177(7)
A.1.1 Network Topology
178(1)
A.1.2 Data Packets and Circuits
178(1)
A.1.3 Protocols
179(1)
A.1.4 Protocol Stacks and Layers
180(1)
A.1.5 Routing
181(1)
A.1.6 Quality of Service
182(1)
A.1.7 Algorithmic Performance
183(1)
A.2 Main Algorithmic Problems
184(5)
A.2.1 Network Design
184(1)
A.2.2 Packet Routing
185(1)
A.2.3 Algorithmic Performance and Complexity
186(1)
A.2.4 Heuristic Methods
187(2)
A.2.5 Distributed Algorithms
189(1)
A.3 Additional Resources
189(2)
References 191(10)
Index 201(4)
About the Authors 205
Carlos Oliveira obtained a PhD in Operations Research from the University of Florida, a Masters in Computer Science from Universidade Federal do Cearį, Brazil, and a B.Sc. in Computer Science from Universidade Estadual do Cearį, Brazil. Carlos has spent more than ten years working on combinatorial optimization problems in several areas, including telecommunications, computational biology, and logistics. He has written more than 20 papers on optimization aspects of these areas. He is an associate editor for J. of Global Optimization and Optimization Letters.

Carlos was assistant professor at Oklahoma State University from 2004 to 2006. Since then he has worked as a consultant in the areas of optimization and software engineering. He works in New York City and lives in New Jersey with his wife and son. Carlos Oliveira can be contacted at his web site http://coliveira.net.





Panos Pardalos is Distinguished Professor of Industrial and Systems Engineering at the University of Florida. He is also affiliated faculty member of the Computer Science Department, the Hellenic Studies Center, and the Biomedical Engineering Program. He is also the director of the Center for Applied Optimization.Dr. Pardalos obtained a PhD degree from the University of Minnesota in Computer and Information Sciences. Dr. Pardalos is a world leading expert in global and combinatorial optimization. He is the editor-in-chief of the Journal of Global Optimization, Journal of Optimization Letters, and Computational Management Science. In addition, he is the managing editor of several book series, and a member of the editorial board of several international journals. He is the author of 8 books and the editor of several books. He has written numerous articles and developed several well known software packages. His research is supported by National Science Foundation and other government organizations. His recent research interests include network design problems, optimization intelecommunications, e-commerce, data mining, biomedical applications, and massive computing.