کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10338968 | 693954 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Analysis of virtual-time complexity in weighted fair queuing
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
شبکه های کامپیوتری و ارتباطات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Analysis of virtual-time complexity in weighted fair queuing Analysis of virtual-time complexity in weighted fair queuing](/preview/png/10338968.png)
چکیده انگلیسی
This paper presents two fundamental theorems that show that the O(N) complexity for updating the virtual time in a weighted fair queuing (WFQ) scheduler with N sessions is caused mainly by simultaneous departures of packets, and not by iterated deletion as was previously claimed. Iterated deletion is caused by an 'avalanche' of consecutive, but not necessarily simultaneous, departures that incur more departures due to increments in available bandwidth from idling sessions. Iterated deletion potentially leads to large numbers of consecutive departures within a given time period. The number of departures is, however, a function of such implementation details as the resolution of the time-stamp and the scheduler clock. On the other hand, the problem of simultaneous time-stamps cannot be solved by any increase in the time resolution of virtual-time update. Essentially, all equal time-stamps must be processed during a single virtual-time update operation. We present a proof to show that O(N) simultaneous departures can occur during a single virtual-time update. We also show that this is a fundamental property of WFQ that holds even under the most restrictive conditions, viz. all packets arrive serially to the scheduler (no simultaneous arrivals), and the input bit-rate does not exceed the output bit-rate.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computer Communications - Volume 28, Issue 7, 2 May 2005, Pages 802-810
Journal: Computer Communications - Volume 28, Issue 7, 2 May 2005, Pages 802-810
نویسندگان
Hussein Alnuweiri, Haitham Tayyar,