In a bandwidth allocation protocol for a mobile communications network, mobile terminals indicate the total quantity of data awaiting transmission, the maximum delay time of the most urgent portion of the data, and the maximum delay time of the least urgent portion. If a collision occurs between transmission by two mobiles, the mobiles wait for an interval controlled by the network before attempting another contention-based access transmission. The network periodically varies the contention-based access capacity available according to the observed usage level and/or collision rate in the previously allocated contention-based access capacity. The network analyses the forward traffic to individual mobiles and predicts likely return bandwidth requirements. The network stores associations between forward and return frequency channels, so that when a mobile receiving a forward frequency channel request return capacity, the network preferentially assigns return bandwidth to the mobile in one or more of the associated return channels.