Method and apparatus for predictive QoS routing for broad band low earth satellite networks

• US 6,609,002 B1
• Filed: 04/03/2000
• Issued: 08/19/2003
• Est. Priority Date: 09/15/1999
• Status: Expired due to Fees

• Current Assignee: HRL Laboratories LLC (The Boeing Co.)
• Original Assignee: HRL Laboratories LLC (The Boeing Co.)
• Inventors: Ercetin, Ozgur, Krishnamurthy, Srikanth V., Dao, Son
• Primary Examiner(s): Kincaid, Lester G.
• Assistant Examiner(s): Ward, Ronald J.
• Application Number:
  US09/541,740
• Time in Patent Office: 1,233 Days
• Field of Search: 455/445, 455/446, 455/427, 455/428, 455/429, 455/452, 455/12.1, 455/13.1, 455/436, 455/440, 455/450, 370/316, 370/323, 370/325, 370/422
• US Class Current: 455/428
• CPC Class Codes: H04B 7/18521 Systems of inter linked satellites, i.e. inter satellite service for optical links between satellites H04B10/118
• CPC Class Codes: H04B 7/1856 for call routing
• CPC Class Codes: H04B 7/18584 Arrangements for data networking, i.e. for data packet routing, for congestion control data switching networks H04L12/00
• CPC Class Codes: H04W 28/26 Resource reservation
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/18 based on predicted events
• CPC Class Codes: H04W 84/06 Airborne or Satellite Networks space-based or airborne stations H04B7/185

Abstract

A predictive routing scheme for broad band Low Earth Orbit (LEO) satellite constellations is presented. The predictive routing scheme may be used to provide Quality of Service (QoS) guarantees for both Constant Bit-Rate (CBR) and Variable Bit-Rate (VBR) traffic types. The predictive routing scheme takes advantage of the predictable qualities of a LEO constellation, such as constant satellite footprint, constant satellite velocity, and predictable satellite trajectory. By using this information, combined with satellite-fixed cells which are divided into a set of equal-sized slots, along with user information such as the location of each particular user as well as the geographic concentrations of user traffic, each satellite may cooperate with surrounding satellites which have recently passed through the area into which they are entering, in order to receive predictive information regarding their future load. The information for each of the individual satellites may be used in order to determine a set of possible routes for new calls based on the predictive information regarding the future load distribution on the network. The predictive routing scheme utilizes a cost function in order to determine an optimal set of routes that maximizes the amount of unused bandwidth of the network, while still providing the required QoS guarantees.

Claims

1. A method for predictive QoS routing of calls within a satellite network including the steps of:

a. providing a satellite constellation orbiting the earth, said satellite constellation including at least one orbit, with each one of the at least one orbit including a plurality S of satellites, each indexed by a number s, and communicatively connected by a plurality of communication links, with each particular satellite having a satellite-fixed cell divided perpendicularly with respect to the orbit of the particular satellite, into a plurality L of satellite-fixed cell slots, with the movement of the plurality S of satellites over the earth being characterized in that the satellite-fixed cell for a satellite indexed at s covers the same area as the satellite-fixed cell of a satellite indexed at s+1 after passing over an area on the earth equivalent to the area of L satellite-fixed cell slots, and with an offset satellite-fixed cell being defined each time the satellite-fixed cell covers the area of one of L satellite-fixed cell slots while moving between the position of the satellite-fixed cell corresponding to a satellite indexed s and the satellite-fixed cell corresponding to a satellite indexed s+1, providing L offset satellite-fixed cells with the L offset satellite-fixed cells for each particular satellite being indexed by a number l=1, . . . , L, with the satellite-fixed cells and the offset satellite-fixed cells being defined as reference satellite-fixed cells;

b. receiving a call from a source user to a destination user, the call having a particular QoS requirement;

c. acquiring information regarding the source user and the destination user, including a user address and user location;

d. determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the source user is located, said satellite being defined as the source user end-reference satellite;

e. determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the destination user is located, said satellite being defined as the destination user end-reference satellite;

f. determining all paths including, at most, a preset number J of inter-satellite hops, between the source user end-reference satellite and the destination end-user reference satellite;

g. calculating a minimum residual link capacity for each of the paths determined in step (f);

h. determining, for each offset satellite-fixed cell l=1, . . . , L, a set {k_l} of paths that maximize the residual bandwidth at that offset satellite-fixed cell;

i. picking, from each set {k_l} of paths determined for each offset satellite-fixed cell, one path p such that the combined set CS of paths for all of the offset satellite-fixed cells minimizes the number of communication link changes necessary to maintain a call between the source user and the end user as the satellites move in their orbits; and

