## 4 Design of RBMM
### Network Overhead Evaluation  
Packet reordering and the RBMM entail network overhead operations, including dynamic threshold calculation for buffer partitioning, flow score computation, packet sequencing via Red-Black Trees (involving insertion and removal operations), and multiple table lookups. The following section presents a detailed complexity analysis and resource overhead evaluation for each operation.  
In Algorithm 1, the primary computational complexity arises from updating the statistical variables \(N_{\text{PHRD}}\) and \(N_{\text{rt}}\) (line 13). This operation requires traversing the buffer to retrieve all flows where the true condition is satisfied, resulting in a time complexity of \(O(N)\), where \(N\) denotes the number of flows in the buffer that are subject to reordering. Notably, the statistical variables are updated only once per interval (Line 11), and the number of reordering flows in the buffer is generally small. Therefore, under the experimental conditions with a flow update interval of 10 ms, the traversal overhead is relatively low. Beyond these two statistical updates, additional operations, including packet characteristic extraction (Line 4), condition evaluation and marking (Lines 5-9), moving average calculation of _Psize_thresh_ (Line 12), dynamic threshold computation (Lines 14-15), and the auxiliary function IsPersistLargeFlow (Line 18), all have a time complexity of \(O(1)\). Overall, the buffer partitioning operation has a limited impact on the system's performance.  
The flow score calculation in Algorithm 2 avoids traversing the entire Red-Black Tree. In Lines 7-8, it retrieves the maximum and minimum elements of the Red-Black Tree using C++ standard library methods (begin() and end()), each with a time complexity of \(O(1)\). Additionally, the size() method for obtaining the overall size of the Red-Black Tree can also be completed in \(O(1)\) time. For the score calculation process (Lines 12-20), a differential update approach is adopted, involving only basic arithmetic operations with a  
Figure 4: Diagram of packet insertion in the middle of a Red–Black Tree.  
time complexity of \(O(1)\). In summary, the time complexity of the entire score calculation process is independent of both the number of flows in the buffer and the number of packets within each flow. Therefore, the impact of the score calculation on the overall system performance is relatively small.  
When using Red-Black Tree structure to organize flows in sequence, the time complexity for both inserting and deleting elements is \(O(logN)\). Since each forwarded packet is the element with the smallest sequence number in its flow (either meeting transmission conditions or evicted due to congestion), this characteristic reduces the overhead of locating elements during deletion.  
The table lookup operations involve queries on the expected sequence number table and the score table. For the expected sequence number table, as maintaining order is unnecessary, a hash table can be used to achieve \(O(1)\) query operations, albeit with additional space overhead. For score queries, as only the maximum and minimum scores are of interest, these values can still be retrieved in \(O(1)\) time by organizing the table using a Red-Black Tree structure.  
In summary, RBMM leverages data structures effectively and carefully designs its computational processes, introducing no significant additional burden to the system. The primary source of network overhead comes from the reordering process itself, as it involves dynamic adjustments to the Red-Black Tree structure. Additionally, during system operation, the Red-Black Trees and table entries associated with flows that have completed transmission are promptly cleared, thus conserving space resources effectively.