Distributed computing network

A distributed computing network has a packet routing system for routing packets among packet lists accessible to tasks. Packets are routed and attached to lists identified within a packet header or selected from router tables. Access to packet lists is managed according to data stored within packet list headers. Several types of packets are used for exchanging data, executing remote instructions, maintaining communication between network nodes, and supplying initialization instructions to network nodes. An inductive booting mechanism uses the packet routing system to initialize nodes and to re-boot failed nodes. Interface tasks manage transmission and reception of packets between nodes in order to provide asynchronous communication between tasks in a multitasking distributed computing environment.

 

What is claimed is:

1. In a multitasking system executing a plurality of tasks effective to issue function calls and to process packets of information, a system for accessing packets comprising:

a plurality of packet lists, each list associated with a packet list header having pointers to packets on the list,

routing means for routing packets to said lists, said routing means including attaching means for attaching packets to said lists, and

obtaining means for obtaining a packet from a selected list and for providing a pointer to said packet in response to a call from one of said tasks, said obtaining means comprising:

determining means for determining the presence of any packets on the selected list, and

de-activation means responsive to said determining means for de-activating said calling task when there are no packets on the selected list,

said routing means including activation means, responsive to said attaching means, for reactivating said calling task.

2. The system of claim 1 wherein said packet list header further comprises a queue pointer to a queue of tasks deactivated by said de-activation means, and said activation means comprises means for removing said calling task from said queue.

3. The system of claim 1 wherein said de-activation means further comprises timer means for re-activating said calling task after a selected period of time if said task is not re-activated by said activation means.

4. The system of claim 1 wherein said routing means comprises list validation means for validating that (i) a packet list header contains a value indicating that the packet list header is associated with a valid packet list, and (ii) a value within a packet corresponds to a value within the packet list header; and wherein said attaching means is responsive to said validation means for attaching the packet to a list when conditions (i) and (ii) are satisfied.

5. The system of claim 1 comprising:

a plurality of interconnected processing nodes, and said routing means includes:

a router table residing at a first node, for providing an associative mapping between selected processing nodes and packet lists residing at said first node;

destination determining means for determining whether a packet residing at said first node is addressed to a second node;

packet list address obtaining means, responsive to said destination determining means, for providing a packet list address to said attaching means on the basis of (i) a list address contained within a packet when the packet is determined to be addressed to a list residing at the first node, and (ii) a list address contained within the router table when the packet is determined to be addressed to the second node.

6. The system of claim 5 wherein said packet list address obtaining means is configured for providing a predetermined packet list address when the packet is determined to be addressed to said second node and when said second node is not among said selected processing nodes.

7. In a multitasking system executing a plurality of tasks effective to issue function calls and to process packets of information, a system for accessing packets comprising:

a plurality of packet lists, each list associated with a packet list header having pointers to packets on the list,

routing means for routing packets to said lists, said routing means including attaching means for attaching packets to said lists, and

obtaining means for obtaining a packet from a selected list and for providing a pointer to said packet in response to a call from one of said tasks, said obtaining means comprising:

determining means for determining the presence of any packets on the selected list, and

de-activation means responsive to said determining means for de-activating said calling task when there are no packets on the selected list, said de-activation means including timer means for re-activating said calling task after a selected period of time if said calling task is not re-activated by said activation means, the period of time being selected in accordance with a parameter passed to said obtaining means by said calling task,

said routing means including activation means, responsive to said attaching means, for reactivating said calling task.

8. A system for transmitting a packet from a first task to a second task, comprising in combination

list means for storing packets on a packet list, said list means including a list header for providing pointers to the packet list and to a queue of tasks waiting for packets on the packet list,

obtaining means responsive to said second task for obtaining a packet from a list, said obtaining means including de-activation means for de-activating said second task in the absence of a packet on the list and for placing said second task on said queue, and

routing means responsive to said first task for placing the packet on the list, said routing means comprising re-activation means for re-activating said second task and removing said second task from said queue.

9. The system of claim 8, comprising:

timer means for reactivating said second task after a selected interval of inactivity subsequent to deactivation if said second task is not reactivated by said routing means, and

wherein said obtaining means is selectively responsive to said timer means and said routing means for selectively obtaining a packet from a list in dependence upon whether said second task is reactivated by said routing means or said timer means.

10. The system of claim 8 wherein said obtaining means comprises activation means for activating a task identified in said queue.

11. A system for delivering packets within a network comprising a plurality of interconnected nodes,

I. each node having:

(a) an addressable memory for storing linked lists of packets, each list having a list header for providing information pertaining to the list, and wherein at least one of said lists is an output list comprising packets for transmission to an adjacent node,

(b) a processor for executing tasks,

(c) sending means for sending packets to an adjacent interconnected node including removing means for removing packets from said output list and transmitting means for transmitting packets from said output list to an adjacent node,

(d) packet routing means residing at the node, said routing means operable by said processing means for attaching packets to lists, and

(e) a router table containing at least one address of an output list header pertaining to said output list and associating said one address with at least one of said nodes;

II. each packet having:

(a) a header containing:

(i) a destination node field for indicating a destination node, and

(ii) a destination list field for indicating the address of a destination list header within the memory of the destination node pertaining to a destination list, and

(b) a body containing a plurality of data fields; and

III. said packet routing means comprising:

(a) determining means for determining whether the destination node field of a packet corresponds to the resident node of said packet routing means,

(b) obtaining means for obtaining an address of one of said lists, said obtaining means including:

