^{1,a)}, Mohamed Jedra

^{1,b)}and Noureddine Zahid

^{1,c)}

### Abstract

In this paper, we present a new routing algorithm called “the self avoiding paths routing algorithm.” Its application to traffic flow in scale-free networks shows a great improvement over the so called “efficient routing” protocol while at the same time maintaining a relatively low average packet travel time. It has the advantage of minimizing path overlapping throughout the network in a self consistent manner with a relatively small number of iterations by maintaining an equilibrated path distribution especially among the hubs. This results in a significant shifting of the critical packet generation rate over which traffic congestion occurs, thus permitting the network to sustain more information packets in the free flow state. The performance of the algorithm is discussed both on a Barábasi-Albert network and real autonomous system network data.

The understanding of information flow throughout a complex network is an important issue from both a theoretical and a practical point of view. The goal of such understanding is to control the traffic in complex systems such as the internet. Indeed, the main problem with these systems is the emergence of congestion when the traffic load becomes higher than a certain threshold. To solve this problem, studies focus on the mechanism of routing of information packets to reach their destinations. In this respect, the well known shortest path protocol directs the traffic more likely towards the more connected nodes (hubs). Many alternative routing protocols (static and traffic aware protocols) have been proposed in order to obtain an equilibrated traffic load between the different paths. The latter protocols need extra communication between the routers compared to the static ones which can easily be implemented. But the proposed static algorithms did not, in general, use the optimal paths explicitly. By introducing a self avoiding mechanism between the paths during the process of their construction, we were able to devise a new routing protocol called: “the self avoiding paths routing (SAPR) algorithm” that results in an optimal distribution of the paths and performs better than many of the previous protocols in raising the overall network capacity.

I. INTRODUCTION

II. MODEL

III. SIMULATION RESULTS AND DISCUSSION

IV. CONCLUSION

### Key Topics

- Electron paramagnetic resonance spectroscopy
- 12.0
- Networks
- 8.0
- Internet
- 3.0
- Information and communication theory
- 2.0
- Complex systems
- 1.0

## Figures

Path discovery process of the SAPR algorithm. (a) The algorithm is in node *u* and tries to check for node *v* with an already existing path via *t*. (b) In this case, the path through *u* is found to have the lowest cost and the path through *t* is removed, so the node costs are updated for the two paths down to the source node *s*. The operations +1 and −1 are to be performed on the number of paths on every node along the two paths (see the two pseudo-codes in text).

Path discovery process of the SAPR algorithm. (a) The algorithm is in node *u* and tries to check for node *v* with an already existing path via *t*. (b) In this case, the path through *u* is found to have the lowest cost and the path through *t* is removed, so the node costs are updated for the two paths down to the source node *s*. The operations +1 and −1 are to be performed on the number of paths on every node along the two paths (see the two pseudo-codes in text).

Number of current packets in the network *N _{cur} * as a function of the number of iterations

*N*for the SAPR algorithm for different values of the parameter α (BA network with

_{iter}*N*= 1000).

Number of current packets in the network *N _{cur} * as a function of the number of iterations

*N*for the SAPR algorithm for different values of the parameter α (BA network with

_{iter}*N*= 1000).

Plot of the average path length as a function of the number *N* of nodes in the BA network for , 4.0, and 6.0.

Plot of the average path length as a function of the number *N* of nodes in the BA network for , 4.0, and 6.0.

Order parameter η (given by Eq. (6) ) of the SAPR algorithm as a function of the packet generation rate *R* for different α values. The arrow indicates the position of the critical value for (BA network with *N* = 1000).

Order parameter η (given by Eq. (6) ) of the SAPR algorithm as a function of the packet generation rate *R* for different α values. The arrow indicates the position of the critical value for (BA network with *N* = 1000).

Plot of the average travel time as a function of the packet generation rate *R* for the algorithms SPR and EPR compared with the SAPR algorithm with (BA network with *N* = 1000).

Plot of the average travel time as a function of the packet generation rate *R* for the algorithms SPR and EPR compared with the SAPR algorithm with (BA network with *N* = 1000).

Plot of the average travel time as a function of the packet generation rate *R* for the algorithms SPR and EPR compared with the SAPR algorithm with , for the AS-733 Oregon Route Views dataset network with *N* = 549.

Plot of the average travel time as a function of the packet generation rate *R* for the algorithms SPR and EPR compared with the SAPR algorithm with , for the AS-733 Oregon Route Views dataset network with *N* = 549.

Variation of the average path length vs. α. The values of corresponding to the algorithms SPR and EPR are indicated for comparison by the arrows (BA network with *N* = 1000).

Variation of the average path length vs. α. The values of corresponding to the algorithms SPR and EPR are indicated for comparison by the arrows (BA network with *N* = 1000).

Critical packet generation rate *R _{c} * as a function of α values. The arrows indicate the values corresponding to the SPR and the EPR algorithms (BA network with

*N*= 1000).

Critical packet generation rate *R _{c} * as a function of α values. The arrows indicate the values corresponding to the SPR and the EPR algorithms (BA network with

*N*= 1000).

Dependence of the number of paths *N _{paths} * traversing each node on the node degree

*k*for the three algorithms: SPR, EPR, SAPR (with ) and EPR2 (BA network with

*N*= 1000).

Dependence of the number of paths *N _{paths} * traversing each node on the node degree

*k*for the three algorithms: SPR, EPR, SAPR (with ) and EPR2 (BA network with

*N*= 1000).

Plot of the average travel time as a function of the packet generation rate *R* for the algorithms SPR and OR compared with the SAPR algorithm with for the BA network with *N* = 200 nodes.

Plot of the average travel time as a function of the packet generation rate *R* for the algorithms SPR and OR compared with the SAPR algorithm with for the BA network with *N* = 200 nodes.

Article metrics loading...

Full text loading...

Commenting has been disabled for this content