Transcript Traffic Engineering

Traffic Engineering
Getting the flavour from a colleague who is finally
getting the hang of it.
or
Computer Networks is not all buzz words and
abbreviations:
(ANSI, ISO, ETSI, OSI, PhL, NRZ, TwP, FWA, IEEE802.11,
IEEE802.15, GFSK, FHSS, DSSS, WDM, QAM, BER, FER,
Mbps, MAC, CSMA/CD, CSMA/CA, IEEE802.3/4/5, HS,
IEEE1394, TTP, JDN, CAN, ATM, QoS, NWL, OBM, IP, IPSec,
IPv6, PAN, WLAN, CPK, MANET, OLSR, TCP, LTS, RED,
SNMP, TMN, VoIP, ASPI, CBR, VBR, ABR, MPEG4 ...)
Traffic Engineering
(purpose)
From outstanders Computer Networks may seem like a jungle of more or
less related bw’s and abb.’s, however there is a huge body of theory behind
the hot air.
In our dept. the word is often around that memorizing bw’s and passing
them on, is what this field is all about.
Therefore it is the intend with this talk to present the non computer network
part of the dept. to some of the theory behind the words.
Since the speaker works within the field of traffic engineering this will be
the topic of the talk, and different approaches to networks analysis will be
given, which may be appealing even to attendees from the control
community.
The traffic engineering problem compound is introduced and focus is turned
to capacity analysis, where probabilistic and deterministic approaches will
be illustrated. Flavour is added from the speakers own work and ideas for
future work are sketched.
The general setup.
Network
Technology
Characterization
• End user behaviour
• End user requirements
• End user relations
• Underlying network technology
Network Technology
• ATM transmission backbone at TDC or Sonofon
• Multi segment realtime heterogenous control
network - (ARCnet,Ethernet,Pnet,ProfiBUS,CANbus e.t.c.)
• Wireless LAN (Bluetooth, IEEE 802.11b e.t.c.)
• Wireless Ad Hoc Network (Bluetooth
HIPERLAN e.t.c.)
End to End Relations
Sender/
Reciever
P1
P1
P2
P3
Traffic descr.
Requirements
(P2,P1)
Traffic descr.
Requirements
(P3,P1)
P2
P3
Traffic descr.
Requirements
(P1,P2)
Traffic descr.
Requirements
(P1,P3)
Traffic descr.
Requirements
(P2,P3)
Traffic descr.
Requirements
(P3,P1)
End User Requirements
QoS
• Bandwidth (long term)
• Delay (End to end)
• Delay jitter (End to end)
• Input filter characteristics.
• Reliability
• Availability
• Setup delay
Input Filter Characteristics
Let A(n) denote the traffic (packets) generated
from end user within 0..n.
If A(n)-A(m) <= f(n-m) for n>m the traffic flow
A is said to comply to an envelope f
(A is f-bounded)
f is a non-decreasing, positive, subadditive
(f(n+m) <= f(m)+f(n) ) and causal (f(n<0)=0)
function f: Z -> Z+
Input Filter Characteristics
•A traffic filter recieves a traffic flow A and
forwards a flow B in FCFS order so that:
B(n) <= A(n) for all n
(no packets are dropped only queued
temporarily)
• A maximal f-filter is a traffic filter where B is
the maximum f-bounded flow complying to the
above: (B*(n) <= B(n) for all n, if B* is fbounded)
Input Filter Characteristics
• Convolution under the (min,+) algebra (normally
(+,*):
f*g (n) = min_(0<=s <n) f(s)+g(n-s)
• A maximal f-filter for A can be found from:
B(n)=min{A(n),B*f(n)}
Input Filter Characteristics
A
B
min
B*f
f
Input Filter Characteristics
• Leaky buckets: f(n)=c*n for n>0
• Token buckets: f(n)=K + a*n for n>=0
• Combined: f(n)=min{c*n , K+a*n} for n >=0
(peak rate c, average rate a)
• D-bind bounds - multiple afine bounds.
Input Filter Characteristics
f(n)
a
K
Token bucket
filter
n
m
m+1
a tokens granted every time until full
K
A
qA
Token bucket
B
qB
Input Filter Characteristics
Network access is often sold by input filter
characteristics: you are allowed a peak rate c and
an average rate a
These characteristics only give you bandwidth
guarantees a, nothing about your real service
qualities like delay and jitter.
Delay qualities are not determined by input filter
alone.
Input Filter Characteristics
To ensure delay qualities you have to inspect queueing
and transmission delays all through the network
(end to end).
In the token bucket case queueing and waiting
happens in both qA and qB.
How do we describe queue lengths and waiting times;
worst case or expected values - surely depends on
application.
End User QoS Requirements
(applications)
Real time control: bandwidth and worst case round trip delay
guarantees required.
Real time alarm notifications: (bandwidth) and worst case
end to end delay required.
One way real time audio: bandwidth and expected delay
jitter guarantees required.
IP telephony: bandwidth and expected delay guarantees.
Video conferencing: bandwidth and expected round trip delay
guarantees.
WEB traffic: bandwidth
End User Behaviour
(applications)
Real time control: periodic/fixed size packets - leaky bucket
complyant.
Real time alarm notification: Aperiodic(sporadic) - token
bucket complyant.
One way real time audio: Aperiodic bursty (talk spurts)
IP telephony: Aperiodic bursty (talk spurts).
Video conferencing: MPEG4/VBR: Aperiodic bursty (scene
changes)
WEB traffic: Aperiodic (very long) bursts (self similar).
End User Behaviour
(probabilistic)
Poisson modelling: simple, well established, far from
reality.
Markov modelling: complex, less established, works
for voice and VBR.
Semi Markov modelling: very complex, young
theory, works for WEB traffic and VBR.
Poisson modelling
(queueing networks)
l2
L
u1 L
u3
u2
p
(1-p)L
L
l1
Flow equations solved:
L=l1+l2+pL => L=(l1+l2)/(1-p)
r1=L/u1, r2=L/u2, r3=pL/u3, qi=ri/(1-ri), I=1,2,3
Queue lengths are independent random variables.
Markovian Arrival Processes
M/G/1 (MMPP/G/1) - queue
l1
l2
l3
Matrix Analytical (geometrical, G=M)
methods exist for single queue systems.
Semi Markov Models
Assymptotic results –
tail probabilities
Queue length may grow
far beyond the Poisson
estimate
Sojourn times not exp
distr. – sub exp./Pareto
Deterministic Models
• Arrival processes are f – bounded (f-upper constrained)
• If not - they are filtered.
• A g – server is a lossless packet forwarding device.
• As response to an input A an output sequence B is
produced where:
• A*g(n) <= B(n) <= A(n)
(*: (min,+) convolution)
• Stability: A(n)-B(n) <= Q for all n
Deterministic Models
An N - TDM multiplexer (1 pck/slot) is an
(n-N)+ - server to each of its input streams.
1
2
g(n)=(n-N)+
3
N
N
n
Deterministic Models
A
B
g - server
Assume A is f – bounded then:
• q(n)=B(n)-A(n) <= max(f(s)-g(s))
• d=inf{d >=0 | B(n+d) >= A(n) n=0,1.,,}=
• inf{d >=0 | f(n) <= g(n+d) n=0,1,..}
• B is h – bounded for h(n)=sup s >=0 (f(n+s)-g(s))
Deterministic Models
(g-server calculus)
h(n)=f(n)+qmax-f(0)
f(n)
dmax = f(0)+N
qmax=f(N)
g(n)
N
If input is f-bounded
Output is h-bounded.
n
Deterministic Models
(g-server calculus)
A
B
g1
g2
g3
g4
B
A
g
• g = g1 * g2 * g3 * g4 (*: (min,+) convolution)
• Individial queue lengths and delays can be found
• Total backlog (summed queue lengths) and delay can be found !
• Also works for feed back systems - > implicitly given solutions.
Deterministic Models
(example)
• f(n)=2+n, input flow A is f-bounded
• h(n)=2n, g(n)=(2n-4)+, l(n)=h*g(n)=g(n)=(2n-4)+
A
h
B
g
C
• Qh <= f(0)=2,dh <= f(0)/2=1,
• B is f-f(0)+Qh = f bounded.
• Qg <= f(2)=4, dg <= (f(0)+2)/2=2, C is f-f(0)+Qg (n+4)
• Conservative: Ql <= Qh + Qg = 6, dl <= dh + dg =3
• Precise: Ql = Qg = 4, dl=dg=2
Arbitration/Scheduling
(principles/technologies)
• CSMA/CD: Ethernet, IEEE 802.11
• Priority based: CAN bus, token bus
• Pure token rotation: token ring, token bus.
• Combined: IEEE-1394 (Firewire), ATM
• Polling: Bluetooth
Arbitration/Scheduling
(analysis)
Priority systems: Critical
Instant theorem.
f1,..,fN ->
g1,..,gN
???
Polling/token based,
combined ???
Busy Period approach
q1(t)
Q1
q2(t)
Q2
Busy period
q3(t)
Q3
q4(t)
Q4
t0
time
qj(0)=0 ->
q1,3,4(t0)<=Q1,3,4 -> qj(t0)<=Qj, j = i ->
q2(t) <= Q2 for t >=t0 qi(t) <= Qi for t >=t0 qj(t) <=Qj
Input Filtering
• Voice and VBR traffic are f-bounded
• Alternatively traffic streams are f-filtered -> f-bounded
•Applying a Markovian arrival process (MAP) to a (T,K) token
bucket filter gives a stationary queue length distr. Fq.??
• Solving the associated MAP/D=T/1/L problem gives Fk where:
q=(k-K)+ -> Fq(0)=Fk(0)+ ..+Fk(K), Fq(n)=Fk(n-K) for n>0
• Waiting times can not be derived through the ”Little
result”since embedding points are not all departures.