Method and means for demand accessing and broadcast transmission among ports in a distributed star network

• US 4,347,498 A
• Filed: 11/21/1979
• Issued: 08/31/1982
• Est. Priority Date: 11/21/1979
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Closs, Felix H., Lee, Robert P.
• Primary Examiner(s): Swann, III, Glen R.
• Application Number:
  US06/096,356
• Time in Patent Office: 1,014 Days
• Field of Search: 340/147 T, 340/147 R, 340/147 LP, 370/60, 370/94, 370/85
• US Class Current: 370/408
• CPC Class Codes: H04L 12/44 Star or tree networks
• CPC Class Codes: H04L 12/56 Packet switching systems

Abstract

A demand access broadcast transmission method and means is capable of supporting random port access and any-to-any transmission at very high data rates. A communication medium (FIG. 2) formed from an inverted tree network of nodes (1, 18, 22) and full duplex connecting links (13, 17, 19) permits the establishment of a path lock up-link through the network from a demanding port to a root node on a first-come first-serve demand access basis with arbitration at each distinct tree node level (FIG. 3). Broadcast transmission is perfected down-link over all fan-out paths from the root node. Collision is avoided by locking a path to a port and by limiting race conditions among active ports to only the leading edges of messages. Thus, relinquishment of a broadcast channel overlapped with transmission of a message does not result in path seizure since the occurrence of message leading edges is the singular path connection invoking event.

Claims

1. A data communications system comprising:

a transmission medium formed from an inverted three network of nodes and full duplex connecting links, the tree network having a network root node, said root node of a tree or subtree thereof having an in-degree of zero, each duplex link including an up-link and a down-link respectively defining a signal path direction toward or away from the network root node, each up and down-link being in either an idle or occupied state;

a plurality of transceiving ports attaching the network at selected nodes, ready ones of the ports transmitting messages at will;

each nodes includes;

means for ascertaining whether the state of each terminating up-link and down-link is idle or occupied; and

means responsive to the first occurring ascertained state transition from idle to occupied among the terminating up-links for completing an exclusive signal path connection to an outbound up-link only if the outbound up-link is concurrently idle.

2. A data communication system according to claim 1 wherein each node further includes:

a pulse source; and

means responsive to an ascertained idle state on all terminating up-links for coupling said pulse source to an outbound up-link.

3. A data communication system according to claim 1, wherein the state ascertaining means includes:

means for terminating an up-link;

a first register;

means responsive to a transition from a time varying waveform to a waveform of constant slope on said up-link for setting the first register to a first value and responsive to a transition from a constant to a time varying waveform for setting the register to a second value.

4. A data communications system according to claim 1, wherein the signal path connection means includes:

means responsive to the initiation of a signal path connection to an outbound up-link for sensing the duration of the round trip propagation delay between a selected tree node and the network root node and for invoking a wrap-around loop connection between the terminating up-links and outbound down-links at the network root node upon the second round trip propagation'"'"'s exceeding a predetermined amount.

5. A data communication system according to claim 1, wherein the signal path connection means includes:

means responsive to a state transition from occupied to idle upon an up-link within an established connection for relinquishment of said connection.

6. A method for any-to-any port transmission of messages through an inverted tree network of nodes and full duplex connecting links, the tree network having a network root node, said root node of the tree or sub-tree thereof having an in-degree of zero, each duplex link including an up-link and a down-link respectively defining a signal path direction toward or away from the network root node, the method being executable by ready-to-transmit ones of a plurality of transceiving ports individually coupling the network at selected nodes, comprising the steps of:

establishing a message initiated path lock up-link through the network from a ready-to-transmit one of the ports to the network root node only by way of a first come, first serve demand access discipline among the up-links terminating at each distinct tree node level to a concurrently idle out-bound up-link; and

broadcast transmitting any message over all down-links fanning out from the network root node, which message was received over an up-link path connection to said network root node.

7. A method according to claim 6, wherein the messages consist of packets.

8. A method according to claim 6, wherein each message includes an addressee port, the method steps further comprising:

confirming to the originating port that its message was delivered to the addressee port by receipt of the down-link echo of the transmitted message by said originating port.

9. A method according to claim 6, wherein the network is operable in a data and idle mode, the method steps further comprising:

impressing signals indicative of the idle mode upon up-links not transmitting messages;

sensing at the up-links terminating in each node any signal change from idle-to-data-modes; and

causing the fist come, first served demand access discipline to be executed at any given node upon sensing idle-to-data-mode transition upon any up-links terminating in the given node.

10. A method according to claim 9, wherein the idle mode signals impressed upon up-links are formed from a predetermined pattern, mode transition being sensed as the change in the up-link from any other pattern to the predetermined pattern (FIGS. 7, 11).

11. A method according to claim 10, wherein the predetermined pattern consists of a series of consecutive pulses.

12. A method according to claim 10, wherein the predetermined pattern consists of a constant level, while the nonpredetermined pattern consists of ternary levels.