Unit-1 Computer Network electrnics .ppt

electronics engineering , placement,computer network

1. Computer Network
(6EC4-02)
VI-Sem(ECE)
1
Dr. Parul Tyagi(Asso. Prof.) & Ms. Deepmala(Asst. Prof.)
Electronics and Communication Engg.
JECRC. Jaipur (Raj), India
Email:- [email protected] , [email protected]

2. Vision of JECRC Vision of JECRC
To become a renowned center of outcome based learning, and work towards
academic, professional, cultural and social enrichment of the lives of individuals
and communities.
Mission of JECRCMission of JECRC
Focus on evaluation of learning outcomes and motivate students to inculcate
research aptitude by project based learning.
Identify, based on informed perception of Indian, regional and global needs,
areas of focus and provide platform to gain knowledge and solutions.
Offer opportunities for interaction between academia and industry.
Develop human potential to its fullest extent so that intellectually capable and
imaginatively gifted leaders can emerge in a range of professions.

3. Vision of the DepartmentVision of the Department
To contribute to the society through excellence in scientific and technical
education, teaching and research aptitude in Electronics and Communication
Engineering to meet the needs of Global Industry.
Mission of the DepartmentMission of the Department
M1: To equip the students with strong foundation of basic sciences and
domain knowledge of ECE, so that they are able to creatively their
knowledge to the solution of problems arising in their career path.
M2: To induce the habit of lifelong learning to continuously enhance overall
performance.
M3: Students are able to communicate their ideas clearly and concisely so
that they can work in team as well as an individual.
M4: To make the students responsive towards the ethical, social,
environmental and in economic context for the society.

4. Course OutcomesCourse Outcomes

Upon successful completion of this course the students will have
developed following skills/abilities:
CO1: Understand and describe the Queuing Theory.
CO2: Describe the layered protocol model, analyses and evaluate
a number of data link, network, and transport layer protocols.
CO3: Analyses and evaluate various computer network protocols
from standards documents and other primary materials found
through research.
CO4: Design networks and services for homes, data centres,
IoT/IoE, LANs and WANs.

5. Disclaimer
The contents used in this presentation are taken from
the text books mentioned in the references. I do not
hold any copyrights for the contents. It has been
prepared to use in the class lectures, not for
commercial purpose.

6. UNIT-1UNIT-1

8. INTRODUCTION TO
QUEUING THEORY

9. Content
• Introduction to queueing theory
• History
• Elements of Queuing System
• A Commonly Seen Queuing Model
• Stochastic process
• Markov process
• Markov chain
• Poisson process
• Birth death process
• Application

10. Introduction of Queueing theory
• Queueing theory is the mathematical study of
waiting lines, or queues.
• In queueing theory a model is constructed so that
queue lengths and waiting times can be predicted.
• Queueing theory is generally considered a branch of
operations research because the results are often used
when making business decisions about the resources
needed to provide a service.

11. A queue is a waiting line of customers requiring service
from one server to another and it is a mathematical study
of waiting lines or queues.
It is extremely useful in predicting and evaluating the
system performance.
There are some applications of queuing like Traffic
control , Health service , Ticket sales etc.
1

12. DEFINITION
• A queue is said to occur when the rate at which the
demand arises exceeds the rate at which service is being
provided.
• It is the quantitative technique which consists of
constructing mathematical models for various types of
queuing systems.
• Mathematical models are constructed so that queue
lengths and waiting times can be predicted which helps in
balancing the cost of service and the cost associated with
customers waiting for service

13. HISTORY
• Queueing theory’s history goes back nearly 105
years.
• It is originated by A. K. Erlang in 1909, in Danish
when he is at his work place.
• Agner Krarup Erlang, a Danish engineer who worked
for the Copenhagen
Telephone Exchange, published the first paper on
what would now be called queueing theory in 1909.
• He modeled the number of telephone calls arriving at
an exchange by a Poisson process.

14. HISTORY
• Johannsen’s “Waiting Times and Number of
Calls” seems to be the first paper on the subject.
• But the method used in this paper was not
mathematically exact and therefore, from the point of
view of exact treatment, the paper that has historic
importance is A. K. Erlang’s, “The Theory of
Probabilities and Telephone Conversations”
• In this paper he lays the foundation for the place of
Poisson (and hence, exponential) distribution in
queueing theory.

