Markov chains research

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

1. Introduction

1.1. Background Research & Literature Review

Many phrases and concepts will be used in this research, and they all need to be researched, identified, and stated clearly, to avoid any misunderstanding.

Markov Chains

Markov Chains was firstly developed by a Russian mathematician named Andrey Markov (1856 ~ 1922), his research was about something called “stochastic processes”. Later on, his research was carried on by the mathematicians and scientists, and was named as “Markov Chains”.

Markov chains are (Hayes & Ganesh Babu, 2004) a set of random processes, which assume a countable set of variables and their values and state changes that occurs within a specific intervals, which will be referred to as T seconds.

Markov chains are characterized by memorylessness in the state transitions; the probability distribution of the upcoming state depends only on the current state and not on the previous state that led up to the present state. Let Si indicate the state of the system at time iT.

Hayes & Ganesh (Hayes & Ganesh Babu, 2004) concluded that the memoryless property could be implied as:

PSN+1=lN+1S1=l1, S2=l2,...,SN=lN = PSN+1=lN+1SN=lN  (1.1)

Where l1, l2,..., lN,... are the particular values, drawn from a countable set that the state assumes. Bernoulli trials provide an example of Markov chains. This consists of a sequence of equally spaced trials or tests. On each trial there is success with probability P, which is independent of the outcomes of past trials. We define the state on the Nth trial to be the accumulated number of successes. [1]

Let Si denote the total number of successes after the ith trial,the probability distribution of the state after the (N+1)thtrial depends on the previous states given by the previous equation. Generally speaking, the probability of changing from one state to another is not a fixed probability, which means it may change overtime.

However, Hayes & Ganesh (Hayes & Ganesh Babu, 2004) found that for a homogenous Markov Chains - which is time dependence- the transition probability depends only on the current state, in this case, we use another formula

Pij=PSN+1=jSN=i    (1.2)

Where Pij refers to the probability of transition from state i to state j.

Basically, this research will show a list of network states, which will include various variables and their probabilities. Then those values will be simulated using MATLAB, in order to show the differences that happen when we change one or more variable.

By the time, many scientists started to apply the Markov Chains theory on the Networks to optimize them; as mentioned before, the best way to optimize a network is by optimizing the way it organizes its traffic.

The point of interest was the Queues, and when applying Markov Chains on the Queuing System, we use the term Markovian Systems.

Since the distribution of the interval and service times are exponential distributions, (Willig, 1999) which will imply that this will exhibit the Memoryless Property also known as Markov Chains. [2]

Based on that, Willig (Willig, 1999) found two important conclusions:

- The state of the system could be summarized in a single variable, for example the number of Packets in the system, But, since the processing time distribution is not memoryless, and so we need to know the remaining time for the current packet to be processed, in addition to the number of packets in the queue.

- In that case, In order to solve this conflict, Markovian System can be mapped to a Continuous Time Markov Chains (CTMC).

Continuous Time Markov Chains will be mainly used to represent the state of the network, which means that we will use the queuing theory A/S/n to represent the different states of our network, and the value of each state.

A: Packet Arrival Intervals.

S: Service (Packet Processing) Time.

n: Number of Servers (Routers/Switches).

A, and S can be denoted as M (Markov: an exponential probability) or D (Deterministic: a fixed time between packets arrival) or G (General: arbitrarily distributed arrival rate); our focus will be on M (Markov Arrival Intervals). This would be assuming an exponential distribution (Poisson distribution).

Since n is the number of servers, mainly we will use 1, that's because in a network (the end portion of a network) we have only one router/switch, and a set of computers.

Ergo, the Queuing Theory to be used is M/M/1: Random number of packets arrives in random intervals denoted to as Poisson distribution, being processed by one router/switch, and it takes a random (Poisson distribution) value to process these packets.

Networks

The Network is the core in any telecommunication process; it is the medium that includes the data transfer and all the traffic. The Network Traffic consist of packets, there are many different types of packet, depends on the type of data the packets carry.

Nevertheless, all packets -no matter what type of data they carry- they all share the same set of states; hence, the packets can be categorized as:

- Sent Packets.

- Received Packets.

- Dropped/Rejected Packets.

- And, Corrupted Packets.

Sent Packets

It is any packet has been created on the sender machines, and been dumped on the network, for a specific destination (i.e. with a pre-specified destination IP); this could be as a request, or a reply to a request, or even a control packet.

Successfully receiving a packet or not, does not change the fact that the packet was sent, so, the packet will be counted as sent, with regardless if it was successfully been received or not.

Received Packets

It is any packet has been arrived to a particular machine, from a specific source. Receiving a correct or corrupted packet does not change the fact that the packet has actually been received, so, the packet will be counted as received, with regardless if it was corrupted or not, delayed or not, or even if it was retransmitted.

Dropped/Rejected Packets

It is any packet that has been ignored or not received by a machine or a router; dropping or rejecting a packet could happen on the end side (machine side) if the packet was transferred to a wrong destination, or if it has a wrong order (been already received before) or even if it has an unknown, hence unauthenticated source.

