Multiplex communications – Pathfinding or routing
Reexamination Certificate
2007-10-09
2007-10-09
Nguyen, Hanh (Department: 2616)
Multiplex communications
Pathfinding or routing
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.
Fleischer Lisa Karen
Saniee Iraj
Shepherd Frederick Bruce
Srinivasan Aravind
Lucent Technologies - Inc.
Nguyen Hanh
LandOfFree
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.
Profile ID: LFUS-PAI-O-3902928