Browse Prior Art Database

Original Publication Date: 1899-Dec-30
Included in the Prior Art Database: 2007-Apr-12
Document File: 27 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Li, Liang: AUTHOR [+4]


PERFORMANCE ANALYSIS OF A SHORTEST-DELAY PROTOCOL* Liang Li, Herman D. Hughes, Lewis H. Greenberg Department of Computer Science

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 10% of the total text.

Page 1 of 27


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

[This page contains 1 picture or other non-text object]

Page 2 of 27

1. Introduction
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

: 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...