Packet Reordering in the Era of 6G: Comparison
View Latest Version
Please note this is a comparison between Version 3 by Lindsay Dong and Version 2 by Lindsay Dong.

The advent of sixth-generation (6G) networks brings unmatched speed, reliability, and capacity for massive connections, making it a cornerstone for revolutionary applications. One such application is in vehicular networks, which have their unique demands and complexities. Specifically, they face the complex issue of packet reordering due to the high-speed movement of vehicles and frequent switching of network connections.

  • packet reordering
  • 6G networks
  • vehicular network
  • packet reordering metrics

1. Introduction

In our rapidly evolving age of information technology, mobile communication networks have upgraded to infrastructures vital to social and industrial functions [1]. From rudimentary first-generation (1G) mobile network technologies to sophisticated fifth-generation (5G) broadband cellular network technologies, each technological iteration endows users with faster data transmission rates, manages more robust connections, and extends the range of application scenarios. However, despite the current power of 5G networks, they still reveal the limitations of our existing network technology. These limitations manifest as restrictions on spectral resources, congestion, and fluctuations in communication quality. These challenges become more prominent when considering the requirements for massive concurrent connections, low-latency communication, and big data processing. To meet the stringent demands of our future intelligent internet—an internet envisioned as a harmonious combination of the Internet of Things and artificial intelligence—researching and designing the next generation of mobile communication network technology becomes critical [2]. Against this backdrop, the dawn of the sixth-generation (6G) mobile communication network begins to break, illuminating the direction for future communication technology.
One specific application scenario, that is, vehicular networks, plays a pivotal role in the context of 6G applications. With the emergence of applications such as autonomous driving, traffic management, and in-car entertainment services, the demand for low-latency communication and large-scale concurrent connections becomes increasingly intense. Additionally, due to the high-speed movement of vehicles and frequent switching of network connections, vehicular networks introduce unique challenges to the issue of packet reordering. As such, studying packet reordering issues in vehicular networks within a 6G environment becomes particularly crucial and complex. Moreover, these challenges extend beyond vehicular networks to encompass the broader 6G network environment. As we confront larger scale concurrent connections, lower latency requirements, and the need to handle more data, the issue of packet reordering emerges as a significant concern. This phenomenon, triggered by the labyrinthine transmission conditions of complex networks, disrupts latency times and scrambles the order of packet arrivals. Notably, packets belonging to one flow may be blocked by packets from multiple other flows, leading to cache losses and a surge in the number of CPU instructions. Consequently, this reduces the efficiency of packet processing applications, thereby threatening the reliability and efficiency of the broader 6G network [3]. In conclusion, the evolution of mobile communication technology, specifically towards 6G, carries the promise of transforming our ways of life, work, and entertainment. However, this technological leap comes with new challenges. Among these, the issue of packet reordering stands out as a key challenge that needs to be addressed to unlock the full potential of 6G networks.

2. Packet Reordering

2.1. Overview

Packet transmission is a fundamental method of modern network communication. It involves dividing data into packets, encapsulating them, and transmitting them from the data source to the receiving end over single or multiple links, following specific protocols. However, in the actual data path, packets may experience disorder, meaning that the order of packets received by the receiver does not match the order in which they were sent by the sender due to various factors during the data processing [4]. Two concurrent links are depicted in Figure 1. Assume that the delay of the two links satisfies 𝐷1≪𝐷2 packets with serial numbers 1, 4, and 6 from the first path arriving at the receive buffer first in sequential order. Subsequently, packets 5, 3, and 2 from the second path arrive. As packet 2 is awaited, packets 1, 4, 6, 5, and 3 remain in the buffer, causing buffer congestion and degrading network performance. This out-of-order phenomenon indicates a discrepancy between the data flows of senders and receivers. Furthermore, this discrepancy occurs because the sequence numbers of the packets do not match the receive index. When packets with larger numbers arrive at the device before those with smaller numbers, the earlier-arriving packets are cached and wait for the arrival of packets with smaller numbers. Ultimately, these packets are reordered together before being delivered to upper-layer applications.
Figure 1. An example of packet reordering.
Packet reordering is a well-known phenomenon on the Internet, referring to the change in relative order of certain packets within a data flow during network transmission, and the behavior of restoring the original order of packets at the sender through the analysis of packet relationships [5]. Discussions on packet reordering in the industry can be categorized into two types [6], both originating from the 1990s. The first type focuses on measurement methods and experimental research, addressing two main aspects: (1) Measurement environment, including the selection of observation points and datasets. Active probing with specific types of packets (such as TCP or ICMP) is required for measurement at the sender/receiver, while passive detection can be performed at certain points in the backbone network. (2) Reordering determination algorithms, including the definition and classification of reordering, as well as the rules for determining reordering. The second type involves specialized research on reordering, covering aspects such as causes, measurement techniques, evaluation methods, and improvement approaches. In 1999, Paxson et al. [7] undertook two extensive sets of end-to-end experiments involving 35 Internet sites, each consisting of 20,000 TCP bulk transfers. The findings from these experiments revealed the existence of asymmetric Internet paths that led to anomalous network events, such as out-of-order delivery. Interestingly, the frequency of these anomalies was markedly different between the two studies, with the first experiment identifying these events in 2% of cases, while the second experiment observed them at a lower rate of 0.26%. Subsequently, Loguinov and Radha [8] conducted early measurement research on UDP flows, and Gharai [9] conducted research on streaming traffic. After the two measurement studies in 1999, Bennett et al. [10] initiated the second type of research, proposing that packet reordering on the Internet is a pathological network behavior caused by the parallelism of Internet components and links. Large-scale packet reordering on the network can significantly degrade TCP performance, so it should be avoided as much as possible or quickly recovered from. This led to a series of discussions and research on packet reordering in the industry.

