# SOS-1K: A Fine-grained Suicide Risk Classification Dataset for Chinese
Social Media Analysis

Hongzhi Qi1, Hanfei Liu1, Jianqiang Li1, Qing Zhao1, Wei Zhai1, Dan Luo2,
Tian Yu He2, Shuo Liu2, Bing Xiang Yang2 and Guanghui Fu*3 *This work was
supported by grants from the National Natural Science Foundation of China
(grant numbers:72174152, 72304212 and 82071546), Fundamental Research Funds
for the Central Universities (grant numbers: 2042022kf1218; 2042022kf1037),
the Young Top-notch Talent Cultivation Program of Hubei Province.
Corresponding author: Guanghui Fu (guanghui.fu@inria.fr)1School of Software
Engineering, Beijing University of Technology, Beijing, China2School of
Nursing, Wuhan University, Wuhan, China3Sorbonne Université, Institut du
Cerveau - Paris Brain Institute - ICM, CNRS, Inria, Inserm, AP-HP, Hôpital de
la Pitié Salpêtrière, Paris, France

###### Abstract

In the social media, users frequently express personal emotions, a subset of
which may indicate potential suicidal tendencies. The implicit and varied
forms of expression in internet language complicate accurate and rapid
identification of suicidal intent on social media, thus creating challenges
for timely intervention efforts. The development of deep learning models for
suicide risk detection is a promising solution, but there is a notable lack of
relevant datasets, especially in the Chinese context. To address this gap,
this study presents a Chinese social media dataset designed for fine-grained
suicide risk classification, focusing on indicators such as expressions of
suicide intent, methods of suicide, and urgency of timing. Seven Pre-trained
models were evaluated in two tasks: high and low suicide risk, and fine-
grained suicide risk classification on a level of 0 to 10. In our experiments,
deep learning models show good performance in distinguishing between high and
low suicide risk, with the best model achieving an F1 score of 88.39%.
However, the results for fine-grained suicide risk classification were still
unsatisfactory, with an weighted F1 score of 50.89%. To address the issues of
data imbalance and limited dataset size, we investigated both traditional and
advanced, large language model based data augmentation techniques,
demonstrating that data augmentation can enhance model performance by up to
4.65% points in F1-score. Notably, the Chinese MentalBERT model, which was
pre-trained on psychological domain data, shows superior performance in both
tasks. This study provides valuable insights for automatic identification of
suicidal individuals, facilitating timely psychological intervention on social
media platforms. The source code and data are publicly available at:
https://github.com/HongzhiQ/FineGrainedSuicideDetection.

##  I Introduction

Mental health disorders have emerged as a significant public health challenge
worldwide. A report from the World Health Organization (WHO) indicates that
one in eight individuals globally suffers from mental disorders [1]. Severe
mental illnesses often precipitate suicidal behaviors. With the advent of the
internet, social media platforms have risen rapidly, becoming a refuge for
many patients who share their distress and seek emotional support [2]. On
these platforms, a significant number of users express their existential pain
under specific topics, with some even disclosing suicidal tendencies [3].
Monitoring mental health through social media content enables early diagnosis
before the deterioration of a user’s psychological state, thus potentially
averting the occurrence of suicide [4]. In China, the Tree Hole Rescue Group
harnessed AI to detect potential online suicide cases, successfully
intervening in 3,629 instances with the assistance of 600 volunteers [4, 5].
Given the high volume of posts on social media, manual review methods often
fail to monitor and assess the vast amount of data in time, posing a
significant challenge to the timely intervention of emergencies such as
suicide, and hence there is an urgent need for an accurate and efficient
automated identification method.

Deep learning methods presents a promising avenue for addressing this
challenge [6]. While existing studies achieve good classification results, the
granularity of the classification is relatively coarse [7, 8, 9]. To address
this issue, Wang et al. [10] proposed a deep evaluation model based on
knowledge-perception that integrates the prediction results based on a suicide
dictionary with those from the BERT model, ultimately achieving a F1 score of
54% on a time-based 10-category dataset. However, this method requires the
construction of a large, specialized suicide dictionary, a process that is
time-consuming and labor-intensive, and prone to the out-of-vocabulary
problem. Furthermore, classification tasks also face the issue of class
imbalance, for which data augmentation is an effective solution [11]. Yet, the
specific methods that effectively enhance model performance require further
investigation [12].

The advent of large language models (LLMs) has further accelerated
technological transformation in the field of mental health [13, 14, 15].
Numerous studies are dedicated to leveraging LLMs for interventions in
psychological issues [16, 17, 18, 19]. Qi et al. [20] conducted experiments
comparing the performance of LLMs and supervised learning models on mental
health tasks in Chinese social media, with a focus on the identification of
cognitive distortions and the prediction of high and low suicide risk.
However, the experimental results indicated that LLMs still lag behind
supervised learning methods in terms of effectiveness in mental health tasks.
This suggests that supervised learning approaches remain the preferred
solution for addressing mental health challenges.

To address this gap, we introduce a new dataset name as SOS-1K, which contains
suicide-related data collected from Chinese social media platforms. This
dataset has been classified into 11 levels based on factors such as the
expression of existential pain, the intensity of suicidal intention, methods
of suicide, and the definiteness and urgency of suicide plans, encompassing a
total of 1249 entries. Additionally, we simplified the fine-grained
classification task into a binary high-low risk classification to meet
different practical needs.

In this study, we evaluated the performance of seven pre-trained models on
both fine-grained and high-low suicide classification tasks using our proposed
dataset. We also explored various data augmentation techniques to address
category imbalance in the fine-grained task, including traditional and LLM
based methods. Utilizing data augmentation for the fine-grained task, the
Chinese MentalBERT [21] model achieving 55.54% in the fine-grained task and
88.39% in the high-low tasks, respectively. The proposed dataset, along with
publicly available models, has potential for detecting suicide-related content
on social media platforms.

##  II Task definition

###  II-A Fine-grained suicide risk classification

Suicide does not occur abrupty and without warning. In fact, most cases follow
certain patterns [22]. Therefore, analyzing and assessing relevant factors can
aid in predicting users’ suicidal behavior and enable timely intervention
[23]. Huang et al. [24] identified five key factors: existential distress,
suicidal intent, suicide plan, method of suicide, and date of suicide. Based
on factors such as the expression of existential distress, the intensity of
suicidal intent, the method of suicide, the certainty of the suicide plan, and
the urgency of time, a 0-10 level suicide risk classification label was
determined. Details of the fine-grained suicide risk classification are
presented in Table I.

TABLE I: The 0-10 suicide risk classification rule defined by Huang et al.
[24]

Level | Description
---|---
level 0 | No expression of existential pain.
level 1 | Existential pain is expressed, with no expression of suicidal desire.
level 2 | Existential pain has been clearly expressed, with no expression of suicidal desire.
level 3 | Strong existential pain, with no expression of suicidal desire.
level 4 | Suicidal desire has been expressed, but the method and plan for suicide are unclear.
level 5 | Strong desire for suicide, with an unclear method of suicide.
level 6 | Planning for suicide has begun, but the method of suicide is unknown.
level 7 | The method of suicide has been determined, but the date of suicide has not.
level 8 | Suicide has been planned, with the date of suicide roughly determined.
level 9 | The method of suicide has been determined, and the person may commit suicide in the near future.
level 10 | Suicide may be ongoing.

###  II-B High-low suicide risk classification

As mentioned above, a fine-grained classification of suicide risk is crucial.
However, for practical applications, simplifying the classification into high
and low risk can be effective. For individuals identified as experiencing a
moderate emotional crisis (categorized as low risk), psychological
interventions can be effectively used to manage and alleviate their emotional
distress. In contrast, individuals classified as high risk require immediate
and specialized crisis intervention strategies due to the urgency of their
situation. Therefore, we classify levels 6 and above as high risk, and levels
1 to 5 as low risk.

##  III Methods

  * •

BERT [25]: Utilizes the Transformer’s [26] encoder and bidirectional
processing to acquire contextual word representations. Its core pre-training
involves the Masked Language Model (MLM), where it predicts randomly hidden
words in a sentence, and Next Sentence Prediction (NSP), assessing if two
sentences are sequential. These tasks collectively refine BERT’s grasp of
complex linguistic nuances.

  * •