j. reserving at each offset satellite-fixed cell, the bandwidth along the path picked in step i, corresponding to the particular QoS requirement of the call.

2. A method for predictive QoS routing of calls within a satellite network as set forth in claim 1, wherein the calculation of the minimum residual link capacity for each of the plurality of paths at a given offset satellite-fixed cell l is defined by r_p(l)=c_i(l)−

R_p, where c_i(l) is the current link capacity of link i at offset satellite-fixed cell l, and where R_p represents the bandwidth required for a new call on path p if the connection is admitted in the offset satellite-fixed cell l, and where $R_p=\frac{\left(b+C_{\mathrm{tot})}\right)}{\left(D_{\mathrm{req}}-d<br><br>\left(p\right)\right)},$

where b represents the token bucket size, C_tot represents the total rate-dependent delay experienced by a packet belonging to the call, D_req represents the end-to-end delay requirement of each packet, and d(p) represents the end-to-end propagation delay for a chosen path p if the connection is admitted on the offset satellite-fixed cell l.

3. A method for predictive QoS routing of calls within a satellite network as set forth in claim 2, wherein the step of picking a path from each set of {k_l} paths includes the sub-steps of:

i. picking, for each set of paths {k_l} for offset satellite-fixed cells l=1, . . . ,L, a path, where the combined set of picked paths over all of the offset satellite-fixed cells l=1, . . . ,L is defined as a combined set of picked paths CS_m, where m=1, . . . ,k^L;

ii. determining the total number of link changes H_Sm required on the combined set of picked paths CS;

iii. repeating sub-steps i and ii for each different combination of paths;

iv. determining an overall reward for each combination set S_m={p₁(i₁), p₂(i₂), . . . , p_L(i_L)}, where i₁=1, . . . , k is the path chosen for offset satellite-fixed cell l, by;

$\mathrm{reward}<br><br>\left(S_m\right)=\underset{l=1}{\overset{L}{\sum <br><br>}}<br><br>\text{\hspace{1em}<br><br>}<br><br>r_p<br><br>\left(l\right)-W·<br><br>H_{\mathrm{Sm}},$

where W is a constant used to weigh the relative importance of having few link changes on the route for the call as offset calls are transitioned, with respect to the balancing of the user traffic;

v. choosing the S_m that maximizes the reward(S_m); and

vi. after a path for every offset satellite-fixed cell l=1, 2, . . . , L has been determined for the connection, reserving the necessary bandwidth for each path to satisfy the QoS requirements along the links forming the paths.

4. A method for predictive QoS routing of calls within a satellite constellation orbiting the earth, said satellite constellation including at least one orbit, with each one of the at least one orbit including a plurality S of satellites, each indexed by a number s, and communicatively connected by a plurality of communication links, with each particular satellite having a satellite-fixed cell divided, perpendicularly with respect to the orbit of the particular satellite, into a plurality L of satellite-fixed cell slots, with the movement of the plurality S of satellites over the earth being characterized in that the satellite-fixed cell for a satellite indexed at s covers the same area as the satellite-fixed cell of a satellite indexed at s+1 after passing over an area on the earth equivalent to the area of L satellite-fixed cell slots, and with an offset satellite-fixed cell being defined each time the satellite-fixed cell covers the area of one of L satellite-fixed cell slots while moving between the position of the satellite-fixed cell corresponding to a satellite indexed s and the satellite-fixed cell corresponding to a satellite indexed s+1, providing L offset satellite-fixed cells with the L offset satellite-fixed cells for each particular satellite being indexed by a number l=1, . . . , L, with the satellite-fixed cells and the offset satellite-fixed cells being defined as reference satellite-fixed cells, said method including the steps of:

a. receiving a call from a source user to a destination user;

b. acquiring information for the source user and the destination user, including a user address and user location;

c. determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the source user is located, said satellite being defined as the source user end-reference satellite;

d. determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the destination user is located, said satellite being defined as the destination user end-reference satellite;

e. determining all paths including at most a predetermined number J of inter-satellite hops, between the source user end-reference satellite and the destination end-user reference satellite;

f. calculating the minimum residual link capacity for each of the paths determined in step (e);

g. determining, for each offset satellite-fixed cell l=1, . . . ,L, a set {k_l} of paths that maximize the residual bandwidth at that offset satellite-fixed cell; and

h. picking, from each set {k_l} of paths determined for each offset satellite-fixed cell, one path p such that the combined set CS of paths for all of the offset satellite-fixed cells minimizes the number of communication link changes necessary to maintain a call between the source user and the end user.

