A Thesis Presented to The Academic Faculty

by

Chao Chen

In Partial Fulfillment of the Requirements for the Degree Doctor of Philosophy in Electrical and Computer Engineering

School of Electrical and Computer Engineering Georgia Institute of Technology May 2005

Copyright © 2005 by Chao Chen

Approved by:

Professor Ian F. Akyildiz, Committee Chair
Professor Ragupathy Sivakumar Professor Chuanyi Ji

Professor Gregory D. Durgin

Professor Mostafa H. Ammar (College of Computing)

Date Approved: April 27, 2005

To my parents, Jixun Chen and Jinwen She, and to my husband Zesheng Chen

ACKNOWLEDGEMENTS

First and foremost, I would like to express my sincere thanks to my dissertation advisor, Dr. Ian F. Akyildiz, for his continuous support and guidance throughout my doctoral study. This work would not have been possible without all the insightful discussions with him. Not only did Dr. Akyildiz lead me into the world of networking research, he has also taught me in many other ways that could lead me to success in my future career.
I would like to acknowledge Dr. Chuanyi Ji, Dr. Ragupathy Sivakumar, and Dr. Gregory D. Durgin for being on my dissertation proposal committee and defense committee. I would also like to thank Dr. Mostafa H. Ammar for serving on my dissertation defense committee. Their invaluable comments and enlightening suggestions have helped improve the quality for this dissertation.
I would like to extend my sincere gratitude towards Eylem Ekici for his patience and insightful discussions during my dissertation process. I would also like to thank the present and past members of the Broadband and Wireless Networking (BWN) Laboratory. Special thanks go to Jiang (Linda) Xie, Weilian Su, Ozgur Baris Akan, Jian Fang, and Shantidev Mohanty. Their friendship and assistance made my last four years an enjoyble experience.
I would also like to thank my parents for their love, support and encouragement. I am deeply thankful to my husband, Zesheng Chen, for his love, patience, encouragement, and sacrifices. I am also grateful to the brothers and sisters in Atlanta Chinese Christian Campus Fellowship (ACCCF) for their continuous encouragement and prayers. Last, I thank God who grants me wisdom, strength, and confidence. I praise Him for what He has done in my life.

TABLE OF CONTENTS

ACKNOWLEDGEMENTS		iv
LIST OF TABLES   		ix
LIST OF FIGURES   		x
ABBREVIATIONS 		xii
SUMMARY 		xv
I	INTRODUCTION		1
 1.1	Satellite Networks		1
 1.2	Interplanetary Internet		3
 1.3	Research Objectives and Solutions		6
 1.4	Thesis Outline		8
II	SATELLITE NETWORK FUNDAMENTALS		10
 2.1	Classification of Satellites		10
 2.2	Elements of Satellite Networks 		13
III	QOS-BASED ROUTING ALGORITHM IN MULTIMEDIA SATEL-
LITE NETWORKS   		16
 3.1	Motivation and Related Work   		16
 3.2	Application Scenario 		18
 3.3	QRA: QoS-based Routing Algorithm 		20

 3.3.1	Deterministic UDL Routing 		21
 3.3.2	Probabilistic ISL Routing 		24
 3.3.3	Handover Rerouting 		25
3.4	Performance Evaluation 		26
IV	SATELLITE GROUPING AND ROUTING PROTOCOL FOR HI-
ERARCHICAL SATELLITE IP NETWORKS		30
 4.1	Motivation and Related Work   		30
 4.2	Hierarchical Satellite Network Architecture 		32

 4.2.1	Satellite Network Components 		33
 4.2.2	Gateway Address Translation 		36
4.3	Mobility Modeling 		36
 4.3.1	LEO Layer Modeling		37
 4.3.2	MEO Layer Modeling		38
 4.3.3	Satellite Groups and Snapshot Periods		39

 4.4	Definitions		41
 4.5	SGRP: Satellite Grouping and Routing Protocol		44

 4.5.1	Delay Report		45
 4.5.2	Delay Exchange 		45
 4.5.3	Routing Table Calculation  		47
 4.5.4	Congestion Avoidance 		48
 4.5.5	Satellite Failure Reaction 		50
4.6	Performance Evaluation 		51
 4.6.1	Snapshot Periods Identification		51
 4.6.2	Traffic Modeling		52
 4.6.3	Delay Performance Evaluation 		55
 4.6.4	Communication Overhead Analysis   		62
 4.6.5	Summary and Discussion 		64
V TERRESTRIAL/SATELLITE NETWORK INTEGRATION THROUGH
BORDER GATEWAY PROTOCOL - SATELLITE VERSION .	66
 5.1	Motivation and Related Work   		66
 5.2	The Hybrid Terrestrial/Satellite Network Architecture 		67

 5.2.1	Network Components 		68
 5.2.2	Packet Forwarding 		70
5.3	BGP-S: Border Gateway Protocol - Satellite Version 		71
 5.3.1	BGP-S Connection Setup 		73
 5.3.2	Path Discovery and Prioritization  		74
 5.3.3	BGP-S Connection Termination  		79

5.4   Performance Evaluation		80
 5.4.1	Topology Generation Process		81
 5.4.2	Simulation Results		84
 5.4.3	Summary		91
VI	A ROUTING FRAMEWORK FOR INTERPLANETARY INTER-
NET 		92
 6.1	Motivation and Related Work   		92
 6.2	Network Description		96

 6.2.1	Network Components		96
 6.2.2	Routing Framework 		100
6.3	Space Backbone Routing - External 		101
 6.3.1	Location-Predicted Directional Broadcast (LPDB) 		102
 6.3.2	Receiver-Initiated On-demand Routing (RIOR) 		106
6.4	Space Backbone Routing - Interior 		113
 6.4.1	Problem Modeling 		113
 6.4.2	Possible Solutions 		115
 6.4.3	Discussion  		116
6.5	Performance Evaluation 		118
 6.5.1	Evaluation of SBR-external Protocols 		118
 6.5.2	Evaluation of SBR-interior Policies 		125
VII	CONCLUSIONS AND FUTURE RESEARCH DIRECTIONS  .	130
7.1	Research Contributions		130
 7.1.1	Connection-Oriented Routing in Multimedia Satellite Networks 130
 7.1.2	Connectionless Routing in Hierarchical Satellite IP Networks	131
 7.1.3	Integration of Satellite IP Networks and the Terrestrial Internet132
 7.1.4	Routing in the Interplanetary Internet 		133
7.2	Future Research Directions 		133

REFERENCES		136

VITA	142

LIST OF TABLES

Table 1	Parameters for MEO and LEO Satellite Constellations		.   51	
Table 2	Internet Hosts Distribution by Continent in January 2001 [7].  . .	.   54	
Table 3	Continental Traffic Flow Shares in %		.   55	
Table 4	Simulation Parameters for Hybrid Terrestrial/Satellite Network. .	.   85	
Table 5	Values of p Under Filtered Gateway Selection Method		.   90	
Table 6	Comparison of Different Traffic Types in IPN Internet		.   102	
Table 7	Format of a Route Entry.   		. 107	

LIST OF FIGURES

Figure	1	Interplanetary Internet Architecture		4	
Figure	2	Planetary Network Architecture.   		4	
Figure	3	Satellite Orbit Types.   		11	
Figure	4	An Example Satellite Network in Walker Star Constellation		14	
Figure	5	General Satellite Network Architecture.   		19	
Figure	6	An Example of Overlapping Satellite Footprints.   		21	
Figure	7	Illustration of the Calculation of the Remaining Coverage Time. . .	24	
Figure	8	Comparison of Path Metrics under Different Connection Duration
Time.   		28	
Figure	9	LEO/MEO Joint Constellation		34	
Figure	10	Logical Locations in the LEO Layer.  		37	
Figure	11	Initial Positions of the MEO Satellites		38	
Figure	12	A MEO Footprint		40	
Figure	13	Congestion Area of Congested Link lxi^x2 When r = 1		44	
Figure	14	Intra-Plane Exchange		46	
Figure	15	Inter-Plane Exchange.  		47	
Figure	16	Distribution of Snapshot Duration		52	
Figure	17	Earth Zone Division and User Density Levels [66]		53	
Figure	18	User Activity in Each Hour (%) [55]		53	
Figure	19	Comparison of Average End-to-End Delay Performance.   		59	
Figure	20	Comparison of Instantaneous End-to-End Delay Performances. . . .	61	
Figure	21	Communication Overhead Comparison		63	
Figure	22	The Hybrid Terrestrial/Satellite Network Architecture		68	
Figure	23	The Activation of Peer Gateways and Connection Setup		73	
Figure	24	The Processing of AS Paths Learned via BGP-S.   		76	
Figure	25	The Schematic Structure of ITSTG.   		80	
Figure	26	Integrated Terrestrial/Satellite Topology Generation	
x	84	

	Networks		.   86	
Figure 28	Performance Comparison between BGP-S and BGP-4. 		.   87	
Figure 29	Effect of Satellite Parameters on BGP-S Performance		.   88	
Figure 30	Effect of Gateway Selection Methods on BGP-S Performance.  . .	.   90	
Figure 31	Proposed Routing Framework in the IPN Internet		.   95	
Figure 32	AR Link luv (t)		.   98	
Figure 33	Location-Predicted Directional Broadcast		.   105	
Figure 34	Route Discovery and Repair for Controlled Data Delivery.  		. 110	
Figure 35	Network Model for IPN Internet		. 118	
Figure 36	Performance Comparison of LPDB with LAR and LPSP		. 122	
Figure 37	Performance Comparison of RIOR with LPDB		. 124	
Figure 38	Performance Comparison of Different SBR-i Policies		. 128	
Figure 39	Message Dropping Probability under Different Queue Limit. . . .	. 128	

Figure 27 Performance Comparison of BGP-4 in Integrated and Terrestrial

ABBREVIATIONS

AoA	Angle of Arrival	
AODV	Ad hoc On-demand Distance Vector protocol	
APR	Active Peer Register	
AR	Autonomous Region	
AS	Autonomous System	
ATM	Asynchronous Transfer Mode	
BGP	Border Gateway Protocol	
BGP-S	Border Gateway Protocol - Satellite version	
BRITE	Boston university Representative Internet Topology gEnerator	
CBR	Constant Bit Rate	
CCSDS	Consultive Committee for Space Data Systems	
DRA	Datagram Routing Algorithm	
DREAM	Distance Routing Effect Algorithm for Mobility	
DSN	Deep Space Network	
DSR	Dynamic Source Routing	
DTN	Delay Tolerant Network	
EBGP	Exterior Border Gateway Protocol	
EGP	Exterior Gateway Protocol	
ESA	European Space Agency	
FHRP	Footprint Handover Rerouting Protocol	
GEO	Geosynchronous Earth Orbit	
GPS	Global Positioning System	
IBGP	Interior Border Gateway Protocol	

ICO	Intermediate Circular Orbit	
IGP	Interior Gateway Protocol	
IOL	Inter Orbital Link	
IP	Internet Protocol	
IPN	Interplanetary	
ISL	Inter-Satellite Link	
ISP	Internet Service Provider	
ITSTG	Integrated Terrestrial/Satellite Topology Generator	
LAR	Location Aided Routing	
LEO	Low Earth Orbit	
LPDB	Location-Predicted Direct Broadcast	
LPSP	Location-Predicted Single Path routing	
LQ	Longest Queues	
MEO	Medium Earth Orbit	
MLSR	Multi-Layered Satellite Routing algorithm	
MW	Minimum Waiting	
NASA	National Aeronautics and Space Administration	
ORT	Original Routing Table	
PGW	Peer Gateway	
QoS	Quality of Service	
QRA	QoS-based Routing Algorithm	
RIB	Routing Information Base	
RIOR	Receiver-Initiated On-demand Routing	
RN	Representative Node	
SBR	Space Backbone Routing	
SBR-e	SBR-external	
SBR-i	SBR-interior	

SCPS-NP	Space Communication Protocol Standard - Network Protocol	
SGRP	Satellite Grouping and Routing Protocol	
SoS	Satellite over Satellite	
SRT	Simplified Routing Table	
UDL	User Data Link	
UTC	Coordinated Universal Time	
VBR	Variable Bit Rate	
VSAT	Very Small Aperture Terminal	

SUMMARY

Satellite systems have the advantage of global coverage and offer a solution for providing broadband access to end users. Local terrestrial networks and terminals can be connected to the rest of the world over Low Earth Orbit (LEO) satellite networks simply by installing small satellite interfaces. With these properties, satellite systems play a crucial role in the global Internet to support real-time and non-real-time applications. Routing in satellite networks, and the integration of satellite networks and the terrestrial Internet are the key issues to support these services.
Furthermore, the developments in space technologies enable the realization of deep-space missions such as Mars exploration. The Interplanetary Internet is envisioned to provide communication services for scientific data delivery and navigation services for the explorer spacecrafts and orbiters of future deep-space missions. The unique characteristics posed by deep-space communications call for different research approaches from those in terrestrial networks.
The objective of this research is to develop advanced architectures and efficient routing protocols for satellite and space networks to support applications with different traffic types and heterogeneous quality-of-service (QoS) requirements. Specifically, a new QoS-based routing algorithm (QRA) is proposed as a connection-oriented routing scheme to support real-time multimedia applications in satellite networks. Next, the satellite grouping and routing protocol (SGRP) is presented as a unicast routing protocol in a two-layer satellite IP network architecture. The border gateway protocol - satellite version (BGP-S) is then proposed as a unified routing protocol to accomplish the integration of the terrestrial and satellite IP networks at the network

layer. Finally, a new routing framework, called the space backbone routing (SBR), is introduced for routing through different autonomous regions in the Interplanetary Internet. SBR provides a self-contained and scalable solution to support different traffic types through the Interplanetary Internet.

CHAPTER I

INTRODUCTION 1.1    Satellite Networks
Satellite networks are regarded as important parts of future communications systems. Especially for the next-generation system that promises global coverage, satellite networks are integral parts of the global network structure because of the following reasons [14]:
 •	Satellite services can be provided over a wide geographical area, including remote, rural, urban, and inaccessible areas.
 •	Satellite communication systems have a global reach with very flexible bandwidth-on-demand capabilities.
 •	Alternative channels can be provided for connections that have unpredictable bandwidth demands and traffic characteristics to achieve maximum resource utilization.
 •	New users can easily be added to the system by simply installing satellite interfaces at customer premises. As a result, network expansion will be a simple task.
 •	Satellite can act as a safety valve for terrestrial networks. Fiber failure or network congestion problems can be recovered easily by routing traffic through a satellite channel.
Compared to Geostationary Earth Orbit (GEO) and Medium Earth Orbit (MEO) satellites, Low Earth Orbit (LEO) satellites have shorter round trip delays and lower

transmission power requirements. Hence, local terrestrial networks and terminals can be connected to the rest of the world over satellite networks simply by installing small satellite interfaces. With these properties, satellite systems play a crucial role in the global Internet to support both real-time and non-real-time applications. Routing in satellite networks, and the integration of satellite networks and the terrestrial Internet are the key issues to support these services.
Real-time and non-real-time applications are expected to be supported by satellite networks using connection-oriented and connectionless routing protocols, respectively. Real-time applications impose strict delay bounds and are sensitive to delay variations and loss. The connection-oriented routing protocols assume ATM-like switches in the satellites. Once the path between two satellites is determined and the switches on the path are configured, the packets belonging to the same flow follow this pre-determined path. A certain level of quality-of-service (QoS) is provided to the connection. Different connections between the same source-destination pair can follow different paths.
With the explosive growth of the Internet, there is an initiative in the commercial and also in the military world to push the IP technology also to satellite networks. In other words, the switches on the satellite could be IP switches. These IP switches are connected to each other as well as to ground stations. Non-real-time applications are charaterized by relaxed delay bounds. They are also insensitive to the variations in delay. Thus, connectionless routing schemes can be used to support this type of traffic. In connectionless schemes, packets are routed in the network individually without considering which flows they belong to.
The satellite routing problems, both connection-oriented and connetionless routing, become especially interesting when the changing distances between satellites in different orbits as well as the movement of the satellites are considered, which cause a constant change in the network topology. The existing solutions developed for fixed networks cannot be applied to satellite networks because they cannot handle the

frequent topological changes of the LEO satellite systems. On the other hand, the solutions developed for terrestrial mobile ad hoc networks incur high protocol overhead since they do not consider nodes with predictive movement patterns. New and efficient routing protocols for satellite networks are necessary to handle the dynamic topology and utilize wireless resources in the satellite networks to their fullest extent. These protocols should also be inter-operable with the methods used in current terrestrial communication networks.

1.2   Interplanetary Internet
The developments in space technologies enable the realization of deep space scientific missions such as Mars exploration. These missions produce significant amounts of scientific data to be delivered to the Earth. In addition, these missions require autonomous space data delivery at high data rates, security of operations, and seamless inter-operability between in-space entities.
For successful transfer of scientific data and reliable navigational communications, NASA enterprises have outlined significant challenges for development of next-generation space network architectures. The next step in the design and development of deep space networks is expected to be the Internet of the deep space planetary networks and defined as the Interplanetary (IPN) Internet [63].
The IPN Internet is envisioned to provide communication services for scientific data delivery and navigation services for the explorer spacecrafts and orbiters in future deep space missions [18]. Many of these future planetary missions, which will be performed by the international space organizations such as NASA and European Space Agency (ESA), have already been scheduled for the next decade [2]. An example IPN Internet architecture is shown in Figure 1 and helps to build a general space network architecture that combines differently challenged parts. It has the following architecture elements [12]:

Figure 1: Interplanetary Internet Architecture.

Figure 2: Planetary Network Architecture.
 •	IPN Backbone Network: It provides a common infrastructure for communications among the Earth, outer-space planets, satellites, and intermediate relay stations.
 •	Planetary Networks: The expanded view of the proposed infrastructure of the planetary network in Figure 1 is illustrated in Figure 2, which is composed of planetary satellite network and planetary surface network. This architecture can be implemented at any outer-space planet, providing interconnection and cooperation among the satellites and surface elements on a planet.
— Planetary Satellite Network: It is composed of satellites that may lie in multiple layers [21] and provides the following services [34]: intermediary

4

caching and relay service between Earth and the planet, relay service between the in-situ mission elements, and location management of planetary surface networks.
— Planetary Surface Network: It provides the communication links between high-power surface elements, such as rovers and landers, that have the capability to connect with satellites. Moreover, the planetary surface network includes surface elements that cannot communicate with satellites directly. These elements, e.g., sensor nodes and balloons, are often organized in clusters and spread out in an ad hoc manner.

It is clear that the IPN Internet is expected to extend the current space communications capabilities to a point where the boundaries between the terrestrial and space communications become transparent. The experience obtained, thus far, from the space missions and NASA's Deep Space Network (DSN) [8] help to understand the unique challenges posed by the deep space communication environments. However, there exist significantly challenging and unique characteristics of the deep space networking paradigm that still need to be addressed for the objective of IPN Internet as follows:
 •	Extremely long and variable propagation delays.
 •	Asymmetrical forward and reverse link capacities.
 •	High link error rates for radio-frequency (RF) communication channels.
 •	Intermittent link connectivity.
 •	Lack of fixed communication infrastructure.
 •	Effects of planetary distances on the signal strength and the protocol design.
 •	Significant power, mass, size, and cost constraints for communication hardware and protocol design.

• Backward compatibility requirement due to high cost involved in deployment and launching processes.

These characteristics lead to different research challenges and hence necessitate different approaches and protocol designs at each of the networking layers for the IPN Internet. Although some of these challenges are also encountered in the terrestrial wireless networking domain, most of them are unique to deep space environment and they further amplify the effects of those other similar factors. Consequently, the realization of the IPN Internet depends on how effectively these challenges are addressed.

1.3   Research Objectives and Solutions
In this research, new and efficient routing protocols are proposed to address the challenges in satellite networks and Interplanetary Internet, respectively. Specifically, the following four areas are investigated under this research:
 1.	Connection-orirented routing in multimedia satellite networks: Realtime applications have strict requirements on bandwidth and delay variations. Satellite link handover increases delay jitter and signaling overhead as well as the termination probability of ongoing connections. To satisfy the QoS requirements of multimedia applications, satellite routing protocols should consider link handovers and minimize their effect on active connections. The QoS-based routing algorithm (QRA) is proposed as a connection-oriented routing scheme to support QoS requirements of multimedia services in LEO satellite networks. It aims to reduce the number of rerouting attempts due to satellite handover, thus reducing delay jitter while guaranteeing bandwidth requirements.
 2.	Connectionless routing in hierarchical satellite IP networks: Routing in satellite IP networks is related to the creation and maintenance of routing tables.

Since the satellite network topology is dynamic, routing tables must reflect the most up-to-date network topology. Considering the scarcity of the wireless resources and the power limitation of the satellites, routing table calculations and maintenance must be performed at minimal costs. The satellite grouping and routing protocol (SGRP) is proposed for hierarchical LEO/MEO satellite IP networks. The main idea of SGRP is to transmit packets in minimum-delay path and distribute the routing table calculation of the LEO satellites to multiple MEO satellites. Recovery mechanisms are also developed to reduce the effect of satellite failures and link congestion.
3.	Integration of satellite IP networks and the terrestrial Internet: The
satellite networks are envisioned as a part of the next-generation Internet. The integration of terrestrial and satellite networks requires development of new schemes enabling the seamless operation of terrestrial and satellite IP networks. The protocols designed to discover and propagate paths in the terrestrial networks do not consider subnetworks with very long propagation delays. The border gateway protocol - satellite version (BGP-S) is proposed as an efficient and automated method of discovering and advertising paths that pass through satellite networks. BGP-S is designed to work in only one terrestrial gateway in every autonomous system and enables the forwarding of discovered paths in the Internet using the BGP-4 protocol.
4.	Routing in the Interplanetary Internet: The space backbone routing (SBR)
is proposed as a single framework for advanced routing functions that can satisfy
the needs of various applications in the IPN Internet. SBR is able to forward
messages in the IPN backbone network in spite of its time-varying and unre-
liable nature. SBR has two integral parts: SBR-external and SBR-interior.
SBR-external addresses the delivery of remote control messages and scientific

data through the IPN Internet. The location-predicated directional broadcast (LPDB) is proposed for the reliable delivery of remote control messages and automatic data reports. For controlled data delivery that contains large amounts of scientific data and requires high reliability, a combination of reactive and proactive approaches is utilized in our proposed receiver-initiated on-demand routing (RIOR). SBR-interior is executed within an autonomous region (AR). It exchanges inter-AR routing information among backbone nodes within an AR and schedules inter-AR message transmissions. We give the problem definition of contact allocation and traffic dispatching, which are two important functionalities of SBR-interior. As a first attempt, the longest queues (LQ) policy for the contact allocation and the minimum waiting (MW) policy for traffic dispatching are proposed.

1.4    Thesis Outline
The objective of this research is to develop advanced architectures and efficient routing protocols for satellite and space networks to support applications with different traffic types and heterogeneous QoS requirements. Chapter 2 starts with the fundamentals of satellite networks. Classification of satellites and elements of satellite networks are introduced in this chapter. Chapter 3 focuses on the connection-oriented routing protocol in multimedia satellite networks. A new QoS-based routing algorithm (QRA) is proposed to support real-time applications in multimedia satellite networks. Next, routing in satellite IP networks is addressed in Chapter 4. The satellite grouping and routing protocol (SGRP) is proposed in this chapter to support data traffic in hierarchical LEO/MEO satellite networks. In Chapter 5, the integration of satellite IP networks and the terrestrial Internet is investigated through a unified routing protocol called border gateway protocol - satellite version (BGP-S). A novel routing framework for the IPN Internet is introduced in Chapter 6.   It is based on the hierarchical

architecture and specifically addresses the challenges of the IPN Internet. Within this framework, protocols are proposed for the delivery of different types of traffic through the IPN Internet. Finally, Chapter 7 summarizes the the research contributions and identifies several future research directions.

CHAPTER II

SATELLITE NETWORK FUNDAMENTALS

A satellite system consists of a space segment and a ground segment. The ground segment contains gateway stations and control centers. The control centers handle overall network resource management, satellite operation, and orbiting control. The gateway stations act as network interfaces between various external networks and the satellite network. They also perform protocol conversion and address translation. The space segment is composed of satellites in certain constellations. In this chapter, satellite network architecture and some basic terminologies are introduced. In Section 2.1, satellites are classified according to their orbits. Section 2.2 introduces the elements and basic terminologies in satellite networks.

2.1    Classification of Satellites
Satellites can be classified according to the types of their orbits. Figure 3 shows the relative positions of different satellite orbit types. Most proposed satellite communication systems use circular orbits, where the Earth is located in the center of the circle. A circular orbit guarantees that satellites move at constant speeds and the time interval that a satellite passes overhead remains constant. Satellites in circular orbits can be further classified as Geosynchronous Earth Orbit (GEO), Medium Earth Orbit (MEO), or Low Earth Orbit (LEO) satellites according to their altitudes.
Geosynchronous Earth Orbit (GEO) satellites are located 35, 786km above the Equator. The angular velocity of a satellite in this orbit matches the angular rate of rotation of the Earth. This makes the satellite appear stationary when observed from the surface of the Earth. This useful feature has resulted in the orbit becoming

extremely popular. The angular separation between two adjacent GEO satellites is at the limit of terrestrial antenna discrimination and can be as low as 1.5° [73].
GEO satellites can serve very large areas. Much of the Earth can be covered with a minimum of three GEO satellites. Propagation delay between an Earth station and a GEO satellite varies with the difference in position in longitude and latitude, but is around 125ms, or around 250ms between ground stations. This leads to the widely-quoted half-second round-trip delay for communications via GEO satellite. GEO satellites are usually used as single-hop networks with or without on-board switching capabilities. The VSAT network [33] is an example for communication network using GEO satellites.
Medium Earth Orbit (MEO) satellites locate at altitudes of between 9, 000km and 11, 000km, between the inner and outer Van Allen radiation belts. MEO satellites appear in motion when observed from the Earth, with visibility period of tens of

