Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-02-26
2003-01-28
Chin, Wellington (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S235000
Reexamination Certificate
active
06512768
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to communications networking. It is directed particularly to a tag distribution protocol employed on a tag-switching network.
Internetworking, Routers and the Internet Protocol
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 the 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 the LAN B bus
22
. Two directly connected, or linked, devices communicate through the exchange of link-layer, e.g., Ethernet, communications packets.
The exchange of data between two indirectly connected devices, e.g., HOST A
1
14
of LAN A and HOST B
1
24
of LAN B, is typically accomplished at the network layer using an Internet Protocol (IP) datagram. The IP datagram is typically forwarded in the payload field of link-layer 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
includes a source IP address field
212
(containing IP address “X”) and a destination IP address field
214
(containing IP address “Y”). 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
.
Routers commonly employ some type of discovery mechanism to automatically identify and maintain links to other routers and thereby avoid the need for explicit network configuration. Under a discovery mechanism, a router periodically broadcasts from each interface a special type of link-layer packet, typically referred to as a Hello packet, to inform other routers of its presence in the network. The router “discovers” a link to another router when a Hello packet is received at one of its interfaces. To verify the ongoing operation of a particular link, the router establishes a hello hold timer associated with the linked router and resets the timer each time a subsequent Hello packet is received at the interface from the linked router. If the router fails to receive a subsequent Hello packet before the timer expires, it assumes that the link is no longer available. The failure to receive a new Hello packet may be due to a poor link connection between the two routers, or the linked router may have failed or perhaps decided for some reason to disable that particular interface.
A conventional 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 learned from neighbor routers and 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 be 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 Tag-Switching Network
A technique known variously as “tag-switching” or “label-switching” is one way of avoiding the longest match searches. 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) and is described in the above-cited Rekhter et al. application.
An Ethernet packet
300
carrying a tagged IP datagram in its payload field
306
is shown in FIG.
3
. The type field
305
of the Ethernet packet is used to identify the payload contents as a tagged datagram and thus distinguish it from a normal IP datagram. A tag stack field
320
is prepended to the IP payload field
306
and is comprised of one or more “tags,” or “labels,” employed for forwarding. In this case, the tag stack field
320
contains a single tag stack entry
322
. A tag-switching router uses the contents of the tag field
324
in place of the destination address
303
to determine the forwarding route of the packet.
FIG. 4
illustrates the exchange of an IP datagram over one type of tag-switching is network. For simplicity, only the destination IP address field
314
(containing IP address “D1”) and the IP payload field
308
(containing “DATA”) of the IP datagram are shown in FIG.
4
. The tag-switching network is comprised of a first tag-switching edge router TE
1
interfacing to a first router R
1
of a first local network; two tag-switching transit routers T
1
, T
2
connecting the tag-switching edge router TE
1
to a second tag-switching edge router TE
2
; and tag-switching edge router TE
2
interfacing to a second router R
2
of a second local network.
We assume that router R
2
sends tag-switching edge router TE
2
an IP datagram within an Ethernet packet of the type depicted in the second row of FIG.
2
. When tag-switching edge router TE
2
receives the IP datagram from router R
2
, it prefixes a tag T
1
that identifies an entry in the forwarding table of the next router, i.e., the first transit router TR
2
, in the backbone path. When the transit router TR
2
receives the IP datagram, it uses the tag T
1
to identify the location in its forwarding table that specifies the forwarding link to the edge router TE
1
; i.e., the transit router TR
2
does not have to perform a time-consuming longest-match search. It then replaces the tag T
1
with the replacement tag T
2
that identifies an entry in the forwarding table of the second transit router TR
1
in the backbone path and forwards the IP datagram. (We assume that, as in the typical case, there are several transit routers in the backbone path, although in some configurations there may be none. All transit routers, except the last transit router in the backbone path, perform in a manner similar to that of transit router TR
2
.) When the second transit router TR
1
, which is also the last transit router in the backbone path, receives the IP datagram, it uses tag T
2
to identify an entry in its forwarding table specifying the forwarding link, removes tag T
2
, and then forwards the untagged IP datagram. When the edge router TE
1
receives the IP datagram, it forwards the data packet to R
1
in the conventional manner.
The ATM Protocol
Although the tag-over-Ethernet protocol illustrated in
FIG. 3
is typical for packets exchanged between tag-switching routers, it is not the only protocol that such routers may employ. The protocols employed on some links types are actually somewhat more complicated than the protocol depicted in FIG.
3
. 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-layer protocol, such as SLIP or PPP, that is different from the Ethernet protocol just described. An implementation that is particularly desirable for high-capacity 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 p
Cesari and McKenna LLP
Chin Wellington
Cisco Technology Inc.
Pham Brenda
LandOfFree
Discovery and tag space identifiers in a tag distribution... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Discovery and tag space identifiers in a tag distribution..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Discovery and tag space identifiers in a tag distribution... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3042612