алгоритм эффективной отправки запроса на узлы

Хммм. Кажется, что при достижении 100 узлов каждый из них должен занимать 1% трафика?

Я, честно говоря, понятия не имею, какую функцию вы выполняете. Я предполагаю, что он пытается найти узел, наиболее удаленный от его долгосрочной средней нагрузки. Но если total_requests это общее на сегодняшний день, тогда я не понимаю, что внешний for(int itr=1;itr<=total_requests+1;itr++) цикл делает, разве это не часть теста, чтобы показать, как он распределяет нагрузку?

В любом случае, в основном то, что вы делаете, похоже на создание неоднородной случайной последовательности. Имея до 100 узлов, если я могу предположить (на мгновение), что 0..999 дает достаточное разрешение, то вы можете использовать «id_vector []» с 1000 идентификаторами узлов, который заполнен n1 копиями узлов 1. ID, n2 копии идентификатора узла-2 и т. Д. — где узел-1 должен получить n1 / 1000 трафика и т. Д. Процесс принятия решения очень и очень прост — выберите id_vector [random ()% 1000]. Со временем узлы получат примерно правильное количество трафика.

Если вы недовольны случайным распределением трафика, то вы заполняете id_vector узлами-идентификаторами, чтобы вы могли выбрать «циклический перебор» и получить подходящую частоту для каждого узла. Одним из способов сделать это было бы случайное перемешивание id_vector, сконструированного, как описано выше (и, возможно, время от времени перестановки, чтобы, если один случай перемешивания был «плохим», вы не застряли с ним). Или вы могли бы сделать одноразовую утечку и заполнить id_vector из этого. Каждый раз вокруг id_vector это гарантирует, что каждый узел получит назначенное ему количество запросов.

Чем тоньше зерно, которое вы делаете id_vector, тем лучше вы получаете контроль над кратковременной частотой запросов к каждому узлу.

Имейте в виду, все вышесказанное предполагает, что относительная нагрузка для узлов постоянна. Если нет, то вам нужно (очень время от времени?) Настроить id_vector.

Изменить, чтобы добавить больше деталей, как требуется …

…Предположим, у нас есть только 5 узлов, но мы выражаем «вес» каждого из них как n/1000, чтобы учесть до 100 узлов. Предположим, у них есть идентификаторы 1..5 и вес:

  ID=1, weight = 100
ID=2, weight = 375
ID=3, weight = 225
ID=4, weight = 195
ID=5, weight = 105

Который, очевидно, складывается до 1000.

Таким образом, мы строим id_vector[1000] чтобы:

  id_vector[  0.. 99] = 1   -- first 100 entries = ID 1
id_vector[100..474] = 2   -- next  375 entries = ID 2
id_vector[475..699] = 3   -- next  225 entries = ID 3
id_vector[700..894] = 4   -- next  195 entries = ID 4
id_vector[100..999] = 5   -- last  105 entries = ID 5

А теперь, если мы будем тасовать id_vector[] мы получаем случайную последовательность выбора узлов, но более 1000 запросов, правильная средняя частота запросов к каждому узлу.

Что касается значения развлечения, я попробовал «утечку», чтобы увидеть, насколько хорошо он может поддерживать постоянную частоту запросов к каждому узлу, заполнив id_vector используя одно протекающее ведро для каждого узла. Код, позволяющий сделать это, и посмотреть, насколько хорошо он работает и насколько хорошо работает простая случайная версия, приведен ниже.

Каждое протекающее ведро имеет cc количество запросов, которые должны быть отправлены (на другие узлы) до того, как на этот запрос будет отправлен следующий запрос. Каждый раз, когда отправляется запрос, все корзины имеют свои cc количество уменьшилось, и узел, чья корзина имеет наименьшее cc (или наименьший идентификатор, если cc равны) отправляется запрос, и в этот момент ведро узла cc перезаряжается. (Каждый запрос приводит к тому, что все корзины выпадают один раз, и корзина для выбранного узла перезаряжается.)

cc является целой частью «содержимого» сегмента. Начальное значение для cc является q = 1000 / w, где w это вес узла. И каждый раз, когда ведро перезаряжается, q добавлен в cc, Чтобы сделать вещи точно, однако, мы должны иметь дело с остатком r = 1000 % w… или, другими словами, «содержимое» имеет дробную часть — где cr приходит истинное значение содержимого cc + cr / w (где cr / w — это истинная дробь, а не целочисленное деление). Начальное значение этого cc = q а также cr = r, Каждый раз, когда ведро перезаряжается, q добавлен в cc, а также r добавлен в cr, Когда cr / w> = 1/2, мы округляем, так что cc +=1, а также cr -= w (добавление единицы к целочисленной части уравновешивается вычитанием 1 — то есть w / w — из дробной части). Чтобы проверить на cr / w> = 1/2, код на самом деле тестирует (cr * 2) >= w, Надеюсь, что bucket_recharge() функция будет иметь смысл (сейчас).

Утечка ведро выполняется 1000 раз, чтобы заполнить id_vector []. Небольшое тестирование показывает, что это поддерживает довольно стабильную частоту для всех узлов и точное число пакетов на узел каждый раз в цикле id_vector [].

Небольшое тестирование показывает, что подход random () shuffle имеет гораздо более переменную частоту в каждом цикле id_vector [], но все же предоставляет точное количество пакетов на узел для каждого цикла.

Устойчивость протекающей корзины предполагает постоянный поток входящих запросов. Что может быть совершенно нереалистичным предположением. Если запросы поступают большими (большими по сравнению с циклом id_vector [], в данном примере 1000), то изменчивость (простого) случайного () случайного подхода может быть уменьшена изменчивостью в поступлении запроса!

