Fundamentals of

Communication Networks

MSc. Ma Việt Đức

Email: [Link]@[Link]

Introduction Chapter

Lecturer
 MSc. Ma Viet Duc
Department of Communication Engineering,
Introduction SEEE, HUST
Email: [Link]@[Link]
Motivation
Research Topics:
◊ Cloud and Edge Computing
Communication
Networks ◊ 5G Networks and Beyond
◊ Network Security
◊ Services Architecture

1
 Fields of Research

Smart Application and Devices

Introduction

Cloud & Edge

Wireless Communication
Motivation Computing

Communication
Networks 5G Networks and Beyond

Motivations
 Network performance evaluation and
modelling
Introduction
 Network simulation
Motivation
 Design of network elements, like
Communication router’s buffer, routing protocols,
Networks
resource allocation, MAC scheduling,
etc

2
 Course Contents
 Chapter 0: Overview of
Communication Networks and network
Introduction
modelling
 Chapter 1: Probability Review
Motivation
 Chapter 2: Queuing theory
Communication
Networks
 Chapter 3: Routing theory
 Chapter 4: Flow and congestion
control
 Chapter 5: Simulation (optional)
5

Pre-requirements
 Attendees need to have:
Knowledge of statistics and probability
Introduction Basis of digital communications
Fundamentals of data communications
Motivation
 References:
Communication
Networks
Will be provided

3
 Evaluation
 Projects or mid-term exam: 30%
Introduction
 Final exam: 70%

Motivation

Communication
Networks

Methodology
 The fundamentals
Reliable/secure communications over
unreliable/insecure channels
Introduction Finding paths through the network
Resource sharing
Motivation Providing common services to applications
Communication
Networks  Case studies (in project based) on how to use the
network
◊Content distribution, DNS, p2p, social
networks, search engines
◊Socket programming

4
 The (communication)
Introduction
networking field is broad and
Motivation confusing…
Communication
Networks

What is an comm. network?

 Network: a collection of entities that
are interconnected
A link (edge) between two entities
Introduction
(nodes) denotes an interaction between
Motivation
two entities
We view this interaction as information
Communication
Networks exchange, hence, data networks
The term encompasses more general
networks

10

10

5
 Why do we care about
networks?
 Because they are everywhere
more and more systems can be modeled
Introduction
as networks
Motivation  Because they are growing
Communication
large scale problems
Networks
 Because we have the computational
power to study them
task: to develop the tools

11

11

Social Networks
 Links denote a social interaction
Networks of acquaintances
Introduction

Motivation

Communication
Networks

12

12

6
 Other Social networks
 actor networks
 co-authorship
networks
Introduction
 director networks
 phone-call networks
Motivation
 e-mail networks
Communication  IM networks
Networks
Microsoft buddy
network
 Bluetooth networks
 sexual networks
13

13

Knowledge (Information)
Networks
 Nodes store information, links
associate information
Introduction
Citation network (directed acyclic)
Motivation
The Web (directed)

Communication
Networks

14

14

7
 Other data networks
 Peer-to-Peer networks
Introduction
 Word networks
 Networks of Trust
Motivation
epinions
Communication
Networks

15

15

Technological networks
 Networks built for distribution of
commodity
The Internet
Introduction ◊router level
◊AS level
Motivation

Communication
Networks

ISP network

16

16

8
 Other technological
networks
 Power Grids
Introduction
 Airline networks
 Telephone networks
 Transportation Networks
Motivation

Communication
Networks
roads, railways, pedestrian traffic
 Software networks

17

17

Biological networks
 Biological systems represented as
networks
Protein-Protein Interaction Networks
Introduction

Motivation

Communication
Networks

18

18

9
 Other Biological networks
 Gene regulation networks

Introduction

 The Food Web

Motivation

Communication
Networks

Neural Networks
19

19

Now what?
 The world is full with networks. What
do we do with them?
Introduction
understand their topology and measure
their properties
Motivation
study their evolution and dynamics
Communication
Networks create realistic models
create algorithms that make use of the
network structure

20

20

10
 Mathematical Tools
 Graph theory
Introduction
 Probability theory
 Linear Algebra
 Control theory
Motivation

Communication
Networks  Queuing theory
 Optimization theory

21

21

Graph Theory
 Graph G=(V,E)
V = set of vertices 2

E = set of edges
Introduction

Motivation 1
3
Communication
Networks

5 4
undirected graph
E={(1,2),(1,3),(2,3),(3,4),(4,5)}

