Pricing activity within ARMOR project: present and future

Contact: Bruno Tuffin

Last update: November 27, 2003

Introduction to pricing

Pricing is a good example of a multi-disciplinary research activity half-way between applied mathematics, economy and networking. Indeed, the Internet is facing a tremendous increase of its traffic volume. As a consequence, real users complain that large data transfers take too long, without any possibility to improve this by themselves (by paying more, for instance). A possible solution to cope with congestion is to increase the link capacities; however, many authors consider that this is not a viable solution as the network must respond to increasing demand (and experience has shown that demand of bandwidth has always been ahead of supply), especially now that the Internet has become a commercial network. Furthermore, incentives to a fair utilization between customers are not included in the current Internet.

For these reasons, it has been suggested that the current flat-rate fees, where customers pay a subscription and obtain an unlimited usage, be replaced by usage-based fees. Besides, the future Internet will carry heterogeneous flows such as video, voice, email, web, file transfer and remote login among others. Each of these applications requires a different quality of service (QoS): for example, video needs very small delays and packet losses, voice requires small delays but can afford some packet losses, email can afford delay (within a given bound) while file transfer needs more a good average throughput and telnet requires small round-trip times. Some pricing incentives should exist so that each user doe not always choose the best QoS for her application and so that the final result is a fair utilisation of the bandwidth. On the other hand, we need to be aware of the trade-off between engineering efficiency and economic efficiency; for example, traffic measurements helps in improving the management of the network but is a costly option.

Pricing has then emerged as a hot topic in the telecommunication world, receiving a lot of attention. Among major projects involved in this research area, we can quote non-exhaustively

• The Information Economy at Berkeley;
• M3I Project;
• Cashman Project.

Pricing activity within ARMOR

The pricing activity started in 2001 in ARMOR. The active members are

• Bruno Tuffin, CR INRIA;
• David Ros, Assistant Professor at ENST-Bretagne;
• Yezekael Hayel, PhD student (thesis started 10/02), working on multiclass pricing for service differentiation;
• Patrick Maille, PhD student (thesis started 10/02), working on auctioning for bandwidth, and more generally on applying game theory to network pricing;
• Ricardo Orozco, PHD student (thesis started 10/03), working on the practical aspects of pricing (design of protocols and architectures).

We coordinate the PRIXNET INRIA ARC, cooperative research action with MISTRAL project, France Telecom, Prism laboratory (University of Versailles-St Quentin) and IBM (Watson research center). We especially have a strong collaboration with Mistral project, which might be involved in our future research activities.

The results we have obtained up to now have focused on the theoretical part of the pricing scheme design.

• We have obtained several results on auctions for bandwidth. In this context, second price auctions (where the bidders pay the price of those excluded from the game by their presence) have been proved to be incentive compatible and efficient (in terms of social welfare). We have extended the initial work developed at Columbia University by N. Semret in different ways. One of our main contributions is the multi-bids auction scheme where the players submit several bids simultaneously, instead of one iteratively until an equilibirum is reached, saving then a lot of signaling overhead, while preserving the optimality and incentive comptatibility properties.
• We have also obtained several results on multi-class pricing, where classes are served differently according to their associated prices. We have studied such schemes for several scheduling strategies: processor sharing, priority queuing and separate queuing (also called paris Metro pricing). We have especially shown that, in order to maximize its revenue, a provider should rather use priority queuing (see pricing and scheduling paper). Other schemes such as to so-called Cumulus where positive or ngative points are awarded to the users, depending on the respect of their contract, have also been analyzed and could fit to the DiffServ architecture for instance.
• As a last subgroup of contributions, we have worked on pricing as a service differentiation means in TCP/RED buffers, where the drop probability is made dependent on the willingness to pay of the users. We have obtained conditions under which an equilibrium could be obtained.

Research directions

• We plan to strengthen our network pricing activity in the next four years. This requires further mathematical modeling and analysis of different possible pricing schemes:
  • Auctioning for bandwidth requires additional investigations. We are working on an extension of our multibid auction scheme to a whole network. Designing protocols devoted to this scheme is also a planned goal.
  • pricing TCP/RED buffers requires also more work. We plan, among other possibilities, to look at parameter values allowing stability in the system, by using automatic control theory. This would be a extension to the existing litterature on TCP/RED buffers, with the willingness to pay (or utility function) of the users as an additional input.
  • On multiclass pricing, we plan to work on other scheduling strategies (discriminatory processor sharing...) for fixed pricing, but also on dynamic pricing, where the price will vary with the level of congestion of the network.
  • Finally we plan to compare mathematically those pricing schemes in terms of provider revenue, social welfare and fairness (when this notion is relevant).
• Second, all pricing models include a "utility function" representing the service valuation by the users. In the literature, stringent assumptions are imposed on this function for the sake of convenience but that might not represent the actual demand and lead to non-optimal prices. Based on tests and in collaboration with the Qualitative Quality Assessment sub-group of ARMOR project, we plan to estimate this function based on "real-world" data, that is, considering subjective measures from real users. This would require extensive testing since we do not need the mean opinion score, but rather the whole distribution with respect to some specified parameters.
• To the best of our knowledge, most of the work on network pricing reported in the literature is of a theoretical nature. However, the deployment of pricing schemes on a real network arises some interesting technological problems, for instance:
  • The design and implementation of protocols for dynamic pricing (for example, protocols for tariff distribution and negotiation).
  • The integration of pricing and metrology tools, that may be needed to deploy complex usage-based pricing schemes.
  • The integration of pricing methods into a service differentiation architecture (like the IETF's DiffServ). Therefore, we also intend to put these methods in practice, to test their feasability and to compare them on an experimental platform in order to select the most likely to be implemented at large scale as a compromise between efficiency and simplicity.
• Finally, up to now this activity has focused on wired networks, but we aim at extending it to wireless and ad hoc networks, dealing both with theoretical modeling issues and with practical and implementation issues like in the case of wired networks.
  • Indeed, third generation of wireless networks, such as the UMTS network, will have to deal with demanding applications in terms of bandwidth and QoS requirements. Even if the capacity has increased with respect to the networks of second generation, demand is supposed to be so important that congestion pricing will probably be the most relevant means to control and manage the traffic (for instance watching a movie on a terminal would require the capacity of an entire base station).
  • Following the same lines, there must be in an ad hoc network some incentives to forward traffic of other nodes. Without associated pricing scheme, choosing to not participate in the network may be in the (short-term) interest of a node, meaning to not exepend energy without receiving any direct gain from doing so. Pricing is then a concept that will introduce incentives for collaboration into the architecture.
  • Also, in the current situation, owners of private WiFi networks often choose to encrypt their networks to prevent outsiders from accessing them. Many of these base stations could be used to allow Internet access to a much larger set of users. Pricing would be a mechanism to incentivize owners of existing private wireless base stations to open their networks to the public, as well as incentivize institutions to deploy base stations in order to obtain ubiquitous WiFi coverage.