This is a web page maintained by OPNEX partners with an aim to index important references in Network Optimization theory in an always updated manner.

 


Resource Allocation

Channel State Acquisition

Policies for acquiring channel state information have received attention only recently. A number of papers concentrate on the case of a single transmitter (base station) who can transmit information to a number of time varying channels. There is a cost associated with measuring the state of each channel as well as a bene t for transmitting information at that channel, and the objective is to develop algorithms that minimize a function of these costs and bene ts.

  • K. Kar, X. Luo, and S. Sarkar. Throughput-optimal scheduling in multichannel access point networks under infrequent channel measurements. In Proc. IEEE INFOCOM, pages  1640-1648, 2007.

Inaccurate or infrequent observations of queue sizes does not reduce the network stability
region. However, this is not the case for channel state measurements.

  • Z. Ji, Y. Yang, M. Takai, and R. Bagrodia. Exploiting medium access diversity in rate adaptive wireless LANS. In Proceedings of ACM MOBICOM, 2004.
  • A. Sabharwal, A. Khoshnevis, and E. Knightly. Opportunistic spectral usage: Bounds and a multi-band CSMA/CA protocol. IEEE/ACM Transactions on Networking, 15(3):533-545, June 2007.

The first works to tackle problems of acquiring channel state information under this model using the RTS/CTS mechanism of the IEEE 802.11 standard in order to exchange channel state information. It is assumed that all channel states are i.i.d. and all costs are
equal. The channel selected for transmission by the selection policy is one of the probed channels.

  • S. Guha, K. Muagala, and S. Sarkar. Optimizing transmission rate in wireless channels using adaptive probes. In Proceeding of SIGMETRICS/Perfrormance, 2006.
  • S. Guha, K. Muagala, and S. Sarkar. Performance guarantees through partial information based control in multichannel wireless networks. Technical report, Univ. of Pennsylvania, Philadelphia, PA, July 2006.
  • S. Guha, K. Munagala, and S. Sarkar. Approximation schemes for information acquisition and exploitation in multichannel wireless networks. In Proceedings of 44th Annual Allerton Conference on Communication, Control and Computing, Allerton, Monticallo, IL, September 2006.
  • S. Guha, K. Munagala, and S. Sarkar. Jointly optimal transmission and probing strategies for multichannel wireless systems. In Proceedings of Conference on Information Sciences and Systems pages 22-24, Princeton, NJ, March 2006.

The same model under varying channel state statistics and varying probing costs has been addressed in this series of papers. The selection policy is allowed to select for transmission one of the channels that have not been probed, if that is deemed appropriate. In the first paper, optimal polynomial algorithms are developed for the case where each channel has two states. For the general case, approximate polynomial algorithms, with cost within a percentage of the optimal cost, are developed in the second and fourth paper. In the third paper, under the assumption that all channel probing costs are equal, polynomial algorithms that achieve any desired tradeoff between approximation and computation time are developed.

  • N. Chang and M. Liu. Optimal channel probing and transmission scheduling for opportunistic spectrum access. In Proceedings of ACM International Conference on Mobile Computing and Networking (MobiCom), Montreal, Canada, September 2007.

The structural properties of the optimal probing policy are developed under arbitrary states, using a dynamic programming approach.

  • A. Gopalan, C. Caramanis, and S. Shakkotai. On wireless scheduling with partial channel-state information. In Proceedings of the 45th Allerton Conference on Communication, Control and Computing, Urbana, IL, September 2007.

In all the previous works, it is assumed that all the channels are continuously backlogged and hence the base station has always available information for transmission to all channels. The problem of dealing with the case where packets arrive to the base station in a random fashion (hence channels may not be always backlogged) is dealt in this paper. Assuming that the base station can probe the states of given subsets of channel states, the authors describe the  stability region of the system and develop a throughput optimal policy.

  • C. Li and M. J. Neely. Energy-optimal scheduling with dynamic channel acquisition in wireless downlinks. In Proceedings of 46th IEEE Conference on Decision and Control, December 2007.

Probing costs are considered in this formulation. It is assumed that the base station may either probe all channels consuming a power Pm or does not probe any channel. The objective then is to stabilize the system under the minimum consumption of power. The stability region of the system is described and optimal probing and selection policies are designed.

  • K. Kar, X. Luo, and S. Sarkar. Throughput-optimal scheduling in multichannel access point networks under infrequent channel measurements. In Proc. IEEE INFOCOM, pages 1640-1648, 2007.

This work that treats the case of random packet arrivals. It is assumed that channel states are measured in regular time intervals which may span a number of slots, hence channel state in known only at the beginning of certain slots. The stability region of such a system is described and algorithms with maximal stability region are developed.

  • A. Pantelidou and A. Ephremides. A cross-layer approach for stable throughput maximization under channel state uncertainty. to apear in ACM/Kluwer Journal of Wireless Networks.

