c++ - 向节点有效发送请求的算法

Question

我想根据每个节点的配置将流量统一分配给各个节点。最多可以有 100 个节点和分配给多个节点的流量百分比 可以配置。

所以说，如果有 4 个节点:-

node 1 - 20
node 2 - 50
node 3 - 10
node 4 - 20
------------
sum    - 100
------------

所有节点的总和应为 100。 示例:-

node 1 - 50
node 2 - 1
node 3 - 1
node 4 - 1
.
.
.
node 100 - 1

在上面的配置中，共有 51 个节点。节点1为50，其余50个节点配置为1。

在一个场景中，请求可以按以下模式分发:- node1,node2,node3,node4,node5,....,node51,node1,node1,node1,node1,node1,node1,node1,......

上面的分布是低效的，因为我们不断地向节点 1 发送过多的流量， 这可能会导致 node1 拒绝请求。

在另一个场景中，请求可以按以下模式分发:- node1,node2,node1,node3,node1,node4,node1,node5,node1,node6,node1,node7,node1,node8……

在上面的 senario 请求被更有效地分发。

我找到了下面的代码，但无法理解它背后的想法。

func()
{
  for(int itr=1;itr<=total_requests+1;itr++)
  {
      myval = 0;           
      // Search the node that needs to be incremented
       // to best approach the rates of all branches                      
      for(int j=0;j<Total_nodes;j++)
      {

         if((nodes[j].count*100/itr > nodes[j].value) ||
           ((nodes[j].value - nodes[j].count*100/itr) < myval) ||
           ((nodes[j].value==0 && nodes[j].count ==0 )))
              continue;

            cand = j;
            myval = abs((long)(nodes[j].count*100/itr - nodes[j].value));
       }
       nodes[cand].count++;

  }

  return nodes[cand].nodeID;
}

在上面的代码中，total_requests 是到目前为止收到的请求总数。 total_requests 变量每次都会递增，将其视为全局值以便于理解。

Total_nodes 是配置的节点总数，每个节点使用以下结构表示。

节点是一个结构:-

struct node{
  int count;
  int value;
  int nodeID;
};

例如:-

If 4 nodes are configured :-
node 1 - 20
node 2 - 50
node 3 - 10
node 4 - 20
------------
sum    - 100
------------

将使用以下值创建四个节点[4]:-

node1{
  count = 0;
  value = 20;
  nodeID = 1;
};

node2{
  count = 0;
  value = 50;
  nodeID = 2;
};

node3{
  count = 0;
  value = 10;
  nodeID = 3;
};

node4{
  count = 0;
  value = 20;
  nodeID = 4;
};

能否请您向我解释一下它实际上如何有效地分发它的算法或想法。

Answer 1

nodes[j].count*100/itr 是节点 j 到目前为止已回答的请求百分比的下限。 nodes[j].value 是节点 j 应该回答的请求的百分比。您发布的代码寻找最落后于其目标百分比的节点(或多或少，受整数除法的影响)并为其分配下一个请求。