(i) table consulting means for consulting the router table and for obtaining the address of an output list header pertaining to said destination node from said router table when said packet is destined for a node other than the resident node of said packet routing means, and

(ii) header consulting means for obtaining said destination list header address from said packet header when said packet is destined for the resident node of said packet routing means, and

(c) attaching means responsive to said obtaining means for attaching said packet to the list pertaining to the address obtained by said obtaining means.

12. The system of claim 11 wherein said table consulting means comprises error means for providing a predetermined address when said destination node is not associated with an output list header within said router table.

13. The system of claim 12 wherein said header consulting means comprises error means for providing a predetermined address when said list header address from said packet header does not correspond to one of said lists in said addressable memory.

14. The system of claim 11 wherein said removing means comprises:

(a) de-activation means for de-activating said sending means when there are no packets on said output list, and

(b) timer means for re-activating said sending means when said sending means has been de-activated for a selected period of time;

and wherein said packet routing means further comprises re-activation means responsive to said attaching means for re-activating said sending means.

15. A packet delivery system for delivering packets within a computing network having a plurality of nodes, each node having an identifier and an addressable memory, the delivery system comprising:

a plurality of linked lists of packets resident within said memories;

each respective list of packets having an associated list header including a pointer field for storing a pointer to the respective list of packets, an identification field for storing an identification value unique to the respective list, and an address field containing the address of the list header;

each packet having a destination node field for indicating the destination node of the packet, and a destination list field for indicating the address and identification value of the destination list header; and

packet routing means resident upon said nodes for selecting a list and attaching a packet to said selected list, said packet routing means having:

comparing means for comparing said destination node field contents of the packet to the resident node,

table means responsive to said comparing means for providing the address of the selected list when said comparison is non-identical,

validating means for verifying that (i) the memory address indicated by the destination address value in the packet contains the destination address and (ii) said destination list identification value field of the destination list header matches the corresponding value in the packet, said validating means responsive to said comparing means when said comparison is identical, said validating means providing the address of the selected list when conditions (i) and (ii) are satisfied,

error means for providing a predetermined list address upon failure of either said table means or said validating means to provide the selected list address, and

linking means for linking the packet to the selected list provided by any of said table means, said validating means, or said error means.

16. A system for transmitting packets of information from a first node to a second node of a distributed computing network comprising:

a list in the memory of the first node for storing packets to be transmitted to said second node;

a communication link between said first node and said second node;

output means for operating said communication link; and

obtaining means operable by said output means for removing a packet from said list and for providing the address of said removed packet to said output means, wherein said obtaining means is operable in a selected one of two modes of operation in dependence upon a selected parameter, and wherein said obtaining means includes:

timer means for de-activating said output means for a selected period of time when the list is empty and said parameter indicates said first mode, and

de-activation means for de-activating said output means until a packet is attached to the list when the list is empty and said parameter indicates said second mode; and

wherein said output means includes:

monitoring means for monitoring the operation of said communication link and for detecting successful transmission of a packet across said link, said output means operating said obtaining means:

(i) in said first mode when successful transmission is detected and

(ii) in said second mode when successful transmission is not detected; and

idle means for producing and transmitting an idle packet when said selected period of time expires.

17. A system for transmitting packets of information from a first node to a second node of a distributed computing network comprising:

a list in the memory of the first node for storing packets to be transmitted to said second node;

a communication link between said first node and said second node;

output means for operating said communication link; and

obtaining means operable by said output means for removing a packet from said list and for providing the address of said removed packet to said output means, wherein said output means comprises:

determining means for determining whether said removed packet contains initialization instructions for said second node,

reset means operable by said first node for resetting said second node, and

downloading means for downloading said initialization instructions to said second node so that said second node is initialized according to said initialization instructions.

18. A distributed computing network comprising:

a first node for executing a plurality of first tasks;

a librarian for storing and retrieving a library of code, said library including initialization code for said first node;

a second node for executing a plurality of second tasks, said second node connected with said first node and with said librarian by data communication links;

failure detection means for allowing said second node to detect a failure of said first node;

first node reset means connected with said first node, said first node reset means operable by said second node for resetting said first node;

request means for allowing said second node to request of said librarian to send said initialization code via one of said data communication links to said second node; and

downloading means for downloading said initialization code to said first node from said second node subsequent to operation of said node reset means.

19. A distributed computing network comprising:

a first node for executing a plurality of first tasks;

a librarian for storing and retrieving a library of code, said library including initialization code for said first node;

a second node for executing a plurality of second tasks, said second node connected with said first node, and with a librarian by data communication links, said library further including second initialization code for initializing said second node;

failure detection means for allowing said second node to detect a failure of said first node;

first node reset means connected with said first node, said first node reset means operable by said second node for resetting said first node;

request means for allowing said second node to request of said librarian to send said initialization code via one of said data communication links to said second node;

downloading means for downloading said initialization code to said first node from said second node subsequent to operation of said first node reset means;

second failure detection means for allowing said first node to detect a failure of said second node;

second node reset means for allowing said first node to reset said second node; and

second request means for allowing said first node to request of said librarian to send said second initialization code to said first node for downloading to said second node subsequent to operation of said second node reset means.

20. A distributed computing network comprising:

a first node for executing a plurality of first tasks;

a librarian for storing and retrieving a library of code, said library including initialization code for said first node;

a second node for executing a plurality of second tasks, said second node connected with said first node, and with a librarian by data communication links, said library further including second initialization code for initializing said second node;

failure detection means for allowing said second node to detect a failure of said first node;

first node reset means connected with said first node, said first node reset means operable by said second node for resetting said first node;

