Multiplex communications – Pathfinding or routing
Reexamination Certificate
2008-05-20
2008-05-20
Levitan, Dmitry (Department: 2616)
Multiplex communications
Pathfinding or routing
Reexamination Certificate
active
07376121
ABSTRACT:
Disclosed is a routing and bandwidth allocation system that maximizes network throughput while maintaining global fairness in the sharing of network resources. From gathered global network information (such as inter-node communications patterns and network topology), routing tables and bandwidth allocation policies are computed for routers. In some embodiments, the computations involve applying multi-commodity flow methods to provide a “max-fair” allocation of network resources. While in some embodiments each router collects global network information and then locally produces its own routing and bandwidth allocation tables, it can be simpler and cheaper in terms of both computation and security for a centralized, trusted control unit to perform the calculations and then to distribute the results to the routers. The computed bandwidth policies can leave some bandwidth unallocated to handle unexpected surges in demand. The computed routing tables can include multiple paths leading to greater link utilization and to robustness to link failure.
REFERENCES:
patent: 5289462 (1994-02-01), Ahmadi et al.
patent: 5347511 (1994-09-01), Gun
patent: 5359593 (1994-10-01), Derby et al.
patent: 5434848 (1995-07-01), Chimento et al.
patent: 5629928 (1997-05-01), Calvignac et al.
patent: 5790522 (1998-08-01), Fichou et al.
patent: 5815492 (1998-09-01), Berthaud et al.
patent: 5884037 (1999-03-01), Aras et al.
patent: 5936940 (1999-08-01), Marin et al.
patent: 5940372 (1999-08-01), Bertin et al.
patent: 6011776 (2000-01-01), Berthaud et al.
patent: 6011804 (2000-01-01), Bertin et al.
patent: 6262974 (2001-07-01), Chevalier et al.
patent: 6359862 (2002-03-01), Jeffries et al.
patent: 6359863 (2002-03-01), Varma et al.
patent: 6377544 (2002-04-01), Muthukrishnan et al.
patent: 6404735 (2002-06-01), Beshai et al.
Adamic, L. A.: “Zipf, Power-laws, and Pareto—a Ranking Tutorial”, pp. 1-6, retrieved from http://ginger.hpl.hp.com/shl/papers/ranking/ranking.html, May 27, 2003.
Aggarwal et al.: “Node-Disjoint Paths on the Mesh and a New Trade-Off in VLSI Layout”, SIAM J. Comput., vol. 29, No. 4, pp. 1321-1333.
Jain et al.: “A Model and Methodology for Computing Performance Bounds in Multi-hop Wireless Networks”, pp. 1-21.
Banchs, A.: “User Fair Queing: Fair Allocation of Bandwidth for Users”, IEEE Infocom (2002).
Bertsekas et al.: “Data Networks”, pp. 524-529, Prentice Hall (1992).
Blanton et al.: “On Making TCP More Robust to Packet Reordering” (2002).
Cao et al.: “Rainbow Fair Queueing: Fair Bandwidth Sharing Without Per-Flow State”, IEEE Infocom (2000).
Chen et al.: “An Efficient Multipath Forwarding Method”, in Proceedings of IEEE Infocom (1998).
Dovrolis et al.: “A Case for Relative Differentiated Services and the Proportional Differentiation Model” (1999).
Floyd et al.: “Promoting the Use of End-to-End Congestion Control in the Internet”, IEEE/ACM Transactions on Networking, vol. 7, No. 4 (1999), pp. 458-472.
Garg et al.: “Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems”, in IEEE Symposium on Foundations of Computer Science (1998), pp. 300-309.
Goel et al.: “Combining Fairness with Throughput: Online Routing with Multiple Objectives”, in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (2000).
Goldberg et al.: “An Implementation of a Combinatorial Approximation Algorithm for Minimum-Cost Multicommodity Flow”, Lecture notes in Computer Science 1412 (1998), starting on p. 338.
Grotschel et al.: “The Ellipsoid Method and Its Consequences in Combinatorial Optimization”, Combinatorica, vol. 1, No. 2 (1981), pp. 169-197.
Hahne: “Round-Robin Scheduling for Max-Min Fairness in Data Networks”, IEEE Journal of Selected Areas in Communications, vol. 9, No. 7 (1991), pp. 1024-1039.
Kamath et al.: “Simple and Fast Distributed Multicommodity Flow Algorithm”.
Kelly et al.: “Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability”, Journal of Operational Research Society, vol. 49 (1998), pp. 237-252.
Klein et al.: “Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts”, SIAM Journal on Computing, vol. 23, No. 3 (1994), pp. 466-487.
Kleinberg et al.: “Approximations for the Disjoint Paths Problem in High-Diameter Planar Networks”, pp. 26-35.
Kleinberg et al.: “Fairness in Routing and Load Balancing”, in IEEE Symposium on Foundations of Computer Science (1999), pp. 568-578.
Kleinberg et al.: “Disjoint Paths in Densely Embedded Graphs”, in IEEE Symposium on Foundations of Computer Science (1995), pp. 52-61.
Kumar et al.: “Fairness Measures for Resource Allocation”, in IEEE Symposium on Foundations of Computer Science (2000), pp. 75-85.
Leighton et al.: “New Algorithmic Aspects of the Local Lemma with Applications to Routing and Partitioning”, in SODA: ACM-SIAM Symposium on Discrete Algorithms (A Conference on Theoretical and Experimental Analysis of Discrete Algorithms) (1999).
Low et al.: “Optimization Flow Control, I: Basic Algorithm and Convergence”, IEEE/ACM Transactions on Networking, vol. 6 (1999), pp. 861-875.
Marbach: “Priority Service and Max-Min Fairness”, in The Proceedings of IEEE Infocom (2002).
Raghavan et al.: “Randomized Rounding: a Technique for Provably Good Algorithms and Algorithmic Proofs”, Combinatorica, vol. 7, No. 4 (1987).
Shenker: “Making Greed Work in Networks: A Game-Theoretic Analysis of Switch Service Disciplines”, in SIGCOMM Symposium on Communications Architectures and Protocols (Aug. 1994), pp. 47-57.
Schmoys: “Approximation Algorithms for NPHard Problems”, chap. 5, PWS Publishing Company (1997).
Stoica et al.: “Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks”, in ACM SIGCOMM (1998).
Suzuki et al.: “Fast Bandwidth Reservation Scheme with Multi-Link & Multi-Path Routing in ATM Networks”, in Proceedings of IEEE Infocom (1992).
Young: “Sequential and Parallel Algorithms for Mixed Packing and Covering”, in IEEE Symposium on Foundations of Computer Science (2001).
Dunagan John David
Wang Jiahe
Levitan Dmitry
Microsoft Corporation
Wolf Greenfield & Sacks P.C.
LandOfFree
Method and system for global routing and bandwidth sharing does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for global routing and bandwidth sharing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for global routing and bandwidth sharing will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2806078