Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2000-06-13
2004-05-11
Ho, Duc (Department: 2665)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S412000, C370S429000
Reexamination Certificate
active
06735207
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to memory management and data communication networks. More particularly, the present invention relates to an apparatus and method for reducing the required number of queuing memory access cycles using a distributed queue structure in devices such as data communication network devices having multiple queues.
As is known to those of ordinary skill in the art, a network is a communication system that allows users to access resources on other computers and, exchange messages with other users. A network is typically a data communication system that links two or more computers and peripheral devices. It allows users to share resources on their own systems with other network users and to access information on centrally located systems or systems that are located at remote offices. It may provide connections to the Internet or the networks of other organizations. The network typically includes a cable that attaches to network interface cards (“NICs”) in each of the devices within the network. Users may interact with network-enabled software applications to make a network request (such as to get a file or print on a network printer). The application may also communicate with the network software, which may then interact with the network hardware to transmit information to other devices attached to the network.
Many techniques and devices are known to those of ordinary skill in the art for transmitting data between nodes in a network. For example, data may be transmitted through multiple intermediate network connection devices, such as routers and switches, located between a source node and a destination node. These intermediate network communication devices may contain one or more queues that temporarily store data awaiting transmission to another node or network communication device in the network. In networks that transmit data using an Internet Protocol (“IP”), best-effort service is typically provided by the various network nodes. Best-effort service does not provide any Quality of Service (“QOS”) guarantees for a particular data stream. Instead, best-effort service transmits data in the order it was received using a network communication device's available bandwidth.
Network communication devices that support QOS or other resource allocation techniques typically use multiple queues in which each queue is associated with a particular QOS or a particular data flow. A portion of the device's resources, such as bandwidth, are allocated to a particular queue within the device.
FIG. 1
is a block diagram illustrating an exemplary network
100
connecting a user
110
and a particular web page
120
.
FIG. 1
is an example that may be consistent with any type of network known to those of ordinary skill in the art, including a Local Area Network (“LAN”), a Wide Area Network (“WAN”), or a combination of networks, such as the Internet.
When a user
110
connects to a particular destination, such as a requested web page
120
, the connection from the user
110
to the web page
120
is typically routed through several internetworking devices such as routers
130
-A-
130
-I. Routers are typically used to connect similar and heterogeneous network segments into internetworks. For example, two LANs may be connected across a dial-up, integrated services digital network (“ISDN”), or across a leased line via routers. Routers may also be found throughout internetwork known as the Internet. End users may connect to a local Internet service provider (“ISP”) (not shown).
As shown in
FIG. 1
, multiple routes are possible to transmit information between user
110
and web page
120
. Networks are designed such that routers attempt to select the best route between computers such as the computer where user
110
is located and the computer where web page
120
is stored. For example, based on a number of factors known to those of ordinary skill in the art, the route defined by following routers
130
-A,
130
-B,
130
-C, and
130
-D may be selected. However, the use of different routing algorithms may result in the selection of the route defined by routers
130
-A,
130
-E,
130
-F, and
130
-G, or possibly even the route defined by routers
130
-A,
130
-B,
130
-H,
130
-I,
130
-F, and
130
-G. A detailed discussion of the aspects of routing algorithms that determine the optimal path between two nodes on a network is not necessary for the purposes of the present invention, and such a discussion is not provided here so as not to overcomplicate the present disclosure.
Routers such as routers
130
-A-
130
-I typically transfer information along data communication networks using formatted data packets. For example, when a “source” computer system (e.g., computer
110
in
FIG. 1
) wishes to transmit information to a “destination” computer system (e.g., computer
120
in FIG.
1
), it generates a packet header in an appropriate format which typically includes the address of the source and destination end system, and then fills the remainder of the packet with the information to be transmitted. The complete data packet is then transmitted to the router attached to (and responsible for) the source computer system, which forwards it toward the destination computer system. Packets transmitted among the routers themselves (typically referred to as “control packets”) are similarly formatted and forwarded.
When a router receives a data packet, it reads the data packet's destination address from the data packet header, and then transmits the data packet on the link leading most directly to the data packet's destination. Along the path from source to destination, a data packet may be transmitted along several links and pass through several routers, with each router on the path reading the data packet header and then forwarding the data packet on to the next “hop.”
To determine how data packets should be forwarded, each router is typically aware of the locations of the network's end systems (i.e., which routers are responsible for which end systems), the nature of the connections between the routers, and the states (e.g., operative or inoperative) of the links forming those connections. Using this information, each router can compute effective routes through the network and avoid, for example, faulty links or routers. A procedure for performing these tasks is generally known as a “routing algorithm.”
FIG. 2
is a block diagram of a sample router
130
suitable for implementing an embodiment of the present invention. For the purpose of explanation, the present invention is described as embodied in a router. However, those of ordinary skill in the art will recognize that various other network communication devices such as switches (including asynchronous transfer mode (ATM) switches and IP switches), data servers, and similar devices may embody the teachings of the present invention. In a particular embodiment of the invention, router
130
is an Internet Protocol (“IP”) router. However, those of ordinary skill in the art will recognize that the present invention can be used with various other protocols.
Referring to
FIG. 2
, router
130
is shown to include a master control processing unit (“CPU”)
210
, low and medium speed interfaces
220
, and high speed interfaces
230
. The CPU
210
may be responsible for performing such router tasks as routing table computations and network management. It may include one or more microprocessor integrated circuits selected from complex instruction set computer (“CISC”) integrated circuits, reduced instruction set computer (“RISC”) integrated circuits, or other commercially available processor integrated circuits. Non-volatile RAM and/or ROM may also form a part of CPU
210
. Those of ordinary skill in the art will recognize that there are many alternative ways in which such memory can be coupled to the system.
Interfaces
220
and
230
are typically provided as interface cards. Generally, they control the transmission and reception of data packets over the network, and sometimes support other p
Prasad Sharat Chandra
Tsai Tuchih
Cisco Technology Inc.
Ho Duc
Ritchie David B.
Thelen Reid & Priest LLP
LandOfFree
Apparatus and method for reducing queuing memory access... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for reducing queuing memory access..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for reducing queuing memory access... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3225419