CS计算机代考程序代写 CEG3185 Winter 2021 Problems solving Tutorial 3

CEG3185 Winter 2021 Problems solving Tutorial 3
Problem 1
CEG3185-Winter 2021 PROBLEMS SOLVING TUTORIAL 3
Consider building a CSMA/CD network running at 5 Mbps over 1-km cable. Repeaters have been inserted to “boost” the signal energy, ensuring that even the farthest away stations can communicate. The signal speed in the cable is 200,000 km/sec. What is the minimum frame size?
Answer
The criterion for having CSMA/CD functioning according to its principle (sense energy, detect collision) is to make sure that even the furthest apart stations on the bus can detect collision if they are the only ones active on the bus (in which case themselves transmit the colliding packets and there isn’t other station in-between to detect the signal and declare the collision). This requires that i frame duration is at least equal to twice the propagation delay.
Repeaters are acting as pure signal amplifiers, thus, the do not introduce any worth considering delay.
The propagation delay between two stations located at the endpoints of the bus is
𝜏 􏰣 1𝐾𝑚 􏰣 5∗10􏱏􏰯𝑠𝑒𝑐 􏰣 5𝜇𝑠𝑒𝑐 200,000 𝐾𝑚/𝑠𝑒𝑐
The frame duration should be 10 sec.
The number of bits corresponding to this time duration for a 10 Mbps link equal to N=5 Mbps * 10 sec= 50 bits. Thus, the minimum frame size equals 50 bits.
1

CEG3185 Winter 2021 Problems solving Tutorial 3
Problem 2
Assume a small communication network, consisting of two user stations and a base station (BS). The users are recording and transmitting data collected by sensors and are transmitting the data frames using frequency band BWu (uplink). BS only collects data and acknowledges them. It uses band BWBS (downlink) for transmissions. An Aloha protocol is used to access the medium by the BS and users. The users generate traffic following Poisson distribution, with frame generation rate u. The time duration of data frames is TF whereas the duration of acknowledgements is is TAck. Determine the probability that the frame generated by a user will be lost.
Answer
Since BS transmits at a different band from the one used by the users and the channel is assumed perfect, no losses of data frames or acknowledgements sent to the users will occur. Because of the same reason, data sent a user will not be damaged because of channel induced errors, thus the only source of loss of a data frame is possible collision with a frame transmitted by the other user.
Assume that User A transmits. Assume User A’s frame reaches the BS at time “t”. The window of vulnerability is 2* TF. If a frame generated by User B reaches the BS within the {t-TF, t+TF} interval, collision will occur. Thus, the window of vulnerability is 2*TF.
For Poisson process, the provability the interarrival time between two consecutive frames is large than  equals:
P(t )  e
For =2*TF we and  = u we get:
P P(t2T )eu2TF CF
With Pc been the probability of frame loss due to collision.
Problem 3
For p-persistent CSMA, consider the following situation. Station is ready to transmit and is listening to the medium. No other station is ready to transmit, and there will not be other transmission for an indefinite period. If the time unit used in the protocol T show that the average number of iterations of step 1 of the protocol is 1/p and that therefore the average time the station
will have to wait after the current transmission is 𝑇 􏱐􏱑􏰡 􏱒 1􏱓.
Answer
In the solution, the following equality is used:
2

CEG3185 Winter 2021 Problems solving Tutorial 3
􏱖1 􏱔𝑖∗𝑋􏱕􏱏􏰡 􏰣􏰧1􏱒𝑋􏰨􏰠 􏱕􏰭􏰡
􏱖
E􏱗number of iterations􏱘 􏰣 􏱔􏰧𝑖 ∗ 𝑃𝑟𝑜𝑏𝑎𝑏𝑖𝑙𝑖𝑡𝑦􏱗𝑒𝑥𝑎𝑐𝑡𝑙𝑦 𝑖 𝑖𝑡𝑒𝑟𝑎𝑡𝑖𝑜𝑛𝑠 𝑜𝑓 𝑠𝑡𝑒𝑝 1􏱘􏰨
……….
……….
􏱕􏰭􏰢 Pr􏱗exactly1iterationofstep1􏱘 􏰣 p
Pr 􏱗exactly 2 iterations of step 1􏱘 􏰣 􏰧1 􏱒 p􏰨 ∗ p Pr 􏱗exactly 𝑖 iterations of step 1􏱘 􏰣 􏰧1 􏱒 p􏰨􏰧􏱕􏱏􏰡􏰨 ∗ p
􏱖
E􏱗number of iterations􏱘 􏰣 􏱔􏰧𝑖 ∗ Pr 􏱗exactly 𝑖 iterations of step 1􏱘􏰨 􏱖 􏱕􏰭􏰡
􏰣 p ∗ 􏱔􏱙𝑖 ∗ 􏰧1 􏱒 p􏰨􏰧􏱕􏱏􏰡􏰨􏱚 􏰣 p 􏰣 1 􏱕􏰭􏰡 􏱙1 􏱒 􏰧1 􏱒 p􏰨􏱚􏰠 p
The average number of iterations the station has to wait is:
([average numbers of iterations it makes to transmit]-[the successful transmission])􏰣 􏱑􏰡 􏱒 1
Since the time unit is T, the average waiting time equals 􏱛𝑇 ∗ 􏱐􏱑􏰡 􏱒 1􏱓􏱜
3

