traffic @
backups | data | logs | language | plugins
public_html | sql | system

Last changed @ 04-12-07 13:32:14

A Modest Proposal

A lightweight alternative to NTCIP

NTCIP, for those who aren't aware of it, is the National Transportation Communication for ITS Protocol, where ITS stands for "Intelligent Traffic Systems". The purpose of NTCIP is to provide a standard communication protocol for roadside devices such as message signs, detector stations, intersection controllers, and so forth. It also addresses some higher-level infrastructural issues, such as data transfer between different traffic-control centers, or between government agencies that require access to traffic data. However, my focus on this page will be the roadside-device aspect.

I have been working with the various NTCIP standards, and participating in their development, for a number of years. While NTCIP is a prodigious effort that wouldn't be where it is today without the hard work of a great many people, I feel that the NTCIP standards as they now exist are unsuitable for a number of important ITS applications.

Purely as an intellectual exercise, I've decided to develop an alternative to the NTCIP base protocol standards. I shall strive to keep it utterly simple for humans to understand and for machines to execute. I shall also attempt to achieve application-level compatibility with existing NTCIP field-device standards, in the following sense: for any message a central system might exchange with a field device using SNMP, an equivalent message shall be possible using my new protocol, and the semantics of that interaction will be the same in each case. That's going to be much harder to achieve than basic functionality and simplicity, but I believe it can be done.

Justification

Almost without exception, municipal ITS systems use some variant of a centralized server architecture. Typically, a "server" machine runs some high-level management software, which communicates with roadside devices in order to monitor their status and co-ordinate their activity. For some kinds of devices, such as intersection controllers, it's important that a "request for status information" be successfully processed very frequently, on the order of once per second, for each device. For other kinds of devices, status polls may be conducted much less frequently, perhaps on the order of once per minute. But you can see that communication bandwidth is a serious concern.

Very often, the communication media used to talk to the roadside devices is something on the order of copper wire, using a 9600bps serial multidrop architecture with four to sixteen devices per channel. That means each device gets around 2Kbps or less, perhaps as little as .5Kbps, under perfect communication conditions. That's OK, because a typical roadside device has only a few tens of bytes of status data that we're really interested in, and only perhaps 20KB of remotely-accessible data total.

