New Page 1

Michael R. Bartolacci
Information Sciences and Technology
Penn State University

Berks/Lehigh Valley College

147 Academic Building

8380 Mohr Lane

Fogelsville, PA 18051

mrb24@psu.edu

S. David Wu
Professor and Chair

Industrial and Systems Engineering Department

Mohler Laboratory

Lehigh University

Bethlehem, PA 18015

sdw1@lehigh.edu

A routing heuristic is proposed for telecommunication networks, based on a classic algorithm that has been extended to allow multiple paths to be utilized. The procedure was inspired by the work of Frank and Chou in that it identifies potential paths and relies on a similar flow assignment heuristic to route flows onto paths. Unlike Frank and Chou's single path routing procedure, the proposed routing procedure is flexible in that it can potentially utilize k paths. The procedure is well suited for recent advances in optical networks where traffic should be routed over several paths, but routing decisions must be made a priori to accommodate optical switches and routers. Routing simulations show the routing procedure to be superior to the Frank and Chou method for networks with heterogeneous capacity structures and at higher traffic levels.

The bulk of the literature regarding telecommunications network routing focuses on one of two general approaches: static or dynamic. Static algorithms were a natural outgrowth of the existing telecommunications infrastructure until very recently where circuit-switched connections dominated. These routing procedures tended to be static in nature with paths determined on an infrequent basis. Dynamic routing approaches allow traffic to be routed in accordance with current network traffic conditions, but most do not encourage overall optimization of capacity use across a network. Quasi-static routing approaches, such as those proposed by Gallager⁹, Bertsekas, et al.² [2] and others, sought to bridge the gap between static and dynamic and have been left behind with the tremendous changes in routing technology that have occurred in the last few years. Beyond the temporal aspects of routing, the nature of the paths used for routing has also been a source of variation. Single path routing represented the bulk of routing approaches due to the nature of the existing telephone-based network, but bifurcated routing approaches have flourished due to the development of the Internet. Traditional routing technology utilizes electronic devices for storing routing tables in a "store and forward" routing environment where packets must be analyzed at each intermediate for their destination information. Such routing creates noticeable nodal processing delays while routing tables are consulted and packets are then directed to an appropriate outbound buffer. These processing delays were one of the major disadvantages of true bifurcated routing; therefore, such approaches were not often utilized in the past.

The nature of routing technology is moving away from the use of electronic routing devices. The deployment of vast amounts of high capacity fiber optic cable has created the need for a new type of routing technology. The drawback for many routing models proposed was that they failed to take into account the delays due to nodal processing created by the optical/electronic/optical conversions required at each node for reception, route determination, and retransmission. The need to convert from an inbound optical transmission to electrical signals for routing and back to optical for retransmission from a node slows the entire communication process. Engineers are currently developing the next generation of routers that will eliminate the need for this conversion and will be strictly optical in nature. Work such as that done by Mokhtar and Azizoglu¹⁹ seeks to optimize the optical routing process in which a route must be determined from a candidate set of routes. The importance of this shift from electronic routing to optical routing is that routing must be an instantaneous process, and an optical packet cannot afford to wait for a route to be determined. The routing determination time required for all-optical processing favors a process by which paths are set up ahead of time. It also renders the need to factor nodal processing delays into routing models virtually obsolete.

Technologies such as Asynchronous Transfer Mode (ATM) utilize connection-based routing via Virtual Paths (VP) to gain a tremendous advantage in speed by eliminating the costly overhead of traditional routing. The proposed static routing approach is well suited for such a routing environment in that k paths to each destination from a given source node can be determined and set based on anticipated traffic requirements, network capacity, and the physical network topology if necessary. These paths can then be efficiently routed using the results of a flow assignment heuristic. The focus of this work is on the heuristic that improves upon the classical routing procedure by Frank and Chou while adding the flexibility of being able to identify multiple paths if necessary. One might argue that an older algorithm does not warrant treatment or improvement, but such algorithms are constantly varied upon, improved, and incorporated into new approaches. Testing on standard test networks from the telecommunications modeling literature was conducted. These test networks reflect older topologies of the early 1990’s, but there exists a dearth of standard test networks in the literature, and such networks are still utilized in limited testing situations since capacity is a matter of scale when testing one algorithm versus another one.