CEG3185 Winter 2021 Problems solving Tutorial 3
Problem 4
The figure below depicts the timing diagrams of two switching methods, circuit switching and packet switching, that are discussed in detail in our course.
Let
N = number of nodes including two end nodes (e.g., N=4 in the diagram given) L = message length in bits
B = data rate in bps
P = packet size in bits (including header and data portion)
H = overhead(header) bits
D = propagation delay per hop
a) Which diagram (left or right) represents circuit switching and which one represents packet switching? and what is the most likely type of packet-switching the diagram represents?
b) List all timing/delay components possible in each case.
c) How many packets Np are required to transmit the message in general?
d) Using packet switching as shown in the diagram, give a general expression in terms of the symbols above for the transfer time Txfer of the message. Then describe in words the major components of Txfer from the diagram (the purpose is for you to see where the expression comes from)
Suppose a message of 5,000 bytes long is to be transmitted along a four-hop communications path. Assume that all links operate at B=2400 bps and D=25 ms and H = 20bits,
e) From (d), find Txfer as a function of P only.
4

CEG3185 Winter 2021 Problems solving Tutorial 3
f)
g) h)
From the equation obtained in (d), derive the packet size P that minimizes Txfer. (Hint: you may have to make one necessary but reasonable assumption to make the derivation easier; justify it).
What is the optimum Txfer? Explain briefly how you verify that this is the minimum. (4 points)
Explain in terms of the results how resource sharing is effected through packet switching?
Answer
a) The diagram on the left represents circuit switching; the one on the right represents packet switching (You have already indicated these). Most likely, this is a datagram packet switching.
b) Time/delay components (ignoring processing delay at the nodes; no acknowledgement is shown in the diagram)
 In circuit switching: call setup time, message delivery time including propagation delay
and transmission time
 In datagram packet switching: propagation delay, packet transmission time determined
by packet size and data rate, number of packets
c) The number of packets Np required to transmit the message in general:
Np = 􏱝 􏱞 􏱡 􏰧􏱟􏱏􏱠􏰨
where ⌈𝑋⌉ means smallest integer larger or equal to X.
d) Using packet switching as shown in the diagram, the transfer time Txfer of the message =
D1 +(N–1)D2,
D1= time to transmit and deliver all packets through first hop D2 = time to deliver last packet through a hop
D1 = Np(P/B) + D
D2 = P/B+D
Thus, Txfer = D1 + (N – 1) D2
= (Np + N – 1)(P/B) + N D
e) From d), Txfer=D1+(N–1)􏱝􏱞 􏱡D2
􏰧􏱟􏱏􏱠􏰨
= (Np+N–1)(P/B)+ND
40000+ 3) (P/2400) + 4  0.025 = (  P  20 
= 40000+ 3) (P/2400) + 0.1 (  P  20 
f) We replace Np =with Np = L/(P – H). This simplifies the derivation. Also, N=􏱝
and L/(P – H) are close to each other, since the number of bits used for “bit studding” should be kept small. Also, it is assumed that D = 0, since this a parameter that is out of the designer’s control. Thus
Td = (L/(P – H) + N – 1)(P/B)
􏱞 􏱡 􏰧􏱟􏱏􏱠􏰨
5

CEG3185 Winter 2021 Problems solving Tutorial 3
To minimize as a function of P, take the derivative and equate with zero: dTd/(dP)=0
0 =(1/B)(L/(P – H) + N – 1) – (P/B)L/(P – H)2 0 = L (P – H) + (N – 1) (P – H)2 – LP
0 = –LH + (N – 1)(P – H)2
(P-H)2 =LH/(N–1)
P = H + 􏱢 􏱞􏱠 􏱣􏱏􏰡
g) The optimum (minimum) Txfer =D1 + (N–1)D2
= (Np + N – 1)(P/B) + N D =(Np+N–1)((H+􏱢􏱞􏱠 )/B)+ND
h) such as a single node-to-node link can be dynamically shared by pkts coming from different users over time.
􏱣􏱏􏰡
6