request means for allowing said second node to request of said librarian to send said initialization code via one of said data communication links to said second node;

downloading means for downloading said initialization code to said first node from said second node subsequent to operation of said node reset means;

second failure detection means for allowing said librarian to detect a failure of said second node;

second node reset means connected with said second node, said second node reset means operable by said librarian node for resetting said second node; and

downloading means for allowing said librarian node to download said second initialization code to said second node subsequent to operation of said second node reset means.

21. A distributed computing network, comprising:

a first node for executing a plurality of first tasks;

a second node for executing a plurality of second tasks, said second node connected with said first node by a data communication means for communicating data;

failure detection means for allowing said second node to detect a failure of said first node;

node reset means connected with said first node, said node reset means operable by said second node for resetting said first node; and

storage means for non-volatile storage of initialization code for initialization of said first node, said storage means connected with said first node and operable by said first node subsequent to operation of said node reset means.

22. A distributed computing network comprising:

a plurality of intelligent interconnected nodes, each of said nodes adjacent to at least one other of said nodes;

data storage means for storing sets of initialization code for said nodes;

a librarian for operating said data storage means;

failure detection means for allowing each of said nodes to detect a failure of an adjacent node;

node reset means for allowing said each of said nodes to reset an adjacent node; and

request means for allowing said each of said nodes to request of said librarian to send a selected one of said sets of initialization codes to an adjacent node subsequent to said each node having detected a failure of said adjacent node.

23. A method of routing a packet of information, said packet being resident within a memory of a node of a distributed computing network, said method comprising the steps of:

(a) comparing a value characteristic of the node to a value contained within the packet;

(b) determining if the packet is to be routed to an other node;

(c) consulting a router table, if the packet is determined in step (b) to be routed to the other node, to find a value characteristic of a list to which to append said packet, the router table being configured to associate nodes of the distributed computing network with lists of packets;

(d) appending the packet to the list;

(e) determining whether a task has been deactivated as a result of there previously having been no packets on the list; and

(f) re-activating said task when the packet is appended to the list.

24. The method of claim 23 comprising the steps of:

validating, on the basis of address values contained within the packet and list values contained within the memory, that the packet is to be appended to a selected list if the packet is not to be routed to the other node; and

appending the packet to the selected list.

25. The method of claim 24 wherein said validating step comprises the steps of:

comparing an address value contained within a list header associated with the selected list with a predetermined value to determine whether the selected list is a valid list; and

comparing an identification value contained within the packet with a corresponding identification value contained within the list header to determine whether the packet identifies the selected list.

26. The method of claim 25, comprising the step of appending the packet to a predetermined list if the selected list is not a valid list or if the packet does not identify the selected list.

27. A method of transmitting a packet of information, said packet resident at a location having an address within a memory of a node of a distributed computing network, said node having an output port, said method comprising the steps of:

(a) obtaining a value indicative of an address from a packet list header, said packet list header including a pointer to said address;

(b) reading the packet from the memory after having obtained the value indicative of said address;

(c) operating said output port to effect transmission of said packet;

(d) detecting a transmission error during said operating step (c); and

(e) generating and transmitting an idle packet from said output port if no error is detected during said detecting step (d) and said packet list header indicates that there are no other packets to be transmitted.

28. The method of claim 27 wherein said detecting step comprises the steps of:

determining, in advance of said operating step, an allowable interval of time for transmitting the packet; and

indicating a transmission error if said operating step exceeds said interval.

29. The method of claim 28 wherein said allowable interval of time is determined on the basis of the length of the packet.

30. The method of claim 27, comprising the steps of:

determining whether said packet contains initialization code for an other node of the network; and

operating a reset means for resetting the other node prior to said operating step.

31. A method of transmitting packets of information from an output port of a node of a distributed computing network, said node connected to an adjacent node by a communication link, the method comprising the steps of:

(a) determining whether there are any packets on a list of packets to be transmitted;

(b) constructing an idle packet for determining the status of the link if there are no packets on the list to be transmitted;

(c) operating the output port to effect transmission of said idle packet to an adjacent node;

(d) obtaining a packet from said list if it was determined in step (a) that there is at least one packet on said list;

(e) determining, on the basis of values contained within the packet obtained in step (d), whether the packet is a boot packet containing initialization instructions for the adjacent node;

(f) operating the output port to effect transmission of the obtained packet if it was determined in step (e) that the packet is not a boot packet;

(g) operating a reset line to the adjacent node if it was determined in step (e) that the packet is a boot packet; and

(h) downloading said initialization instructions to the adjacent node subsequent to step (g).

32. The method of claim 31 further comprising the steps of:

determining the length of the packet to be transmitted to the adjacent node,

comparing the time required for transmitting the packet to the determined time for transmitting the packet, and

signalling a failure of said link if the time required for transmitting the packet exceeds the determined time.

33. A method of receiving a packet of information into a data port of a first node of a distributed computing network from an adjacent node, said method comprising the steps of:

(a) monitoring the data port;

(b) determining that the packet of information is being sent to the first node from the adjacent node;

(c) storing the packet of information into the memory of the first node;

(d) determining whether a packet transmission means for transmitting packets of information from the port is operating in a condition indicative of a failure of the adjacent node; and

(e) signalling the packet transmission means with a signal indicative of the absence of a failure of the adjacent node if said packet transmission means is operating in a condition indicative of a failure of the adjacent node.

34. A method of receiving a packet of information into a data port of a first node of a distributed computing network from an adjacent node, said method comprising the steps of:

(a) monitoring the data port;

