Method and system for determination of routes in LEO satellite networks with bandwidth and priority awareness and adaptive rerouting

• US 8,780,928 B2
• Filed: 10/04/2011
• Issued: 07/15/2014
• Est. Priority Date: 10/04/2010
• Status: Active Grant

• Current Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Original Assignee: Telcordia Technologies Incorporated (Telefonaktiebolaget LM Ericsson)
• Inventors: Natarajan, Narayanan, Bagchi, Anindo, Stephens, William E.
• Primary Examiner(s): Chung, Hoon J
• Application Number:
  US13/252,711
• Publication Number:
  US 20120263042A1
• Time in Patent Office: 1,015 Days
• Field of Search: 370/310.2, 370328-339, 370/349, 370/396, 370/400, 455/422.1, 709239-243
• US Class Current: 370/400
• 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: H04L 45/22 Alternate routing
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality

Abstract

In Low Earth Orbit (LEO) satellite networks data routes for point to point and point to multipoint communication sessions in LEO satellite networks are determined by considering session bandwidth, priority, and the constantly changing terminal-satellite and satellite-satellite connectivity. Multiple routes are computed for a session to facilitate automatic adaptive rerouting by satellite payloads when they encounter network failures or congestion conditions.

Claims

1. A method of determining a primary path and multiple alternative paths for a point-to-point communication session between two ground terminals connected across by a Low Earth Orbit (LEO) satellite network comprising:

a computer located at a network operations center for;

determining routes using the following information;

changes in terminal—

satellite connectivity due to satellite orbits;

changes in satellite—

satellite connectivity due to satellite orbits;

locations of Source and Destination terminals;

communication session duration;

session traffic bandwidth; and

session traffic priority;

determining routes for the primary path and alternative paths based on a LEO Satellite Grid where the Grid represents a fixed logical satellite constellation topology comprising logical nodes representing geolocations, vertical edges representing logical intra-plane crosslinks, horizontal edges representing logical inter-plane crosslinks, and delay information on crosslinks;

wherein the routes for the primary path and alternative paths are determined by computing shortest paths from a Source Node whose coverage area includes a Source terminal location to a Destination Node whose coverage area includes a Destination terminal location, taking into account available bandwidth on logical crosslinks for the duration of the communication session;

wherein a shortest path is a path that has the minimum delay across the Grid;

wherein the primary path is determined first without any preemption by constructing a reduced Grid by eliminating all crosslinks that do not have enough available bandwidth for some time during the session duration, and then invoking Dijkstra'"'"'s algorithm to find a shortest path;

wherein a path is found by preempting lower priority sessions to accommodate the requested session if a path could not be found without preemption;

wherein the route determination with preemption comprises;

checking if preemption is of help by determining if a route exists if bandwidth allocated to all lower priority sessions is reclaimed;

considering in turn each crosslink traversed by the route and checking if preemption is required on that crosslink to accommodate the session; and

considering each lower priority session traversing such above said crosslink in order of increasing priority, and reclaiming the bandwidth allocated to the lower priority session until enough bandwidth is accumulated to accommodate the high priority session;

wherein multiple alternative paths are generated for the primary path by;

considering in turn each node traversed by the primary path;

removing the crosslink that does not have enough bandwidth in the primary path egressing from a Branch Node; and

determining a shortest path to the Destination Node starting from the Branch Node taking into account bandwidth reclaimed from all lower priority sessions that have been preempted thus far and preempting additional lower priority sessions as needed;

wherein the point-to-point route determination is extended for point-to-multipoint routing by;

considering each destination node in some order, and computing a path to the Destination Node avoiding double counting of bandwidth allocated on common crosslinks in the paths for different destinations;

at the end of the initial iteration, the multipoint tree is the path determined for the first destination; and

merging the current path determined at each iteration with the multipoint tree which is the cumulative result of previous iterations by scanning the nodes on the current path starting from the current destination until a node N is found such that N is on the current path as well as in the multipoint tree; and

attaching the subpath starting from N in the current path as a subtree of N in the multipoint tree.

2. The method of claim 1 wherein the geolocations of nodes are chosen such that at any time, the LEO satellites at these locations together provide global coverage.

3. The method of claim 1 wherein forwarding rules are generated for each payload for the routes determined for the primary path and alternative paths for a session by considering each snapshot spanned by the session, where a snapshot is an instance of the Grid for a specific time interval as predetermined by satellite orbits, and consists of a set of <

Node, Satellite Id>

mappings identifying which satellite is occupying which Node.

4. The method of claim 3 wherein the forwarding rule generation for a snapshot for an edge from a node N1 to a node N2 in a primary path or alternative path comprises:

identifying the satellite A that occupies N1 in the snapshot;

identifying the satellite B that occupies N2 in the snapshot;

identifying the output port P in A for the crosslink connected to B in the snapshot;