22

22

11
 Graph Theory
 Graph G=(V,E)
V = set of vertices 2

E = set of edges
Introduction

Motivation 1
3
Communication
Networks

5
directed graph 4
E={‹1,2›, ‹2,1› ‹1,3›, ‹3,2›, ‹3,4›, ‹4,5›}

23

23

Undirected graph
 degree d(i) of node i
2
 number of edges
incident on node i
Introduction

Motivation 1
3
Communication
Networks
 degree sequence (distribution)
 [d(i),d(2),d(3),d(4),d(5)]
 [2,2,2,1,1] 5 4

24

24

12
 Directed Graph 2

 in-degree din(i) of node i

 number of edges pointing to
node i
1
Introduction 3
 out-degree dout(i) of node i
 number of edges leaving node i
Motivation

Communication 5 4
Networks

 in-degree sequence (distribution)

 [1,2,1,1,1]
 out-degree sequence (distribution)
 [2,1,2,1,0]
25

25

Paths
 Path from node i to node j: a sequence of edges
(directed or undirected from node i to node j)
 path length: number of edges on the path
 nodes i and j are connected
 cycle: a path that starts and ends at the same node
Introduction 2 2

Motivation

Communication
Networks 1 1
3 3

5 4 5 4
26

26

13
 Shortest Paths
 Shortest Path from node i to node j
also known as BFS path, or geodesic
path
2 2
Introduction

Motivation

Communication 1 1
Networks
3 3

5 5 4
4 27

27

Diameter
 The longest shortest path in the
graph
2 2
Introduction

Motivation

Communication 1 1
Networks
3 3

5 4 5 4
28

28

14
 Undirected graph
 Connected graph: a
graph where there
2
every pair of nodes
Introduction
is connected
 Disconnected graph:
Motivation a graph that is not 1

Communication
connected 3

Networks
 Connected
Components:
subsets of vertices 5 4
that are connected
29

29

Fully Connected Graph

 Clique Kn
 A graph that has all possible n(n-1)/2
Introduction
edges 2

Motivation

Communication 1
Networks
3

5 4

30

30

15
 Directed Graph
 Strongly connected graph:
2
there exists a path from
every i to every j
Introduction

Motivation 1
3
Communication
Networks  Weakly connected graph: If
edges are made to be
undirected the graph is
5 4
connected

31

31

Subgraphs 2

 Subgraph: Given V’  V,
and E’  E, the graph
G’=(V’,E’) is a subgraph 1
3
Introduction
of G.
 Induced subgraph:
Motivation Given V’  V, let E’ 
5
Communication
E is the set of all edges 4
Networks
between the nodes in
V’. The graph G’=(V’,E’),
is an induced subgraph
of G
32

32

16
 Trees
 Connected Undirected graphs
without cycles
Introduction 2

Motivation

Communication
Networks
1
3

5 4
33

33

Bipartite graphs
 Graphs where the set V can be
partitioned into two sets L and R, such
Introduction that all edges are between nodes in L
and R, and there is no edge within L or R
Motivation

Communication
Networks

34

34

17
 Linear Algebra
 Adjacency Matrix
symmetric matrix for undirected graphs
Introduction
2

Motivation
0 1 1 0 0
1 0 1 0 0 
Communication  1
Networks
A  1 1 0 1 0 3
 
0 0 1 0 1
0 0 0 1 0 
5 4
35

35

Linear Algebra
 Adjacency Matrix
unsymmetric matrix for undirected
graphs 2
Introduction

Motivation
0 1 1 0 0
1 0 0 0 0  1
Communication
Networks  3
A  0 1 0 1 0
 
0 0 0 0 1
0 0 0 0 0  5 4

36

36

18
 Random Walks
 Start from a node, and follow links
uniformly at random.
Introduction  Stationary distribution: The fraction
of times that you visit node i, as the
Motivation
number of steps of the random walk
Communication
Networks
approaches infinity
if the graph is strongly connected, the
stationary distribution converges to a
unique vector.

37

37

Probability Theory
 Probability Space: pair ‹Ω,P›
Ω: sample space
Introduction
P: probability measure over subsets of
Motivation Ω
Communication
 Random variable X: Ω→R
Networks
Probability mass function P[X=x]
 Expectation
EX    xP[X  x]
x
38

38

19
 What is modeling?
 A Model is a simplification of a real
system
 Modeling is the process of representing a
