Question 1:

Suppose you were on a computer where every email message was read
by a human. Suppose you wanted to transfer a 1 megabyte file out of
the server, undetected, using email. Describe how you would do this
at a high level - i.e., you don't have to give an informal coding
algorithm.

Write a program that can output intelligible English sentences (like
the BS program that was advertised on the Systems bboard). Have the
program encode the 1 megabyte file in the length of the words used.

Question 2:

In lecture, you learned about X.509 authentication via certificates.
An issuing authority like Verisign creates certificates for its
customers (e.g., Amazon). Your browser can use these certificates to
authenticate a server as an Amazon server.

In the questions below, assume the issuer is Verisign, the issuee is
Amazon, and the client is a Netscape browser on your machine.

a> You decide to buy a book from Amazon. Your browser requests a
certificate from Amazon. This certificate contains a signature. Who
created that signature?

Verisign

b> What is stored in the signature? (List the components). How are
they sealed? (List whose key(s) are used to seal any information - be
sure to specify public or secret)

{issuee name, public key, valid dates}Kverisign,pub

c> Given your answer to <b>, can the signature be duplicated by
someone who is not Verisign? If so, why? If not, why not? (2-3
sentences)

Yes, because the components are available from the Amazon certificate
and the key is embedded within most browsers.

d> Describe how you would use a nonce to make the signature more
secure.

Use a different signature:

{issuee name, public key, valid dates, nonce}Kverisign,pub

The server can use its (secret) nonce to ensure no one can duplicate a
signature. The nonce could be a random number from a large name space
encrypted with Kverisign,secret for additional security.

Question 3:

In lecture, you learned about the DNS Internet service.

a> Describe the role of the Time To Live parameter for a DNS caching
server.

A caching server must invalidate a cached Domain Name's IP address
when the associated TTL expires. Any subsequent requests for an
invalidated Domain Name requires the caching server to rediscover the
associated IP address.

b> What happens to DNS performance as you increase the TTL? List 1
key tradeoff.

DNS performance increases, since there are less updates. One tradeoff
is a greater chance of receiving an inconsistent IP address.

c> What happens to DNS performance as you decrease the TTL?

DNS performance decreases - as the TTL approaches 0, the benefits of
caching disappear. Instead, an increasing number of DNS requests must
be made to non-authoritative and authoritative servers. Since there
are fewer non-authoritative servers and even fewer authoritative
servers, their load will increase dramatically.

d> Give an example where short TTLs make sense, and explain why it
makes sense.

As discussed in lecture, a company like Akamai uses a network of DNS
servers to redirect requests for static files (e.g., gifs) to the
nearest in a network of servers. As network flow patterns change, and
congestion appears, a short TTL will allow Akamized traffic to be
redirected on a more frequent basis. The network of DNS servers
reduces the DNS load on a per-server basis.

Question 4:

A sender S and a receiver R are communicating over one megabit/second
(1,000,000 bits/sec) digital channels via a geostationary satellite.
The communications delays from S to R and from R to S are each 0.250
seconds. The transmitter is sending a sequence of packets of size
1,000 bits. The receiver sends packets of the same size at certain
times for purposes of acknowledgment and control.

The receiver can buffer B of the transmitter's packets. It may be
prevented from emptying the buffer for unpredictable lengths of time
by other tasks. Otherwise, it can empty the buffer almost as fast as
the packets arrive. Suppose that communication has been established,
and a protocol is used which prevents buffer overflow. Assume no
errors, drops, or out-of-order deliveries for this channel: the
protocol deals only with buffer overflow issues.

a> Suppose that a lock-step flow control protocol is used, with B=1.
What is the maximum rate at which the transmitter can send packets,
assuming the receiver is not servicing other tasks? (One percent
accuracy will do.)

The receiver can store 1 packet without risking overflow. It takes
.25 seconds for the packet to arrive, and .25 seconds to send back an
ACK. The maximum rate is this 1 packet/.5 seconds, or 2 packets per
second.

