Self-configuring communication network

• US 6,757,286 B1
• Filed: 08/01/2000
• Issued: 06/29/2004
• Est. Priority Date: 03/24/1997
• Status: Expired due to Fees

• Current Assignee: Alcatel SA (Nokia Corporation)
• Original Assignee: Alcatel SA (Nokia Corporation)
• Inventors: Stone, Geoffrey C.
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Elallam, Ahmed
• Application Number:
  US09/629,362
• Time in Patent Office: 1,428 Days
• Field of Search: 370/203, 370/217, 370/218, 370/221, 370/225, 370/228, 370/237, 370/254-256, 370/389, 370/392, 370/396-397, 370/399, 370/352, 370/400-402, 370/404, 370/238, 370/395.53, 709/241
• US Class Current: 370/395.53
• 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 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 configuring a tagged virtual connection in a communication network, said virtual connection interconnecting a first boundary device with a second boundary device via N intermediate devices, where N is a positive integer, the method comprising:

(a) on a first boundary device, generating and forwarding to a first intermediate device a first tag allocation request including a logical group identifier;

(b) if N is greater than one, on an (N−

M)th intermediate device, in response to an (N−

M)th tag allocation request, generating and forwarding to an (N−

M+1)th intermediate device an (N−

M+1)th tag allocation request including said logical group identifier, where M is initially equal to N−

1;

(c) if N is greater than one, repeating step (b) for each integral value of M between N−

1 and zero, excluding N−

1 and zero; and

(d) on an Nth intermediate device, in response to an Nth tag allocation request, generating and forwarding to a second boundary device an (N+1)th tag allocation request including said logical group identifier,

wherein tag values associated with said logical group identifier are allocated and transmitted between said devices in relation to number of tag allocation requests; and

wherein said tag values are applied to establish a tagged virtual connection for transmitting end-user messages destined to one or more of a plurality of destination stations belonging to a logical group identified by said logical group identifier.

2. The method according to claim 1, wherein each tag allocation request includes an identifier of one of said boundary devices.

3. The method according to claim 1, wherein each tag allocation request includes a tag value and an identifier of one of said boundary devices as a related pair.

4. The method according to claim 1, wherein each tag allocation request includes a destination device identifier.

5. The method according to claim 1, wherein each tag allocation request includes a value and a destination device identifier as a related pair.

6. The method according to claim 1, wherein each tag allocation request includes a source device identifier.

7. The method according to claim 1, wherein each tag allocation request includes a tag value and a source device identifier as a related pair.

8. The method according to claim 1, wherein said logical group identifier is a virtual network identifier.

9. The method according to claim 1, wherein said devices are data communication switches.

10. The method according to claim 1 wherein said tag values are applied by said devices to establish a tagged virtual connection for transmitting end-user messages originating from one or more of a plurality of source stations belonging to a logical group identified by said logical group identifier to one or more of a plurality of destination stations belonging to said logical group identified by said logical group identifier.

11. A method for configuring a tagged virtual connection in a communication network, said virtual connection interconnecting a first boundary device with a second boundary device via N intermediate devices, where N is a positive integer, the method comprising:

(a) on each of a first boundary device and N intermediate devices, determining an nth best path to a second boundary device for a plurality of logical groups, where n is a positive integer;

(b) on said first boundary device, generating and forwarding to a first intermediate device on the nth best path for a first logical group from said first boundary device to said second boundary device a first tag allocation request;

(c) if N is greater than one, on an (N−

M)th intermediate device, in response to an (N−

M)th tag allocation request, generating and forwarding to an (N−

M+1)th intermediate device on the nth best path for said first logical group from said (N−

M)th intermediate device to said second boundary device an (N−

M+1)th tag allocation request, where M is initially equal to N−

1;

(d) if N is greater than one, repeating step (c) for each integral value of M between N−

1 and zero, excluding N−

1 and zero; and

(e) on an Nth intermediate device, in response to an Nth tag allocation request, generating and forwarding to said second boundary device on the nth best path for said first logical group from said Nth intermediate device to said second boundary device, an (N+1)th tag allocation request.

12. The method according to claim 11, wherein path cost information shared between neighboring ones of said boundary devices and/or intermediate devices is used in each best path determination.

