Packet Scheduling Algorithms Literature

Packet Scheduling Algorithms Literature Abstract- This paper discusses two selected research papers that proposes two different packet scheduling algorithms that focuses on promoting higher throughput and fairness. The two algorithms are Modified Packet Prediction Mechanism algorithm which is a revised version of the current packet prediction mechanism algorithm and the second is prioritized fairness packet Scheduling algorithm. Chapter 1 Introduction Mobile communication has come a long way and has been through multiple generations. Starting from a mere mobile radio telephone used in the old ages to sending text based messages and now fourth generation long term evolution supporting devices which are capable of streaming high bitrate videos, providing us with richer content and more connections at faster rates just from our handy mobile devices. Long term evolution structure adequately utilizes the assets by dynamically scheduling the frequency and the time space of users. And that is possible through long term evolution downlink scheduling which is accountable for the allotment of radio resources mutually throughout mobile devices. Implementing packet scheduling is crucial as it effects the performance by assigning radio resources suitably. 1.1 Problem Statement As the usage of mobile data, online mobile gaming, video streaming and other online applications started to grow, the delivery of packets, data transmission and speed has to be improved. While this is possible through the introduction of long term evolution, the quality and capability to has to be improvised by achieving high throughput connectivity which equates to successful data transmission and also fairness, for improving the distribution of the signal. Implementing a downlink scheduling algorithm is sensitive as if takes into effect the throughput, fairness, rate conditioning and so on. Among them, each has its own perks and features but newly or modified algorithm are being proposed and implemented periodically. As such, the modified packet prediction mechanism algorithm is proposed in order that through simulation has proved to perform better in terms of throughput and fairness. Also submitted is the prioritized fairness packet scheduling algorithm with the improvements in. Chapter 2 Literature Review 2.1 Mobile Network During the earlier decades, facilitating limited services like voice call is the main focus in developing mobile networks. Additional services like short message service was introduced by Global System for Mobile Communication. The craving of user in using mobile internet is the main motivation in development of Universal Mobile Telecommunication System, Enhanced Data rates for Global System for Mobile Communication Evolution known as EDGE and finally, General Packet Radio Services. In 1980, the first-generation analog cellular technology Advanced Mobile Phone Service in short form known as AMPS were introduced. Advanced Mobile Phone Service uses distinct channels or frequencies for every Frequency Division Multiple Access. Therefore, it cause Advanced Mobile Phone Service required huge bandwidth for a higher number of consumer. Second Generation offers digitally encrypted voice data and effective usage of available bandwidth. Short message service was introduced in this generation as a form of data services. Global System for Mobile Communication cellular technology is the foundation for other basis cellular networks. Base Transceiver station controls the cells in Global System for Mobile communication. Mobile Station is being served by each Global System for Mobile Communication cell while Base Station Controller monitors a number of Base Transceiver station. Global System for Mobile Communication network is categorized into four basic sub system which is Mobile Station, Base Station Subsystem, Core Network and External Network. Mobile Station consist of Security Information Management and terminal equipment. Base Station Subsystem consist Base Transceiver station, and Base Station Controller. Providing radio access and Core Network connection to Mobile Station is the main function of Base Station Subsystem. Core Network consist of Mobile Switching Station, Visitor Location Register, Home Location Register, Authentication Center and Operation and Maintenance Center. Main role of core network is to provide billing, transport functions, mobility management, user database such as user location and information about user and so on. External Network is where user can connect such as Public Switched Telephone Network or any other Global System for Mobile communication network. Circuit switching is used for communication in Global System for Mobile Communication networks. User start to demand for high data rates when mobile evolves. Therefore, General Packet Radio Services was introduced. General Packet Radio Services offers new services like web browsing provides packet switching hence increase data rates up to 114 kilobits per second. Enhanced Data rates for Global System for Mobile Communication Evolution is evolution of Global System for Mobile Communication after General Packet Radio Services where provides data rate up to 384 kilobits per second. Shifting the modulation of Global System for Mobile Communication from GPSK to 8PSK is the reason of this achievement. Technology Modulation Switching Method Access Scheme Data Rate (kbps) Services Global System for Mobile Communication GMSK Circuit Switching TDMA/FDD 9.6 to 14.4 Voice, short message service. General Packet Radio Services GMSK Packet Switching TDMA/FDD 115 Voice, short message service, Web Browsing Enhanced Data rates for Global System for Mobile Communication Evolution GMSK, 8PSK Packet Switching TDMA.FDD 384 Voice, short message service, web Browsing Global System for Mobile Communication overview Third Generation Partnership Project develop and maintain Universal Mobile Telecommunication System. Providing new services with better quality of services, better spectral efficiency and increasing data rates was the main aim in the Universal Mobile Telecommunication System development. Wideband Code Division Multiple Access is used as an access in Universal Mobile Telecommunication System. Bandwidth of 5 megahertz is used for downlink and uplink traffic. Universal Mobile Telecommunication System Terrestrial Radio Access Network (UTRAN) is the radio access in Universal Mobile Telecommunication System which consist Radio Network Controller (RNC) and many base stations which known as NodeB. Both circuit and packet switching method is supported in Universal Mobile Telecommunication System. Packet switching is mainly for data services like file transfer, web services while circuit switching is for voice traffic. High Speed Downlink Packet Access known as HSDPA and High Speed Uplink Pack et Access in short form known as HSUPA is the evolution of Universal Mobile Telecommunication System. This Evolution focused in reducing latency, increasing system capacity and data rates. High Speed Downlink Packet Access increases downlink data rates up to 14 Mbps while High Speed Uplink Packet Access increases uplink data rates up to 5.76 Mbps. Technology Modulation Data Rates TTI Time Latency ms Advancements Universal Mobile Telecommunication System BPSK 384 kilobits per second downlink 128 kilobits per second uplink 10 ms 150 Scheduling performed by Radio Network Controller High Speed Downlink Packet Access High Speed Uplink Packet Access QPSK,16 QAM, 64 QAM QPSK 14.4 megabits per second in downlink 5.76 megabits per second in uplink 2 ms 2 ms, 10 ms 100 100 AMC,HARQ, Scheduling at NodeB, MIMO HARQ, Scheduling at NodeB Third Generation overview 2.2 Long Term Evolution Introduction The idea of Long Term Evolution was originally developed due to the need of a technology which is possible to support IP based mobile technology hence, through this, providing features same as broadband connection. The difference between third generation and Long Term Evolution is that third generation is supports both packet and circuit switched while long term evolution supports packet switched and IP based services. Long Term Evolution need to have certain requirements in order to fulfill its goals such as able to provide data rates up to 50 megabits per second for uplink and 100 megabits per second for downlink, higher capacity of need to be provided compare to High Speed Downlink Packet Access, supporting multiple frequency bands, operation need to be cost effective and so on. 2.3 Architecture of Long Term Evolution Four main domains are being used in the architecture of Long Term Evolution which is UE (User Equipment), E-UTRAN (Evolved Utran), EPC (Evolved Packet Core Network) and finally, services. A diagram is illustrated below to show how this four domains are being used in LTE architecture. LTEArchitecture 2.3.1 UE (User Equipment) Device that are being used for communication purpose by end user are called user equipment. Each device has a unique identity module called Universal Subscriber Identity Module. The module being used for identification process, authorization and security for radio transmission. Moreover, the user equipment has other functions as well, such as for an instance mobility management, UI (User Interface) between end users, but mainly it provides communication platform and communication link which can be set up, maintained or removed depending on the user need. 2.3.2 E-UTRAN (Evolved Utran) Evolved NodeB also known as eNodeB is the only existing node in Evolved UTRAN. Radio related activities in the LTE system are being performed through a radio base station located within the network through this evolved NodeB. Besides that, a path is created from the User Equipment to Evolved Packet Core Network with the help of evolved NodeB. Through this, data passing can be done within the ratio connection and IP based Evolved Packet Core Network network connections and evolved NodeB becomes a transmission point to various radio protocols pointing towards the User Equipment. After the data is relayed, Evolve Packet Core Network then performs functions such as ciphering and deciphering to the UP data. In details, activities related to managing radio resource including allocation of the resources based upon on prioritization and traffic scheduling depending on the Quality of Service requirements are also one of the responsibility held by evolved NodeB. Besides that, evolved NodeB is also held responsible for the management of mobility which includes activities such as analyzing radio signal measurements performed by the User Equipment and comes up with same measurements as well. Furthermore, evolve NodeB also handles a new users request for a new connection, the evolved NodeB will route the request to mobility management entity using the previous User Equipment that was connected earlier and if there isnt any information regarding the routing then a new mobility management entity will be selected. The User Equipment can only be connected to one evolved NodeB where else the evolved NodeB is expected to support multiple users. The handover process can be only done if an evolved NodeB is connected to its neighbor, which is another evolved NodeB. A User Equipment can be only assigned with one mobility management entity and serving gateway but multiple mobility management entity and serving gateway can be connected a certain evolved Nod eB. 2.3.3 EPC (Evolved Packet Core) Evolved Packet Core uses different kinds of elements to operate. The elements are Mobility Management Entity (MME), Packet Data Network Gateway (P-GW), Serving Gateway (S-GW) and Policy and Charging Resource Function (PCRF). Mobility management entity is the core of evolved packet core. A direct connection is established with user equipment through mobility management entity and this connection will become the main control channel for the user equipment and network. There are many activities conducted by the mobility management entity such as, authentication of the user equipment. Authorization is provided by the mobility management entity as the user equipment is being newly registered to a network. Other activities such as tracking the available user equipment in a certain area is considered to be the main function for mobility management entity and so on. Responsibility of a serving gateway is resources management and provide resource requested from mobile management entity and so on. In details, the request comes from user equipment due to modification of bearers and so on. Besides that, information passing is also done through the serving gateway which occurs among packet data network gateway and evolved NodeB. Another element that is being used is packet data network gateway. This element is being used mainly for IP allocation to the user equipment. Moreover, bearer switching is done at this element when the user equipment transferred at one serving gateway to another serving gateway at different area. Lastly, the policy and charging resource function takes the decision regarding service handling according to the quality of service. 2.3.4 Services A variation of services can be done such as operator services and so on. In order to run the services smoothly many sub systems are needed, plus logical nodes as well. 2.4 Long Term Evolution Access Scheme The access schemes are used in long term evolution can be divided into three different types which is orthogonal frequency division multiple access, single carrier frequency division multiple access and finally, multiple input and output. Each of these scheme has a certain functions and responsibility to follow. 2.4.1 OFDMA (Orthogonal Frequency Division Multiple Accesses) This scheme is used in downlink in the long term evolution. This scheme was originally modified from Orthogonal Frequency Division Multiplexing. The difference between the modified version and original version is that, orthogonal frequency division multiple accesses allows multiple users by allocating subcarriers dynamically to a variety of users while in the original version, a signal will be divided into a number of band channels which are orthogonal to one and another and consist of different frequencies. Orthogonal frequency division multiple access is used for many reasons, one of it is compatibility. This scheme is compatible with many kind of recently developed antennas and receivers. Moreover, efficiency is another reason this scheme is chosen. Efficiency in handling many bandwidths, performance including spectral can be achieved through this scheme. Originally, Orthogonal Frequency Division Multiplexing was created in the 1950s but was not popular back then due to greatest number of systems were running on analog technology during that time which made the implementation of this scheme hard and less effective. As the era grew, the use of these scheme has increased as it was much more affordable and implementable as well for the end user due to growth of digital technologies. 2.4.2 SC-FDMA (Single Carrier Frequency Division Multiple Access) As mentioned above, the Orthogonal Frequency Division Multiplexing is only being used for downlink in long term evolution where else for uplink the Single Carrier Frequency Division Multiple Access will be used. This is because of multiple carrier which is being utilized in Orthogonal Frequency Division Multiplexing leading it to be less efficient especially when it comes to power consumption as power will be a serious issue in mobile devices. This problem can be avoided by the use of Single Carrier Frequency Division Multiple Access for the uplink process. Advantages of this scheme is that it will be much more robust in contrast to multi path and hence, a low peak ranging to average is being provided. 2.4.3 MIMO (Multiple Input Multiple Out) The Multiple Input Multiple Out scheme can be implemented in both downlink and uplink in long term evolution. A high data rate can be accomplished by using both Orthogonal Frequency Division Multiple Access and Multiple Input Multiple Out as diverse subcarriers will be cast-off. Furthermore, spatial multiplexing meaning that the use of many antennas for transferring diverse data streams and signal processing on the data streams leading to an increase in the data rate is also being done in this scheme. Besides that, even additional functionality such as transmit diversity meaning that relaying the equal signals but originated from different antennas and finally, beam forming as well can be performed in this scheme. 2.5 PRB (Physical Resource Block) According to the base station scheduler, a resource block will be dispersed to the user equipment. This portion is to be considered as the smallest allocation. Moreover, depending on the bandwidth and number of Orthogonal Frequency Division Multiple Access symbols, resource grid will be created in the downlink transmission. A sole subcarrier will be symbolized in each box of the grid and called as resource element and hence automatically representing a symbol. Not only will the user data be stored in the resource grid but also reference signal as well. Resource Block Resource block which is subtypes of a resource element in Long Term Evolution network. A resource block consists many channels and different types of data flows are transferred in Long Term Evolution network. The Long Term Evolution network does not have any standard scheduling method. There are different types of method is exists in scheduling but it based on the researcher. One of the command method that been used in scheduling mechanism in Long Term Evaluation is Dynamic scheduling that used for providing Quality of service and efficiency. Dynamic scheduling is used in downlink scheduling. The purpose of the dynamic scheduling is to control the channel of some of the sign indicated. Evolved NodeB is taken the main role in downlink scheduling. As mention earlier the function has been explaining in additionally Evolved NodeB is one of the import factor for performing scheduling. Evolved NodeB is performing scheduling mechanism in Long Term Evolution network for downlink scheduling mechanism and it managed resource block in the resource elements. Nowadays many users are forwarded toward to the technology so that there were required Quality of Service to the specific application its main reason why scheduling is needed. In Long Term Evolution network have a combination of multiple single cells is connected. The user interaction is connected to the Evolved NodeB with single cell but user equipment is contained N number of members. During the process of uplink scheduling, some packet or data may be lost, one of the reason is a delay in the parameter. The delay queue packet is grouped into a single logical channel and downlink scheduling of evolved NodeB is also holding buffer. In the downlink scheduling, each buffer is related to the user equipment and the user equipment is connected to the evolved NodeB. The evolved NodeB has broadcast the specific data traffic of loaded queue. The main reason of scheduling is to increase the performance of throughput and fairness. And reduce packet loss. Scheduling algorithms for evolved NodeB is not standardized but it based on the used Quality of Service of a user; network provider or service provider is analysis the problem and identify new algorithms and solve the user problem. There different type of scheduling method exists in downlink scheduling. Although there are many algorithms had been discovered in the past yet fair scheduling and opportunistic scheduling is widely been used. Firstly, the Fair Scheduling scheme is one of the algorithm that been used for downlink scheduling it can give least data rate to every user and reduced the inertness. Fair Scheduling scheme is used in real time application for example video conference and voice over IP. Fair Scheduling scheme is functioned as least required information rate all the more successfully. Most of the scheduling algorithms are based on these key factor. Secondly Opportunistic Scheduling schema is another scheduling scheme is commonly been used in LTE networks. The Opportunistic Scheduling schema is explained that due to multiple users multiple users scattered around different location number of channel each user gets may vary. Users can experiences better productivity to correct setting of frequency and time. Multi-user can cause the problem to mobile radio channel because different user come from the various environment and they connected with each other. By utilizing multi-client differing qualities system, this radio channel trademark can be used for giving better information rates. The network provider must choose better dynamic scheduling which is included in downlink scheduling. By using the best dynamic scheduling the user can experience better performance in throughput based on the channel it can be done based on the specific spectrum. Therefore, Opportunistic Scheduling schema also have some drawbacks. The Opportunistic Scheduling scheme is not able to provide the better quality of service to the user and subsequently providing poor performance on fairness to the client. This is the reason why the multiple users are cannot transmit the data to their specific client and also another reason is their channels is not good enough. 2.6 Quality of Services in LTE As years pass by the demand for mobile usage has grown exponentially the people now are capable doing a wonderful thing through their smartphone. The advancement of technology has opened up many new applications and uses. This is the reason why people is demanding quality of service to the network provider. The Quality of Service two also deals with real time application such as voice over IP. Then it also deals with the large scale of the networks. In the long term Evaluation network channel is the mediator for the user equipment and evolved NodeB. In the Long Term Evolution network, there has logical barrier connection between two endpoints. During the data transmission between the user equipment and packet data network gateway has virtual have Transmission Control Protocol connection-oriented connection. During the data transmission between the two endpoint data link layer is involved in transporting the Quality of Services to the user. The Quality of Services can be divided into multiple traits which are bit rate, delay, and reliability. Different type of barrier is producing different kind of result for Quality of Services such as these two types of radio channel, for an example using Lee and Ali, where Lee is capable of enduring a larger packet loss and very low latency but Ali do not care regarding the low latency and hence, he is willing to receive the low latency. This example requires the two radio channel and each radio channel is configured with some packet loss and low latency based on the Quality of Service as requested by the user. There are two types of barrier in the Quality of Services in Long Term Evolution network. What is the minimum guaranteed bit rate barrier and non-guaranteed bit rate barrier? Minimum guaranteed bit rate barrier is real time application and it uses least number of information rate that should be ensured. An example of minimum guaranteed bit rate barrier is that the voice over IP, videoconference, stream gaming, streaming video and video call. Non-guaranteed bit rate barrier are used in application but it does not require specific type of bit rate. For the non-guaranteed bit rate is not specific so the bandwidth has to be set for the networks. An example for the non-guaranteed bit rate is file transfer, games and web searching, which is also known as a non-real-time application. The Quality of Services of a class identifier is represented each of the mobile network barriers which analysis by a Quality of Service characteristics. The Quality of Service of Class Identifier is possible to be divided into a standardized factor which is delay, loss rate and priority. The Quality of Service of the Channel Quality Indicator is divided into 9 Quality of Service of Class Identifier characteristics. Below the table shows the Quality of Service of Class Identifier characteristic with the attributes shown. 2.7 Radio Resource Management Therefore, in the Long Term Evolution network, architecture consist of only one node that is evolved NodeB which is intermediate between the user and the main network. Radio resource management is performing is the function on evolved NodeB. Radio resource management performing First In First Out queue method for packet scheduling. Radio resource management also interacts with downlink scheduling for packet delivery. However, the radio resource management is work with Channel Quality Indicator, transmission time travel and media access control address. 2.8 Scheduling mechanism in LTE In the Long Term Evolution network, multiple user interactions are the main function. Then, Long Term Evolution network data and packet are transferred among multiple users based on the user requirement and Quality of Service. In additionally, downlink scheduling is used metric for transmitting the data and packet. Metric is the method of calculation which priority for the resource block. The calculation is based on the data flow and the resource allocation. 2.8.1 Round robin scheduling Round Robin scheduling is mainly based on time quota. Each process is handled and entertained fairly. Round robin algorithm does not rely on the priority of each task. Round Robin algorithm is easier to implement, simpler to handler and starvation free. Each task is given a time quantum. Each process or task is terminated once the allocated time quantum expires. Round robin produces maximum minimum fairness. If the size of each packet of data equally distributes, then packet that queued longer in the waiting queue is given priority. This is not applicable for data in different sizes. Implementation of round robin algorithm results in poor throughput. This is because round robin algorithm do not consider the Channel Quality Indicator. This causes the performance of throughput drop significantly as its the quantity of bits need to be delivered is not rely with the instantaneous downlink signal to noise ratio. Round Robin is one of the mostly used algorithm in packet scheduling in most systems. Round Robin Scheduling Flow Chart 2.8.2 Best Channel Quality Indicator From the name itself we knew that this algorithm chooses the Best Channel Quality Indicator. This algorithm is primarily used to allocate resource blocks with the good radio link environments to the user. Resource block that been appointed by the algorithm comes with the highest Channel Quality Indicator in the resource block compared to other blocks. The Channel Quality Indicator will be transmitted to base station. Base station will perform the Best channel Quality Indicator. Base station will transmits the reference downlink pilot (signal) to the terminal. These downlink pilot will be utilized by the user equipment for the calculation of the Channel Quality Indicator. The higher the value of Channel Quality Indicator, the Best Channel Quality Indicator it is. The Channel Quality Indicator is a 5 bit information which ranges from 0 to 30. Terminals that located far off from the base station most unlikely will be scheduled. The Channel Quality Indicator depends on the terminals distance. The nearer it is, the higher the Channel Quality Indicator. Since this Best Channel Quality Indicator chooses the nearest terminals, it causes starvation for the other users. When comes to the throughput, the Best Channel Quality algorithm performs well. Its performance in term of fairness is really poor. Best Channel Quality Indicators Flow Chart 2.8.3 Proportional Fair Scheduling Proportional Fair is one of the famous algorithm used in scheduling mechanism. Proportional fair scheduling produces high fairness and throughput. User with the maximum priority is given the resources after the calculation of channel condition. User with fewer priority is followed then after the first one. The main focus of the Proportional Fair scheduling algorithm is to support the non-real time services in Code Division Multiple Access High Data Rate. If the scheduler allocates higher number of resources for a particular user rather than channel quality, then the Proportional Fair scheduling mechanism will be affected. Each data flow is given scheduling priority which is indirectly proportional with the estimated resource allocation. This results in maximum cell throughput and satisfactory fairness. When come to freeness, Proportional Fairness scheduling works better than Best Channel Quality Indicator and Round Robin. Although Proportional Fairness is better, yet it still not abl e to complete due to some expectations. For example, if the user become nearer to the evolve NodeB from a long distance, the sound to noise ratio will be increasing gradually (signal shadowing is ignored). Thus, the users original sound to noise ratio will always will be above the average rate. There is possibilities where user can be frequently scheduled. If the user moves farther than the evolve NodeB, then the sound to noise ratio will be lesser than average. It may causes the user to starve. 2.8.4 Modified Largest Weighted Delay First Largest Weighted Delay First algorithm is proposed packets with error rate and different delays Largest Weighted Delay First algorithm