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


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
Number of pages10
ISBN (Electronic)9783540324409
ISBN (Print)9783540262244
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
ISSN (Print)0302-9743


ConferenceFirst International Conference on Algorithmic Applications in Management, AAIM 2005

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

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


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

Cite this