Concave piecewise linear service curves and deadline calculations

The Internet is gradually and constantly becoming a multimedia network that needs mechanisms to provide effective quality of service (QoS) requirements to users. The service curve (SC) is an efficient description of QoS and the service curve based earliest deadline first policy (SCED) is a scheduling algorithm to guarantee SCs specified by users. In SCED, deadline calculation is the core. However, not every SC has a treatable deadline calculation; currently the only known treatable SC is the concave piecewise linear SC (CPLSC). In this paper, we propose an algorithm to translate all kinds of SCs into CPLSCs. In this way, the whole Internet can have improved performance. Moreover, a modification of the deadline calculation of the original SCED is developed to obtain neat and precise results. The results combining with our proposed algorithm can make the deadline calculation smooth and the multimedia Internet possible.