Fragmented Random Structures
Ed Coffman, Robert Margolies, Peter M. Winkler, Gil Zussman · 2014
Computers with hard-disk storage and networks with dynamic spectrum access illustrate resources that allow fragmented items – in these examples, items are files and spectra, respectively. In our discrete model of such systems, the resource is a sequence of slots. There is a queue of items awaiting allocations of the resource; the queue is served in FIFO order. Specified for each item are the number of slots needed by the item, and for what period of time. Under the key assumption that an item’s allocation can not be changed prior to its departure, fragmentation in the form of alternating gaps and allocated resource builds up as items come and go, regardless of the allocation algorithm adopted. The improvements in resource utilization created by fragmentation are countered by the added cost of manipulating fragmented items, so how fragmentation evolves is an important performance issue. Within a baseline probability model of the system operating at capacity, we prove that, in the stationary limit under any practical algorithm, almost all items are completely fragmented, i.e., items of size i are fragmented into i disjoint slots. In the full paper, this result is balanced by many experimental results which show that, in reality, the times to approach steady-state fragmentation are typically exceptionally long, and hence that even nearly complete fragmentation is often of no concern.