Каково среднее число коллизий, которые произойдут в сети с использованием двоичного экспоненциального отката?
Я пишу программу для моделирования экспоненциальной функции отката, используемой в Ethernet, но я не уверен, что моя модель верна. Кто-нибудь знает среднее количество коллизий, которые произойдут между N станциями в сети, используя эти предположения:
Предположим, что в сети есть N станций. Каждая станция имеет 1 кадр для отправки и разрешена для передачи только в начале временного интервала. Если две или более станции отправляют в начале временного интервала, происходит коллизия, и каждая станция должна откатываться, используя двоичную экспоненциальную функцию отката, описанную здесь: http://en.wikipedia.org/wiki/Exponential_backoff. Предположим, что для передачи кадра требуется один временной интервал; если станция отправляет свой кадр без столкновения, то после этого она остается неактивной.
Похоже, что в моей программе в среднем N^2 полных коллизий для N станций, но я не смог найти никакого источника относительно того, является ли это даже близко к правильному. Любая помощь с благодарностью.
2 ответа
Я не вижу аналитического решения для этого. Случай N = 2, кажется, имеет аналитическое решение:
f (2) = сумма {k=1;k= бесконечность} (k (2k-1) / 2(k2+ 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, чем N2 для меня.
Я собрал симуляцию на основе того, что описано в статье в Википедии. Я не вижу нигде рядом 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
Это среднее количество кадров с коллизией, количество попыток передачи, которые были задействованы в коллизиях, количество успешных передач (должно быть по одному на узел) и количество кадров, которые потребовалось для каждого узла для передачи успешно.
Вот симуляция, которую я собрал в Хаскеле
{-# 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
Изменено, чтобы включить больше статистики для сравнения с другими моделями