Nate Foster：把网络当作程序

Ron Minsky 介绍 Nate Foster。他是 EPFL 教授和 Jane Street 访问研究员，研究将编程语言与网络结合起来。Foster 每周有一天与网络团队一起工作。

Foster 刚上大学时学习物理，后来越来越受计算机科学吸引。他喜欢追踪程序经过编译器、指令集和芯片直至逻辑门的过程，也欣赏 lambda 演算等计算抽象：它们由人创造，却受数学和物理实现的约束。

他的第一次研究经历是与 Kim Bruce 合作的 Java 编译器暑期项目。Java 将垃圾回收和基本可靠的静态类型系统带入广泛应用；在 Java 引入泛型之前，这个项目探索了如何加入多态。

Bruce 的方案是几个竞争设计之一。最终采用的泛型源于 Philip Wadler 和 Martin Odersky 的 GJ。Foster 指出，类型系统看似简单，可能隐藏微妙的可靠性或性能问题，因此借助研究界的成果很有价值。

在英国待过一段时间后，Foster 到 Penn 师从 Benjamin Pierce 攻读博士。他原本预计研究类型系统或语义，但 Pierce 建议他做一个与 OCaml 文件同步工具 Unison 相关的数据同步项目。Foster 起初有些失望，因为它听起来像个系统问题。

这个项目包含一个优雅的编程语言问题：同步不同表示形式，比如 iCal 和 XML 中的日历数据，需要双向转换。这两个函数关系密切，因此研究者开发了一个统一抽象 lens，可以从中导出两个方向的转换。

lens 在数据库和函数式编程研究中已有先例，但 Pierce 和 Alan Schmitt 的表述因清晰而受到关注。Foster 研究了各种变体、其表达能力，以及保证变更在不同表示间准确传播的定律。后来的 Haskell 工作将这一思想推广到其他结构。

博士毕业后，Foster 接受了 Cornell 的教职，但先在 Princeton 与 David Walker 和 Jennifer Rexford 共事一年。研究六年 lens 后，他想寻找新问题；这个团队愿意接纳一位几乎没有网络背景的编程语言研究者。

此后，Foster 在编程语言与网络的交叉领域工作了约 15 年。随着大型科技公司需要更自由地改变网络，并面临巨大数据中心中协议和控制算法的复杂性，软件定义网络应运而生。

其思路是用比单台硬件更高层的方式，通过软件描述网络行为。语言可以帮助工程师组合功能、隔离不应互相干扰的部分，并推断整个网络可能出现的行为。

Minsky 将此与设计、布线之后逐台配置交换机的方式作对比。网络级程序可以加快迭代，也更容易预测某些性质是否成立。物理设计仍然重要，网络程序也有特殊约束：每个数据包在每一跳都分配内存是不现实的。

网络还需要隔离组件，并常由不同团队进行分布式控制。Minsky 将这一问题与硬件综合作比较：两者都需要描述大型图状系统的语言，但各自领域对生成的实现有严格限制。

Foster 的团队开发了 NetKAT，一种描述数据包转发的语言，而不是描述终端主机行为、TCP 或选择路由的控制平面。他们发现自己的设计与带测试的 Kleene 代数相契合，这是一套与 Dexter Kozen 相关、用于命令式程序的现有数学框架。

这一联系将看似奇特的网络操作与有限自动机和状态机等熟悉概念连接起来。Minsky 认为，简单的数学基础能让语言功能更自然地推广和组合。对 Foster 而言，它还提供了构建编译器和验证工具的方法。

团队为 NetKAT 加入概率，以推理不确定流量、故障和随机负载均衡。确定语义十分微妙；Foster 说，现有代数结构帮助他们避免扩展后的语言变得不一致。

Foster 的口号是把网络当作另一个程序。过去，新能力往往依赖硬件厂商添加功能或标准组织就协议达成一致。他希望在网络硬件上部署新行为，能够更像在处理器上编写新程序一样自由。

Minsky 指出，在一个组织控制的大型网络内部，这种自由比跨独立网络更容易实现。Foster 同意：标准和厂商使互联网跨数万个自治系统互联互通，而大型私有网络可以在自己的边界内追求自身目标。

将同样的方法应用于开放互联网很难，因为它的成功也使改变变得困难。不存在一个可行的日子，让所有自治系统同时切换到新协议。研究人员长期以来一直探索让互联网更易扩展和演进的架构。

Foster 认为，把网络当作程序的思想已经很普遍。他与合作者写的一篇愿景论文遭到拒绝，部分原因是审稿人认为这一前提早已确立。但具体预测并未全部实现：完全集中式控制和完全可编程路由器没有按最初设想的形式得到采用。

Minsky 补充说，软件文化本身也有价值：当配置有集中表示时，版本控制、代码审查和测试都可以用于网络。Foster 同意，这比形式验证的范围更广，并指出大型互联网服务提供商在 20 世纪 90 年代就已探索集中式规范。

网络配置的表示也可以在部署前接受测试或验证。例如，工程师可以检查建议的路由变更是否会破坏其他地方的连接。这些检查很重要，因为配置变更的意外影响曾造成重大故障。

