fork download
copy 
  1. /*
  2.   http://t...content-available-to-author-only...h.net/test/read.cgi/tech/1342966104/12
  3.  
  4.   課題1　サーバにアクセスが集中する場合のシミュレーション
  5.  
  6.   ここではVirtual Output Queuing構成のハブをシミュレーションする。設定は
  7.   以下のようにする:
  8.  
  9.   ●ポート数は4.ポート0にはサーバが,残りのポート1〜ポート3にはクライアン
  10.   トが接続されている.
  11.   ●パケットの入出力やスイッチにおけるパケット転送はクロック単位で同期し
  12.   ている.
  13.   ●入力ポートからスイッチへの,またスイッチから出力ポートへの転送は1クロッ
  14.   クにつきPパケット.
  15.   ●サーバが接続するポート0にパケットが到着する平均時間間隔はTa,その他の
  16.   ポートに到着する平均時間間隔は3Taでいずれも指数分布に従う.
  17.   ●ポート0に到着するパケットの宛先ポートはポート1〜ポート3まで等確率でラ
  18.   ンダムに選ぶ. その他のポートから来るパケットの宛先は,確率1/2でポート0,
  19.   残りは他のポートに等確率（つまり他のクライアントポートに1/4ずつの確率）
  20.   であるとする. 
  21.   ●Tクロックの間動作をさせる.
  22.   
  23.   Ta=1,T=1000,P=1として実行し,全てのパケットに対する転送遅延（入力ポート
  24.   に入ってから出力ポートに出ていくまでの時間）の最大値と平均値を求めよ.
  25.   
  26.   課題2　帯域幅の増加ポート数やサーバ配置,パケット数などは課題1と同等とす
  27.   る. ただし,ポート0を流れるパケット数が多いことは容易に想像できるため,こ
  28.   こだけ帯域幅を2とする（つまり,入力ポート0は1クロックに2個のパケットを受
  29.   けとることができ,また出力ポート0は1クロックに2個のパケットを送り出すこ
  30.   とができるものとする）.
  31.   
  32.   Ta=1,T=1000,P=1として実行し,全てのパケットに対する転送遅延（入力ポート
  33.   に入ってから出力ポートに出ていくまでの時間）の最大値と平均値を求めよ.
  34.  
  35.   参考プログラム: http://i...content-available-to-author-only...e.com/T3e0j
  36. */
  37.  
  38. #include<cstdio>
  39. #include<cstdlib>
  40. #include<ctime>
  41. #include<cmath>
  42. #include<vector>
  43. #include<deque>
  44. using namespace std;
  45.  
  46. typedef vector< vector<double> > Matrix;
  47.  
  48. //隣接行列がgraphであるようなグラフにおいて、startからgoalまで幅優先探索を行う。
  49. //goalまでたどりつけばtrue、たどりつけなければfalseを返す。
  50. //trueが返るときには、prevに「直前の頂点」の情報が入っている。
  51. bool bfs(const vector<vector<int> > &graph, int start, int goal, vector<int> &prev)
  52. {
  53.   const int n = graph.size(); //n:グラフの頂点数
  54.  
  55.   //「直前の頂点」の情報をクリア
  56.   for(int i = 0; i < n; ++i){
  57.     prev[i] = -1;
  58.   }
  59.   //アルゴリズムの都合上、出発点の「直前」は出発点自身とする:
  60.   prev[start] = start;
  61.  
  62.   //「まだたどってない頂点」をキューで管理する。最初は出発点だけ。
  63.   deque<int> frontier;
  64.   frontier.push_back(start);
  65.  
  66.   //キューに頂点が残っていたらループ
  67.   while(! frontier.empty()){
  68.     int vertex = frontier[0];
  69.     frontier.pop_front();
  70.  
  71.     //目的地に到達していれば終わり
  72.     if(vertex == goal){
  73.       return true;
  74.     }
  75.  
  76.     //「次にたどるべき頂点」をキューに追加する
  77.     for(int next = 0; next < n; ++next){
  78.       //はじめて見る頂点で今の頂点から行けるものをキューに追加
  79.       if(prev[next] == -1 && graph[vertex][next] > 0){
  80.         prev[next] = vertex;
  81.         frontier.push_back(next);
  82.       }
  83.     }
  84.   }
  85.  
  86.   //目的地にたどりつかなかったのでfalse.
  87.   return false;
  88. }
  89.  
  90. //辺(i,j)の容量がgraph[i][j]であるようなグラフにおけるsourceからsinkへの最大フローを求める。
  91. //求めた最大フローはflowに入る。
  92. //最大フローの値を返す。
  93. int maxFlow(vector<vector<int> > graph, int source, int sink, vector<vector<int> > &flow)
  94. {
  95.   const int n = graph.size(); //n:グラフの頂点数
  96.  
  97.   //フローflowと値valueを初期化
  98.   for(int i = 0; i < n; ++i){
  99.     for(int j = 0; j < n; ++j){
  100.       flow[i][j] = 0;
  101.     }
  102.   }
  103.   int value = 0;
  104.  
  105.   //幅優先探索の準備
  106.   vector<int> prev(n);
  107.  
  108.   //経路が見付かる限りフローを更新
  109.   while(bfs(graph,source,sink,prev)){
  110.     //prevに従って,見付けた経路の容量の最小値を求める.
  111.     int capacity = graph[prev[sink]][sink];
  112.  
  113.     for(int v = sink; v != source; v = prev[v]){
  114.       if(capacity > graph[prev[v]][v]){
  115.         capacity = graph[prev[v]][v];
  116.       }
  117.     }
  118.  
  119.     //フローと残余ネットワークを更新
  120.     for(int v = sink; v != source; v = prev[v]){
  121.       int pv = prev[v];
  122.       flow[pv][v] += capacity;
  123.       graph[pv][v] -= capacity;
  124.       graph[v][pv] += capacity;
  125.     }
  126.     value += capacity;
  127.   }
  128.  
  129.   return value;
  130. }
  131.  
  132. double exprand(double average)
  133. {
  134.   double r = rand() / (RAND_MAX + 1.0);
  135.   return -log(1-r) * average;
  136. }
  137.  
  138. struct Packet {
  139.   int source; //入力ポート
  140.   int dest; //出力ポート
  141.   int arriveTime; //ハブへの到着時刻
  142.   int deliverTime; //ハブからの排出時刻
  143. };
  144.  
  145. typedef deque<Packet> PacketQueue;
  146.  
  147. //ハブに届いたパケットを生成する.
  148. Packet makePacket(int in_port, int current, int ports, const Matrix& m)
  149. {
  150.   Packet packet;
  151.   packet.source = in_port;
  152.   int sum = 0;
  153.   for (int i = 0; i < ports; ++i)
  154.     sum += m[in_port][i];
  155.   int n = int(rand() / (RAND_MAX + 1.0) * sum);
  156.   for (int i = 0; i  < 0; i++) {
  157.     if (m[in_port][i] == 0)
  158.       continue;
  159.     n -= m[in_port][i];
  160.     if (n < 0)
  161.       break;
  162.   }
  163.   packet.dest = n;
  164.   packet.arriveTime = current;
  165.   packet.deliverTime = -1;
  166.   return packet;
  167. }
  168.  
  169. //ポート数Ports,スイッチ転送量xppcパケット/クロックのハブのシミュレーションを行う.
  170. //パケットの平均到着時間間隔はTa,シミュレーション時間はdurationとする.
  171. void runSimulation(int Ports, const int *xppc, const double *Ta, int duration,
  172.                    const Matrix& packet_info)
  173. {
  174.   //入力バッファは入力ポートごとかつ出力ポートごと
  175.   vector<vector<PacketQueue> > inputBuffer(Ports, vector<PacketQueue>(Ports));
  176.  
  177.   //次に各入力ポートにパケットがくるタイミング
  178.   vector<int> nextPacketTime(Ports);
  179.  
  180.   //最初のパケットのタイミングを設定して....
  181.   for(int in_port = 0; in_port < Ports; ++in_port){
  182.     nextPacketTime[in_port] = int(exprand(Ta[in_port]));
  183.   }
  184.  
  185.   int count = 0, sum = 0, max = 0;
  186.  
  187.   //シミュレーション開始
  188.   printf("Simulation start\n");
  189.   for(int current = 0; current < duration; ++current){
  190.     // debug("T% 4d", current);
  191.     //まず入力パケットをもらう
  192.     for(int in_port = 0; in_port < Ports; ++in_port){
  193.       while(current == nextPacketTime[in_port]){
  194.         Packet packet = makePacket(in_port, current, Ports, packet_info);
  195.         inputBuffer[in_port][packet.dest].push_back(packet);
  196.         nextPacketTime[in_port] += int(exprand(Ta[in_port]));
  197.         // debug(" (in%d,to%d)", in_port, packet.dest);
  198.       }
  199.     }
  200.     //グラフを作って
  201.     const int Vertices = 2*Ports+2;
  202.     const int Source = 2*Ports;
  203.     const int Sink = 2*Ports+1;
  204.     vector<vector<int> > graph(Vertices, vector<int>(Vertices));
  205.     for(int in_port = 0; in_port < Ports; ++in_port){
  206.       for(int out_port = 0; out_port < Ports; ++out_port){
  207.         graph[in_port][Ports+out_port] = inputBuffer[in_port][out_port].size();
  208.       }
  209.     }
  210.     for(int in_port = 0; in_port < Ports; ++in_port){
  211.       graph[Source][in_port] = xppc[in_port];
  212.     }
  213.     for(int out_port = 0; out_port < Ports; ++out_port){
  214.       graph[Ports+out_port][Sink] = xppc[out_port];
  215.     }
  216.  
  217.     //最大フローを求め
  218.     vector<vector<int> > flow(Vertices, vector<int>(Vertices));
  219.     maxFlow(graph, Source, Sink, flow);
  220.  
  221.     //それに従ってパケットを送り出す
  222.     for(int in_port = 0; in_port < Ports; ++in_port){
  223.       for(int out_port = 0; out_port < Ports; ++out_port){
  224.         for(int p = 0; p < flow[in_port][Ports+out_port]; ++p){
  225.           inputBuffer[in_port][out_port][0].deliverTime = current;
  226.           // debug(" (from%d, out%d)", in_port, out_port);
  227.           Packet& x = inputBuffer[in_port][out_port][0];
  228.           int time = x.deliverTime - x.arriveTime;
  229.           if (max < time)
  230.             max = time;
  231.           sum += time;
  232.           ++count;
  233.           inputBuffer[in_port][out_port].pop_front();
  234.         }
  235.       }
  236.     }
  237.     // debug("\n");
  238.   }
  239.  
  240.   //時間がきたのでシミュレーション終了
  241.   printf("Simulation finished\n");
  242.   printf("max %d, average %f\n", max, (double) sum / count);
  243. }
  244.  
  245.  
  246. //テスト用のmain
  247. int main()
  248. {
  249.   const int Ports = 4; //ポート数
  250.   const double Ta = 1; //平均到着時間間隔
  251.   double Ta_port[Ports] = {Ta, 3 * Ta, 3 * Ta, 3 * Ta}; 
  252.   // 各ポートの平均到着間隔
  253.   const int T = 1000; //シミュレートする時間数
  254.  
  255.   // 各ポートの1クロックあたりの転送パケット数
  256.   // 課題1
  257.   const int P[] = {1, 1, 1, 1};
  258.   // 課題2
  259.   // const int P[] = {2, 1, 1, 1}; 
  260.   double packet_info_data[Ports*Ports] = {
  261.     0, 1, 1, 1, // ポート0から届いたパケットの宛先ポートが0～3の各割合
  262.     2, 0, 1, 1, // ポート1から
  263.     2, 1, 0, 1, // ポート2から
  264.     2, 1, 1, 0, // ポート3から
  265.   };
  266.  
  267.   Matrix packet_info(Ports);
  268.   double *p = packet_info_data;
  269.   for (int i = 0; i < Ports; ++i)
  270.     for (int j = 0; j < Ports; ++j, ++p)
  271.       packet_info[i].push_back(*p);
  272.  
  273.   srand(time(NULL));
  274.   runSimulation(Ports, P, Ta_port, T, packet_info);
  275.   return 0;
  276. }
  277.  
  278.  
Success #stdin #stdout 0.02s 2824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Simulation start
Simulation finished
max 779, average 45.275947
https://ideone.com/xE29K
language:
C++ (gcc 8.3)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!