Figure 3: Satellite Orbit Types.

minutes. The average round-trip delay for MEO satellites ranges between 110 — 130ms [14]. ICO system [37] is an example of MEO satellite networks.
Low Earth Orbit (LEO) satellites lie beyond the upper atmosphere but below the peaks of the inner Van Allen radiation belt. They have lower altitudes than the MEO satellites, typically between 500km and 2000km. A large number of LEO satellites are required to provide simultaneous global coverage. The actual number of satellites used depends on the coverage required and the minimum elevation angle desired for communication. With a large number of satellites and their resulting small footprint areas and small spotbeam coverage areas, large amounts of frequency reuse become possible across the Earth, providing large system capacity.
LEO satellites move rapidly relative to the surface of the Earth, with a speed at over 25,000km/hour. This implies that the visibility of a satellite lasts for only a few minutes. Propagation delay between ground and a LEO satellite is often under 15ms. Because of low delay characteristics as well as low power requirements for end-stations, LEO satellites are more attractive for real-time communications. Examples of LEO satellite networks include Iridium [49], Teledesic [61], and Globalstar [72].
Satellites with elliptical orbits have varying distances from the Earth as well as variable speeds. Coverage of communication services from elliptical orbits is generally only provided when the satellite is moving very slowly relative to the ground while at apogee. Useful elliptical orbits are inclined at 63.4° to the Equator, so that orbital motion near apogee appears to be stationary with respect to the Earth's surface. High inclination and high altitude enable coverage of high latitudes. Satellite constellations with elliptical orbits are usually used to serve over specific areas in specific periods of time when the communications demand is high. The most famous examples of satellite constellations with elliptical orbits are Molniya and Tundra [51].

2.2   Elements of Satellite Networks
This thesis focuses on the routing problems in satellite networks where the satellites are moving in non-GEO circular orbits. These networks usually have two basic types of constellation geometry: " Walker star' and " Walker delta" constellations [50]. Walker star constellation consists of orbital planes inclined at a constant angle of near 90°. Any point on the Earth's surface sees overhead satellites moving at regular intervals either from north to south (descending) or from south to north (ascending). Walker delta constellation consists of orbital planes inclined at a constant angle of less than 90°. Ascending and descending planes of satellites and their coverage continuously overlap, rather than being separated as in the Walker star constellation.
In Figure 4, we use a satellite system in Walker star constellation to illustrate some basic elements of a satellite network. The satellite network is composed of N separate orbits (planes), each with M satellites. The planes are separated from each other with the same angular distance of . They cross each other only over the North and South Poles. The satellites in a plane are separated from each other with an angular distance of ^jp.. Since the planes are circular, the radii of the satellites in the same plane are the same at all times and so are the distances from each other.
The footprint or the coverage area of a single satellite is defined as the area on the Earth's surface where the satellite can be seen under an elevation angle equal to or greater than the minimum elevation angle of the system. The footprint of a GEO satellite does not change over time whereas the footprints of non-GEO satellites move with respect to the Earth. The maximum time a single satellite covers a fixed point on the Earth's surface ranges between 8 — 11 minutes for LEO satellites and between 30 — 50 minutes for MEO satellites. The footprint of a satellite is usually divided into cells. The cells can move in parallel to the movement of the satellites, i.e., they can "sweep" the Earth's surface. Alternatively, the cells can be Earth-fixed, i.e., the cell boundaries do not change as the satellite moves. The spot beam serving

a cell, however, is switched as the satellite moves over the coverage area. Satellites in a LEO constellation communicate with the ground stations (i.e., mobile terminals or gateways) over user data links (UDLs).
A satellite communicates with other satellites via inter-satellite links (ISLs). Each satellite has several neighboring satellites. The links between satellites in the same plane are called intra-plane ISLs. The links between satellites in different planes are called inter-plane ISLs. On intra- and inter-plane ISLs, the communication is bidirectional. The intra-plane ISLs are maintained at all times. All satellites move in the same circular direction within the same plane. The propagation delays on the intra-plane ISLs are always fixed. For inter-plane ISLs, however, the propagation delays are highly variable. For example, the propagation delays become longest over the Equator and get smaller near the polar regions. The inter-plane ISLs are operated only outside the polar regions. When the satellites move towards the polar regions, the inter-plane ISLs become shorter. When two satellites in adjacent planes cross the poles, they switch their positions. In order to allow this switching, the inter-plane

Figure 4: An Example Satellite Network in Walker Star Constellation.

ISLs are shut down in polar regions and re-established outside of the polar regions. The ISLs across the seam, i.e., the boundary between the counter-rotating planes, have to be turned off very frequently.
Satellite networks may be composed of satellites moving at different altitudes. In these hybrid satellite networks, it is also possible that communications occur between the satellites at different orbits over bidirectional inter-orbital links (IOLs).

CHAPTER III

QOS-BASED ROUTING ALGORITHM IN MULTIMEDIA SATELLITE NETWORKS

3.1   Motivation and Related Work
In recent years there has been a rapid growth of multimedia services in Internet. As integral parts of the global communication infrastructure, satellite networks will be faced with an increasing demand on real-time multimedia applications. Satellite systems can provide global coverage and constantly sustain high bandwidth services. Non-GEO satellites have propagation delays comparative to terrestrial networks. The on-board processing capability and inter-satellite links (ISLs) introduced in many LEO satellite systems help to build a robust communication framework. However, satellite networks have different characteristics from terrestrial networks. The constant movement of satellites causes network connectivity and satellite link delays varying. When satellite links are switched off, handover is required to maintain the active connections. There are two types of handover in satellite networks [15]:
 •	Inter-satellite handover: When the sender or receiver leaves the coverage area of the initial satellite, the entire path should be recreated. The occurrence of inter-satellite handover depends on the time that the ground station remains in a satellite coverage area.
 •	ISL handover: Because of satellite movement, some ISLs in the network are not always available. For example, when a satellite enters the polar regions, its adjacent inter-plane ISLs are turned off. Similarly, inter-plane ISLs through the seams have very short lifetime. Consequently, if a path contains such a link, it must be rerouted when the link is turned off. The timing of link shutdowns can

be calculated, since the link termination only depends on the movement of the satellites. Therefore, if the connection duration is known, the occurence of ISL handover can be predicted.
Link handover causes delay jitter and signaling overhead. Moreover, because of the deficiency of network resources and the delay caused by rerouting, handover increases the forced termination probability of ongoing connections, which is less desirable than blocking a new connection request. For real-time multimedia applications that impose strict delay bounds and are sensitive to delay variations. connection-oriented routing protocols through a satellite network should consider link handover and minimize its effect on each individual connection.
A dynamic routing concept is introduced for ATM-based satellite networks in [69]. The dynamic network topology is considered a periodically repeated series of K topology snapshots. Using a sliding window, a set of k-ordered path sequences between satellite nodes is selected in each topology snapshot with an aim to minimize handover delay jitter and reduce link handover rate. However, the optimization is not done between end users and the inter-satellite handovers are not considered. The predictive routing protocol proposed in [35] provides guaranteed QoS in satellite networks. It exploits the deterministic nature of the LEO satellite topology to predict traffic load on the ISLs up to a short time in the future. k-ordered paths for a particular connection are computed for each staggered cell to maximize the minimum residual bandwidth. The optimal path is picked from the path set to reduce the link changes as well as to balance the user traffic. This protocol does not consider inter-satellite handovers and the computation overhead grows dramatically as k increases. The probabilistic routing protocol [64] utilizes the LEO satellite network dynamics and call statistics, and tries to reduce the number of rerouting attempts resulting from link handover. An ISL is removed from route computation if it is expected to experience an ISL handover with a probability higher than a target probability (p)

during the route establishment phase of a new call. The computation of the ISL handover probability is deduced from the hexagon effective footprints of satellites.
In this chapter, a new QoS-based routing algorithm (QRA) is proposed to reduce both the inter-satellite handover and the ISL handover probabilities. QRA was first described in [24]. It is based on a general satellite constellation model in which satellite footprints may be overlapped. The predictability of link handover is utilized while computing the ISL path through the satellite constellation. Different from the probabilistic routing protocol [64], QRA does not remove the links with a large handover probability thus to avoid high new call blocking probability. A modified version of the footprint handover rerouting protocol (FHRP) [65] is used for rerouting when link handover occurs.

3.2   Application Scenario
The satellite network architecture considered in this research is shown in Figure 5. It consists of satellites orbiting the Earth and ground stations on the Earth's surface. Satellites may lie within one layer or in multiple layers such as a combination of LEO and MEO layers. Ground stations may be fixed, performing as gateways between the satellite and terrestrial networks. Mobile ground stations are handheld terminals that move around with users. It is assumed that the movement of mobile ground stations can be ignored compared to the fast movement of satellites.
The satellites are connected through ISLs. As explained in Chapter 2, there are two types of ISLs: intra-plane ISLs and inter-plane ISLs. Intra-plane ISLs connect satellites within the same plane and are maintained permanently since their relative positions are fixed. Inter-plane ISLs are between satellites in different planes. They are operated only outside the polar regions and need to be switched off temporarily with the change of distance and viewing angle between them. The ISLs enable the routing of messages in satellite network without requiring terrestrial resources.

Satellites communicate with the ground stations via UDLs. Satellite footprints can be overlapped, thus a ground station can be connected to several satellites.
Since the satellite constellation is well-planned before deployment and does not change during operation, typically the location of any satellite (i.e., altitude, latitude, and longitude) at any time can be calculated according to the trajectory information. The location information of mobile ground stations (i.e., latitude and longitude) can be obtained using Global Positioning System (GPS) technology and reported to the satellites. The location information of fixed and mobile ground stations is stored in databases either centrally or in a distributed manner, and can be retrieved whenever needed. The satellites periodically exchange their local information, which includes the available bandwidth on outgoing links and location information of ground stations within their footprints.
Real-time multimedia applications impose strict delay bounds and are sensitive to delay variations. For a network to deliver QoS guarantees, it must reserve and control resources accordingly. The changing connectivity pattern of satellites calls for link handover to maintain active connections. However, link handover increases delay jitter as well as signaling overhead. Excessive handovers also increase the blocking probability of ongoing connections.

Figure 5: General Satellite Network Architecture.

The goal of our new QoS-based routing algorithm (QRA) is to reduce the delay jitter while guaranteeing the bandwidth requirements. It incorporates the location information of satellites and ground stations to predict the lifetime of satellite links, trying to build stable paths for connection requests and reduce the probability of link handovers during connection lifetime. The routing problem considered in this research is as follows: The connection establishment requests arrive on-line; A connection is established by allocating the required bandwidth along some path between the source and the destination nodes; The allocated bandwidth is released when the connection terminates.
It is assumed that the duration of a connection is exponentially distributed with known mean holding time. When a ground station issues a connection request, it should specify the following parameters:
 1.	Location of source s: It is known to the ground station by GPS service;
 2.	ID of destination ground station d: It is used to retrieve the location of d in the location databases;
 3.	Expected connection duration 1///: It is specified through the distribution probability function;
 4.	Requested bandwidth bw: For constant bit rate (CBR) type applications, the requested bandwidth is fixed through the connection duration. For variable bit rate (VBR) type applications, the requested bandwidth can be described by maximum bandwidth and sustained bandwidth, or calculated using a token bucket model and the requested delay bound [35].

3.3   QRA: QoS-based Routing Algorithm
In this section, the detailed design of our new QRA is presented. It includes the following three parts:

 •	Deterministic UDL routing chooses the ingress and the egress satellites according to the locations of the source and the destination ground stations.
 •	Probabilistic ISL routing selects the path within the satellite constellation between the ingress and the egress satellites.
•	Handover rerouting in case of inter-satellite handover and ISL handover. 3.3.1   Deterministic UDL Routing
Most of the existing work assume that the minimum number of satellites is used to achieve global coverage. The overlapped area of the neighbor satellites' footprints thus does not constitute a significant portion of the overall coverage area. In reality, however, the overlapped area increases at higher latitude for polar-type satellite constellations. Furthermore, overlapped coverage areas can be utilized to increase the resources available to regions with dense population. Figure 6 shows an example of overlapping satellite footprints. Ground station A is within the coverage areas of satellite Si, S2, and S3. If the satellites move upwards, it is better for A to select S3 as the relay satellite to avoid inter-satellite handover, although A can receive stronger signals from Si and S2 than S3 at the time it initiates a call.
In this research, a ground station may lie in the overlapping areas of several

Figure 6: An Example of Overlapping Satellite Footprints.

satellite footprints. Upon receiving the connection request, the source ground station performs the UDL routing, i.e., selects the ingress and the egress satellites for the path between the source and the destination. Generally, there are two types of metrics to select the access satellite of a ground station:
 •	Maximum coverage time (Max-Time): The satellite with sufficient bandwidth and the maximum remaining coverage time to the ground station is selected. By doing so, the probability of inter-satellite handover is minimized. The computation of the remaining coverage time of satellites can be done with the knowledge of location information and will be explained later in this section.
 •	Maximum received power (Max-Power): The satellite with sufficient bandwidth and the strongest received power is selected. It is assumed that all satellites have the same transmit power. Then, the selection of access satellite based the Max-Power metric equals choosing the closest satellite to the ground station. This can be easily done using the satellites' location information.
To reduce the inter-satellite handover probability, we choose the Max-Time metric for UDL routing in QRA. Once the ingress and the egress satellites have been chosen, the required bandwidth is allocated along the corresponding UDLs. [PARAMETERS]:
 -	rf: The radius of satellite S's footprint. rf = Re • [arccos(^ • cos9min) — 9min], where Re is the Earth's radius, rs is the radius of the satellite orbit, 9min is E's minimum elevation angle.
 -	(v,e0): Satellite S's footprint velocity and movement direction. Note that the velocity varies with the satellite s location and orbit parameters (e.g, altitude and inclination angle).
 -	(Le,le): Ground station E's latitude and longitude.

- (Ls,ls): Satellite S's latitude and longitude.
Multimedia traffic has longer connection holding times compared to the traffic in the traditional circuit switched networks. For multimedia connections, Earth's rotation can no longer be ignored. Hence, the Earth's rotation is considered in computing the footprint velocity v and direction e0.
Given the above parameters, the calculation of the remaining coverage time of satellite S for ground station E is done by the following two steps: Step 1: Calculating azimuth angle of S toward E
Using the law of sines and cosines for spherical triangles,

sin \le—ls\-sin Ls
sin a   =	1,
cos y  =  cos Le cos Ls cos(ls — le) + sin Le sin Ls. The azimuth angle (AZ) can be computed as:

