Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members
CostFunction.cpp
00001 /*********************************************************************** 00002 * * 00003 * ViTooKi * 00004 * * 00005 * title: CostFunction.cpp * 00006 * * 00007 * * 00008 * * 00009 * ITEC institute of the University of Klagenfurt (Austria) * 00010 * http://www.itec.uni-klu.ac.at * 00011 * * 00012 * * 00013 * For more information visit the ViTooKi homepage: * 00014 * http://ViTooKi.sourceforge.net * 00015 * vitooki-user@lists.sourceforge.net * 00016 * vitooki-devel@lists.sourceforge.net * 00017 * * 00018 * This file is part of ViTooKi, a free video toolkit. * 00019 * ViTooKi is free software; you can redistribute it and/or * 00020 * modify it under the terms of the GNU General Public License * 00021 * as published by the Free Software Foundation; either version 2 * 00022 * of the License, or (at your option) any later version. * 00023 * * 00024 * This program is distributed in the hope that it will be useful, * 00025 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00026 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 00027 * GNU General Public License for more details. * 00028 * * 00029 * You should have received a copy of the GNU General Public License * 00030 * along with this program; if not, write to the Free Software * 00031 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, * 00032 * MA 02111-1307, USA. * 00033 * * 00034 ***********************************************************************/ 00035 00036 /*********************************************************************** 00037 * * 00038 * REVISION HISTORY: * 00039 * * 00040 * * 00041 * * 00042 ***********************************************************************/ 00043 00044 #include "CostFunction.hpp" 00045 #include "cache/AdmissionControl.hpp" 00046 00047 int CostFunction::baseCosts=10; 00048 00049 ResourceUsage* CostFunction::calcResourceUsage( const Feature* origVideo, const Feature* targetVideo, const ResourceLimit* r) 00050 { 00051 assert(origVideo); 00052 assert(targetVideo); 00053 assert(r); 00054 ResourceUsage* u=new ResourceUsage(); 00055 int decoding=cpuCostDecoding(origVideo->dimX,origVideo->dimY,origVideo->frameRate); 00056 int encoding=cpuCostEncoding(targetVideo->dimX,targetVideo->dimY,targetVideo->frameRate); 00057 int spatial=cpuCostResizing(targetVideo->dimX,targetVideo->dimY,targetVideo->frameRate); 00058 int recoding=decoding+encoding; 00059 //we ignore dimY, only dimX can be specified 00060 // we also assume that framerate adjustement can be achieved by B-frame dropping 00061 // we assume only one B-frame between (IPBPBPB) -> (GOP-1)/2 are B-frames 00062 00063 bool transcode=checkTranscoding(origVideo,targetVideo); 00064 00065 if(targetVideo->isCached) { 00066 u->network=((double)targetVideo->bitrate)/r->network; // just sending to client 00067 u->disk=((double)targetVideo->bitrate/8.0)/r->disk; // reading from disk 00068 u->cpu=0.0; // no transcoding 00069 } 00070 else { 00071 // targetvideo not cached 00072 if(origVideo->dimX!=targetVideo->dimX) 00073 recoding+=spatial; 00074 00075 if(origVideo->isCached) { 00076 u->network=((double)targetVideo->bitrate)/r->network; // just sending to client 00077 00078 if(!transcode) { 00079 00080 u->disk=((double)(targetVideo->bitrate/8.0))/r->disk; // reading from disk 00081 u->cpu=0.0; // no transcoding 00082 } 00083 else { 00084 // transcoding, 00085 u->disk=((double)(origVideo->bitrate+targetVideo->bitrate)/8.0)/r->disk; // reading from disk+caching 00086 u->cpu=((double)(recoding))/r->cpu; 00087 } 00088 } 00089 else { 00090 // original not cached 00091 u->network=((double)targetVideo->bitrate+origVideo->bitrate)/r->network; // sending to client+reading orig 00092 if(transcode) 00093 u->disk=((double)(origVideo->bitrate+targetVideo->bitrate)/8.0)/r->disk; // writing orig+transcoded to disk 00094 else 00095 u->disk=((double)(origVideo->bitrate)/8.0)/r->disk; // writing orig to disk 00096 if(transcode) { 00097 u->cpu=((double)(recoding))/r->cpu; 00098 } 00099 else 00100 u->cpu=0.0; 00101 } 00102 } 00103 // DEBUG 00104 // dprintf_full("(%i,%i,%i,%f) --(%i,CPU=%.2lf,NET=%.2lf,DSK=%.2lf)--> (%i,%i,%i,%f)\n",origVideo->dimX,origVideo->dimY,origVideo->bitrate,origVideo->frameRate, recoding,u->cpu,u->network,u->disk,targetVideo->dimX,targetVideo->dimY,targetVideo->bitrate,targetVideo->frameRate); 00105 00106 return u; 00107 }; 00108 00109 double CostFunction::calcWeightedMonetaryCosts( 00110 const ResourceUsage* totalUsed, 00111 const ResourceUsage* req, 00112 const ResourcePrices* prices, 00113 int baseCosts, 00114 int contentCosts, 00115 int startUpDelay, 00116 int maximumDelay) 00117 { 00118 double delay=0.0; 00119 if( startUpDelay >= 0 && startUpDelay<=maximumDelay) { 00120 if(maximumDelay>0) 00121 delay=((double)startUpDelay)/maximumDelay; 00122 else 00123 delay=0.0; 00124 } 00125 else { 00126 // return infinite 00127 return FLT_MAX; 00128 } 00129 if( (totalUsed->network+req->network)>0.99999 || 00130 (totalUsed->cpu+req->cpu)>0.99999 || 00131 (totalUsed->disk+req->cpu)>0.99999) { 00132 // return infinite 00133 // printf("RESOURCE OVERFLOW\r\n"); 00134 return FLT_MAX; 00135 } 00136 return (req->network/(1-totalUsed->network-req->network))*prices->network+ 00137 (req->cpu/(1-totalUsed->cpu-req->cpu))*prices->cpu+ 00138 (req->disk/(1-totalUsed->disk-req->disk))*prices->disk+delay; 00139 }; 00140 00141 double CostFunction::calcFairMonetaryCosts( 00142 const ResourceUsage* req, 00143 const ResourcePrices* priceInCent, 00144 int baseCosts, 00145 int contentCosts, 00146 double videoduration) 00147 { 00148 double result=(double)baseCosts+contentCosts; 00149 double network=0.0,disk=0.0,cpu=0.0, total=0.0; 00150 network=(req->network*priceInCent->network); 00151 network*=videoduration; 00152 disk=(req->disk*priceInCent->disk); 00153 disk*=videoduration; 00154 cpu=req->cpu*priceInCent->cpu; 00155 cpu*=videoduration; 00156 total=disk+network+cpu; 00157 result+=total; 00158 return result; 00159 }; 00160 00161 00162 double CostFunction::calcFinalCosts(double quality, double pay, double weightedcosts) 00163 { 00164 if(weightedcosts>pay || quality < 0.0001) 00165 return FLT_MAX; 00166 // return (quality*pay/totalcosts)+(weightedcosts*totalcosts/pay); 00167 // return (1-quality)+weightedcosts*(totalcosts/pay); //v1 00168 // return 1-quality+weightedcosts+totalcosts/pay; //v2 00169 // return (1-quality)*weightedcosts*3; // 2ndbest so far 00170 // return 10*(1-quality)*(weightedcosts/pay); // best so far 00171 return (1-quality)*weightedcosts; 00172 }; 00173 00174 double CostFunction::calcFinalCosts( 00175 const Request* origVideo, 00176 const Feature* targetVideo, 00177 const ResourceLimit* r, 00178 const ResourceUsage* systemLoad, 00179 const ResourcePrices* prices,int startUpDelay) 00180 { 00181 ResourceUsage* job=CostFunction::calcResourceUsage( &origVideo->sourceVideo, targetVideo, r); 00182 double monetaryCosts=CostFunction::calcWeightedMonetaryCosts(systemLoad,job,prices, 00183 CostFunction::baseCosts,targetVideo->contentCosts,startUpDelay,origVideo->up.delayInMS.point); 00184 double quality=origVideo->up.calcQuality(targetVideo,startUpDelay); 00185 // printf("Quality %lf\r\n",quality); 00186 delete job; 00187 if(quality<0.0001) 00188 return FLT_MAX; 00189 if(monetaryCosts+CostFunction::baseCosts+targetVideo->contentCosts>origVideo->up.pay) 00190 return FLT_MAX; 00191 return CostFunction::calcFinalCosts(quality,origVideo->up.pay,monetaryCosts); 00192 } 00193 00194 // only compares original versions of videos, ignores layers 00195 bool CostFunction::checkTranscoding(const Feature* origVideo, const Feature* targetVideo) { 00196 // only check dimX, dimY is defined through aspect ratio (a constant!!!) and dimX 00197 bool transcode=origVideo->dimX!=targetVideo->dimX; 00198 if(!transcode && origVideo->color) { 00199 // doesn't make sense to transcode from grey to color :-) 00200 transcode=origVideo->color!= targetVideo->color; 00201 } 00202 if(!transcode) { 00203 // bitrate too high 00204 if(origVideo->bitrate>targetVideo->bitrate) { 00205 double newFR; int newBR; 00206 // can we adapt by dropping B-frames? 00207 if(origVideo->canReduceBFramesToBitrate(targetVideo->bitrate,&newFR,&newBR)) { 00208 if(newFR<targetVideo->frameRate) 00209 transcode=true; 00210 } 00211 else 00212 transcode=true; 00213 } 00214 } 00215 return transcode; 00216 } 00217 00218 Feature* CostFunction::findBestVariation(const Request* req,const ResourceUsage* systemLoad, 00219 const ResourceLimit* r,const ResourcePrices* prices, double* lowestCosts, int delayToServer, bool* originalBest) 00220 { 00221 // try all possible combinations of features specified in the userpreferences 00222 assert(req && systemLoad && r && prices && lowestCosts); 00223 assert(originalBest); 00224 // static const int bitrates[]={64000,128000,192000,256000,384000,512000,768000,1024000}; 00225 static const int bitrates[]={1,2,4,8}; 00226 static const int nrBR=4; 00227 *originalBest=false; 00228 00229 int dimx_min=((req->up.dimX.min+43)/44)*44; 00230 int dimx_max=(req->up.dimX.max/44)*44; 00231 Video* target=NULL; 00232 double fr_min=req->up.frameRate.min; 00233 double fr_max=req->up.frameRate.max; 00234 double result,quality,costs; 00235 Video* bestTarget=NULL; 00236 double bestResultCosts=FLT_MAX; 00237 // FILE* fp=fopen("findbestvar.txt","wb"); 00238 00239 // always check the original video first! 00240 int realDelay=0; 00241 if(!req->sourceVideo.isCached) 00242 realDelay=delayToServer; 00243 // bestResultCosts=CostFunction::calcFinalCosts(req,&req->sourceVideo,r,systemLoad,prices,realDelay); 00244 ResourceUsage* job=CostFunction::calcResourceUsage( &req->sourceVideo, &req->sourceVideo, r); 00245 costs=CostFunction::calcWeightedMonetaryCosts(systemLoad,job,prices, 00246 CostFunction::baseCosts,req->sourceVideo.contentCosts,realDelay,req->up.delayInMS.point); 00247 quality=req->up.calcQuality(&req->sourceVideo,realDelay); 00248 if(quality<0.0001) 00249 bestResultCosts=FLT_MAX; 00250 else if(costs+CostFunction::baseCosts+req->sourceVideo.contentCosts>req->up.pay) 00251 bestResultCosts=FLT_MAX; 00252 else 00253 bestResultCosts=CostFunction::calcFinalCosts(quality,req->up.pay,costs); 00254 // minimize transcoding were possible, otherwise check here for full hits! 00255 if(quality>0.01) { 00256 *originalBest=true; 00257 *lowestCosts=bestResultCosts; 00258 delete job; 00259 return new Video(&req->sourceVideo); 00260 } 00261 else { 00262 bestTarget=NULL; 00263 bestResultCosts=FLT_MAX; 00264 } 00265 delete job;job=NULL; 00266 // printf("(%i,%i)Dimx(%i,%i)\r\n",req->up.dimX.min,req->up.dimX.max,dimx_min,dimx_max); 00267 // printf("Framerate(%.2lf,%0.2lf)\r\n",fr_min,fr_max); 00268 // fprintf(fp,"Bitrate\tdimx\tframerate\tresult\tquality\tcosts\r\n"); 00269 for(int dimx=dimx_min;dimx<=dimx_max;dimx+=44) { 00270 int br_min_pos=0; 00271 int nrPixels=(int)(dimx*(((double)dimx)/req->sourceVideo.getAspectRatio())); 00272 00273 while(req->up.bitrate.min>(nrPixels*bitrates[br_min_pos]) && br_min_pos<nrBR) 00274 br_min_pos++; 00275 00276 int br_max_pos=nrBR-1; 00277 while(req->up.bitrate.max<(nrPixels*bitrates[br_max_pos]) && br_min_pos<br_max_pos) 00278 br_max_pos--; 00279 for(int brPos=br_min_pos;brPos<=br_max_pos;brPos++) { 00280 int br=bitrates[brPos]*nrPixels; 00281 // printf("Bitrate %i\r\n",br); 00282 for(double fr=fr_min;fr<=fr_max+0.001;fr+=5.0) { 00283 // assume not cached 00284 // assume that content cost degrade lineary with dimX 00285 int ccost=(int)(((double)dimx)/req->sourceVideo.dimX*req->sourceVideo.contentCosts); 00286 target=new Video(dimx,(int)(((double)dimx)/req->sourceVideo.getAspectRatio()), 00287 req->up.color.point,br,0,ccost,fr,req->sourceVideo.durationInSec); 00288 // assume startup delay of 1 second 00289 // result=CostFunction::calcFinalCosts(req,target,r,systemLoad,prices,delayToServer); 00290 job=CostFunction::calcResourceUsage( &req->sourceVideo, target, r); 00291 costs=CostFunction::calcWeightedMonetaryCosts(systemLoad,job,prices, 00292 CostFunction::baseCosts,target->contentCosts,delayToServer,req->up.delayInMS.point); 00293 quality=req->up.calcQuality(target,delayToServer); 00294 if(quality<0.0001) 00295 result=FLT_MAX; 00296 else if(costs+CostFunction::baseCosts+ccost>req->up.pay) 00297 result=FLT_MAX; 00298 else 00299 result=CostFunction::calcFinalCosts(quality,req->up.pay,costs); 00300 // fprintf(fp,"%6i %6i %.6lf %.6lf %.6lf %.6lf\r\n",br,dimx,fr,result,quality,costs); 00301 // printf("Costs: %.3lf Quality: %.3lf Result: %.3lf \r\n",costs,quality,result); 00302 if(result<bestResultCosts) { 00303 if(bestTarget) 00304 delete bestTarget; 00305 bestTarget=target; 00306 // frame dropping hack: when dropping B-frames never store the adapted version in the cache 00307 // store the original one, detect this case by checking cpu usage of the task 00308 if(job->cpu<0.00001) 00309 printf("Detected TEMPORAL ADAPTATION\r\n"); 00310 *originalBest=(job->cpu<0.00001); 00311 //*originalBest=false; 00312 bestResultCosts=result; 00313 target=NULL; 00314 } 00315 if(target) { 00316 delete target; 00317 target=NULL; 00318 } 00319 if(job) { 00320 delete job; 00321 job=NULL; 00322 } 00323 } 00324 } 00325 } 00326 00327 00328 00329 // fprintf(fp,"%6i %6i %.6lf %.6lf %.6lf %.6lf\r\n",req->sourceVideo.bitrate, 00330 // req->sourceVideo.dimX,req->sourceVideo.frameRate,result,quality,costs); 00331 00332 if(target) { 00333 delete target; 00334 target=NULL; 00335 } 00336 if(job) { 00337 delete job; 00338 job=NULL; 00339 } 00340 00341 // fclose(fp); 00342 *lowestCosts=bestResultCosts; 00343 return bestTarget; 00344 00345 }; 00346 00349 void CostFunction::cleanUserPreferences(UserPreferences* u, const Video* source) 00350 { 00351 if(u->frameRate.min>source->frameRate) { 00352 u->frameRate.min=source->frameRate; 00353 u->frameRate.max=source->frameRate; 00354 } 00355 if(u->frameRate.max>source->frameRate) 00356 u->frameRate.max=source->frameRate; 00357 if(u->bitrate.min>source->bitrate) 00358 u->bitrate.min=source->bitrate-1; 00359 }; 00360