HW1
Assigned: 04.28.2005
Due: 05.06.2005
|
Problem 1:
In Figure 3 of B. P. Crow and I. Widjaja and L. G. Kim and P. T. Sakai.'s paper
on IEEE 802.11, there are four address fields. Please explain their meanings
and when they are used. Please show examples when only 1, 2, 3 or 4 of the
addresses are used.
Problem 2:
Please comment on PCF in IEEE 802.11: why is it seldom implemented in practice?
Problem 3:
a)
In SSCH paper, the author states without proof a mathematical property: Given
two (channel, seed) pairs with M channels, say (C1, S1) and (C2, S2), and two
nodes hop according to the following sequence without parity slot:
Node 1: C1, C1+S1, C1+2*S1, ..., C1+(M-1)*S1, C1, ...
Node 2: C2, C2+S2, C2+2*S2, ..., C2+(M-1)*S2, C1, ...
(All are modulus M operations)
Suppose C1<>C2 (not equal) and S1<>S2 and M is a prime number, please prove
that they overlap at least once every M slots.
b)
Now suppose C1<>C2 and S1=S2, we can see that they won't overlap, and that is
why the authors introduce parity slot:
Node 1: C1, C1+S1, C1+2*S1, ..., C1+(M-1)*S1, S1, C1, ...
Node 2: C2, C2+S2, C2+2*S2, ..., C2+(M-1)*S2, S2, C1, ...
This can ensure that two nodes overlap at least once every (M+1) slots.
Based on the above observations, assume that nodes' time are perfectly
synchronized, M channels, each node has K (channel, seed) pairs, channel
dwelling time (time slot size) is T, channel switching delay is D, please
derive the worst case the percentage of time two nodes overlap. Please consider
two cases: one parity slot after M slots, and one parity slot per cycle as in
the paper.
Compare the two values (formula) you get, in your opinion which one is better
on average and why? Or can you also explain why the authors chose case 2 not
case 1?
Problem 4:
Please read Yu-Chee Tseng and Chih-Shun Hsu and Ten-Yueng Hsieh's paper
on power-saving.
Please prove Theorem 1 at page 4:
The dominating-awake-interval protocol guarantees that when AW >= BI/2 + BW, a
PS host's entire beacon window always overlaps with any neighboring PS host's
active window in every other beacon interval, no matter how much time their
clocks drift away.
Convince yourself that the intuitively right theorem is not so easy to prove!
Problem 5:
Please read the throughput analysis on non-persistent CSMA in Wu and Varshney's
paper:
http://www.soe.ucsc.edu/~ywang/extra-papers/WV99.pdf
This paper is referenced in collision avoidance modeling paper (IEEE ICNP '02)
and should be easier to read. However, in this problem you only need to
reproduce the analytical results for non-persistent CSMA which is compared with
the RTS/CTS scheme in IEEE ICNP '02 paper.
You can use Matlab or any other software tool to calculate the throughput Th
of non-persistent CSMA given a, N and tau (tau = 1 / a) and compare yours with
those shown in Fig. 8 of that paper. Please provide your code and show your graph.
Hints: If you use Matlab, please consult functions: quad and fzero which are
used to do integral and solving functions like p = f(p,p').
Problem 6:
How can we achieve the following operations or modifications with regard to
IEEE 802.11? For example, configure via a user-level program, modify device
driver or upgrade firmware. Please also give some explanations.
1) Enable RTS/CTS and set RTS_Threshold
2) New backoff algorithm other than BEB
3) Maintain per-destination queues like that in SSCH (suppose IEEE 802.11e
is not standardized yet)
4) New control frames, like ATIM-RES in MMAC paper.
Problem 7:
Backoff is used extensively to differentiate nodes' access to the shared
channel. As we said in class, it is not effective, especially in multi-hop ad
hoc networks. Now suppose a node is in backoff stage and needs to send a data
packet to one of neighbors and all the nodes in the network start backoff stage
at the same time with different backoff timers. Surely for this node to
succeed, its backoff timer should have the minimum value among all its
contenders. Suppose RTS/CTS based scheme is used, what is the minimum
difference between this node's backoff timer and its contenders to ensure that
the node's transmission is successful? Propagation delay can be ignored. Please
illustrate with examples.
Now suppose RTS lasts R slots and SIFS lasts 1 slot. Suppose all the nodes choose
uniformly from backoff window [0,W]. For a given node, it has N one-hop neighbors
and M two-hop neighbors. Please calculate the probability that the node can succeed
in RTS/CTS based handshake with one of its neighbors. Assume perfect collision
avoidance as ensured in FAMA's paper and all nodes enter the backoff at the same
time. (Hint: What you need is basic knowledge of probability and you don't need to
simplify the formula.)
Suppose all the (N+M) neighbors are one-hop neighbors of the node, please
calculate the above probability again and compare the difference.
Problem 8:
In 802.11 power saving mode, an AP manages several PS stations. PS mode is granted
by AP and each station is assigned an associated ID code (AID) during the association
process. AID takes value between 0-2007. When a station sends PS-Poll to AP for
frames buffered at AP, it includes AID assigned to itself. Please explain AID's role
in power saving.
Hint: Why station MAC address is not used instead?
Problem 9:
Given three flows as follows:
F2 ------ F1 -------- F3
with weights r2=0.5, r1=0.25, r3=0.25. Assume each flow generates a unit length
packet at the beginning of each time slot and each packet can be transmitted in
one slot.
Please follow Luo and Lu's paper on centralized packet scheduling algorithm to
show the packet transmission sequences for the first 10 time units with rho=4
and rho=8 respectively. Please comment the differences. Note: When there are
ties, the packet from the flow with lower IDs takes precedence.
The first few time sequences for rho=4 have been shown for you:
1 2 3 4 5 6 7 8 9 10 11 12
------------------------------------------------------------------------------
F2 F1 F2 F2
F3 F3
Problem 10:
In some MAC protocols, each station maintains multiple queues for different
neighbors or classes and have separate backoff timers for each queue. For any
node, if its multiple backoff timers expire at the same time, then ``virtual
collisions'' happens and only the packet from the highest-priority queue is
transmitted and for other queues new backoff timers are generated following
binary exponential backoff. This is like what IEEE 802.11e does.
Now suppose there are N nodes in a single-hop network (each node can hear one
another) and each node maintains M separate queues for its neighbors. Compare
this case with another case in which there are N*M nodes in a single-hop
network and each node has only one queue. Which one will perform better given
that all the other conditions are equal and reasonable parameters are used?
Justify your answers.
Hint: You may consider writing simple Matlab programs to experiment with
different N, M and data packet size.
|