A novel neuro-evolutionary Cartesian genetic programming-based frame size estimator for multimedia streaming applications has been proposed in this letter. The frame size obtained from the proposed estimator is used to calculate and allocate the bandwidth required for frame transmission. Bandwidth calculation and allocation is done via various probabilistic and linear regression methods. To obtain conclusive results regarding the feasibility of the proposed system, different test case scenarios have been exploited. The bandwidth allocation efficiency for the technique has been compared with previously proposed methods to evaluate its effectiveness in precise bandwidth utilization. Compared to other contemporary techniques, our technique gives approximately 98% efficient frame size prediction and bandwidth allocation.