On a router side, Dropping or rejecting a packet could be caused by receiving a packet while the queue is full; hence the router buffer was full. Dropping or rejecting a packet could also happen if the Packets' TTL (Time to Live) has become 0.

Corrupted Packets

A Packet is said to be corrupted if it has affected by an error that caused one or more bit to be changed. This packet will be counted as “Received”, but after it has been encapsulated, the processor can determine whether or not the data is corrupted, and according to that, the machine will request a retransmission for that same packet again from that source from which it came from.

On the other hand, machines themselves could have either one of two states:

- Listening,

- Receiving.

- Or, Sending (Transmitting).

Listening

The machine is said to be listening, when it is waiting for a connection to happen, in this case, it does not send any data or any kind of packets to the network, it just wait for a packet to be received.

Being in the listening state will form the majority of any machines time, and it does not depend on receiving any data or not.

Receiving

Being in a transmitting state means that the machine is currently receiving packets from the network, it does not include the setup time or the waiting time (the wait time will be counted as listening).

Specifically, the transmitting state starts from the moment the machines receives the first bit of a packet until it receives the last bit of that same packet, the time between receiving multiple packets will be counted as part of the listening time.

Sending (Transmitting)

Being in a transmitting state means that the machine is currently sending packets over the network, it does not include the setup time or the waiting time (the wait time will be counted as listening).

Specifically, the transmitting state starts from the moment the machines sends the first bit of a packet until it sends the last bit of that same packet, the time between sending packets will also be counted as listening time.

MATLAB

MATLAB is a production of MathWorks, which is a company founded by Jack Little and Cleve Moler, to help engineers and scientists to perform experiments, and to build programs much faster and easier than they used to do with conventional programming languages such as C or C++.

The many features in MATLAB make it suitable and very easy for programming various kinds of applications and experiments, in Communication, Signals, Control Design, Image Processing, and much more; in addition, MATLAB provides a professional, more advanced features than those offered in any other programming language, starting from the easy-to-use tool box, and ending with the massive functions library.

There are different Versions of MATLAB; the very first version was MATLAB 1.0, released in 1984, and the latest version MATLAB 7.12, released couple of days ago on the 8th of April 2011. Between those versions (1.0 and 7.12) there are a total of 35 versions of MATLAB, some of them have a huge improvement than the previous ones, and some of them are just bug fixers and has a slight improvement.

The version that will be used in this research will be MATLAB 7.8, which was the first version ever to work on a 32-bit and 64-bits Windows (specifically for Windows 7). It was released on the 6th of March, 2009. I will use this version, because I have a 64-bit Laptop, and this version is the most suitable and light version on mobile processor computers.

Since I've never used MATLAB, the majority of my time was spent learning MATLAB, and how to use it, learning about all the available functions and libraries, how to create a simulation and how to get correct results.

2. Implementation Approach

2.1. Aims and Objectives

The main aim of this research is to answer these questions:

- What are Markov Chains?

- Are Markov Chains good for modeling a network? If yes, How?

- Would it be possible to make a simulation for Markov Chains? Using what?

- Learn how to use MATLAB.

Markov Chains -as mentioned before- are a set of random processes, which assume a countable set of variables and their values and changes in the state that occurs within a specific period of time.

To give a clearer idea about Markov Chains, let us take the following example (Fig.1)

In the above Figure, we have two different States, A, and B, suppose we started at state A, the probability of staying at the same state is equal 0.3, and the probability of going to the next state is equal 0.7, if the 2nd probability occurred, and the state was changed to B, the probability of staying there is equal 0.2, and the probability of going back to A is equal 0.8.

In the same example, we call A, and B, States, or a Finite Set of space, denoted to as Ω, the probability of changing the state is dependent on a probability distribution called PAB, the probability of changing the state from A to B, and PBA, is the probability of changing the state from B to A. the probability of staying the same state will be PAA, and PBB. And since PAA+ PAB=1, and PBB, and PBA=1, we can use p, p-1 and q, q-1.

PAA = p and PAB = 1-p(2.1)

PBB = q and PBA = 1-q(2.2)

Now, we have Ω= {A, B}. The probability matrix is

P= PAAPABPBAPBB = 0.30.70.80.2 = p1-p1-qq       (2.3)

Applying that on a network, we can assume that a machine on a network is in one of three states, Listening, Sending or Receiving (L, S, R accordingly). The following diagram shows a sample representation for the network Markov Chains.

As the previous figure shows, the machine spends the majority of its time in the listening state; PL will be used to refer to the probability of being in the listening state, PS for the probability of being in the sending state, and PR for the probability of being in the receiving state. According to that, the probability matrix or the Transition Matrix will be:

P= PLLPLSPLRPSLPSSPSRPRLPRSPRR=0.90.050.050.850.10.050.870.040.09(2.4)

