The paper "Internet Traffic Engineering by Optimizing OSPF Weights" by Bernard Fortz and Mikkel Thorup explores the optimization of OSPF (Open Shortest Path First) weights to improve network traffic flow. OSPF is a widely used intra-domain routing protocol that routes traffic along the shortest paths, with weights assigned to links to guide the routing. The authors aim to optimize these weights to minimize congestion and maximize load balancing. The main contributions of the paper include: 1. **NP-hardness of Weight Optimization**: They prove that optimizing OSPF weights for a given set of demands is NP-hard, necessitating the use of a local search heuristic. 2. **Heuristic Algorithm**: A local search heuristic is developed to find near-optimal weight settings. This heuristic uses hash tables to avoid cycling and diversify the search, making it efficient and effective. 3. **Synthetic and Real Networks**: The heuristic is tested on both synthetic and real networks, including the AT&T WorldNet backbone. For the AT&T backbone, the heuristic found weight settings that performed within a few percent of the optimal general routing, indicating that OSPF can achieve good load balancing with clever weight settings. 4. **Performance Comparison**: The heuristic outperforms standard OSPF heuristics such as weights inversely proportional to capacities or proportional to physical distances. It can support a 50%–110% increase in demands while keeping max-utilization below 100%. The paper concludes that OSPF with clever weight settings can provide significant gains in traffic engineering, even compared to more flexible MPLS (Multi-protocol Label Switching) technologies. The results suggest that OSPF can be a powerful tool for increasing a network's ability to handle increasing demands.The paper "Internet Traffic Engineering by Optimizing OSPF Weights" by Bernard Fortz and Mikkel Thorup explores the optimization of OSPF (Open Shortest Path First) weights to improve network traffic flow. OSPF is a widely used intra-domain routing protocol that routes traffic along the shortest paths, with weights assigned to links to guide the routing. The authors aim to optimize these weights to minimize congestion and maximize load balancing. The main contributions of the paper include: 1. **NP-hardness of Weight Optimization**: They prove that optimizing OSPF weights for a given set of demands is NP-hard, necessitating the use of a local search heuristic. 2. **Heuristic Algorithm**: A local search heuristic is developed to find near-optimal weight settings. This heuristic uses hash tables to avoid cycling and diversify the search, making it efficient and effective. 3. **Synthetic and Real Networks**: The heuristic is tested on both synthetic and real networks, including the AT&T WorldNet backbone. For the AT&T backbone, the heuristic found weight settings that performed within a few percent of the optimal general routing, indicating that OSPF can achieve good load balancing with clever weight settings. 4. **Performance Comparison**: The heuristic outperforms standard OSPF heuristics such as weights inversely proportional to capacities or proportional to physical distances. It can support a 50%–110% increase in demands while keeping max-utilization below 100%. The paper concludes that OSPF with clever weight settings can provide significant gains in traffic engineering, even compared to more flexible MPLS (Multi-protocol Label Switching) technologies. The results suggest that OSPF can be a powerful tool for increasing a network's ability to handle increasing demands.