a,	if S lies northeast of E,
n — a,    if S lies southeast of E,
AZ = I	(2)
n + a,    if S lies southwest of E, 2n — a,  if S lies northwest of E. Step 2: Computing the remaining coverage time of satellite S towards E
Suppose after time T, the satellite moves from S to S' and the ground station E is on the edge of the satellite's footprint as shown in Figure 7, the trace of the sub-satellite point during time period T is represented by SS'. First, if S, S', and E lie in a line,
= j r, — SE = r, — yRc,  if «° = AZ
I rf + SE = rf + YRe,  if |AZ — e0\ = n. Otherwise, LESS' = |n — |AZ — e0||. Using the law of sines in spherical triangle AESS',
sin(r,/Re)     sin y       sin(SS'/Re) sin i ESS' = sm7 = sin(Z ESS' + 5)'

SS' = Re • arcsin [sin(rf /Re) sin(^SS' + 5) 1	(4)
sin / ESS'
where
sin ZESS' • sin Yn
5 = arcsin[	————].
sin(rf/Re)
Therefore, the remaining coverage time T = SS'/v. The satellite with the maximum coverage time T* is selected as the access satellite. The ingress and the egress satellites are the satellites that provide the maximum coverage time (i.e., T*u and T*d) to the source and the destination ground stations, respectively.
Assuming exponential connection duration Tc with mean       then,
Prob[inter-satellite handover] = P(Tc > T*) = e~^Tr,	(5)
where T** = min(Tr*u, Tr*d). 3.3.2   Probabilistic ISL Routing
The ISL routing is done after selecting the ingress and the egress satellites. Since ISL handover operations cause high signaling overhead and long delays, to consider the effect of ISL handover, two coefficients are assigned to each link i: propagation delay di and existence probability p^.

Figure 7: Illustration of the Calculation of the Remaining Coverage Time. the remaining travel distance SS' can be written as:

 •	Propagation delay (di): The propagation delay of each satellite link at any specified time can be easily deducted by the satellite trajectory information. di for an inter-plane ISL is changing constantly with the satellite movement.
 •	Existence probability (pi): This is the probability that the ISL link will not be shut down either before the connection ends or an inter-satellite handover occurs.
Since the knowledge of the exact time that the inter-satellite handover would occur is known after the deterministic UDL routing, and the connection duration Tc conforms to exponential distribution with mean 1///, if we can predict the ISL handover time (Ti>lh) of link i, then
I 1,	if Tiilh > Tr*,
Pi = Prob[Titih > min(Tc,T*)} = <	'	(6)
[ 1 - e-^lh,   if Ti,ih <T;.
The cost of link i is computed as:

{di • (1 — ln pi),    if available bandwidth > bw,
(7)
oo,	if available bandwidth < bw.
As pi — 0,Ci — oo. Higher existence probability contributes to lower link cost. When
pi = 1, Ci is represented by the link propagation delay. The Dijkstra's algorithm [46]
is applied to find the minimum cost path through the satellite constellation upon a
connection request. Once an ISL path is found, the required bandwidth is allocated
along the path.

3.3.3   Handover Rerouting
The handover rerouting algorithm is modified from the augmentation algorithm in FHRP [65]. Suppose if at time t = te, one of the ground station moves out of the footprint of its access satellite S, a new satellite S' with the maximum coverage time is selected as the new access satellite. Instead of computing a new ISL path immediately, the path augmentation algorithm is handled by S' as follows:

 1.	The satellite S' checks whether it is already on the old ISL path. If so, the portion of the current path from S up to S' is deleted and the reserved bandwidth is released. The new ISL path starts from S'.
 2.	If S' is not on the current ISL path, a direct link to one of the satellites on the path is searched starting from the other end of the path, i.e., if S' is serving as the ingress satellite to the source ground station, the satellites are checked backwards starting from the egress satellite. If a direct link with sufficient bandwidth to support the connection is found, the link is augmented to the original path.
 3.	If a direct link between S' and the satellite nodes on the current ISL path with required capacity is not found, the reserved bandwidth on the path is released and a full rerouting (i.e., deterministic UDL routing followed by probabilistic ISL routing) is performed.
 4.	If the ingress and the egress satellites of the last computed route have both been updated, the probabilistic ISL routing between the new ingress and egress satellites is called. This is to prevent frequent rerouting attempts resulting from non-optimal routes.
During connection time, if one of the satellite links along the ISL path needs to be switched off, full rerouting is called.

3.4   Performance Evaluation
We have extended the VINT network simulator (ns2.1b9a) [9] by including modules of our QoS-based routing algorithm. A LEO satellite network with 288 satellites are considered in the simulation. There are 12 orbital planes with 24 satellites in each plane. Satellite orbits are 1, 375km in altitude with an orbit inclination angle of

84.7°. The minimum elevation angle of ground stations is 40°. Each satellite has two intra-plane ISLs and two inter-plane ISLs.
To evaluate the QRA, the path metrics (i.e., path delay, delay jitter, rerouting frequency, and rerouting overhead) of a connection between a source-destination pair are monitored. The source is located at (33.39°iV, — 84.26°W) in Atlanta, United States, and the destination is at (39.55°iV, 116.25°) in Beijing, China. The sender generates connection requests with different mean connection duration (1//). The results are the averages of 100 independent simulations. Performance comparisons are made among three different algorithms: our QRA (i.e., Max-Time deterministic UDL routing with probabilistic ISL routing), "Max-Power + ISL" (i.e., Max-Power deterministic UDL routing with probabilistic ISL routing), and the minimum delay routing using Dijkstra's algorithm [46]. The path metrics for these three algorithms under different mean connection duration are depicted in Figure 8.
Figure 8(a) and 8(b) give the delay metrics (i.e., end-to-end delay and delay jitter) of the above three routing algorithms. Apparently, the minimum delay routing returns the path with shortest end-to-end delay. As the other two algorithms divide the end-to-end routing into UDL routing and ISL routing, the resulted path is not optimal in terms of delay. However, their extra delay difference is within 5% of the delay of the shortest path. The delay jitter is represented by the variance of end-to-end delays. Among the three algorithms, our QRA has the minimum delay jitter. This is because that rerouting in QRA tries to keep the original path and reduce the link handover probability. On the other hand, the frequent path updates generated by the minimum delay routing gives more opportunity to delay variance among different paths. Especially when the mean connection duration increases, path updates more frequently, which in turn causes larger delay jitter.
The average rerouting frequency and the rerouting overhead of the three routing algorithms are shown in Figure 8(c) and 8(d), respectively. The rerouting frequency

Figure 8: Comparison of Path Metrics under Different Connection Duration Time.

is measured by the number of handover attempts in the connection duration. For QRA and "Max-Power + ISL" algorithms, we also plotted their values of full rerouting frequency, which stands for the average number of rerouting attempts with actual computation of a new ISL path. The number of rerouting is the sum of the full rerouting and the augmentation rerouting attempts, which are explained in Section 3.3.3. For minimum delay routing, all handover attempts call for full rerouting computation. Among the three algorithms, minimum delay routing has the highest rerouting frequency. Moreover, the full rerouting frequency values of QRA and "Max-Power + ISL" routing algorithms are much lower than that of the minimum delay algorithm.

(a) Delay

(b) Delay jitter

(d) Rerouting overhead

(c) Rerouting frequency

The rerouting overhead is represented by the number of updates in the routing tables of all nodes, i.e., removing the record of a connection or recording a rerouted connection. The augmentation rerouting of QRA in Section 3.3.3 attempts to keep part of the original path by checking if the new access satellite is on or adjacent to the old path. Therefore, less nodes need to be updated and processing overhead is reduced. This is also shown in the Figure 8(d) where minimum delay routing causes much higher rerouting overhead than the other two algorithms.
In summary, the simulation results show that QRA reduces delay jitter, rerouting frequency, and rerouting processing overhead.

CHAPTER IV

SATELLITE GROUPING AND ROUTING PROTOCOL FOR HIERARCHICAL SATELLITE
IP NETWORKS

4.1   Motivation and Related Work
Satellite systems have the advantage of global coverage and inherent broadcast capability, and offer a solution for providing broadband access to end-users. Compared to GEO satellites, LEO and MEO satellite networks have shorter round trip delays and lower transmission power requirements. In many constellations, direct ISLs provide communication paths among satellites. They can be used to carry signaling and network management traffic as well as data packets [71].
The constant movement of satellites, however, causes LEO and MEO satellite networks to have dynamic topologies. The ISL connectivity changes based on the distance and azimuth angle between the two end satellites. Hence, routing in this environment is a challenging problem. Most of the routing schemes developed for LEO satellite networks assume a connection-oriented network structure. In [22] and [70], the dynamic routing problem is tackled by a discrete time network model. In each equal-length interval, the satellite network is regarded as having a fixed topology so that optimal link assignments can be performed. Call statistics are exploited in [64] to maintain the initial paths and reduce the re-routing frequency so as to minimize the signaling overhead. In [48], a satellite over satellite (SoS) network architecture, which is composed of LEO and MEO satellite layers, is proposed. Long distance-dependent traffic is carried in the MEO layer to reduce satellite hops and resource consumption. A LEO/MEO two-tier satellite network and the corresponding routing strategies are described in [41]. However, it is assumed that there is no direct ISL between any two

LEO satellites and all network routing functions involve MEO satellites.
With the rapid growth of Internet-based applications, proposed broadband satellite networks are required to transport IP traffic [74]. Routing protocols for IP-based LEO satellite networks have also been introduced. The datagram routing algorithm (DRA) [30] aims to forward data packets on minimum propagation delay paths. The satellite network is regarded as a mesh topology consisting of logical locations. Data packets are routed distributively on this fixed topology. DRA causes no overhead since the satellites do not exchange any topology information. In [40], link state packets are flooded only as far as the routing radius for a given satellite. Shortest path routing is used in the near vicinity of the destination, whereas data packets are routed based on the destination satellite's position when they are far away. The basic shortcoming of both above schemes for connectionless routing is that the metrics used to calculate the paths do not reflect the total delay a packet may experience in the network. The delay, which is composed of propagation, processing, queuing, and transmission delays, can vary greatly because of the positions of the individual satellites and the network load.
A routing protocol (MLSR) for multilayer satellite IP networks has been proposed in [13]. MLSR computes the routing tables of the satellites based on the delay measurements collected periodically. Under MLSR, LEO satellites are grouped and managed by MEO satellites. LEO group topologies are hidden from other satellites by representing them as meta-nodes in the topology. The routing tables are calculated by GEO satellites based on this summarized information and are further refined by MEO managers for LEO satellites. In many cases, however, satellites are sparsely located in the MEO layer, LEO group abstraction cannot be restored in the MEO layer, and MLSR cannot be implemented effectively. Furthermore, MLSR relies on periodic routing table calculations to handle ISL congestion and lacks a fast-reacting congestion resolution mechanism.

In this chapter, a new routing protocol called satellite grouping and routing protocol (SGRP) is proposed. The SGRP protocol was first introduced in [26] and refined in [25]. SGRP operates on a two-layer satellite network consisting of LEO and MEO satellites. Collaboration between LEO and MEO satellite layers is utilized in SGRP: The MEO satellites compute outing tables for the LEO layer. The main idea of SGRP is to transmit packets in minimum-delay paths and distribute the routing table calculation for the LEO satellites to multiple MEO satellites. The LEO satellites are divided into groups according to the footprint areas of the MEO satellites in each snapshot period. Snapshot periods are determined according to the predictable MEO trajectory and the changes in the LEO group memberships. The MEO satellite that covers a set of LEO satellites becomes the manager of that LEO group. Group managers are in charge of collecting and exchanging the link delay information of the LEO layer, and calculating routing tables for their LEO members. The LEO satellites receive routing tables from their group managers. Using SGRP, the calculation of routing tables is shifted to the MEO satellites, which effectively distributes the power consumption between the LEO and MEO satellites. Since the signaling traffic is physically separated from the data traffic, link congestion does not affect the responsiveness of delay reporting and routing table calculation. Responsive mechanisms to address link congestion and satellite failures are also included in SGRP.

4.2   Hierarchical Satellite Network Architecture
Routing complexity is a crucial issue in satellite networks. Since LEO satellites already have limited processing power, it is not desired to have all LEO satellites compute their own routing tables. The terrestrial gateways are constrained by geographical distribution of continents. Meanwhile, in order to reduce system costs, satellite coverage areas are usually not highly overlapped, which means that the terrestrial gateways do not have line-of-sight communication with many satellites (usually less

than 5 satellites for gateways outside the polar regions). If we choose to use the terrestrial gateways for route computation, the majority of the LEO satellites would be required to send their measurements to the gateways over several hops. Similarly, the routing tables calculated by the terrestrial gateways would be transmitted to the LEO satellites via several hops as well. Both directions of transmission result in an increase of the traffic load. On the other hand, if there is a MEO satellite constellation in operation and ISLs between the LEO and MEO satellites can be set up, the LEO satellites can be partitioned into groups and the computation overhead can be distributed among the MEO satellites. Each LEO group would have line-of-sight communication with a MEO satellite in the second layer. Transfer of link delay measurements and routing table distribution are reduced and the traffic load is not increased in the LEO satellite network.

4.2.1   Satellite Network Components
We consider a two-layer satellite network and the terrestrial gateway stations. The grouping of the LEO satellites is determined by the snapshot concept. In a snapshot period, the LEO satellites are grouped according to the footprint areas of the MEO satellites. The satellite members of a group are constant over this period. The LEO satellites have direct links to their MEO group managers. The terrestrial gateways are fixed on the Earth, they have direct links to the LEO satellites within sight. They are in charge of address translation and the communication between the terrestrial autonomous systems and the satellite network. The terrestrial gateways, together with the LEO and MEO satellites, form an autonomous system.
The satellite network is composed of a LEO satellite layer and a MEO satellite layers, as shown in Figure 9. We assume that both satellite layers provide global coverage.

• MEO layer: The MEO layer is composed of all the MEO satellites in the

network. It has a total number of NM x MM satellites, where NM is the number of planes in the MEO constellation, and MM is the number of satellites in a MEO plane. A MEO satellite is denoted by Mitj, where i = 1,NM,j = 1,MM.
• LEO Layer: The LEO layer consists of all the LEO satellites in the network. The total number of satellites in this layer is NL x ML, where NL is the number of planes in the LEO constellation, and ML is the number of satellites in a LEO plane. The LEO satellites are organized into a Walker-star constellation [67].

The logical location concept [30] is used for the LEO layer. In this research, however, the position of a logical location is not fixed and the satellite that embodies a logical location varies with time. When the satellite assigned to a logical location changes, the successor satellite must take the necessary routing information from its predecessor. The links adjacent to the predecessor LEO satellite are also switched to the new LEO satellite. A logical location is referred to as (n, m), where n is the plane number, 1 < n < NL, and m refers to the satellite position in the plane, 1 < m < ML. The LEO satellite representing the logical location (n, m) at time t is referred to as
Ln,m.

Figure 9: LEO/MEO Joint Constellation.

The MEO satellite topology is captured by a series of snapshots. In every snapshot period, the logical locations covered by a MEO satellite are considered to be fixed although the LEO satellites that embody the logical locations may change. The snapshot period is determined according to the predictable MEO trajectories and the positions of the logical locations. The snapshot concept hides the mobility of the MEO satellites and is independent of the properties of the MEO constellation. The algorithm to determine the snapshot periods will be detailed later in Section 4.3.
As explained in Chapter 2.2, there are three types of duplex links in the network:
 •	ISLs: The communication within the same satellite layer occurs through ISLs. ISL^d or ISL<2_>s denotes an ISL that connects two satellites s and d in the same layer.
 •	IOLs: The communication between MEO and LEO satellites occurs over IOLs. If a LEO satellite s lies in the coverage area of a MEO satellite d, they are connected by an IOL, which is referred to as IOLs^d or IOL<2_>s.
 •	UDLs: LEO satellites communicate with the terrestrial gateways via UDLs. The UDL between a LEO satellite s and a terrestrial gateway G is denoted by UDLs^G or UDLG^s.
In order to partition the LEO satellite network into administrative domains, the LEO satellites are grouped according to the footprint areas of the MEO satellites in each snapshot period. A LEO group is defined as a set of logical locations that reside in the coverage area of the same MEO satellite. The members of a LEO group change as the MEO satellite moves and the LEO logical locations change. Hence, the groups must be redefined in each snapshot period. In a snapshot period, the MEO satellite that covers a set of logical locations becomes the group manager. Group managers are responsible for collecting and exchanging link delay information received from LEO layer, and calculating the routing tables for the LEO group members. A LEO

group Cij is the collection of all LEO satellites that lie in the coverage area of the MEO satellite Miyj, Liyj = {Liyj(k) | k = 1,Kij}, where Kiyj is the number of LEO members in group Liyj. The members of a LEO group are connected to the manager MEO satellite via IOLs. For example, in Figure 9, the LEO group of MEO satellite Miyj is Liyj, which has six members Liyj (1) through Liyj (6).

4.2.2   Gateway Address Translation
The terrestrial gateways are in charge of address translation and communication between the terrestrial autonomous systems and the satellite network. When a packet needs to be routed from gateway Gi to gateway G2 through satellite network, Gi first looks for the nearest LEO logical location for itself and G2. Since the LEO logical locations are fixed with respect to the Earth, only the geographical location of the gateway is needed to determine the closest logical location. Assume that the logical location (ni, mi) is the nearest logical location to Gi, and (n2, m2) is the nearest to G2, G1 then sends the packets to Lni ymi, the LEO satellite that currently represents the logical location (n1,m1), through UDLg^l mi. The destination field of the packet is set as logical location (n2, m2), and is used for routing decision inside the LEO network. After Ln2ym2 receives the packet, it extracts the original destination G2 from the data, then forwards the packet to gateway G2 though UDLL  ma     .

4.3   Mobility Modeling
In order to create the snapshots of the satellite network, the exact positions of the LEO and MEO satellites must be known. Using the location information, the LEO groups and their group managers can be determined. In this section, we build a mobility model for LEO/MEO joint constellation. It gives the positions of the LEO and MEO satellites at any time t, and the method to determine LEO groups and snapshot periods.

4.3.1   LEO Layer Modeling
The latitude <(n, m) and longitude 9(n, m) of a LEO logical location (n, m) vary with time t and are calculated as follows:
,,      ,     f <o(n) - (m - 1)A< + OFS,	if m< \ML/2],
<p(n, m) = <	(8)
[ -180° - <0(n) + (m - 1)A<< + OFS,   if m > \ML/2]. where OFS = (wL x t) MOD A<< is the offset within the latitude interval A0 (= 360°/ML), wL is the angular velocity of LEO satellites; 0o(n) gives the latitude of the first satellite on the nth plane, and is defined as

{d>i,   n odd , where 01 e (90°, 90° - A<f>/2), \<j>2 - <pi\ < A<f>/2. 02,  n even
The first satellites in even-numbered planes have the same latitude <1, whereas the first satellites in odd planes are with latitude <2. Therefore, the satellites with same number m in all planes form a zigzag pattern, as shown in Figure 10 if <1 = <2.

Figure 10: Logical Locations in the LEO Layer.
The longitude 9(n,m) of the logical location (n,m) is given by:
6(n,m) = 90 + (n - 1)A0,	(9)
where 90 is the longitude of the first plane, and A9 = 180°/NL.

As satellites move, different satellites embody the same logical location at different time t.

4.3.2   MEO Layer Modeling
In this section, we illustrate the method to determine the satellite positions in a MEO Walker delta constellation consisting of two planes. This model can also be modified to be used with other MEO constellations.
In a MEO satellite constellation like ICO [37], there are two crossing points for MEO planes 1 and 2 and are located on the equatorial plane, i.e, at latitude 0°. It is assumed that at time t = 0, MEO satellites M1>1 and M2>1 both move to northeast and are located at the first and second crossing points with longitude of 0° and 180°, respectively. The latitude $ and longitude © of MEO satellite M1j at any time t can be computed by:

$ = arcsin(cos a • sin r), $ e [-90°, 90°],
360kt +arccos(cos y/ cos $) - wEt,  if $ > 0,	(10)
360k2 — arccos(cos y/ cos $) — wEt,  if $ < 0.
where a is the inclination angle for MEO plane; y = wMt + (j — 1)A©, with wM being the MEO satellite angular velocity, and A© = 360/Mm; k1 and k2 are independent

Figure 11: Initial Positions of the MEO Satellites.

integers to satisfy © e [0°, 360°]; wE is the angular velocity of the Earth.
The latitude and longitude of the MEO satellites on plane 2 can be determined
by:
latitude(M2 y j) = latitude(M1 y j),	^
longitude(M2 yj) = (longitude(M1 yj + 180°))MOD 360°.

4.3.3   Satellite Groups and Snapshot Periods
Based on the exact positions of the LEO and MEO satellites, and the footprint of every MEO satellite, we create the LEO satellite groups and determine the length of the snapshot period at any time t.
First, the MEO footprints on the LEO layer need to be calculated to determine group membership of the LEO satellites. The half-sided center angle of the MEO footprint on the LEO layer ip is calculated as:

ip = 90 — tmin — arcsin( Re + hh • cos tmin),	(12)
RE + hM
where RE is the radius of the Earth, hL and hM are the plane altitudes of the LEO and MEO layer, respectively, and tmin is the minimum elevation angle of the MEO satellites from the LEO layer.
Suppose that a LEO satellite Lnym is at (0, 9), where 0 and 9 represent the latitude and the longitude of Lnm, and a MEO satellite Mij is at ($, ©). For Lnm to lie in the footprint of Miyj, the following condition must be satisfied:

lA'Bl
ZA'OB = 2 arcsin     	l— < p.	(13)
2(Re + hL)
where as shown in Figure 12, A and B represent the positions of Mij and Lnym, respectively, A' is the sub-satellite point of Mi j on the LEO orbit sphere.
We assume that the satellite network topology is periodic with T, where T is the least common multiple of the revolution periods of the Earth and the MEO satellites, and the time needed for any two satellites to be exactly on a given logical

location. T is referred to as system cycle. The satellite topology can be considered as a periodically repeating series of P topology snapshots in the system cycle T. Over the interval [ti, ti+i], i = 0,1, ...,P — 1, the LEO satellites' group membership is constant. Snapshot periods may have different lengths.
The snapshots and the LEO satellite groups are created according to the following criteria:
 1.	A LEO group is created according to the footprints of the MEO satellites on the LEO layer. Generally, the LEO satellites that lie in the same footprint of a MEO satellite form a group, and this MEO satellite becomes the group manager.
 2.	According to the above definition, LEO satellite groups can be overlapped. If a LEO satellite lies in an overlapping area covered by several MEO satellites, it has more than one MEO group managers. To balance the management load, a primary manager is chosen among them. The primary manager takes care of the routing table calculation of a LEO satellite in a snapshot period. Since the trajectory of the MEO satellites is predictable, a LEO satellite chooses the MEO

Figure 12: A MEO Footprint.

satellite with the longest remaining coverage time as its primary manager1. The members of a LEO group change as the MEO satellites move, hence, the groups must be redefined for each snapshot period.
3. The snapshot period is further determined according to the changes in the LEO group membership. Assuming that at time t = ti, at least one of the LEO satellites is no longer covered by its primary manager in the current snapshot i, in such case, a new snapshot of the system must be created. Every LEO satellite chooses the group manager with the maximum predicted service time as its primary manager for snapshot i + 1. According to this criteria, new snapshots are created at time t1,t2,...,tP = T. The snapshots and the LEO groups repeat with a period of T.

Group information database can be uploaded to all satellites. The database information includes the start time of each snapshot period, LEO satellites' group membership and their MEO group managers in every snapshot.

4-4   Definitions
Definition 1 (Group Manager and Primary Manager) Let H(x) refer to the MEO manager set of LEO satellite x, then H(x) = {Mi j | x E Li j} includes all MEO satellites whose footprints cover x. The primary manager of x is written as VH{x). It is selected from H(x), and has the longest remaining coverage time for x, i.e., within all MEO satellites that currently cover x, PH(x) still covers x after all others exclude x in their footprints.

PH(x) = argmax{remaining coverage time of Mij, w.r.t x | Mij E H(x)}.    (14)

1A mathematical method is explained in Chapter 3.3.1 to compute the remaining coverage time of a satellite over a ground station. The same method can be used to determine the remaining coverage time of a MEO satellite to a LEO satellite.

Definition 2 (Care-of Member List) Every MEO satellite has a "care-of member" list in each snapshot period. The care-of member list CM(Mij) of a MEO satellite Mij is defined as

CM(MhJ) = {x \ PH(x) = MhJ}.	(15)

Hence, Mitj is the primary manager of every LEO satellite in CM(Mij).

Definition 3 (Delay Function) Let lx^y be a direct ISL from node x to node y in LEO layer. The delay function V(lx^y) is defined as follows:

{Delay from x to y,     3 lx^y,
x y,	(16)
oo	,     otherwise.
Definition 4 (Delay Report) Delay report VlZ(x) of LEO satellite x is a set of tuples {y, V(lx^y)}, where y is a LEO satellite such that ISLx^y exists between x and
y.
Delay report VlZ(Mij) of MEO satellite Mitj is a collection of the delay reports of Miyj's care-of members,

Vn(Mitj) = {DR(x) \ x e CM(Mitj)}.	(17)

Delay report VTZ(Mi) of MEO plane i is a collection of the delay reports of Mij in plane i,
DR(Mi) = {VR(Mhj ),j = 1,...,Mm }.	(18)

Definition 5 (Plane Crossing Point) Crossing points of plane i and plane l are referred to as CPindicating where the two planes cross each other. There are two crossing points for each pair of i and l.

After collecting the delay information in the LEO network, each MEO satellite has the same picture of the LEO network topology. MEO satellite Mijj computes the

minimum delay paths from CM(Mij) to all destinations. These paths are then used to create the routing tables. Before sending out routing tables to the LEO satellites, Mi j tries to aggregate faraway LEO destinations into groups to reduce the size of the routing tables. To do this, the remote groups of a source satellite x are defined.

Definition 6 (Remote Group) A remote group of LEO satellite x is a LEO group that is not covered by any satellite in H(x). The set of x's remote group is written as

RM(x) = {Litj I MitJ E H(x)}.	(19)

Definition 7 (Path) Px—y is defined as the minimum delay path associated with source x and destination y. It is a sequential list of the satellites on the path.

In our satellite network architecture, the routing tables are created by the MEO satellites using the delay measurements in the LEO layer. MEO group managers prepare different routing tables for each of their care-of members. In SGRP, two types of routing tables are needed: original routing table and simplified routing table.

Definition 8 (Original Routing Table) Original routing table ORTMi . is kept in MEO satellite Mi j. It provides an entry for each of its care-of members, and registers paths from CM(Mij) to all destinations. The path from satellite x to a destination satellite y is defined as:

ORT(x,y)= Vx—y, where x eCM(M%j).	(20)

Definition 9 (Simplified Routing Table) Simplified routing table SRT x of LEO satellite x is created by and sent from its MEO manager Mi j. The construction of SRTx is based on original routing table ORTMi . and the group membership of destination satellites. Each entry of this routing table has a destination field and a next-hop field, where next-hop is the second node on Px—Dest, and written as SRTx(Desi). Here Dest can be any LEO satellite or a remote group. If the paths to all satellites

in a remote group Citj have the same next-hop, the entries to all those LEO satellite destinations are replaced by a single entry in the simplified routing table. The destination field of this entry is set as Ci>j.
Definition 10 (Congestion Area) The congestion area of a congested link lxi^x2 is defined as:
CA(lxi^x2) = U{lyiI where VXk^yi < r,k = 1 or 2},	(21)
where r is the radius in the number of hops of the congestion area.

Figure 13: Congestion Area of Congested Link lxi^x2 When r =1.

4-5   SGRP: Satellite Grouping and Routing Protocol
The goal of our new satellite grouping and routing protocol (SGRP) is to forward the packets on minimum delay paths in spite of the satellite mobility, and to distribute the routing table calculation for the LEO satellites to multiple MEO satellites. The delay metric used in the route computation is the sum of the processing, queuing, and transmission delays in the satellites and the propagation delays on the ISLs. Routing tables are calculated by the MEO satellite group managers, transmitted to and stored in the LEO satellites.
In this section, the detailed design of SGRP is presented. It includes three phases:

44

 •	Delay report from LEO satellite to MEO layer,
 •	Delay exchange in MEO layer,
 •	Routing table calculation.
SGRP also has mechanisms to resolve congestion and satellite failures to avoid dropping packets.

4.5.1	Delay Report
Delay information of LEO links needs to be reported to MEO satellites every Tc period, it is done as follows:
Initialization: At the beginning of a new snapshot period, MEO satellite Mi j's care-of member list CM(Mi j) is initialized as empty.
Step 1: Delay Report - At the end of every measurement interval of length Tc, a LEO satellite x monitors the delay on its outgoing links. A delay report VlZ(x) is created from the measured delay value and sent to x's primary manager Mij = PH(x) via
IOLx^Mi>j .
Step 2: Delay Reception - After receiving a delay report VlZ(x), Mij adds x into its own delay report CM(Mij). CM(Mij) is formed after all the delay reports from Mi j s care-of members have been received.

4.5.2	Delay Exchange
After collecting link delay measurements from their group members, MEO group managers exchange the measurements inside the MEO layer to obtain a common picture of the LEO network topology. Our proposed exchange method includes two steps: intra-plane exchange and inter-plane exchange. Step 1: Intra-plane Exchange
In MEO layer, the delay reports are first circulated in the same MEO plane.

 1.	MEO satellite Mij sends its delay report VlZ(Mij) to its two adjacent neighbors, MipP, in the same plane through ISLMij—MipP, where p = j - 1,j + 1.
 2.	After receiving a delay report VlZ(Miyj), MipP checks to see if it has been received before. If so, it is discarded.
 3.	MipP forwards the new report VlZ(Mij) on the other intra-plane ISL, which is different from the incoming one, i.e. ISLm, , V-Mt,p+1 or ISLm, , V-MtpP-1.
Figure 14 shows the circulation of delay reports in MEO plane 1. M1 y2 sends out V1Z(M1 y2) to its neighbors M1 y1 and M133. The report then follows the dashed lines in the direction of the arrows. In the end, M14 and M1 y5 each receives a duplicate report, upon which the circulation of V1Z(M1 2) is terminated. Step 2: Inter-plane Exchange
After the LEO delay information is exchanged within plane i, a copy of the same information must be sent out to plane l,l = 1,NM, l = i, and circulated there as well. The steps of the inter-plane delay report exchanging are as follows:
1. The two satellites on plane i nearest to plane crossing points CP(i, l) are chosen to be plane i's starting points. The two satellites nearest to CP(i, l) on plane l are selected as their reception satellites respectively. VTZ(Mi) is sent from plane i to plane l via the inter-plane ISLs.

Figure 14: Intra-Plane Exchange.

Figure 15: Inter-Plane Exchange.

 2.	The two reception satellites on plane l forward VlZ(Mi) clockwise via their intra-plane ISLs to the neighboring MEO satellites.
 3.	After receiving VlZ(Mi), Mim first checks to see whether it has been received before. If so, the delay report is discarded, otherwise, it is forwarded clockwise to the next neighboring MEO satellite.
Figure 15 shows the transfer of VTZ(M1) from plane 1 to plane 2. CP(1, 2) = {A,B}. Mi)i and M1y3 are chosen as the starting points, their reception satellite are M2)5 and M2)2, respectively. Starting from M2)5 and M2y2, the report is circulated clockwise over the dashed lines. Note that the circulation of different plane's delay reports is processed in a parallel way, i.e., the delay report of one plane can be sent to different planes simultaneously.

4.5.3   Routing Table Calculation
Routing tables are prepared by the MEO satellites for their care-of members and updated every Tc period. There are two kinds of routing tables: The original routing tables register the detailed path and are kept in MEO satellites, whereas the simplified routing tables are sent to the LEO satellites.

47

Step 1: Original Routing Table Calculation
The MEO satellites perform routing table calculation after they received all the delay reports. The MEO satellite Mij computes the minimum delay paths from the LEO satellites in CM(Mij) to all LEO destinations, and adds them into original routing table ORTMij. Step 2: Simplified Routing Table Calculation
Based on ORTMi ., MEO group managers arrange the paths into destination and next-hop pairs for each of its care-of members. Before sending routing tables to the LEO layer, Mij tries to aggregate the destinations in remote groups to reduce the size of routing tables. The path aggregation is done as follows:
Algorithm 1 Path Aggregation Let S = all satellites in LEO layer for Li,j E RM(x), do
if the second node on Vx^y = t, Wy E Litj, then (S7ZTx(Li j) = t
S = S\Li ,j end if
end for
for each y E S, do
SRTx(y) = the second node on Vx^y end for

When SRTx is ready, it is sent from PH(x) to x via IOLp^(x)^x. 4.5.4   Congestion Avoidance
In our SGRP, data packets are routed according to the delay information gathered every Tc period. If traffic load changes fast, the routing decision cannot reflect the fluctuation of the real-time delay and congestion may occur. The congestion avoidance phase is introduced to deal with the congestion reactively and has three steps: Step 1: Congestion Detection
To avoid congestion in the LEO network, every LEO satellite continuously monitors the queue lengths of the output buffers of their adjacent links.  If the queue

length associated with lxi^x2 is more than £ packets, then "congestion" is said to have occurred on link lxi^x2.  x1 then promptly reports V(lxi^x2) = oo to all its MEO managers in H(x1). Step 2: Information Propagation
Upon receiving a congestion warning of link lxi^x2, Mij sets V(lxi^x2) = oo. Then, it propagates V(lxi^x2) = oo in MEO layer using the same intra- and inter-plane exchange methods explained previously in Section 4.5.2. Step 3: Path Recalculation
To reduce the computation overhead, MEO group managers only recalculate those paths affected by the congestion. Meanwhile, they try to lead long routes away from entering the congestion area.
A MEO satellite M checks all paths in ORTM, and searches those affected by the congested link. If a path is either originated or destined within the congestion area CA(lxi^x2), it will be kept. If a path goes through CA(lxi~^x2), then M "cuts" the congestion area when re-computating this path, i.e, set all delays associated with links in CA(lxi~^x2) to infinity, thus leads these paths away from entering the congestion area. The path recalculation in MEO satellite M for x E CM(M) is summarized below.

Algorithm 2 Path Recalculation in MEO Satellite M Let S = all satellites in LEO layer for each y E S, do
if lxi^x2 is on ORTm(x,y) = Px^y, then if l E CA(lxi^x2), Wl E Px^y, then
Keep Px^y, search next y end if
if l E CA(lxi^x2), where l is the first or last hop on path Px^y, then
Set   T)(lyi^y2 )   	   (DO,   Wlyi^y2   in   CA(lxi^x2 )
end if
M recalculates Px^y ORTm (x,y) = Px^y end if end for

After the calculation, M updates affected entries in ORTM, aggregates the new paths, and sends packets to update the affected entries in simplified routing table S RTx of its member x accordingly.

4.5.5   Satellite Failure Reaction
A satellite may fail or be shut down temporarily for reasons such as maintenance and testing, or when crossing oceans or polar regions to save energy. When a satellite fails, all minimum delay paths passing through this satellite must be rerouted, so that the packets that normally pass through the failed satellite would not be dropped. In our SGRP, the rerouting is done in the following way: When a satellite fails, its direct neighbors are the first to sense this occurrence. They immediately send reports to MEO group managers. Upon receiving failure notification of a LEO satellite s, Mitj sets all link delays associated with s to infinity, then propagates the update delay report in the MEO layer.
To reduce the computation overhead, MEO group managers only recalculate those paths affected by the failure. A MEO satellite M checks the paths in ORTM, finds those affected by the failed satellite s. If the failed satellite lies on a path, M recalculates the path, updates the corresponding entry in ORTM, and performs group aggregation before arranging into (Dest, next-hop) pairs for its care-of members.
If a packet arrives at the LEO satellite x and finds that the failed satellite is the next hop on its path, i.e., its routing table has not yet been updated, some special routing decision must be made to avoid dropping useful packets. Here we utilize the rerouting method in case of satellite failures in [30]. The packets destined to the failed satellite are deflected into orthogonal directions. The detailed rerouting algorithm can be found in the original paper.

4-6   Performance Evaluation
Our simulation consists of three major parts: First, find the snapshot periods and group membership information in each snapshot period according to the parameters of LEO and MEO satellite constellations. Second, using SGRP, keep track of the end-to-end delay between some terrestrial source-destination pairs, with the background traffic changing dynamically. Last, analytically show that the hierarchy in SGRP can reduce communication overhead compared to the centralized and distributed approaches in a single-layer satellite network.

4.6.1   Snapshot Periods Identification
In our two-layer satellite network model, the ICO network [37] is chosen as the MEO satellite constellation, the LEO satellite constellation is a slightly modified version of the Teledesic network [61], where the orbital inclination is 90° instead of 98.2°. The system parameters are given in Table 1. The system cycle for these parameters is T = 1440 minutes, or one day.
Using our computation method in Section 4.3, there are a total of 93 snapshot periods in a system cycle. As expected, the snapshots repeat after time T. The mean duration time for all 93 snapshots is 15.5 minutes. The length distribution of the

	MEO	LEO	
Altitude	hM = 10, 390km	hL = 700km	
Number of planes	Nm=2	Nl=12	
Number of satellites per plane	Mm=5	Ml=24	
Angular velocity	wM=1°/min	wL=3.6°/min	
Minimum elevation angle at LEO layer	F  ■  =10°	-	
Orbit inclination angle	45°	90°	
Number of intra-plane ISLs	2	2	
Number of inter-plane ISLs	0 or 1	0 or 2	
Longitude of logical location (n, 1)	-	90 = 7.5°	
Latitude of logical location (n, 1)	-	4>i = 86.75° ,02 = 82.5°	

Table 1: Parameters for MEO and LEO Satellite Constellations.

snapshot duration is given in Figure 16, where the durations are in minutes. It can be seen that the lengths of snapshot periods are not fixed.

4.6.2   Traffic Modeling
We divide the Earth into 15° x 15° geographical zones, and map each zone with a LEO logical location. Because of the asymmetry of IP traffic, the user behavior and host behavior are different for each zone. For example, the source of http pages are more likely to be located in North America than in Central Africa. Hence, we build two databases for the user density level and host density level for each zone, where the user density level represents the amount of source requests in each zone and the host density level implies the host distributions over the geographic zones. The global background traffic can be generated using a traffic matrix model.

• User Density Level: The forecasted voice traffic over LEO satellite systems for the year 2005 in [66] (as shown in Figure 17) is referred to determine the user density levels. Here we assume that the potential requirement for satellite network IP traffic from each geographical zone is proportional to the expected volume of voice traffic. As users show different activities during different time

Figure 16: Distribution of Snapshot Duration.

Figure 17: Earth Zone Division and User Density Levels [66].

Figure 18: User Activity in Each Hour (%) [55].

of the day, to make the traffic model more accurate, we take the daily evolution of user density into consideration. Assuming that the daily evolution of traffic activity per user is the same for all users worldwide, and the local time of each traffic zone is equal to the solar time of the respective zone's center longitude. The daily user activity profile introduced in [55] is used. The user traffic distribution of each hour in percentage of the total traffic within a day is shown in Figure 18.

Intensity level	1	2	3	4	5	6	7	8	
Traffic (million minutes/year)	1.6	6.4	16	32	95	191	239	318	

Intensity level and Corresponding Expected Traffic (2005)

• Host Density Level: The statistics of January 2001 in [7] is used to get the host density level for different terrestrial zones. The host density level gives the distribution of the Internet hosts in different continents, which is shown in Table 2. According to the data, we adjust the user density level to get the host density level of each zone by the following equation:

h, = ^-N^.	(22)

where h, is the host density level of zone j, of which the user density level is u,; J2i u(i) is the sum of user density level of zones in continent k; Nh(k) is the number of hosts in continent k. It can be seen that continent k's percentage share of host density on the Earth is equal to p(k) in Table 2.

The inter-satellite traffic requirement between satellites i and j, i.e, Tij, depends on the user density level ui, the host density level h,, and the distance d(i,j) between the satellites.
1   ~(d(i,j))' ■	(23)
Here i corresponds to the LEO logical location (n,m), where n = \i/ML], m = i
MOD ML, ML is the number of satellites in a LEO plane. Setting a = 0.5,/3 = 1.5,
we can get the traffic flow shares among the continents in Table 3.
In our satellite network, the links are modeled as finite capacity queues, the traffic
requirements between satellites are mapped to the ISLs according to the shortest

Continent k	Nh(k): number of hosts (x103)	p(k): (%)	
North America	71871.5	71.27	
Europe	17698	17.55	
Asia	7686.4	7.62	
Oceania	1873.65	1.86	
South America	1474.8	1.46	
Africa	241.9	0.24	

Table 2: Internet Hosts Distribution by Continent in January 2001 [7].

path the packets will take. They provide the arrival rates in the queuing model. We assume Poisson arrival rate and exponentially distributed service time, then the queuing delay of each link can be deduced by the M/M/1/K queuing model.
The average packet arrival rate of each pair of satellites (packets/sec) is computed

XH =     NLxMLX,NLxMLTkl X (total offered traffic),	(24)
where i,j = 1, 2,...,NL x ML, the "total offered traffic" represents the total traffic generated worldwide.

4.6.3   Delay Performance Evaluation
We developed our own simulator on C++. For each simulated routing protocol, the simulator measures the corresponding end-to-end delay metric. In all simulations, the capacity of all UDLs and ISLs are chosen as 160Mbps, and each outgoing link has been allocated a buffer size of 5MB. If we assume an average packet size of 1, 000 bytes, the link capacity becomes 20, 000 packets per second and the buffer size becomes 5, 000 packets. The delay metric is sampled every 1 minute.
Three types of routing protocols are evaluated using our simulator: our SGRP, the datagram routing algorithm (DRA) [30], and the optimal routing computed by the Dijkstra's algorithm [62]. Data packets are carried in the LEO satellite layer. DRA forwards packets in the minimum propagation delay paths. Therefore, the queuing

Source	Destination	

	N. America	Europe	Asia	S. America	Africa	Oceania	
North America	86.18	6.74	4.18	1.76	0.45	0.70	
Europe	25.10	55.88	13.52	1.62	2.84	1.04	
Asia	24.04	20.89	47.74	1.15	1.75	4.43	
South America	52.39	13.02	5.96	25.12	1.85	1.66	
Africa	25.63	43.34	17.33	3.53	7.95	2.22	
Oceania	26.48	10.58	29.22	2.11	1.49	30.12	

Table 3: Continental Traffic Flow Shares in %.

delays caused by the non-uniform traffic distribution are ignored. SGRP measures the link delay values every Tc period and uses the delay values as a reference for computing the minimum delay paths. The Dijkstra's algorithm [62] is used to calculate the routing tables in SGRP. Paths are adjusted when link congestion or satellite failures occur. The SGRP parameters used in the simulator are: the delay measurement interval Tc = 4 minutes unless specifically stated, the radius r of congestion area is set as 1. The optimal routing represents the ideal scenario that each satellite is assumed to be aware of the overall satellite topology and its knowledge of the link delays is updated in real time. Therefore, the optimal routing returns the best delay performance, which is hard to achieve in real systems and can only be approached at the cost of frequent delay measurement as well as heavy communication and computation overhead.
Our comparisons are based on the observation of the end-to-end delay between certain terrestrial source-destination pairs. To evaluate the performance of the LEO/MEO satellite architecture and SGRP, three sets of simulations are conducted:
 •	Path Optimality: The first set of the simulations show the differences of end-to-end delay returned by SGRP, DRA, and the optimal routing.
 •	Effect of Satellite Failures: This set of simulations shows the effect of satellite failures on the performance of SGRP, compared with DRA and the optimal routing.
 •	Effect of Link Congestion: Our SGRP has reaction mechanism when congestion occurs. This set of simulations shows the performance difference among SGRP, DRA, and the optimal routing in case of link congestion.

4.6.3.1   Path Optimality
The first set of simulations compares the end-to-end delay among the paths computed by SGRP, DRA, and the optimal routing. The comparisons are based on the observation of the end-to-end delay between three terrestrial source-destination pairs. The first two pairs are with the same source node located at (112.5oE, 37.5oN) in Asia. The destination nodes are at (277.5oW, 33.25oN) in North America and (52.5oE, 52.5oN) in Europe, respectively. The paths between these two pairs go through areas with traffic concentration. The path between source-destination pair 1 is with longer distance than that of pair 2. The third pair has the source located at (142.5oE, 37.5oS) in Oceania and the destination at (37.5oE, 18.25oS) in Africa. The path associated with the third pair does not travel through high traffic concentration areas. For each of the source-destination pair, the sender generates traffic with an average rate of 8Mbps (1, 000 packets per second) for 100 minutes.
To compare the delays of different schemes under different link load, we increase the ISL utilization in the LEO layer gradually. It is done as follows:
 •	First, the packet arrival rate is generated by Equation (24) and gives the average traffic rates of flows between each pair of satellites. Flows are generated with exponentially distributed rates with fixed mean values (Ay).
 •	The rates are mapped to ISLs according to the minimum propagation delay paths the packets will take. The load of a link is the sum of all the rates of flows that pass through this link. Some ISLs are more heavily loaded than others according to the traffic distribution model.
 •	Assume that the average load proportion across all the links keeps the same, hence to increase the ISL utilization statistically, the "total offered traffic" in Equation (24) is increased, which affects the flow rates Ay and in turn changes

the average load of each satellite link. The queuing delays of all the satellite links are calculated by the M/M/1/K queuing model.
• The delay of a link is the sum of its propagation delay and queuing delay at computation times.

In our simulations, each time a different value of the "total offered traffic" is chosen, the routes and end-to-end delays of certain flows are monitored for 100 minutes. The satellite link loads are changing dynamically with fixed nominal means. The end-to-end delay performance of the SGRP, DRA, and the optimal routing are depicted in Figure 19. For each specific value of average link load, the end-to-end delay is averaged over the 100-minute monitoring time. Note that as the result of non-uniform traffic distribution shown in Table 3, the load of links varies greatly among different satellite links. Thus, some of the links may get congested even when the average link load is as low as 3%.
It can be seen that for paths that go through some high traffic concentration areas, e.g., source-destination pair 1 and 2, when the average link load is below 3%, the end-to-end delay performance of the three protocols is similar. This is reasonable because when the traffic load is light, the propagation delay is the dominant factor in the end-to-end delay. As the average link load increases, however, the delay performance of SGRP and DRA deviates from the value returned by the optimal routing. The end-to-end delay of the path calculated by DRA increases dramatically when the average link load is greater than 8%. This is because when average link load increases, ISLs in areas with higher traffic density tend to be congested more easily. DRA reflects packets only when they approach or enter into the congestion area, whereas the routing scheme based on SGRP can have a big picture of the traffic distribution in the LEO network and reduce the traffic entering into the congested area. As SGRP leads long paths away to avoid even the vicinity of the congested links, however, these

average link load (%)
(a) Source-Destination Pair 1.

(b) Source-Destination Pair 2.

(c) Source-Destination Pair 3. Figure 19: Comparison of Average End-to-End Delay Performance.
routes may experience longer delay compared to the paths calculated by the optimal routing.
For paths that travel only through areas with lower traffic concentration, e.g., source-destination pair 3, SGRP does not introduce higher delay than the optimal value until the average link load is high, e.g., 57% in Figure 19(c). The delay performance of both DRA and SGRP is very close to the optimal value, e.g., the delay deviations from the optimal value for SGRP and DRA are within 0.5msec and 2.5msec, respectively (Note that the scale of the y-axis is different than those in Figures 19(a) and 19(b)). Hence, for paths that do not travel through high traffic density areas, the performances of SGRP and DRA are not affected by congestion in other areas

59

and are very close to the optimal value.
As explained in Section 4.5, the LEO satellites periodically measure delays of adjacent links. This delay information is then used to compute the routing tables for the coming measurement interval Tc. The length of Tc affects the delay performance of SGRP. If Tc is too large, the delay report obtained will not be able to capture the delay behavior in the next Tc period, which may cause the computed path sub-optimal. We have simulated SGRP with different Tc values of 8, 4, and 2 minutes, respectively. As seen in Figure 19, with the decrease of measurement interval Tc, i.e., when routing tables are updated more frequently, the end-to-end delay values returned by SGRP approach the optimal value more closely. If the path does not travel through high traffic concentration areas, the delay difference of SGRP from the optimal value is ignorable. For example, in Figure 19(c), when Tc = 2min, the curve representing the path delay between source-destination pair 3 overlaps with that of the optimal delay. When Tc is large (Tc = 8min in Figure 19), the delay difference of SGRP from the optimal value grows rapidly under link congestion.

4.6.3.2   Effect of Satellite Failure
SGRP introduces a reaction mechanism against satellite failures and link congestion. In the following two sets of simulations, we compare the end-to-end delay of three different routing schemes mentioned previously under these events. To reflect the effect of real-time changes on delay performance, the background traffic is adjusted every hour according to the time of the day. All paths and link loads are updated after recalculation.
When a satellite fails, it affects the routing decision and the path delay. In this set of simulations, we keep track of the end-to-end delay of source-destination pair 1 using these three protocols, respectively. The sender generates traffic of 1, 000 packets per second for 60 minutes from 8:00am to 9:00am. The satellite representing the logical

(a) Under Satellite Failure.	(b) Under Link Congestion.
Figure 20: Comparison of Instantaneous End-to-End Delay Performances.
location of (292.5°W, 67.5°N) is assumed to be out of service from 8:15am to 8:35am.
In Figure 20(a), instantaneous end-to-end delays associated with these three protocols are depicted. DRA routes packets on the minimum propagation delay path, the satellites do not send delay reports to others. Thus, only the immediate neighbors know the satellite failure. When a packet is received by one of these neighbor satellites, and is destined to the failed one, it is deflected to one of the orthogonal directions. In SGRP, the satellite failure is immediately reported to the MEO layer by its neighbors. This failure report is then exchanged among all MEO satellites, causing them to update the routing tables of all the LEO satellites. Hence, we expect SGRP to have better performance than DRA under satellite failures. From the figure, we can see that the failure has minor effect on SGRP, yet in the satellite failure period, the path calculated by DRA undergoes higher end-to-end delay, which is about 55% higher than that of SGRP. On the other hand, the delays of SGRP and optimal routing are very close either under normal condition or when a satellite fails. Because when a satellite fails, the failure report packets are immediately received and passing around in the MEO layer. New shortest paths are calculated and take effect after the LEO satellites receive the new routing tables. This mechanism compensates the effect of satellite failures.

4.6.3.3   Effect of Link Congestion
Similarly, we depict the change of instantaneous end-to-end delay for source-destination pair 1 of the three protocols when link congestion occurs. This congestion is created by injecting some heavy traffic into the satellite network in a certain area. In our simulations, the sender generates traffic of 1,000 packets per second for 60 minutes in a peak hour from 10:00am to 11:00am. The congestion occurs at the link from LEO logical location (277.5oW, 63.25oN) to (277.5oW, 48.25oN) between 10:20am and 10:40am. To simplify the simulation, we confine the congestion to this link, and setting the load on this path to 100% of the link capacity.
From Figure 20(b), the path calculated by DRA always undergoes higher delay within the congestion period. This delay is about 13% higher than that of the path calculated by SGRP. The average difference between the delays of SGRP and the optimal routing is about 0.5msec. When congestion occurs, however, their delay performance is about the same. SGRP recalculates the routing tables right after congestion happens. The recalculation tries to keep the local traffic within the congestion area, but route the long path away from the congested area. Therefore, the effect of congestion will be compensated by enacting the new routing tables.

4.6.4   Communication Overhead Analysis
SGRP divides the LEO satellites into groups according to the snapshot periods and distribute the routing table calculation of all LEO satellites to several MEO satellites. Therefore, a hierarchy is introduced in the architecture. In order to demonstrate the efficiency of SGRP, we analytically compare the communication overhead of each round of routing table calculation in SGRP with the centralized and fully distributed routing table calculation approaches in a single-layer satellite network architecture.
In the centralized routing table calculation scheme, all routing tables are calculated by a designated terrestrial gateway. The satellites in LEO layer create their delay

10' &    106
O
cn (/)
E

0) .C 0)
O     10* O
13
E -E 103 o

