Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-09-08
2001-09-25
Kizou, Hassan (Department: 2738)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S349000, C370S355000, C370S389000, C370S393000, C370S470000, C370S471000, C370S474000, C370S475000
Reexamination Certificate
active
06295296
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 and 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 with a local-area-network bus
22
. There are typically a number of network devices, such as network devices
24
,
26
28
, and
30
, that receive the resultant 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
24
, so the link-layer header's destination-address field will contain the link-layer address of router
24
's interface with network like
22
. That inter-face accordingly reads the remainder of the packet, verifying that the contents of a cyclic-redundancy-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 filed specifies.
In the present case, the type filed specifies that the link-layer packet's payload is an Internet Protocol (“IP”) datagram, 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 (inter-network-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
24
uses this address to determine through which of its interfaces to forward the packet on toward its ultimate destination.
The router makes this determination by using a forwarding table, into which it has distilled information about internetwork topology that it has obtained in various ways, but typically 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 that 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, they 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 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 and expensive longest-match search: the label directs the receiving router directly to the correct forwarding-table entry. More important, it affords ISPs the opportunity to have their ingress routers (which receive packets from outside the service-provider network) specify the egress routers from which received packets should issue from the network. This frees the ISP's interior (“transit”) routers of the task of participating in forwarding policy and maintaining the associated information bases. Commonly assigned co-pending U.S. patent application Ser. No. 08/997,343, filed on Dec. 23, 1997 by Rekhter et al, for Peer-Model Support for Virtual Private Networks with Potentially Overlapping Address, describes in detail one proposal, known as Multiple-Protocol Label Switching (“MPLS”), for employing such shims. I hereby incorporate that application in its entirety by reference.
FIGS. 4 and 5
illustrate how such an operation can be performed. A customer router CE
2
forwards a packet to an ingress router PE
2
in an ISP network. The link-layer packet's payload consists of a datagram, including the datagram's payload data and a header that gives the destination's address as D
1
. The ISP needs to perform its routing rapidly, and so it employs the label switching just described.
Router PE
2
is an “edge” router: it has direct links with routers outside the service-provider network. The ISP's edge routers maintain communications with other edge routers, such as edge router PE
1
, to tell them the address prefixes of hosts outside the provider network to which they can forward packets. Because of this communication, router PE
2
has in its forwarding database an indication that packets having a prefix that matches address D
1
should be sent to PE
1
for forwarding outside the service-provider network. When router PE
2
receives the D
1
-destined packet from customer router CE
2
, it finds this information in its database through a conventi
Cesari and McKenna LLP
Cisco Technology Inc.
Kizou Hassan
Tran Thien D
LandOfFree
Use of a single data structure for label forwarding and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Use of a single data structure for label forwarding and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Use of a single data structure for label forwarding and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2506618