Transcript Network Design Overview

Network Resource Design Background
ECE/CSC 777: Telecommunications Network Design
Fall, 2013, Rudra Dutta

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
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, 2013
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, 2013
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
Copyright Rudra Dutta, NCSU, Fall, 2013
Design Goals

Goals are in terms of network performance
(experienced by traffic)
–
–

Basic goal: Connectivity
Basic design methodology: Routing
Routing - pathfinding
–
–
Output of routing: Forwarding Information Bases
Input to forwarding engine

The one indispensable piece of information in
making a forwarding decision: destination
 Simplest routing approach: map from
destination to next-hop
Copyright Rudra Dutta, NCSU, Fall, 2013
Flows

Multiply defined term
 In this context, the traffic associated with a path or route
 Sometimes (esp. in Internet context) defined as sourceto-destination traffic
 Routing defines flows, but routing can be in terms of
flows
–
If only s-d is considered, routing can be by flow (s-d)

–
Instead of by destination only
But same s-d traffic can be split up and routed variously
Requires some “marker” for various split parts
 A possibility: slotted TDM approach, timeslots “mark” flows

Copyright Rudra Dutta, NCSU, Fall, 2013
Space of Routing Choices

Static vs. dynamic or adaptive
 For a node, next-hop determined by
–
–
–
–
Destination only
Source and destination
Particular flow of traffic
Other characteristics

May be bifurcated (split) or non-bifurcated
 Next-hop may be unique or multiple
–
Deterministically or randomly picked
Copyright Rudra Dutta, NCSU, Fall, 2013
Issue of Traffic Engineering


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, 2013
6
3
5
10
5
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, 2013
About Loss

Loss may occur on the link
–
–

Loss may occur at intermediate nodes
–
–

Usually very little in guided medium - ignore
Usually handled by L2 transmissions or ignored
Store-and-forward buffers are finite - may overflow
Other mechanism at intermediate node may discard
Does retransmission occur?
–
–
May not be required / desired
If desired,


May be at L2, on link
May be E2E, at L4, L7, or L8
Copyright Rudra Dutta, NCSU, Fall, 2013
About Delay

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”
(Capacity  ?)
Consider the position of router R below
1
2
R
3
4
Copyright Rudra Dutta, NCSU, Fall, 2013
Q
Statistical TDM Performance


Bursty traffic, statistical TDM
Usual M/M/1 assumptions
–

In reality, traffic process is heavier-tailed
Delay is lower on average: “Statistical Multiplexing
Gain”
–
But unpredictable for individual packet - prediction is statistical
2
R
3
Q
Average Delay (ms)
1
4
Link utilization l/m
Copyright Rudra Dutta, NCSU, Fall, 2013
Blocking in Telephony

Delay - very small and constant, operative
quantity is blocking ratio
 Average call rate
 Average holding time
 Produce: offered traffic load or intensity
X
c
Copyright Rudra Dutta, NCSU, Fall, 2013
Q
Scaling, Hierarchy, Aggregation

Because of scalability, hierarchy seems inevitable
–
Connectivity is always less than full (esp. in large networks)
– Nature of end-nodes and intermediate nodes vary
– All links are TDM (FDM modeled as separate links)

Hierarchy implies aggregation/disaggregation of traffic
4
2
1
3
Copyright Rudra Dutta, NCSU, Fall, 2013
Traffic Aggregation - Static Traffic


Consider lowest level networks
Assume each station injects traffic steadily
–

Due to aggregation, magnitude increases as traffic
climbs hierarchy
–


But constant nature of traffic remains
Aggregation/dis-aggregation process is straightforward
for intermediate nodes
–

Number of bits injected per time unit is constant for each source
Effectively same as slotted TDM
Therefore static traffic is stable - remains static at higher
levels of hierarchy
Magnitude and therefore capacity, of course, must
increase at higher levels
Copyright Rudra Dutta, NCSU, Fall, 2013
Bursty Traffic

Traffic is generated intermittently at each end node
–

Assume (peak) rates are known
Question of capacity and aggregation become
intertwined
–
One approach: pretend each end node is a steady source at its
peak rate, then provision as before

–
Aggregation will be easy
Another approach: provision for average

Do bursts arrive deterministically? If not, ...
 Sometimes link will be busy when traffic arrives to use it
 Must store-and-forward, or discard
–
Result: bursts are “smoothed” by (a) interleaving, (b) store-andforward

Question of slotting TDM comes in - work conservation
Copyright Rudra Dutta, NCSU, Fall, 2013
A View of Aggregation
1
2
burstiness
4
2
3
1
3
4
4
bitrate
Copyright Rudra Dutta, NCSU, Fall, 2013
Other Contributing Factors

“Elasticity” of traffic
–
–
–

Source-to-destination traffic flows in the Internet are
not static as generated
Congestion in network will slow down bursts
In response, flow duration will increase
“Filling up” of pipes
–
Provisioning levels are not perfect

–

At some levels, flows may be at capacity
At next level, contributes a static flow
Provider utility in revenue, not user traffic
–
–
Once a static block is paid for, it is carried
Even if all you are sending is endless zeros
Copyright Rudra Dutta, NCSU, Fall, 2013
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, 2013
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, 2013
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, 2013
6
3
5
10
5
Multi-layer Network Design

Generalized protocol
layering can create
complicated networks
–
–

Generally, demand is
specified in one layer and
capacity in another
–

Better thought of as multiple
layers
Each layer satisfies flow
constraints
Must assume some mapping
method - possibly constrained
Single large design problem,
or multiple coupled design
problems
Copyright Rudra Dutta, NCSU, Fall, 2013
Ckt-switched
voice
Private
Line
IP
Networks
CrossConnect
Digital
Transmission
Optics
Media
Management Cycle and Design
Reactive Protocol Design
Algorithm Design
Near Real-Time
Resource Design
Capacity Mgmt, Netw Engg.
Network Planning
Copyright Rudra Dutta, NCSU, Fall, 2013
Summation






L3-switched/routed traffic can be thought of as static at
a high level of network
At this level, 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
Continuity design echoes these stages, and
accompanies design
Copyright Rudra Dutta, NCSU, Fall, 2013