102

100      150      200      250      300      350      400      450      500      550      600
number of LEO satellites

Figure 21: Communication Overhead Comparison.

reports and send them to the gateway through minimum hop paths. The terrestrial gateway calculates the individual routing tables for all the LEO satellites separately and sends these routing tables to the corresponding satellites again over minimum-hop paths.
In the fully distributed routing table calculation approach, every satellite is responsible for calculating its own routing table. The delay reports are broadcast to all satellites. Once a satellite receives all delay reports, it calculates the shortest paths to all other nodes. Using the shortest paths, every satellite creates its own routing table that contains the next hop to reach all other nodes in the network.
In Figure 21, the communication overhead of the three routing table calculation schemes are compared. In the hierarchical architecture in SGRP, the number of MEO satellites is set as 10, i.e., 2 planes with 5 satellites in each plane as in the ICO constellation. The total number of LEO satellites was changed and its effect on the communication overhead of the three schemes was recorded. The total communication overhead is expressed in terms of transmission units, which is an entry either in the delay report or in a routing table.

Among these three schemes, SGRP has the least amount of communication overhead. Central routing table calculation generates more communication overhead as the total number of satellites in the network increases. By introducing the hierarchy in SGRP, every LEO satellite only sends delay report to its MEO primary manager. Rather than broadcasting, delay reports are exchanged in the MEO layer in an efficient way. After calculation, routing tables are sent back to the corresponding LEO satellites through one hop from a MEO primary manager to its care-of members. SGRP's communication overhead stays below that of the centralized calculation scheme in all cases. On the other hand, as the distributed calculation scheme requires broadcasting of delay reports to all LEO satellites, which boosts up its communication overhead, the distributed calculation scheme's communication overhead is the highest among the three.

4.6.5   Summary and Discussion
In summary, we assessed the performance of the SGRP protocol with simulations, which revealed that SGRP has better delay performance than the datagram routing algorithm. When satellite failure or link congestion occur, SGRP has mechanisms to reduce their effects on routing. We also showed that SGRP calculates the routing decisions with low communication overhead. SGRP distributes the computational burden to multiple MEO satellites, thus balances the power consumption between LEO and MEO satellites.
In this research, we assume that the traffic load on satellite system is moderate and packets are routed within LEO layer. MEO satellites are used for routing table calculation and transmission of signaling and data control packets. Since the signaling traffic is physically separated from the data traffic, the congested links do not affect the transmission of the delay measurements. SGRP enables the collaboration between different satellite network constellations.   MEO satellites are aware of the overall

topology of LEO and MEO layers, which gives them the possibility of not to constrain the routing to LEO layers. Besides the management functions and route computation, MEO satellites can be used for other purposes as well, such as packet forwarding and navigation.

CHAPTER V

TERRESTRIAL/SATELLITE NETWORK INTEGRATION THROUGH BORDER GATEWAY PROTOCOL - SATELLITE
VERSION

5.1   Motivation and Related Work
Satellite networks are becoming increasingly important for global communications. With the explosive growth of the Internet, the IP technology is being pushed to the satellite networks. To realize this, satellites carry IP-switches that forward packets independently. These IP-switches are connected to each other as well as to ground stations. Several issues related to IP-based satellite networks have been reviewed in [42]. Routing in the LEO satellite environment is a challenging problem because of the dynamic nature of the satellite networks. In recent years, several routing algorithms and protocols have been proposed for IP-based LEO satellite networks [38, 30, 40, 26].
The use of the IP-based satellite networks as a part of the Internet, however, cannot be accomplished only by solving the routing problem of the satellite networks. The integration of the IP-based satellite networks must assure their interoperability with the terrestrial IP networks. Previously, satellite network integration issues were pointed out in [42, 52, 74]. As suggested in these papers, the satellite network can be viewed as a separate autonomous system (AS) with a different addressing scheme. To reduce the load on the satellite network, terrestrial gateways act as border gateways on behalf of the satellite network and perform address translation. Then, paths over both networks can be discovered using an exterior gateway protocol such as BGP [57]. Since the internal and external metrics for terrestrial ASs and the satellite network are different, however, special care must be taken. None of the studies mentioned

above provides a detailed solution as to how this network-level integration can be accomplished.
In this chapter, the border gateway protocol - satellite version (BGP-S) is proposed. The BGPS protocol was first introduced in [31] and refined in [32]. The satellite network is considered an AS with special properties. BGP-S is designed to coexist with the BGP-4 [57] and support the automated discovery of paths that include the satellite hops. It is designed to be implemented in only one terrestrial gateway in every AS that is connected to the satellite network. Since the delay in the satellite network can be much longer than in a terrestrial AS, the acceptance of paths involving satellite hops is accomplished through active delay measurements.

5.2    The Hybrid Terrestrial/Satellite Network Architecture
The general hybrid network consists of the terrestrial Internet and an IP-based satellite network. The terrestrial Internet is organized into ASs. Inside every AS, the routing is accomplished through interior gateway protocols (IGPs). The inter-AS routing is based on an exterior gateway protocol (EGP), specifically, Border Gateway Protocol version 4 (BGP-4) [57]. The satellite network should carry the following properties:
 •	The satellite network should be able to forward individual data packets between two gateways on the Earth. The satellite network may use its own native packet formats and its own addressing scheme.
 •	There is no constraint on the satellite topology as long as any two terrestrial gateways can be connected over the satellite network. The satellite network can consist of any number of satellites in one or more orbits as long as every terrestrial gateway is always in the coverage area of at least one satellite and there exist a path to every other terrestrial gateway.

•	There is no constraint on the routing protocol used in the satellite network, i.e., any custom routing protocol with static or dynamic routing tables/strategies is acceptable.

5.2.1   Network Components
A sample structure of the hybrid terrestrial/satellite network is shown in Figure 22. In this figure, two autonomous systems, ASi and ASr, are depicted. The autonomous systems are connected to the satellite network via a gateway. ASi and ASr are also connected with terrestrial links. Note that this figure is only a partial view of a likely network topology. There may be more autonomous systems with possibly different number of gateways and connected in a more complex way. The following is a list of notations used in this work:
 •	Autonomous System: The collection of routers under the same technical and administrative control is referred to as an autonomous system. The autonomous systems are denoted by ASi as shown in Figure 22.
 •	Routers and BGP Speakers: The routers in every autonomous system ASi are denoted by Rij, for j = 0, • • • , NR — 1, where NR is the number of routers

Figure 22: The Hybrid Terrestrial/Satellite Network Architecture.

in ASi. The BGP speakers are the routers that implement BGP and they are denoted by BSij, for j = 0, • • • , NBS — 1, where NBS is the number of BGP speakers in ASi. Note that NBS < NR and {BSij} C [Rid}.
 •	Network Address: A network address NAi is the longest common IP prefix shared by the network elements in that subnetwork. An example network address is 193.140.196.0/24.
 •	AS Path: An AS path P^Si (NAk) is an ordered list of autonomous systems (ASi, • • •, ASx), which is the jth alternative path for ASi to reach the network address NAk, where NAk resides in ASx.
 •	Gateways and Peer Gateways: The gateways are the terrestrial stations that enable the communication between the autonomous systems and the satellite network. In an autonomous system ASi, the number of gateways is NGW, and the gateways are denoted by GWitj, for j = 0, • • •, NGW — 1. One of the gateways is designated as the peer gateway and implements the BGP-S protocol used for path discovery over the satellite network. The peer gateway in an autonomous system ASi is denoted by PGWi as shown in Figure 22. A peer gateway is a gateway, a router, and a BGP speaker at the same time.
 •	Active Peer Register: The active peer register (APR) is the list of active peer gateways connected to the satellite network. APR can be maintained on the Earth as well as in the satellite network, where it can be reached by peer gateways over pre-configured paths. APR can also be duplicated as long as all copies are updated in real-time.
In addition to these components, there are also other components in the hybrid network. The terrestrial network contains routers and hosts, and there are satellites with on-board routers. Satellites are denoted by Si, for i = 0, • • •, NS — 1, where NS

is the number of satellites. Note that no specific satellite constellation or organization of the satellites is assumed. Thus, only the index i in Si is sufficient to refer to a specific satellite.

5.2.2   Packet Forwarding
The packet forwarding from one terrestrial gateway to the next occurs with "IP over IP" tunneling in the satellite network. Under this scheme, packets are encapsulated individually into native satellite packets before they are sent to the satellite network by the terrestrial gateway. Native satellite packets carry the address of the next terrestrial gateway which can be interpreted by all satellites in the network. Hence, satellites do not need to keep track of all IP addresses. The satellite network is responsible for relaying the packets between terrestrial gateways only. It is assumed that the addressing scheme used by the satellite network and the mappings of these addresses to IP-addresses are available in the terrestrial gateways.
The packet processing in the terrestrial gateways is the most important step to use the satellite network as a part of IP paths. While the routers in the terrestrial network continue using the standard packet forwarding procedures, the terrestrial gateways must translate the IP addresses and encapsulate the IP packets into native satellite packets. For this procedure to work, the terrestrial gateways must be addressable both by the terrestrial and satellite network.

Definition 11 (Next Hop Function NH) Let P denote a packet received by a terrestrial gateway. The function NH(P) returns the next hop on the path of the packet P towards its destination.

Definition 12 (Satellite Next Hop Function SNH) Let P denote a packet received by a terrestrial gateway GWitj, and the next hop for packet P be a terrestrial gateway GWrs, i.e., NH(P) = GWrss, where (r, s) =      ), which is reachable through

the satellite network. The function SNH(GWr>s) returns the satellite St, to which GWij should first send the packet P such that P reaches GWrss.

Upon receiving a packet P, a terrestrial gateway GWi j processes the packet as follows:
 1.	The gateway determines the next hop NH(P) for the received packet P.
 2.	If the packet's next hop is not a terrestrial gateway, i.e.,
NH(P) E {GWr>s | (r, s) = )}, it forwards the packet to the next hop without any modification.
3.	If the next hop of packet P is a terrestrial gateway, i.e., NH(P) = GWrss, (r, s) =
( i, j), then P is encapsulated into a native satellite packet with GWr s as the
destination and sent to its next hop St in the satellite network, where St =
SNH(GWr s).
Note that it is assumed that no two terrestrial gateways are connected to each other with terrestrial links. If it is the case, then the function NH should be modified such that it also indicates if the next hop should be reached through the satellite network or over a direct terrestrial link. When a terrestrial gateway receives a native satellite packet from a satellite, it simply extracts the payload from the satellite packet and processes it as a regular IP packet.