The previous works assumed that a channel state, once probed, is exactly known. However, as mentioned in the beginning of this section, even when probed, channel state may be known only approximately. This work addresses this issue by considering a multi-hop network where each node has a fixed transmission power. Nodes may transmit at the same time and the Signal to Noise Plus Interference (SINR) Model is considered; that is, the interference at a receiver of transmissions from nodes other than the intended transmitter is considered as additive noise. A reception is successful if the SINR is larger than a given threshold and the objective is to select an appropriate link schedule so that transmissions on all activated links are successful. The channel state in this case consists of the channel attenuation factors. It is assumed that these factors can only be estimated and hence the links selected for activation may not all have successful transmission.

 

 

Power Control

The problem of Transmitter Power Control (TPC) regards the appropriate choice of transmission power vector p with respect to the interference each transmission generates to the others, and the resulting SINR. The TPC schemes that have been proposed in the literature can be classi ed into two major categories:

  1. TPC schemes that try to maximize the SINRs of all links - often the target is to maximize the minimum SINR to promote fairness in the wireless network, and
  2. TPC schemes that attempt to achieve an SINR target γ, that is each link should maintain SINR>γ. (in the general case, each link l has each own target γl).

The protocols of the first category were studied first in

  • S. Chen, N. Bambos, and G. Pottie. Admission control schemes for wireless communication networks with adjustable transmitter powers. In IEEE INFOCOM '94, pages 21-28, 1994.
  • J. Zander. Distributed cochannel interference control in cellular radio systems. IEEE Transactions on Vehicular Technology, 41:305-311, 1992.
  • J. Zander. Performance of optimum transmitter power control in cellular radio systems. IEEE Transactions on Vehicular Technology, 41:57-62, 1992.

Ηowever they often result in centralized schemes, requiring a central optimizer with global network knowledge, or require signi cant communication between the links.

Distributed TPC (DPC)

  • G.J. Foschini and Z. Miljanic. A simple distributed autonomous power control algorithm and its convergence. IEEE Transactions on Vehicular Technology, 42:641-646, 1993.
  • G.J. Foschini and Z. Miljanic. Distributed autonomous wireless channel assignement with power control. IEEE Transactions on Vehicular Technology, 44:420-429, 1995.

A well-known, autonomous and iterative distributed TPC scheme is the DPC algorithm proposed by Foschini and Miljanic. The merits of the DPC scheme include its completely autonomous operation, without any other need for interlink communications. Due to its simplicity and optimality, DPC has become quite popular and have spawned a number
of extensions/follow-up works,

  • D. Mitra. An asynchronous distributed algorithm for power control in cellular radio systems. In Proc. WINLAB '93 Workshop, 1993.

regarding asynchronous updates,

  • T. Holliday, N. Bambos, A.J. Goldsmith, and P. Glynn. Distributed power control for time varying wireless networks: Optimality and convergence. In Allerton, 2003.

regarding time-varying channel paths and convergence of time-average SINR values,

  • S. Jagannathan, A.T. Chronopoulos, and S. Ponipireddy. Distributed power control in wireless communication systems. In Computer Communications and Networks, pages 493-496, 2002.

where an enhanced DPC scheme is proposed that speeds up DPC convergence based on the optimal control and Lyapunov stability analysis techniques;

  • R. D. Yates. A framework for uplink power control in cellular radio systems. IEEE Journal on Selected Areas in Communications, 13:1341-1347, Sep 1995.

This work provides a generalized framework for DPC summarizing the above works.

  • S. Jagannathan, M. Zawodniok, and Q. Shang. Distributed power control of cellular networks in the presence of rayleigh fading channel. In IEEE/ACM INFOCOM, pages 1055-1066, 2004.

This work generalizes the above for Rayleigh fading links, focusing on the per slot values of the SINR and the outage probability (i.e. how often SINR falls below the SINR target).

  • G.S. Paschos, P. Mannersalo, and S. Stanczak. Extending the percolation threshold using power control. In IEEE WCNC, 2009.

the authors explore the benefi ts of such an algorithm in an in nite network using recent results from percolation theory. The outcome is that such a DPC algorithm can improve the connectivity (or equivalently the power consumption or link capacity) on the average, but no gains are provided when comparing to the maximum power vector.

DPC and Admission Control

While DPC guarantees eventual convergence and optimality, it essentially lacks admission control, and thus can perform poorly in a real network, where links join and leave at random times, especially as congestion rises up. Aiming to add admission control and protect active connections during the transients,

  • N. Bambos, S.C. Chen, and G. Pottie. Radio link admission algorithms for wireless networks with power control and active link quality protection. In IEEE INFOCOM, pages 97-104, 1995.
  • N. Bambos, S.C. Chen, and G. Pottie. Channel access algorithms with active link protection for wireless communication networks with power control. IEEE/ACM Transactions on Networking, 8:583-597, 2000.

the DPC with Active Link Protection (DPC/ALP) scheme modifies the original DPC iteration by dividing the links into two classes: the active links, which follow the DPC iteration modified with an enhanced target δ , and the new links, that power up geometrically fast but bounded by rate δ.

  • N. Bambos, S. Chen, and D. Mitra. Channel probing for distributed access control in wireless communication networks. In IEEE GLOBECOM, pages 322-325, 1995.

