Fast and scalable approximation methods for finding minimum...

Multiplex communications – Pathfinding or routing

Reexamination Certificate

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

C370S468000, C370S238000

Reexamination Certificate

active

10053079

ABSTRACT:
Broadly, techniques for solving network routing within a predetermined error are disclosed. These techniques may be applied to networks supporting dedicated reserve capacity, where reserved capacity on links in the network is dedicated for a particular commodity (generally, a source and sink pair of computers), and shared recovery, where reserved capacity on links is shared amongst two or more commodities. These techniques use an iterative process to determine flows on each of the links in a network. Costs are set for each commodity, and primary and secondary (i.e., backup) flows are initialized. A commodity is selected and demand for the commodity is routed through the shortest path. Costs are updated for each potential failure mode. For each commodity, the flows and costs are updated. Once all flows and costs are updated, then it is determined if a function is less than a predetermined value. If the function is less than a predetermined value, then the commodity selection, and flow and cost adjustments are again performed. If the function is greater than the predetermined amount, then the network routing problem is solved to within a predetermined amount from an optimal network routing.

REFERENCES:
patent: 5754543 (1998-05-01), Seid
patent: 5862125 (1999-01-01), Russ
patent: 6256295 (2001-07-01), Callon
patent: 6301244 (2001-10-01), Huang et al.
patent: 6324162 (2001-11-01), Chaudhuri
patent: 6363319 (2002-03-01), Hsu
patent: 6542469 (2003-04-01), Kelley et al.
patent: 6628649 (2003-09-01), Raj et al.
patent: 6744727 (2004-06-01), Liu et al.
patent: 6744775 (2004-06-01), Beshai et al.
patent: 6914912 (2005-07-01), Skalecki et al.
patent: 6928484 (2005-08-01), Huai et al.
patent: 2002/0038360 (2002-03-01), Andrews et al.
patent: 2002/0186665 (2002-12-01), Chaffee et al.
Jerram et al., MPLS in Optical Networks, “An Analysis of the features of MPLS and generalized MPLS and their application to Optical Networks, with reference to the Link Management Protocol and Optical UNI,” Oct. 2001, 1-48.

LandOfFree

Say what you really think

Search LandOfFree.com for the USA inventors and patents. Rate them and share your experience with other people.

Rating

Fast and scalable approximation methods for finding minimum... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fast and scalable approximation methods for finding minimum..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast and scalable approximation methods for finding minimum... will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFUS-PAI-O-3902928

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.