Upload
olive
View
23
Download
0
Embed Size (px)
DESCRIPTION
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies –. Rita Girão- Silva a,c , José Craveirinha a,c , João Clímaco b,c Workshop INESC-Coimbra a b c AIORT’05 – Sep. 16, 2005. Introduction - PowerPoint PPT Presentation
Citation preview
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution StrategiesRita Girão-Silva, José Craveirinha, João Clímaco
1
A Model for MultiobjectiveRouting Optimisation in MPLS
with Two Service Classes– Resolution Strategies –
Rita Girão-Silva a,c,
José Craveirinha a,c, João Clímaco b,c
Workshop INESC-Coimbra a b c
AIORT’05 – Sep. 16, 2005
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
2
Summary1. Introduction2. Review of a multiobjective routing framework
for MPLS– Base model– Model for two classes of traffic (QoS and Best
Effort)– Traffic modelling approach
3. Resolution strategies– Search for non-dominated solutions for each
node-to-node flow– Possible heuristic / meta-heuristic to choose
adequate compromise solutions4. Other open issues and difficulties
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
3
Introduction• In MPLS networks, routing models dealing with
multiple, heterogeneous QoS requirements are needed.
• There are potential advantages in using multiobjective formulations for the routing calculation problem.
• Main features proposed in this model:– Two classes of traffic (QoS and BE);– Bi-level stochastic representation of the traffic in the
network.
• Heuristic to solve the problem
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
4
Review of a Framework for Routing Optimisation in MPLS
[Craveirinha et al, 2005]
It is a network-wide routing model of new type:1. Hierarchical multiobjective optimisation model
– First level: objective functions formulated at network level (considering the combined effect of all traffic flows)
– Second level: average performance metrics associated with different types of services
– Third level: average performance metrics associated with the µ-flows of packet streams
2. Explicit consideration of fairness objectives at the three levels of optimisation
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
5
(Review of a Framework for Routing Optimisation in MPLS)
3. It includes an explicit and ‘direct’ represen-tation of the most relevant technical-economic objectives, namely total expected revenue and packet total average delay.
4. It considers a bi-level stochastic representation of the traffic in the network.– Macro-level: traffic flows that correspond to a
stochastic representation of the connection demands in the traffic trunks associated with explicit routes
– Micro-level: stochastic representation of µ-flows of packet streams inside any given traffic flow
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
6
Base-model
Formulation of a hierarchical multiobjective routing optimisation problem (P-M3-S)
tR
Network objectives: min {-WT}
min {BMm}
Service objectives: min {Bms}, s S
min {BMs}, s S
µ-flow network objectives: min {D’T}
min {DMm}
tR
tR
tR
tR
tR
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
7
(Base-model)
• Network objectives– Total expected network revenue
S: set of service typesAs
c: total traffic carried for service sws: expected revenue per µ-flow of type s
– Maximal average blocking probability among all service types (network-level fairness objective)
BMm = max s S {Bms}
• Service objectives– Maximal blocking probability among all traffic flows
of type s (fairness objective at service level)BMs = max fs Fs {B(fs)}
Ss
scsT wAW
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
8
(Base-model)
ss Ff
sstos
ms ))B(f(fAA
1B
• Service objectives (cont.)–Average blocking probability for all traffic flows of type s (of which the set is Fs)
Aso: total traffic offered for service s
At(fs): traffic offered for traffic flow fs
B(fs): the corresponding end-to-end blocking probability
• µ-flow network objectives–Average packet delay for all types of services, weighted by the relative bandwidths
Ss
smsT
T γ'D'γ'
1D'
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
9
(Base-model)• µ-flow network objectives (cont.)
– Maximal average packet delay experienced by all types of packet streams (fairness objective at µ-flow network level)
DMm=max s S {Dms}
---------------------------------------
• This model should be envisaged as a multiobjective routing optimisation framework with a significant degree of flexibility and adaptability.
• The proposed meta-model i.e. the model underlying concepts and logical relations may be configured for other specifications of objective functions and /or constraints as long as the basic structure of the meta-model is preserved.
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
10
Model for QoS and BE service classesHierarchical optimisation problem for two service classes(P-M3-S2)
1st levelQoS network objectives: min {-WT|Q}
min {BMm|Q}2nd level
QoS service objectives: min {Bms|Q}, s SQ
min {BMs|Q}, s SQ
BE network objective: min {-WT|B}3rd level
µ-flow network objectives: min {D’T} min {DMm}
tR
tR
tR
tR
tR
tR
tR
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
11
(Model for QoS and Best Effort service classes)
• The functions WT|Q, WT|B, BMm|Q, Bms|Q, BMs|Q have the meaning described before, but with the index Q (B) indicating that their calculation is reported to traffic flows of class QoS (Best Effort) alone.
• While QoS and BE traffic flows are treated separately in terms of upper level objective functions, the interactions among all traffic flows remain represented in the model (via the teletraffic model underlying the routing optimisation model).– In fact, the link traffic model must integrate the
contributions of all the traffic flows which may use every link.
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
12
Traffic modelling approach• Traffic flows (macro level) are represented
through marked point processes of multirate Poisson type– The concept of effective bandwidth (dks) required by
traffic flows fs on link lk, is used.– This is a stochastic measure of the utilization of
network transmission resources capable of representing the variability of the rates of different traffic sources, as well as effects of statistical multiplexing in the network.
• This and other parameters are included as ‘attributes’ contained in the traffic engineering descriptors , of traffic flow fs=(vi,vj, , ) from node vi to vj.
sγ)(fη s )(fη ssγ
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
13
(Traffic modelling approach - macro level)The traffic model of a link for calculating the blocking
probabilities Bks experienced by flows fs on link lk is a multidimensional Erlang system M1+M2+...+Mn/M/Ck/0.
Bks=Ls( , ,Ck)
Ls is a function implicit in the analytical model.Its values can be calculated by adequate efficient and
robust algorithms (as the Kaufman/ Roberts algorithm or the UAA (Uniform Asymptotic Approximation) for large Ck).
=(dk1,...,dk|S|): vector of equivalent effective bandwidths
=(ρk1,..., ρk|S|): vector of reduced traffic loads offered by flows of type s to lk
kd
kd
kρ
kρ
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
14
(Traffic modelling approach - micro level)
• Traffic modelling at packet µ-flow level (micro level) uses marked point processes characterised by their intensities I’t(fs) [packet/s] and hk(fs) (mean service time in lk of a packet from µ-flows in fs). – The mean [Erl] of each of these processes defines the
potential traffic offered ρtk(fs) to lk by fs, at time period t.
– The loss and control access mechanisms are represented by a multidimensional access function for each link.
– This access function enables the calculation of reduced offered loads ρt
k*(fs) and of the fictitious equivalent total offered traffic
Ss Ff
s*k
t*k
t
ss
)(fρρ
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
15
(Traffic modelling approach - micro level)
• The average expected delay Dk(fs) experienced in lk by packets in µ-flows from fs may be estimated from a M/GI/1/∞ queue model. – A first approximation to the service time distribution
is a hyper-exponential distribution, of which the weights represent the probability of an arbitrary packet offered to lk being originated from each fs.
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
16
Resolution strategies
• The MODR-S model, originally proposed by [L. Martins et al., 2003] may be considered as a particular case of the base model P-M3-S previously reviewed.– The MODR-S was founded on the formulation of a bi-
level hierarchical multiple objective routing optimisation problem for multiservice networks.
– It is based on an underlying bi-objective shortest path algorithm including preference thresholds, for calculating alternative paths for each flow (MMRA-S).
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
17
(Resolution strategies – MODR-S)
– It uses a heuristic for synchronous path selection aiming to obtain a set of routes which is a satisfactory compromise solution for the network routing optimisation problem.
– This approach is based on the MMRA-S algorithm, that seeks to solve the auxiliary bi-objective shortest path problem in the MODR-S framework.
• Two metrics: the blocking probabilities, the implied costs.• Soft constraints in the form of required and / or accepted
values for each metric, defining preference regions in the objective function space.
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
18
(Resolution strategies – Heuristic aproach)
I. Heuristic approach – Extension of the ‘rational’ of MODR-S to address the problem P-M3-S2
• The calculation of candidate solutions for each traffic flow will be based on the resolution of an auxiliary multiobjective shortest path problem for each node-to-node flow.
• The objectives include the blocking probabilities, the implied costs and possibly the delay.– The definition and calculation of the implied costs has
to be reformulated taking into account the consideration of two different classes of service.
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
19
(Resolution strategies)• A suitable resolution approach for this auxiliary
problem has to be developed.– Optimisation of a weighted sum of the objective functions– Reference point-like method----------------------------------------------------------------------------
• The heuristic approach for solving the problem under analysis (P-M3-S2) has to be devised to generate and select adequate compromise solutions (routing plans ).– As the routing problem is formulated as a hierarchical
optimisation problem, the heuristic must include the representation of a system of preferences, which is necessary for an automatic ordering and selection of candidate solutions.
tR
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
20
(Resolution strategies – Possible heuristics for the selection of solutions)
II. Development of a heuristic based on a lexicographic optimisation method– A transformation of the initial formulation of the P-M3-
S2 according to an aggregated achievement function has to be made.
– This implies that a hierarchy of preferences within each priority level has to be defined.
III. Development of an evolutionary algorithm, where a population of solutions may be evaluated and possibly evolve into increasingly “better” solutions
A Model for Multiobjective Routing Optimisation in MPLS with Two Service Classes – Resolution Strategies R. Girão-Silva, J. Craveirinha, J. Clímaco
21
Other open issues and difficulties raised by this modelling framework
• Great complexity of the problem (NP-complete)• Interdependencies among the objective
functions• Representation of the system of preferences in
an automatic decision environment• Treatment of inaccuracy and uncertainty
associated with many parameters• Simulation environment for further testing of the
resolution approaches• Comparison with results obtained with other
methods