RoBERTa [27]: Improves upon BERT by removing the NSP task, using a larger
corpus, and augmenting batch sizes and training steps. It also updates BERT’s
dynamic masking for data variation in each training iteration. These
enhancements boost RoBERTa’s performance in numerous NLP tasks.

  * •

ELECTRA [28]: Introduces replaced token detection mechanism, diverging from
the conventional MLM approach. Instead of predicting masked words, ELECTRA
uses a generator to predict substitutions for “[MASK]” tokens in sentences and
then employs a discriminator to detect these replacements. This method
enhances computational efficiency by utilizing all input words for training,
not just the masked ones.

  * •

MacBERT [29]: Enhances the BERT architecture with a refined MLM task and
curricular learning strategies, incorporating whole word masking for better
suitability with Chinese texts. This advanced MLM task involves predicting
masked words and identifying inaccuracies, catering to complex language
scenarios. These improvements enable MacBERT to outperform BERT in various
natural language processing tasks.

  * •

NeZha [30]: Enhances Transformer [26] models with functional relative position
encoding for long sequences, improving sensitivity to context through long-
distance dependency capture. It includes whole-word masking and mixed-
precision training, achieving superior performance in Chinese language tasks.

  * •

ERNIE 3.0 [31]: Enhances the ERNIE series by combining language understanding
and generation tasks with a heterogeneous knowledge graph for deeper semantic
insights. It uses graph attention for entity and relationship integration and
employs multi-task learning, including traditional MLM and knowledge-driven
tasks, improving domain-specific performance.

  * •

Chinese MentalBERT [21]: A domain-adaptive model for the Chinese mental health
field, utilizing 3.36 million pieces of data, this model employs a lexicon-
guided masking mechanism during the pre-training phase, prioritizing the
masking of keywords related to mental health. It excels in mental health
tasks, effectively capturing psychological nuances.

##  IV Data augmentation

In our study on fine-grained suicide risk classification, we face the
challenge of class imbalance. We employed data augmentation methods to improve
the model’s ability to generalize. We use two traditional data augmentation
methods that proved to be effective [32]: synonym replacement [33] for token-
level augmentation and round-trip translation [34] for sentence-level
augmentation. Additionally, we employed a novel data augmentation method that
utilizes LLM with few-shot training examples as prompts.

###  IV-A Augmentation methods

  * •

Synonym replacement [33]: It is a token-level augmentation method that boosts
the diversity of a corpus by replacing words or phrases with their synonyms.
In our experiment, the TF-IDF algorithm [35] was utilized to identify the
keywords in each text, preserving it while replacing the remaining vocabulary
with synonyms selected from the synonyms Python package [36] based on word
embedding similarity. For each keyword, the top four related synonyms were
chosen to generate four innovative variant texts for every original text.

  * •

Round-trip translation [34]: It is a sentence-level augmentation method used
to create text variations by leveraging translation tools. This method
involves translating a set of original texts from one language to another, and
then translating these texts back to the original language. In our
implementation, we chose English, Spanish, Russian, Arabic, and Japanese as
the languages for translation. We used the Baidu Translation API to facilitate
this process [37] generating five new textual variations for each original
text.

  * •

Data Generation by LLM: We utilized the GPT-4 model [38] with few-shot
prompting: randomly chose six expert-annotated sentences from each category to
serve as few shot training data. The temperature was set to 0.7. We generated
350 candidate data entries for each level and randomly selected them according
to a specific data volume strategy.

###  IV-B Augmentation volumes

To address class imbalance, we used two strategies to ensure that each of the
categories achieves a predefined augmentation volume. Let’s define $L$ as the
total number of categories. For each category $l,N_{l}$ denotes its original
data size. Additionally, $N_{l}^{a}$ represents the target data volume for
category $l$ after applying a specific strategy.

  * •

Maximal category augmentation: To address the problem of inter-class
imbalance, this strategy adjusts the target augmentation volume to match the
size of the largest category. The target volume $N_{l}^{a}$ is:
$N_{l}^{a}=\max_{l=1}^{L}N_{l}$

  * •

Double maximal category augmentation: This strategy doubles the augmentation
volume to test whether increasing the data volume can enhance model
performance by providing a richer and more varied dataset for training.
Specifically, the target augmentation volume for each class is set to $2\times
N_{l}^{a}$.

##  V Experiments

###  V-A Datasets

We obtained data by scraping comments from the “Zoufan” [39] blog on the Weibo
social platform. The initial annotation of the data was conducted using LLM,
followed by a secondary review and annotation by domain experts (B.Y). This
process led to the conduction of the SOcial Media Suicide dataset (SOS-1k),
which contains 1,249 entries. Details of the annotation rule are described in
Section II. The data obtained is publicly available on Weibo, and we remove
all information such as user IDs for anonymization to ensure privacy
protection. Data statistics for the fine-grained and high-low suicide risk
classification tasks in the SOS-1K dataset are shown in Table II. For both
tasks, we use a 4:1 ratio to split the data into training and testing sets.
Additionally, we conduct 5-fold cross-validation to ensure the robustness of
our models.

TABLE II: Distribution of the SOS-1k dataset. $N_{l}$ represents the number of samples at level $l$. $N_{\text{train}}$ and $N_{\text{test}}$ represent the number of data samples in train and test set, respectively. $\overline{W}$ denotes the average word count per sample.  Level $l$ | Risk ($N_{\text{risk}}$) | $N_{l}$
---|---|---
0 | Low (648) | 64
1 | 63
2 | 67
3 | 148
4 | 248
5 | 93
6 | High (601) | 213
7 | 199
8 | 41
9 | 71
10 | 42
$N_{\text{train}}$ = 999; $N_{\text{test}}$ = 250; $N_{\text{total}}=1249$;
$\overline{W}$=47.79

###  V-B Implementation details

This study evaluates the performance of seven pre-trained language models on
two suicide risk classification tasks. To address dataset imbalance in the
fine-grained suicide classification task, weighted average precision, recall,
and F1-score were used as evaluation metrics. For the high-low classification
task, binary averages were employed.

Experiments were conducted utilizing the PyTorch [40] framework. The Adam
optimizer [41] was utilized for training. The learning rate and batch size
vary according to the model and the amount of training data. All text data
were uniformly padded or truncated to 150 tokens for preprocessing. A fully
connected layer with a sigmoid activation function was introduced after the
pre-trained model to serve as a classifier. To prevent overfitting, an early
stopping mechanism was employed; model training will stop if there is no
decrease in loss on the validation set for 30 consecutive epochs. All the
model settings, data and codes are publicly available via:
https://github.com/HongzhiQ/FineGrainedSuicideDetection.

##  VI Results

###  VI-A The performance of suicide risk classification tasks

The performance of the pre-trained models on the fine-grained and high-low
suicide risk classification tasks is shown in Table III.

####  VI-A1 Fine-grained multi-class suicide risk classification

All models failed to achieve high F1 scores, with the top-performing model,
Chinese MentalBERT [21], reaching only 50.89%. This may be due to the task’s
numerous categories and the inherent difficulty in distinguishing between
their respective semantic nuances. The relative outperformance of the Chinese
MentalBERT [21] model compared to other pre-trained models may be due to its
training for domain adaptation on a large corpus of psychology-related social
media content. This specialized training enhanced its ability to understand
and process the specific language and contexts of this field. Note that, the
MacBERT [29] closely follows, trailing by just 0.3% points in F1-score for
this task.

####  VI-A2 High-low suicide risk binary classification

The experimental results demonstrate that all models performed well in this
task, with F1-scores exceeding 80%. Notably, the Chinese MentalBERT [21] model
excelled, achieving an F1 score of 88.39%. In this task, the advantage of
Chinese MentalBERT over MacBERT[29] is evident, achieving an F1-score that is
4.8% points higher.

From these two tasks, it is apparent that the experimental models perform well
in the high-low suicide classification task, but struggle in the fine-grained
classification task, likely due to category imbalance. Consequently, we
continued to explore various data augmentation strategies to address this
issue.

