Maximum throughput scheduling
Encyclopedia
Maximum throughput scheduling is a procedure for scheduling data packets in a packet-switched best-effort communication
s 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.
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.
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.
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 customer
s 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.
Telecommunication
Telecommunication is the transmission of information over significant distances to communicate. In earlier times, telecommunications involved the use of visual signals, such as beacons, smoke signals, semaphore telegraphs, signal flags, and optical heliographs, or audio messages via coded...
s network
Telecommunications network
A telecommunications network is a collection of terminals, links and nodes which connect together to enable telecommunication between users of the terminals. Networks may use circuit switching or message switching. Each terminal in the network must have a unique address so messages or connections...
, typically a wireless network
Wireless network
Wireless network refers to any type of computer network that is not connected by cables of any kind. It is a method by which homes, telecommunications networks and enterprise installations avoid the costly process of introducing cables into a building, or as a connection between various equipment...
, in view to maximize the total throughput
Throughput
In communication networks, such as Ethernet or packet radio, throughput or network throughput is the average rate of successful message delivery over a communication channel. This data may be delivered over a physical or logical link, or pass through a certain network node...
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
FIFO
FIFO is an acronym for First In, First Out, an abstraction related to ways of organizing and manipulation of data relative to time and prioritization...
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.
Example 1: Link adaptation
In a wireless networkWireless network
Wireless network refers to any type of computer network that is not connected by cables of any kind. It is a method by which homes, telecommunications networks and enterprise installations avoid the costly process of introducing cables into a building, or as a connection between various equipment...
with link adaptation
Link adaptation
Link adaptation, or adaptive coding and modulation , is a term used in wireless communications to denote the matching of the modulation, coding and other signal and protocol parameters to the conditions on the radio link Link adaptation, or adaptive coding and modulation (ACM), is a term used in...
, and without co-channel interference from nearby wireless networks, the bit rate
Bit rate
In telecommunications and computing, bit rate is the number of bits that are conveyed or processed per unit of time....
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
Path loss
Path loss is the reduction in power density of an electromagnetic wave as it propagates through space. Path loss is a major component in the analysis and design of the link budget of a telecommunication system....
. 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 spectrumSpread spectrum
Spread-spectrum techniques are methods by which a signal generated in a particular bandwidth is deliberately spread in the frequency domain, resulting in a signal with a wider bandwidth...
cellular system, the carrier-to-interference ratio (CIR) is held constant by the power control
Power control
Power control, broadly speaking, is the intelligent selection of transmit power in a communication system to achieve good performance within the system. The notion of "good performance" can depend on context and may include optimizing metrics such as link data rate, network capacity, geographic...
for all users. For a user that suffers from high path loss
Path loss
Path loss is the reduction in power density of an electromagnetic wave as it propagates through space. Path loss is a major component in the analysis and design of the link budget of a telecommunication system....
, 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
Path loss
Path loss is the reduction in power density of an electromagnetic wave as it propagates through space. Path loss is a major component in the analysis and design of the link budget of a telecommunication system....
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
Profit (economics)
In economics, the term profit has two related but distinct meanings. Normal profit represents the total opportunity costs of a venture to an entrepreneur or investor, whilst economic profit In economics, the term profit has two related but distinct meanings. Normal profit represents the total...
for the network operator. The levels of customer satisfaction
Customer satisfaction
Customer satisfaction, a term frequently used in marketing, is a measure of how products and services supplied by a company meet or surpass customer expectation...
would remain low due to many customer
Customer
A customer is usually used to refer to a current or potential buyer or user of the products of an individual or organization, called the supplier, seller, or vendor. This is typically through purchasing or renting goods or services...
s experiencing long or permanent service outages.
Proportional fairness would result in lower throughput, but starvation would be avoided.
Max-min fairness
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 achieves is maximized, etc.In best-effort statistical...
would result in even lower throughput, but higher level of fairness
Fairness measure
Fairness measures or metrics are used in network engineering to determine whether users or applications are receiving a fair share of system resources. There are several mathematical and conceptual definitions of fairness.-TCP 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
Weighted fair queuing
Weighted fair queuing is a data packet scheduling technique allowing different scheduling priorities to statistically multiplexed data flows.WFQ is a generalization of fair queuing . Both in WFQ and FQ, each data flow has a separate FIFO queue...
also require measurement or calculation of the cost function.
External links
- Mathematical model for maximum throughput scheduling
- Use of randomization techniques in maximum throughput scheduling
- Maiximum throughput scheduling in packet switching networks
- Optimal techniques for maximum throughput scheduling in packet switching networks
- http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.16.8494&rep=rep1&type=pdf ”Evaluation of Packet-by-Packet Downlink Radio Resource Management Schemes”, VTC’01, 6-9 May 2001, Rhodes, Greece.