Method and apparatus for predictive QoS routing for broad band low earth satellite networks
First Claim
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 {kl} of paths that maximize the residual bandwidth at that offset satellite-fixed cell;
i. picking, from each set {kl} 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
12 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 {kl} of paths that maximize the residual bandwidth at that offset satellite-fixed cell;
i. picking, from each set {kl} 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. - View Dependent Claims (2, 3)
where b represents the token bucket size, Ctot represents the total rate-dependent delay experienced by a packet belonging to the call, Dreq 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 {kl} paths includes the sub-steps of:
-
i. picking, for each set of paths {kl} 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 CSm, where m=1, . . . ,kL;
ii. determining the total number of link changes HSm 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 Sm={p1(i1), p2(i2), . . . , pL(iL)}, where i1=1, . . . , k is the path chosen for offset satellite-fixed cell l, by;
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 Sm that maximizes the reward(Sm); 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 {kl} of paths that maximize the residual bandwidth at that offset satellite-fixed cell; and
h. picking, from each set {kl} 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. - View Dependent Claims (5, 6)
where b represents the token bucket size, Ctot represents the total rate-dependent delay experienced by a packet belonging to the call, Dreq 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 {kl} paths includes the sub-steps of:
-
i. picking, for each set of paths {kl} 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 CSm, where m=1, . . . ,kL;
ii. determining the total number of link changes HSm 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 Sm={p1(i1), p2(i2), . . . , pL(iL)}, where i1=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 {kl} of paths that maximize the residual bandwidth at that offset satellite-fixed cell; and
i. means for picking, from each set {kl} 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. - View Dependent Claims (8, 9)
where b represents the token bucket size, Ctst represents the total rate-dependent delay experienced by a packet belonging to the call, Dreq 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 {kl} paths includes the sub-steps of:
-
i. means for picking, for each set of paths {kl} 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 CSm, where m=1, . . . ,kL;
ii. means for determining the total number of link changes HSm 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 Sm={p1(i1), p2(i2), . . . , pL(iL)}, where i1=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 {kl} of paths that maximize the residual bandwidth at that offset satellite-fixed cell; and
h. means for picking, from each set {kl} 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. - View Dependent Claims (11, 12)
where b represents the token bucket size, Ctot represents the total rate-dependent delay experienced by a packet belonging to the call, Dreq 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 {kl} paths includes the sub-steps of:
-
i. means for picking, for each set of paths {kl} 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 CSm, where m=1, . . . ,kL;
ii. means for determining the total number of link changes HSm 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 Sm={p1(i1), p2(i2), . . . , pL(iL)}, where i=1, . . . , k is the path chosen for offset satellite-fixed cell l, by;
-
Specification