Dijkstra's Algorithm
Given a node v and a graph G, this algorithm finds the shortest path from v to every node in G. It does this at the same cost as finding the shortest path from v to any one node.

Queuing Theory
The theoretical study of waiting lines, expressed in mathematical terms--including components such as number of waiting lines, number of servers, average wait time, number of queues or lines, and probabilities of queue times' either increasing or decreasing. Note: Queuing theory is directly applicable to network telecommunications, server queuing, mainframe computer queuing of telecommunications terminals, and advanced telecommunications systems.

Markov Process
A random process whose future probabilities are determined by its most recent values.

Process Oriented Simulation
A form of discrete event simulation which lets the model implementer focus on the activities being processed by a system, as opposed to the systems events which are the focus of event oriented simulation. (Source: Using CSim to Model Complex Systems by Herb Schewtman.)

Computational complexity theory
Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem). Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. Complexity theory differs from computability theory, which deals with whether a problem can be solved at all, regardless of the resources required.

Random Graph
In a random graph, properties of the graph such as the number of vertices or the connectivity are determined in some random way. The study of random graphs focuses on the characteristics held by most graphs in a particular family, rather than looking at the few extreme cases. Just as a random sample can display a certain distribution in statistics, a randomly generated graph might adhere to certain rules. In randomly generated graphs that model the Internet, the distribution of the degrees of the nodes usually follows a power-law distribution, meaning that there are many nodes with low degree and a few nodes with very high degree. (Note: In this context, the degree of a node is the number of edges having that node as one endpoint.)

Relaxation Algorithm
Used for shortest path problems in graphs. The relaxation process updates the costs of all the vertices, v, connected to a vertex, u, if we could improve the best estimate of the shortest path to v by including (u,v) in the path to v. This method is used, for example, in Dijkstra's Algorithm.

Priority Queue
A priority queue is a data structure that has a priority assigned to its elements, such that the element with highest priority is always removed first. This type of data structure is especially useful in implementing greedy algorithms.

Binary Heap
A binary tree where all levels except the last are filled, and each node has a key that is equal to or more extreme than the key of its parent.

Fibonacci Heap
A Fibonacci Heap is similar to a binary heap, with extra information added that allows certain operations to be performed on it with very low time cost. It is a collection of min-heap-ordered trees, usually with a circular, doubly-linked list connecting the roots.

Self-Similarity
The repetition of a unit pattern on different size scales. Some examples of self-similarity are fractals or L-systems. Studies have shown that traffic on the Internet exhibits self-similar behavior when the load is high. The term "bursty" is sometimes used to describe traffic with this quality.

Distance Vector Routing
With distance-vector routing, each router advertises its routing table to its neighbors. This method does not require extensive knowledge about the state of the network, but it leaves many opportunities for error.

Link State Routing
With link state routing, each node keeps a full or partial map of the state of the network. It is more reliable than distance-vector routing, but it is very resource-intensive.

Link State Advertisement (LSA)
A notification that is flooded through the network when a link changes state.

Link State Update Policy
Determines when a link state advertisement should be initiated. Update policies can be periodic or trigger-based. Under a periodic update policy, each node advertises information about its resources at certain time intervals. Trigger-based policies specify that nodes should only advertise information when a significant change occurs. There are several different ways to determine when a trigger-based update should occur.
1. Threshold based updates: an update occurs when the difference between the current bandwidth and the last advertised bandwidth exceeds some threshold value.
2. Equal class based updates: the total bandwidth on a link is partitioned into several equal sized "classes," or ranges. An update occurs when the available bandwidth changes such that it belongs to a different class than the one advertised.
3. Exponential class based updates: similar to equal class based updates, but with unequal class sizes. The size or range of a class is smaller at low bandwidths and larger at high bandwidths. This implementation follows from the logic that if the amount of available bandwidth is large enough, the exact amount doesn't matter.

Autonomous System (AS)
A collection of networks under a common administration that share a common routing strategy.

Randomized Routing
A method of selecting a routing path that uses weighted probability. This method has been shown to help balance network load better than static routing.

"Safety-Based" Routing
Routing algorithms that consider QoS require a great deal of information about the state of the network in order to perform successfully. Triggering updates often is costly, however. One solution is "safety-based routing," which takes the level of uncertainty of link-state information into account. By considering the probability that an advertised bandwidth is correct, safety-based routing algorithms can achieve better performance with infrequent updates.

Bandwidth Acceptance Ratio
A method of measuring the performance of a routing algorithm, defined by the sum of bandwidth requirements of the accepted requests over the sum of bandwidth requirements of all connection requests.