Optimal packet routing method and system for low earth orbit satellite communication system

• US 6,178,163 B1
• Filed: 12/11/1998
• Issued: 01/23/2001
• Est. Priority Date: 12/11/1998
• Status: Expired due to Fees

• Current Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Original Assignee: Northern Telecom Limited (Nortel Networks Corporation)
• Inventors: Yuan, Wei, Subramanian, Sairam
• Primary Examiner(s): Cangialosi, Salvatore
• Application Number:
  US09/210,430
• Time in Patent Office: 774 Days
• Field of Search: 370/323, 370/325, 370/349, 370/393
• US Class Current: 370/323
• 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: H04B 7/195 Non-synchronous stations

Abstract

In a LEO satellite system with the implementation of a virtual network, a method and a system are proposed for arranging an optimal route for data packets to travel. The method and system will diversify the traffic between satellites, and accordingly enhance the efficient use of the entire satellite system. An intermediary satellite is first selected between a source satellite and a destination satellite. Further, an optimal route is found among a plurality of shortest paths between the source satellite and the intermediary satellite, and subsequently another optimal route is found between the intermediary satellite and the destination satellite. Once an optimal route is determined, the route information can be encoded in the header segment of data packets. The data packets will travel from the source satellite, via the intermediary satellite, and eventually to the destination satellite without requiring any satellite to transfer routing tables, and without unnecessarily over burdening the traffic along the way between the source satellite and the destination satellite. By doing so, more communication connections can be made for billable wireless services. Moreover, a randomized selection of an intermediary satellite provides an optimal route, and consequently reduces, if not eliminates, the need for traffic congestion control.

Claims

1. In a Low Earth Orbit satellite communication system using data packets traveling among satellite units and ground stations for information exchange, a method of implementing an optimal route for the data packets to travel from a source satellite to a destination satellite, said method comprising the steps of:

selectively choosing an intermediary satellite at a ground station;

calculating a plurality of shortest paths between the source satellite to the intermediary satellite at the ground station;

calculating a plurality of shortest paths between the intermediary satellite to the destination satellite at the ground station;

selecting an optimal route from the calculated shortest paths between the source satellite to the intermediary satellite at the ground station;

selecting an optimal route from the calculating shortest paths between the intermediary satellite to the destination satellite at the ground station;

encoding route information according to the selected optimal routes from the source satellite to the destination satellite via the intermediary satellite into the data packets at the ground station; and

transmitting the data packets with the encoded route information to the source satellite, wherein the data packets travel from the source satellite to the destination satellite according to the encoded route information.

2. The method of claim 1, wherein the transmission of the data packets from the source satellite to the destination satellite shall not accrue a total time delay exceeding a maximum allowable time delay.

3. The method of claim 1, wherein an optimal route is a selected shortest path between any two satellites for the data packets to travel to achieve a high system efficiency for the Low Earth Orbit satellite communication system.

4. The method of claim 1, wherein a data packet includes a header segment, the header segment having a route information segment therein.

5. The header segment of claim 4, wherein the route information segment includes a series of binary numbers.

6. The header segment of claim 4, further wherein the route information segment includes a second header segment, the second header segment indicating a length of the route information segment.

7. The header segment of claim 4, wherein the route information segment includes route information encoded as a series of binary bits of a prescribed length denoting travel directions for the data packets.

8. In a Low Earth Orbit satellite communication system using data packets traveling among satellites and ground stations for information exchange, a method of implementing an optimal route for the data packets to travel from a source satellite to a destination satellite, said method comprising the steps of:

calculating the optimal route for the data packets to travel from the source satellite to the destination satellite; and

encoding route information for the optimal route directly into the data packets.

9. The method of claim 8, wherein said step of calculating the optimal route further includes the steps of:

selectively choosing an appropriate intermediary satellite for enhancing the overall efficiency of said communication system;

determining an optimal route for said data packets to travel from said source satellite to said intermediary satellite; and

determining an optimal route for said data packets to travel from said intermediary satellite to said destination satellite.

10. The method of claim 8, wherein said step of calculating an optimal route is done by the ground stations.

11. The method of claim 8, wherein said step of encoding route information is carried out by a ground station.

12. The method of claim 8, further includes the step of delivering the data packets from the source satellite to the destination satellite via the optimal route.

13. The method of claim 8, further includes the step of delivering the data packets through a plurality of selected intermediary satellites from the source satellite to the destination satellite.

14. The method of claim 8, whereas a data packet includes a header segment containing the encoded route information.

