How can the problem of congestion be controlled?

Networks often get trapped in the situation of what we call network congestion. For avoiding such collapses, congestion avoidance and congestion control techniques are often used by the networks nowadays. 

In this article, we discuss about how we can control the problem of network congestion using these techniques. Few very common techniques are:

1. Exponential back off (used in CSMA/ CA protocols and Ethernet.)
2. Window reduction (used in TCP)
3. Fair queuing (used in devices such as routers)
4. The implementation of the priority schemes is another way of avoiding the negative effects of this very common problem. Priority schemes let the network transmit the packets having higher priority over the others. This way only the effects of the network congestion can be alleviated for some important transmissions. Priority schemes alone cannot solve this problem.
5. Another method is the explicit allocation of the resources of the network to certain flows. This is commonly used in CFTXOPs (contention – free transmission opportunities) providing very high speed for LAN (local area networks) over the coaxial cables and phone lines that already exist.

- The main cause of the problem of network congestion is the limited capacity of the network. 

- This is to say that the network has limited. 

- The resources also include the link throughput and the router processing time. 

- Congestion control is concerned with curbing the entry of the traffic in to the telecommunications network so that the problem of congestive collapse can be avoided. 

- The over-subscription of the link capabilities is avoided and steps are taken to reduce the resources. 

- One such step is reducing the packet transmission rate. 

- Even though if it sounds similar to flow control, it is not the same thing. 

- Frank Kelly is known as the pioneer of the theory of congestion control. 

- For describing the way in which the network wide rate allocation can be optimized by the individuals by controlling their rates, he used two theories namely the convex optimization theory and the micro economics theory. 

Some optimal rate allocation methods are:

Ø  Max – min fair allocation

Ø  Kelly’s proportional fair allocation

Ways to Classify Congestion Control Algorithm

There are 4 major ways for classifying the congestion control algorithms:

1. Amount as well as type of feedback: This classification involves judging the algorithm on the basis of multi-bit or single bit explicit signals, delay, loss and so on.
2. The performance aspect taken for improvement: Includes variable rate links, short flow advantage, fairness, links that can cause loss etc.
3. Incremental deployability: Modification is the need of sender only, modification is required by receiver and the sender, modification is needed only by the router, and modification is required by all three i.e., the sender, receiver and the router.
4. Fairness criterion being used: It includes minimum potential delay, max – min, proportional and so on.

Two major components are required for preventing network congestive collapse:

1. End to end flow control mechanism: This mechanism has been designed such that it can respond well to the congestive collapse and thus behave accordingly.
2. Mechanism in routers: This mechanism is used for dropping or reordering packets under the condition of overload.

- For repeating the dropped information correct behavior of the end point is required. 

- This indeed slows down the information transmission rate. 

- If all the end points exhibit this kind of behavior, the congestion would be lifted from the network. 

- Also, all the end points would be able to share the available bandwidth fairly. - Slow start is another strategy using which it can be ensured that the router is not overwhelmed by the new connections before congestion can be detected. 

Explain multicast routing?

- Multicast routing is also known as the IP multicast. 

- For sending the IP (internet protocol) data-grams to a group of receivers who are interested in receiving the data-grams, multicast routing is used.

- The data-grams are sent to all the receivers in just one transmission. 

- Multicast routing has got a special use in the applications that require media streaming on private networks as well as internet. 

- Multicast routing is IP specific version. 

- A more general version is the multicast networking.

- Here, the multicast address blocks are especially reserved in IPv6 and IPv4. 

- Broadcast addressing has been replaced by multicast addressing in IPv6. 

- Broadcast addressing was used in IPv4. 

- RFC 1112 describes the multicast routing and in 1986 it was standardized. 

This technique is used for the following types of real – time communication over the IP infrastructure of the network:

Ø  Many – to – many

Ø  One – to – many

- It scales up to receiving population that is large enough and it does not require either knowledge regarding the receivers and the identity of the receivers. 

- Network infrastructure is used efficiently by the multicast efficiently and requires source sending packet to a large number of receivers only once. 

- The responsibility of the replication of the packet is of the nodes which are nothing but the routers and the network switches.

- The packet has to be replicated till it reaches the multiple receivers. 

- Also, it is important that the message is sent only once over the link.   

- UDP or the user data gram protocol is the mostly used protocol of low level. 

- Even though if this protocol does not guarantees reliability i.e., the packets might get delivered or get lost. 

- There are other multicast protocols available that are reliable such as the PGM or the pragmatic general multicast. 

