CSE/EE 461 Computer Networks
Questions and Answers
Spring 1997

This page contains email sent to the CSE/EE 461 class. We will use this list to answer questions of general interest to the class, and make some class announcements.

Index of Messages

Messages

Date: Wed 2 April 1997
From: xinyu@u
To: cse461@ee
Subject: Welcome


Welcome to EE/CSE 461.
Please send me an email, so that I can compile a class mailing list.
For the non-cs students, please pick up a copy of the application form
of CS building key and computer account, fill it, and return either
to Prof Meditch or to the EE461 mailbox at EE mainoffice by Wensday.

Thanks

xinyu


Date: Mon 14, April 1997
From: xinyu@u
To: cse461@ee
Subject:  Project1 and HW3 on homepage


Please check the homepage for the Proj1 and HW3 assignment.

Thanks,

xinyu



Date: Tue 15, April 1997
From: xinyu@u
To: cse461@ee
Subject:   CS account is available

For those of you who have filled the CS account application,
please check with front desk of CS department for your
approved passwd.  Those who requested the keycard, the key
access has been set up.  They can use their student ID
card to open the lab door.  For more information about
the labs and computing in CS department, please check 
with front desk to get some information sheet. 

xinyu 



Date: Fri 25, April 1997
From:  xinyu@u
To: cse461@ee
Subject:      Midterm notice and HW4

The Midterm is scheduled on May 5th.  HW#4 was posted
on the web on Thursday, and is due on Weds April 30th.

xinyu



Date: Mon 29, April 1997
From:  xinyu@u
To: cse461@ee
Subject:    Extended Proj1 Due date  

Hi,

The "turnin" program has worked.  Just type in
"make turn" in your working directory.  The files
entiled "answers", "sender_driven.c", "receiver_driven.c"
will be sent to my directory (project1). You can find
the explantion for "turnin" by typing "man turnin".

Due to the students' requests, the due date for
project1 is extended to this Friday, before class.

For the non-cs students, please read the "IMPORTANT_README"
file in your home directory.  For our class, it is 
recommanded to use "orcas" or "sanjuan" to do your simulation.

xinyu



Date: Mon 29, April 1997
From:  xinyu@u
To: cse461@ee
Subject:    Proj1 Hints  


A few points about project 1:

// 1.  HOW TO SET COMMAND LINE PARAMETERS? 
When run simulator, the command line options are:
  sim  protocol  events  timeout  pct_loss  pct_cksum  debug_flags

  . The "timeout" sets the time sender/receiver would wait for
a packet before taking action.  There is a efficiency-reliability
tradeoff to choose this parameter.
  . The "pct_loss" and "pct_cksum" basically simulates 
the reliablity of the underlying physical channel.
The "timeout", "pct_loss" and "pct_cksum" together determines
the behavior of the protocol. 

In Problem(1), you need to simulate a unreliable channel,
so you can set a high value for "pct_loss" and "pct_cksum".

In Problem(2), you need to set a short "timeout", so that
the protocol#3 is more likely to fail.

// 2.  HOW DO YOU KNOW THE TRANSMISSION IS INCORRECT?
In real world, when you run "protocol 3" for example, you won't
know when there is a missing pkt (see textbook p.200), if the
actual sequence number is not included in the header. In the
simulator, the sequence number information is embedded in the
packet body (for simulation purpose).  Therefore, by tracking 
this information, we can know exactly whether there is an error.
(see "to_network_layer" function in "worker.c").
Another failure check is in "main.c" in "sim.c".  This check is
to detect the deadlock case.  
In simulator, whenever an error is detected, the program hang up,
and the error message is printed out.  If the program successfully
run to the end, you know the transmission works for this time. 
(not necessarily for next trial).  For protocol verification,
see textbook p. 219.  

// 3.  WHAT'S GOING ON IN THE PRINTED OUT STUFF?
The print outs let you track the protocol step by step. The 
summary could serve the purpose for double check the correctness
for each run.  For example, in a successful transmission using 
protocol 3, number of packet retranmissions should equal to the
recv'd data chksm err+data lost+"Ack"lost+"Ack" chksm err. 
From the statistics, you can also get a sense of your command-line
parameter settings, i.e., channel reliability and timeout. 
     

Good luck for your project,

xinyu





Date: Tue, 6, May, 1997
From:  xinyu@u
To: cse461@ee
Subject:    Midterm 

Hi, Please ignore the previous announcement of Midterm on web. Some students
have conflict exam time, so the Midterm time has moved to May 12, Monday.
But, please check with Professor Meditch for the latest update.

Thanks,

