Giochi cooperativi per incentivare la collaborazione tra operatori Internet per l’offerta di nuovi...
-
date post
20-Dec-2015 -
Category
Documents
-
view
215 -
download
0
Transcript of Giochi cooperativi per incentivare la collaborazione tra operatori Internet per l’offerta di nuovi...
Giochi cooperativi per incentivare la collaborazione tra operatori Internet per l’offerta di nuovi servizi a valore aggiunto
Stefano Seccia
in collaborazione con J.-L. Rougiera, A. Pattavinab, M. Mycekc , M. Pioroc , A. Tomaszewskic a Telecom ParisTech, France; b Politecnico di Milano, Italy; c Warsaw University of Technology, Poland
Corso di Teoria dei Giochi, ApplicazioniCollegio Borromeo, Università di Pavia, 29-30 Marzo 2010, Pavia
INFRESpage 4
Current inter-domain routing current practice across top-tier interconnections
Current BGP routing in the Internet core• Routing decisions based on unilateral costs• Lack of routing coordination, especially on peering links• Routing on peering links is increasingly unstable
- High risk of congestions route deviations
- OBJECTIVE: control the coupling between IGP and BGP routing
ISPregional
ISPregional
ISPregional
ISPregional
ISPregional
ISPregional
ISPnational
ISPnational
ISPnational
ISPnational
ISPinternational
ISPinternational
Change of colour = change of top-50 carrier border (10 min sampling)
INFRESpage 5
Coordinated inter-provider BGP routing a game-theoretic approach
ClubMED: Coordinated Multi-Exit Discriminator game• selfish game + dummy game + congestion game
- Is a potential game: Nash equilibrium minimum of the potential function
• IGP cost variations potential min. threshold enlargement of the Nash set• Coordination policies to select efficient multipath equilibrium sets
Tp
INFRES
6
Toward an extended peering framework
AS II
MED=5
c1II
c3II
AS I
c2Ic1
I
Composite MEDA = c1,3II , c1
I
l1 l2MEDA = c1
I MEDA = c2I
Rb
Ra
R1I
R2I
Community AC
om
mu
nity
B
AS III
Co
mm
un
ity C
l3
c3III
c2III
Rc
R1II
R3II R3
III
R2III
c1,2I
cIII,III c2,3
III
•Each peer sees the extended peering frontier as a unique frontier such as for the classical peering
•Routing decision: where to route the egress aggregate flow from its community toward the other communities of the other peers•The receiving peer deaggregates the flow: one toward its destination, one transiting toward another peer folllowing BGP
•Gd is now characterized by ingress costs and transit costs
page 6
INFRES
7
An extended peering game example
4
1
l1 l2
A
B Cl3 8
15
2
3
AS I
AS II AS III
4 3
7
1
14 3
3
123
9
21
page 7
INFRESpage 8
COOPERATIVE CONNECTION-ORIENTED ROUTING
AS II
MED=5
c1II
c3II
AS I
c2Ic1
I
Composite MEDA = c1,3II , c1
I
l1 l2MEDA = c1
I MEDA = c2I
Rb
Ra
R1I
R2I
Community A
Com
mun
ity B
AS III
Com
mun
ity C
l3
c3III
c2III
Rc
R1II
R3II R3
III
R2III
c1,2I
cIII,III c2,3
III
INFRESpage 9
Cooperative provider alliances architecture and protocol extensions
Inter-provider MPLS/G-MPLS provisioning• Definition of the functional architecture• An end-to-end network service as result of service elements composition
INFRESpage 10
Cooperative provider alliances AS-level routing
Proposition of an AS-level source routing algorithm• Requirements: 1. Policy routing 2. Directional metrics
3. Pre-computation 4. Multipoint routing 5. Route diversity
INFRESpage 12
How to incent provider cooperation? a Shapley value perspective
Modeling of cross-provider resource optimization• Application of cooperative game theory to motivate it
- Shapley value: strategic weight of the importance of each player in each possible (sub)coalition
• As income distribution incentive for cross-provider added-value services
- Accounting for how much each provider has reserved resources for other providers’ services
The Shapley value can be used to assign the payoff (income) of a player (provider) as function of its marginal contribution to the coalition. It is calculated as follows:
1. consider all the possible permutations of the providers
2. for each per mutation and each provider, calculate the marginal contribution that the provider grants if it joins the coalition formed by the predecessor providers
3. for each provider, calculate the average of its marginal contributions on all the permutations.
INFRESpage 13
Static reservation in Provider Alliances a Shapley value computation example
Shapley value computation• Starting with per-destination link reservation levels
- How much each provider in each ordered subcoalition can guarantee? What is itsmarginal contribution in terms of bw reservation?
- The weighted average is the SV
p1 = 0.5, p2 = 0.25, p3 = 0.25
INFRESpage 14
Static reservation in Provider Alliances a Shapley value perspective
Modeling of cross-provider resource optimization• Abstract representation of reservation levels• From router link level toward AS-level
INFRESpage 15
Static reservation in Provider Alliances a Shapley value perspective
Modeling of cross-provider resource optimization• Application of cooperative game theory to motivate it
- Shapley value: strategic weight of the importance of each player in each possible (sub)coalition
• As income distribution incentive for cross-provider added-value services
- Accounting for how much each provider has reserved resources for other providers’ services
i = injected t = terminated tr = transitPer inter-AS link and per-flow bandwidth reservation levels
INFRESpage 16
Static reservation in Provider Alliances Shapley value properties
Shapley value properties contextualized
• Symmetry
- If a provider reserve as much bandwidth as another provider for a flow, both should get the same amount
• Efficiency
- All the revenues related to a service are shared among the providers that reserved the resources for that service
• Null player
- If a provider reserve no bandwidth for a tunnel service, it will get zero
• Anonymity
- The name of the provider does not affect the value imputation
• Additivity
- The combination of more games (more tunnels) result in the sum of the single Shapley values
INFRESpage 17
Static reservation in Provider Alliances a Shapley value-based revenue distribution
Fair multi-provider schemes for cost/revenue sharing• Extension for all per-destination flows
INFRESpage 18
Related publications S. Secci, J.-L. Rougier, A. Pattavina, M. Mycek, M. Pioro, A. Tomaszewski, "
Connection-oriented Service Management in Provider Alliances: a Shapley Value Perspective", submitted to Euro-NF 5th Int. Workshop on Traffic Management and Traffic Engineering for the Future Internet, 7-8 Dec. 2009, Paris, France.
M. Mycek, S. Secci, M. Pioro, J.-L. Rougier, A. Tomaszewski, A. Pattavina, "Cooperative Multi-Provider Routing Optimization and Income Distribution", in Proc. of 2009 7th Int. Workshop on the Design of Reliable Communication Networks (DRCN 2009), 25-28 Oct. 2009, Washington, USA.
Interesting overview of Shapley value applications S. Moretti, F. Patrone, Transversality of the Shapley value, Top, 16, no. 1, 1-41,
July 2008. Technology framework paper
R. Douville, J.-L. Le Roux, J.-L. Rougier, S. Secci, "A Service Plane over the PCE Architecture for Automatic Multi-Domain Connection-Oriented Services", IEEE Communications Magazine, Vol. 46, No. 6, June 2008.
PhD dissertation Stefano Secci, Multi-provider Service and Transport Architectures, Politecnico di
Milano and Télécom ParisTech - ENST, Dec. 2009