Transcript Free telephony

Lecture 17. ATM VPs, circuit-switching
D. Moltchanov, TUT, Spring 2015
Outline
ATM virtual path design
Telephone network: single BH
Telephone network: multiple BH
ATM virtual path design
ATM virtual path design
Asynchronous transfer mode (ATM)
Concept of virtual paths (VP) and virtual circuits (VC)
VP: permanent/semi-permanent connections
Several VC multiplexed into one VP
Similar to MPLS but completely separate from IP network
Still used mainly in US
Could be: IP/ATM/SONET or something like this…
ATM virtual path design
Problem we consider
How to determine the link capacity such that the total link cost
is minimized given a set of unsplittable demands and modular
link units of 155Mbps?
Analysis is as usual
Get demands constraints: how demands are realized over path
Get capacity constraints: which flows are using links (link loads)
Analyzing the problem
We have set of paths for demand d: p  1,2, , Pd
Unsplittable (non-bifurcated) solution is needed
We need a binary variable udp {0,1}
Tells us whether a path is chosen or not
Pd
u
p 1
dp
 1, d  1, 2,
which gives us demand constraint
,D
ATM virtual path design
Continuing
Total number of VPs using link e
Pd

p 1
u
edp dp
At most one flow will use link e for each demand due to
Pd
u
p 1
dp
 1, d  1, 2,
,D
If a flow uses link then full demand is realized over this link
The link load is then
Pd
D
 h 
d 1
d
p 1
u  ye , e  1, 2, .E
edp dp
Assume that demand volume and link rates are in units of 155Mbps
Pd
D
 h 
d 1
d
p 1
u  ye , e  1, 2, .E
edp dp
where link rate ye for link e is an integer
ATM virtual path design
Objective function
We are to minimize cost
Let unit cost of 155Mbps be  e in link e
E
 y
The whole problem E
Minimize F  e ye
e1
Subject to
e1
e e

Pd
u
p 1
D
dp
 1, d  1, 2,
Pd
 h 
d 1
d
p 1
,D
u  ye , e  1, 2, .E
edp dp
where udp is binary, ye are integers
Integer programming (IP) problem! Complex to solve!
Applicable to MPLS directly…
ATM virtual path design: LP vs. IP problem
Recall similar problem
minimize F 
E
 y
e1
e e
Pd
x
p 1
subject to
D
dp
 hd , d  1, 2,
Pd

d 1 p 1
,D
x  ye , e  1, 2,
edp dp
,E
y  0, x  0
We have here IP version of LP problem
Pd
minimize F 
E
e ye subject to
e1
u
p 1
D
dp
 1, d  1, 2,
Pd
 h 
d 1
d
p 1
,D
u  ye , e  1, 2, .E
edp dp
udp binary ye integers
Note: way more complex to solve compared to LP
Circuit-switched telephony: single BH
Telephony: single busy hour design
Nodes in telephony networks
End nodes
Transit nodes
End nodes (access nodes)
Digital exchanges generating demand
Demand is expressed in Erlangs
During the busy hour
Network is underloaded at other times
Transit nodes: do not generate demands, act as relays
The describe the load we need
 be the average arrival rate
 be the average duration of a call
the offered traffic load is then
a   , Erlangs
1 Erl:
Telephony: circuits/trunks
Circuits/trunks
Calls require 64Kbps
Calls require path for the whole duration of a session
Path may traverse se sequence of transit nodes
Links between nodes: trunk-groups or circuit-groups
Installation of trunks
Typically installed in module
US/Japan T1 (1.5Mbps) – 24 trunks
Rest of the world: E1 (2.048Mbps) – 30 trunks (+2 signaling, 0 and 16)
Modular link capacity: a number of E1 trunks, 30,60,90,…!
1 LCU = 30, DVU are arbitrary integers
Telephony: problem and GoS
Problem we are to solve
How to determine the modular capacity needed in the network
so that the offered traffic is carried with some acceptable grade
of service (GoS)?
What is grade-of-service (GoS)?
Set of metrics attributed to traffic performance in the network
Simply: allowed call dropping probability (CDP)
Dropping: all resources are busy
Telephone networks
GoS is different for different type of calls
Local: 5-8% CDP during BH
International: 1-3% during BH
Cellular? 5-8% during BH
Networks are always designed for BH!
Telephony: call routing
Call routing
7
According to fixed rules
Using a set of predefined routes
Example
6
demand d: end nodes 1 and 2
1
there are three available routes, Pd=3
(1,3, 4, 2) (1,3,5, 4, 2) (1,3,6, 2)
2
4
3
5
(1,3,7,6,2), (1,3,7,6,4,2) uses end-node 7 which is not allowed
route (1,2,6,4,2) just prohibited
Possible routing rule
Split demand between routes such that
Pd
x
d 1
dp
 hd , d  1, 2,
