Internet multicast routing: algorithms, mechanisms and systems

过去十年，互联网应用激增。以流量衡量，其中最重要的类别是数据传播，占当今互联网数据流量的70%以上。这些应用包括软件补丁的分发、电影文件的点对点传输、存储或实时媒体的流传输、视频会议和在线群体游戏。它们都有一个共同的特性，即数字信息，通常是大量的，由多个用户请求并通过互联网提供给多个用户。这种应用在网络社区中被建模为多播。大量的研究工作致力于了解信息组播的底层结构，建立数学模型，并设计有效的算法，优化其性能。迄今为止，大多数组播算法假设一个合作的网络环境，诚实，合作和利他的代理。然而，这种假设在实践中并不总是安全的;当它们不安全时，网络性能可能会急剧恶化。我们研究如何新的组播算法可以结合经济措施，在互联网上执行自私的代理所需的行为，通过共同调查信息编码，数据流路由，自私的代理控制。网络编码的最新发展将被纳入一个顺从的多播路由问题的算法结构。最佳路由算法模型，然后将设计，既减少自私的用户共享的总成本，并提供一个具体的基础，成本分摊计划可能会发展。激励工程机制的非合作博弈设计将进行研究，以确保解决方案是稳定的，即使在网络中的代理价值自己的效用超过整体福祉的互联网。这项研究计划是最早的尝试之一，在优化数据传播与自私的行为在不同的互联网组件明确解决，对最终的可靠性，鲁棒性和整个互联网的效率的目标作出贡献。

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.