Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form

Scheduling in Networks with Limited Buffers

Elhaddad, Mahmoud (2010) Scheduling in Networks with Limited Buffers. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Primary Text

Download (648kB) | Preview


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).


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairMelhem, Ramimelhem@cs.pitt.eduMELHEM
Committee MemberMosse, Danielmosse@cs.pitt.eduMOSSE
Committee MemberPruhs, Kirk
Committee MemberKrishnamurthy, 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:, etd-08132010-112515
Date Deposited: 10 Nov 2011 19:59
Last Modified: 15 Nov 2016 13:49


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item