Reordering Solution Proof Sample Clauses
Reordering Solution Proof. In order to provide a formal proof we make the following assumptions:
1. Reordering can happen only in a forwarding node; no reordering can happen on the wire or line.
2. Reordering can happen only due to queuing/scheduling; no reordering can happen in the classification logic which decides in which queue each packet is to be inserted.
3. No reordering can happen within a service queue; we assume FIFO queues.
4. Within a node, packets of the same service class traverse the same path from Input to Output (e.g. across the switch fabric). Also, the solution is applied at the earliest point possible in the node where reordering can happen due to service class queuing (e.g. packets are remarked to the original service class and tokens are inserted in the higher class before they (packets) cross the switch fabric on a different quality of service path).
5. No reordering can happen due to routing; this solution does not solve reordering caused by routing.
6. Packets of the same flow are originally marked with, or upgraded/downgraded to, the same code points (i.e. will be classified into the same service queues).
7. No reordering in customer equipment (reordering can occur only in the network).
8. A node can be modeled as a sequence of 3 stages: ingress processing, switch fabric, and egress processing, as shown in Figure 7. In turn, each stage (ingress, fabric, or egress) can be modeled in terms of a sequence of queuing and scheduling stages (not shown in the figure). Figure 7 General Node Model Given the above assumptions, we can model the path from Figure 6 between the first ingress edge node and the last egress edge node as a sequence of classification (Multi-field or aggregate), and queuing-scheduling stages as shown in Figure 8. From assumption 2, reordering can happen only in a queuing-scheduling stage (there are N in the figure; a sequence of n nodes, each having m queuing-scheduling stages). We need to prove that reordering can not happen in the first queuing-scheduling stage, and that given no reordering in stage i-1 there will be no reordering in stage i. At the first node, the classifier classifies the packet into a verification stage (not shown in the figure) that polices the customer’s traffic. Packets can get remarked, metered and policed but not reordered. Two sequential packets of the same original service class will be inserted in the same order of arrival in the same service queue since: - If none of the packets got upgraded/downgraded, they wi...