(b) determining that the packet of information is being sent to the first node from the adjacent node;

(c) determining whether the packet is an idle packet sent by said adjacent node for determining the status of the data port;

(d) storing the packet of information into the memory of the first node;

(e) determining whether a packet transmission means for transmitting packets of information from the port is operating in a condition indicative of a failure of the adjacent node; and

(f) signalling the packet transmission means with a signal indicative of the absence of a failure of the adjacent node if said packet transmission means is operating in a condition indicative of a failure of the adjacent node.

35. The method of claim 34 further comprising the step of discarding the packet if it is an idle packet.

36. A method of receiving a packet of information into a data port of a first node of a distributed computing network from an adjacent node, said method comprising the steps of:

(a) monitoring the data port;

(b) determining that the packet of information is being sent to the first node from the adjacent node;

(c) storing the packet of information into the memory of the first node;

(d) determining whether a packet transmission means for transmitting packets of information from the port is operating in a condition indicative of a failure of the adjacent node;

(e) signalling the packet transmission means with a signal indicative of the absence of a failure of the adjacent node if said packet transmission means is operating in a condition indicative of a failure of the adjacent node; and

(f) causing the packet to be routed toward a destination.

FIELD OF THE INVENTION

The present invention relates to distributed computing networks and particularly to communication of data and control signals among intelligent nodes within a network including the initialization of intelligent nodes by a method of distributed control within a flexible hierarchy.

BACKGROUND OF THE INVENTION

Distributed computing networks are conglomerations of autonomously-functioning processing units which are arranged in such a way that individual units may be assigned to perform tasks, such as programs, processes, routines, functions, or jobs, which are sub-parts of a larger process for which the network is employed. Distributed computer networks are useful for applications such as control of industrial processes wherein many different operations are performed in a number of physical locations, yet many of the operations need to be coordinated with one another. A computer network for such an application would include a number of autonomous intelligent units or nodes which are each programmed to execute particular tasks and which are connected by a web of communication links so that the nodes may share information with one another.

A type of computer chip called a transputer has been developed for use in parallel processing applications. A transputer chip includes a processor with an internal time-sharing system capable of executing more than one task, on-board memory for storing programs and data, and four bi-directional data ports. Ordinarily, communication between tasks in conventional transputer networks is accomplished via synchronous data channels between tasks. Complex switching networks may be needed to provide an adequate number of data channels. As the number of nodes in such a network increases, the complexity of the switching network increases. In order to facilitate the construction of switching networks for transputers, crossbar switching chips have been developed which can interconnect as many as thirty-two (32) bi-directional ports. Layers of router chips can be used to build switching networks of larger arbitrary sizes. Management of such large switching networks requires considerable software overhead, and tasks on each node must still contend for the use of a finite number of channels.

Another problem with traditional distributed computer networks is that, once designed and programmed, it becomes increasingly difficult to add new nodes or to reassign tasks among nodes since any tasks that may be affected or may need to communicate with tasks at the new location must be reprogrammed to account for the new network topology. Additionally, the switching network then requires reconfiguration to accommodate the new nodes.

As network size increases, the average time between node failures decreases. Hence, for networks employing a fixed routing topology, the maximum network size is determined by individual node reliability and the minimum acceptable time between failures. To improve the reliability of distributed computing networks, it would be desirable to provide a network with the ability to dynamically alter its information routing topology so that the functions assigned to failed nodes could be reassigned to other nodes without interrupting network operation. It would further be desirable to provide a network in which the nodes would have the capability of monitoring the operation of their neighboring nodes and to reboot their neighbors upon detecting a failure.

The problems associated with conventional transputer networks, such as the need for synchronous communication between tasks, the need for router chips to effect switching, and difficulties often encountered in network reconfiguration, have limited the development of flexible, adaptable, modular, intelligent networks.

SUMMARY OF THE INVENTION

According to one aspect of the present invention, communication between nodes is accomplished by the use of interface tasks for controlling the operation of each communication port of each transputer node. Each port is assigned a link-output task for transmitting information from the port and a link-input task for receiving information and storing it into the node memory or heap. Information is exchanged between lists in a structure called a packet. Packets include a header containing routing information and a body containing data or instructions.

In accordance with another aspect of the invention, a packet routing system, including a packet routing routine called ROUTE-PACKET and node-local router tables, is used to route packets of information between linked lists of packets. Tasks may access such linked lists of packets. Data structures termed packet list headers are associated with the packet lists and are used to manage access to packet lists. A packet list header includes pointers to the beginning and end of a packet list. Each packet list header may also include pointers to the beginning and end of a task queue comprising a linked list of tasks waiting to take packets from the packet list.

A task may send a packet to a node-local packet list, to a packet list on another node in a local network, or to a packet list on another node in a remote network by invoking ROUTE-PACKET. In order to send a packet on one node to a destination packet list on another node, a sending task upon one node constructs or otherwise obtains a packet in the heap containing the information to be sent. Then, the sending task invokes ROUTE-PACKET, which consults a router table in order to obtain the address of a packet list header pertaining to an intermediate packet list to which the packet is to be attached. Such an intermediate packet list may be associated with a link-output task. The link-output task then can obtain the packet from the intermediate packet list and transmit the packet across a physical link toward the destination node of the packet.

Link-input tasks provide the function of receiving packets from physical links, storing them in the heap, and invoking ROUTE-PACKET to attach incoming packets to either a destination packet list on the node or to yet another intermediate packet list for transmission to another node. Rather than incurring the time losses involved in synchronous intertask communication, tasks within systems send and receive messages by performing operations upon packet lists in the heap at any time without regard for the details of routing or port availability. Packets may likewise be routed among packet lists associated with interface tasks which govern the operation of non-transputer interfaces, as may be used to interconnect nodes of a network or to serve as gateways to networks having disparate data communication protocols.