15. • His most important work, Solutions of Some Problems
in the Theory of Probabilities of Significance in
Automatic Telephone Exchanges , was published in
1917, which contained formulas for loss and waiting
probabilities which are now known as Erlang’s loss
formula (or Erlang B-formula) and delay formula (or
Erlang C-formula), respectively.

16. Elements of Queuing System

17. 1. Arrival Process
•Arrivals can be measured as the arrival rate or the
interarrival time (time between arrivals).
• These quantities may be deterministic or stochastic
(given by a probability distribution).
• Arrivals may also come in batches of multiple
customers, which is called batch or bulk arrivals.
• The batch size may be either deterministic or
stochastic.

18. 2.Customer’s Behaviour
• Balking: If a customer enters a system and decides not
to enter the queue since it is too long is called Balking.
• Reneging: If a customer enters the queue but after
sometimes loses patience and leaves it is called Reneging.
• Jockeying: When there are 2 or more parallel queues
and the customers move from one queue to another to
change his position is called Jockeying.

19. 3. Service Process
• Service Process determines the customer service times
in the system.
• As with arrival patterns, service patterns may be
deterministic or stochastic. There may also be batched
services.
• The service rate may be state-dependent. (This is the
analogue of impatience with arrivals.)


Note that there is an important difference
between
arrivals and services. Services do not occur when
the queue is empty.

20. 4. Number of Servers

22. 5. Queue Discipline
• FIFO- First in First out
Or FCFS- First Come First Serve
• LIFO-Last in First out
• SIRO- Service in Random order
• Priority based

23. FIFO- First in First out

24. LIFO-Last in First out

25. SIRO
“Service In Random Order”
• Lottery system

26. Priority based

27. 6.System capacity
• The capacity of a system can be finite or infinite.
There are many queuing systems whose capacity is
finite. In such cases problem of balking arises. It is
known as forced balking. In forced balking customer
needs the service but due to the problem of limited
capacity of the system the customer leaves the system.

28. Queuing examples

29. A Commonly Seen Queuing Model
• Service times as well as inter arrival times are
assumed independent and identically distributed
– If not otherwise specified
• Commonly used notation principle: A/B/C
– A = The inter arrival time distribution
– B = The service time distribution
– C = The number of parallel servers
• Commonly used distributions
– M = Markovian (exponential) - Memory less
– D = Deterministic distribution
– G = General distribution
• Example: M/M/1
– Queuing system with exponentially distributed
service and inter-arrival times and 1 server

31. Examples of Different Queuing
Systems

33. Stochastic process
Definition : A stochastic process is family of time
indexed random variable where t belongs to index set .
Formal notation , where I is an index set that is subset of
R.
Examples :
• No. of telephone calls are received at a switchboard.
Suppose that is the r.v. which represents the number of
incoming calls in an interval (0,t) of duration t units.
• Outcomes of X(t) are called states .

34. Stochastic process is classified in four
categories on the basis of state space and
time space
• Discrete time , Discrete state space
• Discrete time , Continuous state space
• Continuous time , Discrete state space
• Continuous time, Continuous state space

35. EXAMPLES
• Discrete time, Discrete state space : number of
accidents at 9 pm, 10 pm, 11 pm etc.
• Continuous –time ,Discrete state space : Number of
accidents on a highway at an interval of time say 9 pm to
10 pm.
• Discrete time ,continuous state space :age of people
in a city at a particular year say 2001, 2002, 2003 etc.
• Continuous time , Continuous state space :age of
people from March 2013 to march 2014.

36. MARKOV PROCESS

37. Markov chain :

38. Example of markov chain

39. The Poisson Process
A stochastic process {N(t), t>0} with discrete state
space and continuous time is called a poisson
process if it satisfies the following postulates:
1. Independence
2. Homogeneity in time
3. Regularity

40. Postulates for Poisson Process
• Independence:
N( t+h)-N(t), the number of occurrence in the interval
(t,t+h) is independent of the number of occurrences prior
to that interval.
• Homogeneity in time:
pn(t) depends only on length ‘t’ of the interval and is
independent of where this interval is situated i.e. pn(t)
gives the probability of the number of occurrences in the
interval (t1 , t+t1 ) (which is of length ‘t’) for every t1 .

42. Pure Birth Processes
• Pure birth process is originated from Poisson process
in which the rate of birth depends on number of persons.