5.3   BGP-S: Border Gateway Protocol - Satellite Version
To allow the automated discovery of paths that pass through the satellite network, we introduce a new protocol called the border gateway protocol - satellite version (BGP-S). BGP-S possesses the same basic functionality as BGP-4 [57], which means that the AS policies used in BGP-4 are adopted to control routing traffic among networks.

However, using BGP-S together with BGP-4 has two main advantages. First, the satellite network does not directly participate in the path calculations. Instead, it is only responsible for carrying data packets and (possibly) keeping track of the active peer gateways. Hence, the complexity added to the satellite system is kept at a minimum. Second, if the satellite network is regarded as a regular autonomous system, there would not be any difference between a terrestrial AS and the satellite network. This may be misleading in many cases since the delays in the satellite network are much larger than in a terrestrial AS. Therefore, under BGP-4, if one or more satellite hops are involved in the AS-path, it is necessary to manually configure the routing strategies according to the location of the ASs and delay estimations. BGP-S eliminates the need for manual configuration and enables automatic adaptation based on the delays in the satellite and terrestrial networks.
In the hybrid network model, BGP-4 and BGP-S are used together as shown in Figure 22, where APR is located in the satellite network. Between the terrestrial BGP speakers, the BGP-4 protocol is used. More specifically, the Interior-BGP (IBGP) is used among the BGP speakers in the same AS. The BGP speakers that belong to different ASs use Exterior-BGP (EBGP). Although the message formats are the same for both IBGP and EBGP, there are differences in message processing. Peer gateways communicate over the satellite network using the BGP-S protocol. Peer gateways must implement both BGP-4 and BGP-S.
There are two important rules in a system implementing BGP-S:
 •	Rule 1. There is only one peer gateway in an AS.
 •	Rule 2. The routing policies that are configured for the BGP-4 are automatically adopted by BGP-S.
The first rule aims to limit the number of peer gateways to the number of ASs directly connected to the satellite network. Furthermore, it eliminates duplication of

Figure 23: The Activation of Peer Gateways and Connection Setup.

information received in an AS. The second rule ensures that BGP-S is fully compatible with the BGP-4 protocol, hence with the existing Internet infrastructure. These policies may eliminate paths that contain certain ASs, or may ensure that transit traffic is not carried, etc. Detail descriptions of BGP-4 can be found in [57, 60]. The details of the BGP-S protocol are provided in the following sections.

5.3.1   BGP-S Connection Setup
The BGP-S protocol uses TCP connections between two peer gateways for communication. A BGP-S connection is closed either by an explicit NOTIFICATION message or when no messages are received from the other party within a predetermined time-out period. Considering the number of active peer gateways, the time-out period is suggested to be longer than in BGP-4, approximately 10 seconds. The connection setup is accomplished through the following steps, as also shown in Figure 23:
 1.	When a peer gateway PGWi becomes active and wants to connect to other peer gateways, it sends an Alive(PGWi) message to the active peer register (APR).
 2.	The APR sends a list of already active peer gateways to PGWi.
 3.	PGWi acknowledges the reception of the active peer gateway list to the APR.

73

 4.	The APR sends to all other active peer gateways the AliveJFwdPGWJ to notify them about the availability of the peer gateway PGWi.
 5.	If an already active peer gateway PGWj wants to establish a BGP-S connection, it then sends an OPEN message to PGWi.
 6.	PGWi can establish a BGP-S connection to any other peer gateway PGWk in the active peer register by sending an OPEN message.

The Alive(PGWi) message contains the IP and satellite network addresses of the peer gateway PGWi as well as the AS number where PGWi resides. The Aliv^Fwd(PGWi) message contains the same information as the Alive(PGWi) message. The difference is that Alive messages are created by the peer gateways that become active, and Alive_Fwd messages are created by the APR to notify other peer gateways of the availability of a new peer gateway. The OPEN message has the same format as in the BGP-4 protocol.

5.3.2   Path Discovery and Prioritization
A peer gateway learns paths both via BGP-S and BGP-4. If it decides to advertise the paths to other peer gateways over BGP-S, it then uses UPDATE messages that have the same format as in BGP-4. It is important to note that the paths learned via BGP-S cannot be processed like the paths learned through BGP-4. The reasons for this differentiation were presented at the beginning of Section 5.3. While processing these paths, it is important to be consistent with policies configured with the BGP-4 protocol. Then, the paths are compared based on the delay to the target network. Note that the delay comparison is just an approximation of the real-time delay. The delay changes continuously because of fluctuations in the traffic load and it is not feasible to check the delay to all possible network addresses periodically. In order to discover the delay to a given network, the following new messages are used:

 •	POLL() message: The POLL message is used to request a delay measurement to a specified network or network element. POLL(PGWi; PGWj, A) is a message sent by the peer gateway PGWi to PGWj to learn about the delay between PGWj and A, where A can be a network or a network element. Every POLL message contains the message creation timestamp.
 •	DELAY() message:  The DELAY message is a reply to a POLL message.   The DELAY(PGWj , PGWi, A, B, d) is a message sent by the peer gateway PGWj to PGWi telling that the delay between itself and a network element B in the network A is d. If A is a network element, then A = B.
If A = PGWj, then DELAY is like a ping response; the receiving peer gateway PGWj replies immediately with a delay equal to the timestamp in the POLL message. Then, the peer gateway PGWi calculates the round trip delay to PGWj. If A is a network address, then PGWj measures the delay to the network element B in the network A. Then the DELAY message contains this measured delay as d. When the delay to a network A is needed, PGWj selects a network element B in the network A and measures the delay from itself to B. The delay can be measured using the ping utility. Any other method can be used for delay measurement, as well.

5.3.2.1   New Path Discovery via BGP-S
Assume a peer gateway PGWi learns from PGWj via BGP-S the AS path Pas, (NAk) to reach the network NAk. The new AS path PASj (NAk) is processed following the steps below, which are also shown in Figure 24.
 1.	PGWi checks PASj (NAk) with the policies setup for BGP-4 protocol. If there is a conflict, then PASj (NAk) is discarded.
 2.	If PASj (NAk) conforms with the BGP-4 policies and the delay from PGWi to PGWj is not available to PGWi, then PGWi sends a POLL(PGWi, PGWj,

Figure 24: The Processing of AS Paths Learned via BGP-S. PGWi) message to PGWj.
 3.	PGWi also sends a POLL(PGWi; PGWj, NAk) message to PGWj to learn the delay between PGWj and the network NAk.
 4.	PGWi receives the DELAY(PGWj , PGWi, PGWj, PGWj, dx) message from PGWj. The delay d\ to PGWj, is estimated as half of the difference of the current time Tcur and the timestamp d, i.e., d\ = Tcul2~d.
 5.	PGWj measures the delay d2 to the network element B in network NAk.
 6.	PGWi receives the DELAY(PGWj , PGWi, NAk, B, d2) message from PGWj.
 7.	PGWi measures the delay d3 to B if there exists an AS path Pas\ (NAk) to reach the network NAk in the routing information base (RIB) of BGP-4. If there is no such entry in the BGP-4 RIB, then the delay to B is assigned infinity, i.e., d3 = to.
 8.	If d3 is infinity, then P\Si (NAk) is created by appending ASi to Pasj (NAk) and inserted to BGP-4 RIB with a default local preference value.
 9.	Assume that there is already an AS path PASi (NAk) used in ASi to reach the network NAk such that PASi(NAk) = argmaxXe|p^s (NAk)} LocalPref (X),

76

where the function LocalPref(X) gives the local preference value of the AS path X. If di + d2 > d3, i.e., the new path over the satellite network is longer than the already available AS path, then the new AS path PAs1 (NAk) is inserted into BGP-4 RIB with a local preference value of LocalPref (P*ASi(NAk)) - 1, where p is the number of AS paths to NAk already in the RIB.
10. Under the same conditions as in the previous step, if di + d2 < d3, i.e., the new path over the satellite network is shorter, then the new AS path PAs1 (NAk) is inserted into BGP-4 RIB with the local preference value of LocalPref (PASi (NAk)) + 1, where p is the number of AS paths to NAk already in the RIB.
When an AS path is inserted into the BGP-4 RIB by a peer gateway, the delay information remains local to the BGP-S protocol. The delay comparison is advertised to the BGP speakers in the same network implicitly with the local preference value, which is propagated with the new path information. Note that the local preference values of the AS paths inserted by BGP-S are related with the existing AS paths in the RIB. Although a relative local preference assignment is not allowed under BGP-4, BGP-S assigning relative local preference values does not affect the integrity of the BGP-4 because there is only one network entity per AS that is allowed to perform this operation.

5.3.2.2   New Path Discovery via BGP-4
Assume that a new AS path PAs2(NAk) is advertised via BGP-4, which has a higher local preference value than the currently used, i.e., LocalPref (PAS2(NAk)) > LocalPref (PASi(NAk)).  Also let PASi(NAk) be the AS path with the best delay performance to the network NAk among the AS paths learned via BGP-S. The peer gateway PGWi performs the following steps to process the new AS path:
1. If the BGP-4 RIB does not contain any path to NAk that was learned via BGP-S, then no action is taken.

 2.	Otherwise, the delay to the network element B in NAk is measured for PAS2 (NAk) and PASi (NAk). The measurements are taken following the Steps 2-7 in Section 5.3.2.1, obtaining the delays di, d2, and d3.
 3.	If di + d2 > d3, i.e., the AS path over the satellite network PASi(NAk) is longer than the new AS path PAS2 (NAk), then no action is taken.
 4.	If di + d2 < d3, i.e., the AS path over the satellite network PASi(NAk) is shorter than the new AS path PAs2 (NAk), then PGWi updates the local preference of PASi (NAk) as LocalPref (PAS2(NAk)) + 1. Then, PGWi advertises the path PASi (NAk) with the updated local preference value.

Note that the delay of the paths over the satellite network is re-measured by the peer gateways when learning new paths over BGP-4. However, regular delay monitoring of all the paths by peer gateways would not be feasible given the number of the ASs we consider and the high protocol overhead it would introduce.

5.3.2.3 Path Withdrawal
When a path is withdrawn either via BGP-4 or BGP-S, the peer gateway PGWi in ASi must check the RIB and possibly modify the local preference value of the shortest AS path that goes over the satellite network. Assume that there are p paths in the BGP RIB to reach the network NAk. Upon receiving an UPDATE message that contains the withdrawal of an AS path that leads to NAk, the peer gateway PGWi performs the following operations:
 1.	If the withdrawn AS path is not the one that is currently used, no action is taken.
 2.	If the currently used path is withdrawn and the AS path with the next highest local preference value is learned via BGP-4, then no action is taken.

 3.	If the AS path with the next highest local preference value is learned over BGP-S, then the AS path that is learned via BGP-4 and has the largest local preference value is found, which we call PASi (NAk).
 4.	All AS paths with larger local preference values than PASi (NAk) are collected in the set PAS (NAk).
 5.	The delays of all AS paths in PAS (NAk) are measured as described in Section 5.3.2.1, Steps 2-7. The delay of PASi (NAk) is also measured as described in these steps.
 6.	Let us assume that the AS path PASi (NAk) has the lowest delay ds among all paths in PA%(NAk). Also assume that the delay of PASi(NAk) is dt. If d* < ds, i.e., all AS paths over the satellite network are longer, then the local preference values of all AS paths in PA%(NAk) are set to LocalPref (PASi(NAk)) - 1, i.e., LocalPref (P) = LocalPref (PAS(NAk)) - 1, VP e PAS*(NAk).
 7.	If d > ds, one of the AS paths over the satellite network is shorter, then the local preference values of all AS paths in PASi (NAk) except for PASi (NAk) are set to LocalPref (PASi(NAk)) - 1, i.e., LocalPref (P) = LocalPref (PASi(NAk)) -
1, VP e PAS* (NAk) and P = PASi (NAk). The local preference value of PASi (NAk) is set to LocalPref (PASi(NAk)) + 1.

8.	The updated local preference values are advertised in the autonomous system

ASi.

5.3.3   BGP-S Connection Termination
Assume that a BGP-S connection between two peer gateways PGWi and PGWj is terminated because PGWj does not receive any message from PGWi within a timeout period. If the connection terminates due to time-out, PGWj notifies the APR about the termination. APR checks if PGWi alive. If PGWi is alive, no action is

taken. If PGWi does not respond, then APR records this in its database and informs all active peer gateways about this. Any existing connections to PGWi is terminated and all RIB entries that use ASi are withdrawn by active peer gateways within their ASs.
On the other hand, if a peer gateway PGWi will be turned off or if ASi does not want to receive any traffic from the satellite network, then PGWi terminates all active connections with NOTIFICATION messages. The peer gateways that receive NOTIFICATION messages do not contact APR. Then PGWi sends a message to APR indicating that it is no longer active. APR records this in its database and forwards this message to all active peer gateways. All RIB entries that use ASi are withdrawn by active peer gateways.

5.4   Performance Evaluation
We evaluated the performance of BGP-S on an integrated terrestrial/satellite IP networks model. This integrated network model consists of terrestrial ASs and a satellite network. The new network generation tool we use to create the integrated network topology is called the Integrated Terrestrial/Satellite Topology Generator (ITSTG). The performance of BGP-S is evaluated with simulations run on the network topologies created by ITSTG.

Figure 25: The Schematic Structure of ITSTG.

5.4.1   Topology Generation Process
The structure of ITSTG is shown in Figure 25. It is extended from the Boston university Representative Internet Topology gEnerator (BRITE) [1]. The parameters for terrestrial and satellite network are specified in a configuration file. Using these parameters, the topology generation engine generates terrestrial AS-level topology and the satellite network topology separately. Finally, these two topologies are used as the inputs to the topology integrator to create the integrated terrestrial/satellite network topology. The terrestrial, satellite, and integrated terrestrial/satellite topologies are generated as described in the following sections.

5.4-1-1   Terrestrial Topology
The specific details regarding how a terrestrial topology is generated depend on the specific generation model being used. In general, the generation process is divided into three steps:
 1.	Placing the nodes: The nodes are placed on the terrestrial sphere with heavy-tailed distribution, which describes the topological properties of the Internet [36]. The sphere is divided into squares, and each square is assigned a number of nodes drawn from a heavy tailed distribution. Then these nodes are placed randomly in the square. The positions of nodes have longitude in [0°, 360°) and latitude in [-90°, 90°].
 2.	Interconnecting the nodes: The methods of interconnecting nodes are different for two different models: Waxman and Barabasi. The placing procedures are taken from BRITE with minor modifications.

• Waxman Model: In the Waxman model [68], a new node tends to be connected to existing nodes that are closer in distance. The nodes are added into the topology in an incremental way.  A node is selected

randomly to join the network and interconnected to other existing nodes. The incremental growth is a possible cause for power law of "outdegree exponent" [36] in any network topology.
• Barabasi Model: The Barabasi model is proposed by Barabasi and Albert [16]. This model suggests two possible causes for power law of "outdegree exponent" in network topologies: "incremental growth" and "preferential connectivity". Incremental growth refers to growing networks that are formed by the continuous addition of new nodes, which simulates the gradual increase in the size of the network. Preferential connectivity refers to the tendency of a new node to connect to existing nodes that already have high connectivity.

3. Assigning attributes: The bandwidth of a terrestrial link is assigned a value randomly drawn between BWmin and BWmax. The delay within an AS is a random variable uniformly distributed within ASmin and ASmax, which are specified in the configuration file.

5-4-1-2   Satellite Topology
We consider a single-layer Walker Star [67] type LEO satellite network. Satellites are placed on the sphere of radius RE + h, where h is the altitude of LEO satellites. We utilize the "logical location" concept in [30]. The logical locations are equally spaced points in the grid of the LEO satellite constellation. They do not move with respect to the Earth and are embodied by the nearest LEO satellites. The communication between the satellites occurs through ISLs. One satellite can have at most four adjacent links. Inter-orbital links only exist between neighboring satellites outside polar areas. The bandwidth of links in the satellite network is fixed.

5-4-1-3   Integrated Terrestrial/Satellite Topology
In BGP-S, the detailed topology of the satellite network is hidden from the terrestrial network. The communication between satellite and terrestrial parts of this integrated topology is accomplished through the terrestrial gateways. We assume that one gateway belongs to one terrestrial AS and has only one UDL to one satellite, which is represented by the nearest logical location.
The generation process of integrated network topology has the following three steps:
 1.	Interconnecting gateways and satellites: First, we select the value of p, which is the percentage of ASs having connections with the satellite network. For every terrestrial node, a value is randomly generated between 0 and 1. If the value is smaller than p, then a link is added between that node and its nearest satellite logical location.
 2.	Condensing the satellite topology: The condensed satellite topology only includes the satellites that have UDLs. These satellites are referred to as representative nodes (RNs). Virtual links are built between every pair of representative nodes. The cost of the virtual link between two representative nodes RN1 and RN2 is the accumulated cost of the nodes and links along the path from RN1 to RN2 within the satellite network. If we define the cost as the delay of the link, then the cost of a virtual link is the sum of delays of all links along the minimum delay path. A virtual link is counted as one hop.
 3.	Creating the integrated topology: The integrated topology is the combination of terrestrial topology and the condensed satellite topology. It includes all terrestrial nodes and links, the satellite representative nodes and links between them, and the links between terrestrial gateways and satellite representative nodes.

Figure 26(a) gives an example of interconnected terrestrial/satellite network, in which the terrestrial network has five ASs, three of which contain gateways. After going through the above three steps, the integrated terrestrial/satellite topology is generated as shown in Figure 26(b). In the satellite part, only the three satellites that have UDL connection to terrestrial gateways are kept in the condensed topology. The dashed lines are virtual links that connect these three satellites.

5.4.2   Simulation Results
Based on the topology created, we have simulated the routing between any of the two terrestrial AS nodes. In the simulations, we do not consider the source or destination located in the satellite network, as the users and service providers reside on Earth. In the BGP-4 protocol, the configured policies override the efficiency considerations in the path selection process [57]. We cannot simulate BGP-4 as it works in the real Internet because it is not possible to make realistic assumptions about the administrators' preferences. Hence, we implement minimum hop routing to reflect the characteristics when AS-path hop length is the decision criterion of choosing the path
in BGP-4.

(a) Interconnection of Networks.	(b) Condensed Topology.
Figure 26: Integrated Terrestrial/Satellite Topology Generation.

In our integrated terrestrial/satellite network, every link is associated with an instantaneous delay. This link can be an intra-AS link on earth, a UDL between a gateway and a satellite, or an ISL. Each link is modeled as an infinite capacity queue. Given link load and link capacity, with the assumption of Poisson arrival rate and exponentially distributed service time, the queuing delay of each link can be deduced by the M/M/l queuing model. As the terrestrial part of the ITSTG is built on AS-level, a packet also experiences delay within an AS, which is represented by intra-AS delay value of the AS node.
In all simulations, the number of nodes in the terrestrial network is chosen as 3, 000. The simulation parameters are listed in Table 4. In this table, LS=10 stands for a side length of 10° for the square used in the heavy-tailed node-placement method, and m stands for the number of links per new node. The bandwidths of inter-AS links and the intra-AS delays are uniformly distributed between selected minimum and maximum values. The link loads are uniformly distributed between 0% and 100% of the respective link bandwidths. The bandwidth of UDLs is set as 1.6Mbps.
We conducted simulations on the integrated topology and compared the delay performance of different routing policies. The terrestrial part is generated from the Waxman and Barabasi models. For different values of percentage p, which is the ratio of AS nodes having satellite connections, we generated 100 different integrated terrestrial/satellite network topologies. Taking a topology generated independently each time, we chose 100 different source-destination pairs. For each source-destination pair, BGP-S and BGP-4 are run separately, and the delay results for different routing

Terrestrial	Satellite	
LS=10	planes = 12	
m = 2	satellites per plane = 24	
link bandwidth (BWmin=10Mbps, BWmax=1Gbps)	ISL bandwidth = 160Mbps	
intra-AS delay (ASmin=5msec, ASmax=50msec)	altitude = 1400km	

Table 4: Simulation Parameters for Hybrid Terrestrial/Satellite Network.

method are recorded. This procedure is repeated for every topology. The delay comparisons are made by averaging all 100 x 100 = 10, 000 results.

5.4-2.1   Performance Comparison of BGP-4 in Integrated and Terrestrial Networks
The first set of the simulations compares the delay metric when BGP-4 is implemented both in the terrestrial network and the integrated terrestrial/satellite network. Figure 27 gives the ratio of path delay by implementing BGP-4 globally with and without satellite network versus p. If the ratio equals 1, it means that the delay of the path selected by BGP-4 does not change after the satellite network is included. If the ratio is larger than 1, it means that including satellite network in route selection of BGP-4 introduces longer delays. If the ratio is less than 1, the path delay will be reduced if satellite AS is included in BGP-4. Figure 27 shows that for the Waxman Model and Barabasi Model (when p is larger than 15%), if we apply BGP-4 in the integrated terrestrial/satellite network, the delay is smaller than that in terrestrial network alone. This shows that when satellite links are included in routing selection, the performance improves in terms of delay metric. As p increases, it is easier for BGP-4 to choose the path through satellite network, the performance of BGP-4 in

Figure 27: Performance Comparison of BGP-4 in Integrated and Terrestrial Networks.

the terrestrial/satellite network gets better.

5.4.2.2   Performance Comparison between BGP-S and BGP-4
For the following set of simulations, BGP-S and BGP-4 are simulated on the integrated terrestrial/satellite network. Their results are compared according to the path delay characteristics. The ratio of the delays using BGP-S and BGP-4 versus p is depicted in Figure 28. If the ratio is larger than 1, it means that implementing BGP-S increases the delay of path. Otherwise, the path delay will be reduced if BGP-S is used. In this figure, the ratio is always less than 1 for both the Waxman and Barabasi models, which means that BGP-S always produces lower delays than BGP-4 in the integrated network. This set of simulations show that the satellite network can be utilized with BGP-S in a much better way. However, the decrease/increase of delay ratio as p increases depends on the specific model (Waxman or Barabarsi) used for the terrestrial AS-level network. Later simulations in the following section will show that the change also varies with different selections of satellite constellation.

Figure 28: Performance Comparison between BGP-S and BGP-4.

(a) Different Satellite Numbers.

(b) Different Satellite Altitudes. Figure 29: Effect of Satellite Parameters on BGP-S Performance.

5.4-2.3   Effect of satellite parameters on BGP-S performance
The performance of BGP-S is affected by the architecture of satellite network, such as the number of nodes in satellite network and the altitude of the satellite layer. In this set of simulations, we show the effect of satellite network architecture on the BGP-S performance. In Figure 29(a), the delay ratio of BGP-S and BGP-4 versus p is depicted for satellite architectures with different satellite numbers. The altitudes of all three architectures are fixed as 1, 400km, whereas the satellite numbers are chosen as 60 (with 6 planes), 120 (with 10 planes) and 288 (with 12 planes) respectively. It

shows that when the satellite number decreases, the delay ratio is smaller. In fact, BGP-S produces similar results in all three different architectures. As the satellite number decreases, however, the paths selected by BGP-4 give longer delay as the satellite nodes become sparse.
Next, we fixed the satellite number as 60, and changed the altitude of satellite layer as 700km, 1, 000km, and 1, 400km. The routing procedure is repeated for all three architecture independently. The delay ratio of BGP-S and BGP-4 in the integrated satellite/terrestrial network versus p is plotted in Figure 29(b). It can be seen that as the altitude of satellite layer increases, the performance of BGP-S gets better. This is because when the altitude of satellites is higher, the hops represented by UDLs to/from satellites are longer. If BGP-4 chooses such links, the selected path introduces longer delay. However, BGP-S also gives longer delay as the satellite altitude grows. As the result, the delay ratio varies only slightly (within 1%) under the three different architectures. Hence, we conclude that the satellite altitude does not affect much on the performance gain of BGP-S over BGP-4.

5.4.2.4   Effect of gateway selection methods on BGP-S performance
In previous simulations, the peer gateways are randomly positioned according to the explanation in Section 5.4.1.3. However, we expect that some AS nodes are more likely to have connections to the satellite network. These nodes may include the backbone nodes (e.g., Tier-1 ISPs) and remote nodes (e.g., stub ASs which are several hops away from the Tier-1 ISPs). Hence, in this section, another method called "filtered gateway selection" is used to place the gateways. We set m =1 in this set of simulations, thus, the stub ASs are those with node degree equal to 1.
First, we search for the backbone nodes and remote nodes, where backbone nodes are those with outdegree larger or equal to nb, remote nodes are the terrestrial nodes with node degree equal to 1 and are nr hops away from all the backbone nodes. If

Figure 30: Effect of Gateway Selection Methods on BGP-S Performance.

a node is either a backbone node or a remote node, a peer gateway is equipped and a link is added between this node and its nearest satellite logical location. After placing all gateways, the satellite topology is condensed and the integrated topology is created. We chose several different values of nb and nr for the Waxman model and Barabasi model, respectively. This gave different percentage p of AS nodes having satellite connections. Table 5 lists the values of p corresponding to different nb and nr values. Because the topologies built by the Waxman and Barabasi models have different node degree distributions, their nb values are different, the change of nr also maps to different values of p for the two models.
Figure 30 shows the performance comparison of BGP-S under random gateway selection method and filtered gateway selection method. The y-axis represents the ratio of BGP-S and BGP-4 in the integrated terrestrial/satellite network. Note that the results for random gateway selection method are different from those in Figure 28

		

	1	2	3	4	5	6	7	8	
