Transcript Network Design

Network Resource Design Overview
CSC 401: Fall, 2011, Section 001
Positioning

Networks must be designed (resource
provisioned)
 Design should proceed on the basis of
–
–

What use the network is likely to be put to
What behavior is expected or desired from network
Different answers to above questions
–
Will result in different approach to design
Copyright Rudra Dutta, NCSU, Fall, 2011
Network Traffic


Ultimately, networks exist to serve traffic (enable traffic
to be carried)
What is traffic?
–

That which occupies / is carried by links
Traffic is offered to the network by/at network nodes
–
–
–
Network is made of end nodes, intermediate nodes, and links
All traffic ultimately originated by end-nodes
However, for hierarchical networks, aggregation may occur

In some network paradigms, E2E traffic is recognizable
at all “places” in network
 In others, components within aggregated traffic not
recognizable inside network
Copyright Rudra Dutta, NCSU, Fall, 2011
Traffic Characterization


Traffic - “Demand” for networking services: b/w and
switching
Magnitude (bandwidth)
–

Lifetime
–

How long it is resident in the network
Arrival and departure patterns
–
–
–
–

Could vary with time, if “reasonably long” life
Call (like telephony) arrival and departure
Increment and decrement
Periodic (scheduled)
Static (long-term)
Requirement of performance
–
Hard or statistical
Copyright Rudra Dutta, NCSU, Fall, 2011
Network Design



Various aspects of the network must be
determined/chosen/configured
Network resources - nodes and links
Nodes
–
Circuit (physical connection) interface
– Buffers, scheduling, routing/forwarding, protocol

Links
–

Circuit enablement, bandwidth (bitrate capacity), protocol
Goals are in terms of network performance (experienced by traffic)
–
Basic goal: Connectivity
– Basic design methodology: Routing
– Others: b/w (if possible), buffer, resource management e.g. link
scheduling
– Topology, transmission power, battery allocation, …
Copyright Rudra Dutta, NCSU, Fall, 2011
Design/Management Cycle
Reactive Protocol Design
Algorithm Design
Near Real-Time
Resource Design
Capacity Mgmt, Netw Engg.
Network Planning
Copyright Rudra Dutta, NCSU, Fall, 2011
Network Performance

Ultimately, measured in quantities the end-user
cares about
–

Delay, throughput
–

Assuming we have connectivity, now what?
Other metrics derived from these
More sophisticated metrics
–
–
–
Predictability of above metrics
Predictability of connectivity: Reliability / Survivability
Predictability of delay or throughput

–
Guarantees - Quality of Service contracts
Other emergent characteristics: e.g. Security
Copyright Rudra Dutta, NCSU, Fall, 2011
Designing in Traffic Networks

Controversial proposition:
–
–

“If delay is not important, capacity is not important”
“If delay is important, capacity must be large OR aggregation
must be slotted OR both”
Consider the position of router R below
1
2
R
3
4
Copyright Rudra Dutta, NCSU, Fall, 2011
Q
Statistical TDM Performance


Bursty traffic, statistical TDM
Usual M/M/1 assumptions
–


In reality, traffic process is heavier-tailed
D( ,  ) = 1 / ( -  )
Delay is lower on average: “Statistical Multiplexing Gain”
–
But unpredictable for individual packet - prediction is statistical
1
2
R
3
4
Copyright Rudra Dutta, NCSU, Fall, 2011
Q
M/M/1 Queue
λ
0
λ
1
λ
2
μ
μ
λ
3
μ

p1 = p0 
4
μ
λ
5
μ
λ
6
μ
Average Delay (ms)
p2 + p4 = p3 ( + )
Link utilization  /
Copyright Rudra Dutta, NCSU, Fall, 2011
λ
μ
Network of Routers
Copyright Rudra Dutta, NCSU, Fall, 2011
Congestion


Connectivity-only routing (traditional shortest path)
ignores all traffic metrics
But traffic exists
–
Consider flows 1 4, 1 6, 24, 26
6
1
4
1
4
4
3
1
2
Copyright Rudra Dutta, NCSU, Fall, 2011
6
3
5
10
5
Network of Routers
Copyright Rudra Dutta, NCSU, Fall, 2011
Reactive (Short-time) Solution

Use routing protocols to “tweak” traffic
–
–
–
Away from congested links
Towards underutilized resources
Change link weights dynamically