A follow-up work where a probing scheme is studied and a new link before actually gaining
admission, decides on the congestion of a wireless channel by performing only a few power-up steps. Such a scheme is particularly useful in selecting optimally among multiple wireless channel that are available to join.

  • C. Zhu and M.S. Corson. A distributed channel probing scheme for wireless networks. In IEEE INFOCOM, pages 403-411, 2001.

investigates probing mechanisms for admission control in DPC without ALP. The idea
is that a new link transmits with a constant but low power during probing so as to minimally disturb the active links; by measuring the interference and making the assumption that no more links in the neighborhood attempt to join the network, it can decide whether is admissible or not on a particular channel, and moreover select among multiple channels if available.

TPC for Cellular Systems

Typical representatives of the earlier approach of SINR maximization approach include the first three references above.

  • J. Zander. Performance of optimum transmitter power control in cellular radio systems. IEEE Transactions on Vehicular Technology, 41:57-62, 1992.

Along this direction, this work investigates the maximum possible lowest SINR by studying the eigenvalues of matrix F, and then proposes an algorithm that iterates removing cells from the network as long as the maximum SINR is below a given threshold  (in this scheme, the
algorithm runs independently for each orthogonal wireless channel).

  • J. Zander. Distributed cochannel interference control in cellular radio systems. IEEE Transactions on Vehicular Technology, 41:305-311, 1992.

an algorithm is given for maximizing and equalizing all the links SINRs, in the context of cell removal. The scheme performs an autonomous power update at each link

  • S. Chen, N. Bambos, and G. Pottie. Admission control schemes for wireless communication networks with adjustable transmitter powers. In IEEE INFOCOM '94, pages 21-28, 1994.

a tableau update scheme is investigated to perform centralized admission control and computation of optimum power levels. The scheme resembles Gaussian elimination in
systems of linear equations, and computes in one shot the optimum power levels as connections join and leave the cellular network, however, in contrast with the previous schemes, this algorithm requires explicit estimation of all channel paths-gains (i.e. from all BS to all mobile terminals) through the use of pilot tones, which makes it inherently more complex to implement.

  • M. Andersin, Z. Rosberg, and J. Zander. Soft and safe admission control in cellular networks. IEEE/ACM Transactions on Networking, 5:255-265, 1997.

In contrast to the above, this work investigates a so-called soft&safe scheme based on DPC for optimum power computation, and then uses a centralized approach to carry out admission control in cellular systems, a single link at a time. Similarly to the DPC/ALP scheme, the new link powers up gradually interacting with the BS so as not to disturb the active connections. Unlike the enhanced SINR target of DPC/ALP, the active connections boost only on need basis their powers in order to absorb the dips introduced by the extra interference generated from the new link.

TPC for Elastic and Delay-tolerant Traffic

All the schemes presented so far attempt to maintain a constant SINR, so that a constant
ow of traffc (mainly voice) is maintained. But power control schemes suitably designed to take advantage of the special nature of packet traffic are needed. In particular,

  • K.K. Leung. Power control by interference prediction for broadband wireless packet networks. IEEE Transactions on Wireless Communications, 1:256-265, 2002.

proposes an autonomous and distributed scheme that attempts to maintain a target SINR
and uses Kalman ltering techniques in order to predict interference evolution and adjust correctly the transmission power.

  • K.K. Leung and L.C. Wang. Integrated link adaptation and power control to improve error and throughput performance in broadband wireless packet networks. IEEE Transactions on Wireless Communications, 1:619-629, 2002.

Similarly, this follow-up work considers the augmented problem of joint power control and link adaptation.

  • S. Stanczak and M. Wiczanowski. Distributed utility-based power control: Objectives and algorithms. IEEE Transactions on Signal Processing, 55:5058-5068, 2007.

The power control problem for elastic traffic is formulated with the notion of utility functions
and the issue of fairness at MAC layer among others is studied. The authors present a distributed iterative power update solution that converges geometrically fast using the so-called adjoint network, where the receivers transmit to the transmitters pilot tones to implement a gradient descent method.

TPC Algorithms based on Dynamic Programming

A major technique that has been used in power control for data traffic is Dynamic Programming.

  • N. Bambos and S. Kandukuri. Power-controlled multiple access (pcma) in wireless communication networks. In IEEE INFOCOM, pages 386-395, 2000.

The authors present a formulation that studies each link autonomously operating in a randomly fluctuating interference environment. A key element of the model is that interference from other links is assumed to be non-responsive to the link's transmitter actions, a simplification that reduces the complexity of the system, and permits the design of autonomous so-called Power-Controlled Multiple Access (PCMA) algorithms. The Dynamic Programming formulation permits temporary packet bu ffering in the transmitter's queue, and balances the buff ering delay against the transmission cost, leading to schemes with a notion of back-pressure. Taking advantage of the fluctuating wireless channel, the transmitter has the option to postpone transmissions, whenever the channel is found to be in a degraded
state, for a later time when the channel will be in a good state. This intuitively permits the successful transmission at a low power level.

  • S. Kandukuri and N. Bambos. Multimodal dynamic multiple access (mdma) in wireless packet networks. In IEEE INFOCOM, pages 199-208, 2001.

