Exercises – Protocol theory

A – Point-to-point connections

Exercise 3.1.
Two stations A and B are connected by a bidirectional data transmission system whose ARQ line protocol is characterized by the following parameters:
• fixed size of IUs, whose header is considered negligible, ,
• fixed size of acknowledgments, ,
• negligible processing time of IUs and acknowledgments.
The data transmission between the two stations is carried out by means of a radio system which makes a communication channel available having the following characteristics:
• distance between the two stations, d = 35 km,
• link capacity, C = 34.368 Mbit/s.
The transmission from A to B of a data segment of length is considered. Evaluate the total transfer time of the data segment and the throughput achieved with the stop and wait protocol in the absence of transmission errors.

Exercise 3.4.
Two stations A and B are connected by a bidirectional data transmission system whose ARQ line protocol is characterized by the following parameters:
• fixed size of IUs, whose header is considered negligible, ,
• fixed size of acknowledgments, ,
• negligible processing time of IUs and acknowledgments.
The data transmission between the two stations is carried out by means of a radio system which makes a communication channel available having the following characteristics:
• distance between the two stations, d = 15 km,
• link capacity, C = 155 Mbit/s. A window flow control mechanism is also operating with parameters:
• opening of the transmitter window, ,
• arbitrarily large opening of the receiver window,
• time-out for start of retransmission, .
If the go-back-n protocol is used, evaluate in the absence of transmission errors the total transfer time from A to B of a data segment of length , the throughput and the link usage efficiency achieved.

Since each UI can contain up to \mathrm{byte}, The number of the IUs to be transmitted is given by

   

First of all, the numerical values of the IU transmission and propagation times are determined

   

   

   

so that the time required to receive an acknowledgment is . Given that , it follows that and therefore the window opening throttles the transmission. Considering that after each transmission interruption event due to the window 20 IUs will have been transmitted, we get

   

   

   

Exercise 3.6.
Two terrestrial stations A and B are connected via two simplex radio links characterized as follows: (i) direct connection A-B of length and capacity Mbit/s; (ii) connection B-A consisting of two serial sections connected via a radio reflector R with length of each section and link capacity .
The protocol that controls the transmission of the IUs on this link is of type ARQ, characterized as follows:
• IUs with variable size, which depends on the size of the packet transported, up to a maximum length , of which constitute the header,
• fixed size of acknowledgments, ,
• negligible processing time in stations A and B for IUs and acknowledgments.
The selective repeat protocol is used with a time-out and equal opening of the sender and receiver windows . A data segment of length D = 3355 byte is to be transferred from A to B, requiring that the IUs have maximum length except possibly the last one. Calculate, in the absence of errors on the link, the transfer time of the data segment, the actual data throughput of the link, measured in bit/s, and how much this is worth in percentage with respect to the maximum throughput theoretically achievable on channel A-B ( efficiency).). Also determine the optimal size of the transmitter window which maximizes the throughput of this link.

The basic parameters that determine the data block transfer time must first be calculated. Since each IU can contain up to , the number of the maximum length IUs to be transmitted is given by

   

It is therefore necessary to also transmit a last IU of payload for a total length of . The numerical values of the transmission and propagation times of the IU are then determined, considering the configuration of the two communication sections represented in Figure E3.1:

Figure E3.1 Configuration of transmission links according to Exercise 3.6.

   

   

   

   

   

Therefore, the numerical values and . Since, , the window opening makes the flow of IUs issued by station A discontinuous, as shown in Figure E3.2. In fact, station A must stop its transmission after sending the third IU having sent all the IUs allowed by the opening W_s = 3 of the sender window. Upon arrival of each acknowledgment, the opening of the transmission window “rotates” authorizing the sending of a new IU. The total time required to transfer the data segment is then expressed by

   

Figure E3.2 IU transmission without errors according to Exercise 3.6.

The throughput is computed as

   

The window opening that maximizes the link throughput is easily obtained as

   

   