A packet is routed to a destination packet list on a predetermined node by altering one or more pointers within the associated packet list header. ROUTE-PACKET attaches packets to their destination lists, to intermediate lists such as link-output task lists, or to a designated task list for error handling. In most cases, ROUTE-PACKET receives the heap address of a packet and attaches the packet to a packet list. ROUTE-PACKET may discard certain packets that have encountered routing or delivery errors. When a packet is to be sent to a packet list upon another node, ROUTE-PACKET uses a router table to select an intermediate packet list to which to attach the packet. The router table contains information associating other nodes of the network with one or more packet lists. For packets that are to be transmitted via a network link, the router table is used by ROUTE-PACKET to determine the address of a packet list header, such as may indicate a packet list serviced by an appropriate link-output task for sending a packet across a link to an adjacent node toward the destination of the packet. The router table on the next node contains routing data for the next step, if any, so that a packet ultimately reaches its destination by skipping from node to node. Each packet contains a header which provides information to ROUTE-PACKET indicating the location of the destination packet list. In cases wherein a packet is destined for a packet list on the immediate node, ROUTE-PACKET links the packet directly into the destination packet list without requiring the use of the router table or an intermediate packet list. Such direct attachment to the destination packet list is performed without changing the location of the packet in the heap.

According to a further aspect of the invention, packets propagate in a store-and-forward fashion determined by the routing system according to the router tables resident upon each node. Hence the distributed computer network behaves as its own routing network. The node-specific router tables can be distributed to the nodes from a central library of router tables. The router tables can be altered during the course of operation of the network as circumstances may require without disrupting operation of the network.

Networks constructed according to yet another aspect of the invention possess an inductive booting mechanism whereby nodes are reset and initialized by adjacent nodes in a cascaded fashion. A node or group of nodes execute specialized file access tasks, designated librarian tasks, which include the function of maintaining initialization codes, router tables, and other information relevant to node initialization. The link-output task for each port of a node includes a provision for monitoring the status of the adjacent node and causing the librarian to be notified if the adjacent node has failed or otherwise requires initialization. In such circumstances, the librarian can then issue a specialized packet, called a boot packet, which contains the required initialization information. The link-output task then activates a reset line connected to the adjacent node and downloads information from the boot packet in order to initialize the failed or inoperative node. In this manner, an entire network, or selected nodes therein, can be re-booted or reprogrammed.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing summary, as well as the following detailed description of the preferred embodiments of the present invention, will be better understood when read in conjunction with the appended drawings, in which:

FIG. 1 is a schematic representation of a node employed in t practice of the invention;

FIG. 2 is a logical flowchart of a packet routing procedure;

FIG. 3 is a logical flowchart detailing one of the procedural sp of the packet routing procedure of FIG. 2 in which a router table is consulted;

FIG. 4 is a logical flowchart detailing one of the procedural steps of the packet routing procedure of FIG. 2 in which a list identifier for the destination of a packet is validated;

FIG. 5 is a logical flowchart detailing one of the procedural steps of the packet routing procedure of FIG. 2 in which packets are attached to a list;

FIG. 6 is a memory map of a router table used by the packet routing procedure of FIG. 2;

FIG. 7 is a memory map of a router table specific to a selected node of a network;

FIG. 8 is a functional block diagram of a network of transputer nodes;

FIG. 9 is a memory map of a packet list header;

FIG. 10 is a block diagram of a packet structure;

FIG. 11 is a block diagram of an interpreter packet structure;

FIG. 12 is a logical flowchart of a procedure used by tasks to discard packets;

FIG. 13 is a logical flowchart of a procedure used by tasks to construct packets;

FIG. 14 is a logical flowchart of a procedure used by tasks to obtain packets from packet lists;

FIG. 15A-C are memory maps of packets A, B, and C;

FIG. 15D is a memory map of a packet list header including pointers to the packets A and B of FIGS. 15A-C;

FIG. 16 is a logical flowchart of a link-output task;

FIG. 17 is a logical flowchart of a link-input task;

FIG. 18A-B are adjacent tables used by particular nodes of the network of FIG. 8;

FIG. 19 is a functional block diagram of three local transputer networks that are connected by internetwork links;

FIG. 20 is a logical flowchart of a procedure for transmitting packets from a local transputer network into an internetwork link; and

FIG. 21 is a logical flowchart of a procedure for receiving packets from an internetwork link into a local transputer network.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

An intelligent node 46 for a distributed computing network is shown in FIG. 1. The node 46 includes a processor 47; heap memory 48, four bi-directional data ports 49a-d designated as port 0, port 1, port 2, and port 3; four reset-out lines 50a-d; and four reset-in lines 51a-d. The node 46 may include a transputer, such as a transputer of the T400 or T800 variety manufactured by Inmos Ltd. of the United Kingdom. The node 46 may also include supplemental off-chip random access memory for providing supplemental heap memory. Other types of I/O controllers, such as controllers 56a,b may be provided to allow communication via I/O ports 57a,b in order to interface with various computing hardware using such protocols as SCSI, Ethernet, RS-232, etc. It is to be understood that the node 46 may be a monolithic device or may be implemented using various individual components interconnected to provide memory, processing, and communication capabilities. The functional capacities of a node as defined herein may be provided, for example, by a personal computer equipped with an appropriate communication interface.

