Introduction
The flow deviation algorithm as developed by Leonard Kleinrock et al is an efficient means of assigning routes and flows for a given network topology so as to minimize the overall average delay. The problem consists of finding a set of routes for all communicating end nodes which minimize the delay without violating link capacity constraints. The Flow Deviation method works in a manner very similar to gradient methods for functions with continuous variables, whereby the concept of using gradients is replaced by the concept of “shortest path” flows.
Algorithm Overview
The algorithm proceeds by first assigning length values to network links in proportion to their calculated incremental delay values. Having obtained the set of link length values, the shortest distance paths between all communicating end nodes are found using a shortest path algorithm such a Dijkstra or Bellman. An initial flow pattern can then be determined by loading each of the shortest path links with the traffic requirements.
For every subsequent flow pattern that is then found, it is superposed with with the previously found set of network flow patterns. Superposition involves sending a portion of the network flow on to the old paths and a portion of the network flow on to the new path in such a way as to minimize the total delay. The optimal proportion of flows is found using a binary search over the interval 0..1. To summarize: given and old flow pattern F1, and a new flow pattern F2, the superposed flow pattern F3 is:
F3 = xF1 + (1-x)F2
Having updated the link flows, a new set of shortest paths can then be computed and this process repeated until no significant reductions occur in the average delay.
Finding Shortest Paths
Bellman’s algorithm was chosen to return information on the shortest paths available for a given network topology with link flows and link capacities. It’s output is a two-dimensional array of integers which can be used to determine all of the links in the shortest path between each pair of communicating end nodes. By starting from the destination node, the complete path is found by backtracking along each of the path links until the source node is reached. Once we have these shortest paths, we can load all the shortest path links with their traffic flow requirements.
Finding an initial feasible traffic flow
Upon starting the flow deviation algorithm with an initial set of shortest paths and loading these links with network flows, it may well be necessary to scale up the link capacities at least temporarily, so that they are able to accommodate the flows assigned to them, without any of the link flows exceeding their capacity. As the algorithm iterates and more efficient flow patterns are found, it may be possible to gradually scale back these capacities so they are eventually brought back to their original values without any of the link flows violating their capacity constraints.
C++ Implementation
A modified version of Robert Sedgewick‘s graph data structure was used to represent interconnections between network nodes. Sedgewick’s graph interface essentially consists of two data types:
i. An Edge data type, including a constructor, to represent an edge (link) between two vertices (nodes). Also included in the Edge data type are parameters representing values of link flow, link capacity and link ‘length’.
ii. A Graph data type which incorporates operations to add or remove edges, retrieve edge lists in the form of vector arrays. This Graph structure is used here as a general-purpose interface, in order to support whichever network design algorithms we are interested in applying. The Graph structure also includes V and E variables to directly tell us the number of network nodes and links respectively.
The C++ code implementing the flow deviation algorithm borrows heavily from the algorithm description given in Aaron Kershenbaum‘s book ‘Telecommunications Network Design Algorithms‘ (ISBN:0-07-034228-8), specifically the ‘Chapter 6 – Routing’ section. This project reproduces exactly as possible Kershenbaum’s recommendations, while at the same time taking advantage the advantages in object orientation, data encapsulation and access to the Standard Template Library (STL) that the C++ programming language clearly gives us.
I find static member functions useful when I don’t need to create instances of an object just so I can execute a public function inside it. This was found to be the case when implementing a general utility/helper class for the purpose of repetitively executing each of the Flow Deviation Algorithm components: setting link lengths, loading the links, superposing network flows etc. The FlowDevUtil class does just this kind of repetitive work in the form of a set of public functions that do not require instances to be created and do not have to maintain any state between calls.
The following code sample I think gives a reasonably clear and high-level overview of just how the algorithm achieves the objective of finding the set of network flows and paths that minimise the overall delay:
// Flow deviation algorithm
void Algorithm::FlowDeviation( Graph<Edge>* graph,
SPdist& spdist,
SPpred& sppred,
Req& req,
const int& MsgLen )
{
double PreviousDelay = INFINITY;
int TotalReq = FlowDevUtil::Accumulate( req );
const int nn = graph->V();
FlowDevUtil::SetLinkLens( graph, MsgLen );
for ( int i = 0; i < nn; ++i )
Bellman( graph , i, spdist, sppred );
FlowDevUtil::LoadLinks( graph, req, sppred, true );
bool Aflag = FlowDevUtil::AdjustCaps( graph );
double CurrentDelay =
FlowDevUtil::AverageDelay( graph, TotalReq );
int iter = 0;
while ( Aflag || std::fabs(CurrentDelay - PreviousDelay) > EPSILON )
{
FlowDevUtil::SetLinkLens( graph, MsgLen );
for ( int i = 0; i < nn; ++i )
Bellman( graph , i, spdist, sppred );
FlowDevUtil::LoadLinks( graph, req, sppred, false );
FlowDevUtil::Superpose( graph, TotalReq, MsgLen );
if ( Aflag || iter < 20 )
{
Aflag = FlowDevUtil::AdjustCaps( graph );
}
PreviousDelay = CurrentDelay;
CurrentDelay =
FlowDevUtil::AverageDelay( graph, TotalReq );
iter++;
}
}
Example Usage
For the purpose of demonstration, I have used the same network topology and traffic requirements as the example problem given in Kershenbaum's book. Using the API provided by the Algorithm class to obtain the optimal network flows and routes is simple.
1. First provide the set of Edge components that specify interconnections between nodes (links) as well as their link capacity values and link flow values. Use this array of Edge types to initialize the modified version of Sedgewick's Graph data structure.
2. Create and initialize the traffic requirements matrix (req), a two-dimensional array representing the required traffic flow between communicating end nodes.
3. Create the shortest path matrices, which are also two-dimensional arrays, and are used to store shortest paths (sppred) and shortest path distances (spdist).
4. Create an instance of Algorithm, an run the FlowDeviation method, passing it the Graph data structure, the shortest path / traffic requirement matrices and the message length value as parameters.
Code sample of example usage as shown:
#include "Algorithm.h"
#include "ShortestPathTree.h"
#include "Matrix.h"
#include <iostream>
#include <fstream>
#include <vector>
#include <stdlib.h>
int main()
{
Edge* edges[] = { new Edge( 0, 1, 0.0, 0.0, 0.0, 2.0, 2.0 ),
new Edge( 1, 0, 0.0, 0.0, 0.0, 2.0, 2.0 ),
new Edge( 1, 2, 0.0, 0.0, 0.0, 2.0, 2.0 ),
new Edge( 2, 1, 0.0, 0.0, 0.0, 2.0, 2.0 ),
new Edge( 0, 2, 0.0, 0.0, 0.0, 2.0, 2.0 ),
new Edge( 2, 0, 0.0, 0.0, 0.0, 2.0, 2.0 ) };
int no_edges = sizeof( edges ) / sizeof( edges[ 0 ] );
std::vector<Edge*> v_edges( edges, edges + no_edges );
// Number of network nodes
const int nn = 3;
// Create graph from interconnections given
Graph<Edge> graph( nn, true, v_edges );
// Initialize requirements, shortest path matrices
Req req( nn, nn );
req( 0, 1 ) = 2;
req( 1, 2 ) = 3;
SPdist spdist( nn, nn );
SPpred sppred( nn, nn );
// Apply flow deviation algorithm
Algorithm algorithm;
algorithm.FlowDeviation( &graph, spdist, sppred, req, 1 );
return 0;
}
Computational Results
The following graph show the progress of the Flow Deviation Algorithm in the form of average delay in seconds versus the iteration.
In this simple experiment the algorithm converged to a delay value of 3.43 seconds in 43 iterations, the same as that described by Kershenbaum. (The values of EPSILON and DELTA used in the example were 0.001 and 0.05 respectively.)
The following console output shows the value of incremental delay on each of the six links, plus the average delay, taken over each of the 43 iterations:
Download source code
Download the Visual Studio 2010 project and code. Upon payment you should be promptly directed to a download link. Please contact me if you experience any problems and I will get it sent to you as soon as possible.