2.2. The Causes of Packet Reordering

The causes of packet reordering are multifaceted and can be analyzed from several aspects, including network structure and topology, packet transmission protocols and technologies, network devices and resource scheduling strategies, network congestion, and traffic control, as well as heterogeneous network environments and application scenarios. Understanding and studying the causes of packet reordering contribute to improving network transmission efficiency and stability, reducing network latency, and minimizing packet loss rates.

2.2.1. Network Structure and Topology

In complex network environments, packets may traverse different network nodes and links during transmission. The structure, performance, and connectivity of these nodes and links can lead to packet reordering.
  • Resource Scheduling Strategies. Modern network processors need to support a rich set of services. For example, a multiservice edge router may require support for encryption, decryption, firewall, intrusion detection, and many other services. Packet processing cores used in these processors are often small, and if cores and caches are allocated arbitrarily, it can lead to performance degradation for latency-sensitive network processors, such as packet loss or out-of-order packet transmission. Load balancers also migrate some traffic from overloaded cores to underutilized cores. However, flow migration is undesirable, as incoming packets may experience less queuing delay compared to old packets waiting in the overloaded core queue. This leads to poor data locality and packet reordering.
  • Protocol Specifications for Network Devices. In IPv6, the average packet reordering rate is much lower than in IPv4 networks for two reasons [20]: (1) IPv6 discourages fragmentation in most cases, while in IPv4, hosts and routers can perform packet fragmentation; (2) IPv6 simplifies the basic header, speeding up packet processing and improving the efficiency of packet handling.
    ] and sequencing received packets. On the other hand, UDP is a connectionless protocol that is more sensitive to packet ordering. It does not guarantee the ordered delivery of packets [17]. Therefore, when using UDP, the phenomenon of packet reordering is more noticeable and has a deeper impact.
  • Multipath Transport Protocols. Examples include Multipath TCP (MPTCP) and Multipath UDP (MPUDP). These protocols allow packets to be transmitted through multiple paths, thereby improving network resource utilization and enhancing network robustness. If packets are forwarded through multiple paths, the introduction of asymmetric path characteristics is expected to introduce more parallelism and result in a higher occurrence of packet reordering.
  • Link Layer Technologies and Routing Protocols. Data link layer technologies (such as Ethernet, ATM, Frame Relay, etc.) and routing protocols (such as OSPF, BGP, RIP, etc.) can impact the transmission rate, delay, path, and devices traversed by packets, thus affecting the packet arrival order.

2.2.3. Network Devices and Resource Scheduling Strategies

42] eliminates out-of-order packets completely and effectively reduces the average and 99th flow completion time by up to 73% and 78%, respectively, over the state-of-the-art load balancing scheme.
Electronics 12 03023 g007 550
Figure 23. An example of network coding.

3.1.4. Prediction Based on Stochastic Compensation Effect

In networks, path attributes may dynamically change over time. Most attribute-based calculations assume deterministic proportional scheduling. However, there is no evidence that deterministic scheduling is effective in highly jittery networks where path attributes are random. In such stochastic systems, using a stochastic strategy instead of a deterministic one may be more efficient. This involves partially compensating for the variations in system state parameters through random input parameters, known as the stochastic compensation effect [38].

3.1.5. Prediction Based on Reverse Engineering

Some studies propose reverse engineering methods that adjust the sending packet strategies based on predicting the receiver’s state. This approach aims to ensure that packets arrive at the receiver in the correct order.

3.2. Packet Reordering Avoidance

3.2.1. Prediction Based on Packet-Level Traffic Allocation

In addition to proactive prediction, another approach to mitigate packet reordering is to distribute packets of a flow across multiple paths using traffic splitting or transmission control strategies. This strategy aims to improve throughput and reduce end-to-end latency. However, if the path attributes are asymmetric, it may increase the likelihood of reordering. To address this issue, a solution called QDAPS (Queueing Delay Aware Packet Spraying) has been proposed. QDAPS splits a single flow into packets and then re-routes each packet at a fine granularity by carefully selecting output ports to mitigate packet reordering [43].

3.2.2. Prediction Based on Flow-Level Traffic Allocation

This strategy considers the attributes of the entire flow, such as real-time performance of links, load balancing, and ordered packet transmission. Based on this information, a data allocation scheduling model is constructed, and strategies are implemented to improve congestion conditions of subflows, reduce performance differences between concurrent links, minimize packet reordering, and prevent receiver buffer congestion [44]. Strategies at the flow level include Direct Hashing (DH), Table-based Hashing (TH), Highest Random Weight (HRW), etc. These strategies ensure that packets of the same flow are always mapped to the same path through hash calculations. Table-based Hash Redistribution (THR) methods attempt to improve the hash scheme by addressing the issue of unequal traffic sizes. They allocate a unique mapping table for each service, use incremental hashing for scheduling, identify the highest data rate flow, and dynamically migrate scheduling. This approach effectively avoids packet reordering while maintaining synchronization between flow positions and cache positions, leading to improved network performance [45].

3.2.3. Load Balancing

Load balancing is a network management technique that evenly distributes network traffic across multiple paths or servers to prevent network congestion and optimize network performance [12]. It is a powerful tool to prevent server overload, reduce response times, and improve overall network efficiency and availability. Ideally, load balancing ensures that the actual load on each path matches the desired load, meaning the traffic carried by each path aligns with its capacity. This prevents some paths from being overloaded while others have wasted resources.

3.2.4. Flow Partitioning

To better balance the load on all paths and mitigate bias, flow partitioning strategies have been explored. Methods such as MATE [46], FSLB [47], TeXCP [48], COPE [49], and others employ this strategy in practice, involving dynamic approaches for flow splitting performance. The Flowlet-based Router Engine (FLARE) [50] is an important example that splits a data flow into multiple subflows based on traffic distribution policies. These subflows are guided to switch to paths with the lowest utilization. If the inter-arrival time of two consecutive packets in the same data flow exceeds the maximum time required to send packets via parallel paths, the likelihood of packet reordering decreases.

