Welcome!

SDN Journal Authors: Pat Romanski, Destiny Bertucci, Liz McMillan, Elizabeth White, Amitabh Sinha

Related Topics: SDN Journal

SDN Journal: Blog Post

Graph Theory and Calculating Network Topologies

Any network can be represented as a graph

Over the past few weeks I have had several conversations related to calculating network topologies and how packet forwarding is done based on those topologies. I wrote this post about a year ago explaining some of these details, but after a conversation with a customer earlier this week, I wanted to explain in a little more detail and relate it not only to Shortest Path First methods, but also to more traditional L1 traffic engineering and path creation.

Graphs
Any network can be represented as a graph. The switches in the network are the vertices or nodes in the praph, the links between them the edges. The graph now represents the network and graph theory can be applied to find paths between any two nodes in the graph. Edges can have weights or metrics associated with them, or any other set of constraints that you may want to articulate for that edge (latency, bandwidth, cost, etc). The goal of any path algorithm is to find the best path or paths from a node to all other nodes.

The most common algorithms in use in networking today (OSPF, ISIS) are variations on a Shortest Path Forwarding algorithm or SPF. Published by Dutch computer scientist Dijkstra, the most popular algorithms simply find all possible ways to get from one node to all other nodes, where each edge has a metric value. The shortest path is the path for which the sum of all edge metrics is the least. That path is now the preferred path and will be used for packet forwarding. The algorithm itself guarantees that no loops in the network are created in this path selection and when all switches run this algorithm independently, they each now have a view of the shortest paths to all other switches.

Dense versus Sparse
In networks that are relatively sparse in connectivity (i.e. there are not a lot of links connecting switches together), the amount of possible paths is relatively small and determining which path is the likely one to be picked is fairly straightforward, and you can create a metric map for all the edges that will give you the results you expect.

In networks with much more dense connectivity, the amount of paths starts to increase almost exponentially to the point where no pen, paper or human brain can determine all possibilities, let alone the right ones. Even in relatively small mesh networks (which is what a Plexxi network is), there are easily 100s of potential paths between any two switches, 1000s even. Some are direct, some may be indirect. Trying to assign metrics to links to drive a specific path selection becomes pretty much impossible and you need higher level descriptions of desired paths.

In traditional long haul transport networks where the amount of links is fairly limited due to cost, you will find fairly sparse connectivity between network elements, and with it a desire to be very explicit in creating paths between these endpoints. In metro networks, connectivity is more available and the connectivity becomes denser, and the desire for hand selecting paths becomes less. Move this into a local environment like a data center, and connectivity density will drive path selection to pure math based selection.

Link diversity and characteristics
Not all links are created equal. As I mentioned above, most algorithms allow some metric to be associated with an edge or link in the graph, and the best paths are the ones with the lowest summed metric. But what if you want to articulate more than just some metric? What if I want a path that has the most bandwidth, regardless of the amount of nodes and links? What if I want to set aside certain paths for certain network flows and make sure no other traffic follows those same paths? How do you combine these metrics? The definition of “best” all of sudden becomes less obvious. This is where more complex algorithms come in, those that take other constraints into account and not just calculate the shortest path from any node to any other node.

Plexxi Network Topologies
In a Plexxi network, Control collects the graph that makes up the network fabric. Control discovers all the switches, and the switches discover all links between them, there is a simple peering mechanism that runs across links that connect Plexxi switches. The combination of switches and links is turned into a graph very similar to any other link state protocol out there. But then we take a different approach.

In traditional shortest path selections, there is no notion of the amount of traffic that is expected to flow across the paths selected. Which means that paths that flow through multiple nodes will impact each other because each node may contribute to the load on that link. The path selection has no notion of traffic or expected traffic and simply creates that path, or several parallel paths of the same cost in the case of ECMP.

The Plexxi path selection is based on traffic modeling and calculates paths based on how much traffic is expected to travel across each edge between nodes, on each link between switches. By incrementally satisfying the need from each node to each other node, the algorithms will find that one edge that is shared between multiple end to end paths may be overloaded, and will find different edges for some of these paths. End to end paths between switches in a Plexxi network may be direct, through an intermediate hop, or multiple intermediate hops. When calculating what traffic needs to go where across all these paths, paths may be claimed by a specific flow or set of flows, and removed from consideration for any other traffic. Or when you want to avoid certain links except for failure scenarios, you can provide a preference that may not entirely avoid the use of a link, but only use a specific portion of it. Except in failure conditions.

