A video server or other processing device obtains availability information for a wireless network and modifies a manner in which video segments of a video service are delivered to a user device over the wireless network based on the obtained availability information. The availability information may comprise at least one of network congestion measurement information and transmission pricing information. In an illustrative embodiment, the processing device comprises a video server configured to utilize the availability information to generate a list of video segments available for transmission for at least a portion of the video service, to provide the list of video segments to the user device responsive to a request received from the user device, to receive an additional request from the user device for at least one particular video segment identified in the list, and to provide the requested at least one video segment to the user device.