Google TCP BBR Congestion Control

自 1980 年代網際網路崛起，到 1990 年代快速發展開始，就產生了 TCP 以及 UDP 的 IP 網路，1983年1月1日，ARPANet要求未來所有的網路傳輸都使用 IP 網路，統一了開放網路的規格。

網路通道就像是一條水管/水道，這條通道用來傳送資料，因為沒有即時調節流量的機制，TCP 透過接收端發送確認已經收到封包的 ACK，來判斷是否發送的速度太快，流量控制就是在控制資料發送端的發送速度。

BBR (Bottleneck Bandwidth and Round-trip propagation time) 演算法是 Google 在 2016 年提出的流量控制演算法，他透過有效頻寬偵測機制，並降低網路節點的 buffer 使用量，藉由減低重傳的效能消耗問題，提高頻寬使用率。

流量控制是在做什麼工作

把網路傳輸通道 TCP 想像為一條從山頂的水庫到目的地海洋的河流或水管，水庫有大量水資源，希望能運用水道以最短時間送到海洋，但是水庫並不知道這個水道有多寬，能以多少速度的水量放水。如果水放得太慢，無法享用水道的總流量，水放得太急，有可能會超過水道容量，而讓水漫出水道，造成淹水的情況。

流量控制，就是控制水庫放水速度的一個演算法，因為水道容水量的情況是隨時都在改變的，問題在於，並沒有即時回報的機制，可以隨時調節流量，另外，由於發送端貪婪的本性，他會希望盡可能完全佔用網路水道的所有容水量。

但總不能一直送一直送，也不管接收端有沒有收到資料吧。TCP 的機制是，在接收到收到封包時，會回覆一個 ACK 封包，確認已經收到了，透過 ACK 的偵測，就可以知道現在發送的速度，是不是已經超過了網路通道的容量，如果發生封包遺失的狀況時，發送端就知道要降低發送速度了。

雖然是開放網路，公平競爭，但實際上還是看誰最會搶佔網路資源，因此有些演算法強調搶佔的特性，會侵蝕掉使用其他演算法的 TCP 連線。

但從提供網路服務這一端來看，他希望所有來使用服務的使用者，可以公平地使用伺服器對外的網路通道，而且要盡可能減少因為 TCP 重傳的機制，造成無效的網路資源浪費，這時候，採用強調發送端公平使用網路的演算法，會比較有利。

因為網路通道本身不穩定的特性，如果中間有遇到無線網路時，這種情況會更嚴重，因此網路的路由器本身，通常都會加上 Buffer 的機制，能夠讓暫時無法發送的網路資料，存放在 Buffer 裡面，希望能藉此改善整體網路的效能。就像是水道中間，會加上一些滯洪池的機制，預防水量瞬間增加的問題。

然而這些 Buffer 卻因為 TCP 流量控制貪婪的本性，而被濫用，因為 TCP 希望自己能盡可能使用到網路的最大流量，所以也會盡可能將自己的封包，把路由器的 Buffer 塞滿，讓自己的速度更快，這也會造成 Bufferbloat 的問題。

網路上有許多網路節點，除了控制路由以外，有些節點還增加了 QoS(Quality of Service) 或是 Traffic Shaping 的機制，這也是基於剛剛提到的 Buffer 而提供的功能，因為有了 Buffer，路由器可以先將需要傳送的資料，放入不同等級的 Buffer 裡面，保留固定的傳送頻寬給具有高傳輸權限的網路封包。

BBR 演算法

BBR 演算法的細節，以這兩篇文章的說明比較清楚。

TCP BBR擁塞控制算法解析

Linux Kernel 4.9 中的 BBR 算法與之前的 TCP 擁塞控制相比有什麼優勢？

要不然就要看原始發表的論文

BBR: Congestion-Based Congestion Control Measuring bottleneck bandwidth and round-trip propagation time

BBR 解決問題的方案有兩點

1. 因無法區分 congestion packet loss 及 error packet loss，BBR 考慮讓網路不產生 packet loss
2. 因為把 buffer 塞滿可產生最大流量，但也會造成 RTT 降低，BBR 交替進行頻寬及 delay(RTT) 偵測

BBR 的四個狀態

1. STARTUP
   採用標準的 slow start 方式，指數增加發送速度，發現頻寬被佔滿時，就進入 DRAIN 的階段
2. DRAIN
   降低發送速度，將佔用的 buffer 排空
3. PROBE_BW
   改變發送速度進行頻寬偵測，在一個 RTT 內增加發送速度，如果 RTT 沒有改變，就降低發送速度，排空先前多送的封包，在六個 RTT 內使用這個發送速度
