200 S Laurel Ave - Bldg A

Middletown, NJ

http://www.research.att.com/~maxzhang/

A biased random-key genetic algorithm for wireless backhaul network design

Carlos De , Mauricio Resende, Weiyi Zhang, Rakesh Sinha, Kenneth Reichmann, Robert Doverspike, F. K. Miyazawa

Applied Soft Computing,
2015.
[PDF]
[BIB]

Elsevier Copyright

The definitive version was published in 2015. , 2015-03-31

{This paper describes a biased random-key genetic algorithm for a
real-world wireless backhaul network design problem. This is a novel
problem, closely related to variants of the Steiner tree problem and
the facility location problem. %We seek to build one or more $h$-hop
trees Given a parameter $h$, we want to build a forest where each tree
has at most $h$ hops. Each tree is rooted at specific nodes, called
root nodes, and has leaves at demand nodes, where traffic originates.
Candidate Steiner nodes do not have any demand but represent locations
where we can install cellsites to cover the traffic and equipment to
backhaul the traffic to the cellular core network. Each Steiner node
can cover demand nodes within a given distance, subject to a capacity
constraint. The aggregate set of constraints may make it impossible to
cover or backhaul all demands. A revenue function computes the revenue
associated with the total amount of traffic covered and backhauled
to the root nodes. The objective of the problem is to build a forest
that maximizes the difference between the total revenue and the cost
associated with the installed equipment. Although we will have a
forest when we consider only the backhaul links and root nodes, the
addition of demand vertices can induce undirected cycles, resulting
in a directed acyclic graph. We consider instances of this problem with
several additional constraints that are motivated by the requirements of
real-world telecommunication networks.}

Constraint Routing and Regenerator Site Concentration in ROADM Networks

Rakesh Sinha, Angela Chiu, Guangzhi Li, Weiyi Zhang, Sheryl Woodward, Robert Doverspike, Peter Magill, Balagangadhar Bathula, bergman, Mark Feuer

Journal of optical communications and networking (JOCN),
2013.
[PDF]
[BIB]

Optical Society of America Copyright

The definitive version was published in 2013 , Volume 5, Issue 11, 2013-11-01

{Advances in the development of colorless and
non-directional reconfigurable optical add-drop multiplexers
(ROADMs) enable flexible pre-deployment of optoelectronic
regenerators (reshaping, retiming, and reamplifying
known as 3R) in future optical networks. Compared to
the current practice of installing a regenerator only when
a circuit needs them, pre-deployment of regenerators in
specific sites will allow service providers to achieve rapid
provisioning such as Bandwidth-on-Demand (BoD) service
and fast restoration. Concentrating the pre-deployment of
regenerators in a subset of ROADM sites will achieve high
utilization and reduces the network operational costs. We
prove the resulting optimization problem is NP-hard and
provide the proof. We present an efficient heuristic for this
problem that takes into account both the cost of individual
circuits (regenerator cost and transmission line system
cost) and the number of regenerator sites. We validate our
heuristic approach with Integer Linear Programming (ILP)
formulations for a small network. Using specific network
examples we show that our heuristic has near optimal performance
under most studied scenarios and cost models. We
further enhance the heuristic to incorporate the probability
of a demand for each circuit. This enables a reduction in
the number of regenerator sites, by allowing circuits to
use costlier paths if they have low probability of being
needed. We also evaluate the heuristic to determine the extra
regenerator sites required to support diverse routing. In this
paper we provide detailed analysis, pseudocodes, and proofs
for the models previously presented in [1], [2], and compare
the heuristic results with Integer Linear Programming (ILP)
for a small scale network topology.}

Cost Optimization Using Regenerator Site Concentration and Routing in ROADM Networks

Rakesh Sinha, Angela Chiu, Mark Feuer, Guangzhi Li, Sheryl Woodward, Weiyi Zhang, Balagangadhar G Bathula, Keren Bergman, Robert Doverspike, Peter Magill

DRCN 2013,
2013.
[PDF]
[BIB]

IEEE Copyright

This version of the work is reprinted here with permission of IEEE for your personal use. Not for redistribution. The definitive version was published in 2012. , 2013-03-04

{The advent of colorless and non-directional reconfigurable
optical-add-drop multiplexers (ROADMs) will enable
flexible pre-deployment of optoelectronic regenerators in future
optical networks. Compared to the current practice of installing
regenerators only when a circuit needs them, pre-deployment
will allow service providers to achieve rapid provisioning and
restoration. The pre-deployed regenerators should be concentrated
in a selected subset of ROADM sites in order to attain high
utilization and to reduce operational costs. We prove that the
resulting optimization problem is NP-hard and present an efficient
heuristic for this problem that takes into account both the cost of
individual circuits (regenerator cost and transmission line system
cost) and the probability of a given circuit request, as well as
the number of regenerator sites. We provide various methods
to reduce the number of regenerator sites, if low probability
demands are allowed to have slightly costlier paths. Specific
network examples show that the proposed heuristic has near
optimal performance under most studied scenarios. We present
results for several different cost models. We have also evaluated
the heuristic for survivable optical networks, in which a second,
disjoint path must be supported for each circuit.}