EECS 122:
Introduction to Communication Networks
(fall 1999)

Announcements
Course description
Instructional staff
Textbook
Times & places
Lectures & reading assignments
Homework
Exams
Project
Grades
Viewing PostScript and PDF
Newsgroup
Interesting links

Announcements

2000-Jan-26-Wed
All exams and homeworks are now in 475 Soda. Drop by during the spring 2000 semester to pick them up, and/or send email to Adam Costello. At the end of the semester they may be discarded.

The newsgroup (and mailing list) are now being used by the spring 2000 class, so the fall 1999 instructors and TAs are no longer reading it.

1999-Dec-21-Tue
All scores and grades are now available below.

1999-Dec-20-Mon
Solutions to the final exam are available below.

1999-Dec-19-Sun
The final exams scores are available from the grades section, and the statistics are in the exams section.

1999-Dec-16-Thu
A testing loop is now available as tester.c. It depends on new backward-compatible versions of event.c, network.c, streamers.c, timer_expire.h, and Makefile. Type “make tester” to create a program called tester, which runs random tests forever, so you might want to run it as “./tester |& less”.

network_bottleneck_config() was definitely non-functional. It might work now with the new network.c, but it still hasn't been tested. (But network_path_config() has been somewhat tested.)

The TAs liked the provisional questionaire, so it has become the real questionaire, with only one slight edit (the last question about the extensions has been split into three, one for each extension). It is available from the project page.