4. PROBE_RTT
   每經過 10s，如果沒有得到一個更低的延遲時間，就進入延遲偵測的階段，持續 200ms (或一個 RTT)，這個階段固定發送 4 packets，偵測得到的最小 delay 時間作為最新的延遲時間

一些實測的結果

GCP採用新演算法TCP BBR　傳輸率將提高2700倍！

又一個 TCP BBR 的測試結果

spotify: Smoother Streaming with BBR

BBR 阻塞算法，真是黑科技

這些是使用了 BBR 以後的測試說明，全部都是正面，效能有改善的結果。

Google 在宣傳 BBR 時，都說明只要修改 Server 的部分，讓 Server 以 BBR 演算法運作，原因在於，流量控制演算法著眼的重點，是大量資料的發生源，會產生大量資料，發送出來的地方。只要修改 Server 的原因是他們是針對 Youtube 這樣提供串流服務的 Server 套用 BBR，換句話說，BBR 適用於 Sender Side。

因為串流影音的特性，就是需要一條長時間運作且傳輸量穩定的網路通道，這正好符合了 BBR 提供的流量結果，因為沒有使用到 Router 的 buffer，也沒有大量的重傳封包抵銷了網路的效能。

如果是類似 Hangouts Meeting 這樣的多人雙向影音的應用，因為客戶端 client side 如果沒有使用 BBR，就可能會產生不穩定的個人影音發生源，即使 Server Side 提供了 BBR，也無法形成一個有良好體驗的網路環境。

並不是所有人都認為 BBR 是有用的，以 令人躁動一時且令人不安的TCP BBR算法 這篇文章提出的論點來看，BBR 適合用在速度比較穩定的網路通道上，因為增速快，降速慢的特性，並不適用於忽快忽慢的網路。

我個人的想法是，只要決定了網路通道，固定了網路通道，那麼大部分的情況，網路是穩定的，該文章提出的問題，說明的並不恰當，如果通道上有些路徑的頻寬比較小，這會讓整條網路通道都因為這個最小頻寬的一段路而降速。因為流量控制只會根據接收端的 ACK 來調節，沒辦法知道中間經過每一個網路節點的速度。

會發生問題的地方，應該是網路忽快忽慢的情況，因為變化太大，演算法無法很快地調節到最佳的傳送速度，但這應該是所有演算法都會遇到的問題，BBR 改善的結果已經有顯著的效果了。

如何啟用 BBR

How to Deploy Google BBR on CentOS 7

開啟TCP BBR擁塞控制算法

因為 BBR 已經有在 linux kernel 4.9+ 的版本上實作，在各 linux distribution 的安裝方式，都是安裝新的 kernel repo，將 kernel 更新到 4.9+。

然後在 /etc/sysctl.conf 增加這兩行設定

net.core.default_qdisc = fq
net.ipv4.tcp_congestion_control = bbr

sysctl -p

用以下指令確認有沒有安裝成功

sysctl net.ipv4.tcp_available_congestion_control
sysctl net.ipv4.tcp_congestion_control
lsmod | grep bbr

BBR 可以終結流量控制的問題嗎？

這個 wiki 上的漫畫說明了現實的狀況，原本 BBR 的開發者，想要設計一個新的演算法，打敗既有12種 TCP Congestion Control 演算法，一統江湖，三年後，終於在 Linux 4.9 版 kernel 實現了 TCP BBR，但還是有某些缺陷，而現在變成了有 13 種 TCP Congestion Control 演算法。

References

TCP BBR

TCP擁塞控制

Faster Networking with TCP BBR

TCP BBR : Magic dust for network performance

Google最新tcp擁塞控制算法BBR解析

Julia

2009 年一些 matlab 工程師，還有 Lisp, Python, Ruby, Perl 的開發者集合起來，他們對現況不滿，目標是要有 C 的速度，Ruby 的動態語言特性，要有 Lisp 的 macros，類似 matlab 的語法，也要有 R 的統計功能，Perl 處理字串的能力，要能處理線性代數，統整起來的程式語言，在 2012 年發表了 Julia，並在今年 2018/8/8 發布正式的 1.0 版。

特性

• 核心很精簡，標準函式庫是以 Julia 開發
• 有支援線性代數、快速傅立葉轉換等功能
• 高效能，接近靜態編譯語言的速度
• 支援平行運算
• 支援 unicode
• 可直接呼叫 C 的 function
• 有類似 shell 的 process 管理能力
• 有類似 lisp 的巨集功能
• 動態資料型別的語言

