A-1(c). QoS 管理工具

QoS 管理架構可略分為 Control Plan 及 Data Plan，其典型工具如下：

Control Plan QoS 工具

Resource Manager 適當分配資源的方法以滿足各個 traffic flow 的 QoS 需求，以追求使用者整體最大利益為目標。如果可用資源不足時， Resource Manager 應該根據排定之優先順序與最佳化原則，進行取捨。
Admission Controller 根據系統所擁有的資源量控制允入的服務需求以避免允入過多的需求而超過負荷。

Data Plan QoS 工具

Resource Manager	適當分配資源的方法以滿足各個 traffic flow 的 QoS 需求，以追求使用者整體最大利益為目標。如果可用資源不足時， Resource Manager 應該根據排定之優先順序與最佳化原則，進行取捨。
Admission Controller	根據系統所擁有的資源量控制允入的服務需求以避免允入過多的需求而超過負荷。

Packet Classifier 進行偵測並分類所接收封包的類型。
Traffic Conditioner
and Policing 在某些特定功能發生時，可以將分封拋棄或降低其優序的功能。包括 Metering, Shaping, 及 Dropping 三項功能。 Metering 負責監控 traffice flow 流量， Shaping 負責控制突發性大量封包，避免其堵塞網路， Dropping 負責按優先順序捨棄封包。
Scheduler 當不同的 traffic flow 在一個網路元件同時競爭資源時，這個元件應該根據排定（或動態決定）之優先順序依序處理，以追求使用者整體最大利益為目標。
Mapping 為了克服兩個網域或通訊協定之間的 impedance mismatch 必須在兩者之間的邊界上進行服務品質(QoS)的重新 Mapping. 例如，將應用服務所需之最大所能容忍之 delay time, jitter, packet loss 等等品質需求參數根據下層ATM 網路之特性，轉化成 ATM 之品質參數（CBR, rt-VBR, 等）。

Packet Classifier	進行偵測並分類所接收封包的類型。
Traffic Conditioner and Policing	在某些特定功能發生時，可以將分封拋棄或降低其優序的功能。包括 Metering, Shaping, 及 Dropping 三項功能。 Metering 負責監控 traffice flow 流量， Shaping 負責控制突發性大量封包，避免其堵塞網路， Dropping 負責按優先順序捨棄封包。
Scheduler	當不同的 traffic flow 在一個網路元件同時競爭資源時，這個元件應該根據排定（或動態決定）之優先順序依序處理，以追求使用者整體最大利益為目標。
Mapping	為了克服兩個網域或通訊協定之間的 impedance mismatch 必須在兩者之間的邊界上進行服務品質(QoS)的重新 Mapping. 例如，將應用服務所需之最大所能容忍之 delay time, jitter, packet loss 等等品質需求參數根據下層ATM 網路之特性，轉化成 ATM 之品質參數（CBR, rt-VBR, 等）。

12.3.1.2 管理架構與理念

