Algorithms for Multiplex Bundling in a Telecommunications Network

R. D. Doverspike
Additional contact information
R. D. Doverspike: Bell Communications Research, Red Bank, New Jersey

Operations Research, 1991, vol. 39, issue 6, 925-944

Abstract: The function of a digital telecommunications network is to transport demand of digital signals between pairs of locations. To achieve this economically, multiplex equipment packs lower rate digital signals into higher rate signals for routing over transmission facility links. Given a multiperiod demand forecast and demand routing plan, the multiplex bundling problem minimizes equipment and transmission costs by demultiplexing the higher rate signals into their lower rate components at various nodes along paths to allow lower rate signals from different sources and sinks to be combined. However, exact solution of the multiplex bundling problem is intractable, and therefore this paper presents a heuristic two-phased approach. Phase 1 formulates a single-period, capacitated routing model. The Phase 1 solution method is to first solve a problem with relaxed capacity constraints and then solve a 0–1 multiconstraint knapsack problem to obtain feasibility. Computational results show that the Phase 1 heuristic produces near-optimal results. Phase 2 exactly solves a multiperiod problem for each demand re-routing chosen in Phase 1 by using a single-stage dynamic programming algorithm. The Phase 2 algorithm reduces the state space by taking advantage of state conditions at optimality.

Keywords: communications: telecommunications transmission networks; facilities/equipment planning: capacity expansion of telecommunications equipment; networks/graphs; heuristics: network design optimization (search for similar items in EconPapers)
Date: 1991
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.39.6.925 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:39:y:1991:i:6:p:925-944

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().