Solution to Homework#5:  Queueing, Multiaccess, Networking

Problem 1. Apply Queueing Theory. Dedicated Channel vs. Shared Channel.
Page 13 of queueing handout. http://cs.uccs.edu/~cs522/f2001queueing.pdf

Eight parallel sessions using a 45Mbps  line. Each session generates Poisson traffic with li=20 packets/sec. Packet lengths are exponentially distributed with a mean of 8000 bits.
There are two design choices:
a) Each session is given a dedicated 45/8 Mbps channel (via FDM or TDM).
b) Packets of all sessions compete for a single 45Mbps shared channel.
Which one gives a better response time? Show how you use M/M/1 formula to assist such decision.

Ans: Let us calculate the delays of the two design choices based on the M/M/1 formula. T=1/(m'C-l).
a) C=45/8 Mbps. m'=1/8000 packets/bit. l=20 packets/sec.
    T=1/((45000000/8)*(1/8000) - 20)=0.00146 sec
b) C=45Mbps. m'=1/8000 packets/bit. l=20*8=160 packets/sec
     T=1/((45000000)*(1/8000) - 160)=0.00018 sec
Choice b has much smaller delay, better response time.

Problem 2. Slotted ALOHA. (Chapter 4 problem 6).
Measurement of a slotted ALOHA channel with an infinite number of users shown that 10 percent of the slots are idle.
(a) What is the channel load, G?
(b) What is the throughput?
(c) Is the channel underloaded or overloaded?
Hint: Apply Pr[k]=G^ke^-G/k! to solve G.  Pr[k] is the probability of k frames generated in a frame time.

Ans:

1. Pr[0] is the probability of a slot that does not contain frame, i.e., idle frame slot. Pr[0]=0.1. Pr[0]=G⁰e^-G/0!=1*e^-G=0.1. ln(e^-G)=ln(0.1). -G=-2.30259. G=2.30259.
   The channel load is 2.30259.
2. S=Ge^-G=2.30259*e^-2.30259=0.230258. The throughput is 23.0258%, below the optimal 36.8%.
3. The optimal operating condition for slotted ALOHA is G=05. Here G=2.30259 > 0.5. Therefore it is an overloaded channel.
   

Problem 3. Reservation Based Protocol.
How long does a station has to wait before it can start to send? Considering the following two protocols. Assume there are N stations in this multiaccess network.
1. Bitmap protocol
2. Binary Countdown Protocol.

Ans: We assume that the data frame are d bits.

1. Bitmap Protocol
   • Light load (one station to send during the contention period): The cycle is (N+d) bits, N content bit period folllowed by d bits data frame sending.
     Best case: If station n happens to have data to send right before its designated content bit slot, it only need to wait (N-n+1) bit before sending its data frame.
     Worse case: If station n happens to miss its designated content bit slot, then it has to wait until the end of the next content period, (N-n)+d+N.
   • Heavy load (every station always has data to send): Total cycle is N*(N+d) bits. Need to wait N*(N+d) bit time long.
2. Binary Countdown Protocol:
   • Light load: The content period only floor(log2(N+1)). The whole cycle is floor(log2(N+1))+d. For N=128, you need 8 bits instead of 7 bit for the content period (also served as src address). The reason is the all zero bit pattern represents idle (no station sends) and cannot be used to represent a station.
     It is shorter than that of bitmap.
   • Heavy load: The station with largest ID (all ones) always wins. It need to wait log2(N)+d to send again. Others will have to wait indefinitely.

Problem 4. Spanning Tree Algorithm. Page 9 of http://cs.uccs.edu/~cs522/F99int.PDF
Given the network in Figure 4.44a and assume we prefer a bridge with large ID and elect Bridge J as root bridge. For paths with same cost, Use the IDs of the bridges along the path to break the tie. Larger ID has higher priority.

1. Label root ports in each bridge and root bridge in each LAN.
   

   Ans: Note Here we assume if the cost of the two paths are the same, we will choose the path with larger bridge IDs. For LAN 2, the path from root Bridge J, LAN 6, Bridge G, LAN 5, Bridge D has the same cost as the path from root Bridge J, LAN 6, Bridge E, LAN 3, Bridge B. But the first path has large Bridge IDs G-D compared with Bridges IDs E-B. We choose the first path. Therefore Bridge D is the designated bridge for LAN 2.
   
   Here is the the spanning tree. The included bridges are marked with yellow edges. The include links/ports and all LANs are marked with orange edges. Note that Bridges B, C, and H are not part of the spanning tree. They are not involved the frame relay. Bridge B is not involved, since it is not the designated bridge for LAN 2 and 3. Same reason for Bridges C and H.
   

2. Assume no bridge learning, for host a on LAN1 to send a frame to host c at LAN 9.
   How many copies of the same frame will appear in this interconnected LAN?
   

   
   Ans: The following figure shows how the frame (a to c) is relayed by the bridges in the spanning three. Within six rounds, the frame reaches every LAN with each LAN receives exactly one copy of the frame. There are 9 copies of the same frame appear in this interconnected LAN.
   

3. Explain why Bridge C will not forward the frame from LAN 4 to LAN 3.
   

   Ans: Because Bridge C is not part of the spanning tree. To avoid frame looping, Bridge C is not involved in copying frames from one LAN to the other.

Problem 5. Oscillation in Shortest Path Link State Routing.
Given a 8-node network similar to that in Page 20 of the revised http://cs.uccs.edu/~cs522/chapter5.ppt. Node 8 is the destination node. Node 4 has 0.01 unit of traffic. Mark the routing directions and traffic on each link, from 1st Routing to 4th Routing.

Ans:

For calculating the routing tables in the 2nd routing period, we use the link traffic volumn data collected in 1st routing period. Node 5 finds the clockwise path cost to Node 8 is 1+2+3=6, while the counter-clockwise path cost to Node 8 is 1.01+2.01+3.01=6.03. Therefore Node 5 chooses the clockwise route. Node 6 finds the clockwise path cost to Node 8 is 1+2+3=6, while the counter-clockwise path cost is 2.01+3.01=5.02. Therefore Node 6 chooses the counter-clockwise route during the 2nd Routing period. The traffic splits between

For calculating the routing tables in the 3rd routing period, we use the link traffic volumn data collected in 2nd routing period. Nodes 1-6Node 1 finds the clockwise path cost is 4.01 and the counter-clockwise path cost is 1+2=3. Node 1 chooses counter-clockwise route. Same for all other nodes.

For 4th routing period, every node observes that there is no traffic on clockwise direction in 3rd routing period. Every node chooses the clockwise route. Oscillation will continue.

Problem 6. Reverse Path Forwarding. Chapter 5 Problem 15.
Consider the network of Fig. 5-16(a). Image that one new line is added, between F and G, but the sink tree of Fig. 5-16(b) remains unchanged. What changes occur to Fig. 5-16(c)?

(a) New Network Topology


(b) Sink Tree

Ans: Changes in (c) are marked red.

Two more messages are forwarded. One from F to G. One from G to F. Since they are not arrived from the link on the sink tree, they are not forwarded further.