Maximum throughput scheduling


Maximum throughput scheduling

Maximum throughput scheduling is a procedure for scheduling data packets in a packet-switched best-effort communications network, typically a wireless network, in view to maximize the total throughput of the network, or the system spectral efficiency in a wireless network. This is achieved by giving scheduling priority to the least "expensive" data flows in terms of consumed network resources per transferred amount of information.

In advanced packet radio systems, for example the HSDPA 3.5G cellular system, channel-dependent scheduling is used instead of FIFO queuing to take advantage of favourable channel conditions to make best use of available radio conditions. Maximum throughput scheduling may be tempting in this context, especially in simulations where throughput of various schemes are compared. However, maximum throughput scheduling is normally not desirable, and channel-dependent scheduling should be used with care, as we will see below.

Contents

Cost function in wireless packet radio systems

Example 1: Link adaptation

In a wireless network with link adaptation, and without co-channel interference from nearby wireless networks, the bit rate depends heavily on the carrier to noise ratio (CNR), which depends on the attenuation on the link between the transmitter and receiver, i.e. the path loss. For maximum throughput scheduling, links that are affected by low attenuation should be considered as inexpensive, and should be given scheduling priority.

Example 2: Spread spectrum

In the uplink of a spread spectrum cellular system, the carrier-to-interference ratio (CIR) is held constant by the power control for all users. For a user that suffers from high path loss, the power control will cause high interference level to signals from other users. This will prevent other more efficient data flows, since there is a maximum allowed interference level in the cell, and reduce the throughput. Consequently, for maximum throughput scheduling, data flows that suffer from high path loss should be considered as the most expensive, also in this case.

Example 3: Dynamic channel allocation

Example 3: In wireless network with fast dynamic channel allocation (DCA), on a packet-by-packet or slot-by-slot bases, a user that is situated in the overlap between the coverage areas of several base stations would cause, or would be affected by, interference to/from nearby cells. The DCA algorithm would prevent the nearby cells from using the same frequency channel simultaneously. The cost function would correspond to the number of blocked nearby base station sites.

Comparison with other resource sharing policies

If there are large differences between the "cost" of each data flow, which is the case especially in wireless networking, resources may be assigned to only one or very few data flows per physical channel in the network. If there are many simultaneously active data flows, a majority of the data flows will have to wait until the most inexpensive flows have no more data to transfer, and will suffer from scheduling starvation.

A maximum throughput scheduling policy may be tempting since it would optimize the resource utilization in a given network, but it would not be likely to maximize profit for the network operator. The levels of customer satisfaction would remain low due to many customers experiencing long or permanent service outages.

Proportional fairness would result in lower throughput, but starvation would be avoided.

Max-min fairness would result in even lower throughput, but higher level of fairness, meaning that the service quality that each data flow achieves would be even more stable.

Unlike max-min fair scheduling based on the fair queuing or round robin algorithms, a maximum throughput scheduling algorithm relies on the calculation of a cost function, which in wireless networks may require fast and truthful measurement of the path loss. Proportional fairness based on weighted fair queuing also require measurement or calculation of the cost function.

See also

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Scheduling (computing) — This article is about processes assignment in operating systems. For other uses, see Scheduling (disambiguation). Scheduling is a key concept in computer multitasking, multiprocessing operating system and real time operating system designs.… …   Wikipedia

  • Throughput — This article is about the use of Throughput in communication networks. For disk drives, see Throughput (disk drive). For business management, see Throughput (business). In communication networks, such as Ethernet or packet radio, throughput or… …   Wikipedia

  • Scheduling algorithm — In computer science, a scheduling algorithm is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth). This is usually done to load balance a system effectively or …   Wikipedia

  • Round-robin scheduling — Round robin (RR) is one of the simplest scheduling algorithms for processes in an operating system, which assigns time slices to each process in equal portions and in order, handling all processes without priority. Round robin scheduling is both… …   Wikipedia

  • Relationship between latency and throughput — A common concern in the development or procurement of a telecommunications system is a simple question: will my data arrive fast enough? . This question in fact contains many subtle parts, based on the interplay of several factors. The perceived… …   Wikipedia

  • Max-min fairness — In communication networks and multiplexing, a division of the bandwidth resources is said to be max min fair when: firstly, the minimum data rate that a dataflow achieves is maximized; secondly, the second lowest data rate that a dataflow… …   Wikipedia

  • Fair queuing — is a scheduling algorithm used in computer and telecommunications networks to allow multiple packet flows to fairly share the link capacity. The advantage over conventional first in first out (FIFO) queuing is that a high data rate flow,… …   Wikipedia

  • Radio resource management — (RRM) is the system level control of co channel interference and other radio transmission characteristics in wireless communication systems, for example cellular networks, wireless networks and broadcasting systems. RRM involves strategies and… …   Wikipedia

  • Resource starvation — In computer science, starvation is a multitasking related problem, where a process is perpetually denied necessary resources. Without those resources, the program can never finish its task [] .Starvation is similar in effect to deadlock. Two or… …   Wikipedia

  • High-Speed Downlink Packet Access — (HSDPA) is an enhanced 3G (third generation) mobile telephony communications protocol in the High Speed Packet Access (HSPA) family, also dubbed 3.5G, 3G+ or turbo 3G, which allows networks based on Universal Mobile Telecommunications System… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.