network_config.h and network.c have been updated to do packet duplication. This is an incompatible change, so do not replace these files until you have updated any of your own code that uses struct network_path_parameters to initialize the new duplicate_probability member. (It's probably just main.c that you need to change, if anything.)

1999-Dec-15-Wed
Two clarifications have been added to transport.h: buffer_max need not be the same for both ends of a connection, and transport_sink_delete_connection() may discard undelivered data.

A new file, network_config.h, provides an interface for configuring the behavior of the network layer, and network.c and Makefile have been modified to support it.

streamers.h and streamers.c have been updated (in a backward compatible way). The behaviors of the byte source and byte sink are now configurable. You can muck with their configuration parameters in main.c to conduct various tests. Soon there will also be a configurable version of network.c.

There is a tool called purify available on HP-UX instructional machines (some workstations in 117 & 199 Cory, and 271 & 273 Soda, and mingus.eecs and parker.eecs). It is supposed to be very helpful for finding bugs related to pointers and memory management. See also /usr/pub/purify.help on instructional machines.

1999-Dec-13-Mon
The grades section now links to a list of all exam and homework scores, without names or student IDs (but you can do a pattern match on the scores you already know). It also says a little about how grades might be assigned.

1999-Dec-12-Sun
The project due date has been extended until 3pm Dec-17-Fri. See the project page for submission instructions.

Late homeworks will have their raw scores multiplied by 0.8 and rounded down to the next half point. Homeworks 1 through 5 are exempt because we kept incomplete records of which ones were late.

1999-Dec-11-Sat
If you picked up a partially-graded homework 11, please return it to 467 Cory (slip it under the door).

1999-Dec-09-Thu
By popular demand, the basic project has been reduced: the flow control and efficiency requirements have been moved to an extra-credit extension worth 10%, as reflected on the project page. The transport_extension_flags have been updated accordingly, so get the new versions of transport.h and transport.c.

1999-Dec-08-Wed
The project interviews have been cancelled. Instead, the TAs will compose a short questionaire asking the same sort of questions they would have asked in the interview. The questionaire will be designed to replace a 15 or 20 minute interview, so it will not take much time to answer. It will be posted no later than Dec-12-Sun.

transport.c is due by 8pm on Dec-15-Wed, via email to both dogan@cory.eecs.berkeley.edu and sokratis@eecs.berkeley.edu. Be sure to put the names of all team members in comments near the top of the file. Be sure it uses only standard C, no operating system features or compiler extensions.

1999-Dec-07-Tue
A new version of transport.c fixed a bug: it forgot to include timer.h.

A new version of streamers.c fixes a slight bug that was probably affecting no one (it could have caused an assertion failure at line 55).

A new version of Makefile uses gcc -ansi -pedantic by default, to check your code for ANSI C conformance, so that you will know whether we will be able to compile it. It also uses -Wall to catch common mistakes, and a few of the .c files have been altered to silence a few warnings (which were harmless).

1999-Dec-05-Sun
A new transport.h inserts the word “data” in some comments to clarify that the buffer_max limits apply only to data bytes, not bytes created by the transport layer.

A new network.h adds a comment about addresses:

Every address has its own length, in bytes, not to exceed the maximum declared above. The unused bytes could contain anything, so be careful not to compare them when comparing two addresses.

1999-Dec-04-Sat
There was a bug in streamers.c. It wasn't obeying the requirement (stated in bytestream.h) that the sink's go-ahead method must not call the source's transfer method directly, but must instead set a timer to do it. The new streamers.c fixes this.

1999-Dec-03-Fri
The README file has been updated to clarify some issues related to flow control. First, “will drop” has changed to “cannot acknowledge” in the following sentence:
(the transport source is supposed to avoid sending data that the transport sink cannot acknowledge for lack of buffer space)
That's because regardless of whether the transport sink buffers or drops the data, if it lacks enough buffer space to acknowledge the data, then the transport source will never stop retransmitting it. With flow control, if the sink stops accepting data, the source should eventually stop sending data.

Next, the following sentence has been added:

The easiest way to prevent the transport source from overflowing the transport sink's buffer is to shrink the window size as the buffer fills up, which is typically accomplished by indicating the amount of free buffer space in every ack.
Finally, the paragraph beginning “Another tricky part of flow control” has been removed, because the problem turns out to be not so tricky afterall. It has been replaced by this paragraph:
One might wonder how the transport sink can honor its buffer limit when packets arrive out of order. If the buffer fills up with out-of-order packets, then when the missing packet finally arrives, there's no space for it. But if the transport source is doing its job correctly, it sends only as much data as the transport sink has space for, so this situation will never arise.

1999-Dec-01-Wed
I've added a promise in network.h that the maximum payload length will be at least 320.

The textbook is less emphatic than it should be that entropy is calculated using base 2 logarithms, not base 10 or base e.

A new version of event.c fixes a bug in timer_cancel().

1999-Nov-30-Tue
In transport.h the comment under the declaration of transport_source_receive_bytes() was erroneous. It said:
See bytestream.h. The source and sink are the tranport_source and byte_source (respectively) that were passed to transport_source_create_connection().
That makes no sense, because according to bytestream.h the transfer method is implemented by the sink. This function is implemented by the transport source, so the transport source must be the sink. And that's what we want: the byte source gives bytes to the transport source. In the new version of transport.h “source and sink” has changed to “sink and source”.

1999-Nov-28-Sun
New versions of transport.h and README are available from the project page. The buffer restrictions on the transport sink have been relaxed. The old restrictions were:
The transport sink must not buffer more than buffer_max acknowledged undelivered bytes (it must drop additional incoming bytes until the byte sink has accepted some more of the buffered data).
The first sentence alone expresses my original intention, and the parenthetical inadvertantly increased the restriction. The comment now reads:
The transport sink must not buffer more than buffer_max acknowledged undelivered bytes (additional incoming bytes may be dropped or buffered, but must not be acknowledged until the byte sink has accepted some more of the buffered data).
Relevant to this restriction is a new paragraph in README that begins “Another tricky part of flow control”. In the paragraph about sequence numbers, the words “or both” have been added to point out that numbering packets and numbering bytes are not mutually exclusive; you can do both if you wish.

1999-Nov-28-Sun
A new version of main.c fixes a bug: it was using strncmp() when it should have been using memcmp().

1999-Nov-27-Sat
There is now a README for the project code. Sorry for the delay.

1999-Nov-19-Fri
The project (transport.c) will be due sometime on Dec-15-Wed. We'll choose an exact time of day later. The TAs will also briefly interview each team. We expect most teams to be interviewed on Dec-16-Thu, but we will find a way to accomodate teams that need to be interviewed before the final exam.

Make sure your implementation can correctly get all the bytes across a single connection (despite losses, reordering, corruption, and duplication by the network layer) before you worry about flow control, buffer space limits, efficiency, or any extensions. If you run out of time, it's important to turn in something that at least gets all the bytes across.

1999-Nov-15-Mon
A bug in random.c has been fixed (added #include <float.h>), and the comments on transport_*_create_connection() in transport.h have been slightly reworded for clarity. The latest versions are always available from the project page.

1999-Nov-13-Sat
Runnable code for the project is now available. A slight design flaw was discovered, so now the definitions of the types bytestream_go_ahead_method, bytestream_transfer_method, and timer_handler are slightly different: they are now functions, rather than pointers to functions. Declarations involving those types have been altered accordingly (by adding a *).

1999-Oct-14-Thu
In section 4.10.2, “2TTRT < rho” should be “TTRT > rho”. In section 4.10.4, rho is a typo (twice)--it should be pi.

1999-Oct-02-Sat
It's not clear exactly what the textbook is trying to say about CIDR routing tables, so here is some clarification. The keys (left sides) of the table rows are address prefixes. When a packet arrives, the router finds the longest key that is a prefix of the destination address, and uses the corresponding next hop to forward the packet. Given a set of all possible destination addresses and their next hops, there are generally many different routing tables that can be constructed that will forward packets correctly. Routers try to construct one with as few rows as possible. In homework 4 problem 1, we will accept any solution that forwards packets correctly and uses two rows in each table. There will be no problem about CIDR addressing on midterm 1.

1999-Sep-16-Thu
The book is not entirely clear in its explanation of internet hosts, routers, networks, addresses, masks, etc, so you may wish to read another explanation of the internet model, which will remain linked from the links section.

Course description

[Oops, we never wrote one.]

Instructional staff

instructors
Stavros Tripakis stavros@eecs.berkeley.edu
Adam M. Costello (email address)

teaching assistants
Hakan Dogan dogan@cory.eecs.berkeley.edu
Socrates Vamvakos sokratis@eecs.berkeley.edu

Textbook

The “required” textbook is Communication Networks: A First Course, second edition, by Jean Walrand, published by WCB/McGraw-Hill, 1998 (ISBN 0-256-17404-0). We will follow this book pretty closely starting Sep-08-Wed. Note the errata.

The UC bookstore should have it in stock, or you can also try Classbook.com or varsitybooks.com or fatbrain.com (search by ISBN).

Here are some other good books that we will not use for the course, but which you might be interested in looking at:

Times & places

During the final exam period:

Office hours (instructors):
Weekdays 11am-12pm 467 Cory

Final exam:
Dec-14-Tue 8-11am 2050 Valley Life Sciences Building

During the semester (obsolete):

Lecture:
MWF 9-10am 105 North Gate

Discussion sections:
Mon 12-1pm 289 Cory
Mon 1-2pm 293 Cory
Wed 5-6pm 247 Cory
Thu 11am-12pm 293 Cory

Office hours (instructors):
Mon 10-11am 467 Cory
Thu 4-5pm 467 Cory
or by appointment

Office hours (Hakan):
Mon 11am-12pm 179M Cory
Wed 3-4pm 179M Cory

Office hours (Socrates):
Thu 9-11am 467 Cory

Midterm exams:
Oct-04-Mon A-Lm in 3 LeConte, Ln-Z in 105 North Gate
Nov-08-Mon A-P in 105 North Gate, Q-Z in 3 LeConte

Lectures & reading assignments

Homework

There will be short weekly problem sets generally due on Fridays. They can be turned in in class on the due date, or slipped under the door of 467 Cory before 2pm on the due date (or any time on an earlier day).

Students are welcome to discuss the problems before the due date, but must not write down the solutions during such discussions; they must write the solutions alone.

Homework 1 due 1999-Sep-10-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 2 due 1999-Sep-13-Mon problems: pdf, ps.gz solutions: pdf, ps.gz ASCII chart
Homework 3 due 1999-Sep-17-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 4 due 1999-Sep-24-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 5 due 1999-Oct-01-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 6 due 1999-Oct-15-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 7 due 1999-Oct-22-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 8 due 1999-Nov-01-Mon problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 9 due 1999-Nov-05-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 10 due 1999-Nov-19-Fri problems: pdf, ps.gz solutions: pdf, ps.gz
Homework 11 due 1999-Dec-03-Fri problems: pdf, ps.gz solutions: pdf, ps.gz

Grading policy: Show your work. Every answer gets all points if correct and arrived at validly, half the points if “mostly right”, and no points if “mostly wrong”. The readers are not asked to provide finer granularity. The final homework score will be total points earned over total points possible. “Food-for-thought”, “hands-on”, and “0 points” problems will not be graded, but you are strongly encouraged to work on them.

Graded homeworks can be picked up at discussion sections, or in 467 Cory during office hours.

HW points turned in mean std.dev.
1 11 171 9.3 2.1
2 15 159 12.8 2.6
3 17 155 8.9 3.3
4 8 151 7.3 1.0
5 6 143 4.4 1.2
6 9 135 6.9 1.3
7 6 132 5.1 1.0
8 12 130 9.9 2.1
9 6 129 5.9 0.4
10 6 130 5.5 0.8
11 8

Exams

The first midterm covered material corresponding to homework due before the exam date. Solutions: pdf,ps.gz. The mean was 12.1, standard deviation 2.7, median 12.5, histogram.

The second midterm covered material corresponding to homework due between the two midterm dates. Solutions: pdf,ps.gz. The mean was 8.3, standard deviation 3.1, median 8, histogram.

The final exam covered the material corresponding to all the homework, with roughly equal emphasis on all topics. Solutions: pdf,ps.gz. The mean was 60.0, standard deviation 9.2, median 59.5, histogram.

Project

Grades

homework: 25%
midterm #1: 15%
midterm #2: 15%
project: 15-40%
final exam: 30%

The basic project is worth 15%, making the total 100%. For people who enjoy doing projects, more elaborate versions of the project assignment are defined, worth extra credit. A reasonable grading scale was chosen before the extra credit was taken into account. Specifically, the weighted average was normalized to a score from 0 to 18, with letter grades assigned as follows:

at leastapprox %
17A+94.4
16A 88.9
15A-83.3
14B+77.8
13B 72.2
12B-66.7
11C+61.1
10C 55.6
9C-50
8D+44.4
7D 38.9
6D-33.3
0F 0

You can view all scores of everyone enrolled, without names or IDs (but you need a window with at least 99 columns). Find your row using the first column, which is the last digit of the sum of the digits of your student ID, and then using the scores you already know. Late homeworks have had their raw scores multiplied by 0.8 and rounded down to the next half point (but homeworks 1 through 5 are exempt because we kept incomplete records of which ones were late.)

The column labeled Avg does not include the project extra credit, while the one labeled Totl does. For each, the next column gives the corresponding letter grade. You can view the statistics for both sets of grades.

Viewing PostScript and PDF

Both PostScript (.ps) and PDF (.pdf) files can be viewed by Ghostview and GV under Unix, and GSView under MS-Windows. These are all front-ends for Ghostscript, and all are available for free from the Ghostscript site. (Versions of Ghostscript older than 4.03 cannot read PDF.)

PDF files can also be viewed with the Acrobat Reader (acroread) on most platforms, which is free from Adobe. Besides displaying PDF documents acroread also lets you search for and select text. You need at least version 3.0 to read the PDF files on this site.

For PostScript files, if ghostview gives an error, try gv or gs, or try just sending it to a printer.

PostScript files can be sent directly to most printers with lp or lpr under Unix, and there is presumably a way under MS-Windows). PDF files need to be printed from a program, like any of the PDF viewers.

Gzipped (.gz) files are compressed, and can be decompressed using gunzip (or gzip -d). When a browser attempts to view a gzipped file, it is usually capable of first decompressing the file. When a browser saves a gzipped file to disk, it may take either of the following correct actions: save the compressed file and suggest a filename ending in .gz, or decompress the file and suggest a filename not ending in .gz. Some browsers, unfortunately, decompress the file and suggest a filename ending in .gz. If the file begins with %!PS or %PDF (or anything intelligible), it is not compressed. Gzip is installed on almost all Unix machines, and both source code and precompiled executables for many platforms are available for free from the Gzip site.

PDF printing problems: Some people (not everyone) have problems printing the PDF files from acroread. The printer processes the job, but does not print anything. This appears to be caused by acroread generating PostScript containing carriage returns (13) instead of linefeeds (10), which confuses some printers but not others (and not Ghostscript). We don't know whether this is a bug in the PDF file or a bug in acroread. For now, if you experience this problem, print the PostScript version instead, or have acroread print to a file, and fix the carriage returns before printing it (for example, tr '\015' '\012' < foo.ps | lp).

Newsgroup

There is a newsgroup ucb.class.ee122 for questions and discussions related to the class. Most of the instructional staff will read every article posted there, so please exercise restraint: post an article if you can reasonably expect a non-trivial number of your classmates to be interested in it, or in the response. Otherwise, please just send email to the individual(s) you want to talk to.

Articles can be read and posted using a newsreader program (like trn, pine, or Netscape Communicator), but there is also a gateway that makes the newsgroup look like a mailing list:

ee122-news@arwen.cs.berkeley.edu

All messages mailed to that address will be posted to the newsgroup, and all articles posted to the newsgroup will be sent to the mailing list.

To subscribe to the mailing list, send a message containing only the word “subscribe” (in the body, the Subject is irrelevant) to:

ee122-news-request@arwen.cs.berkeley.edu

As announcements appear on this web page they will also be posted to the newsgroup.

When you reply to an article, please trim your quotation.

Interesting links

Code Division Multiple Access (CDMA)
diffserv (Differentiated Services working group)
Ethernet
Internet Engineering Task Force (IETF)
intserv (Integrated Services working group)
Internet model
Prudent Engineering Practice for Cryptographic Protocols [ps.gz, author's copy]
RFC Editor
Web Over Wireless (WOW)


[AMC]  Prepared by Adam M. Costello
 Last modified: 2001-Aug-29-Wed 00:25:27 GMT
[Any Browser]