3.2.5. Flow Truncation Load Balancing Based on Continuous Inter-Packet Arrival Time

This approach, proposed by FCLB (Flow Chopped Load Balancing algorithm) [12], divides data flows into multiple segments based on the continuous inter-packet arrival time. This ensures that packet chopping on each path approaches the desired chopping rate. This method effectively improves packet ordering and enhances network performance.

3.3. Packet Reordering Identification

3.3.1. Acknowledgment Mechanisms

TCP employs a mechanism called Duplicate ACK (dup ACK), where it sends repeated acknowledgments to the corresponding sender for each expected received data packet that has not arrived. When the number of dup ACKs exceeds a certain threshold at the sender, various congestion control measures are triggered, resulting in a reduction in the congestion window (cwnd) size. However, cumulative acknowledgments are based on the entire system rather than a specific path, and it is challenging to differentiate whether the receipt of duplicate packets indicates their discard or reordering. Consequently, congestion control measures are often erroneously activated, leading to an unnecessary reduction in cwnd and the underutilization of available network resources. If not checked at the transport layer, these errors accumulate and propagate, resulting in a phenomenon known as “information dissipation”. Therefore, it is necessary not only to differentiate packet discard from reordering but also to distinguish packet reordering between different paths. This problem requires modifications to TCP, leading to TCP variants. 

UDP itself does not have congestion control and retransmission mechanisms, which makes UDP transmission unreliable. Therefore, improving its reliability has always been a research focus and hot topic in the field. One class of solutions aims to enhance UDP reliability by establishing simple acknowledgment, retransmission, and forward error correction mechanisms, resembling TCP mechanisms. These solutions are referred to as Enhanced Reliable UDP, these methods address packet reordering or out-of-order issues in different ways:
  • SRUDP. SRUDP introduces acknowledgment, retransmission, and sequence alignment mechanisms. By using forward and backward sequence numbers in the protocol header, it ensures that packets are transmitted and acknowledged in the correct order, reducing the impact of packet reordering.
  • RUDP. RUDP utilizes a request–response mechanism along with enhanced data service quality mechanisms such as improved congestion control and retransmission. These mechanisms help maintain the correct order of packets and ensure reliable transmission in the presence of packet loss and network congestion.
  • KCP. KCP implements the Selective Repeat Automatic Repeat Request (ARQ) mechanism and offers features such as fast retransmission, delayed acknowledgment, and packet loss concession. It provides reliable byte stream transmission and utilizes forward error correction (FEC) using Reed–Solomon erasure codes to reduce the need for retransmissions, thereby minimizing data transmission delays caused by packet reordering.
To handle a large number of data flows, researchers have developed various efficient data structures based on the data plane. Tools such as HashPipe [53] and PRECISION [54] can handle reordering statistics of large data flows, but they cannot detect the reordering of individual packets within the flows. Some systems can detect TCP packet reordering on the data plane, such as Marple [55].

3.3.3. Method Based on Machine Learning

This type of method attempts to identify packet reordering using machine learning algorithms. Fonseca et al. [56] proposed an optimal Bayesian packet loss detection method based on round-trip time and constructed an analytical performance model that incorporates general packet loss inference into TCP. The research showed that, for long-term traffic, based on measured round-trip time, high detection probability and low false alarm probability can generally be achieved. Using more general packet loss inference for realistic detection and false alarm probabilities, TCP throughput can be increased by up to 25%. Therefore, deep learning, support vector machines, and other algorithms can be used to predict packet reordering based on historical data.

3.4. Packet Reordering Tolerance

In many cases, network devices can only handle packet reordering issues by triggering congestion and retransmission mechanisms, which not only increase network latency but may also have a negative impact on the utilization efficiency of network bandwidth.

4. Packet Reordering Metrics

4.1. Basic Metrics

