  The increasing popularity of jumbo frames means growing variance in the size
of packets transmitted in modern networks. Consequently, network monitoring
tools must maintain explicit traffic volume statistics rather than settle for
packet counting as before. We present constant time algorithms for volume
estimations in streams and sliding windows, which are faster than previous
work. Our solutions are formally analyzed and are extensively evaluated over
multiple real-world packet traces as well as synthetic ones. For streams, we
demonstrate a run-time improvement of up to 2.4X compared to the state of the
art. On sliding windows, we exhibit a memory reduction of over 100X on all
traces and an asymptotic runtime improvement to a constant. Finally, we apply
our approach to hierarchical heavy hitters and achieve an empirical 2.4-7X
speedup.
