EP0753979A1
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Routing method and system for a high speed packet switching network
Assignee: International Business Machines Corp
•
Filing: 1995-07-13
•
Granted: —
•
Expires: 2015-07-13
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. <IMAGE>
Inventors
- 👤 Olivier Bertin
- 👤 Eric Levy-Abegnoli
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-24 15:36
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: 10
Claim 1
Independent Claim
103 words
A method in a packet switching communication network (200) comprising a plurality of (201..208) nodes interconnected with transmission links (209), of determining a route between an origin node and a destination node for the transmission of packets without bandwidth reservation, said method characterized in that it comprises the steps of : • weighing each transmission link with a weighing function w' ij dependent of both reserved and non-reserved traffic, so that : - the more traffic, - the more reserved bandwidth, the higher the weight. • determining the optimal route between the origin and the destination node by selecting links of lowest weight.
Claim 2
Dependent Claim
43 words
The method of determining a route between an origin node and a destination node, according to claim 1, wherein said weighing function is dependent of both reserved and non-reserved traffic, so that the more traffic exceeding the reservable bandwidth, the higher the weight.
Claim 3
Independent Claim
282 words
The method of determining a route between an origin node and a destination node, according anyone of the preceding claims wherein said step of weighing each link in function of both reserved and non-reserved traffic comprises the step of determining a Bounded Total Traffic Weight w BT,ij : • When both C ^ (1) T,ij and C ^ (2) T,ij are below the maximum link reservable bandwidth R ij , the Bounded Total Traffic Weight is equal to : w BT,ij = C ij ( C ij - C ^ T,ij (1) )( C ij - C ^ T,ij (2) ) • Whenever C ^ (1) T,ij or C ^ (2) T,ij exceed the maximum link reservable bandwidth R ij given by R ij = rf × C ij , then C ^ (1) T,ij or C ^ (2) T,ij is replaced by the value R ij . • When both C ^ (1) T,ij and C ^ (2) T,ij exceed the maximum link reservable bandwidth R ij , the Bounded Total Traffic Weight is limited to the maximum value : w max,BT,ij = 1 C ij 1 - rf 2 where : • C ij is the total bandwidth of the link between nodes i and j . • C ^ (1) T,ij is the bandwidth C ^ (1) R,ij reserved on the link between nodes i and j by all the existing reserved connections plus the average bandwidth M (1) NR,ij (bps) used by all the existing non-reserved connections. • C ^ (2) T,ij is equal to the bandwidth already reserved C ^ (1) T,ij plus the average bandwidth m NR,k (bps) requested by the new non-reserved connection k .
Claim 4
Independent Claim
154 words
The method of determining a route between an origin node and a destination node, according to anyone of the preceding claims, wherein said step of weighing each link in function of the reserved bandwidth comprises the step of determining a Reserved Traffic Weight w R,ij according to the expression : w R,ij = C ij ( C ij - C ^ R,ij ) with : • w R,ij = 1 when no bandwidth is reserved ( C ^ R,ij = 0), • w R,ij = w max,R,ij = 1 1 - rf 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 5
Independent Claim
137 words
The method of determining a route between an origin node and a destination node, according to anyone of claims 2 to 4, wherein said step of of weighing each link in function of the traffic exceeding the reservable bandwidth comprises the step of determining an Excess Traffic Weight w E,ij according to the equation : w E,ij = max[1, C ^ T,ij (2) R ij ] where : • C ^ (2) T,ij is equal to the bandwidth C ^ (1) R,ij reserved on the link by all the existing reserved connections plus the average bit rate M (2) NR,ij used by all the existing non-reserved connections and the new estimated non-reserved connection k : M (2) NR,ij = M (1) NR,ij + m NR,k • R ij is the reservable bandwidth of the link
Claim 6
Dependent Claim
58 words
The method of determining a route between an origin node and a destination node, according to claim 5, wherein said weighing function 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 7
Independent Claim
53 words
The method for determining a route between an origin node and a destination node according to anyone of the preceding claims, wherein said step of of selecting links with lowest weight includes the step of minimizing the total weight over the route, or minimizing both hop count and total weight over the route.
Claim 8
Independent Claim
40 words
The method for determining a route between an origin node and a destination node according to anyone of the preceding claims, wherein said step of determining an optimal route between the origin and the destination node utilizes a Bellman-Ford algorithm.
Claim 9
Dependent Claim
112 words
A communication node (300) in a packet switching communication network (200) comprising a plurality of nodes (201..208) interconnected with transmission links (209), comprising means for carrying out the method of determining a route between an origin node and a destination node for the transmission of packets without bandwidth reservation according to anyone of preceding claims, said node (300) comprising one or more communication adapters (307, 304) for receiving or transmitting data packets, a route controller (305) for allocating, controlling and managing network resources, and a topology database (306), updated by means of network control messages, for storing the network configuration and the representation of the traffic load on the transmission links (209).
Claim 10
Dependent Claim
23 words
A packet switching communication network (200) comprising a plurality of transmission links for interconnecting a plurality of nodes (201..208) according to claim 9.
References Cited (Backward Citations)
US5291477A
Cited
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.