 |
Description  |
|
|
TECHNICAL FIELD
The invention relates to file transfer systems, and more particularly, to a
method and apparatus for controlling transferring of data files among a
plurality of computers.
BACKGROUND OF THE INVENTION
Data transfer systems for transferring data files among data processing
stations, such as general purpose computers, are well known. Data transfer
network exists wherein a number of computers are interconnected and each
computer is a node in the network. Data files are transferred through the
network using established network protocols. In such networks the separate
computer installations may provide a variety of computing services at the
various nodes of the network and the interconnecting network links make it
possible for one computer system to use the services of another. This kind
of interaction is customarily accompanied by an extensive transfer of data
files between computer installations. File transfers are initiated in
response to user requests which can be handled only when the data transfer
resources are available. Each node in the network has one or more data
transfer facilities which form the network interface at the node. These
facilities include hardware and software and the number of active
facilities affects network congestion and affects the availability of
computer resources at each of the nodes. The network links are expensive
and increasingly in demand as the network grows. The transfer facilities
also are expensive and their activation requires the use of computer
resources in demand for other purposes.
In order to transfer a data file from one node to another, the sending node
must have a transfer facility available for transmission and the receiving
node must have a transfer facility available to receive the file. It may
well be that a transfer facility is not available at the receiving node at
the time that an attempt to transfer is made by the sending station. In
that case, the attempt will be unsuccessful and the transfer facility
which was available at the transmitting end may be used to transmit files
to a different destination. Hence, it may not be available when facilities
at the original destination become free. It can be seen, that with such an
approach it is possible that some files will be delayed in their transfer
a much longer period of time than other files. In fact, it is not unusual
to find that files destined for certain destinations consistently
encounter long delays.
In some networks the unavailability of facilities at the receiving end is
detected only by setting up a connection and testing for availability.
Unsuccessful transfer attempts unnecessarily add to network congestion and
may interfere with other transfers. This adds to the expense of the
network and degrades network performance.
It is an object of this invention to make optimum use of the network
transfer facilities and to avoid unnecessary network congestion.
SUMMARY OF THE INVENTION
In accordance with this invention, these and other prior art problems are
overcome by a method and apparatus for arranging an appointment for file
transfer prior to the actual transfer of the file. In accordance with one
aspect of the invention, a data processing station transmits an
appointment request message defining a future time for a file transfer and
transmits the file at the time defined by the appointment request message.
In accordance with another aspect of the invention, the destination
receiving the appointment request message responds by sending an
acknowledge message and the originating station transmits the file at the
defined future time only if a proper acknowledge has been received. In
accordance with another aspect of the invention, the originating station
transmits an appointment request message defining one or more blocks of
available time for the transfer of a file and the receiving station
selects one of the time periods and transmits an acknowledge message
defining the selected time period. Thereafter, the originator transfers
the identified file to the designated destination during the time defined
by the acknowledge message. In accordance with yet another aspect of the
invention, requests for the transfer of data files are assigned a priority
and are transferred, based on the availability of transfer facilities, in
their order of priority.
Furthermore, highest priority work may be selected from either inbound or
outbound requests. Levels of priority may be assigned on the basis of user
preference and work may be further prioritized within these levels based
on file size. In accordance with another aspect of the invention, an
appointment of a particular duration may be reserved and a plurality of
files may be formed into a batch to transfer a plurality of files in the
reserved period of time. Furthermore, a request for appointment may be
made specifying the highest and lowest priority levels of requests
included in a batch and the receiving side may accept only priorities
greater than a predetermined floor priority. Further, in accordance with
this invention, the number of appointments that one installation has with
all other installations may be limited to a predetermined number and the
maximum number to any particular location may be similarly limited.
Advantageously, the use of prearranged appointments, which may be
established through data messages which are easily and inexpensively
transmitted, avoids unsuccessful file transfer attempts before a file can
be transferred and reduces network congestion. Furthermore, by the use of
priority levels assigned to messages and selecting high priority files for
early appointments, certain files can be given preferred treatment over
other lower priority files. Advantageously, the use of appointments and
batching avoids the separate connection set-up activity and unsuccessful
attempts for each individual file to be transferred, so common in prior
art systems.
It is a further advantage to this invention that the traffic between
installations can be regulated by shifting certain transfers from busy
times to slower times. Furthermore, by the use of limitation on the number
of appointments, data transfer resources are more fairly apportioned.
BRIEF DESCRIPTION OF THE DRAWING
The invention may be better understood from the following detailed
description when read with reference to the drawing in which:
FIG. 1 is a functional block diagram of a number of interconnected computer
installations;
FIG. 2 is a functional representation of a data transfer arrangement in
accordance with the invention including memory blocks;
FIG. 3 represents a memory entry format for the request queue of FIG. 2;
FIGS. 4 through 6 are flowchart representations of the manager module
process of FIG. 2 and certain of its routines;
FIGS. 7 through 15 represent formats for various memory entries used in
this illustrative system;
FIGS. 16A and 16B are flowchart representations of the session scheduling
routine of the manager module process of FIG. 4;
FIG. 17 shows formats of messages exchanged between nodes;
FIGS. 18, 19A and 19B, 20A through 20E, 21A and 21B, and 22 are flowchart
representations of routines of the manager module process of FIG. 4;
FIG. 23 represents the format for a memory entry used for timing purposes;
FIGS. 24 and 25A through 25C are flowchart representations of the routines
of the manager module process of FIG. 4; and
FIGS. 26 and 27 are flowchart representations of TE processes.
DETAILED DESCRIPTION
FIG. 1 is a representation of a plurality of physically separated computer
installations 1 through 4 interconnected via data links 101 through 106 to
form a computer network. Computer networks of this type are well known and
amply described in the literature. FIG. 1 shows only four computer
installations for illustrative purposes. The network may be reasonably
extended to any number of computer installations.
The computer installation 3 has been expanded in FIG. 1 to show the major
system elements present in a computer system. Installations 1, 2 and 4
include similar system elements. As suggested in FIG. 1, each of the
installations may have several data links connected to it and the computer
is connected to the associated data links by means of data link interface
equipment 110. Also depicted is a computer 115, which may represent a
number of computers as is typically found in a large computer
installation. The computer includes a central processing unit (CPU) 116
connected to a memory 117 for storing programs and data, a data file
system 118 for storing data files, and input/output equipment 120. Each
computer will include application software and network software dedicated
to network functions. The network software performs a number of functions,
such as translating between host computer specific data formats and
commands and standard network representations; establishing virtual
circuits and handling datagram messages; packetizing of data: and routing
each packet to its destination. In this illustrative system, the
interconnecting network may be any well-known data transfer network. One
such network is the ARPANET, which is well-described in the literature.
Data link protocol routing algorithms and interface protocol for networks
of this type are described, for example, in Tannenbaum, Prentice-Hall,
Inc. 1981, Computer Networks. Another network, referred to in the
literature as the Bell Labs Network (BLN), is described in Coates, Dvorak
and Watts, "An Overview of BLN: A Bell Laboratories Computing Network",
Proceedings of the Seventh Data Communications Symposium, October, 1981,
and in related papers.
To transfer a file between nodes of the network, the availability of the
data transfer resources of the sending and receiving host computers must
be synchronized. In this illustrative embodiment of the invention, the
users submit a file transfer request to the file transfer scheduler
system. A functional diagram of the structure of the file transfer system
is shown in block diagram form in FIG. 2. The file transfer scheduler of
the sending node negotiates with the receiving node to set an appointment
for a future data file transfer. The scheduler arranges requests by
priority, forms batches of requests to the same destination and initiates
a transfer session via the network at the appointed time. The file
transfer scheduler system described herein will normally be resident on a
host computer with other software and system components which are well
known. Such other systems will be described herein only to the extent that
it is necessary to gain an understanding of the operation of the file
transfer scheduler system. The file transfer scheduler may be implemented
on any number of well-known general purpose computers such as an IBM-360,
a Digital VAX-1170 or other computers capable of performing the individual
actions detailed herein. In this illustrative embodiment, it is assumed
that each of the computer installations 1 through 4 of FIG. 1 contains all
of the subsystems described herein. It is possible, however, that a subset
of the subsystems exists in some of the computer installations, which
would allow a subset of the features described herein to be implemented.
A software routine commonly found in computer systems is the input/output
routine which controls input/output devices such as the terminal 120 of
FIG. 1. I/O routine 201 shown in FIG. 2 may be any well-known routine
adapted to handle such interactions, and need not be described in detail
herein. The data file system 118 will include storage devices such as
disks or tapes and the computer will include software for building,
controlling and administering the files. A user may desire to have a file
transferred from the computer where the file is resident to another node
of the network. To initiate the transfer, the local user will initiate a
request to the system which is accepted by means of the I/O routine 201 of
FIG. 2. The user will provide certain information about the file and the
destination which is received by the I/O routine 201 and placed in the
FIFO (first-in,first-out) request queue 202. This entry will be in the
form of a network service request (NSR), containing the necessary
information to fully define the request. The queue 202 resides in a
reserved area of memory 117 and may be of any desired size commensurate
with system requirements. The format for the entry is shown in FIG. 3. In
addition to storing the request in the queue, the I/O routine 201 signals
a semaphore, referred to as the new job semaphore (NJ), to manager module
209. This is one of a number of semaphores which serve to notify the
manager module 209 of work to be done. A request for file transfer from
the host computer may also be made by datagram from a remote location and
entered in the request queue 202 by means of network software, not
described herein. In either case, when an entry is made in the request
queue, the new job (NJ) semaphore is signaled.
The manager module 209 comprises a number of software routines which are
executed in response to various semaphores. In general, the manager module
209 responds to the new job (NJ) semaphore by reading a request from the
FIFO request queue 202 and placing it in the destination queue 206. This
queue resides in a reserved section of memory 117 and comprises one list
or queue for each destination with which the node communicates. The
service requests are entered in each destination queue by priority and are
subsequently obtained from the queue and serviced by the use of an
appropriately activated transfer entity (TE) such as TE-O through TE-n.
The transfer entity is equivalent to a network port and interacts with the
network in that it requests the establishment of virtual circuit data
transfer paths via the network and accesses and transfers files or
receives and stores files via virtual circuits set up in the network.
Network ports and these network related functions are well understood by
thoses skilled in the art and need not be described in detail herein. The
manager module 209 communicates with the transfer entities to activate
them at the appropriate time. The format for the destination queue entry
is shown in FIG. 10. The manager module 209 maintains a summary of work in
the queues for the various destinations in the outbound request table 208
also stored in memory 117. This table contains an entry for each
destination, the format for which is shown in FIG. 9.
The manager module 209 also maintains an appointment book table 210 in
memory 117. Before transfer of any file to another destination takes
place, the manager module requests an appointment from the destination
node specifying one or more desired starting times and the time period
required for transmission. When a request for appointment is made, an
entry is made in the appointment book table and is confirmed when the
appointment has been accepted. Conversely, when a file is to be received,
an appointment is requested by the sending node. The nodes communicate by
means of messages such as a request appointment, accept appointment, etc.
The format for these and other messages is shown in FIG. 17. The messages
are transferred between nodes by means of datagrams. Datagrams are
messages sent through the network requiring short duration connections
through the network and without the necessity of a long-term virtual
circuit. Datagrams and the method for transmitting them are well known in
the art and need not be described herein.
The manager module 209 also maintains an inbound request table 212 in
memory 117. In the event that another network node requests an appointment
which cannot be accepted, an entry is made in the inbound request table.
When the system becomes ready to accept other appointments, the manager
module will send a message to the node which was denied an appointment to
invite that node to make a request at that time. The format for an inbound
request table entry is shown in FIG. 8.
MANAGER MODULE
FIG. 4 shows the manager module consisting of 6 separate routines 421-425
and having an EVENT WAIT state 410 and an initialization routine. The
initialization routine is a common routine for setting initial values of
parameters used in file transfer scheduling and for initializing the
semaphores used to initiate the execution of routines. The transfer
parameters are determined by system requirements and operational
objectives. A number of the parameters are recorded in a tuning value
table stored in memory 117. The layout for this table is shown in FIG. 13.
Included in the tuning value table is a number representing the maximum
number of appointments which the system will handle at any particular
time. This may be, for example, 20 appointments. Another number in the
table is the maximum number of appointments per destination. This number,
for example, may be 3 appointments per destination, and is chosen to avoid
an excessive number of appointments to one destination in preference over
another destination. Another entry in the table is the priority floor.
Priority may range, for example, from 0 to 100 and the priority floor may
be set initially to low value, e.g. 5, and raised at a later point in time
to avoid handling low priority work during peak times. The priority floor
can be adjusted from time to time depending upon the traffic load on the
system. Another number in the tuning value table is the maximum size
batch. A batch consists of several requests and to meet operational
objectives, the maximum size is limited. For example, the maximum size
batch may be ten megabytes of data, where a byte equals eight bytes.
Similarly, the maximum size request is defined to avoid very large
requests which could prevent other transfer activity for extended periods
of time. The maximum size of the request may, for example, be one
megabyte. The initialization of the tuning value table occurs at system
initialization and, as indicated above, these values may be updated from
time to time depending upon system activity and operational demands.
The manager module EVENT WAIT state 412 is used to wait for appropriate
semaphores to be set. The wait state will include a routine which
periodically checks the semaphores and responds to the semaphores one at a
time. A priority routine may be used to handle certain semaphores such as
the protocol receive (PR) semaphore which is activated when a protocol
message is received from another location. Other semaphores may be given
lower priority in desired order. The use of semaphores to perform
signaling between programs is well known to those skilled in the art. A
semaphore may be accompanied by a message statement, for example, the
protocol receive semaphore will be accompanied by a statement identifying
the message type. Furthermore, counting semaphores are used which are
incremented each time a signal is received and decremented each time they
are serviced.
When a semaphore has been signaled to the manager module, the process
starts by leaving the EVENT WAIT state and executing the indicated
routine. The new job (NJ) semaphore is set, as mentioned earlier, when a
new request is entered into the request queue 202 and in response to this
semaphore the new job routine 421 is executed. During the execution of
this routine, the JM semaphore is signaled. This semaphore or the HT
semaphore will cause the execution of the schedulability routine 420. The
HT semaphore, as well as the timer semaphore, which initiates execution of
the timer routine 425, are signaled by a standard well-known time-out
program which periodically compares time stamps entered in tables or lists
with the current system time. When a time-out has occurred, the
appropriate semaphore will be signaled. The new schedule semaphore, which
causes execution of the session scheduling routine 422, may be set by any
number of other routines of the manager module. The protocol receive (PR)
semaphore is signaled by the network software when a datagram message for
the manager module is received. It is used to initiate execution of the
protocol receive routine 424. The TE semaphore which is signaled by a
transfer entity process, is used to initiate execution of the TE event
routine 423. On completion of any of these routines, a return is made, as
indicated in block 414, to the EVENT WAIT state to wait for a semaphore to
be signaled. Each of the routines 420 through 425 are discussed in
subsequent paragraphs with respect to other figures of the drawing.
JOB ROUTINE
FIG. 5 is a flowchart detailing the functions executed by the new job
routine. This routine is part of the manager module and is entered in
response to the NJ semaphore. As indicated in block 501, the new job
routine reads the network service request from the request queue 202. For
each service request in the request queue there is a separate entry, the
format of which is shown in FIG. 3. This includes a designation of the
destination and user priority. As indicated in block 502, system priority
is computed. When the request is made, a user will indicate a desired
priority. This may be premium, regular, or deferrable priority. This
priority information, together with the size of the request, is used to
compute a system priority for the request. In this illustrative system,
the priority is divided in a range from zero to 100. A minimum priority,
referred to as the floor priority, is initially set at level 5 and
deferrable requests are entered in the range from 5 to 35, regular
requests are entered in the range from 35 to 65 and premium requests are
entered in the range from 65 to 95. The request size is defined by the
total bytes of the files to be transferred. There are four ranges, namely:
less than 10,000 bytes, less than 100,000 bytes, less than 1 megabyte, and
greater than 1 megabyte. Each of the ranges 5 to 35, 35 to 65, and 65 to
95 are divided into four bands, one for each of the size ranges. The
highest priority being given to the smallest size jobs. In this manner a
system priority can be readily computed based upon the user priority and
the size of the request. Additionally, certain destinations may be given
higher priority weight than others and aging of the requests may be taken
into account if the time of entry is recorded. These priority weightings
are a matter of design choice.
As indicated in block 503, the request is entered in the appropriate
destination queue by priority. The format for each destination queue entry
is shown in FIG. 10. It will be apparent that the information in this
entry contains the information that is found in the request queue depicted
in FIG. 3 and a field for system priority, appointment ID, and state. The
newly computed system priority will be entered in the first-named field.
The appointment ID will be entered at a later time, and the state field
will be used to indicate that this is the initial state.
After system priority has been computed, the new request is linked in the
destination queue 206 in order of priority, as indicated in block 503.
This queue comprises a separate linked list queue for each destination and
the new request is entered in the proper list and in the proper place in a
well-known fashion. As noted earlier, the manager module maintains an
outbound request table 208 which contains an entry, depicted in FIG. 9,
for each destination. Each entry includes a summary of all the service
requests without appointments for the corresponding destination. The
summary includes the highest priority of the service requests, the number
of service requests, and the total number of bytes. This table is updated
as indicated in block 505, after a new request has been entered in the
destination queue. Thereafter, in block 509 the job routine signals the JM
semaphore for the manager module 209 and the module returns to the EVENT
WAIT state. The manager module uses a counting NJ semaphore which is
incremented each time the semaphore is signaled to the manager module and
which is decremented each time the job routine is entered. Thus, if other
requests are in the FIFO request queue 202 they will be served when the
job routine is again executed in response to the NJ semaphore.
SCHEDULABILITY ROUTINE
FIG. 6 is a flowchart showing the steps of the schedulability routine 420
of the manager module 209. This routine is entered when the JM semaphore
is signaled by the new job routine or the HT semaphore is signaled. The HT
semaphore is signaled when a time-out has occurred in the so-called "hold"
list. The hold list is a linked list in memory 117 which is linked in
order of a time indication, referred to as a time stamp, which occurs in
each entry of the list. The format for an entry of this linked list is
shown in FIG. 11. This list is used to delay action with respect to a
certain destination or a certain service request by a period of time
defined by the time stamp. The time stamp is generated at the time that an
entry is made and is computed by adding a desired time period to the
current system time. It is common in computer systems to define the
current system time or time of day and the system will have a time-out
routine which periodically compares the current system time with that
indicated by the time stamp. When this routine tests the hold list, it
will signal the HT semaphore when a time-out has occurred in this list. As
indicated in FIG. 11, each entry of the hold linked list has a field
indicating whether this is an NSR or a destination hold and fields
indicating the identification of the NSR and the destination, in addition
to the time stamp.
As indicated in decision block 610 of FIG. 6, a test is made in the
schedulability routine to determine whether the routine has been activated
in response to the JM or HT semaphore. In the case that it is due to the
JM semaphore, the routine will look for a network service request in the
destination queue in the initial state as indicated in block 612. From
this, the identity of the destination will be obtained and, as indicated
in decision block 615 a determination will be made as to whether this
destination has been put on hold. This information may be obtained from
the outbound request table entry for this destination. A typical entry for
this table is shown in FIG. 9 and includes a field which indicates whether
or not the destination has been put on hold. This may have occurred for
various reasons such as the inability to reach the destination or a
failure of the destination to accept requests for appointments. If the
destination is on hold, a destination queue entry will be updated to the
schedulable state as indicated in block 619. Thereafter, a return will be
made to the EVENT WAIT state of the manager module.
If the destination is not on hold, a test is made in decision block 616 to
determine if there is an open appointment to the destination under
consideration. If so, this request will be added to that open appointment.
Information about an open appointment is contained in the appointment book
table 210. The format for an entry in this table is shown in FIG. 12. The
table may be entered by searching for the destination in the peer node ID
field of the table. If an entry is found for that destination, the
open/closed field will be consulted to determine if the appointment is
open. In the event that it is open, the appointment ID found in the
appointment book table is entered in the destination queue entry for the
network service request being handled. This action is reflected in block
617. Subsequently, the outbound request table, which represents a summary
of all requests without appointment, must be updated to reflect the
assignment of an appointment to this request. The entry format for this
table is shown in FIG. 9. The update action is reflected by block 630 in
FIG. 6.
In addition to updating the outbound request table, the appointment book
table (FIG. 12) must be updated in its field reflecting the end time of
the appointment, the priority level of service requests in the appointment
and the total bytes. The information to update the priority and byte
information is readily obtained from the destination queue entry (FIG.
10). The end time may be readily derived from the start time, the total
number of bytes and the transmit speed available between the sending and
receiving hosts. The transmit speed, which may differ for different
destinations, is recorded for each destination in the outbound request
table (FIG. 9). One commonly used transmission rate is 56,000 bits per
second. For purposes of calculating intervals, a conservative rate of 4000
bytes per second (8 bits per byte) may be used on a 56,000 bits per second
transmission facility to assure adequate time for transmission. Times for
other data rate lines may be similarly calculated. In block 619 the state
of the destination queue entry is changed to "schedulable" to indicate
that the request is ready for data transfer. Returning to decision block
616, in the event that it is found that there is not an open destination,
a new appointment will have to be made by means of the session scheduling
routine 422 of the manager module. To activate this process, the new
schedule semaphore is signaled in block 618 and the state of the entry in
the destination queue is updated to schedulable as reflected in block 619.
Referring again to decision block 610 in FIG. 6, in the event that this
routine is entered as a result of the hold timer semaphore HT, the hold
link list is read and the first entry is taken from the list. A typical
entry layout for the hold link list is shown in FIG. 11. As indicated in
FIG. 6, if the HT semaphore is set, the schedulability routine reads the
hold link list in block 620. The first entry is removed from the list and
a test is made in decision block 622 to determine whether the item held is
a service request (NSR) or a destination. This information is obtained
from the NSR/DEST field shown in FIG. 11. In the event that it is a
service request, a test is made in decision block 615 to determine if the
destination corresponding to this service request is on hold. The
destination ID for the NSR may be obtained from the destination queue
entry (FIG. 10) and the hold information may be obtained from the outbound
request table (FIG. 9). If the destination is on hold, the destination
queue entry is updated to schedulable, as indicated in block 619.
Otherwise, the same routine is followed as with the JM semaphore as
discussed above with respect to blocks 616, 617, 618, 619, 630 and 632.
If it is determined by decision block 622 that the item on the link list
was a destination, the hold state of the destination in the outbound
request table (FIG. 9) is changed to release the destination, as indicated
in block 624. Additionally, the new schedule semaphore will be signaled in
block 618, to activate the session scheduling routine referred to in FIG.
4. Thereafter, a return is made to the EVENT WAIT state of the manager
module.
SESSION SCHEDULING ROUTINE
A flowchart representation of the session scheduling routine is depicted in
FIGS. 16a and 16b. The first task, depicted in block 1601 is to compute
the total number of appointments in the host system which are committed or
reserved. This number is found by adding all the appointments found in the
appointment book table 210. The computed total is compared to a
predetermined maximum total for the system defined in the tuning value
table shown in FIG. 13. As described earlier, the maximum number entered
here is a function of system capacity and operational objectives. The
comparison of the computed total with the maximum number is represented by
decision block 1602. If the computed total is equal to or greater than the
stated maximum, the routine will return to the EVENT WAIT state of the
manager module. If the computed total is less than the maximum, the
outbound request table (FIG. 9) is examined in block 1603 to determine if
there are any outbound service requests without appointments. If there are
none, a test is made in block 1614 to determine | | |
