Welcome!

SDN Journal Authors: Destiny Bertucci, Elizabeth White, Liz McMillan, Jignesh Solanki, Daniel Gordon

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
"Storpool does only block-level storage so we do one thing extremely well. The growth in data is what drives the move to software-defined technologies in general and software-defined storage," explained Boyan Ivanov, CEO and co-founder at StorPool, in this SYS-CON.tv interview at 16th Cloud Expo, held June 9-11, 2015, at the Javits Center in New York City.
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...
As DevOps methodologies expand their reach across the enterprise, organizations face the daunting challenge of adapting related cloud strategies to ensure optimal alignment, from managing complexity to ensuring proper governance. How can culture, automation, legacy apps and even budget be reexamined to enable this ongoing shift within the modern software factory? In her Day 2 Keynote at @DevOpsSummit at 21st Cloud Expo, Aruna Ravichandran, VP, DevOps Solutions Marketing, CA Technologies, was jo...
As Marc Andreessen says software is eating the world. Everything is rapidly moving toward being software-defined – from our phones and cars through our washing machines to the datacenter. However, there are larger challenges when implementing software defined on a larger scale - when building software defined infrastructure. In his session at 16th Cloud Expo, Boyan Ivanov, CEO of StorPool, provided some practical insights on what, how and why when implementing "software-defined" in the datacent...
Blockchain. A day doesn’t seem to go by without seeing articles and discussions about the technology. According to PwC executive Seamus Cushley, approximately $1.4B has been invested in blockchain just last year. In Gartner’s recent hype cycle for emerging technologies, blockchain is approaching the peak. It is considered by Gartner as one of the ‘Key platform-enabling technologies to track.’ While there is a lot of ‘hype vs reality’ discussions going on, there is no arguing that blockchain is b...
Blockchain is a shared, secure record of exchange that establishes trust, accountability and transparency across business networks. Supported by the Linux Foundation's open source, open-standards based Hyperledger Project, Blockchain has the potential to improve regulatory compliance, reduce cost as well as advance trade. Are you curious about how Blockchain is built for business? In her session at 21st Cloud Expo, René Bostic, Technical VP of the IBM Cloud Unit in North America, discussed the b...
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.
Is advanced scheduling in Kubernetes achievable?Yes, however, how do you properly accommodate every real-life scenario that a Kubernetes user might encounter? How do you leverage advanced scheduling techniques to shape and describe each scenario in easy-to-use rules and configurations? In his session at @DevOpsSummit at 21st Cloud Expo, Oleg Chunikhin, CTO at Kublr, answered these questions and demonstrated techniques for implementing advanced scheduling. For example, using spot instances and co...
The cloud era has reached the stage where it is no longer a question of whether a company should migrate, but when. Enterprises have embraced the outsourcing of where their various applications are stored and who manages them, saving significant investment along the way. Plus, the cloud has become a defining competitive edge. Companies that fail to successfully adapt risk failure. The media, of course, continues to extol the virtues of the cloud, including how easy it is to get there. Migrating...
The use of containers by developers -- and now increasingly IT operators -- has grown from infatuation to deep and abiding love. But as with any long-term affair, the honeymoon soon leads to needing to live well together ... and maybe even getting some relationship help along the way. And so it goes with container orchestration and automation solutions, which are rapidly emerging as the means to maintain the bliss between rapid container adoption and broad container use among multiple cloud host...
Imagine if you will, a retail floor so densely packed with sensors that they can pick up the movements of insects scurrying across a store aisle. Or a component of a piece of factory equipment so well-instrumented that its digital twin provides resolution down to the micrometer.
The need for greater agility and scalability necessitated the digital transformation in the form of following equation: monolithic to microservices to serverless architecture (FaaS). To keep up with the cut-throat competition, the organisations need to update their technology stack to make software development their differentiating factor. Thus microservices architecture emerged as a potential method to provide development teams with greater flexibility and other advantages, such as the abili...
In his keynote at 18th Cloud Expo, Andrew Keys, Co-Founder of ConsenSys Enterprise, provided an overview of the evolution of the Internet and the Database and the future of their combination – the Blockchain. Andrew Keys is Co-Founder of ConsenSys Enterprise. He comes to ConsenSys Enterprise with capital markets, technology and entrepreneurial experience. Previously, he worked for UBS investment bank in equities analysis. Later, he was responsible for the creation and distribution of life settle...
Product connectivity goes hand and hand these days with increased use of personal data. New IoT devices are becoming more personalized than ever before. In his session at 22nd Cloud Expo | DXWorld Expo, Nicolas Fierro, CEO of MIMIR Blockchain Solutions, will discuss how in order to protect your data and privacy, IoT applications need to embrace Blockchain technology for a new level of product security never before seen - or needed.
Leading companies, from the Global Fortune 500 to the smallest companies, are adopting hybrid cloud as the path to business advantage. Hybrid cloud depends on cloud services and on-premises infrastructure working in unison. Successful implementations require new levels of data mobility, enabled by an automated and seamless flow across on-premises and cloud resources. In his general session at 21st Cloud Expo, Greg Tevis, an IBM Storage Software Technical Strategist and Customer Solution Architec...
Nordstrom is transforming the way that they do business and the cloud is the key to enabling speed and hyper personalized customer experiences. In his session at 21st Cloud Expo, Ken Schow, VP of Engineering at Nordstrom, discussed some of the key learnings and common pitfalls of large enterprises moving to the cloud. This includes strategies around choosing a cloud provider(s), architecture, and lessons learned. In addition, he covered some of the best practices for structured team migration an...
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...
Coca-Cola’s Google powered digital signage system lays the groundwork for a more valuable connection between Coke and its customers. Digital signs pair software with high-resolution displays so that a message can be changed instantly based on what the operator wants to communicate or sell. In their Day 3 Keynote at 21st Cloud Expo, Greg Chambers, Global Group Director, Digital Innovation, Coca-Cola, and Vidya Nagarajan, a Senior Product Manager at Google, discussed how from store operations and ...
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...
"IBM is really all in on blockchain. We take a look at sort of the history of blockchain ledger technologies. It started out with bitcoin, Ethereum, and IBM evaluated these particular blockchain technologies and found they were anonymous and permissionless and that many companies were looking for permissioned blockchain," stated René Bostic, Technical VP of the IBM Cloud Unit in North America, in this SYS-CON.tv interview at 21st Cloud Expo, held Oct 31 – Nov 2, 2017, at the Santa Clara Conventi...