在 Why We Created Julia 這篇文章中，明確地宣告 Julia 的遠大目標：

We are greedy: we want more.

因為他們希望集合很多程式語言的優點，簡單來說，就是精簡的語法，強大的功能，快速的結果這幾個重點，如果能夠達到目標，相信會吸引很多使用者進入這個領域，剩下就是時間的問題，讓時間去證明大家的選擇是對的。

Julia 的優缺點

優點

• 速度快: Julia 的設計目標，就是高速，當然會比 python 快很多

• 更貼近數學的語法: Julia 目標是科學語言，要吸引 matlab, R, Mathematica 的使用者，所以會採用貼近數學方程式的語法

• 自動記憶體管理: 跟 python, java 一樣，會自動 allocate, free memory

• Parallelism: 為達到快速的數學運算，需要儘可能使用所有運算資源

缺點

• 1-indexed: 為了跟 mathematica 或其他數學軟體的設計一樣，Julia 採用 index 1 作為 array 的第一個 element，一般程式語言是使用 index 0

• 目前的 3rd party package 數量還不夠，遠遠不及 C 與 Python library 的數量，但這是因為 Julia 的年紀很小，未來他的優點被更多開發者看見，就會發展更好

• python 已經發展了 27 年，當然在社群的使用度會比 Julia 多

學習資源

官方網頁 Online tutorials 提供了所有學習的資源及連結

另外在 JuliaBox 可用 github 登入，然後在網頁上使用類似 R 語言的互動開發介面，將文件跟 code 整合在一起

References

程式語言Julia歷經6年開發，融合多語言特性終釋出1.0

Julia vs. Python: Julia language rises for data science

Julia (程式語言)

Introducing Julia

JuliaBox

JuliaBox Tutorials

decorator in python

python 的 decorator 功能，使用的語法看起來很像 Java 的 annotation，是在 function 前面加上 @decorator，雖然名稱是 decorator，但實際上比 Decorator Design Pattern 的功能還要多一點。

decorator class

function decorator 使用起來，就是直接在 function 定義前面，加上 @my_decorator。

@my_decorator
def aFunction():
    print("inside aFunction()")

實際上，當 compiler 編譯 aFunction 時，會將 aFunction 整個 function 傳入 myDecorator，有取代原本 aFunction 的感覺，也有點像是 my_decorator(aFunction) 這樣的意思。

要實作 my_decorator 必須要實作 __init__ 以及 __call__ 這兩個 function，__init__會在一開始就被呼叫，而 __call__ 是在結束時被呼叫。

class my_decorator(object):

    def __init__(self, f):
        print("inside my_decorator.__init__()")
        f()

    def __call__(self):
        print("inside my_decorator.__call__()")

@my_decorator
def aFunction():
    print("inside aFunction()")

print("Finished decorating aFunction()")

aFunction()

執行結果如下，在程式中，因為 decorator 初始化的關係，會先呼叫 my_decorator.__init__()，在這個函數裡面，會取得 aFunction 的函數定義，所以可以在裡面呼叫 aFunction，在 aFunction 結束後，才列印了 Finished 的部分。

而最後是因為呼叫 aFunction()，所以轉為呼叫 my_decorator.__call__()。

inside my_decorator.__init__()
inside aFunction()
Finished decorating aFunction()
inside my_decorator.__call__()

也就是說，decorator 是在 init 的時候，就已經取得了 aFunction 的定義，而不是在呼叫 aFunction 時，才傳入 my_decorator。

decorator 其實就只是將 function 傳入另一個 function 的 syntax sugar。

---

在剛剛的例子中，我們在 __init__ 直接呼叫了 f()，但以下這個例子，才是比較重要的功能，他先將 f 儲存到變數中，然後等到 __call 才使用 f()

class entry_exit(object):

    def __init__(self, f):
        self.f = f

    def __call__(self):
        print("Entering", self.f.__name__)
        self.f()
        print("Exited", self.f.__name__)

@entry_exit
def func1():
    print("inside func1()")

@entry_exit
def func2():
    print("inside func2()")

func1()
func2()

所以可以在呼叫 func1() 的前面以及執行完成的後面，在 __call__裡面呼叫 self.f() 的前後加上自己需要增加的 code

Entering func1
inside func1()
Exited func1
Entering func2
inside func2()
Exited func2

function as decorator

剛剛是使用 class 作為 decorator，但可以直接定義一個 decorator function，以下的例子中，定義了 decorator function 以 f 為參數，在裡面定義了新的 new_f，取代了原本的 f

