Hierarchical label switching across multiple OSPF areas

Details Hierarchical label switching across multiple OSPF areas Hierarchical label switching across multiple OSPF areas

1999-03-29

2002-10-29

Vanderpuye, Ken (Department: 2661)

Multiplex communications

Pathfinding or routing

C370S399000

Reexamination Certificate

active

06473421

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention is directed to communications networking and in particular to networks that employ label switching.
Internetwork communications are based on operations of routers, which are network devices that determine, on the basis of destination information in packets that they receive, where to forward the packets so that they are likely to reach the intended destinations.
Router configurations vary widely, but
FIG. 1
depicts a typical approach. Router
10
includes a plurality of communications interfaces
12
,
14
, and
16
, which send and receive communications packets to and from remote locations. When one of the interface modules receives an incoming packet, it places header information from that packet onto an internal communications bus
18
by which it communicates with a forwarding engine
20
, typically a high-performance processor configured by instructions in associated storage circuitry, that determines where the packet should be sent. Once the decision has been made, an output packet is formed from the input packet by packet-assembly circuitry that may reside in one or more of the interface modules and the forwarding engine, and the forwarding engine operates another interface to cause it to send the output packet to a further remote location.
FIG. 2
depicts the router
10
in a local-network environment in which it communicates through one of its interfaces to such remote locations by way of a local-areanetwork bus
22
. In a link of that nature, there are typically a number of network devices, such as network devices
24
,
26
,
28
, and
30
, that receive the resultant packet-bearing signals, but the packet is not usually intended for all of them. Different systems employ different packet formats to enable their various network devices to distinguish the packets they should read from the ones they should not, but the Ethernet packet format of
FIG. 3
is typical.
In that drawing, each packet begins with a link-layer header
32
. The link-layer header includes, among other fields, a field that contains a link-layer destination address. If the destination address does not match the address of a network-device interface that receives the packet, that network device ignores the packet.
For present purposes, we will assume that router
10
intends the packet to be received by a further router
30
, so the link-layer header's destination-address field will contain the link-layer address of router
30
's interface with network link
22
. That interface accordingly reads the remainder of the packet, verifying that the contents of a cyclicredundancy-code trailer
34
are consistent with the remainder of the packet. It then proceeds to process the link-layer packet's payload
36
in accordance with a protocol that the link-layer header's type field specifies.
In the present case, the type field specifies that the link-layer packet's payload is an Internet Protocol (“IP”) datagram, which is a network-layer protocol data unit. The purpose of the router's IP process is to determine how to forward the datagram to its ultimate (internetwork-host) destination. To make this determination, the IP process inspects the IP datagram's header
38
, and in particular its IP destination-address field. That field's contents identify the host system to which the datagram's contents are to be directed, and router
30
uses this address to determine through which of its interfaces to forward the packet on to that host system.
The router makes this determination by using a forwarding table, into which it has distilled information about internetwork topology that it has typically obtained by communications with other routers. Routers inform other routers of the host systems to which they can forward communications packets, and they employ such information obtained from other routers to populate their forwarding tables.
Now, the IP address is 32 bits long in most versions and even longer in versions that will soon be adopted, so the IP address could theoretically distinguish among over four billion host systems. Actually, the number of host systems that have globally unique IP addresses is much smaller that this, but the number still is much greater than it is practical for an individual router to have route entries for in its forwarding table.
The solution to this problem historically has been to base the table look-up on destination-address prefixes. That is, some routers will simply indicate that they can handle traffic to all hosts whose destination addresses begin with a particular, say, 16-bit sequence, or “prefix.” Additionally, a router may compact its information so as to store routes in this form. Prefixes vary in length, the longest being the most specific and thus presumably representing the best routes to the included host addresses. So when a router receives an IP datagram, it searches through the prefix entries in the forwarding table to find the longest prefix that matches the incoming packet's destination address. When it finds that route in its forwarding table, it reads that route's fields that specify the interface over which it should forward the packet and the link-layer address of the router to which the interface should send the packet for further forwarding.
Although this approach has proved quite serviceable and robust, it has exhibited shortcomings that have led some workers to propose a table-index-based forwarding approach for high-speed networks such as those of some Internet-service providers (“ISPs”) . Specifically, routers would inform their neighbor routers of the locations within their tables at which the routes to particular prefixes are located. When their neighbors send them packets destined for those prefixes, those neighbors insert a “shim” between the link-layer header (such as an Ethernet header) and the network-layer header (typically, an IP header). This shim's contents include a label (also referred to as a “tag”) that is an index to the desired route in the receiving router's forwarding table.
One of this approach's advantages is that it relieves the receiving router of the need to perform an expensive longest-match search: the label points the receiving router directly to the correct forwarding-table entry. Commonly assigned co-pending U.S. patent application Ser. No. 08/997,343, filed on Dec. 23, 1997 now U.S. Pat. No. 6,339,995, by Rekhter et al. for Peer-Model Support for Virtual Private Networks with Potentially Overlapping Addresses, describes in detail one proposal, known as Multiple-Protocol Label Switching (“MPLS”), for employing such shims. That application also includes an exemplary protocol, referred to as the Tag Distribution Protocol (“TDP”) by which routers inform their neighbors of the labels that they associate with their forwarding-table entries. I hereby incorporate that application in its entirety by reference.
FIG. 4
depicts the resultant packet format. The link-layer header has the same format as in
FIG. 3
, but its type field identifies the link-layer payload as beginning not with an IP header but rather with an MPLS header, or “shim” between the link-layer header and the network-layer header.
FIG. 4
illustrates the MPLS header's format. The MPLS header is organized as a stack of entries, and
FIG. 4
gives an example in which there are two entries
40
and
42
. In addition to other information, each entry includes a label, which is an index into the forwarding table of the label-switching router that receives it. When a router receives such a packet, it consults the forwarding-table entry that the label specifies and replaces that label with a replacement label that the specified forwarding-table entry contains. That replacement label is typically one that the next router on the path to the requested destination has asked to be included in packets sent to it and intended for the destination with which the forwarding table is associated. For reasons that will become apparent below, the MPLS header may

Affiliated with

Also associated with

Rating

Hierarchical label switching across multiple OSPF areas does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hierarchical label switching across multiple OSPF areas, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hierarchical label switching across multiple OSPF areas will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2938541