Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
1999-06-25
2003-01-28
Rao, Seema S. (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S236100, C370S397000, C370S401000, C370S429000
Reexamination Certificate
active
06512744
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention is directed to communications networks. It particularly concerns congestion avoidance.
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 that of
FIG. 1
is typical. 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 from a remote location, it places header information from that packet onto an internal communications bus
18
by which it communicates with a forwarding engine
20
that determines where the packet should be sent. The interfaces and forwarding engine can be implemented in respective high-performance processors
21
and storage circuitry
22
that contains program instructions that configure the processors to act together as a router. The programming for such implementations is typically provided in some type of persistent medium, such as a magnetic disk or semiconductor read-only memory. That type of implementation most often executes that programming after it has been transferred to a volatile medium, such as dynamic or static random-access memory. The drawing shows the storage circuitry
22
as separate media for each interface or forwarding engine, but some configurations may additionally, or instead, employ common storage. In some cases the router's programming may be updated remotely by sending it electrical or other signals that represent the instructions.
To maximize speed capacity, other routers are implemented wholly or largely in “random logic” instead of general-purpose processors. The “programming” in such implementations is ordinarily hard-coded in the circuitry's structure, but read-only or read/write storage media may be employed in such implementations, too, to affect the router's behavior. 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/or the forwarding engine, and the forwarding engine causes another interface to send the output packet to a further remote location.
Some routers may actually be implemented in switches that employ the Asynchronous Transfer Mode (ATM) protocol. Such switches operate in the manner that
FIG. 2
depicts. Suppose that one of router
10
's ATM interfaces provides communication with another router
24
, while a different ATM interface provides communication with a further router
26
. Suppose further that router
10
is an “edge router” of an internet-service provider: although it is part of a network that is maintained by the service provider, it has direct links to client routers such as router
26
, which are outside the service-provider network.
Router
26
sends information in packets to router
10
, and we will assume for present purposes that the packets sent by router
26
conform to the Internet Protocol (IP). In accordance with that protocol, each packet begins with a header that includes, among other information, an address that indicates the host system to which the packet should ultimately be routed. Router
10
includes storage circuitry containing a routing table that tells the router the direction in which to send the packet so that it will reach the destination set forth in the IP header.
Now, the service provider must of necessity base its initial routing decision on the incoming packet's destination address. But IP addressing makes doing so in the conventional manner a relatively time-consuming process. An IP address is typically 32 bits long: it could theoretically distinguish over four billion host systems. Although the number of host systems that have globally unique IP addresses is much smaller than this, the actual number of such systems is considerably greater than the number of entries it is practical for an individual router's forwarding table to include.
Many of the forwarding table's entries therefore are directed not to a single host address but rather to a “prefix” of fewer than the thirty-two bits. Such an entry indicates that the forwarding information contained in it can be used to reach any destination address that begins with the prefix to which the entry is directed. Prefixes vary in length, the longest being the most specific and thus presumably representing the best routes to the included host addresses. So a router that receives an IP packet searches through its forwarding table to find the longest prefix that matches the incoming packet's destination address, and it forwards the packet in accordance with the information thus found.
Such longest-match searches are time-consuming. But an Internet-service provider's “transit” routers, i.e., those that are not edge routers, can avoid such an expensive longest-match search if they forward the packets in ATM “cells.” An ATM cell includes a “virtual-channel identifier,” which identifies the receiving router's forwarding-table entry that contains the forwarding information for the “virtual channel” along which the cell is to be forwarded. For this purpose, an edge router such as router
10
works with other routers to set up a virtual channel within the service-provider network before it forwards the first packet to a particular destination. That is, successive routers determine the path through the network that such packets should take, and they tell each other where in their respective forwarding tables they keep forwarding information for that virtual circuit.
FIG. 3
depicts the format that ATM switches use to send information over the resultant virtual channel. From the point of view of an ATM client, the frame that FIG.
3
's third row depicts is the basic transmission unit. (Those skilled in the art will recognize that there are also other possible ATM frame formats, but FIG.
6
's third row depicts one, known as “AAL5,” that would typically be employed for user data.) Since the service-provider network is being used to forward IP datagrams from router
26
, that drawing's fourth row depicts the frame's payload as an IP datagram having the usual IP header and IP data.
From the point of view of such an ATM switch, though, the (variable-length) third-row frame is not the basic transmission unit. Specifically, the edge router divides that frame into pieces that it forwards in a plurality of equal-sized cells. As FIG.
3
's second row shows, an ATM cell consists of a cell payload and header. FIG.
3
's first row depicts the cell's header format and shows that it includes a PTI field. One purpose of the PTI field is to indicate whether the cell containing it is the last one in a frame. If it is, then the cell's last eight bytes form the frame trailer field depicted in FIG.
3
's third row. Among other things, the trailer indicates how much of the preceding cell's contents is not actual frame payload but instead is fill used to pad the cell to the predetermined ATM cell size.
The header field of particular interest here is the VPI/VCI field. Each switch associates a virtual path or virtual channel with a virtual-path or virtual-channel identifier of local significance to that switch: it indicates the forwarding-table entry from which the switch is to fetch forwarding information for the cell being forwarded. Part of that entry's information is a replacement for the incoming cell's virtual-path or virtual-channel identifier. The replacement specifies the virtual path or virtual channel's correct entry in the forwarding table of the “next-hop” switch, to which the current switch's forwarding-table entry directs that the cell be sent.
Suppose that the client router
26
of
FIG. 2
sends edge router
10
a packet whose IP destination
Davie Bruce S.
Hughes David A.
Lawrence Jeremy
Cesari and McKenna LLP
Cisco Technology Inc.
Jagannathan Melanie
Rao Seema S.
LandOfFree
Virtual-channel merging does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Virtual-channel merging, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Virtual-channel merging will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3070393