1. Socket
Programming
1.1
(3 points)
Why would a socket be created with a wild card for a foreign destination?
When creating a socket for a server, it is
not known in advance who is going to connect. A wild card is given as
the foreign destination to allow any host to connect.
1.2
(3 points) True or False: Justify your answer. It impossible for two
TCP/IP sockets on host A, both bound to the same local IP address and
local port number, to communicate with two different hosts B and C respectively.
False. It is possible to have have two
different sockets with the same local port and IP address if the destination
port and IP address's are different.
1.3
(3 points) What happens if time-out=0 in the select (maxfd, inputset,
outputset, exceptionset, timeout)?
Two answers were accepted. If the time-out pointer
is NULL then the select function blocks indefinitely. If the time-out
structure is not NULL but has a value of zero seconds the function returns
immediately. This last case would be polling.
(6 points) Write
a function to discover
if a computer is big endian or not. The function should return non-zero
if the computer is big endian and zero otherwise. The function
cannot make any system calls. Explain and comment your code and logic
to be eligible for partial credit if the function does not work.
Hint: The function can be written in a couple of lines with a few
type casts.
/*
* Return non-zero if the computer is a big endian machine.
* cIsBigEndian must not make any system calls.
*
*/
char
cIsBigEndian(void)
{
short s = 0xFF00;
char * c = (char *)(&s);
return *c;
}
3. Fragmentation
and Reassembly
3.1
(5 points)
Why does knowledge of the network MTU yield better utilization of network
bandwidth? Please accompany your explanation with an example.
Packets will not be fragmented if the
MTU is known. No fragments means less overhead which means better
utilization of network bandwidth.
3.2
(4 points) Give two reasons why an intermediate router isn't allowed
to reassemble fragments.
Fragments may not all arrive at the same router.
Reassembled packet may be fragmented again.
Would take up too much time. The router is
supposed to be dumb.
3.3
(3 points) Most IP datagram reassembly algorithms have a timer to avoid
having a lost fragment tie up reassembly buffers forever. Suppose
a datagram is divided into four fragments. The first three segments
arrive, but the last one is delayed. Eventually the timer goes off and
the three fragments in he receiver's buffer are discarded. A little
later, the last segment stumbles in. What should be done with it?
Toss it. Even if we don' toss it there is no
guarantee that it will be fragmented in a way as to make the saved
fragment useful.
3.4
(4 points) What is the minimum network MTU required to send
an IP datagram that contains at least one octet of data?
21 or 24 if you added padding.
4. Naming
and Addressing
4.1
(4 points) If you choose the record-route option,
what limits the maximum number of hops can you record?
The header length field in the IPv4 header
is 4 bits. Hence only 2^4 words - 1 = 15 words. 16 - 5 (the minimum
header size) = 10
4.2
The following figure shows a zoning partition of the DNS domain hierarchy.
The square boxes represent zones, while the rounded ovals represent
hosts.
4.2.1
(3 points) Assuming all nameserver
caches started out empty, list, in order, the name servers contacted
when thumper.telcordia.com tries to resolve xor.engin.umich.edu.
thumper > telcordia; telcordia
> root; telcordia > umich/eecs; telcordia > engin;
4.2.2
(3 points) After the above
resolution, list, in order, the name servers contacted when thumper.telcordia.com
tries to resolve and.engin.umich.edu.
thumper > telcordia; telcordia > engin;
4.2.3
(3 points) After the above
two resolutions, list, in order, the name servers contacted when thumper.telcordia.com
tries to resolve teton.eecs.umich.edu.
thumper > telcordia; telcordia > umich/eecs;
4.2.4
(3 points) After the above
three resolutions, list, in order, the name servers contacted when
nor.engin.umich.edu tries to resolve bambi.telcordia.com.
nor > engin > root > telcordia
5. RIP, Routing
Loops, Split-horizon & Path-hold-down
(15 points) The "split-horizon" routing heuristic, when used alone,
is not sufficient to prevent all routing loops. Show this by constructing
a network topology and a sequence of events such that a routing
loop will be created if only the "split-horizon" heuristic is used
but will not be created if both "split-horizon" and "path hold down"
(with a period of 1) are used. Every link in the network should
must have a cost of 1.
When the
routing loop is created in the "split-horizon-only" case, a set
of routers S will be "counting to infinity" for a destination
D. For both "split-horizon-only" and "split-horizon with path
hold down" show the <next hop & distance> to D in the routing
tables of each router in S. Stop listing entries when the routes
to D converge or when a router's distance to D reaches 6.
|
Topology
|
Sequence of Events
|
6. Link State,
Path Computation & Hierarchical Routing
6.1
(15 points) Showall steps in applying Djikstra's Shortest
Path First (SPF) to the network topology given below.
Permanent |
Temporary |
Comments |
A(A,0) |
B(A,10), D(A,30), E(A,40) |
Root and its neighbors |
A(A,0), B(A, 10) |
C(B, 60), D(A, 30), E(A, 40) |
|
A(A,0), B(A, 10), D(A, 30) |
C(D, 45), E(D, 35) |
|
A(A,0), B(A, 10), D(A, 30), E(D,
35) |
C(D, 45) |
|
A(A,0), B(A, 10), C(D, 45), D(A,
30), E(D, 35) |
Done |
|
6.2 (6
points) When is a link state packet (LSP) with sequence number A older
than an LSP with sequence number B in the lollipop sequence space? Assume
the sequence numbers are signed 32 bit numbers.
A < B <= 0; A < 0 <= B;
0 < A < B & (B - A < N / 4); 0 < B < A & (A
- B > N / 4);
6.3
(4 points) Give one advantage and one disadvantage of setting the link
state packet (LSP) age large.
If
the LSP age (i.e. cache lifetime) is large then the frequency of updates
to refresh the caches is lower thus making better use of network bandwidth.
This is an advantage. However if the lollipop sequence is not used
and a router is rebooted it does not know what sequence number to
start with. Hence it needs to wait for all the others to time out
before it can begin to send updates. If the cache lifetime is large
then the start up time of a rebooted router is longer. That is a disadvantage.
6.4
(8 points) For hierarchical routing with 4800 routers, what region/area
and cluster sizes should be chosen to minimize the size of the routing
table for a three-layer hierarchy?
Suppose there are B big areas containing M
middle areas containing S small areas containing R routers. Each area
has a router designated as its representative. All traffic into this
area passes through this router. All traffic out of this area passes
through this router to a pier area. If you can imagine this then the
routers with the most entries are the representatives to the big areas
(which are also representatives to their respective medium and small
areas). They would have (B - 1) + (M - 1) + (B - 1) entries or approximately
B + M + S entries. Thus B * M * S = 4800. Now we want to minimize
B + M + S subject to B * M * S = 4800. Minimum occurs when B = M =
S = (4800)^(1/3) approx.. 16 or 17.
7.
CIDR, Subnetting, IPv6, and multicast
7.1
(6 points) How many addresses are spanned by the CIDR address 205.12.192.0
with a mask of 0xFFFFF000? And what are the lowest and highest address?
2^12 = 4096 addresses are spanned. Lowest
address: 205.12.192.0; Highest address: 205.12.207.255
7.2
(3 points) Give one main reason why multicast group membership
is not kept track of by anyone.
Keeping track of this information would result
in too much overhead; membership information is constantly changing.
7.3
A new Silicon Valley startup would like to acquire network
space for 2040 hosts.
7.3.1
(2 points) Under CIDR, how many contiguous class C addresses would this
request necessitate?
8 contiguous class C networks are required.
7.3.2
(2 points) What would the appropriate netmask be?
255.255.248.0
7.3.3
(2 points) Assume that this network has been assigned a base address
of 196.150.56.0, and that a packet destined for address 196.150.60.101
arrives at its main router. Is the packet accepted?
Yes, this packet is accepted.
7.4
For the multicast LAN shown below
7.4.1
(4 points) The router R needs to know the existence of one host
interested in a particular multicast group without knowing all
hosts which are interested in the multicast group. How is this fact
exploited in IGMP (Internet Group Management Protocol) to reduce
the traffic overhead associated with IGMP Query -- Reply over the LAN
?
The router will send an IGMP query to every
host on its LAN; each host will set a random timer, and the first host
whose timer expires will reply. Upon hearing an IGMP reply, each host
will cancel its timer. This prevents R from being flooded with IGMP
reply.
7.4.2
(4 points) When all hosts on the LAN have left a particular
multicast group, what does the router R do?
R
will send a message to its parent, pruning itself from the multicast
session.
|