Two Rerouting-Based Congestion Control Algorithms for Centrally-Managed Flow-Oriented Networks
Online Appendix

The main goal of this scenario was to verify the performance of the proposed algorithms in the case of a different network topology. In the following figure, the Viatel backbone network topology is presented. Note that compared to the US backbone network considered in our paper, the Viatel network contains significantly less cycles and the majority of its nodes have degree equal to 2. This means that in the event of a network congestion, the number of alternative paths is much smaller and it is more difficult to mitigate the congestion.

The simulation parameters were as follows:

• Network topology: Viatel (88 nodes, 184 links);
• Link capacity: 1 Gbit/s;
• Relative overload threshold: 0.7;
• Link congestion monitoring interval: 10 s;
• Link overload probability estimated based on 100 most recent samples stored in a circular buffer;
• Number of traffic flows: 10000 (source and destination nodes selected at random according to a uniform distribution);
• Demand of flows: selected at random from range [7.5; 12.5] Mbit/s (uniform distribution), average 10 Mbit/s;
• Duration of flows: average 120 s, Pareto distribution, upper bound 240 s, shape 1.5;
• Flow inter-arrival time: average 0.1 s, exponential distribution, upper bound 0.2 s;
• The average values were computed over the period from the 150th to the 650th second of each simulation to avoid the warm-up and termination phases;
• Number of simulation trials: 10.

The following figure presents the corresponding evaluation results. The fraction of overloaded links was higher (for all the considered solutions) than in the case of the US backbone network, and both proposed algorithms maintained more links in the overloaded state than the reference strategies. At the same time, in terms of the average capacity utilization of overloaded links and the average fraction of fully loaded links, it may be observed that Algorithm I (Max Path Load and Path Overload Probability) performed significantly better than Algorithm II (Max Path Load and Path Length) and the considered reference mechanisms. This observation is related to the fact that with increasing number of congested links, the probability that the candidate path is overloaded becomes an important factor when selecting an alternative path. Thus, in highly congested networks, we would recommend that Algorithm I be used to reallocate traffic flows.

To provide more information about the performance of the proposed solutions, we have analyzed the case when some traffic flows have significantly higher average throughput than the other flows. The simulation parameters were as follows:

• Network topology: US backbone (39 nodes, 122 links);
• Link capacity: 1 Gbit/s;
• Relative overload threshold: 0.7;
• Link congestion monitoring interval: 10 s;
• Link overload probability estimated based on 100 most recent samples stored in a circular buffer;
• Number of traffic flows: 10000 (source and destination nodes selected at random according to a uniform distribution);
• Probability that a new flow is a large flow: 0.05;
• Demand of large flows: selected at random from range [75; 125] Mbit/s (uniform distribution), average 100 Mbit/s;
• Demand of other flows: selected at random from range [7.5; 12.5] Mbit/s (uniform distribution), average 10 Mbit/s;
• Duration of large flows: average 300 s, Pareto distribution, upper bound 600 s, shape 1.5;
• Duration of other flows: average 120 s, Pareto distribution, upper bound 240 s, shape 1.5;
• Flow inter-arrival time: average 0.1 s, exponential distribution, upper bound 0.2 s;
• The average values were computed over the period from the 150th to the 650th second of each simulation to avoid the warm-up and termination phases;
• Number of simulation trials: 10.

The corresponding evaluation results are presented in the figure below. Again, the two proposed flow reallocation strategies caused relatively more links to enter the overloaded state, compared to the other algorithms and the OSPF-like routing with no additional congestion avoidance measures. However, the average capacity utilization of such links in the case of Algorithm I was considerably smaller than for the considered reference strategies, which is a strong advantage. Even more important are the results related to the average fraction of fully loaded links (c) — it was possible to noticeably reduce the number of fully loaded links using Algorithm I, while Algorithm II demonstrated slightly worse performance than the best considered reference solution. It was an expected behavior, as Algorithm I was identified to perform better in more congested networks (see the first section of the Appendix).

If you use any of the figures, results, or other information provided in this Online Appendix, please reference the corresponding journal paper in your work:

BibTeX EndNote