隨機早期檢測演算法程序

A. 什麼是寬頻接入Qos服務等級

在IP網路中，IPv4報文中有三種承載QoS優先順序標簽的方式，分別為基於二層的CoS欄位（IEEE802.1p）的優先順序、基於IP層的IP優先順序欄位ToS優先順序和基於IP層的DSCP（Differentiated Services Codepoint）欄位優先順序。每種優先順序的定義如下：
（1） IEEE802.1p優先順序
它是位於二層帶標簽的乙太網幀的CoS欄位，和VLAN ID在一起使用，在位元組中的位置如下：

其中：IEEE802.1p優先順序：3bit（P2-P0）
未用（CU）：1bit
VLAN ID：12bit（V11-V0）
IEEE802.1p優先順序值有8個（0-7），0優先順序最低，7優先順序最高。報文分為三種情況：帶優先順序和VLAN ID的標簽報文，其優先順序值是自身帶的值；只帶優先順序的標簽報文，此時VLAN ID為0，其優先順序值是自身帶的值；未帶標簽的報文，一般默認的優先順序值為0，也可以進行更改指定新的優先順序。
（2） IP優先順序
它由IP分組報頭中的服務類型（ToS）位元組中的3位組成，其在位元組中的位置如下：
P2 P1 P0 T3 T2 T1 T0 CU
其中：IP優先順序：3bit（P2-P0）
服務類型（ToS）：4bit（T3-T0）
未用（CU）：1bit
IP優先順序值有8個（0-7），0優先順序最低，7優先順序最高。在默認情況下，IP優先順序6和7用於網路控制通訊使用，不推薦用戶使用。ToS欄位的服務類型未能在現有的IP網路中普及使用。
（3） DSCP優先順序
它由IP分組報頭中的6位組成，使用的是ToS位元組，因此在使用DSCP後，該位元組也被稱為DSCP位元組。其在位元組中的位置如下：
DS5 DS4 DS3 DS2 DS1 DS0 CU CU
其中：DSCP優先順序：6bit（DS5-DS0）
未用（CU）：2bit
DSCP優先順序值有64個（0-63），0優先順序最低，63優先順序最高。事實上DSCP欄位是IP優先順序欄位的超集，DSCP欄位的定義向後與IP優先順序欄位兼容。目前定義的DSCP有默認的DSCP，值為0；類選擇器DSCP，定義為向後與IP優先順序兼容，值為（8，16，24，32，40，48，56）；加速轉發（EF），一般用於低延遲的服務，推薦值為46（101110）；確定轉發（AF），定義了4個服務等級，每個服務等級有3個下降過程，因此使用了12個DSCP值（（10，12，14），（18，20，22），（26，28，30），（34，36，38））。
由於存在三種優先順序，因此就有相應的6種優先順序的映射關系，即：Dot1p-DSCP、DSCP- Dot1p、IP Pri-DSCP、DSCP-IP Pri、Dot1p-IP Pri和IP Pri- Dot1p，其中最常用的是Dot1p -DSCP和DSCP- Dot1p兩種映射關系。
在IP網路中，IPv6提供了一定的QoS控制策略。IPv6分組頭定義了一個4比特的優先順序區域，可以指示16種優先順序別，同Ipv4平台的ToS位元組類似。16種優先順序別中的9種用於非實時傳輸業務，其餘的8種用於實時傳輸業務。但在協議中並沒有嚴格規定IPv6路由器應如何使用這一優先順序區域。
在未來的IP網路中，優先順序標簽並不是IPv6標識分組QoS的唯一方法。IPv6的分組頭還包括1個24比特的信息流標簽，這個標簽可由程序來設定，指示某組數據分組屬於某個特定的IP信息流。這樣，設備不需檢查地址、埠或其它信息，就可將數據分組分類。但是，信息流標簽並沒有指明QoS的提供方式，所以仍需使用RSVP和其它預留協議。
3 IP網路中QoS服務模型的選擇
在IP QoS網路架構的基礎上，IETF已經建議了很多服務模型和機制，以滿足QoS的需求。其中比較有名的有：IntServ（Integrated Service）綜合業務模型，DiffServ（Differentiated Service）區分業務模型，MPLS多協議標記交換，TE（Traffic Engineering）流量工程和約束路由等。
目前IP QoS主要的幾種服務模型描述如下：
（1） 盡力而為（Best-Effort）服務模型
盡力而為是一個單一的服務模型，網路盡最大的可能性來發送報文，對時延、可靠性等性能不提供任何保證。 該模型為最早的無QoS保障的服務模型，這也是IP網路最基本的特點所決定的。
（2） IntServ綜合業務服務模型
其基本思想為「所有的流相關狀態信息應該是在端系統上」，它基於每個流（單個的或是匯聚的）提供端到端的保證或是受控負載的服務。IntServ使用資源預留協議RSVP（Resource Reservation Protocol）作為每個流的信令。RSVP信息跨越整個網路, 從接收方到發送方之間沿途的每個路由器都要為每一個要求QoS的數據流預留資源。
在IntServ流中，定義了三種類型的業務：保證業務、受控負載業務和盡力而為的業務。同時IntServ定義了四個功能部件：資源預留協議RSVP(RFC2205)、訪問控制、分類器和.隊列調度器。
該模型的優點是：能夠提供絕對有保證的端到端QoS服務質量；RSVP在源和目的地間可以使用現有的路由協議來決定流的通路；該模型使得QoS能夠在Unicast和Multicast下均能實現。
該模型的缺點是：IntServ結構最致命的一個問題是其可擴展性很差；由於所有路由器必須實現RSVP、訪問控制，因此其對路由器的要求也很高；該模型不適合短生存期的流。
（3） DiffServ區分業務服務模型
基本思想為：在網路入口為每個包加以標記，產生不同的級別，每個級別的包得到不同的服務級別。該模型是由IntServ發展而來的，它採用了IETF的基於RSVP的服務分類標准，拋棄了分組流沿路節點上的資源預留。區分業務服務將會有效地取代跨越大范圍的RSVP的使用。
區分服務區域的主要成員有：核心路由器、邊緣路由器、資源控制器。在區分服務中，網路的邊緣設備對每個分組進行分類、標記DS域，用DS域來攜帶IP分組對服務的需求信息。在網路的核心節點上，路由器根據分組頭上的DS碼點（Code Point）選擇碼點所對應的轉發處理。資源控制器配置了管理規則，為客戶分配資源，它可以通過服務級別協定SLA與客戶進行相互協調以分享規定的帶寬。
DiffServ也定義了三種業務類型：最優的業務、分等級的業務和盡力而為的業務。DiffServ提供了一種簡單的方法對各種服務加以分類。目前的單中繼段行為PHB（Per-hop Behavior）的標准中對兩個最有代表性的服務等級作了規定：
EF（Expedited Forwarding）快速轉發：有一個單獨的碼點(DiffServ值)。EF可以把延遲和抖動減到最小，因而能提供總合服務質量的最高等級。任何超過服務范圍（由本地服務策略決定）的業務被刪除。
AF（Assured Forwarding）保證轉發：有四個等級，每個等級有三個下降過程(總共有12個碼點)。超過AF范圍的業務不會象「業務范圍內」的業務那樣以盡可能高的概率傳送出去。這意味著業務量有可能下降，但不是絕對的。
該模型的優點是：伸縮性較好，DS欄位只是規定了有限數量的業務級別，狀態信息的數量正比於業務級別，而不是流的數量；便於實現，只在網路的邊界上才需要復雜的分類、標記、管制和整形操作。核心路由器只需要實現行為聚集（BA）的分類，因此實現和部署區分型業務都比較容易。
該模型的缺點是：無法完全依靠自己來提供端到端的QoS服務。需要大量網路單元的協同動作，才能向用戶提供端到端的服務質量。解決這一問題的方法有兩種：一是用功能強大的全局策略管理器來完成這一任務；另外一種就是利用MPLS將第三層的QoS轉換為第二層的QoS，通過運營網中第二層的交換機來實現端到端的服務質量保證。
（4） MPLS 服務模型
基本思想為：MPLS是一種前向轉發策略，在進入MPLS作用域時給包賦予一定的標簽，隨後包的分類、轉發和服務都將基於標簽完成。MPLS是利用IntServ模型中現有的技術的主要思想與優勢，制定出一個統一的、完善的第三層交換技術標准。MPLS規定了一整套協議和操作過程，在IP網內實現快速交換。MPLS中的關鍵概念是用標簽來識別和標記IP報文，並把標簽封裝後的報文轉發到已升級改善過的交換機或路由器，由它們在網路內部繼續交換標簽，轉發報文。
MPLS實現信令的方式有兩類，一類是LDP／CR-LDP，它是基於ATM網路的。另外一類是RSVP，它基於傳統的IP網。RSVP和LDP／CR-LDP是兩種不同的協議，它們在協議特性上存在不同，有不同的消息集和信令處理規程。
MPLS網路由標簽邊緣路由器（LER）和標簽交換路由器（LSR）組成。在LSR內，MPLS控制模塊以 IP功能為中心，轉發模塊基於標簽交換演算法，並通過標簽分配協議（LDP）在節點間完成標簽信息以及相關信令的發送。
MPLS服務模型的優點為MPLS有著傳統IP技術所無法實現的功能，可以將ATM和IP很好地結合在一起；缺點為MPLS協議規定的標簽只具有本地意義，LDP信令以及標簽綁定信息只能在MPLS相鄰節點間傳遞。LSR之間或 LSR與LER之間依然需要運行標準的路由協議來獲了拓撲信息。
其它的服務模型：流量工程是一種安排通信流量如何通過網路的過程；約束路由在尋徑路由時會受到一定的約束，如帶寬或時延的要求。
通過以上對各種主要QoS服務模型的分析，則在可運營的電信級IP網路中實現QoS服務機制時，應考慮如下：
（1） 核心/骨幹網路的QoS
當前，由於DWDM等技術的發展，使得核心/骨幹網路的帶寬得到大幅度的增長。帶寬的增長為QoS服務質量減輕了壓力。但是，隨著網路流量的增加，特別是IP網路的路徑不確定性和流量的突發行為，使得網路的流量具有較大的突發性和不均衡性。因此，僅僅依靠帶寬是不足以提供良好QoS服務質量。
在核心/骨幹網路中提供QoS服務質量有兩種方法：一種是採用流量工程，一種是部署DiffServ區分服務模型。目前，流量工程的實施一般都是靜態手工或半靜態，缺乏動態實時的進行流量工程的工具。因此，流量功能很難對短期突發行為進行調節。而區分服務從長遠來看具有更完整的QoS提供能力，通過和流量工程、MPLS等機制結合，可以發揮更大的作用。
（2） 匯聚/接入網路的QoS
由於在匯聚層和接入層，一方面網路的帶寬較小，另一方面網路的情況也比較復雜，涉及到多種接入技術，如乙太網、ATM、FR等。因此，匯聚/接入網路的QoS實現是一個比較復雜的問題。
為了能快速、簡單、有效地部署和實現QoS服務質量，一般在這個匯聚/接入網路層次採用區分服務的思想實現QoS，即通過流量分類和優先順序處理。實際上，包括乙太網、ATM、MPLS在內的多種網路技術都支持報文的標記能力，這為報文的區分和標記提供了基礎。而網路設備，特別是接入設備一般都提供流量分類、標記和限制的能力。因此，在匯聚/接入網路中部署區分服務模型是一個可行的方案，也是一個必然的發展趨勢。
4 匯聚/接入設備中實現QoS的DiffServ服務模型
通過前面的分析，在可運營的電信級IP網路中，在匯聚/接入層次的設備中部署DiffServ服務模型是實現完善的QoS服務機制最適合的方案。
由於匯聚/接入層次設備的多樣性、復雜性，因此在部署QoS的DiffServ服務模型時，要力求簡單、有效、實用。因此，參考IP QoS的網路架構，匯聚/接入設備中應該首先考慮實現以下QoS功能：數據平面的緩存器管理、擁塞避免、報文標簽、隊列和調度、流分類、流策略和流量整形；管理平面的計量管理和策略管理等。
(1) 緩存器管理（Buffer Managment）
匯聚/接入設備中應該擁有報文收發、交換的緩存器，並可對其進行設置、管理。實現對端擁塞控制（HOL）、背壓等控制的功能。
(2) 擁塞避免（Congestion Avoidance）
擁塞避免是為了在報文較多，超出轉發速率時，通過一些演算法丟棄轉發隊列中的一些報文，從而達到避免擁塞的產生。擁塞避免演算法有尾部直接丟棄（Tail-Drop）、隨機早期檢測（RED）和加權的隨機早期檢測（WRED）等。在匯聚/接入設備中應該首先考慮支持尾部直接丟棄（Tail-Drop）和加權的隨機早期檢測（WRED）。
(3) 報文標簽（Packet Marking）
通過前面我們已經了解到IP報文中承載QoS優先順序標簽的有三種： IEEE802.1p優先順序（CoS欄位）、IP優先順序（ToS欄位）和DSCP優先順序（DSCP欄位）。因此，在匯聚/接入設備中應該支持以下功能：
對入口未帶優先順序標簽的報文可以加上各種新的優先順序標簽；
對入口攜帶優先順序標簽的報文可以更改其各種優先順序標簽，變為新的優先順序標簽；
支持報文攜帶新的優先順序標簽從出口輸出；
支持按一定的映射關系實現各種優先順序之間的映射，特別是IEEE802.1p優先順序和DSCP優先順序之間。
(4) 隊列和調度（Queuing & Scheling）
為了能夠實現較完善的QoS服務機制，支持VoIP、IPTV、視頻會議等多種業務。在匯聚/接入設備中應該支持多個隊列的機制，一般情況下應該至少支持4個隊列。
隊列調度有多種演算法，在匯聚/接入設備中比較適用的有：嚴格優先順序隊列調度（PQ）、加權循環隊列調度（WRR）和加權公平隊列調度（WFQ）。同時，也應該支持對WRR的隊列權重和WFQ的參數進行設置的功能。
(5) 流分類（Traffic Classification）
匯聚/接入設備是處於網路的邊沿，因此對數據流的分類是其一項非常重要的功能。通過對入口數據流按一定的規則進行匹配，區分出需要QoS保障的業務流來。一般用於匹配規則的欄位應該有：
eth-type：乙太網包的類型（IP/ARP/RARP）
ip-type：ip包的類型(ICMP/IGMP/TCP/UDP)
source-ip: 源IP地址的匹配
dest-ip: 目的IP地址的匹配
source-mac: 源MAC地址的匹配
dest-mac: 目的MAC地址的匹配
source-port : 源埠的匹配
dest-port: 目的埠的匹配
cos ：CoS優先順序的匹配
dscp：dscp優先順序的匹配
vlan：VLAN的匹配
(6) 流策略（Traffic Policing）
在匯聚/接入設備中應該支持對區分出來的業務流按一定的策略進行處理。即對通過流分類之後的業務流類進行行為控制，一般策略中對流的動作有：對流的速率限制、優先順序標簽的更改、VLAN的更改、超出速率的丟棄或更改優先順序等。
(7) 流量整形（Traffic Shaping）
在匯聚/接入設備的入口和出口，應該支持對數據流的流量整形，並可以設置流量整形的粒度，從而實現對入口或出口突發數據流的緩沖和整形。
(8) 計量管理（Metering）
在匯聚/接入設備中，應該支持對通過流分類之後的業務流進行速率的計量管理，從而達到設備中對各種業務的精確計量管理，保證各種業務的QoS服務質量。
(9) 策略管理（Policy）
在匯聚/接入設備中，應該支持對各種流分類的統一管理，即策略管理，從而達到設備對整體資源的統一調度，對各種業務流的統一協調處理，保證資源的合理應用和各種業務的QoS服務質量。

