Non-blocking destination-based routing networks

Details Non-blocking destination-based routing networks Non-blocking destination-based routing networks

2011-03-01

2011-03-01

Ferris, Derrick W (Department: 2463)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C370S252000

Reexamination Certificate

active

07898957

ABSTRACT:
A route computation algorithm, a load-balancing scheme inside a router for making a hop-by-hop routing network (such as the Internet) nonblocking are described in this patent. The output of the route computation algorithm includes a set of link weights that determine the paths of the hop-by-hop routing network. The route computation algorithm and the load-balancing scheme also determine the ingress and egress traffic constraints at each edge router such that as long as the traffic entering and leaving the network does not exceed the constraints, none of the internal links will ever have traversing traffic more than its link capacity. The network is thus non-blocking internally. This greatly simplifies flow admission control and allows hard QoS to be supported inside the network.

REFERENCES:
patent: 4967345 (1990-10-01), Clarke et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 6804199 (2004-10-01), Kelly et al.
patent: 7366108 (2008-04-01), Szentesi et al.
patent: 2002/0103631 (2002-08-01), Feldmann et al.
patent: 2002/0143929 (2002-10-01), Maltz et al.
patent: 2003/0068975 (2003-04-01), Qiao et al.
patent: 2003/0072267 (2003-04-01), Lohtia et al.
patent: 2003/0072327 (2003-04-01), Fodor et al.
patent: 2003/0118024 (2003-06-01), Lee et al.
patent: 2003/0118027 (2003-06-01), Lee et al.
patent: 2003/0161268 (2003-08-01), Larsson et al.
patent: 2003/0174688 (2003-09-01), Ahmed et al.
patent: 2003/0185209 (2003-10-01), Lee
patent: 2003/0198235 (2003-10-01), Weldon et al.
patent: 2003/0202465 (2003-10-01), Cain
patent: 2003/0202468 (2003-10-01), Cain et al.
patent: 2003/0202469 (2003-10-01), Cain
patent: 2003/0202476 (2003-10-01), Billhartz et al.
patent: 2003/0204587 (2003-10-01), Billhartz
patent: 2003/0204616 (2003-10-01), Billhartz et al.
patent: 2003/0204619 (2003-10-01), Bays
patent: 2003/0204623 (2003-10-01), Cain
patent: 2003/0204625 (2003-10-01), Cain
patent: 2003/0227877 (2003-12-01), Kar et al.
patent: 2003/0229613 (2003-12-01), Zargham et al.
patent: 2004/0022203 (2004-02-01), Michelson et al.
patent: 2004/0022223 (2004-02-01), Billhartz
patent: 2004/0022224 (2004-02-01), Billhartz
patent: 2004/0029553 (2004-02-01), Cain
patent: 2004/0037294 (2004-02-01), Yamaguchi et al.
patent: 2004/0042404 (2004-03-01), Ravindran et al.
patent: 2004/0042473 (2004-03-01), Park et al.
patent: 2004/0057724 (2004-03-01), Oksanen et al.
patent: 2004/0067754 (2004-04-01), Gao et al.
patent: 2004/0071089 (2004-04-01), Bauer et al.
patent: 2004/0071468 (2004-04-01), Doh et al.
patent: 2004/0073701 (2004-04-01), Huang et al.
patent: 2004/0081197 (2004-04-01), Liu
patent: 2004/0114569 (2004-06-01), Naden et al.
patent: 2004/0136324 (2004-07-01), Steinberg et al.
patent: 2004/0143842 (2004-07-01), Joshi
patent: 2004/0184483 (2004-09-01), Okamura et al.
patent: 2004/0190526 (2004-09-01), Kumar et al.
patent: 2004/0192204 (2004-09-01), Periyalwar et al.
patent: 2004/0196787 (2004-10-01), Wang et al.
patent: 2004/0196860 (2004-10-01), Gao et al.
patent: 2004/0203820 (2004-10-01), Billhartz
patent: 2004/0213172 (2004-10-01), Myers et al.
patent: 2004/0213198 (2004-10-01), Mahmood et al.
patent: 2004/0213255 (2004-10-01), Brinkerhoff et al.
patent: 2004/0214576 (2004-10-01), Myers et al.
patent: 2004/0215817 (2004-10-01), Qing et al.
patent: 2004/0221154 (2004-11-01), Aggarwal
patent: 2004/0228304 (2004-11-01), Riedel et al.
patent: 2004/0228323 (2004-11-01), Acharya et al.
patent: 2004/0233850 (2004-11-01), Randriamasy et al.
patent: 2004/0233907 (2004-11-01), Hundscheidt
patent: 2004/0246900 (2004-12-01), Zhang et al.
patent: 2004/0246901 (2004-12-01), Zhang et al.
patent: 2004/0264372 (2004-12-01), Huang
patent: 2004/0264466 (2004-12-01), Huang
patent: 2005/0114541 (2005-05-01), Ghetie et al.
patent: 2005/0265258 (2005-12-01), Kodialam et al.
patent: 2007/0115814 (2007-05-01), Gerla et al.
R. Braden et al., “Integrated Services in the Internet Architecture: An Overview,” RCF 1633, Jun. 1994.
R. Callon, “Use of OSI IS-IS for Routing in TCP/IP and Dual Environments,” RFC 1995, Dec. 1990.
Cisco, Configuring OSPF, 1997.
CPLEX, ILOG CPLEX Division, http: www.cplex.com.
B. Fortz at al, “Optimizing OSPF/IS-IS Weights in a Changing World,” IEEE JSAC Special Issue on Advances in Fundamentals of Network Management, Spring 2002.
K. Holmberg et al., “Optimization of Internet Protocol Network Design and Routing,” Networks, 2004, pp. 39-53, vol. 43.
J. Moy, “OSPF Version 2,” RFC 2328, Apr. 1998.
M. Pioro et al., “On OSPF Related Network Optimization Problems,” Performance Evaluation, 2002, pp. 201-223, vol. 248.
A. Sridharan at al., “Achieving Near-Optimal Traffic Engineering Solutions for Current OSPF/IS-IS Networks,” INFOCOM, 2003.
Y. Wang at al., “Internet Traffic Engineering without Full Mesh Overlaying,” INFOCOM, 2001.
C. Zhang et al., “On Optimal Routing with Multiple Traffic Matrices,” IEEE INFOCOM, Mar. 2005.
Johnson et al., “Optimization by Simulated Annealing: An Experimental Evaluation: Part I, Graph Partitioning”, Operations Research , vol. 37, No. 6, Nov.-Dec. 1989.
Johnson et al., “Optimization by Simulated Annealing: An Experimental Evaluation: Part II, Graph Coloring and Number Partitioning”, Operations Research, vol. 39, No. 3, May-Jun. 1991.
Apostolopoulos, et al. QoS Routing Mechanism and OSPF Extensions RCF 2676, Network Working Group, Aug. 1999.
Fortz, et al. Internet Traffic Engineering by Optimizing OSPF Weights. Proc. IEEE INFOCOM, Mar. 2000.
Kodialam, et al. “A Simple Traffic Independent Scheme for Enabling Restoration Oblivious Routing of Resilient Connections,” IEEE INFOCOM, 2004.
Rosen, et al. “Multiprotocol, Label Switching Architecture,” RCF 3031, Network Working Group, Jan. 2001.
Applegate, et al. “Making Intra-Domain Routing Robust to Changing and Uncertain Traffic Demands : Understanding Fundamental Trade-offs,” Proc.ACM, 2003.
Blake, et al. “An Architecture for Differentiated Services,” RFC 2475, Dec. 1998.
Cetinkaya, et al. “Egress Admission Control,” Proc. IEEE INFOCOM, Mar. 2000.
Chu, et al. “Maximizing EF-Class Traffic in DiffServ Networks,” To be published.
Duffield, et al. “A Flexible Model for Resource Management in Virtual Private Networks,” In ACM SIGGCOM, San Diego, California, USA, Aug. 1999.
Erlebach, et al. “Optimal Bandwidth Reservation in Hose-Model VPNs with Multi-Path Routing.” IEEE INFOCOM 2004.
Giordano, et al. “Advanced QoS Provisioning in IP Networks: The European Premium IP Projects,” IEEE Communication Magazine, Jan. 2003.
Gupta, et al. “Provisioning a Virtual Private Network : A Network Design Problem for Multicommodity Flow,” Proc. ACM 2001.
Ivars, et al. “PBAC: Probe-Based Admission Control,” Proc. QoFIS 2001, pp. 97-109.
J. Chu, et al. “Fast Algorithms for Hose-Model VPNs Construction,” to be published.
Leu, et al. “Label Aggregation Technique for LDP,” Internet draft, IETF, Jul. 2000. www.draft-leu-mpls-Idp-label-aggregation-00.txt.
Chu, et al. “Routing and Restoration in Networks with Hose-Model Traffic Patterns,” to be published.
Juttner, et al. “On Bandwidth Efficiency of the Hose Resource Management Model in Virtual Private Networks,” In IEEE INFOCOM, San Francisco, Apr. 2003.
Knightly, et al. “Admission Control for Statistical QoS : Theory and Practice,” IEEE Network, vol. 13, No. 2, Mar. 1999, pp. 20-29.
Kumar, et al. “Algorithms for Provisioning Virtual Private Networks in the Hose Model,” ACM SIGCOMM, Cambridge Massachusetts, USA, Aug. 2001.
Rosen, et al. BGP/MPLSVPNs, memo, Mar. 1999.
Zhang, et al. “Decoupling QoS Control from Core Routers: A Novel Bandwidth Broker Architecture for Scalable Support of Guaranteed Services,” Proc. ACM SIFCOMM Aug./Sep. 2000.
OA mailed Mar. 20, 2009 for U.S. Appl. No. 11/243,117, 20 pages.
OA mailed A

Affiliated with

Also associated with

Rating

Non-blocking destination-based routing networks does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Non-blocking destination-based routing networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Non-blocking destination-based routing networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2688800