nx_choker.nx source
↩ module page · 100 lines · 4380 B
1// nx_choker.nx -- BitTorrent choke algorithm: tit-for-tat + optimistic unchoke (deterministic).
2//
3// module: nishi-core.torrent.choker
4// depends: nx_syscalls.nx
5// capability: CORE_COMPUTE
6// wired_status: FULLY_WIRED
7//
8// "Better download rates" earned the way the protocol intends: reciprocity. We give upload
9// slots to the peers who feed US fastest (tit-for-tat) so they keep US unchoked, plus one
10// rotating optimistic slot to discover new fast peers and bootstrap newcomers. Mainline
11// rotates the optimistic slot RANDOMLY every ~3 rounds; we rotate it ROUND-ROBIN by a
12// deterministic round counter instead -- same discovery behavior, but the whole choke
13// schedule stays bit-for-bit replayable (the determinism exceed thesis; no client in the
14// field can replay its own choke decisions). Pure selection over caller-owned arrays:
15// no wall clock, no RNG, no syscalls on the decision path.
16
17import "nx_syscalls.nx"
18
19const NX_CH_DEFAULT_SLOTS: i64 = 4 // classic mainline upload slots (caller may override via k)
20const NX_CH_OPT_PERIOD: i64 = 3 // rotate the optimistic slot every 3 choke rounds (override via period)
21
22// ---- tit-for-tat: mark the k highest-rate INTERESTED peers as unchoked ----
23// rates[i] = rolling bytes/sec we received from peer i (reward who feeds us).
24// interested[i] = 1 if peer i wants our data (only the interested are eligible for a slot).
25// Writes 1/0 into out_unchoked (length n) and returns the count unchoked (<= k, <= eligible).
26// Deterministic: highest rate wins, lowest index breaks ties. O(k*n), no sort/RNG.
27func nx_ch_select_top_k(rates: *i64, interested: *i64, n: i64, k: i64, out_unchoked: *i64) -> i64 {
28 var i: i64 = 0
29 while i < n { out_unchoked[i] = 0; i = i + 1 }
30 var filled: i64 = 0
31 while filled < k {
32 var best: i64 = 0 - 1
33 var best_rate: i64 = 0
34 i = 0
35 while i < n {
36 if interested[i] == 1 {
37 if out_unchoked[i] == 0 {
38 var take: i64 = 0
39 if best < 0 { take = 1 }
40 else { if rates[i] > best_rate { take = 1 } }
41 if take == 1 { best = i; best_rate = rates[i] }
42 }
43 }
44 i = i + 1
45 }
46 if best < 0 { filled = k } // no eligible peer left -> stop
47 else { out_unchoked[best] = 1; filled = filled + 1 }
48 }
49 var c: i64 = 0
50 i = 0
51 while i < n { if out_unchoked[i] == 1 { c = c + 1 } i = i + 1 }
52 return c
53}
54
55// ---- optimistic-unchoke target: the rotating extra slot ----
56// Among peers that are INTERESTED but NOT already unchoked, pick one deterministically by
57// round-robin over the round counter (changes every `period` rounds). Returns the peer index,
58// or -1 if there is no eligible peer. This is how newcomers (rate 0, never reciprocated yet)
59// get a chance, and how we discover peers faster than our current top-k.
60func nx_ch_optimistic_slot(interested: *i64, out_unchoked: *i64, n: i64, round: i64, period: i64) -> i64 {
61 var count: i64 = 0
62 var i: i64 = 0
63 while i < n {
64 if interested[i] == 1 { if out_unchoked[i] == 0 { count = count + 1 } }
65 i = i + 1
66 }
67 if count <= 0 { return 0 - 1 }
68 var p: i64 = period
69 if p <= 0 { p = 1 }
70 let pick: i64 = (round / p) % count
71 var seen: i64 = 0
72 i = 0
73 while i < n {
74 if interested[i] == 1 {
75 if out_unchoked[i] == 0 {
76 if seen == pick { return i }
77 seen = seen + 1
78 }
79 }
80 i = i + 1
81 }
82 return 0 - 1
83}
84
85// ---- full choke decision for one round: tit-for-tat top-k + one optimistic slot ----
86// Writes the final 1/0 unchoke set into out_unchoked; returns total unchoked count.
87func nx_ch_compute(rates: *i64, interested: *i64, n: i64, k: i64, round: i64, period: i64, out_unchoked: *i64) -> i64 {
88 let base: i64 = nx_ch_select_top_k(rates, interested, n, k, out_unchoked)
89 let opt: i64 = nx_ch_optimistic_slot(interested, out_unchoked, n, round, period)
90 if opt >= 0 { out_unchoked[opt] = 1; return base + 1 }
91 return base
92}
93
94// ---- does this round begin a fresh optimistic interval? (caller scheduling helper) ----
95func nx_ch_should_rotate(round: i64, period: i64) -> i64 {
96 var p: i64 = period
97 if p <= 0 { p = 1 }
98 if (round % p) == 0 { return 1 }
99 return 0
100}