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 disallowing new demands to be served, 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 to create a defragmented link. We propose an algorithm called MobiPack that is optimal in its degragmentation quality.