Enhancing distributed traffic monitoring via traffic digest splitting

Recently, several Traffic Digest-based Network Monitoring schemes including, Datalite[24], Proportional Union (Pu) [9] and the Quasi Maximum Likelihood approach (Qmle) [8] have been proposed to support distributed traffic measurement and analysis (TMA) for high-speed packet networks in general and network-wide Origination-Destination-pair-based Flow measurement estimation in particular. In these schemes, traffic flows defined by their O–D pair are mapped into a single traffic digest (TD) for measurement as they traverse through a monitoring point. It has been observed that the relative estimation error caused by such single-TD approach is significant for low-volume flows (mice) when they share the link with other large volume ones (elephants), which is quite common in practice. In this paper, we propose to enhance existing TD-based distributed traffic monitoring schemes by taking a localized optimal TD splitting strategy: flows sharing the same link are partitioned and mapped into different sub-TDs according to their previously estimated flow volume. By avoiding the mixing of “mice” and “elephant” flows in a single TD, we can significantly reduce the “noise-to-signal” ratio experienced by the former. Moreover, it can be shown that the reduction in such “noise-to-signal” ratio is more than enough to offset the negative effect caused by reduction in TD memory size for each sub-group (since the total memory size required across all sub-TDs is kept to be the same as that of the single-TD approach without splitting). We have derived analytical expressions of the optimal splitting threshold by minimizing the resultant maximum relative error of the flows sharing a link under various traffic distributions. Our simulation results using empirical traffic traces show that, with single-level TD-splitting, we can reduce the r.m.s. relative estimation error of all flows by 8–76%, depending on the baseline TMA scheme. More importantly, this can be translated to 15–94% savings in TD memory size while maintaining the same estimation error requirement. We also show that, by applying localized multi-level TD-splitting, further savings can be realized at the expense of additional implementation complexity.