분산 네트워크용 결정론적 2차원 격자 + 행렬 아핀 계산 기반 다중 경로 라우팅과 지향성 가십을 구현하는 방법

분산 네트워크용 결정론적 2차원 격자 + 행렬 아핀 계산 기반 다중 경로 라우팅과 지향성 가십을 구현하는 방법작성자: bokkamsun@gmail.com요약: 모든 피어를 같은 시드로 같은 격자에 배치한다. 같은 격자 위에서 최단 1경로 + 좌/우 우회 2경로를 결정론적으로 만든다. 메시지는 경로를 내장해 다음 노드 한 칸만 전진한다. 실패나 장애가 보이면 전방 이웃만 선택하는 지향성 가십을 짧게 켜서 커버리지를 보강한다. 이로써 재현성, 도달성, 대역 효율을 동시에 확보한다.완전한 결정론성: 동일한 시드와 피어 집합이면 모든 노드가 똑같은 격자/경로를 재현한다.구성적 다중경로: 최단 BFS에 아핀 편향 T(θ,k)T(θ,k) 로 좌/우 경로를 의도적으로 합성한다.경로 내장형 포워딩: 메시지에 path[]를 싣고 다음 IP 한 칸만 전진한다.경량 구현, 높은 이식성: 8-이웃 BFS, 격자 스냅, 간단 행렬 연산만으로 구동한다.기존 대비 차별성: 무작위/거미줄형 그래프 탐색이 아니라 결정론적 2D 임베딩 + 선형대수 기반 편향으로 경로를 재현 가능하게 합성한다.실전성 검증: 채굴/투표/검증 흐름에 3경로를 동시에 적용해 혼잡/차단/부분장애에서도 도달률을 실사용 수준으로 확보한다.본 발명은 공통 시드와 IP로 모든 피어를 결정론적으로 정방 격자에 배치한다. 같은 격자 위에서 최단 경로(BFS) 1개와 아핀 편향 T(θ,k)T(θ,k) 로 만든 좌/우 우회 경로 2개를 함께 산출해 항상 3경로를 제공한다. 메시지는 이 경로들을 path[]에 내장하고 각 홉은 다음 IP 한 칸만 전진하므로 중간 판단이 없고 루프가 구조적으로 차단된다. 그리고 지향성 가십은 기존 가십을 대체한다. 전방 이웃만 선택하고 짧은 TTL로 확산해 팬아웃 3 이하를 유지하면서 전역 전파를 수행한다. 즉, 내장 3경로는 확정 경로 전달, 지향성 가십은 대규모 전파의 기본 엔진이다. 입력이 같으면 모든 노드가 동일 경로/동일 전파 패턴을 재현하므로 테스트/감사가 용이하고, 혼잡/검열/부분 장애에서도 안정적 전파와 낮은 비용을 동시에 달성한다.1. 개요본 기술은 무작위 전파 대신 결정론과 경로 내장을 사용한다. 절차는 다음과 같다.결정론 정렬: 공통 시드와 주소로 모두가 같은 순서를 만든다.격자 배치: 그 순서를 바둑판 격자에 채운다.기본 경로 생성: 격자 8이웃 그래프에서 최단 경로를 구한다.우회 경로 합성: 진행축 기준 아핀 편향으로 좌/우 중간점을 잡고, 두 구간 최단을 이어 우회 2경로를 얻는다.경로 내장 전달: 메시지에 path[]를 싣고 다음 노드 한 칸만 보낸다. 중간 판단이 없어 루프와 지터가 줄어든다.지향성 가십: 기존가십과 섞어 쓰거나, 전달 실패/지연 징후가 있으면 전방 이웃만 선택해 짧은 TTL로 확산한다. 필요할 때만 켜 대역 스파이크를 막는다.중복 억제: 송신 측은 동일 첫 홉을 제거하고, 수신 측은 최근 ID 집합으로 중복을 드롭한다.2. 기술분야분산 네트워크와 블록체인 환경에서의 결정론적 토폴로지 구성과 다중 경로 메시지 라우팅.3. 배경기술과 차별성기존 임의 전파는 경로가 흔들려 재현성이 낮다.격자/메쉬 기반 탐색은 단일 최단 중심으로 우회 설계가 빈약하다.경로를 메시지에 내장하지 않으면 중간 홉의 로컬 상태에 경로가 좌우된다.본 발명은 다음에서 차별화된다.결정론 격자 사상으로 모든 노드가 동일 토폴로지를 재현한다.행렬 아핀 편향으로 좌/우로 굽은 우회 경로를 수식적으로 설계하고, 격자 스냅과 두 구간 최단 결합으로 이산화한다.경로 내장형 전달과 양단 중복 억제로 도달성과 효율을 동시에 달성한다.4. 용어와 기호피어 수 NN, 정렬열 v=[v0,…,vN−1]v=[v0,…,vN−1] 이고, 격자 한 변 길이 SS와 좌표는 다음과 같다.S=⌈N⌉S=⌈N⌉r=⌊iS⌋r=⌊Si⌋c=imodSc=imodS격자 좌표 벡터는 p⃗=[cr]p=[cr] 이다.여덟 이웃은 N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)}N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)} 이다.정의: 결정론 임계값 함수(일반형) 에서 임계값은 hp=computeThreshold(ip(p),seed)∈[0,2w)hp=computeThreshold(ip(p),seed)∈[0,2w) 로 둔다.정렬 키는 (hp,ip(p))(hp,ip(p)) 이며 오름차순 사전식으로 정렬한다.구현 예(해시 XOR 기반) 은 다음과 같다.hp=LOWw(F(seed)⊕F(ip(p)))hp=LOWw(F(seed)⊕F(ip(p)))여기서 FF 는 고정 해시 함수, ⊕⊕ 는 비트 XOR, LOWw(⋅)LOWw(⋅) 는 하위 ww비트 취함이다.5. 발명의 요지5.1 결정론 정렬모든 노드는 동일한 seed와 피어 주소 집합에 대해 다음 임계값을 계산한다.hp=LOWw(F(seed)⊕F(ip(p)))hp=LOWw(F(seed)⊕F(ip(p)))정렬은 오름차순 (hp,ip(p))(hp,ip(p)) 기준으로 수행한다. 입력이 같으면 결과가 항상 같으므로 전 노드가 동일한 정렬열을 얻고, 이를 S×SS×S 격자에 순차 배치하므로 토폴로지도 전 노드에서 동일하다.데카르트 좌표토폴로지 구성을 결정론적 격자 배치하여 행렬연산이 가능하다.5.2 격자 사상정렬 순서 ii 번째 피어를 (r,c)(r,c) 에 순차 배치한다. 빈 칸은 존재하지 않는 노드로 간주해 자동 회피된다.5.3 최단 경로여덟 이웃 무가중 그래프에서 시작 p⃗sps 와 목표 p⃗gpg 사이 최단 홉수 경로 P0P0 를 산출한다.5.4 로컬-법선 평행이동 기반 편향진행축을 기준으로 로컬 좌표에서 법선 방향(yy축) 으로 αα 만큼 평행이동한 편향 중간점을 만든 뒤, 두 구간 최단을 이어 좌/우 대체 경로를 얻는다.6. 수학적 구성6.1 진행각과 변위시작점과 목표점은 각각 p⃗s=[csrs]ps=[csrs], p⃗g=[cgrg]pg=[cgrg] 이다.변위는 d⃗=p⃗g−p⃗sd=pg−ps 이고, 진행각은 θ=atan2(rg−rs,cg−cs)θ=atan2(rg−rs,cg−cs) 이다.6.2 진행축 정렬과 로컬-법선 평행이동회전행렬 RR(θ)=(cos⁡θ−sin⁡θsin⁡θcos⁡θ)R(θ)=(cosθsinθ−sinθcosθ)1. 진행각으로 정렬한다.[xLyL]=R(−θ)(p⃗s+td⃗−p⃗s),yL←yL±α,p~m(±)=p⃗s+R(θ)[xLyL].[xLyL]=R(−θ)(ps+td−ps),yL←yL±α,p~m(±)=ps+R(θ)[xLyL].2. 로컬 법선(yLyL)으로 ±α±α 평행이동한다.3. 역정렬하여 월드 좌표로 복귀한다.여기서 d⃗=p⃗g−p⃗sd=pg−ps, t∈(0,1)t∈(0,1) 이며 코드 기본은 t=0.5t=0.5 이다.부연: 기존 문서의 T(θ,k)=R(θ),Sx(k),R(−θ)T(θ,k)=R(θ),Sx(k),R(−θ) 표기는 개념 설명이며, 실제 구현은 로컬-법선 평행이동으로 동치 효과를 낸다.6.2a 동차좌표 버전현재 문서는 작성된 코드와 일관성을 유지하기위해, 동차좌표 없이 "로컬-법선 평행이동"으로 구현하였다. 추가로 이해를 돕기 위해 동일 동작을 3x3 동차 행렬로도 첨부한다.동차 변환T(a,b)=[10a01b001],R(θ)=[cos⁡θ−sin⁡θ0sin⁡θcos⁡θ0001]T(a,b)=100010ab1,R(θ)=cosθsinθ0−sinθcosθ0001편향 중간점 생성 행렬M±=T(cs,rs)R(θ)T(t∥d⃗∥,±α)R(−θ)T(−cs,−rs)M±=T(cs,rs)R(θ)T(t∥d∥,±α)R(−θ)T(−cs,−rs)적용p~m(±)=(M±[cs,rs,1]T)xy,p^m(±)=clipRound(p~m(±))p~m(±)=(M±[cs,rs,1]T)xy,p^m(±)=clipRound(p~m(±))동치성(요지): 위 전개를 풀면p~m(±)=p⃗s+td⃗±αn^p~m(±)=ps+td±αn^즉 본문 식(6.3)과 완전히 동일하다. 여기서 d⃗=p⃗g−p⃗s,n^=[−sin⁡θ,cos⁡θ]Td=pg−ps,n^=[−sinθ,cosθ]T.선택 확장(개념용): 과거 표기 T(θ,k)=R(θ)Sx(k)R(−θ)T(θ,k)=R(θ)Sx(k)R(−θ)를 쓰고 싶다면,M±=TR(θ)Sx(k)T(t∥d⃗∥,±α)R(−θ)T−1M±=TR(θ)Sx(k)T(t∥d∥,±α)R(−θ)T−1처럼 전개 지점에 끼우면 된다. 본 구현은 Sx(k)=ISx(k)=I로 두고 평행이동만 사용한다.구현: 동차 방식을 택해도 마지막은 동일하게 clipRound()와 경계 클램프를 적용한다.6.3 편향 중간점과 격자 스냅법선 단위벡터는 n^=[−sin⁡θcos⁡θ]n^=[−sinθcosθ] 이다.편향 세기는 α=0.6,k,∥d⃗∥α=0.6,k,∥d∥ 이며 기본 t=0.5t=0.5 를 사용한다.연속 공간상의 편향 중간점과 격자 반올림/경계 클램프는p~m(±)=p⃗s+td⃗±αn^,p^m(±)=clipRound(p~m(±)).p~m(±)=ps+td±αn^,p^m(±)=clipRound(p~m(±)).p^m(±)p^m(±) 이 시작 또는 목표와 같은 셀이면, 법선 n^n^ 방향으로 bump=sign(α)⋅max⁡(1,0.1∥d⃗∥)bump=sign(α)⋅max(1,0.1∥d∥) 만큼 추가 평행이동 후 다시 clipRound 한다.해당 셀이 비어 있으면 반경 ≤3≤3 내에서 가장 먼저 발견되는 유효 셀을 대체 선택한다.6.4 두 구간 최단 결합편향 경로는P±=ShortestPath(p⃗s,p^m(±))⊕ShortestPath(p^m(±),p⃗g)P±=ShortestPath(ps,p^m(±))⊕ShortestPath(p^m(±),pg)UBMS 3 path [ t 값이 0.9 ]이며, ⊕⊕ 는 중간점 중복을 한 번만 포함하는 연결이다(코드에서 두 번째 구간은 인덱스 1부터 붙임).7. 지향성 가십 전파(Directional Gossip) — 결정론 격자 기반 부채꼴 전파7.1 정의격자 좌표를 p⃗=[cr]Tp=[cr]T 로 두고, 여덟 이웃 집합은N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)}.N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)}.8이웃(N8N8)방향 부호 벡터 u⃗=[sxsy]T∈{−1,0,1}2∖{(0,0)}u=[sxsy]T∈{−1,0,1}2∖{(0,0)} 를 메시지 필드 op3="sx,sy"로 내장한다. 이는 시작점과 발신자 사이 상대 위치의 부호 정규화:sx=sign⁡(cnbr−csrc),sy=sign⁡(rnbr−rsrc)sx=sign(cnbr−csrc),sy=sign(rnbr−rsrc)sign⁡(z)={1,z>00,z=0−1,z<0sign(z)=⎩⎨⎧1,0,−1,z>0z=0z<07.2 전파 규칙(부채꼴 전방 이웃)현재 홉이 p⃗p 일 때 전방 이웃 집합을Fu⃗(p⃗)={p⃗+δ⃗∣δ⃗∈N8,δ⃗⋅u⃗>0}Fu(p)={p+δ∣δ∈N8,δ⋅u>0}로 정의한다. 즉, u⃗u 와의 내적이 양수인 이웃만 선택.축 방향 (1,0)(1,0): (1,−1),(1,0),(1,1)(1,−1),(1,0),(1,1) 로 3분기.축 방향 (0,1)(0,1): (−1,1),(0,1),(1,1)(−1,1),(0,1),(1,1) 로 3분기.대각 (1,1)(1,1): (1,1),(1,0),(0,1)(1,1),(1,0),(0,1) 로 3분기.u=(1,0)u=(1,1)수신 노드는 TTL←TTL−1TTL←TTL−1 후 유효 피어만 골라 Fu⃗(p⃗)Fu(p) 로 송신하며, 입력 FD는 제외.7.2a 직관 설명: ΔΔ(델타)와 u⃗u(전진축)ΔΔ = "한 칸 이동 후보." 현재 위치 p⃗p에서 p⃗+Δp+Δ로 1홉 이동한다.u⃗u = (sx, sy) = "가고 싶은 큰 방향의 부호." sx, sy ∈{−1,0,1}∈{−1,0,1}, (0,0)은 금지.전방 선택 규칙: 점수 = dx⋅sx+dy⋅sydx⋅sx+dy⋅sy점수 > 0: 전방 이웃. 보낸다.점수 = 0: 측면. 전방이 없을 때만 보조로 쓴다(7.7).점수 < 0: 후방. 버린다.요약: u⃗u는 "전진축", ΔΔ는 "한 걸음". dx⋅sx+dy⋅sy>0dx⋅sx+dy⋅sy>0 인 걸음만 전송한다.7.3 TTL 설정(격자 대각 기반)격자 한 변 S=⌈N⌉S=⌈N⌉, 전체 대각 길이D=(S−1)2+(S−1)2D=(S−1)2+(S−1)2지향성 가십의 TTL은TTL=max⁡(3,⌊ρ⋅D+0.5⌋),ρ∈(0,1],기본 ρ=0.8.TTL=max(3,⌊ρ⋅D+0.5⌋),ρ∈(0,1],기본 ρ=0.8.7.4 메시지 형식op3="sx,sy": 방향 벡터 u⃗u.ttl: 위 식의 TTL.messageId: 고유 식별자.payload: 송신자 상태.7.5 결정론 시작 방향 선택발신 노드가 자기 8이웃 중 선택한 시작 이웃 (cnbr,rnbr)(cnbr,rnbr) 에 대해u⃗=[sign⁡(cnbr−cself)sign⁡(rnbr−rself)].u=[sign(cnbr−cself)sign(rnbr−rself)].선택 정책(라운드로빈, 해시 최소 등)을 고정하면 동일 입력에서 결정론적 시작 방향이 재현된다.7.6 중복 억제각 노드는 messageId 또는 (header, op3, payload) 해시로 최근 수신 집합을 유지하고 중복 패킷을 드롭한다. 동일 첫 홉을 공유하는 분기는 송신 측에서 하나만 남긴다.7.7 경계/결손 노드 처리격자 경계 또는 결손(빈 셀)에서 전방 이웃이 비면 전파를 중단하지 않고 대체 전방 집합을 선택한다.Fu⃗∗(p⃗)=(Fu⃗(p⃗)∩V)∪{p⃗+δ⃗∣δ⃗∈N8,δ⃗⋅u⃗=0,p⃗+δ⃗∈V}Fu∗(p)=(Fu(p)∩V)∪{p+δ∣δ∈N8,δ⋅u=0,p+δ∈V}여기서 VV 는 유효 노드 집합이다. 즉, 우선 전방(δ⃗⋅u⃗>0δ⋅u>0)을 사용하고, 없을 때만 측면(=0=0)을 보조로 사용한다.7.8 종료 조건과 루프 방지TTL←TTL−1,if TTL≤0 then drop.TTL←TTL−1,if TTL≤0 then drop.최근 수신 집합 RR 에 대해if messageId∈R then drop,else R←R∪{messageId}.if messageId∈R then drop,else R←R∪{messageId}.전방 선택은 δ⃗⋅u⃗≥0δ⋅u≥0 만 허용하므로 역방향 전파가 구조적으로 배제된다.7.9 도달률 하한(커버리지)와 TTL 하한격자 변 SS, 대각 길이 D=2(S−1)D=2(S−1). ρ∈(0,1]ρ∈(0,1] 에 대해TTLmin⁡=max⁡(3,⌊ρD+0.5⌋)TTLmin=max(3,⌊ρD+0.5⌋)을 쓰면, 장애 비율이 ≤(1−ρ)≤(1−ρ) 인 균질 환경에서 부채꼴 전선의 도달률 하한이 유지된다. ρρ 를 늘리면 커버리지 증가, 대역비용 증가.7.10 파라미터 튜닝 지침팬아웃 상한: 각 홉 송신수 ≤3≤3 유지. 필요 시 샘플링 확률 p∈(0,1]p∈(0,1] 도입.E[Mdir]≈3pTTL.E[Mdir]≈3pTTL.TTL = 3 이웃 커버리지ρρ: 평시 0.6 ~ 0.8, 장애 구간 감지 시 일시적으로 0.9 이상.최근 집합 크기: 윈도 길이 W≥TTLW≥TTL 로 설정.7.11 보안/검열 회피 고려방향 고정 공격 완화: 시작 방향 u⃗u 를 결정론적이되 라운드 시드로 주기 갱신.u⃗t=choose(N8∖{(0,0)};seedt,N8)ut=choose(N8∖{(0,0)};seedt,N8)동일 라운드 입력에 대해 전 노드가 같은 u⃗tut 를 재현한다.헤더 위/변조 검출: (op3, ttl, payload) 에 대한 경량 MAC 첨부.7.12 성능 상한과 기대치 정리총 송신 상한:Mdir≤3TTL,TTL≤ρ2(S−1)=Θ(N)Mdir≤3TTL,TTL≤ρ2(S−1)=Θ(N)전역 중복 포함 절댓값의 보수 상한은Mdirdup≤3NMdirdup≤3N이지만, 최근 집합과 측면 대체 규칙으로 실측은 Θ(N)Θ(N) 에 근접한다.7.13 호환성: 경로 전파와의 병행 운용동일 메시지 ID에 대해 경로 전파(6절) 를 우선, 지향성 가십은 타임아웃 TfallbackTfallback 후 보조 가동:if not delivered by Tfallback⇒start directional gossip with TTL=TTLmin⁡.if not delivered by Tfallback⇒start directional gossip with TTL=TTLmin.증폭 방지를 위해 송신 측은 동일 첫 홉 중복을 제거한다.8. 지향성 가십의 효과경로 다양성: 8방향 중 선택된 u⃗u 기준 부채꼴 전방 3분기로 검열/혼잡 회피 확률 상승.결정론성: 격자 사상과 시작 방향 정책 고정으로 재현 가능.단순성: 조건 δ⃗⋅u⃗>0δ⋅u>0 만으로 전방 선별.8.1. 일반적인 gossip 전파일반 gossip ttl = 1일반 gossip ttl = 2일반 gossip ttl = 3일반 gossip ttl = 4일반 gossip ttl = 5일반 gossip ttl = end음영구역 발생: 무작위 전파에 가까운 일반적인 가십전파는 필연적인 음영구역 발생.8.2. 지향성 gossip 전파지향성 gossip ttl = 1지향성 gossip ttl = 3지향성 gossip ttl = 5지향성 gossip ttl = 7지향성 gossip ttl = 11지향성 gossip ttl = end치밀하고 체계적인 전파: 각 노드는 방향벡터를 기준으로 전파방향을 설정, 역전파 중복전파 등이 최소화됨.9. 경로 내장 전달과 중복 억제메시지는 전체 경로와 길이를 포함하고 각 홉은 자기 다음 노드로만 전진한다. 송신 측은 세 경로의 첫 번째 다음 홉이 같으면 하나만 남긴다. 수신 측은 최근 본 식별자 또는 경로/내용 해시로 중복을 억제한다. 이중 억제는 증폭을 막으면서 3경로의 도달성 이점을 유지한다.10. 장애와 혼잡 상황에서의 동작 이유좌/우 편향 경로는 기하학적으로 분리된 통로를 제공한다. 편향 경로는 격자 위 두 구간 최단의 합성이어서 불필요한 우회가 작다. ∣k∣∣k∣ 가 커지면 경로 상관이 낮아져 검열/혼잡 회피에 유리하지만 지연은 증가한다. 기본적으로 t=12t=21 가 균형 잡힌 분산을 준다.11. 실시예동일 시드/주소 집합이면 모든 노드가 동일 격자 배치와 동일 3경로를 재현한다. 편향 강도 ∣k∣∣k∣ 를 조절하면 좌/우 경로의 분산 폭이 달라진다. 격자 끝 빈 칸은 자동 회피되며, 편향 중간점이 빈 칸이면 근접 유효 셀 대체로 경로 생성을 지속한다. 기본값은 t=0.5t=0.5, α=0.6,k,∥d⃗∥α=0.6,k,∥d∥ 이다.12. 산업상 이용가능성AI 분산노드: 분산네트워크 환경에서 AI노드간의 통신.블록체인 합의: 투표/검증 신호를 3경로로 동시 전파해 정족수 도달 안정성을 높인다.공개 피어 전파: 꼬리 지연과 실패율을 낮춘다.사물망/현장망/애드혹망: 간섭/단절에도 즉시 우회한다.오버레이/서비스 메쉬: 하부망과 무관하게 응용 계층에서 경로를 고정/내장한다.운영 가이드: 시드는 라운드/시간 단위로 고정해 동일 격자를 재현한다. 편향 강도 kk 는 지연 중심이면 작게, 내결함성 중심이면 크게 정한다. 송신/수신 양단 억제로 중복 최소화. 메시지 길이는 경로 길이와 동일로 설정해 루프를 차단한다.13. 성능과 복잡도격자 면적은 S2S2 이고, 최단 탐색의 시간 복잡도는 대략 O(S2)O(S2) 이다. 본 발명에서 제시하는 방법으로 세 경로 산출은 최단 1회와 편향 각 2회의 두 구간 결합으로 상수배 비용 증가에 그친다.13.1 모델지향성 가십 길이 척도: D=2(S−1)=Θ(N)D=2(S−1)=Θ(N).TTL 상한: TTL≤ρDTTL≤ρD.13.2 경로 내장 3-경로 전파경로 수: 3.경로 길이: 각 Θ(N)Θ(N).총 송신 수: Mpath≈3D=Θ(N).Mpath≈3D=Θ(N).중복 없음. 지연: Θ(N)Θ(N) 홉.13.3 지향성 가십각 홉 전방 이웃 ≤3≤3만 1회 송신.총 송신 수 상한: Mdir≤3N=Θ(N).Mdir≤3N=Θ(N).중복은 최근 ID로 억제. 지연: Θ(N)Θ(N) 홉.13.4 전통 가십(비교 기준)팬아웃 g≥2g≥2, 라운드 수 Θ(log⁡N)Θ(logN).총 송신 수(중복 포함): Mepi=Θ(gNlog⁡N).Mepi=Θ(gNlogN).13.5 정량 예시N=104,ρ=0.8,g=3N=104,ρ=0.8,g=3 가정.D≈0.8⋅2⋅(100−1)≈112D≈0.8⋅2⋅(100−1)≈112.경로 전파: Mpath≈3D≈336Mpath≈3D≈336.지향성 가십: Mdir≤3N=30,000Mdir≤3N=30,000.전통 가십: Mepi≈gNlog⁡2N≈3⋅104⋅13.3≈399,000Mepi≈gNlog2N≈3⋅104⋅13.3≈399,000.13.6 비용/지연 트레이드오프대역 효율: Mpath≪Mdir<MepiMpath≪Mdir<Mepi.도달성/내결함성: 전통 ≥≥ 지향성 >> 경로.지연: 전통 O(log⁡N)O(logN), 경로/지향성 O(N)O(N).재현성/제어성: 경로/지향성은 결정론적, 전통은 비결정적.13.7 운용 권고평시: 경로 3개로 전역 신호 전달(대역 최소).장애/검열 구간 탐지 시: 지향성 가십 보조 활성화로 커버리지 확보.전통 가십은 피크/중복 비용이 커 상시 운용 비권장.14. 청구항청구항 1결정론 정렬/정방 격자 사상을 수행하고, 격자 여덟 이웃 그래프에서 최단 경로 P0P0 를 산출하며, 진행축 정렬-로컬 법선 평행이동-역정렬 변환을 통해 편향 중간점 p^mp^m 을 생성하고, 시작-중간점, 중간점-목표의 두 구간 최단을 연결하여 좌/우 편향 경로 P±P± 를 생성한 뒤, 이를 P0P0 와 함께 제공하는 다중 경로 라우팅 방법.청구항 2편향 중간점이 비어 있거나 유효하지 않을 때 반경 확장으로 근접 유효 셀을 대체 선택하여 편향 경로 생성을 유지하는 방법.청구항 3메시지에 전체 경로와 길이를 포함하여 각 홉에서 다음 노드로만 전진하도록 하여 루프를 억제하고 경로 재현성을 확보하는 방법.청구항 4송신 측에서 첫 번째 다음 홉이 같은 경로를 제거하고, 수신 측에서 최근 본 식별자 또는 경로/내용 해시로 중복을 억제하여 네트워크 증폭을 방지하는 방법.청구항 5연속 공간의 로컬-법선 평행이동 편향을 격자 반올림과 두 구간 최단 결합으로 이산화하여, 현실 네트워크 제약을 만족하면서 경로 다양화를 실현하는 방법.청구항 6상기 방법을 수행하기 위한 저장매체 또는 장치.청구항 7공통 시드와 각 피어 주소에 대해 hp=computeThreshold(ip(p),seed)hp=computeThreshold(ip(p),seed) 를 산출하고, 정렬 키 (hp,ip(p))(hp,ip(p)) 를 오름차순 사전식으로 정렬한 결과를 격자에 배치함으로써, 상기 정렬 및 배치가 모든 노드에서 동일한 토폴로지를 재현하도록 하는 방법.청구항 8격자 좌표에서 방향 부호 벡터 u⃗∈{−1,0,1}2∖{(0,0)}u∈{−1,0,1}2∖{(0,0)} 를 메시지에 내장하고, 각 홉에서 여덟 이웃 N8N8 중 내적이 양수인 전방 이웃Fu⃗(p⃗)={p⃗+δ⃗∣δ⃗∈N8,δ⃗⋅u⃗>0}Fu(p)={p+δ∣δ∈N8,δ⋅u>0}으로만 전달하는 지향성 가십 전파 방법.청구항 9격자 한 변 SS 에 대해TTL=max⁡(3,⌊ρ2(S−1)+0.5⌋)TTL=max(3,⌊ρ2(S−1)+0.5⌋)로 TTL을 설정하여 과전파를 억제하면서 전역 도달성을 확보하는 방법.청구항 10발신 노드가 이웃 선택 정책을 결정론적으로 적용해 시작 방향 u⃗u 를 산출하고, 동일 입력에 대해 네트워크 전체에서 동일한 전파 부채꼴을 재현하는 방법.청구항 11수신 노드가 최근 수신 집합 기반 중복 억제를 수행하고, 송신 노드가 동일 첫 홉을 공유하는 분기 중 하나만 송신하도록 하여 증폭을 방지하는 방법.15. 업계 한계와 본 기술의 가치15.1 기존기술의 문제경로가 매번 달라 재현 불가. 테스트와 감사가 어렵다.중간 노드 판단 의존. 혼잡 시 경로 흔들림과 루프 발생.가십 전파 남발. 대역/CPU 낭비와 꼬리 지연 확대.우회 설계 부족. 검열/부분 장애 시 전달 실패 다발.15.2 본 기술이 푸는 난제결정론적 토폴로지: 모두가 같은 바둑판, 같은 순서. 결과가 항상 같다.내장 경로 3개: 최단 1 + 우회 2. 한쪽이 막혀도 도착한다.한 칸 전진 규칙: 중간 판단 제거. 루프 차단. 구현 단순.지향성 가십: 필요 시 앞쪽으로만 빠르게 확산. 대역 통제 가능.15.3 핵심 장점대역 절감: 평시 전파량이 전통 가십 대비 한 자리수 수준.지연 안정: 경로가 고정되어 지터 감소. 꼬리 지연 축소.운영 단순화: 시드만 맞추면 전 노드가 동일 동작.감사 용이: 재현 가능 경로로 원인 추적이 쉽다.장애 내성: 검열/부분 단절/혼잡에서도 성공률 유지.15.4 쉬운 설명같은 시드로 같은 순서 목록 생성.그 순서대로 바둑판 칸 채움.기본 길 하나와 좌/우 우회 길 둘을 미리 생성.메시지에 그 길을 넣고 다음 칸으로만 보냄.기존 가십전파의 과도한 트래픽을 지향성 전파로 해결할 수 있음.15.5 효과를 체감하는 곳AI 노드: AI 노드간의 통신, 분산네트워킹.블록체인 합의: 투표/검증 신호의 정족수 도달 안정.퍼블릭 피어망: 새 블록/헤더 전파 꼬리 지연 감소.엣지/사물망: 간헐적 단절에서도 즉시 우회.서비스 메쉬: 상위에서 경로 고정. 하부망 변화와 분리.15.6 현장 응용시드는 라운드 단위로 고정.우회 강도는 목표에 맞춰 조정.평시엔 3경로만. 실패 감지 시 지향성 가십을 짧게 가동.첫 홉 중복 제거와 최근 수신 집합 상시 유지.16. 결론본 발명은 결정론 격자, 로컬-법선 평행이동 기반 아핀 편향, 경로 내장형 전달을 결합해, 어디서 계산해도 동일한 3경로를 재현한다. 메시지는 다음 노드로만 전진하므로 루프가 구조적으로 차단되고, 혼잡/검열/부분 장애에서도 도달성과 안정성을 확보한다.더불어 지향성 가십은 전통 가십의 과도한 트래픽과 꼬리 지연 문제를 해결한다. 전방 이웃만 선택해 퍼지므로 매 홉 팬아웃이 최대 3으로 제한되고, 필요할 때만 짧게 가동해 네트워크 스파이크를 억제한다. 평시에는 내장 3경로로 대역을 절감하고, 실패나 장애가 감지될 때만 지향성 가십을 보조로 붙여 커버리지와 도달률을 끌어올린다. 결과적으로 본 기술은 예측 가능성(재현성), 비용 효율(대역/CPU 절감), 지연 안정(지터/꼬리 감소), 내결함성을 동시에 제공한다.유비엠에스 주식회사 (UBMS Co., Ltd.)대표 한혁진 · 사업자등록번호 409-86-55201경기도 안산시 상록구 해안로 705, 지원편의동 402호 (경기테크노파크)개업일 2021.01.26 · bokkamsun@gmail.comUBMS - 독립적 코드베이스 블록체인PoW + PoS + PoB 하이브리드 합의 | PSAN 네트워크

🎁 무료 참여

무료코인 이벤트

FREE COIN EVENT

UBMS 코인의 행운을 잡으세요!

개코개발

1시간 전[KR]39

분산 네트워크용 결정론적 2차원 격자 + 행렬 아핀 계산 기반 다중 경로 라우팅과 지향성 가십을 구현하는 방법 NEW

분산 네트워크용 결정론적 2차원 격자 + 행렬 아핀 계산 기반 다중 경로 라우팅과 지향성 가십을 구현하는 방법

작성자: bokkamsun@gmail.com

요약: 모든 피어를 같은 시드로 같은 격자에 배치한다. 같은 격자 위에서 최단 1경로 + 좌/우 우회 2경로를 결정론적으로 만든다. 메시지는 경로를 내장해 다음 노드 한 칸만 전진한다. 실패나 장애가 보이면 전방 이웃만 선택하는 지향성 가십을 짧게 켜서 커버리지를 보강한다. 이로써 재현성, 도달성, 대역 효율을 동시에 확보한다.

완전한 결정론성: 동일한 시드와 피어 집합이면 모든 노드가 똑같은 격자/경로를 재현한다.
구성적 다중경로: 최단 BFS에 아핀 편향 T(θ,k)T(θ,k) 로 좌/우 경로를 의도적으로 합성한다.
경로 내장형 포워딩: 메시지에 path[]를 싣고 다음 IP 한 칸만 전진한다.
경량 구현, 높은 이식성: 8-이웃 BFS, 격자 스냅, 간단 행렬 연산만으로 구동한다.
기존 대비 차별성: 무작위/거미줄형 그래프 탐색이 아니라 결정론적 2D 임베딩 + 선형대수 기반 편향으로 경로를 재현 가능하게 합성한다.
실전성 검증: 채굴/투표/검증 흐름에 3경로를 동시에 적용해 혼잡/차단/부분장애에서도 도달률을 실사용 수준으로 확보한다.

본 발명은 공통 시드와 IP로 모든 피어를 결정론적으로 정방 격자에 배치한다. 같은 격자 위에서 최단 경로(BFS) 1개와 아핀 편향 T(θ,k)T(θ,k) 로 만든 좌/우 우회 경로 2개를 함께 산출해 항상 3경로를 제공한다. 메시지는 이 경로들을 path[]에 내장하고 각 홉은 다음 IP 한 칸만 전진하므로 중간 판단이 없고 루프가 구조적으로 차단된다. 그리고 지향성 가십은 기존 가십을 대체한다. 전방 이웃만 선택하고 짧은 TTL로 확산해 팬아웃 3 이하를 유지하면서 전역 전파를 수행한다. 즉, 내장 3경로는 확정 경로 전달, 지향성 가십은 대규모 전파의 기본 엔진이다. 입력이 같으면 모든 노드가 동일 경로/동일 전파 패턴을 재현하므로 테스트/감사가 용이하고, 혼잡/검열/부분 장애에서도 안정적 전파와 낮은 비용을 동시에 달성한다.

1. 개요

본 기술은 무작위 전파 대신 결정론과 경로 내장을 사용한다. 절차는 다음과 같다.

결정론 정렬: 공통 시드와 주소로 모두가 같은 순서를 만든다.
격자 배치: 그 순서를 바둑판 격자에 채운다.
기본 경로 생성: 격자 8이웃 그래프에서 최단 경로를 구한다.
우회 경로 합성: 진행축 기준 아핀 편향으로 좌/우 중간점을 잡고, 두 구간 최단을 이어 우회 2경로를 얻는다.
경로 내장 전달: 메시지에 path[]를 싣고 다음 노드 한 칸만 보낸다. 중간 판단이 없어 루프와 지터가 줄어든다.
지향성 가십: 기존가십과 섞어 쓰거나, 전달 실패/지연 징후가 있으면 전방 이웃만 선택해 짧은 TTL로 확산한다. 필요할 때만 켜 대역 스파이크를 막는다.
중복 억제: 송신 측은 동일 첫 홉을 제거하고, 수신 측은 최근 ID 집합으로 중복을 드롭한다.

2. 기술분야

분산 네트워크와 블록체인 환경에서의 결정론적 토폴로지 구성과 다중 경로 메시지 라우팅.

3. 배경기술과 차별성

기존 임의 전파는 경로가 흔들려 재현성이 낮다.
격자/메쉬 기반 탐색은 단일 최단 중심으로 우회 설계가 빈약하다.
경로를 메시지에 내장하지 않으면 중간 홉의 로컬 상태에 경로가 좌우된다.

본 발명은 다음에서 차별화된다.

결정론 격자 사상으로 모든 노드가 동일 토폴로지를 재현한다.
행렬 아핀 편향으로 좌/우로 굽은 우회 경로를 수식적으로 설계하고, 격자 스냅과 두 구간 최단 결합으로 이산화한다.
경로 내장형 전달과 양단 중복 억제로 도달성과 효율을 동시에 달성한다.

4. 용어와 기호

피어 수 NN, 정렬열 v=[v0,…,vN−1]v=[v0,…,vN−1] 이고, 격자 한 변 길이 SS와 좌표는 다음과 같다.

S=⌈N⌉S=⌈N⌉r=⌊iS⌋r=⌊Si⌋c=imodSc=imodS

격자 좌표 벡터는 p⃗=[cr]p=[cr] 이다.
여덟 이웃은 N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)}N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)} 이다.