,D
and we are getting demand constraints
Implemented using load sharing: route p with probability xdp hd
Telephony: call routing
Links load (taking into account load sharing) are
D
Pd

d 1 p 1
x  ye , e  1, 2,
edp dp
,E
where  edp is 1 if link e belongs to path p of demand d
Important notes
link load: average offered traffic to link e (Erl.)
average number of calls in progress given no losses on a link!
given that the link has infinite capacity!
Let be be the call blocking probability for link e, i.e.
b  B ( a, c ) 
ac c!
k
a
 k 0 k !
c
a is the offered load
c is the number of trunks (circuits)
probability that all servers are busy in M/M/c/c queue
Telephony: call routing
B ( a, c )
c 1
c2
c5
B ( a, c )
c  1,3,5,10,25,50,100,1000
c 1
c  10
c  20
c  1000
a, Erl.
However, we want to get c for a certain (a,b)
Forward formula gives b for certain (a,c)
Let c=C(a,b) be inverse of Erlang-B loss formula
Function C(a,b) is concave in a for any b
a, Erl.
Telephony: call routing
Link dependent dimensioning function
Fe (a)  C (a, be )
where be is a certain dimensioning constant (e.g. 1% of losses)
Fe (a) gives real number of circuits to carry offered load a
The whole problem
For offered demands, blocking and unit modular capacity cost
E
Minimize F 
y
e1 e e
Subject to

Pd
x
d 1
dp
 hd , d  1, 2,
,D
 D Pd

Fe    edp xdp   Mye , e  1, 2, , E
 d 1 p 1

where xdp continuous non-negative, ye integers
Concave-integer dimensioning problem
Circuit-switched telephony: multiple BHs
Telephony: multiple BHs
We considered the case
Busy hours of all demands coincide
E.g. all happen at, say 15:00-16:00
May only happen in local proximity
Same time-zone, small country inside a single time-zone
US as an example
8:00 AM Eastern time zone (NY, Boston, Washington)
5:00 AM Pacific time zone (LA, San-Francisco, Seattle)
BHs do not coincide due to time difference
Beneficial for large carriers
Decrease the capacity needed
Route via “still” or “already” lightly loaded regions
Why call prices are that high? Network is unloaded anyway!
Telephony: routing of calls again
Routing in 1970-1980
7
Fixed-order of routes + load sharing
6
Routing 1980 onwards
1
3
Dynamic non-heirarchial routing (DBHR)
5
Dynamically controlled routing (DCR)
Dynamic alternative routing (DAR)
Real-timer network routing (RTNR)
Common: free capacity due to non-coincidence of BHs
One time zone is used as a reference
Applied to core network, e.g. transit nodes
2
4
Telephony: routing of calls again
Problem we consider
How to do modular capacity design given that traffic volume
is different for different times of a day and by taking into
account functional characteristics of a routing scheme.
New demand representation
Partition a day into several “traffic hours” t=1,2,…,T
For each demand its traffic is different at different intervals
Set of demand volume vectors
h1 , h2 ,
, hT , ht  (h1t , h2t ,
, hDt )
Paths is real networks
May contain at most two links
In other words may traverse at most one intermediate hop
We do not even need an algorithm to get them…
Telephony: routing of calls again
Dynamic nature of a flow
Routing should be different at different traffic hours, t=1,2,…,T
Demand d for path p at time t is denoted as
xdpt , d  1, 2,
, D, p  1, 2,
, Pd , t  1, 2,
,T
The whole problem
For demands, blocking, modular capacity cost and t=1,2,…,T
E
Minimize F 
y
e1 e e
Subject to

Pd
x
d 1
dpt
 hdt , d  1, 2,
, D, t  1, 2,
,T
 D Pd

Fet    edpt xdpt   Mye , e  1, 2, , E , t  1, 2, , T
 d 1 p 1

where xdpt are non-negative continuous, ye are integers
Similar concave-integer programming problem
Telephony: routing of calls again
Nodes on dynamic routing
Add another dimension of flexibility
Solution is only slightly more complex
Fet (a) can be made time-dependent
Slightly higher blocking during the links’ busy period
Multi-BH scenario for packet-switching
Dynamic routing is good for packet networks
Dependence of time zones is also evident
Similar to voice traffic
Different traffic matrices for different time of a day
May result in substantial cost savings
Adds implementation complexity