Foster 提醒说，验证问题还没有解决。网络是存在故障、相互作用的控制环路以及模型可能无法准确表示的组件的分布式系统。对快照的检查无法捕捉所有动态交互，也不能消除人为错误。

一项实际成果是利用模型检查器、SAT 求解器或 NetKAT 等工具推理转发平面的快照。工程师可以检查两台主机是否仍然连通，或本应隔离的系统之间是否存在不该有的路径。这些工具既能发现错误，也能让工程师更有信心地进行修改。

拒绝违反某项性质的变更并不总是足够。如果控制器是在响应故障时提出这项变更，而系统拒绝它却没有更好的替代方案，原来的故障可能仍无法解决。挑战在于同时考虑期望的性质和控制系统的响应。

Foster 珍视网络研究界中学术界、云运营商和交换机厂商的紧密交流。研究理论和建设大型骨干网的人互相交换想法，有时能迅速将研究变为实践。编程语言领域的进展往往需要更长时间，尽管其中的联系也在增强。

他参与开发了 P4，一种指定交换机和网络接口行为的语言。OpenFlow 大致将路由器建模为一张大型查找表；真实的高速设备具有由专用单元组成的复杂流水线。P4 暴露了更多流水线结构，同时允许定制其行为。

在 Cornell 休假期间，Foster 加入了开发可编程交换机的 Barefoot Networks。他希望更深入地理解路由器和硬件。与芯片设计专家共事，让他了解到从电路设计到物理布局和制造，一台设备需要多少不同专业的协作。

在 Barefoot，同事 Chang Kim 发现，可编程路由器芯片可以充当一种专用处理器：内存和状态有限，但吞吐量极高。一个数据包穿越数据中心时可能经过多个这样的处理器，由此引出了哪些计算可以放在网络内部的问题。

更难也更有争议的问题是哪些计算应该放在那里。端到端原则提醒人们，不应轻易把只惠及部分用户、却让所有人承担成本的功能放进网络。尽管如此，Foster 认为网络内计算在某些情况下适合用于观测、缓存和部分与共识有关的功能。

Minsky 说，Jane Street 也在网络关键位置加速某些操作，用于监控、过滤和流量整形。一个尤其重要的工作负载是组播：交易所用它向众多接收者分发行情数据。

组播沿分发树复制数据包，但它没有成为人们曾预期的通用视频分发机制。Minsky 认为，带宽变得便宜，而维护许多独立分发树的控制平面状态仍然昂贵。交易网络中的频道相对较少，却需要到达许多消费者，因此组播在那里更有用。

他说，云服务可能主要为兼容旧应用提供类似组播的接口，却不具备交易工作负载所需的性能特征。Foster 欢迎重新审视未能实现的预测：研究界需要空间尝试那些可能永远不会成为主流设计的想法。

Foster 提到鼓励新想法的 Nines 网络会议，以及 Scott Shenker 对自己在服务质量方面错误判断的反思。端到端设计等原则很有用，但如果将它们视为永远不能重新审视的规则，就有停滞的风险。

Minsky 说，Jane Street 的成长让公司能够在渐进式改进之外做更长期的押注。学术研究可以走得更远，探索可能需要几十年才能结果的想法。Foster 早已通过函数式编程了解 Jane Street，并受到其技术雄心和对新方法开放态度的吸引。

Jane Street 的网络已发展到足以受益于自上而下的规范，以及帮助人们有信心地进行修改的工具。Foster 也对金融领域特有的约束感到好奇：组播和极低延迟可能导向不同于超大规模云厂商的解决方案。

Minsky 观察到，研究可能受当下主导的工业问题塑造。他以垃圾回收为例：多年来 Java 的假设影响了许多文献，尽管其他语言和工作负载需要不同的调优选择。

Foster 介绍了一篇关于交易网络中组播的论文。通用路由器的带宽和功能有所增加，但更复杂的流水线可能增加延迟，而组播支持不一定以同样速度发展。论文探索光网络和电路交换等替代方案，包括广泛分发与过滤之间的取舍。

Minsky 想知道组播是否在其他场景中被低估，例如分发更新流或实现状态机复制。在系统内部，它可以充当高效总线；交易所也用它跨组织边界公平地分发行情数据。

Foster 思考分组交换是否应该始终作为默认选择。它能在不可预测的流之间高效共享资源，但路由器必须处理多个请求同时争用同一输出端口的情况。这种动态仲裁增加了高速交换结构的复杂性。

Nick McKeown 和 Sundar 的一篇论文研究了规律的机器学习训练工作负载。如果通信时序和排列可以预测，调度式交换机可能比通用分组交换机更简单、便宜和快速。Foster 看到混合设计的潜力，同时承认分组交换具有高效率和灵活性。

Minsky 指出，训练需要同步昂贵的 GPU：无法被其他工作掩盖的通信时间会让它们闲置。由此产生的吞吐量和低延迟需求，以及不同的纵向扩展和横向扩展网络，为重新思考设计提供了机会。Foster 看到传输协议、集合通信和与 GPU 代码协同优化方面的活跃实验。

