Reliability of Network

The ability of an underlying network system to deliver connectivity functionalities between client devices/software and the reomote cloud.

Connectivity

The basic meaning: is the graph of the network connected? If time is divided into intervals: What is the probability of the event that the graph stays connected in the next interval?

Other notions

We should consider the flow of packets in communication channels.

• Packets from sources gets to destinations
• The network is designed in such a way that capacity of channels should fulfilll the packets flow realized from the intensity of packets produced at nodes, considering at the same time the routing rules.

Capacity of channels

The maximum number of bits that can be inputed into channel per second.

Matrix of intensity

The square matrix, which cell \(n_{ij}\) describes the number of packets that are produced at node \(i\) to destination at node \(j\).

Routing rules

The algorithms that describe how paths between all source nodes and destination nodes are computed.

Flow

For each channel: the real number of packets that traveled through the channel per second. It is a function dependent on intensity of packets produced at nodes and the routing algorithms.

Capacity vs Flow

A channel fulfills basic functionality if its capacity is big enough to realize its flow, i.e. if number of entering packets multiplied by packet size in bits is smaller than capacity.

Packet delay

The time during which a packet traverses the path from the source node to the destination node. The delay relies on packet switching time at routing nodes - the time a packet waits for serving in the router queue. Intuitively the more packets to be served the waiting time is longer.

Capacity - flow - delay

From queue theory: the closer the flow is to the capacity limit, the longer packets are served - the delay is bigger.

Design problem

Better channels (with more capacity) are more expensive. Problem: provide the enough capacity to fulfill the flow in such a way that the delay is acceptable - all at the minimum cost.

Evaluating reliability

Goal: estimate the probability of the event that the network will be functional (satisfy us) in an interval, taking under consideration that some of the channels may become broken. Usually we are given the parameters of each channel including probability it breaks in an interval.

Possible approach

Monte Carlo simulations: the numberofsuccess divided by numberofexperiments.

Experiment

• Simulate the breakdown of each link in an interval, then:
• check if the network is still connected,
• compute all the paths according to routing rules,
• compute flow in channels,
• check if the capacities realize flows,
• compute delays and check if they are acceptable (below assumed threshold),