2020年5月總結（網絡擁塞控制和增強學習初瞰）

起

在之前4月的時候，一天看到了清華深圳研究所學生院夏樹濤老師的招生通告，于是就向其發了封履歷，結果到了4.30号的時候，我驚訝的發現竟然收到了回複。老師給了一個project，要先做完project然後再進一步面試，project要求一個月做完，之後再安排複試。

之後這個5月其實主要精力就放在了做這個project上，結果就是直到今天31号，離完成差了十萬八千裡，剛剛發郵件過去承認了自己的失敗。具體的時間分布和原因分析我放到了結尾。

夏老師的研究方向還是比較廣，project上有10個課題可以選，分别是自拟、深度學習資料增廣，深度學習模型輕量化，對抗樣本，圖像超分辨，機器學習中的安全和隐私保護，乘積量化哈希與圖像檢索，深度壓縮感覺，計算機網絡智能擁塞控制和計算機網絡智能視訊傳輸。

我選的是計算機網絡智能擁塞控制，具體要求如下：

可以一眼看出來的不是很好做hhh，各個課題的任務量是差不多的。

TCP擁塞控制

計算機網絡的十大核心課題之一，如果解決TCP擁塞。

這裡首先理一下關系。

1. TCP是可靠傳輸，假設主機A向主機B發包，那麼B接受到A的包後，需要向A發送一個ACK，A接受到ACK才會認為B已經收到之前發送的包了。
2. 假如A在某一個固定的時間間隔内沒有收到B的ACK，A就會認為自己發送的包産生了丢失，就會執行重傳以及相應的擁塞控制政策。

   

3. 試想對于上面那副圖中所示的網絡系統，假如說中間兩個核心路由器之間的Bottleneck Link的帶寬隻有20Mbps，而每個Server都以100Mbps的速率發送包，那太容易在左側路由器處各個包形成擁堵了。
4. 擁堵意味着每一個包需要等待一定時間才能從中間的Bottleneck Link上通過，由于發送速率大于瓶頸鍊路速率，包的堆積會越來越多，每個包的等待時間也會越來越長。同時，由于等待時間不久後就會超過Server端的等待ACK時間，Server端就會認為包已丢失進行重發，重發的包又繼續堆積到中間的路由器上，形成惡性循環。
5. 是以怎麼讓Server端的主機可以根據丢包情況（沒有收到預期ACK的情況）調控自己的發送速率進而使整個網絡達到最優化呢？這就是擁塞控制問題。
6. 擁塞控制的主要難點在于，Server端的主機對于整個網絡的情況是未知的！假如Server端可以知道整個網絡的情況，擁塞控制問題就不是問題了（比如上面的例子就可以讓每個Server以20Mbps減去瓶頸鍊路已使用帶寬的速率發送包）。實際網絡中，除了少部分内部網絡可以提供網絡環境情況外（in-net support），幾乎所有的網絡都隻能在端對端（end-to-end）的情況下實作擁塞控制，即隻能根據自身發送包的速率，收到ACK的速率或比例，各個包的rtt這些可以在端擷取到的資訊來對網絡情況進行猜測并在端這裡采取相應的行動。

一般教科書上會介紹經典擁塞控制方法是Reno算法，由慢啟動、擁塞避免、快速恢複三個階段組成。

讓我們離開教科書之外。在Reno之後，基于Reno改進的NewReno算法逐漸占據了主導地位。再之後新的算法層出不窮，直到cubic算法的優秀性能逐漸得到了公認。

然後，Google在2016年提出了BBR算法，對整個擁塞控制算法領域進行了一輪革新。該算法強大到直接讓youtube的日吞吐量整體上升了4%并讓rtt下降了33%。不得不說Google真的是推動計算機行業進步的公司，VR眼鏡、Bert模型、浏覽器插件商店，就連擁塞控制這種感覺脫離應用的領域都能直接帶來領域爆炸。。相比之下國内的網際網路巨頭還一直關注于商業和應用倒是有點顯得器小了。。

TCP擁塞控制甚至整個網絡領域都是相對不那麼容易落地的研究方向，讀論文就會發現一大堆一大堆算法的提出，好像大家都是在為了發paper而發paper，真正實際的應用場景也許就隻能看看Linux的新版本又選用了什麼算法之類的，這個方向變現能力極其缺乏是真的。

關于擁塞控制算法的一些資料我也放在了文末，有興趣的讀者看一下。

回到正題，上面提到的都是經典的擁塞控制算法。現階段，鑒于人工智能是時代主旋律和技術發展方向，科學家們開始考慮着将機器學習應用到傳統的擁塞控制上。

增強學習

先解釋一下機器學習、深度學習和增強學習。

