Multiplex communications – Pathfinding or routing – Store and forward
Reexamination Certificate
1999-03-31
2003-07-08
Ton, Dang (Department: 2666)
Multiplex communications
Pathfinding or routing
Store and forward
C370S389000
Reexamination Certificate
active
06590901
ABSTRACT:
BACKGROUND OF THE INVENTION
As it is known in the art, computer networks permit the transfer of information from one computer to another. Some networks, referred to as local-area networks (LANs) include a bus that is shared by a number of computers. Local-area networks permit only one computer to send data over the bus at a given time and that computer can only utilize the bus for a certain period of time before it is required to relinquish it. Because of those constraints, each computer typically segments the information into packets having predefined maximum and minimum lengths. Each packet is sent during a separate bus transaction. If more than one computer needs to send information, then the computers alternately send their packets, so as to share the bus.
On some computer networks, for example Ethernet networks, a collision resolution procedure exists that handles the case where two computers attempt to use the bus at nearly the same time. When a collision occurs, the computers involved in the collision must stop transmitting. Then, each computer re-transmits its information at separate times such that a collision is avoided.
Computer networks are more useful where they are connected to one another such that information can be communicated between two computers on different physical networks. This can be done by employing intermediate computers referred to as “routers”. Each router has two or more network connections to different physical networks. The routers relay packets received from one interface to the other interface and vice versa. For example, consider the network configuration depicted in FIG.
1
. Five hosts
2
,
4
,
6
,
18
and
20
, and two routers
8
,
10
are connected by networks
12
,
14
and
16
. The router R
1
is able to directly deliver any messages that are intended for delivery to hosts
2
,
4
,
18
and
20
. However, a message that is intended for host H
5
must be initially delivered to router R
2
which is able to directly deliver it to H
5
.
Local-area network (LAN) switching is necessary due to the increasing volume of traffic present on many corporate LANs. New applications such as the world-wide web (WWW) and voice-over-LP are responsible for that increased network load. A LAN switch resembles a router in that it relays packets received at one interface, to another interface on the same device. However, the switch must perform this relay operation at high speed and therefore typically does so in hardware rather than software as is the case with a router. Accordingly, it is usually necessary to employ some form of memory in a network switch to handle the case where a packet's intended output port is occupied sending or receiving other traffic.
FIG. 2
shows a situation where buffering is required. Ports P
1
and P
2
each receive traffic for the output port P
3
. Assuming that the input and output ports operate at the same speed, some form of buffering is required such as queue
22
. If port P
3
is busy when packets arrive from ports P
1
or P
2
, then the packets are buffered in queue
22
. Once port P
3
is free, the data packets will be released from queue
22
in the order that they were received.
Two common switch memory architectures exist today that are referred to as the dedicated port memory and the shared global memory. Some switches may use either or both of those architectures to varying degrees. In the dedicated port memory architecture, each network port (either input or output) has memory associated with it. The network port may write packets only into its dedicated memory, and read packets only from its dedicated memory. Usually, a packet must be completely transferred from an input memory to an output memory. However, this transfer methodology is the primary disadvantage of the dedicated port architecture. The other disadvantage is that the amount of memory allocated to a port is finite. If a port's buffer becomes filled, any further information sent to that port will be lost even though memory may be unused elsewhere in the switch. On the other hand, the primary advantage of the dedicated port memory is that there is no need for a port to arbitrate for access to memory, which can be a significant time consuming operation.
In the shared global memory architecture, the switch has access to a single global memory and all network ports must arbitrate for access to that memory. The primary advantages of this architecture are that no copying of packets in memory is required, and the memory is useable by all ports such that no port will be denied any memory until all the memory is in use. The disadvantages of the global memory architecture are twofold. First, a very high bandwidth bus is required to permit all input ports to write into and read out of the memory at speeds that approach the data rate of the network. For example, a twenty-four-port 100 Mbit/second Ethernet switch may perform twenty-four 100 Mbit/second reads and twenty-four 100 MBit/second writes, for a total bus data rate of 4.8 Gbit/sec. It should be noted that such a data rate exceeds the capacity of a 64-bit, 66 MHz PCI bus. The second disadvantage of the global memory architecture is that time is lost in arbitrating for the memory among all of the ports.
SUMMARY OF THE INVENTION
Generally, an embodiment of the present invention is a packet buffer RAM (PBRAM) that provides advantages of the aforementioned memory architectures while removing the disadvantages. PBRAM is a single global memory arranged in a queue architecture, so it has the properties that no packet data copying is required, and that all of the memory is available to all of the ports. PBRAM in the preferred embodiment is a 32-port memory. This means that 32 different devices may access the memory without the need to arbitrate for the data channels.
More specifically, a method and apparatus is provided for storing data packets, transferred across a computer network, in a packet buffer random access memory or PBRAM device. The, PBRAM device receives a number of data packets from network controllers that are coupled to the computer network via associated input ports. After the data packets are received portions thereof are serially transferred to different segments of serial registers that are connected between the input ports and the memory array. Lastly, the data packets are conveyed to the memory array portion of the device in parallel manner while other portions of the packets are being conveyed to other segments of the serial registers.
The PBRAM device further assigns input queue structures in the memory array. It also stores pointers to the packets in a packet table and stores pointers to associated locations of the packet table in the queue structures. Those queue structures are accessible by associated output ports of the PBRAM device such that said pointers are transferred from the input queue structures to associated output queue structures that deliver the data packets to the output ports.
REFERENCES:
patent: 4612634 (1986-09-01), Belamy
patent: 5815723 (1998-09-01), Wilkinson et al.
patent: 6112287 (2000-08-01), Litaize et al.
patent: 6345321 (2002-02-01), Litaize et al.
Hamilton Brook Smith & Reynolds P.C.
MOSAID Technologies Inc.
Ton Dang
LandOfFree
Method and apparatus for providing a packet buffer random... 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 for providing a packet buffer random..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for providing a packet buffer random... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3027657