Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-02-02
2002-01-08
Olms, Douglas (Department: 2732)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S341000
Reexamination Certificate
active
06337861
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to communications networking. It is directed particularly to the routing of ICMP messages in tag-switching networks.
Two local area networks, LAN A
10
and LAN B
20
, interconnected through a “backbone” of routers
2
,
4
,
6
,
8
are shown in
FIG. 1. A
router may have a plurality of interfaces to one or more local networks or to other routers. LAN A includes a router
2
and three host devices
14
,
16
,
18
which can communicate directly with each other over LAN A bus
12
, and LAN B includes a router
8
and three host devices
24
,
26
,
28
which can communicate directly with each other over LAN B bus
22
. The exchange of data between a LAN A device, e.g. HOST A
1
14
, and a LAN B device, e.g. HOST B
1
24
, is typically accomplished using an Internet Protocol (IP) datagram. The IP datagram is forwarded in the payload field of link-layer, e.g. Ethernet, communications packets that are exchanged between the backbone routers. The use of an IP datagram allows for the routing of data between network devices that do not have a link-layer connection and, therefore, cannot exchange link-layer packets with each other.
An Ethernet packet
200
having an IP datagram in its payload field
206
is shown in FIG.
2
. The IP datagram is encapsulated between an Ethernet header field
202
and a trailing CRC field
204
. The Ethernet header field
202
includes a type field
203
that specifies that the payload field
206
contains an IP datagram. The IP datagram includes an IP payload field
208
preceded by an IP header field
210
. The IP header field
210
is comprised of a source IP address field
212
(containing IP address “X”), a destination IP address field
214
(containing IP address “Y”), and a protocol field
215
. The source address field
212
identifies the originator of the IP datagram, e.g. HOST A
1
14
, and the destination address field
214
identifies the intended recipient of the IP datagram, e.g. HOST B
1
24
.
A backbone router typically determines the link over which the IP datagram is to be forwarded by referring to a forwarding table, which contains routing information maintained by the router. Using the “Y” address in the destination IP address field
214
, the router performs a longest match search against IP addresses stored in the table. Unfortunately, because the IP address space is so large, the forwarding table may have to very large. More importantly, a longest match search through the forwarding table can be time consuming and result in the expenditure of valuable router processing resources and a slowing of the movement of packets through the network.
A technique known variously as “tag-switching” or “label-switching” is one way of avoiding the longest match searches. Although packets forwarded by a tag-switching router contain a destination IP address, each packet also includes a stack of one or more “tags,” or “labels,” employed for forwarding. Although the invention to be described below is not limited to any particular implementation of tag switching, one popular method for implementing it is called Multi-Protocol Label Switching (MPLS) as described in commonly assigned co-pending U.S. patent application Ser. No. 08/997,343, filed Dec. 23, 1997, by Rekhter et al. for Peer-Model Support for Virtual Private Networks with Potentially Overlapping Addresses, and is hereby incorporated in its entirety by reference. When a tag-switching router receives a tagged packet, it uses the top tag in the tag stack to identify an entry in its forwarding table that specifies the next link of the route to the packet's destination. In addition to the forwarding link, the entry typically includes a replacement tag. The receiving tag-switching router replaces the top tag in the stack with the replacement tag before forwarding the IP datagram over the next link.
FIG. 3
illustrates the exchange of an IP datagram over one type of tag-switching network. The tag-switching network is comprised of a first tag-switching edge router PE
1
interfacing to a first customer edge router CE
1
of a first local network; two tag-switching transit routers P
1
, P
2
connecting the tag-switching edge router PE
1
to a second tag-switching edge router PE
2
; and tag-switching edge router PE
2
interfacing to a second customer edge router CE
2
of a second local network.
We assume that customer router CE
2
sends tag-switching edge router PE
2
a Ethernet packet of the type depicted in the second row of FIG.
1
and without a tag stack of the type now to be described. Edge router PE
2
prepends such a tag stack before it forwards the packet to transit router P
2
. Specifically, an Ethernet packet
400
containing a tagged IP datagram and forwarded from edge router PE
2
to transit router P
2
is shown in FIG.
4
. As described above, the Ethernet packet
400
contains a payload field
406
that is encapsulated between the Ethernet header field
402
and a trailing CRC field
404
. The Ethernet header field
402
includes a type field
403
that specifies that the payload field
406
contains an MPLS protocol data unit, such as a tagged IP datagram. The payload field
406
holds an IP datagram comprised of an IP payload field
408
preceded by an IP header field
410
. The IP header field
410
, shown in detail in the first row, includes a source IP address field
412
(containing IP address “X”), a destination IP address field
414
(containing IP address “Y”), an identification field
416
, and a fragment offset field
418
. In this case, however, the IP payload field
406
is prepended with a tag stack field
420
that contains a top tag stack entry
422
and a bottom tag stack entry
432
. Each tag stack entry
422
,
432
includes a tag field
424
,
434
pointing to an entry in the forwarding table, a “class of service” (COS) field
426
,
436
, an “end-of-stack” (S) field
428
,
438
set to “one” in the bottom tag stack entry
432
, and a “time-to-live” (TTL) field
430
,
440
to be described below. For simplicity, only the destination IP address field
414
(containing IP address “D
1
”) and the IP payload field
408
(containing “DATA”) of the IP datagram are shown in FIG.
3
.
Although the formats described in
FIGS. 2 and 4
are typical formats for packets exchanged between tag-switching routers, they are not the only formats that such routers may employ. The formats employed on some “Ethernet” links are actually somewhat more complicated than the format depicted here. Moreover, routers that communicate with each other over a point-to-point link, i.e., not by way of a shared medium, typically would employ a link-level protocol, such as SLIP or PPP, that is different from the Ethernet protocol just described. An implementation that is particularly desirable for highcapacity links employs Asynchronous Transfer Mode (“ATM”) switches.
An ATM frame
500
having an IP datagram in its payload field
507
is shown in FIG.
5
. The IP datagram field
506
and a tag stack field
520
of the payload field
507
are similar to the IP datagram field
406
and tag stack field
420
encapsulated by the Ethernet header
402
and trailer
404
of FIG.
4
. The only difference is that the top tag field
524
of the top tag stack entry
522
contains question marks, which indicate that the top tag's contents do not matter.
The reason why the top tag's contents do not matter is that the routing decisions, which are based on those contents when the tag-switching router is implemented as a conventional IP router, are instead based on an ATM VPI/VCI field
546
found in the cell header field
544
of an ATM “cell”
540
when the tag-switching router is implemented as an ATM switch. From the point of view of an ATM client, the ATM frame
500
is the basic unit of transmission, and it can vary in length to as much as 64 Kbytes of payload. (Those skilled in the art will recognize that there are also other possible ATM frame formats, but FIG.
5
's third row depicts one, known as “AAL5,” that would typically be em
Cesari and McKenna LLP
Cisco Technology Inc.
Olms Douglas
Vanderpuye Ken
LandOfFree
Method and apparatus to properly route ICMP messages in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus to properly route ICMP messages in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus to properly route ICMP messages in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2851474