5. A method for predictive QoS routing of calls within a satellite network as set forth in claim 4, wherein the calculation of the minimum residual link capacity for each of the plurality of paths at a given offset satellite-fixed cell l is defined by r_p(l)=c_i(l)−

R_p, where c_i(l) is the current link capacity link i at offset satellite-fixed cell l, and where R_p represents the bandwidth required for a new call on path p if the,connection is admitted in the offset satellite-fixed cell l, and where $R_p=\frac{\left(b+C_{\mathrm{tot})}\right)}{\left(D_{\mathrm{req}}-d<br><br>\left(p\right)\right)},$

where b represents the token bucket size, C_tot represents the total rate-dependent delay experienced by a packet belonging to the call, D_req represents the end-to-end delay requirement of each packet, and d(p) represents the end-to-end propagation delay for a chosen path p if the connection is admitted on the offset satellite-fixed cell l.

6. A method for predictive QoS routing of calls within a satellite network as set forth in claim 5, wherein the step of picking a path from each set of {k_l} paths includes the sub-steps of:

i. picking, for each set of paths {k_l} for offset satellite-fixed cells l=1, . . . ,L, a path, where the combined set of picked paths over all of the offset satellite-fixed cells l=1, . . . ,L is defined as a combined set of picked paths CS_m, where m=1, . . . ,k^L;

ii. determining the total number of link changes H_Sm required on the combined set of picked paths CS;

iii. repeating sub-steps i and ii for each different combination of paths;

iv. determining an overall reward for each combination set S_m={p₁(i₁), p₂(i₂), . . . , p_L(i_L)}, where i₁=1, . . . , k is the path chosen for offset satellite-fixed cell l, by;

7. An apparatus for predictive QoS routing of calls within a satellite network including:

a. a satellite constellation orbiting the earth, said satellite constellation including at least one orbit, with each one of the at least one orbit including a plurality S of satellites, each indexed by a number s, and communicatively connected by a plurality of communication links, with each particular satellite having a satellite-fixed cell divided, perpendicularly with respect to the orbit of the particular satellite, into a plurality L of satellite-fixed cell slots, with the movement of the plurality S of satellites over the earth being characterized in that the satellite-fixed cell for a satellite indexed at s covers the same area as the satellite-fixed cell of a satellite indexed at s+1 after passing over an area on the earth equivalent to the area of L satellite-fixed cell slots, and with an offset satellite-fixed cell being defined each time the satellite-fixed cell covers the area of one of L satellite-fixed cell slots while moving between the position of the satellite-fixed cell corresponding to a satellite indexed s and the satellite-fixed cell corresponding to a satellite indexed s+1, providing L offset satellite-fixed cells with the L offset satellite-fixed cells for each particular satellite being indexed by a number l=1, . . . , L, with the satellite-fixed cells and the offset satellite-fixed cells being defined as reference satellite-fixed cells;

b. means for receiving a call from a source user to a destination user;

c. means for acquiring information for the source user and the destination user, including a user address and user location;

d. means for determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the source user is located, said satellite being defined as the source user end-reference satellite;

e. means for determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the destination user is located, said satellite being defined as the destination user end-reference satellite;

f. means for determining all paths including at most a predetermined number J of inter-satellite hops, between the source user end-reference satellite and the destination end-user reference satellite;

g. means for calculating the minimum residual link capacity for each of the paths determined by the means in (f);

h. means for determining, for each offset satellite-fixed cell l=1, . . . ,L, a set {k_l} of paths that maximize the residual bandwidth at that offset satellite-fixed cell; and

i. means for picking, from each set {k_l} of paths determined for each offset satellite-fixed cell, one path p such that the combined set CS of paths for all of the offset satellite-fixed cells minimizes the number of communication link changes necessary to maintain a call between the source user and the end user.

8. An apparatus for predictive QoS routing of calls within a satellite network as set forth in claim 7, wherein the calculation of the minimum residual link capacity for each of the plurality of paths at a given offset satellite-fixed cell l is defined by r_p(l)=c_i(l)−

R_p, where c_i(l) is the current link capacity of a given link i at offset satellite-fixed cell l, and where R_p represents the bandwidth required for a new call on path p if the connection is admitted in the offset satellite-fixed cell l, and where $R_p=\frac{\left(b+C_{\mathrm{tot})}\right)}{\left(D_{\mathrm{req}}-d<br><br>\left(p\right)\right)},$

where b represents the token bucket size, C_tst represents the total rate-dependent delay experienced by a packet belonging to the call, D_req represents the end-to-end delay requirement of each packet, and d(p) represents the end-to-end propagation delay for a chosen path p if the connection is admitted on the offset satellite-fixed cell l.

