濾波式的流量控制機制

Abstract

我們根據濾波的理論提出一個新的流量控制的方法，且使用（min,＋）代數運算元來取代傳統的（＋,×）代數運算元。在這個理論中，最重要的部份是依據量測到的輸入量和輸出量，使用"迴旋積"的方法來判別網路的擁塞與否。 首先我們發現在某些特殊的情況下，"頻譜轉換"的技巧並不能在給定輸入量與輸出量時，找到濾波器的對應解。其次，以時間軸的分析技巧發現，在某些的情況下，其濾波器解也不一定不存在。我們因此提出使用"絕對誤差"的估計方法，目的在找一個可靠的估測濾波函式h(t)，使得其與輸入量的"迴旋積"的值，和輸出量的絕對誤差為最小。為了方便豈見，我們採用一階的h(t)，其時軸表示式為c•t+d 。 根據濾波器的理論，濾波函式h(t)就像是輸出的上界，所以可以用在每個窗口終點的輸入量x(t)減去h(t)，來估量網路擁塞的程度。為了有更好的輸出表現，所以我們亦提出同時考量"向前"和"向後"的回饋調節機制；所謂的"向後"調節機制，是讓前一級的節點，根據雙方的擁塞狀態，來決定目前的節點的輸出速度；而"向前"調節的機制，是讓這個節點決定前一級節點的輸出速度調節。此外，我們提出參考過去整體網路擁塞資訊的輔助機制，也就是將後面所有節點的擁塞係數（ｃ,ｄ）向前傳，並運用"迴旋積"整合，以做為後續所有節點的整體擁塞情形的判斷依據。 在實驗中，我們將新提出來的濾波式流量控制機制，與傳統的速率式流量控制機制(rate-based)與信用式流量控制機制(credit-based)作比較。在四個節點的網路架構假設下，可以發現濾波式流量控制機制無論在輸出量(throughput)和封包遺掉率(packet loss rate)，都跟傳統的流量控制機制有幾乎相當的效能，但是在輸出量的變異性上，卻是明顯的較其他兩者為優，所以濾波式流量控制機制對於流量變化較大的網路表現較為強健。但當網路的節點超過四個以上，在各種效能表現上，就可以看出濾波式流量控制機制，比傳統的機制流量控制要好。

In this thesis, we propose a new flow control scheme based on filter theory, where the conventional (+,×) algebra is replaced by the (min,+) algebra. An essential part of the filter flow control is to determine the filter formula for the measured arrival and departure so that we can use “convolution” of all the intermediate node filters to estimate the end-to-end congenstionness. We first show that it is unlikely to determine the exact filter expression for given input arrival and output departure in terms of spectrum analysis or transformation technique. We then prove in terms of time-domain analysis that there are situations where the filter formula (for given arrival and departure processes) does not exist. We therefore turn to an absolute-error approximation of the filter expression for which the output due to the measured input and the estimated filter yield minimum absolute-error with the true departure. For ease of convolution calculation, we only take first-order filter approximate h(t) whose formula can be expressed as c•t+d, where t is the time scale. Since h(t), by filter theory, behaves as an upper bound to the departure process, we then employ the sample of x(t)-h(t) at the end of each measured window as a degree of crowdedness over the network, where x(t) is the non-decreasing input arrival process. In order to enhance the performance (throughput), we also propose to include both the feedback and feedforward regulation rules in our flow control scheme. The feedback regulation aims at letting the previous node to regulate the departure rate once crowdedness is sensed. The feedforward regulation focuses on letting the node to re-decide the outgoing rate once crowdedness of its subsequent nodes are sensed. Furthermore, as aforementioned, we also convolve the filter (i.e., c and d) of the subsequent nodes to estimate the degree of congestionness, which we named history information. As expected, each node will periodically pass its estimate of c and d to its previous node. Experiment results over a four-node network will be performed on conventional rate-based and credit-based, as well as our newly proposed filter-based flow control schemes. Simulations show that the filter-based flow control can reach almost the same throughput and packet loss rate as the conventional rate-based and credit-based flow control schemes; however, it results in a much smaller variance of throughput than the other two. As a result, the filter-based flow control is more robust to variability of traffic patterns. When a system involved with more than four network nodes is considered, the superiority of filter-based flow control in its robustness becomes more certain.