정의: 결정론 임계값 함수(일반형) 에서 임계값은 hp=computeThreshold(ip(p),seed)∈[0,2w)hp=computeThreshold(ip(p),seed)∈[0,2w) 로 둔다.
정렬 키는 (hp,ip(p))(hp,ip(p)) 이며 오름차순 사전식으로 정렬한다.

구현 예(해시 XOR 기반) 은 다음과 같다.

hp=LOWw(F(seed)⊕F(ip(p)))hp=LOWw(F(seed)⊕F(ip(p)))

여기서 FF 는 고정 해시 함수, ⊕⊕ 는 비트 XOR, LOWw(⋅)LOWw(⋅) 는 하위 ww비트 취함이다.

5. 발명의 요지

5.1 결정론 정렬

모든 노드는 동일한 seed와 피어 주소 집합에 대해 다음 임계값을 계산한다.

hp=LOWw(F(seed)⊕F(ip(p)))hp=LOWw(F(seed)⊕F(ip(p)))

정렬은 오름차순 (hp,ip(p))(hp,ip(p)) 기준으로 수행한다. 입력이 같으면 결과가 항상 같으므로 전 노드가 동일한 정렬열을 얻고, 이를 S×SS×S 격자에 순차 배치하므로 토폴로지도 전 노드에서 동일하다.

데카르트 좌표

토폴로지 구성을 결정론적 격자 배치하여 행렬연산이 가능하다.

5.2 격자 사상

정렬 순서 ii 번째 피어를 (r,c)(r,c) 에 순차 배치한다. 빈 칸은 존재하지 않는 노드로 간주해 자동 회피된다.

5.3 최단 경로

여덟 이웃 무가중 그래프에서 시작 p⃗sps 와 목표 p⃗gpg 사이 최단 홉수 경로 P0P0 를 산출한다.

5.4 로컬-법선 평행이동 기반 편향

진행축을 기준으로 로컬 좌표에서 법선 방향(yy축) 으로 αα 만큼 평행이동한 편향 중간점을 만든 뒤, 두 구간 최단을 이어 좌/우 대체 경로를 얻는다.

6. 수학적 구성

6.1 진행각과 변위

시작점과 목표점은 각각 p⃗s=[csrs]ps=[csrs], p⃗g=[cgrg]pg=[cgrg] 이다.
변위는 d⃗=p⃗g−p⃗sd=pg−ps 이고, 진행각은 θ=atan2(rg−rs,cg−cs)θ=atan2(rg−rs,cg−cs) 이다.

6.2 진행축 정렬과 로컬-법선 평행이동

회전행렬 R

R(θ)=(cos⁡θ−sin⁡θsin⁡θcos⁡θ)R(θ)=(cosθsinθ−sinθcosθ)

