% -------------------------------------------------------------------------
%  CS 716: Introduction to Communication Networks. Midsem: 17 Sept 2011
% -------------------------------------------------------------------------
\documentstyle[11pt]{article}
\renewcommand{\baselinestretch}{1.1}

\textwidth 6.75in
\textheight 9.75in
\topmargin -0.5in
\oddsidemargin -0.1in
\evensidemargin -0.1in

\newcommand{\bc}{\begin{center}}
\newcommand{\ec}{\end{center}}
\newcommand{\bi}{\begin{itemize}}
\newcommand{\ei}{\end{itemize}}
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}
\newcommand{\im}{\item}

\begin{document}
\pagestyle{empty}

\begin{center}
{\large Department of Computer Science and Engg, IIT Bombay} \\ 
{\large CS 716: Introduction to Communication Networks} \hfill{Midsem: 17 Sept 2011; 08:30--10:30} \\ 
Handwritten notes permitted. No photocopies. \hfill{Weightage: 30\%, Max Marks -- 60}\\
\end{center}

\hline
\be
\im Answer in 2-3 lines each: \hfill{\bf 18 Marks}
\be
\im State two advantages and two disadvantages of using a layered architecture for network protocol design. 
% This is a new question.
% Advantages: Modularity, Abstraction, Encapsulation, Reduces design complexity, Easier modification and trouble-shooting.
% Disadvantages: Header overhead, More processing (More delays), Duplication of functionality (Error checking, fragmentation), Not required for specialized applications.
% Give only partial marks if a point is repeated in different words and counted twice.

\im Your friend claims that the bandwidth of a link is always a more important factor than the delay of the link, for application throughput calculations.
Do you agree? Justify.
% This is a new question.
% No. Key idea for the justification: For small messages, the delay dominates the bandwidth.
% Give partial marks if answer is NO but a reason not relevant to above is given, such as considering other delays (for attaching header, queueing).

\im State two differences between p-persistent and non-persistent CSMA.
% This is a new question.
% If channel idle, p-persistent will transmit with probability p, non-persistent will transmit immediately.
% If channel busy, p-persistent will backoff for 1-time slot and try again, non-persistent will backoff for random time.
% Give partial marks for correct but incomplete answers.

\im Consider the use of RTS\_Threshold in IEEE 802.11 (WiFi). 
It has been observed that as the RTS\_Threshold increases from zero, the network throughput initially increases. 
The network throughput reaches a peak for a certain value of RTS\_Threshold and then starts to drop. Explain.
% Repeated from 2009 endsem.
% Initial increase because overhead of RTS/CTS reduces.
% Decrease because no RTS/CTS for most packets, so more collision.
% Give partial marks for answers that have got the key idea.

\im Suppose we have to modify the IEEE 802.11 standard to include priorities for packets, such that higher priority packets have shorter average delays.
We decide to implement this as: Depending on the priority of the packet, the sender node will use a different value of $CW_{min}$ for selecting the random backoff interval.
Your friend says that we should use larger value of $CW_{min}$ for higher priority packet. Is this correct? Justify your answer.

% This is a new question.
% NO this is wrong. Increasing CW_min will increase the average waiting time for higher priority packets.
% So higher priority packets should have smaller value of CW_min.

\im In Go-back-N ARQ, if the sender has packet numbers 10-15 outstanding (ack not received) and the timeout for packet 12 occurs, which packet(s) would be re-sent?
% This is a new question.
% Packets 12-to-15.

\ee

\im Consider packet sizes are 1000 bits, transmission rate is 1 Mbps, and propagation delay from source to destination is 15 milliseconds.
Assume that acks are very small, processing time for packets and acks is negligible, and there are no errors in transmission.
What will be the throughput if we use:
\be
\im Stop-and-Wait ARQ (send one packet and wait for ack before sending next packet). \hfill({\bf 4~marks})
\im Go-back-N ARQ, with a window size of 20 packets. \hfill({\bf 3~marks})
\ee
% Repeated from 2009 endsem.
% For stop-and-wait, only one packet can be transmitted per RTT (30ms). So in 1 second, approx 33 packets are sent, giving throughput of 33 kbps.
% For Go-back-N, there is no error, so it is just sliding window of 20. 20 packets can be transmitted per RTT (30ms). 
% So in 1 second, approx 660 packets are sent, giving throughput of 660 kbps.
% For sliding window of 40, only 30 packets can be transmitted per RTT (30ms). So throughput is 1 Mbps.
% Give partial marks if the ideas are correct but calculations are wrong.

\im Consider two hosts A and B connected via n links, $A \rightarrow R_1 \rightarrow R_2 \rightarrow \ldots \rightarrow R_{n-1} \rightarrow B$,
where $R_1 \ldots R_{n-1}$ are routers. 
Suppose that all links are point-to-point and have the same capacity C (in bps). 
Assume that the propagation delay of the links to be negligible and that no packets from other hosts exist on the path from A to B. 
Consider a packet of size $S+H$ (in bits) to be transmitted from A to B. S is the amount of actual data, while H is the size of the header.
\be
\im How much time does it take to transmit the packet from A to B? \hfill({\bf 5~marks})
\im Suppose the packet is split into $k$ equal fragments. How much time would it take to transmit the packet from A to B? \hfill({\bf 5~marks})
\ee
(Hint: Splitting the packet allows parallel transmissions. For example, $R_1$ forwarding a fragment to $R_2$ and A sending the next fragment to $R_1$, can be in parallel.
Keep in mind that each fragment will need a header (of size H)).

