Skip to content

Instantly share code, notes, and snippets.

@vincentbernat
Created December 11, 2011 11:36
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save vincentbernat/1460108 to your computer and use it in GitHub Desktop.
Simulation of rt_garbage_collect()
# -*- coding: utf-8 -*-
"""
Simulate route cache with the following assumptions:
1. route cache is never full (things become difficult in this case)
2. route cache is always able to meet its goal (check gc_goal_miss
counter to see if this is your case)
"""
from matplotlib.pylab import *
import random
# Compute various data
def entries(route, seconds, max_size, rhash_entries,
gc_min_interval, gc_elasticity, gc_thresh):
"""
`route` is a function taking two arguments: time in seconds and
number of entries. This allows to specify the number of new route
at the given second.
`seconds` is the number of seconds to run.
"""
time = np.arange(0, seconds, gc_min_interval)
routes = np.zeros(len(time))
entries = np.zeros(len(time))
goal = np.zeros(len(time))
equilibrium = np.zeros(len(time))
for i in xrange(1, len(time)):
entries1 = entries[i-1]
routes1 = route(time[i], entries1)
if entries1 < gc_thresh:
# No garbage collector
entries[i] = entries1 + routes1
goal[i] = goal[i-1]
equilibrium[i] = equilibrium[i-1]
continue
# Garbage collector
# See net/ipv4/route.c (rt_garbage_collect)
goal1 = entries[i-1] - gc_elasticity*rhash_entries
if goal1 <= 0:
eq1 = max(equilibrium[i-1], gc_thresh)
goal1 = entries[i-1] - eq1
if goal1 > 0:
eq1 = eq1 + min(goal1/2, rhash_entries)
goal1 = entries[i]
else:
goal1 = max(goal1/2, rhash_entries)
eq1 = entries1 - goal1
if goal1 < 0:
eq1 = eq1 + goal1
# We assume here that we are able to meet our goal
entries[i] = min(entries1 + routes1 - max(0, goal1),
max_size)
goal[i] = goal1
equilibrium[i] = eq1
routes[i] = routes1
return time, entries
# Setup axis
rcParams['font.size'] = 11
rcParams['legend.loc'] = 'best'
fig = figure(num=None, figsize=(11.69, 8.27), dpi=100)
lines = []
def route2(t, e):
if t < 1000:
return 1000-e/6000
if t < 2000:
return 100000
return 1000-e/6000
t, e = entries(route2, seconds=3000,
max_size=2**22, rhash_entries=2**18,
gc_min_interval=0.5, gc_elasticity=8, gc_thresh=2**18)
lines.append(plot(t, e, ':', color="#E97F02",
label="Attack ~100 000/s, 262144..4194304, t=262144, e=8"))
def route3(t, e):
if t < 1000:
return 1000-e/6000
if t < 2000:
return 0
return 1000-e/6000
t, e = entries(route3, seconds=3000,
max_size=2**22, rhash_entries=2**18,
gc_min_interval=0.5, gc_elasticity=8, gc_thresh=2**18)
lines.append(plot(t, e, '-', color="#8A9B0F",
label="Paused, 262144..4194304, t=262144, e=8"))
route1 = lambda t,e: 1000-e/6000
t, e = entries(route1, seconds=3000,
max_size=2**22, rhash_entries=2**18,
gc_min_interval=0.5, gc_elasticity=8, gc_thresh=2**18)
lines.append(plot(t, e, '-', color="#490A3D", linewidth=2,
label="~2000 r/s, 262144..4194304, t=262144, e=8"))
t, e = entries(route1, seconds=3000,
max_size=2**22, rhash_entries=2**20,
gc_min_interval=0.5, gc_elasticity=2, gc_thresh=2**18)
lines.append(plot(t, e, '-', color="#BD1550",
label="~2000 r/s, 1048576..4194304, t=262144, e=2"))
grid(True, which="both", linestyle="dotted", color="gray")
xlabel("Elapsed time (s)")
legend(fancybox=True, shadow=True,
prop=dict(size=10))
#savefig("%s.pdf" % title)
#savefig("%s.svg" % title, transparent=True)
show()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment