CSC190: Computer Algorithms and Data Structures Assignment 3

\$30.00

Category: You will Instantly receive a download link for .zip solution file upon Payment

Description

5/5 - (2 votes)

Introduction to Data Networks
Transmitting data through the internet (emails, video/voice streaming, etc.) is a complex process. The
internet is essentially a large network composed of intermediate devices that forward transmitted data
originating from a source device to a destination device through links as illustrated in Figure 1. These
intermediate devices include routers and switches that forward data from incoming links to outgoing links
based on their destination.
Figure 1: A Simplified Visualization
2.1 A Transportation of People Analogy
In order to understand how data is transmitted across the internet from a source to a destination, consider
the following analogy. Suppose that 20 people are to be transported from Point A to Point B via cars only.
Everyone is leaving from the same place and intend to arrive at the same place. Cars have fixed space (i.e.
can only seat a maximum of 5 people). Assume that all 20 people manage to fit into 4 cars. These cars then
will use various roads to travel from Point A to Point B. Since the roads are public, these will be shared by
other cars as well. Depending on the time of the day, there will be various degrees of traffic on the roads.
Certain roads such as the highways allow cars to travel at a faster speed than others. The cross point of
roads will be managed by traffic signals. Based on all these factors, the drivers of the four cars may choose
different paths (composed of various roads) to reach the final destination (i.e. Point B). All four cars will
arrive at Point B but possibly at different times depending on the conditions of the roads travelled and speed
limits.
1
2.2 Similarities between Data Network and Transportation
This transportation example has surprisingly many similarities with the process incurred during the transmission of data from a source device to a destination device. Suppose that you would like to send an email
from your computer (source) to your friend (destination) who resides in another country. In the transmission
process, your email is first broken down into smaller entities called packets (analogous to dividing 20 people
into 4 cars). These packets then traverse links (analogous to roads) in order to reach the final destination.
Different links have different speeds/bandwidths (analogous to speed limits on roads). Since links in the
internet are mostly public, your email packets will share the link with other packets from other sources
(roads are shared with other people who are driving from other places). Multiple links intersect at a single
point (i.e. junction at a road intersection). Intermediate devices such as switches or routers decide on where
to forward packets arriving at these junctions. Packets may arrive at different times at a router. When more
than one packet arrives at the router, these are stored in a buffer/queue (i.e. cars waiting at a junction). In
this assignment, the following assumptions are made: data packets are all of the same size, time taken for
a router to forward packets to appropriate links is constant and the queue is infinite in length. Based on
the congestion properties and conditions of the network, routers may forward packets to different links (i.e.
drivers taking different routes). Even though the packets will arrive at the destination, these might arrive
at different times based on the conditions of the paths.
Figure 2: A Simple Representation of a Router Queue
In this assignment, you will model various properties of a queue in a single router when packets arrive into
the queue at a particular rate and depart from the queue at a particular rate. As depicted in Figure 2,
multiple incoming links can converge at the router. Packets arriving through these links are forwarded to
appropriate outgoing links by the router. Service time (i.e. the forwarding of packets to appropriate links) is
assumed to be constant. Intuitively, it is pretty reasonable to postulate that if the arrival rate of packets into
a queue is lower than the service rate, then the queue will be not be congested and the average wait time of
a packet in the queue before being processed will not be excessive. On the other hand, when the arrival rate
of packets into the queue is greater than the service rate, then the queue will get filled up quickly and each
packet in the queue will have to wait for very large periods of time before being served. In this assignment,
you will compute the average waiting times of packets departing a router queue by simulating the router
queue for various packet arrival rates. You will notice that as the arrival rate gets closer to the service rate,
the average waiting times of packets in the queue will increase exponentially and explode. This trend has
been modelled by a well known law called the Little’s Law. The average waiting time E(S) or sojourn time
of a packet in a queue can be related to the arrival rate λ of packets into the queue and service rate µ of the
2
queue which denotes the departure rate of packets from the queue via this equation: E(S) = 1
λ
(
λ
µ +
1
2
(
λ
µ
)
2
1− λ
µ
).
You can use your simulations to verify whether the router queue obeys this law.
2.4 Simulation of a Router Queue
A router queue can have no packets at a time or some packets waiting to be serviced. Packets arrive
at random times. These arrival times depend on the arrival rates of packets. The function double
getRandTime(double arrivalRate) is provided to you in the main.c file. This function returns
the duration (seconds) within which the next packet will arrive into the queue for a particular arrival rate
λ which is passed as an argument to the function. For instance, suppose λ = 0.1 packets/sec, the function
call getRandTime(0.1) may result in 1.344 sec. This means that the next packet will arrive into the
queue within 1.344 sec. Hence, packets can be queued into the router according to the times returned by
getRandTime. Every packet queued into the router will be processed by the router according to the first
come first serve policy. Time taken to serve each packet is assumed to be constant. Suppose the service rate
is µ = 10 packets/sec, then the service time is 1
10 = 0.1 sec. This means that the time required for the
router to process every packet at the front of the queue is 0.1 sec.
In a simulation, certain metrics about the system are measured throughout the simulation period. We
are particularly interested in the average waiting time of departing packets for various combinations of λ
and µ. The simulation will run for ρ sec. Time progression currTime in a simulation is based on events
occurring in the simulation. Simulation will start at 0 sec. In a router queue, an event will occur if a packet is
scheduled to arrive into or depart from the queue. Suppose that a packet is scheduled to arrive into the queue
at timeForNextArrival. Suppose that the number of packets in the queue is at least one. Then the first
packet in the queue is scheduled to depart from the queue at timeForNextDeparture. The next event