Dynamic bidding protocol for conducting multilink sessions through different physical termination points

• US 6,073,176 A
• Filed: 04/30/1997
• Issued: 06/06/2000
• Est. Priority Date: 07/29/1996
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Yiu, Shoou Jiah, Leung, Pokman Perry, Baindur, Ashwin, Harvey, Andrew G., Valencia, Andrew J.
• Primary Examiner(s): Asta, Frank J.
• Assistant Examiner(s): WILLETT, STEPHAN F
• Application Number:
  US08/846,788
• Time in Patent Office: 1,133 Days
• Field of Search: 709/218, 709/227, 709/226, 709/225, 709/235, 709/249
• US Class Current: 709/227
• CPC Class Codes: H04L 12/2856 Access arrangements, e.g. Internet access asynchronous transfer mode networks H04L12/5601; broadband local area networks H04L12/2801; optical access or distribution networks H04Q11/0067; access to open networks H04L12/5691; digital subscriber line end-user equipment and bit-level processing of data on a PSTN-based network H04M11/00; home network gateways H04L12/2834; wireless access networks H04W
• CPC Class Codes: H04L 12/2859 Point-to-point connection between the data network and the subscribers encapsulation H04L12/4633; virtual LANs H04L12/4641; routing of packets H04L45/00
• CPC Class Codes: H04L 12/2872 Termination of subscriber connections
• CPC Class Codes: H04L 63/083 using passwords cryptographic mechanisms or cryptographic arrangements for entity authentication using a predetermined code H04L9/3226
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

A stack group bidding protocol (SGBP) establishes systems as members of a stack group connected together through one or more networks. When an event, such as establishment of a point-to-point link, occurs on one of the systems, a bid request is sent to each stack group member. Each stack group member then bids for the event. The bid is based on dynamic bid weighting criteria that varies depending on the computation capacity of the member at the time the bid request is initiated. A multichassis multilink PPP (MLP) protocol utilizes the SGBP to conduct multilink PPP sessions for links that either originate or terminate on different physical systems. A L2F forwarding protocol is used in combination with multichassis MLP to forward the links from one system to another system and offers location transparency.

Claims

1. A method for conducting a multilink session between multiple systems connected together on a network, comprising:

identifying establishment of a first communication link on a first one of the multiple systems;

identifying establishment of a second communication link on a second one of the multiple systems, the first and second communication link establishing a multilink bundle;

initiating a bidding session for obtaining bid values associated with each one of the multiple systems, the bid values each identifying a priority of the associated one of the multiple systems for being a bundle master that processes all links in the multilink bundle;

comparing the bid values associated with each one of the multiple systems;

establishing one of the multiple systems having a highest priority bid value as the bundle master; and

initiating the first and second one of the multiple systems to forward to the assigned bundle master any of the first communication link and second communication link not terminating on the bundle master after the first communication link is terminated on the first one of the multiple systems and the second communication link is terminated on the second one of the multiple systems, the bundle master then conducting the multilink session by combining packets from the first communication link and with the second communication link.

2. A method according to claim 1 wherein the first communication link and the second communication link are each established using a multilink point-to-point protocol.

3. A method according to claim 1 wherein the step of establishing the bundle master includes the following steps:

establishing at least some of the multiple systems as stack group members;

identifying the first communication link and the second communication link as part of the multilink bundle;

determining whether the bundle master has been assigned to the multilink bundle;

sending out a bid request to each one of the identified stack group members when no bundle master is currently assigned to the multilink bundle;

receiving bids from the stack group members for mastership of the multilink bundle; and

assigning bundle master of the multilink bundle to one of the stack group members providing a highest bid value.

4. A method according to claim 3 wherein establishing stack group members comprise the following steps:

sending a random number from the first one of the multiple systems to the second one of the multiple systems;

encrypting the random number with the second system according to a password;

forwarding the encrypted random number to the first system;

independently encrypting the random number with the first system;

establishing the first and second system as stack group members when the random numbers encrypted by the first and second system match; and

establishing communication connections between the first and second system.

5. A method according to claim 3 including the following steps:

sending out the bid request from one of the stack group members first receiving a call;

receiving the bid values at the stack group member sending out the bid request;

comparing the bid values;

assigning bundle master according to the compared bid values; and

forwarding all communication links for the call to the bundle master after the communication links are terminated on the stack group members.