The folks involved in the NTCIP effort chose to use a "commodity" application-layer protocol as the basis of the standardization effort, which is a reasonable decision. However, the protocol they chose was SNMP (that is, the Simple Network Management Protocol, one of the most stunning examples of ironic naming I'm familiar with). In view of the bandwidth numbers discussed above, this choice is nothing short of mystifying. SNMP is an extremely verbose, and one might even say garrulous, protocol, with lots and lots (and lots) of redundant redundancy. A friend of mine once calculated that each byte of actual device data transferred via SNMP required on the order of 20 (twenty!) bytes of protocol overhead.

One can only presume that the folks who chose SNMP as a base standard imagined that consumers of ITS infrastructure (that is, municipal governments) would be rushing out to replace all of their existing copper with SONET rings or some other high-bandwidth communication medium. But the fact is, almost no one wants to do this, since the costs involved in such a retooling are enormous. Therefore, the NTCIP base protocol has a number of variations intended to address the bandwidth problem. These variations go by names such as the Simple Traffic Managment Protocol (a data-aggregation protocol layered atop SNMP) and Octet Encoding Rules (an ASN.1 encoding discipline that's supposed to be simpler than the Basic Encoding Rules used by SNMP). All of them are (IMO) overly complex, and don't fully address the need to support legacy communication infrastructure.

The goal of this effort, then, is to design an application-layer protocol for ITS, suitable for use with legacy communication infrastructure, starting from first principles.

We don't need to separate syntax from encoding

SNMP is specified in terms of Abstract Syntax Notation.1, or ASN.1. The idea behind ASN.1 is that one can specify the syntax of a message (that is, the names, types, and ordering of data items within the message) in once place, and specify the actual encoding of the message - the actual bytes that get put on the wire for any given message content - separately. One can buy (or build) compilers that accept ASN.1 and produce machine code (in some form) that implements the encoding and decoding rules for the messages defined by the ASN.1. (The encoding used by SNMP is known as the "Basic Encoding Rules", and these are responsible for much of SNMP's verbosity.) ASN.1 is not trivial to understand and use, and the tools that permit developers to make effective use of ASN.1 are usually proprietary and expensive.

When would you really need to separate syntax from encoding? The obvious answer is, "When you anticipate a need to vary those aspects independently". That is, you anticipate that either at a forseeable time in the future, or perhaps on a regular basis, you'll want to change the actual representation of the protocol's messages as they appear on the wire (and therefore, change the encoding and decoding logic within each device that participates in the protocol), without changing the content of the messages. (Obviously, if you change the message syntax the encoding must change, so there's only one way these aspects can vary independently.) It's hard to see why anyone would want to do this at all, but it's especially hard to see why anyone would want to do it in an ITS application, where changing the protocol encoding would likely require physical maintenance of hundreds or thousands of hard-to-reach roadside devices.

The other reason one might want to separate syntax from encoding is to think about them separately. That's a much better reason, and if you had a need to define different kinds of messages on a regular basis and integrate them into your protocol, it would make a lot of sense. But the requirements for NTCIP don't imply such a need. In fact, the very choice of SNMP as a base protocol implies that the message types are going to be limited to the very small set supported by SNMP. Therefore, all of the ASN.1 machinery is redundant and unnecessary.

We don' need no steenkin' TLVs

Now let's proceed to physical protocol issues.

SNMP, by virtue of its choice of ASN.1 and the Basic Encoding Rules, uses a "Type/Length/Value" encoding for essentially every part of a message. So when an SNMP agent wants to say, "3", the message that actually goes on the wire is something like, "This is an integer, it's one byte long, and its value is 3". Saying all that takes a minimum of two additional overhead bytes beyond the actual value being transferred, and that cost is paid on every value in every message that goes across the wire.

That's just a wonderful idea if you have no a priori notion about what kind of data you'll be shipping around in any particular message. When you do have such knowledge, it's a collossal waste of bandwidth.

In traffic applications, we're always going to be sending one of three kinds of data:

  • Integers. These may come in any number of bytes that is an even power of two, though magnitudes greater than four bytes are very rare. Such values could be represented as multiple integer objects, when they occur.
  • Arbitrary byte seqences. Usually these will have some internal structure, but from a communication standpoint, they're just binary sequences.
  • Printable strings. Arguably, these are a subset of "Arbitrary byte sequences", but there are encoding issues with printable text that don't arise with binary data, so it may be important to treat them separately.
Furthermore, if we design our protocol in the appropriate manner (eg so simple a child could understand it), then in every case, we'll know what kind of data to expect up front. So the type data is totally redundant, and therefore totally worthless.

As for length, well, we've pretty much said it all in that regard, too. We can specify the protocol in such a way that we'll always know what size of integer to expect at any particular point in a message, so the length data is totally redundant and useless for integer fields.

Strings are different. We'll generally have to specify a length when sending a string, so let's just assume that we'll always send a length. Let's further assume (this being first and foremost a simple specification) that we'll always encode the length of a printable or binary string as a 16-bit value at the beginning of the string. This may cost us a few extra bytes when sending around lots of short strings, but it does have the advantage of being so simple a child could understand it (henceforth abbreviated SSACCUI).

How about the value? Let's just assume we always encode the value when sending data, and we never encode the value when requesting data. That is, there are to be no optional fields anywhere, but values will only be sent when they actually need to be sent.

That about does it for the encoding of basic data items.

We still need OIDs, though.

An OID, or "object identifier", is a value whose purpose is to uniquely identify a particular data item. There are no commands in SNMP other than "read a data item's value from a device" and "write a data item's value to a device". Behavior that would be implemented as "action" commands in other protocols is instead implemented as a data item whose value, when changed, causes the device to take a particular action. This "transfer-triggered" design is quite nice from the perspective of the communication protocol, because it means that the communication protocol itself is divorced from the kind of device being controlled. That's a sharp contrast to most existing (proprietary) traffic-device control protocols, in which every kind of action one might want to instruct the device to take is typically implemented as a different packet type.

I like the general idea of being concerned only with "data items" (their identities and values) at the protocol level. We'll also have to define the meaning of each data item, but that's a different problem, to be handled elsewhere.

So, we do need OIDs. But do they really need to be encoded as fifteen- or twenty-byte values, with a type and a length tacked on just 'cause they look pretty? That's what SNMP does. It uses a field of something like 2^120 possible values to express OIDs, when the OIDs in question are being used to discriminate between something in the general neighborhood of 2^10 different data items. We'll try to come up with something a bit lighter-weight.

It would be nice to use some kind of integer as our OID analog. Given that there are rarely, if ever, more than a couple of hundred semantically distinct data items in a given device, two bytes ought to be more than enough namespace to identify an item within a particular device, so let's go with that. (Note that words "semantically distinct" in the previous sentence. There might be multiple instances of a particular data item, which we'll deal with using an indexing scheme, described below.)

There are some other things we'd like to know about a data item. Among them:

  • With what sort of device is this data item associated? (Intersection controller, message sign, etc.)
  • Is this data item a standard data item, or is it a custom item added by the device's manufacturer for some proprietary purpose?
Finally, we'd like to have a simple and not-too-verbose way to identify related groups of data items.

General format of an ATCIP packet

In general, an Alternative Transportation Communication for ITS Protocol packet looks like this:
  1. IPI: one byte, value 0xAC. (Well, I gotta pick something.)
  2. Message type: one byte, whose value is one of the following:
    • 1: Request to read data from the device.
    • 2: Request to write data to the device.
    • 3: Request to write data, and whether this attempt succeeds or not, read the data back from the device.
    • 5: Response to a successful read (1) request.
    • 6: Response to a successful write (2) request.
    • 7: Response to a successful write/readback (3) request.
    • 13: Write response with error data.
    • 14: Read response with error data.
    • 15: Write/readback response with error data.
    Note that this byte also permits a bitmask interpretation, based on the values given above:
    • Bit 0 (IS_READ): The message is a read request, or a response to a read.
    • Bit 1 (IS_WRITE): The message is a write request, or a response to a write.
    • Bit 2 (IS_RESPONSE): If 0, the message is passing from the control station to the device; if 1, the message is a response from the device to the control station.
    • Bit 3 (HAS_ERRORDATA): The message contains error data.
    Nevertheless, only the given values are valid for the message type byte. For example, 4 is not a valid value for message type - it would indicate a response to a request that was neither a read nor a write request. (It's possible additional message-type values may be defined in a future revision of the protocol.)
  3. One byte, containing the number of object selector / data groups present in the packet. May be 0 if no data is being transferred or requested (for example, a successful response to a "write" request).
  4. Object selector / data groups : Each group contains an object selector (described below), and, if the message type is 2, 3, 5, or 7, a number of bytes of data. The encoding of the data following each object selector depends on the data type of the selected data item, and is described in detail below.
  5. One byte, containing the number of object selector / error groups present in the packet. This field is present only if bit 3 is set in the message type.
  6. Object selector / error groups : these are present only if bits 3 is set in the message type. It consists of one or more unique (UA bit == 0; see below) object selector/error code groups, each indicating the identity of a data item that could not be read or written, and the nature of the error encountered. The error is encoded as one byte after the object selector, with the bits of the error code having the following interpretations:
    • Bit 0: Could not read selected data item.
    • Bit 1: Could not write selected data item.
    • Bit 2: Item does not exist.
    • Bit 3: Table index out of range.
    • Bit 4: Requested value out of range (for write requests).
    • Bit 5: The device could not process the data in a write request, for some implementation-specific reason.

Object selectors: format and indexing

Skrrch (sound of rubber meeting road). Here I'll describe the basic format of an "object selector" at the bits-and-bytes level. An "object selector" is the moral equivalent of one or more OIDs in SNMP. We'll worry later on about how to associate object selector values with particular application-level data items.

Bit76543210
Byte 3 SP UA Device Type Identifier
2 Reserved NI = number of indices
1 High-order byte of starting object identifier
0 Low-order byte of starting object identifier
(optional) 1 Iff UA == 1: High-order byte of ending object identifier
(optional) 0 Iff UA == 1: Low-order byte of ending object identifier
..... Indexing data.
(Highest-order bit is at the top left of the figure.)

The meaning of this structure is as follows:

  • The SP bit indicates whether the indicated OIDs are standard or proprietary; if set, the OID is proprietary, and all parties involved in communicating values of the OID must somehow know what it means to the device. A manufacturer is free to assign proprietary OIDs in any way she pleases, and make them mean anything she wants. In contrast, standard OIDs have standard meanings defined for all devices of a particular type.
  • The UA bit indicated whether this object selector is identifying a unique data item or an aggregate group of data items. It changes the interpretation of the data following the "starting OID".
  • The device-type identifier partitions the OID namespace according to device type. All of the objects selected by a particular obejct selector must belong to the same device type. However, it's possible for a single device to implement OIDs from different device types. A single device may be both a sign controller and an environmental data collection station, for example. Standard OID 1 would denote a semantically distinct data item in each case.
  • The reserved bits are a CYA mechanism :-)
  • The NI field indicates the number of index values following the base object selector. This data is not really necessary for interpreting the packet (since the number of indexes needed to identify any particular data item is implicit in the item's object identifier), but it is handy for identifying the end of the object selector and the beginning of the actual data, when data is being sent.
  • The first object identifier is the identifier of the first data item to fetch.
  • The last object identifier is the identifier of the last data item to fetch, when UA == 1.
  • The index data consists of one or more 16-bit table indices. All data items identified by a particular object selector must accept the same number of table indices - that is, they must all be members of tables (arrays) of the same dimensionality. Unless one is being unnecessarily clever, they would normally all be members of the same table, or they would all be singleton data items, not members of any table.
When the UA bit is set, it means that:
  1. The last object identifier value will appear in the selector - that is, the selector specifies an inclusive range of data item identifiers; and
  2. Each index value following the base object selector will likewise be expanded to define a range of indices: each index will be represented by four bytes, the first two of which define the starting index of the table for the associated table dimension, and the last two of which define the ending index for the associated table dimension.
So the UA bit enables us to select a block of data items from a table (or a sequence of singleton data items, when no indexes are present). Note that it is permissible for the last object identifier to be equal to the first object identifier, and for the first and last indexes along any particular table dimension to be equal. That means that an aggregate object selector can be used to identify a single data item (though it would be more efficient to use a unique selector to do that), or to identify a slice of table data. The only restriction on the objects that can be selected by an aggregate object selector is that they must all be contiguous in the OID namespace.

Object selector examples

Let's assume we have a bunch of data items defined for an intersection controller. Among them are the following:
  • CoordMaximumMode
    • Standard/Proprietary: standard
    • Description: Coordination mode
    • Indices: None (singleton)
    • Syntax: enumeration w/values:
      1. Other
      2. Maximim 1
      3. Maximum 2
      4. Maxinhibit
    • Object identifier: 1
  • EnabledPhases
    • Standard/Proprietary: proprietary
    • Description: Bitmask of enabled phases
    • Indices: None (singleton)
    • Syntax: Integer (bitmask), range [0..65535]
    • Object identifier: 1
  • ControllerName
    • Standard/Proprietary: proprietary
    • Description: Name of this controller
    • Indices: None (singleton)
    • Syntax: String, size [0..32]
    • Object identifier: 2
  • Phase Table
    • Indices:
      1. Phase number, range [1..16]
    • Columns:
      1. PhaseMinimumGreen
        • Standard/Proprietary: standard
        • Description: Phase minimum green time (1/10 sec)
        • Syntax: Integer, range [1..255]
        • Object identifier: 2
      2. PhaseMaximum1
        • Standard/Proprietary: standard
        • Description: Phase maximum 1 time (1/10 sec)
        • Indices:
          1. Phase number, range [1..16]
        • Syntax: Integer, range [1..255]
        • Object identifier: 3
      3. PhaseMaximum2
        • Standard/Proprietary: standard
        • Description: Phase maximum 2 time (1/10 sec)
        • Indices:
          1. Phase number, range [1..16]
        • Syntax: Integer, range [1..255]
        • Object identifier: 4
      4. PhaseOptions
        • Standard/Proprietary: standard
        • Description: Phase option bitmask (1/10 sec)
        • Indices:
          1. Phase number, range [1..16]
        • Syntax: Integer, range [1..65535]
        • Object identifier: 5
Let us assume that the "device type" value for intersection controllers is 4.

We can then refer to CoordMaximumMode using the unique object selector: 

0x04 0x00 0x00 0x01
This says:
  • 0x04 = standard object, unique, device type 4
  • 0x00 = no index data
  • 0x00 0x01 = 0bject identifier 1

We can refer to the ControllerName of the controller using the unique object selector: 

0x84 0x00 0x00 0x02
This says:
  • 0x84 = proprietary object, unique, device type 4
  • 0x00 = no index data
  • 0x00 0x02 = 0bject identifier 2

We can refer to the PhaseMinimumGreen for phase 3 using the unique object selector: 

0x04 0x01 0x00 0x02 0x00 0x03
This says:
  • 0x04 = standard object, unique, device type 4
  • 0x01 = 1 index value will follow the main selector
  • 0x00 0x02 = object identifier 2
  • 0x00 0x03 = first (and only) index (phase number) == 3

We can refer to all the PhaseMinimumGreen data for phases 1 thru 8 using the aggregate object selector: 

0x44 0x01 0x00 0x02 0x00 0x02 0x00 0x01 0x00 0x08
This says:
  • 0x44 = standard object, aggregate, device type 4
  • 0x01 = 1 index value will follow the main selector (while there are actually two 16-bit index values, they apply to the same index -- phase number)
  • 0x00 0x02 = first object identifier = 2
  • 0x00 0x02 = second object identifier = 2
  • 0x00 0x01 = first (and only) index (phase number), starting value == 1
  • 0x00 0x08 = first (and only) index (phase number), ending value == 8

We can refer to all the phase data other than minimum green (maximum 1, maximum 2, and options) for phases 9 thru 16 using the aggregate object selector: 

0x44 0x01 0x00 0x03 0x00 0x05 0x00 0x09 0x00 0x10
This says:
  • 0x44 = standard object, aggregate, device type 4
  • 0x01 = 1 index value will follow the main selector
  • 0x00 0x03 = first object identifier = 3
  • 0x00 0x05 = second object identifier = 5
  • 0x00 0x09 = first (and only) index (phase number), starting value == 9
  • 0x00 0x10 = first (and only) index (phase number), ending value == 16

You may notice that there are still quite a few apparently wasted byted here. For example, the table indexes we've looked at so far would always fit in a single byte, and that is typical for traffic-device data. However, it occasionally happens that table indexes get larger than 255, and I want to be able to deal with that possibility without violating the SSACCUI principle. I do not, however, anticipate table indices greater than 65535. Perhaps this is shortsighted of me, but after ten years of working in the ITS industry (most of that time spent writing code to control various traffic devices), I see no evidence that this will be a problem.

Encoding the data selected by an object selector

We've already discussed value encodings in a general way, above. Here we'll make the encoding completely explicit. The encoding rules are as follows:

  1. Data shall be encoded following each object selector whenever the message type is 2, 3, 5, or 7.
  2. Basic data types will be encoded in the following manner:
    • Any integer data item shall be encoded as the smallest number of signed two's-complement bytes that both can contain the item's full range, and is a power of two. The meta-data for the data item must specify the item's range; this protocol does not permit arbitrary integer ranges (as does BER). However, since arbitrary-magnitude integer data is a (theoretical) reality in existing NTCIP device metadata specifications (MIBs), any integer data item whose range is not specified in the device meta-data shall be encoded as an eight-byte value (note, this is overkill). Higher-order bytes shall be transmitted first.
    • Any binary string data item shall be encoded as a two-byte length (high-order byte first), followed by a number of bytes of data equal to that length.
    • Printable string data items shall be encoded in exactly the same manner as binary strings. The meta-data for each printable-string data item must specify the encoding (ASCII, UTF-8, etc) used by the string; if this meta-data is not available, ASCII encoding shall be assumed.
  3. When an object selector's UA bit is 0 (that is, a unique data item is being selected), the value of the selected data item shall be encoded immediately following the object selector.
  4. When an object selector's UA bit is 1 (that is, an aggregate of data items is being selected), then all of the data items selected by the object selector shall be encoded starting immediately after the object selector. The items shall be encoded in OID-minor order - that is, the OID value should vary fastest, followed by the first index value, then the second index value, and so forth.

Examples of data encoding

We'll use the object selector examples from above, and show how the object selectors and their data would be encoded.

...to be continued...

Last changed @ 12-04-03 02:04:42

Desirable features of a modern ATMS

In no particular order, and at widely varying levels of abstraction:
  • Channels:
    • A channel is merely a pipe for delivering commands/responses/requests/data.
    • Channels may have layers (as in streams).
    • Any device can be assigned to any channel. That is, we should be able to serve DMS and intersection controllers (or whatever) on the same channel, if the wire protocol permits this.
    • Channel deals with comm scheduling issues.
    • One server process per channel.
    • Logically, a channel is two streams of data packets, one outgoing and one incoming. We should be able to attach generators and filters to a channel in order to
      1. Distribute response packets to their proper handlers.
      2. Automate some channel activity at a low level - polling, for example, ought to be done in a generalized way in the channel process itself.
    • Must handle full-duplex multidrop comm.
    • Connection-oriented channels are probably a different channel implementation. Dialup, for example, doesn't really have much in common with full-duplex multidrop.
  • Devices:
    • Each device object knows how to process device-specific abstract commands.
    • Attaches addressing data to commands for connection-oriented channels.
    • Converts commands to wire protocol for submission to channel; converts wire-protocol responses to abstract responses.
    • Can describe itself and the commands it accepts to the UI server.
    • Can attach a "poller" to a channel, and thereby avoid having to explicitly poll. Channel can deliver all poll responses, or only those that differ from the previous.
    • Protocol libraries convert abstract commands to wire protocol. Initially should support NTCIP, with legacy protocols as time permits.
    • Provide complete management of device state, via database upload/download, and do this in a generic manner.
  • UI:
    • Browser-based.
    • Javascript for better realtime response? (But really strive to be browser-neutral.)
    • Perhaps SVG for status displays and animation.
  • High-level services:
    • Intersection control:
      • Monitor status.
      • Permit timing plan selection and control.
    • Signs:
      • Message composition.
      • Immediate display on selected devices.
      • Schedulable messages.
      • Other schedulable commands (DB upload/download, tests).
    • Ramp meters:
    • Sensor stations:
    • Incident management:
      • Detection (via detectors/sensor stations).
      • "Detection" via human intervention.
      • Plans - a collection of device commands to be used to address an incident at a particular location (or a region).
      • Respond automatically with the "most appropriate" plan, when one or more plans address the incident area.
      • Generate plans in response to incidents in other areas?
      • Avoid conflicting plan implementations.
    • Interaction with law enforcement, emergency management, etc:
    • Interaction with other traffic-management jurisdictions:
    • Managability:
  • Global:
    • Any subsystem can report its status using an efficient API.
    • Subsystems are black-boxes accessed via simple IPC mechanisms, like eg UDP or perhaps SOAP. Simple protocols like UDP and TCP have the advantage that they don't create a build-time dependency between subsystems. I'm not sure about SOAP/XML-RPC, but I know that Java's RMI and CORBA can both lead to dependency hell. (Actually, Erlang is probably a very appropriate implementation language.)
  • General principles:
    • Source available - preferably open.
    • Total transparency and auditability.
    • Built on commodity hardware and open-source platforms and toolsets.
    • Use the best tools available for the job. That means, for example, no Java, probably no C++.
      • C or Forth for low-level, realtime stuff (field comm).
      • Very high-level, dynamic code for UI and glue - maybe a Lisp dialect, or something functional and realtime-ish like Erlang, but at least something as capable as Python (1st-class functions, lexical closures, high interactivity).
      • Specialty tools for things that can benefit from them - Prolog for incident management, for example.

Last changed @ 10-20-03 09:07:46

NTCIP Alternative (ATCIP) meta-data specification

This page will describe a simple way of expressing metadata about the data items transferred using the Alternative TCIP protocol. Basically, this will be a simple line-oriented, block-structured format, trivial to understand and parse.

I'll also describe a simple way of transforming existing NTCIP MIBs into the ATCIP metadata format, including the assignment of ATCIP OIDs to NTCIP data items. The essentials of this transformation are:

  • Only items that are actually transferrable (that is, those whose accessibility is "read-only" or "read-write") are assigned an OID.
  • Starting at the beginning of the MIB and proceeding to the end, assign the next OID value to each accessible data item (OBJECT-TYPE) as it is encountered, starting with 1 for the first OID.