目前学术界最先进的数据包调度器介绍！
目前学术界最先进的数据包调度器介绍！
本文是一篇详细介绍目前业界最先进的队列调度器硬件结构的文章。队列调度器的评价标准很简单，在保证高性能的同时能够支持尽可能多调度算法的硬件调度器就是最好的调度器。前几年，开源的PIFO（Push-In-First-Out）面向硬件实现，在保证性能的前提下，可以部署实现多种调度算法；而PIEO（Push-In-Extract-Out）在PIFO的基础上做了进一步改进，与PIFO一样，它维护元素的有序列表，但与PIFO不同，PIFO只允许从列表的开头出队，而PIEO允许从列表中的任意位置出队；总体而言，PIEO调度程序比PIFO具有更高的表达力和30倍以上的可扩展性。我们期待着业界有采用该架构的产品出现。
随着链路速度的提高和CPU速度缩放速度的降低，软件中的数据包调度会导致较低的精度和较高的CPU利用率。通过将数据包调度卸载到诸如NIC之类的硬件，可以潜在地克服这些缺点。然而，为了保持软件分组调度器的灵活性，硬件中的分组调度器必须是可编程的，同时还必须快速且可扩展。硬件中最先进的数据包调度程序要么折衷了可扩展性（Push-In-First-Out（PIFO）），要么表达了各种数据包调度算法的能力（先进先出（FIFO）））。此外，即使是像PIFO这样的通用调度原语，其表达能力也不足以表达分组调度算法的某些关键类别。因此，在本文中，我们提出了PIFO原语的泛化，称为Push-In-Extract-Out（PIEO），它与PIFO一样，维护元素的有序列表，但与PIFO不同，PIFO只允许从列表的开头出队，PIEO通过在出队时支持基于断言的可编程过滤，允许从列表中的任意位置出队。接下来，我们介绍PIEO调度程序的快速且可扩展的硬件设计，并在FPGA上进行原型设计。总体而言，PIEO调度程序比PIFO具有更高的表达力和30倍以上的可伸缩性。
CCS概念•网络→可编程网络；•硬件→网络硬件；
关键词：可编程分组调度；网络硬件
引言
“在硬件加速计算时代，识别并卸载通用的抽象和原语，而不是单独的算法和协议。”
数据包调度程序执行一种调度算法或调度策略，该算法或调度策略指定何时以及以什么顺序在网上传输数据包。在软件中实施数据包调度程序可以灵活地快速试验并采用新的调度算法和策略。但是，这种灵活性是以消耗CPU周期为代价的，否则这些CPU周期本可以用于运行应用程序。在公共云网络中，这转化为收入损失[15]，因为数据包调度的CPU开销[31]占用了客户VM可用的处理能力。不幸的是，随着链接速度的增加与CPU速度缩放的减慢[11，14]之间越来越大的不匹配，这个问题只会变得越来越糟[3]。
接下来，随着链路速度的提高，用于做出调度决策的时间预算也越来越小，例如，以100 Gbps的链路速度，以MTU时标精度实施调度策略时，需要每120 ns做出一次调度决策。从这个角度来说，单次DRAM访问需要大约100 ns的时间。此外，新的传输协议，如Fastpass[30]、QJump[16]和以太网TDMA[41]，以及最近提出的电路交换设计[35、21、42、25]，以及依赖于非常精确的数据包间隔的协议[2、19]，都要求数据包在线路上以精确的时间传输，在某些情况下，数据包的传输精度达到纳秒级[35]。在软件中满足这些严格的要求是具有挑战性的[31，22，28，2，2，35]，主要是由于非确定性的软件处理抖动，以及缺乏高分辨率的软件定时器。
在硬件中的数据包调度器，如网卡，有可能克服软件数据包调度器的上述限制[31]。但是，为了保留软件数据包调度器的灵活性，硬件中的数据包调度器必须是可编程的。此外，如今的多租户云网络严重依赖虚拟化，数百个虚拟机或轻量级容器在同一物理机上运行。这可能会导致每个终端主机的流量类别或流数万个[32，31]。因此，数据包调度器也必须具有可扩展性。
硬件中最先进的分组调度器是基于两种调度基元之一--(i) 先入先出(FIFO)，它简单地按照元素到达的顺序进行调度，和(ii) 推入先出(PIFO)[37]，它提供了一个优先级队列抽象，通过保持一个有序的元素列表(基于可编程的排序函数)，并总是从有序列表的头部("最小排序 "元素)进行调度。不幸的是，基于这些基元的数据包调度器要么在可扩展性上有所妥协(基于PIFO的调度器)，要么在表达广泛的数据包调度算法的能力上有所妥协(基于FIFO的调度器)。此外，即使像PIFO这样的通用调度基元也不足以表达某些关键类的分组调度算法（§2.3）。因此，在本文中，我们提出了一种新的硬件可编程的分组调度器，它比最先进的调度器更快，更可扩展，更有表现力。
为了设计一个可编程的数据包调度器，我们利用大多数数据包调度算法在调度过程中必须做出两个关键的决定。(i) 一个元素（数据包/流）何时变得有资格进行调度（由作为时间函数的一些可编程的谓词决定），以及(ii) 在符合条件的元素集中以什么顺序进行调度（由一些可编程的等级函数决定）。为此，在任何给定时间，数据包调度算法首先筛选出当时符合调度条件的元素集（使用谓词函数），然后从该集中调度最小的排序元素（§2.2，§2.3，§4）。因此，大多数数据包调度算法可以抽象为以下调度策略--在任何给定的时间内，调度 "最小排名合格 "的元素。
接下来，为了实现调度“最小排序的合格”元素的策略，需要一个提供以下内容抽象的原语：（i）基于断言的过滤，以及（ii）在元素的任意子集中选择最小的元素。不幸的是，基于最新优先级队列的原语（例如PIFO）不提供这些抽象。因此，在本文中，我们提出了一种新的调度原语，称为Push-In-Extract-Out（PIEO）（第3.1节），可以将其视为PIFO原语的概括。PIEO与每个元素关联一个等级和一个资格断言，这两者都可以根据调度算法的选择进行编程。接下来，PIEO通过始终根据元素的等级（“ Push-In”原语）将元素排入列表中的适当位置，从而以排名的升序维护元素的有序列表。最后，对于调度，PIEO首先从有条件断言当时为真的有序列表中筛选出元素的子集，然后在该子集中的最小索引处将元素出队（“ Extract-Out”原语）。因此，PIEO总是安排“排名最低的合格”元素。此外，我们使用的见解是，对于大多数数据包调度算法而言，可以在入队到有序列表中时计算出元素适合进行调度的时间（teligible），并且在出队时进行过滤的资格断言评估通常会减少为（tcurrent ≥teligible）。在这里，t可以是时间的任何单调递增函数。这种见解使PIEO调度程序（第5节）的硬件实现非常有效。最后，我们为PIEO调度程序（第3.2节）提出了一个编程框架，通过该框架我们可以证明它可以表达各种各样的分组调度算法（第4节）。
PIEO原语维护元素的有序列表（“ PushIn”），在队列的顶部会在出队（“ Extract-Out”）时进行过滤和最小等级选择。但是，在硬件中同时实现快速和可扩展的有序列表具有挑战性，因为它在时间复杂度和硬件资源消耗之间提供了基本的权衡。例如，使用O（1）比较器和触发器，假设元素以数组1的形式存储在内存中，则需要O（N）时间才能将元素放入大小为N的有序列表中。另一方面，为了占用O（1）的时间，诸如PIFO [37]之类的设计通过将整个列表存储在触发器中并将比较器与经典并行之后的列表中的每个元素相关联，来利用硬件中的大规模并行性比较移位架构[29]，因此需要O（N）个触发器和比较器，这限制了这种设计的可扩展性[37]。在本文中，我们介绍了PIEO调度程序的有序列表的硬件设计（第5节），它既快速又可扩展。特别是，我们的设计在O（1）时间（四个时钟周期）内执行“推入”和“提取”原始操作，而只需要O（√N）触发器和比较器，而有序列表完全位于SRAM中。
为了演示PIEO调度程序的硬件设计的可行性，我们在FPGA上对它进行了原型制作（第6节）。我们的原型在几十纳秒内执行每个原始操作（足以以100 Gbps的线速调度MTU大小的数据包），同时还可扩展到成千上万个流（比PIFO扩展30倍以上）。为了进一步评估原型的性能，我们使用实现速率限制和公平队列策略的两级分层调度算法对其进行编程，结果表明我们的原型可以非常准确地在40 Gbps接口带宽的FPGA上强制执行这些策略（第6.3节））。
这项工作不会引起任何道德问题。
背景
2.1报文调度模型
图1显示了本文假设的数据包调度模型。准备好要进行传输的数据包将存储在流队列或流量类别3之一中。每个流队列中的数据包按FIFO顺序进行调度，而队列中的数据包则根据某些自定义数据包调度算法或策略进行调度，该算法或策略指定了应何时以及以什么顺序在网络上传输每个队列中的数据包。为了促进调度，自定义调度状态将保留在内存中。通常，此状态也可以由控制平面访问和配置。最后，数据包调度程序用于表达和执行所选的调度算法/策略。本文的重点是设计一种高效的硬件数据包调度程序，可以对它进行编程，以快速，可扩展的方式表达各种数据包调度算法/策略。
图1：通用数据包调度模型
2.2数据包调度算法
大多数数据包调度算法可以抽象为以下调度策略：
为每个元素（数据包/流）分配一个合格断言和一个等级。每当链接空闲时，在断言为true的所有元素中，调度具有最小等级的元素。
断言确定元素何时才有资格进行调度，而等级决定在符合条件的元素中以什么顺序进行调度。通过适当地选择断言和等级函数，可以表达各种分组调度算法（第4节）。此外，分组调度算法可以大致分为两个关键类别：
节省工作的算法。此类数据包调度算法可确保只要有待发送的数据包，网络链接就不会处于空闲状态。因此，在这些算法中，至少一个活动元素的资格断言始终为true，并且每当链路空闲时，就会按等级顺序安排下一个符合条件的元素。节省工作量的分组调度算法的示例包括：赤字循环（DDR）[34]，加权公平排队（WFQ）[13]，最坏情况公平加权公平排队（WF2Q）[5]和随机公平排队（SFQ）[23]。
非工作节约算法。在此类分组调度算法下，即使存在待发送的分组，网络链路也可以处于空闲状态，即与每个活动元素关联的资格断言可能同时为假。非节省工作量的分组调度算法通常指定调度元素的时间，并且元素p的资格断言通常采用以下形式（tcurrent ≥p.teligible）。非工作节约算法自然适合表达流量整形原语，例如速率限制和数据包起搏[31，32]。非工作保存数据包调度算法的经典示例是令牌桶[50]。
2.3数据包调度原语
先进先出（FIFO）。FIFO是最基本的调度原语，它仅按元素到达的顺序对其进行调度。结果，FIFO原语不能表达广泛的分组调度算法。然而，基于FIFO的调度程序是硬件中最常见的数据包调度程序，因为它们的简单性可以实现快速和可扩展的调度。
推入先出（PIFO）[37]。PIFO原语为每个元素分配一个可编程的等级值，并在任何给定时间安排“最小等级”的元素。为了实现这种抽象，PIFO维护了元素的有序列表（以等级递增的顺序），并在有序列表的顶部支持两个基本操作-（i）enqueue（f），它将元素f插入有序列表中的位置由f的等级和（ii）dequeue（）决定，该元素在有序列表的开头提取元素。
PIFO的局限性。PIFO从根本上提供了优先级队列的抽象，该优先级队列可在任何给定时间调度整个列表中“最小排序”的元素。[37]表明，这种简单的抽象可以表达各种调度算法，这些算法可以指定何时或以什么顺序来调度每个元素。但是，PIFO的抽象不足以表达更通用的调度算法/策略类，该类既指定何时以及以什么顺序调度每个元素—此类算法/策略仅调度排名最小的元素，而仅从元素集合中调度当时有资格进行调度的对象，原则上可以是活动元素的任意子集4。因此，它们始终需要一个原语，该原语支持在出队时动态过滤元素的子集，然后从该子集中返回排名最小的元素，而PIFO原语不支持此功能。这种复杂的数据包调度策略在当今的多租户云网络中变得越来越普遍[38]，最经典的例子是最坏情况公平加权公平排队（WF2Q）[6]。WF2Q是已知的最准确的数据包公平排队算法，使其成为实施公平队列调度策略的理想选择。此外，WF2Q的非节省工作版本可以非常准确地实现诸如速率限制之类的整形原语[31]。
WF2Q + 5（图2（a））尝试在链路空闲时调度数据包，该时间可能在任意离散时间t。但是，使用WF2Q +的挑战在于，元素的任何任意子集的资格断言在t处都可以变为真，如图2（c）所示，因此，在时间t安排最小排序的合格元素变得具有挑战性。在图2（d）和（e）中，我们尝试使用PIFO表达WF2Q +。首先，我们尝试使用单个PIFO（图2（d））。很容易看出这是不够的—如果我们通过增加完成时间来对PIFO进行排序，那么如果某个任意元素在头元素之前变得合格，就会导致错误的调度顺序，并且如果我们通过增加开始时间来对PIFO进行排序，如果多个元素同时变为合格，并且完成时间最短的元素不在PIFO的首位，则仍然可能违反正确的调度顺序。一种更有前途的方法是使用两个PIFO，分别通过增加开始和结束时间来排序，并在元素符合条件时在两个PIFO之间移动元素，如图2（e）所示。但是，这种方法也不够用，因为恰好因为任意数量的元素可以在任何给定时间变得合格，例如在图2中，C，D，E和F都在t = 5时才合格，理想情况下C应该排定时间，因为C在符合条件的元素中完成时间最短。但是，由于资格PIFO是通过增加开始时间来排序的，因此释放D来将PIFO排在C之前，从而导致错误的安排顺序。通常，O（N）个元素（N为PIFO大小）可以在任何给定时间变得合格，这在最坏的情况下可能导致O（N）偏离元素的理想调度顺序。
图2：（a）WF2Q +算法[5]。L是流队列开头的数据包长度，r是流f的速率，x是正在传输的当前数据包的传输长度，F是积压的流的集合。（b）在示例系统中，分组位于六个不同流的开头，其中分组可以具有不同的大小（传输长度）。我们还显示了每个分组的开始和结束时间。（c）在WF2Q +的理想运行中安排顺序。（d）和（e）使用PIFO运行WF2Q +时安排订单
此外，PIFO原语不允许按照某些调度算法的要求动态更新有序列表中任意元素的属性（例如等级），例如，根据元素的年龄更新元素的优先级，以避免严格饥饿-基于优先级的调度算法。
最后，用于实现PIFO原语的有序列表的硬件设计实现了非常有限的可伸缩性（[37]，图8）。因此，PIFO调度程序也无法扩展。原则上，可以使用近似数据结构，例如多优先级fifo队列[1]，日历队列[10]，定时轮[40]或多级反馈队列[4]，来实现近似的数据结构PIFO原语。这些数据结构可以通过使用多个FIFO队列，以快速且可扩展的方式近似优先级队列或有序列表的行为。但是，通过设计，它们只能表示密钥包调度算法的近似版本[33，4]，始终会导致较弱的性能保证[52]。此外，这些数据结构还倾向于具有几个对性能至关重要的配置参数，例如，多优先级fifo队列中的优先级级别数，或日历队列中的存储桶的大小和数量，这对于微调而言并非微不足道。
通用分组调度（UPS）[27]。与PIFO试图提出一种通用的数据包调度原语一样，UPS试图提出一种可以模拟所有其他数据包调度算法的调度算法。尽管[27]证明不存在这样的算法，但它也表明经典的最小松弛时间优先（LSTF）[45]算法已接近普及。但是，就像PIFO一样，LSTF还在其核心处使用优先级队列抽象，因为它总是调度“最小的空闲优先”，就像PIFO调度“最小的优先级优先”一样。结果，LSTF具有与上述PIFO相同的局限性。
推入拉出（PIEO）
在本节中，我们描述PIEO原语，并提供一个编程框架以对PIEO调度程序进行编程。
3.1 PIEO原语
PIEO原语为每个元素分配一个合格断言和一个等级，这两者都可以基于调度算法的选择进行编程，并且在任何给定时间，它都会调度“排名最小的合格”元素。为了实现这种抽象，PIEO维护元素的有序列表（以等级递增的顺序），并在有序列表的顶部支持三种基本操作：
- enqueue（f）：此操作将元素f插入到有序列表中，位于f的等级所指定的位置。该操作实现了“推入”原语。
- dequeue（）：此操作首先从有序列表中其资格断言当时为真的元素的子集中过滤出来，然后使该子集中最小索引处的元素出队。因此，此操作始终使“排名最低的合格”元素出队。如果存在多个具有相同最小秩值的合格元素，那么将首先入队的元素出队。如果不存在符合条件的元素，则返回NULL。该操作实现了“提取”原语。
- dequeue（f）：此操作从有序列表中使特定元素f出队。如果f不存在，则返回NULL。
尽管enqueue（f）和dequeue（）操作足以根据PIEO原语调度元素，但附加的dequeue（f）操作提供了更大的灵活性，可以从列表中异步提取特定元素，也就是说，动态更新调度元素的属性（例如等级）（然后使用enqueue（f）重新入队），如第4.4节所示。
断言功能复杂性的限制。PIEO原语将自定义断言与每个元素相关联，在出队时对其进行评估以过滤元素的子集。但是，断言功能的复杂性受到快速且可扩展的数据包调度程序的实际限制。特别是，我们希望每个基本操作都在尽可能少的时钟周期内执行，以跟上链接速度的提高，同时将断言编码的位数尽可能少，以实现可伸缩性。幸运的是，对于大多数数据包调度算法来说，断言通常采用（tcurrent≥teligible）形式，其中t可以是时间的任何单调递增函数，而teligible是元素可以进行调度并可以在入队时计算的时间。有序列表（第4节）。这样可以在出队时快速并行地评估断言。此外，只需要对每个元素的可编码性进行断言编码，从而还可以确保较小的存储空间，这对于可伸缩性很重要。对于时间和存储约束更为宽松的问题，人们可能会使用具有更复杂断言功能的PIEO原语。
3.2 PIEO编程框架
在本节中，我们描述了对PIEO调度程序进行编程的框架。PIEO假定每个数据包都存储在流队列之一中，并且每个流中的数据包都按FIFO顺序进行调度，如第2.1节所述。因此，有序列表中的每个元素都引用一个流，调度流f会导致在流队列f的头部传输数据包。
PIEO调度程序的编程框架如图3所示。PIEO调度程序包括一个实现PIEO原语（第3.1节）的有序列表数据结构，并且可以通过分配给每个元素的rank和predicate属性进行编程。
图3：PIEO编程框架
3.2.1编程功能
在本节中，我们描述程序员可以实现以对PIEO调度程序进行编程的三种通用类型的函数。我们还描述了每个函数的默认行为，然后程序员可以根据他们打算编程的调度算法的选择来扩展该行为。调度所需的所有状态都可以按流或全局状态存储，并且控制平面和编程功能都可以访问。控制平面可以使用内存来存储控制状态，例如每流速率限制值或QoS优先级，而编程功能可以使用内存来存储算法特定的状态，例如WFQ中的虚拟完成时间[13]。
入队前和出队后功能。入队前功能将要入队的流f作为参数，并且至少根据要编程的调度算法的选择，为f分配等级和断言。请注意，虽然断言是在入队期间分配给列表的，但仅在出队过程中对其进行评估。
后出队功能将流f从有序列表中出队作为参数，并且至少在流队列f的开头传输数据包，如果f的队列不为空，则将f重新排队回到有序列表中当前数据包传输之后。
尽管总是在有序列表上的每个dequeue（）操作之后触发Post-Dequeue函数，但是可以通过两种不同的方式触发Pre-Enqueue函数：
1、输入触发模型：在此模型中，每当数据包进入流队列时，都会触发预入队功能。下面显示了此模型下的入队前和出队后功能的默认实现的行为。
2、输出触发模型：在此模型中，每当数据包从流队列中出队时，或每当数据包入空流队列中时，就触发预入队功能。下面显示了此模型下的入队前和出队后功能的默认实现的行为。
程序员可以灵活地在两个模型之间进行选择。权衡是，虽然输出触发模型可以为某些整形策略提供更精确的保证[37]，但它也将Pre-Enqueue函数放在调度的关键路径上，这意味着秩和断言计算的复杂性影响整体调度率。
报警功能和处理程序。使用enqueue（f）和dequeue（f）操作将特定元素异步地从有序列表中入队或出队的能力使程序员能够定义自定义事件，这些事件可以触发可以异步入队或出队特定事件的自定义警报功能流入或流出有序列表。程序员还可以定义自定义警报处理程序功能，以对出队流进行操作。默认情况下，这些功能在PIEO中处于禁用状态。
3.2.2实现编程功能
尽管我们为PIEO调度程序提供了一个编程框架，但本文并未重点介绍用于实现用于对PIEO调度程序进行编程的编程功能的特定编程语言。这将取决于硬件设备的基础架构。例如，对于FPGA设备，可以使用诸如System Verilog [49]，Bluespec [8]或OpenCL [46]之类的语言来实现编程功能。在我们的FPGA原型中，我们使用System Verilog来实现编程功能（第6.3节）。对于具有RMT [9]架构的ASIC硬件设备，可以潜在地将一种域特定语言改编为可编程交换机（例如Domino [36]）（用于对PIFO调度程序进行编程）。我们将探索用于网络硬件设备的新的可编程硬件体系结构和特定于域的语言（和编译器），作为将来工作的途径。
PIEO的表现力
在本节中，我们使用第3节中描述的PIEO原语和编程框架来表达各种分组调度算法。在不失一般性的前提下，本节中介绍的用于编程功能的伪代码采用第3.2.1节中描述的输出触发模型。
4.1节约工作的算法
赤字轮询（DRR）[34]。DRR以循环方式调度流量。调度流后，DRR会从该流传输数据包，直到流用尽信用（赤字计数器）为止。
加权公平排队（WFQ）[13]。WFQ为流中的每个数据包计算虚拟完成时间，并在任何给定时间调度其头部数据包具有最小完成时间值的流。
最坏情况的公平加权公平排队（WF2Q +）[5]。WF2Q +计算流中每个数据包的虚拟开始和结束时间，并在任何给定时间调度头数据包的开始时间小于或等于当前时间的所有流中头数据包具有最小完成时间值的流虚拟时间。
4.2非工作节约算法
令牌桶（TB）[50]。TB调度来自符合条件的流（即具有足够令牌的流）的数据包，或者将流的调度推迟到某个将来的时间，直到该流收集了足够的令牌。
速率控制的静态优先级排队（RCSP）[53]。此类算法通过为流中的每个数据包分配资格时间来塑造每个流中的流量，并在任何给定时间调度所有流中优先级最高的流，并在队列的开头分配一个合格的数据包。
4.3分层调度
到目前为止，我们仅讨论了固定调度。然而，实际上，通常希望将流分组为类的层次结构，例如，包括一组VM的两级层次结构，每个VM内具有一组流。在该示例中，可以使用某种调度策略（例如，针对每个VM的速率限制）在VM之间共享链路带宽，而可以使用不同的调度策略来对每个VM内的流进行调度，例如公平排队。通常，我们可以使用树结构来表示这样的层次结构，如图4所示，其中叶节点表示流，而非叶节点表示更高级别的类，例如VM。不幸的是，由于每个非叶节点都可以实施自己的自定义调度策略来调度其子节点，因此单个PIEO不足以表示分层调度策略。但是，我们可以使用多个PIEO支持分层调度。
我们将树中的每个节点（根节点除外）与一个队列相关联–对于叶节点，这些是按流FIFO队列，用于存储数据包，而对于非叶节点，则是逻辑队列，这些逻辑队列引用了子节点为该节点排队。接下来，我们将每个非叶节点与逻辑PIEO关联，该PIEO将调度该节点的子节点。由于PIEO允许我们使用断言从有序列表中过滤元素的子集，因此处于相同层次结构的所有节点都可以共享相同的物理PIEO，然后可以将其逻辑上划分为一组逻辑PIEO，每个逻辑PIEO 节点在层次结构中处于同一级别，每个逻辑PIEO的大小等于相应节点的子节点数（图4）。接下来，每个非叶子节点p都会维护其逻辑PIEO的开始索引和结束索引，并且其每个子元素f的合格断言都将扩展为（p.start≤f.index≤p.end），从而允许 从物理PIEO中提取p的逻辑PIEO（p的子代）中元素的有序列表。
每个级别的入队都是独立发生的，并由与固定调度相同的条件触发，例如，数据包入队到空队列（第3.2.1节）。出队总是始于根PIEO，并向下传播到树层次结构中的较低级别。每个较低级别的PIEO都与一个FIFO关联，以存储从父级别出队的ID。每当相应的FIFO不为空时，将触发级别为i的出队。然后提取对应于节点fifo.head的逻辑PIEO，然后将逻辑PIEO中排名最小的合格元素从队列中取出并放入i-1级的FIFO中，直到达到最低非叶级为止，此时，安排出队元素（代表流的叶节点）进行传输。所有这些都显示在图4中。
图4：PIEO中的分层数据包调度
最后，为了支持具有任意树形拓扑结构的n级分层调度，我们需要n个物理PIEO。我们将此层次结构映射为作为n个独立物理PIEO的阵列的硬件，并以FIFO作为arraylist中任意两个连续PIEO之间的接口（图4）。
4.4异步调度
在严格的优先级调度中避免饥饿。在严格的基于优先级的调度算法中，避免低优先级流出现饥饿的一种常见方法是定期增加被饿死的流的优先级。通常，只要流花费的时间大于某个阈值而没有计划，就会触发该事件。假设流程在PIEO中按优先级排序，则可以定义一个警报功能和处理程序，该功能可以异步更新饥饿流的优先级以避免饥饿。
基于异步网络反馈的调度。某些数据中心协议（例如[51、12]）可能会基于网络的一些异步反馈而导致流的等级或资格发生变化。例如，在D3 [51]中，可以基于网络反馈异步取消已调度的流。
4.5优先级调度
几种调度算法将优先级分配给每个元素，并按其优先级顺序调度元素。示例包括最短作业优先（SJF）[47]，最短剩余时间优先（SRTF）[48]，最短松弛时间优先（LSTF）[45]和最早截止时间优先（EDF）[44]。可以使用优先级队列数据结构来表示此类算法。通过将每个元素的等级设置为等于其优先级值，并将每个元素的资格断言设置为true，可以轻松地使用PIEO模拟优先级队列。
硬件设计
“计算机科学中的所有问题都可以通过另一层间接解决。”—戴维·惠勒
在本节中，我们描述PIEO调度程序的硬件设计。
我们假设目标硬件设备配备了SRAM。此外，我们假定SRAM分为多个块，每个SRAM块包括独立的访问端口。这样的存储器布局在硬件设备中非常常见，例如，在我们的原型（第6节）中使用的Stratix V FPGA [17]包含大约2500个大小为20 KBits的双端口SRAM块，其中每个SRAM块的访问等待时间为1个时钟周期。
5.1 架构
PIEO调度程序包括一个有序列表，该列表支持三个基本操作（第3.1节）— enqueue（f），dequeue（）和dequeue（f）。但是，在硬件中实现有序列表会在时间复杂度和硬件资源消耗之间实现基本的权衡。为了跟上不断增加的链接速度，我们想在O（1）时间内在有序列表的顶部执行每个基本操作。但是，要实现这一点，最先进的设计（例如PIFO [37]）需要使用经典的并行比较和移位架构[29]对列表中的每个元素进行并行访问，因此必须存储整个列表。列出触发器（与更具扩展性的存储技术（例如SRAM）相对），并将比较器与每个元素相关联。因此，这样的设计需要O（N）个触发器和比较器来获得大小为N的列表，并且随着晶体管缩放的放缓[11，14]，这限制了这种设计的可扩展性。
在本文中，我们提出了一种有序列表的设计，该设计仍然可以在O（1）时间内执行原始操作，但是只需要并行访问和比较O（√N）个元素，而有序列表则完全位于SRAM中。我们使用的关键见解是使用一种间接级别（图5）来存储和访问有序列表。更具体地说，有序列表存储为SRAM中子列表的数组（大小为2√N），其中每个子列表的大小为√N个元素。每个子列表中的元素都按升序排列（排名-子列表）和合格时间的递增顺序（合格-子列表）进行排序。
我们在O（√N）个双端口SRAM块上划分每个子列表的元素，这使我们可以在一个时钟周期内访问两个完整的子列表。接下来，我们在触发器中维护一个数组（大小为2√N），该数组存储指向子列表的指针，该数组中的子列表通过增加每个子列表中最小等级的值来排序。因此，通过按子列表在指针数组中出现的顺序扫过子列表，可以按升序排列获得整个元素列表。
入队和出队操作分两个步骤进行：首先，使用指针数组上的并行比较和优先级编码，找出要入队或出队的正确子列表，然后从SRAM中提取相应的子列表。其次，我们对提取的子列表使用并行比较和优先级编码，以找出子列表在元素中的入队/出队位置，然后将更新后的子列表写回SRAM。因此，通过这种设计，与PIFO中的O（N）不同，我们只需要O（√N）触发器和比较器，以执行几个基本操作（第5.2节）和几个X SRAM开销为代价，只需几个额外的时钟周期（不变式1）。我们在第6节中评估了这些权衡。
5.2 实施
在SRAM中，PIEO维护一个子列表数组（大小为2√N），称为子列表数组。数组中的每个子列表的大小为√N。此外，每个子列表都包含两个有序的子列表-等级子列表和合格子列表。Rank-Sublist中的每个元素都包含三个属性：
- flow_id：这是元素的流ID。
- rank：这是入队函数分配给元素的等级值。
- send_time：编码对入队函数分配给元素的资格断言。PIEO利用以下事实：大多数调度算法都使用形式为（curr_time≥send_time）（§4）的资格断言，其中send_time是元素有资格进行调度的时间。因此，对于每个元素，使用单个send_time值对PIEO中的资格断言进行编码。通过将send_time分配为0来编码始终为真的断言，通过将send_time分配为∞来对始终为假的断言进行编码。
Rank-Sublist通过增加排名值来排序。此外，与每个排名子列表相对应，有一个大小相同的资格-子列表，该列表维护相应的排名-子列表中send_time属性的副本。资格-子列表通过增加send_time值进行排序。
在触发器中，PIEO维护一个大小为2√N的数组，称为OrderedSublist-Array，其中数组中的每个条目都指向Sublist-Array中的一个子列表。更具体地说，Ordered-SublistArray中的每个条目都包含三个属性：
- sublist_id：这是指向Sublist-Array的索引（指针），指向子列表Sublist-Array [sublist_id]。
- minimum_rank：这是子列表Sublist-Array [sublist_id]中最小的排名值，即Sublist-Array [sublist_id] .Rank-Sublist [0] .rank。
- minimum_send_time：这是子列表Sublist-Array [sublist_id]中最小的send_time值，即Sublist-Array [sublist_id].Eligibility-Sublist [0]。
- num：将当前元素的数量存储在Sublist-Array [sublist_id]中。
Ordered-Sublist-Array通过增加minimum_rank值进行排序。此外，Ordered-Sublist-Array被动态划分为两个部分，如图5所示-左侧的部分指向不为空的子列表，而右侧的部分指向所有当前为空的子列表。
通过将子列表按照它们在Ordered-Sublist-Array中出现的顺序缝合在一起，可以得到PIEO中元素的整个列表。我们称此列表为Global-Ordered-List。Global-Ordered-List通过增加排名值进行排序。逻辑上，入队和出队操作发生在Global-Ordered-List的顶部。
图5：PIEO调度程序硬件架构。优先级编码器将位向量作为输入，并返回包含1的最小索引
入队（f）。入队操作将元素f插入Global-Ordered-List。它确保在每个入队操作之后，通过增加等级值对生成的Global-Ordered-List进行排序。这在硬件中实现如下：
图6：示例进入大小为16的元素的PIEO排序列表（大小为4的8个子列表）
- 周期1：在此周期中，我们使用并行比较操作（Ordered-SublistArray [i] .smallest_rank> f.rank）选择要加入f的子列表。我们将生成的位向量输入优先级编码器，该编码器输出索引j。选择由有序子列表数组[j-1]指向的子列表S入队。
- 周期2：在此周期中，我们从SRAM中读取子列表S。如果S已满，则入队操作将推出S中的现有元素。因此，我们还读取了另一个子列表S'来存储推出的元素。S'是Ordered-SublistArray中紧接S的子列表，前提是它不完整，或者是一个新的空子列表。
- 周期3：在此周期中，我们通过在并行比较操作返回的位向量之上运行优先级编码器来确定要进入子列表S的位置（S.Rank-Sublist [i] .rank> f.rank），以及（S.Eligibility-Sublist [i]> f.send_time）分别。如果S已满，则S.RankSublist中的tail元素将移至S'.Rank-Sublist的头部，而我们使用并行比较操作（S'.Eligibility-Sublist [i]> S [tail] .send_time），然后进行优先级编码，以找出从S移动到S'内合格子列表的元素的send_time值排队的位置。如果S'最初是空的，我们还可以通过将S'移到S的紧邻右边来重新排列OrderedSublist-Array。
- 周期4：在此周期中，我们在上一个周期输出的位置处使各个元素入队/出队，然后将S（和S'）写回SRAM。我们还使用以下新值更新了S和S'的OrderedSublist-Array条目：（i）num，（ii）Minimum_rank（从相应的RankSublist读取）和（iii）minimum_send_time（从相应的Eligibility-Sublist读取）。
不变量1 [限制子列表的数量]。确保O（1）入队时间的关键是，当要在其中放入新元素的子列表及其在Ordered-Sublist-Array中紧邻的子列表都已满时，选择一个新的空子列表进行入队。这避免了将一个子列表的尾部元素移动到下一子列表的头部的链式反应（这将导致最坏情况下的O（√N）SRAM访问），但以存储器碎片为代价（图6）。但是，这种设计的结果是不变的，即在有序子列表数组中不能有两个连续的部分完整的子列表。结果，要使用√N个大小的子列表存储N个元素，则最多需要2√N个子列表（2×SRAM开销）。我们将在第6.1节中评估此开销。
出队（）。此操作将返回Global-Ordered-List中的“排名最低的合格”元素。它的实现如下：
- 周期1：在此周期中，我们选择包含“最小排名的合格”元素的子列表。为此，我们使用优先级编码器提取满足条件断言的有序子列表数组中最小索引处的子列表（curr_time≥有序子列表数组[i] .smallest_send_time）。我们称它为S。断言可确保S至少具有一个合格元素，并且由于Ordered-Sublist-Array是通过增加minimum_rank值进行排序的，因此整个列表中“最小排序的合格”元素将保证在S中。
- 周期2：在此周期中，我们从SRAM中读取子列表S。如果S已满，则在出队之后，itwo应该会部分满。因此，为确保不违反不变量1，我们在Ordered-Sublist-Array中S的紧靠左方或紧靠其右方的另一个子列表中读取了一个未满的子列表，并选择了两个子列表（如果两个都为不满。我们称它为S'。如果左右子列表都已满，我们只会读S，因为在这种情况下，即使部分满的S也不会违反不变式1。
图7：从大小为16的元素的PIEO有序列表（每个大小为4的8个子列表）中出队的示例
- 周期3：在此周期中，我们找出从S退出“最小排名合格”元素的位置。为此，我们使用优先级编码器，该编码器在S.Rank-Sublist中输出满足断言（curr_time≥的最小索引idxS.RankSublist [i] .send_time）。将要出队并作为dequeue（）操作的最终输出返回的“最小排名合格”元素是S.Rank-Sublist [idx]。此外，在S已满的情况下，我们将元素从S'移至S，以确保即使出队后S仍保持满，因此确保不违反不变量1。将要移动的元素确定地添加到下一个S.Rank-Sublist的头部（如果S'在S的左侧）或尾部（如果S'在S的右侧）。周期。但是，我们必须依靠优先级编码来确定从e'send_time从S'.Eligibility-Sublist出队的位置，以及在S.Eligibility-Sublist中将其入队的位置。为此，我们使用并行比较操作（S'.Eligibility-Sublist [i] == e.send_time）和（S.Eligibility-Sublist [i]>e.send_time）。最后，如果S或S'在出队后变空，我们通过将S或S'移到包括空子列表的逻辑分区的开头来重新排列有序子列表数组。
- 周期4：在此周期中，我们在上一个周期输出的位置处使各个元素入队/出队，然后将S（和S'）写回SRAM。我们还使用以下新值更新了S和S'的OrderedSublist-Array条目：（i）num，（ii）Minimum_rank（从相应的RankSublist读取）和（iii）minimum_send_time（从相应的Eligibility-Sublist读取）。
出队（f）。该操作使全局元素列表中的特定元素f出队。PIEO会跟踪存储全局顺序列表中每个元素（流）的子列表id（作为流状态的一部分），并在每次基本操作后更新此信息。在循环1中，我们使用该信息选择存储f的子列表，然后从dequeue（）操作重复循环2-4，并在循环3中进行修改，在循环3中，我们使用断言（f == S.Rank-Sublist [i] .flow_id）来找出S.Rank-Sublist中要出队并返回为最终输出的元素的索引idx。
原型与评估
我们在包括234 K自适应逻辑模块（ALM），52 Mbit（6.5 MB）SRAM和40 Gbps接口带宽的Altera Stratix V [17] FPGA上使PIEO调度程序原型化。我们的原型使用System Verilog [49]编写，包含约1300个LOC。
我们通过以下三个指标评估原型的性能：（i）可伸缩性，（ii）计划速度和（iii）可编程性。为了作为基准，我们在FPGA上综合了开源PIFO实现[26]。与PIFO实施相同，我们使用16位rank和predicate字段。
6.1可扩展性
在本节中，我们将评估PIEO设计所消耗的逻辑和内存资源如何随着PIEO调度程序的大小而扩展。我们报告了实现组合的和基于触发器的逻辑所消耗的可用自适应逻辑模块（ALM）的百分比（图8），以及存储有序列表所消耗的可用SRAM的百分比（图9）。基线PIFO实现消耗64％的可用逻辑模块来实现大小为1 K元素的PIFO调度程序，并且它随PIFO的大小线性增长，这意味着我们无法在FPGA上安装具有2 K或更多元素的PIFO 。相反，PIEO的逻辑消耗以次线性增加（作为平方根函数），因此我们可以轻松地在FPGA上安装具有30 K元素的PIEO调度器。这是PIEO设计的直接结果，与PIFO不同，PIEO利用硬件中可用的存储器层次结构来有效地在SRAM和触发器之间分配存储和处理。最后，即使有2倍的SRAM开销（不变量1），用于PIEO实施的总SRAM消耗也相当适中（图9）。
6.2调度率
在本节中，我们评估PIEO调度程序可以做出调度决策的速率。调度速率通常是以下功能的函数：（a）调度器电路的时钟速率，以及（b）执行每个基本操作所需的周期数6。PIEO中的每个原始操作都需要4个时钟周期，图10显示了PIEO电路的时钟速率相对于PIEO尺寸的增加。时钟速率自然会随着电路复杂度的增加而降低，但是即使在80 MHz频率下并且采用非流水线设计，人们也可以每50 ns执行一次PIEO基本操作，这足以以100 Gbps的线速调度MTU大小的数据包。
通过流水线化原始操作，可以进一步提高PIEO的调度速度。在完全流水线设计中，每个时钟周期可以执行一个原始操作。但是，PIEO的设计受到SRAM访问端口数量的限制。这样，每个基本操作（周期2和4）的存储阶段都使用双端口SRAM的两个可用访问端口来读取/写入两个子列表。因此，不同基本操作的存储阶段无法并行执行，从而阻止了完整的流水线设计。原则上，通过仔细调度原始操作，仍然可以实现某种程度的流水线化，从而比非流水线设计获得更好的调度率。但是，为简单起见，我们的原型仅实现了非流水线设计，本文中的所有分析和结果均针对非流水线设计。
此外，PIEO实现的时钟速率是PIEO设计和用于运行该设计的硬件设备的函数。我们希望我们的设计能够在功能更强大的FPGA上以更高的时钟频率运行[18]，但更重要的是，在ASIC硬件上运行，因为基于ASIC的实现往往比相同设计的基于FPGA的等效实现更具性能[20]。为了用一个具体的例子来支持这一点，我们注意到PIFO在FPGA之上的设计的时钟频率为57 MHz，而不是[37]中所示的ASIC硬件上的1 GHz。在1 GHz时钟速率下，PIEO中的每个基本操作仅需4 ns。
PIEO与PIFO的权衡。与PIEO不同，PIFO的硬件设计可以完全流水线化，部分原因是它根本不访问SRAM，因此PIFO调度程序可以以比PIEO更高的速率进行调度。这是我们在PIEO硬件设计中所付出的代价，以实现比PIFO更高的可扩展性。另外，人们也可以使用PIFO的硬件设计7来实现PIEO原语，并在不影响调度速度的情况下实现比PIFO更高的可表达性，尽管规模要小得多。但是，我们认为PIEO的硬件设计需要做出权衡，因为PIEO的设计仍然非常快，可以安排在数十纳秒的时间范围内（在更高的时钟速率下甚至更少），同时还可以扩展到数以万计的流量，这在当今的多租户云网络中至关重要[31，32]。
6.3可编程性
我们在§4中表明，可以使用PIEO原语来表达各种各样的调度算法。在本节中，我们使用System Verilog作为编程语言，在我们的FPGA原型之上对两种这样的算法进行编程，即令牌桶（§4.2）和WF2Q +（§4.1）。在实践中，这两种选择的算法实现了两种最广泛使用的调度策略，即速率限制和公平排队。
我们使用原型对两级分层调度程序进行编程，其中第2级有10个节点，每个节点内有10个流，总共有100个流。我们在FPGA上实现了数据包生成器（每个流一个），以模拟流。链接速度为40 Gbps，我们按MTU粒度进行调度。对于实验，我们为层次结构中级别2的每个节点分配不同的速率限制值，并使用令牌桶算法对其进行实施。然后，使用WF2Q +算法在第2级的特定节点上公平分配速率限制值。在图11中，我们采样了一个随机的2级节点，并显示PIEO调度程序非常准确地对该节点执行了速率限制。此外，在图12中，我们表明，对于分配给所选级别2节点的每个速率限制值，PIEO调度程序非常准确地在该级别2节点内的所有流之间强制执行公平排队。
相关工作
硬件中的数据包调度。硬件中的数据包调度程序传统上是固定功能的，它们既可以实现特定的调度原语（如[31，24]中的速率限制，又可以实现[39，33]中的公平性），或者实现特定的调度算法，例如如[4]中最短的工作优先。最近，有人提出了可编程数据包调度程序（例如PIFO [37]）和通用数据包调度算法（例如UPS [27]）的建议，其目标与我们的工作非常吻合。我们讨论了PIFO和UPS的局限性在2.3节。Loom [38]在某种程度上补充了我们的工作，在NIC中提出了一种灵活的数据包调度框架，它使用新的抽象来表示调度策略，并使用有效的OS / NIC接口进行调度，同时利用PIFO调度程序来实施调度策略。原则上，诸如Loom之类的系统可以使用PIEO调度程序代替PIFO，从而实现更高的可表达性和可伸缩性。
硬件数据包调度程序的数据结构。硬件中的大多数数据包调度程序都依赖于基于FIFO的数据结构，因为它可以实现快速和可扩展的调度，但以有限的可编程性或准确性为代价（第2.3节）。优先级队列允许元素的有序调度，因此可以表达各种调度算法。P-heap [7]是硬件中基于优先级队列的可伸缩实现。不幸的是，基于堆的优先级队列无法在PIEO中有效地实现“ Extract-Out”原语。PIFO [37]还提供了优先级队列抽象，但是使用有序列表数据结构来实现它，该结构也用于实现PIEO。但是，PIFO的有序列表的硬件实现不可扩展（图8）。在本文中，我们介绍了硬件中有序列表的快速和可扩展实现。
讨论
PIEO作为抽象字典数据类型。通常，PIEO原语可以看作是抽象词典数据类型[43]，它维护（键，值）对的集合，由键索引，并允许诸如搜索，插入，删除和更新之类的操作。PIEO在硬件中提供了一种非常有效的字典数据类型实现，它可以在O（1）时间内完成所有上述操作，同时还具有可伸缩性。此外，它还可以非常有效地支持传统上认为具有挑战性的某些其他键字典操作，例如过滤范围内的一组键，因为§5中描述的PIEO实现可以自然地扩展为支持a≤key≤b形式的断言。字典数据类型是计算机科学中使用最广泛的数据类型之一，并且PIEO提供了对字典数据类型的传统硬件实现（例如哈希表和搜索树）的潜在替代方案。
结论
我们提出了一种新的数据包调度原语，称为Push-InExtract-Out（PIEO），它可以表达各种数据包调度算法。PIEO为每个元素分配一个等级和一个资格断言，这两者都可以根据调度算法的选择进行编程，并且可以在任何给定的时间安排“排名最小的合格”元素。我们提出了一种快速且可扩展的硬件设计PIEO调度程序，并在FPGA上进行原型制作。我们的原型可以安排在数十纳秒的时间范围内，同时也可以扩展到成千上万的流量。
致谢。我感谢匿名SIGCOMM审稿人和导师Anirudh Sivaraman提出的宝贵意见和建议。我还要感谢康奈尔大学，HakimWeatherspoon和Rachit Agarwal的导师，以及整个Microsoft Azure Datapath团队的宝贵讨论。这项工作得到了NSF（编号：1704742）的部分支持。
参考资料
[1] IEEE Standard 802.11Q-2005. 2005. Standardfor local and metropolitan areanetworks, Virtual Bridged Local Area Networks.(2005).
[2] Mohammad Alizadeh, Abdul Kabbani, TomEdsall, Balaji Prabhakar, Amin Vahdat, and Masato Yasuda. 2012. Less Is More:Trading a Little Bandwidth for Ultra-Low Latency in the Data Center. In NSDI.
[3] Mina Tahmasbi Arashloo, Monia Ghobadi,Jennifer Rexford, and David Walker. 2017. HotCocoa: Hardware Congestion ControlAbstractions. In HotNets.
[4] Wei Bai, Li Chen, Kai Chen, Dongsu Han,Chen Tian, and Hao Wang. 2015. Information-Agnostic Flow Scheduling forCommodity Data Centers. In NSDI.
[5] Jon C. R. Bennett and Hui Zhang. 1996.Hierarchical Packet Fair Queueing Algorithms. In SIGCOMM.
[6] Jon C. R. Bennett and Hui Zhang. 1996.WF2Q: Worst-case Fair Weighted Fair Queueing. In INFOCOMM.
[7] R. Bhagwan and B. Lin. 2000. Fast andScalable Priority Queue Architecture for High-Speed Network Switches. InINFOCOMM.
[8] Bluespec. 2019. BSV High-Level HDL.(2019). https://bluespec.com/54621-2/
[9] Pat Bosshart, Glen Gibb, Hun-Seok Kim,George Varghese, Nick McKeown, Martin Izzard, Fernando Mujica, and MarkHorowitz. 2013. Forwarding Metamorphosis: Fast Programmable Match-ActionProcessing in Hardware for SDN. In SIGCOMM.
[10] Randy Brown. 1988. Calendar queues: Afast O(1) priority queue implementation for the simulation event set problem.In Communications of the ACM.
[11] R. Colwell. 2013. The chip design gameat the end of Moore’s law. In HotChips.
[12] IEEE DCB. 2011. 802.1Qbb -Priority-based Flow Control. (2011).
http://www.ieee802.org/1/pages/802.1bb.html
[13] Alan Demers, Srinivasan Keshav, andScott Shenker. 1989. Analysis and Simulation of a Fair Queueing Algorithm. InSIGCOMM.
[14] Hadi Esmaeilzadeh, Emily Blem, ReneeSt. Amant, Karthikeyan Sankaralingam, and Doug Burger. 2011. Dark Silicon andthe End of Multicore Scaling. In ISCA.
[15] Daniel Firestone, Andrew Putnam,Sambhrama Mundkur, Derek Chiou, Alireza Dabagh, Mike Andrewartha, Hari Angepat,Vivek Bhanu, Adrian Caulfield, Eric Chung, Harish Kumar Chandrappa, SomeshChaturmohta, Matt Humphrey, Jack Lavier, Norman Lam, Fengfen Liu, KalinOvtcharov, Jitu Padhye, Gautham Popuri, Shachar Raindel, Tejas Sapre, MarkShaw, Gabriel Silva, Madhan Sivakumar, Nisheeth Srivastava, Anshuman Verma,Qasim Zuhair, Deepak Bansal, Doug Burger, Kushagra Vaid, David A. Maltz, andAlbert Greenberg. 2018. Azure Accelerated Networking: SmartNICs in the PublicCloud. In NSDI.
[16] Matthew P. Grosvenor, Malte Schwarzkopf,Ionel Gog, Robert N. M. Watson, Andrew W. Moore, Steven Hand, and JonCrowcroft. 2015. Queues Don’t Matter When You Can JUMP Them!. In NSDI.
[17] Intel. 2015. Stratix V FPGA. (2015).https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/stratix-v/stx5_51001.pdf
[18] Intel. 2018. Stratix 10 FPGA. (2018).https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/hb/stratix-10/s10-overview.pdf
[19] Keon Jang, Justine Sherry, HiteshBallani, and Toby Moncaster. 2015. Silo: Predictable Message Latency in theCloud. In SIGCOMM.
[20] Ian Kuon and Jonathan Rose. 2007.Measuring the Gap Between FPGAs and ASICs. IEEE Transactions on Computer-AidedDesign of Integrated Circuits and Systems 26, 2 (Feb. 2007).
[21] He Liu, Matthew K. Mukerjee, ConglongLi, Nicolas Feltman, George Papen, Stefan Savage, Srinivasan Seshan, GeoffreyM. Voelker, David G. Andersen, Michael Kaminsky, George Porter, and Alex C.Snoeren. 2015. Scheduling techniques for hybrid circuit/packet networks. InCoNEXT.
[22] Rob McGuinness and George Porter.2018. Evaluating the Performance of Software NICs for 100-Gb/s DatacenterTraffic Control. In ANCS.
[23] P McKenney. 1990. Stochastic FairnessQueuing. In INFOCOMM.
[24] Mellanox. 2019. ConnectX-4. (2019).http://www.mellanox.com/page/products_dyn?product_family=204&mtag=connectx_4_en_card
[25] William M. Mellette, Rob McGuinness,Arjun Roy, Alex Forencich, George Papen, Alex C. Snoeren, and George Porter.2017. RotorNet: A scalable, low-complexity, optical datacenter network. InSIGCOMM.
[26] MIT. 2019. PIFO implementation.(2019).https://github.com/programmable-scheduling/pifo-hardware/blob/master/src/rtl/design/pifo.v
[27] Radhika Mittal, Rachit Agarwal, SylviaRatnasamy, and Scott Shenker. 2016. Universal Packet Scheduling. In NSDI.
[28] Radhika Mittal, Terry Lam, NanditaDukkipati, Emily Blem, Hassan Wassel, Monia Ghobadi, Amin Vahdat, Yaogong Wang,David Wetherall, and David Zats. 2015. TIMELY: RTT-based Congestion Control forthe Datacenter. In Sigcomm.
[29] Sung-Whan Moon, J. Rexford, and K.G.Shin. 2000. Scalable hardware priority queue architectures for high-speedpacket switches. IEEE Trans. Comput. 49, 11 (2000), 1215–1227.
[30] Jonathan Perry, Amy Ousterhout, HariBalakrishnan, Devavrat Shah, and Hans Fugal. 2014. Fastpass: A Centralized"Zero-queue" Datacenter Network. In SIGCOMM.
[31] Sivasankar Radhakrishnan, Yilong Geng,Vimalkumar Jeyakumar, Abdul Kabbani, George Porter, and Amin Vahdat. 2014.SENIC: Scalable NIC for End-Host Rate Limiting. In NSDI.
[32] Ahmed Saeed, Nandita Dukkipati,Vytautas Valancius, Vinh The Lam, Carlo Contavalli, and Amin Vahdat. 2017.Carousel: Scalable Traffic Shaping at End Hosts. In SIGCOMM.
[33] Naveen Kr. Sharma, Ming Liu, KishoreAtreya, and Arvind Krishnamurthy. 2018. Approximating Fair Queueing onReconfigurable Switches. In NSDI.
[34] M Shreedhar and G Varghese. 1996.Efficient Fair Queuing using Deficit Round Robin. IEEE/ACM Transactions onNetworking (ToN) 4, 3 (1996), 375–385.
[35] Vishal Shrivastav, Asaf Valadarsky,Hitesh Ballani, Paolo Costa, Ki Suh Lee, Han Wang, Rachit Agarwal, and HakimWeatherspoon. 2019. Shoal: A Network Architecture for Disaggregated Racks. InNSDI.
[36] A Sivaraman, A Cheung, M Budiu, C Kim,M Alizadeh, H Balakrishnan, G Varghese, N McKeown, and S Licking. 2016. PacketTransactions: High-Level Programming for Line-Rate Switches. In SIGCOMM.
[37] Anirudh Sivaraman, SuvinaySubramanian, Mohammad Alizadeh, Sharad Chole, Shang-Tse Chuang, Anurag Agrawal,Hari Balakrishnan, Tom Edsall, Sachin Katti, and Nick McKeown. 2016.Programmable Packet Scheduling at Line Rate. In SIGCOMM.
[38] Brent Stephens, Aditya Akella, andMichael Swift. 2019. Loom: Flexible and Efficient NIC Packet Scheduling. InNSDI.
[39] Brent Stephens, Arjun Singhvi, AdityaAkella, and Michael Swift. 2017. Titan: Fair Packet Scheduling for CommodityMultiqueue NICs. In ATC.
[40] George Varghese and Anthony Lauck.1987. Hashed and Hierarchical Timing Wheels: Efficient Data Structures forImplementing a Timer Facility. In SOSP.
[41] Bhanu Chandra Vattikonda, GeorgePorter, Amin Vahdat, and Alex C. Snoeren. 2012. Practical TDMA for datacenterethernet. In EuroSys.
[42] Shaileshh Bojja Venkatakrishnan,Mohammad Alizadeh, and Pramod Viswanath. 2016. Costly circuits, submodularschedules and approximate caratheodory theorems. In SIGMETRICS.
[43] Wikipedia. 2019. Abstract DictionaryData Type. (2019). https://en.wikipedia.org/wiki/Associative_array
[44] Wikipedia. 2019. Earliest DeadlineFirst. (2019). https://en.wikipedia.org/wiki/Earliest_deadline_first_scheduling
[45] Wikipedia. 2019. Least Slack TimeFirst. (2019). https://en.wikipedia.org/wiki/Least_slack_time_scheduling
[46] Wikipedia. 2019. openCL. (2019).https://en.wikipedia.org/wiki/OpenCL
[47] Wikipedia. 2019. Shortest Job First.(2019). https://en.wikipedia.org/wiki/Shortest_job_next
[48] Wikipedia. 2019. Shortest RemainingTime First. (2019). https://en.wikipedia.org/wiki/Shortest_remaining_time
[49] Wikipedia. 2019. System Verilog.(2019). https://en.wikipedia.org/wiki/SystemVerilog
[50] Wikipedia. 2019. Token Bucket. (2019).https://en.wikipedia.org/wiki/Token_bucket
[51] Christo Wilson, Hitesh Ballani, ThomasKaragiannis, and Ant Rowtron. 2011. Better Never Than Late: Meeting Deadlinesin Datacenter Networks. In SIGCOMM.
[52] Jun Xu and Richard J. Lipton. 2002. Onfundamental tradeoffs between delay bounds and computational complexity inpacket scheduling algorithms. In SIGCOMM.
[53] H Zhang and D Ferrari. 1994.Rate-Controlled Service Disciplines. Journal of High Speed Networks 3, 4(1994), 389–412