Traffic Engineering (TE) is defined as the aspect of Internet network engineering dealing with the issue of performance evaluation and performance optimization of operational networks [1]. In particular, we will focus on the last aspect; i.e. enhancing the performance of an operational network. This problem was extensively studied in the early 90s, since resources were considered scarce and expensive. However, the cost of core link capacities dramatically decreased in subsequent years, which resulted in considering a simple upgrade in this capacity as the panacea of all problems.

Nevertheless, as network services and Internet applications evolved, network traffic has become increasingly complex and dynamic. The convergence of data, telephony and television services on an all-IP network directly translated into a much higher variability and complexity of the traffic injected into the network. To make matters worse, the presence of unexpected events such as network equipment failures, large-volume network attacks, flash crowd occurrences and even external routing modifications induces large uncertainty in traffic patterns. Moreover, current evolution and deployment-rate of broadband access technologies (e.g. Fiber To The Home) only aggravates this uncertainty.

But these are not the only problems network operators are confronted with. The ever increasing access rates available for end-users we just mentioned is such that the assumption of infinitely provisioned core links could soon become obsolete. In fact, recent Internet traffic studies from major network technology vendors like Cisco Systems forecast the advent of the Exabyte era [2, 3], a massive increase in network traffic driven by high-definition video. Furthermore, there are new emerging architectures in which resources are intrinsically scarce (e.g. Wireless Mesh Networks). Thus, simply upgrading link capacities may no longer be an economically or technically viable solution. Moreover, even if overdimensioning would be possible, its environmental impact is not negligible. For instance, the Information and Communication Technology sector alone is responsible for around 2% of the man made CO2, a similar figure to that of the airline industry, but with higher increasing perspectives [24]. An efficient and responsible usage of the resources is then essential.

In the light of this traffic scenario, TE has regained the interest of the academic as well as the industrial community. More to the point, network operators are now, more than ever, in need of Traffic Engineering mechanism which are efficient (make good use of resources), robust with respect to network variations (changes in traffic demands, or characteristics of transported flows) and more tolerant (in case of node/link failures). As the network size increases, its management may become a very complicated  ask. That is why network operators are also interested in the automatization (as much self-configuration as possible) of the TE mechanisms they implement.

We have separated the thesis in two parts. The first one assumes that resources have been reserved and are exclusively used by each of the paths. A typical use of these tunnel-based architectures (e.g. MPLS-TE, T-MPLS, PBT, GELS) is VPN provisioning in metro and backbone networks. Up to now, resources associated with each of these tunnels are usually specified using token buckets. This classical QoS scheme has been described as inefficient and inappropriate for characterizing traffic aggregates [10]. It has been verified that the burst parameter needs to be excessively large, even when the rate parameter is significantly greater than the actual flow mean rate, to achieve a given non-conformity probability. This means that relying on declared token bucket traffic parameters is typically very conservative, which leads to wasted resources.

An attractive alternative is to use the Cross-Protect mechanism [11, 12]. This flow-aware TE technique allows performance guarantees for both streaming and elastic flows while preserving the user-network interface (i.e. neither packet marking nor per-flow signalling is required). Moreover, its configuration relies on only two parameters, which are easily mapped to target performance guarantees. These guarantees are given independently of the flow characteristics, a major difference with token buckets. We propose that provider edge routers implement the Cross-Protect mechanism on a per-tunnel basis in the aforementioned architectures. Since resources are reserved for each tunnel, the mechanism needs to be implemented in the edge only, minimizing deployment complexity. We analyze a cross-protect router and derive analytical formulae for its most important QoS parameters.

To improve resiliency and make a better resource utilization, we will extend the aforementioned TE scheme with a simple flow-aware load-balancing mechanism. This new DLB algorithm leads to better results than classical static load balancing schemes. We have also analyzed this algorithm and derived tight approximations for the most important QoS parameters in this case.

It can be proved that the optimum for this second objective function may also be characterized as the equilibrium of greedy OD pairs that strive to minimize a certain path cost function φP . We will then study possible methods to converge to this equilibrium. A third contribution of this part is to present a DLB algorithm based on so-called no-regret algorithms. The authors of a recent paper [21] proved that if all OD pairs use algorithms of this kind, convergence to this greedy equilibrium is guaranteed. In particular, we will use a variation of the Incrementally Adaptive Weighted Majority Algorithm (iAWM) [22], which presents the advantage of being completely self-regulated, thus avoiding any tricky parameter setting and the reactivity-stability tradeoff we mentioned before. Furthermore, we will present certain adaptations of the algorithm that are necessary to enable its use in the presence of non-stationary traffic. The algorithm is illustrated by several packet as well as flow level simulations.