Abstract: The packets entering a DiffServ network experience a quality of service based on the per hop behaviors defined for different aggregates. An aggregate is a user defined entity which usually includes network traffic requiring similar QoS treatment. The policies thus defined do not ensure that the network is not congested. For this it is proposed to make use of an endpoint admission control strategy with inter-packet delay estimation as the admission decision criteria. The proposed scheme admits a flow of packet stream only when sufficient network bandwidth is available. The simulation results show better performance in terms of higher bottleneck link utilization and a stable, moderate average and peak inter packet delay.
INTRODUCTION
In this study, a probing based endpoint admission control scheme operating on inter-packet delay is proposed. The proposed admission control when integrated with DiffServ based IP network offers a better Quality of Service (QoS) to the data flows admitted in to it. In this design, an end host first probes the network by sending probe packets at the rate equal to the peak rate of the flow to be admitted in to it. At the receiver when the weighted average delay experienced by these probe packets is found to be within a threshold the flow is admitted else rejected.
Traditionally Internet was designed for data traffic and was called as a ‘best effort’ network. The sender fully relied on the network for successful delivery of packets to the destination. With rapid expansion of Internet, newer applications requiring a greater degree of Quality of Service (QoS) were developed and deployed on it. These time sensitive applications demanded strict control in packet loss rate, inter-packet delay and jitter. To provide such QoS assurances, IETF proposed two broad models: DiffServ and IntServ.
QoS MODELS
IntServ provides strict QoS to the flow of packets by reserving network resources across the path before admitting them (Lu and Faynberg, 2003). It results in a per flow state maintenance at the core routers. This makes the model non-scalable as it imposes additional burden on routers, whose main activity is to forward the packets at the earliest and also through a shortest possible path.
DiffServ is a solution that has been proposed to overcome the scalability problem of IntServ. This service model proposes to provide QoS to flow of packets by first classifying them into different aggregates. An aggregate is usually a user specified entity. It can be either based on traffic characteristics, users, organization etc. An aggregate is identified through the TOS (Type of Service) field of an IP header also now known as DSCP (Differential Service Code Point) field. The edge routers mark these DSCP according to the aggregate, to which the packets belong to. These aggregates are then treated based on policies called as PHB (Per Hop Behaviors) defined at each hop across the path. Packet forwarding based on such limited number of aggregate classification does not over burden the core routers. The per-hop behaviors involve metering, shaping and policing. The focus here is on enforcing an SLA (Service Level Agreement) between the user and the service provider. It requires a mapping between DSCP to PHB. In the absence of such association, packets are mapped to the default BE (best effort) service model of the IP network as the PHB.
The two most popular PHB used in DiffServ are: Assured Forwarding (AF) and Expedited Forwarding (EF) (Giacomazzi et al., 2003). The former marks the out of profile packets to a high drop priority policy and forwards it. At the time of congestion these are the packets dropped first, while the later drop all out-of-profile packets. This prevents a router queue from growing beyond a threshold, thereby providing a low delay, low-jitter service, called as “premium service”. It does not use RED principle at the routers. A flow of packets exceeding their contract rate is treated as out-of-profile.
The above two modes of providing QoS to flow of packets in DiffServ can be treated as providing QoS based on “outside view of network”. Such QoS provisioning try to only confine the flow characteristics according to the SLA and not on the internal state of the network, which we call as “Inside out View” of providing QoS. To provide such QoS we propose to use the admission control strategy along with DiffServ network.
RELATED WORK
In the literature several such QoS models and admission control strategies have been proposed. Vogt (2002) provided a detailed overview of different QoS schemes is provided. Centinkaya and Knightly (2001), propose an admission control technique involving only the egress routers for QoS provisioning. Bianchi et al., (2000) introduces an admission control scheme which determines admission decision through probing rate. Breslau et al. (2002) provide a detailed review on the performance of the various MBAC. Más Ivars and Karlsson (2001) present a PBAC scheme for controlled load service. Li et al. (2003) describe a model which integrates an admission control algorithm with DiffServ service. In this the admission decision is based on the calculation of mean explicit rate and queue length for each class of service. Elek et al. (2000) investigate an admission control scheme with FEC.
One such scheme which offers relatively better scalability is the endpoint admission control technique introduced in Breslau et al. (2000). This scheme first probes the network by sending probe packets on an end-to-end basis. The flow admission decision is then based on detection of probing packet losses. If the probe packet drop rate is beyond a threshold, the flow is not admitted. The probe packets are usually sent at a constant rate (CBR) equivalent to the peak rate of the flow to be admitted. This scheme does not take into consideration of the end-to-end delay and jitter experienced by the probing packets at the receiver for the admission decision.
Qiu et al. (2001) suggest that at times of heavy congestion, packet drop based admission criteria is enough. However, when the network is lightly congested or not congested, packet drop ratio does not reflect the correct internal state of the network.
In a later research Bianchi et al. (2002) discusses a similar approach of providing admission control based on inter-packet delay called PCP-DV (Phantom Circuit Protocol-Delay Variation). IP telephony voice traffic based on Brady two states (ON/OFF) model is the source traffic used in their simulation. Their algorithm fixes an upper threshold and a lower threshold based on the initial inter-packet delay observed to admit a flow.
We present, our admission control algorithm operating on the estimation of average delay for a wide range of data source models. It takes flow admission decisions based on the average inter-packet delay experienced by the probe packets, which must not exceed the threshold. This makes the admission decision to rely on a large number of sample values rather than on a single value. The proposed algorithm is found to provide a better link utilization and admission rate in comparison to PCP-DV and also with respect to the conventional packet drop based admission control algorithm.
PROPOSED ADMISSION CONTROL ALGORITHM
A detailed description of the proposed admission control algorithm based on the estimation of average inter-packet delay is shown in Fig. 1.
A flow, on arrival, is not admitted directly into the network. It initiates a probe packet stream. The probing rate is set equal to the peak rate of the flow to be admitted. Such probe packets will encounter an inter packet delay Ds at the sender side. These packets are then required to be delivered to the receiver with the same interval. If Dc(k) represents the jitter measured between kth and (k-1)th packet, ‘α’ the tuning parameter in the range [0,1] then the estimated average jitter is given by Djitter(k). This estimated jitter adds a fraction of the new measured jitter Dc(k) to itself, retaining a fraction (1-α) of past history Djitter(k-1). A smaller ‘α’ value will allow the Djitter to adapt more swiftly to sudden increase in network delay.
| Fig. 1: | Average inter-packet delay estimation based admission control
algorithm |
This has made us to choose α equal to 0.25. Instead of using the last measured inter packet delay (jitter) to make admission decision, it makes sense to use an exponential averaging of a series of measured inter packet delays to eliminate random fluctuations.
In the admission control algorithm, the receiver fixes the admission decision threshold DT at 3 ms more of Ds. It is being fixed to ensure a conservative statistical delay bound of 3 ms on each hop for every probe packet stream (Gopalan, 2003). For real time traffic sources especially voice the end-to-end delay should be less than 150 ms. Normally the end-to-end delay comprises of the following fixed components, an encoding delay of 20 ms, packetization delay of 30 ms, traffic smoothing delay of 40 ms at ingress, switching delay of 40 ms. The remaining 20 ms form the variable queuing delay. If there are approximately 5 hops between the source and receivers, this gives an average queuing delay budget of around 4 ms per hop.
The delay estimated during the entire probe duration (based on EWMA-Exponential Weighted Moving Average) when found to be within the threshold, the flow is admitted. On successful completion of PLT (probe life time) during which the estimated delay experienced by the probe packets has not exceeded the threshold, the flow gets admitted. If at any point of PLT the estimated delay experienced by the probe packets exceeds the threshold the probe flow gets aborted thereby preventing the flow from entering into the network. This helps to make quick admission decision and reduce the probe duration at the times of delay exceeding the threshold earlier itself. A longer probing duration would only increase the flow admission time.
The proposed algorithm is inherently stable. Large arrivals of flow admission requests (probing requests) will only make them starve and will not thrash the network. It is because probe packets are of lower priority than data packets.
ADMISSION CONTROL EXPERIMENTS
Here we evaluate the performance of the proposed admission control algorithm via simulation and compare it with other variants. The simulations have been carried out using network simulator NS2 in a Pentium PIV machine with 256 MB of RAM.
A simple dumbbell network with a single bottleneck link of 10 Mbps configured as core link of the DiffServ network is considered as our simulation network. All links connected to the core link are also considered of 10 Mbps bandwidth and are assumed to have the same propagation delay of 20 ms. Buffer space of up to 250 packets has been provided in the core link. It is been fixed based on a rule-of-thumb attributed to the router buffer sizes (Appenzeller et al., 2004). Also to determine the effect of this large buffer size, we even carried out our simulation with the bottleneck link having a buffer size of 10 packets.
It is required that the intermediate network router queuing system must be able to differentiate data and probe packets. For this data traffic packets are marked with a particular DSCP to make them belong to one aggregate having a higher priority in comparison to the probe packets belonging to another aggregate with a lower priority (Breslau et al., 2000). It is done so that probe packets do not disturb ongoing data flows. Probe packets are also set to small size, thereby enabling the probe flow to generate a large number of packets (Más Ivars et al., 2001). In the simulation a Poisson process having an inter-arrival time of 300 ms models the flow arrival from 2 of the sources. The total offered load on the bottleneck link is 1.5 times of its capacity. The flows admitted have an exponential lifetime with an average of 25 sec. The entire simulation is run for 500 sec.
On arrival of a flow, probe packets are generated at a constant rate equivalent to the peak rate of flow to the destination host. The probe packets generated for each of the incoming flow have a maximum lifetime of 500 ms of CBR characteristics. The probe packet size has been fixed at 50 bytes. The probe flow packets would then either abort or complete. A probe flow gets aborted before PLT only when the decision variable (estimated average delay) exceeds the threshold limit, thus not admitting the flow in to the network. During the entire PLT if the decision variable value is within the threshold limit, the flow would then start and enter the network according to its characteristics as specified.
Table 1 indicates the different data flow sources used for simulation. They are identical to the one used by Breslau et al in their experiments (Breslau et al., 2000). The packet size from these sources has been fixed at 125 bytes. EXP and POO represents the exponential and pareto ON/OFF sources, respectively.
The various metrics used to determine the effectiveness of the proposed admission control algorithm against are i) Average utilization of the bottleneck link. ii) Blocking probability iii) Average and peak delay experienced by the data packets.
When the admission decision is based on the estimation of average inter-packet delay, the probe packets at the receiver must not experience a jitter greater than DT; when using PCP-DV two thresholds, the Lower Threshold (LT) fixed at (Ds - 3 ms) and Upper Threshold (UT) fixed at (Ds + 3 ms) is used to make admission decision.
| Table 1: | Data flow sources |
| Table 2: | Performance evaluation of the admission control algorithms
when the bottleneck link router buffer size is fixed equal to 200 packets |
| Table 3: | The average utilization of the bottleneck link by the effective
data flow packets and the peak delay experienced by them when bottleneck
router buffer size is fixed equal to 10 packets |
Thus for the flow to get admitted, the probe packets must experience a jitter only within this threshold range.
Simulation results of the proposed algorithm against PCP-DV and packet loss based admission algorithms are tabulated in Table 2 and 3. The effect of the bottleneck link router buffer size on the admission control algorithm is also highlighted in the tabulation. For a packet loss based admission control algorithm, the decision of aborting the probe flow (or) to allow it to complete at 0.5 sec the PLT is taken based on the packet drop perceived by the receiver. A probe flow is aborted even when one packet is lost (dropped) during the PLT, otherwise continued and completed indicating successful admission of the data flow.
RESULTS
Table 2 indicates the performance of the different admission control algorithms when the bottleneck link is provided with a buffer space of 250 packets. With such a buffer space the bandwidth utilization of the bottleneck link by data and probe packets are shown in Fig. 2 and 3, respectively. Similarly Table 3 show the performances when the bottleneck link is provided with a buffer space of 10 packets which is less than 1% of the thumb-rule used to fix the intermediate router buffer size. With such a buffer allocation Fig. 5 and 6 shows the bottleneck link utilization by data and probe packets, respectively.
In both cases higher bottleneck link utilization is achieved by using the proposed algorithm for admission control.
| Fig. 2: | Data flow utilizing the bottleneck link with 250 packets
of buffer space |
| Fig. 3: | Bandwidth utilization by probe flow packets when link buffer
space is fixed at 250 packets |
| Fig. 4: | The average delay experienced by the data packets of the admitted
flow when the link is provided with 250 packets of buffer space |
It is because the proposed algorithm is found to have a lowest flow blocking rate when compared to the other two algorithms.
The packet losses are difficult to be estimated in a short interval (Qiu et al., 2001) resulting in a longer time to notify the receiver of the probing status. This causes a larger probe packet flow when probing is initiated with packet loss as admission decision variable. It is also a reason for lower bandwidth utilization by the data packets.
| Fig. 5: | Bottleneck utilization by the admitted data flows when the
link is provided with only 10 packets of buffer space |
| Fig. 6: | Bottleneck utilization by the probe packets when link buffer
space is fixed as 10 packets |
| Fig. 7: | Average delay experienced by the data packets of the admitted
flows when the bottleneck is provided with a buffer space of 10 packets |
Approximately 10% of the bottleneck link bandwidth is occupied by the probe packets when packet loss based admission control algorithm is used with both 250 packets and 10 packets of link buffer space. For both cases it is double when comparing to the delay based admission control algorithms. An interesting observation that has been made is that the proposed admission algorithm favors admitting higher rate flows than the lower rate flows. From the Fig. 4 and 7 it can be seen that the peak delay experienced by the data packets using the proposed algorithm is comparatively less than other two admission control algorithms. The average delay when computed is uniformly at 6.5 m sec for all the above varieties of admission control algorithms.
The above experiment results highlights how the proposed admission control algorithm when integrated with DiffServ network ensures QoS provisioning both from the end user and the network administrator perspective. A higher utilization of the bottleneck bandwidth by data packets rather than by probe packets signifies a better QoS provisioning in the network administrator perspective. Larger the probe packets larger is the network overhead and lower is its effective utilization. By use of the proposed admission control a stable peak inter packet delay is being experienced by the data packets irrespective of change in bottleneck link buffer size. This ensures a QoS provisioning from the end user perspective. It also highlights the stability and robustness of the algorithm.
CONCLUSION AND FUTURE WORK
The proposed endpoint admission control algorithm based on the estimation of average inter-packet delay provides an “inside out view” to admit a flow. It enables a flow to know the current internal state of network more accurately before getting admitted. Thus it ensures that the network can satisfy the required SLA. The future work remaining with the proposed admission control algorithm includes:
| • | Validation of the algorithm in a multi-hop scenario, having very frequent route changes. |
| • | Validating the algorithm in a multicast scenario. |
| • | Determining the relation between the probe lifetime and the flow duration |