Least Congested Routing

Least congested routing (LCR) [6, 80] predetermines a sequence of routes for each source-destination pair similar to FAR. Depending on the arrival time of connection requests, the least-congested routes are selected from among the predetermined routes. The congestion on a link is measured by the number of slots available on the link. If a link has fewer available slots, it is considered to be more congested. The disadvantage of LCR is its higher computation complexity; its blocking probability is almost the same as that of FAR.

Adaptive Routing

In adaptive routing (AR) [80,81], routes between source-destination pairs are chosen dynamically, depending on the network status, such as link-state information. The network status is determined by the set of all connections that are currently active. The most acceptable form of AR is adaptive shortest path routing, which is well suited for use in optical networks. Under this approach, each unused spectrum in the network has a cost of 1 unit, whereas the cost of each used spectrum in the network is taken to be a. When a connection arrives, the shortest path between a source-destination pair is determined. If there are multiple paths with the same distance, one of them is chosen at random. In AR, a connection is considered blocked mainly when there is no route with a required slot between the source-destination pair. Since AR considers all possible routes between source-destination pair, it provides lower blocking probability, but its setup time is comparatively higher than other routing policies. AR requires extensive support from control and management protocols to continuously update the routing tables at the nodes. AR suits centralized implementation rather more than the distributed alternative.

Fixed (solid line), alternate (dotted line) and adaptive (dashed line) routes are shown from source city CA to destination city L

Figure 4.2: Fixed (solid line), alternate (dotted line) and adaptive (dashed line) routes are shown from source city CA to destination city L.

The functionality of the above mentioned routing policies is explained with the help of the sample example network, see Fig. 4.2. It consists of 14 nodes (representing cities) and 21 bi-directional optical links. The fixed shortest route, alternate route, and adaptive route from source city CA to destination city L are shown by the solid, dotted, and dashed lines, respectively. Furthermore, the congested links are denoted as a. If a connection request for a connection from source city CA to destination city L arrives, only AR is able to find a route between CA and L.

Comparisons of Routing Policies

A significant amount of work on the different issues of routing has been reported. Table 4.1 summarizes the major routing policies, and compares their performance in terms of blocking probability, and average setup time [77]. The blocking probability [86,87] in the network is defined as the ratio of the number of blocked lightpath requests to the number of lightpath requests in the network. The average setup time [23] in the network is defined as total execution time required to establish all the lightpaths in the network to the number of successful lightpaths. We observe that FR has the lowest average setup time and time complexity of all routing policies. However, its blocking probability is the highest. AR provides the best performance in terms of blocking probability, but its time complexity is the highest. FAR offers a trade-off between time complexity and blocking probability.

Table 4.1: Summaries of different routing policies.




Performance analysis



On/Off line





Higher BP than others

Shorter AST than others




Lower BP than FR

Longer AST than FR




Almost same as FAR

Almost same as FAR





Lower BP than others

Longer AST than others

On line

< Prev   CONTENTS   Source   Next >