[42912] in North American Network Operators' Group
Re: Points of Failure (was Re: National infrastructure asset)
daemon@ATHENA.MIT.EDU (Peter van Dijk)
Tue Sep 25 16:26:12 2001
Date: Tue, 25 Sep 2001 22:20:13 +0200
From: Peter van Dijk <peter@dataloss.nl>
To: nanog@merit.edu
Message-ID: <20010925222013.D28490@dataloss.nl>
Mail-Followup-To: nanog@merit.edu
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <Pine.BSF.4.21.0109251539280.26736-100000@vapour.net>; from batsy@vapour.net on Tue, Sep 25, 2001 at 04:04:38PM -0400
Errors-To: owner-nanog-outgoing@merit.edu
On Tue, Sep 25, 2001 at 04:04:38PM -0400, batz wrote:
[snip]
> Is there a geometric method of measuring the 'meshedness' of a
> given set? If you take all the as-paths from a sampling of
> peers across the Internet, and show the relative density of
> where the respective paths converge, you can get a good picture
> of who's transiting the most routes.
The mathematical term 'connectivity' measures the least number of
vertices that has to be destroyed to stop a network from being fully
connected.
Any network that contains a SPoF (even if it only causes one small bit
to go lost) has a connectivity of '1'. Any network that you need to
hit at least 2 vertices (routers and switches would be vertices, lines
would be edges) has a connectivity of '2'.
There are very nice mathematical methods for determining the
connectivity and connectionness of a graph (network).
I can recommend Skiena's "The algorithm design manual" for anybody
interested. It is supposedly available online in HTML (I bought the
dead tree version :)
Greetz, Peter
--
Monopoly http://www.dataloss.nl/monopoly.html