Introduction
system with a specific tool to study its
behavior
Motivation
 A model can be:
Communication
Networks Analytic: when a mathematical approach is
feasible (e.g. Queuing Model)
Simulation: model used for complex systems
Experimental: when the real system already
exists
39

39

[Link]

Model (Wikipedia)
 A Model is a pattern, plan, representation
(especially in miniature), or description designed
to show the main object or workings of an object,
system, or concept.
Introduction
 Model may also refer to:
Motivation
Abstractions, concepts, and theories
representations of objects
Communication
Networks
human and animal behavior
occupations
history and culture
lighting
In geography …
40

40

20
 Examples

In general, modeling is used for systems

with some sort of uncertainty
Introduction

• Waiting time in a restaurant/airport

Motivation • Time to go from home to the University
• Response time and Throughput of a web
Communication server
Networks
• The productivity of manufacturing systems
• Design of multi-processor machine
• Performance of MAC protocols (e.g.
CSMA/CA)

41

41

Examples: Movement
 Consider a system when a given object move
 This system can be modeled by the equation
S= V * t V

Introduction Where S is the distance run through

 V is the speed of the object
Motivation  t is the time that has been observed.
 This is simplification of the real world
Communication
Networks  Another model can take into account the
direction of movement, or the three
dimension coordinate …
 It is therefore to study the behaviour of the
system based on a specific model

42

42

21
 Example: Radio Propagation Models
 A radio propagation model is an
empirical mathematical formulation
for the characterization of radio wave
propagation as a function of
frequency, distance and other
conditions.
 Different types of models
Introduction  Models for outdoor
environments: Ground wave,
Sky wave, Environmental
Motivation Attenuation, Point-to-Point
propagation models, Terrain Empirical Model of Radio Channel
models, City Models Source: Kannan Srinivasan and Philip Levis, RSSI is
Communication Under Appreciated, ACM Workshop on Embedded
Networks  Models for indoor environments Networked Sensors (EmNets 2006),

 Free Path Loss Model

(Mathematical Model)

43

43

Characteristics of a model
 A model is never equal to the real system
because it is always simpler than the reality
Introduction
 The accuracy of a model is determined by its
tendency to approach the real system
Motivation
 Is that a problem?
Communication Yes, if the model ignore important parameters
Networks
of the real system (over simplification)
No, if the model takes into account the
important parameters (ignoring some details
is sometimes not problematic)

44

44

22
 Performance Evaluation of a
System
SYSTEM
There is always the
Experiment with the Experiment with a question of whether it
Actual System Model of the System actually reflects the
system.
Introduction
Too costly or disruptive
Not appropriate for the
design
Motivation
Make assumptions that take
Mathematical Model the form of mathematical or
Communication logical relationships
Networks

Analytical Solution Simulation

If the model is simple enough. E.g.,

calculus, algebra, probability theory Highly complex systems

45

45

Simulation Model versus Analytical

Model
Simulation is not used when a suitable mathematical
model exists

Simulations are often complex error-prone pieces of

Introduction
software

Motivation
Simulation only produce approximate answers

Communication
Networks Simulation can take a LONG time to execute

Mathematical models are less flexible, but they are exact

and efficient
• The problem is what model represents better the real world?

46

46

23
 Classification of Models

Dynamic Models Static Models

Introduction • Represents a • Time plays no

system as it role
Motivation evolves over • Represents the
time system at a
Communication
Networks • Example: Cars particular point
arriving to a in time
parking • Example: Monté
Carlo Method

47

47

Classification of Models
Deterministic
Stochastic Models
Models
Introduction • No probabilistic • Some components
component in the of the system has
Motivation system a probablistic
• Example: Worst- behavior (Random
Communication
Networks Case Analysis of variable, event
the system probability)
• Example:
Queueing systems

48

48

24
 Classification of Models
Continuous Models Discrete Models

• The state of the • The state of the

system changes system changes
Introduction
continuously only at discrete
• (e.g., chemical points in time.
Motivation processes)
Communication Bit Arrival in a Queue # of cars in a parking lot
Networks
bit bit

time time
Continuous Model Discrete Model
49

49

Example: Deterministic vs.

Stochastic
Queueuing System

Introduction

Waiting vs. Utilization

Motivation
0.25
0.2
0.15
W(sec)

Communication 0.1

Networks 0.05
0
0 0.2 0.4 0.6 0.8 1 1.2
r (%)

Stochastic Performance
Deterministic Performance
Using Queueing Theory
Using Network Calculus

