[Xorp-cvs] XORP cvs commit: xorp/bgp xorp/libxipc xorp/libxorp
Pavlin Radoslavov
pavlin at icir.org
Thu Aug 10 17:57:44 PDT 2006
CVSROOT: /usr/local/share/doc/apache/cvs
Module name: xorp
Changes by: pavlin at xorpc.icir.org 2006-08-11 00:57:44 UTC
XORP CVS repository
Modified files:
bgp peer.cc route_table_cache.hh
route_table_deletion.cc route_table_deletion.hh
route_table_policy_sm.cc route_table_policy_sm.hh
route_table_ribin.cc route_table_ribin.hh
route_table_ribout.cc route_table_ribout.hh
socket.cc test_cache.cc test_decision.cc
test_deletion.cc test_dump.cc test_ribin.cc
libxipc xrl_pf_stcp.cc
libxorp Makefile.am Makefile.in asyncio.cc asyncio.hh
eventloop.cc eventloop.hh heap.hh selector.cc
selector.hh timer.cc timer.hh win_dispatcher.cc
win_dispatcher.hh
Log message:
Add a priority scheduler to XORP.
[Below is the original (slightly modified) description from the
author: Mark Handley.
In the future, the priority scheduler will be described in details
in some of the XORP documents.]
Old Scheduler:
Each time eventloop:run() is called:
1. Process all selectors that are not blocked.
2. Process all timers that have expired.
The problem with this is that when a process becomes overloaded, it
has no way to prioritise important tasks (like keepalives to the
finder) over unimportant stuff like background garbage collection.
Thus with BGP, if you have too many peers the finder sometimes
declares BGP dead. Also there's a real possibility of processing
input faster than output, resulting in unbounded temporary queues.
So, in the new scheduler, there is a new XorpTask class, which is
intended to get background tasks that don't need to happen at specific
times off the TimerList (so they won't interfere with proper timers).
There is also priority levels for timers, selectors, and tasks.
Finally, there are scheduling weights for tasks, so some tasks can
be processed more frequently that other tasks at the same priority
level. Basically tasks at each priority level are procesed using
Weighted Round Robin scheduling. In the long run, selectors should
probably use WRR too, but currently they don't. Timers obviously
don't have weights - this wouldn't make any sense - they just go off
at the relevant time.
So, each time eventloop::run() is called, only one event will be processed.
The timers, selectors, and tasks are polled to find the highest
priority runnable event from each category (timer, selector, or task).
If more than one category has the same highest priority, then only
one event is run; a timer, or if no timers runnable at that priority,
then a selector, or if no selectors runnable at that priority then a
task.
Note that a high priority selector or task can starve lower priority
selectors, tasks and timers if it's always runnable. Anything higher
that default priority should only be used with care, and only then for
events that are bounded in number.
Zero-second timers should now NOT be used - a XorpTask should be used
instead. They are still present in the code in quite a few places, but
they should be discouraged as they can starve selectors.
Normally the default priority should be used for timers. If timers of
different priorities are mixed, they won't necessarily go off in time
order - a high priority timer can go off before an earlier low
priority timer if the process is heavily loaded.
The aim to make the defaults sensible, so almost all existing code
can run unchanged. However, BGP has been to use non-default
priorities for many tasks to improve its overload behaviour.
XRL Keepalive timers have a very high priority to ensure they always
happen. No other event has such a high priority by default.
AsyncFileWriters have a slightly higher than default priority by
default. This is because getting output out of a process generally
frees up temporary state, so it's usually better to write before
reading. The default priority can be overwritten of course.
In the end, it should be possible to get much improved robustness by
careful use of priorities and weights. Though, it might take a
while to tune things properly.
Submitted by: Mark Handley
Revision Changes Path
1.141 +1 -3; commitid: f9fa44dbd2c37ea6; xorp/bgp/peer.cc
1.22 +10 -11; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_cache.hh
1.22 +7 -13; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_deletion.cc
1.19 +3 -3; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_deletion.hh
1.7 +9 -9; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_policy_sm.cc
1.8 +3 -3; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_policy_sm.hh
1.45 +12 -15; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_ribin.cc
1.24 +4 -4; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_ribin.hh
1.30 +20 -12; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_ribout.cc
1.16 +3 -2; commitid: f9fa44dbd2c37ea6; xorp/bgp/route_table_ribout.hh
1.44 +4 -2; commitid: f9fa44dbd2c37ea6; xorp/bgp/socket.cc
1.30 +2 -2; commitid: f9fa44dbd2c37ea6; xorp/bgp/test_cache.cc
1.38 +7 -7; commitid: f9fa44dbd2c37ea6; xorp/bgp/test_decision.cc
1.29 +16 -16; commitid: f9fa44dbd2c37ea6; xorp/bgp/test_deletion.cc
1.53 +41 -41; commitid: f9fa44dbd2c37ea6; xorp/bgp/test_dump.cc
1.34 +11 -9; commitid: f9fa44dbd2c37ea6; xorp/bgp/test_ribin.cc
1.48 +8 -4; commitid: f9fa44dbd2c37ea6; xorp/libxipc/xrl_pf_stcp.cc
1.48 +12 -1; commitid: f9fa44dbd2c37ea6; xorp/libxorp/Makefile.am
1.61 +32 -19; commitid: f9fa44dbd2c37ea6; xorp/libxorp/Makefile.in
1.26 +12 -7; commitid: f9fa44dbd2c37ea6; xorp/libxorp/asyncio.cc
1.17 +10 -5; commitid: f9fa44dbd2c37ea6; xorp/libxorp/asyncio.hh
1.16 +69 -7; commitid: f9fa44dbd2c37ea6; xorp/libxorp/eventloop.cc
1.22 +57 -18; commitid: f9fa44dbd2c37ea6; xorp/libxorp/eventloop.hh
1.12 +2 -1; commitid: f9fa44dbd2c37ea6; xorp/libxorp/heap.hh
1.35 +111 -6; commitid: f9fa44dbd2c37ea6; xorp/libxorp/selector.cc
1.20 +23 -3; commitid: f9fa44dbd2c37ea6; xorp/libxorp/selector.hh
1.33 +156 -58; commitid: f9fa44dbd2c37ea6; xorp/libxorp/timer.cc
1.30 +60 -23; commitid: f9fa44dbd2c37ea6; xorp/libxorp/timer.hh
1.14 +42 -6; commitid: f9fa44dbd2c37ea6; xorp/libxorp/win_dispatcher.cc
1.11 +24 -4; commitid: f9fa44dbd2c37ea6; xorp/libxorp/win_dispatcher.hh
More information about the Xorp-cvs
mailing list