Exercise 3.11.
Two stations A and B are in communication through a data link on cable with length d = 8 km and capacity C = 40 Mbit/s. The protocol that controls the data transfer on the link is ARQ go-back-n with a fixed length IU byte and acknowledgments of length byte. It is assumed that the IU information flow is unidirectional from station A to station B, with positive or negative acknowledgments sent in the opposite direction. At time t = 0, station A begins the transmission without interruption of 11 IUs, while station B sends 7 acknowledgments, which can be either positive or negative, with transmissions beginning at times t = 100, 160, 280, 340, 400, 460, 520, 580, 640 . IUs are numbered with the smallest possible numbering module . Knowing that the link is subject to errors that can affect only the IUs but not the acknowledgments, identify the IUs and the acknowledgments having numbered the first transmitted IU with number 2 and determine the minimum opening of the sender window compatible with this exchange of IUs.

The data provided make it possible to calculate the transmission times of the IUs and acknowledgments as well as the propagation times along the link, that is

   

   

   

Considering the transmission start times of the different IUs, the exchange of IUs and acknowledgmentss is represented in Figure E3.3a. The sequence of transmissions shows that the third IU, that is IU number 4, does not give rise to a response, while the following one does. It follows that IU number 4 has been lost and the next acknwledgment is a NACK 4, since the next IU number 5 is received correctly but out of sequence. Given the nature of the GBN protocol, which defines a unitary opening of the receiver window , IU number 5 is discarded as only IU number 4 can be accepted. Station A continues in the transmission of new IUs, all discarded in station B, even if correct, as they are out of sequence. Each rejected IU corresponds in station B to the transmission of the positive acknowledgment of the last accepted IU, i.e. ACK 3. Upon receipt of the negative acknowledgment, station A retransmits the requested IU number 4, followed by the transmission of the subsequent IUs, each one is regularly acknowledged. Since station A transmits 4 consecutive IUs, i.e. from number 4 to number 7, awaiting acknowledgment, it follows that , by definition and therefore the IUs are numbered modulo 8, having to assume b = 3. The numbering of the IUs and acknowledgments is shown in Figure E3.3b.

Figure E3.3 Exchange of IUs (a) with the GBN protocol according to Exercise 3.11 and their identification (b).

B – Multipoint networks

Exercise 3.17.
Determine the expression of the maximum throughput of a reservation protocol with all active stations, fixed-length frames with one transmission per cycle and a reservation phase in which the N stations access a single minislot using the same contention mechanism as the slotted ALOHA protocol; It is assumed that a centralized station will acknowledge the reservations successfully received (without collisions) in negligible time on a dedicated return channel.

The maximum throughput of the reservation protocol is achieved when the highest reservation success rate is achieved. This is given by Equation 3.37, that is which implies a number of attempts (cycles) required to be successful in the reservation. It follows that the maximum throughput with all active stations becomes

   

where is the minislot duration normalized to the IU transmission time.

Exercise 3.20.
Determine the minimum extension of a ring network with token transfer for a copper transmission medium with the following characteristics:
• ring capacity, C = 4 Mbit/s,
• number of stations evenly distributed along the ring, N = 4,
• minimum length of the information unit, ,
• station latency,

The total latency of a ring network is given by the expression in which indicates the propagation delay only on the transmission medium along the ring. The condition for the network to operate correctly is that the transmission time of a minimum length IU does not exceed the total ring latency. If this were not true, then a station would receive the first bit of the transmitting IU before it was fully transmitted, creating a collision of signals. Hence the condition

   

directly provides the minimum value of the propagation time on the transmission medium compatible with the problem data. We then derive

   

Therefore, assuming a propagation speed v = 200000 km/s for the transmission medium, the minimum length of the ring is

   

Exercise 3.23.
Generate a graph similar to that of Figure 3.50 for the non-persistent CSMA protocol for the three a values in the figure (a = 1, 0.1, 0.01).

Figure 3.50 Throughput with slotted non-persistent CSMA protocol (Exercise 3.23).

The graph is obtained using the equation

   

which gives rise to Figure E3.4.

Figure E3.4 Throughput with non-persistent CSMA protocol according to Exercise 3.23.

Exercise 3.24.
Determine analytically the value of the maximum throughput and the corresponding value of the offered traffic for the non-persistent CSMA protocol with a = (1, 0.1, 0.01).

As for the ALOHA protocols, the maximum throughput is obtained starting from the expression of the throughput S as a function of the offered traffic G

   

The maximum value of the function is obtained by setting to zero its first derivative, which gives

   

The numerical solution of this equation provides the value of the offered traffic G corresponding to the maximum throughput, as reported in Table E3.1.

Table E3.1 Maximum throughput with non-persistent CSMA protocol according to Exercise 3.24.