def entry_exit(f):
    def new_f():
        print("Entering", f.__name__)
        f()
        print("Exited", f.__name__)
    return new_f

@entry_exit
def func1():
    print("inside func1()")

@entry_exit
def func2():
    print("inside func2()")

func1()
func2()
print(func1.__name__)

執行結果為，因為 new_f 已經取代了 f，所以 func1.__name__ 的名稱結果是 new_f

Entering func1
inside func1()
Exited func1
Entering func2
inside func2()
Exited func2
new_f

如果覺得奇怪，還是可以刻意將 new_f 的名稱修改為跟 f 一樣

def entry_exit(f):
    def new_f():
        print("Entering", f.__name__)
        f()
        print("Exited", f.__name__)
    new_f.__name__ = f.__name__
    return new_f

Decorator with Arguments

因為 decorator 其實也是呼叫一個 function，所以可以直接在 decorator 上加上參數，以下是在 decorator class 裡面取得 decorator 參數的例子

class decorator_with_arguments(object):

    def __init__(self, arg1, arg2, arg3):
        print("Inside __init__()")
        self.arg1 = arg1
        self.arg2 = arg2
        self.arg3 = arg3

    def __call__(self, f):
        print("Inside __call__()")
        def wrapped_f(*args):
            print("Inside wrapped_f()")
            print("Decorator arguments:", self.arg1, self.arg2, self.arg3)
            f(*args)
            print("After f(*args)")
        return wrapped_f

@decorator_with_arguments("hello", "world", 42)
def sayHello(a1, a2, a3, a4):
    print('sayHello arguments:', a1, a2, a3, a4)

print("After decoration")

print("Preparing to call sayHello()")
sayHello("say", "hello", "argument", "list")
print("after first sayHello() call")
sayHello("a", "different", "set of", "arguments")
print("after second sayHello() call")

執行結果如下，在 __init__，可以取得 decorator 的參數，並在 __call__ 裡面使用這些參數

Inside __init__()
Inside __call__()
After decoration

Preparing to call sayHello()
Inside wrapped_f()
Decorator arguments: hello world 42
sayHello arguments: say hello argument list
After f(*args)
after first sayHello() call

Inside wrapped_f()
Decorator arguments: hello world 42
sayHello arguments: a different set of arguments
After f(*args)
after second sayHello() call

function decorator with arguments

同樣的 function decorator 也可以使用參數

def decorator_function_with_arguments(arg1, arg2, arg3):
    def wrap(f):
        print("Inside wrap()")
        def wrapped_f(*args):
            print("Inside wrapped_f()")
            print("Decorator arguments:", arg1, arg2, arg3)
            f(*args)
            print("After f(*args)")
        return wrapped_f
    return wrap

@decorator_function_with_arguments("hello", "world", 42)
def sayHello(a1, a2, a3, a4):
    print('sayHello arguments:', a1, a2, a3, a4)

print("After decoration")

print("Preparing to call sayHello()")
sayHello("say", "hello", "argument", "list")
print("after first sayHello() call")
sayHello("a", "different", "set of", "arguments")
print("after second sayHello() call")

Inside wrap()
After decoration

Preparing to call sayHello()
Inside wrapped_f()
Decorator arguments: hello world 42
sayHello arguments: say hello argument list
After f(*args)
after first sayHello() call

Inside wrapped_f()
Decorator arguments: hello world 42
sayHello arguments: a different set of arguments
After f(*args)
after second sayHello() call

因為被 decorator 修飾的原始 function，無法在實作 decorator 時就預先知道參數的個數，因此在定義 wrapper function 時，是定義為 def wrapped_f(*args):。

其中 *args 代表不固定個數的參數，如果要支援有參數名稱的參數，則可以使用 **kwargs

多個 decorator

@a
@b
@c
def f ():
    pass

如果有好幾個 decorator，那麼實際上呼叫的順序，是以下這樣

f = a(b(c(f)))

處理時間的 decorator

以下這是計算函數處理時間的 decorator

from time import time

def timer(func):
    def wraper(*args, **kwargs):
        before = time()
        result = func(*args, **kwargs)
        after = time()
        print("elapsed: ", after - before)
        return result
    return wraper

@timer
def add(x, y = 10):
    return x + y

@timer
def sub(x, y = 10):
    return x - y

print("add(10)",       add(10))
print("add(20, 30)",   add(20, 30))

執行結果為

