Network Connectivity, Graph Theory, and Reliable Network Design
Overall rating: 4.74 Instructor: 4.81 Materials: 4.84 more …
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 this 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 terminologies 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 the desired level of connectivity per given requirements.
Agenda
Graph Theory: Connectivity and Network Reliability
We will begin with the definition of a graph, and other basic terminologies such as the degree of a vertex, connected graphs, paths, and complete graphs. Next, we will move to a discussion of connectivity.
In this session, you 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 the desired level of connectivity per given requirements.
Graph Theory: Trees
Graphical trees form the “root system” of many operations in networking, including path-finding, connectivity determination, and of course are the structure behind the famous STP protocol. In this lecture we’ll focus on trees, discussing some types and their properties. We’ll take a look at different ways to find minimum/maximum spanning trees, counting how many spanning trees we have in a network, finding elementary paths, implementing different algorithms, and will try to dive a little deeper into STP protocol to understand exactly what it’s doing and why graph theory mattered so much.
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 Traylor is a mathematician whose favorite coworkers are engineers. Her research interests span pure and applied mathematics, but mainly focus on probability theory and its applications to reliability and queueing. She’s invested in closing the disconnect between academic mathematics and the practical world of engineering. She’s held private-sector research positions at Dell EMC, done time as a database administrator for Lockheed Martin Aeronautics, and been an adjunct professor/lecturer at several colleges and universities across the US (Georgia Tech, the University of Texas at Arlington, Marquette University, and Foothill College).
Happy Campers
About the webinar
- it would be good to hear a similar talk on the different algorithms related to networking (eg. SPF)
- Mark Horsfield
- This just scratched the surface; I would love to see more material that dives deeper into various areas mentioned during the webinar. Great content, I really enjoyed it!
- (Anonymous)
- Just about everything that happens in networking involves math in some form or another. We may not directly interact with the math very much, but knowing how it works is what I consider to be a portion of foundational knowledge that every good network architect/engineer should possess.
- Bruno Wollmann
- It was a great session. Up until this session I had foundation knowledge on the topic. A great start and look forward to another session on this topic
- Michael Sifuentes
- Few of my fellow network/system engineers have a solid background in CS (myself included). Sessions like this one inform us about fundamental concepts that are the foundation of the technologies we work with. I look forward to learning more in future sessions!
- Daniel Justice
- It was pretty good overall. Since Rachel is an academic and has no network engineering experience, it was clear that she struggled on a few occasions to connect the theory and application. It was valuable and interesting information all the same.
- (Anonymous)
- I would like to see the math focused webinars continue. If they do, something focused on the theory of traffic engineering would be very interesting to me.
- Steven Dodd
Tweets
- Great webinar this morning with @ioshints featuring @MathCitadel discussing network connectivity, graph theory, and reliable network design. It was time well spent on a holiday Monday in Canada. I’m looking forward to more of these in the future.
- @wollmanbruno