ITR: Analysis of Internet Algorithms: Optimization, Game Theory and Competitive Analysis

ITR：互联网算法分析：优化、博弈论和竞争分析

• 批准号: 0081698
• 负责人: Richard Karp
• 金额: $ 49.98万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0081698&HistoricalAwards=false
• 关键词: ITR; Analysis; Internet; Algorithms; Optimization

As the complexity of the Internet, the nature of its applications, and its socioeconomic framework evolve, new algorithmic and architectural ideas will be proposed, tested, and adopted. While the original Internet design principles will likely remain valid, the researchers believe that it is important to have in place a mathematical framework within which these design principles can be expressed and applied to the next generation of Internet algorithms and architectures. Building such a framework is the ultimate goal. The mathematical tools will come from optimization, game theory and competitive analysis. The researchers shall work on the following topics.Multicast. The researchers shall seek to determine the relative efficiency, in terms of link usage, of multicast versus unicast, devise and analyze efficient methods of multicast error recovery, and determine how efficiently multicast can be simulated in the application layer by a coordinated set of unicasts.Congestion Probing. The TCP congestion control protocol controls its window size with an additive-increase and multiplicative-decrease (AIMD) algorithm. One can think of this as a probing algorithm in which the flow attempts to discover the maximum rate of traffic thatcan be send under current conditions; if a packet drop is recorded it is assumed the bandwidth rate was too high and so the window size is reduced. The researchers shall develop efficient probing algorithms and theoretical limits on the efficiency of probing under different models of Internet congestion.Cost Sharing. How are the recipients of a multicast transmission to share the network costs? The researchers assume that the information to be multicast is of a certain value to each possible recipient, but this value is private to that individual. The researchers shall investigate strategyproof cost sharing methods where each user is assured that their outcome is maximized if they truthfully reveal their value to the network. The researchers' goal is to characterize the set of protocols that are acceptable on both game-theoretic and complexity grounds.Information Dissemination. While traditional databases require transactional consistency, many repositories of information require only the much weaker notion of eventual consistency. That is, in such cases we care only whether, and how quickly, the information is disseminated, but do not require global consistency during the dissemination. The researchers shall identify message-efficient strategies for selectively propagating information so that the network will eventually converge to a fully updated state.

随着互联网的复杂性、其应用的性质以及其社会经济框架的演变，新的算法和架构想法将被提出、测试和采用。虽然最初的互联网设计原则可能仍然有效，但研究人员认为，重要的是要有一个数学框架，在这个框架内可以表达这些设计原则并将其应用于下一代互联网算法和体系结构。建立这样一个框架是最终目标。数学工具将来自最优化、博弈论和竞争分析。研究人员将在以下主题上开展工作。多播。研究人员将寻求确定多播与单播在链路使用方面的相对效率，设计和分析有效的多播错误恢复方法，并确定通过协调的一组单播在应用层模拟多播的效率。TCP拥塞控制协议采用加法增减(AIMD)算法控制其窗口大小。可以将其视为探测算法，其中流试图发现在当前条件下可以发送的业务的最大速率；如果记录了分组丢弃，则假定带宽速率太高，因此窗口大小减小。研究人员应开发有效的探测算法和不同网络拥塞模式下探测效率的理论限制。成本共享。组播传输的接收方如何分担网络成本？研究人员假设，要多播的信息对每个可能的接收者都有一定的价值，但这个值对个人是私有的。研究人员应研究无战略成本分摊方法，确保每个用户在如实向网络透露其价值的情况下，其结果最大化。研究人员的目标是确定一组在博弈论和复杂性方面都可接受的协议的特征。虽然传统数据库需要事务一致性，但许多信息存储库只需要更弱的最终一致性概念。也就是说，在这种情况下，我们只关心信息是否传播以及传播的速度有多快，而不需要在传播过程中保持全球一致性。研究人员应确定有选择地传播信息的消息效率策略，以便网络最终收敛到完全更新的状态。