Generalized foreground-background in Scheduling
Generalized foreground-background
Least Attained Services
(LAS)
Generalized foreground-background
Working of Foreground-Background :
th
th
Theorems under Generalized Foreground-Background (FB) :
Notations :
- p : refers to policy
- X : Service requirement with mean E[X] and variance var(X)
- SRPT : Shortest Remaining Processing Time
- LAS : Another representation for FB
- E[Tl] : E[TLAS]
- E[Ts] : E[TSPRT]
Theorem-1:
Theorem-2:
p
Xp
Theorem-3:
Characteristics of Generalized Foreground – Background :
- LAS gives buffer space priority to first TCP packets of each flow, which means that these packets should not experience any loss.
- A new TCP flow starts in what is known as “slow start”, where its congestion window is initialized to very small value and then doubled after every round of transmission. Since, under FB, first packets of flow will experience no or negligible queuing delay, duration of round will be shorter under FB and congestion window will increase faster.
- The behavior of FB router is similar to that of FB queue, as long as packet to be serviced next arrives at router before the time instant, where it is selected by scheduler.
- FB can be modified to obtain threshold value for TCP packets, where service priority assigned to any packet cannot take value larger than threshold.
- FB minimizes/maximizes queue-length distribution under DFR/IFR distributions, and thus also mean queue length EQ and mean response time EV.
- For deterministic service distributions, FB has mean response times that are as large as possible under any work conserving policy
- For Light-tailed service distributions, FB has tail behavior that matches heaviest tail possible under work conserving policies.