Asynchronous Deterministic Networking Framework for Large-Scale Networks

4.1. Problem Statement

In Section 4, we assume there are only two classes of traffic. The high priority traffic requires latency upper bound guarantee. All the other traffic is considered to be the low priority traffic, and be completely preempted by the high priority traffic. High priority (HP) traffic is our only focus.¶

It is well understood that the necessary conditions for a flow to have a bounded latency inside a network, are that;¶

• a flow entering a network conforms to a prescribed traffic specification (TSpec), including the arrival rate and the maximum burst size, and¶
• all the network nodes serve the flow with a service rate which are greater than or equal to the arrival rate.¶

These conditions make the resource reservation and the admission control mandatory. These two functions are considered given and out of scope of this document.¶

Here, the notion of arrival and service rates represent sustainable or average values. A short-term discrepancy between these two rates contributes to the burst size increment, which can be accumulated as the flow passes through the downstream nodes. This results in an increase in the latency bound. Therefore, the value of accumulated burst size is a critical performance metric.¶

The queuing and scheduling of a flow plays a key role in deciding the accumulated burst size. Ideally, the flows can be queued in separate queues and the queues are scheduled according to the flow rates. In this case a flow can be considered protected. With practical fair schedulers, such as the Deficit Round Robin (DRR), a protected flow still can be affected by the other flows as much as their maximum packet lengths.¶

If we adopt a separate queue per flow at an output port, and assume identical flows from all the input ports, then the maximum burst size of a flow out of the port, Bout, is given as the following:¶

Bout < Bin + (n-1)L*r/C,

where Bout is the outgoing flow's maximum burst size, Bin is the incoming flow's maximum burst size, n is the number of the flows, L is the maximum packet size, r is the average rate of the flow, and C is the link capacity. This approach was taken in the integrated services (IntServ) framework [RFC2212].¶

The separate queues in the aforementioned case can be too many to be handled in real time, especially at the core of large-scale networks. The common practice therefore is to put all the HP flows in a single queue, and serve them with higher priority than best effort traffic. It is also well known that, with a resource reservation, a proper scheduling scheme such as the strict priority (SP) scheduling can guarantee service rates larger than the arrival rates, therefore the latency can still be guaranteed. With such a single aggregate queue the flows are not considered protected, however. In this case a flow's burst size in a node can be increased proportionally to the sum of maximum burst sizes of the other flows in the queue. That is,¶

Bout < Bin + (n-1)Bin*r/C.

The second term on the right-hand side represents the amount of increased maximum burst. It is dominated by the term (n-1)Bin, which is the maximum total burst from the other flows.¶

Moreover, this increased burst affects the other flows' burst size at the next node, and this feedforward can continue indefinitely where a cycle is formed in a network. This phenomenon is called a cyclic dependency of a network. It is argued that the burst accumulation can explode into infinity, therefore the latency is no longer guaranteed.¶

As such, a flow is required to be protected to a certain level, from the other flows' bursts, such that its burst accumulations are kept within a necessary value. By doing so, the other flows are also protected. The regulators or the fair queuing schedulers are described as solutions in this document for such protection. They can decrease the accumulated burst into a desirable level and can protect flows from others. In case of the regulators, however, if the regulation needs a separate queue per flow, then the scalability would be harmed just like the ideal IntServ case. In this document solutions with the IR or the regulations on flow aggregates are described.¶

Meanwhile, the fair queuing (FQ) technique limits interference between flows to the degree of maximum packet size. Packetized generalized processor sharing (PGPS) and weighted fair queuing (WFQ) are representative examples of this technique [PAREKH]. In this technique, the key is to record the service status of the flow in real time to provide exactly the assigned amount of service. The worst delay at each node with FQ is proportional to the maximum packet length divided by service rate. However, for this purpose, the complexity of managing and recording a large amount of state information for each flow is a problem, so it is not usually applied in practice.¶

To solve this problem, the flow entrance node can create state information for each packet, including the finish time (FT) and other necessary information, and record it in the packet. Subsequent nodes infer the exact states of the packet at the node based on these records without managing flow state information. This method provides a scalable solution that enables protection between flows by modifying the FT based on local and initial information as needed. In this document the method of such stateless FQ implementation in core nodes is described.¶

4.2. Asynchronous Traffic Shaping (ATS)

The first solution in this document for latency guarantee is the IEEE TSN TG's ATS technology. Essentially it is a combined effort of the flow aggregation per node per input/output ports pair per class, and the interleaved regulator per flow aggregate (FA). The IR examines the HOQ, identifies the flow the packet belongs to, and transfers the packet only when it is eligible according to the TSpec including the maximum burst size and arrival rate of the flow. Having the flows regulated as their TSpecs, the flow's burst size in a node can be increased proportionally to the sum of initial maximum burst sizes of the other flows in the queue, denoted by B.¶

