Routing method for ring networks, such as WDM ring networks for optical communication
US6381046B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 21, 1999 |
| Grant date | Apr 30, 2002 |
| Priority date | — |
| Expiry date | Jan 21, 2019 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04J14/0249
- WIPO fieldTelecommunications
- WIPO sectorElectrical engineering
Abstract
We disclose a method for routing a set of demands in a ring network that comprises nodes interconnected by directed links, in which each demand may be routed clockwise or counterclockwise. According to our method, a linear program is solved to obtain a set of routing variables that minimize an objective function. Each routing variable corresponds to a respective one of the demands, and has a value, exemplarily, on the closed interval from 0 to 1. A value of 1 signifies, e.g., clockwise routing, and a value of 0 signifies counterclockwise routing. The objective function describes the value of a load, defined on each link and maximized over all links of the network, so that a solution of the linear program provides a minimum value of the maximized load. The method further comprises rounding the routing variables so that the value of each routing variable falls at 1 or 0. This rounding is carried out such that the maximized load does not exceed the previously-obtained minimum value of the maximized load. The method further comprises routing each of the demands clockwise or counterclockwise, in accordance with the value of its respective routing variable.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.