**Project
1 Computer Networks and Graphs
**

**Introduction: **your group has been given the task of reviewing
the computer networks of a national manufacturing company. The wide area
networks (WANs) are already in place, but questions have been raised concerning
reliability and security, as well as cost.

The company you have been hired by manufactures small runs of one of a kind micro electrical components such as miniature motors and pumps. The turnaround time from design to manufacture to shipment is very short and the companies ability to be responsive is a key element in its success.

One element in the responsiveness of the company has been its ability to make use of electronic communication; not just e-mail but images, video, and conference work. This has meant that at a moments notice, the entire expertise of the company may be focused on a problem, regardless of the physical location of the involved parties. Also, computer generated prototypes often involve reworking at the customers sight, with the involvement of engineers in other areas of the country.

Recent breaches in the security of Internet have made the company realize that it may be vulnerable, and communications downtime of any length is not something it can afford.

**Further Information: **the company has property in Seattle, San
Francisco, Salt Lake City, New Orleans, Boston, Nashua NH,Anchorage, Dallas,
Chicago and Worcester. It also has a subcontractor in Seoul, South Korea
which it communicates with via satellite. All other lines are dedicated
data lines rented from companies such as AT&T and MCI.

A graph of the communications paths is below; this shows how the major locations are joined. In addition, each location has offices and plants within it and each of those has its own topology.

**Background: **section 8.1 of Kolman; any book with introductory
material on graph theory and adjacency matrices such as *Applied Combinatorics*
by Fred Roberts (1984, Prentice-Hall)

**Goals: **The overall goal is to develop mathematical techniques
and algorithms which might be used by the company in the future to study
and evaluate their networks. Thus, while accurate answers to the problems
below are important, of even greater importance is the written description
of the technique used to obtain it.

In each of parts 2-4 , please provide an answer in **two** ways:

**a**. by generating an answer (or answers) by hand or visually,
using the sample network provided

**b**. by developing a matrix based method which would yield the
information needed for ** any** communication network, no matter
how big. Please describe your method with suitable clarity so someone from
the communications company may understand and implement it.

**Part** **1**. set up the "adjacency matrix" for the
graph described above.

**Part** **2.** in networking terms, for a given communication
from one place to another, a **hop** is defined as the number of intermediate
sites it must go through to get where it is going. For example, if one
sends email from Boston to Seattle , then there are 2 hops.

Find the **worst** cases of communications in terms of numbers of
hops involved.

**Part** **3.** In terms of security, we are interested in those
situations where there are few or no options for given communication between
2 sites. If there is only one path for a given communication, then that
communication is vulnerable should that path break down.

Give all communication paths a "susceptibility index" which
equals the number of * different *ways that a message may get
from one site to another. Clearly, then, those pairs with a susceptibility
index value of 1 are of great concern. (this should be presented in table
form)

Make recommendations as to what links you would **add** to improve
the reliability of the network.

**Part 4**. the company is also concerned about measuring usage.
Specifically, how much information is passing *through* one site as
compared to another.

By examining powers of the adjacency matrix, what can you say about this? Of interest may be the fact that if you multiply a matrix by a column of all 1s, the result is a column of row sums. Similarly if you multiply on the left by a row of all 1s, the result is a row of all column sums. (try it out by hand!)

**Part 5**. Next, find the largest positive eigenvalue of the adjacency
matrix and an eigenvector associated with it. Can you relate the components
of the vector in any way to your results about usage? There are two ways
this may possibly be done:

a. by the "Power Method" (see project 5 )

b. by using an appropriate software function such *eigenvals* in
Maple

or *poly* and *roots* in Matlab.

**References** Information on networking may be found in *Technical
Aspects of Data Communication* (2nd ed) by John McNamara (Digital Press)
as well as many other books.