Browse Prior Art Database

Decentralized Request Resolution Mechanisms

IP.com Disclosure Number: IPCOM000088766D
Original Publication Date: 1977-Jul-01
Included in the Prior Art Database: 2005-Mar-04
Document File: 3 page(s) / 66K

Publishing Venue

IBM

Related People

Bantz, DF: AUTHOR

Abstract

For reasons of reliability and modularity of performance, it is desirable to eliminate centralized control for resolution of simultaneous requests for a shared resource (e.g., a communication path).

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

Decentralized Request Resolution Mechanisms

For reasons of reliability and modularity of performance, it is desirable to eliminate centralized control for resolution of simultaneous requests for a shared resource (e.g., a communication path).

Although there are known methods for eliminating central control, typically in such methods the resolution of conflicting requests involves retry at pseudo- stochastically determined intervals. The performance in such methods is adequate for constant-rate traffic due to mutual synchronization, but offers less than adequate performance on random traffic. The scheme disclosed herein resolves contention with a purely deterministic mechanism and does not depend on constant-rate traffic for good performance. Also, no bus transmission cycles are lost; each bus cycle that is contended for will have successful transmission.

With reference to Fig. 1, a shared transmission path is contended for by several attachments, A(o), A(1),..., A(n), each having a unique address. A request loop of k lines (k >/- log(2)n) threads all attachments. A common timing line defines the beginning of each bus cycle (each instant at which transmission requests are permitted).

When the timing line is true, indicating that transmission requests are permitted, each attachment that wishes to transmit places its address A(i) on the outbound link of the request loop. Each attachment then monitors the inbound link of the request loop and performs one of the following actions:

1. If the attachment does not want to transmit at this time, it passes the value on the inbound link directly to the outbound link.

2. If the attachment does wish to transmit at this time, it compares the incoming address with its own address. If the comparison indicates that the incoming address has higher priority than the attachment's address, the attachment passes the incoming address to its outbound link. If the incoming address and the attachment address are of equal priority, then the incoming address must be passed to the outbound link. The mechanism for priority assignment to addresses must be identical in all attachments.

3. If any attachment that wishes to transmit recognizes its own address on its incoming link, then that attachment has been granted permission to transmit.

To illustrate the scheme, suppose n = 2 in Fig. 1 (three attachments), and addresses 0, 1 and 2 are assigned. Suppose the highest priority is assigned to the largest address, and both A(1) and A(2) wish to transmit. The addresses on the links 1(o), 1(1) and 1(...