identifying the time TS as being the later of either the start time of the session or the start time of the snapshot;

identifying the end time TE as being the earlier of the end time of the session or the end time of the snapshot; and

generating the forwarding rule for satellite A as <

Source terminal address, Destination terminal address, TS, TE, p, P>

, where p is the session priority.

5. The method of claim 4 wherein forwarding rules generated for the primary path and the alternative path branching at a payload for a snapshot are combined into a single forwarding rule by taking the output port element of each rule and constructing a single output sequence {P0, P1} where P0 is the Port element in the forwarding rule for the primary path and P1 is the Port element in the forwarding rule for the alternative path.

6. A non-transitory computer readable medium having computer readable program for operating on a computer for determining a primary path and multiple alternative paths for a point-to-point communication session between two ground terminals connected across by a Low Earth Orbit (LEO) satellite network, said program comprising instructions that cause the computer to perform the steps of:

determining routes using the following information;

changes in terminal —

satellite connectivity due to satellite orbits;

changes in satellite —

satellite connectivity due to satellite orbits;

locations of Source and Destination terminals;

communication session duration;

session traffic bandwidth; and

session traffic priority;

determining routes for the primary path and alternative paths based on a LEO Satellite Grid where the Grid represents a fixed logical satellite constellation topology comprising logical nodes representing geolocations, vertical edges representing logical intra-plane crosslinks, horizontal edges representing logical inter-plane crosslinks, and delay information on crosslinks;

wherein the routes for the primary path and alternative paths are determined by computing shortest paths from a Source Node whose coverage area includes a Source terminal location to a Destination Node whose coverage area includes a Destination terminal location, taking into account available bandwidth on logical crosslinks for the duration of the communication session;

wherein a shortest path is a path that has the minimum delay across the Grid;

wherein the primary path is determined first without any preemption by constructing a reduced Grid by eliminating all crosslinks that do not have enough available bandwidth for some time during the session duration, and then invoking Dijkstra'"'"'s algorithm to find a shortest path;

wherein a path is found by preempting lower priority sessions to accommodate the requested session if a path could not be found without preemption;

wherein the route determination with preemption comprises;

checking if preemption is of help by determining if a route exists if bandwidth allocated to all lower priority sessions is reclaimed;

considering in turn each crosslink traversed by the route and checking if preemption is required on that crosslink to accommodate the session; and

considering each lower priority session traversing such above said crosslink in order of increasing priority, and reclaiming the bandwidth allocated to the lower priority session until enough bandwidth is accumulated to accommodate the high priority session;

wherein multiple alternative paths are generated for the primary path by;

considering in turn each node traversed by the primary path;

removing the crosslink that does not have enough bandwidth in the primary path egressing from a Branch Node; and

determining a shortest path to the Destination Node starting from the Branch Node taking into account bandwidth reclaimed from all lower priority sessions that have been preempted thus far and preempting additional lower priority sessions as needed;

wherein the point-to-point route determination is extended for point-to-multipoint routing by;

considering each destination node in some order, and computing a path to the Destination Node avoiding double counting of bandwidth allocated on common crosslinks in the paths for different destinations;

at the end of the initial iteration, the multipoint tree is the path determined for the first destination; and

merging the current path determined at each iteration with the multipoint tree which is the cumulative result of previous iterations by scanning the nodes on the current path starting from the current destination until a node N is found such that N is on the current path as well as in the multipoint tree; and

attaching the subpath starting from N in the current path as a subtree of N in the multipoint tree.

7. The program of claim 6, wherein forwarding rules are generated for each payload for the routes determined for the primary path and alternative paths for a session by considering each snapshot spanned by the session, where a snapshot is an instance of the Grid for a specific time interval as predetermined by satellite orbits, and consists of a set of <

Node, Satellite Id>

mappings identifying which satellite is occupying which Node.

8. The program of claim 7, wherein the forwarding rule generation for a snapshot for an edge from a node N1 to a node N2 in a primary path or alternative path comprises:

identifying the satellite A that occupies N1 in the snapshot;

identifying the satellite B that occupies N2 in the snapshot;

identifying the output port P in A for the crosslink connected to B in the snapshot;

identifying the time TS as being the later of either the start time of the session or the start time of the snapshot;

identifying the end time TE as being the earlier of the end time of the session or the end time of the snapshot; and

generating the forwarding rule for satellite A as <

Source terminal address, Destination terminal address, TS, TE, p, P>

, where p is the session priority.

9. The program of claim 8 wherein forwarding rules generated for the primary path and the alternative path branching at a payload for a snapshot are combined into a single forwarding rule by taking the output port element of each rule and constructing a single output sequence {P0, P1} where P0 is the Port element in the forwarding rule for the primary path and P1 is the Port element in the forwarding rule for the alternative path.