Packet-Dropping-Based Buffer Management Algorithms In The Internet

In the Internet, packet-dropping-based buffer mangement algorithm is an important module in a packet-forwarding device. By employing the buffer management algorithms, (1) TCP flows can be protected, (2) without per-flow queueing, the bandwidth of unresponsive and responsive flows can be balanced even with FCFS (First-Come-First-Served) scheduler, (3) based on per-flow queueing, the bandwidth of unresponsive and responsive flows, as well as that of pure responsive flows can be balanced at the same time, and (4) in a multi-priority network, different bandwidth can be allocated according to a predetermined proportion.In Chaper I, a systematic classification method aimed at packet-dropping-based buffer management algorithms is presented, and some dominant packet-dropping-based buffer management algorithms in today's network are introduced.In order to protect TCP bandwidth in an environment mixed with TCP and non-TCP-friendly flows, RED-BC (Random Early Detection with Barrier Control) algorithm is presented in Chapter II. RED-BC not only inherits the benefits of RED (Random Early Detection), but also is able to discard the arriving packets from non-TCP-friendly flows and hence to protect TCP bandwidth. Because of its fitness to be combined with a FCFS scheduler, RED-BC is easy to implement by upgrading the original RED module with a small calculation resource consuming. Due to its function to penalize non-TCP-friendly flows, RED-BC can stimulate the emplyment of end-to-end congestion control mechanisms, and alleviate the severity of danger of congestion collapse.If we hope to allocate the bandwidth balancely between unresponsive and responsive flows with a FCFS scheduler, RED-CAP (RED with Control byAdvance Probabilities) algorithm in Chapter III is a condidate. Based on the packet drop history in RED, this algorithm is able to find aggressive flows and then discards the packets from these flows with the advance probabilities, to avoid the excessive bandwidth occupation by them.For the sake of allocating bandwidth fairer both in an environment mixed with unresponsive and responsive flows and in one full of TCP flows, FRIDAY (Fair Random Indication with Discarding Aggressiveness Yardstick) algorithm is presented and researched, combined with a FCFS and FQ (Fair Queueing) scheduler, in Chapter IV. FRIDAY supports shared buffer as well as per-flow queueing, and calculates the arriving rate for each flow, which provides isolation and protection among different flows. FRIDAY can increase TCP fairness, guarantee high link utilization, and maintain a short average waiting time in the queue at the same time. Using an analytic method, we show the EWMA weight of FRIDAY, i.e. w, can be handled to control the threshold of regarding a bursty traffic as the most aggressive flow. Based on simulations, it is proved that (1) FRIDAY can give TCP protection from the aggressiveness of high-rate UDP flows to some extent; (2) FRIDAY is effective in the case of one-way TCP transmitting FTP; (3) In the case of transmitting ON-OFF Pareto traffic and two-way TCP with higher burstness, FRIDAY is able to provide a higher fairness than LQD (Longest Queue Drop) with the same scheduling algorithm; (4) In the case of multiple bottleneck links, the fairness of FRIDAY is still better than LQD and RED. Besides, in the process of study FRIDAY, we find that FQ-RED is not necessarily to give a higher fairness than FCFS-RED.In order to allocate different bandwidth to different flows in a network supporting multiple priorities according to a predetermined proportion, WFRIDAY (Weighted FRIDAY), which is an extension version of FRIDAY, is presented in Chapter V. To control different bandwidth for different priority, WFRIDAY employs the concept of virtual arriving rate. From the view of EWMA weight, the availability of different bandwidth allocation is proved by ananalytic method. In order to evaluate the results of bandwidth allocation of this algorithm, we present the concept of weighted goodput fairness coefficient. WFRIDAY is able...