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.