It has been developed for adding the following two things a top the IP multicast:

Ø  Retransmission and

Ø  Loss detection

The following 3 things are key elements of an IP multicast:

1. Receiver driven tree creation
2. Multicast distribution tree
3. IP multicast group address

- The receivers and the sources use the last for sending as well as receiving the multicast messages. 

- The group address serves as the destination address of the data packets for the sources whereas it is used for informing the network whether or not the receivers want those packets.

- Receivers need a protocol for joining a group. 

- One most commonly used protocol for this purpose is the IGMP i.e., the internet group management protocol. 

- The multicast distribution trees are set up using this protocol. 

- Once a group has been joined by the receiver, the PIM (protocol independent multicast) protocol is used for constructing a multicast distribution tree for this group. 

- The multicast distribution trees set up with the help of this protocol are used for sending the multicast packets to the members of the multicast group. 

PIM can be implemented in any of the following variations:

1. SM or sparse mode
2. DM or dense mode
3. SSM or source specified mode
4. SDM or sparse – dense mode or bidirectional mode (bidir)

- Since 2006, the sparse mode is the most commonly used mode. 

- The last two variations are more scalable and simpler variations of PIM and are also popular. 

- An active source is not required for carrying out an IP multicast operation and knowing about the group’s receivers. 

- The receiver drives the construction of the IP multicast tree. 

- The network nodes which lie closer to receiver are responsible for initiating this construction.

- This multicast then scales to a receiver population that is large enough. 

- It is important for a multicast router to know which all multicast trees can be reached in the network. 

- Rather, it only requires knowledge of its downstream receivers. 

- This is how the multicast – addressed services can be scaled up. 

Lining up the support structure at the start of a cycle with firm commitments ..

During the course of a software project, you need the support of a number of people. For those who are not so well versed with the various challenges involved in project management, handling the support and resources from outside the core team are one of the biggest challenges during the early stages of the project, during the middle of the project, and during the later stages of the project; which only means that handling the various supporting teams is one of the biggest tasks during a project cycle.
So consider the starting time of a project. The features that are required for the project to succeed have been generated (including the trade off about the ones that are critical for the project vs. the ones that can be cut when there are schedule risks), and there is a need to ensure that there is a formal kick-off for the project. What do you do in a formal kick-off ? Well, one of the key items is to ensure that the team knows what the project is about, what are the key features that will be there in the project, and other such details. Typically the product manager will give a presentation to the team about the aim of the product, the market, the revenue earned by previous versions of the product and the target for the current version, and a high level description of the features that are sought to be included in the project. For many of these features, the further detail that the product manager can give is about how these features were derives, whether these be from competitor analysis or specific requests by customers, or generated based on ideas by the team.
However, as part of the initial kick-off, there are many other discussions that need to take place. For making the software development project successful, there is a lot of support that is needed from other teams. There are teams that prepare the build and the installer, there are teams that work on the documentation and help files, there are teams that deliver components that are required for specific functionality in the product, there are teams that work to translate the product in other languages. Most modern organizations have these kind of dependencies; it is no longer possible to have a situation where a single team does everything that is required for the team (for example, if you have a product that uses video formats, you would rather be using a common component that uses different video codecs to work with these formats rather than write code for working directly with these video formats (it may not even be possible to write code for all these video formats due to technical and commercial limitations)).
It is easier to ensure that you have the support of your core team and more difficult to ensure that all these supporting teams are providing the required support. For this purpose, before the kick-off, you would need to work with all these teams, providing them details about your requirements and the schedule in order to get a commitment from them (in some cases, where there is a clash due to priorities for support, you may need to escalate before you can get the desired commitment). In all cases, unless you can get the required level of support from these teams in terms of commitment, your project is already at a certain amount of risk that you will need to manage in one way or the other.

What is a spanning tree?

Spanning tree is an important field in both mathematics and computer science. Mathematically, we define a spanning tree T of an un-directed and connected graph G as a tree consisting of all the vertices and all or some edges of the graph G.

- Spanning tree is defined as a selection of some edges from G forming a tree such that every vertex is spanned by it. 

- This means that every vertex of graph G is present in the spanning tree but there are no loops or cycles. 

- Also, every bridge of the given graph must be present in its spanning tree. 

- We can even say that a maximal set of the graph G’s edges containing no cycle or a minimal set of the graph G’s vertices forms a spanning tree. 

- In the field of graph theory, it is common finding the MST or the minimum spanning tree for some weighted graph. 

