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.
Tell me more
×
Computer Science Stack Exchange is a question and answer site for
students, researchers and practitioners of computer science. It's 100% free, no registration required.
|
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, see the FAQ.
|
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 ! |
|||||||||||||
|
