B.   CONTRACT TEST PROBLEMS (Part 3)


B.2.7  ADAPTIVE ROUTING ALGORITHM FOR A NODE WITHIN A DATA SWITCHING NETWORK


EX 7

PURPOSE:
Test for language suitability for multicomputer and communications applications.

PROBLEM:
Develop the program for a multiprocessor within one node of a data switching network to maintain the tables of

1. distances,

2. minimum delay time, and

3. routing for the following adaptive routing algorithm:

Each node in a network maintains a table of distances and a table of minimum delay times between itself and all other nodes. The distance metric is the minimum number of hops required to reach each other node. Both tables are maintained through updates in the form of table exchanges which occur only between neighbor nodes (nodes of distance, one). Each node maintains a routing table which directs routing through that neighbor node which achieves the minimum delay time.

In parallel with, and at the same periodic rate as this computing process, separate computing processes at each node are computing the minimum delay times to neighbors; and reading into computer memory the updated distance table of each neighbor, and the updated minimum delay time table of each neighbor. Initially each node knows only the distance to each neighbor, which is one, and the minimum delay time to each neighbor. Other distances and minimum delay times are initially considered infinite. Each node iteratively builds up its own distance and minimum delay time tables from the distance and minimum delay time tables exchanged with its neighbors, and updates tables containing such information about itself. Other computing processes transmit this information between such neighbors. Hence, the routing table at each node is established and periodically updated adaptively from the minimum delay times.

When a link is broken or established, a separate computing process at each of the two former or new neighbors, corrects the distance and minimum delay time tables.

The reason a distance table must be mined is that if the network is disconnected the algorithm causes the distance between disconnected nodes to increase without limit. Thus whenever the distance between two nodes becomes greater than the number of nodes in the network, this distance and minimum delay time is considered infinite, and the node is considered unreachable.

In the example program, consider that the number of nodes in the network, the neighbors of the programmed node, and the periodic update interval are constants known at compile time.

ASSUMPTIONS:
None as far as the hardware is concerned.

GUIDELINES:
The actual interchange between the nodes can be assumed to be performed by given library routines.

DISCUSSION:
This problem involves the adaptive modification of routing tables in a network of processors. In RED, the interprocessor communication could be implemented using mailboxes, with sending a table to a processor being SENDing a message.

The main procedure, ROUTING, is called with the original table passed to it, and the number of the node that the task is running on. ROUTING creates tasks. SEND_TABLE and RECEIVE_TABLE. SEND_TABLE wakes up periodically and sends a copy of its table to all of its neighbors. RECEIVE_TABLE waits for copies of tables to arrive from its neighbors, and then checks to see if the tables it receives indicate the existence of better routing than it previously had, using the algorithm given in the sample.

Each node has its own mailbox. MAIL comes in the form of a record, the fields of which are a table and the node number of the processor that sent it.

B.2.8  GENERAL-PURPOSE REALTIME SCHEDULER


EX 8

PURPOSE:
An exercise to test the possibilities for relating computational processes to real time.

PROBLEM:
A library module shall be written which allows scheduling computational processes in actual real tie. The number of these processes shall be varying, determinable at link-time.

To simplify matters, the time span which can be handled by the scheduler may be restricted to 24 hours, i.e., all times will be computed modulo 24 hours.

This 'real time' shall be accessible to the program by the command

      TIME (operand)

which shall deposit the time (at the point in time the operation is executed) in the location indicated by 'operand' as an ASCII character string with the following conventions:

First two characters:	Hours
Second two characters:	Minutes
Third two characters:	Seconds

But the main purpose of the scheduler shall be the initiation of the execution of computational processes according to predefined conditions in real time. This shall be possible either once or repeatedly.

Processes shall be connected to the scheduler by operations of the form:

      EXECUTE processname, time
      EXECUTE time /* meaning the process which performs this operation*/
      EXECUTE processname, start-time, repetition-interval

Intentionally, no exact representation for these operations is given in the example (especially it shall not be implied that they are procedure calls). The representation shall be proposed by the language designer in order to:

1. Fit into the text of a user program as simply and naturally as possible, and

2. be efficiently implementable in the language proposed.

If two processes are due for execution at the same point in time, they shall be activated in priority order.

Note, that in order to achieve this, a library routine may have to be used which sorts the control blocks of the scheduled processes according to their priority. Because such a sorting routine is of general interest, it should also be usable for other data-types. It should be demonstrated how the parameter passing mechanism of such a routine is fit for this purpose without causing too much runtime overhead.

For the purpose of the example, the sorting algorithm proper may be simple and inefficient because it is not relevant for the demonstration.

