Geodesic
Analysis of Transmissions Scheduling with Packet Fragmentation
Discrete mathematics & theoretical computer science, Tome 4 (2000-2001) no. 2.

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2001_4_2_a5,
     author = {Namman, Nir and Rom, Rapha\"el},
     title = {Analysis of {Transmissions} {Scheduling} with {Packet} {Fragmentation}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {4},
     number = {2},
     year = {2000-2001},
     doi = {10.46298/dmtcs.277},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.277/}
}
TY  - JOUR
AU  - Namman, Nir
AU  - Rom, Raphaël
TI  - Analysis of Transmissions Scheduling with Packet Fragmentation
JO  - Discrete mathematics & theoretical computer science
PY  - 2000-2001
VL  - 4
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.277/
DO  - 10.46298/dmtcs.277
LA  - en
ID  - DMTCS_2001_4_2_a5
ER  - 
%0 Journal Article
%A Namman, Nir
%A Rom, Raphaël
%T Analysis of Transmissions Scheduling with Packet Fragmentation
%J Discrete mathematics & theoretical computer science
%D 2000-2001
%V 4
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.277/
%R 10.46298/dmtcs.277
%G en
%F DMTCS_2001_4_2_a5
Namman, Nir; Rom, Raphaël. Analysis of Transmissions Scheduling with Packet Fragmentation. Discrete mathematics & theoretical computer science, Tome 4 (2000-2001) no. 2. doi : 10.46298/dmtcs.277. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.277/

Cité par Sources :