Operator
Meta-protocol
Use transport protocols to slow down injection
of traffic (later)
–
–
Guessing at network capacity
Best used in conjunction with routing or other “innetwork” mechanisms as above
Copyright Rudra Dutta, NCSU, Fall, 2011
Design/Management Cycle
Reactive Protocol Design
Algorithm Design
Near Real-Time
Resource Design
Capacity Mgmt, Netw Engg.
Network Planning
Copyright Rudra Dutta, NCSU, Fall, 2011
Flow Routing and Global Routing

Most general view of routing
–

Any part of any flow can be routed along some path from source
to destination
Requires the ability to “mark” every part that has to be
routed in a distinct manner
–
Using labels, or timeslots
6
1
4
1
4
4
3
1
2
Copyright Rudra Dutta, NCSU, Fall, 2011
6
3
5
10
5
Connection Oriented Forwarding





A’s FIB
C’s FIB

E’s FIB


6
Copyright Rudra Dutta, NCSU, Fall, 2011
6
3
3
11

H1 sends request to A
A assigns label “1”, forwards
request to C
C assigns label “6”, forwards
request to E
E assigns label “3”, forwards
request to F
F accepts request, replies to
E with label “11”
E notes label, replies to C
with assigned label
C notes label, replies to A
with assigned label
A notes label, replies to H1
with assigned label
H1 sends packets with label
“1” to A on “virtual circuit”
Labeled Flows / Virtual Circuits

(Enables faster switching time)
 Enables flow routing
–
Therefore traffic engineering

Can dynamically route flows, to avoid congestion, say
 Or enforce policies
 Recognizing E2E traffic “inside” network
 Can create subflows
–
Issue of scalability

Possibly too many flows at core of network
 Aggregate flows – flow of flows

Enables QoS realization
–

Throttle each flow to its “permitted” bitrate
Enables “separation of mechanism and policy”
Copyright Rudra Dutta, NCSU, Fall, 2011
OpenFlow
OpenFlow is an API – off a Stanford project
 Control how packets are forwarded
 Implemented on hardware switch
Controller
Software Layer
OpenFlow Firmware
OpenFlow
PC
Flow Table
OF
MAC MAC
IP
IP
TCP
TCP
Switch
Action

Hardware Layer
src
*
port 1
dst
*
Src
*
port 2
Dst
5.6.7.8
Protocol
sport dport
*
*
port 3
port 1
port 4
P
K
T
5.6.7.8
Copyright Rudra Dutta, NCSU, Fall, 2011
1.2.3.4
following
1st packet
packets
routing
routing
IP dst: 5.6.7.8
Design/Management Cycle
Reactive Protocol Design
Algorithm Design
Near Real-Time
Resource Design
Capacity Mgmt, Netw Engg.
Network Planning
Copyright Rudra Dutta, NCSU, Fall, 2011
Static Traffic Performance

Given “matrix” of traffic demand components
–
–
–
Static, “always-on”
Usually aggregate
Measured or estimated

Delay - fairly constant for each demand, small
 Blocking - none; loss - none
–

Except in unusual circumstances
Performance is measured globally
–
–
–
Various objectives
Delay or throughput (global, across all components)
Revenue, fairness, protection, …
Copyright Rudra Dutta, NCSU, Fall, 2011
Transport, Demand, Capacity

Traffic Networks and Transport Networks
 Traffic networks: where stochastic demand
picture is operative
–

Transport networks: where traffic demands of
static magnitude are seen to be operative
–
–
–

Short term switching/routing
(Semi-) Permanent
QoS considerations paramount
Demands seen to be injected at transport network
nodes, lower level networks not visible
Links must have capacity to carry traffic
–
But routing can be designed on basis of traffic
Copyright Rudra Dutta, NCSU, Fall, 2011
Mathematical Programming Problems

A steel company must decide how to allocate production time on a rolling
mill. The mill takes unfinished slabs of steel as input and can produce
either of two products: bands and coils. Bands roll off the mill at 200
Tons/hr, generate $25/Ton profit, and at most 6000 Tons per week can be
produced. The same figures for coils are 140 Tons/hr, $30/Ton profit, 4000
Tons/wk. If 40 hours of production time are available, what should be
produced to maximize profit?

Verbal model

