Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1998-12-24
2003-01-14
Ngo, Ricky (Department: 2664)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S469000, C709S235000
Reexamination Certificate
active
06507563
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates generally to mechanisms and methods for routing data packets between nodes within a network. More specifically, the present invention relates to methods and apparatus for routing data packets from a data queue through a protocol stack.
FIG. 1
is a diagrammatic representation of a conventional network configuration
100
. As shown, data packets
104
are held within a plurality of data queues
102
. For example, data packets
104
a
,
104
b
, and
104
c
are held within a first data queue, data packet
104
d
is held within a second data queue, data packet
104
e
is held within a third data queue, etc.
As shown, there are various types of data that go to the different data queues
102
. For example, internet protocol (IP) data
10
goes to a first data queue and a second data queue; packet assembler disassembler (PAD) data
12
goes to another data queue; qualified logical link control (QLLC) data
14
goes to yet another data queue; and data link switching (DLSW) data
16
goes to yet another data queue.
The network configuration
100
also includes a plurality of diverse protocol stacks through which the data or data packets will be transmitted, and each protocol stack has one or more associated protocol levels (also referred to as protocol layers or contexts). In other words, each data packet is associated with one of the protocol stacks and will eventually be sent through the associated protocol stack. For example, a data packet
104
e
will be transmitted through an associated protocol stack that includes a virtual circuit (VC) protocol layer
112
b
, an X.25 protocol layer
110
, a link logic control (LLC
2
) protocol layer
108
a
, and a physical protocol layer
106
associated with a hardware device (not shown). The hardware device is coupled to other hardware devices (not shown) of other network nodes (not show), such as another router or end destination.
The term protocol is defined as any type of information format that is used to communicate between any independent entities, such as two network nodes.
Each data queue is associated with one or more protocols (herein referred to as a “protocol stack”), and these particular associations depend on the requirements of the particular application being implemented. For example, Internet Protocol data packets are transmitted directly from a data queue to the physical layer
106
. As shown, data packet
104
g
is associated with the physical protocol layer
106
and is sent from the data queue to the physical layer
106
. Likewise, data packets
104
a
through
104
c
are also only associated with the physical protocol layer
106
.
Data packets may travel through various protocols before reaching the physical layer
106
. For example, data packet
104
f
is associated with the virtual circuit (VC) protocol layer
112
a
, the X.25 protocol layer
110
, the LLC
2
protocol layer
108
a
, and the physical protocol layer
106
. Likewise data queue
104
e
is associated with the VC protocol layer
112
b
, the X.25 protocol layer
110
, the LLC
2
protocol layer
108
a
, and the physical protocol layer
106
. By way of another example, data packet
104
d
is only associated with the LLC
2
protocol layer
108
e
and the physical protocol layer
106
.
The data queues represent any suitable queuing mechanism for holding data packets at a point above a plurality of protocol layers. For example, the data queues may simply hold the data pending transmission in the order received. In another example, the data queues may control the quality of service provided to data pending transmission by organizing data into a plurality of queues that each assert a claim of dynamic strength on an opportunity to send. The data queues may be associated or located on any suitable type of data transmission device, such as a router device. A router is defined loosely as meaning any network node for receiving and transmitting data packets from and to another network node.
Each of the protocol layers typically communicate with other similar protocol layers (herein referred to as “peer entities”) within other network devices. For example, the X.25 protocol layer
110
may communicate with another network device, which communication is represented by a virtual communication bus
114
. Actually, the X.25 protocol layer
100
communicates with another peer X.25 protocol layer through the LLC
2
protocol layer
108
a
, the physical protocol layer
106
, the peer physical protocol layer, and peer LLC
2
protocol layer. Likewise, the LLC
2
protocol layers
108
a
and
108
b
each communicate with a peer LLC
2
protocol layer, which communications are represented by virtual communication lines
116
a
and
116
b
, respectively. Physical layer
106
is configured to communicate with other peer physical layers of other network hardware devices through communication line
118
.
A protocol context communicates with a peer context on another network node by using its lower layer protocol context(s). The conversation commonly includes control information, as well as the user data that is carried on behalf of the context's own overlying protocol context(s). The context control information is originated and terminated by the contexts, whereas the user data is sent from and received by the user(s) of the protocol context in the network node.
Both the user data and control data are commonly presented as user data to the underlying protocol context. A protocol context may be required to prohibit user data communication (e.g., it is congested) while remaining capable of exchanging control information. Thus, a protocol context may need to determine whether it's underlying protocol context path is capable of sending control information while maintaining its own context congestion status of being unable to accept user data. Any user data already accepted and queued by a protocol context may be considered control information and may be sent while the context remains unable to accept additional user data.
Peer protocol layers from different network devices or nodes typically pass control information back and forth through its lower protocol context(s) or layers. For example, a first node's LLC
2
protocol context may transmit control data to a second node's LLC
2
protocol context to indicate that the second node LLC
2
protocol context should cease packet transmission. Likewise, the first node's LLC
2
protocol context may transmit information that indicates that the second node's LLC
2
context may resume transmission. Since flow control information is generally time-sensitive, transmission of such flow control information should not be unduly delayed.
Data packets are typically sent to the next protocol layer of an associated protocol stack as soon as the data queue is ready to send and the next protocol layer is ready to accept the data packets. For example, data packet
104
e
is sent to VC protocol context
112
b
. The data packet is then sent to the next protocol layer as soon as the current protocol layer is able to send and/or the next protocol level is ready to accept. If the next protocol level (e.g., the X.25 protocol
110
) is unable to accept the data packet, the data packet is held within a queue of the protocol context itself. For example, if the X.25 protocol context
110
is unable to accept data packets, data packets are held within a queue of VC protocol context
112
b
. In sum, data packets are held within each protocol queue until a next protocol context is able to accept them.
Although conventional data packet transmission approaches work well under certain conditions, these approaches have associated disadvantages. For example, since data packets are typically sent to the next protocol level as soon as the next level is able to accept data packets, so-called “time warp” effects may occur. That is, when a particular protocol context transfers a data packet downstream to a next protocol context, the particular protocol context loses control of the data packet. Thus, if
Beyer Weaver & Thomas LLP.
Cisco Technology Inc.
Ngo Ricky
Olynick, Esq. Mary R.
LandOfFree
Methods and apparatus for controlling congestion within... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for controlling congestion within..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for controlling congestion within... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3052643