 |
Description  |
|
|
The present invention relates to networking systems and the forwarding and
routing of information therein, being more particularly directed to the
problems of a common method for managing both cell and packet or frame
switching in the same device, having common hardware, common QoS (Quality
of Service) algorithms, common forwarding algorithms; building a switch
that handles frame switching without interfering with cell switching.
BACKGROUND OF INVENTION
Two architectures driving networking solutions are cell switching and frame
forwarding. Cell switching involves the transmission of data in fixed size
units called cells. This is based on technology referred to as
Asynchronous Transfer Mode (ATM). Frame forwarding transmits data in
arbitrary size units referred to either as frames or packets. The basis of
frame forwarding is used by a variety of protocols, the most noteworthy
being the Internet Protocol (IP) suite.
The present invention is concerned with forwarding cells and frames in a
common system utilizing common forwarding algorithms. In co-pending U.S.
patent application Ser. No. 581,467, filed Dec. 29, 1995, for High
Performance Universal Multi-Ported Intemally Cached Dynamic Random Access
Memory System, Architecture and Method, now U.S. Pat. No. 5,799,209 issued
Aug. 25, 1998 and co-pending U.S. patent application Ser. No. 900,757,
filed Jul. 25, 1997, for System Architecture for and Method of Dual Path
Data Processing and Management of Packets and/or Cells and the Like, now
U.S. Pat. No. 5,918,074 issued Jun. 29, 1999 both of common assignee
herewith, a promising solution of common cell/frame forwarding is
provided.
Most traditional Internet-style host-to-host data communication is carried
out in variable size packet format, interconnected by networks (defined as
a collection of switches) using packet switches called routers. Recently,
ATM has become widely available as a technology to move data between
hosts, having been developed to provide a common method for sending
traditional telephony data as well as data for computer-to-computer
communication. The previous method employed was to apply Time Division
Multiplexing (TDM) to telephony data, with each circuit allocated a fixed
amount of time on a channel. For example, circuit A may be allocated x
amount of time (and thus data), followed by y and z and then x again, as
later described in connection with hereinafter discussed FIG. 3. Thus each
circuit is completely synchronous. This method, however, has intrinsic
limitations with bandwidth utilization, since if a circuit has nothing to
send, its allocated bandwidth is not used on the line. ATM addresses this
bandwidth issue by allowing the circuits to be asynchronous. Though
bandwidth is still divided among fixed length data items, any circuit can
transmit at any point in time.
The ITU-T (International Telecommunications Union--Telecommunications,
formally the CCITT), an organization chartered by the United Nations to
provide telecommunications standards, defined four classes of service: 1)
Constant Bit Rate for Circuit Emulation, i.e. constant-rate voice and
video; 2) Variable Bit Rate for certain voice and video applications; 3)
Data for Connection-Oriented Traffic; and 4) Data for
Connectionless-Oriented Traffic. These services, in turn, are supported by
certain "classes" of ATM traffic. ATM moves data in fixed size units
called cells. There are several types of ATM "types", referred to as ATM
Adaptation Layers (AAL); these ATM adaptation layers are defined in ITU-T
Recommendation I.363. There are 3 defined types: AAL1, AAL3/4 and AAL5.
AAL2 has never been defined in the ITU-T recommendations and AAL3 and AAL4
were combined into one type. With respect to the ATM cell make-up, there
is no way to distinguish cells that belong to one layer as opposed to
cells that belong to another layer.
The adaptation layer is determined during circuit setup; i.e. when a host
computer communicates to the network. At this time, the host computer
informs the network of the layer it will use for a specific virtual
circuit. AAL1 has been defined to be used for real-time applications such
as voice or video; while AAL5 has been defined for use by traditional
datagram oriented services such as forwarding IP datagrams. A series of
AAL5 cells are defined to make up a packet. The definition of an AAL5
packet consists of a stream of cells with the PTI bit set to 0, except for
the last one (as later illustrated in FIG. 1). This is referred to as a
segmented packet.
Thus, in current networking technology, data is transported in either
variable size packets or fixed size cells depending on the types of
switching devices installed in the network. Routers can be connected to
each other directly or through ATM networks. If connected directly, then
packets are arbitrary size; but if connected by ATM switches, then all
packets exiting the router are chopped into fixed size cells of 53 bytes.
Network architectures based on the Internet Protocol (IP) technology are
designed as a "best effort" service. This means that if bandwidth is
available, the data gets through. If, on the other hand, bandwidth is not
available then the data is dropped. This works well with most computer
data applications such as file transfers or remote terminal access. This
does not work well with applications that can not retransmit, or where
retransmission is of no value, such as with video and voice. Getting a
video frame out of order makes no sense, whereas file transfer
applications can tolerate such anomalies. Since the packet size is
arbitrary at any point in time making specific delay variation commitments
between any two frames is almost impossible, as there is no way of
predicting what type and size of traffic is ahead of any other type of
traffic. The buffers that must handle the data, moreover, must be able to
receive the maximum data size, meaning that that buffering scheme must be
optimized to handle larger data packets while at the same time not wasting
too much memory on smaller packets.
ATM is designed to provide several service categories for different
applications. These include Constant Bit Rate (CBR), Available Bit Rate
(ABR), Unspecified Bit Rate (UBR) and two versions of Variable Bit Rate
(VBR), real-time and non-real-time. These service categories are defined
in terms of Traffic Parameters and QoS Parameters. Traffic Parameters
include Peak Cell Rate (constant bandwidth), Sustainable Cell Rate (SCR),
Maximum Burst Size (MBS), Minimum Cell Rate (MCR) and Cell Delay Variance
Tolerance. QoS parameters include Cell Delay Variation (CDV), Cell Loss
Ratio (CLR) and maximum Cell Transfer Delay (maxCTD). As an example,
Constant Bit Rate CBR (e.g. the service used for voice and video
applications) is defined as a service category that allows the user at
call setup time to specify the PCR (peak cell rate, essentially the
bandwidth), the CDV, maxCTD and CLR. The network must then ensure that the
values requested by the user and accepted by the network are met; if they
are met, the network is said to be supporting CBR.
The various classes of service direct the network to provide better service
for some traffic as opposed to other types of traffic. In ATM, with fixed
length cells, switches manage bandwidth utilization on a line effectively
by controlling the amount of data each traffic flow is allowed to put on a
line at any moment in time. They generally have simpler buffer techniques
arising from the fact that there is but one size of data unit. Another
advantage is predictable network delays, especially queuing latencies at
each switch. Since all data units are the same size, this helps to ensure
that such traffic QoS parameters as CDV are easily measurable in the
network. In non-ATM networks (i.e. frame-based networks), frames can range
anywhere from, say, 40 bytes to thousands of bytes, rendering it difficult
to ensure a consistent CDV (or PDV, Packet Delay Variation) since it is
impossible to predict the delays in the network, lacking consistent
transfer times of individual packets.
By carving data into smaller units, ATM can increase the ability of the
network to decrease the latency of transmitting data from one host to
another. Such also allows for easier queue and buffer management at each
hop through the network. A disadvantage, however, is that a header is
added to each cell making the effective bandwidth of the network less than
if the network had a larger transmission unit. For example, if 1,000 bytes
are to be transferred from one host to another, then a frame-based
solution would append a header (approximately 4 bytes) and transmit the
entire frame in less than a second. In ATM, the 1,000 bytes is chopped
into 48 bytes with a 5 bytes header; i.e. 1,000/48=20.833 (or 21 cells).
Each cell is then given a 5 byte header increasing the bytes to be
transmitted by 5*21=105 extra bytes. Thus ATM effectively decreases the
available bandwidth to the actual data by approximately 100 bytes (or
about 10%); the decreasing of end-to-end latency also decreases the
available bandwidth for data transmission.
For some applications, such as video and voice, latency is more important
than bandwidth while for other applications, such as file transfers,
better bandwidth utilization increases performance rather than decreased
hop-by-hop latency.
Recently, the demands on more bandwidth and QoS have grown many fold due to
new applications for multimedia services, including the before described
video and voice. This is forcing the growth of ATM networks in the core of
traditional packet-based networks. ATM, because of its fixed packet size,
brings reduced processing time in networks and hence faster forwarding
(i.e. lower latency). It also brings with it the ability to take advantage
of traffic classification. Since the cells, as earlier pointed out, are of
fixed size, traffic patterns can be controlled through QoS assignments;
i.e. networks can carry traditional packets (in cell format) and constant
bandwidth stream data (e.g. voice/video based data).
As will subsequently be demonstrated, most conventional networking systems
inherently are designed for either forwarding frames or cells but not
both. In accordance with the present invention, on the other hand, through
use of novel search algorithms, QoS management and management of
packet/cell architecture, both cells and frames can be transmitted in the
same device and with significant advantage over the prior techniques, as
later more fully explained.
OBJECTS OF INVENTION
An object of the present invention, accordingly, is to provide a novel
system architecture and method, useful with any technique for processing
data packets and/or cells simultaneously with data packets, and without
impacting the performance aspects of cell forwarding characteristics.
A further object is to provide such a novel architecture in which the
architected switch can serve as a packet switch in one application and as
a cell switch in another application, using the same hardware and
software.
Still a further object is to provide such a system wherein improved results
are achieved in managing QoS characteristics for both cells and data
packets simultaneously based on a common cell/data packets algorithm.
An additional object is to provide a common parsing algorithm for
forwarding cells and data packets using common and similar techniques.
Other and further objects will be explained hereinafter, and are more
particularly delineated in the appended claims.
SUMMARY
In summary, from one of its important viewpoints, the invention encompasses
in a data networking system wherein data is received as either ATM cells
or arbitrarily-sized multi-protocol frames from a plurality of I/O modules
any of which can be cell or frame interfaces, a method of processing both
ATM cells or such frames in a native mode, i.e. not transforming frames to
cells, using common algorithms for forwarding based on control information
contained in the cell or frame and in such a manner as to preserve QoS
characteristics necessary for correct operation of cell forwarding;
processing the packet/cell control information in a forwarding engine with
common algorithms not dependent on context-sensitive information contained
in the cell or packet, and passing results including QoS information to an
egress queue manager; passing the cell/ packet to the egress I/O transmit
facility in such a manner as to provide a minimal cell delay variation
(CDV) so as not to impact correct cell forwarding characteristics; and
controlling the transmit facility so as to provide a common bandwidth
management algorithm for both cell and packets and all without impacting
the correct operation of either cells or packets.
Preferred and best mode designs and techniques are hereinafter presented in
detail.
DRAWINGS
The invention will now be described in connection with the accompanying
drawings in which the before-mentioned
FIG. 1 is a diagram illustrating an ATM (Asynchronous Transfer Mode) cell
format;
FIG. 2 is a similar diagram of an Internet Protocol (IP) frame format for
32 bit words;
FIG. 3 is a flowchart comparing Time-Division Multiplexing (TDM), ATM and
Packet Data frame forwarding;
FIG. 4 is a block diagram of the switch of the invention with the cell and
packet interfaces;
FIG. 5 is a block diagram of a traditional prior art bus-based switching
architecture, and
FIG. 6, its memory-based switch data flow diagram;
FIG. 7 is a block diagram of a traditional prior art cross-bar type
switching architecture, and
FIG. 8, its cross-bar data flow diagram;
FIGS. 9-11 are interface diagrams illustrating, respectively, a cell switch
with a native interface card, a packet interface on cell switch, and an
AAL5 packet interface on cell switch, all with a cross-bar or memory
switch;
FIGS. 12 and 13 are similar diagrams of a packet switch with native packet
interface cards and with AAL5 interface, respectively, for N.times.N
memory connection buses;
FIG. 14 is a block diagram of the switch architecture of the present
invention, using the word "NeoN" in connection with the packet and cell
data switch as a trade name of NeoNET LLC, the assignee of the present
application;
FIGS. 15 and 16 are diagrams respectively of extended parsing function
flows for forwarding decisions and an overview of such functions and
FIG. 17 is a diagram of the forwarding elements;
FIG. 18 is a first stage parse graph tree lookup block diagram, and
FIG. 19 is a second stage forwarding table lookup (FLT) diagram;
FIGS. 20 and 21 are respective diagrams of parse graph memory on power up
and of a simple illustrative IP multicast packet;
FIG. 22 presents an initialized lookup table, with all entries pointing to
unknown route/cell forwarding information, and
FIG. 23 illustrates the lookup table after adding an illustrative IP
address (209.6.34.224/32); and
FIG. 24 is a queuing diagram for scheduling system operation.
FURTHER BACKGROUND TO PREFERRED EMBODIMENTS OF INVENTION
Before proceeding to illustrate the preferred architecture of the
invention, it is believed necessary to review the limitations of the prior
and of current network systems, which the present invention admirably
overcomes.
Current networking solutions are designed either for switching data packets
or cells. As before stated, all types of data networking switches must
receive data on an ingress port, make a forwarding decision, transfer data
from the ingress port to the egress port and transmit that data on the
appropriate egress port physical interface. Beyond the basic data
forwarding aspects, there are different requirements for cell switching
versus frame forwarding. As before stated, all current technology divides
switching elements into three types: bridges, routers and switches, and in
particular, ATM switches. The distinction between bridges and routers is
blurred in that both forward datagrams and typically most routers also do
bridging functions as well, thus the discussion focuses on datagram
switches (i.e. routers) and ATM switches.
It is in order first to investigate the basic architectural requirements
for these two types of switching devices based on current solutions, and
then to present the reasons why current solutions do not provide
mechanisms to allow simultaneous transfer of cells and frames without
severely impacting the correct operations of either ATM switching or frame
forwarding. The novel solution based on the present invention will then be
clear.
Routers typically have a wide variety of physical interfaces: LAN
interfaces, such as Ethernet, Token ring and FDDI, and wide-area
interfaces, such as Frame Relay, X.25, T1 and ATM. A router has methods
for receiving frames from these various interfaces, and each interface has
different frame characteristics. For example, an Ethernet frame may be
anywhere from 64 bytes to 1500 bytes, and an FDDI frame can be anywhere
from 64 bytes to 4500(including header and trailer) bytes. The router's
I/O module strips the header that is associated with the physical
interface and presents the resulting frame, such as an IP datagram, to the
forwarding engine. The forwarding engine looks at the IP destination
address, FIG. 2, and makes an appropriate forwarding decision. The result
of a forwarding decision is to send datagram to the egress port as
determined by the forwarding tables. The egress port then attaches the
appropriate network-dependent header and transmits the frame from the
physical interface. Since different interfaces may have different frame
size requirements, a router may be required to "fragment" a frame, i.e.
"chop" the datagram into useable size. For example, a 2000 byte FDDI frame
must be fragmented into frames of 1500 bytes or less before being sent out
on a Ethernet interface.
Current router technology offers "best effort" service. This means that
there are no guarantees that datagrams will not be dropped in a
router-based network. Furthermore, because routers transfer datagrams of
varying sizes, there are no per datagram delay variation or latency
guarantees. Typically a router is characterized by its ability to transfer
datagrams of a certain size. Thus, the capacity of a router may be
characterized by its ability to transfer 64 byte frames in one second or
the latency to transfer a 1500 byte frame from an ingress port to an
egress port. This latency is characterized by last bit in, first bit out.
An ATM switch, by comparison, has only one type of interface, i.e. ATM. An
ATM switch makes forwarding decision by looking at a forwarding table
based on VPI/VCI numbers, FIG. 1. The forwarding table is typically
indexed by physical port number, i.e. an incoming cell with a VPI/VCI on
ingress port N gets mapped to an egress port M with a new VPI/VCI pair.
The table is managed by software elsewhere in the system. All cells, no
matter what the ATM Adaptation Layer (AALx), have the same structure, so
that if ATM switches can forward one AAL type, they can forward any type.
In order to switch ATM cells, several fundamental criteria must be met. The
switch must be able to make forwarding decisions based on control
information provided in the ATM header, specifically VPI/VCI. The switch
must provide appropriate QoS functions. The switch must provide for
specific service types, in particular Constant Bit Rate (CBR) traffic and
Variable Bit Rate (VBR). CBR (voice or video) traffic is characterized by
low latency and more importantly low or guaranteed Cell Delay Variation
(CDV) and guaranteed bandwidth.
The three main requirements of implementing CBR type connections over a
traditional packet switch are low CDV, small Delay and guaranteed
bandwidth. Voice, for example, consumes a fixed amount of bandwidth, based
on the fundamental Nyquist's sampling Theorem. CDV is also part of a CBR
contract, and plays a role into the overall Delay. CDV is the total worst
case variance in expected arrival time and actual arrival time of a
packet/cell. In so far as an application is concerned, it wants to see
data arrive equidistant in time. If, however, the network cannot guarantee
this equidistant requirement, some hardware has to buffer data--equal or
more than the worst case CDV amount introduced by the network. The higher
the CDV, the higher is the buffer requirement and hence the higher Delay;
and, as illustrated earlier, Delay is not good for CBR type circuits.
Packet-based networks traditionally queue data at the egress based on
priority of traffic. Regardless of how data is queued, traffic with low
delay variation requirements will get queued behind one or more packets.
Each of them could be maximum packet size, and this inherently contributes
the most to delay variation on a packet-based network.
There are many methodologies used to manage bandwidth and priorities. From
a Network Management point of view, a network manager usually likes to
carve out the total egress bandwidth into priorities. There are several
reasons for carving this bandwidth: e.g. it ensures the manager that
control traffic (Higher Priority and Low Bandwidth) always has room on the
wire even during very high line bandwidth utilization, or perhaps a CBR
(Constant Bit Rate) traffic will be guaranteed on the wire, etc.
There are numerous methods to address bandwidth per traffic priority. Broad
classes of these mechanisms are Round Robin Queuing, Weighted Fair Queuing
and Priority Queuing. Each methodology will be explained for the sake of
discussion and completeness of this document. In all cases of queuing,
traffic is put into queues based on priorities, usually by a hardware
engine that looks at a cell/packet header or control information
associated with cell/packet as the cell/packet arrives from the backplane.
It is how data is extracted/de-queued from these queues that
differentiates one queuing mechanism from another.
Simple Round Robin Queuing
This queuing mechanism empties all queues in a round robin fashion. This
means that traffic is divided into queues and each queue gets the same
fixed bandwidth. While a clear advantage is simplicity of implementation,
a major disadvantage of this queuing technique is that this mechanism
completely loses the concept of priority. Priority must then be managed by
buffer allocation mechanisms. The only clear advantage is simplicity of
implementation.
Weighted Round Robin
This queuing mechanism is an enhancement of Simple Round Robin Queuing
`Simple Round Robin Queuing`, where a weight is placed on each queue by
the network manager during initialization time. In this mechanism, each
priority queue is serviced based on the weight. If one queue is allocated
10% of the bandwidth, it will be serviced 10% of the time. Another queue
may have 50% of the allocated bandwidth, and will be serviced 50% of the
time. The major drawback is there is unused bandwidth on the wire when
there is no traffic in a queue of the allocated bandwidth. This results in
wasted bandwidth. There is, moreover, no association of packet size in the
de-queuing algorithm, which is crucial for packet-based switches. Giving
equal weight to all packet sizes throws off the bandwidth allocation
scheme.
Priority Queuing
In this queuing mechanism, output queues are serviced purely based on
priority. The Highest Priority Queue gets serviced first, and the Lowest
Priority Queue gets serviced last. In this mechanism, Higher Priority
Traffic always preempts the Lower Priority Queue. The drawback of this
type of mechanism is that the Lower Priority Mechanism may result in zero
bandwidth. The advantage of this mechanism, besides being simple, is that
the bandwidth is not wasted; so long as there is data to send, it will be
sent. There is, however, no association of packet size in the de-queuing
algorithm, which is crucial for packet-based switches. Giving equal weight
to all packet sizes throws off the bandwidth allocation scheme, as before
noted.
From the above examples, there is a need to strike a balance between
Priority Queuing and Weighted Round Robin Queuing, along with packet size.
This calls for a solution provided by the present invention where high
priority traffic is serviced before lower priority traffic, but each queue
is serviced at least within its bandwidth allocation. In addition to the
above requirement, the output buffer should be filled with data from a
queue even when the bandwidth of that queue is exhausted, including with
other bandwidth eligible queue data. This technique enforces bandwidth per
traffic queue requirement and also does not waste bandwidth on the wire
and is embodied in the invention
Architectural Issues in Switch Design
Current switching solutions employ two distinct solutions: 1) memory and 2)
cross-bar. These solutions are illustrated in FIGS. 5 and 6 showing a
traditional bus-based and memory based architecture, and in FIG. 7,
showing a traditional cross-bar switching architecture. In the traditional
memory-based solutions represented by FIG. 5, data must first be placed
inside of main memory from the I/O card. This data transfer takes several
cycles as bits are moved from the I/O module to the main memory. Since
several different I/O modules must transfer data to common memory,
contention for this resource occurs. Main memory provides both a buffering
mechanism and a transfer mechanism for data from one physical port to
another physical port. The rate of transfer is then highly dependent on
the speed of the egress port and the ability of the system to move data in
and out of main memory and the number of interfaces that must access main
memory.
As more fully shown in FIG. 6, the CPU interfaces through a common bus,
with memory access, with a plurality of data-receiving and transmitting
I/O ports #1, #2, etc., with the various dotted and dashed lines showing
the interfacing paths and the shared memory, as is well known. As pointed
out previously, the various accesses of the shared memory result in
substantial contention, increasing the latency and unpredictability, which
is already substantial in this kind of architecture because the processing
of the control information cannot begin until the entire packet/cell is
received.
Furthermore, as the accesses to the shared memory are increased, so does
the contention; and as the contention is increased, this results in
increasing the latency of the system. In the traditional memory-based
switch data flow diagram of FIG. 6, thus, where the access time per read
or write to the memory is equal to M, and the number of bits for a memory
access is W, the following functions occur:
There is the write of data from the receive port #1 to shared memory. The
time to transfer a packet or cell is equal to ((B*8)/W)*M, where B is
equal to the number of bytes for the packet or cell, M is the access time
per read or write to the memory and W is the number of bits for a memory
access. As the packet gets larger so does the time to write it to memory.
This means that if a packet is destined to an ATM interface as in FIG. 5,
followed by a cell, the cell is delayed by the amount of transfer time
from main memory, and in the worst case this could be N packets (where N
is the number of packet, non-ATM interfaces) including the contention
among other reads and writes on the bus. If, for example, B=4000 bytes and
M is 80 nanoseconds (for a 64 bit-wide bus for DRAM access), then
((4000*8)/64)* 80=40,000 nanoseconds for a packet transfer queued before a
cell can be sent, and OC 48 is 170 nanoseconds per 64 byte cells. This is
only if there is no contention on the bus whatsoever. In the worst case,
if a switch has 16 ports and all the ports are contending simultaneously,
then to transfer the same packet would require 640,000 nanoseconds just to
get into the memory, and the same amount to get out--a total time of about
1.3 milliseconds. This occurs if between each write into memory, another
port has to write to memory as well. So for n=16 ports, n-1, or 15 ports
have to gain access to memory. This means that 15 ports*80
nanoseconds=1200 nanoseconds are used by the system before the next
transfer into memory of the original port can occur. Since there are 4000
bytes*8 bits/byte)/64 bits=500 accesses, each access is separated by 1200
nanoseconds, and the full transfer takes 500*1200=600,000 nanoseconds. So
the total is system time plus actual transfer time which is 600,000
nanoseconds+40,000 nanoseconds=640,000 nanoseconds for the transfer into
memory, and another 640,000 nanoseconds out of memory. This calculation,
moreover, does not include any CPU contention issues or delay because of
egress port busy, which would make this calculation even larger.
There are similar disadvantages in traditional cross-bar based solutions as
shown in FIG. 7, before referenced, where there is no main memory, and
buffering of data occurs both at the ingress port and egress port. In the
memory-based design of FIGS. 5 and 6, buffer memory is shared across all
ports, making for very efficient utilization of memory on the switch. In
the cross-bar approach of FIG. 7, each port must provide a large amount of
memory, so that the overall memory of the system is large as there is no
common sharing of buffers. The cross-bar switch is only a conduit for the
transfer of data from one physical port on the system to another physical
port on the system. If two ports are simultaneously to transfer data to
one output port, one of the two input ports must buffer the data thereby
increasing the latency and unpredictability as the data from the first
input port is transferred to the output port. The advantage of a cross-bar
switch over a memory-based switch, however, is the high rate of data
transfer from one point to another without the inherent limitation of main
memory contention on the memory-based switch.
In the traditional cross-bar switching architecture system of FIG. 7, the
CPU interfaces through a common bus, with memory access, to an interface
with the various dotted and dashed lines of FIG. 8 showing the interfacing
paths and the shared memory, as is well known. The CPU makes a forwarding
decision based on information in the data. The data must then be
transmitted across the cross-bar switch fabric to the egress port. But if
other traffic is being forwarded to that egress interface, then the data
must be buffered in the ingress interface for so long as the amount of
time it takes to transfer the entire cell/packet to the egress memory.
There is:
A. Write of data from the receive port #1 to local memory. The time to
transfer a packet or cell is equal to ((B*8)/W)*M, where B is equal to the
number of bytes for the packet or cell, M is the access time per read or
write to the memory and W is the number of bits for a memory access. As
the packet gets larger so does the time to write it to memory.
B. Write of data from the receive port #1 to local memory of egress port
#2. The time to transfer a packet or cell is equal to ((B*8)/W)*M+T, where
B is equal to the number of bytes for the packet or cell, M is the access
time per read or write to the memory, W is the number of bits for a memory
access and T is the transfer time of the cross-bar switch. As the packet
gets larger, so does the time to transfer it across the cross bar switch
and write it to local memory.
For a packet transfer followed by a cell transfer to an egress port, the
calculation is the same as for the memory-based solution of FIGS. 5 and 6.
The packet must be transferred to local memory at the same speeds as for
the memory-based solution. The advantage that there is no contention for
central memory, does not alleviate the problem that a packet transfer in
front of a cell transfer can cause delays that prevent the proper
functioning of very fast interface speeds.
The goal is to create a switching device running at high speeds (i.e. SONET
defined rates) that provides the required QoS. The device should be
scalable in terms of speed and ports, and the device should allow for
equal-time transfer of cells and frames from an ingress port to an egress.
While current designs have started to come up with very high speed routers,
they have not, however been able to provide all the ATM service
requirements, thus still maintaining a polarized set of networking
devices, i.e. routers and ATM switches. An optimal solution is one that
achieves very high speeds and that provides the required QoS support and
has interfaces that merge ATM and Packet-based technologies on the same
interface, FIG. 3. This will allow the current investment in either
networking technology to be preserved, yet satisfy bandwidth and QoS
demands.
The issues in merging interfaces on a data switch port that accepts ATM
cells and treats certain ATM cells as packets and others as ATM flows,
accepts only packets on other interfaces and only cells on yet another set
of interfaces, is shown in later-discussed FIG. 4. These issues are three
fold: a) Forwarding decision at the ingress interface for packet and
cells, b) switching packet and cells through the switch fabric and, c)
managing egress bandwidth on packet and cells. The present invention,
based on this technique of the previously cited co-pending applications,
explains how to create a general data switch that merges the two
technologies (i.e. ATM switching and packet switching) and solves the
three issues listed above.
Interface Issues Switch Designs
The purpose of this section is to compare and contrast ATM and Packet-based
switch designs and various interfaces on either type of switch design.
Specifically it identifies problems with both devices as they pertain to
forwarding packet or cells; i.e. issues with ATM switches forwarding
packet, and issues with Packet switches forwarding cells, FIG. 3.
Typical Design of an ATM Switch
As previously explained, defined within the ATM standard there are multiple
ATM Adaptation Layers (AAL1-AAL5), each one specifying a different type of
service from a wide spectrum of services; namely, Constant Bit Rate (CBR)
to Unspecified Bit Rate (UBR). Constant Bit Rate (AAL1) contract
guarantees minimal cell loss with low CDV, while Unspecified Bit Rate
contract specifies no traffic parameters, and no quality of Service
guarantees. For the purposes of this invention it is convenient to limit
the discussion to AAL1 (CBR) and AAL5 (Fragmented Packets).
FIG. 9 illustrates cell switching with native cell interface cards, showing
different modules of a generic ATM Switch with native ATM interfaces. The
cells arriving from the physical layer module (PHY) are processed by a
module called Policing Function Module, which validates per VCI
established contracts (services ) for incoming cells; e.g Peak Cell Rate,
Sustained Cell Rate, Maximum Burst Rate. Other parameters such as Cell
Delay Variation (CDV) and Cell Loss Rate (CLR) are guarantees provided by
the box based on the actual design of the cards and the switch. The
contracts are set by the network manager or via ATM signaling mechanisms.
Cell Data from the policing function then goes, in the example of FIG. 9,
to a Cross Bar-type (FIG. 7) or Memory-based Switch (FIG. 5). Cells are
then forwarded to the egress port which has some requirements of shaping
traffic to avoid congestion on the remote connection. To provide egress
shaping, the design will have to buffer data on the egress side. Since ATM
connections are based on a point-to-point basis, the Egress shaper module
also has to translate the ATM Header. This is because the next hop has no
relationship to the ingress VCI/VPI.
Native Packet Interface on ATM Switch
As mentioned in the `Background` section, if an ATM switch is to provide a
method that facilitates the routing of packets, there have to be at least
two points between two hosts where packets and cells networks meet. This
means that current cell switching equipment has to carry interfaces that
have nati | | |
