Electrical computers and digital data processing systems: input/ – Intrasystem connection – Bus access regulation
Reexamination Certificate
2000-04-11
2004-07-27
Auve, Glenn A. (Department: 2112)
Electrical computers and digital data processing systems: input/
Intrasystem connection
Bus access regulation
C710S111000, C710S310000, C370S395300, C370S412000
Reexamination Certificate
active
06769043
ABSTRACT:
BACKGROUND OF THE INVENTION
Digital networks, including local area networks (LANs), wide area networks (WANs), and of course, the Internet, serve to connect various devices which communicate with each other using digital signals. The capacity or bandwidth of a network link dictates how much information it can carry at any given time. Devices known as routers typically form the nodes to which the network links connect. Such a node may be connected to other network nodes, or directly to local traffic. Various protocols are used along the various paths, and even over the same paths.
Asynchronous transfer mode (ATM) is a cell-based networking technology which supports many types of information transfers at very high speeds. Messages are broken into “cells” of 53 8-bit “octets”, a 5-byte header and a 48-byte information payload. The header includes a generic flow control (GFC) field and a virtual channel identifier (VCI) field, as well as other fields.
Subtending is a mechanism which allows the linking of a number of interface units into one network trunk port by allowing “lower-level” interface units to connect to “higher-level” units, so that ultimately all of the traffic handled at a particular site passes to the trunk through a single interface unit. This feature allows improved per-port costs for service providers by reducing the number of ports required in an aggregator network where multiple interfaces are installed in one location. Subtending links one or more interface units in one area into one network trunk connection.
One of the most common problems in connecting networking systems together through subtending is known as the “parking lot” problem. As each system gets further away from the trunk interface, it only receives half of the available upstream bandwidth from the system above it. A system once removed from the trunk receives ½ of the available upstream bandwidth, while a system twice removed receives ¼ of the available upstream bandwidth, etc.
Most ATM architectures solve this problem using per VC queuing, in which a separate queue is maintained for every virtual channel. However, per VC queuing is complex and costly.
SUMMARY OF THE INVENTION
To avoid the parking lot problem, upstream traffic is enqueued by its source interface unit in the chain. A round robin scheduler is used to dequeue the traffic and send it to the interface unit above it giving each interface unit an equal share of the available upstream bandwidth. To ensure fairness between each interface unit and the traffic local to the interface unit the round robin scheduler is rate locked to the speed of the local trunk.
In an asynchronous transfer mode (ATM) environment, an interface unit identifier is stored in the generic flow control (GFC) field of each ATM cell. This identifier is passed on until it is received at the interface unit connecting to the network trunk, at which point the GFC field can be cleared for transmission of the cell.
Input queues are used to queue ATM cells received from lower level, or subtended, units as well as ATM cells received from local traffic. Each interface unit has at least an input queue for each subtended interface unit, plus an input queue for its own local traffic. As cells are received from each interface unit, they are stored in the appropriate input queue based on the identifier in the GFC field of the ATM header.
Accordingly, to ensure fair access to upstream trunk bandwidth among a plurality of interface units, a plurality of queues is provided in a first unit. One of the queues is associated with the first interface unit. Each of the remaining queues is associated with one of a plurality of second interface units. Local data is received by the first interface unit and forwarded to the respective queue. Data received from a second, subtended interface unit is forwarded to a queue which is associated with the second interface unit. Data is then issued from the queues according to a fairness algorithm.
In one embodiment, a unique identifier is assigned to each interface unit. Associating a queue with an interface unit is done by associating the queue with the respective interface unit's identifier. In each interface unit, local data is tagged with that interface unit's identifier, and received data is forwarded to a queue according to the data's tag.
Where data is formatted as asynchronous transfer mode (ATM) cells, it can be tagged by inserting the receiving interface unit's identifier into the generic flow control (GFC) field of each cell.
Alternatively, a table of associations between virtual channel identifiers (VCIs) and interface unit identifiers can be maintained. The received data is forwarded to a queue according to the interface unit identifier associated with the data's VCI.
In one embodiment, the fairness algorithm is a round robin algorithm.
Interface units may be interconnected such that a top-level interface unit connects to a network trunk, while each non-top-level interface unit connects directly to an interface unit at a next higher level.
The interface units can be arranged in a tree, daisy-chain or star configuration.
Each queue can also be divided into two or more sub-queues, each sub-queue associated with a different priority. Data is then issued from a queue's highest priority sub-queue that contains data.
One advantage of the present invention is configurability. The user need only specify a unique interface unit identifier through, for example, a command line interface. Software and hardware execute the algorithm without any further intervention.
Another advantage is that the algorithm of the present invention works for any trunk speed. As users move from slower (T
1
) to faster (OC
3
) trunk interfaces, they need not reconfigure the box. The hardware is self-timed to the speed of the trunk interface and always ensures fairness.
Another advantage is that because any unit can operate as fast as its subtended link speed, units at the bottom of a tree topology can send data upstream as fast as its subtended link. If no other units in the system are sending traffic upstream, the bottom or lowest-level unit will have full bandwidth use of the upstream network trunk.
Another advantage is that the present invention works well regardless of topology, e.g., a star, tree, or daisy chained topology. The fairness algorithm remains unchanged.
An embodiment of the present invention also supports priority among the various subscribers in a subtended configuration as well. If a subscriber at the bottom interface unit is running high priority voice traffic, while a subscriber at the top unit is running low priority TCP/IP traffic, the high priority traffic will take precedence over the lower priority traffic within the subtended configuration. This results because the input queues are actually per priority per interface unit input queues. Higher priority traffic accesses the upstream trunk bandwidth before lower priority traffic.
REFERENCES:
patent: 4866758 (1989-09-01), Heinzelmann
patent: 5231633 (1993-07-01), Hluchyj et al.
patent: 5506847 (1996-04-01), Shobatake
patent: 5613136 (1997-03-01), Casavant et al.
patent: 5625865 (1997-04-01), Moehrmann
patent: 5812550 (1998-09-01), Sohn et al.
patent: 5862136 (1999-01-01), Irwin
patent: 5870629 (1999-02-01), Borden et al.
patent: 5872938 (1999-02-01), Williams
patent: 5970062 (1999-10-01), Bauchot
patent: 6138172 (2000-10-01), Shimonishi
patent: 6175867 (2001-01-01), Taghadoss
patent: 6192422 (2001-02-01), Daines et al.
patent: 6266324 (2001-07-01), Kirino et al.
patent: 6301630 (2001-10-01), Chen et al.
patent: 6407992 (2002-06-01), Pasternak et al.
patent: 6408341 (2002-06-01), Feeney et al.
patent: 6411627 (2002-06-01), Hullett et al.
patent: 6418459 (2002-07-01), Gulick
patent: 6452933 (2002-09-01), Duffield et al.
patent: 6608813 (2003-08-01), Chiussi et al.
“NI-2 Card Installation and Configuration for the Cisco 6260,” Cisco Systems, Sep. 7, 1999, pp. 1-22.
Fedorkow Guy C.
Hoult Kent H.
Joyce John A.
Milano Michael B.
Savla Vijay J.
Auve Glenn A.
Cisco Technology Inc.
Hamilton Brook Smith & Reynolds P.C.
Lee Christopher E.
LandOfFree
Ensuring fair access to upstream trunk bandwidth in ATM... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Ensuring fair access to upstream trunk bandwidth in ATM..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ensuring fair access to upstream trunk bandwidth in ATM... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3237546