Каково среднее число столкновений, которое произойдет в сети, используя двоичное экспоненциальное отключение?

Question

Я пишу программу для моделирования экспоненциальной функции отсрочки, используемой в Ethernet, но я не уверен, что моя модель верна. Кто-нибудь знает среднее число столкновений, которое произойдет между N станциями в сети, используя эти предположения:

Предположим, что в сети есть N станций. Каждая станция имеет 1 кадр для отправки и разрешается передавать только в начале временного интервала. Если две или более станции отправляются в начале временного интервала, произойдет столкновение, и каждая станция должна отступить, используя описанную здесь функцию двоичного экспоненциального отсрочка: http://en.wikipedia.org/wiki/Exponential_backoff. Предположим, что для передачи кадра требуется один временной интервал; если станция отправляет свой кадр без столкновения, он остается неактивным впоследствии.

У моей программы, как представляется, среднее число N^2 суммарных коллизий для N станций, но я не смог найти источник, насколько это близко к правилу. Любая помощь приветствуется.

Answer 1

Я собрал симуляцию, основанную на том, что описано в статье Википедии. Я не вижу нигде вблизи N^2 столкновений для N узлов, каждый из которых пытается отправить один раз в первый временный кадр и никогда не передавать снова, как только их одно сообщение передается без столкновения.

Nodes Coll Lost Succ Frames 
0  0.0  0.0  0.0  0.0  
1  0.0  0.0  1.0  1.0  
2  1.655 3.31 2.0  5.334 
3  2.623 6.546 3.0  9.238 
4  3.764 10.698 4.0  14.327 
5  4.787 15.01 5.0  19.417 
6  5.944 19.869 6.0  25.821 
7  6.911 24.718 7.0  31.432 
8  8.033 30.155 8.0  38.464 
9  9.11 35.591 9.0  44.295 
10  10.165 41.137 10.0 51.748 
11  11.263 47.043 11.0 58.642 
12  12.395 53.029 12.0 66.874 
13  13.434 59.097 13.0 75.109 
14  14.449 65.097 14.0 81.917 
15  15.443 71.27 15.0 88.52 
16  16.453 77.544 16.0 97.961 
17  17.483 84.04 17.0 104.177 
18  18.711 90.877 18.0 116.288 
19  19.539 97.185 19.0 120.451 
20  20.67 104.059 20.0 130.952 
21  21.592 110.561 21.0 140.519 
22  22.691 117.556 22.0 146.973 
23  23.832 124.608 23.0 158.805 
24  24.667 131.162 24.0 163.776 
25  25.85 138.41 25.0 176.745 
26  26.92 145.641 26.0 189.071 
27  27.823 152.719 27.0 197.514 
28  28.942 160.104 28.0 207.642 
29  29.875 166.963 29.0 215.736 
30  30.866 174.161 30.0 225.025 
31  31.686 181.132 31.0 229.19 
32  32.947 189.118 32.0 242.804 
33  33.973 196.505 33.0 252.973 
34  34.948 203.764 34.0 263.166 
35  36.192 212.065 35.0 273.805 
36  36.795 218.552 36.0 277.656 
37  37.966 226.543 37.0 292.611 
38  39.197 234.595 38.0 307.013 
39  39.908 241.305 39.0 309.537 
40  41.057 249.609 40.0 323.217 
41  42.183 257.519 41.0 331.323 
42  43.223 265.094 42.0 344.867 
43  43.981 272.823 43.0 349.558 
44  44.934 280.297 44.0 355.776 
45  46.106 288.5 45.0 375.085 
46  47.277 296.807 46.0 384.67 
47  48.397 304.742 47.0 401.301 
48  49.207 312.141 48.0 412.576 
49  50.146 320.155 49.0 417.144 

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

Вот моделирования я соединял в Haskell

