A network traffic engineering method, system and computer program cope with dynamic and unpredictable changes in traffic demands and in the availability and quality of interdomain routes by monitoring traffic over a network having nodes and links, calculating a routing utilizing a convex-hull-based optimal traffic engineering algorithm with penalty envelope (COPE), and adjusting network traffic flow in accordance with the calculated routing. Aggregating collected historical traffic matrices to produce a predicted traffic matrix, the method optimizes for the expected traffic scenario while providing a worst-case guarantee for unexpected traffic scenarios and thereby advantageously achieves efficient resource utilization during normal traffic and avoids network congestion in a wide variety of scenarios.