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 2

Rationales

the big picture

INFRESpage 3

COORDINATED Peering ROUTING(recall)

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 11

COOPERATION INCENTIVES FOR INTEGRATED RESOURCE RESERVATION

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

INFRESpage 19

This is the end…

QUESTIONS?