6. A method according to claim 3 including forwarding additional communication links associated with the multilink bundle and established on one of the systems in the stack group to the bundle master.

7. A method according to claim 3 wherein the bidding session comprises the following steps:

bidding values according to a computational power of the individual stack group members

and according to a number of multilink bundles currently being processed by the individual stack group members.

8. A method according to claim 3 including the following steps:

establishing separate tunnels between each one of the stack group members;

encapsulating a link level protocol for the communication link in a layer-two forwarding protocol; and

forwarding the encapsulated link level protocol through the tunnels to the bundle master.

22. A method according to claim 1 wherein each one of the multiple systems generates the bid values based on multiple dynamic bid weighting criteria.

23. A method according to claim 22 wherein one of the dynamic bid weighting criteria varies depending on whether the associated one of the multiple systems is currently controlling the first communication link or second communication link.

24. A method according to claim 22 wherein the dynamic bid weighting criteria varies according to a location of the associated one of the multiple systems in relation to the systems receiving the first communication link and the second communication link.

25. A method according to claim 22 wherein the dynamic bid weighting criteria varies according to a capacity of the associated one of the multiple systems for processing packets from the first communication link and the second communication link.

28. A method according to claim 1 wherein the first or second one of the multiple systems initiates the bidding session and compares the bid values.

29. A method according to claim 1 wherein a third one of the multiple systems that does not serve as a termination point for any communications link initiates the bidding session and compares the bid values.

9. A method of bidding for communication link events with a system in a network, comprising:

identifying with the system other systems in the network that are members of a common stack group;

establishing separate connections between the system and each one of the other members in the common stack group;

receiving one of the events at the system, the received event terminated at the system and identified as associated with the common stack group;

generating a bid for processing all of the events associated with the common stack group, the bid compared with bids generated by the other members of the common stack group;

processing the received event with the system and receiving and processing any other events initially received and terminated on other members of the stack group when the generated bid is the highest bid for any of the members of the stack group; and

forwarding the received event and any other events terminated at the system and associated with the stack group to another one of the members of the stack group when that other member of the stack group has the highest bid.

10. A method according to claim 9 including the following steps:

initiating a bid request from the system receiving the event to the other members of the stack group, the bid request causing the other members of the stack group to generate bids; and

receiving the generated bids from the other members of the stack group, the bids having values that vary according to user selectable default values that are preassigned to individual members of the stack group, a calibrated value that represents a processing capacity for individual members of the stack group and a dynamic variable representing a number of bundles active on the individual members of the stack group at the time the bid request is initiated;

assigning one of the members of the stack group making a highest bid as a bundle master; and

forwarding all events associated with the stack group to the assigned bundle master.

11. A method according to claim 10 wherein at least one of the events comprises establishment of a multilink point to point link.

26. A method according to claim 9 including the following:

establishing point-to-point link events from a multilink bundle between a remote client and an internet service provider using a link level protocol; and

conducting a layer 2 forwarding protocol between the internet service provider and the network that projects the point-to-point link events from the multilink bundle from the internet service provider to the network thereby creating a virtual direct dial-up session between the remote client and said local network.

12. A multichassis multiple point-to-point system, comprising:

multiple dial-in servers providing separate physical termination points for a bundle of communication links, the dial-in servers conducting a bidding session by initiating bid values associated with each one of the multiple dial-in servers, the bid values each identifying a priority of the associated one of the multiple dial-in servers for being a bundle master that processes all the communication links in the bundle, one of the dial-in servers comparing the bid values associated with each one of the multiple dial-in servers, establishing one of multiple dial-in servers having a highest priority bid value as the bundle master, and notifying the other dial-in servers of the bundle master;

the communication links in the bundle forwarded by the dial-in servers after terminating on the dial-in servers to the bundle master, the bundle master then conducting a multilink point to point session with the bundle of communication links.

13. A system according to claim 12 including a public switched telephone network coupling one or more remote clients to the multiple dial-in servers.

14. A system according to claim 12 wherein at least some of the dial-in servers are coupled together through a local network or through a wide area network.

15. A system according to claim 14 including an offload server coupled to the local network or wide area network, the offload server conducting the multilink point to point session solely with the communication links forwarded from the other dial-in servers.

16. A system, comprising;

a first interface for receiving one or more links from a remote client;

a second interface for coupling to a network; and

