Traffic Matrix Estimation for the Delta Routing Protocol

George Porter and Minwen Ji1
(Professor Randy H. Katz)
Compaq/HP Systems Research Center

Large enterprises connect their locations together by building a network (sometimes called an Intranet) out of leased, private communications lines. Although these lines are dedicated to the company's traffic, and thus provide good quality of service, they are very expensive. Because of this, they are not always overprovisioned. HP's Systems Research Center (Palo Alto, California) has developed the delta routing protocol, which allows nodes on a company's network to communicate with each other using both private lines as well as virtual private network (VPN) tunnels over the shared Internet. Each node in the network makes a local decision as to which path (the private network or the shared Internet) is best and forwards data accordingly. Because each node uses only local information, it is possible that it will forward traffic to a part of the network that is congested. In this case, that distant node will have to forward such "excess" traffic over VPN tunnels rather than the private network.

Using this protocol as a base, our contribution is to install measurement agents into each node in the company's network to perform traffic matrix estimations in order to make smarter forwarding decisions. A traffic matrix is a data structure that captures the amount of traffic at each point in the network. With such data, nodes would be able to avoid sending traffic to a portion of the network that is congested. Instead, it would be able to tunnel the traffic around the congestion to a point on the private network where it will be able to continue to the destination. Unfortunately, in a large network it is impractical to give each node a consistent notion of the traffic matrix. Instead, we propose that nodes directly measure flows that they forward and use estimates for flows that travel through another part of the network. These estimates come from periodic flow measurements broadcast from other nodes. A private network using delta routing should be able to respond to congestion if it occurs by shedding excess load to the less predictable, but more flexible, shared Internet.

The delta routing protocol is currently implemented in the ns simulator, and the improved protocol which includes flow measurement and traffic-matrix estimation functionality is in progress. Simulations are going to be performed on both artifically generated networks as well as a model of Compaq's private network.

1HP Systems Research Center

Send mail to the author : (

Edit this abstract