/
choker.go
148 lines (120 loc) · 3.53 KB
/
choker.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package torrent
import (
"math/rand"
"sort"
"time"
"log"
)
// BitTorrent choking policy.
// The choking policy's view of a peer. For current policies we only care
// about identity and download bandwidth.
type Choker interface {
DownloadBPS() float32 // bps
UploadBPS() float32 // bps
}
type ChokePolicy interface {
// Only pass in interested peers.
// mutate the chokers into a list where the first N are to be unchoked.
Choke(chokers []Choker) (unchokeCount int, err error)
}
// Our naive never-choke policy
type NeverChokePolicy struct{}
func (n *NeverChokePolicy) Choke(chokers []Choker) (unchokeCount int, err error) {
return len(chokers), nil
}
// Random Choke Policy
type RandomChokePolicy struct{}
func (rcp *RandomChokePolicy) Choke(chokers []Choker) (unchokeCount int, err error) {
// Randomly Shuffle Choker List
rand.Seed(time.Now().UnixNano())
Shuffle(chokers)
// Unchoke a random number of peers
return rand.Intn(len(chokers)), nil
}
func Shuffle(a []Choker) {
for i := range a {
j := rand.Intn(i + 1)
a[i], a[j] = a[j], a[i]
}
}
type DeficitBPS []Choker
func (a DeficitBPS) Len() int {
return len(a)
}
func (a DeficitBPS) Swap(i, j int) {
a[i], a[j] = a[j], a[i]
}
func (a DeficitBPS) Less(i, j int) bool {
return (a[i].DownloadBPS() - a[i].UploadBPS()) > (a[j].DownloadBPS() - a[j].UploadBPS())
}
// Fair-Torrent Choke Policy
type FairChokePolicy struct{}
func (fcp *FairChokePolicy) Choke(chokers []Choker) (unchokeCount int, err error) {
sort.Sort(DeficitBPS(chokers))
return 4, nil
}
// Our interpretation of the classic bittorrent choke policy.
// Expects to be called once every 10 seconds.
// See the section "Choking and optimistic unchoking" in
// https://wiki.theory.org/BitTorrentSpecification
type ClassicChokePolicy struct {
optimisticUnchoker Choker // The choker we unchoked optimistically
counter int // When to choose a new optimisticUnchoker.
}
type ByDownloadBPS []Choker
func (a ByDownloadBPS) Len() int {
return len(a)
}
func (a ByDownloadBPS) Swap(i, j int) {
a[i], a[j] = a[j], a[i]
}
func (a ByDownloadBPS) Less(i, j int) bool {
return a[i].DownloadBPS() > a[j].DownloadBPS()
}
const HIGH_BANDWIDTH_SLOTS = 3
const OPTIMISTIC_UNCHOKE_INDEX = HIGH_BANDWIDTH_SLOTS
// How many cycles of this algorithm before we pick a new optimistic
const OPTIMISTIC_UNCHOKE_COUNT = 3
func (ccp *ClassicChokePolicy) Choke(chokers []Choker) (unchokeCount int, err error) {
sort.Sort(ByDownloadBPS(chokers))
log.Printf("%v", chokers)
optimistIndex := ccp.findOptimist(chokers)
if optimistIndex >= 0 {
if optimistIndex < OPTIMISTIC_UNCHOKE_INDEX {
// Forget optimistic choke
optimistIndex = -1
} else {
ByDownloadBPS(chokers).Swap(OPTIMISTIC_UNCHOKE_INDEX, optimistIndex)
optimistIndex = OPTIMISTIC_UNCHOKE_INDEX
}
}
if optimistIndex >= 0 {
ccp.counter++
if ccp.counter >= OPTIMISTIC_UNCHOKE_COUNT {
ccp.counter = 0
optimistIndex = -1
}
}
if optimistIndex < 0 {
candidateCount := len(chokers) - OPTIMISTIC_UNCHOKE_INDEX
if candidateCount > 0 {
candidate := OPTIMISTIC_UNCHOKE_INDEX + rand.Intn(candidateCount)
ByDownloadBPS(chokers).Swap(OPTIMISTIC_UNCHOKE_INDEX, candidate)
ccp.counter = 0
ccp.optimisticUnchoker = chokers[OPTIMISTIC_UNCHOKE_INDEX]
}
}
unchokeCount = OPTIMISTIC_UNCHOKE_INDEX + 1
if unchokeCount > len(chokers) {
unchokeCount = len(chokers)
}
return
}
func (ccp *ClassicChokePolicy) findOptimist(chokers []Choker) (index int) {
for i, c := range chokers {
if c == ccp.optimisticUnchoker {
return i
}
}
return -1
}