Graph Theory and computer networks [closed]

What are the various graph theory techniques which are used in modelling of computer networks? Secondly, Will routing algorithms like bellmanford etc also be considered to be part of modelling networks? In short , I want to know the algorithm names which are used in modelling computer networks.

-

closed as not a real question by Luke Mathieson, A.Schulz, Gilles♦Nov 19 '12 at 22:16

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

This question is too broad to receive a meaningful answer. Try to be more specific. Feel free to modify your question. –  A.Schulz Nov 17 '12 at 8:41
@A.Schulz Question edited, hope now it is a little bit specific. –  Zara Nov 17 '12 at 9:30

FIRST PART: There are many types of networks, therefore you really cannot have a single answer for this question. I hope that this is a good answer.

For instance, wireless networks as modeled as geometric graphs or unit disk graphs. P2P networks are modelled as an arbitarary graph (Kazaa and Gnutella) and complete graph (Chord, Pastry etc ..). This despite the fact that no every terminal is directly connected to every other. But if they know the IP to each other, then a complete overlay network is formed. Bipartite graphs are used recently to model RFID readers networks.

The server-client architecture is widely used (which is a star topology - tree of height 1). This lead to hierarichal architectures (e.g. DNS for example). Earlier, ring topologies were frequently used (FDDI). Theoretical networking scientists love this topology because it gives them a simplified view of the problems they try to solve (for instance, the spanning tree construction lower bound in terms message complexity is found only on these structures - based on that, they concluded the same lower bound for arbitrary networks [because arbitrary may be a ring !]).

From my experience, in wireless networks concepts such spanning trees, maximal independent sets, dominating sets, steiner trees, and geometric spanners are frequently used. In P2P, there are many types of networks that are used to model it (e.g., rings, chord graphs, de burijn graphs, viceroy). P2P networks uses the idea of greedy routing to search for objects. -- all these are graph theoretical ideas.

SECOND: routing techniques are not part of the modelling process. But you can optimize your network in a way such that specific routing algorithms work fine on it ! (e.g. structured P2P networks, Bluetooth scatternet formation and topology control problems).

The routing algorithms are graph-theory solutions. They are considered under the category of shortest paths in graphs. There are many heuristics for that. Becuase we dont' really need the best performance always. OR, our performance metrics are different.

In conclusion: networking is the practical side of graph theory !

-
Thanks for such an elaborate answer. One thing I would like to ask again is that if routing is not part of modelling process in computer networks then what other things can be considered? –  Zara Nov 17 '12 at 16:10
be more specific please. What do you mean by modelling ? –  AJed Nov 17 '12 at 17:55
I myself is little confused regarding the word "modelling".By modelling , I think what I have understood is that the graph theoretic concepts involved in designing a computer network like star topology, ring, mesh etc.Am I right? But on net I found more stuff on algorithms especially regarding routing, spanning tree etc –  Zara Nov 17 '12 at 18:01
For me, modelling a network is abstracing it. Usuaully, this abstraction is done in terms of graph (vertices and edges). Networks in practice may have different types (i.e. graph types). This is modelling for me. What you do on the network [different tasks such as routing, broadcasting] are not part of the modelling. We use modelling to make these tasks more understandable. did that answer your question ? –  AJed Nov 17 '12 at 18:08
I d tell them what I mentioned before. No need to mention what algorithms are used. You can also mention distributed computing. That's giving each vertex in a graph the ability to make computation. –  AJed Nov 17 '12 at 18:24