Capacity allocation for fast path restoration

Details Capacity allocation for fast path restoration Capacity allocation for fast path restoration

2007-08-28

2007-08-28

Jain, Raj K. (Department: 2616)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S230000, C370S231000, C370S232000, C370S235000, C370S238000, C370S395210, C709S223000, C709S226000, C709S229000, C709S241000, C709S239000

Reexamination Certificate

active

10357559

ABSTRACT:
Capacity design of an optical network for demands of fast path restorable (FPR) connections forms a linear programming sizing problem for a optimal routing. A dual of the linear programming sizing problem is formed and solved with an approximation algorithm. Edge lengths are initialized based on i) the inverse of the edge's capacity and ii) a scalar constant. Then, the approximation algorithm proceeds in phases to route each commodity over the edges of a graph. During each phase, the demand's flow is sent from the source to destination via multiple iterations. During each iteration, the set of shortest disjoint paths from the source to the destination is determined, a portion of the flow is sent, and the lengths of the edges that carry the flow are updated. The value employed to scale the network is generated after the last phase from the maximum ratio of edge flow to edge capacity.

REFERENCES:
patent: 6498778 (2002-12-01), Cwilich et al.
patent: 6909700 (2005-06-01), Benmohamed et al.
patent: 7145867 (2006-12-01), Aicklen et al.
“Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems” by Naveen Garg and Jochen Kömann, pp. 1-10.
“A Simple Efficient Approximation Scheme for the Restricted Shortest Path Problem” by Dean H. Lorenz and Danny Raz, pp. 1-10.

Affiliated with

Also associated with

Rating

Capacity allocation for fast path restoration does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Capacity allocation for fast path restoration, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capacity allocation for fast path restoration will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3863990