Research and education networks (RENs) worldwide, attracted by the benefits of software-defined networking (SDN) for services involving traffic engineering (TE) such as bandwidth on demand (BoD), have started to include SDN in their network evolution plans. BoD allows users to request end-to-end connectivity services of known duration with a guaranteed bandwidth. Considering such a scenario, this paper presents a set of algorithms and two novel data structures for provisioning of the BoD service in SDN-based RENs. First, network snapshots are used to represent a period of time during which resource availability remains constant. Second, the network snapshot tree (NSTree) allows for different network snapshots to be arranged hierarchically using a time-based node aggregation policy. Additionally, each network snapshot stores multiple alternative paths for each source-destination pair. This innovative approach allows for the network resource utilization and number of service requests being accepted in the network to be improved compared to the most common approach of a single shortest path being considered for each destination. As a result, our approach allows for network resource utilization to be improved by approximately 30%. Furthermore, the two-phase procedure used to pre-compute alternative paths and perform admission control makes it possible to achieve response times on the order of milliseconds, enabling the real-time provision of the service.