Quality of Service in Computer Networks

Components & Modules

• time-space multiplexer

Homogeneous Markov Processes

For irreducible aperiodic MC \[p_{j} = \sum_{i\in S} p_{i}P_{ij} \quad \forall j\in S\]

Global balance \[\sum_{i \in S / \{j\}}} p_{i}p_{j}\]

Non-stationary case

Probability density \(q\) are elegant solution to have simpler equations, independent of time-scale.

• assuming transition probabilities where we zoom on the time axis to where the transition is smooth
  • can be approximated to a linear function
  • $$p_ij(s)=q_ij⋅ s + o(s) \quad j≠ i$

Conditional and absolute transition probability: \[p_{ik}^{\star}(s)=p_{i}(t)\cdot p_{ik}(s)\]

Kolmogoroff Equation

Stationary case

\[p_{X}= \lim_{t\to \infty}p_{X}(t)\] \[lim_t→∞\]

Statistical equilibrium for the states: \[q_{k}p_{k}=\sum_{i\neq k} q_{ik}\cdot p_{i}\]

Generalised state equations:

\begin{align*} p_S = \sum_{k\in S} p_k \\
q_k = \sum_{i\neq k} q_{ki} \end{align*}

You can generalize a set of state to abstract into a single bigger markov state that includes them.

Communication Traffic as Random Process

In formulas \(t\) and \(\Delta t\) are interchangeable.

State process

Call process

\begin{align*} q_{A}= \lambda\\
F_{A}(t)=P(T_{A} \leq t)\\
E(T_{A}) = \frac{1}{\lambda}\\
c = \lambda \\
F_{A}(t) = P(T_{A} \le t) = 1 - e^{-\lambda t} \\
F_{A}^{C}(t) = P(T_{A} > t) = e^{-\lambda t} \\
\end{align*}

End process

\begin{align*} F_H(t) &= P(T_H \leq t) = - e^{\frac{t}{h}}\\
\text{end rate: } \epsilon &= \frac{1}{h}\\
p_{E1}&=1-e^{-\frac{\Delta t}{h}}+o(\Delta t)\\
\text{probability density: } q_{E,x}&=\lim_{\Delta t \to 0}\frac{P_{E,x}(\Delta t)}{\Delta t} \text{ so } q_{E,x}=\frac{x}{h} \end{align*}

One-dimensional birth-death processes

\beg ∑ P_i = 1

\end To not have \(n\) members to the equations we use a generalised state \(S_x\) and consider only the interactions with the interactions with the neighbours crossing its limits. Local balance: \[\lambda_x P_x = \mu_{x+1}P_{x+1}\] \[P_x = P_0 \prod_{i=1}^{x}\frac{\lambda_{i-1}}{\mu_i}\] where the product is defined as \[L_x\], \[L_0=1\]

\[\sum_x P_x = P_0 \cdot \sum_x L_x = 1 \iff P_0 = \frac{1}{\sum_{x}L_x}\] \[P_x = \frac{L_{x}}{\sum_i L_i}\]

Process for unlimited number of traffic sources

Definition of announcement: \[\lambda \cdot h =: A\] Erlang-equation: \[P_x=\frac{}{}]

Definition of loss probability:¹ \[B := P_n = \frac{\frac{A^{n}}{n!}}{\sum_{i=0}^{n}\frac{A^{i}}{i!}}\] Expectation value is calculated over all probabilities. \[E\{n}\}\] Traffic intensity \[Y =\] Residual traffic \[R= Y - A = A\cdot B\]

Queues with Priorities

Priorities for tasks and each one has a service rate in the CPU. The network is basically a M/G/1. Can have preemptive or non-preemptive priorities.

By applying the non-preemptive model in the case of 2 priority classes the result is that to save time compared to a basic M/G/1: \[x_2 > x_1\] Meaning the longest jobs need to be placed in the lowest priority class of the network.

Queueing Networks

A network of queues can be computed by computing independently the single queues based on some assumptions. Kleinrock’s Independence Assumption, 4 conditions

1. packet streams at the inputs of the network are Poisson distributed
2. packet length exponentially distributed
3. no dependency between arrival time of a packet in the next queue and its service times
4. the nodes of the network are sufficiently close to each other

In general this assumption gives a good first approximation of the network, it is well known that the OWTT is overestimated using this independence assumption.

Jackson network helps find exact solutions under certain conditions. This is the case assuming the first 3 conditions of the Kleinrock’s assumption. These networks are called product networks² or Tandem Queues. In these networks packets can go through the network (and spend each queue delay time as well) multiple times. So in addition to the delay for the independent queues one needs to compute an average of passes for a packet stream through the network.

\begin{align*} T_{in,1} &= 3T_1 + 2T_2\\
T_{in,2} &= \frac{3}{2}T_1 + 2T_2 \end{align*}

Quality of Service in Computer Networks

Show that QoS and anonimity and privacy are in constant tension. The contract signing needs to be fair (fair exchange). For a pair of agents, both must succeed or both must fail. There are limitations to network security:

• impossibility of consensus
• asynchronous setting

Solution can be a Trusted Third Party (TTP)

• it is a bottleneck
• should be fair
• should be timely
• receives signatures and distributes the contracts

TTP can

• issue a replacement contract
• issue an abort token
• acts only when requested

Anonymity

• Chaum’s MIX, anonymous email³
  • bad for spam of course
  • the MIX stands between senders and receivers and masks direct communications, to an attacker the MIX will look like flows of incoming and outgoing messages
    • it needs traffic padding and buffering to prevent timing correlation attacks
  • this protocol allows secrecy without authentication where \(A\) knows it is talking with \(B\) but \(B\) does not know, it simply responds to the MIX using fresh public keys generated by \(A\).
  • the adversary needs to control all cascade mixes, one good mix is enough for anonymity
• Dining cryptographers⁴
  • information-theoretic anonymity
  • needs incredible amount of randomness, unpractical
  • we need \(n\) bits to in the end broadcast a single bit