這部分主要參考了一下知乎的一個問題，連結我也放在了最後。大緻可以總結為以下幾點：

1. 機器學習指一切通過優化方法挖掘資料中規律的學科。傳統的機器學習包括線性回歸、邏輯回歸、決策樹、支援向量機等等。機器學習包括深度學習和增強學習。
2. 深度學習大緻指運用了神經網絡作為參數結構進行優化的機器學習算法。深度學習的訓練樣本是有标簽的而且學習過程是靜态的。經典的深度學習領域像cv，nlp。都是通過訓練集标注訓練、測試集檢驗的方法進行。
3. 增強學習不僅能利用現有資料，還可以通過對環境的探索獲得新資料，并利用新資料循環往複地更新疊代現有模型的機器學習算法。強化學習的訓練是沒有标簽的，它是通過環境給出的獎懲來學習。強化學習實際應用目前還較窄，主要包括AI遊戲（如Atari），推薦系統（如阿裡家的），機器人控制相關（如Ng的無人機飛行）。

關于增強學習，這裡推薦一個入門tutorial。A Painless Q-learning Tutorial (一個 Q-learning 算法的簡明教程)。這是一個可以在20分鐘内實作的例子，可以最快最直覺的感受到增強學習最經典的Q-Learing算法。

關于增強學習怎麼在擁塞控制中應用呢？其實想一想會覺得還是挺合适的。增強學習相對于深度學習的優勢是在于對不斷變化的環境進行适應，通過更加個性化達到更好的性能（沒錯核心還是性能）。而網絡一個很大的特征就是網絡環境會不停變化。比如上面提過的啞鈴型網絡，瓶頸帶寬在實際情況中是不一定會一直保持不變的，可能隔壁的server在這個小時對帶寬消耗很大，下一個小時又不消耗帶寬了。是以能夠适應變化的情況的學習方案按理來說會有更好的性能表現。再加上用上機器學習這種萬能黑盒方法，表現應該是不會太差的。

在這裡引用那幾篇論文中的随便一篇的摘要吧

下一代網絡通路技術和Internet應用程式增加了為使用傳統擁塞控制協定的使用者提供滿意的體驗品質的挑戰。根據特定的網絡體系結構或應用程式，通過修改核心擁塞控制方法來優化TCP性能的努力，在廣泛的網絡場景下并不能很好地推廣。這種限制源于基于規則的設計原則，其中性能與預先确定的網絡觀察狀态到相應操作之間的映射相關聯。是以，這些協定無法适應新環境中的行為，也無法從經驗中學習以獲得更好的性能。我們通過将基于強化的Q-learning架構與TCP設計內建在我們稱為QTCP的方法中來解決這個問題。QTCP使發送方能夠以線上方式逐漸學習最優擁塞控制政策。QTCP不需要寫死規則，是以可以推廣到各種不同的網絡場景。此外，我們開發了一種廣義的Kanerva編碼函數近似算法，減少了值函數的計算複雜度和狀态空間的可搜尋大小。我們展示了QTCP優于傳統的基于規則的TCP，它提供了59.5%的高吞吐量，同時保持了較低的傳輸延遲。

Next generation network access technologies and Internet applications have increased the challenge of providing satisfactory quality of experience for users with traditional congestion control protocols. Efforts on optimizing the performance of TCP by modifying the core congestion control method depending on specific network architectures or apps do not generalize well under a wide range of network scenarios. This limitation arises from the rule-based design principle, where the performance is linked to a pre-decided mapping between the observed state of the network to the corresponding actions. Therefore, these protocols are unable to adapt their behavior in new environments or learn from experience for better performance. We address this problem by integrating a reinforcement-based Q-learning framework with TCP design in our approach called QTCP. QTCP enables senders to gradually learn the optimal congestion control policy in an on-line manner. QTCP does not need hard-coded rules, and can therefore generalize to a variety of different networking scenarios. Moreover, we develop a generalized Kanerva coding function approximation algorithm, which reduces the computation complexity of value functions and the searchable size of the state space.We show that QTCP outperforms the traditional rule-based TCP by providing 59.5 percent higher throughput while maintaining low transmission latency.

總之8篇論文的核心思想都是，在某種場景下，我們把增強學習應用在了擁塞控制中，效率得到了很大的提升。當然，具體的應用場景還是比較有趣的，有一篇是将其應用在了命名資料網絡上，還有一篇是根據擁塞控制算法選擇13個經典控制算法中的一種應用（選擇算法的算法），都非常有意思。

下面再介紹一下我在這個月的學習過程中遇到的一些其他的有意思的話題。

ns3網絡模拟

要想進網絡這個領域，一定是要熟悉模拟工具的。比較常見的模拟工具有ns2，ns3，omnet，opnet這些，因為那幾篇論文大多用的ns2和ns3是以我選擇了ns3。

