PROBLEMS CHAPTER 3

3. The following data fragment occurs halfway through a data stream for which the padding algorithm has been used.
of bytes described in the text: A B ESC C ESC FLAG FLAG D. What is the output after the padding?
3. Once filled, we have AB ESC ESC ESC ESC ESC C FLAG FLAG ESC D.
4. One of his colleagues has pointed out that it is a waste to end each plot with a flag byte and start the
Next with another. A single flag byte could do the job, so a saved byte is a byte gained.
Do you agree?
4. If you could always rely on an endless number of frames, a flag byte might be enough. But what if it runs out
a frame of (with a byte of marks) and there are no new frames for 15 minutes. How will the receiver know that the
is the next byte to update the start of a new frame and not just noise on the line? The protocol is much simpler, with
start and end bytes of markers.
5. A bit string, 0111101111101111110, needs to be transmitted at the data link layer. What is the string?
What is really being transmitted after the bit stuffing?
5. The output is 011110111110011111010.
7. Can you think of any circumstance in which an open-loop protocol might be preferable (for example,
a Hamming code) to the feedback-type protocols analyzed throughout this chapter?
7. If the propagation delay is very long, as in the case of a probe in space or near Mars or Venus, the
Forward error correction is indicated. It is also approached in a military situation in which the receiver does not
wants to reveal its location by broadcasting. If the error rate is low enough, a correction error code
it's good enough, but it can also be simpler. Finally, real-time systems cannot tolerate the
waiting for broadcasts
8. To provide greater reliability than what a single parity bit can offer, a coding scheme of
Error detection uses a parity bit for all even number bits. What is the Hamming distance of this?
code?
8. Making a change to any valid character cannot generate another valid CHARACTER due to the nature of the
parity bits. Making two changes to even bits or two changes to odd bits will yield another valid character, therefore
that the distance is 2.
10. A byte of 8 bits with a binary value of 10101111 will be encoded using even parity Hamming code.
What is the binary value resulting from the encoding?
10. The encoded value is 101001001111.
11. A 12-bit Hamming code, whose hexadecimal value is 0xE4F, arrives at the receiver. What was the hexadecimal value?
Assume that no more than one bit is erroneous.
11. If we number the bits from left to right starting with bit 1, in this example, bit 2 (A parity bit) is
incorrect. The 12-bit value transmitted (after Hamming encoding) was 0xA4F. The original 8-bit data value
0xAF.
12. One way to detect errors is to transmit the data as a block of n rows of k bits per row and add bits for
parity for each row and each column. The bottom right corner is a parity bit that checks its row and its column.
Will this scheme detect all single errors? Double errors? Triple errors?
A single error will cause both horizontal and vertical parity checks to fail. Two errors will also
they are easily detected. If they are in different rows, the row parity catches them. If they are in the same row, the parity of the
The column will take them. Three errors may slip in undetected, for example, if some bits are inverted together.
with its row and column parity bits. Even the corner bit will not catch this
16. Data link protocols almost always place the CRC in a trailer rather than in a header. Why?
What?
16. The CRC is calculated during transmission and is added to the output stream as soon as the last bit is output.
wire. If the CRC was found in the header, it would be necessary to make a pass over the frame to calculate the CRC.
before transmission. For this, it would be necessary for each byte to be handled twice: once for the checksum
And once for the transmission. Using the trailer, cut the work in half.
17. A channel has a bit rate of 4 kbps and a propagation delay of 20 ms. What range of sizes ...
In the plot, the stop and wait provide an efficiency of at least 50%?
Efficiency will be 50% when the time to transmit the frame is equal to the time to transmit and the one-way propagation delay.
At a transmission speed of 4 bits/ms, 160 bits takes 40 ms. For frame sizes above 160 bits,
stop-and-wait is reasonably efficient
23. Suppose that the three-instruction while loop near the end of protocol 6 is removed from the code. Will this affect it?
the correction of the protocol or just its performance? Explain your answer.
23. This would lead to a deadlock, because this is the only place where incoming acknowledgments are processed. Without this
code, the sender would maintain the timeout and make no progress.
24. Suppose that the case for checksum errors were removed from the switch statement of protocol 6.
How will this change affect the operation of the protocol?
24. This would be contrary to the purpose of having NAK, so I would have to resort to the timeouts. Although the
performance would degrade, the correction would not be affected. NAKs are not essential.
26. Imagine that you are writing the data link layer software for a line used to send data.
to you, but not from you. The other end uses HDLC, with a three-bit sequence number and a size of
window of seven frames. You may want to buffer as many out-of-sequence frames as possible.
possible to increase efficiency, but you are not allowed to modify the software on the sending side. Is it possible to have a
receiver window greater than one and still ensure that the protocol will never fail? If so, what is the size?
From the largest window that can be used safely?
26. No. The maximum size of the receive window is 1. Let's assume it were 2. Initially, the sender transmits
frames 0-6. All are received and acknowledged, but the acknowledgment of receipt was lost. The receiver is now ready to
accept 7 and 0. When the retransmission of 0 reaches the receiver, it will be BUFFered and 6 recognized. When it appears at 7,
7 and 0 will be passed to the host, which leads to a protocol failure.
27. Consider the operation of protocol 6 on a 1 Mbps error-free line. The maximum frame size is
1000 bits. New packets are generated at intervals of approximately 1 second. The expiration time of the
The timer is 10 ms. If the special acknowledgment timer were eliminated, it would occur
Unnecessary timer terminations. How many times would the average message be transmitted?
27. Suppose an envoy B a plot that arrives correctly, but there was no fallback traffic. After a while
One would be the waiting time and retransmission. B would realize that the sequence number is incorrect, since the
The sequence number is below FrameExpected. Consequently, it would send a NAK, which carries a number of
recognition. Each frame would be sent exactly twice.
29. Frames of 1000 bits are being sent through a 1 Mbps channel using a geostationary satellite whose
Propagation time from Earth is 270 ms. Reception confirmations always overlap in the
Data frames. The headers are very short. Three-bit sequence numbers are used. What is the utilization?
maximum channel that can be achieved for: (a) Stop and wait?
29. We go to t = 0, meaning the beginning of the transmission. At t = 1 ms, the first frame has been transmitted.
completely. At t = 271 ms, the first frame has arrived completely. At t = 272 ms, the recognition frame
that the first one has been sent in its entirety. At t = 542 ms, the acknowledgement frame has arrived
fully. Therefore, the cycle is 542 ms. A total of k frames are sent in 542 ms, for an efficiency of K / 542.
Por lo tanto (A) k = 1, la eficiencia = 1/542 = 0,18% (B) k = 7, eficiencia = 7/542 = 1,29% (C) k = 4, eficiencia = 4/542 = 0,74
32. A cable 100 km long operates at a data rate T1. The propagation speed of the cable is 2/3 of the
speed of light in a vacuum. How many bits fit in the cable?
32. The propagation speed in the cable is 200,000 km/s, or 200 km/ms, so a 100 km cable
will fill in 500 microseconds. Each T1 frame is 193 bits sent in 125 microseconds. This corresponds to four
frames, or 772 bits in the cable.
35. Given the transition rules AC → B, B → AC, CD → E, and E → CD, draw the described Petri net. Based on this net,
draw the finite state graph reachable from the initial state ACD. What well-known concept do these model?
transition rules?
35 The Petri net and the state graph are as follows: BD AE ACD The C B D E 1 2 3 4 The modeling system is the
mutual exclusion. B and E are critical sections that cannot be active at the same time, that is, the state MUST NOT
It is allowed. Put C represents a traffic light that can be utilized by either A or D, but not so much.
for together
PPP is closely based on HDLC, which uses bit stuffing to prevent accidental flag bytes.
inside the payload causes confusion. Give at least one reason why PPP uses byte stuffing.
PPP was clearly designed to be implemented in software, not in hardware as HDLC almost always is.
With a software application, working entirely with bytes is much simpler than working with bits.
Individuals. In addition, PPP was designed to be used with modems, modems, and to accept and transmit data in units.
of 1 byte, not 1 bit.
Problems CAP4

