US5940372A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for selecting path according to reserved and not reserved connections in a high speed packet switching network
Assignee: Cisco Technology Inc
•
Filing: 1996-07-12
•
Granted: 1999-08-17
•
Expires: 2016-07-12
Abstract
Abstract The present invention is related to high speed packet switching networks and, more particularly, to a process for selecting an optimal path for packets transmission without bandwidth reservation in communication systems supporting both bandwidth-reserved and non-bandwidth-reserved connections. Non-reserved network connections do not have bandwidth set aside either implicitly or explicitly. The lowest delay priority is assigned to non-reserved traffic and the networks drops non-reserved packets when their buffer overflow at intermediate links. Because the data profile over the connections is bursty and non deterministic, reserved traffic does not lead to a full links utilization except on peaks. Therefore, non-reserved traffic can be transmitted when some bandwidth is available on the links. The purpose of an efficient bandwidth management is to reserve on the links as many bandwidth as possible with a guaranteed quality of service, and to use the inherent remaining bandwidth to transport traffic from the users who are just expecting a "best effort" service. The Path Selection algorithm for non-reserved connections comprises the step of weighing each transmission link with a weighing function dependent of both reserved non-reserved traffic.
Inventors
- 👤 Olivier Bertin
- 👤 Eric Levy-Abegnoli
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 04:21
CPC Classifications
H; H04; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L; H04L45/00; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5619
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
146 words
For use in a packet switching communication network comprising a plurality of nodes interconnected with transmission links, said network carrying both reserved data traffic on connections to which network resources have been allocated and non-reserved data traffic on connections to which no network resources are allocated, a method of determining a route for non-reserved data traffic between an origin node and a destination node, said method comprising the steps of: assigning a weight to each transmission link, said weight being directly related to both the existing allocation of resources on the link for reserved data traffic connections and the existing, actual utilization of the link for carrying both reserved and non-reserved data traffic; and selecting an optimal path by determining the combined weights of feasible paths between the origin node and the destination node and selecting the least weight path from the set of feasible paths.
Claim 2
Dependent Claim
146 words
For use in a packet switching communication network comprising a plurality of nodes interconnected with transmission links, said network carrying both reserved data traffic on connections to which network resources have been allocated and non-reserved data traffic on connections to which no network resources are allocated, a method of determining a route for non-reserved data traffic between an origin node and a destination node, said method comprising the steps of: assigning a weight to each transmission link, said weight being directly related to both the existing allocation of resources on the link for reserved data traffic connections and the existing, actual utilization of the link for carrying both reserved and non-reserved data traffic; and selecting an optimal path by determining the combined weights of feasible paths between the origin node and the destination node and selecting the least weight path from the set of feasible paths.
Claim 3
Dependent Claim
46 words
The method of determining a route between an origin node and a destination node, according to claim 1, wherein said step of assigning a weight is dependent of both reserved and non-reserved traffic, so that the more traffic exceeding the reservable bandwidth, the higher the weight.
Claim 4
Dependent Claim
217 words
The method of determining a route between an origin node and a destination node, according to claim 2 by assigning a weight to each transmission link comprises the step of determining a Bounded Total Traffic Weight w BT ,ij : When both C T ,ij.sup.(1) and C T ,ij.sup.(2) are below the maximum link reservable bandwidth R ij , the Bounded Total Traffic Weight is equal to: ##EQU10## Whenever C T ,ij.sup.(1) or C T ,ij.sup.(2) exceed the maximum link reservable bandwidth R ij given by R ij =rfx then C T ,ij.sup.(1) or C T ,ij.sup.(2) is replaced by the value R ij ; When both C T ,ij.sup.(1) and C T ,ij.sup.(2) exceed the maximum link reservable bandwidth R ij , the Bounded Total Traffic Weight is limited to the maximum value: ##EQU11## where: C ij is the total bandwidth of the link between nodes i and j; C T ,ij.sup.(1) is the bandwidth C R ,ij.sup.(1) reserved on the link between nodes i and j by all the existing reserved connections plus the average bandwidth M NR ,ij.sup.(1) (bps) used by all the existing non-reserved connections; C T ,ij.sup.(2) is equal to the bandwidth already reserved C T ,ij.sup.(1) plus the average bandwidth m NR ,k (bps) requested by the new non-reserved connection k.
Claim 5
Dependent Claim
113 words
The method of determining a route between an origin node and a destination node according to claim 3 wherein the step of assigning a weight comprises the step of determining a Reserved Traffic Weight w R ,ij according to the expression: ##EQU12## with: w R ,ij =1 when no bandwidth is reserved (C R ,ij =0), ##EQU13## when all reservable bandwidth is reserved (C R ,ij =R ij ); where: C ij is the total bandwidth of the link between nodes i and j; C R ,ij is the bandwidth reserved on the link between nodes i and j by all the existing reserved connections with a maximum value of R ij .
Claim 6
Dependent Claim
110 words
The method of determining a route between an origin node and a destination node, according to claim 4, wherein said step of assigning a weight each link as a function of the traffic exceeding the reservable bandwidth comprises the step of determining an Excess Traffic Weight w E ,ij according to the equation: ##EQU14## where: C T ,ij.sup.(2) is equal to the bandwidth C R ,ij.sup.(1) reserved on the link by all the existing reserved connections plus the average bit rate M NR ,ij.sup.(2) used by all the existing non-reserved connections and the new estimated non-reserved connection k: M.sub.NR,ij.sup.(2) =M.sub.NR,ij.sup.(1) +m.sub.NR,k R ij is the reservable bandwidth of the link.
Claim 7
Dependent Claim
53 words
The method of determining a route between an origin node and a destination node, according to claim 5, wherein assigned weight w' ij is the result of the product of: the Bounded Total Traffic Weight w BT ,ij, the Excess Traffic Weight w E ,ij, and the Reserved Traffic Weight w R ,ij.
Claim 8
Dependent Claim
48 words
The method for determining a route between an origin node and a destination node according to claim 6, wherein said step of selecting an optimal path includes the step of minimizing the total weight over the route, or minimizing both hop count and total weight over the route.
References Cited (Backward Citations)
US5031093A
Cited
US5067127A
Cited
US5253248A
Cited
US5233604A
Cited
US5381404A
Cited
US5347511A
Cited
US5600638A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-16 | 2003-02-15 | 2003-08-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-16 | 2007-02-15 | 2007-08-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-16 | 2011-02-15 | 2011-08-17 | $7700.00 | Window Closed / Lapsed |