50

50

25
 Model Development Lifecycle
Define goals, objectives of study

Develop conceptual model

Introduction
Fundamentally
an iterative
Motivation
Develop specification of model process

Communication Develop computational model

Networks

Verify model

Validate model
51

51

Model Development Lifecycle

Determine Goals and Objectives
• What do you want to do with the model?
• It may be an end in itself
Introduction
• More often, it is a means to an end
• Goals may not be known when you start the project!
• One often learns things along the way
Motivation
Develop Conceptual Model
Communication
Networks
• An abstract representation of the system
• What should be included in model? What can be left out?
• What abstractions should be used? What is the level of
details?
• Appropriate choice depends on the purpose of the model

52

52

26
 Model Development Lifecycle
Develop Specification Model
• A more detailed specification of the model including more specifics
• Collect data to populate model
• Example:
• Traffic: Road geometry, signal timing, expected traffic demand, driver
behavior
Introduction
• Communication: network topology, message type, inter-arrival time, data
rates
• Empirical data or probability distributions often used
Motivation
Develop a Computational Model
Communication • Executable simulation model
Networks • Software approach
• General purpose programming language
• Special purpose simulation language
• Other (non-functional) requirements
• Performance
• Interoperability with other models/tools/data

53

53

Model Development Lifecycle

Verification
• Did I Build the Model Right?
• Does the computational model match the specification model?
• Debugging: checking if the program contains any programming errors.
• Verification is different from Validation: (see model validation)!
Introduction
Validation
• Did I Build the Right Model?
Motivation • Does the computational model match the actual (or envisioned)
system?
• Typically, the validation of a simulation model can be done by comparing
Communication
• Measurements of actual system
Networks
• An analytic (mathematical) model of the system
• Another simulation model
• By necessity, validation is always an incomplete activity!
• Often can only validate portions of the model
• If you can validate the simulation with 100% certainty, why build the
simulation?

54

54

27
 Example: Airport Check-in Desk
Queuing

Introduction

Motivation

Communication
Networks  We consider flight check-in desks in an Airport. The administration
of the airport wants to improve its quality of service by reducing
the waiting time of travelers. For that purpose, they want to
design what could be the best queuing strategy to have the
minimum waiting time.
 The main problem is to know what is the best queuing strategy
that reduces the waiting time of travelers in check-in desks.
55

55

Step. 1. Define the objectives of the

study
 Main Objective: what is the best
queuing strategy that reduces the waiting
time of travelers in check-in desks.
Introduction  Find a model that enables to compute waiting
time of travelers
Motivation  Solution 1. Queueing Theory (Analytical Model)
 Solution 2. Simulation (Computer Program Model)
Communication
Networks  Two Possible Models

56
Model 1 Model 2

56

28
 Step. 2. Develop Conceptual
Model
What are the elements of the system?

Introduction

Motivation Model 1 Model 2

Communication One Queue  Three Queues

Networks
 N=3 servers  N=3 servers

 Customers: travelers that arrive to the check-in desk

 Servers: represents the agent (officer) that makes the
flight registration
57

57

Step. 3. Develop Specification Model

What are the characteristics of the elements of the
system?

Introduction

Model 1 Model 2
Motivation
 One Queue:  Three Queue:
 Length= 60 Travelers  Length= 20 Travelers/Queue
Communication
Networks  N=3 Agents  N=3 Agents
 Service rate: 30  Service rate: 30 travelers/hour
travelers/hour  Travelers arrive with a rate 1
travelers/minute
 Travelers arrive with a
rate  Travelers choose a queue with a

1 travelers/minute probability of 1/3.

58

58

29
 Step. 4. Develop Computation Model
Analytical Model: Queueing Theory

Introduction Model 1 Model 2

1
Delay ( Model 2 )   6 minutes
Motivation (   1 )

Communication 1 (N r ) N
r  26
Delay ( Model 1)  N r  0    2.88 minutes
Networks
  N! (1  r ) 2 
 9

Model 1 is better than Model 2 because it has lower

delay

59

59

Step. 4. Develop Computation Model

Simulation
Model: Arena

Introduction

Motivation

Communication
Networks Model 1 Model 2
Delay (Model 1)  2.93 minutes Delay ( Model 2 )  5.86 minutes

Model 1 is better than Model 2 because it has lower

delay

60

60

30
 End of the Subject
Introduction

Motivation
Introduction
Communication
Networks

61

61

31