QoS

• Service Level Agreement

• => Performance guarantee

  • specifies bound on metrics

  • which needs to be guaranteed for an application

  • to work correctly

• On different layers

  • Packet

  • Flow

  • Applicatoin

  • User Level

• ENd-to-end latency and jitter

• packet loss

• throuthput

• transfer completion time

• time to complete transaction (e.g. SQL, download, backup,…)

• Video or Audio quality

• Quality-of-Experience

• modeling

  • understand which partsof network have impact on SLA

• classification

  • identify which packet needs which service

• scheduling

  • give preferential service to packets

• monitoring

  • check that SLAs are met

  • using passive or active measurements

• ===== Ingress ======

• ingress PHY

• -> Packet classification

• -> Packet marking Shaping/Dropping

• ==============

• -> Packet Processing (MAC learning, forwarding table lookup,…)

• === Egress ========

• packet classification

  • -> Queue 1

  • -> Queue 2

  • -> …

  • -> Queue n

• -> Scheduler (picking from queues)

• -> Egress phys

• live testing in worst-case conditions

• emulations and simulations

• formal verificatoin using analytical models

• input:

  • network topology and configuration

  • flow descriptions

• output:

  • bound on metrics (e.g. end-to-end latencies, buffer sizes,…)

• when we give and calculate the bounds by formal methods

• and they are below the requirements

• propagation

  • depends on cable lengths and physical signal propagation

• Processing

  • depends on hardware

• Transmisison

  • depends on packet sizes

• queuing

  • depends on the behavior of the other flows and the scheduling

• propagation and transmission delay for each hop

• processing delay at each hop in-between

• queuing at recipient

• Maximal delay which is measured on a real network

• during its normal operation, or via simulations.

• Theoretical worst case delay which can actually occur

• in case the elements of the network behave within their limits

• but in a very specific pattern leading to this worst-case

• bound calculated by analytical model

• which is generally larger than actual worst case

• due to

  • approximations

  • simplifications

  • or shortcomings of the formal method

• 0 -> maximal observed delay

  • occur often, most of the delays are in this area

• maximal observed delay -> actual worst case

  • rare events, not many will actually falll into this

• actual worst case -> upper bound

  • (nearly) no fall into this category

  • over provisionning…

• maximal observed delay

• actual worst case

• upper bound

• hard real-time

• firm real-time

• soft real-time

• best-effort

• hard real-time

  • missing deadline is total system failure

• firm real-time

  • infrequent deadline misses are tolerable

  • late packets are discarded

• soft real-time

  • infrequent deadline misses are tolerable

  • late packets may be used

• best effort

  • no deadline requirements

• better accuracy and thightness often paid with higher complexity of the mathemtical tools and more CPU time

• theoretical framework

• developed for analyzing performance guarantees

  • latencies and buffer sizes

• in networks of queues and schedulers

• since early 1990s

  • still under active research

• -> mostly applied to communication networks

  • e.g. validation of embedded networks in airbus A380, A350)

• deterministic

  • no randomness involved

  • => performances are guaranteed whatever happens to the network

• stochastic

  • randomness involved

  • => performances are characterized in probabilistic terms

Dropping three matches

• expected case

  • all matches fall and lie down

• deterministic worst-case

  • all three matches stay ontop of eachother

  • -> no matter what happens, this will be lower bound (as no other outcome can be worse, regardeless of probability of them falling)

• probable worst-case

  • two lie down, one stays

  • -> probably the worst case, but bound by probability, not in all cases (as two can stay although unlikely)

• unidirectional set of packets going from sender to receiver

• used to describe packets and network protocols

• cumulative arrival function A

• A(t) := amount of data sent by flow in time-interval [0,t)

• non-decreasing

• strictly positive

• part of