% Repeated from 2010 endsem.
% Time to traverse 1 link is (S+H)/C. A packet will have to be fully received by a router before forwarding. So total time = n * (H+S)/C.
% Using k fragments, each fragment will be of size ((S/k) + H)/C. After first fragment is received by B, the rest will immediately follow.
% Time for 1 fragment is n * ((S/k) + H)/C. Time for remaining will be (k-1) * ((S/k) + H)/C. Total time is (n+k-1) * ((S/k) + H)/C. 
% Give partial marks if the ideas are correct but calculations are wrong.

\newpage

\im Consider an 802.11 (CSMA/CA) network, in a string topology, N1-N2-N3-N4-N5-N6, with symmetric links; a link between two nodes denotes that those nodes can hear other. 
For example, N1 and N2 can hear each other but N1 and N3 cannot hear each other, and so on.
% This is a new question.
\be
\im Node $N_k$ has data for node $N_{k+1}$, k=[1..5]. Suppose RTS,CTS and ACK packets take 1 unit of time and DATA packets take 10 units of time. 
Calculate the minimum time required to complete all the data transfers. \\
Assume that the time required for all other operations is 0. Also assume that data packets arrive at the MAC layer such that no backoff is required. \hfill({\bf 5~marks})
% They *must* state the assumption that DIFS and SIFS are being ignored or assume that it is included in the 1 unit of time or consider some value for these.
% Ignoring DIFS and SIFS case: There are to be 5 transmissions. Each sequence of RTS+CTS+DATA+ACK = 13 units of time. 
% There are 3 rounds: 1-2 transmission can be in parallel with 4-5 transmission. Then 2-3 in parallel with 5-6. Then 3-4 transmission.
% Assuming that packets arrive at nodes in such a way that no backoff is required, the minimum time is 13*3 = 39 units of time.
% Cut 1 mark if answer is correct but does not consider/mention DIFS and SIFS.
% Give partial marks if the ideas are correct but calculations are wrong.

\im Suppose all the data packets arrive simultaneously at the MAC layers for transmission. 
Choose suitable values of backoff for each $N_k$ and re-calculate the minimum time required to complete all the data transfers now. \\
Assume that one backoff time-slot is 1 unit of time.  \hfill({\bf 5~marks})
% Assuming that all packets arrive at t=0, the favourable backoff values are: 0 for first round, 1 for 2nd round and 2 for 3rd round, 
% So minimum time is 13+14+15 = 42 units of time.
% Give partial marks if backoff values assumed are different but logically correct (such as 1, 2, 3).

\im Suppose N1 is sending a data packet to N2, using RTS-CTS. Assume that packet collisions are the only cause of errors. 
Construct a scenario in which N2 will fail to receive the data packet, even if the RTS/CTS packets never collide with each other.  \hfill({\bf 5~marks})
% This could have multiple answers. One posssible answer:
% A sends RTS to B; C cannot hear the RTS.  Simultaneously, D sends RTS to E; C hears the RTS and sets its NAV.
% D hears CTS from E and starts data transmission. During this time, B sends CTS to A; C cannot hear CTS since both D and B are transmitting simultaneously.
% A hears CTS from B and starts data transmission. C wakes up (after D-E transmission NAV) and sends its own RTS (to D). 
% A's data and C's RTS collide at B. Data will be corrupted.
% If someone has assumed that RTS-CTS is not always required, then scenario can be that D directly sends data simultaneously with B's CTS. 
% Give partial marks for any answers that may not be not fully correct but are in the right direction.

\ee

\im A company has an Ethernet LAN, having nodes $N_1$ to $N_k$. The nodes use CSMA/CD protocol for medium-access, so a node having data to send 
may have to wait for the medium to become free, and perform backoff in case of collision. The company is using the LAN for a real-time application,
which requires the following guarantees: (i) Nodes should get medium-access in the round-robin order $N_1$ to $N_k$, and (ii) There should be no collisions. \\
The company tried implementing a TDMA-based mechanism but it failed because the nodes could not maintain time synchronization. 
So they have hired you to design another protocol that the nodes can implement to ensure that the above guarantees are met.  \hfill({\bf 10~marks})

Show the details of your solution, including: 
\be
\im What are your assumptions regarding the nodes, regarding the packets?
\im What actions happen during the initialization phase (start of your protocol)?
\im How does your protocol ensure that nodes transmit only in the round-robin order $N_1$ to $N_k$?
\im How does your protocol ensure that there are no collisions when any $N_i$ is accessing the medium?
\im Assuming that your protocol is correct, what do you think is a main advantage of your protocol? What is the main disadvantage of your protocol?
\ee

% This is a new question. 
% This could have multiple answers. One posssible answer:
% They have to come up with something like the Token Bus protocol (802.4).
% Assumptions - Nodes are numbered; Special control packet (called token).
% Initialization - Logical Token Ring is formed. Each node is given knows the address of its left and right neighbours. They can assume that a co-ordinator node does this work.
% Working- Token starts at $N_1$, $N_1$ transmits data (if any), then passes the token to $N_2$. Each node passes token to neighour after its turn. This process repeats forever.
% No collisions - Only the one who has the token can transmit, others have to listen and wait till they get the token. 
% Pros - simple to implement, deterministic delays, no time-synchronization, no centralized co-ordinator.
% Cons - Inefficient if only a few nodes have data to transmit. 
% Another correct answer would be to elect a co-ordinator which does polling of the other nodes in the correct order. 
% Give partial marks for any answers that may not be not fully correct but are in the right direction.

\ee
\hline 
\end{document}
