Internet Routing

Internet Routing

EECS4215Winter 2016

Assignment 1

Internet Routing

  1. What is an autonomous system?
  2. What is the difference between an interior routing protocol and an exterior routing protocol?
  3. Compare the three main approaches to routing. Name a protocol used in each approach.
  4. List and briefly explain the main functions of the Border Gateway Protocol (BGP).
  5. BGP’s AS_PATH attribute identifies the autonomous systems through which routing information has passed. How can the AS_PATH attribute be used to detect routing loops?
  6. BGP provides a list of autonomous systems on the path to the destination. However, this information cannot be considered a distance metric. Why?
  7. List and briefly describe 3 metrics that can be used for routing.
  8. Which routing approach is more preferable, distance vector routing or link state routing? Explain.
  9. Given the following directed graph of an autonomous system (Figure 19.8), provide the routing table maintained by node R10.
  10. Why can’t distance vector or link state routing be used for exterior routing?
  11. Describe briefly the 4 types of messages used in BGP.
  12. Given the following diagram illustrating 3 autonomous systems, provide the routing table maintained by the gateway router R6 as computed by BGP.

IEEE 802.3 CSMA/CD

  1. Explain the 3 persistent protocols that can be used with CSMA.
  2. Describe the CSMA/CD algorithm (using a flow diagram).
  3. Which persistent algorithm works best for IEEE 802.3 CSMA/CD? Explain.
  4. Explain binary exponential backoff.
  5. Describe the binary exponential backoff algorithm used in IEEE 802.3 CSMA/CD.
  6. What is the major negative effect of binary exponential backoff? Explain using an example.
  7. How are collisions detected?

Signal Propagation Basics

  1. Define the 3 transmission ranges.
  2. Define the following signal propagation effects with diagrams:
  • shadowing (blocking)
  • reflection
  • scattering
  • refraction
  • diffraction
  1. Prove that the maximum distance d (km) between an antenna with height h (m) and a receiver at the sea level is given by d = 3.57 h, assuming an optical line of sight. Hint: Use the Pythagorean theorem.
  2. Prove that the maximum distance d (km) between two antennas with height h1 and h2 (m) is given by d = 3.57 (h1 + (h2), assuming an optical line of sight.
  3. Convert the following free space path loss ratio to decibel. Show calculations.
  4. What signal propagation effects may cause multipath propagation?
  5. How does multipath propagation affect the quality of the received signal?
  6. What is the difference between short-term and long-term fading?

IEEE 802.11 Medium Access Control

  1. What is a basic service set (BSS)? What is an extended service set (ESS)?
  2. Draw the diagram of a super-frame in IEEE 802.11 and briefly describe each component of the super-frame.
  3. Why can’t collisions of frames be detected in a wireless medium?
  4. Describe the CSMA/CA algorithm (using a flow diagram).
  5. What is the purpose of different inter-frame space (IFS) values?
  6. Use the given information to draw a table containing the following information:

Standard / Slot time ST (s) / SIFS (s) / DIFS (s) / PIFS (s)
IEEE 802.11a
IEEE 802.11b
IEEE 802.11ac
IEEE 802.11g
IEEE 802.11n (5 GHz) / 20
IEEE 802.11n (2.4 GHz)

Note: DIFS = SIFS + 2 x ST

PIFS = SIFS + ST

  1. Describe the binary exponential backoff algorithm used in CSMA/CA.
  2. What is the hidden terminal problem?
  3. What is the exposed terminal problem?
  4. Consider the following ad hoc network and the following assumptions:
  • the distance between any 2 neighbour nodes is d;
  • the transmission range is 1.2d and the sensing (detection) range is 1.5d;
  • the medium is busy at time (slot) t due a long transmission between C and D;
  • node A wants to send a data frame to node B and node X wants to send to node Y at time (slot) t but both detect a busy channel;
  • the channel becomes free at time (slot) t+5;
  • node A draws random number 9, and node X draws random number 6.

Draw a diagram (similar to the one on slide 36 of the lecture notes) that shows

  • the sequence of control and data frames exchanged between A and B, and between X and Y
  • the time gaps (e.g., IFS) between frames or between events
  • the network allocation vectors (NAV) of the stations hearing the control and data frames.


11. What is co-channel interference?

12. What is adjacent-channel interference?

13. Describe briefly how the PCF works.

14. Consider the sequence of actions within a BSS depicted in the following diagram. Draw a timeline, beginning with a period during which the medium is busy and ending with a period in which the CF-End is broadcast from the AP. Show the transmission periods and the time gaps (IFS).

1