Exercise 3.31.
Express the value of the minimum delay required to transfer a single-fragment IU in the CSMA/CA protocol.

The minimum transfer time is obtained with the same reasoning that made it possible to derive the maximum throughput of the protocol as the ratio between the time spent in transmitting user data and the average time taken to complete the transmission (Equation 3.49). The calculation of the minimum delay assumes that the channel is captured at the first contention slot and then

   

In fact, the successful completion of the transmission of the single fragment requires that the station waits for DIFS () before starting the contention, which is assumed to be of zero duration. The station then sends the RTS frame and waits for the CTS response, which generally requires the transmission of two control frames () and two SIFS intervals (). After the fragment transmission time (T) and a propagation time (), the transmission of the acknowledgment takes place which requires a transmission time () and a last propagation time ().

C – Routing protocols

Exercise 3.35.
Determine the routing table of nodes B and F of the six-node and nine-edge network of Figure 3.60 for the first four update steps of the distance vector algorithm, assuming that the distance vectors are transmitted between nodes at the same times and that updating in each node occurs only once per step considering the vectors of all adjacent nodes.

Figure 3.60 Network topology (Exercise 3.35).

The application of the distance vector routing algorithm gives rise to the evolution of the routing table in nodes B and F shown in Figure E3.5

Figure E3.5 Routing table of nodes B and F according to Exercise 3.35.

Exercise 3.38.
Consider a six-node network whose LSPs issued, shown in Figure 3.68, are received in node B in sequence from nodes E, D, A, F, C. Obtain the minimum spanning tree of node B.

Figure 3.68 Link state packet issued by the six network nodes (Exercise 3.38).

Starting from the link state packets that are gradually received, node B determines the minimum spanning tree, as shown in Figure E3.6. The initial network knowledge of node B is determined by its neighbors (Figure E3.6a). The LSP received from node E completes the knowledge in B about the network nodes, updating the current topology (Figure E3.6b). Receiving the LSP from nodes D and A completes the knowledge of the network topology (Figure E3.6c and Figure E3.6d). Subsequent LSPs received from nodes F and C add no further information. The application of Dijkstra’s algorithm to the topology just obtained is shown in Table E3.2 in which, given the same distance from the current tree M of nodes A, F at step 0 and nodes C, E at step 2, the nodes F and C, respectively, have been first selected. From this table, using the information on the predecessor node of each network node, we obtain the minimum spanning tree of node B shown in Figure E3.7.

Figure E3.6 Network topology in node B based on received LSPs according to Exercise 3.38.

Application of Dijkstra’s algorithm for node B according to Exercise 3.38.

Figure E3.7 MST of node B according to Exercise 3.38.

Exercise 3.39.
For the network topology obtained in Exercise 3.38, apply the Dijkstra’s algorithm and obtain the routing table of node B.

The sequence of steps of Dijkstra’s algorithm is shown in Figure E3.8. It is observed that the application of the algorithm causes node B to determine better routes as the current tree aggregates new nodes. In particular, the algorithm determines the best routing to node D only at the last step when node E is also included in the set M.

Figure E3.8 Routing table of node B built with Dijkstra’s algorithm according to Exercise 3.39.

Exercise 3.41.
Consider a network with 9 nodes (A, B, C, D, E, F, G, H, I) and 17 edges whose costs are:
costo | rami
1 | F-G, F-I, G-H
2 | A-B, B-D
3 | B-C, C-D, E-F
4 | A-H, D-E, E-I
5 | D-I
6 | A-G, H-I
7 | D-H, G-I
8 | B-H
Apply the Dijkstra’s algorithm and obtain the minimum spanning tree for node H.

Figure E3.9a shows the assigned network. The application of Dijkstra’s algorithm determines the tree shown with a thick line in Figure E3.9b, where the cost from the root (node H) is shown next to each node reached by the tree.

Figure E3.9 Nine-node network according to Exercise 3.41.

D – Flow and congestion control

