Please submit all project-related correspondence to

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 remaining 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.  Your 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:

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.

1. The columns must be in the order listed above
2. 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.
3. 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).
   
4. 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:

1. The columns must be in the order listed above.
2. Each message (row) listed in the Message Dictionary table must also appear in this table, and the rows must be in the same order. 
3. The values in the underlined columns also appear in the Message Dictionary table.  The two tables must have the consistent values for these columns.
4. 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.
5. 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.

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 reduced the "wasted" bandwidth from 31 bits to 7 bits.  If the controller in question 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 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.

Assignment:

This assignment has several parts:  network scheduling, the next runtime monitor, and more testing of your design.

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.  Note that the tables are on separate sheets in the same xls workbook. 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 hand in 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 able to be opened on the lab machines

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.  Use the utilization and the network bandwidth to compute the actual number of bits/s used by the controllers in your design.  It is okay to trigger the emergency brake during these tests, however (other than the exception thrown by the emergency brake) there must be no java runtime errors when running acceptance tests, especially those related to the network schedule (see below for details on what those look like).
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?

• 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 your 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. Write a Monitor

3.  More Testing

3.1  Complete Unit Testing

3.2  Write and Execute Integration Tests

4. Peer review

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.

• 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 assignment is worth 120 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
  
• 10 points for the RT-9 requirement monitor
  
• 15 points for successfully completing all unit tests (all tests must pass)
  
• 30 points for writing and running integration tests (tests must be valid and complete, but need not to pass all assertions)
• 15 points for the peer reviews of updated or newly created integration tests. Each team member must complete at least one peer review.
  
• 10 points for the peer reviews of the network schedule and message dictionary.
  
• 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.

Back to course home page