Internet multicast routing: algorithms, mechanisms and systems

过去的十年见证了互联网应用的激增。以流量衡量，其中最重要的一类是数据传播，占当今互联网数据流的70%以上。这些应用包括软件补丁的分发、电影文件的点对点传输、存储或直播媒体的流媒体、视频会议和在线群组游戏等。它们有一个共同的属性，即数字信息（通常是大量的）由多个用户请求并通过Internet传递给多个用户。这种应用在网络社区中被建模为多播。大量的研究工作致力于理解信息多播的底层结构，为其创建数学模型，并设计有效的算法来优化其性能。迄今为止，大多数组播算法都假设一个具有诚实、合作和利他行为主体的合作网络环境。然而，这样的假设在实践中并不总是安全的；如果不是这样，网络性能可能会急剧下降。我们通过联合研究信息编码、数据流路由和自私代理控制，研究了新的组播算法如何与经济措施相结合，以强制Internet上的自私代理执行期望的行为。本文将结合网络编码的最新发展，为组播路由问题提供一个可适应的算法结构。然后将设计最优路由算法模型，以减少自私用户共享的总成本，并为开发成本共享方案提供具体依据。非合作博弈设计的激励工程机制将被研究，以确保解决方案是稳定的，即使网络中的代理更看重他们自己的效用而不是互联网的整体福祉。该研究项目是在优化数据传播方面最早的尝试之一，明确解决了互联网不同组件中的自私行为，其目标是为整个互联网的最终可靠性、鲁棒性和效率做出贡献。

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.