The receiver decides that lock-step is too slow, and converts to a
different protocol in which the transmitter continues to send packets
at its peak rate until it receives an explicit *stop* message. The
receiver will then send a message calling for more packets as soon as
its buffer is empty. This is called a bang-bang protocol.

b> What is the smallest B (i.e., number of packets) needed to ensure
that the buffer will not overflow, even when the receiver is busy?

At time t=.25 seconds, the receiver will know it is being sent
packets. It will take another .25 seconds to get a *stop* message
back to the sender. This means the buffer must hold:

(.25 sec + .25 sec) * (1,000,000 bits/sec) * (1 packet/1,000 bits) =
500 packets

c> Assuming the receiver is using your value of B from part (b), when
does the receiver tell the sender to stop?

The receiver must send the stop message as soon as it receives the
first bit of data, since the receiver may otherwise become too busy to
empty the buffer before more data arrives.

d> What is the best rate attainable with your value of B from part (b)
when the receiver is not busy?

The best rate is the same as above - 500 packets/sec, or 500,000
bits/sec. Any rate higher than this has the potential to cause buffer
overflow if the receiver becomes busy.

To try to increase performance further, the receiver tries a
window-based flow control protocol.

e> What is the maximum rate that can be achieved with a window-based
protocol when the receiver is not busy?

If the receiver is not busy, the bottleneck is the network. Thus, the
maximum speed is 1,000,000 bits/sec, or 1,000 packets/sec.

f> How large a window is required to attain that rate?

Window size = round trip delay * bottle neck speed

.5 seconds * 1,000 packets/sec = 500 packets

Question 5:

Consider an operating system running n processes. The OS gives each
process ts milliseconds of run time. ts includes the context switch
time, c milliseconds. In this operating system, processes have equal
priority. Assume you can adjust ts, but not c. For the problems
below, ignore I/O as an issue (e.g., the OS doesn't pre-empt a process
when a mouse click is detected for another process).

a> If one of the n processes is your gnutella client, what percentage
of time is the system running your gnutella code? (we'll call the the
effective efficiency of the system)

(time spent running your code)/(total time spent going through all n processes)

time spent running your code = ts-c
total time spent going through all n processes = n*ts

(ts-c)/(ts*n)=

(1/n)(1-(c/ts))

b> What happens to the effective efficiency of your code as the number
of processes increases? (give your answer in O(f(n)) notation)

The effective effective decreases in an O(1/n) manner

c> What is the minimum ts you can set? What happens if you set a ts
lower than this minimum?

ts=c, otherwise, the kernel won't be able to perform any context
switches at all!

d> If n is fixed, what is the theoretical maximum effective
efficiency? (hint - tweak ts)

As ts approaches infinity, the effective efficiency approaches (1/n)

Now, let's consider the effects of virtual memory. Suppose that the
average amount of time required by the virtual memory system to swap a
process out and another in is v milliseconds.

e> What is the new effective efficiency?

time spent running your code = ts-c-v
total time spent going through all n processes = n*ts

(ts-c-v)/(ts*n)=

(1/n)(1-((c+v)/ts))

f> What is the new minimum ts you can reasonably set?

ts=c+v, otherwise all you are doing is context switching and swapping

g> At what v does thrashing occur? (thrashing was discussed in lecture)

Thrashing is when the amount of swapping prevents the processes from
doing any work (e.g., effective effective = 0)

(1/n)(1-((c+v)/ts)) = 0

Since 1/n cannot be 0, then

(1-((c+v)/ts)) = 0

((c+v)/ts) = 1

c+v = ts

v=(ts-c)

In a real OS, v is actually a function of n. That is, the amount of
time spent swapping depends on the number of processes being run.

h> For simplicity, assume that v=k*n, where k is a constant. What's
the maximum number of processes you can run before you start thrashing?

if v=kn, then thrashing will occur at:

(1/n)(1-((c+kn)/ts)) = 0

Since 1/n cannot be 0, then

(1-((c+kn)/ts)) = 0

((c+kn)/ts) = 1

c+kn = ts

kn=(ts-c)

n = (ts-c)/k