Inter-domain QoS routing on Diffserv networks: a region-based approach

Ibrahim T. Okumus, Haci A. Mantar, 황준석, Steve J. Chapin (2005) · Computer Communications 28:174-188 · DOI ↗

차별화 서비스 네트워크의 인터도메인 QoS 라우팅을 위해 region-based, link-state, source-specified 아키텍처를 제안한다. BGP 의 path-vector 가 QoS 정보를 운반하지 못하고 전통적 link-state 는 모든 라우터가 전체 토폴로지를 알아야 해 확장성이 무너지는 두 문제를 동시에 해결하는 것이 목표다. 인터넷 AS 를 비계층적 region 으로 나누고 region 내부에서만 link-state 를 교환하면 region 크기가 작아질수록 평균 최단 경로 길이(SPL)는 늘지만 통신·계산·저장 부담은 훨씬 더 가파르게 감소함을 보였다. 1500 AS 토폴로지에서 region 수를 10 에서 60 으로 늘리면 평균 region 크기는 82.3% 감소하나 평균 SPL 은 12.3% 증가에 그쳐, 대규모일수록 확장성 이득이 SPL 손실을 압도한다.

RQ: 다수의 자율시스템(AS) 간에 BGP 라우팅을 보완하는 QoS 경로 계산을 계층(hierarchy) 의 정보 손실 없이 어떻게 확장 가능하게 분산시킬 수 있는가.
방법론: 아키텍처 설계, 네트워크 시뮬레이션, BGP 라우팅
데이터: BRITE 생성 합성 토폴로지 100 / 1500 / 15000 노드 + Oregon Route Views BGP(2001-03-31) 기반 MT1500(1522 AS, 6822 edges) + 3000 AS 토폴로지. region 수를 1, 5, 11, 24, 44, 60, 128 까지 변화시키며 시뮬레이션.
주요 발견: 100 AS 에서 region 을 5 개로 분할하면 region 크기 61.4% 감소 · SPL 25% 증가, 11 개로 분할하면 region 크기 81.5% 감소 · SPL 28% 증가. 1500 AS 에서는 region 60 개일 때 region 크기 82.3% 감소 · SPL 12.3% 증가로 대규모 네트워크에서 트레이드오프가 훨씬 유리. MT1500 (실측 토폴로지) 의 평균 SPL 은 4.81 로 실제 인터넷 평균 AS 경로 길이 5.3 보다 짧음. Viewserver 방식 대비 평균 PRM(Path Request Message) 7.51 → 1.46 으로 path setup 시간도 단축.
시사점: 차별화 서비스 기반 인터도메인 QoS 인프라 설계에서 hierarchical aggregation 의 정보 손실 없이 확장성을 확보할 수 있다. region 은 단순한 link-state flooding 경계일 뿐 계층이나 대표 노드를 두지 않으므로 BGP 위에 직접 plug-in 형태로 도입 가능.

Diffserv 인터도메인 QoS 라우팅의 region 단위 토폴로지 분할 구조.

요약

본 페이퍼는 황준석 1기(2000~2006) 네트워크 경제학 라인의 인접 영역인 network-engineering 작업으로, 차별화 서비스 네트워크의 대역폭 브로커가 인터도메인 QoS 경로를 계산할 때 마주치는 토폴로지 배포 문제를 다룬다. BGP4 의 path-vector 는 QoS 정보를 운반하지 않으므로 hop-by-hop try-and-fail 만 가능하고, 전통적 link-state 는 모든 라우터가 전체 인터넷 토폴로지(2003 년 6 월 기준 15,264 AS)를 알아야 해 저장·통신 비용이 비현실적이다. 기존 계층(hierarchical) 라우팅은 여러 도메인을 하나의 추상 도메인으로 표현하는 aggregation 으로 인해 QoS 가 만족 가능한 경로조차 찾지 못하는 정보 손실(lossy abstraction) 문제를 안고 있다.

