Self-configuring ATM network

• US 6,041,057 A
• Filed: 03/24/1997
• Issued: 03/21/2000
• Est. Priority Date: 03/24/1997
• Status: Expired due to Term

• Current Assignee: Alcatel-Lucent SA (Nokia Corporation)
• Original Assignee: Xylan Corp. (Nokia Corporation)
• Inventors: Stone, Geoffrey C.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Previl, Daniel
• Application Number:
  US08/823,078
• Time in Patent Office: 1,093 Days
• Field of Search: 370/397, 370/399, 370/402, 370/404, 370/203, 370/254, 370/396, 370/400, 370/216, 370/217, 370/218, 370/221, 370/225, 370/228, 370/237, 370/465, 370/255, 370/401
• US Class Current: 370/397
• CPC Class Codes: H04L 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• CPC Class Codes: H04L 12/4675 Dynamic sharing of VLAN information amongst network nodes configuration of the network or of network elements H04L41/08
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5642 Multicast/broadcast/point-multipoint, e.g. VOD
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Methods for configuring, maintaining connectivity in and utilizing an ATM network. Neighboring switches share topology information and enable links to neighboring switches for tag switching. Point-to-point tagged virtual connections are established between switches on the best and next-best paths learned from topology information. Point-to-multipoint tagged virtual connections are established on the spanning tree path. Multiple tag allocation requests are included in a single message to preserve bandwidth. Next-best paths are established to reduce latency in event of link failure. Forwarding operations may be performed in hardware to reduce latency during message forwarding.

Claims

1. A method for sharing topology information in a self-configuring ATM network, comprising:

interconnecting n switches, where n is an integer greater than two;

on a first of said n switches, receiving a first set of topology messages from a set of neighboring switches, said first set of topology messages encoded with related pairs of switch identifiers and path cost information for particular ones of said n switches;

on said first switch, after receiving said first set of topology messages, generating and forwarding a second set of topology messages to said set of neighboring switches, said second set of topology messages encoded with related pairs of switch identifiers, VLAN information and path cost information for particular ones of said n switches, including at least related pairs of switch identifiers and path cost information for said first switch and said particular ones of said n switches included in said first set of topology messages.

2. The method according to claim 1, wherein said path cost information is computed based on the number of links on particular paths to said particular ones of said n switches and the bandwidth of said links.

3. The method according to claim 1, further comprising means on said first switch for forwarding a hello request message to each of said neighboring switches, said hello request message encoded with a lower and upper tag value.

4. A method for configuring a point-to-point tagged virtual connection in a self-configuring ATM network, comprising:

(a) interconnecting a switches and a destination switch, where a is an integer greater than one, said a switches including a source switch and b intermediate switches, said b intermediate switches residing in succession on an enabled path between said source switch and said destination switch, where b is a positive integer and where c is initially equal to b minus one;

(b) on said a switches, determining the dth best path to said destination switch, where d is a positive integer;

(c) on said source switch, generating and forwarding to a first intermediate switch on the dth best path from said source switch to said destination switch a first tag allocation request including as a related pair an identifier of said destination switch and a first tag value;

(d) if b is greater than one, on a (b-c)th intermediate switch, upon receiving a (b-c)th tag allocation request, generating and forwarding to a (b-c+1)th intermediate switch on the dth best path from said (b-c)th intermediate switch to said destination switch a (b-c+1)th tag allocation request including said identifier of said destination switch and a (b-c+1)th tag value as a related pair;

(e) if b is greater than one, subtracting one from c and repeating step (d) unless c equals zero;

(f) on said bth intermediate switch, generating and forwarding to said destination switch on the dth best path from said bth intermediate switch to said destination switch a (b+1)th tag allocation request including as a related pair said identifier of said destination switch and a (b+1)th tag value.

5. The method according to claim 4, wherein said dth best paths are paths associated with the dth lowest path cost from one of said a switches to said destination switch over a set of enabled links, among e path costs, where e is a positive integer greater than or equal to d, said path costs computed based on the number of links to said destination switch on a particular path and the bandwidth of said links.

6. The method according to claim 4, wherein d is one.

7. The method according to claim 4, wherein d is two when step (c) is performed and is one in all other instances.

8. The method according to claim 4, wherein d is two during one instance when step (d) is performed and is one in all other instances.

9. The method according to claim 4, wherein d is two when step (f) is performed and is one in all other instances.

10. The method according to claim 4, wherein d is either one or two, and may be one or two in any particular instance.

11. The method according to claim 4, wherein each said tag allocation request is encoded in a tag allocation message and at least one of said messages includes multiple requests.

12. The method according to claim 4, further comprising:

(g) on said source switch, associating said identifier of said destination switch and said first tag value with an identifier of a forwarding ATM port on said source switch; and

(h) on said source switch, storing said associated information a memory means as a related pair.

13. The method according to claim 4, wherein step (d) further comprises:

on said (b-c)th intermediate switch, upon receiving said (b-c)th tag allocation request, associating said (b-c)th tag value with an identifier of a forwarding ATM port and said second to said (b-c+1)th tag value; and

on said (b-c+1)th intermediate switch, storing said associated information in a memory means as a related pair.

14. The method according to claim 4, wherein said (b-c+1)th tag allocation request include an identifier of said source switch, further comprising:

