Internet multicast routing: algorithms, mechanisms and systems

互联网组播路由：算法、机制和系统

• 批准号: 327316-2009
• 负责人: Li, Zongpeng
• 金额: $ 2.19万
• 依托单位: University of Calgary
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2010
• 资助国家: 加拿大
• 起止时间: 2010-01-01 至 2011-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=457873
• 关键词: Internet; multicast; routing; algorithms; mechanisms

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.

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