Browse Prior Art Database

Tree Based Local Network

IP.com Disclosure Number: IPCOM000045739D
Original Publication Date: 1983-Apr-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 3 page(s) / 47K

Publishing Venue

IBM

Related People

Franaszek, PA: AUTHOR

Abstract

Background. A local Network is a means for interconnecting a set of proximate digital devices. In practice, many such networks operate via a form of routing which may be termed address-independent. Roughly speaking, this implies that any node that does forwarding need not examine the origin or destination address attached to a message in order to make a forwarding decision. The advantages are simplicity of control and speed of operation. Examples of such networks include loops and busses. Recently, it was shown that if a routing strategy more general than that for a loop is to be employed, a network with address-independent forwarding must have at least M=2(N-1) directed links, where N is the number of nodes.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Tree Based Local Network

Background. A local Network is a means for interconnecting a set of proximate digital devices. In practice, many such networks operate via a form of routing which may be termed address-independent. Roughly speaking, this implies that any node that does forwarding need not examine the origin or destination address attached to a message in order to make a forwarding decision.

The advantages are simplicity of control and speed of operation. Examples of such networks include loops and busses. Recently, it was shown that if a routing strategy more general than that for a loop is to be employed, a network with address-independent forwarding must have at least M=2(N-1) directed links, where N is the number of nodes. A configuration which meets the minimum, M=2(N-1), is the bidirectional tree, for which three types of address-in dependent forwarding were derived. A system concept is described which permits the use of Type 3 forwarding in a contention network. The result is a system with a number of desirable properties.

Fig. 1 illustrates the overall network structure, which is a bi-directional tree. Nodes are of two kinds: leaf nodes and intermediate nodes. The leaf nodes represent digital devices to be attached to the network; intermediate nodes are special units which perform network control and message forwarding. Transmission Protocol.

Each link has a message buffer at the receiving end. A node V(i) is permitted to transmit only if the receiving buffer associated with each link it will transmit on is empty. In the case of a leaf node, there is only one such buffer.

The routing and pacing protocols are as follows. A message received at an intermediate node V(i) from some other node V(j) is forwarded to all nodes linked to V(i) except V(j). This ensures that each message will propagate throughout the network. The link to V(j) from V(i) (the return path) is used to send a special signal to notify V(j) that its buffer at V(i) is empty. This signal is not forwarded from V(j). The system thus contains two classes of messages: standard messages containing information to be transmitted over the network, and special signals used for pacing.

The main point of the system analysis is the observation that routing of messages in the network is such that the return path is unused, and thus available for transmission of the special signal T which is used to signify the availability of the buffer for the next message, or to inform the previous node that the message it transmitted was not received correctly. Thus, messages are not lost due to contention, and erroneous transmissions do not propagate through the network. Operation of the Leaf Nodes.

Fig. 2 shows a block diagram of a leaf node. This consists of a communicating device and a network attachment. Incoming messages are decoded and placed in the reception buffer. As this buffer is emptied or cleared

1

Page 2 of 3

by the communicating device, the le...