git.sesse.net Git - nms/blob - planning/planning.cpp

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <unistd.h>
   4 #include <limits.h>
   5 #include <vector>
   6 #include <map>
   7 #include <algorithm>
   8 #include <string>
   9
  10 #define NUM_DISTRO 5
  11 #define SWITCHES_PER_ROW 6
  12 #define TRUNCATE_METRIC 1
  13 #define TENPLUSTEN 250
  14 #define THIRTYPLUSTEN 450
  15 #define FIFTYPLUSTEN 650
  16
  17 struct sw {
  18         unsigned char row, num;
  19
  20         sw(unsigned char row, unsigned char num) : row(row), num(num) {}
  21 };
  22 int distro_placements[NUM_DISTRO] = {
  23         5, 12, 19, 26, 33
  24         // 3, 7, 12, 19, 26, 31, 35
  25 };
  26 unsigned horiz_cost[SWITCHES_PER_ROW] = {
  27         // one seat is 80cm wide. first switch is after 6 seats, then 18, then
  28         // 30. gap is 5m extra (the distribution switches are on the eastern
  29         // side).
  30         290, 194, 98, 48, 144, 240
  31 };
  32
  33 // memoization table
  34 struct key {
  35         unsigned char sw_ind, distro_bound, distro_bound_hard;
  36         unsigned char ports_left[NUM_DISTRO];
  37
  38         bool operator< (const key &other) const
  39         {
  40                 if (sw_ind != other.sw_ind)
  41                         return (sw_ind < other.sw_ind);
  42                 if (distro_bound != other.distro_bound)
  43                         return (distro_bound < other.distro_bound);
  44                 if (distro_bound_hard != other.distro_bound_hard)
  45                         return (distro_bound_hard < other.distro_bound_hard);
  46                 for (unsigned i = distro_bound_hard; i < NUM_DISTRO - 1; ++i)
  47                         if (ports_left[i] != other.ports_left[i])
  48                                 return (ports_left[i] < other.ports_left[i]);
  49                 return (ports_left[NUM_DISTRO - 1] < other.ports_left[NUM_DISTRO - 1]);
  50         }
  51 };
  52 struct value {
  53         unsigned char distro;
  54         unsigned cost, this_cost, this_distance;
  55 };
  56 std::map<key, value> cache;
  57 unsigned cache_hits = 0;
  58 std::vector<sw> switches;
  59 std::map<unsigned, unsigned> num_ports_used;
  60
  61 unsigned find_distance(sw from_where, unsigned distro)
  62 {
  63         // 3.7m from row to row (2.5m gap + 1.2m boards)
  64         unsigned base_cost = 37 * abs(from_where.row - distro_placements[distro]) + horiz_cost[from_where.num];
  65
  66         // 4m, 5m, 4m gaps (1.5m, 2.5m, 1.5m extra)
  67         if ((from_where.row <= 9) == (distro_placements[distro] >= 10))
  68                 base_cost += 15;
  69         if ((from_where.row <= 17) == (distro_placements[distro] >= 18))
  70                 base_cost += 25;
  71         if ((from_where.row <= 25) == (distro_placements[distro] >= 26))
  72                 base_cost += 15;
  73
  74         // add 5.6m slack.
  75         return base_cost + 56;
  76 }
  77
  78 unsigned cable_select(unsigned distance)
  79 {
  80
  81         if (distance > 600)
  82                 return 1000;
  83         if (distance > 500)
  84                 return FIFTYPLUSTEN;
  85         if (distance > 400)
  86                 return 500;
  87         if (distance > 300)
  88                 return THIRTYPLUSTEN;
  89         if (distance > 200)
  90                 return 300;
  91         if (distance > 100)
  92                 return TENPLUSTEN;
  93         return 100;
  94 }
  95
  96 unsigned find_slack(unsigned distance)
  97 {
  98         switch (cable_select(distance)) {
  99         case 1000:
 100                 return 1000 - distance;
 101         case FIFTYPLUSTEN:
 102                 return 600 - distance;
 103         case 500:
 104                 return 500 - distance;
 105         case THIRTYPLUSTEN:
 106                 return 400 - distance;
 107         case 300:
 108                 return 300 - distance;
 109         case TENPLUSTEN:
 110                 return 200 - distance;
 111         case 100:
 112                 return 100 - distance;
 113         }
 114 }
 115
 116 unsigned find_cost(unsigned distance)
 117 {
 118         //return find_slack(distance);
 119
 120 #if TRUNCATE_METRIC
 121         return cable_select(distance);
 122 #else
 123         return distance;
 124 //      return ((distance + 90) / 100) * 100;
 125 #endif
 126 }
 127
 128 unsigned find_optimal_cost(key &k)
 129 {
 130         unsigned best_cost = 999999990, best_this_cost = 0, best_this_distance = 0;
 131         int best = -1;
 132         unsigned char db = k.distro_bound;
 133         unsigned char dbh = k.distro_bound_hard;
 134
 135         if (k.sw_ind == switches.size())
 136                 return 0;
 137         if (cache.count(k)) {
 138                 ++cache_hits;
 139                 return cache[k].cost;
 140         }
 141
 142         bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
 143
 144         for (unsigned char i = dbh; i < dbh + 2 && i < NUM_DISTRO; ++i) {
 145                 if (k.ports_left[i] == 0)
 146                         continue;
 147
 148                 unsigned distance = find_distance(switches[k.sw_ind], i);
 149                 unsigned cost = find_cost(distance);
 150
 151                 --(k.ports_left[i]);
 152                 ++(k.sw_ind);
 153
 154                 k.distro_bound = std::max(i, db);
 155                 if (next_changes_row) {
 156                         k.distro_bound_hard = k.distro_bound;
 157                 }
 158
 159                 cost += find_optimal_cost(k);
 160                 --(k.sw_ind);
 161                 ++(k.ports_left[i]);
 162
 163                 if (best == -1 || cost < best_cost) {
 164                         best = i;
 165                         best_cost = cost;
 166                         best_this_distance = distance;
 167                         best_this_cost = find_cost(distance);
 168                 }
 169         }
 170         k.distro_bound = db;
 171         k.distro_bound_hard = dbh;
 172
 173         value v = { best, best_cost, best_this_cost, best_this_distance };
 174         cache[k] = v;
 175
 176         return best_cost;
 177 }
 178
 179 std::string port_name(unsigned distro, unsigned portnum)
 180 {
 181         char buf[16];
 182
 183         if (distro == 0) {
 184                 if (portnum < 23) {
 185                         sprintf(buf, "d01-1 g0/%u", portnum);
 186                 } else {
 187                         sprintf(buf, "d01-2 g0/%u", portnum - 22);
 188                 }
 189         } else if (distro == 1) {
 190                 sprintf(buf, "d02 g1/0/%u", portnum);
 191         } else if (distro == 2) {
 192                 sprintf(buf, "d03 g1/%u", portnum);
 193         } else if (distro == 3) {
 194                 sprintf(buf, "d04 g1/0/%u", portnum);
 195         } else if (distro == 4) {
 196                 if (portnum < 23) {
 197                         sprintf(buf, "d05-1 g0/%u", portnum);
 198                 } else {
 199                         sprintf(buf, "d05-2 g0/%u", portnum - 22);
 200                 }
 201         } else {
 202                 sprintf(buf, "d%02u 1/0/%u", distro + 1, portnum);
 203         }
 204
 205         return buf;
 206 }
 207
 208 int main(int argc, char **argv)
 209 {
 210         struct key start;
 211         FILE *patchlist = fopen("patchlist.txt", "w");
 212         FILE *switchlist = fopen("switches.txt", "w");
 213 #if TRUNCATE_METRIC
 214         std::map<unsigned, unsigned> cable_count;
 215 #endif
 216         unsigned total_slack = 0;
 217
 218 #if 0
 219         // used for placement optimization
 220         distro_placements[0] = atoi(argv[1]);
 221         distro_placements[1] = atoi(argv[2]);
 222         distro_placements[2] = atoi(argv[3]);
 223         distro_placements[3] = atoi(argv[4]);
 224         distro_placements[4] = atoi(argv[5]);
 225         distro_placements[5] = atoi(argv[6]);
 226         distro_placements[6] = atoi(argv[7]);
 227 #endif
 228
 229         switches.push_back(sw(1, 3));
 230         switches.push_back(sw(1, 4));
 231         switches.push_back(sw(1, 5));
 232         switches.push_back(sw(2, 3));
 233         switches.push_back(sw(2, 4));
 234         switches.push_back(sw(2, 5));
 235
 236         for (unsigned i = 3; i <= 15; ++i)
 237                 for (unsigned j = 0; j < SWITCHES_PER_ROW; ++j)
 238                         switches.push_back(sw(i, j));
 239
 240         switches.push_back(sw(16, 0));
 241         switches.push_back(sw(16, 1));
 242         switches.push_back(sw(16, 2));
 243         switches.push_back(sw(16, 4));
 244         switches.push_back(sw(16, 5));
 245
 246         switches.push_back(sw(17, 0));
 247         switches.push_back(sw(17, 1));
 248         switches.push_back(sw(17, 2));
 249         switches.push_back(sw(17, 4));
 250         switches.push_back(sw(17, 5));
 251
 252         for (unsigned i = 18; i <= 34; ++i)
 253                 for (unsigned j = 0; j < SWITCHES_PER_ROW; ++j)
 254                         switches.push_back(sw(i, j));
 255
 256         switches.push_back(sw(35, 3));
 257         switches.push_back(sw(35, 4));
 258         switches.push_back(sw(35, 5));
 259
 260         switches.push_back(sw(36, 3));
 261         switches.push_back(sw(36, 4));
 262         switches.push_back(sw(36, 5));
 263
 264         start.sw_ind = 0;
 265         start.distro_bound = 0;
 266         start.distro_bound_hard = 0;
 267         start.ports_left[0] = 44;
 268         start.ports_left[1] = 42;
 269         start.ports_left[2] = 37;
 270         start.ports_left[3] = 42;
 271         start.ports_left[4] = 44;
 272
 273 #if 0
 274         // split distro
 275         start.ports_left[0] = 22;
 276         start.ports_left[1] = 22;
 277         start.ports_left[2] = 42;
 278         start.ports_left[3] = 37;
 279         start.ports_left[4] = 42;
 280         start.ports_left[5] = 22;
 281         start.ports_left[6] = 22;
 282 #endif
 283
 284         printf("Finding optimal layout for %u switches\n", switches.size());
 285         find_optimal_cost(start);
 286         printf("%u cache nodes, %u cache hits.\n", cache.size(), cache_hits);
 287
 288         key k = start;
 289         int last_row = 0, last_num = -1;
 290         for (unsigned i = 0; i < switches.size(); ++i) {
 291                 value v = cache[k];
 292                 bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
 293
 294                 if (cache.count(k) == 0) {
 295                         fprintf(stderr, "FATAL: no solutions!\n");
 296                         exit(1);
 297                 }
 298
 299                 k.distro_bound = std::max(k.distro_bound, v.distro);
 300                 if (next_changes_row)
 301                         k.distro_bound_hard = k.distro_bound;
 302
 303                 if (last_row != switches[k.sw_ind].row) {
 304                         printf("\n%2u-%2u    ", switches[k.sw_ind].row * 2 - 1, switches[k.sw_ind].row * 2 + 0 );
 305                         last_num = -1;
 306                 }
 307                 for (int j = last_num; j + 1 < switches[k.sw_ind].num; ++j) {
 308                         printf("%11s", "");
 309                 }
 310
 311
 312                 printf("\e[%um%u ", v.distro + 33, v.distro);
 313 #if TRUNCATE_METRIC
 314                 if (cable_select(v.this_distance) == FIFTYPLUSTEN)
 315                         printf("(50+10)  ");
 316                 else if (cable_select(v.this_distance) == THIRTYPLUSTEN)
 317                         printf("(30+10)  ");
 318                 else if (cable_select(v.this_distance) == TENPLUSTEN)
 319                         printf("(10+10)  ");
 320                 else
 321                         printf("(%-3u  )  ", cable_select(v.this_distance) / 10);
 322                 total_slack += find_slack(v.this_distance);
 323                 cable_count[cable_select(v.this_distance)]++;
 324 #else
 325                 total_slack += find_slack(v.this_distance);
 326                 printf("(%3.1f)   ", v.this_cost / 10.0);
 327 #endif
 328
 329                 last_row = switches[k.sw_ind].row;
 330                 last_num = switches[k.sw_ind].num;
 331
 332                 ++(k.sw_ind);
 333                 --k.ports_left[v.distro];
 334
 335                 fprintf(patchlist, "e%u-%u %s\n", last_row * 2 - 1, last_num + 1,
 336                         port_name(v.distro, ++num_ports_used[v.distro]).c_str());
 337
 338                 switch (last_num + 1) {
 339                 case 1:
 340                         fprintf(switchlist, "87.76.%u.0 26 e%u-%u\n",
 341                                 last_row * 2 - 1, last_row * 2 - 1, last_num + 1);
 342                         break;
 343                 case 2:
 344                         fprintf(switchlist, "87.76.%u.64 26 e%u-%u\n",
 345                                 last_row * 2 - 1, last_row * 2 - 1, last_num + 1);
 346                         break;
 347                 case 3:
 348                         fprintf(switchlist, "87.76.%u.128 26 e%u-%u\n",
 349                                 last_row * 2 - 1, last_row * 2 - 1, last_num + 1);
 350                         break;
 351                 case 4:
 352                         fprintf(switchlist, "87.76.%u.0 26 e%u-%u\n",
 353                                 last_row * 2, last_row * 2 - 1, last_num + 1);
 354                         break;
 355                 case 5:
 356                         fprintf(switchlist, "87.76.%u.64 26 e%u-%u\n",
 357                                 last_row * 2, last_row * 2 - 1, last_num + 1);
 358                         break;
 359                 case 6:
 360                         fprintf(switchlist, "87.76.%u.128 26 e%u-%u\n",
 361                                 last_row * 2, last_row * 2 - 1, last_num + 1);
 362                         break;
 363                 }
 364         }
 365         printf("\n");
 366
 367 #if TRUNCATE_METRIC
 368         cable_count[100] += cable_count[TENPLUSTEN];
 369         cable_count[100] += cable_count[TENPLUSTEN];
 370
 371         cable_count[100] += cable_count[THIRTYPLUSTEN];
 372         cable_count[300] += cable_count[THIRTYPLUSTEN];
 373
 374         cable_count[100] += cable_count[FIFTYPLUSTEN];
 375         cable_count[500] += cable_count[FIFTYPLUSTEN];
 376
 377         printf("\n");
 378         printf("10m: %3u\n", cable_count[100]);
 379         printf("30m: %3u\n", cable_count[300]);
 380         printf("50m: %3u\n", cable_count[500]);
 381         printf("Extensions: %u\n", cable_count[TENPLUSTEN] + cable_count[THIRTYPLUSTEN] + cable_count[FIFTYPLUSTEN]);
 382         printf("\n");
 383
 384         unsigned total_cable = 100 * cable_count[100] + 300 * cable_count[300] + 500 * cable_count[500];
 385         printf("Total cable: %.1fm\n", total_cable / 10.0);
 386         printf("Total slack: %.1fm (%.2f%%)\n", total_slack / 10.0, 100.0 * double(total_slack) / double(total_cable));
 387 #endif
 388 }