TABLE III: Performance of seven pre-trained models on two suicide
classification tasks. Precision, recall, and F1-score were reported in
weighted average.

Tasks | Models | Precision | Recall | F1
---|---|---|---|---
Fine-grained | BERT | 48.95% | 50.80% | 46.16%
RoBERTa | 38.03% | 42.80% | 37.11%
ELECTRA | 30.35% | 42.40% | 34.91%
MacBERT | 50.17% | 53.60% | 50.59%
NeZha | 47.61% | 50.40% | 45.72%
ERNIE 3.0 | 47.90% | 51.20% | 47.36%
Chinese MentalBERT | 52.81% | 54.80% | 50.89%
High-low | BERT | 87.68% | 87.60% | 87.61%
RoBERTa | 80.02% | 80.00% | 79.97%
ELECTRA | 81.21% | 81.20% | 81.20%
MacBERT | 83.60% | 83.60% | 83.59%
NeZha | 84.86% | 84.80% | 84.81%
ERNIE 3.0 | 86.42% | 86.40% | 86.39%
Chinese MentalBERT | 88.41% | 88.40% | 88.39%

###  VI-B Model performance after data augmentation

As shown in Table II and Table III, the fine-grained suicide risk
classification task has the challenge of class imbalance, and so we continued
to experiment with several data augmentation methods in an attempt to address
this issue. The model performance after data augmentation are detailed in
Table IV.

TABLE IV: Weighted F1 scores for each model after data augmentation and
comparison to baseline in the fine-grained suicide risk classification task.
Three augmentation strategies are implemented: round-trip translation (RT),
synonym substitution (SR), and LLM generation (LLM-G). The most effective
training strategy for each model is highlighted in bold.

Model | Baseline | RT | SR | LLM | 2$\times$LLM
---|---|---|---|---|---
BERT | 46.16% | 47.05%(+0.89%) | 47.70%(+1.54%) | 48.94%(+2.78%) | 48.49%(+2.33%)
RoBERTa | 37.11% | 38.92%(+1.81%) | 38.10%(+0.99%) | 38.43%(+1.32%) | 41.91%(+4.80%)
ELECTRA | 34.91% | 32.24%(-2.67%) | 35.52%(+0.61%) | 38.15%(+3.24%) | 39.69%(+4.78%)
MacBERT | 50.59% | 47.20%(-3.39%) | 45.01%(-5.58%) | 46.44%(-4.15%) | 48.38%(-2.21%)
NeZha | 45.72% | 46.80%(+1.08%) | 49.66%(+3.94%) | 48.84%(+3.12%) | 48.81%(+3.09%)
ERNIE 3.0 | 47.36% | 48.26%(+0.90%) | 49.44%(+2.08%) | 49.22%(+1.86%) | 51.22%(+3.86%)
Chinese MentalBERT | 50.89% | 55.54%(+4.65%) | 53.46%(+2.57%) | 51.05%(+0.16%) | 53.97%(+3.08%)

From the experimental results we can found that each strategy has its merits
and limitations depending on the model architecture. RT generally shows
positive results, particularly excelling with the Chinese MentalBERT model
where it led to a significant improvement of +4.65%. However, it did not
universally enhance performance, as seen with ELECTRA, where it resulted in a
decrement. SR was notably effective for NeZha, achieving the highest
performance boost of +3.94% for this model, but it caused a substantial
performance decline in MacBERT (-5.58%). This indicates that SR’s
effectiveness is highly contingent on how each model processes semantic
variations. LLM-G provided consistent, moderate improvements across most
models, with the notable exception of MacBERT, reinforcing its reliability but
also highlighting that the magnitude of improvement is generally less dramatic
compared to other strategies. Due to the consistently improving performance of
LLM-G, we continued to employ the double maximal category augmentation
strategy (2$\times$LLM) to investigate the effects of doubling the augmented
data on the model.

When the LLM augmentation volume was doubled, there was a marked improvement
in model performance for models like RoBERTa, ELECTRA, and ERNIE 3.0,
suggesting that a higher volume of LLM-generated data can be beneficial,
particularly for models that already showed positive responses to the initial
LLM-G strategy. For RoBERTa and ELECTRA, the increase in data volume led to
the highest improvements observed (+4.80% and +4.78%, respectively),
indicating that these models may benefit from larger training datasets.
Conversely, NeZha and BERT did not see the best results with this increased
volume, suggesting there may be an optimal point of augmentation that varies
by model. For MacBERT and Chinese MentalBERT, doubling the LLM volume did not
yield improvements that surpassed other strategies, with Chinese MentalBERT
performing best under RT and MacBERT still not reaching its baseline
performance.

The experimental result highlights that while LLM-G offers a reliable base for
performance improvement, increasing the volume of data augmentation with
strategies like 2$\times$LLM can provide benefits for certain models,
especially where initial improvements were promising. However, the varying
effectiveness of RT, SR, and LLM strategies across different models suggests
that data augmentation approaches must be tailored to individual model
architectures and specific tasks to optimize outcomes.

##  VII Discussion

In this study, we employed the GPT-4 to assist in annotating suicide risk
levels. The model encountered several challenges in accurately understanding
the data. First, it struggled to differentiate various levels of severity,
such as distinguishing between the intensity of suicidal ideation and the
degree of existential pain. Additionally, it often misinterpreted narratives
that mentioned potential suicidal actions in the future as indications of a
definite suicide plan. The brevity of the data further complicated the model’s
ability to understand the true semantic meaning of sentences, especially when
it came to internet slang. For instance, phrases like “约死滴滴 (English
translation: Beep, beep, calling for a suicide pact.)”, a type of internet
slang, were sometimes incorrectly assumed to refer to a specific method of
suicide.

In the field of fine-grained suicide risk classification, several challenges
persist, particularly the need to mitigate the subjectivity of annotators.
Additionally, the collection and labeling of large datasets are required to
address issues of data imbalance. While data augmentation techniques have been
effective in enhancing model performance, there remains room for improvement.
One possible solution is to increase semantic diversity or incorporate
internet slang to better reflect the actual language used online. Furthermore,
models need to be trained to detect subtle emotional and semantic cues in
text, thereby enhancing their capability for fine-grained emotional
understanding. In psychology, binary classification tasks are useful for
quickly identifying high-risk individuals. Deep learning models have shown
strong capabilities in robust classification, making them a practical solution
in contemporary settings.

##  VIII Conclusion

This study introduces the SOS-1K dataset, which categorizes suicide risk by
urgency levels. We evaluated seven pre-trained language models on this dataset
for both fine-grained and high-low suicide classification tasks. Given the
class imbalance in fine-grained classification tasks, we explored three data
augmentation methods: synonym replacement, round-trip translation, and data
generation by LLM. The results indicate that data augmentation enhances model
performance, with data generated by LLM generally contributing positively.
Notably, the Chinese MentalBERT model demonstrated superior performance,
achieving a 55.54% weighted F1-score in the fine-grained classification task
and an 88.39% F1-score in the binary high-low suicide risk classification
task. These findings underscore the advantages of domain-specific pre-trained
models. The datasets, source code, and augmented data are publicly accessible.
This research establishes a foundation for future studies and provides
strategies for social media based suicide risk interventions.