This is true in theory, but when applied to an existing network the values differ unexpectedly, that is because the probabilities of being in a state or switching to another state or even staying in the same state, is not a fixed value, it keeps changing according to the network status, type of traffic, or queuing. This will be discussed and explained in the Simulation Design section.

2.2. Gantt Chart

The following Gantt chart shows the estimated time and schedule to be worked out on this research, the start date will be from the date I approved the project and signed the apdf from, and the end date will be the deadline for submitting it.

Task 1: Sign the Apdf

Task 2: Understanding the Requirements

The Project requirements needs to be fully understood and the expected outcomes should be clearly stated.

Task 3: Markov Chains Background

A comprehensive research should be carried about Markov chains, and their features and properties, and a conclusion about whether or not they are suitable for network modeling.

Task 4: Learning MATLAB

After studding Markov Chains, and finding that MATLAB is the most suitable programming language for network modeling, this task will focus on learning MATLAB, as its part of the works that should be done.

Task 5: Simulation Implementation

This task is supposed to be as a first draft of the simulation, and it includes writing the program in MATLAB, and make sure it works as expected.

Task 6: First Simulation

The first simulation will show the initial results, it is not necessarily to be correct, or what is exactly expected, but it will certainly gives and indicate whether or not the simulation is running properly.

Task 7: Second Simulation

The second simulation must be adequate, efficient, and gives a comprehensive respect of the network modeled using Markov Chains.

Task 8: Analyzing the Results

After getting the results of the first and second simulation runs, these results must be analyzed and discussed, this may include changing the values in the simulation parameters, and try to get the best outcomes.

Task 9, and 10: Writing the report, and Finalizing Stage

This task will be on a continuous ongoing task during the whole project period.

2.3. Implementation

The expected simulation is supposed to represent a network status, using an appropriate probabilities theories, and efficient programming language. Is Markov Chains suitable for network modeling? To answer that question, we must define specifically what the expected outcomes of this simulation are, and what the goal behind it is.

When we talk about networks modeling and simulation, we come across the term queuing and queuing theory.

Andreas Willing describes the queuing theory as “consider a service center and a population of customers, which at some times enter the service center in order to obtain service. It is often the case that the service center can only serve a limited number of customers1. If a new customer arrives and the service is exhausted, he enters a waiting line and waits until the service facility becomes available.”

Willing identified three main elements of this system:

- The Population of the customers.

- The service facility.

- And the waiting line (Queue).

The previous figure shows a service facilities system, that holds multiple servers (facilities), and the customers arrives in a random order, with random rates and intervals, and with a fixed size buffer (queue). Commonly this kind of service run on a FIFO algorithm (First In First Out) or as it is called First Come First Served.

This leads us to talk about types of queues, they are many, and the simplest one is M/M/1.

In the M/M/1 Queue, we have a single server, which needs a random time (exponentially distributed) for serving customers that arrives in a random arrival rate (Poisson), and the customers waiting to be served are supposed to wait in an infinite queue.

In Fig.6, the number in each state represents the number of customers in the system, this includes the ones being served, and so if we have 0 customers, this means the system is empty, if we had 3 customers this means there are two in the queue and one being served by the server. The λ represents the probability of having another customer arrived (according to Poisson), and μ represents the probability of having a customer out of the system, i.e. being served (according to an exponential distribution).

The difference when talk about networks, is that in networks we have multiple of queues following each others, this means that we might have a queue at a router, and after that we might face another router, then a switch or a firewall, this is called an open queue network. And on the same computer we have multiple queues and buffers, for the video card or the printer interface or the mouse/keyboard interrupt vectors, and this is called a closed queue network.

All of this yields to have a network of queues, each with its own size, conditions and probabilities.

Learning MATLAB

After understanding the major concepts of the project, the next step is to find out which programming language to use; and since MATLAB is the best for programming mathematical simulations, I need to learn how to use MATLAB; this phase will be counted as part of the project, since I have never used MATLAB before.

The first thing I needed is to have MATLAB installed on my laptop, and since my brother has already purchased R2009a copy, I will be using it.

The resources that I will use to help me learning MATLAB are mainly online tutorials and eBooks:

  1. MATLAB Student Version, Version 6, Release 12 [3]
  2. SimEvents 3 User's Guide [4]

After installing MATLAB, and trying to make a test run for a model in the SimEvents Demo section, it didn't work on my laptop, I tried to run it on a different machine and it worked fine, so I thought that maybe it has something to do with the face that my laptop has a 64-bit processor and a 64-bit Window 7 Home Premium.

I searched on Google and MathWorks websites, and I found that I need to install couple a 64-bit compiler to be able to build MEX-files on my 64-bit machine, because the default installation that comes with MATLAB R2009a of Visual Studio 2008 Express is only able to build some 32-bit binaries, and will not work with MATLAB, so I had to download the following libraries and programs:

- Microsoft Visual Studio 2008 Express Edition.[5]

- Microsoft Windows SDK for Windows 7 and .NET Framework 4 [6]

- Windows SDK for Windows Server 2008 and .NET Framework 3.5 [7]