1. 진행각으로 정렬한다.

[xLyL]=R(−θ)(p⃗s+td⃗−p⃗s),yL←yL±α,p~m(±)=p⃗s+R(θ)[xLyL].[xLyL]=R(−θ)(ps+td−ps),yL←yL±α,p~m(±)=ps+R(θ)[xLyL].

2. 로컬 법선(yLyL)으로 ±α±α 평행이동한다.

3. 역정렬하여 월드 좌표로 복귀한다.

여기서 d⃗=p⃗g−p⃗sd=pg−ps, t∈(0,1)t∈(0,1) 이며 코드 기본은 t=0.5t=0.5 이다.

부연: 기존 문서의 T(θ,k)=R(θ),Sx(k),R(−θ)T(θ,k)=R(θ),Sx(k),R(−θ) 표기는 개념 설명이며, 실제 구현은 로컬-법선 평행이동으로 동치 효과를 낸다.

6.2a 동차좌표 버전

현재 문서는 작성된 코드와 일관성을 유지하기위해, 동차좌표 없이 "로컬-법선 평행이동"으로 구현하였다. 추가로 이해를 돕기 위해 동일 동작을 3x3 동차 행렬로도 첨부한다.

동차 변환

T(a,b)=[10a01b001],R(θ)=[cos⁡θ−sin⁡θ0sin⁡θcos⁡θ0001]T(a,b)=100010ab1,R(θ)=cosθsinθ0−sinθcosθ0001