enum
{
n_nodes  =    5,        /* number of nodes      */
w_res    = 1000,        /* weight resolution    */
} ;

struct node_bucket
{
int   id ;            /* 1 origin                 */

int   cc ;            /* current count            */
int   cr ;            /* current remainder        */

int   q ;             /* recharge -- quotient     */
int   r ;             /* recharge -- remainder    */

int   w ;             /* weight                   */
} ;

static void bucket_recharge(struct node_bucket* b) ;
static void node_checkout(int weights[], int id_vector[], bool rnd) ;
static void node_shuffle(int id_vector[]) ;

/*------------------------------------------------------------------------------
* To begin at the beginning...
*/
int
main(int argc, char* argv[])
{
int node_weights[n_nodes] = { 100, 375, 225, 195, 105 } ;
int id_vector[w_res] ;
int cx ;

struct node_bucket buckets[n_nodes] ;

/* Initialise the buckets -- charged
*/
cx = 0 ;
for (int id = 0 ; id < n_nodes ; ++id)
{
struct node_bucket* b ;

b = &buckets[id] ;

b->id = id + 1 ;              /* 1 origin     */
b->w  = node_weights[id] ;

cx += b->w ;

b->q  = w_res / b->w ;
b->r  = w_res % b->w ;

b->cc = 0 ;
b->cr = 0 ;

bucket_recharge(b) ;
} ;

assert(cx == w_res) ;

/* Run the buckets for one cycle to fill the id_vector
*/
for (int i = 0 ; i < w_res ; ++i)
{
int id ;

id = 0 ;
buckets[id].cc -= 1 ;         /* drip     */

for (int jd = 1 ; jd < n_nodes ; ++jd)
{
buckets[jd].cc -= 1 ;     /* drip     */

if (buckets[jd].cc < buckets[id].cc)
id = jd ;
} ;

id_vector[i] = id + 1 ;       /* '1' origin   */

bucket_recharge(&buckets[id]) ;
} ;

/* Diagnostics and checking
*
* First, check that the id_vector contains exactly the right number of
* each node, and that the bucket state at the end is the same (apart from
* cr) as it is at the beginning.
*/
int nf[n_nodes] = { 0 } ;

for (int i = 0 ; i < w_res ; ++i)
nf[id_vector[i] - 1] += 1 ;

for (int id = 0 ; id < n_nodes ; ++id)
{
struct node_bucket* b ;

b = &buckets[id] ;

printf("ID=%2d weight=%3d freq=%3d  (cc=%3d  cr=%+4d  q=%3d  r=%3d)\n",
b->id, b->w, nf[id], b->cc, b->cr, b->q, b->r) ;
} ;

node_checkout(node_weights, id_vector, false /* not random */) ;

/* Try the random version -- with shuffled id_vector.
*/
int iv ;

iv = 0 ;
for (int id = 0 ; id < n_nodes ; ++id)
{
for (int i = 0 ; i < node_weights[id] ; ++i)
id_vector[iv++] = id + 1 ;
} ;
assert(iv == 1000) ;

for (int s = 0 ; s < 17 ; ++s)
node_shuffle(id_vector) ;

node_checkout(node_weights, id_vector, true /* random */) ;

return 0 ;
} ;

static void
bucket_recharge(struct node_bucket* b)
{
b->cc += b->q ;
b->cr += b->r ;

if ((b->cr * 2) >= b->w)
{
b->cc += 1 ;
b->cr -= b->w ;
} ;
} ;

static void
node_checkout(int weights[], int id_vector[], bool rnd)
{
struct node_test
{
int   last_t ;
int   count ;
int   cycle_count ;
int   intervals[w_res] ;
} ;

struct node_test tests[n_nodes] = { { 0 } } ;

printf("\n---Test Run: %s ---\n", rnd ? "Random Shuffle" : "Leaky Bucket") ;

/* Test run
*/
int s ;
s = 0 ;
for (int t = 1 ; t <= (w_res * 5) ; ++t)
{
int id ;

id = id_vector[s++] - 1 ;

if (tests[id].last_t != 0)
tests[id].intervals[t - tests[id].last_t] += 1 ;

tests[id].count += 1 ;
tests[id].last_t = t ;

if (s == w_res)
{
printf("At time %4d\n", t) ;

for (id = 0 ; id < n_nodes ; ++id)
{
struct node_test*   nt ;
long   total_intervals ;

nt = &tests[id] ;

total_intervals = 0 ;
for (int i = 0 ; i < w_res ; ++i)
total_intervals += (long)i * nt->intervals[i] ;

printf("  ID=%2d weight=%3d count=%4d(+%3d)  av=%6.2f vs %6.2f\n",
id+1, weights[id], nt->count, nt->count - nt->cycle_count,
(double)total_intervals / nt->count,
(double)w_res / weights[id]) ;
nt->cycle_count = nt->count ;

for (int i = 0 ; i < w_res ; ++i)
{
if (nt->intervals[i] != 0)
{
int h ;

printf("  %6d x %4d ", i, nt->intervals[i]) ;

h = ((nt->intervals[i] * 75) + ((nt->count + 1) / 2))/
nt->count ;
while (h-- != 0)
printf("=") ;
printf("\n") ;
} ;
} ;
} ;

if (rnd)
node_shuffle(id_vector) ;

s = 0 ;
} ;
} ;
} ;

static void
node_shuffle(int id_vector[])
{
for (int iv = 0 ; iv < (w_res - 1) ; ++iv)
{
int is, s ;

is = (int)(random() % (w_res - iv)) + iv ;

s             = id_vector[iv] ;
id_vector[iv] = id_vector[is] ;
id_vector[is] = s ;
} ;
} ;