13. The method according to claim 11, where n is one.

14. The method according to claim 11, where step (a) is performed with n equal to one and is repeated with n equal to two.

15. The method according to claim 11, wherein n is two in one instance when one of steps (b), (c) or (e) is performed and is one in all other instances.

16. The method according to claim 11, wherein n is either one or two in all instances when steps (b), (c) and (e) are performed, and may be either one or two in any particular instance when step (b), (c) or (e) is performed.

17. The method according to claim 11, wherein said devices are data communication switches.

18. A method for configuring a point-to-multipoint tagged virtual connection in a communication network, said virtual connection interconnecting a first boundary device with a set of second boundary devices on a plurality of different paths, wherein each path has N intermediate devices and wherein N is an integer whose value may differ between paths, the method comprising:

(a) on a first boundary device, generating and forwarding to a set of intermediate devices on a set of paths between said first boundary device and a set of second boundary devices a set of tag allocation requests including a logical group identifier;

(b) for each path in said set for which N is greater than one, on an (N−

M)th intermediate device, in response to an (N−

M)th tag allocation request, generating and forwarding to an (N−

M)th intermediate device an (N−

M+1)th tag allocation request including a logical group identifier, where M is initially equal to N−

1;

(c) for each path in said ser for which N is greater than one, repeating step (b) for each integral value of M between N−

1 and zero, excluding N−

1 and zero; and

(d) for each path in said set, on an Nth intermediate device, in response to an Nth tag allocation request, generating and forwarding to said second boundary device an (N+1)th tag allocation request and said logical group identifier,

wherein tag values associated with said logical group identifier are allocated and transmitted between said devices in relation to number of tag allocation requests; and

wherein said tag values are applkied to establish a tagged virtual connection for transmitting end-user messages destined to a plurality of destination stations belonging to a logical group identified by said logical group identifier.

19. The method according to claim 18, wherein said logical group identifier is a virtual group identifier.

20. The method according to claim 18, wherein each tag allocation request includes the logical group identifier and an identifier of one of said boundary devices as a related pair.

21. The method according to claim 18, wherein each tag allocation request includes the logical group identifier and a destination device identifier as a related pair.

22. The method according to claim 18, wherein each tag allocation request includes the logical group identifier and a source device identifier as a related pair.

23. The method according to claim 18, wherein the logical group identifier and path cost information shared between neighboring ones of said boundary devices and/or intermediate devices is used in each best path determination.

24. The method according to claim 18 wherein said tag values are applied by said devices to establish a tagged virtual connection for transmitting end-user messages originating from one or more of a plurality of source stations belonging to a logical group identified by said logical group identifier to a plurality of destination stations belonging to said logical group identified by said logical group identifier.

25. Method for forwarding an end-user message on a tagged virtual connection in a communication network, said virtual connection interconnecting a first boundary device with a second boundary device via N intermediate devices, where N is a positive integer, the method comprising:

(a) on a first boundary device, receiving an end-user message;

(b) on said first boundary device, associating said end-user message with a virtual network;

(c) on said first boundary device, determining a first tag value for said end-user message in accordance with said virtual network;

(d) on said first boundary device, encoding said end-user message with said first tag value and forwarding said end-user message to a first intermediate device;

(e) if N is greater than one, on an (N−

M)th intermediate device, in response to receiving said end-user message encoded with an (N−

M)th tag value, encoding said end-user message with an (N−

M+1)th tag value and forwarding said end-user message to an (N−

M+1)th intermediate device, where M is initially equal to N×

1;

(f) if N is greater than one, repeating step (e) for each integral value of M between N−

1 and zero, excluding N−

1 and zero; and

(g) on an Nth intermediate device, in response to receiving said end-user message encoded with an Nth tag value, encoding said end-user message with an (N+1)th tag value and forwarding said end-user message to a second boundary device.

26. The method according to claim 25, wherein said devices are data communication switches.

27. The method according to claim 25, wherein said virtual network is associated with a port on said first boundary device.

28. A method for forwarding an end-user message on a tagged virtual connection in a communication network, said virtual connection interconnecting a first boundary device with a second boundary device via one or more intermediate devices, the method comprising:

(a) receiving an end-user message on a first boundary device;

(b) determining a tag value for said end-user message in accordance with information regarding the best path for a logical group from said first boundary device to a second boundary device under present network conditions, wherein the determination is made from among a plurality of different tag values associated with different paths for said logical group from said first boundary device to said second boundary device;

(c) encoding said end-user message with said determined tag value; and

(d) forwarding said end-user message from said first boundary device to a first intermediate device.

29. The method according to claim 28, wherein said end-user message is associated with said logical group.

30. The method according to claim 28, wherein said logical group is a virtual network.

31. The method according to claim 28, wherein step (b) further comprises determining a forwarding port for said end-user message in accordance with information regarding the best path for said logical group from said first boundary device to said second boundary device under present network conditions, wherein the determination is made from among a plurality of different forwarding ports associated with different paths for said logical group from said first boundary device to said second boundary device.

32. A method for configuring a tagged virtual connection in a communication network, said virtual connection interconnecting a first boundary device with a second boundary device via N intermediate devices, where N is a positive integer, the method comprising:

(a) exchanging first tag allocation information including a first tag value and a logical group identifier between a first boundary device and a first intermediate device;

(b) if N is greater than one, in response to the exchange of (N−

M)th tag allocation information, exchanging (N−

M+1)th tag allocation information including an (N−

M+1)th tag value and said logical group identifier between an (N−

M)th intermediate device and an (N−

M+1)th intermediate device, where M is initially equal to N−

1;

(c) if N is greater than one, repeating step (b) for each integral value of M between N−

1 and zero, excluding N−

1 and zero; and

(d) in response to the exchange of Nth tag allocation information, exchanging (N+1)th tag allocation information including an (N+1)th tag value and said logical group identifier between an Nth intermediate device and a second boundary device,

wherein tag values associated with said logical group identifier are allocated and transmitted between said devices in relation to number of tag allocation requests; and

wherein said tag values are applied to establish a tagged virtual connection for transmitting end-user messages destined to one or more of a plurality of destination stations belonging to a logical group identified by said logical group identifier.

33. The method according to claim 32, wherein said logical group identifier includes a virtual network identifier.

34. The method according to claim 32 wherein said tag values are applied by said devices to establish a tagged virtual connection for transmitting end-user messages originating from one or more of a plurality of source stations belonging to a logical group identified by said logical group identifier to one or more of a plurality of destination stations belonging to said logical group identified by said logical group identifier.

35. A method for configuring a tagged virtual connection in a communication network, said virtual connection interconnecting a first boundary device with a second boundary device via N intermediate devices, where N is a positive integer, the method comprising:

(a) on each of a first boundary device, determining an nth best path to a second boundary device for a plurality of logical groups, where n is a positive integer;

(b) on said first boundary device, generating and forwarding to a first intermediate device on the nth best path for a first logical group a first tag allocation request;

(c) if N is greater than one, on an (N−

M)th intermediate device, in response to an (N−

M)th tag allocation request, generating and forwarding to an (N−

M+1)th intermediate device on the nth best path for said first logical group, an (N−

M+1)th tag allocation request, where M is initially equal to N−

1;

(d) if N is greater than one, repeating step (c) for each integral value of M between N−

1 and zero, excluding N−

1 and zero; and

(e) on an Nth intermediate device, in response to an Nth tag allocation request, generating and forwarding to said second boundary device on the nth best path for said first logical group, an (N+1)th tag allocation request.

36. The method according to claim 35, wherein the logical group is a virtual network.

37. The method according to claim 35, wherein path cost information shared between neighboring ones of said boundary devices and/or intermediate devices is used in each best path determination.

38. The method according to claim 35, wherein n is one.

39. The method according to claim 35, wherein step (a) is performed with n equal to one and is repeated with n equal to two.

40. The method according to claim 35, wherein n is two in one instance when one of steps (b), (c) or (e) is performed and is one in all other instances.

41. The method according to claim 35, wherein n is either one or two in all instances when steps (b), (c) and (e) are performed, and may be either one or two in any particular instance when step (b), (c) or (e) is performed.

42. The method according to claim 35, wherein said devices are data communication switches.