In this chapter, I propose monitoring user flows to estimate the traffic matrix between boundary routers because they can provide a stable (i.e., with little variation) and predictive estimate of the actual traffic. The arrival process of these user flows has in general fewer long- and short-range dependencies. It has been reported that arrivals of user flows in the core behave as if they followed a Poisson process [78]. Feldmann reported that the interarrival times of HTTP flows follow a Weibull distribution [73], but as the link rate increases and more flows are multiplexed together, the interarrival times tend to the special case of the exponential distribution according to Cao et al. [33] and also Cleveland et al. [45]. The Poisson arrival process is well understood and there are many models in queueing theory that use it.
The approach I am proposing requires similar hardware support for monitoring active flows to what was described in Section 4.3, basically a fixed-length classifier that can detect new flows and that monitors the activity of the current flows. Such classifiers are already available for OC-192c link speeds [4,71]. However, counting the number of active flows is not enough, as we need to know the average bandwidth that they use. Most of the time it is not possible to estimate the average bandwidth when the flow starts because it requires knowing the flow duration and the number of bits that will be transmitted. In contrast, it is possible to have an upper bound, which I will call peak bandwidth5.3 of a flow. I consider this flow peak bandwidth to be constant throughout the lifetime of the flow, and it can be determined the same way as in Section 4.3.3 (through signaling or through an estimation of the access link bandwidth) even if one does not know a priori the flow average bandwidth.
More formally, once we know the set of active flows between a pair of boundary routers at a given instant, F(t), we need only to assign a peak bandwidth to each of the flows, Cf, where
Cf average BW(f ),f 
F(t). Then, we need a circuit with a capacity,
Kcct(t), that is greater than or equal to the sum of the flow peak bandwidths,
C(t) = Cf and
Kcct(t) C(t).
Many circuits take time to be created because circuit management signaling, switch scheduling, and/or crossconnect reconfiguration may be slow. If we decide that we need to increase the circuit capacity between two boundary routers, C(t), there will be some latency, T, before the changes take place. During this latency period, the circuit capacity will be insufficient, and queueing delays and potentially packet drops will occur at the circuit head. I call this a circuit overflow. More precisely, a circuit overflow happens at time t when:
Obviously, the longer the circuit-creation latency, T, is, the more circuit overflows occur.
A way of avoiding circuit overflows is to provision extra capacity as safeguard. The size of this safeguard band depends on T and the dynamics of traffic, and it determines the probability of a circuit overflow.
I have used several user-flow traces from the Sprint Backbone [170] to analyze the sizes of the safeguard bands based on the signaling delays and the overflow probabilities. Figure 5.4 displays a sample path showing how the safeguard band varies with time for a circuit-creation latency of
T = 1 s. Based on the sum of average bandwidths of the active flows (dashed line) and the sum of the corresponding peak bandwidths,5.4 one can construct the instantaneous peak-bandwidth envelope, C(t), depicted as a solid line. The dotted line shows the safeguard-band envelope, i.e., the maximum of the peak-bandwidth envelope in the next T period (= 1 s),
(t) = max{C(); [t, t + T)}.
Since we cannot predict the future, we can instead analyze (t) to find the safeguard band, STp, for a given overflow probability p. In other words, we calculate STp such that P((t) - C(t)STp . C(t))p. In a real system, we would continuously estimate the instantaneous peak-bandwidth envelope, C(t). If at any time the difference between the circuit capacity and C(t) goes below the safeguard band, Kcct(t) - C(t) < STp . C(t), then we would request an increase in the circuit capacity, so that the spare capacity remains above the safeguard band to avoid circuit overflows.
Figure 5.5 depicts the safeguard band relative to the peak-bandwidth envelope, ((t) - C(t))/C(t), for various overflow probabilities and circuit-creation latencies for one OC-12 link in the Sprint backbone. There are some stair-case steps for a relative safeguard band between 0.04% and 0.3% because the peak-bandwidth envelope can only increase in multiples of 56 Kbit/s, which is around 0.04% of the peak-bandwidth envelope.
|
Figure 5.5 confirms our intuition that the longer the circuit-creation latency, the larger the safeguard band needs to be for a given overflow probability. For example, for an overflow probability of 0.1%, one needs a safeguard of 0.15% times the current peak-bandwidth envelope for T=1ms, 0.8% for T= 10ms, 6% for T= 100ms and 12% for T= 1s. The faster the crossconnect and the signaling are, the more efficiently resources are used. This result indicates that we should use fast signaling and fast switching elements for the establishment of circuits.
It should also be noted that for safeguard bands greater than or equal to 0.1% of the peak-bandwidth envelope and latencies smaller than or equal to 100 ms, a ten-fold decrease of the circuit-creation latency corresponds to a ten-fold decrease in the overflow probability for the same safeguard band. These results were consistent among all traces that were studied. Figure 5.6 shows the cumulative histogram of the peak-bandwidth envelope for the different Sprint traces. The trace used for Figure 5.5 is the one centered around 150 Mbit/s (nyc-07.0-010724). The other traces yielded similar safety margins.
The liberation of resources is not as important as their reservation because their release does not directly contribute to a circuit overflow (unless bandwidth is scarce, but as mentioned in Chapter 2, bandwidth is plentiful in the core). One can simplify the circuit management signaling with a scheme that uses soft state and an inactivity timeout. This simple scheme would retain the extra circuit bandwidth for a period of time that is at least as long as the circuit-creation latency to avoid oscillations in the resource allocation.