The same basic model has been also extended to link adaptation, where the issue is to jointly
select the transmission power and an appropriate modulation-coding scheme.

Similarly, DP formulations have been considered jointly optimizing power control with

  • S. Gitzenis and N. Bambos. Joint transmitter power control and mobile cache management in wireless computing. IEEE Transactions in Mobile Computing, 7:498-512, 2008.

(i) cache/buffer management with respect to prefetching data over a  fluctuating wireless link,

  • Y. Li, A. Markopoulou, N. Bambos, and J. Apostolopoulos. Joint power-playout control for media streaming over wireless links. IEEE Transactions on Multimedia, 8:830-843, 2006.

(ii) playout buff er control in media streaming for multimedia communications.

A long paper summarizing the work done in power control.

 

Medium Access

MAC Algorithms for distributed coordination

In a wireless system lacking a centralized controller, a MAC protocol can help resolve the joint access of the wireless channel. The wireless world nowadays is dominated by the presence of IEEE 802.11 protocol. This protocol utilizes the Carrier Sense Multiple Access (CSMA) method with Collision Avoidance (better noted as CSMA/CA).

  • G. Bianchi. Performance analysis of the ieee 802.11 distributed coordination function. Selected Areas in Communications, IEEE Journal on, 18(3):535-547, 2000.

This work presents a usefull model for predicting the behaviour of CSMA/CA protocol in the case of saturated sources by means of solving an system of equation using a fixed point iteration. It is wildly expanded in many aspects.

  • K.K. Leung. Power control by interference prediction for broadband wireless packet networks. IEEE Transactions on Wireless Communications, 1:256-265, 2002.

This work provides an extended model which provides a closed-form solution to the performance of CSMA/CA protocol.

Although the single cell scenario of random access is well understood, organizing a network in a spatial fashion brings an great volume of complexity into the analysis.

  • Mathilde Durvy and Patrick Thiran. A Packing Approach to Compare Slotted and Non-Slotted Medium Access Control. In Infocom, 2006.

