Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-03-31
2004-07-06
Duong, Frank (Department: 2666)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S415000
Reexamination Certificate
active
06760331
ABSTRACT:
It is respectfully suggested that it may be appropriate for the same examiner to examine both applications.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to multicast routing.
2. Related Art
Communication on a computer network is accomplished by sending messages. Messages can include one or more data packets. Packets can be of fixed or variable lengths. Cells are packets having a fixed length.
Messages have a source and at least one destination address. A computer network includes devices that direct traffic towards the destination address. A switch is one such device.
Switches have multiple input interfaces and multiple output interfaces, which may be connected in a variety of ways. A cross bar switch is designed so that every input interface can be connected to every output interface.
There are two types of network traffic. In the first type a message has only one final destination address. This is known as unicast traffic. One use of unicast traffic is point to point communication between two computers. In the second type of traffic, called multicast, a message is sent to multiple destinations. One use of multicast transmissions is when a computer user wishes to send a message over the Internet to many individuals wishing to receive the message. A switch can have both unicast input interfaces as well as multicast input interfaces; often an interface handles both unicast as well as multicast traffic.
Memory Bandwidth Limitations
There are two main types of schemes for storing messages in the known art, which are input queuing and output queuing. (Combinations are also possible). In input queuing, a packet is queued before it enters the crossbar switch, and waits in line to arrive at the head of the input queue and be sent onward to its destination across the crossbar fabric. In output queuing, packets are forwarded onto the crossbar fabric from the input interface immediately, and queued up as they arrive at their destination output.
Output queuing hits limitations in memory speed faster than does input queuing because output queuing requires a memory at the output which is capable of momentarily receiving traffic from multiple inputs (in the worst case, all inputs), and sending out traffic at the output line rate. This means the memory in an output queued scheme must be faster than the memory in an input queued scheme by a factor equal to the number of interfaces.
In order to improve efficiency and thus the general performance in the case of high performance systems, it is preferable to use input queuing to accommodate the limited memory speeds available. The following description of the Head of Line Blocking problem assumes an input queued system.
Head of Line Blocking Problem
A unicast message, having only one destination, only needs to be routed to one output interface of a switch. Messages may be simply queued in the order received until they can be transmitted through the selected output interface. A problem in the known art occurs when the message at the head of a first queue is to be sent to an output interface that is not available due to a message from another queue using the output interface. The first queue is blocked until the particular output interface is available; no messages from this queue can be sent until the first element in the queue, or “head element”, is cleared by being sent across the switch to the output interface. (The queue may be implemented with each element being a single packet or cell, or may be implemented with each element including all the packets or cells that make up a single message). If the output interface is busy for an extended period, several queues may become blocked. This is known as the Head-of-Line blocking (“HOL blocking”) problem.
A known technique for approaching the HOL blocking problem for unicast traffic is the use of virtual output queues (“VOQs”). VOQs are virtual (logical) queues maintained in software or hardware; each VOQ is associated with a physical interface. There is a one-to-one correspondence between the VOQs and possible input/output combinations. The number of VOQs needed scales arithmetically as M×N, where M and N are the number of output interfaces and input interfaces, respectively. For a crossbar switch with 16 unicast input interfaces and 16 output interfaces, commonly called a “16×16” switch, 256 VOQs are need. If a particular output interface is tied up, a virtual queue associated with some other output interface can still send messages to that other output interface.
It should be noted that although the term used is “virtual output queue”, the method is actually an input queued method, as the queues are maintained for each input interface.
The VOQ method has the drawback that it only applies to unicast routing. VOQs cannot be applied to multicast routing because for multicast the number of VOQs needed to accommodate all possible input/output combinations is prohibitively large, growing exponentially as 2
M
×N, where M is the number of output interfaces and N is the number of multicast input interfaces. For a switch with 2 input interfaces and 16 output interfaces, a total of 2×2
16
(approximately 130,000) virtual queues would be required to implement VOQs. Very large numbers of VOQs use valuable resources such as memory and chip real estate, and likely cannot fit on a single chip using current technology.
For multicast routing, it is disclosed in the above referenced, co-pending application, “Multicast Routing with Multicast Virtual Output Queues and Shortest Queue First Allocation”, to use multicast virtual output queues (“MVOQs”) to reduce Head-of-Line blocking and improve performance. MVOQs are virtual queues maintained for an input interface having multicast capability. The number of MVOQs is fewer than the 2
M
possible destination vectors for a multicast message. Because of this lack of a one-to-one correspondence between MVOQs and destination vectors, it is not possible to simply maintain dedicated queues as in the unicast/VOQ case where, for each input interface, a VOQ is dedicated to each output interface. Consequently, the problem of assigning incoming flows of messages to the limited number of MVOQs available must be solved.
The use of Shortest Queue First (SQF) Allocation to assign flows is also disclosed in the above referenced, co-pending application, “Multicast Routing with Multicast Virtual Output Queues and Shortest Queue First Allocation”. SQF allocation is intelligent and provides improved performance. However, SQF does not always provide optimal performance. SQF is responsive to the length of the virtual queues but is not directly responsive to, and cannot be customized for, characteristics of the traffic encountered or characteristics of the flows that are already in the queues.
Allocation of flows in such a manner as to improve performance for some kinds of traffic, such as non-uniformly distributed, long-lived, and bursty flows, continues to be a problem. Allocation of flows that can be customized to the traffic is desirable. Multicast transmissions are increasingly common and HOL blocking is an ongoing problem. It will become increasingly common for traffic on networks to be bursty and non-uniform due to increasing popularity of videoconferencing, IP telephony, and other long-lived communications.
Accordingly, it would be advantageous to be able to route multicast transmissions using virtual queues in a manner that further reduces HOL blocking, improves system performance, and can be adjusted for different traffic patterns.
This advantage is achieved in the invention in which vectors, called basis vectors, are associated with virtual queues and multicast flows are assigned to the nearest queue first, producing virtual queues that are distinct from each other in terms of the characteristics of the elements in the queue. Distance is measured as described in the Detailed Description below. In a preferred embodiment, vector quantization methods are used to determine the basis vectors to optimize for the traffic pattern enco
Moussavi Farshid
Shah Dhaval N.
Cesari and McKenna LLP
Cisco Technology Inc.
Duong Frank
Harper Kevin C.
LandOfFree
Multicast routing with nearest queue first allocation and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Multicast routing with nearest queue first allocation and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicast routing with nearest queue first allocation and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3218756