Performance Modeling of A Pro-Active Multi-Tier Dynamic Scheduling Algorithm With Threshold Deriviations
S.Shamala, M.Y. Saman, M.Othman and R.Johari
Department of Network and CommunicationFaculty of Computer Science and Information Technology
Universiti Putra Malaysia
43400 Serdang, Selangor, Malaysia
E-mail:,
ABSTRACT
The Internet has revolutionized the culture of computing and telecommunications. The emergence of newly designed real-time multimedia applications is creating a pressing need to redesign and revamp the Internet architectures, algorithms and protocols. Scheduling algorithms are an integral component in determining the performance of packet-switched networks. Extensive research have been performed to derive the ideal correlation between scheduling algorithms, resource management and admission control. In this study, two new pro-active dynamic multi-tier scheduling algorithms for output-buffered switches with a priority and threshold derivation mechanisms are proposed. The two models are designed on the basis of the predictive service model. The proposed bandwidth and buffer management schemes are performed
dynamically. A pro-active admission control algorithm is also proposed. The admission control algorithm utilizes a recursive formula to compute the probability of a packet incurring an estimated delay exceeding the stipulated service requirements. The second model integrates an additional threshold feature in the dynamic and pro-active compositions. The performance of the two proposed multi-tier scheduling algorithm is compared with the OCcuPancy_Adjusting (OCP_A) scheduling algorithm via extensive discrete-event simulation models. The simulation results demonstrate that the proposed multi-tier dynamic scheduling algorithms provide significant improvements as compared to the OCP_A.
KEYWORDS: dynamic multi-tier scheduling algorithms, pro-active admission control, modeling and simulation
1. INTRODUCTION
The nature of communication systems, the constantly evolving and growing demands of the diligent ‘on-line’ population coupled with the stringent requirements of future applications are causing a pressing need for existing Internet algorithms, protocols and architectures to be revamped and redesigned [1]. Packet-switching networks have long been dominated by the advent features of data applications. These applications advocate low delay, low packet loss, high throughput and are elastic in nature. Algorithms and protocols that were developed to realize these pre-requisites employed the ‘best-effort’ service model. This service model provided no service guarantees to the clients, allowed drastic service degradation when networks were overloaded, required no resource reservations and employed the First Come First Serve packet scheduling (FCFS) algorithms [2,3]. The requirements of low speed data applications such as telnet and file transfer protocol (ftp) were catered for efficiently via these ‘best-effort’ services.
Emerging multimedia technology used in computing and communication system offers a wide spectrum of opportunity that are equally challenging. These challenges are largely related to the characteristics and nature of multimedia traffic [4]. Among the prominent features are as follows: it is composed of multiple traffic patterns, demands stringent quality requirements, constitutes bursty network traffic, and requires differentiated service in an integrated services network. Efforts to integrate multimedia applications into traditional data architectures proved to be unsuccessful [1]. This was partially caused by the fact that traditional architectures provided single level best-effort service. Multimedia applications constitute various data, and demands diversified and stringent QoS requirements. Contradictory to data applications, this requirement implicates the need for resource reservation [5].
Many QoS based resource reservation and traffic management algorithms were derived to enable conducive platforms to be constructed for the deployments of distributed multimedia system. Pioneer schemes placed high weight-age on guaranteeing timing requirements of real-time applications in their design strategies. These schemes were oriented in guaranteeing the requested services without any compromise. Subsequently, resource reservations were done based on worst-case analysis and these reservations were maintained throughout the entire lifetime of the transmission. The Head of Line (HoL) [6], Minimum Laxity Threshold (MLT) [7] and MLT with priority jumping [8] are scheduling schemes derived from these principles. A limitation of these schemes is that service guarantees are provided at the expense of resource utilization. Eventually, with the rapid increase of packet-switching networks (i.e. Internet) users, service models required two mutually exclusive performance parameters to be supported. The parameters were to provide service guarantees whilst achieving high resource utilization. The development of these schemes were further motivated by the emergence of adaptive applications, leading to the deployment of the predictive service models [9]. In this service model, the amounts of resources allocated to a flow are dynamically manageable during the entire transmission. The reallocations of the resources are based on the actual service experienced in comparison to the requested service. Predictive schemes have proven to satisfy the requested service whilst simultaneously achieving high resource utilization.
In this paper, we propose a pro-active Dynamic Multi-Tier with Threshold and priority derivations scheduling algorithm, that is known as the DM-T2 model. This model is complemented with a pro-active admission control algorithm and is based on the principles of the predictive service model. The DM-T2 is an enhanced version of the scheduling algorithm proposed in [10], i.e. known as Dynamic Priority Oriented Scheduling (DPOS). The essence and interest of the proposed models are to investigate the fairness of the scheduler and the network centric characteristics in the presence of dynamic resource management strategy in a multi-tier environment with pro-active admission control. The DM-T2 scheduling algorithm proposed employs a priority – based service mechanism. Each outgoing link corresponds to a four-tier class output buffer. An integral component of the proposed models are the dynamically assigned bandwidth and buffer allocation integrated with a multi-tier buffering system. Priority assignments are performed based on the sensitivity of the flow towards packet loss and delay bound. The admission control algorithm deployed is to capture packets that have properties reflecting the probability of being discarded due to estimated delay breach. The performance of the proposed DPOS and DM-T2 scheduling algorithm is compared with a dynamic scheduling algorithm known as the OCcuPancy_Adjusting (OCP_A) [11].
This paper is presented in the following order. Section 2 presents the system description and model development. In this section the proposed DPOS and DM-T2 scheduling algorithm, admission control and resource management algorithms are discussed in detail. The OCP_A algorithm design and algorithms are also discussed in this section. Section 3, discusses the details of the discrete-event simulation performance analysis. The simulation results and the conclusions are discussed in section 4 and 5 respectively.
2. SYSTEM DESCRIPTIONS AND MODEL DEVELOPMENT
A network node (i.e. switch) considered in this paper is connected to an adjacent network node by a non-blocking incoming and an outgoing link. The simulation model comprises five components, which are the source model, source classifier, pro-active admission controller, dynamic resource management scheme and the threshold and priority based scheduling algorithms. This section describes each component in detail.
2.1 The DPOS and DM-T2 Model
2.1.1 Network model
A network switch with an incoming and outgoing link is considered in this research. The incoming link is assumed to be non-blocking, i.e. packets are never dropped passing through a switching fabric. Packets may be dropped in the queuing stage [12]. The outgoing link has a multi-tier buffer system, which is deployed with a dynamic bandwidth and buffer management system. The derivations of the four buffers are to impose a multi-tier (i.e. multi-class) scheduling strategy in a versatile and dynamic resource management environment. Traffic sources inheriting the same priority level posses the similar QoS requirements. The resources under consideration are the buffer and bandwidth. The management of resources is deployed based on the principles of the predictive service model, whereby the allocated resources are accurately fine-tuned to reflect the actual QoS operating level during the entire transmission life span. Each source is connected to the scheduler via an infinitely fast link and the scheduler is connected to the destination node via a 10 Mbps link. Fig.1 illustrates the network model considered.
Fig.1: Network model
2.1.2 DPOS and DM-T2 traffic source, source classifier and priority assignment model
The model used in this paper consists of N number of sources producing traffic to the same destination node. It is assumed that each source explicitly notifies the network on its service requirements via a QoS tuple <Di, Li>.
Di denotes the delay bound and Li is the loss ratio tolerance [11]. A multi-source traffic generator is implemented to denote the diversified traffic utilizing the link. Each source generates flows, which originates from one of the four traffic classes stated in Table 1. Packets are scheduled in an ascending manner based on their priority values. The definition of the flow is inherited from [13], whereby a flow is defined as a series of packets from the same source which traverse the same route from source to destination, with the same QoS requirements. Thus, each flow with the same priority level inherits the same QoS requirements. Each flow is classified based on the sensitivity towards packet loss and delay [14].
Traffic Class / PriorityClass 01: Sensitive to both packet loss and packet delay / 0
Class 02: Sensitive to packet delay but insensitive to packet loss / 1
Class 03: Sensitive to packet loss but insensitive to packet delay. / 2
Class 04: Insensitive to packet loss and packet delay / 3
Table 1: Traffic classifications
Two traffic models are used: a Poisson model to replicate the data networks traffic and an ON-OFF model for the video sources. The Poisson model has an exponentially distributed interarrival time distribution process and is used to replicate the generation of the packet arrival [15]. The probability of k arrivals in a time slot is given by equation 1. is the average number of arrivals in a slot.
The ON-OFF model is used to model bursty source. In the source model utilized the packet stream consist of arrivals with T ms intervals when the model is in the ON state [16]. There are no arrivals when the model is in the OFF state. The are no arrivals when the model is in the OFF state. The ON and OFF state durations are distributed exponentially with means 1/ and 1/, respectively.
The total number of sources for each type of traffic were 15 sources of interactive multimedia traffic (class 01), 10 sources of video / audio traffic (class 02), 10 sources of file-transfer traffic (class 03) and 15 sources of network management traffic (class 04).
2.1.3DPOS and DM-T2 Pro-Active Admission Controller
In this section, the proposed pro-active admission controller is discussed. For each k-th packet arrival from a flow that is classified as class i and admitted into buffer i (Qi), the packet’s probability of estimation delay () breach is computed. A recursive function is used to compute the estimated delay based on the buffer occupancy in the particular buffer class. Fig.2 presents the proposed delay estimation algorithm. The principle of introducing the , is to indicate the probability that of this packet being discarded due to transient delay if admission is permitted. Thus, estimating the probable delay and discarding the packet prior to admission into the buffer would prevent the packet’s blocking and propagation delay effect. Packets with (Di) properties are admitted into the buffer.
2.1.4The DPOS and DM-T2 dynamic resource management
There has been extensive research performed in the area of resource management algorithms. In this section, we focus our discussion on the proposed dynamic resource management and the next section in a multi-tier scheduling algorithm. The proposed DM-T2 scheduling algorithm integrates a dynamic resource management scheme with a multi-tier admission and scheduling algorithm. In this algorithm, packet admission is based on the proposed multi-class buffering system. The flows generated by the multiple sources (i.e. N number of sources) are classified into four distinct groups. However, the proposed algorithm is tailored to accommodate any number of priority levels. As discussed in the earlier section, prior to admission, each packet’s estimated delay () is computed via the proposed recursive delay estimation algorithm as stated in Fig.2. Packets complying with the ( < Di) relation are admitted into the respective buffer.
We assume that prior to transmission a total of N sources explicitly notify their service requirements in the form of the QoS tuple <Di,Li> and their respective traffic characterization {peak transmission rate (peak_rate) (packets/second), average transmission rate (avg_rate) (packets/ second)and minimum transmission rate (min_rate) (packets/second). Let i denote the number of classes of all traffic sources. For each flow-n from the i-th class of traffic
Delay Estimation Admission Control Algorithm1 / For each k-th packet arrival:
2 / Identify the packet’s buffer class (Qi,k)
3 / Compute the buffer occupancy () for buffer class i(Qi,k)
4 / Compute the total delay (t_delay) incurred until time t;
5 / If (() > 0)
6 / for(cc=0 ; cc <= ; ++cc)
7 / t_delay = t_delay + (simulation clock – arrival time of packet cc);
8 / estimated delay () = (t_delay) /
9 / else if (() == 0)
10 / estimated delay () = 0
11 / if ( > Di)
12 / discard packet
13 / increment packet loss statistics due to estimated delay
14 / else if ( < Di )
15 / Admit into Qi,k
16 / Increment buffer occupancy () for buffer class i(Qi,k)
Fig.2. Proposed delay estimation algorithm
determine the initial or referenced amount of resources to be reserved. The resources considered for each flow-n of the i-th class of traffic are {Bi,n = buffer for i class and flow n, i,n = service rate for class i and flow n}. The referenced amount of resources assigned are equivalent to the value of the avg_rate. Thus, i,n,ref = avg_rate i,n. is computed for the initial resource assignment. The correlation between the i,n,ref and the Bi,n,ref is derived based on equation 2.
Bi,n= Di,n *, i,n(2)
The transmissions of flows are then proceeded under the initially located resources. The reallocation of resource will be based on the observed buffer occupancy () and the observed packet loss ().
There are two distinguishing events, which alter the statistical composition of the system, the arrival of a packet and the departure of a packet from the server.
The essence of the proposed DPOS and DM-T2 scheduling algorithm is embedded in deploying a classified scheduling in a dynamic resource management algorithm. In the proposed scheme, the reallocations of the resources are based on the observed packet loss ratio for each flow relative to their buffer class. An important feature in performing a reallocation strategy is the issue of the monitoring interval. The monitoring interval implemented in this scheme is performed based on the tradeoff between accurate observation on resource consumptions and the overhead of the computation complexity.
The proposed dynamic computation of bandwidth and buffer are elaborated in Fig.3. An integral component in the criterion of reallocation is the buffer occupancy. An observation of a constantly increasing buffer size implies the inadequacy of the allocated bandwidth. Based on the actual packet loss observation (), a correlation is established between the bandwidth and the buffer allocation. In the event of a new packet from flow –n arrival and a full buffer is observed, the packet loss statistics () is analyzed. If discarding this packet will cause the violation of the requested packet loss ratio ( > Li), then certain prevention measures are invoked. Firstly, a statistical observation on the buffer utilization is performed on the lower priority buffers. If the lower priority buffers (Qi-1) are utilized below x% of the allocated buffer, then the newly arrived packet is admitted into the lower priority for a total of duration. The packet is assigned an identification field to denote a cross-tier resource sharing. Allocated buffers under the cross-tier resource-sharing scheme are maintained until the observed loss ratio for flow n class i-1 () equals to Li-1. In the event of no available buffer allocations from the lower priority levels, then the increment of the respective packet’s buffer class (Qi) is performed by an amount of y%. The percentage of increment for the x % and y % are studied for the following value {0.2, 0.4, 0.6, and 0.8} of the allocated buffer.
DPOS and DM-T2 dynamic resource reallocation1 / After monitoring interval (mtr_intv):
2 / Compute the buffer occupancy () for class i
3 / if (() == (allocated buffer for i class and flow n (Bi,n))
4 / if (observed loss ratio for flow n class i (,i,,n) == Li)
5 / Compute the buffer occupancy () for lower priority class (Qi-1)
6 / if ((i-1) < (x% of Bi-1))
7 / Add x% of (Bi-1) (Bi)
8 / else if ((i-1) == ( Bi-1))
9 / Add ( y% Bi of Bi)
10 / Increase i,n = service rate for class i and flow n by :
i,n = (Bi+y%) / Di,n;
Fig.3. Multi-Tier dynamic resource allocation algorithm
2.1.5The DPOS and DM-T2 Scheduling Algorithm
The proposed DPOS and DM-T2 scheduling algorithm has three main functions. The first is to implement a recursive algorithm to compute the highest scheduling priority buffer class. The second is to compute the transient packet with the minimal transmission time within the stipulated buffer class. The third function is to evaluate the selected packet for transmission’s incurred transient delay (). In the event of ( > Di) the packet is discarded, and a recursive search functions is executed to search in theorder of Qk=0, Qk+1, Qk+2 . . . Qk+3 . Buffers in an ascending form are accessed for packets confining to the transient delay, failing which subsequent buffers from lower priority are activated. The search function is terminated when either there are no packets pending for transmission in all the buffers (tt_transmit = 0) or when a packet with a complying transient delay is obtained (flag = 0).