CS434/534 Midterm

Fall 2006

2:00 – 3:30 PM
December 21, 2006

YOUR NET ID ______

YOUR NAME ______

GENERAL INSTRUCTIONS

The examination is closed book, but allows one piece of paper with any notes on it. You can use a calculator.

Write your answers directly on the examination paper, including any work that you wish to be considered for partial credit. Each question is marked with the number of points assigned to that problem; this number is a rough estimation of the number of minutes you will spend on the problem. As a good exam-taking strategy, you may want to first look over all of the problems.
For each question, what we are looking for is an “elevator answer.” Remember people always tell you that you should be prepared to give an “elevator talk” of a subject, so that you can explain to somebody during an elevator ride from the conference floor to your hotel room floor (which takes about 1 minute). You should do the same thing here.

YOUR GRADE (please do not edit)

PROBLEM 1 (25 points): ______

PROBLEM 2 (10 points): ______

PROBLEM 3 (30 points): ______

TOTAL (65 points): ______


1. [25 points] Short Questions

1.a [5 points] Small-Scale Fading and Mobile 802.11b
There were some discussions on using 802.11-like design for mobility. Some people argue that the 802.11b packet size is not suitable to handle small-scale fading due to mobility (assuming the coverage range of 802.11b could be increased). Assume a transmission data rate of 2 Mbps, packet size 1500 bytes, and mobility speed at 30 m/s. Is 802.11b (at 2.4 GHz) packet size suitable for this small-scale fading network? Please justify your answer quantitatively. The speed of light is 3x108 m/s.

Ans. Similar to Problem e) and f) of Hw 1.

1.b [5 points] Power Control and 802.11b
Continue the preceding question. One might think we could extend the coverage of 802.11b from tens of meters to say hundreds of meters by simply increasing the transmission power. Why is this not a feasible solution, assuming power supply is not a problem? Please give at least one reason.

There are many reasons. As an example, increasing the range will increase delay spread.

1.c [5 points] Wireless Capacity
In class, we have derived that an upper bound of the capacity of a wireless multi-hop network is


where l is the aggregated end-to-end throughput, and L is the average (direct-line) distance of all source-destination pairs (assume that the network is scaled so that all nodes are in a unit disk). Please give three examples to extend capacity.


Ans. Reduces lambda by using an infrastructure; directional antenna to improve spatial reuse; larger frequency range; mobility.
1.d [6 points] Orthogonal Variable Spreading Factor (OVSF)
Each WCDMA channel has a fixed chipping rate at 3.84 Mc/s. A novel feature of WCDMA is the concept of orthogonal variable spreading factor (OVSF). The figure on the right shows part of the code hierarchy: each code X can branch out to two codes [X, X] and [X, -X]. Assume code [1, 1, -1, -1] is allocated to a user. What is the bit rate of the user? What is the maximum number of concurrent users given that [1, 1, -1, -1] is assigned? Please consider only downlink which allows code length from 4 to 512.


Ans: Bit rate = chip rate / 4; The maximum number of users happen when each user is assigned 512.

1.e [4 points] Snoop TCP
A major reason TCP does not perform well in wireless networks is that TCP interprets packets losses as congestion and thus reduces its transmission rate when a random packet error happens. Snoop TCP improves TCP performance by 1) dropping duplicate ACKs and 2) conducting local retransmissions at the base station. Some people worried that Snoop TCP may no longer be responsive to network congestion (e.g., when a packet is dropped in an intermediate router due to congestion). How can Snoop TCP make sure that this is unlikely to happen?

This is not covered in class this semester.


2. [10 points] Physical Layer Assumptions and Reality Check


2.a [5 points] Channel Assignment Model
A major problem facing many wireless networks (e.g., cellular and Wi-Fi) is channel assignment, i.e., which frequency channels can be used at which base stations. A theoretical model is that this problem can be modeled as a graph coloring problem: each base station is a graph node, and two nodes are connected with an edge if the transmissions of the two corresponding base stations reach each other. The coloring problem then is to assign colors to the graph nodes so that no two nodes with an edge are assigned the same color. Some people argue that this model may not reflect reality that packet transmission success rate is determined mainly by signal-to-noise ratio (SNR). Why the preceding formulation does not capture SNR well?

Ans: Interference to a node may come from multiple concurrent other transmissions. For example, b -> a can be small, c -> a can be small, .d -> a can be small. But b+c+d-> can be large.

2.b [5 points] Geographic Routing and Physical Layer
In class, we discussed the topology control of GPSR. In particular, we discussed how GPSR uses GG or RNG to prune the topology to make it planar and at the same time connected. Some people argue that the properties of GG and RNG depend on some assumptions on the physical layer model and may not be true in reality. If you think a property of the RNG/GG graph is invalid if a physical model assumption is not true, please give an example. [You may propose a fix to this problem, but a fix could be complicated].

This is not covered this semester.
3. [30 points] Routing and MAC

3.a. [8 points] The figure on the right shows an 802.11 mesh network. The number on each link is the packet success rate, i.e., the percentage of transmitted DATA packets whose ACK are successfully received. If the network uses ETX, please label the link metric on each link, and write down below the routes from each node to destination node D.

Ans: The cost on each link is the inverse of the given success rate. Then you can run shortest path.

3.b. [5 points] A recent measurement study shows that one reason for potentially low packet success rate is that most deployed 802.11 networks use the simpler 802.11 MAC protocol: DATA/ACK, instead of the complete handshake RTS/CTS/DATA/ACK, to reduce signaling overhead. Why may the simpler MAC protocol cause low packet success rate?

Ans: Hidden terminal problem.


3.c. [5 points] A problem of the ETX metric is that it assumes that all links have the same transmission rate. However, this assumption may not be always valid (e.g., in a heterogeneous 802.11b and 802.11a network). How do you extend ETX to address this issue?

Ans: ETX * 1/rate

3.d. [6 points] One reason that different links may run at different rates is that the links may be running an adaptive MAC algorithm; that is, the link layer adjusts its modulation to change the link layer transmission rate. Using the link metric defined in the preceding question, please propose a simple algorithm to adapt MAC rate.

Ans: Previous students have given many algorithms. One of the assignments gave one.

3.e. [6 points] Another criticism of ETX is that it considers only the short-term link rate (i.e., the transmission rate when the link has acquired the floor). However, different links may face different levels of contention (e.g., with different numbers of neighbors). Thus a low loss link with a high contention level may be chosen. Please propose a revision to ETX to address the issue.

Ans: Using link metric that measures the time, starting from a packet is ready to finished transmitting the packet, for sending each packet.

Page 7 of 7