參考資料：http://www.zte.com.cn/Events/ChinaDSLConference2005/pro/pro-3.htm

B. red的RED演算法

首先是計算平均隊列長度，以此作為對擁塞程度的估計。另一個就是計算丟棄分組的概率蔽者。 由於Internet數據的突發性，如果一個隊列很多時候是空的，然後迅速被充滿，又很快被取空，這時就不能說路由器發生擁塞而需要向源端發送擁塞指示。因此，RED在計算平均隊長avgQ時，採用了類似低通濾波器（Low—pass filter）帶權脊並大值的方法：
avgQ=(1-Wq)*avgQ+ Wq* q。
其中，Wq為權值，q為采樣測量時實際隊列長度。這樣由於Internet數據的突發本質或者短暫擁塞導致的實際隊列長度暫時的增長將不會使得平均隊長有明顯的變化，從而「過慮掉短期的隊長變化，盡量反映長期的擁塞變化。
在計算平均隊長的公式中，權值Wq相當於低通濾波器的時間常數，它決定了路由器對輸入流量變化的反應程度。因此對Wq的選擇非常重要，如果Wq過大，那麼RED就不能有效地過慮短暫的擁塞；如果Wq太小，那麼avgQ就會對實際隊列長度的變櫻豎化反應過慢，
不能合理地反映擁塞狀況，在這種情況下，路由器就不能有效檢測到早期的擁塞。Wq的值應根據不同情況預先設置，一般來說，它是由路由器允許發生的突發業務的大小和持續的時間所決定的。 計算平均隊長的目的就是為了反映擁塞狀況，根據擁塞的程度來計算丟棄分組的概率，從而有效地控制平均隊列長度。
RED有兩個和隊列長度相關的閾值：MINth。和MAXth。當有分組達到路由器時，RED計算出平均隊長avgQ。若avgQ< MINth，則沒有分組需要丟棄；當MINth≤avgQ≤MAXth時，計算出概率P，並以此概率丟棄分組；當avgQ>MAXth時，所有的分組都被丟棄。由於RED使用的是基於時間的平均隊長度，就有可能會發生實際隊長大於平均隊長的情況，如果隊列已滿，則到達的分組只能被丟棄。 隨機早起檢測（RED，Random Early Detection）演算法將隊列的平均隊長作為決定擁塞避免機制是否應被處罰的隨機函數的參數，增加了在隊列長度變得太大之前平滑瞬時擁塞的可能性，減少了同時使多個流受分組丟棄影響的可能性。
下圖是一個RED丟棄概率函數的例子

