Efficient Techniques and Tools for Intra-Domain Traffic Engineering

In an Autonomous System (AS), links that connect routers have certain metric (administrative weight or cost of transferring an IP packet) that can be modified by network administrators, usually for the purpose of minimizing traffic congestion or minimizing the cost of overall routing. As traffic is routed along the shortest paths in the network, finding an optimum combination of these integer weights is proved to be NP-Hard (Fortz and Thorup 2000) due to hard protocol constraints, e.g. a flow is evenly distributed along the shortest paths between its origin and destination nodes, also referred to as equal cost multi-path (ECMP) rule. We study the link weight optimization problem in intra-domain networks. We present an open source Internet Traffic Engineering toolbox (TOTEM) and its link weight optimizer (IGP-WO) that we have developed and implemented. Furthermore, we present two heuristic approaches to generate fast and efficient link metric for intra-domain routing. We also present some promising experimental results that were done using various sizes of networks and traffic matrices