我們假設核心網路採用 DiffServ 環境，IP 層以下是透通的 (transparent), 我們品質管理重心是如何在DiffServ 環境之上提供品質管理決策、決定參數、選擇Policy、並指揮協調 DiffServ 之各個QoS元件(Admission control, routing, bandwidth allocation等）以達成QoS之使命。

A-2(a). 設計原則與目標

如同前節所述，一個成功的QoS 管理機制的關鍵是取決於這個管理機制使否簡單可行，像 IntServ 之所以不被認同的重要原因即是因為太複雜而只能適合小型網路。要降低管理複雜度的幾個重要原則是：

為避免 per flow QoS 造成大量的管理負擔，必須使用 aggregation 技術將許多 flow 歸併，減低管理負擔。

本計畫所擬研究之品質管理機制將追求下列目標：

降低管理複雜度，增加可行性
協助網路管理者達成最佳滿意度

本系統之直接使用者為網路營運者，所謂的使用者滿意度，我們採取傳統運籌科學常用的衡量方式：

A-2(e)、需求預測、資源規劃與運用之基本觀念

A-3、Per-Hop QoS 排程

在 BBQ﹙Budget-Based QoS Management Architecture﹚的架構下，每個封包從傳送端到接收端都遵循預定路徑，假設中間所經歷的網路元件 (router)都有事先預估的停留時間，因此每個封包到達每個router都有預定送出的時間，當封包由傳送端進入網路時，因為IP封包的傳遞時間常是起伏不定，使得封包到達每一個router的時間可能會比原先預估的時間早到或遲到。有鑑於此，我們拋棄 FIFO 的處理順序而按封包的緊急程度及重要性調整處理順序，對於遲到的封包，盡可能提前處理，盡力彌補其損失的時間，而對於早到的封包，則在不影響其行程之下禮讓遲到的封包，如此可增加整體滿意度。但與現有類似的作法不同的是，只要router有能力處理，router並不刻意延遲早到的封包，以免浪費網路資源。

Per-Hop QoS 排程是在每一個 router 內各自進行，如要達到最佳排程，各個router之間必須互相分享資訊，並進行分散式運算，此種計算環境在實務上極難實現，此因router為了加快處理速度，不可能進行太複雜的運算。因此，我們的研究將在兩種假設環境下進行，一是完全獨立排程，每個router 根據自身所知的資訊而不參考其他router 的狀態逕自進行排程，二是前瞻式排程 (Looking Ahead Scheduling)，在此模式下，router會參考封包在後續路程上各router的狀態以進行排程。例如：一個嚴重遲到的封包如果在後續路程上所將經過的router上的負載都很重，而判斷無法在限定時間內到達目的地的話，就會在中途被捨棄，反之，如果後續的router之負載都很輕的話，則可能會保留該遲到的封包，並盡力提前送出，而在後續的router中逐漸彌補所耽誤掉的時間，力求及時到達目的地。

本研究將以二階段進行，第一階段進行獨立排程的研究，第二階段進行前瞻式的排程研究。以下是各階段共用的研究方法：

我們將用profit function 的方式表達進入一個router 的封包的緊急程度及重要性，再配合排程演算法來決定封包排程順序。當封包到達router時， router會依據封包的緊急程度、服務等級以及網路處理能力而賦予封包適當的profit function，scheduler 再根據封包的 profit function 進行排程，以最大化總獲利和為目標，調整封包送出的順序，期望減小接收端之 jitter, delay time, 及 loss rate，以提高服務品質。因為不同的封包排程演算法以及 profit function將會影響服務品質，因此我們的研究將著重於 profit function及排程演算法的設計。

A-3(a) Profit Function 的設計

假設每個進入router 的封包都帶有預定送出時間及服務等級，router 將視情況賦予該封包一個 profit function，scheduler 根據所有封包的 profit function 決定送出的順序，求得最大profit，希望能在最終的接收端呈現較高的服務品質。本研究所考慮的 profit function 力求簡單有效，避免造成 router 太大負擔，有四個參數：

hard deadline: 代表送出封包的截止時間，超過 hard deadline 的封包將無利可圖，必須被捨棄；
soft deadline: 代表送出封包的另一個截止時間，超過 soft deadline 的封包將會面臨遲到的風險，獲利將會下降，但在後續的路程上也許還有補救機會，不一定必須捨棄；
pre soft deadline profit rate: 代表在 soft deadline 之前送出封包時，可獲得之 profit；
post soft deadline profit rate: 代表在 soft deadline 之後送出封包時，可獲得之 profit。

本計畫之初期將採用下列四種簡單的 profit function:

Profit Function 1 (Step-Down)

第一種 profit function 是 Step-Down，當router採用 Step-Down type的 profit function 處理此類封包時，儘可能在 hard deadline 之前送出，其送出時間可早可晚，如果封包無法在 hard deadline 之前送出，則 router 認為此封包無法準時送達接收端，便將其丟棄，不必再浪費網路資源。Router可根據封包在此 router 的預定送出時間及後續網路狀況，設定 hard deadline。最簡單的方法，是將 hard deadline 設為其預定送出時間。採取此種設定的時機是當後續的網路狀況非常擁塞而對於遲到的封包沒有補救機會時，如果還有補救機會時，可把 hard deadline 適度延長。

Profit Function 2 (Slope-Down)

第二種 profit function 是 Slope-Down，類似 Step-Down, 但跟 Step-Down 不同的是，多了一個 soft deadline, 而過了soft deadline 之後，profit 隨著時間下降直到 hard deadline。 Router 在 soft deadline 之前可挑選任一時間送出封包，若過了 soft deadline 則必須盡早送出。 Router可根據封包在此router的預定送出時間及後續網路狀況，設定 soft deadline 與 hard deadline。一個簡單的方法，是將soft deadline設為其預定送出時間，並將 hard deadline 適度延長一段時間。採取此種設定的時機是當後續的網路狀況對於遲到的封包仍有補救機會時。

Profit Function 3 (Slope-Step)

第三種profit function是Slope-Step，當router在處理Slope-Step type的封包時，儘可能在hard deadline之前送出，且其送出時間愈早愈好， hard deadline之處理與設定方法類似 Step-Down。

Profit Function 4 (Double-Slope)

第四種profit function是 Double-Slope，當router處理 Double-Slope type的封包時，會進早送出，但會禮讓部分超過soft deadline 的封包。 soft 與 hard deadline之處理與設定方法類似前面的 profit type.

A-3(b) Router 架構及演算法設計

我們將針對下列兩種router 架構設計排程演算法:

Single Preemptive Queue Router﹙SPQ Router﹚架構

在此架構下router內的個別output queue是由single preemptive queue所構成，而router可將進入的封包插到output queue的任意位置。此種架構可以支援任何一種排程要求，但實際網路中的router為了加快交換速度不會輕易採取preemptive queue 作法，且preemptive queue在硬體實作上花費也會過高，因此本架構僅能作為參考。

Multiple Queue Router﹙MQ Router﹚架構

在此架構之下router中的個別output queue是由數個FIFO queue所組成， router只能將欲送出的封包插入其中一個queue的尾端。在此種架構下我們將設計前端排程器﹙pre-scheduler﹚與後端排程器 ﹙post-scheduler﹚，將進入的封包選取適當的 queue插入。此種router架構比較不會影響router之處理速度，在實際網路之中比較容易被採用。

A-3(c) 不同服務等級的差異化處理

當不同的服務等級的封包進入router 而資源不足時，必須給予差異化待遇，讓資源依優先等級調配，如此可以提高整體滿意度。在我們的架構中，所能著力之處在於依照封包的服務等級選擇一個適當的 profit function 造成差異化待遇。研究的重點即在於如何調配 profit function。由於理論分析的困難，我們將藉由NS-2模擬實驗找出適當的配方。

A-4、服務品質差異化的傳輸通訊協定

如前所述，在新世代網路上，傳統的 TCP/UDP 兩種傳輸協定不一定能應付層出不窮的新型態服務，在本研究中，我們將改良 TCP 加入選擇性重傳的機制，讓上層的應用程式決定部分封包不必保證送達。TCP 只需依照指示，選擇性的保證部分封包的傳送，如此可以讓Video 等服務在資源有限的情況下獲得更好的服務品質。我們將以Video 之傳送為例，證明此法的優越性。

通常一個 video stream 都會運用MPEG壓縮技術大幅減少資料量。 MPEG 壓縮會產生不同作用的 frame，其中最重要的是 I-frame，對影像品質有關鍵性的影響，所以構成I-frame的封包必須要能即時無誤的送達。至於其他種類的 frame 則其重要性較低，如果在傳遞過程中遺失，對影像品質的影響較小，如果不重傳的話，既可以省下一些overhead，又可以不耽誤時間。然而，現今廣為大家所使用的傳輸層通訊協定(TCP/UDP) 卻無法提供差異化的處理。 TCP雖然可以保證每個封包能夠正確的到達，但是卻會因為一些較為不重要封包的遺失去做重傳的動作而造成過多的overhead以及 delay。而 UDP卻因為沒有確保每個封包都要正確到達地特性，所以不會因為重要性較低的封包掉落產生過大的overhead及delay，然而當封包遺失率過大，且掉落的封包大部分是含有I-frame資料時，對於video streaming 的品質也會大打折扣。所以，本研究將針對 streaming 的特性及需求設計一個新的TCP-based的通訊協定 "Partial-Reliable TCP"，使用選擇性重傳封包機制，在一定的等待時間當等級較高的封包掉落遺失時才啟動重傳機制，能夠更有彈性，可以確保重要性較高的封包準確送達，又不會因為重要性較低的封包掉落而重傳造成過大的overhead以及delay 進而提昇傳輸的效能及品質。

此外，本研究將設計一個封包等級的錯誤更正機制以減少重傳頻率。

本研究將以 NS-2 模擬器評估我們所提出的方法，在相同的網路拓墣下，與其它的通訊協定做比較，以PSNR值、lost rate及delay time作為效能評估的標準。

A-5、分散式 P2P Streaming 資料分享

利用 Bit-Torrent 模式進行 P2P Video 線上分享，多半利用 UDP 作為傳輸協定，如此可以能符合 real-time 的需求，但在大規模使用的情況下，網路頻寬不可能無限制的支援此種應用，封包的嚴重遺失將是可以預見的事，對於服務品質的保證將大打折扣，我們將採用所發展的 Partial Reliable TCP/UDP 於分散式 P2P Streaming 資料分享上，在有限度增加負擔的情況下，大幅提升服務品質。

A-6、TCP and SCTP over Ad-Hoc Network

如前所述，在Ad hoc network的環境之下，由於傳輸環境本身的不穩定而容易遺失封包，即使網路上的流量不大時， TCP/SCTP 可能會因為 Backward 回傳的 ACK 遺失而使傳送端以為網路發生壅塞，造成不必要的降速，影響效能。我們將研究提高 TCP/SCTP 在 Ad Hoc Network 上的效能。

Router Assisted Congestion Control

本計畫將提出一個適合 Ad Hoc network 的 TCP/SCTP 擁塞控制協定，由於Ad Hoc network 中每個節點都扮演路由器的角色，我們很容易在路由器中加入某些功能，讓路由器協助 TCP/SCTP 進行壅塞控制。

路由器可以提供的資訊包括鏈結存活與否的狀態、鏈結的剩餘頻寬，鏈結通過的資料流(connection oriented sessions, e.g. TCP/UDP/SCTP)等。傳送端可以利用路由器提供的資訊更精確的判斷網路的壅塞狀況，進行細膩的速率調節，比起依靠封包遺失進行傳輸速度控制的方法而言，一則傳送端可以在網路到達壅塞之前即時調降速率，避免送出過多封包將網路擠爆，其直接的效益是可以降低網路壅塞的機會，二則，可以讓傳送端更快速的達到最佳的傳輸速度，避免浪費頻寬，三則在與其他的協定共存時不會受到歧視（例如: TCP Vegas 與 TCP Reno 共存時， TCP Vegas 將會被排擠無法搶到頻寬，以致無法推行 TCP Vegas）。

本計畫的設計重點在於路由器如何估計剩餘頻寬，如何決定公布剩餘頻寬，以及傳送端如何運用獲得的資訊調節傳送速率。我們將用 NS-2 網路模擬器評估我們的方法的效能。

Multiple ACK SCTP over Ad Hoc Networks

本計畫是將修改 SCTP 利用SCTP中的 Multi-homing 機制要求接收端循著兩條路徑傳送重複的 ACK 增加 ACK 在 Ad Hoc Network 中的存活率，減少傳送端因為沒接到 ACK 而誤判為網路壅塞的機會。

SCTP的特點之一是對於Multi-homing的支援：如下圖所示

建立 SCTP 連線時 (SCTP的連線稱作Association)，傳送端與接收端各可以擁有多個 IP Address並同時在一個 Assoication 之下使用多個連線，而每一組可以使用的 IP Address 都會被 SCTP 當成是一個可傳輸路徑 (Transmission Path) 來看待。當連線建立之後，將使用其中一組 IP Address 當成主要傳輸路徑 (Primary Path)，該路徑主要負責新資料的傳輸，而當有其他傳輸路徑存在時，另外一組網路位址將會被當成次要傳輸路徑 (Secondary Path)，用來當作當資料遺失時的重傳路徑。

如下圖所示：

在本研究中，我們將要求接收端循著兩條路徑傳送重複的 ACK，希望能減少由於 ACK 遺失而讓傳送端誤判為網路壅塞的機率，以免SCTP為了處理網路壅塞而縮小 Congestion Window、降低傳輸速率。我們相信若能提高 ACK 的存活率，將有助於提升整體的 throughput。

我們將先以簡單的方式推算出 ACK 存活率以及 throughput 之間的關係，之後利用 NS-2 模擬器實驗驗證我們推算出的結果。