편향 중간점 생성 행렬

M±=T(cs,rs)R(θ)T(t∥d⃗∥,±α)R(−θ)T(−cs,−rs)M±=T(cs,rs)R(θ)T(t∥d∥,±α)R(−θ)T(−cs,−rs)

적용

p~m(±)=(M±[cs,rs,1]T)xy,p^m(±)=clipRound(p~m(±))p~m(±)=(M±[cs,rs,1]T)xy,p^m(±)=clipRound(p~m(±))

동치성(요지): 위 전개를 풀면

p~m(±)=p⃗s+td⃗±αn^p~m(±)=ps+td±αn^

즉 본문 식(6.3)과 완전히 동일하다. 여기서 d⃗=p⃗g−p⃗s,n^=[−sin⁡θ,cos⁡θ]Td=pg−ps,n^=[−sinθ,cosθ]T.

선택 확장(개념용): 과거 표기 T(θ,k)=R(θ)Sx(k)R(−θ)T(θ,k)=R(θ)Sx(k)R(−θ)를 쓰고 싶다면,

M±=TR(θ)Sx(k)T(t∥d⃗∥,±α)R(−θ)T−1M±=TR(θ)Sx(k)T(t∥d∥,±α)R(−θ)T−1

처럼 전개 지점에 끼우면 된다. 본 구현은 Sx(k)=ISx(k)=I로 두고 평행이동만 사용한다.

