Browse Prior Art Database

PERFORMANCE ANALYSIS OF A SHORTEST-DELAY PROTOCOL

IP.com Disclosure Number: IPCOM000148971D
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]

Abstract

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 ABSTRACT 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. I Keywords: Local network, Protocol, Virtual token, Bus propaga- tion delay, Branching-bus topology, Protocol over- head, Carrier-sensing, Exhaustive/non-exhaustive transmission, Queueing delays.

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

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

ABSTRACT

    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.

I

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
[16]

:

-.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).
i

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