第1页 / 共493页
第2页 / 共493页
第3页 / 共493页
第4页 / 共493页
第5页 / 共493页
第6页 / 共493页
第7页 / 共493页
第8页 / 共493页
Mathematical Foundations of Computer Networking 无水印pdf.pdf
Cover
Copyright
Contents
Preface
1 Probability
1.1 Introduction
1.1.1 Outcomes
1.1.2 Events
1.1.3 Disjunctions and Conjunctions of Events
1.1.4 Axioms of Probability
1.1.5 Subjective and Objective Probability
1.2 Joint and Conditional Probability
1.2.1 Joint Probability
1.2.2 Conditional Probability
1.2.3 Bayes's Rule
1.3 Random Variables
1.3.1 Distribution
1.3.2 Cumulative Density Function
1.3.3 Generating Values from an Arbitrary Distribution
1.3.4 Expectation of a Random Variable
1.3.5 Variance of a Random Variable
1.4 Moments and Moment Generating Functions
1.4.1 Moments
1.4.2 Moment Generating Functions
1.4.3 Properties of Moment Generating Functions
1.5 Standard Discrete Distributions
1.5.1 Bernoulli Distribution
1.5.2 Binomial Distribution
1.5.3 Geometric Distribution
1.5.4 Poisson Distribution
1.6 Standard Continuous Distributions
1.6.1 Uniform Distribution
1.6.2 Gaussian, or Normal, Distribution
1.6.3 Exponential Distribution
1.6.4 Power-Law Distribution
1.7 Useful Theorems
1.7.1 Markov's Inequality
1.7.2 Chebyshev's Inequality
1.7.3 Chernoff Bound
1.7.4 Strong Law of Large Numbers
1.7.5 Central Limit Theorem
1.8 Jointly Distributed Random Variables
1.8.1 Bayesian Networks
1.9 Further Reading
1.10 Exercises
2 Statistics
2.1 Sampling a Population
2.1.1 Types of Sampling
2.1.2 Scales
2.1.3 Outliers
2.2 Describing a Sample Parsimoniously
2.2.1 Tables
2.2.2 Bar Graphs, Histograms, and Cumulative Histograms
2.2.3 The Sample Mean
2.2.4 The Sample Median
2.2.5 Measures of Variability
2.3 Inferring Population Parameters from Sample Parameters
2.4 Testing Hypotheses about Outcomes of Experiments
2.4.1 Hypothesis Testing
2.4.2 Errors in Hypothesis Testing
2.4.3 Formulating a Hypothesis
2.4.4 Comparing an Outcome with a Fixed Quantity
2.4.5 Comparing Outcomes from Two Experiments
2.4.6 Testing Hypotheses about Quantities Measured on Ordinal Scales
2.4.7 Fitting a Distribution
2.4.8 Power
2.5 Independence and Dependence: Regression and Correlation
2.5.1 Independence
2.5.2 Regression
2.5.3 Correlation
2.6 Comparing Multiple Outcomes Simultaneously: Analysis of Variance
2.6.1 One-Way Layout
2.6.2 Multiway Layouts
2.7 Design of Experiments
2.8 Dealing with Large Data Sets
2.9 Common Mistakes in Statistical Analysis
2.9.1 Defining Population
2.9.2 Lack of Confidence Intervals in Comparing Results
2.9.3 Not Stating the Null Hypothesis
2.9.4 Too Small a Sample
2.9.5 Too Large a Sample
2.9.6 Not Controlling All Variables When Collecting Observations
2.9.7 Converting Ordinal to Interval Scales
2.9.8 Ignoring Outliers
2.10 Further Reading
2.11 Exercises
3 Linear Algebra
3.1 Vectors and Matrices
3.2 Vector and Matrix Algebra
3.2.1 Addition
3.2.2 Transpose
3.2.3 Multiplication
3.2.4 Square Matrices
3.2.5 Exponentiation
3.2.6 Matrix Exponential
3.3 Linear Combinations, Independence, Basis, and Dimension
3.3.1 Linear Combinations
3.3.2 Linear Independence
3.3.3 Vector Spaces, Basis, and Dimension
3.4 Using Matrix Algebra to Solve Linear Equations
3.4.1 Representation
3.4.2 Elementary Row Operations and Gaussian Elimination
3.4.3 Rank
3.4.4 Determinants
3.4.5 Cramer's Theorem
3.4.6 The Inverse of a Matrix
3.5 Linear Transformations, Eigenvalues, and Eigenvectors
3.5.1 A Matrix as a Linear Transformation
3.5.2 The Eigenvalue of a Matrix
3.5.3 Computing the Eigenvalues of a Matrix
3.5.4 The Importance of Eigenvalues
3.5.5 The Role of the Principal Eigenvalue
3.5.6 Finding Eigenvalues and Eigenvectors
3.5.7 Similarity and Diagonalization
3.6 Stochastic Matrices
3.6.1 Computing State Transitions by Using a Stochastic Matrix
3.6.2 Eigenvalues of a Stochastic Matrix
3.7 Exercises
4 Optimization
4.1 System Modeling and Optimization
4.2 Introduction to Optimization
4.3 Optimizing Linear Systems
4.3.1 Network Flow
4.4 Integer Linear Programming
4.4.1 Total Unimodularity
4.4.2 Weighted Bipartite Matching
4.5 Dynamic Programming
4.6 Nonlinear Constrained Optimization
4.6.1 Lagrangian Techniques
4.6.2 Karush-Kuhn-Tucker Conditions for Nonlinear Optimization
4.7 Heuristic Nonlinear Optimization
4.7.1 Hill Climbing
4.7.2 Genetic Algorithms
4.8 Exercises
5 Signals, Systems, and Transforms
5.1 Background
5.1.1 Sinusoids
5.1.2 Complex Numbers
5.1.3 Euler's Formula
5.1.4 Discrete-Time Convolution and the Impulse Function
5.1.5 Continuous-Time Convolution and the Dirac Delta Function
5.2 Signals
5.2.1 The Complex Exponential Signal
5.3 Systems
5.4 Analysis of a Linear Time-Invariant System
5.4.1 The Effect of an LTI System on a Complex Exponential Input
5.4.2 The Output of an LTI System with a Zero Input
5.4.3 The Output of an LTI System for an Arbitrary Input
5.4.4 Stability of an LTI System
5.5 Transforms
5.6 The Fourier Series
5.7 The Fourier Transform and Its Properties
5.8 The Laplace Transform
5.8.1 Poles, Zeroes, and the Region of Convergence
5.8.2 Properties of the Laplace Transform
5.9 The Discrete Fourier Transform and Fast Fourier Transform
5.9.1 The Impulse Train
5.9.2 The Discrete-Time Fourier Transform
5.9.3 Aliasing
5.9.4 The Discrete-Time-and-Frequency Fourier Transform
5.9.5 The Fast Fourier Transform
5.10 The Z Transform
5.10.1 Relationship between Z and Laplace Transforms
5.10.2 Properties of the Z Transform
5.11 Further Reading
5.12 Exercises
6 Stochastic Processes and Queueing Theory
6.1 Overview
6.1.1 A General Queueing System
6.1.2 Little's Theorem
6.2 Stochastic Processes
6.2.1 Discrete and Continuous Stochastic Processes
6.2.2 Markov Processes
6.2.3 Homogeneity, State-Transition Diagrams, and the Chapman-Kolmogorov Equations
6.2.4 Irreducibility
6.2.5 Recurrence
6.2.6 Periodicity
6.2.7 Ergodicity
6.2.8 A Fundamental Theorem
6.2.9 Stationary (Equilibrium) Probability of a Markov Chain
6.2.10 A Second Fundamental Theorem
6.2.11 Mean Residence Time in a State
6.3 Continuous-Time Markov Chains
6.3.1 Markov Property for Continuous-Time Stochastic Processes
6.3.2 Residence Time in a Continuous-Time Markov Chain
6.3.3 Stationary Probability Distribution for a Continuous-Time Markov Chain
6.4 Birth-Death Processes
6.4.1 Time-Evolution of a Birth-Death Process
6.4.2 Stationary Probability Distribution of a Birth-Death Process
6.4.3 Finding the Transition-Rate Matrix
6.4.4 A Pure-Birth (Poisson) Process
6.4.5 Stationary Probability Distribution for a Birth-Death Process
6.5 The M/M/1 Queue
6.6 Two Variations on the M/M/1 Queue
6.6.1 The M/M/¥ Queue: A Responsive Server
6.6.2 M/M/1/K: Bounded Buffers
6.7 Other Queueing Systems
6.7.1 M/D/1: Deterministic Service Times
6.7.2 G/G/1
6.7.3 Networks of Queues
6.8 Further Reading
6.9 Exercises
7 Game Theory
7.1 Concepts and Terminology
7.1.1 Preferences and Preference Ordering
7.1.2 Terminology
7.1.3 Strategies
7.1.4 Game Representation
7.1.5 Response and Best Response
7.1.6 Dominant and Dominated Strategy
7.1.7 Bayesian Games
7.1.8 Repeated Games
7.2 Solving a Game
7.2.1 Solution Concept and Equilibrium
7.2.2 Dominant-Strategy Equilibria
7.2.3 Iterated Removal of Dominated Strategies
7.2.4 Maximin Equilibrium
7.2.5 Nash Equilibria
7.2.6 Correlated Equilibria
7.2.7 Other Solution Concepts
7.3 Mechanism Design
7.3.1 Practical Mechanisms
7.3.2 Three Negative Results
7.3.3 Examples of Mechanism Design
7.3.4 Formalization
7.3.5 Desirable Properties of a Mechanism
7.3.6 Revelation Principle
7.3.7 Vickrey-Clarke-Groves Mechanism
7.3.8 Problems with VCG Mechanisms
7.4 Limitations of Game Theory
7.5 Further Reading
7.6 Exercises
8 Elements of Control Theory
8.1 Overview of a Controlled System
8.2 Modeling a System
8.2.1 Modeling Approach
8.2.2 Mathematical Representation
8.3 A First-Order System
8.4 A Second-Order System
8.4.1 Case 1 (Undamped System): ζ = 0
8.4.2 Case 2 (Underdamped System): 0 < ζ < 1
8.4.3 Case 3 (Critically Damped System): ζ = 1
8.4.4 Case 4 (Overdamped System): ζ > 1
8.5 Basics of Feedback Control
8.5.1 System Goal
8.5.2 Constraints
8.6 PID Control
8.6.1 Proportional-Mode Control
8.6.2 Integral-Mode Control
8.6.3 Derivative-Mode Control
8.6.4 Combining Modes
8.7 Advanced Control Concepts
8.7.1 Cascade Control
8.7.2 Control Delay
8.8 Stability
8.8.1 BIBO Stability Analysis of a Linear Time-Invariant System
8.8.2 Zero-Input Stability Analysis of a SISO Linear Time-Invariant System
8.8.3 Placing System Roots
8.8.4 Lyapunov Stability
8.9 State Space–Based Modeling and Control
8.9.1 State Space–Based Analysis
8.9.2 Observability and Controllability
8.9.3 Controller Design
8.10 Digital Control
8.11 Partial Fraction Expansion
8.11.1 Distinct Roots
8.11.2 Complex Conjugate Roots
8.11.3 Repeated Roots
8.12 Further Reading
8.13 Exercises
9 Information Theory
9.1 Introduction
9.2 A Mathematical Model for Communication
9.3 From Messages to Symbols
9.4 Source Coding
9.5 The Capacity of a Communication Channel
9.5.1 Modeling a Message Source
9.5.2 The Capacity of a Noiseless Channel
9.5.3 A Noisy Channel
9.6 The Gaussian Channel
9.6.1 Modeling a Continuous Message Source
9.6.2 A Gaussian Channel
9.6.3 The Capacity of a Gaussian Channel
9.7 Further Reading
9.8 Exercises
Solutions to Exercises
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Z
ptg7913109
Mathematical Foundations
of Computer Networking
The Addison-Wesley
Professional Computing Series
Visit informit.com/series/professionalcomputing
for a complete list of available publications.
The Addison-Wesley Professional Computing Series was created in 1990 to
provide serious programmers and networking professionals with well-written
and practical reference books. There are few places to turn for accurate and
authoritative books on current and cutting-edge technology. We hope that our
books will help you understand the state of the art in programming languages,
operating systems, and networks.
Consulting Editor Brian W. Kernighan
Make sure to connect with us!
informit.com/socialconnect
ptg7913109
Mathematical
Foundations of
Computer Networking
Srinivasan Keshav
Upper Saddle River, NJ • Boston • Indianapolis • San Francisco
New York • Toronto • Montreal • London • Munich • Paris • Madrid
Capetown • Sydney • Tokyo • Singapore • Mexico City
ptg7913109
Editor-in-Chief
Mark L. Taub
Senior Acquisitions Editor
Trina MacDonald
Managing Editor
John Fuller
Full-Service Production
Manager
Julie B. Nahil
Copy Editor
Evelyn Pyle
Indexer
Ted Laux
Proofreader
Linda Begley
Technical Reviewers
Alan Kaplan
Abraham Matta
Johnny Wong
Publishing Coordinator
Olivia Basegio
Compositor
Rob Mauhar
Many of the designations used by manufacturers and sellers to distin-
guish their products are claimed as trademarks. Where those designa-
tions appear in this book, and the publisher was aware of a trademark
claim, the designations have been printed with initial capital letters or in
all capitals.
The author and publisher have taken care in the preparation of this book,
but make no expressed or implied warranty of any kind and assume no
responsibility for errors or omissions. No liability is assumed for inciden-
tal or consequential damages in connection with or arising out of the use
of the information or programs contained herein.
The publisher offers excellent discounts on this book when ordered in
quantity for bulk purchases or special sales, which may include electronic
versions and/or custom covers and content particular to your business,
training goals, marketing focus, and branding interests. For more infor-
mation, please contact:
U.S. Corporate and Government Sales
(800) 382-3419
corpsales@pearsontechgroup.com
For sales outside the United States, please contact:
International Sales
international@pearson.com
Visit us on the Web: informit.com/aw
Library of Congress Cataloging-in-Publication Data
Keshav, Srinivasan.
Mathematical foundations of computer networking / Srinivasan Keshav.
p.
cm.
Includes index.
ISBN 978-0-321-79210-5 (pbk. : alk. paper)—ISBN 0-321-79210-6 (pbk. :
alk. paper) 1. Computer networks—Mathematics—Textbooks. I. Title.
TK5105.5.K484 2012
004.601'519—dc23
2011052203
Copyright © 2012 Pearson Education, Inc.
All rights reserved. Printed in the United States of America. This publi-
cation is protected by copyright, and permission must be obtained from
the publisher prior to any prohibited reproduction, storage in a retrieval
system, or transmission in any form or by any means, electronic, mechan-
ical, photocopying, recording, or likewise. To obtain permission to use
material from this work, please submit a written request to Pearson Edu-
cation, Inc., Permissions Department, One Lake Street, Upper Saddle
River, New Jersey 07458, or you may fax your request to (201) 236-3290.
ISBN-13: 978-0-321-79210-5
ISBN-10:
0-321-79210-6
Text printed in the United States on recycled paper at RR Donnelley in
Crawfordsville, Indiana.
First printing, April 2012
ptg7913109
Contents
Preface
Chapter 1
Probability
1.1
Introduction
1.1.1
1.1.2
1.1.3
1.1.4
1.1.5
Outcomes
Events
Disjunctions and Conjunctions of Events
Axioms of Probability
Subjective and Objective Probability
1.2
Joint and Conditional Probability
1.2.1
1.2.2
1.2.3
Joint Probability
Conditional Probability
Bayes’s Rule
1.3
Random Variables
1.3.1
1.3.2
1.3.3
1.3.4
1.3.5
Distribution
Cumulative Density Function
Generating Values from an Arbitrary Distribution
Expectation of a Random Variable
Variance of a Random Variable
xv
1
1
2
3
3
4
5
7
7
7
11
14
15
17
17
18
20
v
ptg7913109
vi
Contents
1.4 Moments and Moment Generating Functions
1.4.1 Moments
1.4.2 Moment Generating Functions
1.4.3
Properties of Moment Generating Functions
1.5
Standard Discrete Distributions
1.5.1
1.5.2
1.5.3
1.5.4
Bernoulli Distribution
Binomial Distribution
Geometric Distribution
Poisson Distribution
1.6
Standard Continuous Distributions
1.6.1 Uniform Distribution
1.6.2
1.6.3
1.6.4
Gaussian, or Normal, Distribution
Exponential Distribution
Power-Law Distribution
1.7
Useful Theorems
1.7.1 Markov’s Inequality
1.7.2
1.7.3
1.7.4
1.7.5
Chebyshev’s Inequality
Chernoff Bound
Strong Law of Large Numbers
Central Limit Theorem
1.8
Jointly Distributed Random Variables
1.8.1
Bayesian Networks
Further Reading
1.9
1.10 Exercises
21
21
22
24
25
25
25
27
27
29
29
29
32
34
35
36
36
37
39
40
42
44
47
47
Chapter 2
Statistics
2.1
2.2
Sampling a Population
Types of Sampling
Scales
Outliers
2.1.1
2.1.2
2.1.3
53
53
55
56
57
57
Tables
58
Bar Graphs, Histograms, and Cumulative Histograms 58
60
The Sample Mean
63
The Sample Median
64
2.2.1
2.2.2
2.2.3
2.2.4
2.2.5 Measures of Variability
Describing a Sample Parsimoniously
ptg7913109
Contents
2.3
2.4
Inferring Population Parameters from Sample
Parameters
Testing Hypotheses about Outcomes of Experiments
2.4.1 Hypothesis Testing
2.4.2
2.4.3
2.4.4
2.4.5
2.4.6
Errors in Hypothesis Testing
Formulating a Hypothesis
Comparing an Outcome with a Fixed Quantity
Comparing Outcomes from Two Experiments
Testing Hypotheses about Quantities Measured on
Ordinal Scales
Fitting a Distribution
Power
2.4.7
2.4.8
2.5
Independence and Dependence: Regression
and Correlation
2.5.1
2.5.2
2.5.3
Independence
Regression
Correlation
2.6
2.7
2.8
2.9
Comparing Multiple Outcomes Simultaneously:
Analysis of Variance
One-Way Layout
2.6.1
2.6.2 Multiway Layouts
Design of Experiments
Dealing with Large Data Sets
Common Mistakes in Statistical Analysis
Defining Population
Lack of Confidence Intervals in Comparing Results
2.9.1
2.9.2
2.9.3 Not Stating the Null Hypothesis
2.9.4
2.9.5
2.9.6 Not Controlling All Variables When Collecting
Too Small a Sample
Too Large a Sample
Observations
Converting Ordinal to Interval Scales
Ignoring Outliers
2.9.7
2.9.8
2.10 Further Reading
2.11 Exercises
vii
66
70
71
72
73
74
76
79
82
85
86
86
88
90
95
95
98
99
100
103
103
103
103
104
104
104
104
105
105
105
ptg7913109
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
