Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-09-29
2004-08-17
Nguyen, Brian (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S432000, C370S256000
Reexamination Certificate
active
06778531
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to routing packets in a telecommunications network, and, more particularly, to determining paths through nodes of the network for multicast routing of packets having guaranteed service levels.
2. Description of the Related Art
In interconnected packet networks, such as the Internet, users establish a connection between a source and a destination with a stream of data packets (called a “packet flow” or “flow”) 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. A packet network connects to one or more other packet networks through ingress and egress points (routers) of the network.
FIG. 1
shows a network
100
of the prior art having nodes N
1
-N
9
interconnected through links
101
that allow communication between packet networks
102
-
104
. A router of node N
1
that transfers packets to the network
100
from a source (packet network
102
) is an example of an ingress point, and a router of node N
4
that transfers packets from the network
100
to a destination (packet network
104
) is an example of an egress point. The 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 routing) 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 network
100
; 2) monitor capacity and utilization of links
101
; and 3) coordinate calculation and installation of provisioned paths as router forwarding tables. Forwarding tables are used by each node's router to forward each received packet to the next node in the path and toward its destination. In addition, the centralized network management system
105
may collect and distribute network topology information.
Interior routing protocols are employed by network routers to determine a path through the nodes of the network along which packets between a source (ingress) and destination (egress) pair are forwarded. 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, but may also be through routes installed with explicit route provisioning. Interior routing protocols may also specify network topology and link-state information (“network topology information”) that is exchanged between the network nodes. Network topology information allows 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 (i.e., how critical the link is to packet routing). 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.
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 networks. The MPLS standard may be employed for networks having virtual circuits (packet flows) or label switched paths (LSPs) 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 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) with traffic engineering extensions or CR-LDP (Constrained Routing Label Distribution Protocol for MPLS networks), may be used to reserve link bandwidth and establish an NTP. NTPs may be provisioned as an explicit route along specific paths between nodes of the 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, sometimes referred to as label, is then employed by routers of the network to forward the corresponding packet. 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.
FIG. 2
shows such an encapsulated packet
200
having a label
201
appended to packet
202
. The label summarizes information in the packet header
214
of the original packet
202
. The summary may be based on the header field and includes a source address field (s)
210
identifying the address of the ingress point, a destination address field (r)
211
identifying the addresses of the egress point(s). For multicast packets, the destination address field
211
may represent a set R
s
of receiver addresses r
I
through r
K
, each of which corresponds to a destination receiving the multicast connection's packets. To distinguish between destinations of a unicast connection (single source and single destination) and those of a multicast connection (single source and multiple destinations), each destination of the multicast connection may be referred to as a “receiver,” though operations of a destination and a receiver are generally equivalent.
Label
201
also includes one or more service-level fields
212
. Each service-level field
212
may identify a desired service level for the virtual circuit (called a “demand”). In some networks, the values for the service-level fields, such as minimum bandwidth (b), may be implied or derived from the label itself. Other fields
213
may be included in label
201
, such as MPLS standard version, interior routing protocol version, maximum delay, or other types of service-level parameters. Label
201
may alternatively be inserted into the packet header (PH)
214
of the packet
202
, so the representation of fields shown in
FIG. 2
is exemplary only. 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 NTP routing through the network.
To generate a forwarding table, each router computes a set of preferred paths through the network nodes, and may use 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 shorte
Kodialam Muralidharan S.
Lakshman Tirnuell V.
Sengupta Sudipta
Lucent Technologies - Inc.
Nguyen Brian
LandOfFree
Multicast routing with service-level guarantees between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicast routing with service-level guarantees between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicast routing with service-level guarantees between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3296301