We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially.

Each request may have multiple paths, but can choose only one of them. For example, in the Figure shown, there are two paths from $s1$ to $s4$ i.e., path1 : $s1-s2-s3-s4$ and path 2: $s1-s5-s6-s4$.

Further, each node on the path has an associated table that records entries. When a path is chosen, an entry may or may not be added to each node on the path. Whether an entry is added or not depends on the nature of the request, but that is not relevant here. Also, the node tables are independent of each other.

Each table has a limit on the number of entries. Suppose each table can hold a maximum of $n$ entries. When a table is full, that node cannot be chosen on any path. The blue boxes in the figure represent the percent full of each table. The node $s3$ is more utilised than the other nodes. If $s3$ becomes full, the path $s1-s2-s3-s4$ cannot be used to route any more requests.

Now, the challenge is to route the maximum number of requests, as they arrive sequentially. Here is what I have so far.

  • Heuristic 1: Choose the path with the least total new table entries added. Using this heuristic, however, can lead to non-uniform utilisation of the tables. Suppose that on the $s1-s2-s3-s4$ path, entries are added only at $s3$. And using the other path, entries are added at $s1$, $s5$, and $s6$. Heuristic 1 will choose path 1, but this may lead to faster fill-up of $s3$ and path1 cannot be used to route more requests.

  • Heuristic 2: Choose a cost function for each node based on a) cost to add new entry and b) percentage utilisation of table. Then choose the path with least total cost.

Let us define the cost metric as $ cost_{node} = cost_{new\;entry} + \frac{|existing\;entries|}{n}$

Using this heuristic, path 2 will be chosen, given the conditions stated above.


Now my question is two fold:

  • Is there a better way of going about this?

  • Given the two heuristics, how would I go about showing the competitive ratio?

Any help in this regard is appreciated.

Edited: For the sake of simplicity, let us consider for each node on a candidate path, a new table entry is added with a probability $p_i$ and not added with probability $1-p_i$.


  • When a request arrives, and we get a set of candidate paths, we can know in $\mathcal{O}(1)$ time for each node in the path, whether it will have an entry added to its table or not. So in $\mathcal{O}(l)$ time we can know the number of new table entries for a path, where $l$ is the length of the path.
  • We have global knowledge about the number of entries in a table of each node at every time instant.
  • $\begingroup$ This sounds pretty complicated. Can you simplify/abstract this any further? When a request arrives, do we know in advance which nodes will have entries added and which won't? Can we ignore the "may or may not be added to each node" and assume an entry is always added to each node on the path, to simplify the problem? What do you mean by "total new rules"? What are rules? Do you mean table entries? Do we have global knowledge of how full the tables at all of the nodes are, when choosing among the candidate paths? $\endgroup$
    – D.W.
    Apr 13 '18 at 15:42
  • $\begingroup$ Edited . For the sake of simplicity, we can consider all $p_i$ same. Does that help? Sorry for the rules/table entries confusion. Indeed I meant table entries. $\endgroup$
    – Niloy Saha
    Apr 13 '18 at 17:06
  • $\begingroup$ It seems to me that if you want to get any kind of worst-case bound, you will need to consider (only) the maximum utilisation of any node on the path. Separately, it's not clear whether there is a probability distribution over destination vertices, or whether this should also be given "worst-case" treatment. $\endgroup$ Apr 14 '18 at 13:30

In general, there are two approaches you can take here:

Empirical evaluation. Pick a realistic workload (a data set with a bunch of scenarios, where each scenario is a sequence of requests). Use this as a benchmark. Test each candidate heuristic on that benchmark, and see which one performs the best on this benchmark.

Theoretical analysis. Alternatively, you can try to prove a theorem about the competitive ratio of these two heuristics. That may be very difficult.

I suspect it's going to be a lot more feasible -- and potentially more useful -- to take the former approach. It does require you to have a dataset of representative requests.

I can suggest another plausible heuristic. Given a graph, you can find use bottleneck shortest paths to find the best path from $s$ to $t$, where "best" is measured by the number of slots in the least empty node that's visited along that path. The larger that number, the better (it means there exists a path with plenty of spare capacity). So, one possible heuristic is to choose whichever path reduces this number the least.

There are probably many other heuristics you could come up with. I suggest brainstorming a few, then evaluating them empirically using the approach listed above.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.