18-649 Project 10

Check the course webpage for due dates

Please submit all project-related correspondence to

In this project, you will develop a network schedule for your design and continue to test your design.

A Recommendation About Design Verification

Runtime monitoring was introduces in Project 7. In Project 11, you will use runtime monitoring to verify that your design meets the new high-level requirements. Although you are not required to do so, you should look ahead at the monitoring requirements and think about how you can use monitoring to verify your improved design. We strongly recommend that you start using a monitor for verification as soon as you have a complete design. Dispatcher algorithms are very complex and have many corner cases. You probably won't find all the problems without runtime monitoring. You should also consider generating additional acceptance tests to further exercise your design. Again, these are not requirements, but remember that the sooner you identify problems in your design, the easier they are to fix!

RMA Network Scheduling for CAN

Up to this point, the simulator has provided unlimited bandwidth for network messages. This effectively means that any network message is delivered instantly. Real CAN networks have limited bandwidth which results in finite delays for messages.
In order to make sure that your system can meet the bandwidth requirements of the network and the timing requirements of the elevator system, you will develop a network schedule using Rate Monotonic Analysis (RMA) with harmonic periods and deadline = period. Sometimes this is called Deadline Monotonic Analysis or Deadline Monotonic Scheduling. For details, refer to the lecture material on scheduling and the two CAN lectures.

Network Schedule Overview

The total worst-case bandwidth required by your elevator must be less than 200,000 bits/second. This means that beginning with this project, you must run your acceptance tests with the additional flag "-b 200". You do NOT need to execute unit or integration tests with this flag enabled.

In order to meet the bandwidth requirements, you will need to use network bandwidth efficiently. This may require changes to your implementation to reduce the bandwidth consumed by some messages. You may also need to combine some messages.

Message periods/deadlines are specified in the Project 7 writeup and in the code. You must use the controller period for the period of network messages sent by that controller. If you wish to change the controller or message periods, you must obtain prior approval of the course staff.

A few notes about optimizing your network schedule:

You may combine some messages if and only if they meet the following criteria:

Messages must originate from the same instance of the sending node. Note that "the same instance of the sending node" means you cannot combine the mDoorMotor messages from multiple DoorController objects.
Messages must have the same deadline.

You may remove any messages that are not required by your design (e.g. mHallLight). If you remove a message in your design, you must also remove references to the message in the message dictionary in the Requirements I document and the input and output interfaces in the Requirements II document. You must add the message to the list of removed messages in the Requirements I document.
You may NOT add new messages to the schedule unless you obtain approval from the course staff. If you think you need to add a message, you should first check to see if there is a way to obtain that information using the current set of messages. We have found the current set of network messages to be sufficient for meeting the elevator requirements with a time-triggered design, so we rarely approve requests to add new messages. However, if you can make a convincing case for the need to add a message, we will consider the request.
All data values must be transmitted in the payload portion of the message. You may not use bits of the message ID to transmit data values. This is a limitation of the simulator architecture, but in real life, it's good to avoid this "hack" if you can, since it can produce a design that is difficult to test and maintain.

The reamaining sections describe the structure for the tables you will use to describe your network schedule and analyze its bandwidth requirements. You will submit these tables with your portfolio. The soda machine example has a complete network schedule (for that system), so you can see how the two tables have been completed in that case. Note that we intentionally omit the excel document used to produce the schedule, since this is something you are supposed to develop on your own.

Message Dictionary Table

You will start by constructing a message dictionary table. You CAN IDs shall have the structure described in the table below. Fields are listed MSB first, so the Criticality field is bits 28-29 of the message ID:

CAN ID Breakdown	Size (bits)
Criticality (always 01)	2
Message ID	11
Sender Node ID	8
Replication ID	8
Total # of bits	29

Note that you may assign arbitrary values for the Message and Source Node IDs within the constraints dictated by the RMA schedule.
Note 2: In this document, the term "CAN ID" refers to the entire 29 bit message ID specified by the above table. The term "Message ID" refers to the 11 bit field in the second row of the table above.

Your message dictionary will be similar to the tables shown in the simulator development overview, although the rows for all messages (even for the module messages) should be contained in a single table.

The message dictionary table shall have the following columns**:

Sender Node Name - the name of the node that sends the message
Message Name - the type of message (e.g. "mDesiredFloor")
Deadline - the deadline given in units of milliseconds. For this analysis, deadline=period
Message ID - the 11-bit message ID number. This value is unique per message type (e.g. "mDoorClosed" messages all have the same Message ID). This value determines message priority.
Sender Node Type - this is an 8-bit numeric value that represents the sender node. For example, all messages sent by a ButtonControl object would have the same Sender Node type
Replication Type - the replication type, e.g. "none", "hall, side", "floor, hall, direction"
Base CAN ID - the 29-bit CAN ID according to the message ID breakdown table above (before a replication ID is added). If the message is not replicated, this value is the same as the CAN ID.

