Flow Deviation: 40 years of incremental flows for packets, waves, cars and tunnels

It was about 40 years ago that the ARPANET had surpassed 40 nodes and was rapidly growing at the rate of one node per month. The first government and commercial P/S networks were emerging. Designing an efficient topology and flow assignment strategy that could meet the requirements at lowest costs was essential in order to outperform the competition represented by circuit-switched or private-line networks. The challenge was to solve a combined flow and capacity assignment problem. Researchers at UCLA, under Len Kleinrock’s leadership and DARPA support, developed a method based on multicommodity flow and non-linear programming principles called the Flow Deviation (FD) algorithm. The key underlying technique was to “deviate flows” on incrementally improving paths until the optimum was reached. In the early days, the FD algorithm was used to design and “upgrade” the growing ARPANET topology. After the ARPANET topology became stable, the FD algorithm took on a life of its own as an intuitive, efficient method to solve a variety of network flow problems in different domains, from ARPANET packets to WDM wavelengths, urban traffic cars and SDN tunnels, as reflected in the over 500 citations.This paper reviews the key concepts and features of the FD algorithm as published in 1973, traces the various problems and scenarios to which it has been applied (most recently, vehicular traffic management) and discusses the possible use of FD in today’s SDN tunnel allocation.