Change search
ReferencesLink to record
Permanent link

Direct link
On Channel Failures, File Fragmentation Policies, and Heavy-Tailed Completion Times
Indian Institute of Technology Bombay.
KTH, School of Electrical Engineering (EES), Centres, ACCESS Linnaeus Centre. KTH, School of Electrical Engineering (EES), Automatic Control.
Monash University. (Centre for Advanced Internet Architectures)
California Institute of Technology.
Show others and affiliations
2014 (English)In: IEEE/ACM Transactions on Networking, ISSN 1063-6692, E-ISSN 1558-2566, Vol. PP, no 99Article in journal (Refereed) Published
Abstract [en]

It has been recently discovered that heavy-tailed completion times can result from protocol interaction even when file sizes are light-tailed. A key to this phenomenon is the use of a restart policy where if the file is interrupted before it is completed, it needs to restart from the beginning. In this paper, we show that fragmenting a file into pieces whose sizes are either bounded or independently chosen after each interruption guarantees light-tailed completion time as long as the file size is light-tailed; i.e., in this case, heavy-tailed completion time can only originate from heavy-tailed file sizes. If the file size is heavy-tailed, then the completion time is necessarily heavy-tailed. For this case, we show that when the file size distribution is regularly varying, then under independent or bounded fragmentation, the completion time tail distribution function is asymptotically bounded above by that of the original file size stretched by a constant factor. We then prove that if the distribution of times between interruptions has nondecreasing failure rate, the expected completion time is minimized by dividing the file into equal-sized fragments; this optimal fragment size is unique but depends on the file size. We also present a simple blind fragmentation policy where the fragment sizes are constant and independent of the file size and prove that it is asymptotically optimal. Both these policies are also shown to have desirable completion time tail behavior. Finally, we bound the error in expected completion time due to error in modeling of the failure process. 

Place, publisher, year, edition, pages
IEEE Press, 2014. Vol. PP, no 99
National Category
Control Engineering
Research subject
Electrical Engineering
URN: urn:nbn:se:kth:diva-164309DOI: 10.1109/TNET.2014.2375920ISI: 000370969300040ScopusID: 2-s2.0-84962449239OAI: diva2:805447

QC 20150420

Available from: 2015-04-15 Created: 2015-04-15 Last updated: 2016-03-23Bibliographically approved

Open Access in DiVA

fulltext(2086 kB)23 downloads
File information
File name FULLTEXT01.pdfFile size 2086 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusIEEEXplore

Search in DiVA

By author/editor
Andreasson, Martin
By organisation
ACCESS Linnaeus CentreAutomatic Control
In the same journal
IEEE/ACM Transactions on Networking
Control Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 23 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 43 hits
ReferencesLink to record
Permanent link

Direct link