Networking and Computation (Technology, Modeling and Performance) ||

This revised textbook, intended for use in undergraduate/graduate courses on computer networking, computer systems/architecture and performance evaluation, presents a host of new and revised content and ancillaries. This text presents a balanced approach between technology and mathematical modeling. It covers networking algorithms (routing, error codes, protocol verification, line codes, network coding and quantum encryption) and analysis (probability for networking with technological examples, queueing models, divisible load scheduling theory and Amdahl's Law). There is also a tutorial chapter providing insights into machine learning for networking, the cutting edge of networking technology. This self-contained text progresses systematically and gives students numerous examples at the end of each chapter. Students in electrical engineering, computer engineering and computer science departments will benefit from this book as will engineers and computer scientists working in relevant fields. Maintains a balanced approach between technology and mathematical modeling Features new and revised content covering the latest advances in the field since the original publication Includes a host of classroom material for students and instructors Preface 6 Contents 8 1 Introduction 13 1.1 Networking Overview 13 1.2 Achieving Network Connectivity 13 1.2.1 Coaxial Cable 13 1.2.2 Twisted Pair Wiring 14 1.2.3 Fiber Optics 14 1.2.4 Microwave Line of Sight 14 1.2.5 Satellites 15 Geostationary Satellites 15 Low Earth Orbit Satellites 15 Other Orbits: MEO and Molniya 16 1.2.6 Cellular Systems 16 1.2.7 Ad Hoc Networks 17 1.2.8 Wireless Sensor Networks 17 1.3 Multiplexing 18 1.3.1 Frequency Division Multiplexing (FDM) 18 1.3.2 Time Division Multiplexing (TDM) 18 1.3.3 Frequency Hopping 18 1.3.4 Direct Sequence Spread Spectrum 19 1.4 Circuit Switching Versus Packet Switching 19 1.5 Layered Protocols 20 1.5.1 Application Layer 20 1.5.2 Presentation Layer 20 1.5.3 Session Layer 20 1.5.4 Transport Layer 20 1.5.5 Network Layer 20 1.5.6 Data Link Layer 20 1.5.7 Physical Layer 21 1.6 Parallel Processing 21 1.7 Machine Learning 21 2 Fundamental Stochastic Models 22 2.1 Introduction 22 2.2 Bernoulli and Poisson Processes 23 2.2.1 The Discrete Time Bernoulli Process 23 2.2.2 The Continuous Time Poisson Process 24 2.3 Bernoulli Process Statistics 26 2.4 Probability Problems 29 2.4.1 Packet Streams 29 Single Packet Stream 29 Dual Packet Streams 30 A Stream of Different Packet Types 31 Packet Generators 31 2.4.2 Switching Elements 32 Switching Element Inputs 32 21 Switching Element 33 42 Switching Element 33 Concatenator 34 2.4.3 Clusters of Computers 34 A Cluster in a Rack 35 Clusters 35 2.4.4 Linear Networks 35 Idle Paths and Blocking 35 2.4.5 Now What? 36 2.5 Multiple Access Performance 36 2.5.1 Introduction 36 2.5.2 Discrete Time Ethernet Model 36 2.5.3 Ethernet Design Equation 38 2.5.4 Aloha Multiple Access Throughput Analysis 39 2.5.5 Aloha Multiple Access Delay Analysis 40 2.6 Switching Elements and Networks 43 2.6.1 Introduction 43 2.6.2 Switching Elements 43 2.6.3 Networks 45 Tree Networks 46 Knockout Switch 47 Crossbar Switch 48 Multiple Bus System 50 2.7 Conclusion 51 2.8 Problems 51 3 Queueing Models 55 3.1 Introduction 55 3.2 Single Queue Models 55 3.2.1 M/M/1 Queue 55 3.2.2 Geom/Geom/1 Queue 59 3.3 Some Important Single Queue Models 62 3.3.1 The Finite Buffer M/M/1 Queueing System 62 3.3.2 The M/M/m/m Loss Queueing System 63 3.3.3 M/M/m Queueing System 64 3.3.4 A Queueing Based Memory Model 65 3.3.5 M/G/1 Queueing System 66 Kendall's Approach and Result 66 The M/G/1 State Transition Diagram 67 3.4 Common Performance Measures 68 3.5 Markovian Queueing Networks 69 3.5.1 Open Networks 69 3.5.2 Closed Networks 71 3.6 Mean Value Analysis for Closed Networks 72 3.6.1 MVA for Cyclic Networks 73 Example: M Identical Cyclic Queues 74 3.6.2 MVA for Random Routing Networks 74 Example: Three Queues with Random Routing 74 3.7 Negative Customer Queueing Networks 75 3.7.1 Negative Customer Product Form Solution 76 Example: Tandem Network 77 3.8 Recursive Solutions for State Probabilities 77 Example: Voice/Data Integrated Protocol 78 3.9 Stochastic Petri Nets 79 3.9.1 Petri Net Schematics 79 3.9.2 Petri Net Markov Chains 80 3.10 Solution Techniques 82 3.10.1 Analytical Solutions 82 3.10.2 Numerical Computation 82 3.10.3 Simulation 82 3.11 Conclusion 83 3.12 Problems 83 4 Networking Algorithms 87 4.1 Introduction 87 4.2 Routing 87 4.2.1 Introduction 87 4.2.2 Dijkstra's Algorithm 88 4.2.3 Ford Fulkerson Algorithm 89 4.2.4 Optimizing Bottleneck Bandwidth 90 4.2.5 Table Driven Routing 91 4.2.6 Source Routing 92 4.2.7 Flooding 92 4.2.8 Hierarchical Routing 92 4.2.9 Self-routing 93 4.2.10 Multicasting 94 4.2.11 Ad Hoc Network Routing 94 4.3 Protocol Verification 95 4.4 Error Codes 96 4.4.1 Introduction 96 4.4.2 Parity Codes 98 4.4.3 Hamming Error Correction 98 4.4.4 The CRC Code 99 Introduction 99 The CRC Algorithm 99 CRC Code Protection 100 4.5 Line Codes for Networking 101 4.5.1 Manchester Encoding 102 4.5.2 mBnB Encoding 102 4B5B Encoding 102 8b10b Encoding 102 64b/66b Encoding 103 4.6 Network Coding 104 4.6.1 Bits Are Different 104 4.6.2 Extensions and Challenges 105 4.7 Quantum Cryptography 105 4.7.1 Introduction 105 4.7.2 Quantum Physics 105 4.7.3 Quantum Communication 106 4.7.4 Quantum Key Distribution (QKD) 106 Implementation 107 Absolute Security? 107 4.8 Conclusion 107 4.9 Problems 108 5 Divisible Loads and Parallel Processing 110 5.1 Introduction 110 5.1.1 Ten Reasons 111 5.1.2 Implications 114 5.2 Some Single Level Tree (Star) Networks 114 5.2.1 Sequential Load Distribution 115 5.2.2 Simultaneous Distribution, Staggered Start 118 5.2.3 Simultaneous Distribution, Simultaneous Start 121 5.2.4 Nonlinear Load Processing Complexity 124 Nonlinear Communication Time 127 5.3 Equivalent Processors 127 5.4 Divisible Loads and Product Form Solutions 128 5.4.1 Model and Notation 129 5.4.2 The M Level Subtree Product Form Solution 129 5.4.3 In Summary 131 5.5 Infinite Size Network Performance 131 5.5.1 Linear Daisy Chains 131 Infinite Number of Processors 132 5.5.2 Tree Networks 133 5.6 Multi-Installment Scheduling 134 5.7 Computing/Communication Monetary Costs 135 5.7.1 A Computing Costs Only Example 136 5.7.2 Two Quantities to Optimize 136 5.7.3 Computation and Communication Monetary Cost 137 5.7.4 In Summary 137 5.7.5 Extensions 137 5.8 Signature Searching 137 5.8.1 Uniformly Distributed Signatures 138 Single Signature 138 Multiple Signatures 138 5.8.2 Arbitrary Distributions of Signature Location 138 5.8.3 Searching in a Networked File System 138 5.8.4 In Summary 139 5.9 Time-Varying Environments 139 5.9.1 Time-Varying Processor Speed 140 5.10 Linear Programming and Divisible Load Modeling 143 5.11 Conclusion 144 5.12 Problems 144 6 Amdahl's and Other Laws 147 6.1 Introduction 147 6.2 Amdahl's Law 147 6.3 Gustafson's Law 149 6.4 A General Law 149 6.5 Symmetric Multicore Design 149 6.6 Asymmetric Multicore Design 150 6.7 Dynamic Multicore Design 151 6.8 A CPU/GPU Example 151 6.8.1 Speedup 151 6.8.2 Average Power 151 6.8.3 Concurrent Asymmetric Performance 152 6.9 Delay and Energy Objective Functions 152 6.9.1 Preliminaries 153 6.9.2 Delay as Cost (Single Processor) 153 6.9.3 Delay as Cost (with Parallelism) 153 6.9.4 Energy as Cost 153 6.9.5 Joint Delay and Energy Optimization 154 6.10 Amdahl's Law and Cloud Computing 154 6.10.1 Local Processing 154 6.10.2 Cloud Processing 155 6.10.3 Energy Performance 156 6.11 Conclusion 157 6.12 Problems 157 7 Machine Learning in Networking 158 7.1 Introduction 158 7.2 An Overview of Machine Learning 159 7.2.1 Categories and Practical Solutions 160 Supervised Learning 160 Unsupervised Learning 160 7.2.2 General Procedure of Building Machine Learning Solutions 162 7.2.3 Data Collection 162 7.2.4 Ground Truth Collection 164 7.2.5 Feature Engineering 164 7.2.6 Data Splitting 167 7.2.7 Performance Evaluation 169 Classification Performance Metrics 169 Regression Performance Metrics 170 Clustering Performance Metrics 171 7.3 Traffic Classification 173 7.3.1 Classification Goals 173 7.3.2 Features 174 Payload-Based Features 174 Flow Statistics 177 7.3.3 State-of-the-Art Solutions 178 7.4 Traffic Routing 182 7.4.1 State-of-the-Art Machine Learning Solutions 183 Value-Based Reinforcement Learning Solutions 184 Policy Gradients and Actor-Critic Reinforcement Learning Solutions 187 7.5 Resource Management 189 7.5.1 The Virtual Network Embedding Problem 190 State-of-the-Art Solutions 191 7.5.2 Resource Management in Software-Defined Networks 193 7.6 Conclusion 195 7.7 Problems 195 A Summation Formulas 198 A.1 Some Summation Formulas 198 Bibliography 199 Index 208 This useful volume adopts a balanced approach between technology and mathematical modeling in computer networks, covering such topics as switching elements and fabrics, Ethernet, and ALOHA design. The discussion includes a variety of queueing models, routing, protocol verification and error codes and divisible load theory, a new modeling technique with applications to grids and parallel and distributed processing. Examples at the end of each chapter provide ample material for practice. This book can serve as an text for an undergraduate or graduate course on computer networks or performance evaluation in electrical and computer engineering or computer science.