Telecommunication Systems
and Networks
Tomasz Kacprzak
Technical University of A
ódz

Institute of Electronics
Wólczańska Street 211/215, 3th floor, room 317b
90-924 A
ódz

e-mail: tomasz.kacprzak@.p.lodz.pl
phone: [phone]
Telecommunication Systems
and Networks
LECTURE 6
Objective of the course
To gain fundamental understanding of the key
concepts behind communication systems and
networks engineering - in order to provide basic
skills in design and performance analysis of
these networks and services offered for end
users.
Prerequisites:
mathematics, basic electrical engineering,
physics.
Telecommunication Systems and Networks
2011-2012
3
Tomasz Kacprzak - Lecture 6
network network
Data link Data link
physical physical
network
R1 R3
Data link
physical
R4
H1
WAN
application
transport
LAN 1
network
R2
LAN 2
data link
physical
application
H2 transport
network
data link
physical
Telecommunication Systems and Networks
2011-2012
4
Tomasz Kacprzak - Lecture 6
Routing in WANs
Shortest Path Routing - Dijkstra s Algorithm
W(Ą�,-) Y(Ą�,-)
1
2
3
1
4
2
V (Ą�,-)
source
X(Ą�,-)
Z (Ą�,-)
destination
7
Telecommunication Systems and Networks
2011-2012
5
Tomasz Kacprzak - Lecture 6
Each node j is labeled with:
1. Cost of reaching the node
2. Label of the one node back on the route
Example: W(2,V)
W(Ą�,-) Y(Ą�,-)
Step1 - initialization
1
2
3
1
4
2
V (0,-)
source
X(Ą�,-)
Z (Ą�,-)
destination
7
Nodes
V W X Y Z
Cost
0 Ą� Ą� Ą� Ą�
Last node - - - - -
N N N N N
Determination
Telecommunication Systems and Networks
2011-2012
6
Tomasz Kacprzak - Lecture 6
Step 2
" Choose the nondermined node with
V W X Y Z
lowest cost; this is V
0 2 4 Ą� 7
" Lebel it as determined and check out its
nondetermined neighbours; they are W,
- V V - V
X and Z
D N N N N
" Change their actual costs and previous
node
W(2,V) Y(Ą�,-)
1
2
3
1
4
2
V (0,-)
source
X(4,V)
Z (7,V)
destination
7
Telecommunication Systems and Networks
2011-2012
7
Tomasz Kacprzak - Lecture 6
Step 3
" Choose the nondetermined node with lowest
V W X Y Z
cost; this is W
" Lebel it as determined and check out its
0 2 3 3 7
nondetermined neighbours; they are X and Y
- V W W V
" The cost to X through W is 2+1 < 4, change
D D N N N
information to 3, also the cost to Y is 2+1 < Ą�,
change information to 3
W(2,V) Y(3,W)
1
2
3
1
4
2
V (0,-)
source
X(3,W)
Z (7,V)
destination
7
Telecommunication Systems and Networks
2011-2012
8
Tomasz Kacprzak - Lecture 6
Step 4
" Choose the nondetermined node with
V W X Y Z
lowest cost; this is X
0 2 3 3 5
" Lebel it as determined and check out its
nondetermined neighbours; it is Z
- V W W X
" The cost to Z through X is 3+2 < 7, change
D D D N N
information to 5 < Ą�
W(2,V) Y(3,W)
1
2
3
1
4
2
V (0,-)
source
X(3,W)
Z (7,V)
destination
7
Telecommunication Systems and Networks
2011-2012
9
Tomasz Kacprzak - Lecture 6
Step 5
" Choose the nondetermined node with
V W X Y Z
lowest cost; this is Y
0 2 3 3 5
" Lebel it as determined and check out its
nondetermined neighbours; it is only Z
- V W W X
" The cost to Z through Y is 3+3 > 5,
D D D D N
therefore the cost is not changed
W(2,V) Y(3,W)
1
2
3
1
4
2
V (0,-)
source
X(3,W)
Z (7,V)
destination
7
Telecommunication Systems and Networks
2011-2012
10
Tomasz Kacprzak - Lecture 6
Step 6
" Choose the nondetermined node with
V W X Y Z
lowest cost; this is Z
0 2 3 3 5
" Lebel it as determined and check out its
nondetermined neighbours;
- V W W X
" No nondermined neighbours
D D D D D
" The algorithm is completed.
W(2,V) Y(3,W)
1
2
3
1
4
2
V (0,-)
source
X(3,W)
Z (7,V)
destination
7
Telecommunication Systems and Networks
2011-2012
11
Tomasz Kacprzak - Lecture 6
Step 7
V W X Y Z
" Determine the shortest path
0 2 3 3 5
" Take inverse sequence from the
destination W to the source V through the
- V W W X
previous nodes
D D D D D
" The shortest path is V W X Z
" with minimum cost 5
W(2,V) Y(3,W)
1
2
3
1
4
2
V (0,-)
source
X(3,W)
Z (7,V)
destination
7
Telecommunication Systems and Networks
2011-2012
12
Tomasz Kacprzak - Lecture 6
ALGORITHM
Initialization
1. Mark all nodes as being  unscanned U
2. Set d(i,i) = 0 (value), distance from node i to itself
3. Set d(i,j) = Ą� for all node j not equal to it i
4. Set d(i,j) = l(i,j) , where
l(j,k) is the length of the link from j to k
5. Set the pointer at j to i for all nodes j directly adjacent
to i.
Telecommunication Systems and Networks
2011-2012
13
Tomasz Kacprzak - Lecture 6
ALGORITHM
Run
1. Mark node i as being  scanned S
2. If all nodes are  scanned , stop the algorithm,
otherwise:
3. Find the  unscanned node j with the smallest d(i,j)
4. Scanning
for all nodes k directly adjacent to j
if d(i,j) + l(j,k) < d(i,k)
then d(i,k) := d(i,j) + l(j,k)
and set the pointer at k to j
otherwise no change .
5. Mark node j as having been  scanned
6. Go to 2
Telecommunication Systems and Networks
2011-2012
14
Tomasz Kacprzak - Lecture 6
Dijkstra s Algorithm
Task to solve  find trace from C to E with minimum cost
A
B
3
3
2
2
1 E
2
C
D
4
5
3
2
G
F
Telecommunication Systems and Networks
2011-2012
15
Tomasz Kacprzak - Lecture 6