Our approach to calculating the best paths from any switch to any other switch is still graph theory. But is has evolved far beyond the basics of shortest path first methodologies. Of course we tend to use short paths over long paths, but the calculations do not end there. If the modeled traffic needs more than what that short paths provide, the answer is not “too bad, add more links along that path”, we simply start to add indirect or non shortest path options to the total set of end to end paths used to get from A to B.

It is not always easy to explain. Having a centralized view of the all switches and their links between them, allows for non traditional graph algorithms to create paths across the network, with constraints that extend well beyond a basic metric. We will happily create 16 or more paths between any two switches, direct and indirect. And use all of them, independently load balanced according to weights calculated by those same algorithms. This is not regular shortest path graph theory anymore.

[Today's fun fact: The human brain is about 80% water. Feels more like jelly at the moment though.]

The post Graph Theory and Calculating Network Topologies appeared first on Plexxi.

Read the original blog entry...

More Stories By Marten Terpstra

Marten Terpstra is a Product Management Director at Plexxi Inc. Marten has extensive knowledge of the architecture, design, deployment and management of enterprise and carrier networks.

@CloudExpo Stories
SYS-CON Events announced today that Synametrics Technologies will exhibit at SYS-CON's 22nd International Cloud Expo®, which will take place on June 5-7, 2018, at the Javits Center in New York, NY. Synametrics Technologies is a privately held company based in Plainsboro, New Jersey that has been providing solutions for the developer community since 1997. Based on the success of its initial product offerings such as WinSQL, Xeams, SynaMan and Syncrify, Synametrics continues to create and hone inn...
As many know, the first generation of Cloud Management Platform (CMP) solutions were designed for managing virtual infrastructure (IaaS) and traditional applications. But that's no longer enough to satisfy evolving and complex business requirements. In his session at 21st Cloud Expo, Scott Davis, Embotics CTO, explored how next-generation CMPs ensure organizations can manage cloud-native and microservice-based application architectures, while also facilitating agile DevOps methodology. He expla...
To get the most out of their data, successful companies are not focusing on queries and data lakes, they are actively integrating analytics into their operations with a data-first application development approach. Real-time adjustments to improve revenues, reduce costs, or mitigate risk rely on applications that minimize latency on a variety of data sources. In his session at @BigDataExpo, Jack Norris, Senior Vice President, Data and Applications at MapR Technologies, reviewed best practices to ...
DevOps promotes continuous improvement through a culture of collaboration. But in real terms, how do you: Integrate activities across diverse teams and services? Make objective decisions with system-wide visibility? Use feedback loops to enable learning and improvement? With technology insights and real-world examples, in his general session at @DevOpsSummit, at 21st Cloud Expo, Andi Mann, Chief Technology Advocate at Splunk, explored how leading organizations use data-driven DevOps to close th...
Continuous Delivery makes it possible to exploit findings of cognitive psychology and neuroscience to increase the productivity and happiness of our teams. In his session at 22nd Cloud Expo | DXWorld Expo, Daniel Jones, CTO of EngineerBetter, will answer: How can we improve willpower and decrease technical debt? Is the present bias real? How can we turn it to our advantage? Can you increase a team’s effective IQ? How do DevOps & Product Teams increase empathy, and what impact does empath...
Most technology leaders, contemporary and from the hardware era, are reshaping their businesses to do software. They hope to capture value from emerging technologies such as IoT, SDN, and AI. Ultimately, irrespective of the vertical, it is about deriving value from independent software applications participating in an ecosystem as one comprehensive solution. In his session at @ThingsExpo, Kausik Sridhar, founder and CTO of Pulzze Systems, discussed how given the magnitude of today's application ...
Modern software design has fundamentally changed how we manage applications, causing many to turn to containers as the new virtual machine for resource management. As container adoption grows beyond stateless applications to stateful workloads, the need for persistent storage is foundational - something customers routinely cite as a top pain point. In his session at @DevOpsSummit at 21st Cloud Expo, Bill Borsari, Head of Systems Engineering at Datera, explored how organizations can reap the bene...
With tough new regulations coming to Europe on data privacy in May 2018, Calligo will explain why in reality the effect is global and transforms how you consider critical data. EU GDPR fundamentally rewrites the rules for cloud, Big Data and IoT. In his session at 21st Cloud Expo, Adam Ryan, Vice President and General Manager EMEA at Calligo, examined the regulations and provided insight on how it affects technology, challenges the established rules and will usher in new levels of diligence arou...
You know you need the cloud, but you're hesitant to simply dump everything at Amazon since you know that not all workloads are suitable for cloud. You know that you want the kind of ease of use and scalability that you get with public cloud, but your applications are architected in a way that makes the public cloud a non-starter. You're looking at private cloud solutions based on hyperconverged infrastructure, but you're concerned with the limits inherent in those technologies. What do you do?
Recently, WebRTC has a lot of eyes from market. The use cases of WebRTC are expanding - video chat, online education, online health care etc. Not only for human-to-human communication, but also IoT use cases such as machine to human use cases can be seen recently. One of the typical use-case is remote camera monitoring. With WebRTC, people can have interoperability and flexibility for deploying monitoring service. However, the benefit of WebRTC for IoT is not only its convenience and interopera...
Sanjeev Sharma Joins June 5-7, 2018 @DevOpsSummit at @Cloud Expo New York Faculty. Sanjeev Sharma is an internationally known DevOps and Cloud Transformation thought leader, technology executive, and author. Sanjeev's industry experience includes tenures as CTO, Technical Sales leader, and Cloud Architect leader. As an IBM Distinguished Engineer, Sanjeev is recognized at the highest levels of IBM's core of technical leaders.
In his general session at 21st Cloud Expo, Greg Dumas, Calligo’s Vice President and G.M. of US operations, discussed the new Global Data Protection Regulation and how Calligo can help business stay compliant in digitally globalized world. Greg Dumas is Calligo's Vice President and G.M. of US operations. Calligo is an established service provider that provides an innovative platform for trusted cloud solutions. Calligo’s customers are typically most concerned about GDPR compliance, application p...
Mobile device usage has increased exponentially during the past several years, as consumers rely on handhelds for everything from news and weather to banking and purchases. What can we expect in the next few years? The way in which we interact with our devices will fundamentally change, as businesses leverage Artificial Intelligence. We already see this taking shape as businesses leverage AI for cost savings and customer responsiveness. This trend will continue, as AI is used for more sophistica...
The 22nd International Cloud Expo | 1st DXWorld Expo has announced that its Call for Papers is open. Cloud Expo | DXWorld Expo, to be held June 5-7, 2018, at the Javits Center in New York, NY, brings together Cloud Computing, Digital Transformation, Big Data, Internet of Things, DevOps, Machine Learning and WebRTC to one location. With cloud computing driving a higher percentage of enterprise IT budgets every year, it becomes increasingly important to plant your flag in this fast-expanding busin...
Smart cities have the potential to change our lives at so many levels for citizens: less pollution, reduced parking obstacles, better health, education and more energy savings. Real-time data streaming and the Internet of Things (IoT) possess the power to turn this vision into a reality. However, most organizations today are building their data infrastructure to focus solely on addressing immediate business needs vs. a platform capable of quickly adapting emerging technologies to address future ...
In his session at 21st Cloud Expo, Raju Shreewastava, founder of Big Data Trunk, provided a fun and simple way to introduce Machine Leaning to anyone and everyone. He solved a machine learning problem and demonstrated an easy way to be able to do machine learning without even coding. Raju Shreewastava is the founder of Big Data Trunk (www.BigDataTrunk.com), a Big Data Training and consulting firm with offices in the United States. He previously led the data warehouse/business intelligence and B...
The past few years have brought a sea change in the way applications are architected, developed, and consumed—increasing both the complexity of testing and the business impact of software failures. How can software testing professionals keep pace with modern application delivery, given the trends that impact both architectures (cloud, microservices, and APIs) and processes (DevOps, agile, and continuous delivery)? This is where continuous testing comes in. D
Cloud Expo | DXWorld Expo have announced the conference tracks for Cloud Expo 2018. Cloud Expo will be held June 5-7, 2018, at the Javits Center in New York City, and November 6-8, 2018, at the Santa Clara Convention Center, Santa Clara, CA. Digital Transformation (DX) is a major focus with the introduction of DX Expo within the program. Successful transformation requires a laser focus on being data-driven and on using all the tools available that enable transformation if they plan to survive ov...
A strange thing is happening along the way to the Internet of Things, namely far too many devices to work with and manage. It has become clear that we'll need much higher efficiency user experiences that can allow us to more easily and scalably work with the thousands of devices that will soon be in each of our lives. Enter the conversational interface revolution, combining bots we can literally talk with, gesture to, and even direct with our thoughts, with embedded artificial intelligence, whic...
"WineSOFT is a software company making proxy server software, which is widely used in the telecommunication industry or the content delivery networks or e-commerce," explained Jonathan Ahn, COO of WineSOFT, in this SYS-CON.tv interview at 21st Cloud Expo, held Oct 31 – Nov 2, 2017, at the Santa Clara Convention Center in Santa Clara, CA.