It is not difficult to see that both packet sequences have three out-of-order packets, resulting in a 50% reordering percentage.
  • Describing based on the proportion of reordering: Packets 3, 4, and 5 are out of order in both sequences.
  • Describing based on the increasing packet sequence numbers: In sequence 1, packets 3 and 4 are out of order, while in sequence 2, only packet 3 is out of order.
  • UDT. UDT builds upon UDP and implements TCP-like protocols and algorithms. It includes adjustments to TCP’s congestion control algorithm and incorporates features such as Negative-ACK (NAK), ACK to ACK (ACK2), and logarithmic-based dynamic AIMD to handle packet reordering and congestion control.
  • Describing based on the absence of lower sequence numbers after higher ones: In sequence 1, only packet 5 is out of order, while in sequence 2, packets 4 and 5 are out of order.
    SCTP. SCTP is designed as a transport layer protocol that supports reliable transmission and message-oriented communication. It offers ordered or unordered message delivery and utilizes multiple network transmission paths. By avoiding TCP’s SYN Flooding attack and utilizing multiple paths, SCTP reduces the impact of packet reordering in the network.
  • QUIC. QUIC addresses packet reordering through flow control and packet loss recovery mechanisms using Packet Numbers. However, it introduces additional processing overhead and latency to handle out-of-order packets efficiently.
  • uTP. uTP incorporates the LEDBAT congestion control algorithm, which detects network congestion based on latency. By detecting congestion early and making larger congestion avoidance adjustments, uTP minimizes the impact of packet reordering on user activities and ensures coexistence between background downloads and foreground operations.
  • Enet. ENet provides a reliable ordered multichannel packet transmission mechanism, which helps maintain packet order and mitigate packet reordering issues.
  • Describing based on the correspondence between packet sequence numbers and receiving indices: In both sequences, packets 3, 4, and 5 are out of order.
    AWS SRD [51]. SRD leverages multiple network paths in modern data center networks to overcome load imbalance and inconsistent delays. While SRD does not preserve packet order, it sends packets through multiple paths, reducing the impact of packet reordering and avoiding path overload.
  • HARP. HARP tracks the sending and receiving states of each packet using a self-developed packet numbering scheme. This allows for out-of-order reception and selective retransmission with low overhead, ensuring reliable transmission while handling packet reordering challenges.
  • KUDP [52]. The Keyed User Datagram Protocol (KUDP) is designed for efficient data transmission. It boasts capabilities of precisely identifying lost packets and, notably, effectively reordering incoming non-conforming packets, thereby enhancing the efficiency of data flow.
  • Router Internal Parallelism, Reordering, and Forwarding Delays. To achieve better I/O performance and increase throughput, modern routers support packet striping [10][18]. Although many network processors have internal hardware to track traffic and reduce packet reordering within the router, multiple parallel links are still used to connect to the next-hop router, especially in load-balanced switches. Continuous packets on an input interface propagate to all intermediate ports, encountering different queuing delays [19] or varying queue lengths, resulting in different transmission times and inconsistent ordering between transmission and reception, leading to packet reordering.
  • Path Asymmetry. Multipath transmission, compared to single-path transmission, can balance the load and provide better congestion performance [11][12]. However, in packet-level multipath routing, the differences in path attributes can cause packet reordering during transmission. Path attributes that have been proven to affect packet reordering include, but are not limited to, sending rate, propagation rate, link bandwidth, packet loss rate, delays (processing delay, queuing delay, transmission delay, propagation delay, tail delay), packet intervals, and packet sizes [9][13].
  • Path Changes. In the absence of packet loss, packets on a single path will not experience reordering. However, when encountering heavy load, instability, or failure on a link, or when choosing a more optimal path due to latency and congestion, packets may oscillate between available routes to the destination, leading to different delays and packet reordering at the destination [14][15]. For example, in mobile ad hoc networks, they exhibit dynamic topological characteristics, where nodes can move freely, resulting in changes in the network’s topology.
  • Limited Link Bandwidth and Time-Varying Capacity. Due to the dynamic changes in the network topology, the amount of traffic forwarded by each node to destinations other than itself also changes over time. Therefore, unlike wired networks, the capacity of links in wireless networks exhibits time-varying characteristics.

