On-line routing of MPLS tunnels with time-varying bandwidth profiles

We consider the problem of routing bandwidth-guaranteed flows with time-varying bandwidth profiles on an MPLS network. We assume that each demand is routed in a fixed LSP, and that the amount of bandwidth that must be reserved along the LSP varies during the day according to a piece-wise mask which is known in advance. Such profiles can be explicitly declared by the VPN customers in the SLA, or, alternatively, predicted by the ISP based on past measurements. We propose a simple on-line algorithm based on shortest-path computation with link weights influenced by the residual peak bandwidth. We also provide an ILP formulation for the associated off-line problem, and adopt it as a reference performance bound for the on-line algorithm. The results presented show that the proposed algorithm, despite its simplicity, closely approximates the optimal solution. The paper shows that the a priori knowledge of the per-demand traffic profiles, still within a fixed routing framework, can be exploited to achieve a sensible bandwidth saving, and/or to differentiate bandwidth provisioning (and billing) on a per-hour basis.