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
- distances,
- minimum delay time, and
- 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:
- Fit into the text of a user program as simply and naturally as possible, and
- 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:
- The message has five addresses, but these can be different for each message.
- The message is five packets long.
- Each packet is 80 bytes long.
- 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).
- An 8 bit machine (one of today's typical microprocessors).
- The program will be capable of processing up to ten addresses.
- 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:
- An 8 bit machine (one of today's typical microprocessors).
- The buffer is assigned from a buffer pool. The exact location of the
buffer is supplied to the program when it is invoked.
- The packet may be up to 256 bytes long.
- The packet-format is:
- Queue entries are obtained from a common pool by calling the routine
'GET-A-QUEUE'.
- To simplify matters, assume an infinite supply of queue entries.
- 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.