Online set cover variant? Routing of requests 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$. 

Note:


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.
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.