구현: 동차 방식을 택해도 마지막은 동일하게 clipRound()와 경계 클램프를 적용한다.

6.3 편향 중간점과 격자 스냅

법선 단위벡터는 n^=[−sin⁡θcos⁡θ]n^=[−sinθcosθ] 이다.
편향 세기는 α=0.6,k,∥d⃗∥α=0.6,k,∥d∥ 이며 기본 t=0.5t=0.5 를 사용한다.
연속 공간상의 편향 중간점과 격자 반올림/경계 클램프는

p~m(±)=p⃗s+td⃗±αn^,p^m(±)=clipRound(p~m(±)).p~m(±)=ps+td±αn^,p^m(±)=clipRound(p~m(±)).

p^m(±)p^m(±) 이 시작 또는 목표와 같은 셀이면, 법선 n^n^ 방향으로 bump=sign(α)⋅max⁡(1,0.1∥d⃗∥)bump=sign(α)⋅max(1,0.1∥d∥) 만큼 추가 평행이동 후 다시 clipRound 한다.
해당 셀이 비어 있으면 반경 ≤3≤3 내에서 가장 먼저 발견되는 유효 셀을 대체 선택한다.

6.4 두 구간 최단 결합

편향 경로는

P±=ShortestPath(p⃗s,p^m(±))⊕ShortestPath(p^m(±),p⃗g)P±=ShortestPath(ps,p^m(±))⊕ShortestPath(p^m(±),pg)

UBMS 3 path [ t 값이 0.9 ]

이며, ⊕⊕ 는 중간점 중복을 한 번만 포함하는 연결이다(코드에서 두 번째 구간은 인덱스 1부터 붙임).

7. 지향성 가십 전파(Directional Gossip) — 결정론 격자 기반 부채꼴 전파

7.1 정의

격자 좌표를 p⃗=[cr]Tp=[cr]T 로 두고, 여덟 이웃 집합은

N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)}.N8={(−1,−1),(−1,0),(−1,1),(0,−1),(0,1),(1,−1),(1,0),(1,1)}.

8이웃(N8N8)

방향 부호 벡터 u⃗=[sxsy]T∈{−1,0,1}2∖{(0,0)}u=[sxsy]T∈{−1,0,1}2∖{(0,0)} 를 메시지 필드 op3="sx,sy"로 내장한다. 이는 시작점과 발신자 사이 상대 위치의 부호 정규화:

sx=sign⁡(cnbr−csrc),sy=sign⁡(rnbr−rsrc)sx=sign(cnbr−csrc),sy=sign(rnbr−rsrc)

