<div><em>
<div><em>On <em>Mon Feb 27 08:50:02 CET 2006 Thomas Lopatic wrote:</em></em></div></em></div>
<div><em></em> </div>
<div>Yes, I believe it would. However, one of the things that we'd need to<br>think through for this is the following. Metrics come in a couple of<br>variants. They differ in how the metric of a multi-hop path is derived 
<br>from the metrics of the individual hops. I think that we have three<br>different kinds.<br><br>  * Additive metrics. Simply add the metrics of the individual hops to<br>obtain the metric of the full path. An example for this is ETX. If we 
<br>have a two-hop path from node A via node B to node C, the ETX for the<br>path from A to C is the sum of the ETX between A and B and the ETX<br>between B and C.<br><br>  * Multiplicative metrics. Packet loss is multiplicative, I'd say. If 
<br>50% of the packets make it from A to B and 40% make it from B to C then<br>the probability of a successful packet transmission on the path A -> B<br>-> C is 50% * 40% = 20%.<br><br>  * Minimum metrics. If we look at the bandwidth of a path then the hop 
<br>that has the lowest bandwidth is the bottleneck and dictates the<br>bandwidth of the complete path. The bandwidth of A -> B -> C then is<br>minimum(bandwidth(A -> B), bandwidth (B -> C)).</div>
<div> </div>
<div><font color="#000099">These are also the metrics I'm aware of, and I can't think, nor have I read that any other types exist (although 'minimum metric' is often referred to as 'concave metric' in the literature). The problem is (and I hope I'm not teaching any grannies to suck eggs here, apologies in advance if I am :P ) is that, as soon as you start combining metrics, the problem becomes horrificly expensive to solve. The following paper describes this issue: 
</font></div>
<div><a onclick="return top.js.OpenExtLink(window,event,this)" href="http://www-inst.eecs.berkeley.edu/~ee290t/sp04/lectures/rdr_paper34.pdf" target="_blank">http://www-inst.eecs.berkeley.edu/~ee290t/sp04/lectures/rdr_paper34.pdf 
</a></div>
<div> </div>
<div><font color="#000099">Which shows that if we have n additive and m multiplicative metrics, and n+m => 2, then our problem is NP-Complete, which as far as I know, basically means its too expensive to feasably calculate :) (I got this from reading 
<a onclick="return top.js.OpenExtLink(window,event,this)" href="http://qolsr.lri.fr/papers/qolsr-selection-lritr04.pdf" target="_blank">http://qolsr.lri.fr/papers/qolsr-selection-lritr04.pdf</a>, page 5, section B as well as a bit of wikipediaing)
</font> </div>
<div><em></em> </div>
<div><em>On <em>Mon Feb 27 08:50:02 CET 2006 Thomas Lopatic wrote:</em></em></div>
<div><br>For additive metrics the Dijkstra algorithm applies. But does it also<br>apply to the other two types? What about combinations of metrics of<br>different kinds, e.g. something based on ETX and the bandwidth? Hmmm. 
<br>Anyone?<br><br>-Thomas</div>
<div>  </div>
<div>
<div><font color="#000099">It does indeed seem as though most attempts at providing some QoS to an ad-hoc protocol are attempting to simplify the multiple metric problem, to that of a single metric problem, rather than attempting to solve the full, NP-Complete problem... 
</font></div>
<div><font color="#000099"></font> </div>
<div><font color="#000099">For example</font></div>
<div><font color="#000099"></font> </div>
<div><a onclick="return top.js.OpenExtLink(window,event,this)" href="http://qolsr.lri.fr/papers/qolsr-multimetric-mwcn03.pdf" target="_blank">http://qolsr.lri.fr/papers/qolsr-multimetric-mwcn03.pdf</a></div>
<div> </div>
<div><font color="#000099">Considers at one point (page one, 'The DBCLH Problem') hop-count, delay and bandwidth as metrics. They use a method based on lagrangian relaxation. As far as I understand, this means that the constraints are changed based on the understanding of the problem area. In this case they reason that 
<font face="Times New Roman" size="2">
<p align="left">"The delay has two basic</p>
<p align="left">components: queuing delay and propagation delay. The</p>
<p align="left">queuing delay is more dynamic and traffic-sensitive, thus</p>
<p align="left">bandwidth is often more critical for most multimedia</p>
<p align="left">applications. If there is no sufficient bandwidth, queuing</p>
<p align="left">delay and probably the loss rate will be very high. So,</p>
<p align="left">we define the precedence as bandwidth and then the</p>
<p align="left">propagation delay. Our strategy is to find a path that</p>
<p align="left">satisfies the bandwidth constraint, and when there is more</p>
<p align="left">than one, we choose the one with shortest hop and under</p>
<p align="left">the delay constraint."</p>
<p align="left"><font face="arial,sans-serif">So I translate this as 'Rather than consider all the metrics individually, simplify it all into one metric. Check bandwidth first, then if there are multiple paths with the same bandwidth, then look at propagation delay. We do this because bandwidth is usually most important, and thus this will give you a near optimal route most of the time'.... I could be wrong though, I'm not very good at translating academiaese :) I think I've read of this idea in other places as the 'widest-shortest algorithm'.... There are some other research papers discussing heuristics flying about too, but I haven't had the time to digest them yet.
</font></p></font></font></div>
<div><font color="#000099">... In any case, I'm not sure the consideration of the seperate metrics in some kind of framework for a plugin is as important as having one single hooking point for the current (ETX) heuristic metric. It would be nice to see this heuristic with only one hook into the code-base, as this would allow easy swapping with other heuristics, and would open the code up to others to allow them to start experimenting easier in this respect :) Although having not looked at the code base much, I'm not sure how feasable this is :S
</font></div>
<div><font color="#000099"></font> </div>
<div><font color="#000099">I also have a question regarding what data (to be used for metrics) is available directly from different technologies? For example, what raw network data can be gathered from, for example, 802.11b
, or ethernet? I'm aware through ETX that we can get packet loss.... But how about throughput? Is this data easily obtained? How about delays (transmission/queueing)? Do drivers provide this information?</font></div>
<div><font color="#000099"></font> </div>
<div><font color="#000099">Anyway, thats my 2c on the situation. Sorry if any of my questions/statements seem a bit dumb, this network stuffs quite a new topic for me :) And great project chaps! I've looked at a lot of ad-hoc implementations to use, and this definitely seems to be the one for me :D
</font></div>
<div><font color="#000099"></font> </div>
<div><font color="#000099">Best regards</font></div>
<div><font color="#000099"></font> </div>
<div><font color="#000099">Liam Conroy</font></div></div>