Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output data buffering
Reexamination Certificate
1997-12-29
2001-04-03
Chan, Eddie (Department: 2183)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output data buffering
C710S056000, C709S234000, C370S414000, C370S444000
Reexamination Certificate
active
06212582
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a packet switching hub, and, more particularly, to flow control techniques for multi-priority, multicast traffic.
BACKGROUND OF THE INVENTION
The past years have witnessed a tremendous increase in the traffic volumes in both WANs like the Internet and also on-premise LANs like the Ethernet. This increase in traffic volume is due to new technologies, migration from a paradigm of central to distributed computing and a host of new applications. Also, the fast pace of technology growth is witnessing increasingly inter-disciplinary work in which groups of individuals from diverse groups/divisions come together for a project and disband. From a networking standpoint, this implies that the typical communities of interest (COI) such as a department no longer are the rule and in fact these COI are regularly changing. This results in severe network management problems. In addition to traffic volumes and network management problems there is also a bewildering variety of co-existing applications such as telephony, video and data networking. The seamless integration of these services poses an extreme challenge in both the premises network and the wide-area network. This has resulted in a dramatic shift from the present method of operation which typically involves routers and bridges to switching in the premises.
A type of switch architecture that has been considered is a dual-bus-based one with bus slots supporting various port cards that interface to the external world.
FIG. 1
illustrates the switching hub architecture
10
including a switch fabric which is a dual-bus architecture where all port boards
25
a
,
25
b
, . . . ,
25
n
transmit on a transmit bus
30
and receive from a separate receive bus
40
. The transmit bus
30
is looped back onto the receive bus
40
through a loop-back circuit
45
located at the far end of the bus. In the example configuration of
FIG. 1
, the busses run at multi-Gbps speed, supporting port cards with aggregate rates up to OC-12. The port cards
25
a
,
25
b
, . . . ,
25
n
are likely to have various interfaces ranging from CBR circuits like T1.5, Ethernet segments, ATM connections to desktops etc. In particular, such an architecture (or like) is considered as an attractive solution for access and backbone in campus, private or corporate networks.
Access to the bus is achieved via a variation of a round-robin discipline with priorities. Transmission on the bus is in units of envelopes which are ATM cells, e.g., wrapped in some local switch fabric headers which includes sequence numbers, flags and addressing information among other. It is assumed bus collision avoidance is accomplished by a suitable bus arbitration mechanism. The switching architecture could be employed to switch variable-sized as well as fixed size packets. On each visit of the poll to a port card, it is assumed that only one envelope is served. This is sufficient to maintain high throughput in a short backplane because the propagation delay is small and envelope transmission and arbitration by polling can be completely pipelined.
Referring back to
FIG. 1
, each port card
25
a
,
25
b
, . . . ,
25
n
interfaces to the bus via a high-speed chip indicated as respective BIC (Bus Interface Chip) chips
50
a
,
50
b
, . . . ,
50
n
that are assumed to have simple high-speed FIFO staging buffers
60
a
,
60
b
, . . . ,
60
n
, respectively, for transmission on the unidirectional bus
30
and receipt from the unidirectional bus
40
. The port cards
25
a
,
25
b
, . . . ,
25
n
each contain a large amount of slow-speed memory, e.g., indicated as RAM
75
a
,
75
b
, . . . ,
75
n
to serve as the primary buffering area to and from the actual physical ports represented as input and output arrows
31
to and from each respective RAM. Thus, the function of the BIC memory space
60
a
,
60
b
, . . . ,
60
n
is to serve as a staging area for envelopes generated on the transmit side and as a rate-converter (from the bus transmission rates to the port transmission rates) on the receive side. Due to the large potential difference in rates between the bus speed and port rates, buffer overflows are a serious issue on the receive side of the BIC.
Routing in the fabric is achieved based on a logical addressing scheme whereby an address is assigned to each “logical” egress point which represents either a port card, in which case it will be referred to as a physical address as well, a port or even an ATM connection (VP/NVCI). Note that no source addressing is used in the switch, and hence all addresses refer to an egress point. As mentioned above, this logical (physical) address is part of the local envelope header. On the receive side, BICs use this address to filter envelopes destined to them.
There are many simple techniques for implementing physical flow control schemes for unicast-type traffic, e.g., by sending out a control packet or envelope containing buffer congestion indication to the sending BIC board and, for deactivating such flow control for unicast streams by sending a flow control packet that signals deactivation for streams destined to a particular physical address. However, multicast traffic, i.e., where ATM cell traffic is sent from a single source to multiple port boards, has its unique flow control problems. In multicast, routing is accomplished by simply assigning the same logical address to multiple physical entities (ports or boards).
Since the receiving BICs are potentially distinct in their traffic patterns and congest and un-congest independently, flow control is complicated. There are several known flow control strategies, ranging from simple strategies to sophisticated strategies. Simple strategies includes transmitting at a source to conform to the slowest receiver, i.e., the sender flow controls whenever any receiver is congested. Sophisticated strategies include flow control by the sender only when a significant number of receivers are congested. Strategies of the latter type are aimed at feeding the uncongested receivers at the fastest rate possible and not penalizing them for congestion at the slower receivers. However, they suffer from the disadvantage that a reliable multicast service will now require retransmissions to the slower receivers at a later time to overcome the losses. Sophisticated schemes are too complicated to implement at the BIC level and hence a simplistic flow control strategy is desired to operate multicast control at the sender when any receiving BIC is congested and de-controlling only when all the BICs are uncongested.
It would thus be highly desirable to provide a simple flow control mechanism by which congestion status of BICs receiving multicast streams may be determined and which may be appropriately used to de-control the sender.
SUMMARY OF THE INVENTION
The present invention is an extended hybrid flow control mechanism that supports bandwidth priorities under flow control and also provides appropriate mechanisms for both unicast and multicast traffic control. As described herein, the term flow control is used to reflect control of streams within the fabric in order to manage the high-speed buffers. The extended hybrid flow control mechanism of the present invention is based on multiple pairs of buffer-occupancy thresholds. Each priority is associated with a different pair of thresholds, a high threshold activating flow control logically and a low threshold deactivating flow control physically for unicast streams and logically for multicast streams at that priority. With physical control, all streams destined to the receiver triggering the control are simultaneously controlled and de-controlled. With logical control, streams are selectively controlled based on their rates and then de-controlled. In addition to the multi-pairs of buffer occupancy thresholds, a top occupancy additional threshold is positioned to shut down all priority streams simultaneously based on the physical address of the congested buffer. This threshold is designed to protect against buffer overflows and h
Chong Song
Nagarajan Ramesh
Wang Yung-Terng
Chan Eddie
Lucent Technologies - Inc.
Patel Gautam R.
LandOfFree
Method for multi-priority, multicast flow control in a... 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 for multi-priority, multicast flow control in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for multi-priority, multicast flow control in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2516140