The processor 47 is a multi-tasking processor which executes tasks, such as programs, processes, routines, functions, or jobs, assigned to the node 46. The operation of the node 46 is generally managed by a kernel task. The heap 48 is a memory which stores local variables and instructions comprising each task and includes allocated space for each task's requirements such as task variables, lists, and stacks and space for packets of information.

The reset-out lines 5Oa-d are lines that carry signals to the reset-in lines 5a-d of the respective nodes to which associated data links 54a-d are connected. Any node to which the data links 54a-d of a predetermined node are directly connected shall be referred to as an adjacent node of the predetermined node regardless of the physical location of such a node relative to the predetermined node.

The transputer node 46 includes reset-in lines 51a-d which cause the node 46 to reset when a reset signal is received at any of the reset-in lines 51a-d. The reset-in lines 51a-d are connected to respective reset-out lines of adjacent nodes, if any, so that each node has the ability to cause an adjacent node to reset. Assertion of any of the reset-in lines 51a-d will cause resetting of the node 46. After being reset, the node 46 is then ready to be booted for operation. Such reset capability may be implemented in alternative embodiments by, for example, providing a single reset-in line which is connected to the output of a multi-input logical OR gate. In such an embodiment, the inputs to the OR gate provide multi-line reset-in capability. It is also noted that more than one network node may be responsive to a single reset line in order to provide the ability to reset and boot several such nodes simultaneously.

Booting, or boot-strapping, is a process in which a computing device, such as the node 46, loads its initial instructions or code to begin operation. The node 46 may load its initial set of instructions via any of the four data ports 49a-d or from an onboard non-volatile memory such as a ROM.

The data ports 49a-d, the processor 47, the heap 48, and the optional I/O controllers 56a,b are cooperatively interconnected to provide the node with processing, memory, and communication capabilities.

Information is exchanged within a network of nodes by routing packets to linked lists of packets. Packets are formatted data structures having a header and a body. The packet header contains information pertaining to routing and to other information about the packet. The packet body is an arbitrarily long field containing data or instructions. A packet routing system, including a packet routing routine called ROUTE-PACKET and router tables, is provided to selectively attach packets of information to packet lists. Such packet lists are referred to herein as (i) destination lists when the packet list is the intended recipient of the packet as indicated by information in the packet list header or (ii) intermediate lists when the packet list is not the intended recipient of the packet, but the packet list serviced by a task which transmits packets toward a particular destination or set of destinations.

Each transputer node 46 maintains interface tasks such as link-output tasks for sending packets via the ports 49a-d. Link-input tasks are also provided for receiving packets through ports 49a-d. Each one of the ports 49a-d is assigned a link-output task for controlling the transmission of packets from the node across the corresponding link. Likewise, each port 49a-d of the node is also assigned a link-input task which performs the function of receiving packets and storing packets in the heap 48. The link-output and link-input tasks facilitate inter-node transmission of packets. Other I/O controllers, such as I/O controllers 56a and 56b, as may be connected with the internal bus of a node are managed by specialized interface tasks which may transmit and receive packets as well as to encapsulate and to decapsulate packets to provide compatibility with various hardware and software communication protocols.

As part of the packet routing system, tasks can access packet lists by using packet list headers, which provide information for locating packets on packet lists. A packet list header includes pointers to the beginning and to the end of its associated packet list. To effect a transfer of a packet between packet lists on different nodes connected by transputer links, a task upon one node constructs in the heap a packet containing the information to be sent. Then the sending task invokes ROUTE-PACKET which links the packet into a selected intermediate packet list that is serviced by a link-output task. The selected packet list may alternatively be associated with another task, such as an interface task, if packets bound for the specified destination node are to be handled by such an interface task. Whenever ROUTE-PACKET is invoked to handle a packet bound for a node other than the current node, the intermediate packet list is selected according to destination packet list information in the packet header and an entry of a router table resident upon the current node. If the selected intermediate packet list is associated with a link-output task, the link-output task will, in the course of its operation, remove the packet from the packet list and then transmit the packet across a link to an adjacent node.

On the other side of the link, a link-input task will receive the packet, store the packet in the heap of its node, and then invoke ROUTE-PACKET. ROUTE-PACKET may attach the incoming packet to the destination list of the packet indicated within the header of the packet. If the destination list of the packet is located on yet another node, ROUTE-PACKET will attach the packet to yet another intermediate list selected from a router table entry corresponding to the destination node of the packet. Such an intermediate list may be, for example, another packet list serviced by a link-output task. Upon eventual arrival at the destination node, the packet is attached by ROUTE-PACKET to the destination list indicated in the packet header. Rather than incurring such time losses as are customary in synchronous intertask communication, tasks within systems send and receive messages by performing operations upon packet lists in the heap at any time without regard for the details of routing or port availability.

Routing a packet to a destination packet list on a predetermined node is accomplished by manipulating pointers in the associated packet list header and by manipulating pointers within the incoming packet and the other packets on the list, if any, in order to link the packets into the destination packet lists. Each packet contains a packet header which provides information to ROUTE-PACKET to indicate the node and address of the destination packet list header associated with the destination packet list. In cases where a packet is to be attached to a destination packet list on the immediate node, ROUTE-PACKET attaches the packet directly to the destination packet list without changing the heap location of the packet and without the intervention of an intermediate packet list. Selection of an intermediate packet list by ROUTE-PACKET for effecting transmission of a packet toward a destination list on another node is facilitated by a router table which contains information associating various network nodes with particular intermediate lists on the sending node. The router table on the next node contains routing information for the next step, and so forth, so that a packet ultimately reaches its destination by skipping from node to node.

