Mobipack: optimal hitless SONET defragmentation in near-optimal cost

We study the problem of bandwidth fragmentation in links that comprise rings and meshes in SONET networks. Fragmentation is a serious challenge for network operators since it creates "holes" in the transport pipe causing new demands to be rejected, in spite of sufficient bandwidth being available. Unlike the well-studied, general fragmentation problem, link defragmentation is "hard" and novel due to some unique constraints imposed by the SONET standard. Since a defragmentation operation typically occurs on a network carrying live traffic, in addition to the "quality" of the output, any link defragmentation algorithm has to avoid traffic hit and also optimize the "cost" of reorganizing circuits. We propose an algorithm called mobipack that is optimal in its defragmentation quality. Moreover, we demonstrate via extensive simulations, that it also achieves its goal in a hitless manner with only marginal additional cost over the optimal, making it extremely attractive to use in practice