Note: see the FAQ for answers to common questions about DP1.

I. Introduction

• What the best choices are,
• How to reconcile sometimes conflicting goals, and
• How to keep the complexity of your design under control.

II. The problem

Each CyberBeanie contains an inexpensive embedded controller CPU and a short-range radio. Two CyberBeanies within radio range can of course directly communicate. Your goal is to allow communication over longer distances, through a group of CyberBeanies, by having CyberBeanies forward packets for each other. You must design the network routing and forwarding protocols that will allow CyberBeanies to communicate over multiple radio hops.

Hardware Environment

Each CyberBeanie comes from the factory pre-programmed with a unique 32-bit ID.

The CyberBeanie radio has a range of 5 feet. Each unit can send a packet at any time, although it can only send one at a time. Any other unit within 5 feet will receive the packet on its radio. Clever use of spread spectrum (which you don't have to understand) ensures that each unit can correctly receive simultaneous transmissions without interference. The radios are full-duplex: each unit can send and receive at the same time. Radios more than 5 feet away cannot hear each other and do not interfere with each other. The radio's data rate is 1000 bits per second.

Software Environment

When a CyberBeanie powers up, it will call an initialization routine that you must supply:

initialize_network(my_id, my_friend_id)

Your interface to the link-layer software consists of two operations. You'll call link_send() to send a packet. link_send() takes two arguments: a buffer containing the packet, and the length of the packet. link_send() transmits the packet on the radio. All CyberBeanies within range receive the packet, which the link layer hands to your software by calling a net_deliver() function that you must write; the only arguments are the packet contents and the packet length.

The link layer manages its own buffer space. You can re-use the memory you pass to link_send() immediately after link_send() returns. You may use the buffer that the link layer passes to your net_deliver() function inside net_deliver(), but the link layer is likely to re-use the storage after net_deliver() returns. You can assume that the link layer has a few hundred bytes of memory to store queues of incoming and outgoing packets.

The link layer doesn't implement a notion of addressing. The link layer does detect corrupted packets and silently discard them.

The CyberBeanie's end-to-end layer will hand you messages periodically. Each message consists of just a 16-bit temperature. You must deliver each message to the unit's friend (as specified by initialize_network()). After your software has forwarded the data to the correct destination, it must hand the data to the end-to-end layer at the destination. The end-to-end software is capable of dealing with duplicate and mis-ordered messages, and of detecting lost messages and re-sending them if appropriate.

One of your jobs is to figure out how often temperature messages should be sent; faster would be better, since that will make the toy more interactive. The inter-message period will be a fixed parameter, set at the factory to whatever value you determine.

Intended Use

Here is an example physical layout of three rows of three children each:

    [100]     [423]	 [511]
    [700]     [111]	 [118]
    [999]     [671]	 [523]

A destination unit may not be present in the classroom, and thus may be unreachable. Your design must do something sensible in this case. You may assume that all units are powered on all the time.

Your Design

Your design should be automatic and self-contained: it should not involve user input or any externally supplied information other than radio communication with other CyberBeanies.

You should hand in a description of your design, and an analysis of its expected performance. Your description should address all the key design decisions you made, with a consideration of the tradeoffs involved and justification for your choices. It should also include detailed packet formats, detailed data structure contents, and high-level pseudocode. The pseudocode should illustrate how your design makes decisions about directing data through a network of CyberBeanies. You should include a completely worked example of how your protocol delivers data through the configuration given above.

Your analysis should answer at least the following questions. You must include your reasoning for each answer. You are allowed to make reasonable simplifying assumptions and approximations, but you must state what they are.

1. How much memory does your design consume as a function of the number of children (and thus CyberBeanies) in the classroom?
2. How long does your protocol take to stabilize as a function of the number of CyberBeanies? Assume that the starting point is when the students all sit down, that each CyberBeanie then wants to send a message to its friend, and that stabilization has occurred when every unit has had a chance to send a message to its friend.
3. How often is it reasonable for each CyberBeanie to send its temperature to its friend, after stabilization? If the answer depends on the number of units in a group, describe how the factory staff should set the period parameter as a function of the intended group size.
4. Does your design support the intended application well? That is, in a classroom of 25 students, will "friendly" CyberBeanies be able to exchange temperature messages often enough to be fun? How about a room with 100 students?
5. Suppose the CyberBeanie were required to work correctly in groups of up to, but no more than, 100, and could take up to 20 seconds to stabilize. Given your design, would this allow the hardware capabilities (radio speed and memory size) to be reduced? Or does it require them to be increased? By how much, in either case?

III. Your report

III.1. Suggestions on Writing Style

Your paper should be as long as is necessary to explain the problem, your solution, the alternatives you considered, and the reasons for your choices.  It should be no longer than that.  We estimate that a good paper will be 8 to 10 pages in length.

A good paper begins with an abstract.  The abstract is a very short summary of the entire paper.  It is not an outline of the organization of the paper! It states the problem to be addressed (in one sentence).  It states the essential points of your solution, without any detailed justification.  And it announces any conclusions you have drawn. Good abstracts can fit in 100-150 words, at most.

The body of your paper should expand the points made in the abstract. Here you should:

1. Explain the problem and the externally imposed constraints.

    You should explain to your intended audience the background of the problem in terms that the audience can understand.

2. Explain and elaborate your solution.

    Be sure to explain the approach or architecture conceptually before delving into details, components, and mechanics. (Remember, you aren't writing a mystery novel!) Present any analysis clearly and concisely.

3. Show how your solution satisfies the constraints and solves the problem (or how it fails to do so);

    Explain how the properties of your solution that result from choices you have made in your design are reasonable or desirable in the context of the problem statement.  Include analysis of the estimated (or measured, if it applies) performance characteristics of your solution.

4. Describe the alternative approaches that you considered and rejected, and why you rejected them.

    Your paper will be more convincing if you say not just why your idea is good, but why it is better than the alternatives.  (For example, if another approach would meet all of the objectives perfectly, but the cost would be 100 times higher, then you should mention that as a reason for choosing your less general but cheaper approach.)

5. Document your sources, giving a list of all references (including personal communications). The style of your citations (references) and bibliography should be similar to the styles in the technical papers you're reading in this class. In particular, a bibliography at the end and no citations in the text of your paper is insufficient; we'd like to see what specific pieces of information you learned from where as we read your paper.

Write for an audience consisting of colleagues who took 6.033 five years ago. That is, they understand the underlying system and network concepts and have a fair amount of experience applying them in various situations, but they have not thought carefully about the particular problem you are dealing with. Assume that your paper will also be used to convince management that you have a viable design. Finally, give enough detail that they can turn the project over to their Information Technology programmers for implementation with some confidence that you won't surprised by the result.

III.2. How do we evaluate your report?

When evaluating your report, your instructor will look at both content and writing.

Some content considerations:

• Does your solution actually address the stated problem?
• Do you explain your decisions and the trade-offs?
• How complex is your solution? Simple is better, yet sometimes simple won't do the job. But unnecessary complexity is bad.
• Is your solution a good fit with the goals of the system?
• Is your analysis clear?

• Is the report easy to comprehend?
• Is it well organized and coherent?
• Does it use diagrams where appropriate? (A frequent problem when people use word processors is that they try to express everything in words, either because the word processor doesn't make it easy to include diagrams, or they haven't ever learned how to use the drawing features. Pictures can communicate some ideas far better.)
• Does it use the concepts, models, and terminology introduced in 6.033? If not, does it have a good reason for using a different universe of discourse?
• Does it address the intended audience?
• Is there a good abstract and bibliography?

Phase Two writing considerations

If you are enrolled in the 6.033 writing practicum, you don't need to do anything special; your practicum instructor will explain how the report will get you credit for the Phase II writing requirement. If you are not enrolled in the practicum, and you want us to forward your design project report to the writing program as your phase II writing project, please say so on the cover page, and make sure that your report is at least 8 pages long. Note also that the writing program has a rule that they will accept only reports that earn a B or better from the class in which they originate. Finally, be aware that the second design project will probably be a team project, and thus much more difficult to tailor to the needs of the writing program than this one.

IV. Collaboration

V. Schedule