- There are a number of other optimization problems that require using the minimum spanning trees and other types of spanning trees. 

The other types of spanning trees include the following:

Ø  Maximum spanning tree

Ø  An MST spanning at least k number of vertices.

Ø  An MST having at the most k number of edges per vertex i.e., the degree constrained spanning tree.

Ø  Spanning tree having the largest no. of leaves (this type of spanning tree bears a close relation with the “smallest connected dominating set”).

Ø  Spanning tree with the fewest number of leaves (this spanning tree bears a close relation with the “Hamiltonian path problem”).

Ø  Minimum diameter spanning tree.

Ø  Minimum dilation spanning tree.

- One characteristic property of the spanning trees is that they do not have any cycles. 

- This also means that if you add just an edge to the tree, a cycle will be created. 

- We call this cycle as the fundamental cycle. 

- For each edge in the spanning there exists a distinct fundamental cycle and therefore there arises a one – to – one correspondence among the edges that are not present and the fundamental cycles. 

- For a graph G that is connected and has V vertices, there are V-1 edges in its spanning tree. 

- Therefore, for a general graph composed of E edges, its spanning tree will have E-V+1 number of fundamental cycles.

- For the cycle space of a given spanning tree these fundamental cycles are used. 

- The notion of the fundamental cut set as well as of the fundamental cycle forms a dual.  

- If we delete even one edge from the spanning tree, two disjoint sets will be formed of the vertices. 

- The set of the edges that if taken out from the graph G partitioning the vertices in to same disjoint sets is defined as the fundamental cut set. 

- For a given graph G there are V-1 fundamental cut sets i.e., one corresponding to each spanning tree edge. 

- The fact that the edges of the cycles that do not appear in the spanning tree but only in the cut sets of the edges can be used to establish the relationship between the cycles and the cut sets.

What is Spanning Forest?

- The sub-graph generalizing the spanning tree concept is called the spanning forest. 

- A spanning forest can be defined as a sub-graph consisting in each of the connected component a spanning tree of the graph G or we can call it a maximal cycle free sub graph.

- For counting the number of spanning trees for a complete graph the formula used is known as the cayley’s formula.

Soliciting features from your pre-release / beta testers to get them more involved ..

An active set of pre-release participants can be very useful for a product team. Typically why does a team use a pre-release program ? Following are some of the reasons:
- Pre-release participants provide external validation of the features of the application, verifying whether the features that have been built into the product are deemed useful for potential customers. When a team builds a feature, they do so on the basis of market research or other inputs, and then through a process of design and working with the user interface team, they design a solution that is supposed to meet the needs of customers. You can show the workflow to research user bases early, but the validation is only when people get their hands on the product and test it out. And this is extremely valuable, since this sort of validation comes in early enough that there can be changes made in the product to incorporate such feedback.
- Many of these pre-release participants would have been there for multiple versions of the product, and as a result, they have a good knowledge of the product with the advantage that they also have knowledge of actual customer workflows, and hence can quickly suggest some great ways of improving the features. It is upto the product team to take such improvements or not, but I have seen cases where this kind of interaction with the pre-release participant helped the product team learn about some workflows that they were not aware of before. This kind of knowledge is invaluable and the product team should ensure that such participants remain committed to contributing to the pre-release program.
- If you consider the case of video products or imaging products or products that are used for writing to CD/DVD, there are a huge range of devices out there. It is practically impossible for a product team to obtain as well as test these range of devices but when you have a large number of pre-release participants, you can be sure that the total number of devices that you are able to test with is more than what you could obtain on your own, and this gives increased confidence on the part of the product team in the product. As another example, we had a case whereby the product was importing video clips, and there are a large number of video formats that can be used. In one specific format, the embedding of audio with the video clip was crashing the application, and this was not happening with other formats. We would never have found this issue, it was reported by a pre-release participant.

With all these, what else can you do with a pre-release participant. I had earlier mentioned that you need to engage with these valuable testers, and engage with them early. I have seen teams using these participants earlier in the program, even working with them during the feature requirement and feature workflow design process, and even making modifications or tweaks based on the inputs that were received. As a result, there were valuable improvements in the features as well as ensuring that the pre-release participants became very involved with the product. A spin off was that many of them became more active in the user forums and helped some of the more simple customer issues.

Creating mailing list, and place for keeping documents for specific projects