저자들은 인터넷을 비계층적 region 의 합집합으로 본다. region 은 transit AS 의 연결 부분그래프이며 region 끼리는 ingress domain 에서 겹친다. 각 AS 는 같은 region 내부의 모든 AS 와 이웃 region 의 ingress domain 만 토폴로지로 본다. source 는 destination 의 region 까지의 regional path 를 먼저 계산하고, 자기 region 내부의 QoS 경로만 bellman-ford-algorithm 으로 구한 뒤, 다음 region 의 ingress domain 에 Path Request Message(PRM) 를 넘긴다. PRM 은 잔여 QoS 예산( $C'_i = C_i - c_{i,d_1}$ ) 을 갱신하며 region 들을 차례로 통과해 destination 에 도달하고, Path Response Message 가 역방향으로 sub-path 들을 이어 붙여 end-to-end 경로를 완성한다. 각 도메인의 edge-to-edge 특성은 RFC3086 의 per-domain-behavior 로 추상화해 intra-domain 토폴로지 노출 없이도 QoS 계산이 가능하게 한다.

ns2 와 BRITE topology generator 로 100 / 1500 / 3000 / 15000 노드 토폴로지를 만들어 평가했다. 100 AS 에서 region 11 개일 때 평균 region 크기 18.5 (단일 region 대비 81.5% 감소) 에 평균 SPL 4.35 (28% 증가), 1500 AS 에서 region 60 개일 때 평균 region 크기 50.65 (10 region 대비 82.3% 감소) 에 평균 SPL 7.84 (12.3% 증가) 로, 토폴로지가 클수록 SPL 손실이 줄어든다. Heavy-tailed Barabasi-Albert 와 Waxman 두 모델로 생성한 10 개 토폴로지에서 결과 패턴이 일관되게 재현돼 토폴로지 의존성도 낮음을 확인했다. alaettinoglu-shankar-1995-viewserver 의 viewserver 계층 방식과 비교하면 동급 storage 에서 PRM 이 7.51 → 1.46 으로 줄어 path setup 시간이 큰 폭으로 개선된다. 본 페이퍼는 동일 그룹의 A Scalable and Efficient Inter-domain QoS Routing Architecture for Diffserv Networks, A Scalable Model for Interbandwidth Broker Resource Reservation and Provisioning 대역폭 브로커 라인을 라우팅 layer 로 확장한 결과이며, 황준석 1기 네트워크 경제학 / QoS Interconnection 라인의 기술 인프라 토대를 이룬다.

핵심 결과

토폴로지	region 수	평균 region 크기	평균 SPL	SPL 변화	평균 PRM
100 AS	1	100	3.41	baseline	0
100 AS	5	38.6	4.29	+25%	1.00
100 AS	11	18.5	4.35	+28%	1.25
1500 AS (B1500)	10	286.5	6.98	baseline	1.00
1500 AS (B1500)	24	121.75	7.08	+1.4%	1.01
1500 AS (B1500)	60	50.65	7.84	+12.3%	1.46
1522 AS (MT1500, 실측)	60	1116.4	2.81	n/a	n/a
3000 AS	128	47.7	9.18	n/a	≤2

Viewserver(vertex-ex, 1100 AS) 대비: storage 50.65~~286.5 vs 362.15, PRM 1.0~~1.46 vs 7.51 메시지.

방법론 노트

region $R_i = (V, E)$ 는 인터넷 $I = (N, L)$ 의 connected subgraph 들의 합집합이며 ( $I = R_1 \cup \cdots \cup R_n$ ), region 끼리는 ingress domain 에서 겹친다 ( $R_m \cap R_n \neq \emptyset$ if 인접). source $s$ 가 region $R_s$ 에서 region $R_d$ 의 destination $d$ 로 QoS 트래픽을 보낼 때, regional path $P_R = (R_s, \ldots, R_d)$ 를 먼저 정한 뒤 각 region 의 ingress domain 이 자기 region 내부의 sub-path 를 계산한다. 도메인 $d_1$ 이 자기 region 에서 QoS 비용 $c_{1,d_1}, c_{2,d_1}, c_{3,d_1}$ 의 sub-path 를 찾으면, 다음 region 으로 넘기는 PRM 의 잔여 QoS 예산은

C'_1 = C_1 - c_{1,d_1}, \quad C'_2 = C_2 - c_{2,d_1}, \quad C'_3 = C_3 - c_{3,d_1}

로 갱신된다. 최종 end-to-end 경로는 region 별 sub-path 들의 concatenation $p = (P_{R_s}, \ldots, P_{R_d})$ 이다. region 내부 path 선택은 가용 대역폭을 metric 으로 하는 bellman-ford-algorithm 으로, multi-metric 문제(NP-complete) 를 회피한다. 평가의 핵심 변수는 평균 region 크기(저장·통신 부담의 proxy) 와 평균 SPL(경로 품질의 proxy) 의 트레이드오프 곡선이다.

연구 계보

본 페이퍼의 직접 선행은 같은 저자 그룹의 A Scalable and Efficient Inter-domain QoS Routing Architecture for Diffserv Networks 와 A Scalable Model for Interbandwidth Broker Resource Reservation and Provisioning 로, Diffserv 네트워크의 대역폭 브로커 간 자원 예약 프로토콜을 정립했고, 본 작업은 그 위에 라우팅 layer 를 얹은 구조다. 인터도메인 라우팅 계열에서는 alaettinoglu-shankar-1995-viewserver 의 viewserver 계층 방식이 정량 비교 대상이며, 본 방식이 storage 와 path setup 메시지 양쪽에서 우위에 있음을 보였다. BGP 의 QoS 확장 시도들 (hwang-altmann-2002-bgp-qos-modified = Enabling Dynamic Market-Managed QoS Interconnection in the Next Generation Internet by a Modified BGP Mechanism 포함) 과는 다른 노선으로, BGP 를 best-effort 트래픽용으로 두고 QoS 트래픽만 별도 plug-in 으로 처리하는 전략이다. 황준석 1기 네트워크 경제학 / QoS Interconnection 라인 안에서 Cross-Network Open Provisioning Intelligent Network (COPIN) for Bandwidth Transaction Services in the Next Generation Internet 의 COPIN 아키텍처, Interprovider differentiated service interconnection management models in the Internet bandwidth commodity markets 의 제공자 간 차별화 서비스 모델과 한 묶음의 시기적 자매 작업이다.

인접 그래프

1-hop 이웃 22개

인물 4
방법론 2
개념 3
주제 3
수록처 1
분류 1
논문 8

휠 = 확대/축소 · 드래그 = 이동 · hover = 라벨 · 클릭 = 페이지 이동

Inter-domain QoS routing on Diffserv networks: a region-based approach

요약

핵심 결과

방법론 노트

연구 계보

See also

인접 그래프

이 문서를 가리키는 페이지

논문 (3)