xinyu



Date: Friday, 16, May, 1997
From:  xinyu@u
To: cse461@ee
Subject:    Binary Tree Algorithm 


Hi,

The following paragraphs try to provide a big picture of the binary
tree algorithm and the its modification in the homework.  It is
not for the homework purpose, but for helping you to understand the binary
tree algorithm. From my office hour yesterday, I felt that many students
were puzzled by the binary tree algoritm.

To answer Question 1 in hw, you need to understand the original
binary tree algorithm well. (see lecture overhead).  Basically,
the algorithm divides those stations involved in the current collision
into two groups. One (say, Ga) will compete to transmit in the next slot, 
the other (say, Gb) will transmit after all the Ga stations have transmitted
successfully. The station(s) in Ga, there are three different cases: 
if station(s) in Ga collide in next slot, the stations in Ga will divide
into two subgroups (Gaa and Gab);  if there is only one station in Ga, it
is transmitted successfully; if nothing in Ga, the next slot will be idle.
This process continues, until all the stations in Ga get transmitted
successfully (or Ga is idle). Then, stations in Gb starts to compete   
to transmit. The above procedure can be visualized as a binary tree. 
That's where it gets its name.

To implement the above tree algorithm, two variables, g and d, are
employed, so as to keep track of the current tree structure. There is only
one "g" varible, while each station has a unique "d" associated.  The "g"
is used to let the algorithm know when the collision are completely
resolved, i.e., when g=0.  The "d"s are to let each station know whether
it is its turn to try the transmission, i.e., d=0.  The values 
of "g" and "d"s are updated upon the feedback from channel, i.e., 
whether the current transmission slot is idle(0), collision(2), or
successful(1).

The binary tree algorithm can be optimized in a couple situations. 
One situation is of a collision slot followed by an idle slot. In this
case, we are sure that next slot following the idle slot will be a collision.
Therefore, we avoid to waste one slot for this sure-to-be collision
try.  Instead, we divide the stations before making a try, which is different
from the original algorithm.  As a result, the updating rule of "g" and   
"d" is different in this situation. 

In the homework, you are asked to track the above situation. You can possibly
use an extra varible to mark this situation. Once the variable is marked,
you need to derive a new rule to update "g" and "d". 
  
Hope it helps to resolve your confusion.  If you still have problem, welcome
to visit me on Tuesday's office hour, so that we can talk face-to-face.

Have a nice weekend,

xinyu 




On Fri, 16 May 1997 10:12:42,  Piotr Brzezicki wrote:
 