相比于人工智能那邊的架構，這些網絡模拟架構的完善程度和學習資料真的是有點寒酸。。其實ns3相對來說也算是完整易用了，但是和其他架構比起來不支援windows，沒有主流IDE擴充支援，沒有自動配置，種種都讓它顯得讓人有那麼點想吐槽。。

另外ns3-tutroial真的是事無巨細的講解呀。。200頁的英文入門門檔，雖然看懂确實沒啥問題但是真的費時間呀，另外對于複現論文來說tutroial完全不夠，manual又是幾百頁，再看看需要的model-library。。。而且B站上都沒有幾個好點的ns3教程。

總之我覺得ns3的入門還有很多事情可以做，要是我之後真的走了網絡方向我就去自己做視訊吧，也歡迎大家為ns3的普及出力。

如果想要對網絡模拟有所了解的話，我也把ns3的官網網址放在了文末。

新一代網絡

新一代網絡是個很有意思的話題。2010年由UCLA牽頭的基于CCN概念的NDN項目NSF資助，使得長期以來不溫不火的ICN網絡又一次受到了重視。

核心思想在于傳統的網絡以IP為中心，不是很好，新一代應該以内容為中心。

這意味着我們寫網絡程式會有很大的改變哈，拿那8篇論文中的一篇中舉得例子來說：

• 當我們要請求網絡資源時，我們不再需要在用戶端程式中寫目标位址！
• 在網絡包在網絡中轉發時，中間節點可以緩存網絡包，這樣可以讓用戶端在下一次的請求直接從中間節點獲得所需内容。
• 對于任一節點，每個網絡包的資訊是可見的！因為基于内容，是以節點會知道這個包是網頁、視訊流、音頻流或者其他什麼，根據不同的内容類型可以采取不同的擁塞控制政策（這是非常美好的構想，因為不同内容對于帶寬的要求會有明顯差異，而這在IP中心網絡中是不可得的）。
• 用官方的話來說，網絡從推模式（由server推給client）變為了拉模式（client向網絡拉取自己需要的内容）

從某種角度上來說，對于用戶端程式，網絡變得向一個黑盒，對于網絡本身，則有了多得多的可利用資訊。

實際上ICN是一種構想，負責具體實作的架構除了NDN（命名資料網絡）、還有XIA，還有很多其他的。北大深研院的李揮教授的工作MIN網絡，就類似于一個整合了新一代各種場景的網絡混合架構方案。

不過新一代網絡這個方向一聽就是不好落地hh，幾乎所有網際網路開發者都能意識到，現在對整個網絡的筋骨下手是十分困難的，幾十年來無數宣稱能重構網絡的網絡層、運輸層協定大多都沒有掀起什麼浪花。現在新一代網絡的研究已經進行了十年，雖然在很多方面都有了一些方案出來，但至少直到現在還沒有商用落地案例。選這個方向還是要好好考慮一下，不過好在這個topic目前有一定的政策支援和熱度，也不好說是不是一定實作不了。

關于新一代網絡的一些其他資料，我也放在了文末。

關于領域初瞰的部分到此就結束了。後面是我的個人失敗原因分析。。

失敗原因分析

核心來說就是兩點：确實難，不上心。

我的時間線大緻是，讀6篇半論文總共用了差不多2周的時間（後面兩篇并沒有讀完），最開始的幾篇是一邊翻譯一邊記筆記整理思路，平均每篇十幾頁的論文要花3-4天，後面幾篇就因為也有點急了，就直接讀英文加上在pdf裡加批注，同時實驗部分統統跳過，這樣的方式就大概1-2天一篇，但是對論文的熟悉程度就和前一種方式差的遠了。除此之外，讀ns3-tutorial和配置環境花了一個多星期。其實這樣下來就隻剩了大概一個多星期的時間來複現論文。但是複現論文時發現複現對ns3的要求要大大超過tutorial，增強學習沒有基礎的情況下很多公式看着容易實際上自己寫不成代碼，以及自己的C++程式設計能力确實差勁。1個多星期沒有完成複現。

上面說的是确實難這個原因，但不上心展現在哪裡呢？其實理論上說複現論文給10天時間應該是足夠的了，即使對于我這樣之前沒有複現過的人來說也不是一定完不成的任務。但是如果遇到問題全無思路卻也不願意去找相關的group問而是自己一邊磨時間一邊慢慢浏覽文檔和google的話，如果每天還是隻付出六七個小時在複現上面而每天娛樂時間也有四五個小時的話，如果由于虛拟機卡嚴重影響效率卻不想着去解決而是由着性子幹脆慢慢搞的話，那必然會失敗的。可怕的是我恰恰全部犯了上面這些錯誤。

