EP1035751A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Adaptive routing system and method for Qos packet networks
Assignee: Nokia of America Corp
•
Filing: 2000-02-28
•
Granted: —
•
Expires: 2020-02-28
Abstract
Abstract A packet network employs routers that determine network routing based on quality of service (QoS) provisioning parameters and network topology information. QoS provisioning parameters are provided to each router from a network management database, and the network topology information is determined from a link state database of the router. The link state database may include network topology information collected by the router in accordance with the open shortest path protocol (OSPF). A network link, router, or other node failure initiates a new path-selection process. First, a temporary set of provisioning entries may be determined with a shortest path first (SPF) routing method. Then, the network packet flows may be classified into packet flows, real-time and non-real-time, and then as packet flows that require reserved bandwidth or that may be multiplexed. A multicommodity flow (MCF) routing method is then employed to determine an optimized set of candidate provisioning entries for the packet flows that may be multiplexed. The MCF routing method determines new routing for the packet flows based on QoS provisioning commitments as parameters. The MCF routing method determines the new routing based on an optimization criterion, such as maximized revenue. Once the new routing is determined, routing of network traffic is enabled by converting the provisioning entries into filter rules, which are then loaded into the packet classifier of the router.
Inventors
- 👤 Petri Aukia
- 👤 T.V. Lakshman
- 👤 Debasis Mitra
- 👤 G. Ramakrishnan Kajamalai
- 👤 Dimitrios Stiliadis
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-28 02:48
CPC Classifications
H; H04; H04L; H04L47/00; H04L47/10; H04L45/00; H04L45/02; H04L45/04; H04L45/302; H04L47/24; H04L47/2408
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
139 words
A method of routing packets through a router of a packet network
comprising the steps of: a) collecting 1) network topology information and 2) quality of service (QoS)
provisioning information for each packet flow through one or more routers of the
packet network; b) determining a path for each packet flow using a general routing
optimization method based on the QoS provisioning and network topology
information; c) generating a set of one or more filter rules for the router based on the one
or more paths for the one or more packet flows passing through the router, each
filter rule defining a physical path for one or more packet flows through the router;
and d) applying a selected filter rule to each packet of a packet flow to cause each
packet to traverse the corresponding path through the router.
Claim 2
Dependent Claim
66 words
The method as recited in claim 1, wherein the general routing
optimization method is a multicommodity flow (MCF) method, and step a) includes
the steps of: a1) receiving, in accordance with a network protocol, a potion of the
network topology information from each router of the packet network into a
database of the router; and a2) receiving the QoS provisioning information from a network management
database.
Claim 3
Dependent Claim
26 words
The method as recited in claim 2, wherein, for step a1), the network
protocol is at least one of a link-state protocol and a topology-covering protocol.
Claim 4
Dependent Claim
22 words
The method as recited in claim 2, wherein, for step a1), the network
protocol is the open shortest path first (OSPF) protocol.
Claim 5
Dependent Claim
120 words
The method as recited in claim 1, wherein step b) includes the steps
of: b1) computing the effective bandwidth of each packet flow; b2) classifying each packet flow as a multiplexable flow or a non-multiplexable
flow based on a comparison of the corresponding effective bandwidth
with a threshold value; b3) reserving a first portion of an available capacity of the router for the non-multiplexable
flows and a second portion of the available capacity for the
multiplexable flows; b4) determining a set of candidate routes, each candidate route corresponding
to a packet flow, and at least one candidate route allocated to the second portion of
the available capacity ; and b5) calculating the paths based on the set of candidate routes.
Claim 6
Dependent Claim
57 words
The method as recited in claim 5, wherein step b) further includes the
steps of classifying each packet flow as a real-time flow or a non-real-time flow based
on a delay threshold, and calculating a nodal delay for each packet flow based on the
network topology and corresponding classification as a real-time flow or a non-real-time
flow.
Claim 7
Dependent Claim
45 words
The method as recited in claim 6, wherein step b) further includes the
steps of determining one or more candidate routes for the non-multiplexable flows in
accordance with a network routing method; and calculating a corresponding path for
each candidate routes of the non-multiplexable flows.
Claim 8
Dependent Claim
22 words
The method as recited in claim 7, wherein, for step b), the network
routing method is a shortest path first (SPF) method.
Claim 9
Dependent Claim
192 words
The method as recited in claim 6, wherein step b4) determines the set
of candidate routes by the steps of: i) receiving a present value for network revenue and estimates for offered
rates of traffic for the one or more packet flows of each class, the class identifying a
set of QoS commitments of the QoS provisioning information associated with one or
more packet flows assigned to the class; ii)determining route loss probabilities and network sensitivities of each class
based on the nodal delay and effective bandwidth of each corresponding packet flow,
the network topology information, the present value for network revenue, and the
estimates for offered rates of traffic; iii) adjusting the estimates for the offered rates of traffic; iv) forming a new value for network revenue; v) comparing the new and present values for network revenue to determine
whether the new value converges; and vi) if the new value converges, determining the set of candidate routes based
on the new value of network revenue and the estimates for the offered rates of traffic;
otherwise, setting the new value of network revenue as the present value and then
repeating steps ii)-v).
Claim 10
Dependent Claim
56 words
The method as recited in claim 1, wherein step c) includes the steps
of: c1) deleting a set of running filter rules from at least one interface card of the
router; c2) deleting each packet flow identifier and each class currently installed in
each interface card, wherein the packet flow identifier identifies one or more packet
Claim 11
Independent Claim
28 words
An apparatus for routing packets in a packet network
comprising means adapted to carry out each step of a method as
claimed in any of the preceding claims.
Claim 12
Dependent Claim
187 words
A router of a packet network routing packets in accordance with an
internet protocol, the router comprising: a routing processor comprising: an Open Shortest Path First (OSPF) processing module adapted to
receive, in accordance with an OSPF routing protocol, network topology
information from each router of the packet network into a link state database
of the router, a link state database adapted to receive QoS provisioning information
from a network management database into the link state database, and a QoS routing module adapted to determine a path for each packet
flow using a multicommodity flow routing method based on the QoS
provisioning and network topology information; a control processor adapted to generate a set of one or more filter rules for
the router based on the one or more paths for the one or more packet flows passing
through the router, each filter rule defining a physical path for one or more packet
flows through the router; and a packet classifier adapted to apply a selected filter rule to each packet of a
packet flow to cause each packet to traverse the corresponding path through the
router.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.