Design and Analysis of Internet Algorithms: Routing, Filtering, Overlay Design and Influence of Heterogeneity

这项研究涉及用于在互联网和其他分布式通信网络(如无线网络)中高效传输数据的协议。研究的重点是路由、拥塞控制和异构性。路由涉及消息的路由选择以及由存储在路由器中的路由表管理的本地决策对这些路由的实施。这些表格的大小必须很小，这是一个基本的限制。拥塞控制通过选择性地丢弃来自接收的带宽超过其公平份额的流的数据包来努力减少拥塞。异构性的问题是分布式系统的容量在处理器之间平均分配还是不均匀分配更好。地理路由为每个处理器分配坐标，将其放置在公制空间中。该研究调查了地理布线方案的正确性和效率。地理路由的特殊情况包括贪婪路由和信标路由，在贪婪路由中，选择每一跳以最小化到目的地的距离；在信标路由中，主机的每个坐标给出从主机到所选信标节点的最小跳数。这项研究探索了边界网关协议中出现的那种类型的路由约束所造成的效率损失。探讨了覆盖节点提高路由效率的能力。研究了紧凑多播路由表的构造问题。给出了识别高速率流并优先丢弃它们的有效方法。最后，证据表明，当它们的容量在处理器之间均匀分布时，系统的健壮性更强。

This research concerns protocols used for the efficient transmission of data in the Internet and other distributed communication networks, such as wireless networks. The research focuses on routing, congestion control and heterogeneity. Routing concern the choice of routes for messages and the enforcement of those routes by local decisions governed by routing tables stored at the routers. It is a fundamental constraintthat the sizes of these tables must be small. Congestion control strives to reduce congestion by selectively dropping packets from flows that are receiving more than their fair share of bandwidth. The issue of heterogeneity is whether it is better to have the capacity of a distributed system divided evenly or unevenly among its processors.Geographic routing assigns coordinates to each processor, placing it in a metric space. The research investigates the correctness and efficiency of geographic routing schemes. Special cases of geographic routing include greedy routing, in which each hop is chosen to minimize distance to the destination, and beacon routing, in which each coordinate of a host gives the minimum number of hops from the host to a selected beacon node. The research explores the loss of efficiency imposed by routing constraints of the type arising in the Border Gateway Protocol. The ability of overlay nodes to improve routing efficiency is explored. The construction of compact multicast routing tables is investigated. Efficient methods are given for identifying high-rate flows and dropping their packets preferentially.Finally, evidence is provided that systems are more robust when their capacity is distributed heterogeneously among the processors.