MS&E 130/231: Information Systems, Autumn 2005-06

Instructor: Ashish Goel

Handout 2: Homework 1. Given 10/6/05. Due 10/13/05.

 

 

Since there is no class on 10/13, please slip your HW under my door before noon.

 

Collaboration Policy: You are allowed to discuss general strategies for solving a problem with other students in the class, and also to clarify your understanding of the problem. You are not allowed to copy or see somebody else’s homework.

 

Problem 5 can be done in groups of at most 3. All members of the group must include the same answer in their submission, and cite each other.

 

 

  1. Use nslookup to estimate the fraction of the IP address space that is assigned to the publicly accessible Internet. Comment on the need for expanding the IP address space. Hint: I have attached below a piece of code that generates k random IP addresses where k is an argument to the program. Please do not run nslookup on more than 250 addresses  – we don’t want to start our own Distributed Denial of Service (DDoS) attack on Stanford name servers!

 

  1. Estimate the diameter of the Internet as best as you can by guessing names of remote websites and running traceroute. Report the longest path you found in terms of the number of hops, and the corresponding website. What does this tell you about the time for routing tables to stabilize under RIP? Note: When running traceoute, you will notice a lot of  *** entries. These correspond to routers that do not participate in the underlying protocol used by traceroute. The “length” of a path is the largest hop-count for which you actually get the name of a router as opposed to just a ***.

 

  1. Consider an IP routing table which has the following entries:

 

171.64.132.0/22                      Interface A

171.64.128.0/20                      Interface B

0.0.0.0/0                      Interface C

171.64.135.21/32        Local

 

            To which interface should packets for the following destinations be forwarded?

 

                        171.64.135.17

                        171.64.136.0

                        171.64.144.0

 

  1. In order to avoid routing loops, RIP follows the following simple rule: If an entry in the routing table of A is via a neighboring node B, then this entry is not included when A sends its routing table to B. Unfortunately, this does not quite solve all problems. Consider the network in figure 1 below. Assume that the routing tables of A, B, C, and D have the following entries:

 

A’s table:         0.0.0.0/0          cost=2              via P

B’s table:          0.0.0.0/0          cost=3              via A

C’s table:          0.0.0.0/0          cost=4              via B

D’s table:         0.0.0.0/0          cost=10                        via Q

 

Now suppose the link from A to P gets disrupted. Show a sequence of events which would result in there being a routing loop among A, B, and C.  When will this loop get removed, assuming that no other links come up or go down? An event is something of the form: “Router X sends its routing table entries to Y”.

 

  1. Discuss briefly (500 words or less) the potential and the limitations of the market for real-time, multi-player, virtual reality games over the Internet. What possible directions can this market move towards as a result of social and technological factors?

 

Code:

#include <stdio.h>

#include <stdlib.h>

#include <assert.h>

 

int main(int argc, char **argv) {

  int n,i;

  int a,b,c,d;

 

  assert (argc == 2);

  n = atoi(argv[1]);

  assert(n > 0);

  assert(n < 1000);

 

  for (i=0; i<n; ++i) {

    a = random() % 256;

    b = random() % 256;

    c = random() % 256;

    d = random() % 256;

    printf("%0d.%0d.%0d.%0d\n",a,b,c,d);

  }

}

 

Figure 1: The labels on the links, when provided, denote costs.