關(guān)鍵詞：端上擁塞控制 接收端驅(qū)動 短流
1.陌生名詞
heavy-tailed：重尾分布淡溯，尾部比指數(shù)分布大
tail latency：少量響應(yīng)的延遲高于均值函荣，這些響應(yīng)稱為尾延遲
downlink：邊緣終端或節(jié)點從網(wǎng)絡(luò)核心或從更高級別的網(wǎng)絡(luò)節(jié)點（例如路由器和服務(wù)器）接收數(shù)據(jù)
incast：是指一種多對一的通信模式
2.目標(biāo)
在高網(wǎng)絡(luò)負(fù)載下使用當(dāng)前網(wǎng)絡(luò)硬件為短消息提供盡可能低的延遲（消息延遲而不是包延遲）
3.核心挑戰(zhàn)與要點
消除短消息的排隊時延翠拣。
- 不去調(diào)度每一個包：理想的調(diào)度有——基于中央仲裁器/receiver的調(diào)度按摘，短消息等待調(diào)度需要花費1.5RTTs朗徊，而直接發(fā)送只需要0.5RTT
為盡可能低的延遲，必須盲目傳輸短消息娜庇，而不考慮潛在的擁塞拇泛。 通常滨巴，發(fā)送方必須盲目傳輸足夠的字節(jié)以覆蓋接收方的往返時間（包括兩端的軟件開銷）。在這段時間內(nèi)俺叭，接收機可以返回明確的調(diào)度信息以控制未來的傳輸恭取，而不會引入額外的延遲。
buffer的必要性和困擾：盲目傳輸意味著當(dāng)多個發(fā)送者發(fā)送到同一個接收者時熄守，沒有任何協(xié)議可以在沒有緩沖的情況下達到最小延遲蜈垮。然而緩沖區(qū)也會帶來時延，但這是不可避免的裕照。
充分利用In-network的優(yōu)先級：現(xiàn)代交換機中的每個輸出端口支持少量的優(yōu)先級（通常為8）攒发，每個優(yōu)先級有一個隊列。
基于交換機的優(yōu)先級的調(diào)度方案可以用來改善消息延遲晋南，Homa實現(xiàn)了近似SRPT（最短剩余處理時間優(yōu)先惠猿，只是思想，不是實現(xiàn)的算法）的設(shè)計
- 最大限度地利用有限的優(yōu)先權(quán)需要接收方的控制负间。
接收機確定優(yōu)先級偶妖。 除了盲傳輸之外，接收方還知道從TOR交換機downlink的爭奪帶寬的確切消息集政溃。 結(jié)果趾访，接收方可以最好地決定對每個傳入數(shù)據(jù)包使用哪個優(yōu)先級。 此外董虱，接收器可以通過將優(yōu)先級與數(shù)據(jù)包調(diào)度機制集成在一起來增強優(yōu)先級的有效性
- 接收方必須動態(tài)分配優(yōu)先級扼鞋。
每個接收方使用兩種機制為其自己的下行鏈路分配優(yōu)先級。
- 對于大于RTTbytes的消息愤诱，接收者將根據(jù)入站消息的確切集合云头，將每個數(shù)據(jù)包的優(yōu)先級動態(tài)地傳達給其發(fā)送者。 這幾乎消除了所有搶占延遲淫半。
- 對于盲目發(fā)送的短消息溃槐，發(fā)送者無法知道接收者的其他入站消息。 即使這樣撮慨，接收方仍可以根據(jù)其最近的工作量提前向發(fā)送方提供指導(dǎo)竿痰。
- 接收方必須以可控的方式過量使用其下行鏈路脆粥。
使用來自接收方的授權(quán)來調(diào)度數(shù)據(jù)包傳輸會減少緩沖區(qū)占用砌溺，但這帶來了新的挑戰(zhàn)：接收方可能將授權(quán)發(fā)送給未及時向其發(fā)送的發(fā)送方。例如变隔，當(dāng)一個發(fā)送者有多個接收者的消息時规伐，如果一個以上的接收者決定發(fā)送授權(quán)，則發(fā)送者無法將數(shù)據(jù)包全速發(fā)送給所有此類接收者匣缘。這浪費了接收器下行鏈路的帶寬猖闪。
為了應(yīng)對這一挑戰(zhàn)鲜棠，Homa的接收者有意通過同時授予少量發(fā)送者來過度分配其下行鏈路； 這樣可以在接收方的TOR處實現(xiàn)受控的數(shù)據(jù)包排隊培慌，但對于實現(xiàn)高網(wǎng)絡(luò)利用率和高負(fù)載下的最佳消息延遲至關(guān)重要
- 發(fā)送方也需要SRPT
排隊可能在發(fā)送者和接收者處累積豁陆，這會導(dǎo)致短消息的長時間延遲。對于同一目的地通常會建立一條流吵护，流內(nèi)的包順序發(fā)送盒音，會導(dǎo)致短消息在同一目的地的長消息后面的字節(jié)流中排隊。對于低尾latency馅而，發(fā)送方必須確保短消息不會被長消息延遲祥诽。
4.基本設(shè)計
Homa的四個關(guān)鍵設(shè)計原則：
盲目發(fā)送短消息
使用網(wǎng)絡(luò)優(yōu)先級
結(jié)合接收方驅(qū)動的速率控制來動態(tài)分配優(yōu)先級
接收方下行鏈路的受控的超量使用
Homa將消息分為兩部分：初始unscheduled部分，然后是scheduled部分瓮恭。
發(fā)送方立即發(fā)送unscheduled的數(shù)據(jù)包（RTTbytes）雄坪，但直到接收方指示，它才發(fā)送scheduled數(shù)據(jù)包屯蹦。 unscheduled數(shù)據(jù)包的到來使接收方意識到了該消息维哈。
接收者通過為每個scheduled數(shù)據(jù)包發(fā)送一個授權(quán)數(shù)據(jù)包來請求調(diào)度數(shù)據(jù)包的傳輸。 Homa的接收者動態(tài)設(shè)置scheduled數(shù)據(jù)包的優(yōu)先級颇玷，并定期將一組閾值通知發(fā)送方笨农，以設(shè)置unscheduled數(shù)據(jù)包的優(yōu)先級。 最后帖渠，在沒有響應(yīng)的發(fā)送者的情況下谒亦，接收者實施受控的過量使用以維持高利用率。 最終結(jié)果是使用少量優(yōu)先級隊列精確近似實現(xiàn)了SRPT調(diào)度策略空郊。
5.詳細(xì)解讀
Key Word:接收方驅(qū)動的份招；它是面向消息的(而不是面向流的)；它是無連接的狞甚；它不使用顯式的確認(rèn)锁摔；以及它至少實現(xiàn)一次語義，而不是更傳統(tǒng)的至多一次語義哼审。
Homa使用了四種數(shù)據(jù)包類型:
Data:從發(fā)送方發(fā)送到接收方谐腰。包含消息中的字節(jié)范圍，由偏移量和長度定義涩盾。還指示消息的總長度
Grant:從接收者發(fā)送到發(fā)送者十气。指示發(fā)送方現(xiàn)在可以將消息中的所有字節(jié)傳輸?shù)浇o定的偏移量，并指定要使用的優(yōu)先級
Resend:從接收者發(fā)送到發(fā)送者春霍。表示發(fā)送方應(yīng)該再次發(fā)送消息中給定的字節(jié)范圍內(nèi)的內(nèi)容
Busy:從發(fā)送方發(fā)送到接收方砸西。指示響應(yīng)ReSend將被延遲（發(fā)送方正忙于傳輸高優(yōu)先級消息，或者RPC操作仍在執(zhí)行）；用于防止超時
5.1無連接的RPC
Homa的無連接方法意味著服務(wù)器上保留的狀態(tài)由活動RPC的數(shù)量決定芹枷，而不是由客戶端的總數(shù)決定衅疙，同時保證了同一個sender&receiver pair之前所有消息的獨立傳遞，對于降低尾部延遲至關(guān)重要鸳慈。
5.2發(fā)送方策略
當(dāng)消息到達發(fā)送方的傳輸模塊時饱溢，Homa將其分為兩部分：初始unscheduled部分（第一個RTTbytes字節(jié)），然后是scheduled部分走芋。發(fā)送方使用一個或多個DATA數(shù)據(jù)包立即發(fā)送unscheduled字節(jié)理朋。 在接收方使用GRANTs數(shù)據(jù)包明確請求之前，不會發(fā)送scheduled的字節(jié)绿聘。
每個DATA數(shù)據(jù)包都有一個優(yōu)先級嗽上，該優(yōu)先級由接收方?jīng)Q定，發(fā)送方為其輸出數(shù)據(jù)包實現(xiàn)SRPT：如果來自多個消息的DATA數(shù)據(jù)包準(zhǔn)備好同時傳輸熄攘，則該消息的數(shù)據(jù)包最少其余字節(jié)先發(fā)送兽愤。 發(fā)送方在調(diào)度其數(shù)據(jù)包傳輸時不考慮DATA數(shù)據(jù)包中的優(yōu)先級（DATA數(shù)據(jù)包中的優(yōu)先級用在到達接收方的downlinks）。GRANT和RESEND控制數(shù)據(jù)包總是比DATA數(shù)據(jù)包具有更高的優(yōu)先級挪圾。
5.3流控制
實現(xiàn)在接收端:如果到來的DATA包過多浅萧，那么根據(jù)優(yōu)先級接受，同時接收端返回GRANT的時間會延后哲思，這意味著每個傳入的消息可以占用接收方TOR中最多RRTbyte大小的緩沖區(qū)空間洼畅。
此外消息的數(shù)據(jù)包可以以任何順序到達；接收方使用每個包中的偏移量對它們進行整理棚赔。這使得Homa可以使用每包多路徑路由來最小化網(wǎng)絡(luò)核心的擁塞帝簇。
5.4 包優(yōu)先級
接收方確定其所有傳入數(shù)據(jù)包的優(yōu)先級，以便近似于SRPT策略靠益。它對unscheduled和scheduled的數(shù)據(jù)包使用不同的機制丧肴。
對于未調(diào)度的數(shù)據(jù)包，接收方預(yù)先分配優(yōu)先級胧后。它使用最近的流量模式來選擇優(yōu)先級分配芋浮，并通過將這些信息打包到其他數(shù)據(jù)包上，將這些信息傳播給發(fā)送者壳快。每個sender保留每個receiver的最新分配優(yōu)先級（每個接收器占用十幾個字節(jié)）纸巷，并在傳遞unscheduled的數(shù)據(jù)包時使用這些信息。如果receiver的接收的通信量發(fā)生變化眶痰，它將在下一次與每個發(fā)送方通信時分發(fā)新的優(yōu)先級分配瘤旨。
還沒讀懂3.4
5.5 overcommitment
最初的設(shè)計中，每個接收器一次只允許一條active消息凛驮。如果一個接收者有多個部分接收到的消息裆站，它只向其中的最高優(yōu)先級發(fā)送授權(quán)条辟；一旦它授予了最高優(yōu)先級消息的所有字節(jié)黔夭，它就開始向下一個最高優(yōu)先級消息授予權(quán)限宏胯，依此類推。這種方法的理由是最小化緩沖區(qū)占用本姥，實現(xiàn)從運行到完成肩袍，而不是循環(huán)調(diào)度。但由于發(fā)送者并不總是立即響應(yīng)grant婚惫，所以網(wǎng)絡(luò)未得到充分利用氛赐。
接收器沒有辦法知道某個特定的發(fā)送方是否會響應(yīng)授權(quán)，因此保持downlink充分利用的唯一方法是過度提交：一個receiver一次向多個sender授權(quán)先舷，即使它的downlink一次只能支持一個傳輸艰管。使用這種方法，如果一個sender沒有響應(yīng)蒋川，那么downlink可以用于另一個sender牲芋。如果多個sender同時響應(yīng)，優(yōu)先級機制確保首先傳遞最短的消息,來自其他消息的包將被緩沖在TOR中
使用“degree of overcommitment”這個術(shù)語來表示給定接收器上一次可以激活的消息的最大數(shù)量捺球。更高程度的degree of overcommitment使用降低了浪費帶寬的可能性缸浦，但它會在TOR中消耗更多的緩沖空間（每個活動消息最多為RTTbytes），并且會導(dǎo)致消息之間更多的循環(huán)調(diào)度氮兵，從而增加存儲空間完成時間裂逐。
5.6 incast
Homa通過計算每個節(jié)點的未完成的rpc來檢測即將到來的incasts。一旦這個數(shù)字超過一個閾值泣栈，新的RPC就會被標(biāo)記上一個特殊的標(biāo)志卜高，使服務(wù)器在響應(yīng)消息中對unscheduled字節(jié)使用一個更低的限制（幾百字節(jié)）。較小的響應(yīng)仍將很快通過南片，但較大的響應(yīng)將由接收方調(diào)度篙悯；
Incast也可能以不可預(yù)測的方式發(fā)生；例如铃绒，多臺計算機可能同時決定向單個服務(wù)器發(fā)出請求鸽照。然而，許多這樣的請求不太可能緊密地同步颠悬，從而導(dǎo)致不必要的問題矮燎。如果發(fā)生這種情況，Homa對緩沖空間的有效利用仍然允許它支持?jǐn)?shù)百個同時到達而不丟失數(shù)據(jù)包赔癌。此外诞外，在很多請求被發(fā)出之前就完成了，所以這種情況存在的概率不太高
5.6 丟包與重傳
丟包有兩個原因：網(wǎng)絡(luò)損壞和緩沖區(qū)溢出灾票。前者非常罕見峡谊，而homa減少了很多緩沖區(qū)的使用，使得緩沖區(qū)溢出也變得罕見〖让牵基于這個背景濒析，Homa對丟包處理進行了簡化
如果經(jīng)過一段很長的時間（幾毫秒）而沒有其他數(shù)據(jù)包到達消息，receiver將發(fā)送一個重新發(fā)送數(shù)據(jù)包啥纸，標(biāo)識丟失字節(jié)的第一個范圍号杏；sender將重新傳輸這些字節(jié)。（與tcp收到后返回ACK斯棒，發(fā)送方負(fù)責(zé)檢測重發(fā)不同）
如果RPC請求的所有初始數(shù)據(jù)包都丟失了盾致，服務(wù)器將不知道該消息，因此它不會發(fā)出消息重新發(fā)送荣暮。但是庭惜，客戶端將在響應(yīng)消息上超時，并且它將為響應(yīng)發(fā)送一個RESEND（即使請求尚未完全傳輸穗酥，它也會這樣做）蜈块。當(dāng)服務(wù)器接收到一個帶有未知RPCid的響應(yīng)的RESEND時，它假定請求消息一定已丟失迷扇，并結(jié)束對請求的第一個RTTbytes的重新發(fā)送.
如果多次重發(fā)無響應(yīng)百揭，將會向上層調(diào)用方報錯
創(chuàng)新點
-
使用現(xiàn)代網(wǎng)絡(luò)交換機提供的優(yōu)先級隊列。為了充分利用有限的優(yōu)先級隊列數(shù)
- Homa對接收者動態(tài)分配優(yōu)先級蜓席，并將優(yōu)先級與pHost和NDP等接收者驅(qū)動的流量控制機制相結(jié)合器一。
-
使用控制承諾（controlled over commitment），即接收者允許少數(shù)發(fā)送者同時發(fā)送厨内。
- 稍微超量使用接收器下行鏈路這種方式使Homa有效地使用網(wǎng)絡(luò)帶寬：Homa可以比pFabric[4]祈秕、PIAS、pHost和NDP高2-33%地維持網(wǎng)絡(luò)負(fù)載雏胃。Homa限制了超量使用请毛，并將其與優(yōu)先級機制集成，以防止短消息排隊瞭亮。
-
Homa還具有其他特性
使用基于消息的體系結(jié)構(gòu)方仿，而不是流式傳輸方法:這消除了發(fā)送方的首行阻塞，并將尾部延遲比流式傳輸（如TCP）減少了100倍统翩。
Homa是無連接的仙蚜，減少了在大規(guī)模應(yīng)用上的連接狀態(tài)。
它沒有明確的確認(rèn)厂汗，從而減少了小消息的開銷委粉，并且實現(xiàn)了至少一次而不是一次的語義
性能提升
與之前的接收器驅(qū)動相比，Homa的優(yōu)先級機制提高了尾部延遲2-16倍接近
與發(fā)送方驅(qū)動的優(yōu)先級機制（如asPIAS[6]）相比娶桦，Homa提供了更好的SRPT（最短剩余處理時間優(yōu)先）的近似值贾节；這比PIA減少了0-3倍的尾部延遲
#涉及技術(shù)
pHost：最接近Homa的先驗方案汁汗，是使用接收機驅(qū)動方法近似SRPT的一個例子
主要機制是數(shù)據(jù)包調(diào)度：發(fā)送者盲目地發(fā)送每個消息的第一個RTTbytes，但是之后的包只在響應(yīng)來自接收方的顯式請求時才被傳輸栗涂。接收機調(diào)度授權(quán)來實現(xiàn)SRPT知牌，同時控制分組的流入以匹配下行鏈路的速度
-
不足
pHost僅有限地使用優(yōu)先級：它統(tǒng)計地為所有盲傳輸分配一個高優(yōu)先級，為所有調(diào)度的數(shù)據(jù)包分配一個較低的優(yōu)先級戴差。這在兩個方面影響了它近似SRPT的能力。首先铛嘱，它將所有盲傳輸捆綁到一個單一優(yōu)先級中暖释。雖然這對于大多數(shù)字節(jié)來自大消息（圖1中的W4-W5）的工作負(fù)載是有原因的，但是對于大量字節(jié)被盲目傳輸?shù)墓ぷ髫?fù)載（W1-W3）來說墨吓，這是有問題的
第二球匕，對于比RTTbytes長的消息，pHost不能立即搶占一個較大的消息來替換較短的消息帖烘。同樣亮曹，問題的根源是pHost將所有這些消息捆綁到一個優(yōu)先級中，這會導(dǎo)致排隊延遲秘症。我們將在§3.4中說明照卦，這種情況會導(dǎo)致延遲，這會損害延遲乡摹，特別是對于持續(xù)幾個rtt的中等大小的消息
