Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!ihnp3!mth
From: mth@ihnp3.UUCP
Newsgroups: comp.ai
Subject: Network Complexity
Message-ID: <292@ihnp3.UUCP>
Date: Thu, 19-Feb-87 17:47:52 EST
Article-I.D.: ihnp3.292
Posted: Thu Feb 19 17:47:52 1987
Date-Received: Sun, 22-Feb-87 15:46:50 EST
Organization: AT&T Bell Labs, Naperville, IL
Lines: 40
Keywords: graph theory, computer networks, brain hurts

(sorry if this is a duplicate posting, but my machine burped)

I am in the process of putting together a paper which attempts to
motivate planning and development of software based Network Management tools.
In general, such tools would be both STRATEGIC, eg. network topology planning,
from the perspective of capacity, security, fault tolerance, etc, and
TACTICAL, such as visualization of network activity, dynamic routing, fault
recovery, congestion avoidance, etc.  Clearly, this fields is ready for
and in desperate need of AI, which is why I'm addressing it to this group.

Now, my intuition tells me that as these networks become more complicated,
we'll realize that the seat-of-the-pants network management we're used to is
inadequate, and we'll wish that we had spent time developing the right tools
to do the job.  I envision the complexity of our computer networks to be
exploding at some exponential rate, while our ability to understand and
control them is falling behind, growing relatively slowly.  This brings
me to my QUESTION:

	If we define the "complexity" of a computer network as a
	measure of difficulty in observing, understanding, and
	excercising a modicum of control over it, how is this
	"complexity" estimated?

	If we further choose a simple but intuitive way of representing
	a computer network by a graph, how do we quantify this "complexity"
	with respect to the graph's topology?

Clearly metrics such as the number of nodes, edges circuits etc have intuitive
appeal, but do not individually seem to convey the underlying combinatorial
explosion that, I believe, lurks underneath.

Are you aware of any analytic, graph-theoretical, heuristic, empirical,
or otherwise useful metrics of such "complexity"?  I am not necessarily
looking for some absolute measure of the thing, but general concepts.
Any facts, comments, opinions and thoughts will be most appreciated.

					M. Horbal
					@ Bell Labs
					ihnp4!ihnp3!mth
					(312) 979-6496