43. Birth-and-Death Process

44. Note: The foundation of many of the
most commonly used queuing models

Birth – equivalent to the arrival of a
customer

Death – equivalent to the
departure of a served customer

45. A Birth-and-Death Process Rate
Diagram

46. Application of Queuing Theory
• Telecommunication.
• Traffic control.
• Determine the sequence of computer
operations.
• Predicting computer performance.
• Health service ( e.g. Control of hospital
bed assignments).
• Airport traffic, airline ticket sales.
• Layout of manufacturing systems.

47. 1. Arrival Process: If the students arrive at times t
1,t
2,...,t
j
the random variables τ
j = t
j – t
j-1 are called the
interarrival times. It is generally assumed that τ
j form a
sequence of Independent and Identically Distributed
random variables.
2
2. Service Time Distribution: We also need to know the
time each student spends at the terminal. This is called
the service time. It is common to assume that the
service times are random variables, which are IID.

48. 3. Number of Servers: The terminal room may have one or
more terminals, all are considered part of the same queuing
system since they are all identical, and any terminal may be
assigned to any student.
If all the servers are not identical, they are usually divided
into groups of identical servers with separate queues for each
group.
3
4. System Capacity: The maximum number of students
who can stay may be limited due to space availability
and also to avoid long waiting times. This number is
called the system capacity.

49. 5.Population Size: The total number of potential students
who can ever come to the computer centre is the
population size.
6.Service Discipline: The order in which the students are
served is called the service discipline. The most common
discipline is First Come First Served (FCFS). Other
possibilities are Last Come First Served (LCFS) and Last
Come First Served with Preempt and Resume (LCFS-
PR).
4

50. There are somekey variables used in queueing analysis
are as follow:
τ =interarrivaltime,thetime
between twosuccessive arrivals.
λ = mean arrival rate.
s = service time per job.
m = number of servers.
μ= mean service rate per server.
n= numberofjobsinthe
system. Thisisalsocalled queue
length.
5

51. n
q = number of jobs waiting to receive service.
n
s = number of jobs receiving service.
r = response time.
w = waiting time.
There are a number of relationships among these variables
that apply to G/G/m queues.
1. Stability Condition: If the number of jobs in a system
grows continuously and becomes infinite, the system is
said to be unstable. For stability the mean arrival rate
should be less than the mean service rate is
λ > mμ
6

52. 2. Number in System versus Number in Queue: The
number of jobs in the system is always equal to the sum
of the number in the queue and the number receiving
service:
7
n=n
q + n
s
n, n
q, and n
s, are random variables.
The mean number of jobs in the system is
equal to the sum of the mean number in of
job in the queue and the mean number
receiving service.
E[n]=E[n
q] + E[n
s]
If the service rate of each server is
independent of the number in the queue, we
have
Cov(n
q,n
s) = 0 and Var[n] = Var[n
q] +
Var[n
s]

53. 3. Number versus Time: If jobs are not lost due to
insufficient buffers, the mean number of jobs in a
system is related to its mean response time as follows:
8
Meannumberofjobsinsystem=arrivalrate×
mean response time.
Meannumberofjobsinqueue=arrivalrate×
mean waiting time.

54. 4.TimeinSystemversusTimeinQueue:Thetime
9
spentby a job in a queueing system.
r = w + s
r, w, and s are random variables
The mean response time is equal to the sum of the mean
waiting time and the mean service time.
E[r] = E[w] + E[s]
If the service rate is independent of the number of jobs in
the queue, we have
Cov(w,s) = 0 and Var[r] = Var[w] + Var[s]

55. Little’s law, which was first proven by Little in 1961.
The most commonly used theorems in queuing theory is
Little’s law, which allows us to relate the mean number of
jobs in any system with the mean time spent in the system as
follows:
Mean number in the system = arrival rate × mean response
time
The law applies as long as the number of jobs entering the
system is equal to completing service, so that no new jobs
are created in the system and no jobs are lost inside the
system.
10

56. The law can be applied to the part of the system
consisting of the waiting and serving positions because
once a job finds a waiting position , it is not lost.
11

57. Queuing theory is major for computer system
performance and also in our daily life. It can be used to
help reduce waiting times. It helps in determining the
time that the jobs spend in various queues in the
system.
18