# Simplified use of Baye's Theorem in Computer Networks

• September 2nd, 2005, 05:35 PM
pi><boy
Simplified use of Baye's Theorem in Computer Networks
Notation:

1. P(X) means the probability of occurence of event X.

2. P(X|Y) means the probability of occurence of event X provided event Y has already happened

3. An means A with subscript n.

4. 'sum'is the summation function.

******************************
Introduction to Baye's Theorem
******************************

Suppose for the occurence of an event A, n hypotheses are proposed like A1,A2,......,An. Now for 1≤k≤n,

P(Ak|A)= [P(Ak)*P(A|Ak)] / [∑ (i=1 to n) {P(Ai)*P(A|Ai)} ]

The probabilites P(Ai), i=1,2,.....,n are called a priori probabilities and are known before beginning the experiment. Note these are the probabilities of occurence of the hypotheses.

The probabilities P(A|Ai) are called likelihoods as they show how likely A is to occur given a priori probabilities.

The probabilites P(Ai|A) are called posteriori probabilities as they are obtained after the experiment.

***********************
The Mathematical Model
***********************

http://img295.imageshack.us/img295/1549/bayes0pg.png

The objective is to send data from A to B through the available nodes on the network.

Now P(Ci|A) implies probability of data being received correctly by Ci provided A sends it and P(A|Ci) implies probability of A sending the data provided Ci acknowledges the transmission. The acknowledgment will depend upon the state of the machine at node Ci. For e.g. if it is engaged in another transmission or is performing a resource hogging task it may not acknowledge the transmission. So P(A|Ci) is to be found out in real time by the network software.

Now applying the Baye's Theorem to the segment of data flow from A to Ci,

P(Ci|A)= [P(Ci)*P(A|Ci)] / [∑ (i=1 to 4) {P(Ci)*P(A|Ci)} ]

Before the beginning of data flow, the prbability of all Ci receiving data is equal i.e. P(C1)=P(C2)=P(C3)=P(C4)=1/4

From this the probability of Ci receiving the data correctly will be known and the node with P(Ci|A)=1 will recieve the datagrams. If none of them provides with absolute prbability i.e. 1 then the data will not be sent, A will wait for a few minutes or try other nodes in the network.

In the same way data from Ci will be sent to Di and at last to B.

I tried my best to explain whatever came in my mind. It may also sound stupid. But please tell whatever you feel of this.

YOU HAVE FULL RIGHTS TO FLAME ME.
• September 3rd, 2005, 05:37 AM
pi><boy
Can anybody tell me why the image is not showing up? I have used the [IMG] tag. :?
• September 3rd, 2005, 05:54 AM
Negative
It links just fine. Images don't show up within posts here :)
• September 3rd, 2005, 10:09 AM
sec_ware
Hi

pi&gt;&lt;boy, you decided to present a very interesting approach to traffic engineering
of a fixed routing problem from A to B. A couple of suggestions/questions. Please do
not take offence, I am just curious.

First, it would be interesting if you could illustrate the power of Bayes' Theorem on a
widely-used application, ie. the typical disease test probabilities: What is the probability
that the HIV is present if the result is positiv? If I would not know about Bayes' Theorem,
I would have no idea what you are talking about :) Then, to which extend can this
be used to analyse traffic and to decide ...something.

Second, what really is your goal? Do you want to send traffic from A to B, or do you want to
find an optimal path given a priori distribution? Is this even possible? And if, why so and
how do you do it? I would like to see an explicit method to determine a specific path given
a certain "situation". You have describe the approache, but still I would
not be able to perform the calculation without further development.
Hence, I need more illustration :)

Third, the Bayesian framework needs an assumption of the priori distributions, which
often is a point of criticism. Why have you chosen the Bayesian approach rather than the
likelihood/Ford Fulkerson method[1]? Can the Bayesian approach be mapped onto
those standard methods?

