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.)

Comments

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

The ONE KB has a new home

The ONE Knowledge Base is now hosted at http://theonekb.pythonanywhere.com/ 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!

SeeR: Simulated Annealing-based Routing in Opportunistic Mobile Networks

Conceptual architecture of SeeR Opportunistic Mobile Networks (OMNs) are characterized by intermittent connectivity among nodes. In many scenarios, the nodes attempt at local decision making based on greedy approaches, which can result in getting trapped at local optimum. Moreover, for efficient routing, the nodes often collect and exchange lot of information about others. To alleviate such issues, we present SeeR, a simulated annealing-based routing protocol for OMNs. In SeeR, each message is associated with a cost function, which is evaluated by considering its current hop-count and the average aggregated inter-contact time of the node. A node replicates a message to another node, when the latter offers a lower cost. Otherwise, the message is replicated with decreasing probability. Moreover, SeeR works based solely upon local observations. In particular, a node does not track information about other nodes, and, therefore, reduces the risk of privacy leaks unlike m