Preface
Contents
1 Introduction
1.1 Networking Overview
1.2 Achieving Network Connectivity
1.2.1 Coaxial Cable
1.2.2 Twisted Pair Wiring
1.2.3 Fiber Optics
1.2.4 Microwave Line of Sight
1.2.5 Satellites
Geostationary Satellites
Low Earth Orbit Satellites
Other Orbits: MEO and Molniya
1.2.6 Cellular Systems
1.2.7 Ad Hoc Networks
1.2.8 Wireless Sensor Networks
1.3 Multiplexing
1.3.1 Frequency Division Multiplexing (FDM)
1.3.2 Time Division Multiplexing (TDM)
1.3.3 Frequency Hopping
1.3.4 Direct Sequence Spread Spectrum
1.4 Circuit Switching Versus Packet Switching
1.5 Layered Protocols
1.5.1 Application Layer
1.5.2 Presentation Layer
1.5.3 Session Layer
1.5.4 Transport Layer
1.5.5 Network Layer
1.5.6 Data Link Layer
1.5.7 Physical Layer
1.6 Parallel Processing
1.7 Machine Learning
2 Fundamental Stochastic Models
2.1 Introduction
2.2 Bernoulli and Poisson Processes
2.2.1 The Discrete Time Bernoulli Process
2.2.2 The Continuous Time Poisson Process
2.3 Bernoulli Process Statistics
2.4 Probability Problems
2.4.1 Packet Streams
Single Packet Stream
Dual Packet Streams
A Stream of Different Packet Types
Packet Generators
2.4.2 Switching Elements
Switching Element Inputs
21 Switching Element
42 Switching Element
Concatenator
2.4.3 Clusters of Computers
A Cluster in a Rack
Clusters
2.4.4 Linear Networks
Idle Paths and Blocking
2.4.5 Now What?
2.5 Multiple Access Performance
2.5.1 Introduction
2.5.2 Discrete Time Ethernet Model
2.5.3 Ethernet Design Equation
2.5.4 Aloha Multiple Access Throughput Analysis
2.5.5 Aloha Multiple Access Delay Analysis
2.6 Switching Elements and Networks
2.6.1 Introduction
2.6.2 Switching Elements
2.6.3 Networks
Tree Networks
Knockout Switch
Crossbar Switch
Multiple Bus System
2.7 Conclusion
2.8 Problems
3 Queueing Models
3.1 Introduction
3.2 Single Queue Models
3.2.1 M/M/1 Queue
3.2.2 Geom/Geom/1 Queue
3.3 Some Important Single Queue Models
3.3.1 The Finite Buffer M/M/1 Queueing System
3.3.2 The M/M/m/m Loss Queueing System
3.3.3 M/M/m Queueing System
3.3.4 A Queueing Based Memory Model
3.3.5 M/G/1 Queueing System
Kendall's Approach and Result
The M/G/1 State Transition Diagram
3.4 Common Performance Measures
3.5 Markovian Queueing Networks
3.5.1 Open Networks
3.5.2 Closed Networks
3.6 Mean Value Analysis for Closed Networks
3.6.1 MVA for Cyclic Networks
Example: M Identical Cyclic Queues
3.6.2 MVA for Random Routing Networks
Example: Three Queues with Random Routing
3.7 Negative Customer Queueing Networks
3.7.1 Negative Customer Product Form Solution
Example: Tandem Network
3.8 Recursive Solutions for State Probabilities
Example: Voice/Data Integrated Protocol
3.9 Stochastic Petri Nets
3.9.1 Petri Net Schematics
3.9.2 Petri Net Markov Chains
3.10 Solution Techniques
3.10.1 Analytical Solutions
3.10.2 Numerical Computation
3.10.3 Simulation
3.11 Conclusion
3.12 Problems
4 Networking Algorithms
4.1 Introduction
4.2 Routing
4.2.1 Introduction
4.2.2 Dijkstra's Algorithm
4.2.3 Ford Fulkerson Algorithm
4.2.4 Optimizing Bottleneck Bandwidth
4.2.5 Table Driven Routing
4.2.6 Source Routing
4.2.7 Flooding
4.2.8 Hierarchical Routing
4.2.9 Self-routing
4.2.10 Multicasting
4.2.11 Ad Hoc Network Routing
4.3 Protocol Verification
4.4 Error Codes
4.4.1 Introduction
4.4.2 Parity Codes
4.4.3 Hamming Error Correction
4.4.4 The CRC Code
Introduction
The CRC Algorithm
CRC Code Protection
4.5 Line Codes for Networking
4.5.1 Manchester Encoding
4.5.2 mBnB Encoding
4B5B Encoding
8b10b Encoding
64b/66b Encoding
4.6 Network Coding
4.6.1 Bits Are Different
4.6.2 Extensions and Challenges
4.7 Quantum Cryptography
4.7.1 Introduction
4.7.2 Quantum Physics
4.7.3 Quantum Communication
4.7.4 Quantum Key Distribution (QKD)
Implementation
Absolute Security?
4.8 Conclusion
4.9 Problems
5 Divisible Loads and Parallel Processing
5.1 Introduction
5.1.1 Ten Reasons
5.1.2 Implications
5.2 Some Single Level Tree (Star) Networks
5.2.1 Sequential Load Distribution
5.2.2 Simultaneous Distribution, Staggered Start
5.2.3 Simultaneous Distribution, Simultaneous Start
5.2.4 Nonlinear Load Processing Complexity
Nonlinear Communication Time
5.3 Equivalent Processors
5.4 Divisible Loads and Product Form Solutions
5.4.1 Model and Notation
5.4.2 The M Level Subtree Product Form Solution
5.4.3 In Summary
5.5 Infinite Size Network Performance
5.5.1 Linear Daisy Chains
Infinite Number of Processors
5.5.2 Tree Networks
5.6 Multi-Installment Scheduling
5.7 Computing/Communication Monetary Costs
5.7.1 A Computing Costs Only Example
5.7.2 Two Quantities to Optimize
5.7.3 Computation and Communication Monetary Cost
5.7.4 In Summary
5.7.5 Extensions
5.8 Signature Searching
5.8.1 Uniformly Distributed Signatures
Single Signature
Multiple Signatures
5.8.2 Arbitrary Distributions of Signature Location
5.8.3 Searching in a Networked File System
5.8.4 In Summary
5.9 Time-Varying Environments
5.9.1 Time-Varying Processor Speed
5.10 Linear Programming and Divisible Load Modeling
5.11 Conclusion
5.12 Problems
6 Amdahl's and Other Laws
6.1 Introduction
6.2 Amdahl's Law
6.3 Gustafson's Law
6.4 A General Law
6.5 Symmetric Multicore Design
6.6 Asymmetric Multicore Design
6.7 Dynamic Multicore Design
6.8 A CPU/GPU Example
6.8.1 Speedup
6.8.2 Average Power
6.8.3 Concurrent Asymmetric Performance
6.9 Delay and Energy Objective Functions
6.9.1 Preliminaries
6.9.2 Delay as Cost (Single Processor)
6.9.3 Delay as Cost (with Parallelism)
6.9.4 Energy as Cost
6.9.5 Joint Delay and Energy Optimization
6.10 Amdahl's Law and Cloud Computing
6.10.1 Local Processing
6.10.2 Cloud Processing
6.10.3 Energy Performance
6.11 Conclusion
6.12 Problems
7 Machine Learning in Networking
7.1 Introduction
7.2 An Overview of Machine Learning
7.2.1 Categories and Practical Solutions
Supervised Learning
Unsupervised Learning
7.2.2 General Procedure of Building Machine Learning Solutions
7.2.3 Data Collection
7.2.4 Ground Truth Collection
7.2.5 Feature Engineering
7.2.6 Data Splitting
7.2.7 Performance Evaluation
Classification Performance Metrics
Regression Performance Metrics
Clustering Performance Metrics
7.3 Traffic Classification
7.3.1 Classification Goals
7.3.2 Features
Payload-Based Features
Flow Statistics
7.3.3 State-of-the-Art Solutions
7.4 Traffic Routing
7.4.1 State-of-the-Art Machine Learning Solutions
Value-Based Reinforcement Learning Solutions
Policy Gradients and Actor-Critic Reinforcement Learning Solutions
7.5 Resource Management
7.5.1 The Virtual Network Embedding Problem
State-of-the-Art Solutions
7.5.2 Resource Management in Software-Defined Networks
7.6 Conclusion
7.7 Problems
A Summation Formulas
A.1 Some Summation Formulas
Bibliography
Index