Transcript LTD

Logical Topology Design
1
Logical Topology vs. Physical
Topology
• Optical layer provides lightpaths between
pairs of client layer equipment (SONET
TMs, IP routers, ATM switches)
• The lightpaths and the client layer network
nodes form a logical topology
• The OXCs and optical fibers form a
physical topology
2
Logical Topology Design
• Lightpath can eliminate electronic processing at
intermediate nodes in the client layer => save
client layer switch ports/electronic processing
– Cost: more wavelength required at the optical layer
• Ideally: use a fully-connected logical topology,
i.e., setup a lightpath between every pair of
source-destination nodes
– Not possible for larger networks due to limit on #
wavelengths per fiber
3
Logical Topology Design
• Design logical topology based on given traffic
patterns and the physical topology
– Traffic routed over logical topology
– Traffic may travel more than one logical hops
• A logical topology can be reconfigured by
changing the set of lightpaths
– Adaptability (when traffic patterns change)
– Self-healing capability (when physical topology
changes due to network component failures)
– Upgradability (when physical topology changes due to
addition or upgrading of network components)
4
A Logical Topology Design
Problem (LDT)
• Given:
– Physical topology
– Packet arrival rates for every source-destination pair
• Objective:
– Compute a logical topology with minimal congestion
(congestion is the maximum traffic routed over a
logical link)
• Why minimize congestion?
– Low congestion leads to low packet queuing delay
– LT can accommodate the maximum traffic scale-up
• Note: need solve the packets routing problem together with
LDT
5
LTD
Assumptions:
• No limit on the number of wavelengths in the
optical layer
• All lightpaths are bidirectional: if we set up a
lightpath from node i to node j, we also set up a
lightpath from node j to node i
• Each IP router has at most Δ input ports and Δ
output ports
– constrains cost of IP routers and number of lightpaths
• Traffic between the same pair of nodes can be split
over different paths
6
Mathematical Formulation
• See handout for problem formulation
• The objective functions and the constraints are
linear functions of the variables
– Linear program (LP): all variables are real
– Integer linear program (ILP): all variables must take
integer values
– Mixed integer linear program (MILP): some variables
must take integer values
• There are efficient algorithms for solving LPs
• ILPs and MILPs are NP-hard
7
A Heuristic for LTD-MILP
• Use LP-relaxation and rounding
• Terms used in mathematical programming
– Feasible solution: any set of values of the
variables that satisfy all the constraints
– Optimal solution: a feasible solution that
optimizes the objective function
– Value: value of the objective function achieved
by any optimal solution
8
A Heuristic for LTD-MILP
• LP-relaxation: if we replace the constraints bij 
{0,1} by 0  bij  1, LTD-MILP reduces to LDTLP
• The value of the LTD-LP is a lower bound on the
value of the LTD-MILP
– The bound is called the LP-relaxation bound
• Routing-LP: the values of the bij are fixed at 0 or 1
such that the degree constraints are satisfied
– The problem is to route the packets over the logical
topology to minimize the congestion
– The value of routing-LP is an upper bound on the value
of LTD-MILP
9
A Heuristic for LTD-MILP
• Solve LTD-LP
• Fix the values of bij in LTD-LP to 0 or 1
using the rounding algorithm
• Solve the routing-LP
10
Rounding Algorithm
•
•
Idea: round the bij in LTD-LP to the closet
integer
Rounding algorithm
1. Arrange the values of the bij obtained in an optimal
solution of the LTD-LP in decreasing order
2. Starting at the top of the list, set each bij = 1 if the
degree constraints would not be violated. Otherwise,
set the bij = 0.
3. Stop when all the degree constraints are satisfied or
the bijs are exhausted
11