elapsed:  9.5367431640625e-07
add(10) 20
elapsed:  1.1920928955078125e-06
add(20, 30) 50

函數參數的型別檢查 pylimit

pylimit2

利用裝飾器給python的函式加上型別限制

pylimit

python 因為是動態資料型別語言，變數不需要定義資料型別，隨時會改變，但是在實作時，常常會遇到一個問題，就是實作的 function 只能處理某些資料型別的參數，程式如果寫錯，很容易就 crash。

上面的兩個 pylimit 套件，就是利用 decorator 的做法，在裡面加上 function 參數的資料型別定義，然後就可以在呼叫該函數時，進行資料型別檢查，這樣就不需要在實作時，寫上很多 type() 檢查的程式碼。

References

Decorators

Python Decorator(裝飾器)

[Python] Decorator 介紹

理解 Python 裝飾器看這一篇就夠了

萬惡的 Python Decorator 究竟是什麼？

Python Decorator 入門教學

python 簡易 websocket server

Websocket Server 是一個簡單的 websocket server，沒有任何其他的關聯的套件，只需要 python 標準的 sdk。

由 github 下載原始檔 zip 後，將 server.py 以及 websocket_server 目錄複製到 project 裡面。

在 server.py 的 message_received 加上一行廣播訊息的程式碼。

server.py

from websocket_server import WebsocketServer

# Called for every client connecting (after handshake)
def new_client(client, server):
    print("New client connected and was given id %d" % client['id'])
    server.send_message_to_all("Hey all, a new client has joined us")


# Called for every client disconnecting
def client_left(client, server):
    print("Client(%d) disconnected" % client['id'])


# Called when a client sends a message
def message_received(client, server, message):
    if len(message) > 200:
        message = message[:200]+'..'
    print("Client(%d) said: %s" % (client['id'], message))
    server.send_message_to_all("Client(%d) said: %s" % (client['id'], message))


PORT=9001
server = WebsocketServer(PORT)
server.set_fn_new_client(new_client)
server.set_fn_client_left(client_left)
server.set_fn_message_received(message_received)
server.run_forever()

另外製作一個 client.html

<!DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>html5 websocket特性</title>
        <style>
            body{
                overflow: hidden;
            }
            h2{
                margin-top: 30px;
                text-align: center;
                background-color: #393D49;
                color: #fff;
                ont-weight: normal;
            padding: 15px 0
            }
            #chat{
                text-align: center;
            }
            #win{
                margin-top: 20px;
                text-align: center;
            }
            #sse{
                margin-top: 10px;
                text-align: center;
            }
            #sse button{
                background-color: #009688;
                color: #fff;
                height: 40px;
                border: 0;
                border-radius: 3px 3px;
                padding-left: 10px;
                padding-right: 10px;
                cursor: pointer;
            }
        </style>
        <script src="http://code.jquery.com/jquery-1.12.4.min.js"></script>
    </head>
    <body>
        <h2>聊天室</h2>
            <div id="chat">
                <textarea id="history" cols="80" rows="20"></textarea>
            </div>

            <div id="win">
                <textarea id="messagewin" cols="80" rows="5"></textarea>
            </div>

            <div id="sse">
                <button onclick="sendMessage()">傳送對話</button>
            </div>

        <script type="text/javascript">
            var oHistory = $('#history');
            var oWin = $('#messagewin');

            if ("WebSocket" in window){
                console.log("您的瀏覽器支援 WebSocket!");
                var ws = new WebSocket("ws://127.0.0.1:9001");
                //var ws = new WebSocket("ws://localhost:9001");
                ws.onopen = function(){
                    console.log("websocket 已連線上");
                }

                ws.onmessage = function (evt) {
                    var dataReceive = evt.data;
                    console.log("資料已接收..."+dataReceive);
                    $('#history').val($('#history').val()+dataReceive+"\n");
                };

                ws.onclose = function() {
                    console.log("連線已關閉...");
                };

            }else{
                // 瀏覽器不支援 WebSocket
                console.log("您的瀏覽器不支援 WebSocket!");
            }

            function sendMessage(){
                var dataSend = oWin.val().trim();
                ws.send(dataSend);
                oWin.val('');
            }
        </script>
    </body>
</html>

將 client.html 放在任意一個 webserver 上，因為 client.html 會連接到 127.0.0.1 的 websocket server，以 python server.py 啟動 server 後，打開兩個 browser tab，打開 client.html

兩個視窗間，因為剛剛增加的那一行廣播訊息的 code，所以可以看到所有訊息。

References

python與html5 websocket開發聊天對話窗