–
XB number of tons of bands produced.
– XC number of tons of coils produced.
–
Put the objective and constraints
into words
– For constraints, use the form
{a verbal description of the LHS}
{a relationship} {an RHS constant}
Maximize: total profit
Subject to: total number of production hours  40
tons of bands produced  6,000
tons of coils produced  4,000
Define the Decision Variables

Construct the Symbolic Model
Maximize:
Subject to:
25 X B  30 X C
1 200X B  1 140X C  40
0  X B  6000
0  X C  4000
Example adapted from “AMPL”, by Kernighan et al, 1993
Copyright Rudra Dutta, NCSU, Fall, 2011
Solving LP Problems

Graphical Solution Method
Coils
Coils
Constraints
6000
6000
Hours
Profit
220K
192K
4000
4000
Optimal solution
2000
Feasible region
2000
Bands
0
0
2000
Copyright Rudra Dutta, NCSU, Fall, 2011
4000
6000
8000
120K
Bands
0
0
2000
4000
6000
8000
Solving LP Problems

4 Possible Outcomes
Unique Optimal Solution
No Feasible Solution
Copyright Rudra Dutta, NCSU, Fall, 2011
Alternate Optimal Solutions
Unbounded Optimal Solution
Solving LP Problems

Simplex method
–
Efficient algorithm to solve LP problems by performing matrix
operations on the LP Tableau
– Developed by George Dantzig (1947)
– Can be used to solve small LP problems by hand

AMPL and CPLEX
–
AMPL: modeling language (and software) for designing large and
complex LP/IP problems (now use OPL)
– CPLEX: software package (“solver”) to solve large and complex
LP/IP problems

Sub-Optimal Algorithms (Heuristics)
–
Simulated annealing
– Genetic algorithms
– Tabu search
– Many others, often very specific to the type of problem
Copyright Rudra Dutta, NCSU, Fall, 2011
Integer Programming

Convert Example to Integer Program
–
Assume that orders for bands and coils are placed (and filled) in
1,000s of pounds only.
– Although feasible region is greatly reduced, problem becomes much
more difficult.

New Symbolic Model
–
Let the new decision variables be the number of 1000 pound “units”
or orders of bands and coils.
Maximize:
25000 X B  30000 X C
Subject to:
1000 200X B  1000 140X C  40
0  X B  6, integer
0  X C  4, integer
Copyright Rudra Dutta, NCSU, Fall, 2011
Integer Programming

Graphical Solution Method
Coils
6
$185K
Optimal integer solution ($185K)
4
2
Feasible integer solutions
Bands
0
0
Copyright Rudra Dutta, NCSU, Fall, 2011
2
4
6
8
Multi-Commodity Flow Formulation

Parameters
n : number of nodes
i
– A : set of all links (i, j)
– uij : bitrate of link
– cij : cost per bit on link
– bkl : traffic demand from node k to node l
–

j
Variables
–

l
k
xklij : traffic from k to l using link from i to j
Goal: minimize total cost
Source: Bertsimas and Tsitsilkis
Copyright Rudra Dutta, NCSU, Fall, 2011
Multi-Commodity Flow Formulation
i
Copyright Rudra Dutta, NCSU, Fall, 2011
Blocking in Telephony

Delay - very small and constant, operative
quantity is blocking ratio
 Average call rate 
 Average holding time 
 Offered traffic load or intensity a =  
ac / c!
 B(a,c) = ------------------c
k=0 ak / k!
Copyright Rudra Dutta, NCSU, Fall, 2011
X
Q
Telephone Network
Copyright Rudra Dutta, NCSU, Fall, 2011
Summation

In low level networks, traffic is bursty, unpredictable, and in general
low
–
–
–

L3-switched/routed traffic can be thought of as static at a high level
of network
–
–
–
–

A traffic network
Impractical to design for peak traffic, other notions not very meaningful
Design for connectivity, with roughly correct capacities
A transport view of network is appropriate, using slotted TDM
This approach is indispensable when strong guarantees must be made
w.r.t. delay, variability of delay, and bandwidth
Capacity of links becomes important in meeting such guarantees
Capacity, routing, and other variables can be thought of as “control
knobs” in the ensuing design problem
For circuits, can reflect physical resource occupations to obtain
quantitative idea
–
May also be useful for “logical” circuits at L3 (or not)
Copyright Rudra Dutta, NCSU, Fall, 2011