Summarization: The strain imposed by the bandwidth demands of multimedia applications on wired and wireless networks calls for efficient novel solutions to the problem of network resource allocation, to avoid significant packet losses. In this letter, we focus on a large variety of MPEG-4, H.264 and H.265-encoded video traces. We use the metaheuristic technique of Simulated Annealing to predict the size of B-frames, and compare it against an existing approach from the literature. B-frame size prediction can be used in order to reduce bandwidth requirements and smoothen the encoded video stream, by selective B-frame dropping. We show that Simulated Annealing can significantly improve the prediction accuracy.Presented on