令牌桶算法是網絡流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法。典型情況下，令牌桶算法用來控制發送到網絡上的數據的數目，并允許突發數據的發送。

用簡單的話語來說就是限制流量，將其控制到某一平均值穩定輸出，并可以在短時間內應對高額流量（短時高速率流量）的一種方法。

需要注意的是，限速只是讓他盡可能速率一致，是存在速率不穩定的情況的，只有在長期來看速率才是恒定的，而當令牌桶應對突發流量時會進行令牌桶內令牌的小號，理論上的峰值速率=令牌桶的容量+恒定速率，舉個例子，令牌桶的容量 為100MB，限制的速率為10MB/s，峰值速率則可以達到100+10=110MB/s。

?

?b為桶的容量，r為單位時間內放入的令牌數量，以下圖為例：

在r=10，b=5時，即表明每1/r=0.1，每0.1秒投入一個令牌，而在到0.5秒時達到桶的極限容量5，在此刻繼續投入令牌則無法維持，這些令牌將會被廢棄，同時在此時若有5個指令同時想要去走令牌則可以同時取走令牌桶內的所有令牌，即為取走b=5個。

注意：

1. 當b>1時（桶的大小大于1個令牌時），任意1/r秒內最多可以取走b個令牌；
2. 而當b=1時（桶的大小就是1），每秒鐘最多可以被取走r個令牌。

綜上，令牌桶算法的總體流程大致分為如下三步：

1. 將令牌放入桶內：按照固定的速率放入令牌桶內，例如r=10，20，100等；
2. 獲取令牌：任意請求只有在取得可用令牌才會被接收處理；
3. 令牌桶已滿：當桶內令牌已滿時，新加入的令牌會被丟棄或者拒絕接收。

與網絡帶寬分配相結合，可在一定程度上減少資源的浪費，同時可以根據不同優先級的業務來進行基于令牌桶的帶寬分配改進方式，針對不同優先級的業務設定不同的業務權值，以此來自適應業務速率的變化，可通過業務權值的占用比例進行動態分配令牌資源，利用令牌桶嵌入漏桶機制實現對業務占用的帶寬進行二次分配,根據業務優先級的高低對溢出的令牌實現依次填充,從而減少資源浪費。（源自論文：基于動態令牌桶的衛星網絡帶寬分配方法）

衛星網絡模型：一個GEO衛星，若干地面終端和網絡控制中心NCC（Network Control Center）組成，地面終端則是經由SG（Satallite Gateway）連接到Internet網絡。通過網絡控制中心NCC來進行處理各個SG發來的帶寬申請和分配新的貸款，上行鏈路由各個SG提供，下行鏈路則是數據流共享的信道。

GEO衛星網絡?

令牌桶方法實現：令牌桶的填充速率R，令牌桶容量S（令牌桶所能容納的最大令牌數），令牌桶的當前狀態為x，表示當前對應令牌桶的深度，工作流程如下圖：

工作流程上，GEO衛星上的帶寬資源被定義為n個令牌桶，當有業務傳達到時，NCC處理由SG為每個業務發送的帶寬請求并為其分配帶寬，哥哥令牌桶為每個業務分配基本保證帶寬，即為R1,R2,R3......Rn。調整R1,R2,R3......Rn的大小可以設定各個業務的保證帶寬，需要注意，各個令牌桶的尺寸小于鏈路的信道容量，各個業務到達相應令牌桶后，根據數據包長度與令牌桶內數量來進行分配，若數據包長度小于令牌數，業務傳送出去，令牌桶內令牌相應減少。而高優先級的業務將會優先進行放入。而由于令牌桶間仙姑獨立，令牌桶無法動態借用空閑令牌，即空閑帶寬無法進行有效利用，且令牌桶在填充過程中，令牌個數不會大于令牌桶容量，溢出令牌會丟失，也進一步造成了帶寬資源的浪費。

改進方法：將漏桶嵌入到令牌桶中,即每一個令牌桶連接一個漏桶,有幾個優先級就有幾個令牌桶。這樣可以保證優先級為n的最小帶寬,溢出桶用來存儲溢出的令牌,借用令牌桶的動態帶寬分配算法（Dynamic Bandwidth Allocation Algorithm with Token Bucket,DBAATB），原理下圖：

?代碼實現：

acquire獲取令牌的操作中，使用鎖保護數據正確性，使用條件等待令牌足夠才繼續往下執行。

bool CountSemaphore::acquire(unsigned long long count)
{std::unique_lock<std::mutex> lck(m_mtx);if (count > m_maxCount){return false;}m_cv.wait(lck, [&]() -> bool { return m_updateCount >= count; });m_updateCount -= count;return true;
}

release增加令牌數量，并通知其他等待條件的線程繼續執行。

void CountSemaphore::release(unsigned long long count){std::unique_lock<std::mutex> lck(m_mtx);auto tobeCount = m_updateCount + count;if (tobeCount > m_maxCount){m_updateCount = m_maxCount;}else{m_updateCount = tobeCount;}m_cv.notify_all();
}

TokenSpeedLimiter是令牌桶的封裝。包含令牌桶的限速速度，令牌的投遞時間間隔和令牌桶的容量。提供開始和結束投遞操作和獲取令牌的操作。

void TokenSpeedLimiter::workingThread()
{auto lastTime = std::chrono::steady_clock::now();while (m_runing){// 延時定時投遞std::this_thread::sleep_for(std::chrono::milliseconds(m_deliveryIntervalMs));// 計算投遞時間差auto curTime = std::chrono::steady_clock::now();auto elapsedMs = std::chrono::duration<double, std::milli>(curTime - lastTime).count();lastTime = curTime;// 根據時間差計算投遞令牌的數量(除以1000換算成毫秒投遞數量，然后再乘以毫秒時間差)auto tokens = m_limitSpeed * elapsedMs / 1000;// 投遞令牌m_semaphore.release((unsigned long long)tokens);}
}