Bout < B + (n-1)B*r/C.

The initial maximum burst size refers to the maximum burst size specified in TSpec.¶

This solution can have only one queue per FA, but suffers from having to maintain each individual flow state. The detailed description on ATS can be found in [IEEE802.1Qcr].¶

4.3. Flow Aggregate Interleaved Regulators (FAIR)

         .~~.    +---+    .~~,        +---+        .~~.
+---+   [    ]   |IR |   [    ]       |IR |       [    ]   +----+
|Src|->[  AD  ]->|per|->[  AD  ]-> ...|per|... ->[  AD  ]->|Dest|
+---+   [    ]   |FA |   [    ]       |FA |       [    ]   +----+
         '~~'    +---+    '~~'        +---+        '~~'

4.4. Port-based Flow Aggregate Regulators (PFAR)

The IR in the ATS and the FAIR suffers from two major complex tasks; the flow state maintenance and the HOQ lookup to determine the flow to which the packet belongs. Both tasks involve real-time packet processing and queue management. As the number of flows increases, the IR operation may become burdensome as much as the per- flow regulators. Without maintaining individual flow states, however, the flows can be protected to a certain level, as is described in this section.¶

Let us call the set of flows sharing the same input/output ports pair the port-based FA (PFA). The only aggregation criteria for a PFA are the ports and the class. The port-based flow aggregate regulators (PFAR) framework puts a regulator for each PFA in an output port module, just before the class-based queuing/scheduling system of the output port module. The PFAR framework sees a PFA as a single flow with the "PFA-Tspec", {the sum of the initial maximum bursts; and the sum of the initial arrival rates} of the flows that are the elements of the PFA; and regulates the PFA to meet its PFA-Tspec.¶

If we assume identical flows in a network with ideal symmetrical topology, then the maximum burst size of an arbitrary set of flows within an PFA, Bout, is given as the following:¶

Bout < Bin + (p-1)B*r/C,

where Bin is the sum of maximum burst sizes of the flows within the FAin, B is the sum of initial maximum burst sizes of the flows within the FAin, and p is the number of the ports in the node.¶

The PFARs can be placed at the output port of a node before the output SP scheduler. The architecture is similar to that suggested in the IEEE ATS, except that in the ATS, the IRs are placed instead of the PFARs.¶

Note that Bout is affected mostly by B; in other words, the burst size out of a node is affected mostly by the initial maximum burst sizes of the other PFAs from different input ports of the node. This property makes the Bout does not increase exponentially even in the existence of cyclic dependencies. The regulator in PFAR increases the worst latency, as much as (Bin - B)/r, while the IR does not.¶

With the PFAR, the HOQ flow identification process is unnecessary, and only the PFAs' states, instead of individual flows' states, must be maintained at a node. In this respect, the complexity of process of PFAR is reduced compared to IR of the ATS or the FAIR.¶

In a recent study [ADN], it was also shown, through a numerical analysis with symmetrical networks with cycles, that PFAR, when implemented at every node, can achieve comparable latency bounds to the IEEE ATS technique.¶

The ATS, the FAIR, and the PFAR frameworks maintain regulators per FA. The FAs in these frameworks are composed of the flows sharing the same ingress/egress ports of an AD. The ADs can encompass a single hop or multiple hops. The regulators can be the IR or the aggregate regulator. There can be other combinations of AD and regulator type, which could be further investigated and compared to the frameworks introduced in this document.¶

4.5. Work-conserving stateless core fair queuing (C-SCORE)

The generalized processor sharing (GPS) [PAREKH], the weighted fair queuing (WFQ), the virtual clock (VC), and similar other schedulers utilize the concept of finish time (FT) that is the service order assigned to a packet. The packet with the minimum FT in a buffer is served first. We will call these works collectively as the fair queuing (FQ).¶

As an example, the VC scheduler [ZHANG] defines the FT to be¶

F(p) = max{F(p-1), A(p)} + L(p)/r,          (1)

where (p-1) and p are consecutive packets of the flow under observation, A(p)is the arrival time of p, L(p) is the length of p, and r is the flow service rate. The flow index is omitted.¶

The key idea of the FQ is to calculate the service finish times of packets in an imaginary ideal fluid service model and use them as the service order in the real packet-based scheduler.¶

While having the excellent flow protection property, the FQ needs to maintain the flow state, F(p-1). For every arriving packet, the flow it belongs to has to be identified and its previous packet's FT should be extracted. As the packet departs, the flow state, F(p), has to be updated as well.¶

We consider a framework for constructing FTs for packets at core nodes without flow states. In a core node, the following conditions on FTs are preferred to be met.¶

C1)