For packets which are to be sent through transputer channels to an adjacent node which is linked by a transputer link, transmission is effected by attachment to an intermediate list that is serviced by a link-output task. Packets which are to be sent to nodes accessible via other types of network links, for example an ethernet, are attached to intermediate lists serviced by specialized interface tasks, such as an ethernet encapsulator, which encapsulates and translates the packet into a suitable form depending upon the nature of the network to which the task interfaces. A router table contains at least sufficient information for selecting a packet list to which a packet is to be attached whenever the packet is addressed to a valid node number that does not match the current node.

Tasks within a network may access linked lists of packets, if any, waiting to be processed. Each such list of packets is associated with a packet list header which provides information for managing access to the packet list. A task variable 'PKT is used to point to the heap address of the current packet of interest for a predetermined task. Another task variable, 'LIST, is used to point to the packet list header associated with the packet list currently of interest to the task. In order to determine whether any packets are attached to a packet list, a task may invoke a routine called GET-PACKET to set 'PKT to the address of the first packet on the list indicated by 'LIST and to adjust the packet list header accordingly to remove the packet from the list.

GET-PACKET will cause a task to sleep, or to be taken off of the processor's active process queue, if there are no packets on the packet list. When the task has been de-activated, the task is placed upon a queue of inactive tasks waiting to remove packets from the packet list. Pointers to the beginning and to the end of the inactive task queues are maintained by the packet list header. Re-activation of an inactive task may be effected in one of two ways. GET-PACKET may be invoked with or without a parameter specifying a timeout interval. When the packet removal routine is invoked without a timeout interval, hereinafter referred to simply as GET-PACKET, the invoking task will remain inactive until a packet arrives on the selected list. When GET-PACKET is invoked with a specified timeout interval, hereinafter referred to as GET-PACKET.TN, the invoking task is placed onto the inactive process queue for a finite timeout interval of N milliseconds if there are no packets on the packet list serviced by the invoking task. Reactivation of the task may be caused by either the passage of the timeout interval or by the arrival of a packet on the packet list. The condition causing the invoking task to return to the active process queue may be determined according to a task-local flag which is set when the invoking task is re-activated.

A basic operation of a link-output task, for example, is to invoke GET-PACKET.TN to obtain a packet from its packet list and then to transmit that packet to an adjacent node. When a link-output task calls GET-PACKET.TN and reaches timeout without detecting the presence of a packet on the packet list, the link-output task will then transmit a specialized packet termed an idle packet in order to ascertain the status of the communication link. As described more fully hereinafter, such transmission of idle packets by link-output tasks upon timeout of GET-PACKET.TN is a key feature by which integrity of the network may be maintained.

The packet list header associated with each packet list includes pointers to a linked queue of tasks, if any, which have been inactivated by GET-PACKET or GET-PACKET.TN in the course of attempting to obtain a packet from an empty packet list. When ROUTE-PACKET attaches a packet to a packet list, the first task on the inactive task queue is re-activated and the packet list header is adjusted in order to advance other waiting tasks, if any, forward in the inactive task queue.

Route-Packet and Router Tables

The packet routing system includes the routine called ROUTE-PACKET for linking packets to packet lists. The packet routing system further employs data structures called router tables which ROUTE-PACKET uses to select lists to which to attach packets that are destined for other nodes. A router table contains the addresses of packet list headers that are associated with packet lists serviced by, for example, link-output tasks, specialized interface I/O controller tasks, or tasks corresponding to virtual nodes.

When a predetermined task constructs or otherwise obtains a packet that is to be sent to another task, the predetermined task invokes ROUTE-PACKET. A general flowchart of the procedure followed by ROUTE-PACKET is shown in FIG. 2. ROUTE-PACKET 20 provides the function of attaching the current packet of a predetermined task to a packet list on the same node. ROUTE-PACKET preferably accomplishes this function by re-arranging pointers within packet list headers and within packets rather than actually changing the location of packets within the heap. Pointers and other information within packet list headers and within packet headers are adjusted as needed in order to attach packets to packet lists. In instances where the current packet of a predetermined task is destined for a packet list on another node, ROUTE-PACKET uses information encoded within a router table to determine the specific node-local intermediate packet list to which to attach the current packet. Usually, ROUTE-PACKET will determine an appropriate value for a list pointer indicating the address of a packet list header associated with a packet list to which to attach the current packet.

Upon being invoked in step 21, ROUTE-PACKET 20 examines the packet header in step 22. Among the information encoded within the header of a packet is a value designated PKT-DNODE which indicates the node number of the destination node. In step 22, ROUTE-PACKET 20 compares PKT-DNODE to a node-local variable TNODE, which indicates the node number of the current node. If the current node is the destination node found in the packet header such that PKT-DNODE=TNODE, ROUTE-PACKET then, in step 27, proceeds to validate a destination list identification (DLID) also contained in the packet header. The DLID includes the node number, the packet list header address, and an identifying code pertaining to the destination packet list.

If an invalid DLID is discovered in step 27, ROUTE-PACKET 20 executes an error-handling routine in step 29. The error-handling routine of step 29 sets a status field within the packet header to indicate that a list validation error has occurred. Then, a list pointer is set to the address of a packet list header associated with a packet list that is serviced by a predetermined error handling task, such as the kernel task of the node. Alternatively, ROUTE-PACKET may determine whether the packet contains an indication that the packet is to be returned to the sending task if a delivery error is encountered. If so, ROUTE-PACKET may then route the packet to the sending task. If such a return request is not indicated by the packet, or if the packet contains an indication that the packet had incurred a previous delivery error, ROUTE-PACKET may discard the packet and exit. Otherwise, in step 30, the packet will be attached to a packet list of the predetermined error handling task.

