Size-Based Flow-Scheduling Using Spike-Detection (Telecommunication Networks) (Analytical and Stochastic Modeling) Part 2

Simulations: Goals and Settings

Goals

The goal of the simulations is mainly to evaluate the performance of the TLPS scheduler using spike-detection mechanism. Precisely, we would like to compare it with the following policies:

— FCFS: A router today usually has a FCFS scheduler serving packets arriving at the drop-tail buffer. We use ‘FCFS’ to denote this system.

— PS+PS: This policy uses a threshold 0, to differentially serve large and small flows (as discussed in section 3).

— SB-TB: This mechanism uses both sampling and PS+PS scheduling. It uses the threshold parameter 0, as well as the per-packet sampling probability ps.

Unlike most previous works, where the performance was analyzed using just one metric (usually the conditional mean response time), we consider the following different metrics:

1. Conditional mean completion time of small flows;

2. Number of time-outs encountered by small flows;

3. Number of times the congestion windows were reduced (congestion cuts) by all flows;

4. Mean completion time for range of flow sizes;

5. Mean completion time for small flows, large flows and all flows;

6. Maximum completion time of small flows.

Settings

Simulations are performed using NS-2. A dumbbell topology as seen in Fig. 1(a) was used throughout. The bottleneck link capacity was set to 1 Gbps, and the capacities of the source nodes were all set to 100 Mbps. The delays on the links were set such that the base RTT (consisting of only propagation delays) is equal to 100 ms. The size of the bottleneck queue is set in bytes, as the bandwidth delay product (BDP) for 100 ms base RTT. There were 100 node pairs, with the source nodes generating flows according to a Poisson traffic. The flow arrival rate is adapted to have a packet loss rate of around 1.25% with FCFS scheduler and drop-tail buffer.


