Principles of Communications, Digital Communication II Past Paper

Readings,

Routing

Packet size

TCP

DV vs LS

General

Cell switching (ATM) vs. packet switching (IP)

Inter-domain

Intra-domain

Fibbing

Multi-protocol label switching

Segment

Multicast

Mobile and telephone

Mobile

Telephone circuits: dynamic alternative routing

Flow / congestion control

Scheduling

The scheduler allocates the delay, bandwidth and loss rate to the packets in the output queues.

work-conserving: whenever there is a packet to send, the scheduler will send it.

∑i=1nρiqi=C,\sum_{i=1}^n \rho_i q_i = C,

non-work-conserving: the scheduler may idle even if there are packets to send.

Past papers

Fairness

max-min fairness

Given the list of demands, each flow is assigned mim_i resource, which neither exceeds its demand xix_i, nor exceeds an equal share of the remaining capacity (for unsatisfied flows), in the order of increasing flow demand,

m0=0,mi=min⁡(xi,C−∑j=0i−1mjn−(i−1)).m_0=0, m_{i} = \min(x_i, \frac{C - \sum_{j=0}^{i-1} m_j}{n-(i-1)}).

It allocates the small demanding flows what they want, and then evenly distributes the remaining capacity among the larger demanding flows. The process is repeated until all flows are satisfied.

Past papers

vs. proportional fairness

fairness in multipath routing

4G

Protection/Isolation

misbehavior by one connection should not affect the performance received by other connections (or flows), where misbehavior includes sending packets at a rate faster than its fair share.

relationship: fair →\rightarrow protection, i.e., a fair scheduler automatically provides protection. However, the converse need not be true.

Scheduling algorithms

algo. work-conserving? max-min fair? protection? w/o mean pkg size?
FIFO/FCFS ✓ ✘ ✘ ✓
Priority ✓ ✘ ✘ starve ✓
GPS ✓ ✓ ✓ ✓
WRR ✓ long time scale ✓ long time scale ✓ ✘
Deficit RR ✓ medium and long time scales ✓ ✓
WFQ ✓ ✓ ✓ ✓

Past papers

Queue management

drop from T/H, smart/random drop, flush, Active Queue Management (e.g. Random Early Detection), ECN.

fair for ? pros cons global syn.?
flush ✘ aggressive clear severely penalize all ✓
tail-drop steady & small easy to implement drop burst arrival ✓
head-drop burst, real-time prevent hogging drop long-latency ✘
smart-drop ✓ per-flow, adaptive complex classifier ✘
random long time ✓ treat flows evenly non-deterministic ✘
RED ✓ adaptive on length complex to tune ✘

Past papers

Data centers

QJump, a switch priority queueing, combined with end systems traffic regulation, by exploiting its regular topology & traffic matrix (src-dst) & source behaviour.

Optimization

In general, we have two coupled problems, i.e.,

min⁡R∑l∈LD(ul), where ul=∑iRlixicl.(routing)\min_{R} \quad \sum_{l \in L} D(u_l), \quad \text{ where } u_l = \frac{\sum_{i} R_{li} x_i }{c_l}. \tag{routing}

max⁡xs∑s∈SUs(xs), s.t. ∑s∈lxs≤Cl,∀l∈L.(system)\max_{x_s} \quad \sum_{s \in S} U_s(x_s), \quad \text{ s.t. } \sum_{s \in l} x_s \leq C_l, \forall l \in L. \tag{system}

Routing

     / p_1 with rate x_1
    /
- rw -->  p_2 with rate x_2
    \
     \ p_3 with rate x_3

Given (routing) on link l=ijl=ij, it's equivalent to the following,

∑all links lDl(∑all p with lxp), s.t.∑p∈Pwxp=rw,∀w∈W;xp≥0,\sum_{\text{all links } l} D_l( \sum_{\text{all } p \text{ with } l } x_p ), \quad \text{ s.t.} \sum_{p \in P_w} x_p = r_w, \forall w \in W; x_p \geq 0,

where DlD_l is the congestion function of link ll, which is a non-decreasing function of the total flow FlF_l through it,

Dl(Fl)=FlCl−Fl,D_l( F_l ) = \frac{F_l}{C_l - F_l},

For each sd pair ww and each kwk_w paths, evaluate marginal utilities ∂D(x)∂pi\frac{\partial{D(x)}}{{\partial{p_i}}} equal, where i∈[1,...,kw]i \in [1, ..., k_w].

Congestion control

Proportional fairness

For adaptive-rate flows, the vector of rates XsX_s is proportional fair if for any other vector of rates Xs′X'_s,

∑s∈Sxs′−xsxs≤0.\sum_{s \in S} \frac{x'_s - x_s}{x_s} \leq 0.

the sum of relative improvements possible for each individual flow is non-positive.

(A) For the network problem, we are trying to maximize the revenue, which is in diminishing returns w.r.t the rate xsx_s,

max⁡xs≥0ωslog⁡xs, s.t. ∑s∈lxs≤Cl,(network)\max_{x_s \geq 0} \quad \omega_s \log x_s, \quad \text{ s.t. }\sum_{s \in l} x_s \leq C_l, \tag{network}

is the proportional fairness of rates xsx_s per unit charge, via aggregated rate xrx_r by replacing single user with wrw_r users.

(B) For the user problem, we are trying to maximize the user's utility, while decreasing the cost involved, for each source ss,

max⁡Us(xs=psωs)−ωs, s.t. ωs≥0.(user)\max \quad U_s(x_s = \frac{p_s}{\omega_s}) - \omega_s, \quad \text{ s.t. } \omega_s \geq 0. \tag{user}

Together with (A) and (B), we are solving the intractable system problem, since the source utility functions are not known by the network in advance,

max⁡∑s∈SUs(xs), s.t. ∑s∈lxs≤Cl,∀l∈L.(system)\max \quad \sum_{s \in S} U_s(x_s), \quad \text{ s.t. } \sum_{s \in l} x_s \leq C_l, \forall l \in L. \tag{system}

Under the decomposition of (system) problem into (network) and (user), we derive xr=ωr∑j∈rpjx_r = \frac{\omega_r}{\sum_{j\in r} p_j} from the (network) Lagrangian.

The dual problem is reduced to differential equation, the change in bandwidth allocation at source ss includes linear increase of ωs\omega_s and the multiplicative decrease based on the shadow price,

ddtxs(t)=k[ωs−xs(t)∑l∈L(s)pl(t)],\frac{d}{dt} x_s(t) = k [\omega_s - x_s(t) \sum_{l \in L(s)} p_l(t)],

where shadow prices (congestion signals) pl(t)=gl[∑sxs(t)]p_l(t) = g_l [\sum_{s} x_s(t)] is accumulated along the path L(s)L(s) from the source ss to the destination,

Past papers

vs. max-min

Traffic management

QoS + Connectivity.

Elastic vs inelastic

Traffic classes and synchrony (see Flow control section)

Utility function, Traffic model (measure or math), time scale, renegotiation, admission control, capacity planning and macroscopic QoS.

Peak load pricing

Signalling

Related: multicast (RSVP : Resource reSerVation Protocol)

General

IntServ vs. DiffServ

System design

randomness

Layering