Transcript ppt - DPNM Lab

Changbin Liu, Lei Shi, Bin Liu
Department of Computer Science and Technology, Tsinghua University
Proceedings of the Fourth European Conference on Universal Multiservice Networks
(ECUMN’07)
Chen Bin Kuo (20077202)
Young J. Won (20063292)






Introduction
NGN traffic classifications and their utility functions
Network utility maximization (NUM)
Numeric results and analysis
Discussion
Conclusion
DPNM Lab.
4/11/2016
2

Next generation network (NGN) must natively
support triple-plays.

How to schedule traffic and allocate bandwidth at
both backbone and access links.

Designing a scheduling (bandwidth allocation)
algorithm is exactly the issue this paper tries to settle.
DPNM Lab.
4/11/2016
3

In industry designing NGN [13][14], the strictpriority scheduling is mostly adopted.
 Rigidly favors the voice and video traffic without flexibility

Utility-based solutions
 Shenker [1] discussed traffic classifications in IP network
from the viewpoint of user utility
 Kelly et al. [5][6] applying utility-based methods to
scheduling and bandwidth allocation in the objective of
Network Utility Maximization (NUM)
DPNM Lab.
4/11/2016
4

No single work has emphasized on the practical issue
of scheduling triple-play services under the
background of NGN.

Translating this issue into a nonlinear maximization
problem with inequality constraints.
DPNM Lab.
4/11/2016
5
a)
b)
c)
d)
e)
VoIP traffic
IPTV traffic
TCP elastic traffic
HTTP traffic
Other UDP traffic
4/11/2016
6

Due to remarkable distinction of QoS requirements
in NGN
 Classifying NGN traffic into five categories

User utility function is introduced
 To measure network performance and user satisfaction
degree
 Determined by the QoS metrics received in the user end
 Including packet delay, jitter and loss rate
DPNM Lab.
4/11/2016
7

Sensitive to packet delay and loss caused by
bandwidth insufficiency
 Utility function falls into the category of hard real-time kind
[1][2][10], with a minimal bandwidth requirement of Bmin1
DPNM Lab.
4/11/2016
8

Utility function is similar to VoIP’s but with some
differences
 Tolerate occasional delay-bound violations and packet drops
 Minimal encoding rate, denoted as Bmin2 is independent of
network congestion
 Logistic model is used
DPNM Lab.
4/11/2016
9

Generated by delay-tolerant TCP applications
 Such as file transfer and email

Utility function have been studied by Kelly et al. [6]
and other researchers [11][12]
DPNM Lab.
4/11/2016
10

TCP traffic which concerns packet delay
 Mainly contains the HTTP traffic generated by web services

Utility function is different from TCP elastic traffic,
has a minimum tolerable bandwidth Bmin4
DPNM Lab.
4/11/2016
11

DNS packets, other streaming media traffic, and online gaming traffic [17][18]
 Delay-sensitive
 Every application type has a utility function

The shape of utility function resembles IPTV traffic
DPNM Lab.
4/11/2016
12
Bmin
VoIP
IPTV
64Kbps
100 Kbps
Bmax
10Mbps
ɛ
0.001
DPNM Lab.
TCP elastic
HTTP
UDP
24Kbps
10Mbps
10Mbps
500Kbps
0.001
4/11/2016
13
a)
b)
KKT method
Lagrange multipliers method without KKT conditions
4/11/2016
14

Based on NGN traffic’s utility functions, we can
solve the congestion-phased bandwidth allocation
issue while conforming to NUM.

Total utility gained on the link is:

Bandwidth allocation is restricted by:
N : the number of NGN
users utilizing this link
pi : traffics classes
C : the bandwidth of a link
(set to 10Gbps)
DPNM Lab.
4/11/2016
15

Lagrange Multiplier method with KKT (KarushKuhn-Tucker) conditions

Solving the nonlinear optimization problem

Accurate and comprehensive solution requires
substantial complicated computations
 Applying simplified form which is enough to ravel NUM
problem for triple-plays
DPNM Lab.
4/11/2016
16

Observing NGN traffic’s utility functions
 VoIP/IPTV/other UDP traffic’s utility functions are
relatively smoother in some points
 It is not cost-effective to allocate bandwidth to
VoIP/IPTV/other UDP traffic without booming the utility

Turning point (TP)
IPTV
HTTP
Bandwidth
DPNM Lab.
4/11/2016
17

After finding the TP, we can apply the Lagrange
Multipliers method without KKT conditions to solve
the NUM problem in (10)

Subject to:
DPNM Lab.
4/11/2016
18
a)
b)
Data-dominated network
IPTV-dominated network
4/11/2016
19

Two network scenarios
 Current Internet, where HTTP and TCP elastic traffic still
dominate the volume
 Prospective NGN, where the emerging services, especially
the IPTV traffic, will dominate the network

For each scenario, calculate in two situations
 Maximal Utility Equalization (MUE)
 Maximal Utility In-equalization (MUI)
V1 (VoIP)
V2 (IPTV)
V3 (TCP elastic)
V4 (HTTP)
V5 (other UDP)
MUE
1
1
1
1
1
MUI
1
9
1
1.5
2
DPNM Lab.
4/11/2016
20

Data-dominated network
 According to recent trace observation [15]
VoIP
Traffic
proportions

10%
IPTV
TCP elastic
10%
10%
HTTP
other UDP
50%
20%
IPTV-dominated network
VoIP
Traffic
proportions
10%
DPNM Lab.
IPTV
50%
TCP elastic
10%
HTTP
other UDP
20%
4/11/2016
10%
21
DPNM Lab.
4/11/2016
22
DPNM Lab.
4/11/2016
23

Previous bandwidth allocation schemes for tripleplay services mostly adopt the strict-priority
scheduling
 Highest priority to VoIP traffic
 Second highest priority to IPTV and lowest priority to others

In this paper
 Highest priority to VoIP traffic
 Assigning IPTV traffic with second-highest priority is not
well supported from the objective of NUM
 Suggesting that ISP charges more about IPTV services
(future work)
DPNM Lab.
4/11/2016
24



Studied the problem of scheduling and bandwidth
allocation for triple-play services in the objective of
NUM.
Presenting theoretical method to compute bandwidth
allocation results
Results:
 VoIP and other low-throughput UDP traffic can always be
guaranteed of sufficient bandwidth
 As congestion becomes severer, IPTV’s bandwidth
decreasing quickly
 TCP elastic and HTTP traffic experience exponential
bandwidth degradations when congestion degree increases
DPNM Lab.
4/11/2016
25
4/11/2016
26