Waxman model (nb=9)	0.506	0.497	0.470	0.416	0.340	0.254	0.173	0.109	
Barabasi model (nb=25)	0.670	0.591	0.432	0.260	0.132	0.059	0.024	0.010	

Table 5: Values of p Under Filtered Gateway Selection Method.

due to different m values. The results show that as p grows, BGP-S performs better under filtered gateway selection method. Moreover, the growth of p has greater effect on the delay ratio of BGP-S and BGP-4 in the integrated terrestrial/satellite network, if the gateways are installed pre-selectively in backbone ASs and remote ASs.

5.4.3   Summary
Based on the topologies created by ITSTG, we simulated the routing between any pair of terrestrial AS nodes and compared the delay performance of BGP-S and BGP-4 routing policies. The simulation results show that BGP-S always produces lower delays than BGP-4 in the integrated terrestrial/satellite network. The effect of satellite parameters on BGP-S performance was also evaluated. The following conclusions can be made from the simulation results: As the satellite number decreases, the paths selected by BGP-4 have longer delay than those of BGP-S. The satellite altitude does not affect much on the performance gain of BGP-S over BGP-4. Moreover, the growth of p, i.e., the ratio of AS nodes having satellite connections, has greater effect on the delay ratio of BGP-S and BGP-4 in the integrated terrestrial/satellite network if the gateways are installed pre-selectively in backbone ASs and remote ASs.

CHAPTER VI

A ROUTING FRAMEWORK FOR INTERPLANETARY INTERNET

6.1   Motivation and Related Work
The developments in the space technologies enable the realization of deep-space scientific missions such as Mars exploration. These missions require reliable control and produce a significant amount of data to be delivered to the Earth. Moreover, as the next step in the design and development of deep-space networks, the Interplanetary (IPN) Internet is envisioned by NASA enterprises to provide communication services for scientific data delivery and navigation services for the explorer spacecrafts and orbiters of the future deep-space missions [18].
All of these future space missions have a common objective of scientific data acquisition and delivery, which are also the main possible applications of the IPN Internet described as follows [20]:
 •	Time-Insensitive Scientific Data Delivery: The main objective of IPN Internet is to realize communication between in-space entities allowing large volume of scientific data to be collected from planets and moons.
 •	Time-Sensitive Scientific Data Delivery: Great volumes of audio/visual information about local environment is expected to be delivered to the Earth, in-situ controlling robots, or eventually in-situ astronauts [20].
 •	Mission Status Telemetry: The status and the health report of the mission, spacecraft, or the landed vehicles could be delivered to the mission center or other nodes. This application requires periodic or event-driven transmission services which do not require 100% reliable transport.

•	Command and Control of In-situ Elements: The closed-loop command and control may involve indirect or multi-hop communication of the remote nodes, i.e., Earth station commands the mission rover on planet surface or close proximity nodes, i.e., planetary orbit commands the lander.

The main challenges that affect routing in the IPN Internet are listed as follows [11]:
 •	Long and Variable Propagation Delay: The deep-space communication links have extremely long and variable propagation delay. For example, Mars-Earth round-trip time varies from 8.5 minutes to 40 minutes according to the orbital location of the planets [29]. In such networks, the most severely affected routing protocols are the distributed ones that require timely dissemination of the topology information. Node movement during propagation time must be considered in the process of route computation and message scheduling.
 •	Intermittent Connectivity: Link outage may occur for natural reasons such as planetary body blockage and environmental interference. Furthermore, for economical reasons, the radio transceivers of backbone nodes are shared and the link connectivity is scheduled to be episodic. Optimal path selection is difficult because of the temporal nature of the topology graph and the non-negligible link propagation time, especially when the network size is large.
 •	High Bit Error Rates: The raw bit error rate can be in the order of 10_1 on IPN links [29]. Furthermore, burst errors that last on the order of minutes can also be expected. Therefore, the delivery in the IPN Internet is unreliable.
 •	Power Constraints: The operation of the space elements mainly depends on rechargeable batteries using solar energy [53]. The use of nuclear power has also been explored in space applications [6]. The high cost of nuclear power

and the risk of radioactivity release in case of accidents, however, prevent it from extensive communication usage. Therefore, routing protocols in the IPN Internet need to be power efficient.
• Link Asymmetry: The quality of a space link is affected by the sender's power generation capability, the receiver's power amplification capability, the distance between sender and receiver, and the path condition. The link quality is therefore different in opposite directions. The time-dependent nature of the network topology also causes the deep-space links to be asymmetric in delay and stability. Finally, because of application requirements, forward/reverse channels of deep-space communication links have bandwidth asymmetry, which is typically on the order of 1000:1 in spacecraft missions [29]. Therefore, routing in the IPN Internet needs to address the link asymmetry property.
Most of these characteristics are unique to the space communication paradigm and thus lead to different research approaches from those in the terrestrial networks. The IPN Internet is composed of different subnetworks, which face specific challenges. While the existing routing protocols for mobile ad hoc and sensor networks can be applied to some parts in this architecture, there exists significant challenges that necessitate specifically tailored solutions for routing in the IPN Internet.
Space Communication Protocol Standards - Network Protocol (SCPS-NP) by Con-sultive Committee for Space Data Systems (CCSDS) [10] is proposed as a scalable network standard for routing through space networks. SCPS-NP provides multiple design options to meet the requirements and constraints of different missions. For example, routing tables can be configured statically, centrally, or locally by exchanging state information among each other. In addition, datagrams with different priorities can select end system routing, path routing, multicast routing, or flood routing. In spite of its diversified design options, SCPS-NP does not discuss how these options can be implemented in a real space-based network.

Space Backbone Routing

SBR-external	
remote control& automatic data delivery
LPDB	controlled data delivery RIOR	

SBR-interior	
contact allocation
LQ	traffic dispatching MW	

Figure 31: Proposed Routing Framework in the IPN Internet.

The IPN Internet is a special type of the delay-tolerant networks (DTNs) [19], where continuous end-to-end connectivity cannot be assumed. Routing through the DTNs is done in the bundle layer [58], which resides between the application and the lower layers. To address the intermittent connectivity property, a store-and-forward message switching mechanism called "tiered routing' is proposed in the bundle layer. Node-to-node reliability is added into the network by the storage and retransmission functionalities of the bundle agents. A recent paper [44] formulates the DTN routing problem based on different knowledge about network topology. The proposed algorithms require error-free communication and no effective solutions are given when unpredictable link failures occur. Furthermore, neither the bundle layer descriptions [58] nor the DTN routing paper [44] provides mechanisms for gathering the forwarding information through the network.
In this research, a new routing framework for the IPN Internet, i.e., space backbone routing (SBR), is introduced as shown in Figure 31. SBR is proposed based on the hierarchical architecture of the IPN Internet and specifically addresses its challenges. SBR was first described in [23]. SBR has two integral parts: SBR-external and SBR-interior. SBR-external addresses the delivery of remote control messages and scientific data through the IPN Internet. The control and data messages are delivered in a store-and-forward manner and they may need to be buffered in intermediate nodes for a considerably long time. Location-predicted directional broadcast (LPDB) is proposed for fast and reliable delivery of remote control messages and automatic data reports. Paths to the destination are calculated en route based on the predictable

node locations and reachability information. These paths are used to direct and limit the forwarding area of the control message broadcast. For controlled data delivery that contains large amounts of scientific data from remote exploration sites back to the Earth and requires high reliability, a combination of reactive and proactive approach is utilized in our proposed receiver-initiated on-demand routing (RIOR) protocol. Route discovery is initiated on-demand by the receiver and routing tables are maintained in soft state at the nodes along the forwarding area. No end-to-end path is recorded for the data delivery. Link state exchange during the data transmission process provides the nodes with up-to-date path information. SBR-interior is executed within an autonomous region (AR). It exchanges inter-AR routing information among backbone nodes within an AR and schedules inter-AR message transmissions. The problem definitions of two important functionalities of SBR-i, i.e., contact allocation and traffic dispatching, are given. As a first attempt, we propose the longest queues (LQ) policy for contact allocation and the minimum waiting (MW) policy for traffic dispatching.

6.2   Network Description
The IPN Internet shown in Figure 1 supports data delivery across interplanetary distances for deep-space exploration. The properties and assumptions of the nodes and links in the IPN Internet, and the proposed routing framework for this network architecture are described in this section.

6.2.1   Network Components
• Autonomous Regions
The IPN Internet is composed of multiple autonomous regions (ARs). An AR contains communication entities that are located close (i.e., much shorter than the interplanetary distance) to each other. These regions are called "autonomous" since the local nodes can communicate among themselves using a single common protocol

family. The routing decisions within a region can be made locally without consulting a centralized authority in the IPN Internet or intervention from other regions. The Mars planetary network in the IPN Internet architecture shown in Figure 1 is an example of AR. The IPN backbone network provides a common infrastructure for communications among different ARs. An AR topology is formed by abstracting each AR as a meta-node called an AR node. The location of an AR node can be represented by a position within the AR. For example, the location of the Mars region can be represented by the geometrical center of the Mars planet. • Backbone Nodes
The nodes in the IPN backbone network have long haul communication capability and are called " backbone nodes." Examples of backbone nodes include:
 1.	Planet surface elements such as the Earth ground stations for NASA's Deep Space Network [8].
 2.	Relay satellites orbiting around planets such as Earth satellites and those consisting Mars Network [39].
 3.	Other intermediate relay nodes, such as mission-specific space shuttles and relay stations at the Lagrangian points1 of planets like Jupiter and Pluto [18].
As described previously, these backbone nodes are organized into different ARs according to their locations.
The backbone nodes are constantly moving abiding by the orbital mechanics. This kind of node mobility is calculable by the knowledge of their trajectory information. For example, an ephemeris, which is a table of the positions of celestial bodies at specified intervals of time, can be built to describe the predictable aspects of the

1The Lagrangian points are positions where the gravitational pull of two large masses precisely cancels the centripedal accelerationrequired to rotate with them. A third body of negligible mass could be placed at the Lagrangian points and maintains its position relative to the two massive bodies.

Figure 32: AR Link luv(t).

node mobility [28]. • AR Links
Consider the solar system as a linear vector space centered at the sun, the position of an AR node u at time t is then represented by a vector ru(t) originating from the sun. An AR node v is reachable by node u and called an AR neighbor of node u at time t, if there exists some A(t) > 0 that satisfies the following condition:

rv(t + A(t)) - ru(t)|| = C • A(t) < Luv(t)

(25)

where C is the speed of light and Luv (t) is the reachable range limit between node u and v. If the transmission delay can be omitted, Equation (25) states that a signal transmitted at time t from node u located at ru(t) can be received by node v at position rv (t + A(t)) at time t + A(t), as shown in Figure 32. For clarity, we associate A(t) with each link and write it as duv (t), which represents the link propagation delay from u to v. Both duv(t) and Luv(t) vary with time. For deep-space communication links, duv (t) may be as long as several minutes. Luv (t) is decided by factors such as node u's transmission power and transmit antenna gain, node v's receive antenna gain, and the path condition between u and v within time period [t,t + duv (t)]. The reachability from u to v at time t is denoted by an AR link luv(t). Each backbone node maintains its reachability information, which specifies possible reachability opportunities with its AR neighbors.

The signal transmission and reception on AR links are assumed to have the following properties:
 1.	Inter-AR communication uses different frequency band from that used for intra-AR communication. Therefore, signals targeted for receivers within the local AR and those for the backbone nodes in a different AR do not interfere with each other.
 2.	Due to the extremely long distance, communication via AR links require huge power consumption and the cost per second of transmission can become very high. To reduce the transmission cost associated with AR links, directional antennas are used to increase the power efficiency toward targets. Moreover, a backbone node can only transmit to one AR neighbor in a timeslot (Tsiot in length).
 3.	Omni-directional antennas or multiple directional antennas with different pointing angles are used for signal reception. A backbone node can receive signals from different ARs simultaneously and differentiate them by their distinct angle-of-arrivals (AoAs). Signals from different backbone nodes in the same AR to the same AR neighbor collide with each other, as their AoAs are approximately the same.
 4.	Incoming signal from an AR neighbor can be picked up by any local backbone nodes that are within the transmission antenna's field-of-view.
• Contacts
It is assumed that the backbone nodes in an AR are time-synchronized and time is slotted with length Tslot. The local time at different ARs can be translated to a common time, e.g., the coordinated universal time (UTC) [3]. The difference in time synchronization between ARs is omittable compared to the propagation delay on AR

links. As one of the communication properties of AR links, there can be only one backbone node in an AR that transmits to a specific AR neighbor within a timeslot. Therefore, some scheduling mechanism is needed to allocate the next contact toward an AR neighbor to one local backbone node. A contact describes an allocated time period when a backbone node, but not other backbone nodes in the same AR, can transmit to one AR neighbor. In this research, the length of a contact is a multiple of Tslot. An AR node u is "connected' to an AR neighbor v at time t only if v is reachable by u and one of u's backbone nodes is in contact with v at time t.
In the AR topology, there is at most one AR link between any two AR nodes. AR links may be intermittent and represented by a series of different contacts at different time. A contact is characterized by the transmit backbone node, the reception AR neighbor, start time, end time, and a link capacity.

6.2.2   Routing Framework
The terrestrial Internet is organized into autonomous systems (ASs). Inside every AS, routing is accomplished through interior gateway protocols (IGPs). Inter-AS routing is based on an exterior gateway protocol (EGP), namely the border gateway protocol (BGP). BGP has two parts: external BGP (EBGP) used between ASs and interior BGP (IBGP) to exchange inter-AS routes within an AS. Similarly, the IPN Internet is organized into ARs. Different routing protocols can be developed for intra-AR communications to address specific challenges inside each AR, whereas a common routing protocol is needed for communication across the IPN Internet. For this purpose, we propose a common routing framework, namely space backbone routing (SBR), for communication among ARs through the IPN Internet. As shown in Figure 31, SBR has two integral pieces: SBR-external (SBR-e) and SBR-interior (SBR-i).
• SBR-external populates the forwarding information through the IPN Internet and selects AR paths for inter-AR messages.

•	SBR-interior routes inter-AR traffic through an AR and schedules inter-AR message transmission at backbone nodes.

6.3   Space Backbone Routing - External
The objective of the IPN Internet is to realize communication among in-space entities allowing large volume of scientific data to be collected from remote space exploration sites. The main traffic through the IPN Internet contains the following:
 •	Remote Control: The command and control messages sent from the Earth to remote devices at the exploration sites. Although in-situ command and control by local components (such as a lander controls a rover) within an AR is preferred to avoid the long propagation delay [20], the Earth control center is still responsible for backup remote control and new instructions injection. The delivery of remote control messages is time-sensitive and requires high reliability.
 •	Data Delivery: The scientific data delivery from the exploration sites back to the Earth. We further classify the data delivery into two types with respect to the initiator and the service requirements:

 —	Automatic Data Delivery: This type of data delivery is initiated by the mission devices at the remote exploration site, reporting mission status and some environmental data typically via repetitive transmissions [20]. Automatic data delivery is time sensitive and does not have strict reliability requirement.
 —	Controlled Data Delivery: The Earth control center actively queries the mission devices for important scientific data delivery. In this application, the Earth center is aware of where to retrieve the scientific data from and initiates the data delivery. Compared to other traffic types, this type of data delivery requires the higheest level of reliability.

Control and data messages are self-contained units of work, which are called "bundles" in [19]. A message contains whatever the application wishes to send and is delivered in an atomic fashion. Messages are routed through the IPN Internet in a store-and-forward manner and may need to be stored in an AR for a considerably long time (minutes or even hours), waiting for an outgoing contact opportunity.
According to the traffic types in the IPN Internet, we propose to use
 •	Location-predicted directional broadcast (LPDB) for remote control and automatic data delivery, and
 •	Receiver-initiated on-demand routing (RIOR) for controlled data delivery.
The characteristics of different traffic types and their respective routing strategies proposed in this paper are listed in Table 6.

6.3.1   Location-Predicted Directional Broadcast (LPDB)
Although the locations of the AR nodes are predictable, there exist unpredictable factors in the AR topology caused by different contact schedules at AR nodes, environmental interferences, and power variation. Flooding is the most reliable method for fast delivery of control messages and automatic data delivery, but at the expense of network resource wastage and high power consumption. Therefore, we limit the broadcast area in space and time.
A control message or an automatic data delivery message contains fields of {destAR, expireAt}, where destAR identifies the destination AR node and expireAt indicates the time constraint set by the application. The LPDB protocol is done independently

Traffic type	Initiator	Message size	Time-sensitive	Reliability	
remote control	sender	small	yes	high	
automatic data delivery	sender	medium		medium	
controlled data delivery	receiver	large	no	highest	

Table 6: Comparison of Different Traffic Types in IPN Internet.

at each AR node and has two parts: reference AR path computation and directional forwarding.

6.3.1.1   Reference AR path computation
A reference AR path is computed according to the predictable AR topology at all times and some locally available information at the source AR. The problem of reference AR path computation can be formulated as follows: Given the following parameters,
-	A time-varying AR topology G(V, E(t),t), which composes of AR nodes V and a set of AR links E(t). AR links are directed links that describe the reachability and the associated propagation delay between AR nodes, as defined in Section
6.2.1.
 -	Source AR s, destination AR d, and message arrival time ts.
 -	Expected waiting time usv at s to its AR neighbors //v E Ns, where Ns is the set of possible AR neighbors of AR s. usv consists of the buffering time at s waiting for a contact opportunity to AR neighbor v to occur, and the queuing time waiting for all the locally-buffered messages to v to be serviced2.
A fastest traversal AR path can be computed as a concatenation of possibly time-disjoint AR links Ps^d = (lsvi(td),^■ lvm-1d(rm-i)), where lvi_1vi(Ti-1) is an AR link at time Ti-1 as defined in Section 6.2.1. Then n = (s,v1, ■■■,vm-1, d) is the topological AR path. The departure times at the AR nodes on the topological AR path are computed by t0 = ts + usvi, Ti = Ti-1 + dvi-ivi(Ti-1) + ti, 0 < i < m — 1, where ti is the message buffering time at node vi.
This type of problems can be solved using extensions of Dijkstra's algorithm in time-dependent networks [54], where the fixed link cost is replaced by the sum of

2The estimation of this expected waiting time is done by SBR-i inside every AR as in Section 6.4 and the updated values are locally available to LPDB.

message buffering time and the time-dependent link propagation delay (duv (t)). In
the first hop, this buffering time is the locally-available expected waiting time (usv),
which is the sum of the buffering time at s waiting for a contact opportunity to v1 to
occur and the queuing time waiting for all the locally buffered messages to v1 to be
serviced. With queuing delay omitted, the message buffering time      in later hops
is approximated by the waiting time for the next AR neighbor (vi) to be reachable,
which can be calculated by the predictable location information of AR nodes. The
modified Dijkstra's algorithm for the time-dependent AR topology is given below:
Algorithm 3 Modified Dijkstra's algorithm Input: G = (V,E (t),t); s,d,ts; uSv, /v E Ns
Output:  Ps^d = (lsvi (To),lviv2 (T1),       lvm-id(Tm-1))
Set D(s) = ts; D(v) = ts + u)sv + dsv(ts + ^sv), tau(v) = ts + u)sv, pred(v) = s, hop(v) = 1, /v E Ns; D(v) = 00, /v E V,v = s,v £ Ns Set S = V\{s} while S = 0, do
Let u = arg minxes D(x)
S = S\{u}
for each v E S, do
t* = min{t I luv(t) E E(t),t > D(u)} if D(v) > t* + duv (t*), then
D(v) = t* + duv(t*), tau(v) = t*
pred( v) = u, hop( v) = hop( u) + 1 end if end for end while
Set v = d, m = hop(d) while v = s, do
Tm-1 = tau(v), vm-1 = pred(v)
v = pred(v), m = m — 1 end while

The AR path computed in this way only represents the shortest-delay path under the condition that the queuing delay can be omitted at the computed departure time ( Ti, 0 < i < m — 1) and the intermediate nodes are ready to pick up the messages at the reception time. When scheduling or retransmission delays the messages, however, the computed AR path may not be optimal or exist any more. The computed AR

path is used just as a reference to direct the message forwarding and thus called "reference AR path". As actual message delivery can deviate from the pre-calculated timeline, the AR paths calculated by previous AR nodes may be obsolete. Therefore, the intermediate AR nodes update the reference AR path as messages traverse the IPN Internet.

6.3.1.2   Directional forwarding
When an AR node (including the source AR node) receives a control message or an automatic data delivery message, it computes the reference AR path from itself to the destination AR node. The message forwarding is limited in space and time. Specifically, suppose an AR node v receives a message at time t0, the topological AR path from v to the destination d is computed as n = (v,v1, ■■■,vm-1,d), and the departure time at v is T0. Then, only AR neighbors that lie within the forwarding cone within time interval [t0,T0 + Tthresh] can receive a copy of the message, where Tthresh is a parameter set by the application or at the AR nodes.
As shown in Figure 33, if the antenna gain at different receivers is the same, the forwarding cone contains the space that is within node v's transmission power range Lv and limited within cone angle 9 around the axis from v to d. The cone angle is

Figure 33: Location-Predicted Directional Broadcast.

calculated by

9(n,t) =  max {ivvd + 5],	(26)
vien\{v]
where 5 is a parameter that controls the width of the forwarding cone. In order to adjust the forwarding cone to the movement of AR nodes during the message delivery process, lvivd is computed by the predicted location of node vi on the reference AR path, e.g., the location of vi on the path is represented by rvi(Ti-1 + dvi_ivi(Ti-1)). In Figure 33, the reference AR path is n = (v, v1,v3, d), the control message is forwarded to nodes v1 and v2 in the forwarding cone. Any redundant message or outdated message received by an intermediate AR node gets dropped3.
Remark: LPDB can be classified as a special type of location-aware routing protocol [27]. Its difference from traditional algorithms like LAR [47] and DREAM [17] is that no network-wide flooding is needed in LPDB to obtain nodes' location information, which can be calculated according to the orbital mechanics. Furthermore, the network connectivity intermittency caused by predictable natural reasons, such as the planetary body blockage, is addressed by allowing message buffering at the AR nodes. Directional forwarding provides multipath routing near the reference AR path in order to handle link unreliability and speed up end-to-end delivery.

6.3.2   Receiver-Initiated On-demand Routing (RIOR)
The Earth-controlled data delivery carries scientific data that are usually unprocessed and very large in volume. Therefore, flooding and the directional broadcast in LPDB would consume very high network resources. This type of traffic also requires high reliability, which is difficult to achieve in the deep-space environment without redundant delivery or maintenance of up-to-date routing information. Since the Earth

3 To detect message redundancy, some state information about the messages needs to be maintained.

Table 7: Format of a Route Entry.
sink   nh   delayToSink
sink:	destination AR;
nh:	one upstream AR neighbor to sink;
delayToSink:   delay from the local AR to the sink by way of nh.

control center knows when and where this type of data needs to be gathered, we propose the use of on-demand route discovery initiated by the receiver, i.e., the Earth control center. Routing tables at the intermediate AR nodes that are possibly on the data delivery path are built on-demand and maintained in soft state by exploring the link status and load distribution. The proposed routing protocol is referred to as the receiver-initiated on-demand routing (RIOR) thereafter.

6.3.2.1   Route Discovery and Maintenance
For convenience, we call the Earth control center the "sink1 in this application scenario. The route discovery contains two parts:
 •	RREQ notification and KeepAlive exchange,
 •	Routing table maintenance.
Table 7 shows the format of an entry in the routing table. 1) RREQ notification and KeepAlive exchange
At some time long enough4 before the data delivery will start, the sink initiates route discovery by sending out an RREQ control message to the data source AR periodically at an interval Trreq . The delivery of the RREQ message follows the same LPDB scheme in Section 6.3.1 as for other control messages. Duplicated and outdated RREQ messages are dropped.
The reception of the RREQ message also initiates periodic KeepAlive requests from the receiving AR node to the message sender, and the KeepAlive reply in the reverse

4Considering the long propagation delay between the sink and the data source.

direction. The KeepAlive exchange interval Tka is much smaller than Trreq. The exchange of KeepAlive message serves for two purposes:
 •	To measure the delay of AR links and monitor the AR link quality, and
 •	To build route entries to the sink AR.

Due to the constant movement of the AR nodes, new rounds of RREQ message transmission are initiated periodically until the expected data arrives the sink or after a specified timeout value. Later RREQ messages may follow different reference AR paths to the data source. This is to adapt the area of the control message exchange to node movement and AR link condition changes.
2) Routing table maintenance
Routing tables at the intermediate AR nodes are built upon reception of the KeepAlive reply messages. There may be multiple route entries for the same sink, enabling multipath routing and providing alternate paths when one path fails.
A new route entry is built as follows:
 •	Upon receiving the KeepAlive request, an AR node (u) records the directional link delay (dvu) from the sending node (v). This link delay is the time elapsed from the transmission of the request at v to its reception time at u.
 •	Node u selects the minimum delayToSink value (Du) in all entries associated with the same sink in its routing table.
 •	A KeepAlive reply is sent in the reverse direction (from u to v), containing the link delay (dvu) and the minimum delayToSink value (Du).
 •	Node v then retrieves the information (dvu and Du) from the KeepAlive reply and creates a new route entry with parameters of (sink, nh=u, delayToSink=
dvu + Du).

