×

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
First Claim
Patent Images

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.

View all claims
  • 1 Assignment
Timeline View
Assignment View
    ×
    ×