After downloading and installing the previous files, I was able to compile and run any model in the SimEvents Demos. But first, I will try to build a small program that simulates Markov Chains just to see how to it would look like. The Markov Chains simulation that I made was based on the equation 2.4 mentioned before on Page 15.

P= PLLPLSPLRPSLPSSPSRPRLPRSPRR=0.90.050.050.850.10.050.870.040.09(2.5)

The first simulation run was based on n=100, where n is the number of periods the simulation will run at.

Fig. 12.b: First Markov Chains Simulation, n=100

The highlighted lines in the previous figure (Fig. 11.b) show the number of times each state has occurred, and the percentage of the overall time the system was in each one of those states.

Sending state is: 5, which is 5.0505% of the time

Listening state is: 90, which is 90.9091% of the time

Receiving state is: 4, which is 4.0404% of the time

The second Simulation was for the same transition matrix (same probabilities) but for n=1000 instead of n=100.

Fig. 13.a: Second Markov Chains Simulation, n=1000

Fig. 13.b: Second Markov Chains Simulation, n=1000

The highlighted lines in the above figure shows the number of times each state has occurred, and the percentage of the overall time the system was in each one of those states.

Sending state is: 42, which is 4.2042% of the time

Listening state is: 914, which is 91.4915% of the time

Receiving state is: 43, which is 4.3043% of the time

The Third simulation will take in consideration that switching between sending and receiving cannot be done directly, ergo PSR, and PRS will be equal to Zero, and the new transition matrix will be:

P= PSSPSLPSRPLSPLLPLRPRSPRLPRR=0.450.550.000.160.730.110.000.550.45(2.6)

Fig. 14.a: Third Markov Chains Simulation, n=100

Fig. 14.b: Third Markov Chains Simulation, n=100

The highlighted lines in the above figure shows the number of times each state has occurred, and the percentage of the overall time the system was in each one of those states.

Sending state is: 20, which is 20.202% of the time

Listening state is: 69, which is 69.697% of the time

Receiving state is: 10, which is 10.101% of the time

As we can notice, the system still spends the majority of the time in the listening state, but now it spends more time using the channel by sending or receiving, this will definitely enhance the network utilization. Being in the sending state was increased from 5% to 20.2%, and being in the receiving state was increased from 4% to 10.1%.

Running the same previous simulation again for n=1000 would even give a better indicator:

3. Modeling and Simulation

3.1. Modeling Preparation

In this phase, we must identify the steps that are going to be followed in order to create the model, and build the simulation for it.

Modeling Markov Chains

Markov Chains modeling is used to represent a real world dynamic model using transitions matrix and mathematical probability equations. For example, if we considered the weather as our field of study, and we have only two different states, Sunny or Cloudy, if we had a sunny day, we have a probability of PSS for having the next day also sunny and the probability of PSC for having a cloudy day.

In such example, the real world dynamical model would be something like this:

And the Markov Chains models for the same example would be:

Ω = {C, S}, Where Ω is the space of available states.

P = PSSPSCPCSPCC   (3.1)

Transforming the representation from a real world dynamic model, into a mathematical equation is they way of modeling Markov Chains; the same way it happened for a simple example (The Weather) it could be also done for the network, and it would give a very good indicator about the network performance. In computer networks, Markov Chains apply on Queues, and it uses the term “Birth and Death”, which represent the “number of customers in the queue waiting to be served”; in networking we use “number of packets in the buffer waiting to be sent” instead of the previous term.  Whenever a the NIC (Network Interface Card) sends a packet through the network, it becomes available to send another one, so following the FIFO (First In First Out), the first packet entered the buffer, will exit and becomes ready to be sent. This will reduce the number on the packets in the buffer (Death), and whenever a new packet arrives to the NIC, if it was busy sending, it will wait in the buffer (Birth).