## References

  * [1] W. H. Organization _et al._ , “World mental health report: transforming mental health for all,” 2022.
  * [2] B. Keles, N. McCrae, and A. Grealish, “A systematic review: the influence of social media on depression, anxiety and psychological distress in adolescents,” _International journal of adolescence and youth_ , vol. 25, no. 1, pp. 79–93, 2020.
  * [3] P. Chen, Y. Qian, Z. Huang, C. Zhao, Z. Liu, and B. Yang, “Negative emotional characteristics of weibo “tree hole”’ users,” _Zhongguo Xinliweisheng Zazhi_ , vol. 5, pp. 437–444, 2020.
  * [4] B. X. Yang, L. Xia, L. Liu, W. Nie, Q. Liu, X. Y. Li, M. Q. Ao, X. Q. Wang, Y. D. Xie, Z. Liu _et al._ , “A suicide monitoring and crisis intervention strategy based on knowledge graph technology for “tree hole” microblog users in China,” _Frontiers in psychology_ , vol. 12, p. 674481, 2021.
  * [5] Z. Yimeng and L. Kun, “AI gives potential suicides pause for thought,” _China Daily_ , 2020.
  * [6] G. Coppersmith, R. Leary, P. Crutchley, and A. Fine, “Natural language processing of social media as screening for suicide risk,” _Biomedical informatics insights_ , vol. 10, p. 1178222618792860, 2018.
  * [7] G. Fu, C. Song, J. Li, Y. Ma, P. Chen, R. Wang, B. X. Yang, and Z. Huang, “Distant supervision for mental health management in social media: suicide risk classification system development study,” _Journal of medical internet research_ , vol. 23, no. 8, p. e26119, 2021.
  * [8] S. Renjith, A. Abraham, S. B. Jyothi, L. Chandran, and J. Thomson, “An ensemble deep learning technique for detecting suicidal ideation from posts in social media platforms,” _Journal of King Saud University-Computer and Information Sciences_ , vol. 34, no. 10, pp. 9564–9575, 2022.
  * [9] J. Gorai and D. K. Shaw, “A BERT-encoded ensembled CNN model for suicide risk identification in social media posts,” _Neural Computing and Applications_ , pp. 1–16, 2024.
  * [10] R. Wang, B. X. Yang, Y. Ma, P. Wang, Q. Yu, X. Zong, Z. Huang, S. Ma, L. Hu, K. Hwang _et al._ , “Medical-level suicide risk analysis: A novel standard and evaluation model,” _IEEE Internet of Things Journal_ , vol. 8, no. 23, pp. 16 825–16 834, 2021.
  * [11] C. Shorten, T. M. Khoshgoftaar, and B. Furht, “Text data augmentation for deep learning,” _Journal of big Data_ , vol. 8, no. 1, p. 101, 2021.
  * [12] J. Chen, D. Tam, C. Raffel, M. Bansal, and D. Yang, “An Empirical Survey of Data Augmentation for Limited Data Learning in NLP,” _Transactions of the Association for Computational Linguistics_ , vol. 11, pp. 191–211, 03 2023. [Online]. Available: https://doi.org/10.1162/tacl_a_00542
  * [13] W. X. Zhao, K. Zhou, J. Li, T. Tang, X. Wang, Y. Hou, Y. Min, B. Zhang, J. Zhang, Z. Dong _et al._ , “A survey of large language models,” _arXiv preprint arXiv:2303.18223_ , 2023.
  * [14] J. Kaddour, J. Harris, M. Mozes, H. Bradley, R. Raileanu, and R. McHardy, “Challenges and applications of large language models,” _arXiv preprint arXiv:2307.10169_ , 2023.
  * [15] T. He, G. Fu, Y. Yu, F. Wang, J. Li, Q. Zhao, C. Song, H. Qi, D. Luo, H. Zou _et al._ , “Towards a psychological generalist AI: A survey of current applications of large language models and future prospects,” _arXiv preprint arXiv:2312.04578_ , 2023.
  * [16] J. M. Liu, D. Li, H. Cao, T. Ren, Z. Liao, and J. Wu, “Chatcounselor: A large language models for mental health support,” _arXiv preprint arXiv:2309.15461_ , 2023.
  * [17] G. Fu, Q. Zhao, J. Li, D. Luo, C. Song, W. Zhai, S. Liu, F. Wang, Y. Wang, L. Cheng _et al._ , “Enhancing psychological counseling with large language model: A multifaceted decision-support system for non-professionals,” _arXiv preprint arXiv:2308.15192_ , 2023.
  * [18] W. Zhou, L. C. Prater, E. V. Goldstein, S. J. Mooney _et al._ , “Identifying rare circumstances preceding female firearm suicides: validating a large language model approach,” _JMIR mental health_ , vol. 10, no. 1, p. e49359, 2023.
  * [19] J. W. Ayers, A. Poliak, M. Dredze, E. C. Leas, Z. Zhu, J. B. Kelley, D. J. Faix, A. M. Goodman, C. A. Longhurst, M. Hogarth _et al._ , “Comparing physician and artificial intelligence chatbot responses to patient questions posted to a public social media forum,” _JAMA internal medicine_ , vol. 183, no. 6, pp. 589–596, 2023.
  * [20] H. Qi, Q. Zhao, J. Li, C. Song, W. Zhai, L. Dan, S. Liu, Y. J. Yu, F. Wang, H. Zou _et al._ , “Supervised learning and large language model benchmarks on mental health datasets: Cognitive distortions and suicidal risks in chinese social media,” 2023.
  * [21] W. Zhai, H. Qi, Q. Zhao, J. Li, Z. Wang, H. Wang, B. X. Yang, and G. Fu, “Chinese MentalBERT: Domain-adaptive pre-training on social media for chinese mental health text analysis,” _arXiv preprint arXiv:2402.09151_ , 2024.
  * [22] Y. Xiao, K. Bi, P. S.-F. Yip, J. Cerel, T. T. Brown, Y. Peng, J. Pathak, and J. J. Mann, “Decoding suicide decedent profiles and signs of suicidal intent using latent class analysis,” _JAMA psychiatry_ , 2024.
  * [23] P. Cowen, P. Harrison, and T. Burns, _Shorter Oxford textbook of psychiatry_. Oxford University Press, USA, 2012.
  * [24] Z. Huang, Q. Hu, J. Gu, J. Yang, Y. Feng, and G. Wang, “Web-based intelligent agents for suicide monitoring and early warning,” _China Digital Medicine_ , vol. 14, no. 3, pp. 2–6, 2019.
  * [25] J. D. M.-W. C. Kenton and L. K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of naacL-HLT_ , vol. 1, 2019, p. 2.
  * [26] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” _Advances in neural information processing systems_ , vol. 30, 2017.
  * [27] Y. Liu, M. Ott, N. Goyal, J. Du, M. Joshi, D. Chen, O. Levy, M. Lewis, L. Zettlemoyer, and V. Stoyanov, “RoBERTa: A robustly optimized bert pretraining approach,” _arXiv preprint arXiv:1907.11692_ , 2019.
  * [28] K. Clark, M.-T. Luong, Q. V. Le, and C. D. Manning, “ELECTRA: Pre-training text encoders as discriminators rather than generators,” _arXiv preprint arXiv:2003.10555_ , 2020.
  * [29] Y. Cui, W. Che, T. Liu, B. Qin, and Z. Yang, “Pre-training with whole word masking for Chinese BERT,” _IEEE/ACM Transactions on Audio, Speech, and Language Processing_ , vol. 29, pp. 3504–3514, 2021.
  * [30] J. Wei, X. Ren, X. Li, W. Huang, Y. Liao, Y. Wang, J. Lin, X. Jiang, X. Chen, and Q. Liu, “Nezha: Neural contextualized representation for chinese language understanding,” _arXiv preprint arXiv:1909.00204_ , 2019.
  * [31] Y. Sun, S. Wang, S. Feng, S. Ding, C. Pang, J. Shang, J. Liu, X. Chen, Y. Zhao, Y. Lu _et al._ , “ERNIE 3.0: Large-scale knowledge enhanced pre-training for language understanding and generation,” _arXiv preprint arXiv:2107.02137_ , 2021.
  * [32] J. Chen, D. Tam, C. Raffel, M. Bansal, and D. Yang, “An empirical survey of data augmentation for limited data learning in NLP,” _Transactions of the Association for Computational Linguistics_ , vol. 11, pp. 191–211, 2023.
  * [33] O. Kolomiyets, S. Bethard, and M.-F. Moens, “Model-portability experiments for textual temporal analysis,” in _Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies_ , vol. 2. ACL; East Stroudsburg, PA, 2011, pp. 271–276.
  * [34] M. Aiken and M. Park, “The efficacy of round-trip translation for MT evaluation,” _Translation Journal_ , vol. 14, no. 1, pp. 1–10, 2010.
  * [35] G. Salton, A. Wong, and C.-S. Yang, “A vector space model for automatic indexing,” _Communications of the ACM_ , vol. 18, no. 11, pp. 613–620, 1975.
  * [36] H. Y. X. Hai Liang Wang. (2017) Chinese synonym toolkit: Synonyms. [Online]. Available: https://github.com/chatopera/Synonyms
  * [37] Baidu, Inc., “Baidu translate api,” https://api.fanyi.baidu.com/, accessed: 2024-02-21.
  * [38] J. Achiam, S. Adler, S. Agarwal, L. Ahmad, I. Akkaya, F. L. Aleman, D. Almeida, J. Altenschmidt, S. Altman, S. Anadkat _et al._ , “GPT-4 technical report,” _arXiv preprint arXiv:2303.08774_ , 2023.
  * [39] ZouFan, “Sina weibo ”Zoufan” comment,” 2023. [Online]. Available: https://www.weibo.com/xiaofan116?is_all=1
  * [40] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “PyTorch: An imperative style, high-performance deep learning library,” _Advances in neural information processing systems_ , vol. 32, 2019.
  * [41] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” in _3rd International Conference on Learning Representations, ICLR 2015 - Conference Track Proceedings_ , San Diego, CA, USA, 2015.


