Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-12-03
2003-10-21
Ngo, Ricky (Department: 2697)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S390000, C370S429000, C370S432000
Reexamination Certificate
active
06636524
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computer network technology, and more particularly, to a method and system for handling the output queuing of received packets in a switching hub in a packet-switching network.
2. Description of Related Art
A computer network system is composed of a number of building blocks, including hubs, bridges, routers, network adapters, terminals, servers, transmission media connectors, network management programs, and so on. A hub is a device that joins communication lines at a central location to provide a common connection to all devices on the network. Various types of hubs are provided in a network, including, for example, standalone repeating hubs, stackable hubs, and switching hubs. A switching hub includes a plurality of ports and is capable of performing the so-called store-and-forward function, which stores the packets (or called frames) received at one port thereof temporarily therein and then outputs the stored packets from designated port or ports thereof so as to forward them to their destinations. A packet is typically 64 bytes to 1518 bytes in length. In Ethernet, there are three types of packets: broadcast packets, multicast packets, and unicast packets. When a switching hub receives a broadcast packet at one port thereof, the received broadcast packet will be subsequently outputted from all the other ports; when a multicast packet is received, it will be subsequently outputted only from some designated ports; and when a unicast packet is received, it will be subsequently outputted solely from one designated port. Presently, a switching hub typically includes 16 ports, with each port having a data rate of 100 MBps (megabyte per second). The conventional switching hub is describing as follows.
FIG. 1
is a schematic diagram showing the core architecture of a conventional switching hub. As shown, the switching hub includes a switching IC (integrated circuit) or a control IC
100
, an SRAM (static random-access memory) unit
110
, and a memory, such as an SDRAM (synchronous dynamic random-access memory) unit
120
. The switching IC
100
contains the control circuits used to control the store-and-forward function for the received packets.
Referring also to
FIG. 2
, the SRAM unit
110
includes a first storage area
112
for storing a forward table, a second storage area
114
for storing the available link nodes of free lists (hereinafter referred to a free-list link node set), and a third storage area
116
for storing an attribute-entry list. The forward table
112
is used to register the source address and destination port number of each received packet; the free-list link node set
114
is used to store all the available free-list link nodes in the switching hub, each stored free-list link node being indicated by the reference numeral
114
a
; and the attribute-entry list
116
is used to stored a number of attribute entries, each stored attribute entry being indicated by the reference numeral
116
a
. Further, each port of the switching hub is associated with an output queue for sequencing those packets that are to be outputted from this associated port.
FIG. 3A
is a schematic diagram used to depict the data structure of each output queue, here designated by the reference numeral
130
. Each time when a packet is received and intended to be outputted from a certain designated port, the switching IC
100
will responsively retrieve a free-list link node
114
a
from the free-list link node set
114
in the SRAM unit
110
and then assign the retrieved free-list link node
114
a
to the output queue
130
of the designated port.
FIG. 3A
shows the case of having three link nodes (herein indicated by the reference numeral
114
a′
) assigned to the output queue
130
. Further, each output queue
130
includes an output-queue head H and an output-queue tail T, which are respectively pointed to the first and last link nodes in the output queue
130
.
Further,
FIG. 3B
shows the format of each link node
114
a
′ in the output queue
130
of FIG.
3
A. As shown, in this preferred embodiment, each link node
114
a
′ is 64 bits in length, wherein Bit
0
is used as a drop flag indicative of whether this link node
114
a
′ is being used or unused; Bits
1
to
16
are collectively used to serve as a pointer indicative of the address of the next link node; Bit
17
is used to indicate the type of the packet that is pointed by this link node
114
a
′; and Bits
18
to
33
are collectively used to serve as a pointer indicative of the address of the packet buffer where the pointed packet is stored.
Referring back to
FIGS. 1 and 2
, the SDRAM unit
120
is partitioned into a plurality of blocks
122
, each having a size of 1.5 KB (kilobyte) and being used as a packet buffer for temporary storage of one of the received packets. Each attribute entry
116
a
in the attribute-entry list
116
in the SRAM unit
110
is mapped in one-to-one correspondence to one of the packet buffers
122
in the SDRAM unit
120
, and is used to indicate whether the corresponding packet has been forwarded or not.
FIG. 3C
shows the format of each attribute entry
116
a
in the attribute-entry list
116
in the SRAM unit
110
. As shown, each attribute entry
116
a
is also 64 bits in length, wherein Bits
0
-
15
are collectively used as a pointer indicative of the address of the next free-list link node; Bits
16
-
32
are collectively used as a port mask; and Bits
33
-
63
are reserved.
The switching hub is designed to handle the received packets in a FIFO (First-In First-Out) manner. To satisfy this requirement, however, the switching hub of
FIG. 1
would be considerably inefficient in its store-and-forward operation. This drawback is depicted with the following example. Assume the switching hub of
FIG. 1
receives a broadcast packet at one port (for example, Port
0
) thereof and subsequently receives a unicast packet at another port (for example, Port
12
) thereof, and the received unicast packet is to be outputted from still another port (for example, Port
1
) of the switching hub. The operation performed by the switching hub of
FIG. 1
to handle this situation is depicted in FIG.
4
. As shown, assume the output queue at Port
1
currently contains
6
link nodes U
11
-U
16
for the outputting of six unicast packets; the output queue at Port
2
currently contains 2 link nodes U
21
-U
22
for the outputting of
2
unicast packets; and the output queue at Port
3
currently contains 9 link nodes U
31
-U
39
(in
FIG. 4
, Port
4
through Port
15
are eliminated for simplification of the drawing and description). When the switching hub receives a broadcast packet at Port
0
, the SRAM unit
110
will responsively assign
15
free-list link nodes
114
a
respectively to the Port
1
through Port
15
, thereby forming a broadcast-packet link node B at the end of each output queue, with each broadcast-packet link node B pointing to one of the packet buffers
122
in the SDRAM unit
120
where the received broadcast packet is temporarily stored. The pointed packet buffer is further mapped to one of the attribute entries
116
a
in the attribute-entry list
116
in the SRAM unit
110
. The port-mask portion (Bits
16
-
32
) of each attribute entry
116
a
is used to indicate whether the associated broadcast packet has been forwarded or not. At the time t
2
when a unicast packet is received at Port
12
and is intended to be outputted from Port
1
for forwarding to its destination, the SRAM unit
110
will responsively assign one free-list link node
114
a
in the SRAM unit
110
to the output queue at Port
1
. At t
6
, Port
1
retrieves the broadcast packet stored in the one of the packet buffers
122
that is pointed by the broadcast-packet link node B. After this, in order to meet the FIFO requirement, Port
1
will output the unicast packet after the outputting of the broadcast packet is completed. After the broadcast packet is outputted from all the other ports, the SRAM unit
Chen Jen-Kai
Liou Jiann-Hwa
Ha Yvonne Q.
J. C. Patents
Ngo Ricky
Via Technologies Inc.
LandOfFree
Method and system for handling the output queuing of... 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 system for handling the output queuing of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for handling the output queuing of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136258