Network Connectivity, Graph Theory, and Reliable Network Design

Network engineers are tasked with designing reliable networks while balancing business and physical concerns such as cost and available space. Reliable networks are designed to ensure packets can still reach required destinations even upon a node or router failure. At the design level, how do we ensure a network is “connected” enough to provide a required number of alternative paths from any node to any other node?

Mathematicians, electrical engineers, and early network engineers studied these problem using graph theory. We have a formal definition of the measure of connectivity of a graph or network that also allow us to determine the “weak points” whose failure would sever the network into 2 or more separated blocks. In this webinar, the attendee will be introduced to the terminology and study of graph theory in context with these engineering questions in order to develop a new perspective and skill set he/she can apply to his day-to-day work (no background in mathematics or graph theory is required).

We will begin with the definition of a graph, and other basic terminology such as the degree of a vertex, connected graphs, paths, and complete graphs. Next, we will move to a discussion of connectivity. The attendee will learn what a cut-vertex is, and several ways of finding them in a network. The notion of a nonseparable graph will be mentioned, and we will discuss how we can know if a given network is nonseparable. These fundamentals will enable us to understand what the connectivity measure of a graph is, its relation to the resilience and reliability of a network. We will also look at using powers of graphs to add edges to achieve a desired level of connectivity per given requirements.

Availability

This webinar is part of Internetworking roadmap and accessible with standard subscription

Start now Access content

Agenda

Intro: Why we care about graph theory and connectivity

Graph Basics:

  • What is a graph?
  • What are the parts of a graph?
  • How do we get around on graphs?
  • What does it mean to say a graph is connected?
  • What is the degree of a graph?
  • What is a complete graph?

Connectivity:

  • What is a cut-vertex? What does it mean if we have one in our network? How do we find these?
  • Nonseparable graphs — How do we know if our network is nonseparable? Can we make a network nonseparable?
  • Vertex connectivity and its relation to reliability and resilience of a network
  • How do we determine the maximum connectivity graphs? (Intro to Harary graphs)
  • Using powers of graphs to add edges to achieve connectivity requirements

Takeaway

The key takeaways for the attendees will be

  • New familiarity with a mathematical topic highly applicable to his field (and partially developed as a result of questions posed in early network engineering)
  • An understanding of what connectivity in networks means mathematically
  • A new perspective on network design

Author

Rachel TraylorDr. Rachel Traylor is a professional private-sector mathematician and the cofounder of the Math Citadel, a research and consulting firm specializing in mathematical consulting. She received her PhD in mathematics from the University of Texas at Arlington, a MS Statistics and BS Applied Mathematics from Georgia Tech. Her research interests include probability theory, reliability, and queuing theory; in particular, she’s been very interested in sequences of dependent random variables. She’s a former senior research scientist for Dell EMC, former university lecturer in mathematics and statistics (Foothill College, University of Texas at Arlington, Georgia Tech), and former DBA/Quality Analyst at Lockheed Martin. She has 6 pending patents and 9 academic publications in the fields of probability and reliability theory.

More about Rachel…