2. A group of N stations shares a pure ALOHA channel of 56 kbps. The output of each station is a frame of
1000 bits on average every 100 seconds even if the previous one has not been sent (for example, stations can store
in buffer the outgoing frames). What is the maximum value of N?
With pure ALOHA, the usable bandwidth is 0.184 × 56 kbps = 10.3 kbps. Each station requires 10 basic points.
so N = 10,300 / 10 = 1,030 stations.
3. Consider the delay of pure ALOHA compared to slotted ALOHA when the load is low. Which is lower?
Explain your answer.
3. With pure ALOHA, transmission can start immediately. Under low load, collisions are not expected.
likely to succeed the transmission. With slotted ALOHA, which has to wait for the next slot. This introduces
half of a slot time delay.
10,000 airline reservation stations compete for a single slotted ALOHA channel. The station
Average is 18 requests/hour. A slot lasts 125 μsec. What is the approximate total load of the channel?
4. Each terminal makes a request every 200 seconds, for a total load of 50 requests/sec. Therefore T = 50
/ 8000 = 1 / 160
A large population of ALOHA users generates 50 requests/sec including both originals and retransmissions.
El tiempo se divide en ranuras de 40 mseg. (a) ¿Cuál es la oportunidad de éxito en el primer intento? (b) ¿Cuál es la
exact probability of k collisions and then succeeding? (c) What is the expected number of transmission attempts?
necessary?
5. (A) with T = 2 the Poisson law gives a probability of mail -2. (B) (1 - e - T ) k e - T = 0.135 × 0.865 k. (C) The number
expected of transmissions is email T = 7.4.
6. Measurements in a slotted ALOHA channel with an infinite number of users show that 10% of the slots are
What load, G, does the channel have?
overloaded?
6. (a) Starting from the Poisson law again, P 0 = E - T, so T = -ln P 0 = -Ln 0.1 = 2.3. (b) The use of S = Ge - T with T
= 2.3 and email - T = 0.1, S = 0.23. (C) When T > 1 the channel is overloaded, so it is overloaded.
10. Sixteen stations compete for a shared channel that uses the spanning tree protocol. If all the
stations whose addresses are prime numbers will suddenly be ready at the same time, how many bit slots
What is needed to resolve the contention?
10. Stations 2, 3, 5, 7, 11, and 13 wish to send. Eleven slots are needed, with the content of each slot being as follows
manera: ranura 1: 2, 3, 5, 7, 11, 13 ranura 2: 2, 3, 5, 7 ranura 3: 2, 3 Ranura 4: 2 Ranura 5: 3 ranura 6: 5, 7 ranura 7: 5
ranura 8: 7 ranura 9: 11, 13 ranura 10: 11 ranura 11: 13
12. The wireless LANs we studied used protocols like MACA instead of CSMA/CD. Under what conditions
Would it be possible to use CSMA/CD?
12. Radios cannot receive and transmit on the same frequency at the same time, so CSMA/CD cannot be used.
use. If this problem could be solved (for example, by equipping each station with two radios), there is still the
problem of not all stations being within radio range of each other. Only if both problems can be solved
resolver, is CSMA/CD a candidate
13. What common properties do WDMA and GSM channel access protocols have? Refer to GSM in the chapter
2.
13. Both use a combination of FDM and TDM. In both cases frequency dedicated (i.e., wavelength)
bands are available, and in both cases these bands are notched for TDM
14. Six stations, from A to F, communicate using the MACA protocol. Is it possible for two transmissions to have
place simultaneously? Explain your answer.
Yes. Imagine that you are in a straight line and that each station can only reach its nearest neighbors. Then A
You can send to B, while E is the shipment to F.
16. What is the baud rate of standard 10 Mbps Ethernet?
16. Ethernet uses Manchester encoding, which means it has two signal periods for each bit sent.
The standard Ethernet data rate is 10 Mbps, so the transmission speed is double, or 20.
megabaudios.
17. Outline the Manchester encoding for the bit stream: 0001110101.
17. The signal is a square wave with two values, high (H) y low (L). The sea swallow is
LHLHLHHLHLHLLHHLLHHL.
18. Sketch the Manchester differential encoding for the bit stream from the previous problem. Assume that the line is
initially found in the low state.
The pattern of this time is HLHLHLLHHLLHLHHLHLLH
21. Consider the construction of a CSMA/CD network that operates at 1 Gbps over a 1 km long cable without
repeaters. The speed of the signal in the cable is 200,000 km/s. What is the minimum frame size?
For a 1 km cable, the one-way propagation time is 5 microseconds, so 2τ = 10 microseconds. For
to do the CSMA/CD work, it must be impossible to transmit a complete frame in this interval. At 1 Gbps, all the
frames under 10,000 bits can be transmitted completely in less than 10 microseconds, so
The minimum frame is 10,000 bits or 1,250 bytes.
23. Ethernet frames must be at least 64 bytes in length to ensure that the transmitter stays in
line in case a collision occurs at the far end of the cable. Fast Ethernet is the same size
minimum frame of 64 bytes but can receive bits ten times faster. How is it possible to maintain the same
minimum frame size?
23. The maximum length of fast Ethernet cable is 1/10, as long as in Ethernet.
24. Some books state that the maximum size of an Ethernet frame is 1518 bytes instead of 1500. Are they in a
error? Explain your answer.
24. The payload is 1500 bytes, but when the destination address, source address, Type/length, and the fields
The checksum was also counted, the total is actually 1518.
25. The 1000Base-SX specification indicates that the clock must run at 1250 MHz, even though it is assumed to be Gigabit
Ethernet works at 1 Gbps. Does this higher speed provide an additional margin of safety? If not, what
What's happening?
25. Coding is only 80% efficient. It takes 10 bits of data transmitted to represent 8 bits of data.
In one second, 1,250 megabits are transmitted, which means 125 million words of code. Each word
The code represents 8 bits of data, so the actual data rate is indeed 1,000 megabits/second.
26. How many frames per second can Gigabit Ethernet handle? Reflect carefully and take into account everything.
relevant cases. Suggestion: the fact that it is about Gigabit Ethernet is important.
The smallest Ethernet frame is 512 bits, so at 1 Gbps we get 1953125 or almost 2 million frames.
However, this only works when burst framing is operating. Without burst framing, short frames
they fill up to 4096 bits, in which case the maximum number is 244,140. For the largest frame (12,144 bits), not
There can be as many as 82,345 frames per second.
27. Mention two networks that allow packaging frames one after another. Why is this feature important?
27. Gigabit Ethernet has the same with 802.16. Bandwidth efficiency is useful (a preamble, etc.),
but also when there is a lower limit on the frame size
30. An 802.16 network has a channel width of 20 MHz. How many bits/second can be sent to a subscribed station?
30. It depends on how far the subscriber is. If the subscriber is close, QAM-64 is used for 120 Mbps. For distances.
media, QAM-16 is used for 80 Mbps. For distant stations, QPSK is used for 40 Mbps.
31. IEEE 802.16 supports four classes of service. Which is the best class of service for sending uncompressed video?
31. Uncompressed video has a constant bit rate. Each frame has the same number of pixels as the
previous plot. Therefore, it is possible to calculate very precisely how much bandwidth is needed and when.
consequently, constant bit rate service is the best option
Para mejorar la fiabilidad de la transmisión de datos, permitiendo la recuperación de la información perdida o dañada.
errors and retransmission.
32. One reason is the need for real-time quality of service. If an error is discovered, there is no time to
get a broadcast. The show must go on. Bug fixes can be used here. Another reason is that in
very low quality lines (for example, wireless channels), the error rate can be so high that it is practically
All the frames would have to be retransmitted, and the retransmission is probably damaged as well. To avoid this, the
forward error correction is used to increase the fraction of frames that arrive correctly
35. Bluetooth supports two types of links between a master and a slave. What are they and what is each used for?
35. An ACL channel is asynchronous, with frames arriving irregularly as data is produced. A SCO channel is
synchronous, with frames to arrive periodically at a well-defined speed.
36. The beacon frames in the spread spectrum with frequency hopping, a variant of 802.11, contain the time of
Permanence. Do you think that the Bluetooth analog beacon plots also contain time of permanence?
Explain your answer.
36. They do not do it. The dwell time in 802.11 is not standardized, so it has to be announced to the
new stations that arrive. In Bluetooth this is always 625 microseconds. There is no need to announce this.
All Bluetooth devices have this hardwired in the chip. Bluetooth was designed to be cheap, and the fixing of
the hop rate and dwell time leads to a simple chip.
40. A switch designed for Fast Ethernet has a motherboard that can carry 10 Gbps. How many
how many threads/segments can it handle in the worst case?
40. The worst case is an endless stream of 64-byte frames (512 bits). If the back plane can handle 10^9 bps,
The number of frames it can handle is 10 9 / 512. This is 1,953,125 frames/second.