Intra-Vehicular LAN and Method of Routing Messages Along It Using Hash Functions

The present invention relates to message routing within local area networks (LANs) and, more particularly, to the use of hash functions for table lookups by microcontroller modules connected to an intra-vehicular local area network.

In automated factories and other similar environments, it has been found that an efficient method of operating involves distribution of the control functions throughout the environment. This is achieved by utilizing a plurality of remotely located microcomputers that are programmed to handle special functions. In order to coordinate the operation, the microcomputers are connected together over a local area network ("LAN") and one or more supervisory microcomputers may also be connected to the LAN. An example of such a system for use in an automated factory is disclosed in U.S. Pat. No. 4,972,367 of Burke. In this patent there is recognized the problem of reduced performance because of the necessity to transmit numerous messages over the LAN.

Microcontroller modules within a vehicle typically perform many tasks, such as controlling the engine, producing chimes, monitoring various vehicular functions, producing audible messages, etc. Many of these microcontroller modules must communicate with other microcontroller modules within the vehicle. For example, a first microcontroller may recognize a problem, such as low oil pressure, and may need to communicate the existence of the problem to a second microcontroller module that controls the production of audible messages to the driver. Upon receipt of the information, the second microcontroller module produces the audible message.

The need for communication between the microcontroller modules within a vehicle has lead to the introduction of intra-vehicular LANs that provide the microcontroller modules located throughout a vehicle with the means to communicate with each other. As a result, each of the microcontroller modules within the network is required to determine which of the many messages broadcast on the LAN must be acted upon by it.

Whether the LAN is in a factory, a vehicle or other environment, there is a need to overcome the problems of communication between the microcontrollers over the LAN. One method of accomplishing this is to tag the broadcast message with a microcontroller destination address or identifier. In that case, microcontrollers on the LAN examine each incoming message, compare its address with that which was tagged to the message and immediately determine whether the message was meant for it. This scheme, however, does not provide for the case where one message must be acted upon by more than one microcontroller. Further, it is not very flexible. For example, if a function is moved from one microcontroller to another, all the microcontrollers broadcasting messages relating to that function must be modified.

In addition, an address system requires a great deal of computer overhead. For example, a microcontroller that detects a vehicle operating problem must also be programmed to know the appropriate response and the address of the other microcontrollers that need to execute the response. A system with such a heavy overhead is described in U.S. Pat. No. 5,117,458 of Takaragi et al.

To provide a more flexible system with smaller computer overhead, the messages can be tagged with message identifiers (IDs) which identify the message rather than the destination microcontroller. Such a technique is disclosed in U.S. Pat. No. 5,095,480 of Fenner. With this arrangement each microcontroller on the LAN must search a table it maintains which contains all IDs that it must respond to in order to determine if the message is for it. Further, the table may also contain other parameters necessary to properly respond to a particular message. Typically, a microcontroller module will have to respond to more than one type of message with different parameter requirements.

The introduction into motor vehicles of vehicle multiplex networks has resulted in the need for these modules using the network to do a lot of table lookups. The primary need is to find the messages and determine the parameters of the message and locate information how to process the message. Another reason for the table lookups is to process diagnostic requests which often ask for parameter information by means of a parameter ID. Again a table is consulted to find the location of the parameter, its scaling, etc. This increased use of table lookups, especially during the handling of normal multiplex network traffic, means that a non-trivial fraction of a microprocessor's time can be spent doing table lookups. If there were a way to perform these table lookups more quickly, then the microprocessor could spend its time doing more productive work, such as controlling an engine or transmission.

A common method of looking up information in a table is to search linearly. Message IDs and information are stored in a table, typically with the most frequently occurring message IDs stored in the beginning of the table. The entries are examined one by one until a match is found, or until the entire table has been searched and no match has been found. One problem associated with linear table searching is controller or processor overhead, i.e. the microcontroller is spending time performing searches rather than performing its primary job.

The overhead problem in a linear table search can be illustrated by considering a few examples. In the examples that follow the following assumptions are made. The lookup table will have four bytes per entry, one byte for the ID, one byte for the message length and two bytes for the address of the message service routine. The code samples are written in Motorola 68HC11 assembly language. For purposes of comparing execution times of different table look-up methods, the 68HC11 is assumed to be running at 8 MHz so a CPU cycle takes 0.5 microseconds. The tables will have the same information in them regardless of which lookup method is used, but may be ordered differently.

The table lookup code used in a typical vehicle controller is simple loop which compares the received ID with entries in a table. The IDs are typically placed in the table so that the highest frequency messages are located near the beginning of the table. Table 1 shows a typical implementation of a linear table lookup.

