본 명세서에서 개시되는 실시예들은 불균형한 트래픽 분포로 인해 위성에 작용하는 과부하를 분산시키는 위성 라우팅 장치 및 그것의 분산형 라우팅 방법에 관한 것이다.Embodiments disclosed herein relate to a satellite routing device and a distributed routing method thereof for distributing overload acting on a satellite due to unbalanced traffic distribution.
저궤도(LEO: Low earth orbit) 위성 네트워크란 통상의 정지 위성 궤도인 36,000km 보다 낮은 상공인 700~2,000km 안팎에 다수의 저궤도 위성을 배치하고, 지상에서 유저 단말(UE, User Equipment)과 통신함으로써 전 세계 어디서나 이동통신 서비스를 받을 수 있는 네트워크 시스템을 의미한다. 저궤도 위성 네트워크는 넓은 커버리지를 지원하며 고속의 통신 속도를 획득할 수 있는 종래의 지상 네트워크 기술의 대안 기술에 해당하며, 동시에 다양한 국가 차원에서 그리고 기업들이 앞다투어 연구개발을 진행하고 있는 차세대 네트워크 기술이다. 이러한, 저궤도 위성 네트워크는 지상 네트워크 인프라가 부족한 오지, 산간 및, 해양 등에 다중 홉 라우팅(multi-hop routing)을 통해 통신 서비스를 제공할 수 있다.A low-earth orbit (LEO) satellite network is a network system that deploys multiple low-earth orbit satellites at an altitude of 700 to 2,000 km, lower than the standard geostationary satellite orbit of 36,000 km, and communicates with user equipment (UE) on the ground, thereby enabling mobile communication services anywhere in the world. LEO satellite networks are an alternative to conventional terrestrial network technologies that support wide coverage and high-speed communication speeds. At the same time, they are a next-generation network technology that various countries and companies are competing to research and develop. These LEO satellite networks can provide communication services through multi-hop routing to remote areas, mountainous regions, and oceans where terrestrial network infrastructure is lacking.
그러나, 저궤도 위성 네트워크는 인구 밀집 지역 등과 같은 지형적 특성으로 인한 위성들 각각에서 트래픽 분포의 불균형이 발생할 수 있다. 만약, 트래픽 분포가 밀집한 지역에 위치한 위성은 다른 위성과 통신하기 위한 링크, 즉 위성 간 링크(ISL: Inter-Satellite Link)의 과도한 사용으로 위성 자원 사용에 과부하를 초래할 수 있으며, 데이터 패킷의 손실을 초래하는 문제점이 있었다.However, low-orbit satellite networks can experience traffic imbalances among satellites due to geographic characteristics, such as densely populated areas. Satellites located in densely populated areas can overuse the inter-satellite link (ISL)—the link used to communicate with other satellites—which can lead to overloading satellite resources and data packet loss.
또한, 저궤도 위성 네트워크는 위성에서의 부하를 분산하기 위해 주기적으로 인접 위성들과 관련 정보를 포함한 데이터 패킷을 송수신한다. 이로 인해, 저궤도 위성 네트워크는 실제 데이터가 아닌 과부하 분산을 위한 네트워크 관리 정보를 송수신함에 따라 실제 데이터의 전송에 사용할 네트워크 자원을 낭비하게 되는 문제점이 있었다.Additionally, low-orbit satellite networks periodically transmit and receive data packets containing relevant information with neighboring satellites to distribute the load on the satellites. This resulted in the network wasting network resources that could otherwise be used for actual data transmission, as the network transmitted and received network management information for overload distribution rather than actual data.
한편, 전술한 배경기술은 발명자가 본 발명의 도출을 위해 보유하고 있었거나, 본 발명의 도출 과정에서 습득한 기술 정보로서, 반드시 본 발명의 출원 전에 일반 공중에게 공개된 공지기술이라 할 수는 없다.Meanwhile, the background technology described above is technical information that the inventor possessed for the purpose of deriving the present invention or acquired during the process of deriving the present invention, and cannot necessarily be said to be publicly known technology disclosed to the general public prior to the application for the present invention.
본 명세서에서 개시되는 실시예들은, 트래픽 분포가 밀집한 지역에 위치한 위성의 과부하를 분산할 수 있는 위성 라우팅 장치 및 그것의 분산형 라우팅 방법을 제공함에 있다.Embodiments disclosed in this specification provide a satellite routing device and a distributed routing method thereof capable of distributing overload of a satellite located in an area with dense traffic distribution.
본 명세서에서 개시되는 실시예들은, 위성의 과부하 분산을 위한 관련 정보의 전송을 최소화하는 위성 라우팅 장치 및 그것의 분산형 라우팅 방법을 제공함에 있다.Embodiments disclosed herein provide a satellite routing device and a distributed routing method thereof that minimize the transmission of related information for overload distribution of a satellite.
상술한 기술적 과제를 달성하기 위한 기술적 수단으로서, 일 실시예에 따르면, 위성 라우팅 장치는, 데이터 패킷을 송수신하는 위성 송수신기, 및 상기 데이터 패킷을 전송할 다음 위성을 결정하여 상기 데이터 패킷을 전송하는 위성 라우터를 포함하되, 상기 위성 라우터는, 예측된 트래픽 흐름에 따라 위성 간 링크에 가중치를 부여하여 위성의 라우팅 테이블을 생성하고, 상기 라우팅 테이블을 이용하여 상기 데이터 패킷을 전송할 다음 홉 방향의 버퍼 큐 상태를 확인하여 상기 데이터 패킷의 우회 여부를 결정한다.As a technical means for achieving the above-described technical task, according to one embodiment, a satellite routing device includes a satellite transceiver for transmitting and receiving a data packet, and a satellite router for determining a next satellite to transmit the data packet and transmitting the data packet, wherein the satellite router generates a routing table of the satellite by assigning weights to links between satellites according to a predicted traffic flow, and determines whether to bypass the data packet by checking a buffer queue status in a next hop direction to transmit the data packet using the routing table.
또 다른 실시예에 따르면, 위성 라우팅 장치의 분산형 라우팅 방법은, 위성 네트워크의 토폴로지 그래프를 생성하는 단계, 상기 위성 네트워크를 통해 전송될 트래픽 흐름을 예측하는 단계, 상기 토폴로지 그래프에서 위성 간 링크 각각에 대한 가중치를 상기 트래픽 흐름으로 계산된 위성 간 링크의 대기열 지연 시간으로 갱신하는 단계, 각 위성의 라우팅 테이블을 생성하는 단계, 데이터 패킷을 수신하면, 목적지 위성에 대한 최선의 다음 홉 위성(BH: Best next Hop satellite)과 차선의 다음 홉 위성(SBH: Second-Best next Hop satellite)을 확인하는 단계, 및 버퍼 큐의 점유율을 확인하여 상기 데이터 패킷을 전송할 다음 위성을 결정하여 데이터 패킷을 전송하는 단계를 포함한다.According to another embodiment, a distributed routing method of a satellite routing device includes the steps of: generating a topology graph of a satellite network; predicting a traffic flow to be transmitted through the satellite network; updating a weight for each inter-satellite link in the topology graph with a queue delay time of the inter-satellite link calculated from the traffic flow; generating a routing table for each satellite; when receiving a data packet, checking a best next hop satellite (BH) and a second-best next hop satellite (SBH) for a destination satellite; and checking an occupancy rate of a buffer queue to determine a next satellite to transmit the data packet, thereby transmitting the data packet.
전술한 과제 해결 수단 중 어느 하나에 의하면, 트래픽 분포가 밀집한 지역에 위치한 위성의 과부하를 분산할 수 있다.Any of the aforementioned problem solving methods can distribute the overload of satellites located in areas with dense traffic distribution.
전술한 과제 해결 수단 중 어느 하나에 의하면, 위성의 과부하 분산을 위한 관련 정보의 전송을 최소화할 수 있다.Any of the aforementioned problem solving methods can minimize the transmission of relevant information for satellite overload distribution.
전술한 과제 해결 수단 중 어느 하나에 의하면, 데이터 패킷의 종단 간 지연을 감소시키고, 데이터 패킷의 손실률을 최소화할 수 있다.Any one of the aforementioned problem solving means can reduce the end-to-end delay of data packets and minimize the loss rate of data packets.
본 발명에서 얻을 수 있는 효과는 이상에서 언급한 효과들로 제한되지 않으며, 언급하지 않은 또 다른 효과들은 아래의 기재로부터 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 명확하게 이해될 수 있을 것이다.The effects that can be obtained from the present invention are not limited to the effects mentioned above, and other effects not mentioned can be clearly understood by a person having ordinary skill in the art to which the present invention belongs from the description below.
도 1은 일 실시예에 따른 위성 시스템을 도시한 블록도이다.
도 2는 일 실시예에 따른 위성 성상도에 따른 네트워크 토폴로지 생성을 도시한 도면이다.
도 3은 일 실시예에 따른 위성 성상도를 위성간 링크로 연결한 네트워크 토폴로지로 도시한 도면이다.
도 4는 일 실시예에 따른 지표면 영역의 트래픽 분포 밀도 값을 도시한 도면이다.
도 5는 일 실시예에 따른 최선의 다음 홉 위성과 차선의 다음 홉 위성의 선정을 도시한 도면이다.
도 6은 일 실시예에 따른 라우팅 장치에서의 분산형 라우팅 동작을 도시한 순서도이다.
도 7은 일 실시예에 따른 패킷 생성률을 변화하며 목적지에 도착한 패킷의 평균 패킷 손실률을 도시한 그래프이다.
도 8은 일 실시예에 따른 패킷 생성률을 변화하며 패킷 데이터의 처리량을 도시한 그래프이다.
도 9는 일 실시예에 따른 패킷 생성률을 변화하며 패킷의 평균 종단 간 지연을 도시한 그래프이다.
도 10은 일 실시예에 따른 패킷 생성률을 변화하며 목적지에 도착한 평균 대기열 지연을 도시한 그래프이다.
도 11은 일 실시예에 따른 패킷 생성률을 변화하며 전체 패킷의 평균 종단 간 지연을 도시한 그래프이다.
도 12는 일 실시예에 따른 패킷 생성률을 변화하며 분산 인덱스를 도시한 그래프이다.
도 13은 일 실시예에 따른 세계의 주요 도시 간 패킷 흐름의 평균 종단 간 지연을 도시한 그래프이다.FIG. 1 is a block diagram illustrating a satellite system according to one embodiment.
FIG. 2 is a diagram illustrating the creation of a network topology according to a satellite constellation diagram according to one embodiment.
FIG. 3 is a diagram illustrating a network topology in which a satellite constellation is connected by an inter-satellite link according to one embodiment.
FIG. 4 is a diagram illustrating traffic distribution density values of a ground surface area according to one embodiment.
FIG. 5 is a diagram illustrating selection of a best next-hop satellite and a second-best next-hop satellite according to one embodiment.
FIG. 6 is a flowchart illustrating distributed routing operations in a routing device according to one embodiment.
FIG. 7 is a graph showing the average packet loss rate of packets arriving at a destination while changing the packet generation rate according to one embodiment.
FIG. 8 is a graph showing the processing amount of packet data while changing the packet generation rate according to one embodiment.
FIG. 9 is a graph showing the average end-to-end delay of packets as the packet generation rate changes according to one embodiment.
FIG. 10 is a graph showing the average queue delay at the destination as the packet generation rate changes according to one embodiment.
FIG. 11 is a graph showing the average end-to-end delay of all packets as the packet generation rate changes according to one embodiment.
FIG. 12 is a graph showing a distribution index while changing a packet generation rate according to one embodiment.
FIG. 13 is a graph illustrating the average end-to-end delay of packet flows between major cities around the world according to one embodiment.
아래에서는 첨부한 도면을 참조하여 다양한 실시예들을 상세히 설명한다. 아래에서 설명되는 실시예들은 여러 가지 상이한 형태로 변형되어 실시될 수도 있다. 실시예들의 특징을 보다 명확히 설명하기 위하여, 이하의 실시예들이 속하는 기술분야에서 통상의 지식을 가진 자에게 널리 알려져 있는 사항들에 관해서 자세한 설명은 생략하였다. 그리고, 도면에서 실시예들의 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다.Below, various embodiments are described in detail with reference to the attached drawings. The embodiments described below may be modified and implemented in various different forms. To more clearly explain the features of the embodiments, detailed descriptions of matters widely known to those skilled in the art to which the embodiments pertain below have been omitted. In addition, parts of the drawings that are not related to the description of the embodiments have been omitted, and similar parts have been designated with similar drawing reference numerals throughout the specification.
명세서 전체에서, 어떤 구성이 다른 구성과 "연결"되어 있다고 할 때, 이는 '직접적으로 연결'되어 있는 경우뿐 아니라, '그 중간에 다른 구성을 사이에 두고 연결'되어 있는 경우도 포함한다. 또한, 어떤 구성이 어떤 구성을 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한, 그 외 다른 구성을 제외하는 것이 아니라 다른 구성들을 더 포함할 수도 있음을 의미한다.Throughout the specification, when a component is said to be "connected" to another component, this includes not only the "direct connection" but also the "connection with other components in between." Furthermore, when a component is said to "include" another component, this does not exclude other components, but rather implies that other components may be included, unless otherwise specifically stated.
이하 첨부된 도면을 참고하여 실시예들을 설명하기에 앞서, 하기에서 설명될 용어를 간단히 설명하기로 한다.Before describing the embodiments with reference to the attached drawings below, the terms to be explained below will be briefly explained.
하기에서 설명되는 위성은 저궤도(LEO: Low earth orbit) 위성을 기준으로 섬명하지만, 저궤도 위성 이외의 다른 궤도에 위치한 위성을 포함할 수 있으며, 행성의 궤도 상에 위치한 다른 다양한 위성 또는 비행체들을 모두 포함할 수 있다. 또한, 위성은 라우팅 동작을 설명하기 위해 라우팅 경로 상에 존재하는 노드(node), 홉(hop), 또는 지점(point)의 용어로 대체되어 설명될 수도 있다.The satellites described below are based on low-earth orbit (LEO) satellites, but may include satellites in orbits other than LEO satellites, and may also include various other satellites or aircraft located in planetary orbits. Furthermore, satellites may be described using the terms node, hop, or point along a routing path to describe routing operations.
한편, 본 발명은 워커-스타 군집 모델(Walker-star constellation)의 저궤도 위성 네트워크를 기준으로 설명한다. 워커-스타 군집 모델의 위성은 주어진 경사도를 기반으로 궤도를 따라 이동하며, 이러한 궤도가 포함하고 있는 기하학적인 평면을 궤도 평면(orbit plane)이라 한다. 저궤도 위성 네트워크의 모든 위성은 복수의 궤도 평면 각각에서 동일한 궤도의 고도를 갖고, 동일한 궤도 평면 내의 위성들은 서로 균일한 간격으로 배치될 수 있다. 또한, 궤도 평면의 교차점에서 충돌이나 간섭을 피하기 위해서 인접 궤도의 위성 간 위상 차이가 존재한다.Meanwhile, the present invention is explained based on a low-orbit satellite network of the Walker-star constellation model. Satellites in the Walker-star constellation model move along orbits based on a given inclination, and the geometric plane contained in such orbits is called an orbital plane. All satellites in the low-orbit satellite network have the same orbital altitude in each of a plurality of orbital planes, and satellites within the same orbital plane can be arranged at equal intervals from each other. In addition, a phase difference exists between satellites in adjacent orbits to avoid collisions or interference at the intersection of orbital planes.
상술한 워커-스타 군집 모델의 저궤도 위성 네트워크는 설명의 편의를 위하여 설명한 것으로, 상술한 저궤도 위성 네트워크와 다른 다양한 형태의 위성 네트워크에도 제안된 분산형 라우팅 방식을 이용하여 고밀도 지역에서의 위성 간 링크의 과부하 분산을 위해 사용될 수 있다.The low-orbit satellite network of the Walker-Star constellation model described above is described for convenience of explanation, and the proposed distributed routing method can be used for various types of satellite networks other than the low-orbit satellite network described above to distribute overload of inter-satellite links in high-density areas.
이하 첨부된 도면을 참고하여 실시예들을 상세히 설명하기로 한다.The embodiments will be described in detail with reference to the attached drawings below.
도 1은 일 실시예에 따른 위성 시스템을 도시한 블록도이다.FIG. 1 is a block diagram illustrating a satellite system according to one embodiment.
도 1을 참조하면, 위성 시스템은 복수의 위성들(110, 120, 130)을 포함할 수 있다. 여기서, 위성들(110, 120, 130) 각각은 인접한 다른 위성들과 정보 교환을 위한 링크를 연결할 수 있으며, 지상에 있는 기지국들 또는 단말들과 통신할 수 있다.Referring to FIG. 1, a satellite system may include a plurality of satellites (110, 120, 130). Here, each of the satellites (110, 120, 130) may be connected to a link for information exchange with other adjacent satellites and may communicate with base stations or terminals on the ground.
제1 위성(110)은 메모리(111), 제어부(112), 및 송수신기(113)를 포함할 수 있다. 제2 위성(120)은 메모리(121), 제어부(122), 및 송수신기(123)를 포함할 수 있다. 또한, 제n 위성은 메모리(131), 제어부(132), 및 송수신기(133)를 포함할 수 있다.The first satellite (110) may include a memory (111), a control unit (112), and a transceiver (113). The second satellite (120) may include a memory (121), a control unit (122), and a transceiver (123). In addition, the n-th satellite may include a memory (131), a control unit (132), and a transceiver (133).
이와 같이, 제1 위성(110) 내지 제n 위성(130)은 지구 상의 일정 궤도 구간 내에서 서로 다른 상공에 배치되어 위치할 뿐 전반적으로 유사한 구조와 기능을 갖기 때문에 제1 위성(110)을 기준으로 간략히 설명한다.In this way, the first satellite (110) to the nth satellite (130) are positioned at different altitudes within a certain orbital section on the Earth, but have similar structures and functions overall, so they will be briefly described based on the first satellite (110).
메모리(111)에는 제1 위성(110)이 궤도를 따라 이동시키기 위한 구동 프로그램 등과 같이 위성의 운용을 위한 프로그램들이 저장될 수 있으며, 데이터 패킷의 송수신에 의해 송수신되는 데이터가 일시 저장될 수 있다.The memory (111) may store programs for operating the satellite, such as a driving program for moving the first satellite (110) along an orbit, and data transmitted and received by transmitting and receiving data packets may be temporarily stored.
제어부(112)는 위성의 전반적인 동작을 제어할 수 있으며, 메모리(111)에 저장된 데이터를 이용하여 위성의 동작을 제어하거나 송수신되는 데이터 패킷을 저장할 수도 있다.The control unit (112) can control the overall operation of the satellite, and can also control the operation of the satellite or store data packets transmitted and received using data stored in the memory (111).
송수신기(113)는 안테나에 연결되어 데이터 패킷을 송수신할 수 있다. 송수신기(113)는 안테나를 이용하여 타 위성, 지상의 기지국, 또는 지상의 단말 등과 통신할 수 있다.A transceiver (113) is connected to an antenna and can transmit and receive data packets. The transceiver (113) can communicate with other satellites, ground base stations, or ground terminals using the antenna.
제1 위성(110)은 상술한 메모리(111), 제어부(112), 송수신기(113) 외에도 전원부(미도시) 등과 같은 다른 구성 요소들을 추가로 포함할 수 있다.In addition to the above-described memory (111), control unit (112), and transmitter/receiver (113), the first satellite (110) may additionally include other components such as a power supply unit (not shown).
한편, 본 발명에서 제안하는 위성 라우팅 장치(100)는 위성 라우터(101)와 위성 송수신기(102)를 포함할 수 있다.Meanwhile, the satellite routing device (100) proposed in the present invention may include a satellite router (101) and a satellite transceiver (102).
위성 라우터(101)는 위성들 사이에 송수신되는 데이터 패킷의 라우팅을 수행할 수 있다. 이때, 위성 라우터(101)는 데이터 패킷의 전송 경로에 위치한 위성들 각각을 통해 라우팅되기 때문에, 복수의 위성들(110, 120, 130) 각각을 통해 구현될 수 있으며, 특히, 위성들 각각 내에 포함된 메모리들(111, 121, 131) 및/또는 제어부(112, 122, 132) 등을 이용하여 구현될 수 있다.A satellite router (101) can perform routing of data packets transmitted and received between satellites. At this time, since the satellite router (101) routes through each of the satellites located in the transmission path of the data packet, it can be implemented through each of a plurality of satellites (110, 120, 130), and in particular, it can be implemented using memories (111, 121, 131) and/or control units (112, 122, 132) included in each of the satellites.
위성 라우터(101)는 트래픽 흐름에 따라 위성과 위성을 연결하는 위성 간 링크(ISL: Inter-Satellite Link)에 가중치를 부여하여 위성의 라우팅 테이블을 생성할 수 있다. 또한, 위성 라우터(101)는 생성된 라우팅 테이블을 이용하여 데이터 패킷을 전송할 다음 홉, 즉 다음 위성 방향의 버퍼 큐 상태를 확인하여 데이터 패킷의 우회 여부를 결정하고, 데이터 패킷을 전송할 수 있다.The satellite router (101) can generate a satellite routing table by assigning weights to the inter-satellite links (ISLs) connecting satellites according to traffic flow. Furthermore, the satellite router (101) can use the generated routing table to check the buffer queue status toward the next hop, i.e., the next satellite, to which data packets will be transmitted, to determine whether to bypass the data packet, and then transmit the data packet.
이러한, 위성 라우터(101)의 상세 동작은 하기의 도 2 내지 도 11을 참조하여 상세히 설명한다.The detailed operation of the satellite router (101) is described in detail with reference to FIGS. 2 to 11 below.
위성 송수신기(102)는 위성 라우터(101)의 제어에 따라 위성들(110, 120, 130) 각각에서 전달되는 데이터 패킷을 송수신할 수 있다.The satellite transceiver (102) can transmit and receive data packets transmitted from each of the satellites (110, 120, 130) under the control of the satellite router (101).
하기에서는 도 2 내지 도 5를 참조하여 위성 라우터(101)의 동작을 상세히 설명하기로 한다.Below, the operation of the satellite router (101) will be described in detail with reference to FIGS. 2 to 5.
위성 라우터(101)는 데이터 패킷을 생성할 수 있다. 데이터 패킷 데이터는 출발지 위성(SRC: Source)과 목적지(또는 도착지) 위성(DST: Destination)의 정보를 포함할 수 있으며, 다른 위성으로 전송할 정보, 즉 데이터를 포함한다.A satellite router (101) can generate a data packet. The data packet data can include information on a source satellite (SRC: Source) and a destination (or arrival) satellite (DST: Destination), and includes information, i.e., data, to be transmitted to another satellite.
위성 라우터(101)는 위성의 성상도를 그래프로 표현할 수 있다. 그리고, 위성 라우터(101)는 위성 성상도에 따른 네트워크 토폴로지를 생성할 수 있다.A satellite router (101) can represent a satellite's constellation in a graph. In addition, the satellite router (101) can generate a network topology according to the satellite's constellation.
도 2는 일 실시예에 따른 위성 성상도에 따른 네트워크 토폴로지 생성을 도시한 도면이다. 도 2를 참조하면, 네트워크 토폴로지(200)는 6개의 플레인(plane)을 기준으로, 플레인 각각에 11개의 위성이 배치된 위성 성상도를 도시한다. 좌표(X, Y)로 표시된 영역들 각각은 위성을 나타내고, 좌표에서 X는 플레인 번호를 나타내고, Y는 위성 번호를 나타낸다. 각 플레인 상에 각 위성은 네트워크 토폴로지 가장 우측에 배치된 위도(latitude)를 중심으로 배치되어 있다.FIG. 2 is a diagram illustrating the creation of a network topology according to a satellite constellation according to one embodiment. Referring to FIG. 2, a network topology (200) depicts a satellite constellation in which 11 satellites are arranged on each of six planes. Each area indicated by a coordinate (X, Y) represents a satellite, and in the coordinates, X represents a plane number and Y represents a satellite number. On each plane, each satellite is arranged with the latitude positioned at the far right of the network topology as the center.
이러한, 네트워크 토폴로지(200)의 일부를 위성 간 링크(ISL: Inter-Satellite Link)를 이용하여 연결하면 도 3과 같이 도식화될 수 있다.If a part of this network topology (200) is connected using an inter-satellite link (ISL), it can be diagrammed as in Fig. 3.
도 3은 일 실시예에 따른 위성 성상도를 위성 간 링크로 연결한 네트워크 토폴로지로 도시한 도면이다. 도 4를 참조하면, 네트워크 토폴로지(300)는 도 3의 네트워크 토폴로지(200)의 일부를 도식화한 것이다. 네트워크 토폴로지(300) 내에서 각 위성은 노드(node)로 대응될 수 있으며, 각 위성을 연결하는 위성 간 링크(ISL)는 간선(edge)에 대응될 수 있다. 여기서, 위성 간 링크(ISL)는 방향성을 가질 수 있다. 네트워크 토폴로지(300)에서 위성은 원으로 표시되어 있으며, 간선은 실선과 점선으로 표시되어 있다.FIG. 3 is a diagram illustrating a network topology in which satellite constellations are connected by inter-satellite links according to one embodiment. Referring to FIG. 4, the network topology (300) is a diagrammatic representation of a portion of the network topology (200) of FIG. 3. Within the network topology (300), each satellite may correspond to a node, and the inter-satellite links (ISLs) connecting each satellite may correspond to edges. Here, the inter-satellite links (ISLs) may have directionality. In the network topology (300), satellites are represented by circles, and edges are represented by solid and dotted lines.
네트워크 토폴로지(300)에서는 극 지방에 위치한 위성들은 인접한 궤도에 위치한 위성들과 위성 간 링크(ISL)를 연결하기 위해서는 안테나 각도가 커져야 하기 때문에 인접한 궤도에 위치한 위성과 위성 간 링크를 연결하기 어렵다. 또한, 북극 또는 남극으로 이동 중인 위성들은 상대적인 속도 차이가 다른 위성들 대비 매우 커지기 때문에 인접한 궤도에 위치한 위성과 위성 간 링크(ISL)가 연결되지 않는 심(Seam) 영역이 존재한다. 즉, 북극 또는 남극으로 이동 중인 위성들은 심(Seam) 영역으로 인해 인접한 궤도에 위치한 위성과 위성 간 링크를 연결하기 어렵다.In the network topology (300), satellites located in polar regions have difficulty connecting satellite-to-satellite links (ISLs) with satellites located in adjacent orbits because the antenna angle must be large in order to connect the satellite-to-satellite links (ISLs) with satellites located in adjacent orbits. In addition, satellites moving toward the North or South Poles have a very large relative speed difference compared to other satellites, so there exists a seam region where satellite-to-satellite links (ISLs) with satellites located in adjacent orbits are not connected. In other words, satellites moving toward the North or South Poles have difficulty connecting satellite-to-satellite links with satellites located in adjacent orbits due to the seam region.
네트워크 토폴로지(300)에서 진한 색상으로 표시되고, 최상단의 행에 위치한 위성들은 극지방에 위치한 위성들을 나타낸다. 극지방에 위치한 위성들 중 제1 위성(310)을 살펴보면, 제1 위성(310)은 실선으로 표시된 두 개의 동일 궤도 위성 간 링크(ISL)를 가질 수 있다. 한편, 심 영역에 위치한 위성들은 두 개의 동일 궤도 위성 간 링크(ISL)와 하나의 인접 궤도 위성간 링크(ISL)를 가질 수 있다.In the network topology (300), satellites in the uppermost row, indicated by a dark color, represent satellites located in polar regions. Looking at the first satellite (310) among the satellites located in polar regions, the first satellite (310) can have two in-orbit inter-satellite links (ISLs), indicated by solid lines. Meanwhile, satellites located in the deep region can have two in-orbit inter-satellite links (ISLs) and one adjacent-orbit inter-satellite link (ISL).
네트워크 토폴로지(300)에서 극지방이나 심 영역에 위치한 위성들을 제외한 나머지 위성들은 대부분 동일 궤도 위성 간 링크(ISL) 2개와 인접 궤도 위성 간 링크(ISL) 2개를 가져 모두 4개의 위성 간 링크(ISL)를 형성할 수 있다.In the network topology (300), most of the satellites, excluding those located in polar regions or deep regions, have two inter-satellite links (ISLs) and two inter-satellite links (ISLs) in adjacent orbits, forming a total of four inter-satellite links (ISLs).
예를 들어, 네트워크 토폴로지(300)에서 제2 위성(320)을 살펴보면, 제2 위성(320)은 실선으로 표시된 두 개의 동일 궤도 위성 간 링크(ISL)(a1, a2)를 가질 수 있고, 점선으로 표시된 두 개의 인접 궤도 위성 간 링크(ISL)(b1, b2)를 가져 4개의 위성 간 링크(ISL)를 형성할 수 있다.For example, looking at the second satellite (320) in the network topology (300), the second satellite (320) may have two inter-satellite links (ISLs) (a1, a2) in the same orbit indicated by solid lines, and two inter-satellite links (ISLs) (b1, b2) in adjacent orbit indicated by dotted lines, forming four inter-satellite links (ISLs).
따라서, 위성은 인접한 위성들과 위성 간 링크(ISL)를 이용하여 직접 통신을 한다. 위성은 일정한 고도에서 궤도를 따라 이동하기 때문에 인접 위성 간의 거리는 위도에 의해 결정된다. 위성 간의 거리에 따라 통신 과정에서 전파 지연(propagation delay)이 발생한다.Therefore, satellites communicate directly with neighboring satellites using inter-satellite links (ISL). Because satellites orbit at a constant altitude, the distance between neighboring satellites is determined by latitude. The distance between satellites creates a propagation delay during the communication process.
한편, 위성 라우터(101)는 위성들 각각에서 라우팅 방법에 따라 데이터 패킷을 목적지 위성(DST)으로 전송하기 위한 최적의 인접 위성을 결정한다. 위성 라우터(101)는 각 인접 위성으로 전송할 데이터 패킷이 대기하는 소정 개수, 예를 들어, 4개의 버퍼 큐를 가질 수 있다. 위성 라우터(101)는 버퍼 큐에 삽입된 패킷을 위성 간 링크(ISL)의 처리 속도에 따라 버퍼 큐에서 대기할 수 있으며, 이러한 대기 시간으로 인해 대기열 지연(queueing delay)이 발생할 수 있다. 만약, 버퍼 큐에 저장된 데이터의 크기가 버퍼 큐의 최대 크기에 도달하면, 이후 버퍼 큐에 삽입되는 데이터 패킷은 손실될 수 있다. 따라서, 데이터 패킷을 기준으로 출발지 위성(SRC)로부터 전송이 시작되어 도착지 위성(DST)에 도착하는 시점까지의 전파 지연과 대기열 지연의 합을 종단 간 지연(E2E delay: End-to-End delay)으로 정의할 수 있다.Meanwhile, the satellite router (101) determines the optimal neighboring satellite for transmitting data packets to the destination satellite (DST) according to the routing method of each satellite. The satellite router (101) may have a predetermined number of buffer queues, for example, four, in which data packets to be transmitted to each neighboring satellite wait. The satellite router (101) may wait packets inserted into the buffer queues in the buffer queues according to the processing speed of the inter-satellite link (ISL), and this waiting time may cause queuing delay. If the size of data stored in the buffer queue reaches the maximum size of the buffer queue, data packets inserted into the buffer queue thereafter may be lost. Therefore, the sum of the propagation delay and the queuing delay from the time when transmission from the source satellite (SRC) begins until the time when the data packet arrives at the destination satellite (DST) may be defined as the end-to-end delay (E2E delay).
이에, 위성 라우터(101)는 저궤도 위성 네트워크에서 데이터 패킷의 종단 간 지연(E2E delay) 손실을 최소화하기 위해 글로벌 트래픽 분포 밀도를 이용한다. 또한, 위성 라우터(101)는 트래픽 분포 밀도에 기초하여 트래픽 흐름을 예측하여 라우팅 테이블을 생성한 후, 생성된 라우팅 테이블을 이용하여 라우팅 경로의 부하를 경감시켜 데이터 패킷을 전송할 수 있는 우회 경로를 선택할 수 있다.Accordingly, the satellite router (101) utilizes the global traffic distribution density to minimize the end-to-end delay (E2E delay) loss of data packets in the low-orbit satellite network. Furthermore, the satellite router (101) predicts traffic flow based on the traffic distribution density, generates a routing table, and then uses the generated routing table to select a detour route that can transmit data packets while reducing the load on the routing path.
위성 라우터(101)에서 트래픽 분포 기반의 라우팅 테이블 설계 동작에 근거한 의사 결정 코드는 하기의 표 1과 같이 나타낼 수 있다.The decision code based on the routing table design operation based on traffic distribution in the satellite router (101) can be expressed as shown in Table 1 below.
위성 라우터(101)는 각 위성을 노드(V), 위성 간 링크(ISL)를 엣지(E)로 하고, 각 엣지(E)에 적용되는 가중치(W)를 포함하는 위성 네트워크의 토폴로지 그래프(G(V, E, W))를 생성할 수 있다. 여기서, 초기 가중치는 위성 간 링크(ISL) 길이에 따른 전파 지연 값을 적용한다.A satellite router (101) can generate a topology graph (G(V, E, W)) of a satellite network, which includes each satellite as a node (V), an inter-satellite link (ISL) as an edge (E), and a weight (W) applied to each edge (E). Here, the initial weight applies a propagation delay value according to the length of the inter-satellite link (ISL).
위성 라우터(101)는 데이터 패킷의 전송 경로를 다익스트라 최단 거리 알고리즘(Dijkstra's algorism)을 이용하여 탐색할 수 있다. 이러한 다익스트라 최단 거리 알고리즘은 노드 간 엣지의 가중치 값이 최소가 되는 경로를 탐색하는 알고리즘이다. 따라서, 위성 라우터(101)는 다익스트라 최단 거리 알고리즘을 토폴로지 그래프에 적용하면 데이터 패킷의 전송 지연을 최소화할 수 있다.The satellite router (101) can search for a data packet transmission path using Dijkstra's algorithm. This Dijkstra's algorithm is an algorithm that searches for a path with the minimum edge weight value between nodes. Therefore, the satellite router (101) can minimize the transmission delay of data packets by applying Dijkstra's algorithm to a topology graph.
위성 라우터(101)는 토폴로지 그래프에서 가중치(W)의 초기값으로 전파 지연을 사용한다. 예를 들어, 위성 라우터(101)는 제1 위성(v)과 제2 위성(v') 사이의 전파 지연을 하기의 수학식 1을 사용하여 계산할 수 있다.The satellite router (101) uses the propagation delay as the initial value of the weight (W) in the topology graph. For example, the satellite router (101) can calculate the propagation delay between the first satellite (v) and the second satellite (v') using the following mathematical expression 1.
여기서,는 동일 궤도 위성 간 거리이고,는 인접 궤도 위성 간 거리이다. 이때, 위성 라우터(101)는 하기의 수학식 2로 동일 궤도 위성 간 거리를 계산할 수 있으며, 하기의 수학식 3으로 인접 궤도 위성 간 거리를 계산할 수 있다.Here, is the distance between satellites in the same orbit, is the distance between adjacent orbit satellites. At this time, the satellite router (101) can calculate the distance between satellites in the same orbit using the following mathematical formula 2, and can calculate the distance between satellites in adjacent orbits using the following mathematical formula 3.
여기서,는 한 궤도 평면에 포함되는 위성의 수이고,는 인접 위성 간 위상차이고,는 두 위성의 위도차이고,는 위성의 현재 위도를 나타낸다.Here, is the number of satellites included in one orbital plane, is the phase difference between adjacent satellites, is the latitude difference between the two satellites, is a satellite Indicates the current latitude.
는 정해진 위성 모델 내에서 위성이 균일하게 배치되었을 때, 항상 일정한 값을 유지한다. 반면에,는 현재 위성의 위도에 따라 값이 변한다. 고위도에 위치하는 위성의는 저위도에 위치하는 위성보다 작은 값을 갖는다. 따라서, 최단 거리 기반의 라우팅 기술에서는 고위도 위성 간에는 전파 지연이 짧아 인접 궤도 간 트래픽 전달을 고위도 지역을 선호하게 된다.is always a constant value when satellites are uniformly distributed within a given satellite model. On the other hand, The value changes depending on the current latitude of the satellite. For satellites located at high latitudes, has a smaller value than satellites located at lower latitudes. Therefore, in routing technology based on the shortest path, the propagation delay between high-latitude satellites is shorter, so high-latitude regions are preferred for traffic transmission between adjacent orbits.
이후, 위성 라우터(101)는 대기열 지연에 대한 가중치를 반영하기 위해 트래픽 흐름을 예측할 수 있다.Afterwards, the satellite router (101) can predict the traffic flow to reflect the weight for the queue delay.
도 4는 일 실시예에 따른 지표면 영역의 트래픽 분포 밀도 값을 도시한 도면이다.FIG. 4 is a diagram illustrating traffic distribution density values of a ground surface area according to one embodiment.
도 4를 참조하면, 지표면을 8 X 16의 단위 영역으로 분할하고, 각 단위 영역 내에는 트래픽 분포 밀도 값이 기록되어 있다. 이러한, 트래픽 분포 밀도 값은 예를 들어, 인터넷 사용자 수와 인구 수를 기반으로 계산될 수 있다.Referring to Figure 4, the earth's surface is divided into 8 X 16 unit areas, and a traffic distribution density value is recorded within each unit area. This traffic distribution density value can be calculated based on, for example, the number of Internet users and the population.
트래픽 분포 밀도를 살펴보면, 단위 영역들(411, 413, 415)에서는 트래픽 분포 밀도 수치가 다른 영역들 대비 상대적으로 높기 때문에 트래픽이 다량 분포될 수 있다. 반면에, 단위 영역(417)에서는 트래픽 분포 밀도 수치가 다른 영역들 대비 상대적으로 낮기 때문에 트래픽이 소량 분포될 수 있다. 즉, 트래픽 분포 밀도 값의 숫자가 높을수록 트래픽 분포가 혼잡한 것을 나타낸다.Looking at the traffic distribution density, the unit areas (411, 413, 415) have relatively high traffic distribution density values compared to other areas, which may result in a large amount of traffic being distributed. Conversely, the unit area (417) has relatively low traffic distribution density values compared to other areas, which may result in a small amount of traffic being distributed. In other words, a higher traffic distribution density value indicates a more congested traffic distribution.
위성 라우터(101)는 트래픽 분포 밀도를 기반으로 트래픽 흐름을 예측하고, 각 위성 간 링크(ISL)의 대기열 지연에 대한 가중치를 계산할 수 있다. 위성 라우터(101)는 트래픽 발생되는 출발지 위성(SRC)으로부터 목적지 위성(DST)까지 전송되는 데이터 패킷, 즉 트래픽에 대한 예측 대기열 지연의 가중치()를 하기의 수학식 4를 사용하여 계산할 수 있다.The satellite router (101) can predict traffic flow based on the traffic distribution density and calculate a weight for the queue delay of each inter-satellite link (ISL). The satellite router (101) can calculate the weight of the predicted queue delay for the data packet transmitted from the source satellite (SRC) where the traffic is generated to the destination satellite (DST). ) can be calculated using the following mathematical formula 4.
여기서,는 트래픽 분포 밀도에서영역의 밀도값이다. 다음으로, 위성 라우터(101)는 가중치를 반영하기 위해 토폴로지 그래프에서 다익스트라 최단거리 알고리즘을 이용하여 출발지 위성(SRC)으로부터 목적지 위성(DST)까지 최소 가중치 합의 경로를 찾는다. 위성 라우터(101)는 찾은 경로의 모든 위성 간 링크(ISL), 즉 토폴로지 그래프에서 엣지의 기존 가중치(W)에 계산된를 합산하여 가중치를 갱신할 수 있다.Here, is in the traffic distribution density is the density value of the area. Next, the satellite router (101) finds the minimum weighted sum path from the source satellite (SRC) to the destination satellite (DST) using the Dijkstra shortest path algorithm in the topology graph to reflect the weight. The satellite router (101) calculates the minimum weighted sum path from all inter-satellite links (ISLs) of the found path, i.e., the existing weight (W) of the edge in the topology graph. The weights can be updated by adding them up.
위성 라우터(101)는 토폴로지 그래프의 가중치를 모든 위성의 출발지 위성(SRC) 및 목적지 위성(DST)의 쌍을 기준으로 수행한다. 이를 통해, 트래픽의 흐름이 많아 자주 사용되는 위성 간 링크(ISL)의 가중치는 트래픽의 흐름이 적어 자주 사용되지 않는 위성 간 링크(ISL)의 가중치보다 더 높은 값을 갖는다. 이를 통해, 위성 라우터(101)는 토폴로지 그래프의 가중치에 트래픽 흐름을 반영시켜 라우팅 경로를 분산시킬 수 있다. 하지만, 트래픽 분포가 밀집된 지역에서의 라우팅 경로는 계속해서 동일한 경로를 사용하게 된다.The satellite router (101) weights the topology graph based on the pairs of the source satellite (SRC) and destination satellite (DST) of each satellite. This allows the weights of frequently used inter-satellite links (ISLs) with high traffic flow to be higher than those of less frequently used inter-satellite links (ISLs) with low traffic flow. This allows the satellite router (101) to distribute routing paths by reflecting traffic flow in the weights of the topology graph. However, routing paths in areas with dense traffic distribution continue to use the same paths.
따라서, 위성 라우터(101)는 밀집된 지역의 라우팅 경로를 분산시키기 위한 반복적인 예측 대기열 지연 가중치를 반영한다. 예를 들어, 위성 라우터(101)는 가중치가 변경된 토폴로지 그래프에서 최소 가중치 합 경로를 다시 찾아 예측 대기열 지연의 가중치()를 더한다. 위성 라우터(101)는 이러한 가중치 반영 동작을 반복하여 고밀도 트래픽 분포 지역에서의 위성 간 링크(ISL)의 가중치를 높여, 라우팅 경로의 중첩을 회피할 수 있도록 유도할 수 있다. 즉, 위성 라우터(101)는 라우팅 경로가 중첩되는 상황을 줄여 각 위성 간 링크(ISL)로 데이터 패킷을 전송을 위해 제공된 데이터 큐의 과부하를 예방할 수 있다.Therefore, the satellite router (101) reflects the iterative prediction queue delay weight to distribute the routing path in the dense area. For example, the satellite router (101) finds the minimum weight sum path again in the topology graph with changed weights and adjusts the weight of the predicted queue delay ( ) is added. The satellite router (101) can repeat this weight reflection operation to increase the weight of the inter-satellite link (ISL) in a high-density traffic distribution area, thereby avoiding overlapping of routing paths. That is, the satellite router (101) can reduce the situation in which routing paths overlap, thereby preventing overload of the data queue provided for transmitting data packets to each inter-satellite link (ISL).
위성 라우터(101)는 토폴로지 그래프에서 라우팅 경로 상의 과부하를 방지할 수 있도록 가중치를 갱신할 수 있으며, 가중치가 갱신된 토폴로지 그래프를 이용하여 각 위성의 라우팅 테이블을 생성할 수 있다. 여기서, 라우팅 테이블은 목적지 위성(DST)에 대한 최선의 다음 홉 위성(BH: Best next Hop satellite)과 차선의 다음 홉 위성(SBH: Second-Best next Hop satellite)에 대한 정보를 저장할 수 있다.The satellite router (101) can update weights in a topology graph to prevent overload on a routing path, and can generate a routing table for each satellite using the topology graph with updated weights. Here, the routing table can store information about the best next hop satellite (BH) and the second-best next hop satellite (SBH) for the destination satellite (DST).
위성 라우터(101)에서 부하 분산 라우팅 동작에 근거한 의사 결정 코드는 하기의 표 2와 같이 나타낼 수 있다.The decision code based on the load distribution routing operation in the satellite router (101) can be expressed as shown in Table 2 below.
위성 라우터(101)는 라우팅 테이블에서 다음 홉 위성(BH: Best next Hop satellite)과 차선의 다음 홉 위성(SBH: Second-Best next Hop satellite)에 대한 정보를 확인하고, 부하 분산을 위한 우회 경로로의 사용 여부를 확인할 수 있다.The satellite router (101) can check information about the next hop satellite (BH: Best next Hop satellite) and the next best next hop satellite (SBH: Second-Best next Hop satellite) in the routing table and check whether to use it as a detour route for load distribution.
도 5는 일 실시예에 따른 최선의 다음 홉 위성과 차선의 다음 홉 위성의 선정을 도시한 도면이다.FIG. 5 is a diagram illustrating selection of a best next-hop satellite and a second-best next-hop satellite according to one embodiment.
도 5를 참조하면, 위성 성상도를 기준으로 위성(N1)은 최선의 다음 홉 위성(BH: Best next Hop satellite)과 차선의 다음 홉 위성(SBH: Second-Best next Hop satellite) 중 하나를 선정하여 데이터 패킷을 전송할 수 있다. 최선의 다음 홉 위성(BH)은 위성(N1) 주변에서 데이터 패킷을 전송하기 위한 위성 간 링크(ISL) 상태가 가장 좋은 위성일 수 있고, 차선의 다음 홉 위성(SBH)은 최선의 다음 홉 위성(BH)을 제외한 나머지 홉 위성들과의 위성 간 링크(ISL) 중에서 상태가 가장 좋은 위성(SBH)일 수 있다. 따라서, 최선의 다음 홉 위성(BH)으로의 데이터 패킷 전송의 과부하가 발생하면, 차선의 다음 홉 위성(SBH)을 이용하여 라우팅 경로를 우회할 수 있다.Referring to FIG. 5, based on the satellite constellation, a satellite (N1) can select either a best next hop satellite (BH) or a second-best next hop satellite (SBH) to transmit data packets. The best next hop satellite (BH) may be the satellite with the best inter-satellite link (ISL) status for transmitting data packets around the satellite (N1), and the second-best next hop satellite (SBH) may be the satellite (SBH) with the best status among the inter-satellite links (ISLs) with the remaining hop satellites excluding the best next hop satellite (BH). Therefore, if an overload occurs in transmitting data packets to the best next hop satellite (BH), the routing path can be bypassed using the second-best next hop satellite (SBH).
기존의 위성 네트워크에서는 인접 위성 또는 전체 위성의 버퍼 큐 상태를 수집하는 동작을 주기적으로 수행하여 다음 홉 위성을 선택하지만, 주기적인 위성 간 정보의 교환을 필요로 한다. 링크에 데이터 패킷 전송을 위한 과부하가 발생된 경우, 데이터 패킷이 아닌 라우팅 테이블을 수정하거나 부하를 분산하는 사용되는 신호가 증가하면 실제 데이터 패킷의 전송을 위한 네트워크 자원(예를 들어, 위성 간 링크(ISL), 버퍼 큐 등)을 소모시킨다.In conventional satellite networks, the buffer queue status of neighboring satellites or all satellites is periodically collected to select the next-hop satellite. However, this requires periodic exchange of information between satellites. If a link becomes overloaded due to data packet transmission, routing tables are modified instead of data packets, or the increased use of signals to distribute the load consumes network resources (e.g., inter-satellite links (ISLs), buffer queues, etc.) for actual data packet transmission.
한편, 위성 라우터(101)는 라우팅 경로가 분산되더라도 트래픽 양이 증가하게 되면, 위성 간 링크(ISL)에 과부하가 발생할 수 있다. 이로 인해, 위성 라우터(101)는 버퍼의 큐 상태에 따라 패킷을 우회시키는 부하 분산 라우팅을 수행한다.Meanwhile, even if the routing path is distributed, the satellite router (101) may experience an overload on the inter-satellite link (ISL) if traffic volume increases. Therefore, the satellite router (101) performs load-balancing routing to divert packets based on the buffer queue status.
이와 같이, 위성 라우터(101)는 위성 간의 정보 교환없이 데이터 패킷의 전송을 위한 위성의 각 방향의 버퍼 큐의 현재 크기를 확인하고, 버퍼 큐 점유율에 따라 다음 홉 위성을 결정할 수 있다.In this way, the satellite router (101) can check the current size of the buffer queue in each direction of the satellite for transmission of data packets without exchanging information between satellites, and determine the next hop satellite based on the buffer queue occupancy rate.
위성 라우터(101)는 t시간에서 위성 v의 v'방향의 버퍼 큐의 크기를 하기의 수학식 5로 계산할 수 있다.The satellite router (101) can calculate the size of the buffer queue in the v' direction of satellite v at time t using the following mathematical expression 5.
여기서,는 t시간에 위성 v가 전달받은 패킷 중 다음 홉이 v'인 패킷의 양을 나타낸다.Here, represents the amount of packets whose next hop is v' among the packets received by satellite v at time t.
또한, 위성 라우터(101)는 버퍼 큐의 점유율을 하기의 수학식 6으로 계산할 수 있다.Additionally, the satellite router (101) can calculate the occupancy rate of the buffer queue using the following mathematical expression 6.
여기서,는 버퍼 큐의 최대 크기이다.Here, is the maximum size of the buffer queue.
위성 라우터(101)는 최선의 다음 홉 위성(BH: Best next Hop satellite)의 버퍼 큐의 점유율인가 소정 임계값(Threshold) 이상이면, 차선의 다음 홉 위성(SBH)으로 우회시켜 전송할 수 있다. 위성 라우터(101)는 우회 경로로 인한 라우팅 루프가 발생할 수 있다. 이를 방지하기 위해, 위성 라우터(101)는 세 개의 데이터 패킷의 전송에 따른 우회 방지 조건을 적용한다. 예를 들어, 위성 라우터(101)는 다음 홉 위성(BH: Best next Hop satellite)이 도착지인 경우, SBH 방향의 버퍼 큐의 점유율도 소정 임계값 이상인 경우, SBH가 데이터 패킷이 전송된 이전 경로의 위성인 경우 중 적어도 하나이면 데이터 패킷을 우회시키지 않고, 최선의 다음 홉 위성(BH)으로 전달할 수 있다.The satellite router (101) is the occupancy rate of the buffer queue of the best next hop satellite (BH). If the threshold is greater than or equal to a predetermined threshold, the data packet can be transmitted by detouring to the next best hop satellite (SBH). The satellite router (101) may cause a routing loop due to the detour path. To prevent this, the satellite router (101) applies a detour prevention condition according to the transmission of three data packets. For example, the satellite router (101) may not detour the data packet and transmit it to the best next hop satellite (BH) if at least one of the following conditions exists: if the next hop satellite (BH) is the destination; if the occupancy rate of the buffer queue in the SBH direction is greater than or equal to a predetermined threshold; and if the SBH is the satellite of the previous path on which the data packet was transmitted.
도 6은 일 실시예에 따른 라우팅 장치에서의 분산형 라우팅 동작을 도시한 순서도이다.FIG. 6 is a flowchart illustrating distributed routing operations in a routing device according to one embodiment.
도 6을 참조하면, 위성 라우팅 장치(100)는 위성 네트워크의 토폴로지 그래프를 생성하기 위해 위성 간 링크(ISL) 각각에 대해 가중치를 부여한다(611단계). 위성 라우팅 장치(100)는 위성 인 노드(V), 위성 간 링크(ISL)인 엣지(E), 위성 간 링크(ISL)에 대한 가중치(W)를 포함한 토폴로지 그래프(G(V,E,W))를 생성할 수 있다. 위성 라우팅 장치(100)는 위성 들 간 전파 지연을 토폴로지 그래프 내 가중치의 초기값으로 설정할 수 있다.Referring to FIG. 6, the satellite routing device (100) assigns a weight to each inter-satellite link (ISL) to generate a topology graph of a satellite network (step 611). The satellite routing device (100) can generate a topology graph (G(V,E,W)) including a node (V) which is a satellite, an edge (E) which is an inter-satellite link (ISL), and a weight (W) for the inter-satellite link (ISL). The satellite routing device (100) can set the propagation delay between satellites as an initial value of the weight in the topology graph.
위성 라우팅 장치(100)는 위성 네트워크를 통해 전송될 트래픽 흐름을 예측할 수 있다(613단계). 여기서, 트래픽 흐름은 지표면을 분할한 단위 면적들 각각에 대한 트래픽 분포 밀도를 이용하여 계산될 수 있으며, 트래픽 분포 밀도는 단위 면적 내의 인터넷 사용자 수와 인구 수를 기반으로 계산될 수 있다.The satellite routing device (100) can predict the traffic flow to be transmitted through the satellite network (step 613). Here, the traffic flow can be calculated using the traffic distribution density for each unit area dividing the Earth's surface, and the traffic distribution density can be calculated based on the number of Internet users and the population within the unit area.
위성 라우팅 장치(100)는 예측된 트래픽 흐름을 토폴로지 그래프 내 가중치를 반영할 수 있다(615단계). 위성 라우팅 장치(100)는 위성 간 링크(ISL)에 가중치를 반영하기 위해 중력 모델(Gravity model)을 사용할 수 있다. 여기서, 중력 모델은 두 지점 사이의 흐름을 예측하는데 사용되는 모델로 트래픽 분포 밀도 지표를 사용하여 두 지점 사이의 트래픽 흐름을 예측한다.The satellite routing device (100) can reflect the predicted traffic flow as a weight within the topology graph (step 615). The satellite routing device (100) can use a gravity model to reflect the weight in the inter-satellite link (ISL). Here, the gravity model is a model used to predict the flow between two points, and predicts the traffic flow between the two points using a traffic distribution density index.
또한, 위성 라우팅 장치(100)는 토폴로지 그래프에서 위성 간 링크(ISL) 각각에 대한 가중치를 트래픽 흐름으로 계산된 위성 간 링크의 대기열 지연 시간(예측된 대기열 지연 시간)으로 갱신할 수 있다.Additionally, the satellite routing device (100) can update the weight for each inter-satellite link (ISL) in the topology graph with the queuing delay time (predicted queuing delay time) of the inter-satellite link calculated as a traffic flow.
위성 라우팅 장치(100)는 상기 가중치 반복하여 반영할지를 판단한다(617단계). 617단계의 판단결과, 위성 라우팅 장치는 가중치를 반복하여 반영하고자 하는 경우, S615단계로 진행하여 최소 가중치를 갖는 최단 경로를 소정 회수 이상 반복 검색하여 계산된 대기열 지연 계산으로 상기 가중치를 반복하여 갱신할 수 있다.The satellite routing device (100) determines whether to repeatedly reflect the weight (step 617). If the satellite routing device determines that it wishes to repeatedly reflect the weight based on the determination result of step 617, it proceeds to step S615, and repeatedly searches for the shortest path with the minimum weight a predetermined number of times to calculate the calculated queue delay, thereby repeatedly updating the weight.
617단계의 판단결과, 위성 라우팅 장치(100)는 가중치의 반복 반영을 종료하는 경우, S619단계로 진행한다.If the satellite routing device (100) terminates the repeated reflection of the weights as a result of the judgment in step 617, it proceeds to step S619.
위성 라우팅 장치(100)는 각 위성의 라우팅 테이블을 생성할 수 있다(619단계).The satellite routing device (100) can create a routing table for each satellite (step 619).
위성 라우팅 장치(100)는 데이터 패킷을 수신하였는지 확인한다(621단계).The satellite routing device (100) checks whether a data packet has been received (step 621).
621단계의 확인결과, 위성 라우팅 장치(100)는 데이터 패킷을 수신하지 못하면, 데이터 패킷을 수신할 때까지 대기한다.As a result of the verification in step 621, if the satellite routing device (100) does not receive a data packet, it waits until it receives a data packet.
621단계의 확인결과, 위성 라우팅 장치(100)는 데이터 패킷을 수신하면, S623단계로 진행한다. 위성 라우팅 장치(100)는 라우팅 테이블을 이용하여 수신된 데이터 패킷의 목적지 위성에 대한 최선의 다음 홉 위성(BH: Best next Hop satellite)과 차선의 다음 홉 위성(SBH)을 확인한다(625단계).As a result of the verification in step 621, if the satellite routing device (100) receives a data packet, it proceeds to step S623. The satellite routing device (100) uses the routing table to check the best next hop satellite (BH) and the next best next hop satellite (SBH) for the destination satellite of the received data packet (step 625).
위성 라우팅 장치(100)는 위성의 각 방향에 대한 버퍼 큐의 크기를 확인할 수 있다(627단계). 즉, 위성 라우팅 장치(100)는 위성의 각 방향에 대한 버퍼 큐의 사용량 즉, 데이터 패킷의 점유 상태를 확인할 수 있다.The satellite routing device (100) can check the size of the buffer queue for each direction of the satellite (step 627). That is, the satellite routing device (100) can check the usage of the buffer queue for each direction of the satellite, i.e., the occupancy status of data packets.
위성 라우팅 장치(100)는 현재 버퍼 큐의 점유율에 따라 다음 홉 위성을 결정한다(629단계).The satellite routing device (100) determines the next hop satellite based on the current buffer queue occupancy rate (step 629).
이때, 위성 라우팅 장치(100)는 데이터 패킷의 전송 시 우회 경로 선택 조건에 대응되는지 판단할 수 있다(629단계).At this time, the satellite routing device (100) can determine whether the conditions for selecting a detour route are met when transmitting a data packet (step 629).
629단계의 판단결과, 위성 라우팅 장치(100)는 우회 경로 선택 조건에 대응되면, 631단계로 진행한다. 위성 라우팅 장치(100)는 우회 경로 선택 조건에 대응되는 경우, 데이터 패킷을 우회하지 않고 전달한다(631단계).As a result of the judgment in step 629, if the satellite routing device (100) corresponds to the detour route selection condition, it proceeds to step 631. If the satellite routing device (100) corresponds to the detour route selection condition, it transmits the data packet without detouring (step 631).
여기서, 우회 경로 선택 조건은 다음과 같다. 첫 번째는, 최선의 다음 홉 위성(BH: Best next Hop satellite)이 도착지인 경우이다. 두 번째는, 차선의 다음 홉 위성(SBH: Second-Best next Hop satellite) 방향의 버퍼 큐의 점유율이 소정 임계값 이상인 경우이다. 세 번째는, SBH가 데이터 패킷이 전송된 이전 경로의 위성인 경우이다. 따라서, 위성 라우팅 장치(100)는 위의 세 가지 중 적어도 하나의 조건에 대응되면, 패킷을 우회하지 않고 전달할 수 있다.Here, the conditions for selecting a detour route are as follows. First, the destination is the Best Next Hop Satellite (BH). Second, the buffer queue occupancy rate toward the Second-Best Next Hop Satellite (SBH) exceeds a predetermined threshold. Third, the SBH is the satellite along the previous route along which the data packet was transmitted. Therefore, the satellite routing device (100) can forward the packet without detouring if at least one of the three conditions above is met.
629단계의 판단결과, 위성 라우팅 장치(100)는 우회 경로 선택 조건에 대응되지 않으면, 635단계로 진행한다. 위성 라우팅 장치(100)는 우회 경로 선택 조건에 대응되는 않는 데이터 패킷에 대해서는 최선의 다음 홉 위성(BH: Best next Hop satellite)의 버퍼큐 점유율에 따라 데이터 패킷을 우회하여 전송한다.As a result of the judgment in step 629, if the satellite routing device (100) does not correspond to the detour path selection condition, the satellite routing device (100) proceeds to step 635. For data packets that do not correspond to the detour path selection condition, the satellite routing device (100) transmits the data packets by detour according to the buffer queue occupancy rate of the best next hop satellite (BH).
633단계에서 위성 라우팅 장치(100)는 패킷이 목적지에 도달하였는지 확인한다. 633단계에서 위성 라우팅 장치(100)는 패킷이 목적지에 도달하였으면, 프로세스를 종료할 수 있다. 하지만, 633단계에서, 위성 라우팅 장치(100)는 패킷이 목적지에 도달하지 않으면, 621단계로 진행하여 데이터 패킷을 수신하여 처리하는 동작을 수행한다.In step 633, the satellite routing device (100) determines whether the packet has reached its destination. If the packet has reached its destination in step 633, the satellite routing device (100) can terminate the process. However, if the packet has not reached its destination in step 633, the satellite routing device (100) proceeds to step 621 to receive and process the data packet.
상술한 바와 같이, 기존에는 불균형한 트래픽 분포로 인한 발생하는 위성 간 링크(ISL)의 부하를 분산하지 못한다. 불균형한 트래픽 분포에서 일부 지역 간의 트래픽 흐름이 많고, 해당 트래픽 흐름은 같은 라우팅 경로를 통해 패킷이 전달되기 때문에 특정한 위성 간 링크(ISL)의 과부하를 발생시킨다. 위성 간 링크(ISL)의 과부하는 해당 위성 간 링크(ISL)를 라우팅 경로로 사용하는 패킷의 종단 간 지연(E2E delay)를 높이며, 트래픽 양이 증가하게 되면 패킷 손실을 유발한다. 높은 종단 간 지연은 서비스의 끊김 및 반응 시간 지연 등의 사용자 경험 저하를 가져오고, 패킷 손실은 패킷 재전송을 유발해 위성 간 링크(ISL) 과부하 문제를 더욱 악화시킨다.As described above, existing systems fail to distribute the load on inter-satellite links (ISLs) resulting from unbalanced traffic distribution. This unbalanced traffic distribution results in significant traffic flow between certain regions, and since these traffic flows transmit packets through the same routing path, they overload specific ISLs. This ISL overload increases the end-to-end delay (E2E) of packets that use the ISL as a routing path, and as traffic volume increases, packet loss occurs. High E2E delay results in a degraded user experience, such as service interruptions and delayed response times, and packet loss triggers packet retransmission, further exacerbating the ISL overload problem.
하지만, 본 발명에서 제안된 분산형 라우팅 기술은 트래픽 분포를 반영한 라우팅 테이블을 생성하기 때문에, 트래픽 흐름을 반영하여 라우팅 경로를 분산시킬 수 있다. 분산된 라우팅 경로는 패킷의 라우팅 경로의 중첩을 최소화함으로써 위성 간 링크(ISL)의 과부하 발생을 감소시킨다. 또한, 부하 분산 라우팅 알고리즘으로 버퍼 큐의 부하에 따라 패킷의 라우팅 경로를 우회시켜 ISL의 과부하 발생을 최소화해 패킷의 종단 간 지연과 패킷 손실을 감소시킬 수 있다.However, the distributed routing technology proposed in the present invention generates a routing table that reflects traffic distribution, enabling the distribution of routing paths to reflect traffic flow. Distributed routing paths minimize overlapping packet routing paths, thereby reducing the occurrence of inter-satellite link (ISL) overload. Furthermore, the load-balancing routing algorithm can bypass packet routing paths based on buffer queue load, thereby minimizing ISL overload and reducing end-to-end packet delay and packet loss.
본 발명에서 제안된 기술의 성능을 평가하기 위한 시뮬레이션 환경을 간략히 설명한다. 시뮬레이션 환경에서 LEO 위성의 수는 128개이며 8개의 궤도 평면에 16개의 위성이 배치된다. 궤도 평면은 약 89°의 궤도 기울기를 갖고, 궤도 평면 내의 위성은 약 800km 고도에서 균일한 간격으로 배치된다. 위성은 2.5MB 크기의 버퍼 큐를 약 4개 갖고, 인접 위성으로 전달할 패킷을 보관할 수 있다. 위성 간 링크(ISL)는 260Mbps의 속도로 버퍼 큐의 패킷을 처리한다. 시뮬레이션 환경은 6.0~11.5Gbps의 패킷 생성률을 0.5Gbps 단위로 증가시켜 진행시켜 1분(60,000ms) 동안의 라우팅 성능을 평가한다. 패킷은 1KB 크기를 가지며, 1ms 마다 생성된다. 패킷의 생성지와 목적지는 트래픽 분포 밀도에 따라 중력 모델을 기반으로 결정된다.This paper briefly describes the simulation environment for evaluating the performance of the technology proposed in this invention. The simulation environment consists of 128 LEO satellites, 16 of which are deployed in eight orbital planes. The orbital planes have an orbital inclination of approximately 89°, and the satellites within the orbital planes are evenly spaced at an altitude of approximately 800 km. The satellites have approximately four 2.5 MB buffer queues, each capable of storing packets to be forwarded to neighboring satellites. The inter-satellite link (ISL) processes packets in the buffer queues at a rate of 260 Mbps. The simulation environment evaluates routing performance over one minute (60,000 ms) by increasing the packet generation rate from 6.0 to 11.5 Gbps in 0.5 Gbps increments. Packets are 1 KB in size and generated every 1 ms. The packet generation and destination are determined based on a gravity model based on traffic distribution density.
본 발명의 성능을 비교하기 위해 두 개의 기술을 이용한다. 우선, 본 발명에서 제안하는 기술은 Proposed로 표시한다. 첫 번째 벤치마크 기술은 명시적 부하 분산 방식으로 시뮬레이션 그래프에서 ELB의 용어로 표시한다. 해당 기술은 위성이 인접 위성과 혼잡 상태에 대한 정보를 명시적으로 교환하여 혼잡 수준에 따라 패킷을 라우팅한다. 두 번째 벤치마크 기술은 신호등 기반의 부하 분산 방식으로 시뮬레이션 그래프에서 TLR의 용어로 표시한다. 해당 기술은 각 방향의 버퍼 큐의 혼잡 상태와 인접 위성의 혼잡 상태에 따라 신호등 색을 결정하고, 신호등 색에 패킷을 라우팅한다. 비교를 위한 두 개의 기술들은 주기적으로 네트워크 전체 위성의 혼잡 상태에 대한 정보를 수집하여 라우팅 테이블을 수정한다.To compare the performance of the present invention, we utilize two techniques. First, the technique proposed in the present invention is denoted as "Proposed." The first benchmark technique is an explicit load balancing technique, denoted as ELB in the simulation graph. This technique explicitly exchanges information about congestion status with neighboring satellites and routes packets based on the congestion level. The second benchmark technique is a traffic light-based load balancing technique, denoted as TLR in the simulation graph. This technique determines the color of the traffic lights based on the congestion status of the buffer queues in each direction and the congestion status of neighboring satellites, and routes packets based on the corresponding traffic light color. Both techniques for comparison periodically collect information about the congestion status of satellites across the network and update their routing tables.
도 7은 일 실시예에 따른 패킷 생성률을 변화하며 목적지에 도착한 패킷의 평균 패킷 손실률을 도시한 그래프이다.FIG. 7 is a graph showing the average packet loss rate of packets arriving at a destination while changing the packet generation rate according to one embodiment.
도 7을 참조하면, 그래프의 가로축은 패킷 생성률을 나타내고, 세로축은 패킷 손실률을 나타낸다. 여기서, 패킷 손실은 드롭-테일(drop-tail) 버퍼 큐로 패킷이 손실되는 경우만 고려한다. 패킷 손실률은 전체 생성된 총 패킷 수에서 손실된 패킷의 수의 비율이다. 제안된 실시예(proposed)는 비교 대상 기술들인 TLR 기술 및 ELB 기술과 패킷 생성률을 증가시켜 가며 비교한 결과, 일정 패킷을 생성할 때까지 손실된 패킷이 제로(0)에 가깝고, 비교 대상 기술들 보다 패킷 손실률이 현저히 낮은 것을 확인할 수 있다.Referring to Fig. 7, the horizontal axis of the graph represents the packet generation rate, and the vertical axis represents the packet loss rate. Here, packet loss only considers cases where packets are lost due to a drop-tail buffer queue. The packet loss rate is the ratio of the number of lost packets to the total number of generated packets. The proposed embodiment is compared with the comparative technologies, TLR technology and ELB technology, by increasing the packet generation rate. As a result, it can be confirmed that the number of lost packets is close to zero (0) until a certain number of packets are generated, and the packet loss rate is significantly lower than that of the comparative technologies.
도 8은 일 실시예에 따른 패킷 생성률을 변화하며 패킷 데이터의 처리량을 도시한 그래프이다.FIG. 8 is a graph showing the processing amount of packet data while changing the packet generation rate according to one embodiment.
도 8을 참조하면, 그래프의 가로축은 패킷 생성률을 나타내고, 세로축은 처리량을 나타낸다. 여기서, 패킷 처리량은 전체 생성된 데이터 패킷 수에서 목적지에 도달한 데이터 패킷의 수를 나타낸다. 제안된 실시예(proposed)는 비교 대상 기술들인 TLR 기술 및 ELB 기술과 패킷 생성률을 증가시켜 가며 비교한 결과, 데이터 패킷의 처리량이 상대적으로 높게 나타나는 것을 확인할 수 있다.Referring to Figure 8, the horizontal axis of the graph represents the packet generation rate, and the vertical axis represents throughput. Here, packet throughput represents the number of data packets that reach the destination out of the total number of data packets generated. The proposed embodiment, when compared with the comparative technologies TLR and ELB, shows a relatively high data packet throughput when the packet generation rate is increased.
도 9는 일 실시예에 따른 패킷 생성률을 변화하며 패킷의 평균 종단 간 지연을 도시한 그래프이다.FIG. 9 is a graph showing the average end-to-end delay of packets as the packet generation rate changes according to one embodiment.
도 9를 참조하면, 그래프의 가로축은 패킷 생성률을 나타내고, 세로축은 평균 종단간 지연을 나타낸다. 여기서, 평균 종단 간 지연은 출발지 위성부터 목적지 위성까지의 도착 시간을 의미한다. 제안된 실시예(proposed)는 비교 대상 기술들인 TLR 기술 및 ELB 기술과 패킷 생성률을 증가시켜 가며 비교한 결과, 평균 종단 간 지연이 데이터 패킷의 생성률이 10.5Gbps를 초과할 때까지 종단간 지연이 현저히 짧은 시간을 갖는 것을 확인할 수 있다.Referring to Figure 9, the horizontal axis of the graph represents the packet generation rate, and the vertical axis represents the average end-to-end delay. Here, the average end-to-end delay refers to the arrival time from the source satellite to the destination satellite. The proposed embodiment was compared with the comparative technologies, TLR and ELB, while increasing the packet generation rate. As a result, it was confirmed that the average end-to-end delay has a significantly shorter time until the data packet generation rate exceeds 10.5 Gbps.
도 10은 일 실시예에 따른 패킷 생성률을 변화하며 목적지에 도착한 평균 대기열 지연을 도시한 그래프이다.FIG. 10 is a graph showing the average queue delay at the destination as the packet generation rate changes according to one embodiment.
도 10을 참조하면, 그래프의 가로축은 패킷 생성률을 나타내고, 세로축은 평균 대기열 지연을 나타낸다. 여기서, 평균 대기열 지연은 패킷의 라우팅 경로에서 발생하는 대기열의 지연 시간의 합을 의미한다. 제안된 실시예(proposed)는 비교 대상 기술들인 TLR 기술 및 ELB 기술과 패킷 생성률을 증가시켜 가며 비교한 결과, 평균 대기열 지연이 데이터 패킷의 생성률이 10.5Gbps를 초과할 때까지 종단간 지연이 현저히 짧은 시간을 갖는 것을 확인할 수 있다.Referring to Figure 10, the horizontal axis of the graph represents the packet generation rate, and the vertical axis represents the average queuing delay. Here, the average queuing delay refers to the sum of the delay times of the queues that occur along the packet routing path. The proposed embodiment was compared with the comparative technologies, TLR and ELB, while increasing the packet generation rate. As a result, it was confirmed that the average queuing delay has a significantly shorter end-to-end delay time until the data packet generation rate exceeds 10.5 Gbps.
도 11은 일 실시예에 따른 패킷 생성률을 변화하며 전체 패킷의 평균 종단 간 지연을 도시한 그래프이다.FIG. 11 is a graph showing the average end-to-end delay of all packets as the packet generation rate changes according to one embodiment.
도 11을 참조하면, 그래프의 가로축은 패킷 생성률을 나타내고, 세로축은 전체 패킷의 평균 종단 간 지연을 나타낸다. 여기서, 패킷 손실을 반영하여 종단 간 지연을 비교하기 위해 손실된 패킷의 종단 간 지연은 최단 거리의 라우팅 경로에서 최대 대기열 지연을 갖는 것으로 간주한다. 제안된 실시예(proposed)는 비교 대상 기술들인 TLR 기술 및 ELB 기술과 패킷 생성률을 증가시켜 가며 비교한 결과, 평균 종단 간 지연이 현저히 짧은 시간을 갖는 것을 확인할 수 있다.Referring to Figure 11, the horizontal axis of the graph represents the packet generation rate, and the vertical axis represents the average end-to-end delay of all packets. Here, to compare the end-to-end delay by reflecting packet loss, the end-to-end delay of the lost packet is considered to have the maximum queuing delay on the shortest routing path. The proposed embodiment was compared with the comparative technologies, TLR and ELB, by increasing the packet generation rate, and it can be confirmed that the average end-to-end delay is significantly shorter.
도 12는 일 실시예에 따른 패킷 생성률을 변화하며 분산 인덱스를 도시한 그래프이다.FIG. 12 is a graph showing a distribution index while changing a packet generation rate according to one embodiment.
도 12를 참조하면, 그래프의 가로축은 패킷 생성률을 나타내고, 세로축은 분산 인덱스(DI: Distribution Index)를 나타낸다. 위성 간 링크(ISL)의 활용도는 분산 인덱스(DI)로 계산될 수 있으며, 하기의 수학식 7로 계산할 수 있다.Referring to Figure 12, the horizontal axis of the graph represents the packet generation rate, and the vertical axis represents the distribution index (DI). The utilization of the inter-satellite link (ISL) can be calculated using the distribution index (DI), as shown in Equation 7 below.
여기서, 전체 패킷의 수가개,번째 위성 간 링크(ISL) 사용 횟수가일 때이고, 분산 인덱스(DI)는 0에서 1사이의 값을 가질 수 있고, 위성 간 링크(ISL)의 사용 횟수가 모두 같은 경우, 분산 인덱스(DI)는 1이고, 특정 위성 간 링크(ISL)만 주로 사용되는 경우, 분산 인덱스(DI)는 감소한다.Here, the total number of packets is dog, The number of times the second inter-satellite link (ISL) was used , and the dispersion index (DI) can have a value between 0 and 1. When the number of uses of all inter-satellite links (ISLs) is the same, the dispersion index (DI) is 1, and when only a specific inter-satellite link (ISL) is primarily used, the dispersion index (DI) decreases.
제안된 실시예(proposed)는 비교 대상 기술들인 TLR 기술 및 ELB 기술과 패킷 생성률을 증가시켜 가며 비교한 결과, 분산 인덱스(DI)가 높게 나타나는 것을 확인할 수 있다.The proposed embodiment is compared with the comparative technologies, TLR technology and ELB technology, by increasing the packet generation rate, and it can be confirmed that the distribution index (DI) is high.
도 13을 참조하면, 그래프의 가로축은 패킷이 종단 간에 전달되는 대륙에서 주요 도시들을 나타내며, 세로축은 평균 종단 간 지연을 나타낸다. 각 대륙의 주요 도시를 꼽아 세 가지 라우팅 방식의 두 지역 간 전달되는 패킷의 평균 종단 간 지연을 비교한 그래프이다. 대표 주요 도시의 패킷은 뉴욕 (NYC) → 서울 (SEL), 도쿄 (TYO) → 런던 (LON), 파리 (PAR) → 요하네스버그 (JNB), 카이로 (CAI) → 퍼스 (PER), 시드니 (SYD) → 부에노스아이레스 (BUE), 상파울루 (GRU) → 로스앤젤레스 (LAX)이다.Referring to Figure 13, the horizontal axis of the graph represents major cities on the continent where packets are transmitted end-to-end, and the vertical axis represents the average end-to-end delay. This graph compares the average end-to-end delay of packets transmitted between two regions using three routing methods, selecting major cities on each continent. The packets from representative major cities are New York (NYC) → Seoul (SEL), Tokyo (TYO) → London (LON), Paris (PAR) → Johannesburg (JNB), Cairo (CAI) → Perth (PER), Sydney (SYD) → Buenos Aires (BUE), and São Paulo (GRU) → Los Angeles (LAX).
제안된 실시예(proposed)는 비교 대상 기술들인 TLR 기술 및 ELB 기술과 주요 도시간 데이터 패킷의 전송에 따른 평균 종단 간 지연을 비교한 결과, 일부에서는 성능이 우수하며, 나머지에서도 비교 대상 기술들 대비 크게 저하되지 않는 것을 확인할 수 있다.The proposed embodiment compares the average end-to-end delay for transmission of major intercity data packets with the comparative technologies, TLR technology and ELB technology, and it can be confirmed that the performance is superior in some cases and does not deteriorate significantly compared to the comparative technologies in the remaining cases.
이상의 실시예들에서 사용되는 '~부'라는 용어는 소프트웨어 또는 FPGA(field programmable gate array) 또는 ASIC 와 같은 하드웨어 구성요소를 의미하며, '~부'는 어떤 역할들을 수행한다. 그렇지만 '~부'는 소프트웨어 또는 하드웨어에 한정되는 의미는 아니다. '~부'는 어드레싱할 수 있는 저장 매체에 있도록 구성될 수도 있고 하나 또는 그 이상의 프로세서들을 재생시키도록 구성될 수도 있다. 따라서, 일 예로서 '~부'는 소프트웨어 구성요소들, 객체지향 소프트웨어 구성요소들, 클래스 구성요소들 및 태스크 구성요소들과 같은 구성요소들과, 프로세스들, 함수들, 속성들, 프로시저들, 서브루틴들, 프로그램특허 코드의 세그먼트들, 드라이버들, 펌웨어, 마이크로코드, 회로, 데이터, 데이터베이스, 데이터 구조들, 테이블들, 어레이들, 및 변수들을 포함한다.The term '~ unit' used in the above embodiments means a software or hardware component such as an FPGA (field programmable gate array) or an ASIC, and the '~ unit' performs certain roles. However, the '~ unit' is not limited to software or hardware. The '~ unit' may be configured to be on an addressable storage medium or may be configured to play one or more processors. Thus, as an example, the '~ unit' includes components such as software components, object-oriented software components, class components, and task components, processes, functions, attributes, procedures, subroutines, segments of program code, drivers, firmware, microcode, circuits, data, databases, data structures, tables, arrays, and variables.
구성요소들과 '~부'들 안에서 제공되는 기능은 더 작은 수의 구성요소들 및 '~부'들로 결합되거나 추가적인 구성요소들과 '~부'들로부터 분리될 수 있다.The functionality provided within the components and '~sub-components' may be combined into a smaller number of components and '~sub-components' or separated into additional components and '~sub-components'.
뿐만 아니라, 구성요소들 및 '~부'들은 디바이스 또는 보안 멀티미디어카드 내의 하나 또는 그 이상의 CPU 들을 재생시키도록 구현될 수도 있다.Additionally, components and '~parts' may be implemented to regenerate one or more CPUs within a device or secure multimedia card.
상술된 실시예들은 예시를 위한 것이며, 상술된 실시예들이 속하는 기술분야의 통상의 지식을 가진 자는 상술된 실시예들이 갖는 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 쉽게 변형이 가능하다는 것을 이해할 수 있을 것이다. 그러므로 상술된 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다. 예를 들어, 단일형으로 설명되어 있는 각 구성 요소는 분산되어 실시될 수도 있으며, 마찬가지로 분산된 것으로 설명되어 있는 구성 요소들도 결합된 형태로 실시될 수 있다.The embodiments described above are provided for illustrative purposes only, and those skilled in the art will readily appreciate that the embodiments described above can be readily modified into other specific forms without altering the technical concepts or essential characteristics of the embodiments described above. Therefore, the embodiments described above should be understood as illustrative in all respects and not restrictive. For example, components described as being single may be implemented in a distributed manner, and similarly, components described as being distributed may be implemented in a combined manner.
본 명세서를 통해 보호 받고자 하는 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미 및 범위 그리고 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태를 포함하는 것으로 해석되어야 한다.The scope of protection sought through this specification is indicated by the claims described below rather than the detailed description above, and should be interpreted to include all changes or modifications derived from the meaning and scope of the claims and their equivalent concepts.
100: 위성 라우팅 장치101: 위성 라우터
102: 위성 송수신기110, 120, 130: 위성들
111, 121, 131: 메모리들112, 122, 132: 제어부들
113, 123, 133: 송수신기들100: Satellite Routing Devices 101: Satellite Routers
102: Satellite transceiver 110, 120, 130: Satellites
111, 121, 131: Memories 112, 122, 132: Control units
113, 123, 133: Transmitters and receivers
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020230180902AKR102849664B1 (en) | 2023-12-13 | 2023-12-13 | Satellite routing apparatus and method for distributed routing considering imbalanced traffic distribution thereof |
| PCT/KR2024/096903WO2025127856A1 (en) | 2023-12-13 | 2024-12-13 | Satellite routing device that considers unbalanced traffic distribution, and distributed routing method therefor |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| KR1020230180902AKR102849664B1 (en) | 2023-12-13 | 2023-12-13 | Satellite routing apparatus and method for distributed routing considering imbalanced traffic distribution thereof |
| Publication Number | Publication Date |
|---|---|
| KR20250090821A KR20250090821A (en) | 2025-06-20 |
| KR102849664B1true KR102849664B1 (en) | 2025-08-21 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| KR1020230180902AActiveKR102849664B1 (en) | 2023-12-13 | 2023-12-13 | Satellite routing apparatus and method for distributed routing considering imbalanced traffic distribution thereof |
| Country | Link |
|---|---|
| KR (1) | KR102849664B1 (en) |
| WO (1) | WO2025127856A1 (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20120263042A1 (en)* | 2010-10-04 | 2012-10-18 | Telcordia Technologies, Inc. | Method and system for determination of routes in leo satellite networks with bandwidth and priority awareness and adaptive rerouting |
| JP2019514295A (en)* | 2016-04-14 | 2019-05-30 | テレサット カナダ | Dual LEO satellite system and method for global coverage |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR101408455B1 (en) | 2012-11-29 | 2014-06-17 | 아주대학교산학협력단 | Random access load control method of satellite communication |
| KR102407992B1 (en)* | 2022-04-12 | 2022-06-13 | 한화시스템(주) | Satellite repeater system for low orbit inter-satellite ip data transmission and mtehod for routing thereof |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US20120263042A1 (en)* | 2010-10-04 | 2012-10-18 | Telcordia Technologies, Inc. | Method and system for determination of routes in leo satellite networks with bandwidth and priority awareness and adaptive rerouting |
| JP2019514295A (en)* | 2016-04-14 | 2019-05-30 | テレサット カナダ | Dual LEO satellite system and method for global coverage |
| Title |
|---|
| Tie Liu et al., "Load Balancing Routing Algorithm of Low-Orbit Communication Satellite ...," Wireless Communications and Mobile Computing, (2021)* |
| Publication number | Publication date |
|---|---|
| KR20250090821A (en) | 2025-06-20 |
| WO2025127856A1 (en) | 2025-06-19 |
| Publication | Publication Date | Title |
|---|---|---|
| Handley | Delay is not an option: Low latency routing in space | |
| CN110505153B (en) | Heaven and earth integrated hybrid routing method | |
| CN111148161B (en) | Low-orbit satellite constellation inter-satellite load route balancing method and system | |
| US10264509B2 (en) | Mobile network node routing | |
| CN112333109B (en) | Ant colony optimization-based load balancing routing method in low-orbit satellite network | |
| Liu et al. | A low-complexity routing algorithm based on load balancing for LEO satellite networks | |
| US9973267B2 (en) | Satellite constellation | |
| Zhu et al. | Software defined routing algorithm in LEO satellite networks | |
| Liu et al. | A low-complexity probabilistic routing algorithm for polar orbits satellite constellation networks | |
| CN111294108B (en) | An Efficient Routing Method for Orthogonal Circular Orbit Configuration Satellite Constellation | |
| CN109586785B (en) | Routing strategy for low-orbit satellite network based on K shortest path algorithm | |
| Long | Satellite network robust QoS-aware routing | |
| Yang | Low earth orbit (LEO) mega constellations-satellite and terrestrial integrated communication networks. | |
| CN105228209A (en) | A kind of distributed GEO/LEO hybrid network method for routing based on dummy node | |
| Wang et al. | A load balanced routing algorithm based on congestion prediction for LEO satellite networks | |
| Barbosa et al. | A comparative evaluation of TCP congestion control schemes over low-Earth-orbit (LEO) satellite networks | |
| Guo et al. | LEO satellite routing algorithm in software defined space terrestrial integrated network | |
| Hou et al. | The QoS guaranteed routing strategy in low earth orbit satellite constellations | |
| Kawamoto et al. | Assessing packet delivery delay in multi-layered satellite networks | |
| KR102849664B1 (en) | Satellite routing apparatus and method for distributed routing considering imbalanced traffic distribution thereof | |
| Xu et al. | A hybrid routing algorithm in terrestrial-satellite integrated network | |
| Liu et al. | Enabling ubiquitous and efficient data delivery by leo satellites and ground station networks | |
| Nag et al. | Designing a disruption tolerant network for reactive spacecraft constellations | |
| Tian et al. | An efficient QoS-aware routing algorithm for LEO polar constellations | |
| JP7632652B2 (en) | Wireless communication system, wireless communication method, network controller, and network control program |
| Date | Code | Title | Description |
|---|---|---|---|
| PA0109 | Patent application | St.27 status event code:A-0-1-A10-A12-nap-PA0109 | |
| PA0201 | Request for examination | St.27 status event code:A-1-2-D10-D11-exm-PA0201 | |
| D13-X000 | Search requested | St.27 status event code:A-1-2-D10-D13-srh-X000 | |
| PE0902 | Notice of grounds for rejection | St.27 status event code:A-1-2-D10-D21-exm-PE0902 | |
| E13-X000 | Pre-grant limitation requested | St.27 status event code:A-2-3-E10-E13-lim-X000 | |
| P11-X000 | Amendment of application requested | St.27 status event code:A-2-2-P10-P11-nap-X000 | |
| PG1501 | Laying open of application | St.27 status event code:A-1-1-Q10-Q12-nap-PG1501 | |
| PE0701 | Decision of registration | St.27 status event code:A-1-2-D10-D22-exm-PE0701 | |
| PR0701 | Registration of establishment | St.27 status event code:A-2-4-F10-F11-exm-PR0701 | |
| PR1002 | Payment of registration fee | St.27 status event code:A-2-2-U10-U11-oth-PR1002 Fee payment year number:1 | |
| PG1601 | Publication of registration | St.27 status event code:A-4-4-Q10-Q13-nap-PG1601 |