main.bib

# Measuring time delay in path MTU discovery in transmitting a packet in IPv4
and IPv6 network

Ishfaq Hussain and Janibul Bashir

###### Abstract

Path MTU Discovery (PMTUD) was initially designed for Internet protocol
version 4 (IPv4) to prevent the communication loss due to smaller path MTU.
This protocol is then further developed for Internet protocol version 6 (IPv6)
with new set of constraints. In IPv4 network, the PMTUD activates when the
packets DF bit is set, while as in IPv6, PMTUD is always running for every
packet. In this paper, we analyzed the time consumed to transmit a single
packet from source to destination in IPv6 and IPv4 network in the presence of
PMTUD. Based on our analysis we concluded that the communication time
increases with the varying MTU of the intermediate nodes. Moreover, we
formulated the mathematical model to determine the communication delay in a
network. Our model shows that the asymptotic lower bound for time taken is
$\Omega(n)$ and the asymptotic upper bound is $\Theta(n^{2})$, using path MTU
discovery.

##  1 Introduction

The Path MTU Discovery (PMTUD) protocol was designed for Internet protocol
version 4 (IPv4) [rfc1191, rfc791] with the aim to discover the minimum path
MTU of the path from source to destination. The goal is to reduce the packet
drop frequency in networks. The protocol works for the packets where the don’t
fragment (DF) bit is set or in scenarios where the intermediate nodes are not
allowed to fragment the incoming packets. The protocol make use of ICMP
messages to inform the source about the minimum MTU of the path from the
source to the destination [rfc792].

The ICMP message encapsulates the size of the last node’s forwarding MTU value
along the cause of the packet drop with message as "fragmentation needed and
DF bit set". On reaching this message to the source node it further fragments
the packet and re-transmits it into small chunks of size equal to or lower
then the said MTU value informed by the ICMPv4 message, It keeps on repeating
the process until it reaches to destination [rfc1191].

In case of IPv6 network, the intermediate nodes are not allowed to fragment
the packets [rfc8200]. This decision was carried out mainly for the reason as
the fragmentation is considered harmful [frag] and has many effects on
security and network performance of wired, wireless [wireless] , Internet of
Things (IOT) [IOT] and 6LoWPAN [6152926] networks. As a result, PMTUD protocol
is always active in such networks. The Path MTU discovery v6 uses ICMPv6
message protocol with (Type 2, Code 0) error message as "Packet too Big"
[rfc4443]. On receiving this ICMPv6 packet [rfc4443] it contains the next Path
MTU value of the problem occurred node and the source node regenerates the
same packet of size equal to the informed MTU value in ICMPv6 message and re-
transmits it and this process keeps on repeating until the packet is reached
to destination [rfc8201].

In both the networks, IPv4 and IPv6, Path MTU Discovery results in increase in
time delay if the process of re-transmission keeps on repeating and hence
adversely affects the network throughput as it largely depends on the time
delay. There are many factors for the re-transmission of a single packet
through a network path but most of the common factors are :

  * •

Random and decreasing MTU value of the nodes in the path.

  * •

ICMP message unreachable due to firewall restrictions [firewall], MTU mismatch
[mismatch], routers are configured to not send ICMP destination unreachable
messages, software bugs responsible for PMTUD failures [behave] and PMTUD
Black holes [BB12] cases the source to continuously send packets without
knowing the path MTU after every timeout.

  * •

The change in path MTU value over time due to the change in routing topology
[topology, Ptopology] after every next re-transmission making increased use of
PMTUD algorithm results in time consumption in sending a packet [rfc1191].

The aim of this paper is to analyze time consumption due to re-transmission of
packet in the network concentric only to the first and the last factor and
excluding the middle factor i.e ICMP unreachable, using Path MTU discovery for
both IPv4 and IPv6 networks. We analyzed the best to the worst situation that
could happen using PMTUD in IPv6. The calculations and analysis made for IPv6
can easily be extended to PMTUDv4 in IPv4. The mathematical model proposed can
easily be integrated in any state-of-the-art network simulator to calculate
the effect of PMTUD on various network parameters.

In this paper the time delay due to PMTUD protocol is expressed by a term
"Time Wastage" and is symbolised as ${}^{P}T_{W}$. Thus, "Time Wastage" is
defined as the extra time that has been taken by PMTUD protocol to decrease
the MTU to the minimum MTU of the path.

Contributions: Let us summarize the contributions of this paper:

  * •

We prove that the asymptotic upper bound and lower bound of time wastage in
using Path MTU discovery is $\Theta(n^{2})$ and $\Omega(n)$ respectively, in
IPv6 and IPv4 network with DF=1.

  * •

We calculated the maximum time wastage in sending a single packet with DF bit
set in PMTUD, is of two degree polynomial equation and the minimum time
wastage is one degree polynomial equation.

  * •

We designed a mathematical model to find out the total time wastage in sending
a single packet for different scenarios using PMTUD protocol in IPv6 and IPv4
network with DF=1.

The rest of the treatise is as follows. Section 2 discusses the methods of
calculating total time delay in PMTUD followed by Section 3 where we analyse
the time wastage in PMTUD. The paper concludes in Section 4.

##  2 Method

###  2.1 Measurement on Time Delay in PMTUD

To implement Path MTU Discovery algorithm is really simple, but the use of PTB
messages in form of ICMP error messages made it unreliable in IPv4 and fail
more often in IPv6 network. Many studies has been carried out regarding the
PMTUD failure and its effects on IPv6 protocol but none of these have proposed
or discussed any mathematical methods of calculating or measuring the delay
associated with Path MTU Discovery in a more generalised way. We came across
modeling a new start-of-art protocol and find a real need of such models in
calculating the robustness and performance of our new designed algorithm to
that of the Path MTU discovery, please note that in this paper we are only
discussing the mathematical modeling and analysis of time delay in Path MTU
Discovery, which is the most basic parameter in Internet system to measure the
performance and Quality of the network, network parameters, network equipment
and protocols.

Before going into the analysis we have begin with a case study where we
designed a theoretical network configuration as shown in Figure 1. This
network configuration can be used for both IPv4 and IPv6 packets analysis as
in this study we are analysing the effect of PMTUD in time delay, so both of
them using PMTUD protocol and no separate network configuration and analysis
is needed [ishfaq]. In Figure 1 shows a network configuration between a source
and destination , where the source tries to sends a packet of size 1800 octet
to destination and follows different steps to complete the transmission with a
path of varying MTUs. We will first measure and analyse the time delays using
Path MTU Discovery. The outputs from this case study will be used later in the
paper, to further analyse time consumption.

Figure 1:  End to End Delay using PMTUD.

###  2.2 Effect on Total Time Delay Using PMTUD

In Figure 1, the source begins to transmit the first transmission with initial
packet of size 1800 bytes, the packet travels up-to node 2, at node 2 the
next-interface MTU is lower than the incoming packet size so the node
truncates the packet and sends an ICMPv6 type 2 message to source “Packet too
Big”. The time taken by a packet to reach at node 2 from source is $2T_{D1}$,
where $T_{D1}$ is End to End delay (E2ED) [article] due to first transmission
and the factor 2 is because it travels two links e1 and e2. Similarly, time
delay for the ICMPv6 message is $2T\textquoteright_{D1}$ where
$T\textquoteright_{D1}$ is the End to End delay between hops for ICMPv6
message for first transmission. The source on receiving the ICMPv6 message it
fragments the packet and initiate the $2_{nd}$ re transmission. The total time
taken for the fragmentation process is $T_{f}$. Since, the waste of time up-to
$2_{nd}$ re-transmission is :