sign⁡(z)={1,z>00,z=0−1,z<0sign(z)=⎩⎨⎧1,0,−1,z>0z=0z<0

7.2 전파 규칙(부채꼴 전방 이웃)

현재 홉이 p⃗p 일 때 전방 이웃 집합을

Fu⃗(p⃗)={p⃗+δ⃗∣δ⃗∈N8,δ⃗⋅u⃗>0}Fu(p)={p+δ∣δ∈N8,δ⋅u>0}

로 정의한다. 즉, u⃗u 와의 내적이 양수인 이웃만 선택.

축 방향 (1,0)(1,0): (1,−1),(1,0),(1,1)(1,−1),(1,0),(1,1) 로 3분기.
축 방향 (0,1)(0,1): (−1,1),(0,1),(1,1)(−1,1),(0,1),(1,1) 로 3분기.
대각 (1,1)(1,1): (1,1),(1,0),(0,1)(1,1),(1,0),(0,1) 로 3분기.

u=(1,0)

u=(1,1)

수신 노드는 TTL←TTL−1TTL←TTL−1 후 유효 피어만 골라 Fu⃗(p⃗)Fu(p) 로 송신하며, 입력 FD는 제외.

7.2a 직관 설명: ΔΔ(델타)와 u⃗u(전진축)

ΔΔ = "한 칸 이동 후보." 현재 위치 p⃗p에서 p⃗+Δp+Δ로 1홉 이동한다.
u⃗u = (sx, sy) = "가고 싶은 큰 방향의 부호." sx, sy ∈{−1,0,1}∈{−1,0,1}, (0,0)은 금지.
전방 선택 규칙: 점수 = dx⋅sx+dy⋅sydx⋅sx+dy⋅sy
- 점수 > 0: 전방 이웃. 보낸다.
- 점수 = 0: 측면. 전방이 없을 때만 보조로 쓴다(7.7).
- 점수 < 0: 후방. 버린다.
요약: u⃗u는 "전진축", ΔΔ는 "한 걸음". dx⋅sx+dy⋅sy>0dx⋅sx+dy⋅sy>0 인 걸음만 전송한다.

7.3 TTL 설정(격자 대각 기반)

격자 한 변 S=⌈N⌉S=⌈N⌉, 전체 대각 길이

D=(S−1)2+(S−1)2D=(S−1)2+(S−1)2

지향성 가십의 TTL은

TTL=max⁡(3,⌊ρ⋅D+0.5⌋),ρ∈(0,1],기본 ρ=0.8.TTL=max(3,⌊ρ⋅D+0.5⌋),ρ∈(0,1],기본 ρ=0.8.

7.4 메시지 형식

op3="sx,sy": 방향 벡터 u⃗u.
ttl: 위 식의 TTL.
messageId: 고유 식별자.
payload: 송신자 상태.

7.5 결정론 시작 방향 선택

발신 노드가 자기 8이웃 중 선택한 시작 이웃 (cnbr,rnbr)(cnbr,rnbr) 에 대해

u⃗=[sign⁡(cnbr−cself)sign⁡(rnbr−rself)].u=[sign(cnbr−cself)sign(rnbr−rself)].

선택 정책(라운드로빈, 해시 최소 등)을 고정하면 동일 입력에서 결정론적 시작 방향이 재현된다.

7.6 중복 억제

각 노드는 messageId 또는 (header, op3, payload) 해시로 최근 수신 집합을 유지하고 중복 패킷을 드롭한다. 동일 첫 홉을 공유하는 분기는 송신 측에서 하나만 남긴다.

7.7 경계/결손 노드 처리

격자 경계 또는 결손(빈 셀)에서 전방 이웃이 비면 전파를 중단하지 않고 대체 전방 집합을 선택한다.

Fu⃗∗(p⃗)=(Fu⃗(p⃗)∩V)∪{p⃗+δ⃗∣δ⃗∈N8,δ⃗⋅u⃗=0,p⃗+δ⃗∈V}Fu∗(p)=(Fu(p)∩V)∪{p+δ∣δ∈N8,δ⋅u=0,p+δ∈V}

여기서 VV 는 유효 노드 집합이다. 즉, 우선 전방(δ⃗⋅u⃗>0δ⋅u>0)을 사용하고, 없을 때만 측면(=0=0)을 보조로 사용한다.

7.8 종료 조건과 루프 방지

TTL←TTL−1,if TTL≤0 then drop.TTL←TTL−1,if TTL≤0 then drop.

최근 수신 집합 RR 에 대해

if messageId∈R then drop,else R←R∪{messageId}.if messageId∈R then drop,else R←R∪{messageId}.

전방 선택은 δ⃗⋅u⃗≥0δ⋅u≥0 만 허용하므로 역방향 전파가 구조적으로 배제된다.

7.9 도달률 하한(커버리지)와 TTL 하한

격자 변 SS, 대각 길이 D=2(S−1)D=2(S−1). ρ∈(0,1]ρ∈(0,1] 에 대해

TTLmin⁡=max⁡(3,⌊ρD+0.5⌋)TTLmin=max(3,⌊ρD+0.5⌋)

을 쓰면, 장애 비율이 ≤(1−ρ)≤(1−ρ) 인 균질 환경에서 부채꼴 전선의 도달률 하한이 유지된다. ρρ 를 늘리면 커버리지 증가, 대역비용 증가.

7.10 파라미터 튜닝 지침

팬아웃 상한: 각 홉 송신수 ≤3≤3 유지. 필요 시 샘플링 확률 p∈(0,1]p∈(0,1] 도입.

E[Mdir]≈3pTTL.E[Mdir]≈3pTTL.

TTL = 3 이웃 커버리지

ρρ: 평시 0.6 ~ 0.8, 장애 구간 감지 시 일시적으로 0.9 이상.
최근 집합 크기: 윈도 길이 W≥TTLW≥TTL 로 설정.

7.11 보안/검열 회피 고려

방향 고정 공격 완화: 시작 방향 u⃗u 를 결정론적이되 라운드 시드로 주기 갱신.

u⃗t=choose(N8∖{(0,0)};seedt,N8)ut=choose(N8∖{(0,0)};seedt,N8)

동일 라운드 입력에 대해 전 노드가 같은 u⃗tut 를 재현한다.

헤더 위/변조 검출: (op3, ttl, payload) 에 대한 경량 MAC 첨부.

7.12 성능 상한과 기대치 정리

총 송신 상한:

Mdir≤3TTL,TTL≤ρ2(S−1)=Θ(N)Mdir≤3TTL,TTL≤ρ2(S−1)=Θ(N)

전역 중복 포함 절댓값의 보수 상한은

Mdirdup≤3NMdirdup≤3N

이지만, 최근 집합과 측면 대체 규칙으로 실측은 Θ(N)Θ(N) 에 근접한다.

7.13 호환성: 경로 전파와의 병행 운용

동일 메시지 ID에 대해 경로 전파(6절) 를 우선, 지향성 가십은 타임아웃 TfallbackTfallback 후 보조 가동:

if not delivered by Tfallback⇒start directional gossip with TTL=TTLmin⁡.if not delivered by Tfallback⇒start directional gossip with TTL=TTLmin.

증폭 방지를 위해 송신 측은 동일 첫 홉 중복을 제거한다.

8. 지향성 가십의 효과

경로 다양성: 8방향 중 선택된 u⃗u 기준 부채꼴 전방 3분기로 검열/혼잡 회피 확률 상승.
결정론성: 격자 사상과 시작 방향 정책 고정으로 재현 가능.
단순성: 조건 δ⃗⋅u⃗>0δ⋅u>0 만으로 전방 선별.

8.1. 일반적인 gossip 전파

일반 gossip ttl = 1

일반 gossip ttl = 2

일반 gossip ttl = 3

일반 gossip ttl = 4

일반 gossip ttl = 5

일반 gossip ttl = end

음영구역 발생: 무작위 전파에 가까운 일반적인 가십전파는 필연적인 음영구역 발생.

8.2. 지향성 gossip 전파

지향성 gossip ttl = 1

지향성 gossip ttl = 3

지향성 gossip ttl = 5

지향성 gossip ttl = 7

지향성 gossip ttl = 11

지향성 gossip ttl = end

치밀하고 체계적인 전파: 각 노드는 방향벡터를 기준으로 전파방향을 설정, 역전파 중복전파 등이 최소화됨.

9. 경로 내장 전달과 중복 억제

메시지는 전체 경로와 길이를 포함하고 각 홉은 자기 다음 노드로만 전진한다. 송신 측은 세 경로의 첫 번째 다음 홉이 같으면 하나만 남긴다. 수신 측은 최근 본 식별자 또는 경로/내용 해시로 중복을 억제한다. 이중 억제는 증폭을 막으면서 3경로의 도달성 이점을 유지한다.

10. 장애와 혼잡 상황에서의 동작 이유

좌/우 편향 경로는 기하학적으로 분리된 통로를 제공한다. 편향 경로는 격자 위 두 구간 최단의 합성이어서 불필요한 우회가 작다. ∣k∣∣k∣ 가 커지면 경로 상관이 낮아져 검열/혼잡 회피에 유리하지만 지연은 증가한다. 기본적으로 t=12t=21 가 균형 잡힌 분산을 준다.

11. 실시예

동일 시드/주소 집합이면 모든 노드가 동일 격자 배치와 동일 3경로를 재현한다. 편향 강도 ∣k∣∣k∣ 를 조절하면 좌/우 경로의 분산 폭이 달라진다. 격자 끝 빈 칸은 자동 회피되며, 편향 중간점이 빈 칸이면 근접 유효 셀 대체로 경로 생성을 지속한다. 기본값은 t=0.5t=0.5, α=0.6,k,∥d⃗∥α=0.6,k,∥d∥ 이다.

12. 산업상 이용가능성

AI 분산노드: 분산네트워크 환경에서 AI노드간의 통신.
블록체인 합의: 투표/검증 신호를 3경로로 동시 전파해 정족수 도달 안정성을 높인다.
공개 피어 전파: 꼬리 지연과 실패율을 낮춘다.
사물망/현장망/애드혹망: 간섭/단절에도 즉시 우회한다.
오버레이/서비스 메쉬: 하부망과 무관하게 응용 계층에서 경로를 고정/내장한다.

운영 가이드: 시드는 라운드/시간 단위로 고정해 동일 격자를 재현한다. 편향 강도 kk 는 지연 중심이면 작게, 내결함성 중심이면 크게 정한다. 송신/수신 양단 억제로 중복 최소화. 메시지 길이는 경로 길이와 동일로 설정해 루프를 차단한다.

13. 성능과 복잡도

격자 면적은 S2S2 이고, 최단 탐색의 시간 복잡도는 대략 O(S2)O(S2) 이다. 본 발명에서 제시하는 방법으로 세 경로 산출은 최단 1회와 편향 각 2회의 두 구간 결합으로 상수배 비용 증가에 그친다.

13.1 모델

지향성 가십 길이 척도: D=2(S−1)=Θ(N)D=2(S−1)=Θ(N).
TTL 상한: TTL≤ρDTTL≤ρD.

13.2 경로 내장 3-경로 전파

경로 수: 3.
경로 길이: 각 Θ(N)Θ(N).
총 송신 수: Mpath≈3D=Θ(N).Mpath≈3D=Θ(N).
중복 없음. 지연: Θ(N)Θ(N) 홉.

13.3 지향성 가십

각 홉 전방 이웃 ≤3≤3만 1회 송신.
총 송신 수 상한: Mdir≤3N=Θ(N).Mdir≤3N=Θ(N).
중복은 최근 ID로 억제. 지연: Θ(N)Θ(N) 홉.

13.4 전통 가십(비교 기준)

팬아웃 g≥2g≥2, 라운드 수 Θ(log⁡N)Θ(logN).
총 송신 수(중복 포함): Mepi=Θ(gNlog⁡N).Mepi=Θ(gNlogN).

13.5 정량 예시

N=104,ρ=0.8,g=3N=104,ρ=0.8,g=3 가정.

D≈0.8⋅2⋅(100−1)≈112D≈0.8⋅2⋅(100−1)≈112.
경로 전파: Mpath≈3D≈336Mpath≈3D≈336.
지향성 가십: Mdir≤3N=30,000Mdir≤3N=30,000.
전통 가십: Mepi≈gNlog⁡2N≈3⋅104⋅13.3≈399,000Mepi≈gNlog2N≈3⋅104⋅13.3≈399,000.

13.6 비용/지연 트레이드오프

대역 효율: Mpath≪Mdir<MepiMpath≪Mdir<Mepi.
도달성/내결함성: 전통 ≥≥ 지향성 >> 경로.
지연: 전통 O(log⁡N)O(logN), 경로/지향성 O(N)O(N).
재현성/제어성: 경로/지향성은 결정론적, 전통은 비결정적.

13.7 운용 권고

평시: 경로 3개로 전역 신호 전달(대역 최소).
장애/검열 구간 탐지 시: 지향성 가십 보조 활성화로 커버리지 확보.
전통 가십은 피크/중복 비용이 커 상시 운용 비권장.

14. 청구항

청구항 1
결정론 정렬/정방 격자 사상을 수행하고, 격자 여덟 이웃 그래프에서 최단 경로 P0P0 를 산출하며, 진행축 정렬-로컬 법선 평행이동-역정렬 변환을 통해 편향 중간점 p^mp^m 을 생성하고, 시작-중간점, 중간점-목표의 두 구간 최단을 연결하여 좌/우 편향 경로 P±P± 를 생성한 뒤, 이를 P0P0 와 함께 제공하는 다중 경로 라우팅 방법.

청구항 2
편향 중간점이 비어 있거나 유효하지 않을 때 반경 확장으로 근접 유효 셀을 대체 선택하여 편향 경로 생성을 유지하는 방법.

청구항 3
메시지에 전체 경로와 길이를 포함하여 각 홉에서 다음 노드로만 전진하도록 하여 루프를 억제하고 경로 재현성을 확보하는 방법.

청구항 4
송신 측에서 첫 번째 다음 홉이 같은 경로를 제거하고, 수신 측에서 최근 본 식별자 또는 경로/내용 해시로 중복을 억제하여 네트워크 증폭을 방지하는 방법.

청구항 5
연속 공간의 로컬-법선 평행이동 편향을 격자 반올림과 두 구간 최단 결합으로 이산화하여, 현실 네트워크 제약을 만족하면서 경로 다양화를 실현하는 방법.

청구항 6
상기 방법을 수행하기 위한 저장매체 또는 장치.

청구항 7
공통 시드와 각 피어 주소에 대해 hp=computeThreshold(ip(p),seed)hp=computeThreshold(ip(p),seed) 를 산출하고, 정렬 키 (hp,ip(p))(hp,ip(p)) 를 오름차순 사전식으로 정렬한 결과를 격자에 배치함으로써, 상기 정렬 및 배치가 모든 노드에서 동일한 토폴로지를 재현하도록 하는 방법.

청구항 8
격자 좌표에서 방향 부호 벡터 u⃗∈{−1,0,1}2∖{(0,0)}u∈{−1,0,1}2∖{(0,0)} 를 메시지에 내장하고, 각 홉에서 여덟 이웃 N8N8 중 내적이 양수인 전방 이웃

Fu⃗(p⃗)={p⃗+δ⃗∣δ⃗∈N8,δ⃗⋅u⃗>0}Fu(p)={p+δ∣δ∈N8,δ⋅u>0}

으로만 전달하는 지향성 가십 전파 방법.

청구항 9
격자 한 변 SS 에 대해

TTL=max⁡(3,⌊ρ2(S−1)+0.5⌋)TTL=max(3,⌊ρ2(S−1)+0.5⌋)

로 TTL을 설정하여 과전파를 억제하면서 전역 도달성을 확보하는 방법.

청구항 10
발신 노드가 이웃 선택 정책을 결정론적으로 적용해 시작 방향 u⃗u 를 산출하고, 동일 입력에 대해 네트워크 전체에서 동일한 전파 부채꼴을 재현하는 방법.

청구항 11
수신 노드가 최근 수신 집합 기반 중복 억제를 수행하고, 송신 노드가 동일 첫 홉을 공유하는 분기 중 하나만 송신하도록 하여 증폭을 방지하는 방법.

15. 업계 한계와 본 기술의 가치

15.1 기존기술의 문제

경로가 매번 달라 재현 불가. 테스트와 감사가 어렵다.
중간 노드 판단 의존. 혼잡 시 경로 흔들림과 루프 발생.
가십 전파 남발. 대역/CPU 낭비와 꼬리 지연 확대.
우회 설계 부족. 검열/부분 장애 시 전달 실패 다발.

15.2 본 기술이 푸는 난제

결정론적 토폴로지: 모두가 같은 바둑판, 같은 순서. 결과가 항상 같다.
내장 경로 3개: 최단 1 + 우회 2. 한쪽이 막혀도 도착한다.
한 칸 전진 규칙: 중간 판단 제거. 루프 차단. 구현 단순.
지향성 가십: 필요 시 앞쪽으로만 빠르게 확산. 대역 통제 가능.

15.3 핵심 장점

대역 절감: 평시 전파량이 전통 가십 대비 한 자리수 수준.
지연 안정: 경로가 고정되어 지터 감소. 꼬리 지연 축소.
운영 단순화: 시드만 맞추면 전 노드가 동일 동작.
감사 용이: 재현 가능 경로로 원인 추적이 쉽다.
장애 내성: 검열/부분 단절/혼잡에서도 성공률 유지.

15.4 쉬운 설명

같은 시드로 같은 순서 목록 생성.
그 순서대로 바둑판 칸 채움.
기본 길 하나와 좌/우 우회 길 둘을 미리 생성.
메시지에 그 길을 넣고 다음 칸으로만 보냄.
기존 가십전파의 과도한 트래픽을 지향성 전파로 해결할 수 있음.

15.5 효과를 체감하는 곳

AI 노드: AI 노드간의 통신, 분산네트워킹.
블록체인 합의: 투표/검증 신호의 정족수 도달 안정.
퍼블릭 피어망: 새 블록/헤더 전파 꼬리 지연 감소.
엣지/사물망: 간헐적 단절에서도 즉시 우회.
서비스 메쉬: 상위에서 경로 고정. 하부망 변화와 분리.

15.6 현장 응용

시드는 라운드 단위로 고정.
우회 강도는 목표에 맞춰 조정.
평시엔 3경로만. 실패 감지 시 지향성 가십을 짧게 가동.
첫 홉 중복 제거와 최근 수신 집합 상시 유지.

16. 결론

본 발명은 결정론 격자, 로컬-법선 평행이동 기반 아핀 편향, 경로 내장형 전달을 결합해, 어디서 계산해도 동일한 3경로를 재현한다. 메시지는 다음 노드로만 전진하므로 루프가 구조적으로 차단되고, 혼잡/검열/부분 장애에서도 도달성과 안정성을 확보한다.

더불어 지향성 가십은 전통 가십의 과도한 트래픽과 꼬리 지연 문제를 해결한다. 전방 이웃만 선택해 퍼지므로 매 홉 팬아웃이 최대 3으로 제한되고, 필요할 때만 짧게 가동해 네트워크 스파이크를 억제한다. 평시에는 내장 3경로로 대역을 절감하고, 실패나 장애가 감지될 때만 지향성 가십을 보조로 붙여 커버리지와 도달률을 끌어올린다. 결과적으로 본 기술은 예측 가능성(재현성), 비용 효율(대역/CPU 절감), 지연 안정(지터/꼬리 감소), 내결함성을 동시에 제공한다.

유비엠에스 주식회사 (UBMS Co., Ltd.)
대표 한혁진 · 사업자등록번호 409-86-55201
경기도 안산시 상록구 해안로 705, 지원편의동 402호 (경기테크노파크)
개업일 2021.01.26 · bokkamsun@gmail.com

UBMS - 독립적 코드베이스 블록체인

PoW + PoS + PoB 하이브리드 합의 | PSAN 네트워크

댓글이 없습니다.

🎁 무료 참여

무료코인 이벤트

FREE COIN EVENT

UBMS 코인의 행운을 잡으세요!