Hashed and Hierarchical Timing Wheels

Август 21, 2022

Главная
Информатика
Hashed and Hierarchical Timing Wheels

Содержание

2. Motivation Timers are important for Failure recovery, rate based flow control, scheduling algorithms, controlling packet lifetime
3. Model & Performance Measure Routines in the model Client Invoked : START_TIMER(Interval, Request_ID, Expiry_Action) STOP_TIMER(Request_ID) Timer
4. Currently Used Timer Schemes a b c d e Can maintain absolute expiry time or the
5. Tree based timers a b c d a b c d maintain absolute expiry time START_TIMER
6. Simple Timing Wheel Keep a large timing wheel A curser in the timing wheel moves one
7. Hashed Timing Wheel 1 2 3 4 5 6 7 0 2 4 1 2 2
8. Hashed Timing Wheel Sorted Lists in each bucket The list in each bucket can be insertion
9. Hierarchical Timing Wheel 1 2 3 4 5 6 7 0 3 5 7 5 2
10. Hierarchical Timing Wheels START_TIMER = O(m) where m is the number of wheels The bucket value
12. Скачать презентацию

Слайд 2

Motivation
Timers are important for
Failure recovery, rate based flow control, scheduling

algorithms, controlling packet lifetime in networks
Timer maintenance high if
Processor interrupted every clock tick
Fine granularity timers are used
# outstanding timers is high
Efficient timer algorithms are required to reduce the overall interrupt overhead

Слайд 3

Model & Performance Measure
Routines in the model
Client Invoked :
START_TIMER(Interval, Request_ID, Expiry_Action)
STOP_TIMER(Request_ID)
Timer

tick invoked :
PER_TICK_BOOKKEEPING
EXPIRY_PROCESSING
Performance Measure
Space : Memory used by the data structures
Latency : Time required to begin and end any of the routines mentioned above

Слайд 4

Currently Used Timer Schemes
a
b
c
d
e
Can maintain absolute expiry
time or the timer

interval
START_TIMER = O(1)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(n)

maintain absolute expiry time
START_TIMER = O(n)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1)

Слайд 5

Tree based timers
a
b
c
d
a
b
c
d
maintain absolute expiry
time
START_TIMER = O(log(n))
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING

= O(1)

Can degenerate to a
linear list in case of equal
Interval timers
START_TIMER = O(n)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1)

Слайд 6

Simple Timing Wheel
Keep a large timing wheel
A curser in the timing

wheel moves one location every time unit (just like a seconds hand in the clock)
If the timer interval is within a rotation from the current curser position then put the timer in the corresponding location
Requires exponential amount of memory

START_TIMER = O(1)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1)

Слайд 7

Hashed Timing Wheel
1
2
3
4
5
6
7
0
2
4
1
2
2
1
1
2
# of rounds remaining
Say wheel has 8 ticks
Timer value

= 17
Make 2 rounds of wheel + 1 more tick
Schedule the timer in the bucket “1”
Keep the # rounds with the timer
At the expiry processing if the # rounds > 0 then reinsert the timer

Слайд 8

Hashed Timing Wheel
Sorted Lists in each bucket
The list in each bucket

can be insertion sorted
Hence START_TIMER takes O(n) time in the worst case
If n < WheelSize then average O(1)
Unsorted list in each bucket
List can be kept unsorted to avoid worst case O(n) latency for START_TIMER
However worst case PER_TICK_BOOKKEEPING = O(n)
Again, if n < WheelSize then average O(1)

Слайд 9

Hierarchical Timing Wheel
1
2
3
4
5
6
7
0
3
5
7
5
2
1
1
Hours wheel
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
Minutes wheel
Seconds wheel

Слайд 10

Hierarchical Timing Wheels
START_TIMER = O(m) where m is the number of

wheels
The bucket value on each wheel needs to be calculated
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1) on avg.

Hashed and Hierarchical Timing Wheels

Содержание

MotivationTimers are important for Failure recovery, rate based flow control, scheduling

Model & Performance MeasureRoutines in the modelClient Invoked :START_TIMER(Interval, Request_ID, Expiry_Action)STOP_TIMER(Request_ID)Timer

Currently Used Timer SchemesabcdeCan maintain absolute expiry time or the timer

Tree based timersabcdabcdmaintain absolute expiry time START_TIMER = O(log(n))STOP_TIMER = O(1)PER_TICK_BOOKKEEPING

Simple Timing WheelKeep a large timing wheelA curser in the timing

Hashed Timing Wheel1234567024122112# of rounds remainingSay wheel has 8 ticksTimer value

Hashed Timing WheelSorted Lists in each bucketThe list in each bucket

Hierarchical Timing Wheel123456703575211Hours wheel1234567012345670Minutes wheelSeconds wheel

Hierarchical Timing WheelsSTART_TIMER = O(m) where m is the number of

Похожие презентации