$T_{W1}=2(T_{D1}+T\textquoteright_{D1})+T_{F}\\\ $ (1)

Where ${}^{P}T_{W}$ is the time wastage in first transmission.
In $2_{nd}$ re-transmission of packet the size is now lower than the previous
transmission and the packet travels up-to node 3 and is again been truncated
by $3_{rd}$ node and send the same ICMPv6 type 2 message to source “Packet too
Big". The E2ED from source to the node 3 is $3T_{D2}$ where the factor 3 is
because the packet traveled 3 links and the subscript 2 identifies the
$2_{nd}$ re-transmission. The E2ED for the ICMPv6 message from node 3 to
source is $3T\textquoteright_{D2}$ such that, $T\textquoteright_{D2}<T_{D2}$.
At source the packet is again fragmented and initiate the third transmission.
The fragmentation at source takes some time to fragment the packet which is
$T_{F}$ . So the E2ED for $2_{nd}$ re-transmission from source to initiation
of $3_{rd}$ re-transmission is calculated as:

$T_{W2}=3(T_{D2}+T\textquoteright_{D2})+T_{F}$ (2)

Similarly, in the $3_{rd}$ re-transmission the transmission is again failed at
node 5 which sends back the ICMPv6 (Type 2) message “Packet too Big” to
source. Therefore the E2ED for the $5_{th}$ transmission is the sum of time
delay for packet to reach node 5 from source, the time delay of ICMPv6 message
from node 5 to source and the fragmentation time at source. i.e

$T_{W3}=5(T_{D3}+T\textquoteright_{D3})+T_{F}$ (3)

In $4_{th}$ re-transmission the packet size is least compared to the packet
size of all previous transmissions and is equal to the lowest MTU of the node
in the path. This transmission gets successful and packet reaches to
destination and sends back an acknowledgement (ACK) packet to source. Since
the E2ED in sending the packet from source to destination in $4_{th}$ re-
transmission is given by:

$\displaystyle T_{4}$ $\displaystyle=^{P}T_{D}(n+1)$ (4) $\displaystyle T_{4}$
$\displaystyle=^{P}T_{D}(5+1)$ (5) $\displaystyle T_{4}$
$\displaystyle=6(^{P}T_{D})$ (6)

where $T_{4}$ is E2ED of $4_{th}$ transmission which is also a successful
transmission and ${}^{P}T_{D}$ is the average time delay between consecutive
node and n is number of nodes in the path.

Therefore, the total loss of time or time wastage $(^{P}T_{W})$ on sending the
packet from source to destination from $1_{st}$ transmission to last
transmission is:

${}^{P}T_{W}$ $\displaystyle=T_{W1}+T_{W2}+T_{W3}$ (7) ${}^{P}T_{W}$
$\displaystyle=((2T_{D1}+T^{\prime}_{D1}+T_{F})+(3T_{D2}+T\textquoteright_{D2}+T_{F})+(5T_{D3}+T\textquoteright_{D3})+T_{F})$
(8)

Since there is no time loss in $4_{th}$ re-transmission as its successful
transmission.

The E2ED between nodes in transmission 1, 2 , 3 are not similar that’s why we
add subscript to them. It’s because of the reason that, as packet size
increases the E2ED between nodes increases due to increase in over all
overhead on node from processing, queuing and transmission which cause the
total increase in the E2ED between nodes. The increasing order of the E2ED
between nodes of the transmissions is

$\displaystyle T_{D1}>T_{D2}>T_{D3}>T_{D4}$ (9)

Lets take the worst case scenario that the E2ED of the failed transmission
will be equal to E2ED of last successful transmission for the sack of easy
calculation i.e;

$T_{D1}=T_{D2}=T_{D3}=T_{D4}$

Our this assumption may lightly decrease the total time wastage in PMTUD. The
actual time wastage will be slightly higher then the time wastage shown in the
Equation 10, which is because from Equation 9 we have:

$T_{Di}-T_{D4}<0$ $where,\qquad\ i=(1,2,3)$

Therefore, Equation 8 becomes:

${}^{P}T_{W}\ =\ 10(T_{D4}+T^{\prime}_{D4})+3T_{F}$ (10)

Since, the $4_{th}$ transmission is also the successful transmission.

Therefore,

$T_{D4}=^{P}T_{D},$

Hence,

${}^{P}T_{W}=10(^{P}T_{D}+T\textquoteright_{D})+3T_{F}$ (11)

Therefore, The total time for transmitting the packet in PMTUD is:

$\displaystyle Total\ time\ =\ T_{4}+^{P}T_{W}$
${}^{P}T=6(^{P}T_{D})+10(^{P}T_{D}+^{P}T\textquoteright_{D})+3T_{F}$ (12)

So, we would neglect the changing of E2ED between nodes due to different
packet size in each transmission and will take E2ED between nodes of all
transmission equal to the E2ED between nodes of successful transmission. So
from now own in our calculation we would neglect the E2ED between nodes of
various packet size and apply the E2ED between nodes of successful
transmission.

We have calculated the time wastage in IPv4 and IPv6 network due to the packet
drop by intermediate nodes which we also called as extra time delay or exceed
time delay using all these name reflect same meaning. The time wastage or
extra time delay can be understand as data exchange between Bob and Alice,
that when Bob transmits a packet to Alice it expected total time delay of
$T_{D}$ without any node dropping that packet, but if any node drops the
packet then the Bob has to re-transmit a new packet with decreased packet size
to Alice and the packet arrives to Alice in the expected time $T_{D}$, since
the time consumed in the previous failed transmission which comprises the E2ED
of packet and the E2ED of ICMPv6 which is named as the time wastage or extra
time delay. Now the total time delay in sending the packet will be :

$Total\ time\ delay(T)\ =\ (T_{D})\ +\ (T_{W})$

where $T_{D}$ is expected time without packet loss and $T_{W}$ is time wastage
due to failed transmission and $T$ is actual observed time. In other words the
sum of total time delay of failed transmissions due to successive single
packet loss by intermediate nodes is called time wastage or extra time delay.
In the following theorems we will show different time wastage depending upon
the order by which nodes drop packet and number of nodes involved using PMTUD
algorithm. We will now draw some further conclusions on time wastage using
PMTUD in more general way.

##  3 Analysis of Time Wastage in Path MTU Discovery

######  Theorem 1.

The maximum or the $worst-case$ total time wastage $(^{P}T_{W})$ for the
packet drop using PMTUD algorithm is :

${}^{P}T_{W}=S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{F},\\\ where\
n\subset\mathbb{Z}^{+}$ (13)

where $S_{n}$ is sum of n-terms and n is defined as the number of nodes
between source and destination.

###### Proof.

When the first node drop packet , then it has to send ICMP message to source
and then source send a new packet which reaches node 1 doing this the time
wastage will be the sum of E2ED from source to node 1 and the ICMP message
packet delay from node 1 to source i.e ${}^{P}T_{D}+^{P}T^{\prime}_{D}$.
Similarly, if the packet is drop by second node only, then the time wastage
will be $2(^{P}T_{p}+^{P}T^{\prime}_{D})$ as the node has to reach the source
for Ack packet and send the packet again up-to $2_{nd}$ node it will take
$2(^{P}T_{p}+^{P}T^{\prime}_{D})$ extra time to do that. Since, if the packet
is dropped by any number of nodes in the path between source and destination,
then the time wastage is the effecting node multiply to the sum of E2ED of
packet and ICMPv6 packet and it forms an arithmetic progression of difference
of $(^{P}T_{p}+^{P}T^{\prime}_{D})$ , so by A.P the $a_{n}th$ term is given by

$a_{n}=a+(n-1)d,\ \forall\ n\in(nodes)\ \to\mathbb{Z}^{+}$

