Paper Info
Title
Fair and efficient scheduling in data ferrying networks
Abstract
Data-ferrying disconnection-tolerant networks allow remote rural areas to access the Internet at very low cost, making them viable alternatives to more expensive access technologies such as DSL, CDMA, and dial-up. In such a network, an Internet-based proxy gathers data from the Internet and sends it to a set of edge nodes called "gateways", from which data ferries, such as buses and cars, opportunistically pick up the data using short-range WiFi as they drive past, and deliver it wirelessly to kiosks in remote villages. In this context, we pose the following question: assuming knowledge of ferry schedules, when and to which gateway should the proxy send each data bundle so that the overall delay is minimized and the bandwidth is shared fairly among competing kiosks? We show that a well-known schedule-aware routing scheme proposed in the literature, i.e., EDLQ [11] is far from optimal. Moreover, EDLQ does not provide means to enforce bandwidth allocations. To remedy these problems, we employ a token bucket mechanism to decouple fairness and delay minimization concerns. We also describe a utility-maximizing scheduler based on the classical minimum-cost network flow problem, that finds optimal schedules. Through simulations, we show that our scheme performs at least as well as EDLQ in scenarios that favour EDLQ, yet achieves up to 40% reduction in delay in those that do not.
Year
DOI
Venue
2007
10.1145/1364654.1364671
CoNEXT
Keywords
Field
DocType
efficient scheduling,classical minimum-cost network flow,data ferry,optimal schedule,internet-based proxy,overall delay,expensive access technology,bandwidth allocation,favour edlq,data bundle,disconnection-tolerant network,addressing,network flow,routing,rural area,lisp
Flow network,Token bucket,Computer science,Digital subscriber line,Scheduling (computing),Computer network,Default gateway,Schedule,Bandwidth (signal processing),The Internet,Distributed computing
Conference
Citations 
PageRank 
References 
22
1.26
19
Authors
2
Name
Order
Citations
PageRank
Shimin Guo1516.95
Srinivasan Keshav23778761.32