محدوده تاخیر برای شبکه ی سرورهای نرخ تضمین شده با تجمع FIFO

To support quality of service guarantees in a scalable manner, aggregate scheduling has attracted a lot of attention in the networking community. However, while there are a large number of results available for flow-based scheduling algorithms, few such results are available for aggregate-based scheduling. In this paper, we study a network implementing guaranteed rate (GR) scheduling with first-in–first-out aggregation. We derive an upper bound on the worst case end-to-end delay for the network. We show that while for a specific network configuration, the derived delay bound is not restricted by the utilization level on the GR, it is so for a general network configuration.

To support quality of service guarantees in a scalable manner, aggregate scheduling has attracted a lot of attention in the networking community. For example, in the Differentiated Services (DiffServ) framework [2], a required per-hop behavior (PHB) is provided on aggregate basis. However, while there are a large number of results available for flow-based scheduling algorithms, few such results are available for aggregate-based scheduling. In a recent work done by Charny and Le Boudec [6], a delay bound is derived (as Theorem 1 in [6]) for a network implementing aggregate scheduling. In the considered network in [6], each node implements aggregate class-based strict priority (SP) scheduling and the considered traffic class is the priority class which has priority over all other traffic classes. The bound derived in [6] has been adopted in [4], [16] and [17]. Also, it has been extended without proof in [1] to obtain an upper bound on end-to-end delay of an expedited forwarding (EF) packet achieved by a DiffServ network with arbitrary topology where each node can be a guaranteed rate (GR) server. However, we will demonstrate by a simple example that while the bound derived in [6] is correct under the fluid model assumption, for packetized networks, it needs to be improved. In this paper, we study a network of arbitrary topology which implements GR scheduling [12] with first-in–first-out (FIFO) aggregation. We derive an upper bound on the worst case end-to-end delay for the network using a similar method as adopted in [6]. We show that while for a specific network configuration, the derived delay bound is not restricted by the utilization level on the GR, it is so for a general network configuration. Since many scheduling disciplines proposed in the literature belong to GR, the considered network in this paper is more general than the one considered in [6]. The rest of the paper is organized as follows. In Section 2, we present the model of the considered network. In Section 3, we derive an end-to-end delay bound for the considered network using a similar method as adopted in [6]. In Section 4, we review some related work. Finally in Section 5, we conclude the paper.

Aggregate scheduling has recently attracted a lot of attention in the networking community because of its potential scalability in support of quality of service guarantees. In this paper, we studied a network of GR servers with FIFO aggregation and derived a bound on end-to-end delay for the network of arbitrary topology. While our work was motivated by [6], we have improved the bound in [6] and have extended the derivation to networks of GR servers. In addition, we have shown that while the derived delay bound is not restricted by the utilization level on the GR for a specific network configuration where at every node, the sum of all incoming links’ speeds is less than the GR at the output link, it is so for general network configurations. The results of this paper may be used to derive edge-to-edge delay bound in a DiffServ network. There are a number of issues to be investigated. As discussed in above, with FIFO aggregation, the derived delay bound is in general restricted by the utilization level of the offered rate. By taking into account the actual network topology, the analytic approach in this paper may be extended to obtain better performance bounds. In addition, some other aggregation methods such as those introduced in [21] may be designed to overcome the restriction caused by FIFO aggregation. These are research directions to be explored.