$Since,\ a\ =^{P}T_{D}+^{P}T^{\prime}_{D}+T_{F}\ ,\
d=^{P}T_{D}+^{P}T^{\prime}_{D}$
Then the time wastage for incremental nodes dropping packets can be derived
and is given by :

${}^{P}T_{D}+^{P}T^{\prime}_{D}+T_{F},\ 2^{P}T_{D}+2^{P}T^{\prime}_{D}+T_{F},\
3^{P}T_{D}+3^{P}T^{\prime}_{D}+T_{F},\ 4^{P}T_{D}+4^{P}T^{\prime}_{D}+T_{F},$
$\displaystyle 5^{P}T_{D}+5^{P}T^{\prime}_{D}+T_{F},\
6^{P}T_{D}+6^{P}T^{\prime}_{D}+T_{F},\ .....\ ,\
n^{P}T_{D}+n^{P}T^{\prime}_{D}+T_{F}$

Then the total time wastage is given by adding time wastage due to each node 1
upto $n^{th}$ :

${}^{P}T_{W}\ =\ $
$\displaystyle[^{P}T_{D}+^{P}T^{\prime}_{D}+T_{F}]+[2^{P}T_{D}+2^{P}T^{\prime}_{D}+T_{F}]+[3^{P}T_{D}+3^{P}T^{\prime}_{D}+T_{F}]+$
$\displaystyle[4^{P}T_{D}+4^{P}T^{\prime}_{D}+T_{F}]+...+[n^{P}T_{D}+n^{P}T^{\prime}_{D}+T_{F}]$
$\displaystyle=\ $ $\displaystyle[^{P}T_{D}+^{P}T^{\prime}_{D}](1\ +\ 2\ +\ 3\
+\ 4\ +\ ...\ +\ n)+nT_{F}$ $\displaystyle=\ $ $\displaystyle
S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{F}$ ${}^{P}T_{W}\ =\ $ $\displaystyle
S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{F},\ \forall\ n\in\mathbb{Z}^{+}$

∎

######  Corollary 1.1.

The asymptotic upper bound for the $worst-case$ time wastage using Path MTU
discovery is of $\Theta(n)$.

###### Proof.

Since, from the Theorem 1, the equation 13 which can be written as function of
n:

$f(n)={n^{2}\left({}^{P}T_{D}+^{P}T^{\prime}_{D}\over
2\right)}+n\left({{}^{P}T_{D}+^{P}T^{\prime}_{D}\over 2}+T_{f}\right)$

Which is in the form of two-degree polynomial equation of form $an^{2}+bn+c\
where\ a=[^{P}T_{D}+^{P}T^{\prime}_{D}]/2,\ b\
=[^{P}T_{D}+^{P}T^{\prime}_{D}]/2+T_{f},\ c=0\ and\ a>0$, therefore we can
present this equation in asymptotic notation which has the positive constant
of $c_{1}\ ,c_{2}\ and\ n_{0}$ therefore the constants can be found as:

$c_{1}n^{2}\leq f(n)\leq c_{2}n^{2}$
$c_{1}n^{2}\leq{n^{2}\left({}^{P}T_{D}+^{P}T^{\prime}_{D}\over
2\right)}+n\left({{}^{P}T_{D}+^{P}T^{\prime}_{D}\over 2}+T_{f}\right)\leq
c_{2}n^{2}$ $c_{1}\leq{\left({}^{P}T_{D}+^{P}T^{\prime}_{D}\over
2\right)}+\left({{}^{P}T_{D}+^{P}T^{\prime}_{D}+2T_{f}\over 2n}\right)\leq
c_{2}$

The right hand inequality hold for any vale of $n->\infty$ by choosing any
kind of constant $c_{1}\leq^{P}T_{D}+^{P}T^{\prime}_{D}$. Similarly , we make
the left side inequality hold true for any value of $n\geq 1$ by selecting any
constant $c_{2}\geq PT_{D}+^{P}T^{\prime}_{D}+T_{f}$. Since by Choosing
$c_{1},\ c_{2},\ and\ n$ at these given values we can say that:

$f(x)=\Theta(n^{2})$

∎

Since, the asymptotic upper bound of $worst-case$ time wastage in PMTUD
algorithm is $\Theta(n^{2})$, where $n$ is the number of nodes in the path
between source and the destination which the packet has traversed.

Since f(x) has resulted in a asymptotic tight bound of $\Theta(n^{2})$ which
can yield both upper bound and lower bound of time wastage in PMTUD. The upper
bound can also be expressed as $O(n^{2})$ [cormen]. However, the lowest bound
at worst-case time wastage of PMTUD algorithm is $\sigma(n^{2})$ and can’t be
the overall lower bound of time wastage in PMTUD as in normal packet drop in
PMTUD the lower bound of time delay is $\sigma(n)$ as detailed in Corollary
2.1.

######  Theorem 2.

When a packet has been truncate by any single intermediate node using PMTUD
algorithm, then the time wastage $(^{P}T_{W})$ for transmitting the single
packet is given by:

${}^{P}T_{W}=n_{1}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F},\qquad\qquad\forall\
n_{1}\subset n,$ (14)

where $n\in(nodes)\to\mathbb{Z}^{+},$ such that $n_{1}\in n_{i}$ represents
the node which dropped packet first.

###### Proof.

Let the time delay between hops be ${}^{P}T_{D}$ and the time delay for ICMPv6
message be ${}^{P}T^{\prime}_{D}$ as the ICMPv6 message can’t be greater then
1280 octets , therefore ICMPv6 time delay be less then the transmitting packet
delay. On sending back the new packet the source need to do fragmentation and
it will take a small time called fragmentation time $T_{F}$.

When $1^{st}$ node drop packet the time wastage would be the time until it
route the packet to $2_{nd}$ node that will be the delay between the source to
$1^{st}$ hop and the ICMP message delay by hop to the source and time for the
fragmentation by source.

i.e.

${}^{P}T_{D}+^{P}T^{\prime}_{D}+T_{F}$

Similarly, for other nodes the time wastage is,

