Discrete Mathematics & Theoretical Computer Science, Vol 4, No 2 (2001)

Font Size:  Small  Medium  Large
DMTCS vol 4 no 2 (2001), pp. 139-156

Discrete Mathematics & Theoretical Computer Science


Volume 4 n° 2 (2001), pp. 139-156

author:Nir Menakerman and Raphael Rom
title:Analysis of Transmissions Scheduling with Packet Fragmentation
keywords:scheduling, bin packing, algorithm, average case analysis, CATV, fragmentation
abstract:We investigate a scheduling problem in which packets, or datagrams, may be fragmented. While there are a few applications to scheduling with datagram fragmentation, our model of the problem is derived from a scheduling problem present in data over CATV networks. In the scheduling problem datagrams of variable lengths must be assigned (packed) into fixed length time slots. One of the capabilities of the system is the ability to break a datagram into several fragments. When a datagram is fragmented, extra bits are added to the original datagram to enable the reassembly of all the fragments. We convert the scheduling problem into the problem of bin packing with item fragmentation, which we define in the following way: we are asked to pack a list of items into a minimum number of unit capacity bins. Each item may be fragmented in which case overhead units are added to the size of every fragment. The cost associated with fragmentation renders the problem NP-hard, therefore an approximation algorithm is needed. We define a version of the well-known Next-Fit algorithm, capable of fragmenting items, and investigate its performance. We present both worst case and average case results and compare them to the case where fragmentation is not allowed.
reference: Nir Menakerman and Raphael Rom (2001), Analysis of Transmissions Scheduling with Packet Fragmentation, Discrete Mathematics and Theoretical Computer Science 4, pp. 139-156
bibtex:For a corresponding BibTeX entry, please consider our BibTeX-file.
ps.gz-source:dm040207.ps.gz (0 K)
ps-source:dm040207.ps (177 K)
pdf-source:dm040207.pdf (128 K)

The first source gives you the `gzipped' PostScript, the second the plain PostScript and the third the format for the Adobe accrobat reader. Depending on the installation of your web browser, at least one of these should (after some amount of time) pop up a window for you that shows the full article. If this is not the case, you should contact your system administrator to install your browser correctly.

Due to limitations of your local software, the two formats may show up differently on your screen. If eg you use xpdf to visualize pdf, some of the graphics in the file may not come across. On the other hand, pdf has a capacity of giving links to sections, bibliography and external references that will not appear with PostScript.

Automatically produced on Tue Oct 30 12:57:32 CET 2001 by gustedt