一個以分群為基礎用在主動式佇列管理之壅塞控制演算法

Abstract

在壅塞的網路中，產生flow數目越多的節點會得到比較多的頻寬，這會使得其他節點得不到公平的服務。我們得知使用多個虛擬佇列(virtual queue)可以解決節點flow數目之差異性所造成網路不公平的問題。當網路中的每個節點都使用一個虛擬佇列時，在每個單位時間動態地去調整每個虛擬佇列的初始丟棄機率(initial drop probability)就可以使每個節點得到公平的頻寬。但是，當節點很多時，使用很多的虛擬佇列並不實際。因此在本篇論文中，我們希望將網路中的每一個節點作分群，將flow數目相差不多的節點分在相同群組。被分在相同群組的節點共同使用一個虛擬佇列。在實驗中，實作模擬工具軟體ns2，將會幫助驗證。若是每個節點所獲得的頻寬差異越小，Fairness index會越接近1，代表網路越公平。從計算fairness index中，我們可以了解在網路中節點分群的結果。舉例，從實驗中，當網路有50個節點，使用10個虛擬佇列，其fairness index等於0.984。我們所提出的方法可以有效減少使用虛擬佇列的個數，還可以讓網路中的每個節點可以得到合理公平的頻寬。

In a congested network, an aggressive node could acquire more bandwidth for itself by intentionally increasing the number of flows. This leads to a serious problem of fairness in bandwidth allocation. This problem can be solved by a technique known as virtual queue. In the network, each node employs a virtual queue with an initial drop probability. The probability is dynamically adjusted for each node to acquire a fair share of the bandwidth. However, the virtual-queue technique has a major drawback, it bccomes considerably difficult and impractical to manage a large number of virtual queues, as the number of nodes explodes. In this thesis, we propose an efficient method to deal with this problem. Our idea is to sort nodes into groups on the basis of flow numbers. Nodes with similar flow numbers are placed in a group and they share a single virtual queue for bandwidth allocation. We verify the effectiveness of our proposed method through a simulation tool - ns2. By calculating fairness index, we are able to evaluate the performance of our method operating in various conditions. The simulation results show that the proposed method can effectively reduce the number of virtual queues in use. In addition, it guarantees that all the nodes receive a fair treatment of bandwidth allocation.