00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #include <math.h>
00028 #include <stdio.h>
00029 #include <stdlib.h>
00030 #include <string.h>
00031 #include <strings.h>
00032 #include <assert.h>
00033 #include <iostream>
00034
00035 #include "agent.h"
00036
00037
00038 #define _RED_ROUTER_MAIN_
00039 #include "asim.h"
00040
00041 #define sp " "
00042
00043 typedef struct c{
00044 int no;
00045 double delay;
00046 double drop;
00047 double p_tput;
00048 double t;
00049
00050 int is_sflow;
00051 double slambda;
00052 int snopkts;
00053 RedRouter * red;
00054 int scaled;
00055 }flow_stats;
00056
00057 typedef struct n{
00058 int red;
00059 double pmin, pmax, minth, maxth;
00060 double lambda;
00061 double plambda;
00062 double tlambda;
00063 double mu;
00064 double prop;
00065 double qdelay;
00066 int buffer;
00067 double drop;
00068 int nflows;
00069 int *theflows;
00070 double scaled_lambda;
00071 double unscaled_lambda;
00072
00073 double utput;
00074 double uc;
00075
00076
00077 RedRouter * redrouter;
00078
00079 }link_stats;
00080
00081
00082 class asim : public NsObject{
00083
00084 public:
00085
00086
00087 int nConnections;
00088 int K, MaxHops;
00089 int nLinks;
00090 int **Adj;
00091 int *nAdj;
00092
00093 link_stats* links;
00094 flow_stats* flows;
00095
00096 double min(double x, double y){
00097 return (x<y)?x:y;
00098 }
00099
00100 double padhye(double rtt, double p){
00101
00102 double rto = 1;
00103 double t=1;
00104 t = rtt*sqrt(2*p/3)+rto*min(1,(3*sqrt(3*p/8)))*p*(1+32*p*p);
00105 return min(20/rtt,1/t);
00106
00107 }
00108
00109 double Po(double rho, int K){
00110
00111 if(rho==1)
00112 return 1.0/(K+1);
00113
00114 double t;
00115 t=(1.0*(1-rho))/(1.0-pow(rho,K));
00116 return t;
00117
00118 }
00119
00120 double Pk(double rho, int K, int k){
00121
00122 if(rho==1)
00123 return 1.0/(K+1);
00124
00125 double t;
00126 t=(1-rho)*pow(rho,k);
00127 t/=1-pow(rho,K+1);
00128 return t;
00129 }
00130
00131 double Lq(double rho, int K){
00132
00133 double t1,t2;
00134
00135 if(rho==1){
00136 return (1.0*K*(K-1))/(2.0*(K+1));
00137 }
00138
00139 t1=rho*1.0/(1-rho);
00140 t2=rho*1.0/(1-pow(rho,K+1));
00141 t2*=K*pow(rho,K)+1;
00142 return (t1-t2)/2;
00143
00144 }
00145
00146 int command (int argc, const char*const* argv){
00147
00148 if (strcmp(argv[1], "run") == 0) {
00149 int niter=0;
00150 for(int i=0; i<20; i++){
00151 CalcLinkDelays(1);
00152 CalcPerFlowDelays();
00153 newupdate(niter);
00154 }
00155
00156 return (TCL_OK);
00157 }
00158
00159 if (strcmp(argv[1], "readinput") == 0) {
00160 GetInputs((char*)argv[2]);
00161
00162 return (TCL_OK);
00163 }
00164
00165 if (strcmp(argv[1], "get-link-drop") == 0) {
00166 cout << "Hi";
00167 Tcl& tcl = Tcl::instance();
00168 tcl.resultf("%lf",get_link_drop(atoi(argv[2])));
00169 return (TCL_OK);
00170 }
00171
00172 if (strcmp(argv[1], "get-link-delay") == 0) {
00173 Tcl& tcl = Tcl::instance();
00174 tcl.resultf("%lf",get_link_delay(atoi(argv[2])));
00175 return (TCL_OK);
00176 }
00177
00178 if (strcmp(argv[1], "get-link-tput") == 0) {
00179 Tcl& tcl = Tcl::instance();
00180 tcl.resultf("%lf",get_link_tput(atoi(argv[2])));
00181 return (TCL_OK);
00182 }
00183
00184 if (strcmp(argv[1], "get-flow-tput") == 0) {
00185 Tcl& tcl = Tcl::instance();
00186 tcl.resultf("%lf",get_flow_tput(atoi(argv[2])));
00187 return (TCL_OK);
00188 }
00189
00190 if (strcmp(argv[1], "get-flow-delay") == 0) {
00191 Tcl& tcl = Tcl::instance();
00192 tcl.resultf("%lf",get_flow_delay(atoi(argv[2])));
00193 return (TCL_OK);
00194 }
00195
00196 if (strcmp(argv[1], "get-flow-drop") == 0) {
00197 Tcl& tcl = Tcl::instance();
00198 tcl.resultf("%lf",get_flow_drop(atoi(argv[2])));
00199 return (TCL_OK);
00200 }
00201
00202 }
00203
00204 double get_link_drop(int x){
00205 assert(x<nLinks);
00206 return links[x].drop;
00207 cout << "Hi there";
00208 PrintResults();
00209 }
00210
00211 double get_link_delay(int x){
00212 assert(x<nLinks);
00213 return links[x].qdelay + links[x].prop ;
00214 }
00215
00216 double get_link_qdelay(int x){
00217 assert(x<nLinks);
00218 return links[x].qdelay;
00219 }
00220
00221 double get_link_pdelay(int x){
00222 assert(x<nLinks);
00223 return links[x].prop;
00224 }
00225
00226 double get_link_tput(int x){
00227 assert(x<nLinks);
00228 return links[x].lambda;
00229 }
00230
00231 double get_flow_delay(int x){
00232 assert(x<nConnections);
00233 return flows[x].delay;
00234 }
00235
00236 double get_flow_tput(int x){
00237 assert(x<nConnections);
00238 return flows[x].p_tput;
00239 }
00240
00241 double get_flow_drop(int x){
00242 assert(x<nConnections);
00243 return flows[x].drop;
00244 }
00245
00246 void GetInputs(char *argv) {
00247
00248
00249
00250
00251
00252
00253
00254
00255
00256 MaxHops = 0;
00257
00258
00259
00260
00261
00262 nConnections = 0;
00263 nLinks = 0;
00264
00265
00266 FILE *f;
00267 f = fopen(argv,"r");
00268 assert(f);
00269
00270 char s[256];
00271 while (fgets(s, 255, f)) {
00272
00273
00274 char *t;
00275 t = strtok(s, " \t\n");
00276
00277
00278 if (!t || !t[0] || (t[0] == '#') || !strncasecmp(t, "comment", 6))
00279 continue;
00280
00281
00282 if (!strcasecmp(t,"n")) {
00283 t = strtok(NULL," \t");
00284 assert(t);
00285 nConnections = atoi(t);
00286 assert(nConnections > 0);
00287 assert(nConnections >= 0);
00288 nAdj = new int[nConnections];
00289 Adj = new int*[nConnections];
00290 flows = new flow_stats[nConnections];
00291 for (int i=0; i<nConnections; ++i)
00292 nAdj[i] = -1;
00293 continue;
00294 }
00295
00296
00297 else if (!strcasecmp(t,"m")) {
00298
00299 t = strtok(NULL," \t");
00300 assert(t);
00301
00302 nLinks = atoi(t);
00303 assert(nLinks > 0);
00304
00305 links = new link_stats[nLinks];
00306 continue;
00307 }
00308
00309
00310 else if (!strcasecmp(t,"route")) {
00311
00312 assert (nConnections > 0);
00313 assert (nLinks > 0);
00314 t = strtok(NULL," \t");
00315 assert(t);
00316 int i = atoi(t);
00317 assert(i > 0 && i<= nConnections);
00318 i--;
00319
00320
00321 flows[i].is_sflow = 0;
00322 flows[i].drop = 0;
00323 flows[i].scaled = 0;
00324
00325 t = strtok(NULL," \t");
00326 assert(t);
00327 nAdj[i] = atoi(t);
00328 assert(nAdj[i] > 0 && nAdj[i] <= nLinks);
00329 Adj[i] = new int[nAdj[i]];
00330 for (int j=0; j<nAdj[i]; ++j) {
00331 t = strtok(NULL," \t");
00332 assert(t);
00333 int l = atoi(t);
00334 assert(l > 0 && l <= nLinks);
00335 l--;
00336 Adj[i][j] = l;
00337 }
00338
00339 if (MaxHops < nAdj[i]) MaxHops = nAdj[i];
00340
00341
00342 t = strtok(NULL," \t");
00343
00344
00345
00346
00347 if (t && !strcasecmp(t,"sh")) {
00348
00349 flows[i].is_sflow = 1;
00350
00351
00352 t = strtok(NULL," \t");
00353 assert(t);
00354 double tmp = atof(t);
00355 flows[i].slambda = tmp;
00356
00357
00358 t = strtok(NULL," \t");
00359 assert(t);
00360 int tmpi = atoi(t);
00361 flows[i].snopkts = tmpi;
00362 }
00363
00364 continue;
00365 }
00366
00367 else if(!strcasecmp(t,"link")){
00368
00369 assert (nLinks > 0);
00370
00371
00372 t = strtok(NULL," \t");
00373 assert(t);
00374 int i = atoi(t);
00375 assert(i > 0 && i<= nLinks);
00376 i--;
00377
00378
00379 t = strtok(NULL," \t");
00380 assert(t);
00381 double p = atof(t);
00382 assert(p>=0);
00383 links[i].prop = p;
00384
00385
00386 t = strtok(NULL," \t");
00387 assert(t);
00388 p = atof(t);
00389 assert(p>=0);
00390 links[i].lambda = 0;
00391 links[i].tlambda = p;
00392 links[i].plambda = p;
00393
00394
00395 t = strtok(NULL," \t");
00396 assert(t);
00397 p = atof(t);
00398 assert(p>=0);
00399 links[i].mu = p;
00400
00401
00402 t = strtok(NULL," \t");
00403 assert(t);
00404 int t1 = atoi(t);
00405 assert(t1>0);
00406 links[i].buffer = t1;
00407
00408
00409 t = strtok(NULL," \t");
00410 if(t && !strcasecmp(t,"red")){
00411
00412
00413
00414
00415 links[i].red=1;
00416
00417 t = strtok(NULL," \t");
00418 double dt = atof(t);
00419
00420 links[i].minth=dt;
00421
00422
00423 t = strtok(NULL," \t");
00424 dt = atof(t);
00425
00426 links[i].pmin=dt;
00427
00428
00429 t = strtok(NULL," \t");
00430 dt = atof(t);
00431
00432 links[i].maxth=dt;
00433
00434
00435 t = strtok(NULL," \t");
00436 dt = atof(t);
00437
00438 links[i].pmax=dt;
00439
00440
00441
00442 links[i].redrouter = new RedRouter((int)links[i].minth,
00443 (int)links[i].maxth,
00444 links[i].pmax);
00445 assert(links[i].red);
00446
00447 }
00448 else{
00449 links[i].red=0;
00450 }
00451
00452 continue;
00453
00454 }
00455
00456 assert(0);
00457 }
00458
00459
00460 assert (nConnections > 0);
00461 assert (nLinks > 0);
00462 int i;
00463 for (i=0; i<nConnections; ++i)
00464 assert(nAdj[i] > 0);
00465
00466
00467
00468
00469
00470 for(i=0;i<nLinks;i++){
00471
00472
00473 int c=0; links[i].tlambda=0;
00474
00475 for(int j=0;j<nConnections;j++){
00476 for(int k=0;k<nAdj[j];k++){
00477 if(Adj[j][k]==i){
00478 c++;
00479 }
00480 }
00481 }
00482 links[i].nflows=c;
00483
00484
00485 if(c){
00486 links[i].theflows = new int[c];
00487 c = 0;
00488
00489 for(int j=0;j<nConnections;j++){
00490 for(int k=0;k<nAdj[j];k++){
00491 if(Adj[j][k]==i){
00492 if(flows[j].is_sflow){
00493 links[i].lambda+=flows[j].slambda*flows[j].snopkts;
00494 }
00495 links[i].theflows[c++]=j;
00496
00497 }
00498 }
00499 }
00500
00501 }
00502
00503 else links[i].theflows = 0;
00504
00505
00506
00507
00508 }
00509
00510
00511
00512
00513
00514
00515
00516
00517
00518
00519
00520
00521
00522 }
00523
00524
00525
00526 double redFn(double minth, double pmin,
00527 double maxth, double pmax, double qlength){
00528
00529 assert(qlength>=0 && qlength<=1);
00530 assert(pmax>=0 && pmax<=1);
00531 assert(pmin>=0 && pmin<=1);
00532 assert(minth>=0 && minth<=1);
00533 assert(maxth>=0 && maxth<=1);
00534 assert(maxth>=minth);
00535 assert(pmax>pmin);
00536
00537 double t;
00538 if(qlength<minth)
00539 return 0;
00540 if(qlength>maxth)
00541 return 1;
00542 return pmin + (qlength-minth)/(pmax-pmin);
00543
00544 }
00545
00546
00547 void CalcLinkDelays(int flag = 0){
00548
00549
00550
00551
00552
00553 for(int i=0; i<nLinks; i++){
00554
00555 double rho = links[i].lambda/links[i].mu;
00556 double qlength = Lq(rho,links[i].buffer);
00557
00558 links[i].qdelay = qlength/links[i].mu;
00559 links[i].drop = Pk(rho,links[i].buffer,links[i].buffer);
00560
00561
00562
00563 if(flag){
00564 if(links[i].red){
00565 double minth, maxth, pmin, pmax, delay,p;
00566 minth = links[i].minth;
00567 maxth = links[i].maxth;
00568 pmin = links[i].pmin;
00569 pmax = links[i].pmax;
00570
00571
00572
00573
00574
00575
00576
00577 p=(links[i].redrouter)->ComputeProbability(rho, delay);
00578 links[i].drop = p;
00579 qlength = Lq(rho*(1-p), links[i].buffer);
00580 links[i].qdelay = delay;
00581 }
00582 }
00583
00584
00585
00586
00587
00588 }
00589
00590 }
00591
00592 void CalcPerFlowDelays(){
00593 for(int i=0; i<nConnections; i++){
00594 double d = 0, p = 1 ;
00595
00596 for(int j=0;j<nAdj[i];j++){
00597 d += 2*links[Adj[i][j]].prop;
00598 p *= 1-links[Adj[i][j]].drop;
00599 }
00600 p = 1-p;
00601
00602 flows[i].no = nAdj[i];
00603 flows[i].delay = d;
00604 flows[i].drop = p;
00605 flows[i].t = flows[i].p_tput;
00606
00607
00608
00609
00610
00611
00612
00613 if(flows[i].is_sflow){
00614
00615
00616 double t = (flows[i].slambda*flows[i].snopkts);
00617 flows[i].p_tput = t/(1-p);
00618 }
00619 else{
00620
00621 if(!p){
00622
00623 }
00624 flows[i].p_tput = padhye(d,p);
00625 }
00626
00627
00628
00629
00630
00631 }
00632 }
00633
00634 void PrintData(){
00635 for(int i=0;i<nLinks;i++){
00636 cout << i << sp << links[i].lambda << sp << links[i].mu;
00637 cout << sp << links[i].buffer << endl;
00638 }
00639 }
00640
00641 void PrintResults(){
00642 int i;
00643
00644 for(i=0;i<nLinks;i++){
00645
00646 cout << sp << "Qdelay = " << links[i].prop << sp << links[i].lambda;
00647 cout << sp << links[i].drop << endl;
00648 }
00649
00650 for(i=0; i<nConnections; i++){
00651 cout << i << sp << flows[i].delay << sp;
00652 cout << flows[i].drop << sp << flows[i].p_tput << sp;
00653 cout << sp << endl;
00654 }
00655
00656 }
00657
00658 void UpdateHelper(int flag=0){
00659
00660
00661
00662
00663 int i;
00664 for(i=0; i<nLinks; i++){
00665 links[i].tlambda=0;
00666 }
00667
00668 for(i=0; i<nConnections; i++){
00669 if(!flag || !flows[i].scaled)
00670 for(int j=0;j<nAdj[i];j++)
00671 links[Adj[i][j]].tlambda += flows[i].p_tput;
00672
00673 }
00674
00675 }
00676
00677
00678 void Update(int niter){
00679
00680 UpdateHelper();
00681
00682 for(int i=0; i<nLinks; i++){
00683 links[i].plambda = links[i].lambda;
00684 double t;
00685 double tk=links[i].mu*(1.1);
00686
00687 if(niter){
00688 if(links[i].tlambda>tk)
00689
00690 t = ((links[i].lambda)+tk)/2;
00691
00692 else
00693
00694 t= ((links[i].tlambda)+(links[i].lambda))/2;
00695
00696 }
00697 else t = links[i].tlambda;
00698 links[i].lambda = t;
00699 }
00700
00701 }
00702
00703
00704 void Update2(){
00705
00706 UpdateHelper();
00707
00708 for(int i=0; i<nLinks; i++){
00709 links[i].plambda = links[i].lambda;
00710 links[i].lambda = (links[i].lambda + links[i].tlambda)/2;
00711 }
00712 }
00713
00714 int allscaled(){
00715
00716
00717
00718 for(int i=0; i<nConnections; i++)
00719 if(!flows[i].is_sflow && !flows[i].scaled){
00720 cout << "Connection " << i << " not scaled as yet\n";
00721 return 0;
00722 }
00723
00724
00725
00726 return 1;
00727
00728 }
00729
00730
00731 void Update3(int flag = 0){
00732
00733
00734
00735
00736 double maxtlambda = -1e7;
00737 int bneck = -1;
00738 int i;
00739
00740
00741 for(i=0; i<nConnections; i++)
00742 flows[i].scaled = 0;
00743
00744
00745 UpdateHelper();
00746
00747
00748
00749 for(i=0; i<nLinks; i++){
00750
00751 if(links[i].tlambda>maxtlambda){
00752 bneck = i;
00753 maxtlambda = links[i].tlambda;
00754 }
00755 }
00756
00757 cout << "bottleneck = " << bneck << sp << maxtlambda <<endl;
00758
00759 double tk = links[bneck].mu*(1+links[bneck].drop)+5;
00760
00761
00762 while((maxtlambda > tk + 1) && ! allscaled()){
00763
00764 cout << "Maxtlambda = " << maxtlambda << " bneck = " << bneck << endl;
00765
00766
00767
00768
00769 assert(bneck>=0 && bneck<=nLinks);
00770 int i;
00771 for(i=0; i<links[bneck].nflows; i++){
00772
00773
00774 int t = links[bneck].theflows[i];
00775
00776
00777 if(flag){
00778 if(!flows[t].is_sflow && !flows[t].scaled){
00779 flows[t].p_tput *= (tk)/maxtlambda;
00780
00781 flows[t].scaled = 1;
00782 }
00783 }
00784 else
00785 flows[t].p_tput *= (tk)/maxtlambda;
00786 flows[t].scaled = 1;
00787
00788 }
00789
00790 for (i=0; i<nLinks;i++){
00791 cout << "Link " << i << " tlambda = " << links[i].tlambda << endl;
00792 }
00793
00794 char x =getchar();
00795
00796
00797 UpdateHelper(0);
00798
00799
00800 bneck = -1;
00801 maxtlambda = -1e7;
00802 for(i=0; i<nLinks; i++){
00803 if(links[i].tlambda>maxtlambda){
00804 bneck = i;
00805 maxtlambda = links[i].tlambda;
00806 }
00807 }
00808
00809
00810 tk = links[bneck].mu*(1+links[bneck].drop)+5;
00811
00812
00813 }
00814
00815 Update(0);
00816 cout << "Out of the converge loop\n";
00817 for (i =0; i<nLinks;i++){
00818 cout << "Link " << i << " tlambda = " << links[i].tlambda << endl;
00819 }
00820
00821 }
00822
00823
00824 void newupdate(int niter){
00825
00826 int i;
00827
00828
00829 for (i=0;i<nLinks;i++){
00830 links[i].uc = links[i].mu*(1.1);
00831 links[i].utput = 0;
00832 }
00833
00834
00835
00836
00837 for(i=0; i<nConnections; i++){
00838 if(flows[i].is_sflow)
00839 flows[i].scaled = 1;
00840 else
00841 flows[i].scaled = 0;
00842 for(int j=0;j<nAdj[i];j++){
00843 if(flows[i].is_sflow)
00844 links[Adj[i][j]].uc -= flows[i].p_tput;
00845 else
00846 links[Adj[i][j]].utput += flows[i].p_tput;
00847 }
00848 }
00849
00850
00851
00852
00853
00854 double maxgamma;
00855 int bneck;
00856 double t;
00857
00858 bneck = -1;
00859 maxgamma = 0;
00860 for(i=0; i<nLinks; i++){
00861 if(links[i].uc){
00862 t=links[i].utput/links[i].uc;
00863 if(t > maxgamma){
00864 bneck = i;
00865 maxgamma = t;
00866 }
00867 }
00868 }
00869
00870
00871
00872
00873
00874
00875
00876
00877
00878
00879
00880
00881
00882
00883
00884 while(bneck+1){
00885
00886
00887
00888 for(i=0; i<links[bneck].nflows; i++){
00889
00890 int t = links[bneck].theflows[i];
00891
00892
00893
00894 if(!flows[t].is_sflow && !flows[t].scaled){
00895 flows[t].p_tput /= maxgamma;
00896
00897 flows[t].scaled = 1;
00898 for(int j=0;j<nAdj[t];j++){
00899
00900
00901 links[Adj[t][j]].uc -= flows[t].p_tput;
00902 links[Adj[t][j]].utput -= flows[t].p_tput*maxgamma;
00903
00904 }
00905
00906 }
00907 }
00908
00909
00910
00911 links[bneck].uc = 0;
00912
00913 bneck = -1;
00914 maxgamma = 0;
00915 for(i=0; i<nLinks; i++){
00916 if(links[i].uc){
00917 t=links[i].utput/links[i].uc;
00918 if(t > maxgamma){
00919 bneck = i;
00920 maxgamma = t;
00921 }
00922 }
00923 }
00924
00925
00926
00927
00928
00929
00930
00931
00932
00933
00934
00935
00936
00937 }
00938
00939 Update(niter);
00940
00941 }
00942
00943
00944 asim(){
00945
00946 }
00947
00948 void recv(Packet *, Handler * = 0){}
00949
00950 };
00951
00952
00953
00954 static class AsimClass : public TclClass {
00955 public:
00956 AsimClass(): TclClass("Asim"){ }
00957 TclObject * create(int, const char*const*) {
00958 return (new asim());
00959 }
00960 } class_asim;
00961
00962
00963
00964
00965
00966
00967
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979
00980
00981
00982
00983
00984
00985
00986
00987
00988
00989
00990
00991
00992
00993
00994
00995
00996
00997
00998
00999
01000