Based On The Ecmp Ip Network Traffic Engineering Study

With the rapid development of the Internet, various multimedia services such as audio, vedio and online games have emerged. As a result, bandwidth demand increased to a high level, which makes bandwidth allocation a challenging problem. To address this issue, traffic engineering is considered as an effective approach to distributed traffic around in network to avoid congestion. Traditionally, this kind of"load banlancing"could be only achieved by tuning link weights. Recently, IETF defined an enhanced mechanism called Equal-Cost Multi-Path (ECMP), which, together with link weight tuning, can achive better performance in terms of load banlancing. However, the optimization problem in this situation is quite different from traditional single shortest path problem. Therefore, traffic engineering based on ECMP has great significance to research.The works presented in this thesis falls in two parts. Firstly, we develop techniques for solving ECMP-based link weight assignment problem, which can be modeled as a Mixed Integer Programming (MIP) problem with high complexity. Secondly, two versions of the ECMP-based link weight assignment problem are studied, in which realistic constraint and objective metric are considered.Since the MIP model of ECMP-based link weight assignment problem is hard to slove, an Enhanced Branch-and-Cut algorithm is proposed. By adding path-based constraints as cut inequalities, the searching space and the time consumed is reduced effectively. But, some problem instances with large-scale network topologies (e.g., more than 10 nodes) can not be solved by this algorithm in an acceptable time. To address this issue, a modified Genetic Algorithm for ECMP (GAECMP) is proposed, and the experimental results show that this algorithm can obtain approximate solution in a time-efficient manner.However, the original ECMP-based link weight assignment model does not consider some constraints or metrics arise in realistic scenarios. In this thesis, the original model is extened according to two different scenarios. Firstly, the scenario of limited ECMP deployment is considered, in which only a portion of the routers in network can forward packets according to ECMP strategy. We developed an Optional ECMP (OECMP) model to account for this variation. Based on this model, the relationship between the percentages of routers with ECMP functions and network performance is studied, and the best allocation strategy for ECMP nodes is discussed. Secondly, it is often the case that cost of bandwidth consumption is needed to be considered beside the load banlancing metric. We introduced a model called Expense-ECMP (EECMP) to describe this scenario. Based on this model, the relationship between these two objectives (to minimize the maximum link utilization and to minimize the expense of link bandwidth consumed) is studied through extensive simulations.