Browse Prior Art Database

On-line Regenerator Placement Method in Optical Networks

IP.com Disclosure Number: IPCOM000247338D
Publication Date: 2016-Aug-25
Document File: 2 page(s) / 30K

Publishing Venue

The IP.com Prior Art Database

Abstract

We present randomized protocol for on-line regenerator placement problem in optical networks. In the on-line regenerator placement problem paths arrive sequentially. Each new path has to be handled without changing regenerator placement for the paths that were already handled. We present randomized protocol that computes regenerator placement for each new path. If maximum degree of a graph spanned by the set of all light paths is at most dk/4 then our protocol guarantees that all light paths are satisfied with high probability at least 1 - 1/n, where n is the number of nodes in the network.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 01 of 2

On-line Regenerator Placement Method in Optical Networks

We present randomized protocol for the On-line Regenerator Placement Problem (RPP) in Optical networks. Our randomized protocol computes regenerator placement for each new path. If maximum degree of a graph spanned by the set of all light paths is at most dk/4 then our protocol guarantees that all light paths are satisfied with high probability at least 1 - 1/n, where n is the number of nodes in the network

Background

We present randomized protocol for the On-line Regenerator Placement Problem (RPP) in Optical networks. One of the main challenges in optical networks is that the signal in a light path has to be regenerated every d hops. Therefore, in order to satisfy a given set of light paths {P1; … ; Pm}, additional regenerator devices have to be placed in nodes of the optical network, in such a way that the distance between any two consecutive regenerators is at most d for each light path. Regenerators cannot be shared between light paths. This problem would be trivial if each node in the optical network could store infnitely many regenerators. However, in real optical networks capacity of a node is limited by some value k =>1. In the on-line version of the RPP the set of light paths is not known in advance.

Light paths that need to be handled arrive sequentially. The protocol has to handle each path once
it arrives without changing the placement of regenerators that were already placed to satisfy needs of the previously arrived light paths. Such scenarios often occure in real optical networks, and are much more challenging than the static ones (off-line) in which all light paths are known in advance. It was shown in [1] that off-line RPP problem is NP-complete for d=3 and k=1. No on-line protocols are known for this problem. We show that on-line RPP can be solved by randomized protocol with very high probability. More precisely, if the maximum node degree of a graph spanned by the set of all light paths is at most dk/4 then our protocol guarantees success with very high probability of at least 1 - 1/n, where n is the total number of nodes in the network.


[1] On the Complexity of the Regenerator Placement Problem in Optical Networks Flammini, M.; Marchetti-Spaccamela, A.; Monaco, G.; Moscardelli, L.; Zaks, S. Networking, IEEE/ACM Transactions on Volume: 19, Issue: 2 , 2011 , Page(s): 498 - 511

Summary of the idea

We present randomized protocol for on-line regenerator placement problem in optical networks. In the on- line regenerator placement problem paths arrive sequentially. Each new path has to be handled without changing regenerator placement for the paths that were already handled. We present randomized protocol that computes regenerator placement for each new path. If maximum degree of a graph spanned by the set of all light paths is at most dk/4 then our protocol guarantees that all light paths are satisfied with high proba...