(i) on said destination switch, associating said identifier of said source switch and said (b+1)th tag value with an identifier of a receiving ATM port; and

(j) on said destination switch, storing said associated information in a memory means as a related pair.

15. The method according to claim 4, wherein each of said a switches selects a different tag value for each tag allocation request.

16. A method for configuring a point-to-multipoint tagged virtual connection in a self-configuring ATM network, comprising:

(a) interconnecting a switches and a set of destination switches, where a is an integer greater than one, said a switches including a source switch and b sets of intermediate switches, said b sets of intermediate switches residing in succession on a set of enabled paths between said source switch and said sets of destination switches, where b is a positive integer and where c is initially equal to b minus one, said set of destination switches sharing a VLAN with said source switch;

(b) on said a switches, determining the spanning tree path to said set of destination switches;

(c) on said source switch, generating and forwarding to a first set of intermediate switches on the spanning tree path a first set of tag allocation requests including as a related pair an identifier of said shared VLAN and a first set of tag values;

(d) if b is greater than one, on said (b-c)th set of intermediate switches, upon receiving a (b-c)th set of tag allocation requests, generating and forwarding to a (b-c+1)th set of intermediate switches on the spanning tree path a (b-c+1)th set of tag allocation requests including as related pairs said identifier of said shared VLAN and a (b-c+1)th set of tag values;

(e) if b is greater than one, subtracting one from c and repeating step (d) unless c equals zero;

(f) on said bth set of intermediate switches, generating and forwarding to said set of destination switches on the spanning tree path a set of (b+1)th tag allocation requests including as related pairs said identifier of said shared VLAN and a set of (b+1)th tag values.

17. The method according to claim 16, wherein each said tag allocation request is encoded in a tag allocation message and at least one of said messages includes multiple requests.

18. The method according to claim 16, further comprising:

(g) on said source switch, associating said identifier of said shared VLAN and said first set of tag values with an identifier of a set of forwarding ATM ports on said source switch; and

(h) on said source switch, storing said associated information a memory means as a related pair.

19. The method according to claim 16, wherein step (d) further comprises:

on said set of (b-c)th intermediate switches, upon receiving said set of (b-c)th tag allocation requests, associating said set of (b-c)th tag values with a set of identifiers of a set of forwarding ATM ports and said set of (b-c+1)th tag values; and

on said set of (b-c+1)th intermediate switches, storing said associated information in a memory means as a related pair.

20. The method according to claim 16, wherein said set of (b-c+1)th tag allocation requests include an identifier of said source switch, further comprising:

(i) on said set of destination switches, associating said identifier of said source switch and said set of (b-c+1)th tag values with a set of identifiers of a set of receiving ATM ports; and

(j) on said set of destination switches, storing said associated information a set of memory means as a set of related pairs.

21. The method according to claim 16, wherein each of said a switches selects a different tag value for each tag allocation request.

22. A method for forwarding an end-user message on a point-to-point virtual connection in a self-configuring ATM network, comprising:

(a) interconnecting a switches and a destination switch, where a is an integer greater than one, said a switches including a source switch and b intermediate switches, said b intermediate switches residing in succession on an enabled path between said source switch and said destination switch, where b is a positive integer, and where c is initially equal to b minus one;

(b) on said source switch, receiving said end-user message, said end-user message having a payload and destination information;

(c) on said source switch, resolving said destination information to a forwarding ATM port identifier and a first tag value associated with the dth best path from said source switch to said destination switch, where d is initially one;

(d) on said source switch, encoding said end-user message with said first tag value and forwarding said end-user message to a first intermediate switch on the dth best path from said first intermediate switch to said destination switch;

(e) if b is greater than one, on a (b-c)th intermediate switch, upon receiving said end-user message encoded with a (b-c)th tag value, for encoding said end-user message with a (b-c+1)th tag value and forwarding said end-user message to a (b-c+1)th intermediate switch on the dth best path from said (b-c)th intermediate switch to said destination switch;

(f) if b is greater than one, subtracting one from c and repeating step (e) unless c equals zero;

(g) on said bth intermediate switch, upon receiving said end-user message encoded with a bth tag value, for encoding said end-user message with a (b+1)th tag value and forwarding said message to said destination switch on the dth best path from said bth intermediate switch to said destination switch.

23. The method according to claim 22, wherein d becomes two upon a failed attempt to forward said end-user message on the best path from one of said a switches to said destination switch and reverts to one after a successful forwarding attempt by said particular one of said a switches.

24. The method according to claim 22, wherein said end-user message includes source information, further comprising:

(h) on said destination switch, associating said source information with a tag value for a point-to-point virtual connection to said source switch; and

(i) on said destination switch, storing said associated information as a related pair in a memory means.

25. The method according to claim 22, wherein step (c) is carried out using custom logic.

26. The method according to claim 22, wherein said custom logic is an application-specific integrated circuit.

27. The method according to claim 22, wherein step (d) is carried out using custom logic.

28. The method according to claim 22, wherein said custom logic is an application-specific integrated circuit.

29. The method according to claim 22, wherein step (e) is carried out using custom logic.

30. The method according to claim 22, wherein said custom logic is an application-specific integrated circuit.