CS522 F2006 Homework

Goal:

Learn how to apply queueing theory.
Learn how evaluate the performance of ALOHA and Reservation protocols.
Learn how spanning tree algorithm reduces packet looping in interconnected LAN.
Learn how link state routing work and why oscillation problem occurs.
Learn how broadcast routing works.

Assignment Date: 11/29/2006
Due Day: 12/6/2006
Description:

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.
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.
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.
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 designated bridge in each LAN. I have marked them partially.
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?
3. Explain why Bridge C will not forward the frame from LAN 4 to LAN 3.
Problem 5. 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.
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)?

CS522 F2006 Homework#5: Queueing, Multiaccess, Networking

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.

Label root ports in each bridge and designated bridge in each LAN. I have marked them partially.

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?

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

Problem 5. 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.

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)?

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.

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?

Problem 5. 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.

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)?