| Congestion information can greatly benefit network level decisions. For example, fast-reroute algorithms should leverage congestion information when computing backup paths. They could also use the information to monitor if the re-routing decision itself causes congestion in the network. Today, most solutions for inferring congestion work at the end-host level and relay end-to-end congestion information to transport protocols. Network level decisions, on the other hand, may need link level congestion information. Unfortunately, the mechanisms that routers can use to infer link level congestion information are insufficient. Such information could potentially be obtained by periodically sharing estimates between routers. However, this solution increases the traffic load on the network and has difficulty in reliably delivering the estimates during periods of congestion.;In this thesis we show that routers inside an autonomous system can easily and accurately infer congestion information about each other. Routers first measure path level congestion information only from the congestion markings in the traffic that they forward. Next, we propose that routers combine routing information with the path level congestion information to obtain a more detailed description of the congestion in the network. Link level congestion information can be computed using this approach. Our techniques never add supplementary traffic into the network and use little router resources. They can be deployed incrementally or in heterogeneous environments. We show that the accuracy of the inference is good using experiments with multiple traffic patterns and various congestion levels. |
