PERFORMANCE ANALYSIS OF A SHORTEST-DELAY PROTOCOL
Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Software Patent Institute
Li, Liang: AUTHOR [+4]
PERFORMANCE ANALYSIS OF A SHORTEST-DELAY PROTOCOL* Liang Li, Herman D. Hughes, Lewis H. Greenberg Department of Computer Science
PERFORMANCE ANALYSIS OF A SHORTEST-DELAY PROTOCOL*
Liang Li, Herman D. Hughes, Lewis H. Greenberg
Department of Computer Science
Michigan State University
East Lansing, Michigan 48824
A generalized shortest-delay access method (SDAM) protocol
for local networks is defined and evaluated. This protocol dif-
fers from a previously reported SDAM 1161 in that it accommodates
a branching-bus topology instead of a single-bus network. It is
shown that for small bus-delays, SDllM performs very close to that
of M/D/~--with perfect scheduling. In this paper, the performance
evaluation of SDAM is more pragmatic: in that the effects of vari-
ous protocol overheads (e.g., decoding, turnaround time, initial-
izing packets, etc.) are taken into account. An analysis of the
tradeoffs between exhaustive and nonexhaustive transmission dis-
ciplines is also presented.
Keywords: Local network, Protocol, Virtual token, Bus propaga-
tion delay, Branching-bus topology, Protocol over-
head, Carrier-sensing, Exhaustive/non-exhaustive
transmission, Queueing delays.
* Research supported in part by NSF' - Grant No. PRM-8115413
In a recent paper [161, Li and Hughes proposed an access-
level protocol for local computer networks (LCN). This protocol
employs a scheme which is analogous to the one-directional short-
est-seek-time-first (SCAN) algorithm advanced by Denning et al.
[6,7,8] and :is referred to as the "shortest-delay access method"
(SDAM). Briefly, the SDAM protocol has the following properties
-.works on a single-trunk bus-structured local network,
*.has a decentralized control,
*.maintains conflict-free transmissions,
*.uses simple algorithms and little control overheads,
performs closely to M/D/l with perfect scheduling in ideal
cases (taking into account the bus propagation delay). In
particular, the performance of SDM exceeds that of the
popular CSMA/CD protocol in medium to high loads,
*.provides adequate services to a large number of users
(nodes) (e.g., 1000 nodes).
1 Recognizing the inconvenience of a single-bus topology (e.g.,
i reconfiguring the network or adding new nodes at certain loca-
tions), this paper generalizes the SDAM protocol to a branching-
bus network. A discussion of this generalization is presented
in Section 2 of this paper.
In Section 3, two variants of the SDAM protocol, the closed
SDAM (C-SDAM) and the open-ended SDAM (OE-SDAM), are closely ex-
amined for their relative merits. That is, the performance of
these protocols is evaluated by both analytic and simulation mod-
els and compared to that of M/D/ŵith perfect scheduling. Since
the OE-SDAM provides equal access to all nodes, the performance
evaluations throughout Section 3 will focus on this protocol.
In order to claim that the implementation of SDAM is feasi-
ble, the effects of th...