Once a route entry is built, delayToSink is updated as the value contained in the latest KeepAlive reply to capture the current link property. If an AR node has not received RREQ or KeepAlive message from one AR neighbor for a long time5, it stops KeepAlive message exchange with this neighbor and the corresponding route entry is removed as well.
The actual data delivery follows the information contained in local routing tables. The nh with the minimum delayToSink value6 is chosen as the next-hop AR. As the delayToSink value is augmented with the propagation of RREQ message from the sink to the source, the delay of the previous part of the path that RREQ message traverses may be outdated. The correctness of this delayToSink value therefore decreases as the distance from an AR node to the sink grows. When the RREQ message first reaches the source AR, the minimum delay path seen from the source may not be optimal. Nevertheless, KeepAlive exchange continues updating the route state during the data delivery and refining the remaining path toward the sink. As the data message traverses closer to the sink, the delayToSink approaches its current value.

6.3.2.2 Route Repair
As a data message traverses the network, if an intermediate AR node finds that the nh with the minimum delayToSink value is not reachable, or it cannot receive an acknowledgment from the nh after a certain number of consecutive retransmission attempts, a link failure to this nh is detected. In this case,
 •	It reroutes the data message to alternate, possibly longer delay paths in the routing table.
 •	If no alternate path is available, a copy of the data message is sent back to the previous hop, which may find an alternate path.

5 Each AR node can decide its timeout period independently, taking consideration of its power availability, the link propagation delay, or the delayToSink value.
6Data can also be forwarded to multiple next-hops for multipath routing.

(a) RREQ Message Forwarding.

(b) KeepAlive Message Exchange. Figure 34: Route Discovery and Repair for Controlled Data Delivery.
• Meanwhile, an RREQ message is initiated and sent to the sink periodically with interval Trreq using the LPDB scheme in Section 6.3.1. KeepAlive exchange is also initiated between AR neighbors along the forwarding path to the sink. However, an AR nodes only starts new KeepAlive exchange with the AR neighbors that it has no information about.

The above procedure facilitates route discovery in case of link failure.

6.3.2.3   Example
An illustrative example of RIOR is shown in Figure 34, where the RREQ message forwarding and KeepAlive message exchange are depicted in Figures 34(a) and 34(b), respectively. The solid lines in Figure 34(a) represent the forwarding of the RREQ message from the sink. The reception of RREQ along the forwarding paths initiates KeepAlive exchange between AR neighbors as shown by the solid lines in Figure 34(b). The AR nodes in the forwarding paths, i.e., nodes v1 to v6, build and update route entries to the sink.
Take node v4 as an example, it sends out KeepAlive request to its upstream neighbors Vi and v5 after reception of RREQ messages from them. vi and v5 inform v4 that their minimum delayToSink values to the sink are 25min and 56min, respectively. The KeepAlive replies from v1 and v5 also provide v4 the link delay values (d41 = 20min and d45 = 30min, respectively). Based on these information, v4 builds two route entries to the sink, which are {sink, v1, 45min} and {sink, v5, 86min} in Figure 34(b). v4's minimum delayToSink value D4 is set as 45min. The route entries are updated as new KeepAlive replies are received.
Suppose a data message takes the path of (source, v4, v5) and finds that the link to v2 is not reachable. As no alternate path is available at node v5, a copy of the data message is reflected back to node v4. Meanwhile, an RREQ message is sent from v5 to v7 in v5's forwarding cone to the sink along the dashed lines in Figure 34(a). Periodic KeepAlive exchanges are initiated between the new nodes on the forwarding path, as shown by the dashed lines in Figure 34(b). Thus, new paths, such as (source, v4, v5, v7, v8, sink), can be found.
Remark: RIOR executes reactively to the application requests. There is no network-wide topology propagation. RIOR does not look for a specific route used for the data delivery session as other on-demand routing protocols in wireless ad hoc networks,

such as DSR [45] and AODV [56], since this route may be obsolete after the long route-discovery phase. Upon detection of link failures, DSR and AODV notify the sender node, which then restarts the route-discovery process. In the RIOR protocol, on the other hand, the KeepAlive messages are utilized to obtain the up-to-date link property, so that the updated route entries reflect more recent delay metrics. The maintenance of multiple route entries to the sink provides alternate routing options. New route discovery can be issued at any intermediate node that encounters link failure. These mechanisms help RIOR adapt fast to the changes in the IPN Internet with long and variable delay. RIOR does not assume link symmetry, all delay measurements are directional. In other words, the challenge of link asymmetry as stated in Section 6.1 is addressed by RIOR.
Another related work is the directed diffusion [43] proposed for wireless sensor networks, which is also a type of receiver-initiated protocol. In directed diffusion, an interest message (like the RREQ message in RIOR) is injected into the network and refreshed periodically by the sink node. Each sensor node maintains an interest cache, of which an entry contains a gradient field associated with an upstream neighbor to the sink. Each gradient field records the reception rate of interest message from a neighbor. The sink reinforces the paths with better quality only after it starts receiving the exploratory events from the event area. This type of feedback-based adjustment, however, is not applicable in the IPN Internet with long delay. The routing table in our RIOR protocol functions similar to the interest cache in directed diffusion. However, RIOR records the delayToSink value instead of the data rate via each upstream neighbor. The entries with shorter delayToSink metric are selected in the data delivery session. Also note that end-to-end negotiation, which is described in directed diffusion [43], does not exist in RIOR.
The location-predictability is not required for the functioning of RIOR. Therefore, RIOR can also be used in other types of wireless networks with dynamic topology

when schemes other than LPDB are used for RREQ propagation.

6.4   Space Backbone Routing - Interior
The computation of forwarding cone and routing table maintenance for inter-AR traffic are done by SBR-external (SBR-e), whereas the actual information exchange and message delivery between ARs are functions of SBR-interior (SBR-i). SBR-i directs the inter-AR traffic through each AR by way of border routers, which may be any backbone nodes as long as they can reach the next-hop AR neighbors.
As described in Section 6.2.1, a backbone node can only transmit to one distant neighbor in a timeslot with length Tsiot and only one border router in an AR can transmit to an AR neighbor. To avoid signal collision, a contact allocation policy is called to schedule the contacts for each border router to its AR neighbors. Meanwhile, a traffic dispatching policy is needed to direct each incoming message to an egress router. SBR-i is executed inside each AR and performs the functions of contact allocation and traffic dispatching as follows:
 •	Allocate contact schedule for border routers in an AR,
 •	Direct messages to their next-hop ARs via dynamically selected border routers.
It is also pointed out in [20] that in the presence of intermittently available links, the IPN gateway needs to decide not only the next-hop destination but also the time at which to send a message. The routing function in IPN gateways is conceptually described in [20] and has three parts: the contact scheduler, the route evaluation algorithm, and the dispatcher algorithm. In our work, the second is addressed in SBR-e whereas the first and the last are included in SBR-i in our routing framework.

6.4.1   Problem Modeling
Suppose that the number of backbone nodes in an AR is N, the transmission to a specific AR neighbor can be thought as a queuing model consisting of a single

server and N parallel queues, where the server is the AR neighbor and each queue corresponds to a backbone node. If an AR has M AR neighbors, the transmission to these neighbors contains M such queuing models with inter-dependent queue lengths and server working schedules. Consider AR u, given
 -	Bu, the set of backbone nodes in AR u,
 -	Nu(t), u's AR neighbors set at any timeslot t,
 -	Qiv (t), the queue length of a backbone node i e Bu to any AR neighbor v e Nu(t) at the current timeslot t,
 -	Riv (t), a binary variable describing the reachability of an AR neighbor v e Nu(t) by a backbone node i e Bu at any timeslot t.
For clarity, we say that an AR neighbor v e Nu (t) is reachable by a backbone node i E Bu at timeslot t, i.e., Riv(t) = 1, if Equation (25) is satisfied for a period in timeslot t and the signal transmission from i to v is not blocked by the body of AR u.
SBR-i performs two major functions as follows:
 •	Contact Allocation: For each backbone node i e Bu, decide its target AR neighbor at any timeslot t, Ti(t) e {Nu(t),e}, where e stands for the IDLE mode. According to the assumptions in Section 6.2.1, no more than one border router can simultaneously transmit to the same AR neighbor, i.e., if j = i and Ti(t) = e, then Tj (t) = Ti(t). For a specific backbone node i, the allocated values of Ti(t) in continuous time give its contact schedule, which contains a discontinuous set of contacts.
 •	Traffic Dispatching: For an incoming message £ arriving at t with next-hop AR neighbor v, select    (t) e Bu, the backbone node that performs as its egress

router in AR u.

The objective function can be the maximum AR throughput, the minimum buffering delay of incoming messages, or load sharing among backbone nodes, etc.

6.4.2   Possible Solutions
We propose two simple policies for the problem of contact allocation and traffic dispatching, respectively.
1) Longest Queues (LQ) policy: Allocate the next timeslot to the backbone nodes that can reach and also have the longest queues associated with the AR neighbors. The goal for this policy is to transmit as much inter-AR traffic load as possible, thus achieving maximum throughput.
The LQ policy is executed at a contact allocator, which contains the queuing information of all backbone nodes. In detail, at the start of each timeslot, every backbone node reports to the contact allocator the queue lengths associated with its reachable AR neighbors. The comparison of queue lengths takes into consideration of the difference in message lengths. For example, if there are two messages in a queue, with lengths of 4KB and 6KB, then the queue length is 10KB. A simplified version of the LQ policy is executed in Algorithm 4.

