Network Coordinate-based Web Service Positioning Framework for Response Time Prediction
undefined
WSP
: A Network Coordinate based
W
eb
S
ervice
P
ositioning Framework
for Response Time Prediction
Jieming Zhu
, Yu Kang, Zibin Zheng and Michael R. Lyu
The Chinese University of Hong Kong
ICWS 2012, Honolulu
Outline
M
o
t
i
v
a
t
i
o
n
R
e
l
a
t
e
d
W
o
r
k
W
S
P
F
r
a
m
e
w
o
r
k
W
S
P
-
b
a
s
e
d
R
e
s
p
o
n
s
e
T
i
m
e
P
r
e
d
i
c
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
2
Motivation
W
e
b
s
e
r
v
i
c
e
s
:
c
o
m
p
u
t
a
t
i
o
n
a
l
c
o
m
p
o
n
e
n
t
s
t
o
b
u
i
l
d
s
e
r
v
i
c
e
-
o
r
i
e
n
t
e
d
d
i
s
t
r
i
b
u
t
e
d
s
y
s
t
e
m
s
3
Web Services
Components
Motivation
W
e
b
s
e
r
v
i
c
e
c
o
m
p
o
s
i
t
i
o
n
:
b
u
i
l
d
s
e
r
v
i
c
e
-
o
r
i
e
n
t
e
d
s
y
s
t
e
m
s
u
s
i
n
g
e
x
i
s
t
i
n
g
W
e
b
s
e
r
v
i
c
e
c
o
m
p
o
n
e
n
t
s
4
How to select
Web services?
Motivation
Q
u
a
l
i
t
y
-
o
f
-
S
e
r
v
i
c
e
(
Q
o
S
)
Response time, throughput, failure probability
Q
o
S
e
v
a
l
u
a
t
i
o
n
o
f
W
e
b
s
e
r
v
i
c
e
s
Service Level Agreement (SLA):
static QoS
Dynamic QoS:
Network conditions
Time-varying server workload
Service users at different locations
H
o
w
t
o
e
v
a
l
u
a
t
e
t
h
e
Q
o
S
f
r
o
m
t
h
e
u
s
e
r
s
’
p
e
r
s
p
e
c
t
i
v
e
?
5
Motivation
A
c
t
i
v
e
Q
o
S
m
e
a
s
u
r
e
m
e
n
t
i
s
i
n
f
e
a
s
i
b
l
e
The large number of Web service candidates and replicas
Time consuming and resource consuming
Q
o
S
p
r
e
d
i
c
t
i
o
n
:
a
n
u
r
g
e
n
t
t
a
s
k
6
Predict the
unknown
values
Outline
M
o
t
i
v
a
t
i
o
n
R
e
l
a
t
e
d
W
o
r
k
W
S
P
F
r
a
m
e
w
o
r
k
Offline Coordinates Updating
Online Web Service Selection
W
S
P
-
b
a
s
e
d
R
e
s
p
o
n
s
e
T
i
m
e
P
r
e
d
i
c
t
i
o
n
Landmark Coordinate Computation
Web Service Coordinate Computation
Service User Coordinate Computation
Response Time Prediction
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
7
Related Work
C
o
l
l
a
b
o
r
a
t
i
v
e
f
i
l
t
e
r
i
n
g
(
C
F
)
b
a
s
e
d
Q
o
S
p
r
e
d
i
c
t
i
o
n
a
p
p
r
o
a
c
h
e
s
UPCC [Shao et al. 2007]
IPCC, UIPCC [Zheng et al. 2009]
Variants:
RegionKNN [Chen et al. 2010], PHCF [Jiang et al.
2011]
N
e
t
w
o
r
k
c
o
o
r
d
i
n
a
t
e
(
N
C
)
b
a
s
e
d
n
e
t
w
o
r
k
d
i
s
t
a
n
c
e
p
r
e
d
i
c
t
i
o
n
a
p
p
r
o
a
c
h
e
s
Triangulated Heuristic, GNP [T. S. E. Ng et al. 2002]
IDES [Mao et al. 2006]
NC Survey [Donnet et al. 2010]
8
Collaborative Filtering
C
o
l
l
a
b
o
r
a
t
i
v
e
f
i
l
t
e
r
i
n
g
:
u
s
i
n
g
h
i
s
t
o
r
i
c
a
l
Q
o
S
d
a
t
a
t
o
p
r
e
d
i
c
t
t
h
e
u
n
k
n
o
w
n
v
a
l
u
e
s
IPCC:
UPCC:
UIPCC:
Convex combination
PCC similarity
Mean of u
QoS of u
a
Mean of i
Similar neighbors
Mean of i
k
9
Similarity between u
a
and u
Network Coordinate
N
e
t
w
o
r
k
c
o
o
r
d
i
n
a
t
e
:
t
a
k
e
s
o
m
e
m
e
a
s
u
r
e
m
e
n
t
s
t
o
p
r
e
d
i
c
t
t
h
e
m
a
j
o
r
u
n
k
n
o
w
n
v
a
l
u
e
s
(
e
.
g
.
,
R
T
T
)
GNP:
embed the Internet hosts into a high dimensional
Euclidean space
A Prototype of Network Coordinate System
Landmark Operation:
Ordinary Host Operation:
Sum of error
10
11
Limitations
C
F
-
b
a
s
e
d
Q
o
S
p
r
e
d
i
c
t
i
o
n
a
p
p
r
o
a
c
h
e
s
Suffer from the
sparsity
of historical QoS data
Cold start problem:
Incapable for handling new user
without available historical data
Not applicable for mobile users
N
C
-
b
a
s
e
d
a
p
p
r
o
a
c
h
e
s
Traditional approaches in P2P scenario
Take no advantage of useful historical information
WSP: Web Service Positioning
C
o
l
l
a
b
o
r
a
t
i
v
e
f
i
l
t
e
r
i
n
g
(
C
F
)
e
m
p
l
o
y
s
t
h
e
a
v
a
i
l
a
b
l
e
h
i
s
t
o
r
i
c
a
l
Q
o
S
d
a
t
a
N
e
t
w
o
r
k
c
o
o
r
d
i
n
a
t
e
(
N
C
)
e
m
p
l
o
y
s
t
h
e
r
e
f
e
r
e
n
c
e
i
n
f
o
r
m
a
t
i
o
n
o
f
l
a
n
d
m
a
r
k
s
W
S
P
:
N
C
-
b
a
s
e
d
W
e
b
S
e
r
v
i
c
e
P
o
s
i
t
i
o
n
i
n
g
C
ombine the advantages of CF and NC to achieve
better performance with more available information
12
Sparsity problem
P2P scenario,
No historical Info
involved
Better performance in
client-server scenario
Outline
M
o
t
i
v
a
t
i
o
n
R
e
l
a
t
e
d
W
o
r
k
W
S
P
F
r
a
m
e
w
o
r
k
Offline Coordinates Updating
Online Web Service Selection
W
S
P
-
b
a
s
e
d
R
e
s
p
o
n
s
e
T
i
m
e
P
r
e
d
i
c
t
i
o
n
Landmark Coordinate Computation
Web Service Coordinate Computation
Service User Coordinate Computation
Response Time Prediction
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
13
WSP Framework
WSP Framework for response time prediction
Offline Coordinates Updating
Online Response Time Prediction
14
WSP Framework for response time prediction
Offline Coordinates Updating
a.
The deployed
landmarks measure the
network distances
between each other
b.
Embed the landmarks
into an high-dimensional
Euclidean space
c.
Update the landmark
coordinates periodically
WSP Framework
15
WSP Framework
WSP Framework for response time prediction
Offline Coordinates Updating
16
d.
The landmarks
monitor the available
Web services with
periodical invocations
e.
Obtain the coordinates
of Web services by taking
the landmarks as
references
f.
Update the coordinates
of Web services
periodically
WSP Framework
WSP Framework for response time prediction
Offline Coordinates Updating
Online Response Time Prediction
17
a.
When a service user
requests for a Web
service invocation, it first
measures the network
distances to the
landmarks
b.
The results are sent to
a central node to
compute the user’s
coordinate, combining
with the historical data
WSP Framework
WSP Framework for response time prediction
Offline Coordinates Updating
Online Response Time Prediction
18
c.
Predict the response
times by computing the
corresponding Euclidean
distances
d.
Optimal Web service
is selected for the user
e.
The user invokes the
selected Web service for
application
f.
Update the response
time to the database
Outline
M
o
t
i
v
a
t
i
o
n
R
e
l
a
t
e
d
W
o
r
k
W
S
P
F
r
a
m
e
w
o
r
k
Offline Coordinates Updating
Online Web Service Selection
W
S
P
-
b
a
s
e
d
R
e
s
p
o
n
s
e
T
i
m
e
P
r
e
d
i
c
t
i
o
n
Landmark Coordinate Computation
Web Service Coordinate Computation
Service User Coordinate Computation
Response Time Prediction
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
19
Response Time Prediction
Algorithm Overview
20
Offline Coordinates
Updating
Online Web Service
Selection
Response Time Prediction
Landmark Coordinate Computation
21
Distance Matrix
between n landmarks
where
Squared sum of
prediction error
Regularization term
Euclidean distance
Min
Simplex Downhill Algorithm
: to solve the multi-dimensional global
minimization problem
Landmarks
Response Time Prediction
Web Service Coordinate Computation
22
Distance matrix between
n
landmarks and
w
Web
service hosts
Min
Squared Sum
of Error
Regularization term
Web service host
The coordinates of landmarks and Web services are updated
periodically!
Service User Coordinate Computation
Min
Service user
Web service
hosts
Historical data
Reference information
of landmarks
Available historical
data constraints
Regularization term
Response Time Prediction
23
WSP combines the advantages of collaborative filtering based
approaches and network coordinate based approaches.
Response Time Prediction & WS Selection
Response time prediction
:
Web service selection
:
Optimal Web service selection according to the response time
prediction
Selection approach: out of the scope of this work
Response Time Prediction
24
The set of Web
services with unknown
response time data
The coordinate
of service user
u
The coordinate
of Web service
s
i
Outline
M
o
t
i
v
a
t
i
o
n
R
e
l
a
t
e
d
W
o
r
k
W
S
P
F
r
a
m
e
w
o
r
k
Offline Coordinates Updating
Online Web Service Selection
W
S
P
-
b
a
s
e
d
R
e
s
p
o
n
s
e
T
i
m
e
P
r
e
d
i
c
t
i
o
n
Landmark Coordinate Computation
Web Service Coordinate Computation
Service User Coordinate Computation
Response Time Prediction
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
25
D
a
t
a
C
o
l
l
e
c
t
i
o
n
Response times between 200 users (PlanetLab nodes) and
1,597 Web services
The network distances between the 200 distributed nodes
E
v
a
l
u
a
t
i
o
n
M
e
t
r
i
c
s
MAE:
to measure the average prediction accuracy
MRE
(Median Relative Error):
to identify the error effect of
different magnitudes of prediction values
Experiments
26
50% of the relative errors are below MRE
P
e
r
f
o
r
m
a
n
c
e
C
o
m
p
a
r
i
s
o
n
Parameters setting: 16 Landmarks, 184 users, 1,597 Web
services, coordinate dimension m=10, regularization
coefficient =0.1.
Matrix density: means how many historical data we use
Experiments
27
WSP outperforms the others!
Less sensitive to data sparsity!
Take no advantage of historical data
T
h
e
I
m
p
a
c
t
o
f
P
a
r
a
m
e
t
e
r
s
Experiments
28
The impact of matrix
density:
WSP is less sensitive to the
data sparsity.
The impact of
number of landmarks:
Optimal landmarks can be
selected to achieve best
performance.
W
S
P
:
W
e
b
s
e
r
v
i
c
e
p
o
s
i
t
i
o
n
i
n
g
f
r
a
m
e
w
o
r
k
f
o
r
r
e
s
p
o
n
s
e
t
i
m
e
p
r
e
d
i
c
t
i
o
n
The
first work
to apply network coordinate technique to
response time prediction for WS
Outperforms the other existing approaches, especially
when the historical data is sparse.
Applicable for users without available historical data, such
as
mobile users
.
F
u
t
u
r
e
W
o
r
k
Extend the current work to prediction of
more QoS
properties
Detect and eliminate the anomalies to improve the
accuracy
Conclusions & Future Work
29
Thank you!
Q & A
30
Jieming Zhu
Email: jmzhu@cse.cuhk.edu.hk
This paper presents the WSP framework, a network coordinate-based approach for predicting response times in web services. It explores the motivation behind web service composition, quality-of-service evaluation, and the challenges of QoS prediction. The WSP framework enables the selection of web services based on dynamic QoS measures, tackling the issues associated with active QoS measurement. The study discusses related collaborative filtering and network distance prediction approaches for QoS prediction in web services.
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
WSP: A Network Coordinate based Web Service Positioning Framework for Response Time Prediction Jieming Zhu, Yu Kang, Zibin Zheng and Michael R. Lyu The Chinese University of Hong Kong ICWS 2012, Honolulu
Outline Motivation Related Work WSP Framework WSP-based Response Time Prediction Experiments Conclusions & Future Work 2
Motivation Web services: computational components to build service-oriented distributed systems Web Services Components 3
Motivation Web service composition: build service- oriented systems using existing Web service components How to select Web services? 4
Motivation Quality-of-Service (QoS) Response time, throughput, failure probability QoS evaluation of Web services Service Level Agreement (SLA): static QoS Dynamic QoS: Network conditions Time-varying server workload Service users at different locations How to evaluate the QoS from the users perspective? 5
Motivation Active QoS measurement is infeasible The large number of Web service candidates and replicas Time consuming and resource consuming QoS prediction: an urgent task Predict the unknown values 6
Outline Motivation Related Work WSP Framework Offline Coordinates Updating Online Web Service Selection WSP-based Response Time Prediction Landmark Coordinate Computation Web Service Coordinate Computation Service User Coordinate Computation Response Time Prediction Experiments Conclusions & Future Work 7
Related Work Collaborative filtering (CF) based QoS prediction approaches UPCC [Shao et al. 2007] IPCC, UIPCC [Zheng et al. 2009] Variants: RegionKNN [Chen et al. 2010], PHCF [Jiang et al. 2011] Network coordinate (NC) based network distance prediction approaches Triangulated Heuristic, GNP [T. S. E. Ng et al. 2002] IDES [Mao et al. 2006] NC Survey [Donnet et al. 2010] 8
Collaborative Filtering Collaborative filtering: using historical QoS data to predict the unknown values QoS of ua PCC similarity Mean of u UPCC: IPCC: Mean of ik Mean of i Similar neighbors UIPCC: Convex combination Similarity between ua and u 9
Network Coordinate Network coordinate: take some measurements to predict the major unknown values (e.g., RTT) GNP: embed the Internet hosts into a high dimensional Euclidean space Landmark Operation: Sum of error Ordinary Host Operation: A Prototype of Network Coordinate System B(12,40) y 78.6ms 76.5ms C(90,30) B 77ms 36.4ms C 78ms 35ms Euclidean 26.9ms 25ms 94ms 91.5ms Embedding A D 76ms Internet 78ms D(80,5) x A(2,5) 10
Limitations CF-based QoS prediction approaches Suffer from the sparsity of historical QoS data Cold start problem: Incapable for handling new user without available historical data Not applicable for mobile users NC-based approaches Traditional approaches in P2P scenario Take no advantage of useful historical information 11
WSP: Web Service Positioning Collaborative filtering (CF) employs the available historical QoS data Network coordinate (NC) employs the reference information of landmarks WSP: NC-based Web Service Positioning Combine the advantages of CF and NC to achieve better performance with more available information CF Sparsity problem Better performance in client-server scenario WSP P2P scenario, No historical Info involved NC 12
Outline Motivation Related Work WSP Framework Offline Coordinates Updating Online Web Service Selection WSP-based Response Time Prediction Landmark Coordinate Computation Web Service Coordinate Computation Service User Coordinate Computation Response Time Prediction Experiments Conclusions & Future Work 13
WSP Framework WSP Framework for response time prediction Offline Coordinates Updating Online Response Time Prediction Web Services Manager optimal invocation Web Services Service Users measure monitoring update y WS Selection RTs Data L2 L1 x L4 Coordinates Computation RT L3 Prediction Landmarks update Response Time (RT) Prediction for WS Coordinates Manager (Landmark, WS) 14
WSP Framework WSP Framework for response time prediction Offline Coordinates Updating a. The deployed landmarks measure the network distances between each other Web Services Manager optimal invocation Web Services Service Users measure monitoring update b. Embed the landmarks into an high-dimensional Euclidean space y WS Selection RTs Data L2 L1 x L4 Coordinates Computation RT L3 Prediction c. Update the landmark coordinates periodically Landmarks update Response Time (RT) Prediction for WS Coordinates Manager (Landmark, WS) 15
WSP Framework WSP Framework for response time prediction Offline Coordinates Updating d. The landmarks monitor the available Web services with periodical invocations Web Services Manager optimal invocation Web Services Service Users measure e. Obtain the coordinates of Web services by taking the landmarks as references monitoring update y WS Selection RTs Data L2 L1 x L4 Coordinates Computation RT L3 f. Update the coordinates of Web services periodically Prediction Landmarks update Response Time (RT) Prediction for WS Coordinates Manager (Landmark, WS) 16
WSP Framework WSP Framework for response time prediction Offline Coordinates Updating Online Response Time Prediction a. When a service user requests for a Web service invocation, it first measures the network distances to the landmarks Web Services Manager optimal invocation Web Services Service Users measure monitoring update y WS Selection RTs Data L2 b. The results are sent to a central node to compute the user s coordinate, combining with the historical data L1 x L4 Coordinates Computation RT L3 Prediction Landmarks update Response Time (RT) Prediction for WS Coordinates Manager (Landmark, WS) 17
WSP Framework WSP Framework for response time prediction Offline Coordinates Updating Online Response Time Prediction c. Predict the response times by computing the corresponding Euclidean distances d. Optimal Web service is selected for the user Web Services Manager optimal invocation Web Services Service Users measure monitoring update y WS Selection RTs Data e. The user invokes the selected Web service for application L2 L1 x L4 Coordinates Computation RT L3 Prediction Landmarks f. Update the response time to the database update Response Time (RT) Prediction for WS Coordinates Manager (Landmark, WS) 18
Outline Motivation Related Work WSP Framework Offline Coordinates Updating Online Web Service Selection WSP-based Response Time Prediction Landmark Coordinate Computation Web Service Coordinate Computation Service User Coordinate Computation Response Time Prediction Experiments Conclusions & Future Work 19
Response Time Prediction Algorithm Overview Landmark Coordinate Computation Offline Coordinates Updating Web Service Coordinate Computation Service User Coordinate Computation Online Web Service Selection Response Time Prediction Web Service Selection 20
Response Time Prediction Landmark Coordinate Computation Distance Matrix between n landmarks Landmarks Squared sum of prediction error Min Regularization term where Euclidean distance Simplex Downhill Algorithm: to solve the multi-dimensional global minimization problem 21
Response Time Prediction Web Service Coordinate Computation Distance matrix between n landmarks and w Web service hosts Web service host Min Squared Sum of Error Regularization term The coordinates of landmarks and Web services are updated periodically! 22
Response Time Prediction Service User Coordinate Computation Service user Web service hosts Historical data Reference information of landmarks Min Available historical data constraints Regularization term WSP combines the advantages of collaborative filtering based approaches and network coordinate based approaches. 23
Response Time Prediction Response Time Prediction & WS Selection Response time prediction: The set of Web services with unknown response time data The coordinate of service user u The coordinate of Web service si Web service selection: Optimal Web service selection according to the response time prediction Selection approach: out of the scope of this work 24
Outline Motivation Related Work WSP Framework Offline Coordinates Updating Online Web Service Selection WSP-based Response Time Prediction Landmark Coordinate Computation Web Service Coordinate Computation Service User Coordinate Computation Response Time Prediction Experiments Conclusions & Future Work 25
Experiments Data Collection Response times between 200 users (PlanetLab nodes) and 1,597 Web services The network distances between the 200 distributed nodes Evaluation Metrics MAE: to measure the average prediction accuracy MRE (Median Relative Error): to identify the error effect of different magnitudes of prediction values 50% of the relative errors are below MRE 26
Experiments Performance Comparison Parameters setting: 16 Landmarks, 184 users, 1,597 Web services, coordinate dimension m=10, regularization coefficient =0.1. Matrix density: means how many historical data we use Take no advantage of historical data WSP outperforms the others! Less sensitive to data sparsity! 27
Experiments The Impact of Parameters The impact of matrix density: WSP is less sensitive to the data sparsity. The impact of number of landmarks: Optimal landmarks can be selected to achieve best performance. 28
Conclusions & Future Work WSP: Web service positioning framework for response time prediction The first work to apply network coordinate technique to response time prediction for WS Outperforms the other existing approaches, especially when the historical data is sparse. Applicable for users without available historical data, such as mobile users. Future Work Extend the current work to prediction of more QoS properties Detect and eliminate the anomalies to improve the accuracy 29
Thank you! Q & A Jieming Zhu Email: jmzhu@cse.cuhk.edu.hk 30