• F =

  • {f:R^+ -> R^+ |

    • function from all positive real values to all positive real values

  • for all 0 <= t <= s:

  • f(t) <= f(s),

    • earlier values are always smaller or equal

  • f(0) = 0

• if its cumulative arrival function A satisfies:

• A(t+s) - A(t)

• <=

• α(s),

• For all (s,t) >= 0

=> what ever has arrived in timespan s (for each timepoint t)

is smaller than what has arrived at timepoint s in our arrival curve

=> there cannot be more sent in the arrival function than in the arrival curve… (regardeless of the observed time interval)

=> arrival curve is deterministic if it is upper bound for cumulative arrival function…

• example of deterministic arrival function

• -> defined by long-term averate rate r

• and burstiness parameter b

• γ_r,b (s) = r · s + b, ∀s ≥ 0

• as servers ß

• A -> (ß) -> A*

=> cumulative arrival functoin goes in

-> circle around server ß (graphical representation…)

-> cumulative arrival function A* goes out

• server S offers strict service curve ß

• if during any period of duratoin ∆

• where there is data waiting to be served by S

• the output of S (A*) is at least ß(∆)

=> ß gives lower bound of what is served for a given time interval…(if there is enough data available to be served…)

• upper bound for transmissions / time

• A* (t + ∆) − A* (t) ≥ β(∆)

  • output cumulative arrival from timeinterval ∆ is larger than ß(∆)

• A* (t) ≥ A(s) + β(t − s)

  • cumulative output at time t

  • is larger equal than

  • cumulative input at earlier point s

  • plus upper bound for processes stuff …?

• example of deterministic service curve

• -> defined by rate R and processing delay T

• denoted β_R,T

• β_R,T(t)

• = R[t − T]^+ ,

• where [x]^+ = max(0, x)

• => higher value than 0

• -> gives the processing rate right shifted by the processing delay

• -> begins at point T and increases with processing rate

• -> y-axis is cumulative arrival of output (A*)

• horizontal space is the delay

  • -> same height == same packet from input/output

  • => time it takes for packet to traverse queue

  • D(t) -> infimum for all s > 0

  • of all values where {A(t) <= A*(t+s)}

  • -> basically the smallest horizontal difference for all s >0(menaing later) -> is straight forward horizontal distance… as all later will be larger distnace…

• vertical space: queue size

  • -> what is arrived but not yet processed at certain point in time…

    
    

• maximum time a given data has to wait before being processed by the server

• => graphical : maximum horizontal deviation between arrival and service curve

• maximum amount of data that will have to wait before being processed by the server

• -> graphical: max vertical deviation between arival and service curve

• A*(t) − A(t − s)

• <=

• sup_t>=0

• { inf s>=0

• {α(t) ≤ β(t + s)}

• }

=>

• congolution (f ⊗ g)(t)

• deconvolutoin (f (only one from left lower to right upper in circle) g)(t)

• inf _0<=s<=t (lower bound between s and t)

• {f(s) + g(t-s)}

(f  g)(t) := sup s≥0 {f(t + s) − g(s)}

A ∗ (t) ≥ (A ⊗ β)(t)

=> convolute input accumul. fct with ß (service curve)

• α* (t) = (α  β)(t)

• -> output curve -> deconvolve input curve with service curve…

infimum for s:

deconvolve alpha and beta over -s

-> smaller equals 0

• alpha deconvolve beta (0)

(γr,b  βR,T )(t) = γr,b+rT (t)

• two concatenated servers (ß) can be conbined into one by convoluting them…

• => (βR1 ,T1 ⊗ βR2 ,T2 )(t) = βmin(R1 ,R2 ),T1 +T2 (t)

=> take minimum of first value and sum of second => basically add delay and keep lowest steigung, as delay accumulative and steigung upper bound…

=> concatenation property with multiple servers

• multiple flows traversing a server

• => performance of one flow depends on influence of other flow

• -> assumption worst case (if we know nothing)

  
  

• blind multiplexing

• arbitrary multiplexing

• -> assume worst case

• make use of service that is left after flow 2 has been serviced…

• => called resudial or left-over service curve

• ß^(l.o.) = [ß - α2]^+

• = ß_(R-r),)(b+RT)/(R-r)

• queues are polled in priority order until non-empty queue is found

• queue can be served only if all higher priority queues are empty

• majority of ethernet switches on the market

• easy implementation

• zero configuration

• simple formal verification

• starvation problem

• highest priority:

  • ß (l.o.highest) = ß

  • ß (l.o.next highest) = [ß - alpha_highest]^+

  • …

  • ß (l.o.lowest) =

    • [ß - (sum of alpha of all highers)] ^+

• compute bounds in network by separating individual bounds and then aggregating them

1. Compute the left-over service curve for each server traversed by the flow

2. Concatenate the left-over service curves

3. Compute the bounds

• not fluid serving of server

• => server identifies all packets from individual flows and groups them

• -> if all packets from a flow have arrived, serve them simultaneously

• => step function…

• what happens if a computer sends more than expected?

• => enforcement!!!

  • switches and routers need to check that each flow conform to its arrival curve…

• mechanism: rate shaping/limiting and flow filtering

• protocols: IntServ and RSVP, DiffServ, MPLS-TE

• Commercial devices usually have limitations or unwanted functionalities

• Custom-designed and/or industry-specific devices and protocols

New protocols currently standardized:

• IEEE Time Sensitive Networking (TSN)

• OpenFlow meters

• Study the cummulative arrival of traffic

• Characterize the behavior of servers as function of the cummulative arrival,

• Define a (simple) bounding function of the traffic and server behavior,

• Work with the bounding functions – not the traffic itself – to compute bounds.