Exercise 3.43.
Consider a network with 6 nodes, labelled A, B, C, D, E, F, and 8 edges with lengths 20 km for A-B, 12 km for B-C, 10 km for C-D, 40 km for D-E, 10 km for E-F, 5 km for F-A, 35 km for A-C, 40 km for B-F. All links are made of optical fibre and have a capacity C = 20 Mbit/s. The network nodes behave like ideal store and forward switches: any processing and queuing delay is negligible, and a packet in transit is retransmitted only after having received it entirely. An isarithmic flow control mechanism operates on the network between the access nodes. The entrance into the network of a packet “consumes” a permit in the entry node. The exit from the network of a packet generates in the exit node a new permit which is retransmitted back to the entry node along the same path used by the packet. In the absence of permits, the input node keeps the packets received from the source in a buffer waiting for new permits to be available. It is assumed that:
• the packets entering the network are all of equal length (byte) and have payloads of = 100 byte, and an overhead ;
• the permits are carried by control packets that have length with .
Two virtual circuits are active, the first from node C to node B and the second from node C to node A which are routed along the shortest route. Consider the case in which C receives from the sources of the two virtual circuits the following contiguous sequence of information packets: two for B, three for A, three for B. At time t = 0 node C has received completely from the sources all the packets that must be sent; moreover, N = 4 permits are available in node C at time t = 0. Determine the overall transfer time of the packets from node C to the respective destinations.

The assigned network topology is shown in Figure E3.10. It is necessary to first calculate the transfer times of the information units, that is the information packets and the control packets. Given the distances between nodes, a minimum distance routing causes packets from C to B to follow the direct link, while those from C to A are routed through node B. Considering the capacity of the links and their type, the transmission times and of the information and control packets are easily obtained, as well as the propagation times .

   

   

   

   

Figure E3.11 shows the sequence of transmission and propagation events for the transfer of information and control packets. Note how, despite the number N = 4 of permits initially available, node C can carry out six consecutive transmissions, since two permits are received back before the initial permits are exhausted. This implies that each of the two subsequent packets, addressed to node B, can be transmitted only upon receipt of a permit, thus making the transmission from node C discontinuous. Through Figure E3.11 it is possible to obtain the sequence of time intervals that are not overlapped. The total packet transfer time is therefore given by

   

Figure E3.10 Network topology according to Exercise 3.43.

Figure E3.11 Flow control with isarithmic technique according to Exercise 3.43.

Exercise 3.45.
Consider a periodic VBR source, whose activity for a period of 3 s is characterized as follows:
• source peak rate, ,
• activity and inactivity periods with constant duration, and , with the start of activity at time ,
• fixed size packets issued by the source, .
Obtain the graph of the outgoing flow from a leaky bucket and a token bucket in store and forward (S&F) mode with the following features:
• output rate from the bucket, ,
• permit arrival rate,,
• time of first arrival of the permits, ,
• bucket capacity in the leaky bucket, W = 10 pacchetti,
• bucket capacity in the token bucket, W = 10 permessi.

The profile of traffic generated by the source is shown in Figure E3.12. The maximum network access capacity is and the consistency of each packet determines the transmission time out of the bucket . The flow of packet transmissions outgoing from the leaky bucket and from the token bucket is shown in Figure E3.13, noting that the IU and permit buffers are never saturated.

Figure E3.12 Activity of a VBR source according to Exercise 3.45.

Figure E3.13 Output rate from the leaky bucket (a) and the token bucket (b) according to Exercise 3.45.

Exercise 3.50.
Consider a non-periodic source, whose (constant) packet generation rate is characterized as follows: for , for , for , for , linearly decreasing rate from to for . The source feeds a leaky bucket flow control device with permit interarrival time from t = 0 and memory size (buffer) of the information units W = 300 IUs. Obtain the time diagram representing the output rate from the device fout, the filling level of the memory , as well as the number of lost IUs, assuming that the device does not add overhead.

The time diagram of the input rate to the leaky bucket is shown in Figure E3.14. The permit inter-arrival time determines a (maximum) output rate = 100 IU/s. Then the IUs received in excess in the (2-4) s interval enter the buffer which is then saturated, with the consequence that the IUs received in the (4-5) s interval in excess of are lost, namely = 200 IUs. For the first activity period of the source, therefore, the outgoing flow lasts 3 s beyond the end of source activity as the buffer is emptied. In the second activity period of the source, 100 IUs are received in excess of the frequency f_{out}. The filling level of the buffer in this case is determined as the area included between the curve that specifies the input rate fin and the level $f_{out} = 100. The two curves are shown in Figure E3.15.

Figure E3.14 Source generation rate of IUs according to Exercise 3.50.

Figure E3.15 Output rate from the leaky bucket (a) and buffer filling (b) according to Exercise 3.50.