Frank and Chou⁷ were among the first researchers to develop a centralized, static routing heuristic. Their work was based on the multi-commodity network flow model, but the heuristic they developed was limited to virtual circuit (single path) routing. Their algorithm provided the inspiration for the proposed routing procedure. Their heuristic sought to minimize average time delay in a network with static traffic requirements and fixed arc capacities. Their routing procedure consisted of the following basic steps:

a. Generate all shortest paths (in number of intermediate nodes) from each source

b. For each source node, group destination nodes based on shortest path length (in

c. For each source node, route traffic to adjacent destination nodes first; then route

Another centralized static routing heuristic based on the multi-commodity flow model was the classic "Flow Deviation Method" by Fratta, Gerla, and Kleinrock⁸. Their bifurcated routing procedure utilized repeated applications of a steepest descent approach for incrementally assigning flows to paths. This method assigned flows along shortest paths (as determined by an arbitrary metric) incrementally in a manner that approaches steepest descent. Cantor and Gerla³ eliminated the propagation delay terms from Kleinrock's equation for average network delay in the objective for their routing heuristic. Their "Extremal Flows" method utilized gradient projection for the iterative assignment of flows to routes. This approach was similar to the "Flow Deviation Method" and represents a computationally intensive method for bifurcated routing. Pirkul and Narasimhan²² addressed the problem of choosing a primary and secondary route for all communicating source-destination pairs in a backbone network. Secondary routes are considered only for the cases of node or link failure. This approach therefore differs from the proposed approach in that the k paths are identified as part of the overall routing scheme to be used for the splitting of traffic.

Topkis²⁵ proposed a k loop-less shortest path algorithm for adaptive routing in telecommunication networks. This dynamic routing methodology was built upon a routing technique termed delta routing. Delta routing should not be confused with our proposed routing approach, delta-s, which is a novel static routing procedure utilizing k shortest paths. Delta routing, which was actually implemented in the TRANSPAC public data network in France, works in the following manner:

b. the delay estimates are periodically transmitted to a centralized routing center.

d. the routing center then transmits to each node a routing table corresponding to

each other node where the routing table consists of the initial links on those of

Most of the other proposed heuristics for bifurcated routing, such as the procedures proposed by Gavish and Neuman¹¹ and Gavish and Altikemer¹² employ a form of Lagrangean relaxation and subgradient optimization for the solution of the multi-commodity network flow problem or a special case of it. Although many of these approaches have been shown to produce very good solutions for theoretical test networks, they are restricted by their underlying mathematical rigidity in their ability to incorporate practical constraints as a network evolves. Work by Gendreau, Sanso, and Stanford¹³ formulated a variant of the multi-commodity network flow for delay minimization. Their solution approach involved the identification of feasible flow patterns and the subsequent iterative modification of flow quantities to identify local optima. Their approach is noteworthy in this discussion in that flows were not required to have an underlying Poisson arrival process, a standard assumption for most routing models. In general, the solution of the static bifurcated routing problem for telecommunication networks has not received as much recent attention as either single path (virtual circuit) or dynamic routing. This was due to the fact that until the growth of the Internet in the mid-1990's, the independent routing of individual packets (and the splitting of traffic streams) was more of a novelty than a widespread practice in networking.

Although the proposed routing heuristic is based on the work of Frank and Chou and would be utilized as a single path routing method for most current networks, a discussion of work with respect to shortest paths is useful. Much work has been conducted on the determination of k shortest paths in a network or graph. Some of the earlier seminal works include those by Pollack²³, Clarke, et al.⁴, Dreyfus⁵, Yen²⁶, and Lawler¹⁸. Two separate types of k shortest path problems were investigated: loopless paths and those that were allowed to contain loops. The practical applications of the first type of problem are obvious, but it also created additional complexity with respect to the algorithmic approaches. The Double Sweep algorithm developed by Shier²⁴ [24] is of the second type. Other more recent work by Katoh, et al.¹⁶, Gallo and Pallottino¹⁰, Perko²⁰, and Azevedo, et al.¹ all focus on reviewing or improving the efficiencies of some of the earlier approaches. Most of the approaches proposed deal with so-called "label correcting" algorithms that grew from the classical single-origin, all-destinations shortest path problem. Significant works by Guerriero, et al.¹⁴ and Eppstein⁶ in the last five years have also added to the body of literature in this area. Eppstein's approach, in particular, focuses on applications in which loops would be allowed, and all paths shorter than a given length with the same time bounds can be found.

Routing problems for telecommunication networks are traditionally modeled using the Multi-Commodity Network Flow Model. This model is presented in the context of defining the nature of the routing problem that will be solved heuristically due to its complexity. A communication network consists of two basic elements: stations that wish to communicate with each other (nodes) and the transmission media used to connect these stations (links). These nodes and arcs form a directed graph D(V,A) where V is the set of all nodes and A is the set of all arcs in the graph. For D(V,A) there are C pairs of source-destination nodes. These pairs are represented by (s^c,d^c) with c = 1, ... C. The traffic from a specific source to its destination is considered a "commodity." Each arc (i,j) in the network has a capacity defined as u_ij.

Also, there exists a requirements matrix F consisting of the required flows for each commodity. The sum of all elements of this matrix is G. The multi-commodity network flow model represents the basis for the problem formulation where an objective function based on Kleinrock's equation for average network delay [17] is utilized for the objective function and is formulated as:

Assumptions made relative to the formulation above for its application to a telecommunications network include the following: a single class of service exists for each commodity, infinite buffers exist at each node in the network for storing traffic, packet lengths are exponentially distributed (in order to apply a form of Kleinrock's average delay function), propagation delays are minimal and can be ignored (traffic travels near the speed of light and therefore delays incurred due to distance traveled are negligible), and no nodal processing delays are incurred (this assumption is based on the use of optical switching technologies as described in the introduction).

The proposed routing method consists of a bifurcated routing procedure but was developed for (and inspired by) single path routing such that alternate paths would be available if needed. This procedure can be configured to handle more limited cases where a single path is chosen among several candidate paths for each commodity's traffic. The proposed routing heuristic utilizes a k-shortest path algorithm, which identifies potential paths for bifurcated flows and a flow assignment heuristic that determines the percentages of flow requirements that are routed on each path. The flow assignment heuristic is implemented within an iterative framework that seeks to identify local optima with respect to the minimization of average delay for a network. The complete procedure is detailed in Figure 1.

Much like Frank and Chou's approach [7], we first identify potential paths using Phillips and Garcia-Diaz's²¹ implementation of Shier's Double Sweep k-shortest path algorithm [24]. The parameter k utilized by our approach is topology-dependent but should be large enough to ensure that each commodity's traffic will have several potential paths on which to route its traffic. A tradeoff involved in the selection of k is the storage required for additional path information versus the advantage of identifying additional potential paths on which to route traffic. A drawback of using an arbitrarily large k is the computation time involved with shortest path calculations. In contrast to dynamic routing procedures that utilize instantaneous queue length and other delay-related information for shortest path calculations, the distance measure d_ijutilized in the proposed approach is a linear combination of the normalized flow requirements NFR_ij between two given nodes, i and j, and the normalized topological distance NTD_ij between the two nodes. The corresponding weights for each are a₁ and (1 - a₁) respectively. The formulas for each are as follows:

The inclusion of the normalized topological distance NTD_ij in the distance measure follows from Frank and Chou's requirement that traffic from adjacent nodes be routed first. The weight a determines the relative importance of the two distance measures.

The next part of the proposed routing procedure is the flow assignment heuristic which is implemented in an iterative manner. The number of iterations is a parameter that can be tuned depending upon the size and density of the network being routed. Following the assignment of all traffic requirements for all commodities in the network, residual capacities are calculated for all paths. These residual capacities are utilized in determining the next iteration's flow assignments. The flow assignment heuristic for bifurcated routing involves the determination of what portion of a commodity's flow requirements should be assigned to each of the k paths identified. The flow assignment heuristic consists of two basic steps for which the second step utilizes the residual path capacities of the previous iteration. These two steps are

The first step ranks commodities in order to determine the order for consideration in the flow assignment step. Commodities are ranked in ascending order utilizing a ranking metric, rm_ij, which is a linear combination of the normalized flow requirements between the nodes, NFR_ij, and the normalized distance in hops, NDH_ij, with respective weights b and (1 - b ).

The smaller the ranking metric for a given commodity, the greater the priority it is given with respect to the order of flow assignment.

The next step of the flow assignment heuristic is the assignment of flows to paths identified by the k-shortest path algorithm. This step of the heuristic is implemented in an iterative fashion using the residual path capacities from the previous iteration and an iteration weight parameter w_z for iteration z. The assignment of flow to each path for a given commodity is based on the fraction of total capacity available on all k paths identified that a particular path provides. For each ranked commodity c, the following procedure determines each path's fraction of the flow requirements that it will carry:

The traffic assignment quantity, TA^p_c, is the amount of traffic for commodity c that is to be routed over viable path p. Each viable path is then considered in order of increasing length (resulting from k shortest path calculations) for actual routing of traffic. Each path is then assigned the following traffic with current capacity calculations being conducted after every flow assignment to a path:

The determination of u_c^zp in (13) is necessary for the iterative improvement desired in the heuristic. The proper tuning of the iteration weight is a key factor in obtaining decreases in average delay over the range of the iterations. The second term of (13) encourages those paths with greater residual capacities to be assigned greater relative portions of the flow requirements. The result of the iterative flow assignment heuristic part of the proposed routing procedure is the determination of the amounts of traffic for each commodity that are routed on each of the k paths identified. The quantities of traffic for each path can be easily converted to percentages for routing implementation purposes.

Two modifications to the flow assignment heuristic are needed in order to accommodate single path network routing. Although k paths are still identified through the Double Sweep algorithm, only one of the paths is used for each commodity. The other paths would be reserved as alternates in the event of a node or link failure in an implementation. The first modification is to eliminate the repeated calculations of current capacity for each path for a given commodity. The capacities for all paths of a given commodity are calculated once prior to flow assignment. The second modification concerns the flow assignment metric FA^p_c. The flow assignment metric is calculated as before for all feasible paths, but single path routing only requires the path with the greatest FA^p_c to be chosen for flow assignment. This path is then assigned Min {CC^p_c,F^c}.

For testing purposes, we assigned our static routing method the name "Delta-S.” Due to the fact that the classic Frank and Chou algorithm provided the inspiration for the proposed routing method, and that no static k shortest path-based telecommunications routing algorithms were available from the literature, Delta-S was tested against the Frank and Chou routing procedure. Both are static routing procedures, but Delta-S was limited to single path routing for the testing in order to make a fair comparison. Standard test networks from the literature were utilized along with several generated networks with specific properties for the computational testing. The capacities of the standard test networks from the literature do not reflect recent increases in capacities due to new technologies, but this is merely a question of scale for routed traffic and does not affect their properties for routing. Generated test networks were also kept to a similar scale for capacities and routed traffic capabilities in order to make a fair comparison with the standard test networks. All testing results tables show the percentage from the best for a given set of parameters (traffic level, nodal degree, test network) for each algorithm tested (Delta-S and Frank and Chou).

Four factors affecting average delay were identified and utilized in computational testing. Parameter tuning experiments on 50 node random geometric networks (generated via a procedure based on the one defined in [15]) were conducted in order to determine appropriate values of z and w_z. The number of iterations, z, was set at 100, and the iteration weight, w_z, at .1 for all tests following parameter tuning experiments. For each set of experiments, the parameter was varied within an appropriate range. Another factor identified was the variation of capacity within the network. Experiments on homogeneous capacity, varied-level capacity, and random capacity networks were conducted. The average nodal degree connectivity was also utilized as a testing parameter. Experiments on networks displaying varying levels of average nodal degree connectivity were also conducted. All of the experiments display the performance of each algorithm versus the other in terms of "% from best.”

The first set of experiments sought to identify the effects of capacity variation on the routing performance for Delta-S (D-S) versus the Frank and Chou (F&C) algorithm. The standard USA test network (Figure 2) is a network of 26 nodes and 40 bi-directional links of four different capacity levels. This test network is an example of the varied-level capacity network previously mentioned. Table 1 displays the average routing delays results for the USA network. It can be seen that Delta-S performs better than F&C at greater traffic levels for these experiments.

The results in Table 1 from the USA network can be compared with the results for the ARPA test network of 21 nodes and 26 bi-directional links with a homogeneous capacity arrangement. The ARPA test network in Figure 3 contains communication links of 50 kbps capacity each. The results in Table 2 show that F&C gave lower average routing delays at all traffic levels. This would suggest that Delta-S is not well suited for homogeneous capacity networks, an unrealistic scenario in the present networking environment. Further experiments reveal some advantages of Delta-S in other types of networks with heterogeneous capacity arrangements.

Three generated test networks of 36 nodes and 55 bi-directional links with the same physical topology, but different capacity arrangements, entitled Chou 1, Chou 2, and Chou 3 (see figures 4a - 4c) were also tested. Chou 1 is similar to the ARPA network in that it contains homogeneous capacity links. Chou 2 is the same topology displaying an obvious backbone arrangement. Chou 3 displays an "ad hoc" capacity arrangement representing a network where capacity is added on an "as needed" basis. The results of the experiments on these topologies are given in Tables 3-5. These results confirm that F&C is much more suited for networks with a homogeneous capacity arrangement as is the case with Chou 1. D-S performed very well on the other two-capacity arrangements that better represent actual networks.

Additional experiments were conducted on more general topologies. Five random geometric 50 node networks were generated (based on a procedure outlined in [15]) with an average nodal degree of 6. Random capacities between 30 kbps and 80 kbps were generated for the networks. The results in Tables 6-10 show an advantage in performance for D-S in routing these test networks.

A set of experiments on randomly generated geometric networks was conducted in order to explore the performance of Delta-S when the average nodal degree of such networks is relatively small. Two sets of these networks were generated, one with an average nodal degree of six and another with an average nodal degree of 3. Table 11 displays the average routing delays for both sets of networks for both Delta-S and Frank and Chou. Figure 5 graphically displays the average "percentage from best" for both routing procedures across both sets of test networks. It is apparent from the graph that the performance of Delta-S versus Frank and Chou is superior at the three highest traffic levels (which are much greater than initial traffic levels tested), which is a very favorable result.

The proposed routing procedure, Delta-S, is a static, bifurcated routing procedure that was inspired by the work of Frank and Chou⁷ but presents a novel approach for routing that is well suited to recent advances in optical networking. The foundation of the routing procedure utilizes a k shortest path algorithm to identify paths and a flow assignment heuristic that seeks to minimize average routing delay in the network. Due to the fact that the proposed k shortest path telecommunication routing approaches in the literature are of a dynamic nature, Delta-S was tested against a static single path routing procedure: the Frank and Chou routing procedure. The procedure was tested on various test networks from the literature including the USA, RING, and ARPA networks. In addition, three new test networks were created with varying levels of capacity homogeneity. From all of this testing, Delta-S proved valuable in networks with more realistic capacity arrangements and at the higher traffic levels tested. Although not originally designed for single path routing, Delta-S performed very well against the Frank and Chou procedure that was created expressly for single path routing.

4. Clarke, S., A Krikorian, and J. Rausen (1963), "Computing the N Best Loopless

8. Fratta, L., M. Gerla, and L. Kleinrock (1973), "The Flow Deviation Method: An

24. Shier, D.A. (1976), "Iterative Methods for Determining the K Shortest Paths in a

Volume 4, Number 1, Fall 2003