话题转向边界网关协议 BGP。Jane Street 不断扩大的广域网当时仍以逐台路由器配置的形式表达。BGP 旨在连接互联网上的自治系统：每个系统决定如何路由流量，并与邻居分享选定的可达性信息。

路由器可以通告自己知道一条通往目的地的路径，并附带成本或标签等属性。接收方比较通告并做出本地选择。协议是分布式的，但这些本地选择共同形成了整个网络的路由。

为什么这个去中心化系统通常能收敛？Foster 提到 Lixin Gao 和 Jennifer Rexford 的研究，指出互联网商业关系和路由偏好的性质有助于解释其稳定性。BGP 也可以在组织内部使用，让路由器学习内部和外部路径并响应故障。

BGP 表达能力强、支持广泛，网络工程师也很熟悉。Foster 说，早期 SDN 愿景的一个弱点是认为单一高层目标必然需要集中式实现。分布式协议可以快速响应故障，无须全局协调。

Jane Street 的 Butane 系统结合了这些思路。工程师在代码仓库中维护高层规范，像软件一样审查变更，再将其编译成每台路由器的 BGP 配置。随后路由器交换消息，共同形成转发行为。

策略区分了需要最快可用路径的流量和只需要到达目的地的流量，也反映公司网络结构、站点和流量分类。工程师可以修改简洁的策略，而不是手工编辑多台路由器的配置。

Foster 说，其价值并不在某个令人惊叹的单一算法，而在软件化工作流程：编译器生成 BGP 配置，工具验证并可视化变更，随后部署结果。网络工程师尤其欣赏能够在修改前看到预期后果。

利用历史测量数据以及 Butane 和 BGP 语义构建的模型，可以估算站点间延迟等变化。团队正在探索更强大的假设问题：如果链路故障会怎样？哪些配置变更能缓解热点，同时尽量减少影响？

Foster 强调，自动寻找这类变更仍是研究课题，类似于程序综合或基于求解器的配置探索。建立信心需要一个经过数学检验、也与实际厂商硬件对照过的模型，因为硬件实现必须符合假设的 BGP 语义。

Foster 认为，形式方法的作用不只是像安全带一样防止错误。可信模型还能让工程师探索更大的变更并比较后果。Minsky 将其描述为对可能网络设计的一种可观测性，但前提是模型准确。

团队也开始用模型进行容量规划：根据流量需求、历史工作负载和可用光纤，工程师可以考虑未来购买哪些链路。同一个模型既能帮助确定今天的路由，也能帮助规划明天的网络扩展。

Butane 借鉴了学术成果，包括 Zachary Tatlock 等研究者提出的 BGP 形式语义。团队选择了相对简单、能直接编译成厂商配置的策略抽象，而不是选择表达能力更强、却会掩盖更多映射关系的语言。

Foster 起初觉得这种朴素设计不够令人兴奋，但现在认为它适合这个场景。工程师可以揭开抽象，看到它如何映射到 BGP。Minsky 同意，即使更复杂的优化可能有价值，直接的编译方式仍能让行为更容易理解。

作为访问研究员，Foster 通常每周在 Jane Street 工作一天，与网络工程师和工具专家一起设计并制作系统原型。他珍视工程师的效率和专业能力，也珍视解决真实运营问题所带来的反馈。

生产上线所需的工作远超做出可运行原型。团队反复测试，包括在实验室和尚未承载生产业务的新基础设施上测试，然后才更广泛地上线。运营工作还包括升级路由器固件，以及与公司的部署流程集成。

Jane Street 自建的工具让团队能够直接接触开发部署基础设施的工程师。Foster 说，这使他们能够加入项目需要的功能。Minsky 指出，公司独特的软件生态既带来困难，也让他们能够在很大程度上控制技术栈。

Foster 喜欢访问研究员角色，部分原因是它让他在学术职责之外有时间编写代码。这项工作也启发了他的实验室：最初的 Butane 和 BGP 语义使用操作模拟器，而他的学生正在探索更代数化的路由模型。

Tim Griffin 的 metarouting 工作提出了策略语言的通用构件。不同组织选择路径和分享信息的方式各不相同，因此一种策略语言可能不适合所有人。BGP 可以作为多种不同策略语言的低层目标。

路由代数抽象了与对等方交换的信息，以及在收到的路由之间做出的选择。例如，关注延迟和带宽的代数可以组合成更丰富的策略，并定义两者之间的优先关系。这为用可复用构件构建领域专用语言提供了方法。

理论还研究路由系统何时收敛。BGP 配置可能发生振荡：一方偏好的路径使另一方改变选择，进而不断互相影响。代数条件可以帮助刻画何时能够保证稳定解。Foster 的实验室正在重新研究这些思想。

更广泛的目标是通过 BGP 这样的分布式协议实现高层网络程序。Foster 认为，路由代数最终可能帮助 Jane Street 推理更丰富的 Butane 策略，尽管现有策略抽象最初有意设定了较为有限的目标。