>
>I've already handed in hw6 today in class, but I still don't understand,
>and didn't solve corectly, problem #1. We have tried to put out heads
>together with Agniszka (she'll probably try to contact you also), but
>still, no results:-(
>



Date: Tue, 20, May, 1997
From:  xinyu@u
To: cse461@ee
Subject:    HW7 and Proj2b 


Hi, All,

Due to a computer system crash this morning, all the 
email I received between 6:00pm yesterday to 9:40am 
this morning are lost.  If any of you sent me email
within the above time slot, can you please send me
again?  Sorry for the inconvenience.

In yesterday's office hour, there were some questions
about the homework and project. Following may help them
who did not come yesterday.

1. Project2b:

To test your protocol, you first need to test its correctness,
then its efficiency.  

The correctness test has been explained
in my project1 email to class.  In brief, the simulator keeps
watching whether the message received is the same (and in order)
as the message sent out.  Also the simulator keeps track of the
deadlock situation.  If the simulator does not hang up (and exit
with error), it means your protocol is correct for the current run.
(even though not necessarily correct for next run, due to probability
of error).

The efficiency can be checked by looking the statistics summary.
Basically,  
 Y =  "total date pkt transm" - "corct rec'd" - "data pkt in error"
is the inefficient part of the transmission. For the selective
repeat, Y is smaller than go back n. In the project, the first
modification will give you a large "Y" value. You can compare it
with the "Y" value from the second modification.  

2.  Homework #7

This problem is a bit tricky, even to myself. However, a few  
points can make the problem managable. 

First, we just limit ourself to one-way traffic, therefore,
The data pkt (or may be piggyback'd ACk) is not considered.
And the chnl compacity is for the one-way traffic.
   
Second, we assume the protocol is selective repeat with 
a large window, so that the input can keep on transmitting
without waiting for the ACK.

Third, lamda can be analyzed in three category, <1, >10, in between.

If you have any question, let me know,


xinyu



BTW (1) The grade for project1 will be available by tomorrow morning.
    (2) Midterm solution is available in Eng Lib Copy Center.
    (3) Remind you to resent me email due to my computer failure.



Date: Wed, 21, May, 1997
From:  xinyu@u
To: jitu@u
CC: ee461@ee 
Subject:    Proj2b turnin 


Hi, Jason,

If you got a Makefile with "turnin -c cse461 -p project2b answers_p2",
please either modify the Makefile to 
"turnin -c cse461 -p project2b p8.c"
or just type in the above line in your command line.

Thanks,

xinyu

>what's suppose to be contained in the file answers_p2?




Date: Th, 22, May, 1997
From:  xinyu@u
To: ee461@ee 
Subject:    HM7 again 


Hi, All,

The problem 7 is a bit tough.  It combines the knowledge of the
switch(router) implementation, buffer management, concept of 
line capacity and throughput. There are scattered around the texbook,
in p.130 (switch), in p.374(congestion control algorithm),
p.388(service scheduling), ...

Since it's tough, just try your best.

The solution to the problem depends on the implementation of
the router and the related service scheduling policy. So, please
state your switch(router) modeling, and make the derivation based
on the model.

One possible model is the shared input buffer, in which the incoming
cells are buffered, before being routed. In this case, the throughput
depends on the output line capacity and how fast the output from 
buffer could be. The throughput will the the smaller one of the two.
The output supplied by buffer, in turn, depends on the 
capacity of the input line, the buffer size and the service policy.
It is where the interaction of two input lines happens.
Due to this shared buffer, the input rate of 0.7 wouldn't get 
through to the output line as 0.7.  It might be slowed down at
the buffer by packets from other line mixed in between.

Second possible model is the output buffer model, in which the incoming
cells are routed to different line. Then the cells are buffered at
each different output lines, so that to adjust its rate according to
the output line capacity.  This model makes the calculation easier,
because here, routing lines are independent from each other. So,
you just do the calculation for each routing line independently, and
add them together.  There is no intercation between them.

The third possible model is called the input-output buffer model,
in which the buffer is located at the cross-bar junction. 

There are pros and cons for the different switch implementation.
An obvious one is that the input shared buffer can save many storage
space in the switch; while the output buffer has better throughput. 
To solve the problem, I suggest you use either the first or the second
models. (The second model is simpler). 

The different between part (b) and part (c) is that, in part (b), 
there is retranmission, which adds extra traffic load in the input
lines to the router. So, the total traffic on the input lines may
be larger that just lamda and 0.7 (depends on the switch models).
In part (c), the overloaded cells at router is just blindly dropped.
So, the traffic load in the input lines will be lamda or 0.7


Just try your best.  The homework 7 will be graded loosely.
BTW, the project1 grades have been sent out to the cs account,
to those who submitted using "turnin"

Take care,

xinyu
 


BTW, you can assume buffer size as W.



Date: Mon, 26, May, 1997
From:  xinyu@u
To: ee461@ee 
Subject:    Project 3 

Hi,

I have recompiled the 461server and 461chat for orcas.
The newly compiled executable is in 
/cse/courses/cse461/chat-Sp97

A student pointed out the data stucture of message,
which is an union, forgets to include the 
"broadcast" message type. He is right.  Please include
one more item in the above union.  

xinyu


>
>From dsc@oz.net Sun May 25 08:41:08 1997
>From: "D. Cook" 
>
>I believe you forgot to add msg_broadcast to the union msg in msg.h
>
>A long message will be longer than msg plus the code is much nastier without it in the union
>due to nasty type conversion problems.
>
>-- Devin



Date: Tue, 27, May, 1997
From:  xinyu@u
To: johnalex@cs.washington.edu 
Cc: ee461@ee
Subject:    Project 3 (2) 


Hi,

In "input_loop", there is a better way to get out the
while loop, than what was currently written. A simple
quit or exit message from the client will be sufficient.
Just check whether the client types in "quit".  If so,
break out of the loop; otherwise, do "send_data",....

As for "recvfrom()" in process_message_from_server(),
please do the suggestion in my last broadcast email to class,
that is, to add a BROADCAST type in defining the msg as
union (in msgs.h).  It should work.

Let me know if you have any problem.

xinyu

>
>From johnalex@cs.washington.edu Sat May 24 15:45:16 1997
>From: John Alexander 
>To: xinyu@hitl.washington.edu
>Subject: Re: Project 3
>
>Actually have answered most of them myself.  The
>executables are indeed compiled for orcas/sanjuan
>and do indeed run on them when called properly
>(not obvious from the instructions).  The only
>problem left (not counting the stupid way it's
>written to not see what others have written until
>after you yourself type something in) is that
>there seems to be no way to get out of the while(1)
>loop in input_loop in chat.c to get to the
>send_leave(); statement, and I keep getting socket
>errors trying to do a recvfrom() in process_message_
>from_server().
>



Date: May 29, 1997
From:  xinyu@u
To: ee461@ee
Subject:    Homework 8 

Hi, 

The graded hw 6 is available now.  Please pick it up
from EEB 213 during my office hour today from 4:30pm-5:30pm.
The door is open during that period. After that, I will
leave the homework on desk #1 (or #2). However, you can
only go into EE213 when the door is open.  Next week, I will
still have office hour.

The homework #8 is available on web now. The due time is
June 4th.

Please drop the homework #8 into my mailbox at EE mainoffice.

Thanks,

xinyu




Date: Mon 2 June, 1997
From:  xinyu@u
To: studio@halcyon.com 
Cc: ee461@ee
Subject:    Homework 8 (2) 

From: xinyu@hitl.washington.edu
Date: Mon, 2 Jun 1997 10:26:02 -0700 (PDT)
To: studio@halcyon.com
Subject: Re:  homework 8
Cc: ee461@ee.washington.edu

The singular arrows in homework8 is supposed to have
a line connecting two points. (There is something
wrong with the file format, and the line is missing).

For the second problem, please refer to textbook 
page 380-384.

xinyu


>I don't understand the singular arrows on the first problem.  ie the
>arrows that don't have a line connecting them.  Do these mean a connection
>is available in between the two points that would otherwise have a line
>between them?
>
>On the second question, where do we get the info to answer this?  I don't
>remember discussing anything like this in class.
>


Me again,

Due to the requests of students, the due date of
project3 and homework8 are extended to Friday, i.e.,
the last day of the lecture.

xinyu



Date: Tue 3 June, 1997
From:  xinyu@u
To: peterb@cs 
Cc: ee461@ee
Subject:    Project 3 (3) 

Hi, Peter,

To simulate chat, you can open three x-windows, one for
server, another two for two separate clients. In the server
window, type in  "461server 6666".  In the client windows,
type in "461chat orcas 6666 peterb", and "461chat orcase 6666 bob".
Then anything typed in one of the client window will be 
shown up in the server window, and another client window (need to
hit return).

xinyu


>how do I simulate chat? When I type "461server 6666" at the unix prompt,
>nothing happens. Also nothing happens when I type "461chat orcas 6666
>Peter" afterwards. What do I have to do simulate chat?
>





Date: Tue 3 June, 1997
From:  xinyu@u
To: peterb@cs
Cc: ee461@ee
Subject:    Project 3 (4) 

Me again,

Yes, you are right.  The chat coding was written in a way that requires
the client to type in return to see the broadcasting message.
If you are interested in, you can modify the code slightly, so
that to make the broadcast message shown up without hitting return.

Let me know if you have any problem,

xinyu

>Ok., it seems to be working. I'm running independent Xwindows on the
>screen, having one user in each window (and 461server in one, of course).
>It works, but the weird thing is that if I send a message from one window,
>let's say the one Peter is using, the message typed by Peter does show up
>in the server windows instantly, but in another 461chat window only when a
>message is send from that window. But, I guess, that's the way it sould
>be, am I right?
>



Date: Thu 5 June, 1997
From:  xinyu@u
To: jchin@cs 
Cc: ee461@ee
Subject:    Homework 8 

Hi, Jeffery,

On part b of Prob 1, the capacity following the sequence
of UP, Down, Down, and Up are 1,2,4,2, respectively.
For part b, please find the shortest paths from every other       
nodes to Node 1.  I forgot to indicate this in Problem set.
Due to this, the Part b will not be graded.

Homework #7 has been graded, and will be available in EE213
starting at 3:30pm this afternoon.       

BTW, Prof Meditch has posted the coverage of final exam
outside his office.  

Take care,

xinyu

>From jchin@cs.washington.edu Wed Jun  4 23:14:28 1997
>Date: Wed, 4 Jun 1997 23:13:46 -0700 (PDT)
>
>On part b of problem 1, it isn't clear for the paths between nodes 2 and 3
>and 4 and 5 which distance goes with each path.  Also, it seems to me that
>there are no shortest paths from node 1 to every other node, because there
>are no paths leaving node 1 . . . therefore all paths out of 1 are
>infinitely long (i.e. nonexistent).  Is this correct?  Or, am I doing
>something wrong?
>
>Thanks.
>
meditch@ee.washington.edu
xinyu@u.washington.edu
(Last Update: 06/03/97)