The 'fair distance' of consecutive packets of a flow generated at the entrance node has to be kept in the core nodes. That is; Fh(p) >= Fh(p-1) + L(p)/r, where Fh(p) is the F(p) at node h.¶

C2)

The order of FTs and the actual service order, within a flow, have to be kept. That is; Fh(p) > Fh(p-1) and Ch(p) > Ch(p-1), where Ch(p) is the actual service completion time of packet p at node h.¶

C3)

The time lapse at each hop has to be reflected. That is; Fh(p) >= F(h-1)(p), where F(h-1)(p) is the FT of p at the node h-1, the upstream node of h.¶

C4)

The FTs of a flow have to be aligned to the packet arrival times. The packets of aligned flows arriving at a node at the same time should have FT values that are within a bound.¶

It was suggested by [STILIADIS-RPS] for a scheduler to be a packetized rate proportional server (PRPS), FT of a flow should be aligned to the current virtual time; i.e. L(p)/r < Fh(p)- V(Ah(p))< Delta. Delta is any finite positive number. V(t) is called a virtual time function. Virtual time represents the progress of the system. If the backlogged flows almost fill the link capacity, then the system slowly progresses in terms of a flow's view, and so does the virtual time. If there is only a handful of backlogged flows, then the virtual time increases with a higher rate. It prevents an unfair situation in which flows that entered late have relatively small FTs thus receive services earlier for a considerable period of time, compared to existing flows.¶

In essence, (1) has to be approximated in core nodes. There can be many possible solutions to meet these conditions. We describe a generic framework with requirements for constructing FTs in core nodes that meet the conditions, without flow state, in the following.¶

Requirement 1: In the entrance node, it is required to obtain the FTs with (1). 0 denotes the entrance node of the flow under observation.¶

F0(p) = max{F0(p-1), A0(p)}+L(p)/r.

Note that F0(p) keeps the fair distances from the FTs of consecutive packets of the flow.¶

Requirement 2: In a core node h, it is required to increase the FT of a packet by an amount that depends on the nodes and the packet, dh(p).¶

Fh(p) = F(h-1)(p) + d(h-1)(p).

Requirement 3: It is required that dh(p) is a non-decreasing function of p, within a flow active period.¶

Definition 1: An active period for a flow is a maximal interval of time during a node busy period, over which the finish time of the most recently arrived packet of the flow is greater than the virtual time (equivalently the system potential). Any other period is an inactive period for the flow.¶

Definition 2: A node busy period is a maximal interval between consecutive node idle periods. During a node idle period, the node has no packet to send.¶

By Requirements 1, 2, and 3; Conditions 1), 2), and 3) are met.¶

We call the described FT construction framework the work conserving stateless core fair queuing (C-SCORE), which can be compared to the existing non-work conserving scheme [STOICA].¶

dh(p) = SL(h-1).        (2)

SLh = Lh/Rh + L/r,

   Dh(p) <= (B-L)/r + SL0 + SL1 + ... + SLh,     (3)

5.1. Problem statement

The problem of guaranteeing jitter bounds in arbitrarily sized networks with any type of topology with random dynamic input traffic is considered.¶

There are several possible solutions to guarantee jitter bounds in packet networks, such as IEEE TSN's cyclic queuing and forwarding (CQF) [IEEE802.1Qch], its asynchronous variations [I-D.yizhou-detnet-ipv6-options-for-cqf-variant], and the latency-based forwarding (LBF) [LBF].¶

The CQF requires time-synchronization across every node in the network including the source. It is not scalable to a large network with significant propagation delays between the nodes. The asynchronous CQFs are scalable, but they may not satisfy applications' jitter requirements. This is because their jitter bounds cannot be controlled as desired, but are only determined by the cycle time, which should be large enough to accommodate all the traffic to be forwarded.¶

The systems with slotted operations such as the CQF and its variations turn the problem of packet scheduling into the problem of scheduling flows to fit into slots. The difficulty of such a slot scheduling is a significant drawback in large scale dynamic networks with irregular traffic generations and various propagation delays.¶

The LBF is a framework of the forwarding action decision based on the flow and packet status, such as the delay budget left for a packet in a node. The LBF does not specify the actions to take according to the status. It suggests a packet slow down or speedup by changing the service order, by pushing packets into any desirable position of a first out queue, as a possible action to take. In essence, by having latency budget information of every packet, the LBF is expected to maintain the latency and jitter within desired bounds. The processing latency required in LBF includes times 1) to lookup the latency budget information on every packet header, 2) to decide the queue position of the packet, 3) to modify the queue linked list, and 4) to update the budget information on the packet upon transmission. This processing latency, however, can affect the scalability especially in high speed core networks.¶

The ATS, the FAIR, and the PFAR utilize the regulation function to proactively prevent the possible burst accumulation in the downstream nodes. It is not clear whether the LBF can take such preventive action. If so the LBF can also act as a regulator and yield a similar latency bound.¶

