Epidemic broadcast trees

被引:42
作者
Leitao, Joao [1 ]
Pereira, Jose [2 ]
Rodrigues, Luis [1 ]
机构
[1] Univ Lisbon, P-1699 Lisbon, Portugal
[2] Univ Minho, P-4719 Braga, Portugal
来源
SRDS 2007: 26TH IEEE INTERNATIONAL SYMPOSIUM ON RELIABLE DISTRIBUTED SYSTEMS, PROCEEDINGS | 2007年
关键词
D O I
10.1109/SRDS.2007.27
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
There is an inherent trade-off between epidemic and deterministic tree-based broadcast primitives. Tree-based approaches have a small message complexity in steady-state but are very fragile in the presence of faults. Gossip, or epidemic, protocols have a higher message complexity but also offer much higher resilience. This paper proposes an integrated broadcast scheme that combines both approaches. We use a low cost scheme to build and maintain broadcast trees embedded on a gossip-based overlay. The protocol sends the message payload preferably via tree branches but uses the remaining links of the gossip overlay for fast recovery and expedite tree healing. Experimental evaluation presented in the paper shows that our new strategy has a low overhead and that is able to support large number of faults while maintaining a high reliability.
引用
收藏
页码:301 / +
页数:2
相关论文
共 26 条
[1]  
[Anonymous], 2001, UCBCSD011141
[2]  
BADISHI G, 2004, P INT C DEP SYST NET, P201
[3]  
BIRMAN K, 1999, ACM T COMPUTER SYSTE, V17
[4]  
Carvalho N., 2007, P INT C DEP SYST NET
[5]   Scribe: A large-scale and decentralized application-level multicast infrastructure [J].
Castro, M ;
Druschel, P ;
Kermarrec, AM ;
Rowstron, AIT .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2002, 20 (08) :1489-1499
[6]   A case for end system multicast [J].
Chu, YH ;
Rao, SG ;
Seshan, S ;
Zhang, H .
IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2002, 20 (08) :1456-1471
[7]   PlanetLab: An overlay testbed for broad-coverage services [J].
Chun, B ;
Culler, D ;
Roscoe, T ;
Bavier, A ;
Peterson, L ;
Wawrzoniak, M ;
Bowman, M .
ACM SIGCOMM COMPUTER COMMUNICATION REVIEW, 2003, 33 (03) :3-12
[8]   MULTICAST ROUTING IN DATAGRAM INTERNETWORKS AND EXTENDED LANS [J].
DEERING, SE ;
CHERITON, DR .
ACM TRANSACTIONS ON COMPUTER SYSTEMS, 1990, 8 (02) :85-110
[9]  
DESHPANDE M, 2006, ICDCS 06, P45
[10]   Deployment issues for the IP multicast service and architecture [J].
Diot, C ;
Levine, BN ;
Lyles, B ;
Kassem, H ;
Balensiefen, D .
IEEE NETWORK, 2000, 14 (01) :78-88