[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

efficient way for dynamic classifier?




I have a question on current implementation of routing table (routing
classifier). It can also apply to more general cases. The question
is: currently in ns, a "table" is implemented by a array. The size of the
table is initialized to 32. Whenever we need more space, we will double
the
table size (c.f. alloc() in classifier.cc). It works fine if no dynamic
thing happens. However, in dynamic routing algorithm, we need to update
the routing table very frequently (whenever we receive a routing update
message). In this case, we need to refresh the routing table. In
route-proto.tcl, it did the following things:
      1. call delete-routes to remove all previous records
      2. compute new routes based on new information
      3. call add-routes to add all new routes.
The problem is, currently delete-routes didn't do any thing to
"shrink" the routing table, in other words, it didn't reduce the
number of "occupied slots" correspondingly, so to add the new routes, it
has to enlarge the routing table. As a result, the routing table will keep
growing until the simulation ended, it will be a disaster if we need to do
a very long time simulation.

Of course we can do some simple modification for this special case, (for
example, set the size of the routing table to 0 in the first step because
here we need to clear the routing table). What I am concerning is if in
the future, we want to do something like only delete some of the routing
entries, is there any efficient way other than pushing the alive entries
together?

cheers.

Guo, Liang.