We consider the problem of transmission scheduling of data over a wireless fading channel with hard deadline constraints. Our system consists of N users, each with a fixed amount of data that must be served by a common deadline. Given that, for each user, the channel fade state determines the throughput per unit of energy expended, our objective is to minimize the overall expected energy consumption while satisfying the deadline constraint. We consider both a linear and a strictly convex rate-power curve and obtain optimal solutions, based on dynamic programming (DP), and tractable approximate heuristics in both cases. For the special non-fading channel case with convex rate-power curve, an optimal solution is obtained based on the shortest path formulation. In the case of a linear rate-power curve, our DP solution has a nice "threshold" form; while for the convex rate-power curve we are able to obtain a heuristic algorithm with comparable performance with that of the optimal scheduling scheme.

In this paper we propose a new fluid model approach in which a different description of the dynamics of traffic sources is adopted, exploiting partial differential equations. This new description of the source dynamics allows the natural representation of short-lived as well as long-lived TCP connections, with no sacrifice in the scalability of the model. In addition, the use of partial differential equations permits the description of distributions, instead of averages, thus providing better accuracy in the results. The comparison between the performance estimates obtained with fluid models and with ns-2 simulations proves the accuracy of the proposed modeling approach.

Fluid models of IP networks have been recently proposed as a way to break the scalability barrier of traditional discrete state-space models, both simulative (e.g., ns-2) and analytical (e.g., queues and Markov chains). Fluid models adopt an abstract deterministic description of the average network dynamics through a set of ordinary differential equations that are then solved numerically, obtaining estimates of the time-dependent network behavior. However, an important limit of the fluid model approaches presented so far in the literature is their unnatural representation of scenarios comprising the short-lived TCP flows that dominate in today's Internet. In this paper we propose a new fluid model approach in which a different description of the dynamics of traffic sources is adopted, exploiting partial differential equations. This new description of the source dynamics allows the natural representation of short-lived as well as long-lived TCP connections, with little sacrifice in the scalability of the model. In addition, the use of partial differential equations permits the description of distributions, instead of averages, thus providing better accuracy in the results. The comparison between the performance estimates obtained with fluid models and with ns simulations proves the accuracy of the proposed modeling approach.

Instability in packet-switching networks is normally associated with overload conditions, since queueing network models show that, in simple configurations, only overload generates instability. However, some results showing that instability can happen also in underloaded queueing networks began to appear about a decade ago. Underload instabilities can be produced by: 1) customer routes that visit the same queues several times; 2) variations of the customer service times at the different queues; and 3) complex scheduling algorithms. We study, using fluid models and adversarial queueing theory, possible underload instabilities due to flow schedulers in packet networks, focusing on output queued switches with strict priority (SP) schedulers and Generalized Processor Sharing (GPS) schedulers. The considered scenarios always refer to acyclic packet routes and consider customer service times that vary only according to channel capacities, thus resembling the approaches being currently considered to provide QoS in the Internet. Our (in)stability results are rather surprising: SP schedulers appear to be more robust than GPS schedulers whenever exact information on the effective average packet flow rates is not available.

Although instability in packet networks has been traditionally associated with overload conditions (because queueing network models show that, in simple configurations, only overload generates instability), some results showing instability in underloaded packet networks have appeared in the recent literature. In M. Ajmone Marsan, et al. (2003) we studied, with fluid models and with adversarial queueing theory, possible underload instabilities due to complex scheduling algorithms that closely resemble quality of service (QoS) schedulers considered today for packet networks, when sources are non-adaptive. In this paper we extend the study of the underload instabilities to packet networks carrying the traffic generated by elastic (rate-adaptive) sources. In particular, we consider additive-increase, multiplicative-decrease (AIMD) sources, and we show this type of adaptivity is not sufficient to mitigate the phenomena leading to underload instabilities and to reduced network throughput.

Instability in packet-switching networks is normally associated with overload conditions, since queueing network models show that, in simple configurations, only overload generates instability. However, some results showing that instability can happen also in underloaded queueing networks appeared in the recent literature. Underload instabilities can be produced by complex scheduling algorithms, that bear significant resemblance to the Quality of Service (QoS) schedulers considered today for packet networks. In this paper, we study with fluid models and with adversarial queueing theory possible underload instabilities due to strict-priority schedulers and to Generalized Processor Sharing (GPS) schedulers.

No abstract available.