3 Basic routing theory I – Oblivious routing

Now that we had a look at how well certain families of networks can perform routing, we want to concentrate on the problem of how to find good paths in networks. One way would be to simply calculate the best collection of paths for a given routing problem and then to use it to send the messages. This has two major drawbacks: • In order to calculate the best paths, global information is needed about the routing problem, which may consume a lot of time to obtain (if possible at all). • Even if it were possible to collect information about the routing problem sufficiently fast, it can still take a lot of time to compute a (near-)optimal solution to that problem (large linear programs may have to be solved!). Hence, path selection strategies are needed that allow the nodes to decide locally in a small amount of time along which edge to forward a packet. There are basically two approaches to that: oblivious routing and adaptive routing. In oblivious routing a system of optional paths is chosen in advance for every source-destination pair, and every packet for that pair must travel along one of these optional paths (see Figure 1). Thus, the path a packet takes only depends on its source-destination pair (and maybe a random choice to select one of the options). Formally, this can be expressed as follows: Definition 3.1 An oblivious routing strategy is specified by a path system P and a function w assigning a weight to every path in P. w has the property that for every source-destination pair (s, t), the system w(q) = 1. of flow paths Ps,t for (s, t) fulfills � q∈Ps,t In adaptive routing, however, the path taken by a packet may also depend on other packets or events taking place in the network during its travel