Internet multicast routing: algorithms, mechanisms and systems

点击翻译按钮获取中文摘要

The past decade has witnessed the proliferation of Internet applications. The most significant category of them, when measured in traffic volume, is data dissemination, accounting for over 70% of today's Internet data flows. These include applications such as the distribution of software patches, peer-to-peer transmission of movie files, the streaming of stored or live media, video conferencing and online group gaming. They share the common property that digital information, often in large volume, is requested by and delivered across the Internet to multiple users. Such applications are modelled as multicast in the networking community. Substantial research effort has been devoted to understanding the underlying structure of information multicast, creating mathematical models for it, and designing effective algorithms that optimize its performance. To date, most multicast algorithms assume a cooperative network environment with honest, cooperative and altruistic agents. However, such assumptions are not always safe in practice; and when they are not, the network performance may deteriorate dramatically. We study how new multicast algorithms can be combined with economic measures to enforce desired behaviours on selfish agents in the Internet, by jointly investigating information coding, data flow routing, and selfish agent control. Latest developments on network coding will be incorporated for an amenable algorithmic structure of the multicast routing problem. Optimal routing algorithm models will then be designed, both to reduce the total cost shared by selfish users, and to provide a concrete ground in which cost sharing schemes may be developed. Incentive engineering mechanisms for noncooperative game design will be studied, to ensure the solution is stable even if agents in the network value their own utilities more than the overall well-being of the Internet. This research program represents one of the earliest attempts in optimizing data dissemination with selfish behaviours in different components of the Internet explicitly addressed, with a goal of contributing towards the ultimate reliability, robustness and efficiency of the entire Internet.