Algorithm 4 LQ policy
Input: QiV(t), Vi e Bu, Vv e Nu(t) Output: Ti(t), Vi e Bu
Set S = Nu(t); Ti(t) = e,Vi e Bu while S = 0, do
Q* = max(i(zBu,v(,s){QiV(t) | Ti(t) = e,RiV(t) = 1}
if Q* = 0, then break
end if
(i*,v*) = argmax(i€Bu,ves){Qiv(t) | Ti(t) = e} Allocate Ti* (t) = v* S = S\v end while

2) Minimum Waiting (MW) policy: Direct a message to the border router that is expected to have the minimum waiting time to serve new traffic.
To execute the MW policy, each backbone node needs to calculate the expected waiting time to its AR neighbors, and reports the values to a traffic dispatcher. The MW policy can be written in Algorithm 5.
Algorithm 5 MW policy
Input: message £ with next-hop AR v arriving AR u at t Output: egress router     (t) = argminieB«{uiv}

Message £ is encapsulated and sent to the selected egress router (t), which then does the de-capsulation. If (t) is not allocated to the AR neighbor v at the current timeslot t, the message is buffered there and waits for a future contact opportunity.
The estimation of the waiting time uiv includes two parts: the calculation of the time till the AR neighbor v to be reachable, and the estimation of the time to finish serving the message contents in node i s queue to AR neighbor v. The former can be decided by node i and AR v s trajectory information, whereas the latter needs to take the current queuing information and the AR link capacity into consideration.
After decision of the egress router, the expected waiting time of AR node u to AR neighbor v is represented by the waiting time from the egress router to v, i.e., uuv = uiv, where i = (t). uuv is also provided to SBR-e and help computing the reference AR path in LPDB, as described in Section 6.3.1.1.

6.4.3   Discussion
We give the problem definition of contact allocation and traffic dispatching, and propose some possible solutions for these SBR-interior functions. However, the proposed solutions are some preliminary attempts. Further exploration is needed to address the following issues:

• The contact allocation and the traffic dispatching policies are correlated to each

other. For instance, the traffic dispatching policy directs traffic to different border routers, thus affects the traffic arrival rates and queue lengths at each backbone node, which are important decision factors of the contact allocation policy. On the other hand, the contact allocation policy affects the message buffering time at each backbone node, which in turn influences the decision of the traffic dispatching. Therefore, the two policies cannot be considered separately in order to achieve best performance.
 •	The performance of SBR-e is affected by the contact allocation and traffic dispatching policies in SBR-i as well. For example, in LPDB, the longer the messages need to wait at an AR to be serviced, the less accurate the computed reference AR path will be. RIOR requires periodic RREQ and KeepAlive message exchanges between AR neighbors; the scheduled property of link contacts between AR neighbors would probably delay the exchange, which in turn affects the timely propagation of routing information. Possible improvements include priority-setting different types of messages (e.g., RREQ and KeepAlive messages, and application data message) for queuing, and bandwidth reservation for applications with certain QoS requirements.
 •	The contact allocator and the traffic dispatcher can be located in a specific device in an AR network, or distributely at multiple backbone nodes. Some efficient information report/exchange scheme is required to reduce the control overhead while keep the related information up-to-date.
 •	As mentioned in Section 6.2.1, an incoming message £ can be captured by several border routers in an AR. The redundant copies of £ can be deleted at the selected egress router (t). This method, however, introduces redundant delivery inside AR networks. To design an efficient scheme that detects and removes the redundant copies is also an ongoing research.

6.5   Performance Evaluation
In this section, we evaluate through simulations the performance of the proposed SBR-external (SBR-e) protocols for remote control and data delivery, and the proposed SBR-interior (SBR-i) policies for contact allocation and traffic dispatching, respectively. The results confirm that the protocols for SBR-e are efficient in both message delivery and power consumption, and meet the service requirements of different traffic types in the IPN Internet. The policies for SBR-i achieve low buffering delay and higher throughput with low message dropping probability.

6.5.1   Evaluation of SBR-external Protocols
An event-driven simulator on C++ is developed to evaluate the performance of SBR-e. Two types of AR nodes are built in the network model: planet ARs and the planetary Lagrangian ARs. Specifically, there are 9 planet ARs and 18 planetary Lagrangian ARs. To simplify the model, all planets move around the sun in circular orbits in the same plane. The orbit radii of the planets are from 1AU to 9AU (1AU ~ 149, 600, 000km), with 1AU in between. The planet orbiting period T (in year) is decided by the Kepler's third law: T2 = a3, where a is the planet orbit radius in

Figure 35: Network Model for IPN Internet.

AU [5]. The Lagrangian ARs (of type L4 and L5 [59]) are on the same orbits of the associated planet, 60° ahead of or behind the planet. The reachable range limits of all AR pairs are set as 5AU. Our network model is shown in Figure 35, where the dots refer to the planet ARs and the triangles are the planetary Lagrangian ARs. All nodes circulate around the sun according to the orbital mechanics.
For the sake of simplicity and to minimize the effect of SBR-i on the performance of SBR-e, we assume that contact allocation does not delay message forwarding. In other words, whenever an AR catches a message, it is connected to the computed next-hop AR neighbor at the time when the neighbor first becomes reachable. It is further assumed that each contact has an associated link capacity that is large enough to finish the transmission of a message before the contact's end time. The transmission and queuing delays can be omitted compared to the link propagation delay.
In each simulation round, the initial positions of the planet AR nodes are randomly set with central angles uniformly distributed in [0°, 360°). Control/Data messages are sent in 1 hour interval within each simulation round of 1 day long. All results are averages of 20 simulation rounds. Control/Data message delivery performances are evaluated under different link failure probabilities. Each link between AR neighbors is prone to failure according to a probability. Failure is independent across different links.

6.5.1.1   SBR-e for Remote Control and Automatic Data Delivery
For remote control and automatic data delivery, our proposed location-predicted directional broadcast (LPDB) scheme in Section 6.3.1 utilizes the location predictability of AR nodes. It also selects multiple next-hop nodes to forward the message to provide redundancy in the unreliable IPN Internet. To measure the performance of these techniques, we compare LPDB with two other schemes:

 •	Location-aided routing (LAR): This is the LAR scheme 2 in [47] with a = 1 and f3 = 0, i.e., a message is forwarded from the current AR node to the neighbors that are closer to the destination. The computation of distance takes into consideration the movement of the destination node.
 •	Location-predicted single-path routing (LPSP): This is a special case of LPDB where a message is forwarded only to the next-hop neighbor on the reference AR path. The reference AR path is computed the same way as in Section 6.3.1.1 and updated at each intermediate AR node.
To measure the effect of forwarding cone angle on the performance of LPDB scheme, two different values of 5 (as explained in Section 6.3.1.2) are chosen in the simulation.
We use both message delivery and message transmission cost metrics to evaluate the performance of the three different routing schemes. The message delivery ratio is defined as the ratio of the number of successfully delivered message to the total number of messages generated. The message transmission cost gives the average total transmissions at the intermediate AR nodes for each successful message delivery. This metric also measures the efficiency of energy usage. The message delay is the average delay between the time that the message is generated and the time that the message is first received at the destination AR. Note that this delay is averaged only over the cases of successful deliveries.
In our simulations, we test the performance of remote control delivery. Remote control messages are sent from node 0 (orbit radius = 1AU) to node 7 (orbit radius = 8AU), with maximum life time of 6 hours. Control messages are transferred in a store-and-forward manner. Each AR node stores a copy of the message and should make sure that every next-hop AR gets a correct copy of the message via per-hop acknowledgment before it removes its local copy.

Figure 36(a) shows the message delivery ratio of these three schemes under different link failure probabilities. None of the schemes guarantees 100% end-to-end delivery although hop-by-hop reliable delivery is assured by acknowledgments. The reasons for message delivery failure may include: The LAR scheme cannot find any AR neighbor that is closer to the destination than the current AR, hop-by-hop reliable delivery takes too long that the next-hop neighbor moves out of current AR node s reachable range limit, no reference AR path can be computed thus the message must be dropped, or the message times out during delivery. The LPSP scheme does not provide path redundancy so that the message delivery ratio drops the fastest when the link failure probability increases. For the LPDB scheme, as the forwarding cone angle increases, more messages are successfully delivered to the destination. The delivery ratio is always higher than 90%. When 5 = 60°, the message delivery ratio of LPDB approximates that of LAR.
The LAR scheme provides high degree of redundancy for message delivery. Thus, it achieves low end-to-end delay but with high transmission cost, as can be seen in Figures 36(c) and 36(b), respectively. The message transmission cost of the LPSP scheme is the lowest among the three schemes, as depicted in Figure 36(b). LPSP introduces much higher end-to-end delay than the other two schemes. The reason is that LPSP relies on successful message transmissions on the reference AR path to reach the destination. The increase of link failure probability lengthens the time for per-hop transmission over any AR link, which in turn affects the end-to-end delay performance. The transmission cost and message delay performances of LPDB lie between those of the other two schemes. As the forwarding cone angle (controlled by 5, as shown in Figure 33) increases, LPDB's performance gets closer to that of LAR. Smaller value of 5 leads the performance of LPDB closer to that of LPSP.

(a) Message Delivery Ratio.

(b) Message Transmission Cost.

(c) Message Delay.

Figure 36: Performance Comparison of LPDB with LAR and LPSP.

In summary, our LPDB scheme balances between reliability and redundancy, as well as between delay and transmission cost. Depending on the application requirements and power availability, AR nodes can change the forwarding cone angle by the adjustment of value 5, thus to control the message delivery performance.

6.5.1.2   SBR-e for Controlled Data Delivery
Earth-controlled delivery of data messages from the planetary exploration site usually contains large amounts of unprocessed scientific data. These data messages are much larger and require higher reliability than control messages and automatic data reports. Our proposed receiver-initiated on-demand routing (RIOR) tends to minimize the

122

utilization of bandwidth, energy, and buffer size by maintaining route states at the AR nodes. Furthermore, updating of route information during the data delivery process provides higher end-to-end reliability. In RIOR, data messages are transferred in a store-and-forward manner. Different from LPDB, if an AR node cannot receive an acknowledgment from the next-hop AR after K consecutive retransmissions, a link failure is detected and no further retransmission attempt will be conducted.
We compare our RIOR scheme with LPDB proposed for remote control and automatic data delivery. Same as in Section 6.5.1.1, the following metrics are selected to compare their performance: message delivery ratio, message transmission cost, and message delay, where the message transmission cost measures the total data transmissions on delivery path for each successful message delivery. In our simulation, Trreq = 1 hour, TKA = 10 minutes, and K = 3. Data messages are sent from node 7 (orbit radius = 8AU) to node 0 (orbit radius = 1AU). The maximum life time for data messages is 10 hours. No multipath forwarding is utilized in RIOR, i.e., a data message is forwarded to a single next-hop AR. The simulation results are shown in Figure 37. The parameter 5 in LPDB controls the width of the forwarding cone, whereas 5 in RIOR controls the forwarding cone of RREQ messages. The parameter 5 does not affect much the performance of RIOR.
Figure 37(a) depicts the message delivery ratio of the two protocols under different link failure probabilities. RIOR always keeps the delivery ratio higher than 90%, even when the link failure probability becomes as high as 0.6. Compared with RIOR, LPDB is less reliable especially when the link failure probability is high. This is because LPDB does not provide any route repair under link failure. When the transmission cost is concerned, RIOR costs much less data overhead, which is around 30% to 50% of those of LPDB with 5 = 60° and 30°, respectively. This is because data message in RIOR is transmitted over a single-path, which is discovered and maintained by the route discovery and repair procedures. In the LPDB scheme, however, data message

(a) Message Delivery Ratio.

(b) Message Transmission Cost.

(c) Message Delay. Figure 37: Performance Comparison of RIOR with LPDB.
is delivered in a multicast tree (although in a controlled manner), much higher data overhead is produced as seen in Figure 37(b). Note that the transmission cost of the LPDB scheme dose not show consistent growth as the link failure probability (p) increases. When p grows beyond 0.4, the success ratio of message delivery starts to decrease fast, more messages get delayed or lost early on the delivery path, only "lucky" ones make their way to the destination. As the result, the average message transmission cost for the successful end-to-end deliveries is lower compared to the cases when the link failure probability is smaller. As a benefit of the multipath transfer, LPDB results in lower message delay than RIOR as in Figure 37(c), thus is more suitable for messages that require fast delivery.

124

We also conducted simulations and compared RIOR with other on-demand ad hoc routing protocols, such as DSR [45] and AODV [56]. It is obvious that they cannot compete with RIOR since they are not specifically proposed for the IPN Internet application scenario and the unique characteristics of the IPN Internet would dramatically impair their performances. For example, DSR [45] attempt to find a complete route before the actual data transmission takes place. The characteristics (e.g., delay and connectivity) of the discovered route in the IPN Internet, however, are under constant changes during the data delivery process. We do not list the results of the comparison here because of unfairness.
In summary, RIOR achieves higher data delivery reliability when there is no strict time constraint on the message content (i.e., the delay can be tolerated); whereas LPDB provides fast delivery of messages with considerably smaller sizes and lower reliability requirements. Based on the different performance of LPDB and RIOR, we can utilize them in delivering different types of traffic in the IPN Internet, addressing their specific requirements as in Table 6, and reduce the effect of their disadvantages in each application scenario.

6.5.2   Evaluation of SBR-interior Policies
The evaluation of SBR-i is done by modeling the contact allocation and traffic dispatching processes in a single AR, which has N backbone nodes and M possible AR neighbors. To simplify the evaluation, it is assumed that these N backbone nodes have the same reachability pattern towards the AR neighbors, i.e., the binary reachability variable towards an AR neighbor v satisfies Riv(t) = Rjv(t) = Rv(t), E Bx, where t specifies any timeslot. To differentiate among the backbone nodes, however, the start and finish time of the same reachability period at different backbone nodes are set differently. Specifically, the reachability pattern and the associated time intervals are generated as follows: First, in each timeslot, randomly decide the neighbor

reachability which is designated by 1 or 0. Then, based on the generated binary reachability sequences for the whole evaluation period, e.g., (110010111), each backbone node randomly selects the start and finish time (within a timeslot) of every reachable period marked by consecutive 1's. The generated reachability schedule should guarantee that there is no blackout gap between two consecutive 1's.
Four combinations of contact allocation and traffic dispatching policies are evaluated:
 •	LQ+MW: Our proposed longest queues (LQ) policy combined with our minimum waiting (MW) policy, which are explained in Section 6.4.2. The calculation of expected waiting time is based on the following information: the contact schedule in the current timeslot, current queue lengths at each backbone node (assuming first-in-first-out scheduling), and the reachability schedules of all backbone nodes.
 •	LQ only: The LQ policy with random traffic dispatching, i.e., incoming messages randomly choose one of the N backbone nodes as the egress router.
 •	MW only: Random contact allocation with the MW policy, i.e., the allocation of contacts in the current timeslot is only based on the knowledge of the reachability schedule, while the queue lengths at the backbone nodes are ignored. The contact to a certain AR neighbor v is randomly allocated to a backbone node if the reachability variable Rv(t) at the current timeslot t is 1.
 •	Random: Random contact allocation and random traffic dispatching without considering any queuing information.
In our simulations, messages are of the same fixed length and the message arrival process is Poisson with an arrival rate of A. A message randomly chooses one of the M AR neighbors as its next-hop. The message transmission rate fi is fixed. The

parameters used in the simulation are: N = 3, M = 5, Tsiot = 10 timeunit, fi =1 mes-sage/timeunit. The queue limit for each AR neighbor at backbone nodes is set as 10 messages. If a message finds that the queue at the egress router towards the next-hop AR neighbor exceeds the queue limit, this message is dropped due to buffer overflow. We evaluate the performance of the above four combinations of SBR-i policies under different values of message arrival rate (A). The performance metrics under evaluation are message buffering delay, message throughput, and message dropping probability.
Figure 38(a) shows the delay performance of the four policy combinations. If we ignore the queuing delay and remove the restrictions on the transmission on AR links, i.e., a backbone node can transmit to different AR neighbors, and different backbone nodes can transmit to the same AR neighbor at the same time, then an incoming message can be transmitted at the earliest time that its next-hop AR neighbor becomes reachable to a backbone node. This time is written as the "minimum transmit bound". The depicted "message buffering delay" in the figure is the difference between the actual message transmit time and this minimum transmit bound. It accounts for the portion of the message delay that is caused solely by the contact allocation and traffic dispatching. From this figure, it can be seen that as the message arrival rate increases, i.e., the average message arrival interval decreases, messages are buffered for a longer period of time. Our proposed "LQ+MW" policy causes minimum buffering delay among the four combinations. When only LQ or MW policy is implemented, the message buffering delay is also reduced compared to that under the random case.
The message throughput performance is shown in Figure 38(b), which also confirms that the "LQ+MW" policy achieves higher message throughput. The message dropping probability due to buffer overflow is shown in Figure 39, where the queue limit is set as 10 messages. The dropping of messages starts when the message arrival interval decreases below 2 messages/unit. The "LQ+MW" and "LQ only" policies

(a) Message Buffering Delay.

(b) Message Throughput.

(c) Message Dropping Probability. Figure 38: Performance Comparison of Different SBR-i Policies.

Figure 39: Message Dropping Probability under Different Queue Limit.

128

cause less message dropping than the other two policies. When we set the average message arrival interval as 5 timeunits, and change the queue limit, the message dropping probability of the "LQ+MW" policy is the lowest when the queue limit decreases, as depicted in Figure 39. It can also be concluded from this figure that the message dropping can be effectively controlled by increasing the queue limit at backbone nodes. This is easy to achieve by employing large intermediate storage at backbone nodes.
In summary, the combination of LQ and MW policies achieves low message buffering delay, high message throughput, and low message dropping probability under contact allocation and traffic dispatching.

CHAPTER VII

CONCLUSIONS AND FUTURE RESEARCH
DIRECTIONS

7.1   Research Contributions
In this thesis, new advanced routing protocols have been developed for satellite and space networks to support applications with different traffic types and heterogeneous QoS requirements. Research contributions have been made in the following areas:
 1.	Connection-oriented routing in multimedia satellite networks.
 2.	Connectionless routing in hierarchical satellite IP networks.
 3.	Integration of satellite IP networks and the terrestrial Internet.
 4.	Routing in the Interplanetary Internet.

7.1.1   Connection-Oriented Routing in Multimedia Satellite Networks
Real-time multimedia applications impose strict delay bounds and are sensitive to delay variations. The constant movement of non-GEO satellites causes the network connectivity varying. Satellite link handover increases delay jitter and signaling overhead as well as the termination probability of ongoing connections. To satisfy the QoS requirements of multimedia applications, satellite routing protocols should consider link handovers and minimize their effect on the active connections.
In Chapter 3, a new QoS-based routing algorithm (QRA) is proposed to support real-time applications in multimedia satellite networks. Real-time applications have strict requirements on bandwidth and delay variations. QRA aims to reduce the number of rerouting attempts because of satellite link handovers and to build stable paths

for connection requests, thus reducing delay jitter while guaranteeing bandwidth requirements. QRA can operate on a general satellite constellation model in which satellite footprints may be overlapped. The deterministic UDL routing based on the maximum coverage time together with the probabilistic ISL routing are introduced for routing between two ground stations via satellite networks. A rerouting algorithm is called when link handover occurs. QRA utilizes the satellite trajectory information and the connection statistics to reduce the link handover probability while satisfying users' bandwidth requirements. Simulation results show that QRA results in small delay jitter, low rerouting frequency, and low rerouting processing overhead.

7.1.2   Connectionless Routing in Hierarchical Satellite IP Networks
The rapid growth of Internet-based applications pushes broadband satellite networks to carry on IP traffic. In previously proposed connectionless routing schemes in satellite networks, the metrics used to calculate the paths do not reflect the total delay a packet may experience.
In Chapter 4, a new satellite grouping and routing protocol (SGRP) that operates in a hierarchical LEO/MEO satellite architecture is proposed. In SGRP, data traffic is carried by the LEO satellite network and the collaboration between LEO and MEO satellite layers is enabled. The main idea of SGRP is to transmit packets in minimum-delay paths and distribute the routing table calculation of the LEO satellites to multiple MEO satellites. In each snapshot period, SGRP divides the LEO satellites into dynamic groups according to the footprint areas of the MEO satellites. Based on the delay reports sent by the LEO satellites, the MEO satellite managers compute the minimum-delay paths for their LEO members. Since the signaling traffic is physically separated from the data traffic, link congestion does not affect the responsiveness of delay reporting and routing table calculation. The snapshot and group formation methods as well as fast reacting mechanisms to address link congestion and satellite

failures are described in detail.
The performance of SGRP is evaluated through simulations and analysis. SGRP performs better than datagram routing algorithm as it tries to route data packets through minimum-delay paths. When satellite failures or link congestion occur, SGRP has mechanisms to reduce their effects on routing. It is also shown by analysis that SGRP calculates the routing decisions with low communication overhead, since it distributes the computational burden to multiple MEO satellites, thus balances the power consumption between LEO and MEO satellites.

7.1.3   Integration of Satellite IP Networks and the Terrestrial Internet
The use of the IP-based satellite networks as a part of the Internet cannot be accomplished only by solving the routing problem of the satellite networks. To accomplish network layer integration of terrestrial and satellite IP networks, special exterior gateway protocols are needed. Moreover, the integration of the IP-based satellite networks must assure their interoperability with the terrestrial IP networks. Previously, satellite network integration issues have been pointed out in [42, 52, 74]. However, none of these studies provides a detailed solution as how this network level integration can be accomplished.
In Chapter 5, the border gateway protocol - satellite version (BGP-S) is proposed as a novel protocol to accomplish the integration of terrestrial and satellite IP networks at the network layer. The BGP-S protocol does not require a special satellite network architecture and works independent of the internal routing of the satellite network. BGP-S elimiates the need for manual configuration and enables the automated path discovery based on the instantaneous delay measurements in the satellite and terrestrial networks. BGP-S is fully compatible with the BGP-4 protocol. Moreover, BGP-S is implemented only in one terrestrial gateway in every terrestrial AS to reduce the complexity. The functionalities of the BGP speakers in the terrestrial

ASs remain the same.
The performance of BGP-S has been assessed with simulations. The results show that BGP-S always produces lower delays than BGP-4 in the integrated terrestrial/satellite network. When satellite altitude increases or satellite number decreases, the performance gain of BGP-S over BGP-4 grows. The effect of terrestrial gateway selection method on BGP-S performance is also evaluated.

7.1.4   Routing in the Interplanetary Internet
The characteristics of the IPN Internet are unique to the space communication paradigm and lead to different research approaches from those in terrestrial networks.
In Chapter 6, a novel routing framework called space backbone routing (SBR) is proposed based on the hierarchical architecture and specifically addresses the challenges of the IPN Internet. SBR has two integral parts: SBR-external and SBR-interior. To address the challenges in deep-space communication environment and meet the application requirements, location-predicted directional broadcast (LPDB) and receiver-initiated on-demand routing (RIOR) are proposed for remote control and data delivery in the realm of SBR-external. The simulation results show that LPDB and RIOR address the service requirements of different types of traffic, and are efficient both in message delivery and power consumption. For contact allocation and traffic dispatching, which are two important functionalities of SBR-interior, we give the problem definition and further propose two simple policies: the longest queues (LQ) policy and the minimum waiting (MW) policy, respectively. The simulation results show that a combination of proposed LQ and MW policies achieves good delay and throughput performances.

7.2   Future Research Directions

• Integration of Wireless/Wired Networks: Wireless devices are becoming

powerful tools to allow information access from anywhere at anytime, especially after the interconnection across networks. This evolution has motivated the integration of wireless/wired networks and the seamless migration of services between them. This integration can help extend network connections at a low cost and relieve congestion over the wired network. Wireless networks, however, have strict power constraints and comparatively low bandwidth, which make it hard to ensure QoS requirements such as bandwidth and delay. Thus, designing protocols that are both adaptive and secure is urgent and challenging. Future trends include constructing efficient infrastructure with wireless access enhancement and developing fast and secure schemes for roaming between subnet boundaries.
 •	Routing in Planetary Networks: The routing in planetary networks is a necessary part to achieve end-to-end communication between Earth and outer-space planets. Planetary networks face challenges of intermittent connectivity and power constraints. Furthermore, planetary networks have to be autonomous and reconfigurable [18] to maintain the network connectivity despite the extreme environmental challenges. The performance of the existing ad hoc routing protocols [27] depends on node density and network connectivity. In outer-space planets, frequent power failure and node damage may cause frequent network partitioning that will significantly affect the performance of these protocols. Moreover, according to the mission objectives, planetary surface networks may be divided into several physically disconnected sub-networks. Hence, planetary satellite network should assist surface communications and node reconfigurations to help resume the connection between partitioned parts of a network or between distant networks.
 •	End-to-end Routing Issues in the IPN Internet: Possible solutions to

support end-to-end routing in the IPN Internet include developing a universal addressing scheme. The new scheme should support the following functions: Locating the elements in a hierarchical way in the IPN Internet architecture to support efficient routing through different subnetworks; Allocating addresses dynamically under node movement, node device depletion, and new device deployment; Allowing the IPN Internet to expand while maintaining the addressability of previously-deployed elements.
• Routing in Delay Tolerant Networks: Delay tolerant networks (DTNs) [4] are characterized by the lack of consistent infrastructures, interruption of communication links, and network heterogeneity. Example application scenarios of DTNs are deep-space networks, military battlefields, underwater communication, and some forms of ad hoc sensor/actor networks. The challenges of communication in such networks may include large delay resulting from physical link properties or extended periods of network partitioning, routing efficiently with frequently disconnected, pre-scheduled, or opportunistic link availability, high link error rates, heterogeneous underlying network technologies, and lack of end-to-end negotiation. New protocols are needed to support routing in DTNs.

REFERENCES

[1] "BRITE: Boston university Representative Internet Topology gEnerator." http://www.cs.bu.edu/brite/index.html.
[2] "Chronology	of        Lunar	and	Planetary	Exploration."
http://nssdc.gsfc.nasa.gov/planetary/chrono.html. The National Space Science
Data Center (NSSDC), NASA Goddard Space Flight Center.
[3]	"Coordinated Universal Time." http://www.ghcc.msfc.nasa.gov/utc.html.
[4]	"Delay Tolerant Networking Research Group." http://www.dtnrg.org.
[5]	"Kepler's Third Law." http://www-istp.gsfc.nasa.gov/stargaze/Skepl3rd.htm.
[6]	"SpaceNuclearPowerSystems." http://www.ne.doe.gov/space/space-desc.html.
[7] "Telcordia NetSizer, Internet Hosts Distribution by Continent in January 2001." http://www.infometre.cefrio.qc.ca/fiches/fiche275.asp.
[8] "The NASA Deep Space Network (DSN)." http://deepspace.jpl.nasa.gov/dsn/.

[9] "The Network Simulator (ns), version 2.1b9a ." http://www.isi.edu/nsnam/ns/.
[10] "Space Communications Protocol Specification (SCPS) - Network Protocol (SCPS-NP)."  Draft Recommendation for Space Data Systems Standards,
CCSDS 713.0-B-1.Blue Book, May 1999.
[11] Akyildiz, I. F., Aran, O. B., Chen, C., Fang, J., and Su, W., "InterPlaNetary Internet: State-of-the-Art and Research Challenges," Computer Networks Journal (Elsevier), vol. 43, pp. 75-112, Oct. 2003.
[12] Akyildiz, I. F., Aran, O. B., Chen, C., Fang, J., and Su, W., "The State of the Art in Interplanetary Internet," IEEE Communications Magazine, vol. 42,
pp. 108-118, July 2004.
[13] Akyildiz, I. F., Ekici, E., and Bender, M. D., "MLSR: A Novel Routing Algorithm for Multi-Layered Satellite IP Networks," IEEE/ACM Transaction on Networking, vol. 10, pp. 411-424, June 2002.
[14] Akyildiz, I. F. and Jeong, S., "Satellite ATM Networks: A Survey," IEEE Communications Magazine, vol. 35, pp. 30-44, July 1997.
[15] Akyildiz, I. F., Uzunalioglu, H., and Bender, M. D., "Handover Management in Low Earth Orbit (LEO) Satellite Network," ACM-Baltzer Journal
of Mobile Networks and Applications (MONET), vol. 4, pp. 301-310, Dec. 1999.

[16] Barabasi, A. L. and Albert, R., "Emergence of Scaling in Random Networks," Science, vol. 401, pp. 509-512, Oct. 1999.
[17] Basagni, S., Chlamtac, I., Syrotiuk, R., and Woodward, B., "A Distance Routing Effect Algorithm for Mobility (DREAM)," in Proceedings of 4th annual ACM/IEEE International Conference on Mobile Computing and Networking (MOBICOM'98), (Dallas, TX), pp. 76-84, Oct. 1998.
[18] Bhasin, K. and Hayden, J. L., "Space Internet Architecture and Technologies for NASA Enterprises," International Journal of Satellite Communications, vol. 20, pp. 311-332, 2002.
[19] Burleigh, S., Hooke, A., Torgerson, L., Fall, K., Cerf, V., Durst, B., and Scott, K., "Delay-Tolerant Networking: An Approach to Interplanetary Internet," IEEE Communications Magazine, vol. 41, pp. 128-136, June 2003.
[20] Cerf, V., Burleigh, S., Hooke, A., Burst, R., Scott, K., Travis, E., and Weiss, H., "Interplanetary Internet (IPN): Architectural Definition," Internet draft, draft-irtf-ipnrg-arch-00.txt, May 2001.
[21] Cesarone, R. J., Hastrup, R. C., Bell, D. J., Lyons, D. T., and Nelson, K. G., "Architectural Design for a Mars Communications and Navigation Orbital Infrastructure." paper presented at the AAS/AIAA Astrodynamics Specialist Conference, Aug. 1999.
[22] Chang, H. S., Kim, B. W., Lee, C. G., Min, S. L., Choi, Y., Yang, H. S., Kim, D. N.,and Kim, C. S., "FSA-Based Link Assignment and Routing in Low-Earth Orbit Satellite Networks," IEEE Transactions on Vehicular Technology,
vol. 47, pp. 1037-1048, Aug. 1998.
[23] Chen, C., "A Routing Framework for Interplanetary Internet," to appear in Computer Networks Journal (Elsevier).
[24] Chen, C., "A QoS-based Routing Algorithm in Multimedia Satellite Networks," in Proceedings of IEEE 58th Vehicular Technology Conference (VTC2003-Fall),
vol. 4, (Orlando, Florida), pp. 2703-2707, Oct. 2003.
[25] Chen, C. and Ekici, E., "A Routing Protocol for Hierarchical LEO/MEO Satellite IP Networks," to appear in ACM/Kluwer Wireless Networks Journal (WINET).
[26] Chen, C., Ekici, E., and Akyildiz, I. F., "Satellite Grouping and Routing Protocol for LEO/MEO Satellite IP Networks," in Proceedings of the 5th ACM International Workshop on Wireless Mobile Multimedia (WoWMoM '02),
pp. 109-116, Sept. 2002.
[27] Chlamtac, I., Conti, M., and Liu, J. J.-N., "Mobile Ad Hoc Networking: Imperatives and Challenges," Ad Hoc Networks, vol. 1, pp. 13-64, July 2003.

[28] Durst, R. C., "Delay-Tolerant Networking: An Example Interplanetary Internet Bundle Transfer," Internet Draft, draft-irtf-dtnrg-ipn-bundle-xfer-01.txt, Oct.
2003.
[29] Durst,   R.   C.,   Feighery,   P.   D.,   and	Scott,   K.   L.,   "Why
not Use the Standard Internet Suite for the	Interplanetary Internet?."
http://www.ipnsig.org/reports/TCPIP.pdf.
[30] Ekici, E., Akyildiz, I. F., and Bender, M. D., "A Distributed Routing Algorithm for Datagram Traffic in LEO Satellite Networks," IEEE/ACM Transaction on Networking, vol. 9, pp. 137-147, Apr. 2001.
[31] Ekici, E., Akyildiz, I. F., and Bender, M. D., "Network Layer Integration of Terrestrial and Satellite IP Networks over BGP-S," in Proceedings of IEEE GLOBECOM 2001, (San Antonio, TX), pp. 2698-2702, Nov. 2001.
[32] Ekici, E. and Chen, C., "BGP-S: A Protocol for Terrestrial and Satellite Network Integration in Network Layer," ACM/Kluwer Wireless Networks Journal,
vol. 10, pp. 595-605, Sept. 2004.

[33] Elbert, B. R., The Satellite Communication Applications Handbook, ch. 8,9,
pp. 287-365. Artech House, Inc., 2 ed., 2004.
[34] Ely, T. A., Anderson, R., Bar-Server, Y. E., Bell, D., Guinn, J., Jah, M., Kallemeyn, P., Levene, E., Romans, L., and Wu, S.-C.,
"Mars Network Constellation Design Drivers and Strategies." paper presented at AAS/AIAA Astrodynamics Specialist Conference, Aug. 1999.
[35] Ercetin, O., Krishnamurthy, S., Dao, S., and Tassiulas, L., "Provision of Guaranteed Services in Broadband LEO Satellite Networks," Computer Networks Journal (Elsevier), vol. 39, pp. 61-77, May 2002.
[36] Faloutsos, M., Faloutsos, P., and Faloutsos, C., "On Power-Law Relationships of the Internet Topology," Computer Communication Review, vol. 29,
pp. 251-262, Sept. 1999.
[37] Ghedia, L., Smith, K., and Titzer, G., "Satellite PCN - The ICO System," International Journal ofSatellite Communications, vol. 17, pp. 273-289,
July/Aug. 1999.
[38] Hashimoto, Y. and Sarikaya, B., "Design of IP-based Routing in a LEO Satellite Network," in Proceedings of 3rd ACM/IEEE International Workshop on Satellite-based Information Services (WOSBIS 98), (Dallas, TX), pp. 81-88,
Oct. 1998.
[39] Hastrup, R. C., Cesarone, R. J., Srinivasan, J. M., and Morabito, D. D., "Mars Comm/Nav MicroSat Network." paper presented at the 13th AIAA/USU Conference on Small Satellites, Aug. 1999.

[40] Henderson, T. R. and Katz, R. H., "On Distributed, Geographic-based Packet Routing for LEO Satellite Networks," in Proceedings ofIEEE GLOBE-
COM 2000, vol. 2, (San Francisco, CA), pp. 1119-1123, Dec. 2000.
[41] Hu, J. H. and Yeung, K. L., "Routing and Re-routing in a LEO/MEO Two-Tier Mobile Satellite Communications System with Inter-Satellite Links," in Proceedings ofIEEE International Conference on Communications (ICC 2000),
vol. 1, (New Orleans, LA), pp. 134-138, June 2000.
[42] Hu, Y. and Li, V. O. K., "Satellite-based Internet: A Tutorial," IEEE Communications Magazine, vol. 39, pp. 154-162, Mar. 2001.
[43] Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J., and Silva, F., "Directed Diffusion for Wireless Sensor Networking," IEEE/ACM Transactions on Networking, vol. 11, pp. 2-16, Feb. 2003.
[44] Jain, S., Fall, K., and Patra, R., "Routing in a Delay Tolerant Network," in Proceedings of ACM SIGCOMM 2004, (Portland, OR), pp. 145-158, Sept. 2004.
[45] Johnson, D. B. and Maltz, D. A., Dynamic Source Routing in Ad-hoc Wireless Networks, ch. 5, pp. 153-181. Dordrecht: Kluwer Adademic Publishers, 1996. in "Mobile Computing", Edited by T. Imielinski and H. Korth.
[46] Kerschenbaum, A., Telecommunications Network Design Algorithms. New York: McGraw-Hill, 1993.
[47] Ko, Y.-B. and Vaidya, N. H., "Location-Aided Routing (LAR) in Mobile Ad hoc Networks," ACM/Kluwer Wireless Networks, vol. 6, pp. 307-321, July 2000.
[48] Lee, J. and Kang, S., "Satellite over Satellite (SOS) Network: A Novel Architecture for Satellite Network," in Proceedings of IEEE INFOCOM'2000, vol. 1,
(Tel Aviv, Israel), pp. 315-321, Mar. 2000.
[49] Leopold, R. J. and Miller, A., "The Iridium Communication System," IEEE Potentials, vol. 12, pp. 6-9, Apr. 1993.
[50] Lo, M. W., "Satellite Constellation Design," Computing in Science and Engineering, vol. 1, pp. 58-67, Jan.-Feb. 1999.
[51] Maral, G. and Bousquet, M., Satellite Communication Systems, ch. 7. J. Wiley & Sons, 3 ed., 1998.
[52] Narvaez, P., Clerget, A., and Dabbous, W., "Internet Routing over LEO Satellite Constellations," in Proceedings of3rd ACM/IEEE International Workshop on Satellite-based Information Services (WOSBIS 98), (Dallas, TX),
pp. 89-95, Oct. 1998.
[53] Oman, H., "Deep Space Travel Energy Sources," IEEE Aerospace and Electronics Systems Magazine, vol. 18, pp. 28-35, Feb. 2003.

[54] Orda, A. and Rom, R., "Shortest-path and Minimum-delay Algorithms in Networks with Time-dependent Edge-length," Journal ofthe ACM, vol. 37, pp. 607625, July 1990.
[55] Perdigues, J., Werner, M., and Karafolas, N., "Methodology for Traffic Analysis and ISL Capacity Dimensioning in Broadband Satellite Constellations Using Optical WDM Networking," in Proceedings of 19th AIAA International Communication Satellite Systems Conference (ICSSC 01), (Toulouse, France),
Apr. 2001.
[56] Perkins, C. E. and Royer, E. M., "Ad hoc On-demand Distance Vector Routing," in Proceedings of2nd IEEE workshop on Mobile Computing Systems and Applications, (New Orleans, LA), pp. 90-100, Feb. 1999.

[57] Rekhter, Y. and Li, T., "A Border Gateway Protocol (BGP-4)," RFC 1771,
Mar. 1995.
[58] Scott, K. and Burleigh, S., "Bundle Protocol Specification." Internet Draft, draft-irtf-dtnrg-bundle-spec-02.txt, July 2004.
[59] Stern, D. P., "From Stargazers to Starships - (34b) The L4 and L5 Lagrangian Points." http://www-spof.gsfc.nasa.gov/stargaze/Slagrang2.htm.
[60] Stewart, J. W., BGP-4: Inter-Domain Routing in the Internet. Addison-Wesley Publishers Company, 1999.
[61] Sturza, M. A., "Architecture of Teledesic Satellite System," in Proceedings of the 4th International Mobile Satellite Conference (IMSC 95), (Ottawa, Canada),
pp. 212-218, June 1995.

[62] Tanenbaum, A., Computer Networks. Pretence Hall, Inc., 3 ed., 1996.
[63] Travis, E., "The Interplanetary Internet: Architecture and Key Technical Concepts." paper presented at the Internet Global Summit, INET 2001, June 2001.
[64] Uzunalioglu, H., Akyildiz, I. F., and Bender, M. D., "A Routing Algorithm for Connection-Oriented Low Earth Orbit (LEO) Satellite Network with Dynamic Connectivity," ACM-Baltzer Journal ofWireless Networks (WINET),
vol. 6, pp. 181-190, June 2000.
[65] Uzunalioglu, H., Akyildiz, I. F., Yesha, Y., and Yen, W., "Footprint Handover Rerouting Protocol for LEO Satellite Networks," ACM-Baltzer Journal
ofWireless Networks (WINET), vol. 5, pp. 327-337, Nov. 1999.
[66] Voilet, M. D., "The Development and Application of a Cost per Minute Metric of the Evaluation of Mobile Satellite Systems in a Limited-Growth Voice Communications Market," Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, Department of Aeronautics and Astronautics, Sept. 1995. http://theses.mit.edu/Dienst/UI/2.0/Describe/0018.mit.theses%2f1995-189.

[67] Wang, C. J., "Structural Properties of a Low Earth Orbit Satellite Constellation - the Walker Delta Network," in Proceedings ofMilitary Communications Conference (MILCOM'93), vol. 3, (Boston, MA), pp. 968-972, Oct. 1993.
[68] Waxman, B. M., "Routing of Multipoint Connections," IEEE Journal of Selected Areas in Communication (JSAC), vol. 6, pp. 1617-1622, Dec. 1988.
[69] Werner, M., "A Dynamic Routing Concept for ATM-based Satellite Personal Communication Networks," IEEE Journal on Selected Areas in Communications
(JSAC), vol. 15, pp. 1636-1648, Oct. 1997.
[70] Werner, W., Berndl, G., and Edmaier, B., "Performance of Optimized Routing in LEO Intersatellite Link Networks," in Proceedings of IEEE 47th Vehicular Technology Conference (VTC'97), vol. 1, (Phoenix, AZ), pp. 246-250,
May 1997.
[71] Werner, W., Jahn, A., Lutz, E., and Bottcher, A., "Analysis of System Parameters for LEO/ICO-Satellite Communication Networks," IEEE Journal on Selected Areas in Communications, vol. 13, pp. 371-381, Feb. 1995.
[72] Wiedeman, R. A. and Viterbi, A. J., "The Globalstar Mobile Satellite System for Worldwide Personal Communications," in Proceedings ofthe 3rd International Mobile Satelite Conference (IMSC 93), (Pasadena, CA), pp. 291-296,
June 1993.
[73] Wood, L., Internetworking with Satellite Constellations. PhD thesis, University of Surrey, June 2001.
[74] Wood, L., Clerget, A., Andrikopoulos, I., Pavlou, G., and Dabbous, W. , "IP Routing Issues in Satellite Constellation Networks," International Journal ofSatellite Communications, vol. 19, pp. 69-92, Jan./Feb. 2001.

VITA

Chao Chen was born in Changsha, Hunan, P. R. China in May 1976. She received the Bachelor of Engineering degree and the Master of Engineering degree in Electronic Engineering from Shanghai Jiao Tong University, Shanghai, China, in 1998 and 2001, respectively. She attended the doctoral program in the School of Electrical and Computer Engineering at the Georgia Insitute of Technology, Atlanta, GA, from May 2001 to August 2005. At the same time, she was a graduate research assitant in the Broadband and Wireless Networking Laboratory (BWN-LAB) at the Georgia Institute of Technology. She received the Master of Science degree and the Doctor of Philosophy degree in December 2003 and August 2005, respectively, in Electrical and Computer Engineering from the Georgia Institute of Technology.