Optimal QoS-based classification for link models with predetermined service levels

We investigate the problem of optimal QoSbased classification of traffic streams in the context of multiclass link model with predetermined service levels. Specifically, we consider a link model with fixed service levels which may be represented by a finite number of MPLS Label Switched Paths (LSPs). Our target is to classify a set of traffic streams with arbitrary local QoS, in addition to the bandwidth requirements, to these service levels while achieving the minimum quantization overhead. The quantization overhead is defined as a function of the differences between the required and offered service levels. We formulate the classification as a constrained integer linear optimization problem. We then present two efficient algorithms to obtain the optimal classification for a set of traffic streams for link models with predetermined service levels to minimize the quantization overhead. Our results indicate that by properly selecting the service class weights, the quantization overhead can become as low as 2% using as few as 5 service levels for clustered QoS distribution. On the other hands, if the class weights are not selected appropriately the quantization overhead is around 32% for uniform QoS distribution.