Systems and methods for employing a recursive mesh network with extraplanar links

• US 5,530,575 A
• Filed: 09/09/1994
• Issued: 06/25/1996
• Est. Priority Date: 09/09/1994
• Status: Expired due to Fees

• Current Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Original Assignee: Trustees Of Columbia University In The City Of New York (Columbia University)
• Inventors: Acampora, Anthony, Brown, Glenn C.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): NEGASH, KINFE MICHAEL
• Application Number:
  US08/303,485
• Time in Patent Office: 655 Days
• Field of Search: 359/109, 359/118, 359/123, 359/125, 359/128, 359/137, 359/139, 370/94.3
• US Class Current: 398/58
• CPC Class Codes: H04B 10/27 Arrangements for networking
• CPC Class Codes: H04J 14/0227 Operation, administration, maintenance or provisioning [OAMP] of WDM networks, e.g. media access, routing or wavelength allocation
• CPC Class Codes: H04J 14/0241 Wavelength allocation for communications one-to-one, e.g. unicasting wavelengths
• CPC Class Codes: H04J 14/028 WDM bus architectures
• CPC Class Codes: H04J 14/0284 WDM mesh architectures
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/357 Fibre channel switches
• CPC Class Codes: H04Q 11/0062 Network aspects
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 2011/0013 using gating amplifiers
• CPC Class Codes: H04Q 2011/0015 using splitting combining
• CPC Class Codes: H04Q 2011/0035 using miscellaneous components, e.g. circulator, polarisation, acousto/thermo optical
• CPC Class Codes: H04Q 2011/0039 Electrical control
• CPC Class Codes: H04Q 2011/009 Topology aspects

Abstract

Techniques for making a recursive mesh network for connecting a varying number of access stations within a service area is disclosed. The techniques include (a) dividing the service area into M×N rectangular regions, having (M+1)×(N+1) corners, which cover the entire range of the service area; (b) placing an access station at an available region corner whenever a new access station becomes available, and connecting the access station to its corresponding optical connection paths, until (M+1)×(N+1) access stations have been so connected; (c) determining, for each additional new access station, which region the additional new access station falls within; (d) if this determined region has not been divided, dividing the determined region into S×T sub-regions; (e) if the divided determined region has less than (S+1)×(T+1) access stations within it, placing the additional new access station at an available sub-region corner in the region and connecting the new additional access station to at least one other access station within the same region; and (f) if the divided determined region has (S+1)×(T+1) access stations within it, repeating steps (c)-(f) with respect to that sub-region until the new additional access station can be connected. Also disclosed are an optical telecommunications network and techniques for routing information in a recursive mesh network.

Claims

1. A method for providing a recursive mesh network for connecting a plurality number of access stations within a service area by connecting links, comprising the steps of:

(a) dividing said service area into M×

N regions, having (M+1)×

(N+1) corners, M and N being integers ≧

2, wherein each side of each region corresponds to a bidirectional connection link;

(b) assigning a new access station at an unoccupied region corner and connecting said new access station to corresponding connection links, until (M+1)×

(N+1) access stations have been connected;

(c) determining, after all (M+1)×

(N+1) region corner have been occupied, for each additional new access station, which of said regions said additional new access station falls within;

(d) when said determined region has not been divided, dividing said determined region into M'"'"'×

N'"'"' sub-regions having (M'"'"'+1)×

