Minimum-cost routing with network coding

Details Minimum-cost routing with network coding Minimum-cost routing with network coding

2004-12-30

2008-08-19

Ngo, Ricky (Department: 2616)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S396000, C370S390000, C709S232000

Reexamination Certificate

active

07414978

ABSTRACT:
A method and computer program product for performing minimum cost routing with network coding is presented. The method and system model a network as a directed graph. A cost per unit flow is associated with each link of the directed graph. A link capacity is associated with each link of the directed graph. A network code is then computed that sets up a routing connection that achieves an optimal cost using the cost per unit flow for each link of the directed graph and using the link capacity for each link of the directed graph.

REFERENCES:
patent: 5596719 (1997-01-01), Ramakrishnan et al.
patent: 6762997 (2004-07-01), Liu et al.
patent: 7020086 (2006-03-01), Juttner et al.
patent: 7035937 (2006-04-01), Haas et al.
patent: 2004/0218536 (2004-11-01), Yasukawa et al.
patent: 2005/0010675 (2005-01-01), Jaggi et al.
patent: 2005/0152391 (2005-07-01), Effros et al.
Bertsekas et al.;“Relaxation Methods for Minimum Cost Network Flow Problems”; Oct. 1983; p. 2-62;□□□□Bertseka et al. ;“Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems”: Feb. 1988; JSTOR; pp. 93-106.
Bertsekas et al.; “E-Relation and Auction Methods For Seperable Convex Cost Network Flow problems”; Apr. 1996; pp. 2-18.□□□□Wu et al; “Network palnning in Wireless Ad hoc Network: A Cross-layer Approach”; Nov. 2003; p. 2-39.
Wu et al. “Minimum-Energy Multicast in Mobile Ad hoc Networks using Network Coding”; Mar. 2004; p. 2-24.□□□□Ashlswede et al; “Network Information Flow”; 2000; IEEE; pp. 1204-1216.
Bertsekas et al.; “The Auction Algorithm: A Distributed Relaxation Method for the Assignment Problem”: 1988; J.C. Baltzer A.G.; p. 105-120. Parsa et al.; “An Iterative Algorithm for Delay- Constrained Minimum-Cost Multicasting”; IEEE; pp. 461-473.
Rudolf Ahlswede, et al., “Network Information Flow”, IEEE Transactions on Information Theory, vol. 46, No. 4, Jul. 2000, pp. 1204-1216.
Ashwinder Ahluwalia, et al., “On the Complexity and Distributed Construction of Energy-Efficient Broadcast Trees in Static Ad Hoc Wireless Networks”, In Proceedings. 2002 Conference on Information Sciences and Systems (CISS 2002), Mar. 2002, pp. 807-813.
Ning Cai, et al., “Secure Network Coding”, In Proceedings, 2002 IEEE International Symposium on Information Theory, Jun. 30-Jul. 5, 2002, p. 323.
Philip A. Chou, et al., “Practical Network Coding”, In Proceedings. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 40-49.
Alan Demers, et al., “Epidemic Algorithms for Replicated Database Maintenance”, In Proc. ACM Symposium on Principles of Distributed Computing, 1987, pp. 1-12.
Michelle Effros, “Distortion-Rate Bounds for Fixed-and Variable-Rate Multiresolution Source Codes”, IEEE Transactions on Information Theory, vol. 45, No. 6, Sep. 1999, pp. 1887-1910.
Tracey Ho, et al., “On Randomized Network Coding”, In Proc. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 11-20.
Tracy Ho, et al., “Byzantine Modification Detection In Multicast Networks Using Randomized Network Coding”, ISIT 2004, Chicago, USA, Jun. 27-Jul. 2, 2004, p. 144.
Tracey Ho, et al., “The Benefits of Coding Over Routing In A Randomized Setting”, ISIT 2003, Yokohama, Japan, Jun. 29-Jul. 4, 2003, p. 442.
R. Karp, et al., “Randomized Rumor Spreading”, In Proc. Foundations of Computer Science, 2000. pp. 565-574.
David Kempe, et al., “Protocols and Impossibility Results for Gossip-Based Communication Mechanisms”, In Proc. 43rdIEEE Symposium on Foundations of Computer Science, 2002. pp. 471-480.
Ralf Koetter, et al., “An Algebraic Approach to Network Coding”, IEEE/ACM Transactions on Networking, vol. 11, No. 5, Oct. 2003. pp. 782-795.
Kadaba Bharath-Kumar, et al., “Routing to Multiple Destinations in Computer Networks”, IEEE Transactions on Communications, vol. Com-31, No. 3, Mar. 1983, pp. 343-351.
April Rasala Lehman, et al., “Complexity Classification of Network Information Flow Problems”, In Proc. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 9-10.
Muriel Medard, et al., “on Coding for Non-Multicast Networks”, In Proc. 41stAnnual Allerton Conference on Communication, Control and Computing, Oct. 2003, pp. 21-29.
S. Ramanathan, “Multicast Tree Generation in Networks With Asymmetric Links”, IEEE/ACM Transactions on Networking, vol. 4, No. 4, Aug. 1996, pp. 558-568.
Tim Roughgarden, et al., “How Bad Is Selfish Routing?”, Journal of the ACM, vol. 49, No. 2, Mar. 2002, pp. 236-259.
Scott Shenker, et al., “Pricing in Computer Networks: Reshaping the Research Agenda”, Telecommunications Policy, vol. 20, No. 3, 1996, pp. 183-201.
Hanif D. Sherali, et al., “Recovery of Primal Solutions When Using Subgradient Optimization Methods to Solve Lagrangian Duals of Linear Programs”, Operations Research Letters 19 (1996), pp. 105-113.
Luhua Song, et al., “Zero-Error Network Coding for Acyclic Networks”, IEEE Transactions on Information Theory, vol. 49, No. 12, Dec. 2003, pp. 3129-3139.
Shuo-Yen Robert Li, et al, “Linear Network Coding”, IEEE Transactions on Information Theory, vol. 49, No. 2, Feb. 2003, pp. 371-381.
Jeffrey E. Wieselthier, et al., “Energy-Aware Wireless Networking with Directional Antennas: The Case of Session-Based Broadcasting and Multicasting”, IEEE Trans. On Mobile Computing, vol. 1, No. 3, Jul.-Sep. 2002, pp. 176-191.
Jeffrey E. Wieselthier, et al., “Energy-Efficient Broadcast and Multicast Trees in Wireless Networks”, Mobile Networks and Applications 7, 2002, pp. 481-492.
Raymond W. Yeung, “Multilevel Diversity Coding with Distortion”, IEEE Transactions on Information Theory, vol. 41, No. 2, Mar. 1995, pp. 412-422.

Affiliated with

Also associated with

Rating

Minimum-cost routing with network coding does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Minimum-cost routing with network coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum-cost routing with network coding will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4011072