Stable Partition Problem
- PDF / 4,383,294 Bytes
- 135 Pages / 547.087 x 737.008 pts Page_size
- 86 Downloads / 201 Views
S
S
Schedulers for Optimistic Rate Based Flow Control 2005; Fatourou, Mavronicolas, Spirakis PANAGIOTA FATOUROU Department of Computer Science, University of Ioannina, Ioannina, Greece
Keywords and Synonyms Rate allocation; Rate adjustment; Bandwidth allocation
Problem Definition The problem concerns the design of efficient rate-based flow control algorithms for virtual-circuit communication networks where a connection is established by allocating a fixed path, called session, between the source and the destination. Rate-based flow-control algorithms repeatedly adjust the transmission rates of different sessions in an end-to-end manner with primary objectives to optimize the network utilization and achieve some kind of fairness in sharing bandwidth between different sessions. A widely-accepted fairness criterion for flow-control is max-min fairness which requires that the rate of a session can be increased only if this increase does not cause a decrease to any other session with smaller or equal rate. Once max-min fairness has been achieved, no session rate can be increased any further without violating the above condition or exceeding the bandwidth capacity of some link. Call max-min rates the session rates when max-min fairness has been reached. Rate-based flow control algorithms perform rate adjustments through a sequence of operations in a way that the capacities of network links are never exceeded. Some of these algorithms, called conservative [3,6,10,11,12], employ operations that gradually increase session rates until
they converge to the max-min rates without ever performing any rate decreases. On the other hand, optimistic algorithms, introduced more recently by Afek, Mansour, and Ostfeld [1], allow for decreases, so that a session’s rate may be intermediately be larger than its final max-min rate. Optimistic algorithms [1,7] employ a specific rate adjustment operation, called update operation (introduced in [1]). The goal of an update operation is to achieve fairness among a set of neighboring sessions and optimize the network utilization in a local basis. More specifically, an update operation calculates an increase for the rate of a particular session (the updated session) for each link the session traverses. The calculated increase on a particular link is the maximum possible that respects the maxmin fairness condition between the sessions traversing the link; that is, this increase should not cause a decrease to the rate of any other session traversing the link with smaller rate than the rate of the updated session after the increase. Once the maximum increase on each link has been calculated the minimum among them is applied to the session’s rate (let e be the link for which the minimum increase has been calculated). This causes the decrease of the rates of those sessions traversing e which had larger rates than the increased rate of the updated session to the new rate. Moreover, the update operation guarantees that all the capacity of link e is allocated to the sessions traversing it (so the bandwidth of t
Data Loading...
