Design DiffServ multicast with selfish agents

WeiZhao Wang*, Xiang-Yang Li, Zheng Sun

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

Abstract

Differentiated service (DiffServ) is a mechanism to provide the Quality of Service (QoS) with a certain performance guarantee. In this paper, we study how to design DiffServ multicast when the participants (i.e., relay links) are selfish. We assume that each link ei is associated with a cost coefficient ai such that the cost of ei to provide a multicast service with bandwidth demand x is ai · x. We first show that a previous approximation algorithm does not directly induce a truthful mechanism. We then give a new polynomial time 8-approximation algorithm to construct a DiffServ multicast tree. Based on this tree, we design a truthful mechanism for DiffServ multicast, i.e., we give a polynomial-time computable payment scheme to compensate all chosen relay links such that each link ei maximizes its profit when it reports its privately cost coefficient ai truthfully.

Original languageEnglish
Title of host publicationInternational Conference on Algorithmic Applications in Management
Subtitle of host publicationAAIM 2005: Algorithmic Applications in Management
EditorsNimrod Megiddo, Yinfeng Xu, Binhai Zhu
Place of PublicationBerlin
PublisherSpringer
Pages214-223
Number of pages10
Edition1st
ISBN (Electronic)9783540324409
ISBN (Print)9783540262244
DOIs
Publication statusPublished - 22 Jun 2005
Externally publishedYes
EventFirst International Conference on Algorithmic Applications in Management, AAIM 2005 - Xi'an, China
Duration: 22 Jun 200525 Jun 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume3521
ISSN (Print)0302-9743

Conference

ConferenceFirst International Conference on Algorithmic Applications in Management, AAIM 2005
Country/TerritoryChina
CityXi'an
Period22/06/0525/06/05

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Algorithm mechanism design
  • Approximation algorithms
  • DiffServ
  • Multicast
  • Selfish agents

Fingerprint

Dive into the research topics of 'Design DiffServ multicast with selfish agents'. Together they form a unique fingerprint.

Cite this