15. The header segment of claim 14, wherein the encoded route information includes a series of binary bits.

16. The header segment of claim 14, wherein the encoded route information is of a prescribed length.

17. The header segment of claim 14, wherein the encoded route information has a varying length.

18. In a low earth orbit satellite communication system using data packets traveling among satellites and ground stations for information exchange, a method of implementing a most optimal route for the data packets to travel from a source satellite to a destination satellite, said method comprising the steps of:

determining the optimal route by selectively choosing an intermediary satellite at a ground station;

encoding route information from the source satellite to the destination satellite via the intermediary satellite into the data packets at the ground station; and

delivering the data packets from the source satellite to the destination satellite according to the encoded route information.

19. The method of claim 18, wherein said step of determining the optimal route includes selecting the intermediary satellite as a function of an enhancement of overall efficiency of the communication system.

20. The method of claim 18, wherein said step of determining the optimal route further includes the steps of:

selecting a first shortest path between the source satellite to the intermediary satellite so as to minimize traffic congestion between the source satellite and the intermediary satellite; and

selecting a second shortest path between the intermediary satellite to the destination satellite so as to minimize traffic congestion between the intermediary satellite and the destination satellite.

21. The method of claim 18, wherein said step of encoding route information includes utilizing a series of binary bits of a predetermined length, the series of binary bits occupying a segment of the data structure of a data packet.

22. The binary bits of claim 21, wherein the segment of the data structure is a header segment of a data packet.

23. The method of claim 18, wherein said step of encoding route information includes utilizing a series of binary bits of a varying length, the series of binary bits occupying a segment of the data structure of a data packet.

24. The binary bits of claim 23, wherein the segment of the data structure is a header segment of a data packet.

25. An efficient Low Earth Orbit satellite communication system having data packets as a means for information exchange, the data packets traveling among telecommunication hardware means through a most optimal route, said system comprising:

a first telecommunication hardware means for initiating a request to transfer data;

a first ground station for determining an optimal route for the data packets to travel and encoding route information for the optimal route into the data packets;

a source satellite for transmitting said data packets;

a destination satellite for receiving and further transmit the data packets;

a second ground station for receiving the data packets from the destination satellite; and

a second telecommunication hardware means for receiving the transferred data initiated by the first telecommunication hardware means from the second ground station.

26. The system of claim 25, wherein the first telecommunication means is a wireless telephone.

27. The system of claim 25, wherein the first ground station calculates a plurality of potential paths that would not result in an impermissible overall time delay for the data packets to travel.

28. The system of claim 25, wherein the first ground station further selectively chooses an appropriate intermediary satellite for determining the optimal route in order to enhance the overall efficiency of the satellite communication system.

29. The first ground station of claim 28, further wherein the first ground station determines an optimal route for the data packets to travel from the source satellite to the intermediary satellite.

30. The first ground station of claim 28, further wherein the first ground station determines an optimal route for the data packets to travel from the intermediary satellite to the destination satellite.

31. The first ground station of claim 28, wherein the first ground station determines an optimal route for the data packets to travel from the source satellite to the destination satellite via a plurality of intermediary satellites.

32. In a low earth orbit satellite communication system using data packets traveling among satellites and ground stations for information exchange, a system of implementing a most optimal route for the data packets to travel from a source satellite to a destination satellite, said system comprising:

a ground station for determining the optimal route and encoding route information from the source satellite to the destination satellite;

at least one data packet encoded with the route information; and

a plurality of satellites for receiving and transmitting the data packets according to the encoded route information.

33. The system of claim 32, wherein said ground station further selects an intermediary satellite as a function of an enhancement of overall efficiency of the communication system.

34. The system of claim 32, wherein said ground station further selects a first shortest path between the source satellite to the intermediary satellite so as to minimize traffic congestion between the source satellite and the intermediary satellite.

35. The system of claim 32, wherein said ground station further selects a second shortest path between the intermediary satellite to the destination satellite so as to minimize traffic congestion between the intermediary satellite and the destination satellite.

36. The system of claim 32, wherein said data packets encoded with route information includes a series of binary bits of a predetermined length, the series of binary bits occupying a segment of the data structure of said data packets.

37. The binary bits of claim 36, wherein the segment of the data structure is a header segment of a data packet.

38. The system of claim 32, wherein said data packets encoded with route information includes a series of binary bits of a varying length, the series of binary bits occupying a segment of the data structure of a data packet.

39. The binary bits of claim 38, wherein the segment of the data structure is a header segment of a data packet.