Multiplex communications – Pathfinding or routing
Reexamination Certificate
2003-09-05
2008-12-16
Phan, Man (Department: 2619)
Multiplex communications
Pathfinding or routing
C370S222000, C370S238000, C709S220000
Reexamination Certificate
active
07466688
ABSTRACT:
Techniques for network routing and design are provided. A technique for determining a route for a demand in a network, wherein the network comprises primary paths and secondary paths, and at least two secondary paths may share a given link, comprises the following steps/operations. First, a graph representing the network is transformed. Edges of the graph represent channels associated with paths and nodes of the graph represent nodes of the network. The transformation is performed such that costs associated with the edges reflect costs of using channels in secondary paths. Then, the shortest path between nodes corresponding to the demand is found in the transformed graph. The shortest path represents the least-cost path in the network over which the demand may be routed. When the above route determination steps/operations result in a path with at least one loop, an alternative routing process may be executed so as to determine a loopless path for the demand. Further, integer linear program formulation design techniques are provided.
REFERENCES:
patent: 5892819 (1999-04-01), Stumer
patent: 6023501 (2000-02-01), Wakamatsu
patent: 6141318 (2000-10-01), Miyao
patent: 7023806 (2006-04-01), Gunluk
patent: 7058012 (2006-06-01), Chen et al.
patent: 2002/0073393 (2002-06-01), Campbell et al.
patent: 2002/0118647 (2002-08-01), Maeno
patent: 2003/0023706 (2003-01-01), Zimmel et al.
patent: 2003/0099014 (2003-05-01), Egner et al.
U.S. Appl. No. 10/392,574, filed Mar. 20, 2003, M.A.K. Alicherry et al.
V. Poosala et al., “FASTeR: Shared Restoration Without Signaling,” OFC, pp. 1-4, Mar. 2003.
J.W. Suurballe, “Disjoint Paths in a Network,” Networks, John Wiley and Sons, Inc.,vol. 4, pp. 125-145, Jun. 1974.
E.L. Lawler, “A Procedure for Computing theKBest Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem,” Management Science, vol. 18, No. 7, pp. 401-405, Mar. 1972.
Alicherry Mansoor Ali Khan
Nagesh Harsha S.
Phadke Chitra A.
Poosala Viswanath
Alcatel-Lucent USA Inc.
Phan Man
LandOfFree
Routing and design in K-shared network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routing and design in K-shared network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing and design in K-shared network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4027463