{-# LANGUAGE MultiParamTypeClasses, FlexibleInstances, FlexibleContexts, DeriveFunctor, OverlappingInstances #-} 
-- OverlapingInstances shouldn't be required; there's no Functor instance for NodeDict. 
module Main (
    main 
) where 

import System.Random 
import qualified Data.Foldable as Foldable 

main = do  
    output ["Nodes", "Coll", "Lost", "Succ", "Frames"] 
    sequence_ $ map expirement $ take 50 $ iterate (1+) 0 

expirement n = do 
    let numTrials = 1000 
    results <- sequence $ take numTrials $ repeat (trial n) 
    let averages = summarize average results 
    output [show n, show $ collisions averages, show $ lostTransmissions averages, show $ successfulTransmissions averages, show $ frames averages ] 

trial n = do 
    generator <- newStdGen 
    let network = take n $ randomNodes generator 
    let monitoredNetwork = (Passive $ Monitor [], network) 
    let (Passive (Monitor result), _) = simulate monitoredNetwork 
    return TrialResult { 
     collisions = count collision result, 
     lostTransmissions = sum $ map collided $ filter collision result, 
     successfulTransmissions = count (==Frame) result, 
     frames = length result 
    } 

-- Initialize network with exponential backoffs 
randomNodes :: (RandomGen g) => g -> [Single (NodeDict Transmission Reception)] 
randomNodes = map randomNode . splits 
    where 
     randomNode generator = Single $ backOffTransmissions (randomExponentialBackoffSchedules generator) $ transmit done 

data TrialResult a = TrialResult { 
    collisions :: !a, 
    lostTransmissions :: !a, 
    successfulTransmissions :: !a, 
    frames :: !a 
} deriving Show 

average :: (Real r, Fractional a) => [r] -> a 
average results = (fromRational . toRational $ sum results)/(fromRational $ toRational $ length results) 

summarize :: ([a] -> b) -> [TrialResult a] -> TrialResult b 
summarize summarizer results = TrialResult { 
    collisions = summarizer $ map collisions results, 
    lostTransmissions = summarizer $ map lostTransmissions results, 
    successfulTransmissions = summarizer $ map successfulTransmissions results, 
    frames = summarizer $ map frames results 
} 

output = putStrLn . concat . map (padr 8)  

padr :: Int -> [Char] -> [Char] 
padr n s = take n $ s ++ repeat ' ' 

-- Model for nodes 

class Transmitter t s where 
    transmission :: s -> t 

class Reciever r s where 
    recieve :: r -> s -> s 

-- Ordinary node with no type information attached 
data NodeDict t r = NodeDict { 
    _transmission :: t, 
    _recieve :: r -> NodeDict t r 
} 

instance Transmitter t (NodeDict t r) where 
    transmission = _transmission 

instance Reciever r (NodeDict t r) where 
    recieve = flip _recieve 

-- Networks 

class Transmitters t s where 
    transmissions :: s -> [t] 

-- Network consisting of a single node 

newtype Single a = Single { 
    only :: a 
} deriving Functor 

instance Transmitter t s => Transmitters t (Single s) where 
    transmissions = (replicate 1) . transmission . only 

-- Network instance for a list of networks 

instance (Transmitters t s, Foldable.Foldable f) => Transmitters t (f s) where 
    transmissions = Foldable.foldMap transmissions 

instance (Reciever r s, Functor f) => Reciever r (f s) where 
    recieve r = fmap (recieve r)  

-- Network instances for tuples of networks 

instance (Transmitters t sa, Transmitters t sb) => Transmitters t (sa, sb) where 
    transmissions (a, b) = transmissions a ++ transmissions b 

instance (Reciever r sa, Reciever r sb) => Reciever r (sa, sb) where 
    recieve r (a, b) = (recieve r a, recieve r b) 

-- Node that monitors the network 

newtype Passive a = Passive { 
    unPassive :: a 
} deriving Functor 

instance Transmitters t (Passive a) where 
    transmissions _ = [] 

newtype Monitor a = Monitor { 
    observations :: [a] 
} 

instance Reciever r (Monitor r) where 
    recieve r s = Monitor (r:observations s) 

-- Our signals 

data Transmission = Done | Waiting | Transmitting deriving (Show, Eq) 

data Reception = None | Frame | Collision {collided :: Int} deriving (Show, Eq)  

collision :: Reception -> Bool 
collision (Collision _) = True 
collision _ = False 

-- Simulate collisions in a network 

count :: (a -> Bool) -> [a] -> Int 
count f = length . filter f 

simulate :: (Transmitters Transmission s, Reciever Reception s) => s -> s 
simulate state = 
    case all (==Done) current of 
     False -> 
      simulate nextState 
      where 
       currentlyTransmitting = count (==Transmitting) current 
       signal = 
        case currentlyTransmitting of 
         0 -> None 
         1 -> Frame 
         _ -> Collision currentlyTransmitting 
       nextState = recieve signal state 
     _ -> state 
    where current = transmissions state 

-- Some network nodes 
-- Node that does something, ignores what it recieves and does the next thing 
node :: t -> NodeDict t r -> NodeDict t r 
node t r = NodeDict { 
    _transmission = t, 
    _recieve = \_ -> r 
} 

-- Done forever 
done :: NodeDict Transmission r 
done = node Done done 

-- Wait, then do the next thing 
wait :: NodeDict Transmission r -> NodeDict Transmission r 
wait = node Waiting 

-- Transmit, then do the next thing 
transmit :: NodeDict Transmission r -> NodeDict Transmission r 
transmit = node Transmitting 

-- When transmitting, check for collision and back off acording to the current schedule 
backOffTransmissions :: [[Int]] -> NodeDict Transmission Reception -> NodeDict Transmission Reception 
backOffTransmissions schedules n = NodeDict { 
     _transmission = (transmission n), 
     _recieve = case (transmission n==Transmitting) of 
      True -> \r -> case (collision r) of 
       True -> (iterate wait $ backOffTransmissions newSchedules n) !! steps 
        where 
         ((steps: thisSchedule) : remainingSchedules) = schedules 
         newSchedules = thisSchedule : remainingSchedules 
       False -> backOffTransmissions (tail schedules) (recieve r n) 
      _ -> \r -> backOffTransmissions schedules (recieve r n) 
    } 

-- Exponential backoff 

powersOf2 :: Num n => [n] 
powersOf2 = iterate (*2) 1 

exponentialBackoffRanges :: Num n => [(n,n)] 
exponentialBackoffRanges = map (\x -> (0, x-1)) $ tail powersOf2 

exponentialBackoffGenerators :: (Num n, Random n, RandomGen g) => [g -> (n, g)] 
exponentialBackoffGenerators = map randomR exponentialBackoffRanges 

zipRandom :: RandomGen g => [g -> (a, g)] -> g -> [a] 
zipRandom (step:steps) generator = 
    let (value, nextGenerator) = step generator 
    in value : zipRandom steps nextGenerator 

splits :: RandomGen g => g -> [g] 
splits = zipRandom (repeat split) 

randomExponentialBackoffs :: (RandomGen g, Random n, Num n) => g -> [n] 
randomExponentialBackoffs = zipRandom exponentialBackoffGenerators 

randomExponentialBackoffSchedules :: (RandomGen g, Random n, Num n) => g -> [[n]] 
randomExponentialBackoffSchedules = map randomExponentialBackoffs . splits 

Editted включать больше статистических данных для сравнения с другими моделирования

Answer 2

Я не вижу аналитическое решение для этого. N = 2 случай, как представляется, аналитическое решение:

F (2) = {сумма к = 1; к = бесконечность} (к (2 ^к -1)/2 ^{(к + k)/2})

, который выходит примерно к 1.64163, и случай N = 3 не так прост.

Когда я имитировать, я получаю это:

1: 0 
2: 1.63772 
3: 2.63643 
4: 3.70488 
5: 4.80432 
6: 5.89181 
7: 6.97669 
8: 8.05497 
9: 9.13575 
10: 10.2013 
11: 11.2844 
12: 12.3304 
13: 13.3865 
14: 14.4362 
15: 15.4775 
16: 16.5293 
17: 17.554 
18: 18.6101 
19: 19.6427 
20: 20.6934 

Это выглядит как N, чем N мне.