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