Scalable QoS Prediction for Service Adaptation in Service-Based Applications
undefined
Towards Online, Accurate, and
Scalable QoS Prediction for
Runtime Service Adaptation
Jieming Zhu, Pinjia He, Zibin Zheng,
and Michael R. Lyu
The Chinese University of Hong Kong
ICDCS 2014
Madrid, Spain 30 June-3 July 2014
Outline
I
n
t
r
o
d
u
c
t
i
o
n
Q
o
S
P
r
e
d
i
c
t
i
o
n
P
r
o
b
l
e
m
C
o
l
l
a
b
o
r
a
t
i
v
e
F
i
l
t
e
r
i
n
g
A
d
a
p
t
i
v
e
M
a
t
r
i
x
F
a
c
t
o
r
i
z
a
t
i
o
n
E
x
p
e
r
i
m
e
n
t
s
C
o
n
c
l
u
s
i
o
n
&
F
u
t
u
r
e
W
o
r
k
2
Introduction
S
e
r
v
i
c
e
-
b
a
s
e
d
a
p
p
l
i
c
a
t
i
o
n
s
:
b
u
i
l
t
o
n
a
s
e
t
o
f
c
o
m
p
o
n
e
n
t
s
e
r
v
i
c
e
s
3
[ref. http://www.priceline.com]
Introduction
R
e
d
u
n
d
a
n
t
s
e
r
v
i
c
e
s
:
f
u
n
c
t
i
o
n
a
l
l
y
-
e
q
u
i
v
a
l
e
n
t
s
e
r
v
i
c
e
s
p
r
o
v
i
d
e
d
i
n
t
h
e
c
l
o
u
d
4
Car rental s
ervices provided by
different companies
Introduction
Q
u
a
l
i
t
y
-
o
f
-
S
e
r
v
i
c
e
(
Q
o
S
)
:
u
s
e
r
r
e
q
u
i
r
e
m
e
n
t
s
Response time, throughput, failure probability
C
o
m
p
l
e
x
o
p
e
r
a
t
i
n
g
e
n
v
i
r
o
n
m
e
n
t
Service failures / SLA violations
5
Failure
Introduction
S
e
r
v
i
c
e
a
d
a
p
t
a
t
i
o
n
:
s
w
i
t
c
h
a
w
o
r
k
i
n
g
s
e
r
v
i
c
e
t
o
a
c
a
n
d
i
d
a
t
e
s
e
r
v
i
c
e
a
t
r
u
n
t
i
m
e
(
e
.
g
.
,
B
1
B
2
)
Loose coupling and dynamic binding
Make use of redundant services
Become resilient against failures of component services
6
Introduction
D
e
c
i
s
i
o
n
s
f
o
r
s
e
r
v
i
c
e
a
d
a
p
t
a
t
i
o
n
When to trigger an adaptation action?
Which working services to be replaced?
Which candidate services to employ?
N
e
e
d
a
v
a
i
l
a
b
l
e
Q
o
S
i
n
f
o
r
m
a
t
i
o
n
o
f
c
o
m
p
o
n
e
n
t
s
e
r
v
i
c
e
s
QoS for working services
Existing work:
e.g., monitoring
QoS for candidate services
Our work:
unsolved problem
7
Outline
I
n
t
r
o
d
u
c
t
i
o
n
Q
o
S
P
r
e
d
i
c
t
i
o
n
P
r
o
b
l
e
m
C
o
l
l
a
b
o
r
a
t
i
v
e
F
i
l
t
e
r
i
n
g
A
d
a
p
t
i
v
e
M
a
t
r
i
x
F
a
c
t
o
r
i
z
a
t
i
o
n
E
x
p
e
r
i
m
e
n
t
s
C
o
n
c
l
u
s
i
o
n
s
&
F
u
t
u
r
e
W
o
r
k
8
Observations
Q
o
S
A
t
t
r
i
b
u
t
e
s
Dynamic:
Users are distributed worldwide
The workload of service is varying
Network is dynamic
User-specific:
Different users may perceive different QoS
M
o
n
i
t
o
r
a
l
l
Q
o
S
v
a
l
u
e
s
:
s
t
r
a
i
g
h
t
f
o
r
w
a
r
d
y
e
t
i
m
p
r
a
c
t
i
c
a
l
A large number of users as well as services
Prohibitive overhead at runtime
9
Challenges
Q
o
S
p
r
e
d
i
c
t
i
o
n
:
a
p
r
o
m
i
s
i
n
g
a
p
p
r
o
a
c
h
10
Predict the
missing values
Outline
I
n
t
r
o
d
u
c
t
i
o
n
Q
o
S
P
r
e
d
i
c
t
i
o
n
P
r
o
b
l
e
m
C
o
l
l
a
b
o
r
a
t
i
v
e
F
i
l
t
e
r
i
n
g
A
d
a
p
t
i
v
e
M
a
t
r
i
x
F
a
c
t
o
r
i
z
a
t
i
o
n
E
x
p
e
r
i
m
e
n
t
s
C
o
n
c
l
u
s
i
o
n
&
F
u
t
u
r
e
W
o
r
k
11
Collaborative Filtering (CF)
C
o
l
l
a
b
o
r
a
t
i
v
e
f
i
l
t
e
r
i
n
g
p
r
o
b
l
e
m
User-movie rating prediction (Netflix challenge)
Similar users (e.g., similar preferences)
Similar movies (e.g., similar themes)
12
movies
users
Rating
matrix
CF vs QoS Prediction
U
s
e
r
-
p
e
r
c
e
i
v
e
d
Q
o
S
p
r
e
d
i
c
t
i
o
n
C
o
l
l
a
b
o
r
a
t
i
v
e
f
i
l
t
e
r
i
n
g
f
o
r
Q
o
S
p
r
e
d
i
c
t
i
o
n
?
13
Classic model for CF
M
a
t
r
i
x
f
a
c
t
o
r
i
z
a
t
i
o
n
(
M
F
)
:
M
i
n
i
m
i
z
a
t
i
o
n
f
o
r
m
u
l
a
t
i
o
n
:
Usually solved by gradient descend algorithm (batch mode)
14
Sum of squared error
Regularization terms
Limitations of MF for QoS prediction
L
i
m
i
t
a
t
i
o
n
1
:
s
k
e
w
e
d
Q
o
S
v
a
l
u
e
d
i
s
t
r
i
b
u
t
i
o
n
s
Mismatch with the probabilistic assumption for MF
Degrade its prediction accuracy
L
i
m
i
t
a
t
i
o
n
2
:
t
i
m
e
v
a
r
y
i
n
g
Q
o
S
v
a
l
u
e
s
Existing QoS values can be continuously updated
However, MF work offline, and cannot adapt to new
observed QoS values
15
Response Time
Throughput
Limitations of MF for QoS prediction
L
i
m
i
t
a
t
i
o
n
3
:
s
c
a
l
a
b
i
l
i
t
y
o
n
n
e
w
u
s
e
r
s
a
n
d
s
e
r
v
i
c
e
s
Users and services may join or leave the environment
MF works on a matrix with a fixed size, not scalable
H
o
w
t
o
a
d
d
r
e
s
s
t
h
e
s
e
l
i
m
i
t
a
t
i
o
n
s
?
Our approach: adaptive matrix factorization
Aim to meet the requirements of being online, accurate,
and scalable
16
Adaptive Matrix Factorization
A
l
g
o
r
i
t
h
m
o
v
e
r
v
i
e
w
17
Box-Cox transformation (to address limitation 1)
Stabilize data variance
Rank-preserving
18
Key Techniques 1: Data Transformation
Response Time
Throughput
Response Time
Throughput
Online learning (to address limitation 2)
Stochastic gradient descent (SGD)
Adapt to each newly observed data sample
Update a user vector and a service vector at each step
E
x
t
e
n
s
i
b
l
e
t
o
n
e
w
u
s
e
r
s
a
n
d
s
e
r
v
i
c
e
s
19
Key Techniques 2: Online Learning
SGD update rules
Online mode
A
d
a
p
t
i
v
e
w
e
i
g
h
t
s
(
t
o
a
d
d
r
e
s
s
l
i
m
i
t
a
t
i
o
n
3
)
Become robust
Existing users and services keep stable
New users and services converge fast
Unique learning rate for each user/service
Large for new vectors, small for converged vectors
20
Key Techniques 3: Adaptive Weights
Outline
I
n
t
r
o
d
u
c
t
i
o
n
Q
o
S
P
r
e
d
i
c
t
i
o
n
P
r
o
b
l
e
m
C
o
l
l
a
b
o
r
a
t
i
v
e
F
i
l
t
e
r
i
n
g
A
d
a
p
t
i
v
e
M
a
t
r
i
x
F
a
c
t
o
r
i
z
a
t
i
o
n
E
x
p
e
r
i
m
e
n
t
s
C
o
n
c
l
u
s
i
o
n
&
F
u
t
u
r
e
W
o
r
k
21
D
a
t
a
s
e
t
c
o
l
l
e
c
t
i
o
n
Response time (RT):
user-perceived delay of service
invocation (sec)
Throughput (TP):
data transmission rate (kbps)
142 * 4500 * 64
QoS matrix
142
users (Planetlab nodes)
4,500
real-world Web services
64
time slices, at
15
min time interval
Experiments
22
23
E
v
a
l
u
a
t
i
o
n
M
e
t
r
i
c
s
MAE (Mean Absolute Error):
to measure the average
prediction accuracy
MRE (Median Relative Error):
a key metric to identify the
error effect of different magnitudes of prediction values
NMRE (Ninety-Percentile Relative Error)
：
NPRE takes the
90th percentile of all the pairwise relative errors
Experiments
P
e
r
f
o
r
m
a
n
c
e
C
o
m
p
a
r
i
s
o
n
Compared approaches:
UPCC, IPCC, UIPCC:
conventional CF baselines
PMF:
convectional matrix factorization approach
These approaches cannot perform online
Matrix density:
means how many historical data we use
Experiments
24
Experiments
25
E
f
f
i
c
i
e
n
c
y
a
n
a
l
y
s
i
s
Compared approaches:
UIPCC
PMF
Experiments
26
Re-train the entire model
at each time slice
AMF: continuously
and incremental
updating
S
c
a
l
a
b
i
l
i
t
y
a
n
a
l
y
s
i
s
80% of users and services at time slice 1 as existing users and
services
Add the remaining 20% into the model
Experiments
27
Robust to new users and services
Outline
I
n
t
r
o
d
u
c
t
i
o
n
Q
o
S
P
r
e
d
i
c
t
i
o
n
P
r
o
b
l
e
m
C
o
l
l
a
b
o
r
a
t
i
v
e
F
i
l
t
e
r
i
n
g
A
d
a
p
t
i
v
e
M
a
t
r
i
x
F
a
c
t
o
r
i
z
a
t
i
o
n
E
x
p
e
r
i
m
e
n
t
s
C
o
n
c
l
u
s
i
o
n
&
F
u
t
u
r
e
W
o
r
k
28
Q
o
S
p
r
e
d
i
c
t
i
o
n
f
o
r
c
a
n
d
i
d
a
t
e
s
e
r
v
i
c
e
s
AMF: Adaptive Matrix Factorization
Data transformation, online learning, and adaptive weights
Online, accurate, and scalable
F
u
t
u
r
e
w
o
r
k
Implement our QoS prediction approach together with
service adaptation mechanisms
Real-world evaluation on case studies
Conclusions
29
Our data & code are available at:
http://wsdream.github.io/AMF
30
Thank you!
This study delves into the challenge of predicting Quality of Service (QoS) for runtime service adaptation in service-based applications. It explores collaborative filtering and adaptive matrix factorization techniques for accurate QoS prediction, aiming towards enhancing service resilience and reducing failures in a dynamic operating environment.
Uploaded on Sep 14, 2024 | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
ICDCS 2014 Madrid, Spain 30 June-3 July 2014 Towards Online, Accurate, and Scalable QoS Prediction for Runtime Service Adaptation Zhu, Pinjia Pinjia He, and Michael R. and Michael R. Lyu The Chinese University of Hong Kong The Chinese University of Hong Kong Jieming Jieming Zhu, He, Zibin Zibin Zheng, Lyu Zheng,
Outline Introduction QoS Prediction Problem Collaborative Filtering Adaptive Matrix Factorization Experiments Conclusion & Future Work 2
Introduction Service-based applications: built on a set of component services Service Service Service Service 3 [ref. http://www.priceline.com]
Introduction Redundant services: functionally-equivalent services provided in the cloud Car rental services provided by different companies 4
Introduction Failure Quality-of-Service (QoS): user requirements Response time, throughput, failure probability Complex operating environment Service failures / SLA violations 5
Introduction Service adaptation: switch a working service to a candidate service at runtime (e.g., B1 B2) Loose coupling and dynamic binding Make use of redundant services Become resilient against failures of component services 6
Introduction Decisions for service adaptation When to trigger an adaptation action? Which working services to be replaced? Which candidate services to employ? Need available QoS information of component services QoS for working services Existing work: e.g., monitoring QoS for candidate services Our work: unsolved problem 7
Outline Introduction QoS Prediction Problem Collaborative Filtering Adaptive Matrix Factorization Experiments Conclusions & Future Work 8
Observations QoS Attributes Dynamic: Users are distributed worldwide The workload of service is varying Network is dynamic User-specific: Different users may perceive different QoS Monitor all QoS values: straightforward yet impractical A large number of users as well as services Prohibitive overhead at runtime 9
Challenges QoS prediction: a promising approach Predict the missing values 10
Outline Introduction QoS Prediction Problem Collaborative Filtering Adaptive Matrix Factorization Experiments Conclusion & Future Work 11
Collaborative Filtering (CF) Collaborative filtering problem User-movie rating prediction (Netflix challenge) Similar users (e.g., similar preferences) Similar movies (e.g., similar themes) movies Rating matrix users 12
CF vs QoS Prediction User-perceived QoS prediction Collaborative filtering for QoS prediction? Collaborative filtering QoS Prediction User- movie rating matrix Rows users Columns movies User-service QoS matrix Rows users Columns services Latent factors: preferences, topics Latent factors: network, workload 13
Classic model for CF Matrix factorization (MF): Minimization formulation: Regularization terms Sum of squared error Usually solved by gradient descend algorithm (batch mode) 14
Limitations of MF for QoS prediction Limitation 1: skewed QoS value distributions Mismatch with the probabilistic assumption for MF Degrade its prediction accuracy Response Time Throughput Limitation 2: time varying QoS values Existing QoS values can be continuously updated However, MF work offline, and cannot adapt to new observed QoS values 15
Limitations of MF for QoS prediction Limitation 3: scalability on new users and services Users and services may join or leave the environment MF works on a matrix with a fixed size, not scalable How to address these limitations? Our approach: adaptive matrix factorization Aim to meet the requirements of being online, accurate, and scalable 16
Adaptive Matrix Factorization Algorithm overview QoS data stream collection Data transformation Online learning and updating Return predicted QoS values 17
Key Techniques 1: Data Transformation Box-Cox transformation (to address limitation 1) Stabilize data variance Rank-preserving Response Time Throughput Response Time 18 Throughput
Key Techniques 2: Online Learning Online learning (to address limitation 2) Stochastic gradient descent (SGD) Adapt to each newly observed data sample Update a user vector and a service vector at each step Online mode SGD update rules Extensible to new users and services 19
Key Techniques 3: Adaptive Weights Adaptive weights (to address limitation 3) Become robust Existing users and services keep stable New users and services converge fast Unique learning rate for each user/service Large for new vectors, small for converged vectors 1.0 1.5 20
Outline Introduction QoS Prediction Problem Collaborative Filtering Adaptive Matrix Factorization Experiments Conclusion & Future Work 21
Experiments Dataset collection Response time (RT): user-perceived delay of service invocation (sec) Throughput (TP): data transmission rate (kbps) 142 * 4500 * 64 QoS matrix 142 users (Planetlab nodes) 4,500 real-world Web services 64 time slices, at 15min time interval 22
Experiments Evaluation Metrics MAE (Mean Absolute Error): to measure the average prediction accuracy MRE (Median Relative Error): a key metric to identify the error effect of different magnitudes of prediction values NMRE (Ninety-Percentile Relative Error) NPRE takes the 90th percentile of all the pairwise relative errors 23
Experiments Performance Comparison Compared approaches: UPCC, IPCC, UIPCC: conventional CF baselines PMF: convectional matrix factorization approach These approaches cannot perform online Matrix density: means how many historical data we use 24
Experiments Impact of data transformation Compared approaches PMF (without data transformation) AMF(? = 1, reduce to linear normalization) AMF (? can be tuned automatically ) 25
Experiments Efficiency analysis Compared approaches: UIPCC Re-train the entire model at each time slice PMF AMF: continuously and incremental updating 26
Outline Introduction QoS Prediction Problem Collaborative Filtering Adaptive Matrix Factorization Experiments Conclusion & Future Work 28
Conclusions QoS prediction for candidate services AMF: Adaptive Matrix Factorization Data transformation, online learning, and adaptive weights Online, accurate, and scalable Future work Implement our QoS prediction approach together with service adaptation mechanisms Real-world evaluation on case studies 29
Thank you! Our data & code are available at: http://wsdream.github.io/AMF 30