The authors attempt a direct comparison of slotted and non-slotted approaches where the non-slotted approaches are found to be superior (!) in throughput for a range of contention window values. The result is interpreted by means of a spatial packing issue. Each node has an exclusive domain whenever it transmits (i.e. a domain where all nodes situated are immediately put into idle mode{see above). Therefore one should fill the space with as many as possible exclusive domains to obtain a maximal schedule. It turns out that the non-slotted algorithms always converge to states where a maximal schedule is retained. Then following a Markov process, the system jumps frequently into different states all constituting maximal or near-maximal schedules and spends some non negligible time there. This persistence leads to high efficiency but sadly behaves quite unfairly for links that are not part of any maximal or quasi-maximal schedule.

  • A. Proutiere, Y. Yi, and M. Chiang. Throughput of random access without message passing. In 42nd Annual Conference on Information Sciences and Systems (CISS), 2008.

CSMA type algorithms are developed that do not exchange any information between links in
the network and are guaranteed to achieve the same performance as that of some maximal scheduling algorithms, as the duration of the control slots decreases. However, if the control slot duration is constant, the time needed to obtain a schedule with these algorithms increases.

  • X. Lin and S. Rasool. Constant-time distributed scheduling policies for ad-hoc wireless networks. In IEEE Conf. on Decision and Control, 2006.

A constant-time CSMA type algorithm is developed. This algorithm relies on information exchange between neighboring nodes and it is shown that its stability region is at least (1/3-1/M) S, where S is that stability region obtainable by any scheduling algorithm. The algorithm is further improved in

  • Changhee Joo and N.B. Shroff . Performance of random access scheduling schemes in multihop wireless networks. In INFOCOM 2007. 26th IEEE International Conference on Computer Communications, pages 19-27, May 2007.
  • R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin. Throughput analysis in multihop csma packet radio networks. IEEE Transactions on Communications, 35(3):267-274, sep 1987.

The authors showed that a Markov chain describing the evolution of schedules has a product form stationary distribution under an idealized continuous CSMA model (this involves zero propagation/sensing delay, no hidden terminals and no collisions).

  • L. Jiang and J. Walrand. A distributed csma algorithm for throughput and utility maximization in wireless networks. In 46th Annual Allerton Conference on Communication, Control and Computing, Sep. 2008.

The authors propose an algorithm that achieves optimal throughput and they are able to improve it so the delays are reduced. Particularly, they make the algorithm more agressive by adding a term c/rk(t) where c is a constant and rk(t) is the current aggressiveness of link k. By the term aggressiveness they mean the logarithm of the inverse mean of backoff length
(this indicates the rate at which the particular link tends to occupy a free channel).

  • A. Pantelidou and A. Ephremides. A cross-layer approach for stable throughput maximization under channel state uncertainty. to apear in ACM/Kluwer Journal of Wireless Networks.

The authors relax the assumption of continuous modeling. They prove that it is possible to
provide an algorithm that optimizes throughput in this case while introducing an overhead that does not grow with the network size (i.e. the order of complexity growth is O(1)). Instead of drawing backoff values from a continuous distribution (which guarantees zero probability of collisions) they combat collisions in a di erent way. They split each frame into a minislot part and a data part. In the minislot part, there is a contention taking place where a feasible schedule is decided (called decision schedule). This schedule is easy to make by letting all nodes compete with RTS/CTS handshakes named INTENT messages. When an INTENT message is transmitted by some node, all neighborhood gives up for this frame. If the transmission of INTENT message is successful, then this link is part of the decision
schedule. If the INTENT collides, no node takes part in the decision schedule from this neighborhood. The decision schedule is used to modulate the transmit schedule. In other words, whenever the decision schedule is empty, the transmission pattern of the previous frame is repeated. This results in a very aggressive protocol which suprisingly enough becomes independent of the minislot length. As such, the authors propose a careful construction of the decision schedule which in turn provides a throughput
optimal algorithm. The only portion of throughput lost is due to a neglidgible overhead for contention which however does not scale with the size of the network.

  • D. Chafekar, D. Levin, V.S.A. Kumar, M.V. Marathe, S. Parthasarathy, and A. Srinivasan. Capacity of asynchronous random-access scheduling in wireless networks. pages  1148-1156, April 2008.

The authors study the capacity of asynchronous random access scheduling. According to their fi ndings, a serious decrease in throughput is observed whenever the link transmission times differ greatly between several links. Also, assuming that random access policies are based only on access probability tuning, they claim that all random access policies cannot achieve more than a fraction 1/Δγ of the capacity region, where Δγ is the maximum
number of interfering naighbors that are non-interfering with each other and is a parameter relative to the hidden terminal problem. This implies, that competitiveness requires an increase in backoff which in turns compromises the total throughput.

  • P. Marbach, A. Eryilmaz, and A. Ozdaglar. Achievable rate region of csma schedulers in wireless networks with primary interference constraints. In Decision and Control, 2007 46th IEEE Conference on, pages 1156-1161, Dec. 2007.

The authors show that CSMA type algorithms are asymptotically throughput optimal for large networks under the node exclusive interference model, with many small flows and small sensing time.

  • C. Bordenave, S. Foss, and V. Shneer. A random multiple access protocol with spatial interactions. In 5th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks and Workshops, WiOpt 2007, pages 1-6, Apr. 2007.

The authors study the stability of the system prove it for symmetric conditions. However, there are cases shown that the system exhibits highly dynamic behavior.

 

Scheduling

Consider a generic packet switching system with N inputs and N outputs, where the packets leave the network after being served (single-hop traffic). We will assume that in the above packet switching system, the service constraints allow the transmission of at most one packet per time-slot from each input, which must be sent to a single output (in graph-theoretic terms, the transmitter/receiver pairs must form a matching in the underlying network connectivity graph). In an FDMA wireless network, such constraints model the fact that each receiver is tuned at a speci c frequency and the corresponding transmitter should use this frequency to send a packet to its destination. To avoid collisions on the same frequency channel, at most one transmitter should use the same frequency at the same time. Similar constraints exist in TDMA and CDMA networks, where the shared resource is time (which must be allocated to the users in the form of slots comprising a frame, where each slot is dedicated to a single user) and codebook, respectively. In a switching fabric, the service constraints model the fact
that in a non-blocking bufferless fabric (like a crossbar), at most one packet can be  transferred from each input and to each output at any given time.

Maxweight scheduling (MWS)

  • N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications, 47(8):1260-1267, August 1999.
  • L. Tassiulas and A. Ephremides. Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37:1936-1948, 1992.

It is shown that the optimal policy for single-hop networks (namely, the policy that achieves maximum, or 100%, throughput) should compute the maximum weight matching (MWM).
This fundamental result is obtained under i.i.d. arrival processes by applying the stochastic Lyapunov function methodology.

  • J. G. Dai and B. Prabhakar. The throughput of data switches with and without speedup. In Proc. of IEEE INFOCOM 2000, pages 556-564, Tel-Aviv, Israel, March 2000.

More general arrival processes are studied using fluid models.

It was later shown that it is not necessary, with regard to achieving maximum throughput, to compute the MWM using the VOQ sizes as edge weights. Indeed, the edge weight can also be either the waiting time of the head-of-the-line packet in the corresponding VOQ:

  • N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand. Achieving 100% throughput in an input-queued switch. IEEE Transactions on Communications, 47(8):1260-1267, August 1999.

, or the sum of all packets stored in the corresponding input and output ports:

  • N. McKeown and A. Mekkittikul. A practical scheduling algorithm to achieve 100% throughput in input-queued switches. In Proc. of IEEE INFOCOM 1998, pages 792-798, San Francisco, CA, April 1998.
  • M. Ajmone Marsan, E. Leonardi, M. Mellia, and F. Neri. On the stability of isolated and interconnected input-queueing switches under multiclass trac. IEEE Transactions on Iinformation Theory, 45(3):1167-1174, March 2005.
  • K. Ross and N. Bambos. Local search scheduling algorithms for maximal throughput in packet switches. In Proc. of IEEE INFOCOM 2004, volume 2, pages 1158-1169, March 2004.

Provide a general characterization of scheduling algorithms which guarantee 100%
throughput in pure IQ architectures.

  • P. Giaccone, B. Prabhakar, and D. Shah. Randomized scheduling algorithms for high-aggregate bandwidth switches. 21(4):546-559, May 2003.
  • L. Tassiulas. Linear complexity algorithms for maximum throughput in radio networks and input queued switches. In Proc. of IEEE INFOCOM 1998, pages 553-559, San Francisco, CA, April 1998.

Exploit the system's memory (i.e. the fact that Xn and Xn+1 are strongly correlated) to simplify the scheduling algorithms while guaranteeing 100% throughput for IQ architectures.

  • E. Leonardi, M. Mellia, F. Neri, and M. Ajmone Marsan. Bounds on delays and queue lengths in input-queued cell switches. Journal of the ACM, 50(4):520-550, July 2003.

The stochastic Lyapunov methodology is used to evaluate delay bounds on the
performance of MWM policy.

The above model assumes that fixed size packets are transferred across the packet switching system. To apply the previous results to an IP based network, it is necessary either to chop the variable-size packets into fixed-size blocks (and reassemble them at the outputs), or to switch natively variable-size packets. Variable-length packets can be modeled in this context as trains of fixed size blocks which have to be transferred to output ports through synchronous fabrics in contiguous time slots.

  • M. Ajmone Marsan, A. Bianco, P. Giaccone, E. Leonardi, and F. Neri. Packet-mode scheduling in input-queued cell-based switches. IEEE/ACM Transactions on Networking, 10(5):666-678, 2002.

Applying the stochastic Lyapunov function methodology, it is proved that a pure IQ switch with no speedup, implementing a variant of the MWM algorithm that allows the transfer of blocks originated by the same packet in contiguous time slots, still achieves the maximum throughput.

  • Y. Ganjali, A. Keshavarzian, and D. Shah. Cell switching versus packet switching in input-queued switches. IEEE/ACM Transactions on Networking, 13(4):782-789, August 2005.

The above result is extended, using a fluid model to a wider class of arrival processes. In conclusion, the MWM policy is throughput optimal for variable-size packets as well.

Message Passing

In order to find the optimal schedule (or equivalently the MWM) we have to solve a specific global (network-wide) combinatorial optimization problem in every timeslot. Since the number of possible scheduling policies is finite, this problem is solvable. However, if the
scheduling constraints are complex, then designing an efficient distributed algorithm may be a challenging task. Message passing algorithms are a new class of decentralized and asynchronous methods for solving problems with graphical structure. The idea is that the original objective function can be optimized by optimizing a set of local functions, whose optimal is aligned to the global one through appropriate messages that are exchanged among the nodes.

Such algorithms have been applied in a number of fields such as artificial intelligence:

  • Glenn Shafer and Prakash P. Shenoy. Probability propagation. Ann. Math. Artif. Intell., 2:327-351, 1990.

, statistics, error correcting codes:

  • Thomas J. Richardson and Rüdiger L. Urbanke. The capacity of low-density parity-check codes under message-passing decoding. IEEE Transactions on Information Theory, 47(2):599-618, 2001.

and neural networks.

  • Kyomin Jung and Devavrat Shah. Low delay scheduling in wireless network. pages 1396-1400, June 2007.

In our setting, the authors propose a throughput optimal algorithm that is amenable to distributed implementation through message passing. The basic idea is that in order to achieve throughput optimality it is sufficient to keep the weight of the schedule close to the optimal, not necessarily optimal. In each iteration a new schedule is randomly selected out of all the possible ones. The nodes estimate the new total weight, by exchanging some information with each other. They compare it to the existing one and adopt the best one. Although, this algorithm is throughput optimal for almost all instances of our setup, it cannot guarantee anything about the resulting queue sizes.

  • E. Modianno, D. Shah, and G. Zussman. Maximizing throughput in wireless networks via gossiping. In Proc. SIGMETRICS, pages 27-38, 2006.

A modification of this algorithm is presented for the case of a VOQ system. Instead of
using either the new randomly selected schedule or the old one, a merging operation between the two is performed. Thus, the best weights of each schedule are maintained and the simulations indicate that the queue sizes are reduced drastically. However, this modi cation is not applicable in every case. Such a characteristic example is the MaximumWeight Independent Set (MWIS) problem, where a transmission of a node is successful only if none of its neighbours in the interference graph is transmitting at the same time.

  • David Tse Devavrat Shah and J.N. Tsitsiklis. On hardness of low delay scheduling.

The authors proved that in this more general case the aforementioned algorithm has
exponentially large, in size of N, average queue-size and that no simple modification exists.

A special case of message passing algorithms are the max-product (or belief propagation) ones. These were initially suggested for finding the maximum (marginal) a posteriori assignment of a discrete probability distribution specified by a graphical model.

  • Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.

Shows that these algorithms converge to the correct probabilities on tree-like graphs

  • Srinivas M. Aji, Gavin B. Horn, and Robert J. Mceliece. On the convergence of iterative decoding on graphs with a single cycle. In In Proc. 1998 ISIT, page 276, 1998.

on graphs with one loop and some other special cases.

  • Mohsen Bayati, Devavrat Shah, and Mayank Sharma. Max-product for maximum weight matching: Convergence, correctness, and lp duality. IEEE Transactions on Information Theory, 54(3):1241-1251, 2008.

Consider the MWM in a bipartite graph (the VOQ scenario), as a MAP problem on a suitably defined graphical model. They show that although the bipartite graph has loops, the max-product algorithm, if the solution is unique, it converges to the desirable fixed point and requires only O(N3) operations. In this point we should mention that this is also the complexity for the best known centralized solution (Hungarian Algorithm). However, the convergence to the optimal is not established for the general case.

  • Yuan sheng Cheng, M. Neely, and K.M. Chugg. Iterative message passing algorithm for bipartite maximum weighted matching. pages 1934-1938, July 2006.

An alternative message passing approach is applied in the dual graph leading to similar conclusions. This algorithm requires less storage and can be used to solve the integer Maximal Weighted Matching problem, where the optimal solution is generally not unique.

  • Sujay Sanghavi, Devavrat Shah, and Alan S. Willsky. Message-passing for maximum weight independent set. CoRR, abs/0807.5091, 2008.

 

Studies the applicability of the max-product algorithms in the more general problem of finding the maximum weight independent set. They show that each fixed-point estimate of the  maxproduct can be mapped to an extreme of the MWIS. However, this extreme point is not always the one that maximizes the value of the node weights; the convergence point depends on the initialization values. When the max-product algorithm is initialized with messages that have no information, it finds the correct schedule (if it converges). A modi ed version of the algorithm is shown to find the best schedule, when the graph is bipartite and the MWIS is unique.

Greedy Maximal scheduling

Trying to implement MWM might become extremely complicated especially for large networks (for example, a centralized solution of the MWM problem has complexity O(N3), where N is the number of nodes but in a problem with general Interference constraints the problem becomes hard). In order to derive distributed low complexity algorithms, many proposed solutions consider the option of imperfect scheduling at the expense of a smaller achievable capacity region. The proposed solutions for the distributed resource allocation with respect to stability can be classified into two major categories. In the first class, there exist algorithms which adopt simplified physical and access layer protocols and propose suboptimal scheduling schemes. The main issue in this line of research is the examination of the inherent tradeoff between the reduced complexity of the proposed scheduling schemes and the (possible) loss of performance. The latter is usually quantified through the reduction of the stability region.

  • P. Chaporkar, K. Kar, and S. Sarkar. Throughput guarantees through maximal scheduling in wireless networks. In Proc. Allerton Conf. Control, Commun., Comput., pages 1557-1567, 2005.

The authors present a simple scheduling policy, referred to as Maximal scheduling, which ensures activation of a maximal set of non-interfering links. They consider simple interference models and prove that the performance loss due to the "distributization" of the algorithm is bounded. That is, the algorithm guarantees a certain fraction of the optimum centralized solution, which varies according to the specific communication and interference model.

  • X. Wu, R. Srikant, and J. Perkins. Queue-length stability of maximal greedy schedules in wireless networks. In Proc. of Workshop on Information Theory and Applications, 2006.

The authors consider multi-hop networks and propose the Greedy scheduling algorithm
which also provides the maximal number of activated links. The idea is that each node attempts to independently schedule transmissions over one of its backlogged links until it finds a non interfered one. The performance loss of the algorithm is bounded and relates to the network architecture.

  • X. Lin and N.B. Shroff . The impact of imperfect scheduling on cross-layer rate control in wireless networks. In INFOCOM 2005. 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings IEEE, volume 3, pages 1804-1814, 2005.

It is shown that greedy scheduling policy achieves at least half of the capacity region of the network under the extensively studied node-exclusive interference model.

The Greedy Maximal Matching (GMM) algorithm sorts the links in descending weight order and enables the first link (at the same time disabling all links that interfere with it). It then selects, out of the remaining links, the largest-weighted one and repeats the procedure until no links remain. This algorithm is much faster than MWM but less efficient since the outcome is a maximal matching (instead of a maximum-weight one). All algorithms referring to maximal matching lean on the popular paper of Hoepman:

  • Jaap-Henk Hoepman. Simple distributed weighted matchings. CoRR, cs.DC/0410047, 2004.

where an algorithm for finding a maximal matching in a distributed manner is indicated.

  • C. Joo, X. Lin, and N. Shro . Understanding the capacity region of the greedy maximal scheduling algorithm in multi-hop wireless networks. In Proc. IEEE INFOCOM, pages 1103-1111, 2008.

The authors introduce the notion of local pooling. A graph with local pooling is a graph
for which the weighted utilities of all maximal matchings are equal, so that all maximal matchings are a priori equally good (a simple example is the triangle graph of unity utility per link under the node-exclusive interference model). This implies that finding a maximal matching should be as efficient as finding a maximum matching, which explains why GMM is optimal on a graph with local pooling.

  • G. Zussman, A. Brzezinski, and E. Modiano. Multihop local pooling for distributed throughput maximization in wireless networks. In Proc. IEEE INFOCOM, pages 1139-1147, 2008.

The authors study local pooling in a general interference setting and introduce the idea of
multihop local pooling factor. They extract important results regarding the efficiency of maximal matching scheduling policies (like GMM) in the case of low and high interference degree (hops away). They show that local pooling holds when the interference degree is low and, more importantly, local pooling can be achieved even in a high interference setting, albeit at a loss of performance.

  • M. Neely. Delay analysis for maximal scheduling in wireless networks with bursty traffic. In Proc. IEEE INFOCOM, pages 6-10, 2008. Provides results for the delay performance of maximal matching scheduling policies.

Specifically, it proves the stability for a particular traffic model and then provides tight bounds for the delay that a customer (packet) experiences at the queue.

  • A. Gupta, X. Lin, and R. Srikant. Low-complexity distributed scheduling algorithms for wireless networks. In Proc. IEEE INFOCOM, pages 1631-1639, 2007.

In an attempt to propose a more realistic model, the authors present two algorithms that can provide near optimal performance in a distributed manner. The first one (called Q-SCHED) uses local queue information. The second one (BP-SIM) is based on the distributed algorithm of:

  • K. Jung and D. Shah. A distributed matching protocol. Massachusetts Institute of Technology Report, 2006.

in order to find a matching.

Approximate algorithms for distributed scheduling

Most of the previous bounds are made possible by producing in each time slot a suboptimal solution to the underlying scheduling problem (e.g. the MWM problem for the primary interference model above) with guaranteed performance with respect to the optimal solution.

  • Y. Yi, A. Proutiere, and M. Chiang. Complexity in wireless scheduling: impact and tradeo s. In MobiHoc '08: Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, pages 33-42, 2008.

Formalizes this notion by introducing the class of (γ,ξ) approximate algorithms (where 0 < γ
< 1 is a scaling parameter for the capacity region), see definition in D2.1. Most of the aforementioned algorithms (such as the greedy, maximal matching and the randomized algorithm proposed above by Tassiulas) fall into this category.

A lot of attention has been devoted to the distributed computation of such suboptimal solutions, although most works propose solutions whose overhead is at least linear with respect to network size.

  • E. Modianno, D. Shah, and G. Zussman. Maximizing throughput in wireless networks via gossiping. In Proc. SIGMETRICS, pages 27-38, 2006.

It is argued that an accurate weight-based comparison of the schedules is difficult to be performed in a distributed manner, which motivates the authors to propose a randomized comparison algorithm that produces the better of the two schedules with a sufficiently high
probability (albeit, not w.p 1). It is proved that the combination of the two previous steps achieves a stability region which is a fraction of the original one while the complexity of the combined steps is O(N).

  • S. Sanghavi, L. Bui, and R. Srikant. Distributed link scheduling with constant overhead. In Proc. SIGMETRICS, pages 313-324, 2007.

An important contribution to the distributed scheduling problem with guaranteed performance; it proposes an algorithm with O(1) (i.e. constant) overhead with respect to network size under the node-exclusive interference model. It takes into account the time overhead required by the algorithm's execution and splits the slot into control and data subslots. Essentially, the distributed schedule is determined during the control part of the slot and is then used in the data part (throughput is defined with respect to the data part of the slot). The major contribution of this work is the proposal of a randomized distributed algorithm that requires only 4k +2 control subslots for the computation of the schedule in each slot (where k is integer and the actual duration of a control subslot can be made
equal to the time required for a successful handshake between two adjacent nodes) and is guaranteed to achieve a capacity region of at least (k/(k + 2))Λ. Furthermore, the nodes need to perform only minor operations, such as randomly selecting one of their neighbors and subtracting two values.

  • Y. Yi and M. Chiang. Wireless scheduling algorithms with o(1) overhead for m-hop interference model. In IEEE ICC, pages 3105-3109, 2008.

The previous constant overhead algorithm was proposed under the node-exclusive interference setting, which may be too restrictive for some types of wireless networks. Here an extension to M-hop interference models is provided, where a valid matching is defined to be a matching where all active links are at least M hops apart from each other. The authors use the concept of the conflict graph, which simplifies the construction of valid matchings (see references for exact de nitions), and propose an augmentation method, performed on the con
ict graph which achieves a stability region of at least (k/(k + 2))Λ.

  • Aneesh Reddy, Sanjay Shakkottai, and Lei Ying. Distributed power control in wireless ad hoc networks using message passing: Throughput optimality and network utility maximization. In CISS, pages 770-775, 2008.

The authors Considered the problem of link scheduling and power control in a k-hop interference limited line network. They developed a message passing algorithm that in this simple case finds the optimal power allocation and has a O(N) time complexity. If combined with appropriate congestion control and routing algorithms, throughput optimality and utility maximization can also be established. Finally, they show that modeling the physical interference case as an appropriately selected k-hop interference model yields ε-optimality.