Technical Overview

The goal of this work is to provide Integtrated services semantic for unicast traffic in a SCORE network. Unlike previous solutions, our solution does not require core routers to maintain per-flow state on the data or control paths. The key idea is to use Dynamic Packet State (DPS) to push the complexity from the network core to edges, without compromising the service semantic. The next two section outlines our solution for both the data and the control paths.

Data Path

On the data path, the main idea is to emulate the functionality of a network in which every node implements Jitter Virtual-Clock (JVC) with a SCORE network in which every node implements a novel scheduling algorithm that we call Core Jitter Virtual-Clock (CJVC).

Jitter Virtual Clock (Jitter-VC) Jitter-VC is a non-work-conserving version of the well-known Virtual Clock algorithm. It uses a combination of a delay-jitter rate controller and a Virtual Clock scheduler. The algorithm works as follows: each packet is assigned an eligibility time and a deadline upon its arrival. The packet is held in the rate controller until its eligible time expires. The scheduler orders the transmission of eligible packets according to their deadlines. The eligible and the deadline of the packets of a flow with reservation r are computed as being the start and finish time of transmitting the packet in an ideal network in which the flow has dedicated links of capacity r. In particular the eligible time of a packet is computed as being the maximum between

1. the packet arrival time
2. the deadline of the previous packet of the flow at the current node
3. the deadline of the packet at the previous node

Finally, the deadline of a packet is computed as the sum between the packet's arrival time and the time it takes to transmit the packet in the ideal system, i.e., l / r, where l represents the packet length.

The Figure below shows the time diagram for the first two packets of a flow along a path of four nodes. The arrival times of the first packet at each node are represented by the blue arrows, while the arrival times of the second packet are represented by the orange arrows. The starting times of the horizontal blue and orange lines represent the eligible times of the first, and the second packet, respectively, at each node. The length of these lines represent the time it takes to transmit the packet in the ideal system, i.e. l/r. For simplicity, here we assume that the propagation delay between any two nodes is zero.

The key point to note in the above Figure is that the eligible time of the second packet (i.e., the orange packet) at nodes 3 and 4 depends on the deadline of the previous packet of the same flow (i.e., the blue one). This dependency is the fundamental reason of why implementing Jitter-VC requires us to maintain per-flow state.

Core-Jitter Virtual Clock (CJVC) From the above discussion, it follows that in order to eliminate per-flow state on the data path, we need to eliminate the dependence of a packet eligible time on the previous packet deadline. To achieve this we propose a new scheduling discipline called Core-Jitter Virtual Clock (CJVC).

The key idea behind CJVC is to introduce a slack variable s and use it, instead of the previous packet deadline, to compute the packet eligible time. The slack variable s is computed by the ingress node and inserted in the packet header (see [1]). In turn, each subsequent node uses s to compute the packet eligible time by simply adding it to the previous packet deadline. Since the eligible time computed in this way is never smaller than the deadline of the previous packet (see [1] for proof), we can simply ignore the deadline. In this way there is no longer need to maintain per-flow state for computing the eligible time.

The following Figure illustrates how the eligible times of the second packet are computed under CJVC. Note that unlike Jitter-VC the eligible times are always larger than the deadlines of the previous packet of the flow at the same node.

In [1] we prove two important properties of CJVC

1. CJVC exhibits the same worst-case end-to-end packet delay as Jitter-VC. In other words the deadlines of a packet at the egress node under both CJVC and Jitter-VC are identical. Note that this is despite the fact that the eligible times and the deadlines of a packet at core nodes under CJVC can be larger than under Jitter-VC. The above two figures illustrate this point in the case of the second packet. In this way we eliminate the need of maintaining per-flow state without affecting the worst-case delay.

2. To compute the eligible times there is no need that the clocks of the routers to be synchronized. To achieve this we use the ahead of schedule parameter instead of the deadline of the packet at the previous node to compute the eligible time. Ahead of schedule represents the time interval by which the packet is sent ahead of its deadline. This is computed by each node and inserted in the packet header.

Control Path - Admission Control

For simplicity, we consider only bandwidth reservation. A simple approach to perform admission control is then to maintain the actual reserved rate and use it to determine the available bandwidth. In particular, when a request arrives, a node simply grants it if the available bandwidth, i.e., the link capacity minus the total reserved rate, is larger than the requested bandwidth. Otherwise, the request is denied. Unfortunately, this approach assumes a transaction like semantic: a request is granted if and only if all routers along the path accept it; if the request is not granted, then all nodes that have accepted the reservation have to roll back to the previous state. Implementing such semantic in a network system where reservation requests can be lost or duplicated is notoriously complex, and, in addition, requires per flow state.

By using the DPS we are able to eliminate both this complexity and the need to maintain per-flow state. The price we pay is resource utilization. This is because instead of using the exact value of total reserved rate for computing the available bandwidth we use an upper-bound of this value. In particular, we can allocate no more than 80% - 90% of the link capacity to the guaranteed traffic. However, we believe that in practice this is acceptable, as the un-allocated bandwidth can be used by the best-effort traffic.

To compute an upper-bound for the total reservation we start with estimating the total reserved rate. We first make the following simple observation. If all flows were sending at their reserved rates, estimating the total reserved rate at a core node is trivial: just estimate the actual aggregate rate. The following Figure shows two flows with reservations of 2 Mbps, and 3 Mbps, respectively. If both flows send at their reserved rates, then by measuring the aggregate rate at a core router we obtain 5 Mbps, which represents exactly the total reserved rate along the link.

The obvious problem with this approach is that usually flows do not send at their reserved rate. To get around this problem our solution is to use DPS. In particular, for each packet, ingress routers compute a virtual length and insert it in the packet header before forwarding it. Virtual length represents the number of bits that the flow was supposed to send at its reserved rate since the previous packet was transmitted. By definition, the virtual length of the first packet of a flow is equal to its actual length. Figure below illustrates the computation of the packets' virtual lengths for a flow that has a reservation of 1 Mbps. The inter-departure times between the first four packets is 1.2 ms, 1.3 ms, and 2.5 ms, respectively. The packets are flowing from left to right, and the first packet has 1000 bits.

Estimating the total reserved rate becomes now trivial. This reduces to measure the aggregate traffic rate using the virtual lengths of the packets, instead of their actual lengths.

In [1], by using this estimate we derive an upper-bound for the total reserved rate. In doing this we account for inaccuracies introduced by packet losses and duplications, and for reservation that start or finish in the middle of the estimation interval.