I.
1. half-duplex
2. selective repeat
3. router
4. store and forward lockup (or deadlock)
5. hot potato routing
II.
1. The round trip propogation delay must be less than the time to send a packet,
otherwise, a sender could completely send a packet before knowing that the packet
had suffered a collision. This is equivalent to requiring that the ratio of round
trip propagation delay to packet transmission time is
< 1. (Note: let's call this ratio Beta).
Beta = Round Trip prop. delay / (minimum packet length/ data rate)
( Call this Equation 1)
Beta cannot be greater than 1. However, we want Beta to be as close to 1 as possible, since this means we are pushing the data rate as high as possible for a given cable length(or alternatively, making the cable length as long as possible for a given data rate). To see this, note that Round trip propogation delay is directly proportional to the length of the cable(as cable length increases, propogation delay increases proportionally).
Assuming that standard Ethernet has its data rate and round trip prop. delay(which again depends on the cable length) set so that Beta is as close to 1(without going over or equaling 1), we now ask what has to change to maintain this property if the data rate is increased by a factor of 10 (from 10 Mb/s to 100 Mb/s)
Looking at Equation 1, we see that the Round Trip propogation delay must be decreases by 1/10. This amounts to making the maximum cable length 1/10 as long(since Round Trip prop delay is directly proportional to cable length).
Note: as was brought up in class, we could make the minimum packet length 10 times greater. However, this would require the well-established Ethernet packet formats to be changed, and would also lead to more inefficient use of the channel(since short packets would have to padded with many "dummy" zero bits in order to make the packets meet the much greater minimum length restriction.
2. It's for error recovery from the failure of both rings at one point as the two rings can be joined together to form a single ring, that still maintains connectivity for the whole network. If they aren't counter-rotating, we don't have this nice property. (note: the nodes on the network all have special switching circuitry, so that in the case of a failure, they can join the two rings back together).
3. (1) Propagation delay- the larger the ring is, the more terminals are connected to it. Thus, the maximum time anyone has to wait for the token increases. Imagine that the token just passed you and now you decide to send something. You have to wait even longer for it to get back the larger the ring. This might not seem significant at first, but imagine the ridiculous case of trying to connect all computers throught the state(or the world for that matter) with a token ring style network. Just think how long you might have to wait to get the token!.
(2) Wasted bandwidth on users who rarely have anything to send. Imagine a gigabit network with 100 users that uses a token ring. Then imagine that only 5 users are communicating, but they would like the full available bandwidth to do videoconferencing. While the token is being passed around to the other 95 users, they are using an incredibly small portion of the available bandwidth in just reading the token and putting it back on the line to send to the next user(This is also true if most users just have small messages to send). During this time, the full available bandwidth is being wasted while there are 5 other users that really need it.
Note, the propagation delay is the main reason.
III.
Let's imagine time as being slotted in units of T second. In slot 1 the source node sends the first packet. At each subsequent time slot, the second node and subsequent nodes along the path cannot ACK it until the destination node receives the packed from the node before it. This follows according to rule (1). Once the packet is taken at the destination node, ACKs begin propagating back starting from the last destination node, and continue along the connection path.
Hence the time between the first packet transmission and the second packet transmission from the source node is
(packet transmission time + ACK transmission time) * (n-1)
+ round trip prop. delay(for message one way and ack the other)
Note that (packet transmission time + ACK transmission time) * (n-1)
represents the transmission delay, and is charged to each node except
the last(once a message or ACK reaches the last node on the path, it
doesn't have to be retransmitted by this last node, so we have (n-1).
We get,
( tau + tau/2 ) * (n-1) + 2 * tau
= tau * (3n + 1)/2 (after some algebraic simplification)
Thus, the throughput is one packet every tau * (3n + 1)/2 second, which gives 2/(tau * (3n +1)) as the throughput.
Also note that when the network increases, more nodes are added, and connection paths get longer, so n increases. Looking at the last equation shows that as n increases, the throughput decreases. Specifically, say that n doubles. Then 3n+1 increases to 6n+1 which is roughly 2*(3n+1) for large n. So we see that throughput is cut in half.
IV.
See Homework Solutions
IV. (See Homework for alternate solution)
Check my arithmetic.
1. Solving x_1 = (1 - p_0) * lambda, x2= p_0 * lambda, x_3 = x_1 + (1-p_2)*x_2,
=> x_1 = x_2 = lambda/2, x_3 = (2/3)*lambda
2. Using the Little's law N = lambda * T = lambda / (mu - lambda), you get
N_1 = N_2 = lambda/(2-lambda), N_3= 2*lambda/(3 - 2*lambda)
3. T = (N_1+N_2+ N_3)/lambda = 1/(2-lambda) + 1/(2-lambda) + 1/ (3-2*lambda)
4. Using the condition (x_i/ mu_i) < 1 where i=1,2 and 3 for the system to be in a steady-state, you should get the necessary and sufficient condition as below.
=> lambda < 3/2