當隊列長度小於低的門限值Tmin時，不丟棄新到達的分組；當隊列長度介於Tmin和Tmax之間時，以一定的概率丟棄分組，且分組概率隨著隊列長度的增長線性增加，隊列長度達到Tmax時，到達的分組全部被丟棄。這3個階段分別被稱作正常、擁塞避免和擁塞控制三個階段。最壞情況的最大隊列大小被限制為Tmax。RED在隊列滿之前提前開始觸發擁塞標識。路由器可對不同的隊列支持不同的Tmin、Tmax和Pmax值以平衡隊列可用空間、要求的隊列數和使用每一個隊列的業務類的延遲/抖動范圍。
RED最初是作為IntServ中的一種擁塞避免機制提出來的，當用在DiffServ中時，為了獲得更好的性能，為一致的分組和不一致的分組提供不同的待遇，產生了一些改進的演算法，如WEED、RIO等。

C. 簡單說下red和wred

隨機早期檢測(Random Early Detection)

隨機早期檢測(Random Early Detection)是一個擁塞避免演算法，在其中小比例的分組被放棄，當擁塞被探測到時，和這個隊列被懷疑完全地溢出前

加權隨機早期探測(WRED: Weighted random early detection)

加權隨機早期探測(WRED)是一個保證高優先順序通信比其它通信在擁塞時間有更低的損失率的排隊方法。