Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-08-03
2003-06-24
Kizou, Hassan (Department: 2662)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S238100, C370S397000, C370S399000, C370S252000, C709S241000
Reexamination Certificate
active
06584071
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to packet routing in telecommunication systems, and, more particularly, to determining paths through nodes of a packet network for routing of packets with guaranteed service levels.
2. Description of the Related Art
In interconnected communications packet networks, such as the Internet, users establish connections between a source and a destination with a stream of data packets, called packet flows, that are transferred through the network over a network path. The network path is defined by a set of nodes interconnected by a set of links. Packet networks may have a hierarchical structure in which smaller networks are interconnected by larger networks, and a peer structure in which equivalent networks are interconnected. At the highest levels, packet networks with high capacity that route packets transferred between other, outside packet networks are commonly referred to as “backbone” networks. A packet network connects to one or more other packet networks through ingress and egress points (routers) of the backbone network.
FIG. 1
shows a backbone network
100
of the prior art having nodes N
1
-N
9
interconnected through links
101
that allow communication between packet networks
102
-
104
. An ingress point is a router of node N
1
that transfers packets to the backbone network
100
from a source (packet network
102
), and an egress point is a router of node N
4
that transfers packets from the backbone network
100
to a destination (packet network
104
). The backbone network
100
may support an interior routing protocol to distribute network topology information and route packets between ingress and egress points based on best effort routing (e.g., destination-based shortest path) through the nodes N
1
-N
9
. A centralized network management system
105
may be employed to 1) provision virtual circuits, or packet flows, through the backbone network
100
; 2) monitor capacity and utilization of links
101
; and 3) coordinate calculation and installation of provisioned paths. Forwarding tables are used by each node's router to forward each received packet to the next node toward its destination. In addition, the centralized network management system
105
may also be employed to collect and distribute network topology information.
Interior routing protocols are employed by routers to determine forwarding of packets between a source and destination pair along a path through the nodes of the interconnected packet network. Packets received by a node's router are forwarded to other nodes based on a forwarding table constructed in accordance with the interior routing protocol or routes installed with explicit route provisioning. Interior routing protocols may also specify exchange network topology and link-state information (“network topology information”) among routers to allow the node's router to construct the corresponding forwarding table. An example of a widely-used interior routing protocol for “best effort” routing is the Open Shortest Path First (OSPF) protocol. In addition, some routing protocols associate a link “cost” with each link between nodes. This link cost may be associated with, for example, average link utilization or revenue generated by the link, as well as link importance in the network. When link-state information or link-bandwidth (e.g., connectivity or available bandwidth) is exchanged between routers, each router in the network has a complete description of the network's topology.
Since routing of packets at the higher levels is desirably performed at high speed, each higher-level packet network may use its own interior routing protocol in addition to the interior routing protocol of the lower-level packet network. Routing protocols, in addition to providing connectivity, may also enable traffic management. The Multi-Protocol Label Switched (MPLS) standard, for example, allows such routing protocols in backbone networks. The MPLS standard may be employed for networks having virtual circuits (packet flows) with provisioned service levels (also known as guaranteed quality-of-service (QoS)).
Provisioned service levels may be, for example, a guaranteed minimum bandwidth for the path of a packet flow through the backbone network. This path having a guaranteed level of service between ingress and egress points may be referred to as a Network Tunnel Path (NTP). As would be apparent to one skilled in the art, specific implementations of NTPs exist for different types of networks. As examples of NTPs, virtual circuits may be established for packet flows in TCP/IP networks, virtual circuits may be established for cells in Asynchronous Transfer Mode (ATM) networks, and label switched paths (LSPs) may be established for packets in MPLS networks. Packets of a signaling protocol, such as RSVP (Reservation Protocol for IP and MPLS networks) or LDP (Label Distribution Protocol for MPLS networks), may be used to reserve link bandwidth and establish an NTP, once routing for the NTP is calculated. NTPs may be provisioned as an explicit route along specific paths between nodes of the backbone network (i.e., when an NTP is provisioned, all intermediate points may be specified through which a packet passes between the ingress and egress points of the NTP).
In MPLS networks, packets are encapsulated by appending to the packet, or forming from the packet, additional information when the packet is received at an ingress point. The additional information, called a label, is used by routers of the backbone network to forward the packets.
FIG. 2
shows such an encapsulated packet
200
having a label
201
appended to packet
202
. The label summarizes information in the packet header. The summary may be based on the header field and include an origination (source) address field (o)
210
identifying the address of the ingress point, a termination (destination) address field (t)
211
identifying the address of the egress point(s). In some cases, the label may simply be a pointer that identifies or is otherwise related to specific origination and termination address fields in the header of the received packet. The label also includes one or more service level fields (bd)
212
. Service level field
212
may identify a desired service level for the virtual circuit (called a “demand”), such as minimum bandwidth required. In some networks, the service level field is implied from the label itself. Other fields
213
may be included in the label
201
, such as MPLS standard version, interior routing protocol version, maximum delay, or other types of service level parameters. The label
201
may alternatively be inserted into the packet header (PH)
214
of the packet
202
, so the order of fields shown in
FIG. 2
is exemplary only. Backbone networks may employ labels to group encapsulated packets having similar LSPs into classes (equivalence classes), and methods for forwarding equivalence classes may be employed to simplify calculation of routing for LSPs.
To generate a forwarding table, each router computes a set of preferred paths through the network nodes, and may use the weights to calculate the set of preferred paths. Each preferred path has a minimum total weight between nodes as well as minimum summed weight through nodes of the path, which is known in the art as shortest-path routing. This set of preferred paths may be defined with a shortest-path tree (SPT). The forwarding table with routing information (e.g., source-destination pair, source ports, and destination ports) is generated from the SPT. The router uses the routing information to forward a received packet to its destination along the shortest path of the SPT. The SPT may be calculated using an algorithm such as Dijkstra's algorithm, described in E. Dijkstra, “A Note: Two Problems In Connection With Graphs,” Numerical Mathematics, vol.1, 1959, pp. 269-271.
A common shortest-path routing algorithm employed by routers to generate routing of an LSP is the min-hop algorithm. In the min-hop algorithm, eac
Kodialam Muralidharan S.
Lakshman T. V.
Kizou Hassan
Lucent Technologies - Inc.
Waxman John M.
LandOfFree
Routing with service level guarantees between ingress-egress... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Routing with service level guarantees between ingress-egress..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing with service level guarantees between ingress-egress... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3139278