$\displaystyle 1^{st}\ ,$ ${}^{P}T_{W}=^{P}T_{D}+^{P}T^{\prime}_{D}+T_{F}\ or\
1[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ (15) $\displaystyle 2^{nd}\ ,\ $
${}^{P}T_{W}=2^{P}T_{D}+2^{P}T^{\prime}_{D}+T_{F}\ or\
2[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ (16) $\displaystyle 3^{rd}\ ,\ $
${}^{P}T_{W}=3^{P}T_{D}+3^{P}T^{\prime}_{D}+T_{F}\ or\
3[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ (17) $\displaystyle 4^{th}\ ,\ $
${}^{P}T_{W}=4^{P}T_{D}+4^{P}T^{\prime}_{D}+T_{F}\ or\
4[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ (18) $\displaystyle 5^{th}\ ,\ $
${}^{P}T_{W}=5^{P}T_{D}+5^{P}T^{\prime}_{D}+T_{F}\ or\
5[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ (19) $\displaystyle 6^{th}\ ,\ $
${}^{P}T_{W}=6^{P}T_{D}+6^{P}T^{\prime}_{D}+T_{F}\ or\
6[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ (20)

Since, from Equation 15 to 20 we see that the ${}^{P}T_{W}$ for each node
depends on the position number of the node factor
with$[^{P}T_{D}+^{P}T^{\prime}_{D}]$ , having constant $T_{F}$ throughout.
Therefore, the general equation for the time wastage for $n_{1}$ node drop
packet is:

i.e

${}^{P}T_{W}\ =\ n_{1}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F},$
$\displaystyle\forall\ n_{1}\subset n,\ where\ n\in(nodes)\to\mathbb{Z}^{+}.$

∎

######  Corollary 2.1.

The asymptotic lower bound for the time wastage using Path MTU discovery is of
$\Omega(n)$

###### Proof.

From theorem 2 the equation 14 form a linear 1 degree polynomial equation of
form $an+b\ where\ a\ =[^{P}T_{D}+^{P}T^{\prime}_{D}]\ and\ b=T_{f}$ which
shows that:

$f(n)=an+b$ $f(n)=\Omega(n)$

where

$cn\leq{[^{P}T_{D}+^{P}T^{\prime}_{D}]\over n}+T_{f}$

dividing both the sides of inequality by n we get:

$c\leq[^{P}T_{D}+^{P}T^{\prime}_{D}]+{T_{f}\over n}$

The left hand inequality can be hold for any value n $\geq$ 0 choosing any
constant c $\leq[^{P}T_{D}+^{P}T^{\prime}_{D}]$

Therefore, the asymptotic lower bound is $\Omega(n)$. which implies that this
is the best case scenario of the time wastage in Path MTU discovery. ∎

######  Theorem 3.

The minimum total time wastage for nodes dropping packet at least in one
position in the path between source and destination in PMTUD is given by,

${}^{P}T_{W}=\sum_{i=1}^{\ a}[n_{i}(^{P}T_{D}\ +\ ^{P}T^{\prime}_{D})]+aT_{F}$
(21)

Where $n_{i}$ is the position of the node in the path which drops packet at i
times, also $T_{F}$ is the time of fragmentation by source node and a is
number of times packet dropped in the path.

###### Proof.

In Theorem 2 we have ${}^{P}T_{W}\ =n_{1}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$
which is time wastage for a node dropping packet in the path between the
source and destination. The time wastage for two nodes dropping packets in the
path is given by $[n_{1}+n_{2}][^{P}T_{D}+^{P}T^{\prime}_{D}]+2T_{F},$

$where,\ n_{1}\in\ n\ and\ n_{2}\ \in n-(1,2,3,...,n_{1})\ ,\ n_{1}\neq\
n_{2}\ ,\ n_{1}<n_{2},\ such\ that\ n\in(nodes)\to\mathbb{Z}^{+}$ are first
and second nodes respectively which dropped packets in the path. Similarly, as
we go on increasing the number of nodes which dropping packets to i their is
always a term $n_{i}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ is incremented to
the preceding time wastage, so in general for all of nodes which drop packet
in the path in different order can be given by :

$\displaystyle^{P}T_{W}=\left(\begin{array}[]{lll}(^{P}T_{D}\ +\
^{P}T^{\prime}_{D})\sum_{i=1}^{\ a}[n_{i}]\end{array}\right)+\
aT_{F},\qquad\left(\begin{array}[]{lll}{n_{i-1}\neq\ n_{i}\neq n_{i+1},}\\\
{n_{i}\in(a)\ \to(n),}\\\ {n_{i+1}\in(a)-(1,2,3....n_{i})}\end{array}\right.$
(26)

where a is the number of nodes which dropped packet. Now the Equation 26 is a
general equation for the total time wastage for all cases for nodes which drop
packet from $i=1\ to\ i=n,\ \ where\ n\ \in(nodes)\to\mathbb{Z}^{+}.$ ∎

######  Theorem 4.

The minimum time wastage equals to the maximum total time wastage using PMTUD
algorithm at a = n , which is given by,

${}^{P}T_{W}\ =S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{f}.$ (27)

###### Proof.

If all the nodes in between the path of source and destination drops the
packet consecutively then the theorem for the minimum total time wastage is
given by:

$\displaystyle^{P}T_{W}=(^{P}T_{D}\ +\ ^{P}T^{\prime}_{D})\sum_{i=1}^{\
n}[n_{i}]+nT_{F}$ (28) $\displaystyle where\ a\ =\ n\ ,\ as\ all\ nodes\ are\
dropping\ packet$

Expanding Equation 28 by putting values of i which runs from 1 to n and is
given by:

$\displaystyle^{P}T_{W}=$
$\displaystyle[n_{1}(^{P}T_{D}+^{P}T^{\prime}_{D})+T_{F}]+[n_{2}(^{P}T_{D}+^{P}T^{\prime}_{D})+T_{F}]+[n_{3}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}]+$
$\displaystyle+......+[n_{n}(^{P}T_{D}+^{P}T^{\prime}_{D})+T_{F}]$
$\displaystyle=$
$\displaystyle[^{P}T_{D}+^{P}T^{\prime}_{D}][n_{1}+n_{2}+n_{3}+.....+n_{n}]+[1+1+1+1+\
.....\ n-times]T_{F}$ $\displaystyle=$
$\displaystyle[^{P}T_{D}+^{P}T^{\prime}_{D}][1+2+3+4+....+n]+nT_{F}$
$\displaystyle=$ $\displaystyle[^{P}T_{D}+^{P}T^{\prime}_{D}]S_{n}+nT_{F}$
${}^{P}T_{W}\ =$ $\displaystyle S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{F}$
(29)

Since the Equation 3 which is derived from General formula of minimum time
wastage is equal to the maximum total time wastage at a = n. ∎

######  Theorem 5.

The limit of lower bound and the Upper bound of the total time wastage using
PMTUD algorithm is given by :

$\displaystyle n_{1}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}\leq^{P}T_{W}\leq
S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{f}$ (30)

###### Proof.

In Theorem 3 the general formula for the nodes dropping packets at least at
one position is given by :

${}^{P}T_{W}=(^{P}T_{D}\ +\ ^{P}T^{\prime}_{D})\sum_{i=1}^{\ n}[n_{i}]+nT_{F}$
(31) At a= 1 , ${}^{P}T_{W}=(^{P}T_{D}\ +\ ^{P}T^{\prime}_{D})[n_{1}]+T_{F}$
(32)

Since, the minimum lower bound ${}^{P}T_{W}$ is
$n_{1}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ when one node drop packet at
$n_{1}^{th}$position in the path. As we goes on increasing value of a the
${}^{P}T_{W}$ also goes on increasing up-to a certain point where $a=n$ then
${}^{P}T_{W}=S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{f})$, which is the upper
bound time wastage

$\therefore\qquad n_{1}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}\ \leq\ ^{P}T_{W}\
\leq\ S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{f}\\\ $ (33)

Therefore, the value of ${}^{P}T_{W}$ can’t be lower then
$n_{1}[^{P}T_{D}+^{P}T^{\prime}_{D}]+T_{F}$ and can’t be higher then
$S_{n}[^{P}T_{D}+^{P}T^{\prime}_{D}]+nT_{f}.$ ∎

##  4 Conclusions & Future Work

In this paper, we analyzed the effect of Path MTU Discovery in IPv6 and IPv4
networks. We concluded that the time wastage varies with the increase in the
number of re-transmissions for a single packet. We adopted new theorems and
corollaries to clearly calculate the time wastage resulted due to continuous
use of Path MTU Discovery in IPv6 and IPv4 networks. The comprehensive
analysis carried-out in the paper are one of the first stages of research in
time delays encountered in Path MTU Discovery in IPv4 and IPv6 networks. The
conclusion that is drawn from these analysis is that the time wastage due to
Path MTU discovery has an asymptotic lower bound of $\Omega(n)$ and upper
bound of $\Theta(n^{2})$ with the domain depending only on the number of nodes
the packet traverses the path.

The analysis can be used by the research community to fine tune some of the
parameters in order to reduce the delays associated with PMTUD protocol. The
analysis can also been used as the way to find the optimistic and robustness
of a new protocol design than the present one.

## Authors

Janibul Bashir earned his Ph.D from the Computer Science and Engineering
department of IIT Delhi. He is currently working as an Assistant Professor in
the Information Technology Department at National Institute of Technology,
Srinagar. Before joining NIT Srinagar, he was working as a Software Engineer
at Samsung Research India, Bangalore. He primary works on improving the
performance of multicore systems, on-chip security, and application of machine
learning techniques in the computer architecture domain (emerging
technologies, network-on-chip, thermal management). He is also interested in
the operating systems and parallel programming (distributed systems). He can
be reached at<EMAIL_ADDRESS>
Ishfaq Hussain was previously a student of National Institute of Technology,
Srinagar with field of study concentric to Information Technology. He has a
broad area of research interests in computer science and mathematical areas
but not concentric to computer network, algorithms, mathematical analysis and
computer architectures. He is currently a part of research community by
contributing high authentic work to research communities of computer and
mathematical society. He can be reached at<EMAIL_ADDRESS>
## Key Words

Packet Drop; Time Delay; Ipv6 Protocol; Time Wastage; Path MTU Discovery; Path
MTU.