Even if, as we all known, High Performance Computing (HPC) systems can greatly reduce application performance, there is little quantification of congestion on credit-based in- terconnected networks. This paper proposed a method for de- tecting, extracting and characterizing congested regions in the network. The authors have implemented this methodology in a deployable tool, Monet, which can provide such analysis and feedback at runtime. Using Monet, we can character- ize and diagnose the congestion in Blue Waters, the world’s largest 3D torus network. Blue Waters is a 13.3- petaflop su- percomputer at the National Center for Supercomputing Ap- plications. Introduction As we all know that network congestion in High Perfor- mance Computing (HPC) system can greatly degrade per- formance of applications. But there are few ways to quan- tify such congestion on credit-base interconnect networks. In this paper, we present a way to detect, extract and char- acterize congestion regions in networks. We use Monet, a tool that is able to help us to characterize and diagnose con- gestion in Blue Waters, a petaflop supercomputer at the Na- tional Center for Supercomputing Applications. There are two major contributions in this paper. First of all, this pa- per proposes a methodology for quantitative characteriza- tion of congestion in high-speed networks. Secondly, this paper introduced Monet that could employs such method. On Blue Waters, we will use gpcdr ( ?) and Lightweight Distributed Metric Service (LDMS) to monitor framework. These tools can help us to collect data on the network, file system traffic and appliations. We will use a network hotspot extraction and characterization tool that will extract Conges- tion Regions (CRs) at runtime. Also, a diagnosis tool which will determine the reason of the congestion will be used. Common causes include link failures or excessive file sys- tem traffic from applications. The utility of CRs could be shown by helping trigger congestion mitigation responses. This methodology is important because it is very common that HSN are vulnerable to congestion. As shown in Fig- ure 1, CMEs(congestion mitigation events) were triggered 261 times and 29.8% of which did not reduce congestion in the system. Figure 1 shows a situation where the scale and severity of CRs increases after some throttling events. Figure 1: Examples to show the visualization of congestion regions. Figure 2: Examples to show high-speed networks (HSN) are susceptible to high congestion. Our contribution is that we adopted unsupervised algo- rithm to run on AWS ubuntu system. Due to computing power limit, we only extract data in about 1 month frame. Then we experiments (CR size vs CR and CR duration vs CR) and have our own experiments results and analysis. Our results are following the same pattern but CR size and CR duration are much smaller. Related Work High-performance datacenters and clouds (HPC) (Shazeer et al. 2018) are widely used in high-speed interconnect net- works, which used credit-based control algorithm. This ad- vantages of this technique is to support low-latency com- munications, including low per-hop latency, low tail-latency variation and high bisection bandwidth. Significant perfor- mance variation has been observed in production systems running real-world workloads because of the network con- gestion. However, there has been only a little quantification Figure 3: Characterization and diagnosis workflow for interconnection-networks. Figure 4: Colume name and description of the dataset. of congestion on such interconnect networks. Previous works more focused on I/O profiling and per- formance anomaly diagnosis, including Darshan( ?), Bea- con(Yang et al. 2019) and Kaleidoscope(Jha et al. 2019). In addition, these works assumed steady state utiliza- tion/congestion behavior and thus do not address full pro- duction workloads. Different from these works, this pa- per focuses on assessing network congestion in credit- flow based interconnection networks. There are three main questions to solve in this paper. First, how often sys- tem/applications are experiencing congestion? Second, what are the culprits behind congestion? Third, how to avoid and mitigate effects of congestion. To address the congestion problem, some of the previous works (Deveci et al. 2014; Jha et al. 2019) employs indirect measures like messaging rates, network counters from switch. Other methods like (Agelas- tos et al. 2014; Bhatele et al. 2015) use the global network counter data. Recently, some approaches are tuned for TCP/IP net- works and this paper is complementary to these efforts. For example, ExpressPass(Cho, Jang, and Han 2017), DC- QCN(Zhu et al. 2015a) and TIMELY(Mittal et al. 2015) fo- cus on preventing and mitigating congestion. Other works like PathDump(Tammana, Agarwal, and Lee 2016; Liu et al. 2023; Liu, Tan, and Tensmeyer 2023), Switch- Pointer(Tammana, Agarwal, and Lee 2018; Liu et al. 2020a,b) and EverFlow(Zhu et al. 2015b; Li et al. 2023) pay more attention to network monitoring. Figure 5: Mechanism behind the Percent Time Stalled. Proposed Method Comparing with Darshan (Yang et al. 2019; Liu, Yacoob, and Shrivastava 2023), Beacon (Yang et al. 2019) and Kalei- doscope (Jha et al. 2019), this paper used credit-based net- work to assess and reduce workload instead of I/O profil- ing and performance anomaly diagnosis. Then comparing to (Deveci et al. 2014; Liu et al. 2020a; Agelastos et al. 2014; Liu et al. 2023; Liu, Tan, and Tensmeyer 2023), this paper is the first one that is the characterization of high-speed in- terconnect network congestion of a large- scale production system, where network resources are shared by nodes across disparate job allocations, using global network counters. An- other advantage is that this paper employs direct measure- ment to address the congestion instead of presenting only representative examples of congestion through time or ex- ecuted a single application on the system. Comparing with (Yang et al. 2019; Fu et al. 2016), this paper involves the generation and characterization of congestion regions, diag- nosis of congestion causes. In the following parts, we will first introduce the workflow of our algorithm. After that, we will describe the way we used to measure the congestion or severity level. Then we will talk a little bit reasons why we choose the congestion algorithm. Finally, we will discuss the Figure 6: Credit-based flow control network. Figure 7: How to calculate Percent Time Stalled ( PTS). detailed segmentation algorithm. Workflow The workflow of our model is described in Figure 3. After the step: system description and data collection, we will go to the main part of the our implementation, which is the core task for us. The initial step for us is to use unsupervised al- gorithm to extract Congestion Region (CR). In details, we use the segmentation algorithm to segment the network into groups of links with similar congestion values. After that, we will implement the characterization operation to classify the congestion categories. Finally, we will use cases to check Congestion response and try to find mitigation methods. At the same time, Finding diagnosing causes of congestion is also our target. The first step of our workflow is the intro- duction of the dataset. The dataset here we used is the Blue Water Network, which is a 3-D topology instead of the 2- D topology graph. After getting the data, then unsupervised learning algorithm will be used to extract the congestion re- gion. The third step is the analyze the results from the con- gestion regions. The congestion size and congestion dura- tion are the main two aspects we will use to measure the congestion. Finally, we will also try to find the root causes behind the congestion. Our target mainly includes the fol- lowing three questions: How often system/applications are experiencing congestion? What are the culprits behind con- gestion? How to avoid and mitigate effects of congestion? Percent Time Stalled In the previous sections, we talked a lot about the congestion definitions, effects and causes, but how to measure the con- gestion level or severity is still not mentioned. In the section, we will specifically talk about the measurement method: Percent Time Stalled ( PTS). Figure 5 describes the behind mechanism of how con- gestion happens. In the figure, the red section means the flit waiting (no credit available allocated buffer full) since our data spreading mechanism depends on credit-based flow control network. If credit is 0, no flit will be sent, which is described in Figure 6. The insight of Figure 6 is congestionspreads locally (i.e., fans out from an origin point to other senders). The ways to calculate Percent Time Stalled ( PTS) is described in Figure 7. Timeans the network cycles in ith measurement interval meanwhile the Ti smeans the total cy- cles the link was stalled in Ti. In Figure 5, the value of Ti s is 5 and the value of Tiis 12. In this case, the Percent Time Stalled value is 0.42. Apart from the Percent Time Stalled, we also assign 4 congestion or severity level in order to measure, understand and compare the extent of congestion. Specifically, we as- sign 0-5 percent average PTSin a CR as Negligible or ‘Neg’, 5-15 percent as ‘Low’, 15-25 percent as ‘Medium’, and ¿25 percent as ‘High’. We will then use these levels in characterizations in the following parts of this work. More accurate determinations of impact could be used in place of these in the future, without changing the validity of the CR extraction technique. Why Congestion Regions? In this section, we will describe the reasons why it’s neces- sary to used congestion regions to analyze the severity level. There are mainly two reasons. First, characterizing hotspot links individually do not reveal regions of conges- tion. This is simply because the hotspot links are useful to understand the severity level at the link level. However, they are possible to hide the spatial features of congestion includ- ing the existence of multiple pockets of congestion and their spread and growth overtime. If we lack this kind of informa- tion, it will make it difficult to understand congestion char- acteristics and their root cause in the future. Second reason is that CRs captures relationship between congestion-level and application slowdown efficiently. As shown in Figure 8b, execution time increases with increas- ing maximum of average PTSover all regions by using con- gestion regions. Without using congestion regions, the cor- relation value is only 0.33 in Figure 8a, which is much less than the correlation value 0.89 in Figure 8b.This is a moti- vating factor for the extraction of such congestion regions as indicators of ‘hot-spots’ in the network. Segmentation Algorithm Then the details of the cluster is described below. Before that, we have some parameters: network graph, congestion measures value, neighbor distance metric and the stall simi- larity. This algorithm of segmentation includes four phrases in sequence. First of all, we first group the close links which have the very similar stall values within the threshold. Sec- ond, the nearby regions with similar average stall values, are grouped together through repetition of the previous step. Fi- nally the congestion regions that are below the size threshold are merged into the nearest region within the distance thresh- old. We also have the following assumptions: the congestion runs locally and the link stall values are stable in the same congestion regions. The detailed steps are includes 4 steps. First, the close links will be grouped or classified into the same categories if they meet the following requirements. For example, there are two links xandy. If the distance between the two ver- tices are below the threshold δmeanwhile the stall values Figure 8: Why choose congestion regions? between the two are below the threshold θp, they can be put into the same class. Then as for the second step, if the close regions have the similar stalled values and they are close to each other. The stalled values here we used are the average values between the stalled value of the links in this region. Then if the congestion regions that are below the size thresh- old and the distance is also within the threshold, they will be merged into one group. Then finally, if the left small con- gestion regions will be discarded since they are too small to analyze. Dataset We downloaded and analyzed the dataset, the Blue Wa- ters Network Dataset, which contains collected and aggre- gated network information from NCSA’s Blue Water sys- tem, which is comprised of 27648 nodes connected via Cray Germini 3D torus (dimension 24x24x24) interconnect, from Jan/01/2017 to May/31/2017. All LDMS/OVIS data is stored in Comma Separated Values (CSV) format. Each file name follows the format YYYYMMDD where YYYY , MM and DD is the year, month and date when the data was col- lected. The column name and description shows in the figure 4. Since the size of the source dataset is too large 140G, we only include the sample data in the final submission. The location of the original dataset is this link. Experiment Evaluation As described in the paper (Fu et al. 2016), there are three steps for diagnosis. First of all, Mining candidate congestion-causing factors. For each CR, identified at time T, we create two tables A and F. Each row in table A corre- sponds to an application that is within Nhops ¡ 3 hops away from the bounding box of the congestion region CR. Table A has characteristics across 7 traffic features such as appli- cation name, maximum read bytes per minute and so on. Each row in table F corresponds to an application that is within Nhops ¡= 3 away from the congestion boundary of CR. For table F, it contains information about failures events across 3 failure features such as failure timestamp, failurelocation and failure type. Secondly, identifying anomalous or extreme factors. Next, we will identify extreme applica- tion traffic characteristics or network-related failures over the past 30-mins. The last step is to generate evidence in order to decide whether anomalous factors are really respon- sible for the congestion observed in the network. Implementation We are implementing a hotspot extraction and characeter- ization tool which will enable us to extract and visualize Congestion Regions at run time. The tool will be realiz- ing the unsupervised region-growth clustering algorithm as mentioned in the paper (Jha et al. 2019). This clustering ap- proach requires us to have specification of congestion met- rics such as percent time stalled and stall-to-flit-ratios. Also, a network topology graph is needed for us to extract re- gions of congestion which can be used for network char- acterization if time permits. Moreover, we will find a con- gestion vizualization tool to display the congestion regions. So far, we decided to build our tool based on the region growth segmentation algorithm in open-source PointCloud Library(PCL). However, there were some challenges. For example, we tried to ran PCL on several operation systems but they all encounter different kinds of errors such as the index-pack error shown in Figure 11 when running on Mac OS and the c++ compiler error shown in Figure 12 when running on Centos system. Finally, we found we success- fully installed PCL docker and implement our tool on an AWS EC2 instance with Ubuntu 18.04 operation system. Results Due to computing power and time limit, we are not able to simulate the whole Blue Water network. Instead, we ex- tracted part of the data collected within only one month. We re-experimented two experiments in the paper(Jha et al. 2020). The first one is recording the relationship between size of congestion region and the number of congested links. The second one is recording the relationship between con- gestion duration and the number of congestion regions. Ac- cording to the paper, we use run time as estimate for dif- ferent kinds of severity levels because they can be easily calculated and are handy for us to compare. In our exper- iments, we assign 0-5 percent of 400 min as ’Low’, 15-18 percent as ’Medium’ and ’High’ when the run time exceed 25 percent of 400 min. As shown in figure 13, our results are showing that our average duration for Low is about 300 mins. The average for Med is about 400 mins and the aver- age for high is about 150 mins. Also, as shown in figure 15, compared to the results from authors, our results are show- ing the same pattern which is that the longer CR duration the more congested regions can be detected and this pattern is the same for all severity. We also noticed that low sever- ity happened the most frequent as more than 50,000 linked can be detected in just 100 mins. However, the low sever- ity line also drop very rapidly as time go on. Compared to low severity, medium severity is more stable as time go on as the range of the largest number of congested regions de- tected and the least of congested regions detected is about Figure 9: Segmentation algorithm behind congestion regions, where x,y are vertices in the graph, δ,θpare the thresholds of the distance and stall values Figure 10: screenshot when compiling on Mac OS Figure 11: screenshot when compiling on Centos OS only 17,000. However, we also found something in our re- sults very different from those of authors. As shown in fig- ure 15, all Low, Med and High severity are very fast within first 100 mins. But ours does not show such drastic decline. We believe this situation is caused by small size of data and shorter of running time. For another experiment about CR size, we also have similar pattern with the results from the authors as shown in figure 16. Still, most of the congested links are spreading in low severity CRs and high severity has the least. We can also see the figure 17 that all severity lines are decline as congestion size increase, which means there are not many large size CRs. Low severity CR is very stable as its number of congested regions do not decrease much as CR size increases. However, both medium and low severity are decreasing dramatically along with increasing CR size. we also noticed that low and medium severity lines are basi- cally overlapping under the size of 350 and the reason could be high and medium severity congestion both happen with Figure 12: CR sizes in terms of the number of links for each congested state from our results the same frequency under this size. Another point worthy mentioning is that after separating at size of 350, the two lines end up with similar congestion region numbers, which proves that high and medium severity congestion region are very similar to each other in a certain size. Another thing worth to be noted is that compared to the results from the authors, we found our results do not show 0 congested re- gion situation. But we can see that the number of CRs drop to 0 for all severity when CR size reaches 2048 links. We believe the reason is due to our limited CR size in our net- work. Diagnosis The authors showed three congestion scenarios: (a) system issues (e.g. changes in system load), (b) network-component failures (e.g. link failures), and (c) intra-application con- tention. (a) Network congestion may result from contention be- tween different applications for the same network resources. That can occur because of a change in system load (e.g. launches of new applications) or change in application traffic that increases contention on shared links between applica- tions. (b) Network-related failures are frequent and may lead to network congestion, depending on the traffic on the net- work and the type of failure. Failures of directional links or Figure 13: CR sizes in terms of the number of links for each congested state from our results Figure 14: CR sizes in terms of the number of links for each congested state from authors’ results routers generally lead to occurrences of ‘High’ CRs, while isolated failures of a few switch links (which are much more frequent) generally do not lead to occurrences of significant CRs. (c) Congestion within an application’s geometry (intra- application contention) can occur even with TAS. Intra- application contention is less likely to elevate to cause global network issue, unless the links are involved in global (e.g., I/O) routes, or if the resulting congestion is heavy enough to trigger the system-wide mitigation mechanism. For each cause, system managers could trigger one of the following actions to reduce/manage congestion. In the case of intra- application congestion, an automated MPI rank remapping tool such as TopoMapping [46], could be used to change traffic flow bandwidth on links to reduce congestion on them. In the case of inter-application congestion (caused by system issues or network failures), a node-allocation policy (e.g., TAS) could use knowledge of congested regions to re- duce the impact of congestion on applications. Finally, if ex- ecution of an application frequently causes inter-application congestion, then the application should be re-engineered to limit chances of congestion. How do we divide these congestion causes in order to help draw a system manager’s attention to anomalous scenarios and potential offenders for further analysis? The authors pre- sented a methodology which combine system information Figure 15: CR sizes in terms of the number of links for each congested state from our results Figure 16: CR sizes in terms of the number of links for each congested state from our results with the CR-characterizations to help diagnose causes of significant congestion. Factors include applications that in- ject more traffic than can be ejected into the targets or than the traversed links can transfer, either via communication patterns (e.g., all-to-all or many-to-one) or I/O traffic, and link failures. These can typically be identified by observa- tion of anomalies in the data.The first step is mining candi- date congestion-causing factors. The second step is identi- fying extreme application traffic characteristics or network- related failures over the past 30 minutes that have led to the occurrence of CRs.The last step is generating evidence for determining whether anomalous factors identified in the pre- vious step are truly responsible for the observed congestion in the CR. The evidence is provided in the form of a statis- tical correlation taken over the most recent 30 measurement time-windows between the moving average stall value of the links and the numerical traffic feature(s) obtained from the data (e.g., RDMA read bytes per minute of the application) associated with the anomalous factor(s). Conclusion and Future Work In this paper, the authors presented methodologies for de- tecting, characterizing, and diagnosing network congestion. It implemented these capabilities and demonstrated them us- ing production data from NCSA’s 27,648 node, Cray Gemini based, Blue Waters system. While they utilized the scale and data availability of the Blue Waters system to validate the approach, the methodologies presented are generally appli- cable to other credit-based k-dimensional meshes or toroidal Figure 17: CR sizes in terms of the number of links for each congested state from authors’ results networks. The future work will involve extending the presented techniques to other network technologies and topology. Ac- cording to our process now, we have the following future plans. First, we will solve the required package problem by working with the original authors together. Second, we will experiment the model on the dataset with different time peri- ods since the total amount of the data is too large. Third, we will write the code to achieve the visualization of the char- acterizations of the congestion regions. Finally, we plan to automate the congestion region characterization, diagnosis and visualization since the current version of Monet is not totally automated.