2.2.2. Packet Transport Protocols and Technologies

  • Transport Layer Protocols. Transport layer protocols such as TCP and UDP have different characteristics when handling packets. TCP is reliable and ensures ordered delivery by retransmitting lost packets [16

2.2.4. Network Congestion and Traffic Control

Network congestion, traffic control, and the application of different protocols and technologies all have an impact on the packet transmission order in a network. These factors interact with each other, exacerbating the complexity and diversity of packet reordering phenomena. In terms of network congestion and traffic control, congestion can lead to reduced packet transmission rates, increased latency, and higher packet loss rates. Traffic control and congestion control strategies adjust the sending rate, discard policies, and route selection to reduce network congestion. However, these strategies may cause fluctuations in the packet transmission rates in the network, thereby affecting the arrival order of packets. 

2.2.5. Heterogeneous Network Environment and Application Scenarios

In heterogeneous network environments and application scenarios, the phenomenon of packet reordering exhibits higher complexity. These scenarios include wireless networks, mobile networks, data center networks, cloud computing environments, software-defined networks (SDN), and network function virtualization (NFV) [21]. The diverse network structures, devices, protocols, and technologies in these scenarios collectively impact the transmission order of packets. For example, factors such as channel quality, mobility, and multipath propagation in wireless and mobile networks result in fluctuations in packet transmission rates and delays. In data center networks and cloud computing environments, load balancing strategies, virtual machine migration, and dynamic resource allocation techniques and policies lead to changes in the transmission paths and rates of packets.

2.3. The Impact of Packet Reordering

2.3.1. Application Performance and User Experience

Packet reordering can lead to increased latency, decreased throughput, and jitter in application-layer data transmission, thereby impacting the Quality of Service (QoS) and Quality of Experience (QoE) for applications. In delay-sensitive applications based on UDP, such as multimedia software, receiving out-of-order packets after the playback time is as detrimental as lost packets. The cost of recovering from packet reordering at the user end is high, as it increases the buffer requirements and introduces processing-related delays. Severe packet reordering can cause a buffer overflow, leading to the dropping of a large number of out-of-order packets, resulting in issues such as audio–video stuttering and blurry visuals, ultimately degrading the user experience. In the case of reliable transport protocols such as TCP, the impact of reordering depends on whether the packets are reordered in the forward path (forward path reordering) or the acknowledgments are reordered in the reverse path (reverse path reordering) [22]. As shown in Figure 2, in the forward path from the sender to the receiver, forward path reordering refers to the arrival of packets out of order, which can be perceived as packet loss. In the reverse path, reverse path reordering occurs when ACKs arrive out of order at the destination, leading to the loss of TCP’s ACK self-clocking. This affects the ACK sequence from the receiver to the sender, resulting in burst packet transmissions and congestion. Both types of reordering significantly impact the receiver’s efficiency and TCP end-to-end performance, leading to a reduced congestion window and unnecessary retransmissions [23].
Electronics 12 03023 g005 550
Figure 2. Forward path reordering and reverse path reordering.
  • Spurious Retransmissions. TCP has two methods to trigger its retransmission mechanism [24]. The first method relies on the reception of duplicate ACKs, indicating that the receiver has lost some data [25]. After receiving a required number of consecutive duplicate ACKs (usually three), the TCP sender retransmits the first unacknowledged segment [26] using the fast retransmit and recovery algorithm. The second method involves the TCP sender maintaining a retransmission timer. If a segment remains unacknowledged before the retransmission timeout (RTO) expires, the timer triggers the retransmission of the segment. Upon a retransmission timeout, the TCP sender enters RTO recovery, where the congestion window is initialized to one segment, and the unacknowledged segments are retransmitted using the slow-start algorithm. The retransmission timer is dynamically adjusted based on the measured round-trip time (RTT) [27].
  • Congestion window reduction. TCP is unable to distinguish between packet reordering and packet loss. The receiver of TCP expects that packets from the same data stream are consecutively numbered. After receiving several consecutive duplicate ACKs, the sender may assume that a particular packet is lost. Consequently, it will initiate retransmission and recovery algorithms, leading to a multiplicative reduction in the congestion window size (cwnd) of TCP, transitioning from a “slow start” to a gradual increase in transmission speed. In networks where packet reordering persists and is substantial, TCP will erroneously retransmit data segments, keeping its cwnd unnecessarily small.
  • ACK clock interruption [28]. TCP nodes are distributed worldwide, making it impossible to achieve global clock synchronization for driving cooperative network behavior. Therefore, TCP relies on ACKs and timeout timers to achieve this synchronization. Ideally, with a stable ACK clock, the TCP sender would continuously feed the data stream into the network driven by that clock

2.3.2. Network Security and Performance Diagnosis

Packet reordering has significant implications for network stability and security. Even a small fraction of reordered packets in the backbone link can cause a significant decrease in throughput [29]. Packet reordering can mislead certain protocols (e.g., DCCP, SCTP) and security-related functionalities (e.g., network intrusion detection and prevention systems), leading them to incorrectly perceive network issues or attacks. For example, intrusion detection and defense systems may mistakenly interpret packet reordering as a sign of an attack, resulting in false positives. These systems need to maintain the state of each flow [30][31][32].
Furthermore, packet reordering is contagious [33]. This means that the reordering of one packet can trigger delays for the same data flow or even other data flows, leading to suboptimal data transmission on the link and expanding the scope of impact. The coupled overall transmission performance is reduced. Finally, it is worth mentioning that packet reordering is not entirely disadvantageous. For instance, it can be deliberately induced and used as a means to enhance channel reliability, simulate realistic traffic distributions, augment stealthiness, and enable more secure and private data transmission [34].

3. The Solution to Packet Reordering

3.1. Packet Reordering Prediction

3.1.1. Path-Based Prediction

In multipath transmission, the arrival order of packets can be influenced by the attributes of multiple paths, such as delay and packet loss rate. It is not always ideal to have more parallel paths, as the aggregated throughput can be limited by high-latency transmission links. One approach is to consider these path attributes before transmission and build a reordering model based on the network state and optimization criteria [35][36][37]. This model can select the optimal transmission path, such as choosing the path with the lowest utilization [38] or selecting high-performance paths as the primary paths while using others as backup paths for retransmission and redundancy [39].

3.1.2. Importance-Based Prediction

In addition to path attributes, it can also consider the importance of each packet. For example, certain packets may contain critical information for the entire information flow, and it may need to allocate better paths for these packets or use redundancy transmission to ensure their arrival [37], enabling subsequent batch decisions.

3.1.3. Redundant Transmission Based on Network Coding

To ensure data integrity and reliability, it can use a technique called network coding, which adds redundant information to improve the reliability of packets [39][40][41]. As shown in Figure 23, network coding primarily focuses on basic linear computations, enabling each packet to be replaced by other packets, thus enhancing the overall robustness of the network. This is particularly useful for rare events with high queuing delays. The latest method named Coding-based Distributed Congestion-aware Packet Spraying mechanism or CDCPS [

3.3.2. Method Based on Network Characteristics

It is evident that describing the degree of reordering solely based on the percentage of out-of-order packets is ambiguous and does not provide a detailed and precise description of the depth of reordering. Therefore, it has certain limitations. To address the issue of packet reordering, it is crucial and necessary to choose appropriate metrics as tools and flexibly adjust them in different environments [57].

4.2. Advanced Metrics

Choosing and designing metrics is a multifaceted process that necessitates comprehensive assessment of their essential and advanced features, thorough evaluations, and comparative analyses. It is crucial to understand that no single metric can satisfy all application scenarios, and metrics should provide insight into the user experience or performance. While basic metrics, due to their simplicity and low computational overhead, are beneficial, they may fall short in addressing more complex requirements. In response to these needs, this study synthesizes and consolidates representative advanced metrics, taking into account the aforementioned metric characteristics. Metrics such as Reordering Density (RD) have demonstrated effective performance and have been validated in several studies [22][58][59]. Other metrics, such as Reordering Buffer Density (RBD), have found applications in a variety of contexts [60][61][62][63][64][65][66]. In an analysis of Figure 34, RD emerges as superior in performance, encompassing all basic and advanced characteristics, and outperforming other evaluation metrics. Its functional form enables real-time assessment of network reordering performance. However, traditional criteria for single-path transmission scenarios may be inadequate for capturing the reordering phenomena in multipath transmissions. Therefore, it becomes necessary to combine RD with a more concise and appropriate criterion for continuous monitoring of reordering.
Electronics 12 03023 g009 550
Figure 34. Advanced metrics summary. The ‘✔’ symbol represents that the corresponding metric possesses the indicated property, while the ‘×’ symbol indicates that it does not. The symbol between ‘✔’ and ‘×’ indicates that it partially satisfies the property.
The importance of robust metrics in network analysis cannot be overstated. While traditional metrics such as the Percentage of Late Packets (PL), Mean Displacement of Packets (MD), and Mean Displacement of Late Packets (ML) offer valuable insights, the complexities of packet reordering in 6G networks demand more sophisticated solutions. Two such emerging metrics of interest are Reordering Entropy (RE) [67] and Reorder Density (RD). Reordering Entropy applies the concept of entropy to measure the randomness or disorderliness in packet reordering. With its high informational content, practicality, lower computational cost, and encompassing characteristics, RE serves as an effective tool to gauge the degree of chaos, reordering characteristics, and trends in the packet sequence.

References

  1. Ge, X.; Cheng, H.; Guizani, M.; Han, T. 5G wireless backhaul networks: Challenges and research advances. IEEE Netw. 2014, 28, 6–11.
  2. Yang, P.; Xiao, Y.; Xiao, M.; Li, S. 6G Wireless Communications: Vision and Potential Techniques. IEEE Netw. 2019, 33, 70–75.
  3. Ghasemirahni, H.; Barbette, T.; Katsikas, G.P.; Farshin, A.; Roozbeh, A.; Girondi, M.; Chiesa, M.; Maguire, G.Q., Jr.; Kostić, D. Packet order matters! improving application performance by deliberately delaying packets. In Proceedings of the 19th USENIX Symposium on Networked Systems Design and Implementation (NSDI 22), Renton, WA, USA, 4–6 April 2022; pp. 807–827.
  4. Jayasumana, A.; Piratla, N.; Labs, D.T.; Banka, T.; Bare, A.; Whitner, R. Improved Packet Reordering Metrics. RFC 5236, 1–26. Available online: https://www.rfc-editor.org/info/rfc5236 (accessed on 13 June 2023).
  5. Leung, K.C.; Lai, C.; Li, V.; Yang, D. A packet-reordering solution to wireless losses in transmission control protocol. Wirel. Netw. 2013, 19, 1577–1593.
  6. Yi, W.; Lu, G.; Xing, L. A Study of Internet Packet Reordering; Springer: Berlin/Heidelberg, Germany, 2004.
  7. Paxson, V.; Almes, G.; Mahdavi, J.; Mathis, M. Framework for IP Performance Metrics. RFC 2330: 1–40. 1998. Available online: https://www.rfc-editor.org/info/rfc2330 (accessed on 13 June 2023).
  8. Khayam, S.A.; Karande, S.; Radha, H.; Loguinov, D. Performance analysis and modeling of errors and losses over 802.11b LANs for high-bit-rate real-time multimedia. Signal Process Image Commun. 2003, 18, 575–595.
  9. Gharai, L.; Perkins, C.; Lehman, T. Packet reordering, high speed networks and transport protocol performance. In Proceedings of the Proceedings. 13th International Conference on Computer Communications and Networks (IEEE Cat. No.04EX969), Chicago, IL, USA, 11–13 October 2004; pp. 73–78.
  10. Bennett, J.C.R.; Partridge, C. Packet reordering is not pathological network behavior. IEEE/ACM Trans. Netw. 1999, 7, 789–798.
  11. Pham, P.P.; Perreau, S. Performance analysis of reactive shortest path and multipath routing mechanism with load balance. In Proceedings of the INFOCOM 2003. Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, IEEE Societies, San Franciso, CA, USA, 30 March–3 April 2003; pp. 251–259.
  12. Chao, W.; Zhang, X.; Chen, W.; Niu, X. Load Balancing Algorithm Using Flow Chopping to Avoid Packet Reordering. In Proceedings of the 2009 International Forum on Information Technology and Applications, Chengdu, China, 15–17 May 2009; pp. 193–197.
  13. Tinta, S.; Mohr, A.; Wong, J. Characterizing end-to-end packet reordering with UDP traffic. In Proceedings of the 14th IEEE Symposium on Computers and Communications (ISCC 2009), Sousse, Tunisia, 5–8 July 2009; pp. 321–324.
  14. Nebat, Y.; Sidi, M. Analysis of resequencing in downloads. Int. J. Commun. Syst. 2010, 16, 735–757.
  15. Kaspar, D.; Evensen, K.; Hansen, A.F.; Engelstad, P.; Halvorsen, P.; Griwodz, C. An analysis of the heterogeneity and IP packet reordering over multiple wireless networks. In Proceedings of the 14th IEEE Symposium on Computers and Communications (ISCC 2009), Sousse, Tunisia, 5–8 July 2009; pp. 637–642.
  16. Hu, F.; Sharma, N.K. Enhancing wireless internet performance. IEEE Commun. Surv. Tutor. 2009, 4, 2–15.
  17. Arthur, C.M.; Girma, D.; Harle, D.; Lehane, A. The effects of packet reordering in a wireless multimedia environment. In Proceedings of the 1st IEEE International Symposium on Wireless Communication Systems, ISWCS 2004, Mauritius, 20–22 September 2004; pp. 453–457.
  18. Paxson, V. End-to-end Internet packet dynamics. IEEE/ACM Trans. Netw. 1999, 7, 277–292.
  19. Yang, S.; Lin, B.; Tune, P.; Xu, J.J. A simple re-sequencing load-balanced switch based on analytical packet reordering bounds. In Proceedings of the 2017 IEEE Conference on Computer Communications, INFOCOM 2017, Atlanta, GA, USA, 1–4 May 2017; pp. 1–9.
  20. Li, F.; Wang, X.; Pan, T.; Yang, J. A Case Study of IPv6 Network Performance: Packet Delay, Loss, and Reordering. Math. Probl. Eng. 2017, 2017, 1–10.
  21. Gao, C.; Ling, Z.; Yuan, Y. Packet reordering analysis for concurrent multipath transfer. Int. J. Commun. Syst. 2014, 27, 4510–4526.
  22. Piratla, N.M.; Jayasumana, A.P.; Bare, A.A.; Banka, T. Reorder buffer-occupancy density and its application for measurement and evaluation of packet reordering. Comput. Commun. 2007, 30, 1980–1993.
  23. Blanton, E.; Allman, M. On Making TCP More Robust to Packet Reordering. ACM SIGCOMM Comput. Commun. Rev. 2002, 32, 20–30.
  24. Postel, J. Transmission Control Protocol. RFC 1981, 2, 595–599. Available online: https://www.rfc-editor.org/info/rfc0793 (accessed on 11 June 2023).
  25. Kasimsetti, S.P.; Hussain, A. Enhanced packet reordering procedure to improve TCP communication. Int. J. Pervasive Comput. Commun. 2022, 18, 98–113.
  26. Allman, M. TCP Congestion Control. RFC 2009. Available online: https://www.rfc-editor.org/info/rfc5681 (accessed on 13 June 2023).
  27. Paxson, V.; Allman, M.J. RFC 2988—Computing TCP’s Retransmission Timer; RFC: 2012. Available online: https://www.rfc-editor.org/info/rfc2988 (accessed on 11 June 2023).
  28. Jacobson, V. Congestion avoidance and control. ACM SIGCOMM Comput. Commun. Rev. 1988, 18, 314–329.
  29. Laor, M.; Gendel, L. The effect of packet reordering in a backbone link on application throughput. IEEE Netw. 2002, 16, 28–36.
  30. Dharmapurikar, S.; Paxson, V. Robust TCP stream reassembly in the presence of adversaries. In Proceedings of the 14th USENIX Security Symposium, Baltimore, MD, USA, 31 July–5 August 2005.
  31. Varghese, G.; Fingerhut, J.A.; Bonomi, F. Detecting evasion attacks at high speeds without reassembly. In Proceedings of the ACM SIGCOMM 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Pisa, Italy, 11–15 September 2006; p. 327.
  32. Vutukuru, M.; Balakrishnan, H.; Paxson, V. Efficient and Robust TCP Stream Normalization. In Proceedings of the Security and Privacy (SP 2008), Oakland, CA, USA, 18–21 May 2008; IEEE: Piscataway, NJ, USA, 2008.
  33. Rottenstreich, O.; Li, P.; Horev, I.; Keslassy, I.; Kalyanaraman, S. The Switch Reordering Contagion: Preventing a Few Late Packets from Ruining the Whole Party. IEEE Trans. Comput. 2014, 63, 1262–1276.
  34. El-Atawy, A.; Al-Shaer, E. Building covert channels over the packet reordering phenomenon. In Proceedings of the IEEE INFOCOM 2009; IEEE: Piscataway, NJ, USA, 2009; pp. 2186–2194.
  35. Wu, J.; Bo, C.; Shang, Y.; Huang, J.; Chen, J. A novel scheduling approach to concurrent multipath transmission of high definition video in overlay networks. J. Netw. Comput. Appl. 2014, 44, 17–29.
  36. Chebrolu, K.; Rao, R.R. Bandwidth aggregation for real-time applications in heterogeneous wireless networks. IEEE Trans. Mob. Comput. 2006, 5, 388–403.
  37. Jurca, D.; Frossard, P. Video Packet Selection and Scheduling for Multipath Streaming. IEEE Trans. Multimed. 2007, 9, 629–641.
  38. Korzun, D.; Kuptsov, D.; Gurtov, A. A Simulation Study of the Stochastic Compensation Effect for Packet Reordering in Multipath Data Streaming. In Proceedings of the 2015 IEEE European Modelling Symposium, EMS 2015, Madrid, Spain, 6–8 October 2015; pp. 409–414.
  39. Wu, D.; Wang, R.; Zhen, Y. Link stability-aware reliable packet transmitting mechanism in mobile ad hoc network. Int. J. Commun. Syst. 2012, 25, 1568–1584.
  40. Zhou, X.; Zhang, D.; Yang, Y.; Obaidat, M.S. Network-coded multiple-source cooperation aided relaying for free-space optical transmission. Int. J. Commun. Syst. 2012, 25, 1465–1478.
  41. Ha, N.V.; Tsuru, M. TCP with Network Coding Performance Under Packet Reordering. In Proceedings of the Advances in Internet, Data and Web Technologies, 7th International Conference on Emerging Internet, Data and Web Technologies (EIDWT-2019), Fujairah Campus, United Arab Emirates, 26–28 February 2019; Springer: Berlin/Heidelberg, Germany, 2019; Volume 29, pp. 552–563.
  42. Hu, J.; Ruan, C.; Wang, L.; Alfarraj, O.; Tolba, A. Coding-Based Distributed Congestion-Aware Packet Spraying to Avoid Reordering in Data Center Networks. IEEE Access 2021, 9, 35539–35548.
  43. Huang, J.; Lyu, W.; Li, W.; Wang, J.; He, T. Mitigating Packet Reordering for Random Packet Spraying in Data Center Networks. IEEE/ACM Trans. Netw. 2021, 29, 1183–1196.
  44. Mohammadpour, E.; Boudec, J.L. On Packet Reordering in Time-Sensitive Networks. IEEE/ACM Trans. Netw. 2022, 30, 1045–1057.
  45. Iqbal, M.F.; Holt, J.; Ryoo, J.H.; John, L.K.; Veciance, G.D. Flow Migration on Multicore Network Processors: Load Balancing While Minimizing Packet Reordering. In Proceedings of the 42nd International Conference on Parallel Processing, ICPP 2013, Lyon, France, 1–4 October 2013; pp. 150–159.
  46. Elwalid, A.; Jin, C.; Low, S.; Widjaja, I. MATE: MPLS adaptive traffic engineering. In Proceedings of the IEEE INFOCOM 2001, The Conference on Computer Communications, Twentieth Annual Joint Conference of the IEEE Computer and Communications Societies, Twenty years into the communications odyssey, Anchorage, AK, USA, 22–26 April 2001; pp. 1300–1309.
  47. You-Jun, B.U. Load Balancing Algorithm Using Flow Splitting to Avoid Packet Reordering. Comput. Sci. 2010, 37, 67–70.
  48. Kandula, S.; Katabi, D.; Davie, B.S.; Charny, A. Walking the Tightrope: Responsive Yet Stable Traffic Engineering. In Proceedings of the ACM SIGCOMM 2005 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Philadelphia, PA, USA, 22–26 August 2005; pp. 253–264.
  49. Hao, W.; Xie, H.; Qiu, L.; Yang, R.Y.; Greenberg, A.G. COPE: Traffic engineering in dynamic networks. In Proceedings of the ACM SIGCOMM 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, Pisa, Italy, 11–15 September 2006; pp. 99–110.
  50. Roughan, M. Public review for dynamic load balancing without packet reordering. ACM SIGCOMM Comput. Commun. Rev. 2007, 37, 51.
  51. Shalev, L.; Ayoub, H.; Bshara, N.; Sabbag, E. A cloud-optimized transport protocol for elastic and scalable hpc. IEEE Micro 2020, 40, 67–73.
  52. Gil, F.M.; Garcia, N.M.; Matos, B.; Pombo, N.; Goleva, R.; Dobre, C. Identifying Packet Loss and Reordering Packets in Keyed UDP Transmissions. In Proceedings of the GLOBECOM (Workshops), Taipei, Taiwan, 8–10 December 2020; IEEE: Piscataway, NJ, USA, 2020; pp. 1–5.
  53. Sivaraman, V.; Narayana, S.; Rottenstreich, O.; Muthukrishnan, S.; Rexford, J. Heavy-hitter detection entirely in the data plane. In Proceedings of the Symposium on SDN Research, SOSR 2017, Santa Clara, CA, USA, 3–4 April 2017; pp. 164–176.
  54. Metwally, A.; Agrawal, D.; El Abbadi, A. Efficient computation of frequent and top-k elements in data streams. In Proceedings of the Database Theory-ICDT 2005, 10th International Conference, Edinburgh, UK, 5–7 January 2005; Springer: Berlin/Heidelberg, Germany, 2005; pp. 398–412.
  55. Narayana, S.; Sivaraman, A.; Nathan, V.; Goyal, P.; Arun, V.; Alizadeh, M.; Jeyakumar, V.; Kim, C. Language-directed hardware design for network performance monitoring. In Proceedings of the Conference of the ACM Special Interest Group on Data Communication, SIGCOMM 2017, Los Angeles, CA, USA, 21–25 August 2017; pp. 85–98.
  56. Fonseca, N.; Crovella, M. Bayesian packet loss detection for TCP. In Proceedings of the INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies, Miami, FL, USA, 13–17 March 2005; Volume 3, pp. 1826–1837.
  57. Torres, P.R., Jr.; Ribeiro, E.P. Packet Reordering Metrics to Enable Performance Comparison in IP-Networks. J. Comput. Netw. Commun. 2020, 2020, 8465191:1–8465191:8.
  58. Piratla, N.M.; Jayasumana, A.P.; Banka, T. On reorder density and its application to characterization of packet reordering. In Proceedings of the IEEE Conference on Local Computer Networks 30th Anniversary (LCN’05)l, Sydney, NSW, Australia, 17 November 2005; IEEE: Piscataway, NJ, USA, 2005.
  59. Piratla, N.M. A Theoretical Foundation, Metrics and Modeling of Packet Reordering and Methodology of Delay Modeling Using Inter-Packet Gaps; Colorado State University: Fort Collins, CO, USA, 2005.
  60. Wu, W.; Demar, P.; Crawford, M. Sorting Reordered Packets with Interrupt Coalescing. Comput. Netw. 2009, 53, 2646–2662.
  61. Evensen, K.; Kaspar, D.; Engelstad, P.; Hansen, A.F.; Griwodz, C.; Halvorsen, P. A network-layer proxy for bandwidth aggregation and reduction of IP packet reordering. In Proceedings of the 34th Annual IEEE Conference on Local Computer Networks, LCN 2009, Zurich, Switzerland, 20–23 October 2009; pp. 585–592.
  62. Kaspar, D. Multipath aggregation of heterogeneous access networks. ACM 2012, 4, 27–28.
  63. Ramaboli, A.L.; Falowo, O.E.; Chan, A.H. Bandwidth aggregation in heterogeneous wireless networks: A survey of current approaches and issues. J. Netw. Comput. Appl. 2012, 35, 1674–1690.
  64. Narasiodeyar, R.M.; Jayasumana, A.P. Improvement in packet-reordering with limited re-sequencing buffers: An analysis. In Proceedings of the 38th Annual IEEE Conference on Local Computer Networks, Sydney, Australia, 21–24 October 2013; pp. 416–424.
  65. Latif, S.A.; Masud, M.H.; Anwar, F.; Alam, M.K. An investigation of scheduling and packet reordering algorithms for bandwidth aggregation in heterogeneous wireless networks. Middle East J. Sci. Res. 2013, 16, 1613–1623.
  66. El-Atawy, A.; Duan, Q.; Al-Shaer, E. A novel class of robust covert channels using out-of-order packets. IEEE Trans. Dependable Secur. Comput. 2015, 14, 116–129.
  67. Anwar, F.; Masud, M.H.; Khan, B.U.I.; Olanrewaju, R.F.; Latif, S.A. Analysis of packet reordering delay for bandwidth aggregation in heterogeneous wireless networks. IPASJ Int. J. Inf. Technol. 2018, 6.
More
© Text is available under the terms and conditions of the Creative Commons Attribution (CC BY) license (http://creativecommons.org/licenses/by/4.0/)
ScholarVision Creations
Feedback