-
Notifications
You must be signed in to change notification settings - Fork 305
/
scheduler.go
530 lines (487 loc) · 17.8 KB
/
scheduler.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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
// Copyright © 2019 The Things Network Foundation, The Things Industries B.V.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package scheduling
import (
"context"
"math"
"runtime/trace"
"sync"
"time"
"go.thethings.network/lorawan-stack/v3/pkg/band"
"go.thethings.network/lorawan-stack/v3/pkg/errors"
"go.thethings.network/lorawan-stack/v3/pkg/frequencyplans"
"go.thethings.network/lorawan-stack/v3/pkg/log"
"go.thethings.network/lorawan-stack/v3/pkg/toa"
"go.thethings.network/lorawan-stack/v3/pkg/ttnpb"
)
var (
// QueueDelay indicates the time the gateway needs to recharge the concentrator between items in the queue.
// This is a conservative value as implemented in the Semtech UDP Packet Forwarder reference implementation,
// see https://github.com/Lora-net/packet_forwarder/blob/v4.0.1/lora_pkt_fwd/src/jitqueue.c#L39
QueueDelay = 30 * time.Millisecond
// ScheduleTimeShort is a short time to send a downlink message to the gateway before it has to be transmitted.
// This time is comprised of a lower network latency and QueueDelay. This delay is used to block scheduling when the
// schedule time to the estimated concentrator time is less than this value, see ScheduleAt.
ScheduleTimeShort = 100*time.Millisecond + QueueDelay
// ScheduleTimeLong is a long time to send a downlink message to the gateway before it has to be transmitted.
// This time is comprised of a higher network latency and QueueDelay. This delay is used for pseudo-immediate
// scheduling, see ScheduleAnytime.
ScheduleTimeLong = 500*time.Millisecond + QueueDelay
// scheduleMinRTTCount is the minimum number of observed round-trip times that are taken into account before using
// using their statistics for calculating an absolute time or determining whether scheduling is too late.
scheduleMinRTTCount = 5
// scheduleLateRTTPercentile is the percentile of round-trip times that is considered for determining whether
// scheduling is too late.
scheduleLateRTTPercentile = 90
)
// TimeSource is a source for getting a current time.
type TimeSource interface {
Now() time.Time
}
type systemTimeSource struct{}
// Now implements TimeSource.
func (systemTimeSource) Now() time.Time { return time.Now() }
// SystemTimeSource is a TimeSource that uses the local system time.
var SystemTimeSource = &systemTimeSource{}
// RTTs provides round-trip times.
type RTTs interface {
Stats(percentile int, ref time.Time) (min, max, median, np time.Duration, count int)
}
var (
errFrequencyPlansTimeOffAir = errors.DefineInvalidArgument("frequency_plans_time_off_air", "frequency plans must have the same time off air value")
errFrequencyPlansOverlapSubBand = errors.DefineInvalidArgument("frequency_plans_overlap_sub_band", "frequency plans must not have overlapping sub bands")
)
// NewScheduler instantiates a new Scheduler for the given frequency plan.
// If no time source is specified, the system time is used.
func NewScheduler(
ctx context.Context,
fps map[string]*frequencyplans.FrequencyPlan,
enforceDutyCycle bool,
dutyCycleStyle DutyCycleStyle,
scheduleAnytimeDelay *time.Duration,
timeSource TimeSource,
) (*Scheduler, error) {
logger := log.FromContext(ctx)
if timeSource == nil {
timeSource = SystemTimeSource
}
if scheduleAnytimeDelay == nil || *scheduleAnytimeDelay == 0 {
scheduleAnytimeDelay = &ScheduleTimeLong
} else if *scheduleAnytimeDelay < ScheduleTimeShort {
logger.WithFields(log.Fields(
"minimum", ScheduleTimeShort,
"requested", *scheduleAnytimeDelay,
)).Info("Requested scheduling delay is too small")
scheduleAnytimeDelay = &ScheduleTimeShort
}
var timeOffAir *frequencyplans.TimeOffAir
for _, fp := range fps {
if timeOffAir != nil && fp.TimeOffAir != *timeOffAir {
return nil, errFrequencyPlansTimeOffAir.New()
}
timeOffAir = fp.TimeOffAir.Clone()
}
if timeOffAir.Duration < QueueDelay {
timeOffAir.Duration = QueueDelay
}
s := &Scheduler{
clock: &RolloverClock{},
timeOffAir: *timeOffAir,
fps: fps,
timeSource: timeSource,
scheduleAnytimeDelay: *scheduleAnytimeDelay,
}
if enforceDutyCycle {
for _, fp := range fps {
if subBands := fp.SubBands; len(subBands) > 0 {
for _, subBand := range subBands {
params := SubBandParameters{
MinFrequency: subBand.MinFrequency,
MaxFrequency: subBand.MaxFrequency,
DutyCycle: subBand.DutyCycle,
}
sb := NewSubBand(params, s.clock, nil, dutyCycleStyle)
var isIdentical bool
for _, subBand := range s.subBands {
if subBand.IsIdentical(sb) {
isIdentical = true
break
}
if subBand.HasOverlap(sb) {
return nil, errFrequencyPlansOverlapSubBand.New()
}
}
if !isIdentical {
s.subBands = append(s.subBands, sb)
}
}
} else {
band, err := band.GetLatest(fp.BandID)
if err != nil {
return nil, err
}
for _, subBand := range band.SubBands {
params := SubBandParameters{
MinFrequency: subBand.MinFrequency,
MaxFrequency: subBand.MaxFrequency,
DutyCycle: subBand.DutyCycle,
}
sb := NewSubBand(params, s.clock, nil, dutyCycleStyle)
var isIdentical bool
for _, subBand := range s.subBands {
if subBand.IsIdentical(sb) {
isIdentical = true
break
}
if subBand.HasOverlap(sb) {
return nil, errFrequencyPlansOverlapSubBand.New()
}
}
if !isIdentical {
s.subBands = append(s.subBands, sb)
}
}
}
}
} else {
noDutyCycleParams := SubBandParameters{
MinFrequency: 0,
MaxFrequency: math.MaxUint64,
}
sb := NewSubBand(noDutyCycleParams, s.clock, nil, dutyCycleStyle)
s.subBands = append(s.subBands, sb)
}
go s.gc(ctx)
return s, nil
}
// Scheduler is a packet scheduler that takes time conflicts and sub-band restrictions into account.
type Scheduler struct {
clock *RolloverClock
fps map[string]*frequencyplans.FrequencyPlan
timeOffAir frequencyplans.TimeOffAir
timeSource TimeSource
subBands []*SubBand
mu sync.RWMutex
emissions Emissions
scheduleAnytimeDelay time.Duration
}
var errSubBandNotFound = errors.DefineFailedPrecondition("sub_band_not_found", "sub-band not found for frequency `{frequency}` Hz")
func (s *Scheduler) findSubBand(frequency uint64) (*SubBand, error) {
for _, subBand := range s.subBands {
if subBand.Comprises(frequency) {
return subBand, nil
}
}
return nil, errSubBandNotFound.WithAttributes("frequency", frequency)
}
func (s *Scheduler) gc(ctx context.Context) error {
ticker := time.NewTicker(DutyCycleWindow / 2)
defer ticker.Stop()
for {
select {
case <-ctx.Done():
return ctx.Err()
case <-ticker.C:
s.mu.RLock()
serverTime, ok := s.clock.FromServerTime(s.timeSource.Now())
s.mu.RUnlock()
if !ok {
continue
}
to := serverTime - ConcentratorTime(DutyCycleWindow)
for _, subBand := range s.subBands {
subBand.gc(to)
}
s.mu.Lock()
s.emissions = s.emissions.GreaterThan(to)
s.mu.Unlock()
}
}
}
var errDwellTime = errors.DefineFailedPrecondition("dwell_time", "packet exceeds dwell time restriction")
func (s *Scheduler) newEmission(payloadSize int, settings *ttnpb.TxSettings, starts ConcentratorTime) (Emission, error) {
d, err := toa.Compute(payloadSize, settings)
if err != nil {
return Emission{}, err
}
for _, fp := range s.fps {
if fp.RespectsDwellTime(true, settings.Frequency, d) {
return NewEmission(starts, d), nil
}
}
return Emission{}, errDwellTime.New()
}
// SubBandCount returns the number of sub bands in the scheduler.
func (s *Scheduler) SubBandCount() int {
return len(s.subBands)
}
// syncWithUplinkToken synchronizes the clock using the given token.
// If the given token does not provide enough information or if the latest clock sync is more recent, this method returns false.
// This method assumes that the mutex is held.
func (s *Scheduler) syncWithUplinkToken(token *ttnpb.UplinkToken) bool {
if token.GetServerTime() == nil || token.GetConcentratorTime() == 0 {
return false
}
if lastSync, ok := s.clock.SyncTime(); ok && lastSync.After(*ttnpb.StdTime(token.ServerTime)) {
return false
}
s.clock.SyncWithGatewayConcentrator(token.Timestamp, *ttnpb.StdTime(token.ServerTime), ttnpb.StdTime(token.GatewayTime), ConcentratorTime(token.ConcentratorTime))
return true
}
var (
errConflict = errors.DefineAlreadyExists("conflict", "scheduling conflict")
errTooLate = errors.DefineFailedPrecondition(
"too_late", "too late to transmission scheduled time", "delay", "min",
)
errNoClockSync = errors.DefineUnavailable("no_clock_sync", "no clock sync")
errNoAbsoluteGatewayTime = errors.DefineAborted("no_absolute_gateway_time", "no absolute gateway time")
errNoServerTime = errors.DefineAborted("no_server_time", "no server time")
)
// Options define options for scheduling downlink.
type Options struct {
PayloadSize int
*ttnpb.TxSettings
RTTs RTTs
Priority ttnpb.TxSchedulePriority
UplinkToken *ttnpb.UplinkToken
}
// ScheduleAt attempts to schedule the given Tx settings with the given priority.
// If there are round-trip times available, the nth percentile (n = scheduleLateRTTPercentile) value will be used instead of ScheduleTimeShort.
func (s *Scheduler) ScheduleAt(ctx context.Context, opts Options) (res Emission, now ConcentratorTime, err error) {
defer trace.StartRegion(ctx, "schedule transmission").End()
s.mu.Lock()
defer s.mu.Unlock()
if opts.UplinkToken != nil {
s.syncWithUplinkToken(opts.UplinkToken)
}
if !s.clock.IsSynced() {
return Emission{}, 0, errNoClockSync.New()
}
minScheduleTime := ScheduleTimeShort
var medianRTT *time.Duration
if opts.RTTs != nil {
if _, _, median, np, n := opts.RTTs.Stats(scheduleLateRTTPercentile, s.timeSource.Now()); n >= scheduleMinRTTCount {
minScheduleTime = np/2 + QueueDelay
medianRTT = &median
}
}
log.FromContext(ctx).WithFields(log.Fields(
"median_rtt", medianRTT,
"min_schedule_time", minScheduleTime,
)).Debug("Computed scheduling delays")
var starts ConcentratorTime
now, ok := s.clock.FromServerTime(s.timeSource.Now())
if !ok {
panic("clock is synced without server time")
}
if opts.Time != nil {
var ok bool
starts, ok = s.clock.FromGatewayTime(*ttnpb.StdTime(opts.Time))
if !ok {
if medianRTT == nil {
return Emission{}, 0, errNoAbsoluteGatewayTime.New()
}
serverTime, ok := s.clock.FromServerTime(*ttnpb.StdTime(opts.Time))
if !ok {
return Emission{}, 0, errNoServerTime.New()
}
starts = serverTime - ConcentratorTime(*medianRTT/2)
}
} else {
starts = s.clock.FromTimestampTime(opts.Timestamp)
}
delay := time.Duration(starts - now)
if delay < minScheduleTime {
return Emission{}, 0, errTooLate.WithAttributes(
"delay", delay,
"min", minScheduleTime,
)
}
log.FromContext(ctx).WithFields(log.Fields(
"now", now,
"starts", starts,
"delay", delay,
)).Debug("Computed downlink start timestamp")
sb, err := s.findSubBand(opts.Frequency)
if err != nil {
return Emission{}, 0, err
}
em, err := s.newEmission(opts.PayloadSize, opts.TxSettings, starts)
if err != nil {
return Emission{}, 0, err
}
for _, other := range s.emissions {
if em.OverlapsWithOffAir(other, s.timeOffAir) {
return Emission{}, 0, errConflict.New()
}
}
if err := sb.Schedule(em, opts.Priority); err != nil {
return Emission{}, 0, err
}
s.emissions = s.emissions.Insert(em)
return em, now, nil
}
// ScheduleAnytime attempts to schedule the given Tx settings with the given priority from the time in the settings.
// If there are round-trip times available, the maximum value will be used instead of ScheduleTimeShort.
// This method returns the emission.
//
// The scheduler does not support immediate scheduling, i.e. sending a message to the gateway that should be transmitted
// immediately. The reason for this is that this scheduler cannot determine conflicts or enforce duty-cycle when the
// emission time is unknown. Therefore, when the time is set to Immediate, the estimated current concentrator time plus
// ScheduleDelayLong will be used.
func (s *Scheduler) ScheduleAnytime(ctx context.Context, opts Options) (res Emission, now ConcentratorTime, err error) {
defer trace.StartRegion(ctx, "schedule transmission at any time").End()
s.mu.Lock()
defer s.mu.Unlock()
if opts.UplinkToken != nil {
s.syncWithUplinkToken(opts.UplinkToken)
}
if !s.clock.IsSynced() {
return Emission{}, 0, errNoClockSync.New()
}
minScheduleTime := ScheduleTimeShort
if opts.RTTs != nil {
if _, _, _, np, n := opts.RTTs.Stats(scheduleLateRTTPercentile, s.timeSource.Now()); n >= scheduleMinRTTCount {
minScheduleTime = np/2 + QueueDelay
}
}
var starts ConcentratorTime
now, ok := s.clock.FromServerTime(s.timeSource.Now())
if !ok {
panic("clock is synced without server time")
}
if opts.Timestamp == 0 {
starts = now + ConcentratorTime(s.scheduleAnytimeDelay)
opts.Timestamp = uint32(time.Duration(starts) / time.Microsecond)
} else {
starts = s.clock.FromTimestampTime(opts.Timestamp)
if delta := minScheduleTime - time.Duration(starts-now); delta > 0 {
starts += ConcentratorTime(delta)
opts.Timestamp += uint32(delta / time.Microsecond)
}
}
sb, err := s.findSubBand(opts.Frequency)
if err != nil {
return Emission{}, 0, err
}
em, err := s.newEmission(opts.PayloadSize, opts.TxSettings, starts)
if err != nil {
return Emission{}, 0, err
}
i := 0
next := func() ConcentratorTime {
if len(s.emissions) == 0 {
// No emissions; schedule at the requested time.
return em.t
}
for i < len(s.emissions)-1 {
// Find a window between two emissions that does not conflict with either side.
if em.OverlapsWithOffAir(s.emissions[i], s.timeOffAir) {
// Schedule right after previous to resolve conflict.
em.t = s.emissions[i].EndsWithOffAir(s.timeOffAir)
}
if em.OverlapsWithOffAir(s.emissions[i+1], s.timeOffAir) {
// Schedule right after next to resolve conflict.
em.t = s.emissions[i+1].EndsWithOffAir(s.timeOffAir)
i++
continue
}
// No conflicts, but advance counter for potential next iteration.
// A next iteration can be necessary when this emission and priority exceeds a duty-cycle limitation.
i++
return em.t
}
// No emissions to schedule in between; schedule at timestamp or last transmission, whichever comes first.
afterLast := s.emissions[len(s.emissions)-1].EndsWithOffAir(s.timeOffAir)
if afterLast > em.t {
return afterLast
}
return em.t
}
em, err = sb.ScheduleAnytime(em.d, next, opts.Priority)
if err != nil {
return Emission{}, 0, err
}
s.emissions = s.emissions.Insert(em)
return em, now, nil
}
// Sync synchronizes the clock with the given concentrator time v and the server time.
func (s *Scheduler) Sync(v uint32, server time.Time) ConcentratorTime {
s.mu.Lock()
defer s.mu.Unlock()
return s.clock.Sync(v, server)
}
// SyncWithGatewayAbsolute synchronizes the clock with the given concentrator timestamp, the server time and the
// absolute gateway time that corresponds to the given timestamp.
func (s *Scheduler) SyncWithGatewayAbsolute(timestamp uint32, server, gateway time.Time) ConcentratorTime {
s.mu.Lock()
defer s.mu.Unlock()
return s.clock.SyncWithGatewayAbsolute(timestamp, server, gateway)
}
// SyncWithGatewayConcentrator synchronizes the clock with the given concentrator timestamp, the server time and the
// relative gateway time that corresponds to the given timestamp.
func (s *Scheduler) SyncWithGatewayConcentrator(timestamp uint32, server time.Time, gateway *time.Time, concentrator ConcentratorTime) ConcentratorTime {
s.mu.Lock()
defer s.mu.Unlock()
return s.clock.SyncWithGatewayConcentrator(timestamp, server, gateway, concentrator)
}
// IsGatewayTimeSynced reports whether scheduler clock is synchronized with gateway time.
func (s *Scheduler) IsGatewayTimeSynced() bool {
s.mu.RLock()
defer s.mu.RUnlock()
return s.clock.IsSynced() && s.clock.gateway != nil
}
// Now returns an indication of the current concentrator time.
// This method returns false if the clock is not synced with the server.
func (s *Scheduler) Now() (ConcentratorTime, bool) {
s.mu.RLock()
defer s.mu.RUnlock()
if !s.clock.IsSynced() {
return 0, false
}
return s.clock.FromServerTime(s.timeSource.Now())
}
// TimeFromTimestampTime returns the concentrator time by the given timestamp.
// This method returns false if the clock is not synced with the server.
func (s *Scheduler) TimeFromTimestampTime(t uint32) (ConcentratorTime, bool) {
s.mu.RLock()
defer s.mu.RUnlock()
if !s.clock.IsSynced() {
return 0, false
}
return s.clock.FromTimestampTime(t), true
}
// TimeFromServerTime returns an indication of the provided timestamp in concentrator time.
// This method returns false if the clock is not synced with the server.
func (s *Scheduler) TimeFromServerTime(t time.Time) (ConcentratorTime, bool) {
s.mu.RLock()
defer s.mu.RUnlock()
if !s.clock.IsSynced() {
return 0, false
}
return s.clock.FromServerTime(t)
}
// SubBandStats returns a map with the usage stats of each sub band.
func (s *Scheduler) SubBandStats() []*ttnpb.GatewayConnectionStats_SubBand {
var res []*ttnpb.GatewayConnectionStats_SubBand
for _, sb := range s.subBands {
res = append(res, &ttnpb.GatewayConnectionStats_SubBand{
MaxFrequency: sb.MaxFrequency,
MinFrequency: sb.MinFrequency,
DownlinkUtilizationLimit: sb.DutyCycle,
DownlinkUtilization: sb.DutyCycleUtilization(),
})
}
return res
}