9. An apparatus for predictive QoS routing of calls within a satellite network as set forth in claim 8, wherein the step of picking a path from each set of {k_l} paths includes the sub-steps of:

i. means for picking, for each set of paths {k_l} for offset satellite-fixed cells l=1, . . . ,L, a path, where the combined set of picked paths over all of the offset satellite-fixed cells l=1, . . . ,L is defined as a combined set of picked paths CS_m, where m=1, . . . ,k^L;

ii. means for determining the total number of link changes H_Sm required on the combined set of picked paths CS;

iii. means for operating the means of i and ii for each different combination of paths;

iv. means for determining an overall reward for each combination set S_m={p₁(i₁), p₂(i₂), . . . , p_L(i_L)}, where i₁=1, . . . , k is the path chosen for offset satellite-fixed cell l, by;

10. An apparatus for predictive QoS routing of calls within a satellite constellation orbiting the earth, said satellite constellation including at least one orbit, with each one of the at least one orbit including a plurality S of satellites, each indexed by a number s, and communicatively connected by a plurality of communication links, with each particular satellite having a satellite-fixed cell divided, perpendicularly with respect to the orbit of the particular satellite, into a plurality L of satellite-fixed cell slots, with the movement of the plurality S of satellites over the each being characterized in that the satellite-fixed cell for a satellite indexed at s covers the same area as the satellite-fixed cell of a satellite indexed at s+1 after passing over an area on the earth equivalent to the area of L satellite-fixed cell slots, and with an offset satellite-fixed cell being defined each time the satellite-fixed cell covers the area of one of L satellite-fixed cell slots while moving between the position of the satellite-fixed cell corresponding to a satellite indexed s and the satellite-fixed cell corresponding to a satellite indexed s+1, providing L offset satellite-fixed cells with the L offset satellite-fixed cells for each particular satellite being indexed by a number l=1, . . . , L, with the satellite-fixed cells and the offset satellite-fixed cells being defined as reference satellite-fixed cells, said apparatus including:

a. means for receiving a call from a source user to a destination user;

b. means for acquiring information for the source user and the destination user, including a user address and user location;

c. means for determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the source user is located, said satellite being defined as the source user end-reference satellite;

d. means for determining the satellite, the satellite-fixed cell, and the satellite-fixed cell slot within the satellite-fixed cell in which the destination user is located, said satellite being defined as the destination user end-reference satellite;

e. means for determining all paths including at most a predetermined number J of inter-satellite hops, between the source user end-reference satellite and the destination end-user reference satellite;

f. means for calculating the minimum residual link capacity for each of the paths determined by the means of (e);

g. means for determining, for each offset satellite-fixed cell l=1, . . . ,L, a set {k_l} of paths that maximize the residual bandwidth at that offset satellite-fixed cell; and

h. means for picking, from each set {k_l} of paths determined for each offset satellite-fixed cell, one path p such that the combined set CS of paths for all of the offset satellite-fixed cells minimizes the number of communication link changes necessary to maintain a call between the source user and the end user.

11. An apparatus for predictive QoS routing of calls within a satellite network as set forth in claim 10, wherein the calculation of the minimum residual link capacity for each of the plurality of paths at a given offset satellite-fixed cell l is defined by r_p(l)=c_i(l)−

R_p, where c_i(l) is the current link capacity of a given link i at offset satellite-fixed cell l, and where R_p represents the bandwidth required for a new call on path p if the connection is admitted in the offset satellite-fixed cell l, and where $R_p=\frac{\left(b+C_{\mathrm{tot})}\right)}{\left(D_{\mathrm{req}}-d<br><br>\left(p\right)\right)},$

where b represents the token bucket size, C_tot represents the total rate-dependent delay experienced by a packet belonging to the call, D_req represents the end-to-end delay requirement of each packet, and d(p) represents the end-to-end propagation delay for a chosen path p if the connection is admitted on the offset satellite-fixed cell l.

12. An apparatus for predictive QoS routing of calls within a satellite network as set forth in claim 11, wherein the step of picking a path from each set of {k_l} paths includes the sub-steps of:

i. means for picking, for each set of paths {k_l} for offset satellite-fixed cells l=1, . . . ,L, a path, where the combined set of picked paths over all of the offset satellite-fixed cells l=1, . . . ,L is defined as a combined set of picked paths CS_m, where m=1, . . . ,k^L;

ii. means for determining the total number of link changes H_Sm required on the combined set of picked paths CS;

iii. means for operating the means of i and ii for each different combination of paths;

iv. means for determining an overall reward for each combination set S_m={p₁(i₁), p₂(i₂), . . . , p_L(i_L)}, where i=1, . . . , k is the path chosen for offset satellite-fixed cell l, by;