5.2. Buffered network (BN)

The BN framework in this document for jitter bound guarantee is composed of¶

• a network that guarantees latency upper bounds;¶
• a timestamper for packets with a clock that is not necessarily synchronized with the other nodes, which resides in between, including the source and the network ingress interface; and¶
• a buffer that can hold the packets for a predetermined interval, which resides in between, including the destination and the network egress interface.¶

Figure 2 depicts the overall architecture of the BN framework for jitter-bound guarantees [BN]. Only a single flow is depicted between the source and destination in Figure 2. The arrival (an), departure (bn), and buffer-out (cn) times of the nth packet of a flow are denoted. The end-to-end (E2E) latency and the E2E buffered latency are defined as (bn-an) and (cn-an), respectively.¶

                            +--------------+
+-----+an +-------------+   | Network with |bn +--------+cn +-------+
| Src |-->| Timestamper |-->|   latency    |-->| Buffer |-->| Dest. |
+-----+   +-------------+   |  guarantee   |   +--------+   +-------+
                            +--------------+
        |<--------------- E2E latency ------>|
        |<--------------- E2E buffered latency ---------->|

The buffer supports as many as the number of the flows destined for the destination. The destination shown in Figure 2 can be an end station or another deterministic network. The buffer holds packets in a flow according to predefined intervals. The decision of the buffering intervals involves the time-stamp value within each packet.¶

The network in between the time-stamper and the buffer can be of arbitrarily sized network. The input traffic can be dynamic. It is required that the network be able to guarantee and identify the E2E latency upper bounds of the flows. The network is also required to let the buffer be aware of the E2E latency upper bounds of the flows it has to process. It is recommended that the E2E latency lower bound information is provided by the network as well. The lower bound may be contributed from the transmission and propagation delays within the network.¶

The time-stamper marks on the packets their arrival times. The time-stamping function can use the real-time transport protocol (RTP) over the user datagram protocol (UDP) or the transmission control protocol (TCP). Either the source or network ingress interface can stamp the packet. In the case where the source stamps, the timestamp value is the packet departure time from the source, which is only a propagation time away from the packet arrival time to the network. The source and destination do not need to share a synchronized clock. All we need to know is the differences between the time stamps, that is, the information about the inter-arrival times.¶

5.4. Frequency synchronization between the source and the buffer

Clock drift refers to phenomena wherein a clock does not run at exactly the same rate as a reference clock. If we do not frequency-synchronize the clocks of different nodes in a network, clock drift is unavoidable. Consequently, jitter occurs owing to the clock frequency difference or clock drift between the source (timestamper) and the buffer. Therefore, it is recommended to frequency-synchronize the source (timestamper) and the buffer.¶

5.5. Omission of the timestamper

For isochronous traffic whose inter-arrival times are well-known fixed values, and the network can preserve the FIFO property for such traffic, then the timestampers can be omitted.¶

Otherwise the FIFO property cannot be guaranteed, then a sequence number field in the packet header would be enough to replace the timestamper.¶

5.6. Mitigation of the increased E2E buffered latency

The increased E2E buffered latency bound by the proposed framework, from U to almost 2U, can be mitigated by one of the added functionalities given as follows.¶

1) First, one can measure the E2E latency of a flow's first packet exactly, and buffer it to make its E2E buffered latency be U. Then, by following the rules given in Section 5.3, every subsequent packet will experience the same E2E buffered latency, which is U, with zero jitter. An example of the exact latency measurement may be performed by time-synchronization between the source (timestamper) and the buffer. However, how to measure the latency is for further investigation.¶

2) Second, one can expedite the first packet's service with a special treatment, to make its latency lower, compared to the other packets of the flow. If we can make the first packet's latency to be a small value d, then every packet will experience the same buffered latency d+U, with zero jitter. Considering that the E2E latency bound is calculated from the worst case in which rare events occur simultaneously, however, the first packet's latency is likely to be far less than what the bound suggests. Therefore, the special treatment to the first packet may be ineffective in real implementations.¶

5.7. Multi-sources single-destination flows' jitter control

The BN framework can also be used for jitter control among multiple sources' flows having a single destination. When a session is composed of more than one sources, physically or virtually separated, the buffer at the boundary can mitigate the latency variations of packets from different sources due to different routes or network treatments. Such a scenario may arise in cases such as¶

• 1) that a central unit controls multiple devices for a coordinated execution in smart factories, or¶
• 2) multi-user conferencing applications, in which multiple devices/users physically separated can have a difficulty in real-time interactions.¶

The sources, or the ingress boundary nodes of the network, need to be synchronized with each other in order for the time-stamps from separated sources to be able to identify the absolute arrival times.¶