作者 Jennifer Rexford 普林斯顿大学
域间路由、流量工程、互联网架构方面的大牛，这个他的一个类似随笔的文章，很有意思。
俗话说，“理论上理论和实践之间没有差别，但在实践中确实存在差别。” 在网络研究中，理论与实践各有许多优秀的论文。然而，许多实际研究的论文缺乏严谨的问题定义或深思熟虑的解决方案，而许多理论研究的论文则忽略或假设掉了一些他们想要建模的系统中的关键因素。不过，偶尔会有一篇论文完美结合实践问题和恰当的理论。每当这种情况发生时，真是美不胜收。这是我最喜欢的十个例子。在某些情况下，我会提到一些综述论文，它们涵盖了整个研究领域的成果，或者引用期刊论文来展示比会议论文更为成熟的概述，而不是单独挑出某一项研究结果。（顺便说一句，我认为优秀的综述论文对学术界是非常宝贵的贡献，我希望更多人能够投入大量时间和精力来撰写这样的论文。）
这两篇论文非常清晰地展示了一个协议是（或者应该是）对某个良好定义的问题的分布式解决方案。通常情况下，理论模型是在协议实现之后才出现，带有一种忠实的逆向工程意味。或许在未来，我们可以“向前发展”，利用模型来指导我们如何设计协议。
T. G. Griffin, F. B. Shepherd 和 G. Wilfong, “The stable paths problem and interdomain routing,” IEEE/ACM Transactions on Networking, 2002 年 4 月, pp. 232–243
这篇期刊论文，以及在此之前的几篇会议论文，使我（以及很多其他人）对 BGP 产生了兴趣。该论文描述了 BGP 隐含地在解决的问题，并证明了关于域间路由系统的多个令人不安的负面结果。论文剖析了 BGP 的大量细节，提炼出了协议最重要的部分——即每个节点都有自己的路径局部排名（针对某个路径子集），并在与邻居的选择保持一致的情况下选取排名最高的路径。论文还通过一些简单的例子（如“坏设备”（Bad Gadget）、“意外”（Surprise）和“分歧”（Disagree）等巧妙的名称）来说明关键思想和反例。而且，谁会想到 BGP 和 3-SAT 问题之间还有联系？这篇论文促使近年来产生了大量关于 BGP 的理论研究——这些研究很可能不会发生，若不是有人首先做了大量艰苦的工作，创建了一个清晰、准确的协议模型。这篇论文的确不易读懂，但绝对值得投入时间。
M. Chiang, S. H. Low, A. R. Calderbank 和 J. C. Doyle, “Layering as optimization decomposition: A mathematical theory of network architectures,” Proceedings of the IEEE, 2007 年 1 月, pp. 255–312
这篇论文综述了日益增多的将协议设计与分析视作优化问题的分布式解决方案的研究成果。论文从数学上严谨地探讨了“网络架构”这一难以定义的概念——即网络中功能的定义与配置。将优化问题分解，导致一系列子问题（对应于不同的协议层）和协调这些子问题的变量（对应于各层之间的接口）。例如，早期研究表明 TCP 拥塞控制——终端在包丢失时调整发送速率——隐含地最大化了用户效用总和。每种 TCP 变体对应于不同形状的效用函数。利用优化分解进行“正向工程”，已经引领了多种新协议的开发，包括 TCP FAST 和新型 MAC 协议，并具有可证明的最优性和稳定性特性。尽管优化理论不能提供所有答案，但这篇论文表明它可以成为我们前进道路上的宝贵指南。
在过去十年中，网络测量已成为一个丰富而活跃的研究领域，最早的研究工作聚焦于描述单条链路上 IP 流量的特性和互联网端到端路径的性能。后来的研究意识到测量数据在数据网络（如互联网服务提供商的主干网络）的设计和运营中的重要性。网络运营商往往需要网络范围内的流量视图，以检测拒绝服务攻击或进行流量工程。然而，可用的测量数据与运营商所需的数据信息之间通常存在较大差距。这两篇论文为如何从少量测量数据中提取最有用的信息提供了新的视角。
N. G. Duffield 和 M. Grossglauser, “Trajectory sampling for direct traffic observation,” IEEE/ACM Transactions on Networking, 2001年6月, pp. 280–292
大多数测量研究集中于巧妙利用已有数据，或设计计算特定统计量的点对点解决方案。这篇论文则是一个显著的例外。论文提出，路由器应以一致的方式对数据包进行采样，从而计算出“轨迹”，即跟踪网络中部分数据包的流动情况。轨迹采样可以用于确定网络中的应用类型分布、追踪分布式拒绝服务攻击、测量单向丢包和延迟等。论文展示了 IP 数据包拥有足够的熵，以使哈希函数能够对相对较少位数的数据进行伪随机采样。第二个哈希函数可生成采样数据包的简要摘要，以便高效导出至监控系统。轨迹采样简单有效，现已被纳入 IETF 的“psamp”工作组制定的数据包采样标准。
Y. Zhang, M. Roughan, N. Duffield 和 A. Greenberg, “Fast accurate computation of large-scale IP traffic matrices from link loads,” Proc. ACM SIGMETRICS, 2003年6月, pp. 206–217
网络运营商需要了解流量矩阵——即网络中所有入口和出口点之间的负载情况，以便进行流量工程和容量规划。然而，没有网络边缘的细粒度测量数据时，流量矩阵却难以计算。数年来，研究人员尝试利用“层析成像”技术，通过链路负载统计数据和路由信息推断流量矩阵。然而，由于链路数（提供负载统计）远少于入口-出口对数（构成流量矩阵），问题严重欠约束。早期研究试图应用其他领域（如交通网络）中发展出的现有层析技术，但由于模型假设不符，效果并不理想。该论文引入了一个效果更好、速度更快的“引力模型”。在 SIGCOMM’03 上发表的后续论文《基于信息论的流量矩阵估计方法》为“层析-引力”方法为何效果显著提供了数学解释。
许多网络问题本质上都是规模问题。我们往往拥有的数据量超出分析能力，或者需要维护的状态比实际可存储的更多。能巧妙地筛选大量数据或维持系统状态的准确近似在实践中非常有价值。以下两篇论文就是很好的例子。
Cristian Estan、Stefan Savage 和 George Varghese, “Automatically inferring patterns of resource consumption in network traffic,” Proc. ACM SIGCOMM, 2003年8月, pp. 137–148
网络运营商在分析数据包或流量记录时，必须从高维度的大量数据中提取有意义的信息。早期的研究仅在预先确定的方式下对数据进行聚合（如基于 TCP 连接、IP 地址对或 IP 前缀），然后报告流量的主要贡献者。然而，运营商实际上更关心“重要”或“意外”的流量贡献者。该论文提出的算法可以识别大型流量簇，以便最小化其表示。算法通过各种维度聚合数据，计算多维树，并识别代表显著且独特流量聚合的节点。例如，算法可能识别到单个 UDP 传输占据了 15% 的流量，而某个源 IP 地址则占据了 25%，而非简单地报告前十个流的列表。论文展示了算法的边界、对测量记录的评估，以及被网络运营商广泛使用的公开工具（称为 AutoFocus）。
A. Broder 和 M. Mitzenmacher, “Network applications of Bloom filters: A survey,” Internet Mathematics, 2004年, 第1卷第4期, pp. 485–509
Bloom 过滤器是一种简洁的数据结构，用于表示一组项，旨在回答成员查询。与存储和传输完整的项列表相比，Bloom 过滤器所需的空间和带宽通常少得多，但代价是引入了误报。（幸运的是，误报在许多实际应用中是可以接受的。）其基本思想是维护一个包含 m 位的数组，并使用 k 个独立的哈希函数将每个项映射为 1 到 m 的随机数。将一个元素加入集合时，需将 Bloom 过滤器中的相关位设置为 1；同样，集合成员查询则需检查所有相关位是否都已设置为 1。尽管 Bloom 过滤器发明已有 35 年以上，但在网络领域的应用相对较新。该综述论文很好地概述了 Bloom 过滤器在解决各种网络问题中的应用和扩展，例如在对等网络中总结内容、收集流量测量数据和检测转发循环。论文还提供了 Bloom 过滤器背后数学原理的易理解概述，以及诸如计数 Bloom 过滤器和压缩 Bloom 过滤器等实用变体。
在90年代初至中期，网络界涌现了大量关于在分组交换网络中提供服务质量保证的理论性论文。将范围缩小到少数几篇论文实属不易，但以下两篇在我脑海中尤为突出，堪称清晰实用问题与优雅严格解决方案结合的典范。
A. Parekh 和 R. Gallagher, “A generalized processor sharing approach to flow control in integrated services networks: The single-node case,” IEEE/ACM Transactions on Networking, 1993年6月, pp. 344–357
这篇论文及其续篇《多节点案例》（发表于1994年4月的ToN期刊）堪称经典。我已不记得在90年代中期读过多少次了。这篇论文提出了广义处理器共享（GPS）作为设计和分析分组调度算法的理想模型，例如加权公平队列（WFQ）。在GPS中，每个活跃流 iii 根据其权重 wiw_iwi 获得与其成比例的链路带宽份额，所有流量被视为流体。实际的WFQ方案可以根据在GPS模拟中的完成时间（或开始时间）来调度分组，并可以分析其性能是否符合理想化的GPS系统所提供的公平性和延迟保证。特别地，论文显示，基于分组的GPS方案结合漏桶准入控制，可以使网络在吞吐量和延迟方面提供严格的界限，令人称奇。
J. D. Salehi、Z.-L. Zhang、J. Kurose 和 D. Towsley, “Supporting stored video: Reducing rate variability and end-to-end resource requirements through optimal smoothing,” IEEE/ACM Transactions on Networking, 1998年8月, pp. 397–410
可变比特率的视频流，其帧大小随时间剧烈变化，使得高效传输变得困难。为峰值比特率分配网络带宽是浪费的，而仅分配平均值则不够。90年代中期，一些论文探索了利用接收端的缓冲区空间来“平滑”可变比特率视频的方式。基本问题是要将帧 iii（大小为 fif_ifi）传输到拥有缓冲区空间 bbb 的接收端，确保在播放前送达，并最小化网络流量的突发性。发送端必须计算传输计划，既要支持连续播放，又不能让接收端的缓冲区溢出。该论文提出了一种线性时间算法来计算最小化最大传输速率及更高阶矩的传输计划，从而尽可能减少速率的变化。论文不仅提出了针对实际问题的最优解决方案，还巧妙地联系到主化理论，正式定义了“平滑性”并证明了该算法的最优性。
最后这两篇论文严格来说并非网络领域的论文，但我不得不将它们纳入我的前十名单中，因为其中的教训对网络领域有着极大的借鉴意义。负载均衡问题广泛存在于计算机科学的许多领域中，从在共享计算集群上管理作业到在网络中将数据包分配到多条路径上。负载均衡引发了一些重要的问题，例如在系统资源利用效率上需要多大的灵活性、是否值得重新评估过去的负载均衡决策，以及在应对过时信息时如何防止震荡。这两篇论文正是专注于这些问题。
Mor Harchol-Balter 和 Allen Downey, “Exploiting process lifetime distributions for dynamic load balancing,” ACM Transactions on Computer Systems, 1997年8月, pp. 253–285
这篇论文挑战了关于在计算机集群中将正在运行的作业迁移到不同机器以实现负载均衡是否值得的传统观点。早期的研究认为，负载均衡的好处被作业迁移的开销所抵消，建议负载均衡仅应关注新作业进入系统时的放置。然而，该论文分析了UNIX工作站工作负载的痕迹，发现实际上作业的生命周期存在极高的方差，少数作业会运行很长时间。一旦一个作业在系统中存在了一段时间，它很可能会继续存在很长时间。迁移这些长时间运行的作业是非常值得的，论文中的分析模型证明了这一点。该论文有效地展示了工作负载对系统设计的适宜性有着深远的影响。对我而言，论文还提供了另一个宝贵的教训——工作负载中的高变异性并不一定是坏事，实际上可以成为优势。
M. Mitzenmacher, A. Richa, 和 R. Sitaraman, “The power of two random choices: A survey of techniques and results,” 书章节, Handbook of Randomized Computing: Volume 1, 2001年, pp. 255–312
老实说，我将这篇综述论文列入前十榜单有点“取巧”，因为我想提到两篇我非常喜欢的论文：《The power of two choices in randomized load balancing》（IEEE Transactions on Parallel and Distributed Computing, 2001年10月）和《How useful is old information?》（IEEE Transactions on Parallel and Distributed Systems, 2000年1月），这两篇都是由Michael Mitzenmacher撰写的。这篇综述论文总结了这两篇以及更多相关研究。第一篇关于“双重选择的力量”的论文展示了，即便稍微增加一点灵活性也能带来显著效果。特别地，从随机选择的两个选项中选择更好的一个（例如网络路径）会出乎意料地有效。第二篇关于过时信息的论文探讨了如何在信息过时时实现负载均衡。选择“最优”选项可能会引发误导，甚至导致不稳定。相反，从随机选出的两个选项中选取较优的是更好的方法。多年来，这两篇论文对我在思考如何使负载敏感路由变得稳定且高效方面帮助很大。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/66802.html