Perhaps I should begin by mentioning that, in every case in which I confronted the problem of designing a benchmark to measure parameters of network flow, I ended up designing customized algorithms and/or software to benchmark the specific problem required to fit the customer's situation, whether it was a computer network, an oil pipeline, a rice paddy irrigation system, etc. That said, there have been popular standardized system-level networking benchmarks such as TPC-C and TPC-D used in decision support or OLTP applications, AIM, NNBB, SPEC. Here I purposely omit many component benchmarks such as Whetstone, Dhrystone etc. because the way in which you formulated the question implies to me that you are interested in benchmarking a whole network flow system.

In responding, it may be helpful to know the application or range of applications with which your study is concerned. I was not sure why you qualified the problem scenario by "flow dependent transit times" and "system optimal flow patterns". In particular I did not encounter any problem of dynamic flow that did not have flow dependent transit times, since parameters such as latency, carrier speed or bandwidth, multiplexing method, propagation delay, transmission time, packet sizes, retransmission due to noise, cloud server utilization if applicable, can be and frequently are variable. As to optimality of flow patterns, it may be helpful to know the criterion of optimality: response time, throughput, cost of productivity, time allotted to complete, or something else. I am hoping that these comments are somewhat helpful and that other respondent(s) can guide you on the issue of comparative benchmark performance.

@ Albert G. Di Canzio

Dear Albert, many thanks for your worthwhile information. I concentrate on some combinatorial optimization problems that are modeled as network flow problems (see the book Ahuja, R., et al. (1993) Network Flows: Theory, Algorithms, and Applications). For example, I am working on the maximum dynamic network flow problem in which the aim is to send as much flow as possible from a source node s to a terminal node t by a horizon time T through a network with limited link capacities; or the quickest flow problem in which the aim is to send a fixed amount of flow D from s to t as fast as possible.

Regarding transit times, network flows are surveyed in the literature in three cases:

1) static flows, where there are no transit times on the links,

2) flows over time with fixed transit times, and

3) flows over time with flow-dependent transit times.

For the 3rd case, good benchmarks exist for equilibrium systems, in which the aim is to achieve a Nash equilibrium, versus the optimum systems (system-optimal flow patterns) in which the key is to optimize some objective functions. To avoid any misconception, I stressed the kind of transit times as well as the kind of system. Moreover, I am interested in analyzing the performance of algorithms in solving the practical applications of the stated problems. I hope this description will clarify the issue.

Regarding OLTP applications, I am not sure whether there exist relevant benchmark problems. I will be grateful if you let me know about the existence of specific benchmark problems for my case.

@ Hossein Alipour

Re: "specific benchmark problems for my case", I have no doubt that you have searched for them outside RG and come up less than satisfied, as I too have been unsatisfied by standard benchmarks on every network development project. Although now I understand much better what your objective is (your case 3 targeting Nash equilibrium) I am unaware of any standard off-the-shelf benchmarks with this target. On the practical side of your question, if I were tasked "to send a fixed amount of flow D from s to t as fast as possible" under the constraints of your project, I would not focus initially on algorithms, but instead design a minimum-distance traversable network topology with maximum feasible carrier speed. Then and only then I would look for or produce an algorithm that segments the transmission into small enough packets to maximize parallelism on the network while fitting the equilibrium constraint of your project. The performance metric looks like simply time rate of completion of flow, which should be easy to measure.

@ Albert G. Di Canzio

Thanks again for your advice. Just one point for more clarification: in case 3, I mentioned that the Nash equilibrium is the key point of equilibrium systems, but my question is about actual examples of optimum systems as described. Therefore, the Nash equilibrium is not my concern.

Yes, I see. Transaction processing has also a constraint on response time. Optimization then takes more of its canonical form: Your goal "as fast as possible" (this refers to network traversal or RTT) becomes the objective, subject to constraints on benchmark performance which are typically transaction response time and an acceptable range of resource utilization, including link utilization. Actual benchmarks known to me that accomplish such optimization are company-proprietary (I have developed some but under non-disclosure contract). I do not know of very similar standard benchmarks but do have a look at TPC to see how close or how well a TPC standard benchmark would fit your application. I look forward to seeing other respondents who might know actual public-domain sample algorithms.