Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-10-05
2004-11-09
Kizou, Hassan (Department: 2662)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000, C370S399000, C370S428000
Reexamination Certificate
active
06816489
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to communication switching methods, in particular packet switching on platforms using an asynchronous transfer mode (ATM) fabric.
2. Description of the Related Art
Many devices, such as layer
2
switches (sometime referred to as bridges) and layer
3
switches (sometime referred to as routers), are being developed based on asynchronous transfer mode (ATM) switch architectures. In an ATM switch, the data enter the device through an ingress port, are switched through an ATM switch fabric, and exit the device through an egress port. Both the ingress and egress ports, as presently known in the art, perform a certain amount of intelligent packet processing and datapath switching functions. Since a typical ATM switch device has multiple input/output ports, the ports are usually grouped together on physical linecards or I/O modules. In some literature, these linecards are referred to as port adapters. Each linecard contains several physical connections to the network and the associated control and processing circuits necessary to manage the logical ports representing the physical network connections. The linecard is also connected to the switch fabric within the switch, and thereby connected to every other linecard in the switch.
One logical element of a model ATM switch, known as the control plane, consists of routing protocol, configuration, and management subsystems. The control plane is typically implemented as part of a central routing processor. It may also be implemented in a distributed or pipelined processing architecture through a shared message-passing interface or similar logical structure known in the art. The term “control plane” can also describe a logical combination of subsystems that defines a central route processor. Regardless of configuration, the control plane establishes the internal connections between ingress and egress ports that provide “any to any” switching.
The organization and terminology used to describe ATM switches is further explicated in Chapter 15 of Roger L. Freeman,
Telecommunication System Engineering
, 3d ed. (1996), incorporated herein by reference in its entirety. Further technical explanation of ATM networks and switching is to be found in H. J. R. Dutton and P. Lenhard,
Asynchronous Transfer Mode (ATM) Technical Overview
(2d ed. 1995); Othmar Kyas, ATM Networks (1995); and W. A. Flanagan, ATM User's Guide, (1995), all of which are incorporated herein by reference.
The basic communication unit within the Asynchronous Transfer Mode protocol is the cell. An ATM cell is 53 octets in length, and includes a header and a payload. The cell header occupies 5 octets and the remaining 48 octets are reserved for the payload. The cell destination is identified by a Virtual Path Identifier/Virtual Connection Identifier (“VPI/VCI”) located in the header. The VPI is either 8 or 12 bits in length, depending on whether the link is a Network to Network Interface (“NNI”) or a User Network Interface (“UNI”). The VCI is 16 bits in length. Thus, the VPI and VCI collectively provide a 24 or 28 bit address.
Supporting the total number of connections defined by the VPI/VCI address space would be impractical for most commercial ATM switch applications due to large memory requirements and attendant costs. For this reason, it is common practice to translate the VPI/VCI address space to a smaller address space by address translation techniques. In typical ATM switches, the incoming VPI/VCI address is translated into a smaller, local address space whose width defines the number of connections supported by the switch. This internal-to-the switch, local address is the Incoming Virtual Circuit number or IVC. The cell is directed to one or more ports within the switch based on the IVC. In an output process, a remapping is executed to define an outgoing VPI/VCI address for the cell.
Remapping the outgoing VPI/VCI becomes memory intensive when supporting multicast operation since a single incoming VPI/VCI may spawn multiple VPI/VCIs for transmission. For example, if an ATM switch includes 14 linecards, each having 8 I/O ports, it is possible that one input may spawn 112 outputs. It is theoretically possible to employ a lookup table at each port to remap the outgoing address to the proper destination VPI/VCI. However, such an architecture would be impractical since it would require an inordinately large amount of memory. A more efficient technique for handling multicast cells would therefore be of benefit.
As discussed above, packets of data (also called “cells” in ATM literature) are sent from the ingress port on an internal connection to one or more egress ports, also known as egress interfaces. (In ATM terminology, the terms “port” and “interface” are interchangeable and refer to the external network connection to or from the switch.) There are typically two logical components to the internal connection in an ATM switch. The logical part of the connection between the ingress port and the switch fabric is the incoming virtual circuit (IVC) discussed above. The logical part of the connection between the switch fabric and egress port is called the outgoing virtual circuit (OVC). And, as noted above, an internal connection could be one of two types: a point-to-point connection or a point-to-multipoint connection. The IVC associated with a point-to-multipoint connection is known as a “root” and the corresponding set of (multipoint) OVCs are termed “leaves”.
Each egress port then makes its own decision on how to send the packet out of the switching device. For example, egress port processing determines the outgoing (or “uplink”) VPI/VCI on which to send the packet out of the switch. The egress port also decides the type of encapsulation (e.g., UNI or NNI) to use on the outbound packet based on which virtual LAN (VLAN) or external VC that the packet is to use to leave the switch.
Packet processing is thus distributed between both the ingress and egress ports. The ingress processing tasks include packet parsing, header validation, and address look-up at OSI layer
2
and/or layer
3
, as commonly known and used in the art. The layer
2
/
3
address look-up task determines the next hop (i.e., the path denoted by the uplink VPI/VCI to the next switch or the final packet destination) that the packet will take. This determination also determines the egress interface or port. Since the processing power in both the ingress and egress interfaces is limited, it is important to avoid duplicating processing efforts between the ingress and egress sides of the switch.
In the case of broadcast or multicast traffic, the packet replication necessary to send one packet to multiple destinations is typically performed in the switch fabric. However, since the encapsulation and processing of each packet for a particular outbound interface is unique to each outbound interface, the ingress processing is unable to determine a priori all of the necessary encapsulations for broadcast/multicast packets. In other words, it is not possible for the ingress side to convey all of the necessary forwarding information to the egress side. This means that, for broadcast/multicast packets, the egress interface has to determine at least some of the forwarding information based on information presented to it by the switch fabric.
One approach to egress processing of multicast cells previously used in the art maintains an outgoing virtual circuit table at the egress interface. This OVC table is used by the egress interface to look-up the parameters required for egress processing. U.S. Pat. No. 5,666,361, “ATM Cell Forwarding and Label Swapping Method and Apparatus” to Aznar, et al., incorporated herein by reference in its entirety describes one approach to this problem.
As noted above, the main function of an ATM switch is to receive incoming ATM cells (or “packets” of data, generally) at the input ports of one or more port adapters (linecards) and to redirect those cells to specific output ports (on the same or different linec
Patra Abhijit
Sharma Samar
Campbell Stephenson Ascolese LLP
Cisco Technology Inc.
Kizou Hassan
Levitan Dmitry
LandOfFree
Efficient method for packet switching on asynchronous... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient method for packet switching on asynchronous..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient method for packet switching on asynchronous... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3337813