1.) (12 points) Define or explain the following terms:
ATM cell
The packet used in ATM. Has fixed size of 53 bytes, consisting of 5 byte header and 48 byte payload.
GRADING. Need a reference to a "packet". A "block" is fine.
virtual circuit vs. packet switched
Virtual circuit the path in connection-oriented packet switching: the path is established by the connection request and all packets of the connection use that path. Packet-switched means the network transfers packets from source to destination by store-and-forward routing. The routing can be either along a virtual circuit, or each packet can be routed independently (datagram or connectionless).
GRADING. A complete answer should include a reference to the difference in path organization. A correct description of each term (only) costs 1 point each.
POTS
Plain Old Telephone Service: the usual telephone dialing and voice (3Khz analog) service.
GRADING. Any reference to the traditional telephone goes.
Frequence Division Multiplexing
Providing multiple channels on the same physical media (wired or wireless) by shifting the channels to distinct carrier frequencies separated by a sufficient gap to accomodate the signals on the channels.
GRADING. A correct illustration (picture only) gets 1 point. A reference to "shifting" (only) gets 1 point. A vague reference to "assign frequency" (only) gets 1 point.
2.) (18 points) Limits on information exchange.
a) If we wish to send 1,000 octets per second through a 800hz channel, what is the minimum signal to noise ratio in decibels?
1000 octets per second is equivalent to 8000 kb/s. Shannon's result for a noisy channel states:
GRADING. Using Shannon's formula: 3 points. Correct formula for dB: 3 points. Octets are 8 bits: 3 points. Correctly plugged in values including taking the log101023: 2 points. (The latter turned out to be a challenge.) Total 11 maximum.
b) Explain why using additional bits per baud will not increase the maximum transmission rate through a channel with a fixed bandwidth and signal to noise ratio?
Obviously, Shannon's result makes it clear that using additional bits per baud does not increase the data rate. The question is why. To increase the data rate by increasing the bits per baud, (1) we need more more signal levels in order to encode more bits per baud, and (2) we need to make sure that the bauds per second does not decrease. This means having more levels in the same time interval. But this is not possible because the bandwidth constrains the magnitude of a level change in a given interval of time, and the noise imposes a minimum distance between levels (otherwise the levels cannot be distinguished).
GRADING. Reference to Shannon's rule (only) gets 3 points. Explanation why it does not depend on the "bits per baud" packing factor gets the rest. (Maximum 7).
3.) (15 points) Layering: What is the difference between a protocol and a service interface? Explain your answer in terms of a the ISO seven layer model.
| ^ | ^
V | V |
------------------------------------------- SERVICE
| ^ | ^
V | V |
_____ _____
| | PROTOCOL | |
| | <-------------> | |
|_____| |_____|
| ^ | ^
V | V |
------------------------------------------- SERVICE
| ^ | ^
V | V |
_____ _____
| | | |
| | PROTOCOL | |
|_____| |_____|
| ^ | ^
V | V |
------------------------------------------- SERVICE
| ^ | ^
V | V |
A protocol is the rules (message formats and semantics)
followed by peer entities,
ie, entities in the same layer at different sites,
for communicating with each other.
A service is the rules (service primitive formats and semantics)
followed by entities in adjacent layers
for communicating with each other at the same site.
GRADING. Definition of each (only) gets 7 points (each). Both, 15 points. An example of each (only) gets 2 points.
4.) (20 points) A proposed way to fix the count-to-infinity problem in distance-vector routing is that on a link failure the two routers at either end of the link immediately broadcast (via flooding) that the link between the two routers has failed. Will this solve the problem? Explain your answer.
No. In distance-vector routing, each router A maintains for every other router B the distance to B via every neighbor of A. Thus A cannot make use of the information that the link between two remote routers, say X and Y.
GRADING. The negative answer gets 5 points. A correct explanation gets 15 points. Total 20.
5.) (20 points) The following C program runs two threads, t1 and t2, that share two integer variables, x and y. Thread t1 executes xdec() and thread t2 executes ydec(). xdec() should repeatedly do the following: decrement x by 2 and increment y by 1 if x is at least 2, otherwise block until x is at least 2. ydec() should repeatedly do the following: decrement y by 1 and increment x by 2 if y is at least 1, otherwise block until y is at least 1.
Using Pthreads, supply the MISSING CODE to achieve this:
int x = 10 ;
int y = 10 ;
MISSING CODE pthread_mutex_t xyMutex ;
pthread_cond_t xGe2 ;
pthread_cond_t yGe1 ;
xdec() {
while (1) {
MISSING CODE pthread_mutex_lock( &xyMutex ) ;
while (x < 2) pthread_cond_wait( &xGe2, &xyMutex ) ;
x = x-2 ;
y = y+1 ;
MISSING CODE if (y = 1) pthread_cond_signal( &yGe1 ) ;
pthread_mutex_lock( &xyMutex ) ;
}
}
ydec() {
while (1) {
MISSING CODE pthread_mutex_lock( &xyMutex ) ;
while (y < 1) pthread_cond_wait( &yGe1, &xyMutex ) ;
y = y-1 ;
x = x+2 ;
MISSING CODE if (x = 2) pthread_cond_signal( &xGe2 ) ;
pthread_mutex_lock( &xyMutex ) ;
}
}
main() {
pthread_t t1, t2 ;
pthread_init( &t1, NULL ) ;
pthread_init( &t2, NULL ) ;
MISSING CODE pthread_mutex_init_t( &xyMutex , NULL);
pthread_cond_init_t( &xGe2, NULL) ;
pthread_cond_init_t( &yGe1, NULL) ;
pthread_create( &t1, NULL, xdec , NULL ) ;
pthread_create( &t2, NULL, ydec , NULL ) ;
}
GRADING. There are two parts: 8-10 points for ensuring that x and y are accessed mutually exclusively and 10-12 points for implementing the waiting.
COMMON MISTAKES: Using two mutexes and getting into deadlock. Busy waiting. Accessing shared variables without first ensuring mutual exclusion. Locking and unlocking threads. Using "if" instead of "while" in the check for waiting.
6.) (15 points) Consider a time division switch for circuit switching. The switch has 8 input lines and 8 output lines, with each line delivering an octet every 2 microseconds. What is the acess time of the switch memory?
Every 2 microseconds, an octet (= byte) has to be read from each input line and written to each output line. Thus 16 octets per 2 microseconds, which leads to an access time of one octet every 2/16 microseconds, that is, one octet every 125 nanoseconds. The memory word size should be at least one octet.
GRADING. 12 points for only considering inputs and not outputs, ie, getting 250 nanoseconds.
END OF EXAM