{{Short description, Procedure for scheduling data packets in a packet switched best-effort network Maximum throughput scheduling is a procedure for scheduling

data packet In telecommunications and computer networking, a network packet is a formatted unit of data carried by a packet-switched network. A packet consists of control information and user data; the latter is also known as the ''payload''. Control informa ...

s in a

packet-switched In telecommunications, packet switching is a method of grouping data into '' packets'' that are transmitted over a digital network. Packets are made of a header and a payload. Data in the header is used by networking hardware to direct the pac ...

best-effort network Best-effort delivery describes a network service in which the network does ''not'' provide any guarantee that data is delivered or that delivery meets any quality of service. In a best-effort network, all users obtain best-effort service. Under ...

, typically a

wireless network A wireless network is a computer network that uses wireless data connections between network nodes. Wireless networking is a method by which homes, telecommunications networks and business installations avoid the costly process of introducing c ...

, in view to maximize the total

throughput Network throughput (or just throughput, when in context) refers to the rate of message delivery over a communication channel, such as Ethernet or packet radio, in a communication network. The data that these messages contain may be delivered ov ...

of the network, or the

system spectral efficiency Spectral efficiency, spectrum efficiency or bandwidth efficiency refers to the information rate that can be transmitted over a given bandwidth in a specific communication system. It is a measure of how efficiently a limited frequency spectrum is ut ...

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 High Speed Packet Access (HSPA) is an amalgamation of two mobile protocols—High Speed Downlink Packet Access (HSDPA) and High Speed Uplink Packet Access (HSUPA)—that extends and improves the performance of existing 3G mobile telecommunicat ...

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.

Cost function in wireless packet radio systems

Example 1: Link adaptation

In a

with

link adaptation Link adaptation, comprising adaptive coding and modulation (ACM) and others (such as Power Control), is a term used in wireless communications to denote the matching of the modulation, coding and other signal and protocol parameters to the conditio ...

, and without co-channel interference from nearby wireless networks, the

bit rate In telecommunications and computing, bit rate (bitrate or as a variable ''R'') is the number of bits that are conveyed or processed per unit of time. The bit rate is expressed in the unit bit per second (symbol: bit/s), often in conjunction w ...

depends heavily on the

carrier to noise ratio In telecommunications, the carrier-to-noise ratio, often written CNR or ''C/N'', is the signal-to-noise ratio (SNR) of a modulated signal. The term is used to distinguish the CNR of the radio frequency passband signal from the SNR of an analog ba ...

(CNR), which depends on the attenuation on the link between the transmitter and receiver, i.e. the

path loss Path loss, or path attenuation, is the reduction in power density (attenuation) 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 spectrum In telecommunication and radio communication, spread-spectrum techniques are methods by which a signal (e.g., an electrical, electromagnetic, or acoustic signal) generated with a particular bandwidth is deliberately spread in the frequency dom ...

cellular system, the carrier-to-interference ratio (CIR) is held constant by the

power control Power control, broadly speaking, is the intelligent selection of transmitter power output in a communication system to achieve good performance within the system.Guowang Miao, Jens Zander, Ki Won Sung, and Ben Slimane, Fundamentals of Mobile Data ...

for all users. For a user that suffers from high

, 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

should be considered as the most expensive, also in this case.

Example 3: Dynamic channel allocation

In wireless network with fast

dynamic channel allocation In radio resource management for wireless and cellular networks, channel allocation schemes allocate bandwidth and communication channels to base stations, access points and terminal equipment. The objective is to achieve maximum system spectral e ...

(DCA), on a packet-by-packet or slot-by-slot basis, 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 may refer to: Business and law * Profit (accounting), the difference between the purchase price and the costs of bringing to market * Profit (economics), normal profit and economic profit * Profit (real property), a nonpossessory intere ...

for the network operator. The levels of

customer satisfaction Customer satisfaction (often abbreviated as CSAT) is a term frequently used in marketing. It is a measure of how products and services supplied by a company meet or surpass customer expectation. Customer satisfaction is defined as "the number of c ...

would remain low due to many

customer In sales, commerce, and economics, a customer (sometimes known as a client, buyer, or purchaser) is the recipient of a good, service, product or an idea - obtained from a seller, vendor, or supplier via a financial transaction or exchange for ...

s experiencing long or permanent service outages. Proportional fairness would result in lower throughput, but starvation would be avoided.

Max-min fairness In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessari ...

would result in even lower throughput, but higher level of

fairness Fairness or being fair can refer to: * Justice * The character in the award-nominated musical comedy '' A Theory of Justice: The Musical.'' * Equity (law), a legal principle allowing for the use of discretion and fairness when applying justice ...

, meaning that the service quality that each data flow achieves would be even more stable. Unlike

max-min fair In communication networks, multiplexing and the division of scarce resources, max-min fairness is said to be achieved by an allocation if and only if the allocation is feasible and an attempt to increase the allocation of any participant necessar ...

scheduling based on the fair queuing or

round robin Round-robin may refer to: Computing * Round-robin DNS, a technique for dealing with redundant Internet Protocol service hosts * Round-robin networks, communications networks made up of radio nodes organized in a mesh topology * Round-robin schedu ...

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 queueing (WFQ) is a network scheduling algorithm. WFQ is both a packet-based implementation of the generalized processor sharing (GPS) policy, and a natural extension of fair queuing (FQ). Whereas FQ shares the link's capacity in ...

also require measurement or calculation of the cost function.

External links

Maiximum throughput scheduling in packet switching networks

Optimal techniques for maximum throughput scheduling in packet switching networks

”Evaluation of Packet-by-Packet Downlink Radio Resource Management Schemes”, VTC’01, 6-9 May 2001, Rhodes, Greece. Network scheduling algorithms Radio resource management