Advanced Problems

Site under construction ...

Bilevel Programming


Networks consist of interacting components. Some of them are related to each other as complements (e.g., two links in a line), other elements are substitutes (e.g., two parallel links). In almost all cases the functionality of network requires technical standards so that the network components can act in concert: the elements must be compatible.

By contrast, all technical standards have the inherent problem that they tend to prevent technical progress due to barring from competition. As an example, standards are frequently used by those who set the standars to exclude competitors from entering markets.

Famous examples for international standards: paletts, containers, portable document files (PDFs), etc.
National standards with international incompatibilities: power sockets, (rail) gauges, etc.

Grade of Service (GoS)

Grade of service (GoS) addresses accessibility and availability of network services. Accessibility refers to the possibility of conditions that make it impossible to set up end-to-end connections normally supported through a telecommunications service. While accessibility is a measure of perceived QoS, availability measures intrinsic QoS which is defined from the viewpoint of the service provider rather than the service user. Availability is a ratio of uptime to total time.
See also Quality of Service (QoS)

Location Theory

Overall System Delay

Performance of Networks

Network performance signifies not only Quality of Service (QoS) such as overall system delays but also throughput, both of which depend among others on the speed on the communication lines, number of hops, and occupation rates.

Quality of Service (QoS)

Competition in the provision of communication services has forced the providers to measure their quality of service in an operationally meaningful manner and to guarantee predefined levels of service to their customers. The following list of QoS criteria applies to (tele-)communications systems (see Hardy (2001)), but it has corresponding meanings for other networks such as road systems, where trip times, risk of accidents, and reliability are of major importance.

See also Grade of Service (GoS)


Queuing aims at a different form of sharing network resources. It may be seen as one instrument that coordinates individual, non-cooperating network processes. The basic problem is that (stochastic) arrivals of flows claim scarce network resources that can serve only a limited number of jobs at a time. This fact results in delays caused by queues, the length of which vary with the arrivals and departures.

Literature on queuing: Kleinrock (1975)


Network reliability aims at the modeling of failure mechanisms in order to come up with failure rates that can be expected to increase in time and traffic intensity, see also Ball et al. (1995).
From an economic point of view it is worth to install redundant facilities to avoid traffic breakdowns due to a malfunction of some network elements. The reliability of a graph indicates the probability that the "surviving" network without its failing elements remains connected.

Ferrari (1988, 1991) defines the reliability of a motorway transport system as the probability that, starting from the instant when reliability is measured within a certain period of time, no drops in speed to an extent deemed hazardous will occur. Hence, reliability can be increased if the conditions of instability are known and if there are control instruments to intervene before traffic break downs take place.


Survivability of networks aims at the functionality of the network if one or more network components break down.


Throughput of a Network

The network throughput is measured in flow units (packets, vehicles, etc.) per unit of time (i.e. seconds, hours, days etc.) and denotes the total incoming message rate for the network. This definition must be refined if we allow for packet losses. In this case it is more useful to define the network throughput by successfully delivered packets.

Traffic (packet switched vs. circuit switched)

Circuit-switched characterizes a type of network such as the regular voice telephone network in which the communication circuit (path) for the call is set up and dedicated to the participants in that call. For the duration of the connection, all resources on that circuit are unavailable for other users and new sessions must be rejected. The same concept is valid for networks where each communication line allocates a given portion of its total transmission capacity for the session. Again these resources are blocked for other users.

The opposite of circuit-switched is packet-switched describing types of networks in which relatively small units of data, say packets, are routed through a network based upon the destination address contained within each packet (store-and-forward network). Breaking communication down into packets allows the same data path to be shared among many users in the network. This type of communication between sender and receiver is known as connectionless (rather than dedicated). Most traffic over the Internet uses packet switching and the Internet is basically a connectionless network.


Vulnerability of a network refers to the design of survivable networks that are still functional after the failure of certain network components so that the surviving traffic can be rerouted, see Grötschel et al. (1995).
When failing network components cannot be precluded at reasonable costs, further strategies are needed to protect survivability and reliability of networks. One approach is to provide excess capacities that can be used in failure states in order to reroute the surviving traffic.