Source: http://www.google.com/patents/US7639614?ie=ISO-8859-1&dq=6861155
Timestamp: 2014-07-11 11:58:37
Document Index: 266950789

Matched Legal Cases: ['art 300', 'art 300', 'art 400', 'art 400', 'art 500', 'art 500', 'art 600', 'art 600', 'art 700', 'art 700']

Patent US7639614 - Distribution-tuning mechanism for link aggregation group management - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsIn a link aggregation group aggregating a number of ports of a network element, the network element may distribute frames among the ports using a distribution function that operates according to information in the received frames. The network element may apply one of several different distribution functions...http://www.google.com/patents/US7639614?utm_source=gb-gplus-sharePatent US7639614 - Distribution-tuning mechanism for link aggregation group managementAdvanced Patent SearchPublication numberUS7639614 B2Publication typeGrantApplication numberUS 11/394,908Publication dateDec 29, 2009Filing dateMar 31, 2006Priority dateApr 12, 2005Fee statusPaidAlso published asEP1713216A1, US20060251106Publication number11394908, 394908, US 7639614 B2, US 7639614B2, US-B2-7639614, US7639614 B2, US7639614B2InventorsYukihiro Nakagawa, Takeshi ShimizuOriginal AssigneeFujitsu LimitedExport CitationBiBTeX, EndNote, RefManPatent Citations (17), Non-Patent Citations (15), Referenced by (7), Classifications (21), Legal Events (2) External Links: USPTO, USPTO Assignment, EspacenetDistribution-tuning mechanism for link aggregation group managementUS 7639614 B2Abstract In a link aggregation group aggregating a number of ports of a network element, the network element may distribute frames among the ports using a distribution function that operates according to information in the received frames. The network element may apply one of several different distribution functions and, at appropriate times, change the selected distribution function to effect a different distribution of frames among the ports.
1. A method for distributing frames among links in a link aggregation group comprising:
after disabling distribution of frames among the ports, dropping frames remaining in one or more output queues;
3. The method of claim 1, further comprising, after determining to adjust the selected distribution function:
4. The method of claim 1, wherein determining to adjust the selected distribution function comprises receiving a notice from a network management device.
5. The method of claim 4, wherein the notice identifies one of the distribution functions.
6. The method of claim 1, wherein the selected distribution function operates in conjunction with a distribution parameter, the method further comprising selecting a value for the distribution parameter.
8. The method of claim 1, wherein each of the distribution functions operates to distribute frames among the ports based on addressing information specified in the frames.
the frame distributor operable to select one of the distribution functions as a selected distribution function, to distribute received frames among the aggregated ports in accordance with the selected distribution function, to determine to adjust the selected distribution function, after determining to adjust the selected distribution function, to disable distribution of frames among the aggregated ports, after disabling distribution of frames among the aggregated ports to drop frames remaining in one or more output queues, to select a different one of the distribution functions as the selected distribution function, and to enable distribution of received frames among the aggregated ports in accordance with the selected distribution function after selecting the different one of the distribution functions as the selected distribution function.
10. The network element of claim 9, further comprising a controller operable to monitor performance of the link aggregation group to detect underutilization of one or more links in the link aggregation group and to determine to adjust the selected distribution function in response to the performance.
11. The network element of claim 9, wherein:
12. The network element of claim 9, wherein the frame distributor is further operable to determine to adjust the selected distribution function in response to receiving a notice from a network management device.
13. The network element of claim 12, wherein the notice identifies one of the distribution functions.
14. The network element of claim 9, wherein the selected distribution function operates in conjunction with a distribution parameter, the frame distributor further operable to select a value for the distribution parameter.
15. The network element of claim 9, wherein each of the distribution functions operates to distribute frames among the aggregated ports based on addressing information specified in the frames.
16. A computer readable medium encoding software for distributing frames among links in a link aggregation group, which when executed by a computer causes the computer to perform the steps of:
17. The computer readable medium of claim 16, further operable when executed to perform the steps of:
18. The computer readable medium of claim 16, wherein the selected distribution function operates in conjunction with a distribution parameter, the logic further operable when executed to identify a value for the distribution parameter.
19. The computer readable medium of claim 16, wherein each of the distribution functions operates to distribute frames among the ports based on addressing information specified in the frames.
means for, after determining to adjust the selected distribution function, disabling distribution of frames among the ports; after disabling distribution of frames among the ports,
means for after disabling distribution of frames among the ports, dropping frames remaining in one or more output queues;
means for enabling distribution of received frames among the ports in accordance with the selected distribution function after selecting the different one of the distribution functions as the selected distribution function. Description
RELATED APPLICATION This Application claims the benefit under 35 U.S.C. � 119(e) of U.S. Provisional Application Ser. No. 60/670,369 entitled �Link Aggregation and Network Management Techniques,� filed on Apr. 12, 2005 and incorporated by reference herein.
TECHNICAL FIELD OF THE INVENTION The present invention relates generally to network management and, more particularly, to a distribution-tuning mechanism for link aggregation group management.
BACKGROUND OF THE INVENTION A link aggregation group (LAG) combines multiple physical, network links into a single, logical link that provides aggregated throughput and high availability to endpoints. Communication between two endpoints occurs over the single, logical link of the LAG. The distribution of communications among physical links of the LAG may vary depending on the number and arrangement of endpoints communicating across the LAG.
SUMMARY OF THE INVENTION In accordance with the present invention, a distribution-tuning mechanism for link aggregation group management is provided.
FIG. 1 illustrates a communication system that includes a LAG that implements a purge mechanism in accordance with particular embodiments of the present invention;
FIG. 2 illustrates an example network element from the system of FIG. 1;
FIG. 3 is a flowchart illustrating a method for moving a conversation between ports with the purge mechanism using a frame distributor at a transmitting network element;
FIG. 4 is a flowchart illustrating a method for responding to a determination to move the conversation between ports with the purge mechanism using a frame collector at a receiving network element;
FIG. 5 is a flowchart illustrating a method for implementing a distribution tuning mechanism for the LAG;
FIG. 6 is a flowchart illustrating a method for implementing a special marker message using the frame distributor at the transmitting network element; and
FIG. 7 is a flowchart illustrating a method for responding to a special marker message using the frame collector at the receiving network element.
DETAILED DESCRIPTION OF THE DRAWINGS FIG. 1 illustrates a communication system, indicated generally at 10, that includes a LAG that implements a purge mechanism. Endpoints 18 communicate with each other over network 12 using network elements 16. In general, network elements 16 provide for the formation of a LAG to enable high speed communications between endpoints 18. To support the operation of LAGs, network elements 16 may implement techniques including: a purge mechanism to enable quick movement of conversations among links in a LAG, an extended marker protocol to enable effective movement of communications from failed or otherwise inactive links in a LAG, and tuning of distribution algorithms to help support efficient and full use links in a LAG. Network elements 16 may implement some or all of these techniques to support the operation of LAGs.
Network element 16 represents network communications equipment, including appropriate controlling logic, that facilitates the communication between endpoints 18. For example, network elements 16 may include switches, routers, gateways, servers, or other suitable network equipment. According to particular embodiments, network elements 16 communicate with each other by way of high-speed electrical signals. In the illustrated embodiment, a LAG 15 is formed between network elements 16 a and 16 b to provide increased bandwidth and increased availability during communication. According to particular embodiments, network element 16 a negotiates LAG 15 with another link-aggregation enabled network element 16 b. To form LAG 15, one or more physical links 17 between network elements 16 are aggregated together.
According to particular embodiments, components within system 10 communicate frames using Ethernet standards. A frame includes any suitable segmentation of data, such as packets, frames, or cells. Moreover, Ethernet and Ethernet standards include communication protocols that have been developed to handle transmission of frames between components, including any extensions, add-ons, and/or future developments that may occur with respect to these protocols. For example, Ethernet standards encompass the protocols set forth within the IEEE 802.3 and supplements.
As noted above, LAGs 15 function as single logical links formed from multiple individual physical links 17 coupling between network elements 16. During operation, two network elements 16 coupled by a particular LAG 15 may treat that LAG 15 as a single physical connection, potentially with some restrictions. As an example of operation, consider endpoint 18 a communicating with endpoint 18 b over network 12, and links 17 a-17 c between network elements 16 a and 16 b aggregated to form LAG 15. The communication between network element 16 a and network element 16 b may be referred to as a conversation. According to particular embodiments, network elements 16 maintain each conversation on a single link 17 within a given LAG 15. This can help to maintain frame ordering within a conversation. If conversations are unevenly distributed among links 17 in LAG 15, this can result in poor utilization of the full bandwidth of LAG 15. In addition, failure of one link 17 will potentially cut off conversations occurring over that link 17. Thus, in response to link failure, poor link utilization, reconfigurations, or other suitable conditions, conversations may be switched among links 17 within LAG 15.
For normal movement of communications between links 17 within LAG 15, network elements 16 may support a marker protocol, which may be based on a standard, such as the Institute of Electrical and Electronics Engineers, Inc. (IEEE) 802.3 Clause 43. Continuing the example from above, assume that the conversation between endpoint 18 a and endpoint 18 b involves a stream of frames communicated from endpoint 18 a to endpoint 18 b, and that network element 16 a transmits these frames to network element 16 b using link 17 a. In response to a failure of link 17 a, redistribution of conversations, or other appropriate circumstances, network element 16 a may determine to move the conversation on link 17 a to another link 17 in LAG 15.
To enable quick movement of the conversation (or multiple conversations), network element 16 a may use a purge mechanism. In an example embodiment, the purge mechanism includes disabling distribution of additional frames to the output queues associated with link 17 a and potentially the dropping of some or all frames from the output queues associated with link 17 a. Network element 16 a sends a message to network element 16 b regarding moving the conversation. For example, network element 16 a may send a marker message to network element 16 b using an administrative queue associated with link 17 a. When network element 16 b responds to the message, network element 16 a may move the conversation to another link 17 within LAG 15. The use of marker messages and marker responses can help to ensure the appropriate ordering of frames transmitted on LAG 15. By implementing the purge mechanism, conversations can be quickly moved between links 17.
According to particular embodiments, network element 16 a moves all conversations occurring on link 17 a using the purge mechanism. For example, network elements 16 a may move multiple conversations from link 17 a to link 17 c, or may spread conversations among two or more other links 17 in the given LAG 15. In addition, network elements 16 may use the purge mechanism concurrently on multiple different links 17. For example, network element 16 may use the purge mechanism on all links 17 in LAG 15 in conjunction with the redistribution of conversations among links 17 based on a change in the distribution algorithm.
FIG. 2 illustrates an example network element 16 from system 10 of FIG. 1. Network element 16 may include any appropriate combination and arrangement of components and modules. In the illustrated embodiment, network element 16 includes a LAG element 20 that facilitates the formation of LAG 15, a network element controller 21 to manage the operation of components within network element 16, and ports 22 that communicate over links 17, which aggregate to form LAG 15. LAG element 20 includes a LAG controller 24 and one or more LAG modules 26. Each LAG module 26 includes a Media Access Control (MAC) client 28 and an aggregator 30, which includes a frame distributor 32 and a frame collector 34. Port 22 includes one or more output queues 50, a central processing unit (CPU) queue 52, and an input queue 54 that facilitate the communication of frames 56. In general, the components within network element 16 facilitate the communication between endpoints 18 over network 12. More specifically, the components within network element 16 provide a purge mechanism that facilitates moving of conversations between links 17 in LAG 15.
Each negotiated LAG 15 has an associated module 26, which may be a logical depiction, in element 20. Module 26 facilitates functionality of its associated LAG 15 and provides for the implementation of varying features within LAG 15. For example, when links 17 are active, communications occurring on link 17 a within LAG 15 may be moved to link 17 c using module 26. As another example, if link 17 a fails during communication, the communication on link 17 a may be moved to link 17 c using module 26.
As discussed above, network elements 16 support a marker protocol and an extended marker protocol. Both protocols provide for communications among aggregations. Using these protocols, for example, frame distributor 32 of network element 16 a generates and distributes a marker, using marker protocol or the extended marker protocol, to frame collector 34 of network element 16 b. Frame collector 34 of network element 16 b distributes a marker response, using marker protocol or extended marker protocol, to frame distributor 32 of network element 16 a. Messages, including a marker and a marker response, in marker protocol may have any suitable format. As discussed above, marker protocol provides for moving conversations between links 17 within LAG 15. Using marker protocol, controller 24 generates and transmits a marker on one or more active links 17 within LAG 15. Frame collector 34 in the receiving network element 16 provides a maker response to frame distributor 32 in the transmitting network element 16. During the process of moving conversations from one link 17, conversations on other links 17 may continue without interruption. Alternatively, network element 16 may use the marker protocol to shift conversations among two or more links 17 in the associated LAG 15. For example, controller 24 may generate and transmit marker messages on one or more links 17 and, after receiving responses, move conversations occurring on those links 17.
Destination Address = MAC address of the destination port Source Address = MAC address of a non-failed source port Type = 0x8809 Subtype = Marker Protocol Version = 0x01 TLV: Marker Information = 0x01, Marker Response = 0x02, Special Marker = 0x03, Special Marker Response = 0x04 Information Length = 0x10 (1610) Requester Port Requester System Requester Transaction ID = Failed port for special messages Pad = 0x0000 Terminator = 0x00 Terminator Length = 0x00 Reserved Frame Check Sequence As discussed above, the extended marker protocol may be used when link 17 fails, or is otherwise inactivated, and conversations are to be moved to one or more active links 17. In accordance with one embodiment of the extended marker protocol, frame distributor 32 in network element 16 a in provides a special marker on an active link 17 within LAG 15. Frame collector 34 in network element 16 b provides a special marker response to frame distributor 32. During the process of moving conversations from one link 17, conversations on other links 17 may continue without interruption. In the alternative, network element 16 may use the extended marker protocol to shift conversations among two or more links 17 in the associated LAG 15. For example, controller 24 may generate and transmit marker messages on one or more links 17 and, after receiving responses, move conversations occurring on those links 17.
FIG. 3 is a flowchart 300 illustrating a method for moving a conversation between ports 22 with the purge mechanism using frame distributor 32 at transmitting network element 16. The following description of flowchart 300 is provided with reference to frame distributor 32 of network element 16 as described above. However, any appropriate element or combination of elements may implement the steps as described below.
FIG. 4 is a flowchart 400 illustrating a method for responding to a determination to move the conversation between ports 22 with the purge mechanism using frame collector 34 at receiving network element 16. The following description of flowchart 400 is provided with reference to frame collector 34 of network element 16 as described above. However, any appropriate element or combination of elements may implement the actions as follows.
FIG. 5 is a flowchart 500 illustrating a method for implementing a distribution tuning mechanism in LAG 15. The following description of flowchart 500 is provided with reference to network element 16 as described above. However, any appropriate element or combination of elements may implement the steps as described below.
FIG. 6 is a flowchart 600 illustrating a method for implementing a special marker message using frame distributor 32 at transmitting network element 16. The following description of flowchart 600 is provided with reference to frame distributor 32 of network element 16 as described above. However, any appropriate element or combination of elements may implement the steps as described below.
FIG. 7 is a flowchart 700 illustrating a method for responding to the special marker message using frame collector 34 at receiving network element 16. The following description of flowchart 700 is provided with reference to frame collector 34 of network element 16 as described above. However, any appropriate element or combination of elements may implement the actions as follows.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS5959968Jul 30, 1997Sep 28, 1999Cisco Systems, Inc.Port aggregation protocolUS6498781 *Aug 13, 1999Dec 24, 2002International Business Machines CorporationSelf-tuning link aggregation systemUS6501749Jun 25, 1999Dec 31, 2002International Business Machines CorporationSystem and method for data transmission across a link aggregationUS6504843 *Jul 14, 1999Jan 7, 20033Com TechnologiesSystem and method for dynamically mapping a high speed link to a multiplicity of low speed trunked linksUS6532229Jan 15, 1999Mar 11, 2003Brian Weatherred JohnsonLow cost link aggregation method and systemUS6535489May 21, 1999Mar 18, 2003Advanced Micro Devices, Inc.Method and apparatus in a network switch for handling link failure and link recovery in a trunked data pathUS6862293Nov 13, 2001Mar 1, 2005Mcdata CorporationMethod and apparatus for providing optimized high speed link utilizationUS6934293 *Oct 10, 2003Aug 23, 2005Cisco Technology, Inc.Port aggregation load balancingUS6990068Dec 30, 2000Jan 24, 2006Cisco Technology, Inc.Virtual path restoration scheme using fast dynamic mesh restoration in an optical networkUS7050392Oct 6, 2001May 23, 2006Brocade Communications Systems, Inc.In-order delivery of frames during topology changeUS20040252639Feb 17, 2004Dec 16, 2004Van HunterLoad sharing/trunking in a communication deviceUS20050213573 *Sep 30, 2004Sep 29, 2005Shunichi ShibataCommunication terminal, load distribution method and load distribution processing programUS20060153186 *Dec 29, 2004Jul 13, 2006Cisco Technology, Inc.In-order fibre channel packet deliveryCA2459027A1Jun 15, 2001Dec 15, 2002Tropic Networks IncExtension of link aggregation protocols over the network anda switching node thereforEP1300992A1Oct 8, 2001Apr 9, 2003Alcatel Alsthom Compagnie Generale D'electriciteMethod for distributing load over multiple shared resources in a communication network and network applying such a methodWO2000056013A2Mar 17, 2000Sep 21, 2000Broadcom CorpMethod for avoiding out-of-ordering of frames in a network switchWO2005022826A2Sep 3, 2004Mar 10, 2005Siemens AgSimple and resource-efficient resilient network systems* Cited by examinerNon-Patent CitationsReference1Chim et al., "Traffic Distribution over Equal-Cost-Multi-Paths," IEEE Communications Society, pp. 1207-1211, 2004.2EPO European Search Report for Application No. EP 06 00 7590, Patent No. 06007590.0-2416, Reference No. 114 574 a/npo, Applicant: Fujitsu Ltd., 8 pages, Jun. 28, 2006.3EPO European Search Report for Application No./Patent No. 06007588.4-2416, Reference No. 114 514 a/lga, Applicant: Fujitsu Ltd., 8 pages, Jan. 8, 2006.4EPO European Search Report for Application No./Patent No. 06007595.9-2416, Reference No. 114 575 a/lga, Applicant: Fijitsu Ltd., 7 pages, Jan. 8, 2006.5Finn, "Port Aggregation Protocol," IEEE 802.3ad Workshop Group, Cisco, pp. 1-27, May 1, 1998.6Lan Man Standards Committee, "Amendment to Carrier Sense Multiple Access with Collision Detection (CSMA/CD) Access Method and Physical Layer Specifications-Aggregation of Multiple Lnk Segments," IEEE Std 802.3ad-2000, 182 pages (173 plus 9 pages of title and index), Mar. 30, 2000.7Patent Pending U.S. Appl. No. 11/278,751, entitled "Filtering Frames at an Input Port of a Switch," by Takeshi Shimizu, 24 pages plus 3 pages of drawings, filed Apr. 5, 2006.8Patent Pending U.S. Appl. No. 11/394,892, entitled "Purge Mechanism in Link Aggregation Group Management," by Yukihiro Nakagawa et al., 32 pages plus 6 pages of drawings, filed Mar. 31, 2006.9Patent Pending U.S. Appl. No. 11/394,960, entitled "Special Marker Message for Link Aggregation Marker Protocol," by Yukihiro Nagawa et al., 32 pages plus 6 pages of drawings, filed Mar. 31, 2006.10Patent Pending U.S. Appl. No. 11/398,257, entitled "Network Based Routing Scheme," by Takeshi Shimizu, 34 pages plus 5 pages of drawings, filed Apr. 4, 2006.11Rost et al., "Rate-Aware Splitting of Aggregate Traffic," XP-002390208, MIT Laboratory for Computer Science, pp. 1-12, Dec. 2003.12The State Intellectual Property Office of China, Office Action, 12 pages, Dec. 21, 2007.13USPTO Office Action for U.S. Appl. No. 11/394,892, Nakagawa, Oct. 2, 2008.14USPTO Office Action for U.S. Appl. No. 11/394,960, Nakagawa, Oct. 14, 2008.15 *Various Authors, IEEE Standard 802.3ad, Mar. 30, 2000, IEEE, pp. 97-117 and 159-173.* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS8264953 *Sep 5, 2008Sep 11, 2012Harris Stratex Networks, Inc.Resilient data communications with physical layer link aggregation, extended failure detection and load balancingUS8264959Jun 15, 2010Sep 11, 2012Harris Stratex Networks Operating CorporationDynamic load balancing for layer-2 link aggregationUS8614950 *Nov 29, 2011Dec 24, 2013Marvell Israel (M.I.S.L) Ltd.Load balancing hash computation for network switchesUS8660005Nov 29, 2011Feb 25, 2014Marvell Israel (M.I.S.L) Ltd.Load balancing hash computation for network switchesUS8693308Feb 10, 2006Apr 8, 2014Aviat U.S., Inc.System and method for resilient wireless packet communicationsUS20120134262 *Nov 28, 2011May 31, 2012Harris Stratex Networks, Inc.Resilient Data Communications with Physical Layer Link Aggregation, Extended Failure Detection and Load BalancingUS20120134497 *Nov 29, 2011May 31, 2012Amir RoitshteinLoad balancing hash computation for network switches* Cited by examinerClassifications U.S. Classification370/232, 370/542International ClassificationG08C15/00, G01R31/08, H04L12/16, H04L12/26, G06F11/00, H04J3/14, H04J3/02, H04J1/16, H04L1/00, H04L12/28Cooperative ClassificationH04L45/245, H04L45/00, Y02B60/33, H04L45/52, H04L45/04European ClassificationH04L45/04, H04L45/52, H04L45/00, H04L45/24ALegal EventsDateCodeEventDescriptionMar 11, 2013FPAYFee paymentYear of fee payment: 4Mar 31, 2006ASAssignmentOwner name: FUJITSU LIMITED, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:NAKAGAWA, YUKIHIRO;SHIMIZU, TAKESHI;REEL/FRAME:017756/0264Effective date: 20060331RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google