IERG 3310 Homework Assignment 4
Instructions:
1. Submission Deadline: 23:59, April 14, 2025. Late submissions are subject to score
deductions.
2. Submission format: please submit your homework in SOFTCOPY via BlackBoard
E-learning system. If you write your answers manually, please SCAN them first
and then upload to the BlackBoard system.
Name____________________ Score _________________/100
1. (20 points) A bit stream 10100101 is transmitted using the standard CRC method
described in the textbook. The generator polynomial is 𝑥 3 + 𝑥 2 + 1.
a. (10 points) Show the actual bit string transmitted.
b. (10 points) Suppose the third bit from the left is inverted during transmissions.
Explain how this error is detected at the receiver's end.
Solution:
a. G=1101, Actual bit string transmitted: 10100101001
b.
2. (20 points) Suppose four nodes, A, B, C and D, are competing for access to a
channel using slotted ALOHA. Assume each node has an infinite number of packets
to send. Each node attempts to transmit in each slot with probability p. Answer the
following questions and show the process of your calculation. Express your answer in
the function of p.
What’s the probability that the first success (e.g., some node successfully transmits
without causing a collision) occurs in slot 3? Hint: First derive the probability that
some node succeeds in a slot, and the probability that no node succeeds in a slot.
Solution:
3. (25 points) Consider the figure below. A sender begins sending packetized audio
periodically at t = 1. The first packet arrives at the receiver at t = 8.
a. (14 points) What are the delays (from sender to receiver, ignoring any playout
delays) of packets 2 through 8? Note that each vertical and horizontal line
segment in the figure has a length of 1, 2, or 3 time units.
b. (5 points) If audio playout begins as soon as the first packet arrives at the
receiver at t = 8, which of the first eight packets sent will not arrive in time for
playout?
c. (4 points) If audio playout begins at t = 9, which of the first eight packets sent
will not arrive in time for playout?
d. (2 points) What is the minimum playout delay at the receiver that results in all
of the first eight packets arriving in time for their playout?
Solution:
4.(30 points) Consider the scenario shown in the following figure, in which there are
four wireless nodes, A, B, C, and D. The radio coverage of the four nodes is shown
via the shaded ovals; all nodes share the same frequency. When A transmits, it can
only be heard/received by B; when B transmits, both A and C can hear/receive from
B; when C transmits, both B and D can hear/receive from C; when D transmits, only
C can hear/receive from D. Suppose now that each node has an infinite supply of
messages that it wants to send to each of the other nodes. If a message’s destination is
not an immediate neighbor, then the message must be relayed. For example, if A
wants to send to D, a message from A must first be sent to B, which then sends the
message to C, which then sends the message to D. Time is slotted, with a message
transmission time taking exactly one time slot, e.g., as in slotted Aloha. During a slot,
a node can do one of the following: (i) send a message, (ii) receive a message (if
exactly one message is being sent to it), (iii) remain silent. As always, if a node hears
two or more simultaneous transmissions, a collision occurs and none of the
transmitted messages are received successfully. You can assume here that there are no
bit-level errors, and thus if exactly one message is sent, it will be received correctly
by those within the transmission radius of the sender.
a. (5 points) Suppose now that an omniscient controller (i.e., a controller that knows
the state of every node in the network) can command each node to do whatever it (the
omniscient controller) wishes, i.e., to send a message, to receive a message, or to
remain silent. Given this omniscient controller, what is the maximum rate at which a
data message can be transferred from C to A, given that there are no other messages
between any other source/destination pairs?
b. (5 points) Suppose now that A sends messages to B, and D sends messages to C.
What is the combined maximum rate at which data messages can flow from A to B
and from D to C?
c. (5 points) Suppose now that A sends messages to B, and C sends messages to D.
What is the combined maximum rate at which data messages can flow from A to B
and from C to D?
d. (15 points) Suppose now that the wireless links are replaced by wired links. Repeat
questions (a) through (c) again in this wired scenario.