It must also be possible to disconnect processes from the scheduler at any point in time, either by action from themselves or from other processes.

ASSUMPTIONS:
Assume a system clock which delivers 'ticks' of a frequency which is sufficient to do the necessary computations with the necessary precision. The way, how processes can be made known to the scheduler, depends on the implementation model which underlies the language proposal.

DISCUSSION:
In this solution, we have shown how the built-in RED scheduler can be used to achieve the affects desired. The user creates a task activation, and the activation contains the proper timing and iteration code. For example, the first SAMPLEPROCESS illustrates the use of the DELAY_UNTIL primitive to defer the execution of the body of the process until the time desired. If mutual exclusion of several such tasks is desired, one can place the body in the scope of the REGION construction, as illustrated.

SAMPLEINTERVAL shows how to repeat the body of the process COUNT times, waiting for a certain interval of time between execution activations. Again, the inclusion of the REGION construction would prevent mutual execution of several such processes.

A more complex example shows how to use the generic facilities to code a task EXECUTE. EXECUTE is passed a task name (here, JOB), plus several parameters indicating the starting time (START), the repetition interval (REP), the priority (PRIOR), and a mailbox (DONE) to which a message can be sent requesting the termination of the execution.

In addition to the built-in RED scheduler, the facility for adding user-specified schedulers exists in the RED language. Such schedulers allow great flexibility in the scheduling of tasks. See, for example, the RED language reference manual for a sample of a round-robin scheduler. Our solutions here emphasize simplicity.

B.2.9  DISTRIBUTED PARALLEL OUTPUT


EX 9

PURPOSE:
An exercise to demonstrate the ability of processing parallel events which need not progress at the same rate.

PROBLEM:
This program has encountered a multiple addressee message to be output over a number of asynchronous links. Each link is controlled by an individual process which performs all link related processing. Each process can accept one packet of the message at a time, and will notify the program when the last packet furnish to it has been acknowledged at the distant station. When all transmissions are complete, the program shall purge the message.

ASSUMPTIONS:

1. The message has five addresses, but these can be different for each message.

2. The message is five packets long.

3. Each packet is 80 bytes long.

4. At initialization, the program shall be furnished the address of the first buffer, the number of buffers, and the identity of the five links over which the message is to be sent (each link is controlled by an individual process, name L0..L9).

5. An 8 bit machine (one of today's typical microprocessors).

6. The program will be capable of processing up to ten addresses.

7. There is no queuing delay, i.e., the link-processes are dedicated and can react immediately.

REMARK: One can assume that the individual link processes are resident in dedicated microprocessors, and that the coordination is done in another processor to which they are connected by a bus.

GUIDELINES:
None.

DISCUSSION:
This problem demonstrates the ability of processing parallel events in RED that do not progress at the same rate. The events consist of sending messages to 5 different addressees over separate asynchronous links. The key point of the program is to show how all 5 links can be kept as busy as possible.

We have programmed this using a main procedure, DIST_OUT, that takes the list of users and the message as arguments. DIST_OUT, in turn, creates 5 copies of task DIST_OUT1, one for each of the addressees. Each DIST_OUT1 activation sends the message in packets (5 packets of 80 characters each). When all 5 DlST_OUT1 activations have terminated, DIST_OUT returns. Nearly maximum overlapping is achieved by the RED task scheduler since tasks will not be runnable while waiting for a packet to be sent.

The generic facilities of RED are also illustrated in that DIST_OUT1 selects the correct L1 procedure and passes it as a parameter. We assume that each procedure L1 handles the output to its addressee, blocking the calling task until completion.

B.2.10  UNPACKING AND CONVERSION OF DATA


EX 10

PURPOSE:
An exercise to process a packed binary message header.

PROBLEM:
A packed binary message packet has been received and placed in a buffer by the line handler. This porgram's task is to determine the classification, precedence and destination of the message packet. These data shall then be reordered and placed in a queue entry for later processing by another program.

ASSUMPTIONS:

1. An 8 bit machine (one of today's typical microprocessors).

2. The buffer is assigned from a buffer pool. The exact location of the buffer is supplied to the program when it is invoked.

3. The packet may be up to 256 bytes long.

4. The packet-format is:

   

5. Queue entries are obtained from a common pool by calling the routine 'GET-A-QUEUE'.

6. To simplify matters, assume an infinite supply of queue entries.

7. A packet is passed to a program prior to this routine's termination.

GUIDELINES:
None.

DISCUSSION:
This solution emphasizes the use of the REP construction in RED to simplify the data conversion problems.