Exploring algorithms for network capacity dimensioning, and traffic modeling along with performance evaluation

In this thesis, algorithms for network traffic engineering are explored within three areas. The first area is about network capacity dimensioning, and contains the following four optimization problems: Minimum Cost Routing Problem (MCRP), Balanced Utilization Routing Problem (BURP), Minimum Delay Routing Problem (MDRP) and Minimum Cost Spare Capacity Problem (MCSCP).; The first problem, the MCRP, is solved with the well-developed Lagrangian relaxation algorithm, which takes another efficient algorithm, the “successive approximation push-relabel method” as the procedure to solve the minimum-cost flow problem associated with each commodity in a Lagrangian subproblem.; The remaining three problems are variations of MCRP. Each of them is first converted into one or a series of MCRP, and then solved by an algorithm having the MCRP algorithm as a component. Among these problems, the formulations for BURP and MCSCP are new, and we have not seen similar ones in our literature review.; The second area is about modeling network traffic as self-similar processes, and their parameter estimation. Our main contributions are: proposing a new approximation schema, which is more accurate and more efficient than the existing ones, to calculate the spectral density for FGN (Fractional Gaussian Noise, a special type of self-similar processes); improving the efficiency of the Whittle's estimator (one of the best estimators for self-similarity parameter) significantly by using the proposed approximation schema.; The third area is about algorithms to synthesize self-similar network traffic traces, and performance evaluation by taking the following two types of synthesized traces as input into a simulated queue: self-similar traces with different self-similarity parameter values, and Poisson traces. Our main contributions are: improving the efficiency of a svnthesis algorithm for FGN based on Discrete Time Fourier Transform, by using the approximation schema for the formula of spectral density proposed in the second area; correcting mistakes in a wavelet-based synthesis algorithm and proposing improvements on the accuracy of the algorithm; comparing three performance metrics (packet loss percentage, packet delay, and packet delay jitter) among the different synthesized traces as input into the simulated queue.