关键词：端上拥塞控制 接收端驱动 短流
1.陌生名词
heavy-tailed：重尾分布，尾部比指数分布大
tail latency：少量响应的延迟高于均值，这些响应称为尾延迟
downlink：边缘终端或节点从网络核心或从更高级别的网络节点（例如路由器和服务器）接收数据
incast：是指一种多对一的通信模式
2.目标
在高网络负载下使用当前网络硬件为短消息提供尽可能低的延迟（消息延迟而不是包延迟）
3.核心挑战与要点
消除短消息的排队时延。
- 不去调度每一个包：理想的调度有——基于中央仲裁器/receiver的调度，短消息等待调度需要花费1.5RTTs，而直接发送只需要0.5RTT
为尽可能低的延迟，必须盲目传输短消息，而不考虑潜在的拥塞。 通常，发送方必须盲目传输足够的字节以覆盖接收方的往返时间（包括两端的软件开销）。在这段时间内，接收机可以返回明确的调度信息以控制未来的传输，而不会引入额外的延迟。
-
buffer的必要性和困扰：盲目传输意味着当多个发送者发送到同一个接收者时，没有任何协议可以在没有缓冲的情况下达到最小延迟。然而缓冲区也会带来时延，但这是不可避免的。
-
充分利用In-network的优先级：现代交换机中的每个输出端口支持少量的优先级（通常为8），每个优先级有一个队列。
基于交换机的优先级的调度方案可以用来改善消息延迟，Homa实现了近似SRPT（最短剩余处理时间优先，只是思想，不是实现的算法）的设计
- 最大限度地利用有限的优先权需要接收方的控制。
接收机确定优先级。 除了盲传输之外，接收方还知道从TOR交换机downlink的争夺带宽的确切消息集。 结果，接收方可以最好地决定对每个传入数据包使用哪个优先级。 此外，接收器可以通过将优先级与数据包调度机制集成在一起来增强优先级的有效性
- 接收方必须动态分配优先级。
每个接收方使用两种机制为其自己的下行链路分配优先级。
- 对于大于RTTbytes的消息，接收者将根据入站消息的确切集合，将每个数据包的优先级动态地传达给其发送者。 这几乎消除了所有抢占延迟。
- 对于盲目发送的短消息，发送者无法知道接收者的其他入站消息。 即使这样，接收方仍可以根据其最近的工作量提前向发送方提供指导。
- 接收方必须以可控的方式过量使用其下行链路。
使用来自接收方的授权来调度数据包传输会减少缓冲区占用，但这带来了新的挑战：接收方可能将授权发送给未及时向其发送的发送方。例如，当一个发送者有多个接收者的消息时，如果一个以上的接收者决定发送授权，则发送者无法将数据包全速发送给所有此类接收者。这浪费了接收器下行链路的带宽。
为了应对这一挑战，Homa的接收者有意通过同时授予少量发送者来过度分配其下行链路； 这样可以在接收方的TOR处实现受控的数据包排队，但对于实现高网络利用率和高负载下的最佳消息延迟至关重要
- 发送方也需要SRPT
排队可能在发送者和接收者处累积，这会导致短消息的长时间延迟。对于同一目的地通常会建立一条流，流内的包顺序发送，会导致短消息在同一目的地的长消息后面的字节流中排队。对于低尾latency，发送方必须确保短消息不会被长消息延迟。
4.基本设计
Homa的四个关键设计原则：
-
盲目发送短消息
-
使用网络优先级
-
结合接收方驱动的速率控制来动态分配优先级
-
接收方下行链路的受控的超量使用
Homa将消息分为两部分：初始unscheduled部分，然后是scheduled部分。
发送方立即发送unscheduled的数据包（RTTbytes），但直到接收方指示，它才发送scheduled数据包。 unscheduled数据包的到来使接收方意识到了该消息。
接收者通过为每个scheduled数据包发送一个授权数据包来请求调度数据包的传输。 Homa的接收者动态设置scheduled数据包的优先级，并定期将一组阈值通知发送方，以设置unscheduled数据包的优先级。 最后，在没有响应的发送者的情况下，接收者实施受控的过量使用以维持高利用率。 最终结果是使用少量优先级队列精确近似实现了SRPT调度策略。
5.详细解读
Key Word:接收方驱动的；它是面向消息的(而不是面向流的)；它是无连接的；它不使用显式的确认；以及它至少实现一次语义，而不是更传统的至多一次语义。
Homa使用了四种数据包类型:
-
Data:从发送方发送到接收方。包含消息中的字节范围，由偏移量和长度定义。还指示消息的总长度
-
Grant:从接收者发送到发送者。指示发送方现在可以将消息中的所有字节传输到给定的偏移量，并指定要使用的优先级
-
Resend:从接收者发送到发送者。表示发送方应该再次发送消息中给定的字节范围内的内容
-
Busy:从发送方发送到接收方。指示响应ReSend将被延迟（发送方正忙于传输高优先级消息，或者RPC操作仍在执行）；用于防止超时
5.1无连接的RPC
Homa的无连接方法意味着服务器上保留的状态由活动RPC的数量决定，而不是由客户端的总数决定，同时保证了同一个sender&receiver pair之前所有消息的独立传递，对于降低尾部延迟至关重要。
5.2发送方策略
当消息到达发送方的传输模块时，Homa将其分为两部分：初始unscheduled部分（第一个RTTbytes字节），然后是scheduled部分。发送方使用一个或多个DATA数据包立即发送unscheduled字节。 在接收方使用GRANTs数据包明确请求之前，不会发送scheduled的字节。
每个DATA数据包都有一个优先级，该优先级由接收方决定，发送方为其输出数据包实现SRPT：如果来自多个消息的DATA数据包准备好同时传输，则该消息的数据包最少其余字节先发送。 发送方在调度其数据包传输时不考虑DATA数据包中的优先级（DATA数据包中的优先级用在到达接收方的downlinks）。GRANT和RESEND控制数据包总是比DATA数据包具有更高的优先级。
5.3流控制
实现在接收端:如果到来的DATA包过多，那么根据优先级接受，同时接收端返回GRANT的时间会延后，这意味着每个传入的消息可以占用接收方TOR中最多RRTbyte大小的缓冲区空间。
此外消息的数据包可以以任何顺序到达；接收方使用每个包中的偏移量对它们进行整理。这使得Homa可以使用每包多路径路由来最小化网络核心的拥塞。
5.4 包优先级
接收方确定其所有传入数据包的优先级，以便近似于SRPT策略。它对unscheduled和scheduled的数据包使用不同的机制。
对于未调度的数据包，接收方预先分配优先级。它使用最近的流量模式来选择优先级分配，并通过将这些信息打包到其他数据包上，将这些信息传播给发送者。每个sender保留每个receiver的最新分配优先级（每个接收器占用十几个字节），并在传递unscheduled的数据包时使用这些信息。如果receiver的接收的通信量发生变化，它将在下一次与每个发送方通信时分发新的优先级分配。
还没读懂3.4
5.5 overcommitment
最初的设计中，每个接收器一次只允许一条active消息。如果一个接收者有多个部分接收到的消息，它只向其中的最高优先级发送授权；一旦它授予了最高优先级消息的所有字节，它就开始向下一个最高优先级消息授予权限，依此类推。这种方法的理由是最小化缓冲区占用，实现从运行到完成，而不是循环调度。但由于发送者并不总是立即响应grant，所以网络未得到充分利用。
接收器没有办法知道某个特定的发送方是否会响应授权，因此保持downlink充分利用的唯一方法是过度提交：一个receiver一次向多个sender授权，即使它的downlink一次只能支持一个传输。使用这种方法，如果一个sender没有响应，那么downlink可以用于另一个sender。如果多个sender同时响应，优先级机制确保首先传递最短的消息,来自其他消息的包将被缓冲在TOR中
使用“degree of overcommitment”这个术语来表示给定接收器上一次可以激活的消息的最大数量。更高程度的degree of overcommitment使用降低了浪费带宽的可能性，但它会在TOR中消耗更多的缓冲空间（每个活动消息最多为RTTbytes），并且会导致消息之间更多的循环调度，从而增加存储空间完成时间。
5.6 incast
Homa通过计算每个节点的未完成的rpc来检测即将到来的incasts。一旦这个数字超过一个阈值，新的RPC就会被标记上一个特殊的标志，使服务器在响应消息中对unscheduled字节使用一个更低的限制（几百字节）。较小的响应仍将很快通过，但较大的响应将由接收方调度；
Incast也可能以不可预测的方式发生；例如，多台计算机可能同时决定向单个服务器发出请求。然而，许多这样的请求不太可能紧密地同步，从而导致不必要的问题。如果发生这种情况，Homa对缓冲空间的有效利用仍然允许它支持数百个同时到达而不丢失数据包。此外，在很多请求被发出之前就完成了，所以这种情况存在的概率不太高
5.6 丢包与重传
丢包有两个原因：网络损坏和缓冲区溢出。前者非常罕见，而homa减少了很多缓冲区的使用，使得缓冲区溢出也变得罕见。基于这个背景，Homa对丢包处理进行了简化
如果经过一段很长的时间（几毫秒）而没有其他数据包到达消息，receiver将发送一个重新发送数据包，标识丢失字节的第一个范围；sender将重新传输这些字节。（与tcp收到后返回ACK，发送方负责检测重发不同）
如果RPC请求的所有初始数据包都丢失了，服务器将不知道该消息，因此它不会发出消息重新发送。但是，客户端将在响应消息上超时，并且它将为响应发送一个RESEND（即使请求尚未完全传输，它也会这样做）。当服务器接收到一个带有未知RPCid的响应的RESEND时，它假定请求消息一定已丢失，并结束对请求的第一个RTTbytes的重新发送.
如果多次重发无响应，将会向上层调用方报错
创新点
-
使用现代网络交换机提供的优先级队列。为了充分利用有限的优先级队列数
- Homa对接收者动态分配优先级，并将优先级与pHost和NDP等接收者驱动的流量控制机制相结合。
-
使用控制承诺（controlled over commitment），即接收者允许少数发送者同时发送。
- 稍微超量使用接收器下行链路这种方式使Homa有效地使用网络带宽：Homa可以比pFabric[4]、PIAS、pHost和NDP高2-33%地维持网络负载。Homa限制了超量使用，并将其与优先级机制集成，以防止短消息排队。
-
Homa还具有其他特性
-
使用基于消息的体系结构，而不是流式传输方法:这消除了发送方的首行阻塞，并将尾部延迟比流式传输（如TCP）减少了100倍。
-
Homa是无连接的，减少了在大规模应用上的连接状态。
-
它没有明确的确认，从而减少了小消息的开销，并且实现了至少一次而不是一次的语义
-
性能提升
-
与之前的接收器驱动相比，Homa的优先级机制提高了尾部延迟2-16倍接近
-
与发送方驱动的优先级机制（如asPIAS[6]）相比，Homa提供了更好的SRPT（最短剩余处理时间优先）的近似值；这比PIA减少了0-3倍的尾部延迟
#涉及技术
pHost：最接近Homa的先验方案，是使用接收机驱动方法近似SRPT的一个例子
-
主要机制是数据包调度：发送者盲目地发送每个消息的第一个RTTbytes，但是之后的包只在响应来自接收方的显式请求时才被传输。接收机调度授权来实现SRPT，同时控制分组的流入以匹配下行链路的速度
-
不足
-
pHost仅有限地使用优先级：它统计地为所有盲传输分配一个高优先级，为所有调度的数据包分配一个较低的优先级。这在两个方面影响了它近似SRPT的能力。首先，它将所有盲传输捆绑到一个单一优先级中。虽然这对于大多数字节来自大消息（图1中的W4-W5）的工作负载是有原因的，但是对于大量字节被盲目传输的工作负载（W1-W3）来说，这是有问题的
-
第二，对于比RTTbytes长的消息，pHost不能立即抢占一个较大的消息来替换较短的消息。同样，问题的根源是pHost将所有这些消息捆绑到一个优先级中，这会导致排队延迟。我们将在§3.4中说明，这种情况会导致延迟，这会损害延迟，特别是对于持续几个rtt的中等大小的消息
-
网友评论