The probability of having a Death (sending a packet before a new one arrives) is called λ and the probability of having a Birth (a new packet arrives the NIC while it's still sending, so the service or sending rate is longer than the arrival rate) is called μ.

To model Markov Chains and implementing the Birth/Death model, we need first to identify the factors of the study, what are the parameters that this research should focus on?

- Average delay as a function of traffic density.

- Delay Statistics.

- Blocking probability as a function of the traffic loading.

- Throughput and Utilization as a function of traffic loading.

The average delay is normally the average of the multiple types of delays, these delays are:

- Service (Processing) Time.

- Waiting Time in the Queue.

- Sending (Transmission) Time

- Propagation Delay.

The Propagation delays both depends on the network speed (the line bandwidth) and it is relatively small compared with other delays; in addition, the service time depends on the speed of the server, and it is also relatively small, and the Sending delay depends on both the network speed, and the server speed. So, in this research I will focus more on the waiting time (waiting delay), because it is the longest delay between the other three, and it is directly related to the queue, and Markov Chains. And since we are going to assume the M/M/1 System, then we can use the following equations:

N= ρ1-ρ(3.2)

N: average number of messages in the queue

ρ: Utilization

ρ= λμ    (3.3)

λ: arrival rate

μ: service rate

MWT = 1μ-λ - 1μ(3.4)

MWT: mean waiting time in the queue

T= 1μ-λ   (3.5)

T: average waiting time

These will be done in the logbook, and only the final results will be shown here, but in order to start doing the mathematical equations, we need to have a set of data ready, and using this data, we will be able to identify a new term, in order to go on with the calculations, this term will be the Stationary Distribution of Markov Chains.

In general, when the network starts, the initial state of the buffers will be empty, hence they all will be in state π0, which indicates the initial state; after one time unit (we will suppose its 1 millisecond), the initial state of the buffer may change, and become π 1, which means State number one, which in fact represent the number of packets waiting in the buffer, so after one time unite the state will be:

π1 = π0 . P0,1  (3.6)

In words, it means that: the probability of being in state π 1, where 1 means only one packet waiting in the buffer, is equal to the probability of new arrival (P01) multiplied by the probability of being in state π 0 before it happened. In general we can define:

πj = πi . Pij , j = i+1    (3.7)

For fixed values of probabilities, Pij will be always the same no matter what states are included, this means:

πj = πi . Pj  (3.8)

Where ∑i=1n πi = 1      (3.9)

This concludes that the balance equation provide that the summation of the probabilities for the transitions coming in and out of a state i is balanced and equal to 1.

P11 = 1 - ∑i=1n πi , where i ≠ 1

P22 = 1 - ∑i=1n πi , where i ≠ 2

P33 = 1 - ∑i=1n πi , where i ≠ 3

... etc(3.10)

From the previous equations we can come up with the following matrix:

π = π

1 - ∑i=1nP1i, i≠1

P12

P13

...

P1j

(3.11)

P21

1 - ∑i=1nP1i, i≠2

P23

...

P2j

P31

P32

1 - ∑i=1nP1i, i≠3

...

P3j

 

 

 

⋱

 

Pj1

Pj2

Pj3

...

1 - ∑i=1nP1i, i≠j

The previous matrix is called the stationary distributions for Markov Chains matrix, it hold s the values at which it is possible to switch between different states, the difference between this matrix and the transition matrix is that here we define a constant values between each two states, and we multiply the result with the constant π in order to get the final result, that will give us the probability of being in the state πi, where i: integer >0; While the transition matrix gives us the probability of switching between one state to another only.

Multiple codes and models are supposed to be built in order to get the final results; the first model I will start with will be the one that generates the packets. The packets will be generated according to a Poisson distribution, with a mean value of λ, this means that we will get a random number of packets generated per time interval, and each random number will represent the possible number of packets that would arrive at the buffer before it is ready to be sent over the network, and this random number of packets will have a mean, or an average value of λ, it might be bigger or smaller, according to the random number generated. The lowest possible number will be Zero, and the highest possible number would be infinity, but since we are using Poisson distributions that would never happen.

Mathematically, the Poisson distribution equation is:

P(k) =e-λ λkk! ; k=0, 1, 2, ... (3.12)

In MATLAB, there is a built in function called  poissrnd, which is used to generate a Poisson distribution random number. It takes one parameter (λ) and generates the random number.

function [Arrivals_Rate]=arrival()

interval=100;

Arrivals_Rate=zeros(1,interval);

Total_Arrivals=zeros(1,interval);

lambda=2;

for p=1: interval

Arrivals_Rate(p) = poissrnd(lambda);

Total_Arrivals(p)=sum(Arrivals_Rate);

end

figure(1);

stem(Arrivals_Rate);

figure(2);

plot(Total_Arrivals);

The above code will generates a vector called Arrivals_Rate, which will include the possible number of arriving packets at each time interval, this number of packet will vary according to the value of λ which would be = 2. The total run time will be done for 100 times interval and 1000 times intervals. The Total_Arrivals vector will include the total cumulative number of packets arrived at the buffer, it is not the number of packets currently in the system.

As we can notice, using a value of lambda = 2, on interval n=100, we got the above variations of arrival rates per time unit, for example at time n=29, 7 packets arrived at the same time, where on the other hand at time n=30, 0 packets arrived. Again, this is just a random number of packets generated according to Poisson distribution, each time we run that simulation we get a different set of values, and each time we change the value of lambda, we get different results, if lambda was high, we get higher mean values of arrivals, of lambda was low or close to zero, we get a very low or most of times zero arrival packets at each time unit.

In addition, I wrote a code that will generates Poisson probabilities, this will show the probability of having different number of packets arriving the buffer at any given time,

function [P_Arrivals]=test2()

lambda=2;

max_arrivals=10;

P_Arrivals=zeros(1,max_arrivals);

for p=1:max_arrivals

P_Arrivals(p)=((exp(-lambda))*(lambda^p))/factorial(p);

end

figure(1);

plot(P_Arrivals);

Figure 18, shows is the probability distribution for different number of arrivals, where the mean value λ is equal to 2, and the maximum possible arrivals are set to 10, the exact value of each number is:

ans =

0.27070.27070.18040.09020.03610.01200.00340.00090.00020.0000

As we can notice, when lambda was close to 0, we almost didn't get any arrivals, except for some occasions where we received one or a maximum of two packets, while on the other hand, when lambda was equal to 20, the minimum number of arrivals was 7 at n = 86, and the highest number of arrival was 32 at n=95.

In the same simulation we can also get the total number of arrivals, as stated before, this doesn't mean the total number of packets currently in the buffer, it means the total cumulative number of packets arrived the buffer from n=0, until n=100.

The second simulation shows the average number of packets currently in the system, with respect to the system utilization (data flow), and the average delay of the system with respect to the system utilization (data flow).

function []=numofpackets()

Roh=zeros(1,96);

N=zeros(1,96);

D=zeros(1,96);

Roh(p)=Roh(p-1)+0.01;

end;

for p=1:96

N(p)=Roh(p)/(1-Roh(p));

end;

for p=1:96

D(p)=1/(1-Roh(p));

end;

plot(Roh,N,Roh,D);

The first three lines are used to initiate the vectors that will hold the different values of Roh (ρ), N (Average number of packets in the buffer, and D(average packet delay in the buffer).

Section number one of the code, is used to determine the different values of  roh to be used in the simulation, this will divide roh into 100 time intervals, with a step of 0.01 between roh=1 to roh =0.99. Section two will calculate the average number of packets in the buffer, where stated previously in equation (3.2)  N= ρ1-ρ.

And the third section will calculate the average delay time, which would be according to the following equation:

D= 11-ρ(3.13)

Fig. 24: Average packets number and delay, with respect to utilization (data flow)

As the network utilization approaches 1, the network traffic increases, this will raise the number of packets exponentially, and as a result, the average packet delay will increase accordingly, until it reaches almost 1, where it explodes to infinity.

To calculate the network Utilization and throughput, we use the following equations:

Utilization= ArrivalsServiced

ρ= λμ(3.14)

Throughput= ServicedArrivals*8                                  (3.15)

To convert it from kilo bit to kilo bytes per second.

3.2.    Simulation and Results

After building multiple small files, now it's the time to try to put them all together in one single code and run it as a single unit, the simulation run will have the following assumptions:

- The Time interval unit (n) is in Seconds.

- The Arrival Rate Lambda (λ) is between 0 and 100.

- The Arrivals Number is between 0 and 100, with a mean value equal  λ.

- The Serviced Rate Mu (μ) is between 0 and 100.

- The Serviced Number is between floor (μ/2) and 100, with mean value of μ. This assuming that the server (NIC or the Processor) will be able to process at least μ/2 packets per time unit.

- Buffer Size is in MB.

- Average Packet Size is in KB.

The First Simulation run will assume:

- n=1000, λ = μ = 5;

- Buffer Size = 1 MB, and Average Packet Size = 25 KB.

The simulation was run for more than 10 times; these are two of the results:

===================================================================

The Total Packets Arrived: 5100 Packets

The Average number of packets waiting in the queue was: 2 Packets

The Total number of Dropped packets was: 0 Packets

Lambda= 5, Mu= 5, Simulation Time= 0:16:40

===================================================================

The Total Packets Arrived: 4871 Packets

The Average number of packets waiting in the queue was: 1 Packets

The Total number of Dropped packets was: 0 Packets

Lambda= 5, Mu= 5, Simulation Time= 0:16:40

===================================================================

From the previous simulation figures, we can notice the following:

- The number of arrived packets has a maximum of 14 and a minimum of 0, with an obvious mean value alternating around 5. (Fig.25)

- The number of serviced packets has a maximum of 54, and a minimum of 3, with an obvious mean value alternating around 5. (Fig.26)

- The number of packets waiting in the queue at any given time has a maximum of 18 packets, and a minimum of 0, with an average value of one packet. This is because we used the same values for λ and μ. (Fig.27)

- The number of dropped packets, was none, this is also because we used the same value of λ and μ, and also because we have a relatively small packet size, and relatively big buffer size. If the buffer size was smaller, and/or the packet size was bigger, we might have some packets being dropped once in a while. (Fig.28)

- The utilization (Fig.29) shows that the system was mostly busy at the beginning of the and the simulation, where the highest utilization value was 85%, and as the simulation time passed by, the utilization value started to drop and reached the lowest value of 0.46, and then it started to alternate a little bit, before it almost stabilized around 55%.

- Throughput (Fig.30) stabled around 230 kbps.

The Second Simulation run will assume:

- n=1000, λ = 5, μ = 10;

- Buffer Size = 1 MB, and Average Packet Size = 25 KB.

The simulation was run for more than 10 times; these are two of the results:

===================================================================

The Total Packets Arrived: 4871 Packets

The Average number of packets waiting in the queue was: 1 Packets

The Total number of Dropped packets was: 0 Packets

Lambda= 5, Mu= 5, Simulation Time= 0:16:40

===================================================================

The Total Packets Arrived: 4949 Packets

The Average number of packets waiting in the queue was: 0 Packets

The Total number of Dropped packets was: 0 Packets

Lambda= 5, Mu= 5, Simulation Time= 0:16:40

===================================================================

From the previous simulation figures, we can notice the following:

- The number of arrived packets has a maximum of 16 and a minimum of 0, with an obvious mean value alternating around 5. (Fig.31)

- The number of serviced packets has a maximum of 76, and a minimum of 3, with an obvious mean value alternating around 10. (Fig.32)

- The number of packets waiting in the queue at any given time has a maximum of 5 packets, and a minimum of 0, with an average value of 0 packets. This is because we used a higher value of μ than the one used in λ.(Fig.33)

- The number of dropped packets, was none, this is also because we used we used a higher value of μ than the one used in λ, and again, because we have a relatively small packet size, and relatively big buffer size. However, even If the buffer size was smaller, and/or the packet size was bigger, we are unlikely to have any packets being dropped.(Fig.34)

- The utilization (Fig.35) shows that the system was barely busy at any time since the start of the simulation, and it was alternating and almost become stable at 30%.

- Throughput (Fig.36) started with higher values of 520 kbps and then started to drop until it became almost stable around 425 kbps.

The Third Simulation run will assume:

- n=1000, λ = 15, μ = 5;

- Buffer Size = 1 MB, and Average Packet Size = 25 KB.

The simulation was run for more than 10 times; these are two of the results:

===================================================================

The Total Packets Arrived: 15038 Packets

The Average number of packets waiting in the queue was: 41 Packets

The Total number of Dropped packets was: 8415 Packets

Lambda= 5, Mu= 5, Simulation Time= 0:16:40

===================================================================

The Total Packets Arrived: 15024 Packets

The Average number of packets waiting in the queue was: 42 Packets

The Total number of Dropped packets was: 8345 Packets

Lambda= 5, Mu= 5, Simulation Time= 0:16:40

===================================================================

From the previous simulation figures, we can notice the following:

- The number of arrived packets has a maximum of 28 and a minimum of 3, with an obvious mean value alternating around 15. (Fig.37)

- The number of serviced packets has a maximum of 27, and a minimum of 3, with an obvious mean value alternating around 5. (Fig.38)

- The number of packets waiting in the queue at any given time has a maximum of 41, which is the maximum number of packets the buffer can hold. (1 MB = 1024, 1024/25=40.9, which is rounded down to 40 packets) and a minimum of 21, with an average value of 40 packets. This is because we used a very high value λ, and a relatively smaller value of μ.(Fig.39)

- The total number of dropped packets was 8345 packets which is very high, with at any time maximum of 24, and minimum of 0, with an average of 9 Packets being dropped per second. This is also because we used we used a higher value of λ than the one used in μ.(Fig.40)

- The utilization (Fig.41) shows that the system was completely busy since the start of the simulation, and the system became overflow, and it almost become stable around 110%, which means that these parameters are not efficient to be used in the network.

- Throughput (Fig.42) started with very high values of 240 kbps and then started to drop until it became almost stable around 140 kbps.

For The Last Simulation I will assume:

- n=10000, λ = 12, μ = 15;

- Buffer Size = 2 MB, and Average Packet Size = 30 KB.

This simulation took a lot of time, so I was able to do it only 3 times (each time took more than 6 hrs!)

===================================================================

The Total Packets Arrived: 120228 Packets

The Average number of packets waiting in the queue was: 10 Packets

The Total number of Dropped packets was: 126 Packets

Lambda= 5, Mu= 5, Simulation Time= 2:46:40

===================================================================

The Total Packets Arrived: 119913 Packets

The Average number of packets waiting in the queue was: 9 Packets

The Total number of Dropped packets was: 46 Packets

Lambda= 5, Mu= 5, Simulation Time= 2:46:40

===================================================================

From the previous simulation figures, we can notice the following:

- The number of arrived packets has a maximum of 28 and a minimum of 1, with an obvious mean value alternating around 12. (Fig.43)

- The number of serviced packets has a maximum of 50, and a minimum of 3, with an obvious mean value alternating around 15. (Fig.44)

- The number of packets waiting in the queue at any given time has a maximum of 68, which is the maximum number of packets the buffer can hold (2 MB = 2048, 2048/30=68.2, which is rounded down to 68 packets) and a minimum of 0, with an average value of 9 packets. (Fig.45)

- The total number of dropped packets (Fig.46) was 46 packets, with at any time maximum of 10, and minimum of 0, which is somehow acceptable.

- The utilization (Fig.47) shows that the system was heavily used by the start of the simulation where the utilization was almost 100%, and the then it became more stable and closer to a value of 57%

- Throughput (Fig.48) started with a low value of 220 kbps and then started to increase slightly until it became almost stable around 300 kbps.

Since the simulation itself have many loops, and two interrelated loops, it takes a very long time to simulate, especially when using a values of n higher than 2,000, because when we need to calculate the utilization and the throughput, we need to do the calculation each time starting from the first point, this will increase exponentially, so for values of n more than 1,000 it will take about 30 ~ 40 seconds to finish, but for values of n=3,000 it will take more than 27 ~ 30 minutes. And since the final simulation was for a value of n =10,000 it literally took more than 6 hours, yet I was able to do the simulation about 3 times, and I placed two of those three in the report.

So if the reader want to try run the simulation, they are advised to use values of n between 1,000 and 3,000 as maximum, and they should run it on a powerful computer that can do such complex calculations as fast as possible. My laptop has a Quad Core Processor with a clock speed of 2.2 GHZ per core, along with 4 GB of RAM. Any computer with lower specification may take longer time than what mentioned before.

4. Problems Faced

Like any other project, problems always arises to slow down the work flow, but fortunately, it could not stop it, I faced couple of problems since the start of this project, some of them were technical problems, some were more theoretical, and the others were mathematical; in this section I will state those problems, so it would help anyone who want to use my research and enhance it.

4.1.   Problem one

The first problem was to understand the exact relationship between Markov Chains, Networks, Delays and Traffic. I had a good background about Markov Chains and Network performance, but I couldn't create that link between both of them!

After reading many books, I came to a conclusion that Markov Chains are mainly used when we have queuing in the buffer (in the machine or router). So the use of Markov Chains is mainly to estimate the queuing and the average delay for the packets by calculating the probabilities of receiving a certain value of packets, while giving the probabilities of the packets been departed from the system.

A book provided to me by Dr. Boris (“Modeling and Analysis of Telecommunications Networks”, Jeremiah F. Hayes, Thimma V. J. Ganesh Babu, 2004) was a very helpful resource, and most of the work carried in the project was based on ideas, theories, or equations taken from that book. Another very helpful resource was (“Analysis of Computer and Communication Networks”, Fayez Gebali, 2008) where it talks mostly about how to understand the model requirements and it provides some tips in using MATLAB for doing so.

4.2.   Problem Two

The second problem appeared when I was trying to install MATLAB, since I have a 64-bit Windows 7 laptop, I needed a special version that works with Windows 7 64-bit. After checking in MathWorks website, I realized that the best version would be R2009a, since it was firstly designed to work with 64-bit processors.

After Installing the R2009a MATLAB version, I faced another problem when running any simulation; it turned out that I need to install some patches and a 64-bit C++ Compiler.

The reason why I stated this as one of the problems, is that after I searched the web for a solution, I discovered that too many people have the same problem, maybe it is because the 64-bit processors has become more popular than before, and most of the people are using it, so I wanted to state the problem and the solution for it, just in case someone wanted to use my research and they ran into this same problem.

Mainly the solution lies within the following steps:

- Downloading and Installing Microsoft Visual Studio 2008 Express Edition.

http://www.microsoft.com/downloads/details.aspx?displaylang=en&FamilyID=a22341ee-21db-43aa-8431-40be78461ee0

- Downloading and Installing Microsoft Windows SDK 6.1 and .Net Framework 3.5

http://www.microsoft.com/downloads/en/details.aspx?FamilyId=F26B1AA4-741A-433A-9BE5-FA919850BDBF&displaylang=en

5. Conclusion

Markov chains is one of the best way to represent a network model, and it gives a very good indicator for the network performance, however, since it uses a random variables, there is no way to make sure that the readings you get from the simulation is the actual readings you might get when monitoring a real network.

According to the assumed values, and the many simulation runs that I did, I realized that (using the Markov Chains Model) at any given time, according to the random number distribution, we may receive a high number of arrivals, and a very high value of service rate, this means a very low number of packets being served. However, after enhancing the model, I added something to the service rate, where at any given time there must be at least a certain number of packets being served, i.e. at no given time the system will serve 0 packets, unless we had 0 arrivals or there were no packets in the queue.

Another interesting point appeared while doing the simulation was the number of dropped packets, which mainly depends on the average size of the packet, and the buffer size. The simulation was done for a long time (almost 4 hours in reality) and the results were completely irrational! I had a number of packets been dropped which almost the same as the number of packets arrived! I realized that the buffer size I was using was relatively small, where it could hold up to 3 or 4 packets in maximum, so I changed the buffer size, and made it 2 MB, with an average packet size of 10 KB, and did the simulation again, and I received much more satisfactory results.

As a conclusion, I can say that MATLAB is a very good way to represent network models, since it has the ability to do a huge mathematical work, in a relatively small time compared with other programming language, in addition it provides a wide set of mathematical functions that helps creating any mathematical model. And as for the network itself, it turned out that the best way to enhance the network performance with respect to efficiency is to either make a much faster processor in the switches or routers, in a way that it will process the traffic faster, which will reduce the congestions, and as a result increase the network performance. Or, adding a bigger buffer for the current switches and routers, in a way that they will be able to hold much more packets, so they will not be lost, which will save the time of resending them again.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.