The table indicates the time required to process an ID. Note that the first 3 lines set up the loop and take 4 microseconds to execute. Lines 4-8 (8.5 microseconds) are executed once for every table entry that does not match the received ID until the entire table is checked. Thus the total time to process an ID which is not in the table is 4+8.5.times.(# table entries). For example, for 12 table entries it would be 106 microseconds. Some vehicle controllers have 20 IDs to receive so it would take them 174 microseconds, worst case, to process a received ID. That is a long time to be tied up for a real time controller.

A rough estimate of the percentage of the processor's time that can be wasted looking up ID's can be made. Assuming that the average message is three bytes long, that the LAN bit rate is 7812.5 bits per second and that the bus is busy 35% of the time, there will be about 68 messages per second transmitted on the bus. If 106 microseconds are used 68 times a second then the processor is spending over 0.7% of its time just sorting messages from the LAN. If 174 microseconds are used, the number becomes almost 1.2%. Note that these are worst case numbers. In reality, no module ignores all of the messages on the bus, so some of the IDs will be found in the table before the maximum time is used. In addition, a module will not have to process any messages that it transmits.

"Hashing" has been found to be an efficient means to search a table. With hashing an arithmetic function, or hash function, is used to create a key related to the message ID. If the hash function is applied to a received ID that has been hash coded, the result is a pointer into a table maintained for the microcomputer which indicates the section of the message. Methods of arriving at an appropriate hash function for a given application are well known. Examples of these methods are described in two papers, incorporated herein by reference: Jaeschke, G., Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions, Comm. ACM 24,12 (December 1981) 829-833; and Sprugnoli, R., Perfect Hashing Functions: A Single Probe Retrieving Method for Static Sets. Comm. ACM 20,11 (November 1977) 841-850.

The basic idea of hashing is to take the item you want to find in the table and perform some numerical computation (the hash function) on it to get a table address. Hash functions have been used since the earliest days of computers to perform table lookups. They have been used most often on mainframe computers for compilers and databases, and there is extensive literature on different ways to use them. But a mainframe is much different than a microcontroller: the memory for storing the tables is much larger, there are peripheral storage devices and the CPU has a full complement of fast, high precision arithmetic instructions. Furthermore, many existing hash functions are designed for dynamic systems, where items are being added and taken away from the table.

The present invention is directed to reducing microcomputer or microcontroller overhead for communication over a LAN, while still providing flexibility in the assignment of tasks in a distributed control environment. This purpose is achieved by using messages on the LAN that have static identifiers and having the microcontrollers detect their messages by using particular hash functions with local message tables.

In an illustrative embodiment of the present invention, a plurality of microcontrollers are connected together over a LAN and provide distributed control and operation of some environment, e.g. a factory or a motor vehicle. A microcontroller which has a message to report, or needs some service from another microcontroller, broadcasts a message on the LAN tagged with an identifier (ID) which identifies the contents of the message, rather than a destination address. Microcontrollers on the network are provided with read only memory (ROM) that contain a table of message IDs and accompanying data about how to respond to the message. Rather than linearly checking the table to see if the ID matches an ID in its table, the microcontroller applies a hash function to the ID, the result of which is a table address in the ROM. Thus, instead of searching the table for a matching ID, the hash function is applied and the results used as a pointer into the table. The microcontroller compares the message ID stored in that pointer location with the received message ID. If they are equal, the microcontroller performs the predetermined function. If the message IDs are not equal, the message is ignored.

In preferred embodiments, linear congruential, multiplicative XOR, linear congruential with XOR and reciprocal hashing functions are used with the microcomputers of an intra-vehicular LAN.

The foregoing and other features of the present invention will be more readily apparent from the following detailed description of preferred embodiments taken in conjunction with the accompanying drawings wherein:

FIG. 1 is a block diagram of the intra-vehicular LAN of the present invention;

FIG. 2 is a flowchart of a method of storing message identifiers using hash functions;

FIG. 3 is a flowchart of a method for determining whether a message should be acted upon; and

FIGS. 4-7 are a flowchart of a method for determining the parameter values for a Linear Congruential Hash function.

FIG. 1 illustrates microcontroller modules 10 on an intra-vehicular LAN 25. These microcontrollers individually control certain operations of the vehicle, e.g. engine operation or the reporting of certain conditions. As a result, the microcontrollers generate messages which may call for further operations of other microcontrollers or may merely report status. These output messages are not addressed to any particular microcontroller on the LAN, but are provided with messages IDs which indicate the type of message. It is then up to the other microcontrollers to determine if they are required to take some action based on the message. This is determined by the microcontroller checking to see if a message with this ID is stored in a table associated with the microcontroller. Each microcontroller 10 is provided with a static memory or ROM 5 which contains a table of messages. The messages are stored and retrieved in the tables in ROMs 5 using a hash function.

FIG. 2 is a flow chart of a preferred embodiment of a method of storing message identifiers, i.e. a hash function. The function, as illustrated, is a linear congruential hashing function wherein the hash function is in the following form:

where the numerical value of A and B depend on the IDs to be stored, the table size, and the table entry sizes. Table 2 is similar to Table 1 and shows how to use the hash function.

Lines 1-4 of Table 2 are implemented in a straightforward fashion, leaving the index bits in the upper part of register B. Line 5 extracts the index for a table with 16 entries and lines 6-7 move the index into the proper position to address a table with four byte entries. Lines 8-9 add the index to the beginning of the table. Finally, lines 10-12 compare the received ID with the table entry. If they match, then the message is processed according to the information in the table; if not, then the message can be ignored. It is necessary to compare the received ID with the ID in the table because the hash function is a many-to-one function. In this example, 256 possible IDs are mapped into a table of 16 entries so that several IDs will map into each table entry. However, only one of the IDs in the list of IDs received by the module will map into any given table entry.

There are no loops or branches in the code so it processes all IDs, regardless of whether they are in the table or not, in the same amount of time, i.e. 19.5 microseconds. This linear congruential hash function method becomes competitive with the prior art linear search method of Table 1 in terms of execution time when there are 2 or more entries in the table. For the 12 entry table discussed above, the congruential hash function method of the present invention is 5 times as fast as the linear table search of the prior art (i.e. Table 1).

To further illustrate the method, we assume a vehicle controller has 12 hexadecimal ("hex") IDs. The linear congruential hash function, wherein A=hex 5B and B=4 illustrates a perfect hash function for the following list of 12 IDs to be input:

If ID A4 is received by a microcontroller, it then is multiplied by 5B (resulting in hex 3A4C) and is added to get 3A5O. Line 5 of Table 2 eliminates everything but the highest four bits of the low byte of this product and the subsequent lines adjust the result to properly index a table of 4 byte entries. This is the same as extracting the second hexadecimal digit from the right which is 5 and using it as an offset into the table given above. Counting from 0, A4 is at entry five in the table. The other IDs also generate offsets using this formula, which is what is required for a perfect hash function; there are 12 IDs but the table is 16 entries long. Since 00 is an illegal ID, unused table entries are filled with 00.

It is always possible to find a perfect hash function given a large enough table; for example, if the IDs are 8 bits long then the ID can be used as an address in a 256 entry table. However, depending on the set of IDs for which a hash function is sought, there is no guarantee that a perfect hash function for a table of reasonable size will be found. Similarly, if there is a severe space constraint, it may be desirable to use a small table which does not contain all of the necessary IDs. In such cases, it is simple to have hard coded checks for the few IDs which do not work with the desired hash function. Still, the Linear Congruential hash function works remarkably well with ID lists from real world microcontroller applications.

Referring to the flowchart of FIG. 2, the implementation of Table 2 in software is illustrated. At step 21, an ID is loaded into a register. The register is next multiplied by hex 5B (Step 22) and 4 is added (Step 23). Next, the register is ANDed in Step 24 with hex F0, thereby retaining only the upper four bits or nibble of the low order byte. These bits represents the order number in which the ID should be stored, e.g. if the nibble is 5, the ID should be the sixth entry in the table (assuming the first entry is 0). Next, the offset from the beginning of the table must be calculated. Thus the nibble must be multiplied by the size of the entry, which is four bytes. Since at Step 24 the index is still in the upper nibble of the low order byte, the register is shifted right two bits in Step 25, instead of dividing by 16 then multiplying by four. However, it gives the same results. The register contents now contain the address offset from the beginning of the table where the ID and accompanying data should be stored.

Once the IDs are stored, a microprocessor can begin to examine message IDs broadcast on the LAN and determine whether it is required to react in response thereto. FIG. 3 is a flowchart illustrating how this determination is made. Each microprocessor examines the message ID broadcast on the network (Step 31). Next, the microprocessor applies the appropriate hash function to the ID (Step 32). Using the output of the function as an offset address, the microprocessor compares the received message ID to the message ID stored at that offset address (Step 33). If there is a match, the microprocessor performs the corresponding function (Step 34), otherwise the message is ignored (Step 35).

As Table 3 shows, the Linear Congruential Hashing Method is able to produce a minimal perfect hash function for one vehicle controller and near minimal perfect hash functions for other modules. The "All but 2 fitted" and "All but 1 fitted" columns show that sometimes a much smaller table can be used if all of the IDs are not handled via the hash function. In particular, a if table size of 27 is needed for a perfect hash function, a table size of only 18 is needed for a near perfect hash function which handles 16 of the 18 IDs.

The example code assumes that the table size is 16 and that the record size is a power of 2. These need to be generalized. For other table sizes which are a power of two, AND function can still be used to extract the index bits if the constant in line 5 of Table 2 is changed so that the number of bits extracted is log.sub.2 (table Size). For example, if the table size were 32 then the constant should be $F8. The case where the table size is not a power of two requires a little more code to handle, i.e. line 5 in Table 2 must be replaced with the following lines:

If the record size is not a power of two, then lines 6 and 7 of Table 2 must be replaced with the following lines:

In certain situations it may be possible to combine these two multiply operations by the step of multiplying once by the constant TblSize * RecSize.

These generalizations add instructions to the hash function. On the other hand, it may be possible to find a hash function which has one or more parameters which are zero. In those cases, the instructions which implement those parameters can be eliminated.

It will be understood by those skilled in the art that there are many known hash function other than those illustrated that can be utilized. Another known hash function is a Multiplicative exclusive OR ("XOR") function having the form:

where A represents the XOR operation. To code this function, simply replace the ADD instruction in line 4 of Table 2 with an XOR instruction. Table 5 shows the effectiveness of the Multiplicative XOR method.

Still another has function is called Linear Congruential with XOR. It combines the ideas from the first two functions. Its form is

where represents the XOR operation. To code this function, simply add the following instruction after line 4 of Table 2.

This function is more effective than either Linear Congruential or Multiplicative XOR hashing at the expense of a longer search time and a little more execution time. Here is how this function performs on the test data sets.

There is one more type of hash function to mention, Reciprocal Hashing. This hash function has several points against it:

It uses a divide instruction, which is much less common in microcontrollers than the multiply instruction.

Division, even if it is available, takes much longer to perform than multiplication (41 cycles versus 10 cycles in the MC68HC11).

If the table size is not a power of 2, then two divisions are required.

It is only about as effective as the simpler hash functions.

Still, it is worth mentioning because it may be useful in some situations. This hash function technique is fully described in the article "Reciprocal Hashing: A Method for Generating Minimal Perfect Hashing Functions" by G. Jaeshke in Communications of the ACM, Volume 24, Number 12 (December 1981). The equation describing this method is:

The MC68HC11 implementation of this method for a 16 element table is shown in Table 7.

As Table 8 shows, it is somewhat less effective at finding perfect hash functions than the Linear Congruential with XOR method described earlier.

In order to make use of the above described techniques, you need some method for finding the appropriate hash functions. FIGS. 4-7 illustrate a brute force method for finding the parameter values appropriate for a given set of IDs using a Linear Congruential Hash function.

Referring to FIGS. 4-7, parameter indexes, A, B, and maxcount are initialized (Step 41). A and B will ultimately contain the parameters appropriate for the given set of IDs. The entire set of IDs are then read into an array (Steps 42-44). A1 and B1 are then initialized (Step 47) and will hold parameter values being tested. Next, the entire table is initialized with all table entries set to zero (Steps 48-51). Using A1 and B1 as the parameter values, and using each ID, table indexes are calculated using a Linear Congruential hash formula (Steps 53-62). For each index, if the table entry at that index is zero, the ID is stored in the table entry (Steps 54-55) and counted. If the number of entries stored is greater than the total count of the IDs stored using another set of parameter values, A is set to A1 and B is set to B1, and the count is saved (Steps 63-64). A1 is then incremented (Step 65), the table entries are reinitialized (Steps 48-51) and the IDs are all tested again (Steps 53-62). This continues until A1 is 256 (Step 66). A1 is then set to zero and B1 is then incremented (Step 71). The table entries are reinitialized (Steps 48-51), and the IDs are tested (Steps 53-62). This process continues until all combinations of possible A1 and B1 values are tested. After they have all been tested, A and B will contain the best parameter values for a Linear Congruential Hash function.

It should be obvious to one skilled in the art that the flowchart in FIGS. 4-7 may be used for the other described hash functions, with some modification.

While the present invention has been particularly shown and described with reference to preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the invention.