If a valid DLID is found in step 27, control passes to step 28. In step 28, the list pointer is set to the destination packet list header address and the packet is subsequently attached to the associated destination packet list in step 30.

Packets are routed by ROUTE-PACKET 20 to packet lists other than the destination packet list indicated in the packet header when, in step 22, the destination node is found to have a different value than the current node, i.e. PKT-DNODE.noteq.TNODE. In that instance, control passes from step 22 to step 23 wherein ROUTE-PACKET consults the router table in order to determine the location of an intermediate packet list header associated with an intermediate packet list which is designated to accept packets destined for the specified PKT-DNODE. Such an intermediate packet list may, for example, be serviced by a specialized interface task or one of the link-output tasks of the sending node governing the port of the sending node through which the packet is to be transmitted toward the destination node of the packet.

If an error is encountered during consultation of the router table in step 23, such as failure to find a packet list for PKT-DNODE, then step 24 directs control to step 26 wherein a packet status field is set to indicate a node number error. Then, the list pointer is set to the address of a packet list header associated with a packet list serviced by the kernel task or other designated error handling task. The packet is then attached to the indicated packet list in step 30.

If no error is found during consultation of the router table in step 23, then ROUTE-PACKET proceeds through step 24 to step 25 wherein the list pointer is set to the contents of an index field obtained during router table consultation in step 23. The index pointer indicates the router table entry containing the address of the packet list header of the intermediate packet list to which the packet is to be attached. ROUTE-PACKET 20 then proceeds to step 30.

In step 30, ROUTE-PACKET 20 attaches the current packet of the invoking task to a packet list indicated by the list pointer that was set during any of the procedures leading to step 30. Additionally, ROUTE-PACKET may discard packets containing an erroneous or invalid DLID and then exit prior to reaching step 30, as discussed previously herein.

In step 30, the packet may be attached to the packet list of the kernel task in case an error is encountered by ROUTE-PACKET 20 during its execution. The packet may be attached to a destination list if the destination list and the invoking task are on the same node. Finally, the packet may be attached to an intermediate list determined by the router table if the packet is addressed to a destination list resident upon a node that is different from the invoking task's node. Then, in step 3, the packet is removed from the invoking task by setting the value of 'PKT of the invoking task to NULL since the packet has been placed upon another list and is no longer associated with the invoking task.

ROUTE-PACKET then proceeds to step 32 wherein ROUTE-PACKET consults the packet list header fields pertaining to the queue of inactive tasks, if any, that may be waiting to take packets from the packet list to which the packet had been attached in step 30. If there are no such inactive tasks, then ROUTE-PACKET proceeds to step 33 and exits. If, in step 32, there are any inactive tasks on the queue, then an inactive task is re-activated in step 32a. Inactive tasks in transputer-based systems may be reactivated via an alternative input channel of the inactive task. Other task activation mechanisms, such as task-local registers for indicating active status may be employed. When an inactive task is reactivated, a flag local to that task is set to indicate the condition, or alternative input channel, which led to its reactivation. Preferably, tasks are taken off of the inactive queue on a first-in/first-out basis although other queuing protocols may be implemented. ROUTE-PACKET 20 then proceeds to step 33 and exits.

The structure of a router table 40 is illustrated in FIG. 6. Only a portion of a router table is shown for purposes of illustration since a router table may be arbitrarily large depending upon the number of nodes in the network and the network topology. The router table is a list of pairs of destination node interval limits and pointers to packet list headers of intermediate packet lists to which packets addressed to nodes within the intervals are to be attached. The router table for a given node is stored in the heap at an address indicated by a node-local variable, 'ROUTER-TBL 45. The first entry 43 in the router table 40 contains the number of interval/list pairs in the table. The second entry 44 is a number corresponding to the lowest node number in the network. Entries 41a and 41b in the table identify packet list header addresses. Entries 42a and 42b identify the limits of destination node number intervals consecutive to the previous destination node number interval entry in the table. The table thereby provides packet list header addresses which correspond to intervals of node numbers.

For example, entry 42a is used in conjunction with entry 44 to define a range, inclusive with the contents of entry 44, of destination node numbers for which packets will be attached to a packet list indicated by entry 4a. The contents of entry 4a include the address of a packet list header associated with the indicated intermediate packet list. Such a packet list could be, for example, a packet list serviced by a link-output task. Similarly, entry 42b is used in conjunction with entry 42a to define another range, exclusive of the contents of entry 42a, of node numbers for which packets will be attached to a packet list associated with a packet list header address stored in entry 41b. Different intervals of node numbers may be assigned to the same packet list. All of the nodes in the network, except for the node on which the specific router table is resident, may be identified on the router table so that each node is assigned a packet list to which ROUTE-PACKET will attach packets destined for that node.

Because ROUTE-PACKET does not consult the router table in order to route packets destined for packet lists on the local node, there is no router table entry needed for the node upon which the table is resident. For intra-node packet communication, ROUTE-PACKET attaches a packet directly to the destination packet list rather than by attaching the packet to an intermediate packet list selected from the router table. Such intra-node transfer of packets is accomplished by adjusting pointers within the packet list headers of the affected packet lists and within the affected packet headers rather than by actually changing the location of the packets in the heap.

The heap address of the router table 40 is known to ROUTE-PACKET via a