"Academic Press is an imprint of Elsevier"--T.p.

Includes bibliographical references (pages 431-435) and index.

Machine generated contents note: 1.1. The Purpose of this Book -- 1.2. The Design Process -- 1.3.A First Example -- 1.4. Algorithms for Hard Problems -- 1.4.1.Complexity Classes -- 1.4.2. Showing Problem Hardness -- 1.5. Models and Algorithms -- 1.5.1. Classification of Algorithms -- 1.5.2. Randomization -- 1.5.3. Monte Carlo Techniques -- 1.6.Organization of this Book -- 1.7. Summary -- 2.1. Preliminaries -- 2.1.1. Basic Flow Concepts -- 2.1.2. Graph Flow Problems -- 2.2.Network Representations -- 2.3. Graph Connectivity -- 2.3.1. Depth-First Search -- 2.3.2. Breadth-First Search -- 2.4. Shortest Paths -- 2.4.1. Shortest Path as a Linear Program -- 2.4.2. Dijkstra's Algorithm -- 2.4.3. The Bellman-Ford Algorithm -- 2.4.4. The Floyd-Warshall Algorithm -- 2.5. Maximum Flows -- 2.5.1. Maximum Flow as a Linear Program -- 2.5.2. The Ford-Fulkerson Labeling Algorithm -- 2.5.3. Approximate Maximum Flow -- 2.6. Summary -- 3.1. Multi-Terminal Flows -- 3.1.1. The Gomory-Hu Algorithm -- 3.2. Minimum-Cost Flows. Contents note continued: 3.2.1. Problem Formulation -- 3.2.2. The Out-of-Kilter Algorithm -- 3.2.3. Variants and Modifications -- 3.3. Multi-Commodity Flows -- 3.3.1. Problem Formulation -- 3.3.2. An Approximation Algorithm -- 3.4. Summary -- 4.1. Capacitated Network Design -- 4.1.1. Cost Functions -- 4.1.2. Routing -- 4.2. Important Properties of Graphs -- 4.2.1. Sparseness of Graphs -- 4.2.2. Example Topologies -- 4.3. Ring Topologies -- 4.3.1. The Nearest Neighbor Algorithm -- 4.3.2. Incremental Insertion -- 4.3.3.k-Optimal Methods -- 4.4. Spanning Trees and Spanners -- 4.4.1. Properties of Spanners -- 4.4.2.A Greedy Algorithm for Spanner Construction -- 4.5. Gomory-Hu Design -- 4.5.1. Constant Edge Costs -- 4.5.2. Extension to General Networks -- 4.6. Randomized Topological Design -- 4.6.1. Expander Graphs -- 4.6.2. Monte Carlo Optimization -- 4.7. Genetic Algorithms -- 4.8. Resource Allocation -- 4.8.1. The Knapsack Problem -- 4.8.2. Dynamic Programming -- 4.8.3. Branch-and-Bound -- 4.9. Summary. Contents note continued: 5.1. Traffic and Blocking -- 5.1.1. Point Processes -- 5.1.2. The Poisson Process -- 5.1.3. Characterization of Traffic -- 5.2. Modeling with Queues -- 5.2.1. Characteristics of Queueing Processes -- 5.2.2. Measuring System Performance -- 5.2.3. Some General Results -- 5.2.4. Simple Markovian Queues -- 5.3. Markov Chain Analysis -- 5.3.1. Discrete-Time Markov Chains -- 5.3.2. Numerical Solution of Markov Chains -- 5.3.3. Randomization -- 5.3.4. Truncation of State Space -- 5.3.5. Two Stations in Tandem -- 5.4. The Erlang B-Formula and Generalizations -- 5.4.1. Integer Number of Circuits -- 5.4.2. Non-Integer Number of Circuits -- 5.4.3. Approximations -- 5.4.4. The Erlang C-Formula -- 5.4.5. Derivatives -- 5.4.6. Inverse -- 5.5. Overflow Theory -- 5.5.1. The Hayward Approximation -- 5.5.2. The Wilkinson-Bretschneider Method -- 5.6. Summary -- 6.1. Calculating Blocking in a Network -- 6.2. Resource Allocation -- 6.2.1. Moe's Principle -- 6.2.2. An Optimization Procedure. Contents note continued: 6.3. Routing and Admission Control -- 6.3.1. Routing -- 6.4.Network Programming -- 6.4.1.Network Bounds -- 6.4.2. Symmetric Networks -- 6.4.3. The Cube Network -- 6.4.4. General Networks -- 6.5. Simulation of Loss Networks -- 6.5.1. Discrete Event Simulation -- 6.5.2. The Erlang Link -- 6.6. Efficiency and Stability of Loss Networks -- 6.6.1.Network Model -- 6.6.2. Instability -- 6.6.3. Trunk Reservation and Multiple Alternatives -- 6.7. Summary -- 7.1. General Properties of Packet Networks -- 7.1.1. Routing -- 7.2. Queueing Networks -- 7.2.1. Open Jackson Networks -- 7.2.2. The Routing Matrix -- 7.2.3. End-to-End Delay -- 7.3. Resource Allocation -- 7.3.1. Linear Costs -- 7.3.2. Concave Costs -- 7.3.3. Discrete Costs -- 7.3.4. Moe's Principle -- 7.4. Flow Optimization -- 7.4.1. The Flow Deviation Method -- 7.5. Simultaneous Resource and Flow Optimization -- 7.6. Finite Buffers -- 7.7. Local Search -- 7.7.1. The Branch Exchange Method -- 7.7.2. The Cut-Saturation Method. Contents note continued: 7.8. Simulation of General Packet Networks -- 7.8.1. The Single Link -- 7.8.2. Queueing Networks -- 7.9. Summary -- 8.1. Flow Control and Congestion Control -- 8.1.1. Virtual Channels -- 8.1.2. Transmission Control Protocol (TCP) -- 8.2. Closed Queueing Networks -- 8.2.1. The Product-Form Solution -- 8.2.2. Solving the Traffic Equation -- 8.3. Convolution -- 8.4. Mean Value Analysis -- 8.4.1. Approximate Mean Value Analysis -- 8.5. Closed Network Approximations -- 8.5.1. The Equal Throughput Method -- 8.5.2. The Fixed-Population Mean Method -- 8.5.3. Virtual Channels -- 8.6. Decomposition -- 8.6.1. Norton's Theorem -- 8.6.2. Linear Interpolation -- 8.6.3. Conditional Mean Value Analysis -- 8.7. TCP Controlled Networks -- 8.7.1. Performance Metrics -- 8.7.2. The TCP Model -- 8.7.3. Fixed-Point Equations -- 8.7.4. The Effect of TCP -- 8.8. Summary -- 9.1. Broadband Services -- 9.2. Queues in Multi-Service Networks -- 9.2.1. The M/G/1 Queue -- 9.2.2. Finite Queues. Contents note continued: 9.2.3. The M/D/1 queue -- 9.2.4. Approximations for General Queues -- 9.3. Large Deviations -- 9.3.1. The Scaled Cumulant Generation Funtion -- 9.3.2. The Chernoff Formula -- 9.3.3. Normal Approximation -- 9.3.4. Improved Approximation -- 9.3.5. Varadhan's Lemma -- 9.4. Effective Bandwidth -- 9.4.1. The Workload Process -- 9.4.2. Buffer Allocation -- 9.4.3. Calculating Effective Bandwidths -- 9.5. Modeling Services -- 9.5.1. The Basic On-Off Model -- 9.5.2. Telephony -- 9.5.3. The Markovian Additive Process -- 9.5.4. Streaming Video -- 9.5.5. Data Services -- 9.5.6. Simulation of Markov Additive Processes -- 9.6. Estimation Techniques -- 9.6.1. Constant Time-Window Estimator -- 9.6.2. Variable Time-Window Estimator -- 9.7. Finite Buffers -- 9.8. Summary -- 10.1. The Acceptance Region -- 10.2. The Binomial-Poisson-Pascal Models -- 10.2.1. The Binomial Distribution -- 10.2.2. Engset Distribution -- 10.2.3. The Negative Binomial Distribution. Contents note continued: 10.2.4. The Truncated Negative Binomial Distribution -- 10.3. Loss Systems with Multiple Services -- 10.3.1. Systems in Product form -- 10.3.2. Multi-Rate Systems -- 10.3.3. Convolution -- 10.3.4. State-Space Recursion -- 10.3.5.A Generalized Algorithm -- 10.3.6. Monte Carlo Simulation -- 10.4. Admission Control -- 10.5. Processor Load Sharing -- 10.5.1. The Single-Server Queue with Processor Sharing -- 10.5.2. Extensions to the Model -- 10.5.3.A Recursive Algorithm -- 10.6. Summary -- 11.1. Fixed-Point Network Analysis -- 11.1.1. Admission Control and Adaptive Routing -- 11.1.2. The Fixed-Point Model -- 11.2. Generalized Queueing Networks -- 11.2.1. Convolution Algorithm -- 11.2.2. Mean Value Analysis -- 11.3. Flow Analysis by Effective Bandwidth -- 11.3.1. Effective and Decoupling Bandwidths -- 11.3.2. Design Methodology for Multi-Service Networks -- 11.4. Summary -- 12.1. Connectivity and Cuts -- 12.2. Spanning Trees -- 12.2.1. The Deletion-Contraction Principle. Contents note continued: 12.2.2. Kirchhoff's Matrix-Tree Theorem -- 12.2.3. Graph Strength -- 12.3.A Primal-Dual Algorithm -- 12.4. Local Search -- 12.4.1. Testing Feasibility -- 12.4.2. Generating an Initial Solution -- 12.4.3. The Search Neighborhood -- 12.4.4. Algorithm Summary -- 12.5. The Reliability Polynomial -- 12.5.1. The Deletion-Contraction Principle -- 12.5.2. Bounds and Approximations -- 12.5.3.A Randomized Algorithm -- 12.6. Optimal Topologies and Circulants -- 12.7. Summary.

Focuses on methods and algorithms related to the design of communication networks, using optimization, graph theory, probability theory and simulation techniques. This book discusses the nature and complexity of the network design process, then introduces theoretical concepts, problems and solutions.

College of Engineering and Computer Studies