PAC Learning
- PDF / 160,429 Bytes
- 3 Pages / 547.087 x 737.008 pts Page_size
- 39 Downloads / 227 Views
P
PAC Learning
The authors then define an interval structure for input instances. An interval I is said to be of type i if at every step t 2 I MPG outputs a packet of value at least ˇ i , and I is a maximal interval with this property. I i is the collection of maximal intervals of type i, and I is the union of all I i ’s. This is a multiset, since an interval of type i can also be contained in an interval of one or more types j < i. This induces an interval structure which is a sequence of ordered rooted trees in a natural way: the root of each tree is an interval in I0 , and the children of each interval I 2 I i are all the maximal intervals of type i + 1 which are contained in I. These children are ordered from left to right based on time, as are the trees themselves. The intervals of type i (and the vertices that represent them) are distinguished by whether or not an eviction of a packet of value at least ˇ i occurred during the interval. To complete the proof, the authors show that for every interval structure T , the competitive ratio of MPG on instances with interval structure T can be bounded by the solution of a linear program indexed by T . Finally, it is shown that for every T and every ˇ 4, the solution of this program is at most 2 1/ˇ. Applications In recent years, there has been a lot of interest in Quality of Service networks. In regular IP networks, packets are indistinguishable and in case of overload any packet may be dropped. In a commercial environment, it is much more preferable to allow better service to higher-paying customers or customers with critical requirements. The idea of Quality of Service guarantees is that packets are marked with values which indicate their importance. This naturally leads to decision problems at network switches when many packets arrive and overload occurs. The algorithm presented in this entry can be used to maximize network performance in a network which supports Quality of Service.
the corresponding lower bound of 1.28 from Mansour et al. [9]. An open problem is to close the remaining small gap. Cross References Packet Switching in Multi-Queue Switches Recommended Reading 1. Aiello, W., Mansour, Y., Rajagopolan, S., Rosen, A.: Competitive queue policies for differentiated services. In: Proc. of the IEEE INFOCOM, pp. 431–440. IEEE, Tel-Aviv, Israel (2000) 2. Andelman, N., Mansour, Y., Zhu, A.: Competitive queueing policies in QoS switches. In: Proc. 14th Symp. on Discrete Algorithms (SODA), pp. 761–770 ACM/SIAM, San Francisco, CA, USA (2003) 3. Bansal, N., Fleischer, L., Kimbrel, T., Mahdian, M., Schieber, B., Sviridenko, M.: Further improvements in competitive guarantees for QoS buffering. In: Proc. 31st International Colloquium on Automata, Languages, and Programming (ICALP). Lecture Notes in Computer Science, vol. 3142, pp. 196–207. Springer, Berlin (2004) 4. Englert, M., Westermann, M.: Lower and upper bounds on FIFO buffer management in qos switches. In: Azar, Y., Erlebach, T. (eds.) Algorithms – ESA 2006, 14th Annual European Symposium, Proceedings.
Data Loading...
