Elhaddad, Mahmoud
(2010)
Scheduling in Networks with Limited Buffers.
Doctoral Dissertation, University of Pittsburgh.
(Unpublished)
Abstract
In networks with limited buffer capacity, packet loss can occur at a link even when the average packet arrival rate is low compared to the link's speed. To offer strong loss-rateguarantees, ISPs may need to adopt stringent routing constraints to limit the load at the network links and the routing path length. However, to simultaneously maximize revenue, ISPs should be interested in scheduling algorithms that lead to the least stringent routing constraints. This work attempts to address the ISPs needs as follows. First, by proposing an algorithm that performs well (in terms of routing constraints) on networks of output queued (OQ) routers (that is, ideal routers), and second, by bounding the extra switch fabric speed and buffer capacity required for the emulationof these algorithms in combined input-output queued (CIOQ) routers.The first part of the thesis studies the problem of minimizing the maximum session loss rate in networks of OQ routers. It introduces the Rolling Priority algorithm, a local online scheduling algorithm that offers superior loss guarantees compared to FCFS/Drop Tail and FCFS/Random Drop. Rolling Priority has the following properties: (1) it does not favor any sessions over others at any link, (2) it ensures a proportion of packets from each session are subject to a negligibly small loss probability at every link along the session's path, and (3) maximizes the proportion of packets subject to negligible loss probability. The second part of the thesis studies the emulation of OQ routers using CIOQ. The OQ routers are equipped with a buffer of capacity B packets at every output. For the family of work-conserving scheduling algorithms, we find that whereas every greedy CIOQ policy is valid for the emulation of every OQ algorithm at speedup B, no CIOQ policy is valid at speedup less than the cubic root of B-2 when preemption is allowed. We also find that CCF, a well-studied CIOQ policy, is not valid at any speedup less than B. We then introduce a CIOQ policy CEH, that is valid at speedup greater than the square root of 2(B-1).
Share
| Citation/Export: |
|
| Social Networking: |
|
Details
| Item Type: |
University of Pittsburgh ETD
|
| Status: |
Unpublished |
| Creators/Authors: |
|
| ETD Committee: |
| Title | Member | Email Address | Pitt Username | ORCID |
|---|
| Committee Chair | Melhem, Rami | melhem@cs.pitt.edu | MELHEM | | | Committee Member | Mosse, Daniel | mosse@cs.pitt.edu | MOSSE | | | Committee Member | Pruhs, Kirk | | | | | Committee Member | Krishnamurthy, Prashant | | | |
|
| Date: |
30 September 2010 |
| Date Type: |
Completion |
| Defense Date: |
6 May 2010 |
| Approval Date: |
30 September 2010 |
| Submission Date: |
13 August 2010 |
| Access Restriction: |
5 year -- Restrict access to University of Pittsburgh for a period of 5 years. |
| Institution: |
University of Pittsburgh |
| Schools and Programs: |
Dietrich School of Arts and Sciences > Computer Science |
| Degree: |
PhD - Doctor of Philosophy |
| Thesis Type: |
Doctoral Dissertation |
| Refereed: |
Yes |
| Uncontrolled Keywords: |
packet routing; Packet-switched networks; small buffers |
| Other ID: |
http://etd.library.pitt.edu/ETD/available/etd-08132010-112515/, etd-08132010-112515 |
| Date Deposited: |
10 Nov 2011 19:59 |
| Last Modified: |
15 Nov 2016 13:49 |
| URI: |
http://d-scholarship.pitt.edu/id/eprint/9087 |
Metrics
Monthly Views for the past 3 years
Plum Analytics
Actions (login required)
 |
View Item |
![[feed]](/images/feed-icon-32x32.png){kind=icon}