Routing, Flow, and Capacity Design in Communication and Computer Networks (Hardcover)

Michal Pioro, Deep Medhi

  • 出版商: Morgan Kaufmann
  • 出版日期: 2004-06-01
  • 售價: $2,980
  • 貴賓價: 9.5$2,831
  • 語言: 英文
  • 頁數: 800
  • 裝訂: Hardcover
  • ISBN: 0125571895
  • ISBN-13: 9780125571890
  • 相關分類: Computer-networks
  • 已絕版

買這商品的人也買了...

商品描述

Description:

In network design, the gap between theory and practice is woefully broad. This book narrows it, comprehensively and critically examining current network design models and methods. You will learn where mathematical modeling and algorithmic optimization have been under-utilized. At the opposite extreme, you will learn where they tend to fail to contribute to the twin goals of network efficiency and cost-savings. Most of all, you will learn precisely how to tailor theoretical models to make them as useful as possible in practice.

Throughout, the authors focus on the traffic demands encountered in the real world of network design. Their generic approach, however, allows problem formulations and solutions to be applied across the board to virtually any type of backbone communication or computer network. For beginners, this book is an excellent introduction. For seasoned professionals, it provides immediate solutions and a strong foundation for further advances in the use of mathematical modeling for network design.

 

Table of Contents:

Foreword
Preface

PART I - INTRODUCTORY NETWORK DESIGN

Chapter 1 - Overview
1.1 A Network Analogy
1.2 Communication and Computer Networks, and Network Providers
1.3 Notion of Traffic and Traffic Demand
1.4 A Simple Design Example
1.5 Notion of Routing and Flows
1.6 Architecture of Networks: Multi-Layer Networks
1.7 Network Management Cycle
1.8 Scope of the Book
1.9 Naming and Numbering Convention
1.10 Summary