This sounds so simple, but these are measures that can make a lot of difference to the successful execution of a project. You start out with a project which is different from the regular stuff that you are doing, with some people working for this project either on a full time basis, or on a part time basis. For example, while working on your regular project, there is a need for a patch to be released for a previous version of the product which was there in the market, and for which some security issue was found and which needs to be fixed. The teams and organizations that I have worked with typically do not have specialized teams for such tasks, with these instead being done by the core team as well; however, additional resources could be provided as required. In fact, there might be the need for some additional resources for the testing effort, since this would require a high amount of testing in a short period of time.
Finally you are getting the team together which we will be working to execute this project, and the team is brought together for a kick-off meeting where the basic objective of the project, the responsibilities, etc are defined for all the team members and their leads.
But, given the short nature of such projects, there are some specific challenges that come into focus, especially when it comes to items such as communication, and reducing the stress that people come under. For such short projects, there is a high amount of work that is expected to be done within the required timeline, and the team managers need to do all they to ensure that the scope for minimization of activities that could cause stress is there.
The other major problem is communication. Quite often, some communication happens between two or more team members that is important for the project, but there are people who miss this kind of communication. In the normal run of things, people affected will eventually learn about this communication, and things will not go out of control. However, when you consider the short duration of such projects, some communication that gets missed by a couple of team members when it was relevant to them can cause problems in the execution of the project. Setting up project specific emailing lists and encouraging the team members to use such email lists works well in ensuring that everybody gets communication related to the project.
At the same time, there is the need to setup internal sites and document repositories that capture information about the project, including a specific set of requirements and design, as well documents that capture the evolution of these (including comments and queries and answers that came up during the actual discussion to finalize these documents). Having such facilities ensures that people can refer to them easily enough, and new members to the team can pick these up fairly quickly.

When is a situation called as congestion?

- Network congestion is quite a common problem in the queuing theory and data networking. 

- Sometimes, the data carried by a node or a link is so much that its QoS (quality of service) starts deteriorating. 

- This situation or problem is known as the network congestion or simply congestion. 

This problem has the following two typical effects:

Ø  Queuing delay

Ø  Packet loss and

Ø  Blocking of the new connections

- The last two effects lead to two other problems. 

- As the offered load increases by the increments, either the throughput of the network is actually reduced or the throughput increases by very small amounts. 

- Aggressive re-transmissions are used by the network protocols for compensating for the packet loss. 

- The network protocols thus tend to maintain a state of network congestion for the system even if the actual initial load is too less that it cannot cause the problem of network congestion. 

- Thus, two stable states are exhibited by the networks that use these protocols under similar load levels. 

- The stable state in which the throughput is low is called the congestive collapse. 

- Congestive collapse is also called congestion collapse.

- In this condition, the switched computer network that can be reached by a packet when because of congestion there is no or little communication happening.

- In such a situation even if a little communication happens it is of no use. 

- There are certain points in the network called the choke points where the congestion usually occurs.

- At these points, the outgoing bandwidth is lesser than the incoming traffic. 

- Choke points are usually the points which connect the wide area network and a local area network. 

- When a network falls in such a condition, it is said to be in a stable state. 

- In this state, the demand for the traffic is high but the useful throughput is quite less.

- Also, the levels of packet delay are quite high. 

- The quality of service gets extremely bad and the routers cause the packet loss since their output queues are full and they discard the packets. 

- The problem of the network congestion was identified in the year of 1984. 

- The problem first came in to the scenario when the backbone of the NSF net phase dropped 3 times of its actual capacity. 

- This problem continued to occur until the Van Jacobson’s congestion control method was implemented at the end nodes.

Let us now see what is the cause of this problem? 

- When the number of packets being set to a router exceeds its packet handling capacity, many packets are discarded by the routers that are intermediate. 

- These routers expect the re-transmission of the discarded information. 

- Earlier, the re-transmission behavior of the TCP implementations was very bad. 

- Whenever a packet was lost, the extra packets were sent in by the end points, thus repeating the lost information. 

- But this doubled the data rate. 

- This is just the opposite of what routine should be carried out during the congestion problem. 

- The entire network is thus pushed in a state of the congestive collapse resulting in a huge loss of packets and reducing the throughput of the network. 

- Congestion control as well as congestion avoidance techniques are used by the networks of modern era for avoiding the congestive collapse problem. 

- Various congestion control algorithms are available that can be implemented for avoiding the problem of network congestion. 

- There are various criteria based up on which these congestion control algorithms are classified such as amount of feedback, deploy-ability and so on.