Inter-DataCenter　Wide　Area　Network　(Inter-DC　WAN)　that　connects　geographically　distributed　data　centers　is　becoming　one　of　the　most　critical　network　infrastructures.　Due　to　limited　bandwidth　and　inevitable　link　failures,　it　is　highly　challenging　to　guarantee　network　availability　for　services,　especially　those　with　stringent　bandwidth　demands,　over　inter-DC　WAN.　We　present　BATE,　a　novel　Traffic　Engineering　(TE)　framework　for　bandwidth　availability　(BA)　provision,　which　aims　to　ensure　that　each　bandwidth　demand　must　be　satisfied　with　a　stipulated　probability,　when　subjected　to　the　network　capacity　and　possible　failures　of　the　inter-DC　WAN.　The　three　core　components　of　BATE,　i.e.,　admission　control,　traffic　scheduling　and　failure　recovery,　are　formulated　through　different　mathematical　models　and　theoretically　analyzed.　They　are　also　extensively　compared　against　state-of-the-art　TE　schemes,　using　a　testbed　as　well　as　real　trace　driven　simulations　across　different　topologies,　traffic　matrices　and　failure　scenarios.　Our　evaluations　show　that,　compared　with　the　optimal　admission　strategy,　BATE　can　speed　up　the　online　admission　control　by　30x　at　the　expense　of　less　than　4%　false　rejections.　On　the　other　hand,　compared　with　the　latest　TE　schemes　like　FFC　and　TEAVAR,　BATE　can　meet　the　bandwidth　availability　targets　for　23%∼60%　more　demands　under　normal　loads,　and　when　network　failure　causes　BA　targets　violations.　©　2021　ACM.