I'm trying to come up with a sample solution for the following homework
question from Patterson and Hennessy's Computer Hardware Software
Interface chapter 8 question 8.28. It's basically a simple binary
exponential backoff simulation. All background info and the question
is below. All is needed is the program. You have a choice of C or
Java (preferrably in C, but if you already have this done in some other
languages such as Java or C++ you can use that as an answer). Compilers
used: gcc/g++ (for C, C++) or javac j2sdk1.4.1. I need this done in about
5 days. Thanks.
(Note: T is exponentially distributed with mean M-- T = t>=0 is M *
e^(-M * t). See clarification at the end below)
An Ethernet is essentially a standard bus with multiple masters (each
computer can be a master) and a distributed arbitration scheme using
collision detection. Most Ethernets are implemented using coaxial
cable as the medium. When a particular node wants to use the bus, it
first checks to see whether some other node is using the bus; if not,
it places a carrier signal on the bus, and then proceeds to transmit.
A complication can arise because the control is distributed and the
devices may be physically far apart. Ass a result, two nodes can both
check the Ethernet, find it idle, and begin transmitting at once; this
is called a collision. A node detects collisions by listening to the
network when transmitting to see whether a collision has occurred. A
collision is detected when the node finds that what it hears on the
Ethernet differs from what it transmitted. When collisions occur, both
nodes stop transmitting and delay a random time interval before trying
to resume using the network-just as two polit
8.28: Write a program that simulates an Ethernet. Assume the following
network system characteristics:
- A transmission bandwidth of 10 Mbits/sec
- A latency for signal to travel the entire length of the network and
return to its origin in 15us. This is also the time required to
detect a collision. Make the following assumptions about the 100
hosts on the network:
* The packet size is 1000 bytes
* Each host tries to send a packet after T seconds of computation,
where T is exponentially distributed with mean M. note that the host
begins its T seconds of computation only after successfully transmitting
a packet
* If a collision is detected, the host waits a random amount of time chosen
from an exponential distribution with a mean of 60us.
Simulate and plot the sustained bandwidth of the network compared to
the mean time between transmission attempts (M). Also, plot the
average wait time between trying to initiate a transmission and
succeeding in initiating it (compared to M).
Ethernets actually use an exponential back-off algorithm that increases
the mean of the back-off time after successive collisions. Assume that
the mean of the distribution from which the host chooses how much to
delay is doubled on successive collisions. How well does this work?
Is the bandwidth higher than when a single distribution is used? Can
the initial mean be lower?
CLARIFICATIONS
==================================
1. Global variables/constants to use in your program:
H = Number of hosts (you will simulate for 100 hosts). M =
Mean of the exponentially distributed computation time
in between packet transmissions. W = Mean of the
exponentially distributed time that a host
waits on detecting a collision before attempting
retransmission (its default value is 60 micro secs.). C =
Collision detection time = signal rountrip time = 15 micro secs.
S = Time taken for the rest of the message to reach destination
once the first bit has reached destination
= (1000 * 8)/10 = 800 micro secs.
L = Total message transmission latency
= C + S = 15 + 800 = 815 micro secs.
Q = Total wait time for all messages for all hosts so far. Wait
time
is the "time between trying to initiate a transmission and
succeeding in initiating it." Q is initialized to 0. P =
Total number of messages successfully transmitted so far.
P is initialized to 0.
2. Suppose a host h1 initiates transmission at time t1. The first bit
of the message will return to the host h1 at time t2 = t1 + C. The
last bit of the message will return to h1 at time t3 = t1 + C + S =
t1 + L. Hosts other than h1 will be aware of the Ethernet being
used by h1 only in the time interval [t2, t3] (includes all time t
such that t2 <= t <= t3). Therefore, hosts other than h1 that are
scheduled to transmit in the time interval [t2, t3] will have to
wait till t3+1 before transmitting (if there are multiple such
hosts waiting, they will cause a collision later at time t3+1 when
they all try to transmit simultaneously). However, if there are
hosts other than h1 that are scheduled to transmit in the time
interval [t1, t2-1], they will not be aware of the transmission by
h1 and will proceed with their own transmissions, thus causing a
collision -- note that the collision will be caused by the first
such hosts that try to transmit, the others may cause their own
collisions. For example, suppose h2 and h3 are scheduled to
transmit at the same time in the time interval [t1, t2-1], and h4
and h5 are also scheduled to transmit simultaneously in [t1, t2-1],
but after h2 and h3. Then, in this case, the collision initially
involves h1, h2, and h3 and occurs at the time h2 and h3 initiate
transmission -- at the time of this collision, h1, h2, and h3 will
each wait a random amount of time drawn from an exponential
distribution with mean W (you will need to generate three random
variables in this example). Assume that just after the collision,
there are no signals from the failed transmissions by h1, h2, and
h3 on the network. Consequently, on finding the network free at
their scheduled time for message transmission, h4 and h5 will
initiate transmission simultaneously and their messages will
collide.
3. For each host, have the following variables or compute/determine
the following:
- The next time that it is scheduled to transmit or retransmit
a message. - The number of attempts that the next transmission
represents
-- if this message transmission has not encountered any
collisions, it is the first attempt, otherwise, it is the second,
third, or later attempt depending upon the number of collisions
encountered by this message.
4. Let us say you store the next message transmission times computed
for all the hosts in an array of structures N[], where each array
element structure has three fields: (a) the host number, (b) the
next message transmission time, and (c) the number of attempts for
this next message transmission. Let us also assume that N[] is
sorted at all times in nondecreasing order by the next message
transmission time.
5. The overall procedure for the simulation is as follows:
- At time 0 (beginning of the simulation), determine for all hosts
their first scheduled message transmission time from an
exponentially distributed random variable with mean M and store
these in N[] along with the host numbers and transmission
attempts (which for the first message transmission would be 1) --
note that you will need to generate as many random variables as
the number of hosts.
- Sort N[] in order of nondecreasing next message transmission
times.
- Pick the host h1 with the earliest scheduled next transmission
time
from N[] and check to see if that host will encounter any
collisions by scanning the array N[] in nondecreasing order of
scheduled transmission times and applying the logic elucidated in
item 2 above. As also explained in item 2 above, the collision is
caused by only the set of hosts that first try to transmit
simultaneously within a time interval C; other hosts that are
scheduled to transmit within interval C, but after the above set
of "first" hosts are not yet the cause of collision, and
shouldn't be considered at the present -- see item 2 above.
- If there was a collision, all hosts involved in the collision
will wait a random amount of time drawn from an exponential
distribution with mean W -- note that you will need to generate
as many random numbers as the number of hosts involved in the
collision. For each host involved in the collision, determine its
next scheduled transmission time by adding the random wait time
generated for it to the time of the collision and also increment
the number of transmission attempts for the host. Since the
message transmission times of some hosts will have changed, you
will need to re-sort the array N[].
- If instead, there was no collision, the message would be
successfully transmitted. Therefore, the next message
transmission time of the transmitting host h1 will be incremented
by L (message latency) + T (an exponentially distributed random
variable with mean M) and its number of attempts will be set to
1.
If there are hosts other than h1 that are scheduled to transmit
during [t2, t3] (i.e., from C to L amount of time after h1
initiated transmission -- see item 2 above), the next message
transmission times of these hosts will be set to t3 + 1. That is,
these hosts will have to "wait" to initiate message
transmission. Therefore, at this time, you should update Q.
Since the message transmission times of some hosts will have
changed, you will need to re-sort the array N[].
- Again repeat the above by picking the host with the earliest
scheduled next message transmission time.
- Note that you will need additional variables for each host in
order to properly update the total wait time Q. You will also
need to increment P with each successful message transmission.
6. Simulate the Ethernet until at least 1,000 messages have been
successfully transmitted. The sustained bandwidth is the combined
size of all messages successfully transmitted (= P * 1000 bytes)
divided by the time interval between the initiation of the first
message transmission (whether successful or not) and the completion
of the last message transmission.
7. From Q, you can compute the average wait time over all actual
message transmission initiations -- note that initiation of a
message transmission does not mean that the message will be
successfully transmitted.
8. When you need to plot some measure (such as the sustained bandwidth
or average wait time) versus M, perform simulations for M values
(in micro secs.) of 8000, 16000, 32000, 64000, 81500, 128000,
256000, 512000, 1024000, 2048000 to obtain the requisite points.
If you find that the smaller values of M (8000, 16000, etc.) cause
too many collisions to be able to transmit 1000 messages
successfully, you don't have to plot for those values of M, but you
should state the fact that for values of M = (give values from the
above list) successful transmissions of 1000 messages was not
possible and/or too time consuming.
9. Note that instead of storing the next transmission times of hosts
in a sorted array N[] and sorting the array N[] whenever any
transmission times change, it will be more efficient to store the
next transmission times in a balanced heap, such as a red-black
tree data structure -- refer to a Data Structures and Algorithms
book for this. However, since only a few of the transmission times
will change at a time, a re-sort of the array to correct the
positions of these changed elements should not prove all that
inefficient. Either way, the procedure is correct.
10. For generating exponentially distributed random variables in a C
program, do the following:
- At the beginning of your file, include the lines:
#include
double drand48();
- Then you can generate an exponentially distributed random
variable t with mean M as:
t = -M * log(1 - drand48());
- Note that the base of the "log" in the above expression is "e."
- Each time you execute the above statement, you get one such
random variable.
- For your information, the function drand48() is a C
library function that generates double-precision
floating-point values uniformly distributed over the interval
[0.0, 1.0), i.e., including 0.0, but excluding 1.0. |
