In my last post Intelligent Network Part I, we talked about different ways physical networks can expose rather intelligent behaviors, how they relate to human social behaviors and how they evolved to become something that’s part of our lives, something we can’t live without nowadays. This time, we’ll slightly change our focus and dig a little deeper into some technical details about network. How many different types of networks are there?
In the past 5 years, I am lucky enough to be able to work on some workflow processing systems over distributed networks. It was quite a journey, and I’ll try to share some of my experiences with my readers.
Types of Network
In my last post, we talked about an intriguing story about how a spy during WWII utilized an agent network to hide his real identity and also pass on vital tactical information. This time, let’s imagine during the same war, there is a network of communication stations needs to pass on information about an enemy attack on one of the coastal cities. Let’s assume that the communication stations can only talk to one other station at a time because of some technical limitations at the time. So how would you design the network, and how fast the messages can be propagated to every single stations in the network?
Networks can be divide into two major categories based on their scalability.
The first figure is a sample of a centralized network. Imagine we have a central broadcasting communication station that’s capable of talking to any other station in the network, then we can simply have this station to send a message to all the other stations, one message at a time. Assuming we have n stations and each communication takes 1 second. This way we’ll have to spend a total of n seconds for the message to propagate through the entire network. Mathematically we call this O( n ) linear efficiency.
- Only one network node needs to be capable of sending messages, all other nodes can just listen/receive messages.
- Not fault tolerant. Obviously if the central station failed for some reason, the entire network paralyzes.
- The central node needs to be able to reach every other node in order for this design to work.
- Non-central nodes is not aware of presence of any nodes other than the central node.
Figure 2 and 3 are examples of distributed networks. The key difference is lack of a centralized node. Each node is connected with one or more other nodes, and messages can be propagated through the entire network using a much more efficient and sophiscated algorithm. I’ll give you a hint that we can achieve the same by using only O(lg n) time as compared with O ( n ) in the centralized design. Spend some time think about this question, and come back for answers in our next blog post.
- Fault tolerant: single node failure does not paralyze the entire network.
- More efficient aggregation algorithms available.
- Network can scale. Internet itself is a form of a distributed network.
- Network can scale to include very large number of nodes, which in turn causes much more complexity.
- Not every node can directly communicate with any node in the network, message propagation takes time.
In the next post we’ll talk about some global aggregation algorithms for solving interesting problems with these different types of network.