**IMPORTANT NOTE: There are a few strict requirements for this table:

The columns must be in the order listed above
The rows in the table must be in ascending order of message deadline (shorter deadlines appear first in the table). For messages that have the same deadline, they can appear in any order, but the order must be consistent between this table and the Network Schedule Analysis table below.
Each row of the table shall describe a message type and every message shall be included in the table (messages sent by controllers and messages sent by the modules and smart sensors).
The values in the underlined columns also appear in the Network Schedule Analysis table (below). The two tables must have the consistent values for these columns.

Network Schedule Analysis Table

Next, construct a network schedule analysis table.

The table shall have the following columns***:

Sender Node Name
Message Name
Base CAN ID
Replication Count - how many replications of this message are actually sent a fully instantiated elevator. This value must be a positive integer number. Note that some instances of a replicated message are never sent. E.g. there are no hall call buttons or controllers for the 2 FRONT landing, no up hall call buttons on the top floor, etc. So the Replication Count for mHallCall is actually less than (# of floors) * (# of hallways) * 2.
Deadline - value in ms.
Field 1 description - description of the data in the first message field
Field 1 type - the data type, e.g. "Boolean", "enum" or "int" and any units associated with the data (e.g. "mm" or "m/s")
Field 1 bit length - the number of bits in the data payload that are required to send this message. Be sure you factor in the new drive parameters!
(Optional) additional sets of field columns (description, type, bit length). You can add as many additional sets of field columns as needed for messages that contain multiple fields. There are three sets of field columns included in the Excel template.
Total payload bit length - total number of bits needed to transmit the message payload. For example, a message payload with a single boolean value requires only 1 bit.
Total payload byte length - number of bytes needed to transmit the message payload. You should think about how this value is related to the Total Bit Length field. This value must be a positive integer.
Best-case message length - the total length of the CAN message, including header and payload, but no bit-stuff overhead.
Worst-case message length - the total length of the CAN message, including header, payload, and worst-case bit-stuff overhead. ****
Best-case bandwidth* - compute the total number of bits per second that will be used by all instances (replicas) of the message in the best case.
Worst-case bandwidth* - compute the total number of bits per second that will be used by all instances (replicas) of the message in the worst case.

***IMPORTANT NOTE: There are a few strict requirements for this table:

The columns must be in the order listed above.
Each message (row) listed in the Message Dictionary table must also appear in this table, and the rows must be in the same order.
The values in the underlined columns also appear in the Message Dictionary table. The two tables must have the consistent values for these columns.
Columns marked with an asterisk (*) and highlighted in purple must contain an extra row at the bottom that contains the total of all values in the column.
The purpose of "Field X bit length" column is to describe how many bits are actually used to store the information. You will need to analyze the source code of the translators used the system modules (in the elevatormodules package) to determine the field sizes and formats of those messages.

**** A note on worst-case message length computation:
When computing the worst-case message length, use the bit-stuffing formulas from lecture since they provice the most conservative upper bound. Even though some hard coded values (like message ID) might not actually be stuffed because of the distribution of 1's, assume that the message IDs are subject to change, so that you can't count on the bit stuff performance of a particular ID value.

Notes on Updating Design and Implementation with The New Network Schedule

You should conduct the analysis above to make your design as efficient as possible. For example, the provided BooleanCanPayloadTranslator uses a 32-bit payload to send a Boolean value that could be represented in just one bit. This is extremely wasteful. The CAN spec specifies that CAN payloads must be a whole number of bytes, so you cannot have a payload with fewer than 8 bits (one byte). That means that you have reduce the "wasted" bandwidth from 31 bits to 7 bits. If the controller in question has sends multiple messages that can be combined (and still meet the restrictions above), you could also use these 7 bits to send the other message value.

There is a special challenge to converting numeric values into bit representations for sending. You should spend some time thinking about what representation (and precision) might be appropriate for the various network messages with numeric values.

In order to meet the bandwidth requirements of the system, you will need to rewrite your message translators to match the reduced the size of the CAN payloads in your network schedule. At this point, you will need to stop using the BooleanCanPayloadTranslator and IntegerCanPayloadTranslator, which are very inefficient. You may store data in the translators any way you wish, as long as you send the required information (and no additional information). Remember that all your code (including translator classes) must be included in the elevatorcontrol package and that no modifications to the rest of the simulator may be included in your submission.

You will also need to modify the elevatorcontrol.MessageDictionary file with the CAN IDs required by your schedule.

You should consider your completed Network Schedule Analysis to be a specification for your implementation. It is VERY IMPORTANT that your implementation matches your design. If you were working in the real world, it would be important to follow the network spec so that other distributed modules could decode your network messages if needed. This includes:

The message payload fields that are described in the network schedule shall correspond to the actual way bits are manipulated by the CanPayloadTranslator objects. This means that if you have three fields in a message, they must each use the exact number of bits noted in the table and be in the same order.
The CAN ID's listed in the Message Dictionary and Network Schedule Analysis shall correspond to those used in the implementation.

A few more notes regarding adding, removing, and combining messages and how this can affect your design documents:

If you combine messages, you should do so only in the network schedule and implementation. Do NOT modify your design documents (e.g. input or output interfaces) with the combined messages. Conceptually, combining messages is an implementation issue. You are essentially saying, "coincidentally, these messages are always sent at the same time."
If you remove or add* messages, you MUST update the Message Dictionary and Interfaces in the Requirements I and II documents. You will also need to update any sequence diagrams and other artifacts that may directly or indirectly refer to the message. This is part of having a complete and consistent design.
If you combine messages, then you should alias the constants in the MessageDictionary class with the same value. For example, suppose you combine mDesiredFloor and mDesiredDwell into a single message with ID 0x11111111. Then your MessageDictionary would look like this:
    public final static int DESIRED_DWELL_BASE_CAN_ID = 0x11111111;
    public final static int DESIRED_FLOOR_CAN_ID = 0x11111111;
You may define an additional constant, e.g.
    public final static int DESIRED_FLOOR_AND_DWELL_CAN_ID = 0x11111111;
But you may NOT remove any of the pre-defined constants. Doing so may cause your code to no longer be compile compatible with the simulation framework. If you remove any of the existing constant definitions and it results in a failure to compile, or any other failure in the system (such as the fault injector), then you will have significant points deducted.

*You may only add messages after obtaining permission from a the course staff.

Assignment:

This assignment has two parts: network scheduling, and complete testing of your design.

Before you begin, be sure you download the latest release of the simulator from the download page. The new release contains the drive modifications and some necessary upgrades for the network schedule analysis.

1. Network Schedule

1.1 Make a Network Schedule

Read the discussion about network scheduling above. Fill in the two tables: Message Dictionary Table and Network Schedule Analysis Table. You can find a template for the two tables here: network-schedule-template.xls. Consult the technical notes page for some Excel hints on constructing these tables.

After you have finished the new network schedule, add a vanilla HTML version of the Message Dictionary Table and Network Schedule Analysis table to the Network Schedule document in your portfolio. You should also your completed Excel worksheet and include a link to the excel sheet on the Network Schedule page of your portfolio. The Excel document you submit must be in Excel 2003 format.

1.2 Update Design and Implementation

Once you have settled on a schedule that will meet the bandwidth requirement (less than the 200,000 bits/sec), you will need to update your design and implementation as described above.

1.3. Compare your analysis with simulation results

Run one or more acceptance tests with the "-b 200" flag and record the network utilization (you can combine this part with step 2.3 below). Use the utilization and the the network bandwidth to compute the actual number of bits/s used by the controllers in your design. Record the simulation results along with the total best- and worst-case total bandwidth in the summary HTML file and include 1-2 paragraphs (no more than 500 words) of discussion that addresses the following points:

Is the theoretical analysis consistent with the simulation results?
What factors might cause the simulation results to differ?

Notes:

If you find that your simulated bandwidth usage is not between the theoretical best- and worst- case, then you have likely made a mistake in your analysis, or your analysis does not match your implementation. In either case, you must rectify this problem in order to receive full credit.
Our testing indicates that the utilization results produced by the simulator are accurate. If you believe that your analysis is accurate, but you do not fall within the theoretical best- / worst-case bandwidth bounds, then you must submit a bug report explaining what specific parts of the network simulation framework are incorrect and causing your result to appear inconsistent. Be sure to follow the bug report guidelines from the Project FAQ.
If you receive runtime errors about a message not meeting its deadline, this means that the CAN IDs you have assigned do not correctly prioritize your CAN network messages.
If you design is not passing any of the acceptance tests, you can use the utilization verbose flag to obtain an network utilization values from during the simulation. Use an average of several of these values for your theoretical-to-simulated bandwidth comparison.
If you receive an error message [RepeatedPayload] @x.xx: RepeadedPayload[msg=yyy]failed to meed deadline. This is not due to a simulator defect but rather a due to scheduling problem.

2. Complete Testing

2.1 Complete Unit Testing

Update your unit tests to reflect changes to the CAN IDs and translators in your implementation. The technical notes page contains a script that can replace the old CAN IDs with the new ones in all your test files with one command.

Run all unit tests. For this project, all unit tests must pass (0 failed assertions). Note that you do not need to specify the "-b 200" flag for unit tests.

2.2 Write and Execute Integration Tests

First, double check your sequence diagrams to requirements traceability to make sure it is up-to-date. Make sure your sequence diagrams are consistent with the design changes introduced in project 8 and 9.

If needed, review the Integration Testing section of the Testing Requirements document.

Once your sequence diagrams are fully up-to-date, you will update your current integration tests and create new integration tests for any additional sequence diagrams that you created for the fast elevator design. If you have been keeping up with your issue log, it should be easy for you to use it to identify which integration tests need to be created or updated. You should also make sure that the the traceability comments in all your integration tests are complete and up-to-date.

When updating your integration tests, make sure you use the new CAN IDs and translators required by changes related to the new CAN network schedule. The technical notes page contains a script that can replace the old CAN IDs with the new ones in all your test files with one command.

Update your Integration Test Summary File with the new integration tests. Use the verification script to ensure that the summary file is correct and complete.

When you have completed this part of the project, you should have at least one integration test for every sequence diagram. Have someone other than the test author complete a peer review of the updated tests and update the peer review section of the Peer Review Log. For this project you must perform at least 4 formal peer reviews and log them although it is encouraged for you to do more if necessary. Remember any peer reviews that result in unfixed issues, should be added to the Issue Log.

Execute your integration tests and record the results in the Integration Test Log. Note that you do not need to specify the "-b 200" flag for integration tests. Each test must be syntactically valid (generate no Java runtime errors when executed against your code), but you are not required to pass Integration tests for this project. You will need to pass these tests next week, so don't blow this part of the project off.

2.3. Execute Acceptance Tests

You will re-run your acceptance tests (and some new ones) with the new network schedule and the bandwidth limitation of 200,000 bits/s.

Execute the following tests (make sure you use the "-b 200" command line option) and record the results in your Acceptance Test Log:

You do NOT need to pass these tests (deliver all passengers), but the tests must be able to be run. There must be no java runtime errors when running acceptance tests (especially those related to the network schedule).

You must have an up to date Acceptance Test Log entry for each test, including a detailed description of the outstanding design issues for any tests that do not deliver all passengers.

Team Design Portfolio

The portfolio you submit should contain the most up-to-date design package for your elevator system organized and formatted according to the portfolio guidelines. You are going to update your portfolio every week, so be sure to keep an up to date working copy.

Ensure your design portfolio is complete and consistent.

The following is a partial list of the characteristics your portfolio should exhibit:

Changes requested by the TAs in previous projects have been applied.
All required documents are complete and up-to-date to the extent required by the projects (you do not need to update files or links related to future projects).
All documents include group # and member names at the top of the document. (This includes code, where this information should appear in the header field)
Individual documents have a uniform appearance (i.e., don't look like they were written by 4 individual people and then pieced together)
The issue log is up to date and detailed enough to track changes to the project.

Handing In Results

Each team shall submit exactly one copy of the assignment.
Follow the handin instructions detailed in the Project FAQ to submit your portfolio into the afs handin directory (/afs/ece/class/ece649/Public/handin/project10/group#/ontime/).
Be sure you follow the required format for the directory structure of the portfolio and its location in the handin directories.
Be sure to follow ALL the portfolio guidelines detailed in the Portfolio Layout page.
Any submission that contains files with modification dates after the project deadline will be considered late and subject to a grade deduction (see course policy page for more information).

Grading Criteria:

This project counts as one team grade. Points are assigned as follows. A detailed grading rubric is available here.

This project assignment is worth 115 points:

10 points for the message dictionary table
20 points for the network schedule analysis table
5 points for completed excel network schedule
10 points for comparison of theoretical / simulation bandwidth results
15 points for successfully completing all unit tests (all tests must pass)
15 points for running all integration tests (tests must be valid and complete, but need not to pass all assertions)
15 points for running all acceptance tests and documenting test results
20 points for 4 peer reviews of updated or newly created integration tests
5 points for an entry in the Improvements Log that tells us what can be improved about this project. If you encountered any minor bugs that we haven't already addressed, please mention them so we can fix them. If you have no suggestions, say so in your entry for this project.

NOTE: For Fall 2011 use "-b 200"

Back to course home page