The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Apr. 30, 2002
Filed:
Jan. 21, 1999
Gordon Thomas Wilfong, Gillette, NJ (US);
Peter M. Winkler, Madison, NJ (US);
Lucent Technologies Inc., Murray Hill, NJ (US);
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.