除此之外，還有自身編碼能力的嚴重不足。舉個非常簡單的例子。在Q-Learning中，我們需要維護一個QTable表。具體為由一個state和一個action可以得到一個Q-value值。在論文的具體場景中，state由三個字段構成：avg_send（平均發送速率），avg_ack(平均收到ack速率)和avg_rtt（平均rtt）。action有三種情況，分别是cwnd = cwnd +10, -1, +0. 整個運作過程中大概會出現2000個state，每個state和action對應的Q-value可以用double表示。那麼應該如何實作呢？

這其實是個很小，很簡單（相比于核心算法來說）的問題。但是卻卡了我一兩個小時。很容易想到應該實作成根據state和action獲得Q-value的資料結構，但是具體怎麼做呢？用stl庫，一開始想用unordered_map，但是是不是map更合适呢？map内部用的是紅黑樹，需要鍵實作能比較大小的重載，根據大小比較查找元素。unordered_map使用的是hash，需要鍵實作hash函數的重載。在這個場景中應該是用map更适合，因為state的三個成員全是數值，比較大小會很友善而且分布會比較好。但是這裡有state和action兩個對象要作為鍵，怎麼辦呢？要使用stl的pair類嗎？使用的話不僅要嵌套中多次實作重載，查詢、添加都要有很多邏輯處理（如果之前采用unordered_map方案，hash重載更麻煩的要死），不如直接使用state重載“<”作為鍵，每個值是一個長度為3的一維數組，對應着每個action的具體Q-value值，這樣在設計上和實作上都會友善些。但是對于我來說，想到unordered_map，查相關用法用了十幾分鐘，想到map，查相關用法用了十幾分鐘，發現需要重載運算符或者哈希，查相關重載方法用了十幾分鐘，想到pair，查相關用法用了十幾分鐘。時間就這麼過去了，完全不行。。這次也算是用事實打破了我之前一直自認為編碼能力良好的認知吧。

最後還有一點是懷疑，雖然不能說是我沒做完的主要原因，但也确實是對我的效率産生了一定影響。我在五月的大多數時間，内心是認為自己不會成功進到夏老師課題組的，因為我的水準是留本校而不是進清華的水準。這就有一個很詭異的邏輯鍊。我有考核資格->我的實力和對方的層次本身就不比對->我不會通過->我沒有必要努力。我現在覺得，真的應該找準自己的目标，要根據自己的實力水準确定要跳到哪裡，這樣才會避免上面的邏輯鍊的出現。之前和一位同學聊，他問我是不是總是告訴自己失敗是正常的好讓自己覺得失敗了也不丢人，當時我未明白其意，現在才認識到這種思維的害處如此之大。除此之外，之前和另一位同學關于方向和現實的讨論也讓我沉淪了兩三天并一度想要放棄這個項目，但是那個關于方向選擇的問題這裡就不想再展開了。

最後插一句。我個人的情況是櫻花大學軟體工程專業，排名31/258（12%）。科研經曆有一段這學期劃水的科研經曆，但是是非常冷門的RFID協定方向，而且沒有産出。項目經曆有一個校級大創和一個沒有得獎的花旗杯比賽項目。其他方面能說的就是軟考過了，六級518。保研的同學應該都能看出來，我能拿出手的東西其實相當少，但這樣的履歷還是通過了履歷關，可見夏老師确實是更注重動手能力而不在履歷上卡人。是以來年如果還是這樣的形勢的話大家大可以不必拿着比我好的多的成績而自卑，大膽投一投履歷，夏老師的口碑确實還是挺好的，學術能力也很強。

資料

網絡擁塞控制：

ns3中關于各個擁塞控制算法的一個簡要介紹

面試頭條你需要懂的 TCP 擁塞控制原理

TCP BBR算法與Reno/CUBIC的對比

一文解釋清楚Google BBR擁塞控制算法原理

Google BBR擁塞控制算法背後的數學解釋

增強學習：

機器學習、深度學習和強化學習的關系和差別是什麼？

A Painless Q-learning Tutorial (一個 Q-learning 算法的簡明教程)

關于使用了增強學習的擁塞控制算法，可以查閱前面放上的project裡面的論文。

ns3模拟：

ns3官網

ns3-users的google-group

新一代網絡：

網際網路網絡架構發展白皮書釋出

什麼是命名資料網絡NDN？

以NDN和IPFS為代表的ICN架構能為網際網路帶來什麼

資訊中心網絡的前世今生

其實關于新一代網絡，還是推薦大家直接去看相關的論文。會科學性強一些。不過說回來這個新一代網絡。。現在好像連個成體系的書籍都沒有。。

一些其他有趣的知識

如何看待 HTTP/3 ？