A network topology refers to the connectivity of a set of nodes.

A node represents a processing unit
A link between nodes represents a communication channel

The network topology can be represented as a Graph in which nodes are the vertices and the communication channels its edges.

The goodness of a network topology depends on structural (physical) parameters and the communication logic (routing and protocols) that controls the reachability and dynamic behavior (communication flow) of the nodes.

• Structural parameters include spectrum of the nodes degrees, diameter, path analysis, number of connected components, and number of circuits.
  
  
• Protocols are event-driven rules that determine the reactive behavior of each node and consequently the dynamics of the topology; routing is the existence of a path in the structure of the topology that respects the protocols of communication, for example a firewall might prevent a route that exists at the structural level.

Over time nodes or links might fail. Such failures can disrupt parts of the network, resulting in disjoint connected components making reachability of nodes from separate sets impossible. These faults can be of various types:

• Physical (Hardware) level faults:
  • a connection is lost due to damage to a wire or a wireless emitter
  • a node is abruptly removed from the network without undertaking any removal protocol

• Software level faults:
  • An intermediary node experiences overloading and drops transient messages
  • A node is overtaken by a malicious program that inserts errors into the observed state of the network

One node fail stops include :

• A centralized star topology when central node fails
• A ring, line, or tree topology when any forwarding node fails

N node fail stops include:

• A bus topology when the bus fails or the link of a subset of nodes to the bus fails
• A fully connected or mesh topolgy

spectrum of the nodes degrees, diameter, path analysis, number of connected components, and number of circuits.

[Min,Avg,Max] Degree Diameter [Min,Avg,Max] Path Length Circuits Star [1, 2, N] 2 [1,1.5,2] 0 Ring [1,1.5,2] N-1 [1,N/2,N-1] 1 Tree [0,2,2] log(N) [1,log(N)/2,log(N)] 0 Full [N-1,N-1,N-1] 1 [1,1,1] C(N,3)

Question: How can a dynamic network be rewired to maintain structural properties within given bounds ?