a processor coupled to the first and second interface, the processor identifying links belonging to a multilink bundle and sending a bid in a bidding process that is compared with other bids for mastership of the multilink bundle,

the processor forwarding the received one or more links terminated at the system and belonging to the multilink bundle to another system over the network when that other system wins mastership of the multilink bundle by generating a winning bid during the bidding process;

the processor processing the received one or more links along with processing any additional links belonging to the multilink bundle received and terminated on other systems when the processor wins mastership of the multilink bundle by generating the winning bid during the bidding process.

17. A system according to claim 16 including a memory for storing bid values that represent the system processing capacity, the bid values determining when the processor forwards links or receives links.

27. A system according to claim 17 wherein the processor and the memory conduct a layer 2 forwarding protocol that projects the links through an internet infrastructure to the network independently of an internet protocol used in the internet infrastructure.

30. A system according to claim 16 wherein the processor identifies other systems that are stack group members assigned to the multilink bundle, sends out bid requests to the identified stack group members, receives bids from the stack group members for mastership of the multilink bundle, and assigns bundle master of the multilink bundle to one of the stack group members providing a highest bid value.

31. A system according to claim 16 including a network processing node operating independently of the processor wherein the network processing node identifies other systems that are stack group members assigned to the multilink bundle, sends out bid requests to each one of the identified stack group members, receives bids from the stack group members for mastership of the multilink bundle, and assigns bundle master of the multilink bundle to one of the stack group members providing a highest bid value.

32. A system according to claim 16 wherein the processor establishes stack group members for the multilink bundle as follows:

sending a random number from the processor to at least one other system;

enabling the other system to encrypt the random number according to a password;

independently encrypting the random number with the processor;

establishing the other system as one of the stack group members when the random numbers encrypted by the processor and the other system match; and

establishing communication connections between the processor and the other system.

33. A system according to claim 16 wherein the processor sends out bid requests to other systems, the processor then receiving the bid values from the other systems, comparing the bid values, and assigning mastership of the multilink bundle according to the compared bid values.

34. A system according to claim 16 wherein the processor sends the bid according to processor computational power or according to a number of links currently being processed by the processor.

18. A method for conducting a multichassis multilink session, comprising:

establishing a stack group with multiple members of a dial-in pool;

establishing multiple communication links at the stack group members that operate together as a multilink bundle;

sending bid requests to the stack group members upon receiving the communication links;

initiating bids from the stack group members for mastership of the multilink bundle;

comparing the bids and assigning one of the stack group members making a highest bid as a bundle master;

forwarding the communication links in the bundle terminated at the stack group members to the bundle master; and

conducting the multilink session with the bundle master.

19. A method according to claim 18 including sending bid values from the stack group members that vary according to a number of active bundles on the stack group members.

20. A method according to claim 18 including sending bid values from the stack group members that equal a default value+a calibrated value-a number of active bundles on the stack group member.

21. A method according to claim 18 including manually configuring the bid value for the stack group members.

35. A computer program for use in a network processing device, said computer program, comprising:

event occurrence detection for detecting communication links that are part of a multilink bundle;

bidding initiation for initiating a bidding session that generates a bid value for the network processing device and initiates generation of bid values from other network processing devices, the bid values identifying priorities of the network processing devices for being a bundle master that processes all the communication links in the multilink bundle;

bid comparison for comparing the bid values and identifying as the bundle master one of the network processing devices having a highest bid value;

bundle master notification for notifying the network processing devices of the bundle master;

link forwarding for forwarding any of the communication links to the bundle master when the network processing device is not the bundle master; and

multilink processing for processing any communication links terminated on the network processing device and processing other communication links in the multilink bundle terminated and then forwarded from the other network processing devices when the network processing device is the bundle master.

36. A software program for operating in a network processing device, comprising:

program code for identifying other network processing devices that are members of a common stack group;

program code for establishing separate connections between each one of the other network processing devices identified as members of the common stack group;

program code for receiving one or more communications links identified as associated with the common stack group;

program code for initiating a bid for processing all communications links associated the common stack group, the bid compared with bids generated by the other members in the common stack group;

program code for processing all the communication links associated with the common stack group when the generated bid is the highest bid for any of the members in the common stack group; and

program code for forwarding any terminated communication links associated with the common stack group when another member of the common stack group generates the highest bid.