Fourth, an idea for an extension: Here you consider a system that you control completely .
Assume a system, where you just observe a part of the network, typically the Internet.
Then, there is unobserved, but possible traffic from A to B, or more precise from any
observable node to another one. Can you still use a Bayesian framework to analyse the
network traffic, ie can you infer the traffic from a node to another only being able
to measure a set of observable links, assuming you cannot observe the node itself?
...

Cheers :)

[1] http://www-b2.is.tokushima-u.ac.jp/~.../Maxflow.shtml
• September 3rd, 2005, 05:49 PM
pi><boy
Hi sec_ware,

I am quite grateful to you that you took this seriously.

But, I am still only a high school student and have never ever heard of Ford Fulkerson method :(

I know that you have quite a strong background in theoritical maths. But for me, no such thing at present.

1. Yes, "Bayesian Networks" are used to analyse such probabilities and they are quite succesful. You can feed any amount of causes and some predefined effects in a Bayesian Network and as a prequisite, define a few possible outcomes. After that as you use the system, it learns and provides accurate information and after a certain amount of usage it becomes impeccable. Bayesian Networks are not only used in connection to Bayes Theorem but also with other models like Hidden Markov Models.

2. My goal is to find an optimal path. Given in a LAN, the speed of transmission is quite high. So I don't think that figuring out a priori probabilities would not be such a mean task. I have heard of data transmission techniques called CSMA/CD. I have no experience of them and I was thinking if this type of algorithm can be used in such schemes. In this context, I would like to request the members to provide me some reading stuff and links.

3. I have used Bayes Theorem as I said Bayesian Networks learn by itself and if needed can also start from scratch. I think this is better than the multi-layered neural networks.

I would try to learn about the Ford method you have mentioned and then only can I map the algorithm to it.

4. Please excuse me for now. I have to go offline. Will be back within 24 hours........

And why would I take offence when you are posting :D
• November 6th, 2005, 04:40 PM
pi><boy
Quote:

Fourth, an idea for an extension: Here you consider a system that you control completely .
Assume a system, where you just observe a part of the network, typically the Internet.
Then, there is unobserved, but possible traffic from A to B, or more precise from any
observable node to another one. Can you still use a Bayesian framework to analyse the
network traffic, ie can you infer the traffic from a node to another only being able
to measure a set of observable links, assuming you cannot observe the node itself?
...

The answer to this is probably yes. I will try to just give an outline of the process.
Code:

```1. Perform a predefined number of traceroute attempts at constant time intervals from A on B. 2. If two or more paths found consisting of different routers create a Bayesian network using the routers obtained from the traceroute attempt as the nodes. The value of the nodes can be assigned the absolute time in ms. 3. Keep updating the value of the nodes along with each traceroute. 4. Priority of data transmission:                   (a) First check the number of hops or routers that are involved in the transmission.                                     (b) The path consisting of the least number of hops is assigned the topmost priority.                   (c) If number of hops is same for two or more paths, choose the path with the least                                                  value at the nodes and assign it topmost priority. 5. Transmit data through the path with the topmost priority.```
Note: Even if any router is down during the course of data transmission, it leads to the removal of the whole path from the Bayesian network and retransmission of data occurs through the other paths if available.

• November 7th, 2005, 02:43 AM
Ghost_25inf
Attach can and string to point A
Attach can and other end of string to point B
pull tight and send data

Simplified? I would hate to see the unsimplified copy
• November 7th, 2005, 04:17 AM
pi><boy
Oh! So you think its that easy as 2 rusty cans and a slack string??

Maybe you possess the same views about the spam filtering softwares, the disease testing softwares, the Microsoft Office Assistant and maybe even the Autoclass project by NASA.

See for yourself:

http://ic-www.arc.nasa.gov/ic/projec...ass/index.html

Though I admit that Bayesian analysis comes with its own set of limitations.

The most striking problem is that of the aprior distributions and the belief that each of the factors is equally important.

And secondly, sec_ware fully illustrated it in his fourth point. Exploration of unknown networks through this frameworks may become costly in real time as it would involve calculation of probabilities of each branch and given the number of variables that can arise it would also become much more time consuming process.

Still its higly effective in case of a small network such as a LAN or even a WAN spanning some two or three blocks.