Capacity allocation for networks having path length routing...

Details Capacity allocation for networks having path length routing... Capacity allocation for networks having path length routing...

2003-02-04

2009-12-15

Mattis, Jason E (Department: 2416)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S235000, C370S236000

Reexamination Certificate

active

07633867

ABSTRACT:
Capacity design of an optical network for demands of 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 shortest length-bounded path 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: 5546542 (1996-08-01), Cosares et al.
patent: 5940372 (1999-08-01), Bertin et al.
patent: 6538991 (2003-03-01), Kodialam et al.
patent: 7263100 (2007-08-01), Hauser et al.
patent: 2006/0051090 (2006-03-01), Saniee et al.
“Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems” by Naveen Garg and Jochen Könemann, 1998, pp. 1-10.
“A Simple Efficient Approximation Scheme for the Restricted Shortest Path Problem” by Dean H. Lorenz and Danny Raz, 1999, pp. 1-10.

Affiliated with

Also associated with

Rating

Capacity allocation for networks having path length routing... 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 networks having path length routing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Capacity allocation for networks having path length routing... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4148318