Skip to main content

SAFAR: Simulated Annealing-based Optimal Flow Allocation in Industrial Networks

Given a network (a set of nodes) and a set of traffic flows, a network flow allocation assigns network paths to these flows, so that data (for example, packets) can be sent from the respective source nodes to the corresponding destination nodes. In case of optimal network flow allocation, certain criteria, such as latency and utilization, need to be optimized. Moreover, in case of integral network flow allocation, all packets from a source node to a given destination node must travel via a single path or none at all. In other words, such a flow cannot be “split” across multiple paths.

Overview of SAFAR

Optimal network flow allocation is a computationally hard problem, which not only requires a long time to solve, but also high level of skills. The problem becomes further challenging when unique business and industrial requirements are considered.

In our recent work, we investigated this problem in the context of power grid networks, where the flows often require delay-symmetric upstream and downstream paths. We designed Simulated Annealing-based Flow Allocation Rules (SAFAR), which uses Simulated Annealing to solve the hard optimization problem, while maintaining a level of fairness in flow allocation. As shown in Figure 1, SAFAR essentially is a set of algorithms that:

  • identify optimal paths for the feasible flows
  • allocate bandwidth slices to the infeasible flows, and 
  • install the relevant flow rules. 

A feasible flow is one where the sum of bandwidth requirements of the flows passing through a link does not exceed the physical bandwidth available to the link.

Our study, based on real-life networks, reveals that SAFAR can allocate up to 99% flows by meeting the various constraints. In addition, SAFAR also allocates bandwidth slices to the remainder of the flows. This is done while ensuring that a fraction of the link bandwidth is kept unused, which, for example, can help to accommodate future flows. Finally, SAFAR generates all the flow rules to be installed at the switches, which can be used by a network manager. We verified this behavior using a set of Open vSwitch switches. In other words, SAFAR provides a one-stop solution to enable end-to-end optimal flow allocation in industrial networks.

SAFAR, in general, is technology-agnostic and therefore, can be used with any network regardless of the link technology; the final step of flow rules allocation needs to be adapted accordingly. SAFAR can be used with greenfield networks, where all the network services are pre-configured. Moreover, SAFAR can be used with brownfield networks as well, for example, to configure a new set of services. Finally, SAFAR can also be used in conjunction with Intent-based Networks for network management.

For further details, check out the following paper:

B. K. Saha, L. Haab, and Ł. Podleski, “SAFAR: Simulated Annealing-based Flow Allocation Rules for Industrial Networks,” in IEEE Transactions on Network and Service Management, 2020, DOI: 10.1109/TNSM.2020.3035792.

The full-text of SAFAR is also available (only for personal use.)


Popular posts from this blog

Text Highlighting in Latex

While preparing a manuscript with Latex, it is often useful to highlight the changes made in the current revision with a different color. This can be achieved using the \ textcolor command provided by Latex. For example, \textcolor {red}{Hello World} would display the string "Hello World" in red color. However, the final/published copy of the manuscript does not contain any highlighted text. Therefore, if a large volume of changes were made, it becomes tiresome at the end to find and remove all the individual portions of highlighted text. This can be circumvented by defining a utility command to switch highlighting on and off as desired. In the following, we define a new Latex command, highlighttext , for this purpose. The command takes only a single argument—the text to be highlighted.     \usepackage {color}    % For highlighting changes in this version with red color   \newcommand { \highlighttext }[1] { \textcolor {red}{#1}}   % Remove all text highlighting

Commonly Used Metrics for Performance Evaluation

The following metrics are commonly used when evaluating scenarios related to DTN protocols. Delivery ratio of the messages, Average message delivery latency Overhead ratio (of the underlying routing mechanism) Suppose that $M$ be the set of all messages created in the network and $M_d$ be the set of all messages delivered. Then, the delivery ratio is computed as $|M_d| / |M|$. Now let the $i^{th}$ delivered message was created at time $c_i$ and delivered at time $d_i$. Then the average message delivery latency is computed as $(\sum_{i = 1}^{|M_d|} (d_i - c_i)) / |M_d|$. Note that, in Statistics, mean, median and mode are all the measures of average. But "loosely speaking", unless otherwise specified, we refer to the "mean" value when we say "average." Nevertheless, the MessageStatsReport in the ONE simulator provides a measure of both the mean and median values wherever appropriate. One may refer the above metric as "end-to-end delay.

The ONE KB has a new home

The ONE Knowledge Base is now hosted at If you are unaware, the ONE KB allows you to search the old email archives of the simulator's community. Therefore, if you have any question related to simulation, you may query the existing database at the above link. Chances are good that your question might already have been answered previously. If not, you can still post an email to the community's mailing list. Have you tried the ONE KB already? How was your experience? Was it helpful? Let me know in the comments!