Chapter 2 - Network Design Problems—Notation and Illustrations
2.1 A Network Flow Example in Link-Path Formulation
2.2 Node-Link Formulation
2.3 Notions and Notations
2.4 Dimensioning Problems
2.5 Shortest-Path Routing
2.6 Fair Networks
2.7 Topological Design
2.8 Restoration Design
2.9

  • Multi-Layer Networks Modeling
    2.10 Summary
    Exercises for Chapter 2

    Chapter 3 - Technology-Related Modeling Examples
    3.1 IP Networks: Intra-Domain Traffic Engineering
    3.2 MPLS Networks: Tunneling Optimization
    3.3 ATM Networks: Virtual Path Design
    3.4 Digital Circuit-Switched Telephone Networks: Single–Busy Hour and Multi–Busy Hour Network Dimensioning
    3.5 SONET/SDH Transport Networks: Capacity and Protection Design
    3.6 SONET/SDH Rings: Ring Bandwidth Design
    3.7 WDM Networks: Restoration Design with Optical Cross-Connects
    3.8 IP Over SONET: Combined Two-Layer Design
    3.9 Summary and Further Reading
    Exercises for Chapter 3

    PART II - DESIGN MODELING AND METHODS

    Chapter 4 - Network Design Problem Modeling
    4.1 Basic Uncapacitated and Capacitated Design Problems
    4.2 Routing Restrictions
    4.3 Non-Linear Link Dimensioning, Cost, and Delay Functions
    4.4 Budget Constraint
    4.5 Incremental NDPs
    4.6 Extensions of Problem Modeling
    4.7 Summary and Further Reading
    Exercises for Chapter 4

    Chapter 5 - General Optimization Methods for Network Design
    5.1 Linear Programming
    5.2 Mixed-Integer Programming
    5.3 Stochastic Heuristic Methods
    5.4 LP Decomposition Methods
    5.5 Gradient Minimization and Other Approaches for Convex Programming Problems
    5.6 Special Heuristics for Concave Programming Problems
    5.7 Solving Multi-Commodity Flow Problems
    5.8 Summary and Further Reading
    Exercises for Chapter 5

    Chapter 6 - Location and Topological Design
    6.1 Node Location Problem
    6.2 Joint Node Location and Link Connectivity Problem
    6.3 Topological Design
    6.4 Lower Bounds for Branch-and-Bound
    6.5 Summary and Further Reading
    Exercises for Chapter 6

    Chapter 7 - Networks With Shortest-Path Routing
    7.1 Shortest-Path Routing Allocation Problem
    7.2 MIP Formulation of the Shortest-Path Routing Allocation Problem and Dual Problems
    7.3 Heuristic Direct Methods for Determining the Link Metric System
    7.4 Two-Phase Solution Approach
    7.5 Impact Due to Stochastic Approaches
    7.6 Impact of Different Link Weight System
    7.7 Impact on Different Performance Measures
    7.8 Uncapacitated Shortest-Path Routing Problem
    7.9 Optimization of the Link Metric System under Transient Failures
    7.10
  • NP-Completeness of the Shortest-Path Routing Allocation Problem
    7.11
  • Selfish Routing and its Relation to Optimal Routing
    7.12 Summary and Further Reading
    Exercises for Chapter 7

    Chapter 8 - Fair Networks
    8.1 Notions of Fairness
    8.2 Design Problems for Max-Min Fairness (MMF)
    8.3 Design Problems for Proportional Fairness (PF)
    8.4 Summary and Further Reading
    Exercises for Chapter 8

    PART III - ADVANCED MODELS

    Chapter 9 - Restoration and Protection Design of Resilient Networks
    9.1 Failure States, Protection/Restoration Mechanisms, and Diversity
    9.2 Link Capacity Protection/Restoration
    9.3 Demand Flow Re-Establishment
    9.4 Extensions
    9.5 Protection Problems
    9.6 Applicability of the Protection/Restoration Design Models
    9.7 Summary and Further Reading
    Exercises for Chapter 9

    Chapter 10 - Application of Optimization Techniques for Protection and Restoration Design
    10.1 Path Generation
    10.2 Lagrangian Relaxation (LR) With Subgradient Maximization
    10.3 Benders’ Decomposition
    10.4 Modular Links
    10.5 Stochastic Heuristic Methods
    10.6
Selected Application: Wavelength Assignment Problem in WDM Networks
10.7 Summary and Further Reading
Exercises for Chapter 10

Chapter 11 - Multi-Hour and Multi–Time-Period Network Modeling and Design
11.1 Multi-Hour Design
11.2 Multi-Period Design
11.3 Summary and Further Reading
Exercises for Chapter 11

Chapter 12 - Multi-Layer Networks: Modeling and Design
12.1 Design of Multi-Layer Networks
12.2 Modeling of Multi-Layer Networks for Restoration Design
12.3 Multi-Layer Design With Multi-Hour Traffic
12.4 Application of Decomposition Methods for Two-Layer Design
12.5 Numerical Results
12.6 Cost Comparison
12.7 Grooming/Multiplex Bundling
12.8 Summary and Further Reading
Exercises for Chapter 12

Chapter 13 - Restoration Design of Single- and Multi-Layer Fair Networks
13.1 Restoration Design of Single-Layer PF Networks
13.2 Decomposition Methods for the Single-Layer Restoration Problems
13.3 Design of Resilient Two-Layer PF Networks
13.4 Extensions
13.5 Summary and Further Reading
Exercises for Chapter 13

APPENDICES

Appendix A - Optimization Theory Refresher
A.1 Basic Notions
A.2 Karush-Kuhn-Tucker (KKT) Optimality Conditions
A.3 Interpretation of the Lagrange Multipliers in the KKT Conditions
A.4 Numerical Methods for Finding Minima of Differentiable Problems
A.5 Duality
A.6 Duality for Convex Programs
A.7 Duality for Convex Objective and Linear Constraints
A.8 Subgradient Maximization of the Dual Function
A.9 Subgradient Maximization of the Dual Function of Linear Programming Problems

