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

随着互联网的复杂性、其应用的性质及其社会经济框架的发展，新的算法和架构思想将被提出、测试和采用。虽然最初的互联网设计原则可能仍然有效，但研究人员认为，重要的是要有一个合适的数学框架，在这个框架中，这些设计原则可以表达出来，并应用于下一代互联网算法和架构。构建这样一个框架是最终目标。数学工具将来自优化、博弈论和竞争分析。研究人员将研究以下主题：组播。研究人员应寻求确定组播与单播在链路使用方面的相对效率，设计和分析组播错误恢复的有效方法，并确定如何有效地在应用层通过一组协调的单播来模拟组播。拥堵探测。TCP拥塞控制协议通过AIMD （additive-increase and multiply - reduction）算法控制其窗口大小。可以把它看作是一种探测算法，其中流试图发现在当前条件下可以发送的最大流量；如果记录了丢包，则假定带宽速率过高，因此减小了窗口大小。研究人员需要开发有效的探测算法，并对不同网络拥塞模型下的探测效率进行理论限制。成本分摊。多播传输的接收方如何分担网络开销？研究人员假设要多播的信息对每个可能的接收者都有一定的值，但这个值对该个体是私有的。研究人员应该研究策略证明的成本分摊方法，在这种方法中，每个用户都确信，如果他们真实地向网络展示自己的价值，他们的结果就会最大化。研究人员的目标是描述一组在博弈论和复杂性基础上都可以接受的协议。信息传播。虽然传统数据库需要事务一致性，但许多信息存储库只需要较弱的最终一致性概念。也就是说，在这种情况下，我们只关心信息是否传播，以及传播速度有多快，而不要求传播过程中的全球一致性。研究人员应找出讯息效率策略，选择性地传播资讯，使网路最终收敛到完全更新的状态。

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.