(N'"'"'+1) sub-region corners, M'"'"' and N'"'"' being inters ≧

2;

(e) when said divided determined sub-region has less than (M'"'"'+1)×

(N'"'"'+1) access stations within it, assigning said additional new access station at an available corner of said sub-region and connecting said new additional access station to bidirectional connection links that lead to at least one other access station within the same sub-region; and

(f) when said divided determined sub-region has (M'"'"'+1)×

(N'"'"'+1) access stations therewithin, repeating steps (c)-(f) with respect to that sub-region until said new additional access station is connected.

2. The method of claim 1, further including the step of:

(g) adding at least one extraplanar-link to said recursive mesh network, wherein each extraplanar link connects a first access station within said recursive mesh network to a second access station within said recursive mesh network.

3. The method of claim 2, wherein said first and second access stations are selected in response to current prevailing traffic patterns within the service area.

4. The method of claim 2, wherein at least one extraplanar link is bidirectional.

5. The method of claim 2, wherein said access stations are connected to said connection links and said extraplanar links through optical switches.

6. The method of claim 5, wherein said optical switches include a plurality of 5 I/O ports.

7. The method of claim 1, wherein said recursive mesh network comprises an optical mesh, said connection links comprise optical channels, and said connection steps (b) and (e) include connecting access stations to said optical channels.

8. The method of claim 1, wherein said recursive mesh network comprises a fiber mesh, said connection links comprise fiber links, and said connection steps (b) and (e) include connecting access stations to said fiber links.

9. The method of claim 1, wherein said step (b) comprises the steps of:

(i) assigning an access station at a region corner corresponding to a service area corner if a service area corner is available;

(ii) assigning an access station at a region corner corresponding to a non-corner service area side if no service area corner is available and a service area side is available; and

(iii) assigning an access station at a region corner that does not correspond to a service area corner or side if no service area corner or side is available.

10. The method of claim 9, wherein said step (e) comprises the steps of:

(i) assigning an access station at a sub-region corner corresponding to a non-corner region side if a region side is available; and

(ii) assigning an access station at a sub-region corner that does not correspond to a region corner or side if no service area side is available.

11. The method of claim 1, wherein all M and N variables have an identical value.

18. The apparatus of claim 1, wherein said recursive mesh network comprises an optical mesh and said connection links comprise optical virtual channels.

19. The apparatus of claim 1, wherein said recursive mesh network comprises a fiber mesh and said connection links comprise fiber links.

12. Apparatus for providing a recursive mesh network for connecting a plurality number of access stations within a service area by connecting links, comprising:

(a) first dividing means for dividing said service area into M×

N regions, having (M+1)×

(N+1) corners, M and N being integers ≧

2, wherein each side of each region corresponds to a bidirectional connection link;

(b) first assignment means, coupled to said first dividing means, for assigning a new access station at an unoccupied region corner and connecting said new access station to corresponding connection links, until (M+1)×

(N+1) access stations have been connected;

(c) locator means, coupled to said first assignment means, for determining, for each additional new access station, after all (M+1)×

(N+1) region corner have been occupied, which of said regions said additional new access station falls within;

(d) second dividing means, coupled to said locator means, for dividing said determined region into M'"'"'×

N'"'"' sub-regions having (M'"'"'+1)×

(N'"'"'+1) sub-region corners, M'"'"' and N'"'"' being inters ≧

2, when said determined region has not been divided;

(e) second assignment means, coupled to said second dividing means, for assigning said additional new access station at an available corner of said sub-region and connecting said new additional access station to bidirectional connection links that lead to at least one other access station within the same sub-region, when said divided determined sub-region has less than (M'"'"'+1)×

(N'"'"'+1) access stations within it; and

(f) repeat means, coupled to said locator, second dividing and second assignment means, for causing said locator, second dividing and second assignment means to act with respect to said divided determined sub-region until said new additional access station is connected when said divided determined sub-region has (M'"'"'+1)×

(N'"'"'+1) access stations therewithin,.

13. The apparatus of claim 12, further including:

(g) third assignment means, coupled to said locator means, for adding at least one extraplanar-link to said recursive mesh network, wherein each extraplanar link connects a first access station within said recursive mesh network to a second access station within said recursive mesh network.

14. The apparatus of claim 13, wherein said first and second access stations are selected in response to current prevailing traffic patterns within the service area.

15. The apparatus of claim 13, wherein at least one extraplanar link is bidirectional.

16. The apparatus of claim 13, wherein said access stations are connected to said connection links and said extraplanar links through optical switches.

17. The apparatus of claim 16, wherein said optical switches include a plurality of 5 I/O ports.

20. The apparatus of claim 12, wherein said first assignment means comprises:

(i) means, coupled to said first assignment means, for assigning an access station at a region corner corresponding to a service area corner if a service area corner is available;

(ii) means, coupled to said first assignment means, for assigning an access station at a region corner corresponding to a non-corner service area side if no service area corner is available and a service area side is available; and

(iii) means, coupled to said first assignment means, for assigning an access station at a region corner that does not correspond to a service area corner or side if no service area corner or side is available.

21. The apparatus of claim 20, wherein said second assignment means comprises:

(i) means, coupled to said second assignment means, for assigning an access station at a sub-region corner corresponding to a non-corner region side if a region side is available; and

(ii) means, coupled to said second assignment means, for assigning an access station at a sub-region corner that does not correspond to a region corner or side if no service area side is available.

22. The apparatus of claim 12, wherein all M and N variables have an identical value.

23. A telecommunications network connecting a plurality of users within a service area by a recursive mesh network, comprising:

(a) a plurality of access stations, at least two access stations being capable of being accessed by at least one user; and

(b) a plurality of bidirectional connection links for connecting each of said access stations to at least one other access station, wherein said connection links connect said access stations as said recursive mesh network.

24. The telecommunications network of claim 23, further including one or more extraplanar links, wherein each extraplanar link connects an access station within said recursive mesh network to a different access station within said recursive mesh network.

25. The telecommunications network of claim 24, wherein said access stations are selected based upon current prevailing traffic patterns within the service area.

26. The telecommunications network of claim 24, wherein at least one extraplanar link is bidirectional.

27. The telecommunications network of claim 24, further including a plurality of switches, wherein each of said access stations is connected to its connection and extraplanar links by a switch.

28. The telecommunications network of claim 27, wherein said switches include a plurality of I/O ports.

29. The telecommunications network of claim 24, wherein said recursive mesh network comprises an optical mesh and said connection and extraplanar link comprise optical channels, so that said access stations are connected to said optical channels to form an optical mesh network with extraplanar optical links.

30. The telecommunications network of claim 24, wherein said recursive mesh network comprises a fiber mesh and said connection and extraplanar links comprise fiber channels, so that said access stations are connected to said fiber channels to form a fiber mesh network with extraplanar fiber links.

31. A method for routing information in a recursive mesh network to connect a first access station A at location (x_A, y_A) to a second access station B at location (x_B, y_B), wherein each access station within said network stores data sufficient to route said information to all other access stations no more than a preselected number of hops away in a local table T, each access station at a head-end stores the shortest path to every other access station within that head-end region in a local table H, and each access station within an incomplete grid stores the shortest path to the nearest head-end in a local table H, comprising the steps of:

(a) using the local routing table T of access station A to reach access station B from access station A if said table T contains the address of B;

if said table T does not contain the address of B;

(b) routing along the connection paths of said network using local tables T in such a way that the distance to said access station B is reduced at each intermediate node if such routing is possible;

if such routing is not possible due to blocking at node C, then;

(c) routing from access station C to access station B, by;

(i) using the local routing table H of access station C to reach an access station C'"'"' at the head-end of C;

(ii) routing along the x connection paths and the y connection paths of said network from access station C'"'"' to access station B'"'"' in such a way that the distance to said access station B'"'"' is reduced at each intermediate node, wherein access station B'"'"' lies at the head-end of B; and

(iii) using the local routing table H of access station B'"'"' to reach access station B.

32. A method for routing information in a recursive mesh network to connect a first access station A at location (x_A, y_A) to a second access station B at location (x_B, y_B), wherein each access station within said network stores data sufficient to route said information to all other access stations no more than a preselected number of hops away in a local table T, and D(A,B) is defined as the distance between said access station A and said access station B, comprising the steps of:

(a) starting at access station A;

(b) routing from the present access station P to a new access station X if P and X share a connection path and D(X,B)<

D (P,B); and

(c) when P and X are do not share a connection path or D(X,B)>

D (P,B);

(i) routing from said present access station P to the access station L at the left of said access station P;

(ii) routing to the access station R at the right of said access station L; and

(iii) repeating step (c)(ii) until D(R,B)<

D(Q,B) for all Q ε

N, wherein N is the set of all access stations visited during such routing;

(d) repeating steps (b) and (c) until access station B is connected.

33. The method of claim 32, wherein D(A,B) is defined as being equal to the sum of the absolute value of (x_A -x_B) and the absolute value of (y_A -y_B).

34. The method of claim 32, wherein D(A,B)=√

(X_a -X_B)² +(Y_A Y_B)².

35. An apparatus for routing information in a recursive mesh network to connect a first access station A at location (x_A, y_A) to a second access station B at location (x_B, y_B), wherein each access station within said network stores data sufficient to route said information to all other access stations no more than a preselected number of hops away in a local table T, each access station at a head-end stores the shortest path to every other access station within that head-end region in a local table H, and each access station within an incomplete grid stores the shortest path to the nearest head-end in a local table H, comprising:

(a) first memory means for using the local routing table T of access station A to reach access station B from access station A if said table T contains the address of B;

(b) first routing means, coupled to said first memory means, for routing along the connection paths of said network using local tables T in such a way that the distance to said access station B is reduced at each intermediate node if such routing is possible, if said table T of access station A does not contain the address of B;

(c) second routing means, coupled to said first routing means, for routing from access station C to access station B if said first routing means is not able to route due to blocking at node C, wherein said second routing means includes;

(i) second memory means, coupled to said second routing means, for using the local routing table H of access station C to reach an access station C'"'"' at the head-end of C;

(ii) third routing means, coupled to said second routing means, for routing along the x connection paths and the y connection paths of said network from access station C'"'"' to access station B'"'"' in such a way that the distance to said access station B'"'"' is reduced at each intermediate node, wherein access station B'"'"' lies at the head-end of B; and

(iii) third memory means, coupled to said second routing means, for using the local routing table H of access station B'"'"' to reach access station B.

36. An apparatus for routing information in a recursive mesh network to connect a first access station A at location (x_A, y_A) to a second access station B at location (x_B, y_B), wherein each access station within said network stores data sufficient to route said information to all other access stations no more than a preselected number of hops away in a local table T, and D(A,B) is defined as the distance between said access station A and said access station B, comprising:

(a) initiation means for starting at access station A;

(b) first routing means, coupled to said initiation means, for routing from the present access station P to a new access station X if P and X share a connection path and D(X,B)<

D (P,B);

(c) second routing means, coupled to said initiation means, to route information when P and X do not share a connection path or D(X,B)>

D (P,B), including;

(i) left routing means, coupled to said second routing means, for routing from said present access station P to the access station L at the left of said access station P;

(ii) right routing means, coupled to said second routing means, for repeatedly routing to the access station R at the right of the present access station until D(R,B)<

D(Q,B) for all Q ε

N, wherein N is the set of all access stations visited during such routing; and

(d) repeat means, coupled to said first and second routing means, for causing said first and second routing means to rout said information until said station B is connected.

37. The apparatus of claim 36, wherein D(A,B) is defined as being equal to the sum of the absolute value of (x_A -x_B) and the absolute value of (y_A -y_B).

38. The apparatus of claim 36, wherein D (A,B)=√

(X_a -X_B)² +(Y_A Y_B)².