Appendix B - Introduction to Complexity Theory and NP-Completeness
B.1 Introduction
B.2 Complexity of a Problem
B.3 Deterministic and Non-Deterministic Machines
B.4 The Classes of Problems Known as P and NP
B.5 Reducibility Relation between Problems
B.6 The Class of NP-Complete Problems
B.7 The Satisfiability Problem and Cook’s Theorem
B.8 Network Flow Problems
B.9 Final Remarks

Appendix C - Shortest-Path Algorithms
C.1 Introduction and Basic Notions
C.2 Basic Shortest-Path Problem
C.3 K-Shortest Paths and All Optimal Paths
C.4 Shortest Sets of Disjoint Paths

Appendix D - Using LP/MIP Packages
D.1 Solving Linear Programming Problems using Maple, Matlab, and CPLEX
D.2 Solving (Mixed) Integer Programming Problems Using CPLEX
D.3 Modeling Using AMPL
D.4 Final Remark

List of Acronyms
Solutions to Selected Exercises
Bibliography
Index

 

商品描述(中文翻譯)

描述:
在網路設計中,理論與實踐之間的差距非常大。本書對當前的網路設計模型和方法進行了全面而批判性的檢查,縮小了這一差距。您將學習到數學建模和算法優化在哪些地方被過度低估。相反,您將學習到它們在實現網路效率和節省成本的雙重目標方面往往無法貢獻的地方。最重要的是,您將學習到如何精確地調整理論模型,使其在實踐中盡可能有用。

整本書中,作者們專注於網路設計中遇到的實際交通需求。然而,他們的通用方法允許問題的形式和解決方案適用於幾乎任何類型的主幹通信或計算機網路。對於初學者來說,本書是一本很好的入門書。對於經驗豐富的專業人士來說,它提供了即時的解決方案和在使用數學建模進行網路設計方面進一步進展的堅實基礎。

目錄:
前言
前言
第一部分 - 入門網路設計
第1章 - 概述
1.1 網路類比
1.2 通信和計算機網路,以及網路提供商
1.3 交通和交通需求的概念
1.4 簡單的設計示例
1.5 路由和流量的概念
1.6 網路架構:多層網路
1.7 網路管理循環
1.8 本書的範圍
1.9 命名和編號慣例
1.10 摘要

第2章 - 網路設計問題-符號和示例
2.1 鏈路-路徑形式的網路流量示例
2.2 節點-鏈路形式
2.3 概念和符號
2.4 尺寸問題
2.5 最短路由
2.6 公平網路
2.7 拓撲設計
2.8 恢復設計
2.9

多層網路建模
2.10 摘要
第2章練習

第3章 - 與技術相關的建模示例
3.1 IP網路:域內流量工程
3.2 MPLS網路:隧道優化
3.3 ATM網路:虛擬路徑設計
3.4 數字電路交換電話網路:單繁忙小時和多繁忙小時網路尺寸
3.5 SONET/SDH傳輸網路:容量和保護設計
3.6 SONET/SDH環:環帶寬設計
3.7 WDM網路:帶有光交叉連接的恢復設計
3.8 IP Over SONET:結合的兩層設計
3.9 摘要和進一步閱讀
第3章練習

第二部分 - 設計建模和方法
第4章 - 網路設計問題建模
4.1 基本的非容量和容量設計問題
4.2 路由限制
4.3 非線性鏈路尺寸、成本和延遲函數
4.4 預算限制
4.5 增量式NDP
4.6 問題建模的擴展
4.7 摘要和進一步閱讀
第4章練習

第5章 - 網路設計的通用優化方法
5.1 線性規劃
5.2 混合整數規劃
5.3 隨機啟發式方法
5.4 LP分解方法
5.5 梯度最小化和其他凸規劃問題的方法
5.6 凹規劃問題的特殊啟發式方法
5.7 解決多商品流問題
5.8 摘要和進一步閱讀
第5章練習

第6章 - 位置和拓撲設計
6.1 節點位置問題
6.2 聯合節點位置和線路