18-540 Fall 2000

Homework 6

Due: Tuesday 10/24, 4:00 PM in HH D-204

Consider a JCSMA/CA protocol. This protocol uses a jam to restart an idle network. There is a single frame gap of 350 nsec after each message (also after each jam), with that frame gap followed by a CSMA/CA slot progression. There is a set of three fixed-priority slots (#0,1,2 - #0 is first, assigned by message type rather than node number) followed immediately by four rotating slots (#0.. #3 - each node has exactly one slot assigned by node number starting with a slot one higher than the node number transmitting). If no message is transmitted in the priority slots plus one rotation of the rotating slots, the bus goes idle. A jam is implicitly treated as having being equivalent to a message from node #0 for slot rotation and message gap purposes, although it carries no data. The raw bit rate for this network is 4 Mbits/sec.

• 1) Sketch a picture of the slot rotation after a priority #1 message is transmitted from node #2, numbering each slot position and the "token" field at the end of the message. Assume there is no message transmitted on the bus during the slots. The horizontal axis should be time; but just sketch the sequence -- don't worry about labeling the exact times in your sketch.
• 2) Compute the time from the end of a message to the end of the last possible slot (i.e., time from end of message to bus going idle):
  • Propagation delay (t_pd) is 100 nanoseconds
  • Each node is able to assert a signal in its designated slot with zero latency after it "thinks" it is time to assert its signal.
  • Each node requires 90 nsec of a steady signal reception within a slot beyond the 2 t_pd minimum "flight time" for receiving, sampling, and reacting to a signal in a slot. (In other words, if the slot is taken by a transmitter, that transmitter's signal must be asserted 90 nsec before the end of the slot in addition to the 2 t_pd minimum slot width; this tells you how long slots have to be.)
  • Precision of the oscillators is perfect. But of course nodes are still not perfectly synchronized because of effects related to t_pd
• 3) Assume that all messages are exactly 100 bits long. Assume that two messages arrive on the network simultaneously on two different nodes and that the network is idle. What is the worst-case latency until the last bit of the second message is delivered? Assume that:
  • A "jam" signal lasts for 10 bit times.
  • Messages begin exactly 150 nsec into slot times according to some global clock (i.e., we're not going to do the details of global/distributed time, although that would matter in real life)
  • Note that t_pd is small enough that you can just ignore it for this problem
• 4) What is the best-case steady-state utilization, in percent of data bits compared to raw bandwidth available, of this network (transmitted message bits/second)? Assume that 64 data bits are delivered per 100-bit message.
• 5) What is the worst-case steady-state utilization under the same assumptions as question #4, and assuming that there is always a message queued (i.e., the network never goes idle, and all messages are delivered error-free)?

• 6) Suppose that you had a message workload that was the following. Assume zero jitter for periodic messages and perfect precision/synchronization/offset. This means that all the periodic messages are queued at exactly time 0, and exactly every period thereafter. Assume that exponential messages cannot re-occur any faster than their stated deadlines (e.g., a deadline of 15 msec means that pairs of that particular exponential message can't be generated closer than 15 msec apart).

  Message Name	Transmit Node	Priority	Distribution	Mean Period	Deadline
  A	3	0	Periodic	100 microsec	100 microsec
  B	2	1	Exponential	3 msec	100 microsec
  C	1	Rotating	Periodic	6 msec	6 msec
  D	0	Rotating	Periodic	6 msec	3 msec
  E	2	Rotating	Periodic	12 msec	12 msec

  We're going to operate at a higher level of abstraction for this question. Don't worry about the time it takes for slots - just assume every message delay is the same length of 30 microseconds as a hand-waving, but conservative approximation.

  6a) What is the worst-case delay for completing transmission of Message A?

  6b) What is the worst-case delay for message type E?

  6c) What is the worst-case percentage loading this network will experience? (ie. over a period of 12 msec)

Home page