Flow sizes are taken from a Pareto distribution with a = 1.1, and mean flow size set to 500 KB. 20, 000 flows are generated during each run, all carried by TCP, in particular, using the SACK version. Packet size is kept constant and is equal to 1000 B. For simplicity, we keep the parameters of TLPS/SD mechanism n and [, as well as the threshold 0 used in PS+PS and SB-TB policies, in packets. n is set to 4. The other parameter of interest, 0, of both PS+PS and SB-TB policies, is set to 31 packets. Packet sampling probability (used in SB-TB policy), ps = 1/100. The value of [ was set to 200 packets to reduce the number of packet processing required for the mechanism, and this is discussed in Section 7.1.

For post-simulation analysis, we define 'small flow' as a flow with size less than or equal to 20 KB, and 'large flow' as one with size greater than 20 KB. Here the flow size is the size of data generated by the application, not including any header or TCP/IP information. Also note that, a small flow of 20 KB can take more than 25 packets to transfer the data, as it includes control packets (like SYN, FIN etc.) and retransmitted packets.

Performance Analysis

Efficiency

In this section, we analyze the efficiency of the TLPS/SD mechanism.

For now, in the SD mechanism, we assume the following sequence order at an equipment: arriving spikes are queued, the queue length is observed, if its greater than [ , the spike-detection mechanism is triggered. That is, the mechanism is triggered only at instants of spike-arrivals causing actual length to exceed [ packets. This means, the maximum number of packets before the spike arrived is not greater than [ . The spike that arrived just then, has packets that belong to a single flow; hence header processing is done only once, and so is the creation/update of flow-table entry. But, for each of the packets in the queue, which is not greater than [, flow-table lookup and creation/update has to be done.

At the packet level, the probability that the queue length exceeds l packets is P(Q > l). Due to PASTA property, an arriving batch in MX/M/1 queue, finds the queue length greater than l with the same probability, P(Q > l). Triggering of the SD mechanism will result in the processing of (headers of) all the packets in the queue as well as the arriving batch.

Fig. 1.

Fig. 1.

Given the probability of batch size as in in Eq. (4), the mean number of packets processed per arriving batch is,

tmpF-800_thumb

We take the mean number of packets processed (per arriving packet) as E[N]/E[X], where E[X] is the mean batch size. Fig. 1(b) plots the mean number of packets processed per packet, during the spike-detection process, for varying values of 3. The batch size was set to 20. Observe that, the mean number of packets processed can be brought down by increasing the value of 3 for a given load. For example, for 3 = 200 packets, the number of packets processed is less by at least an order of magnitude in comparison to the number of packets that arrive to the system.

Validation Using Simulations: Simulations were carried out to validate the analysis above, with the scenario as described in Section 6.2. n was set to 4; and the value of 3 was set to 100, 200, 300 and 400 packets, in different runs. It was noted that 29.93% of the packets that arrived were processed for spike detection, when 3 was 100; whereas, only less than 3.1% of arriving packets were processed for 3 = 200, and the percentage remained close for the other values of 3 (300 and 400 packets). We therefore set 3 = 200 for analysing the performance of small flows. The figures following are obtained from simulations.

Analysis Using Flow Metric

Fig. 2(a) shows the conditional mean response time for small flows. Observe that, all policies perform better than FCFS with respect to this metric. TLPS/SD performs similar to PS+PS for small flows. Another important observation is that TLPS/SD performs better than both PS+PS and SB-TB policies, for medium size flows with size greater than the threshold 0. PS+PS policy soon approaches FCFS with increasing flow size, though the flow sizes are not large. This happens as PS+PS serves all flows with size greater than 0 in the low-priority queue, once the first 0 packets are served in the high-priority queue. SB-TB policy serves a flow in the high-priority queue until the flow not only gets sampled but also sends 0 packets after being sampled; hence giving better performance to medium-size flows in comparison to PS+PS. On the other hand, in TLPS/SD, a flow can be served in the high-priority queue as long as the queue Q1 does not build up to greater than 3 packets. Therefore, some of the medium-size flows may get served in the high-priority queue, decreasing the corresponding mean response time.

Conditional mean completion time for large flows

Fig. 2. Conditional mean completion time for large flows

Fig. 2(b) shows that large flows are not harmed by giving priority to small flows. But, from Fig. 3, which plots the mean response time for different ranges of flow sizes, it can be seen that TLPS/SD gives improved response time to small flows at the expense of large flows. Large flows experience the worst mean delay in TLPS/SD policy. This is expected, as the scheduling policies used here are work-conserving in nature. Once again, note that TLPS/SD gives reduced completion time for small and medium-size flows, in comparison to the rest.

Next we show the maximum completion time faced by flows of a given size. For clarity, it is displayed in two figures: Fig. 4(a) and Fig. 4(b). Fig. 4(a) compares FCFS with TLPS/SD. Evidently, flows under FCFS experience high variance in the maximum completion time. In Fig. 4(b) (along with Fig. 4(a)) we see that TLPS/SD performs better than not only FCFS, but also PS+PS and SB-TB policies, when it comes to the worst-case delay faced by small flows. Observe that, under PS+PS policy, flows with sizes near to, but greater than the threshold can experience maximum delays that are not better than in FCFS. This happens as the last few packets of these flows are queued in the low-priority queue Q1 once the threshold is exceeded. If Q2 has large queue length, it can cause time-outs to these small flows, thereby increasing the response times many fold. Similar explanation goes for SB-TB policy, in particular for flows that get sampled early in their life-times.

Mean completion time

Fig. 3. Mean completion time

Maximum completion time

Fig. 4. Maximum completion time

Table 1 compares other metrics. For each policy, the table lists the number of timeouts faced by small flows in the first column, the total number of cwnd cuts in the second column, and the mean completion times (indicated by CT) for small, large and all flows in the remaining three columns. A note on the second metric: sum CC (standing for ‘Congestion Cuts’) gives the total number of times all the flows reduced their congestion windows during their lifetimes.

The table shows that TLPS/SD policy reduces the number of timeouts encountered by small flows, in comparison to other policies. The reason for this is, in the spike-detection mechanism, many flows that have sizes near, but greater than 2n+1 also enjoy service in Q1. For example, all flows of size below 48 packets, are served in Q1 even if some of them have size greater than 2v+1 for n = 4. This is because such flows do not have a spike greater than 2n packets. One may get comparable performance using PS+PS by increasing its threshold 0.

Now, observe the values of the second metric — sum CC — for the policies. As congestion cuts are equivalent to congestion signals, we can say that, flows face the largest number of congestion signals in PS+PS policy, even more than FCFS. 

Table 1. Comparison of different metrics

Metrics

small TOs

sum CC

small CT

large CT

all

CT

FCFS

579

9988

0.8432

2.3294

1.9022

PS+PS

416

12710

0.4355

2.0627

1.5950

SB-SH

460

8949

0.4377

1.6299

1.2872

TLPS/SD

311

7110

0.4246

1.6504

1.2981

The reason for this is the same as said earlier — all the medium-size (and even small-size) flows with size starting from just above 0, join the tail of the low-priority queue soon after having sent the first 0 packets. During high-loads, when the low-priority queue is building up, they may face packet drops. This does not happen so deterministically in neither SB-TB nor in TLPS/SD. In SB-TB policy, it depends on when the flow gets sampled, and in TLPS/SD such flows will be de-prioritized only when the length of Q1 exceeds 3 packets; and the build-up of Q1 is not influenced by the load at Q2. This performance gain is also emphasized in Fig. 3. TLPS/SD is also seen to give the minimum overall mean completion time for small flows.

Conclusions

Size-based flow-scheduling is a solution to improve the response times of mice flows, which will otherwise be adversely hurt due to the presence of large elephant flows. In the absence of sampling, the existing mechanisms are far from being practical, as they are either complex or have scalability issues. In this paper, we proposed a new way of detecting large flows without the need to track all flows. The number of packets processed (for performing size-based scheduling) in this new system is less by at least an order of magnitude in comparison to the number of packets that arrive. Large flows are detected only at times when they cause the queue length to grow beyond a pre-determined threshold, using the TLPS scheduling along with spike-detection mechanism. We also presented an integrated packet/spike model for the high-priority queue in such a system, and showed the existence a fixed-point for the throughput that depends on the queue-length threshold 3.

The TLPS/SD has a number of good properties. The response time achieved by the small flows in the TLPS/SD system is even better than that achieved in PS+PS scheduling, as the latter de-prioritizes flows using just one information — the threshold 0 — in a deterministic manner. Though SB-TB policy is better (than PS+PS) in this aspect, still the flows getting detected early would be treated similarly, and this was highlighted while comparing the maximum delay faced by small flows. On the other hand, TLPS/SD uses the queue-length information to de-prioritize flows, and hence gives improved response times to not only small flows, but all medium-size flows. This is a more ‘natural’ approach, as  flows need to be treated differentially only when the system is near overload. The improvement brought by the TLPS/SD system was highlighted by comparing a number of metrics.

In addition, it should be noted that, while the PS+PS policy as well as the SB-TB policy de-prioritize even constant-bit-rate flows, TLPS/SD will not do so, as long as they do not cause queueing. Similarly, large flows that are too slow will not have large spike-size (as packets may be dispersed in time), and hence will not be de-prioritized either. But, PS+PS and SB-TB policies will de-prioritize even such flows, further slowing them down.

While exploring and analyzing this new approach of performing size-based scheduling in a practical way, we also revealed the performance of both PS+PS and SB-TB policies using a number of metrics not studied earlier.

The integrated packet/spike model developed here can be used to analyze the performance of flows in both the queues. As part of future work, we intend to work on this.

Next post:

Previous post: