Selfish flows: where qos meets game theory
Sreenivas Gollapudi, Aidong Zhang · 2004
QoS management is central to the efficient working of a large network such as the Internet. Owing to the size of such networks, it becomes difficult to enforce any central scheme to monitor flow behavior or perform functions such as routing and bandwidth allocation. We try to answer this question at different levels of QoS management. Our contributions are twofold—The first part of the study deals with identifying misbehaving flows in the network. Here we assume most of the flows are well behaved, i.e. behave in a socially responsible manner and detect the misbehaving flows. To keep the cost of identifying the misbehaving flows low, we propose data stream algorithms to detect misbehavior only if e fraction of the bandwidth is lost to such flows. In another scenario, we propose trend analysis algorithms for data streams to identifying the outliers or misbehaving flows among a set of given flows. Data streams algorithms, in general, are extremely efficient in terms of memory and time requirements to process the elements in a data stream. We believe they are ideally suited for supporting QoS, flow and congestion control, and more generally, for bandwidth management in active network architectures. The second main contribution of this study is in designing mechanisms for bandwidth allocation and QoS routing in networks such that selfish behavior of flows leads to socially desirable outcomes both from a flow's point of view of receiving a fair amount of a network resource and the network's point of view of maximizing throughput and at the same time satisfying the QoS requirements of as many flows as possible. We also propose a novel mechanism for routing and bandwidth allocation that exploits the selfish and rational behavior of flows in a network. Our mechanism leads to allocations that simultaneously optimize throughput and fairness criteria. Thus, it produces desirable outcomes without using the a expensive and involved solution that involves a convex combination of fair and throughput-optimum solutions. Our mechanism is also fairly simple and admits an efficient distributed implementation. (Abstract shortened by UMI.)