我正在编写一个程序来模拟以太网中使用的指数退避函数，但我不确定我的模型是否正确。有没有人知道网络中 N 个站之间将发生的平均冲突次数，使用这些假设：
假设网络有 N 个站。每个站有 1 帧要发送，并且只允许在时隙开始时发送。如果两个或多个站点在一个时隙开始时发送，将会发生冲突，并且每个站点都必须使用此处描述的二进制指数退避函数进行退避：http ://en.wikipedia.org/wiki/Exponential_backoff 。假设传输一帧需要一个时隙；如果一个站发送它的帧没有冲突，它之后保持不活动。
我的程序似乎对 N 个站点平均有 N^2 次总碰撞，但我无法找到任何来源来证明这是否接近正确。任何帮助是极大的赞赏。
我没有看到对此的分析解决方案。N=2 的情况似乎有解析解：
f(2) = sum{k=1;k=infinity}(k (2 k -1)/2 (k 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 2。
我根据维基百科文章中的描述进行了模拟。我没有看到 N 节点的 N^2 冲突附近的任何地方，每个节点都尝试在第一个时间帧发送一次，并且一旦它们的单个消息在没有冲突的情况下传输，就再也不会再次传输。
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
编辑以包含更多统计数据以与其他模拟进行比较