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

Labels:

Comments

Post a Comment

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
1 comment
Read more

Specifying Source and Destination of Messages

One of the frequently asked questions in the community is how to specify which particular nodes would act as source(s) and destination(s) of the messages created in the ONE simulator. The simulator, in fact, provides a pair of settings (shown below in bold face) aimed for this particular purpose. Let us consider that there are $n + 1$ nodes in an OMN.  Further, let the nodes with addresses from $x$ to $y$, both inclusive, would create messages. The nodes in the range $w$ to $z$, both inclusive, would be the destinations of those messages, where $0 \le x \le y \le n$, and $0 \le w \le z \le n$. Then, the corresponding simulation scenario can be configured as follows. ## Message creation parameters # How many event generators Events.nrof = 1 # Class of the first event generator Events1.class = MessageEventGenerator # (Following settings are specific for the MessageEventGenerator class) # Creation interval in seconds (one new message every 25 to 35 seconds) Events1.interval = 25
19 comments
Read more

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!
8 comments
Read more