A Scalable Model for Interbandwidth Broker Resource Reservation and Provisioning

Haci A. Mantar, 황준석, Ibrahim T. Okumus, Steve J. Chapin (2004) · IEEE Journal on Selected Areas in Communications 22 · DOI ↗

Diffserv 도메인 간 Bandwidth Broker (BB) 협상의 scalability 모형. 기존 pipe model 의 state scalability O(N²) 문제 (인터넷 13,500 도메인·130,000 네트워크 환경에서 transit router 의 한계 초과) 를 destination-region 기반 aggregated reservation 으로 풀어 O(N×k) 로 축소 (k=인접 peer 수). 신규 BBRP (BB Resource Reservation and Provisioning) 프로토콜은 SIBBS 위에서 wholesale-retailer 패러다임 — BB 가 provider 로부터 사서 customer 에게 판매 — 으로 동작. 5-domain test-bed + CAIDA TSRI-AS(2641) trace 실험에서 BBRP 가 SIBBS 대비 signaling 부하 52% 감소, 자원 12.5% over-provision trade-off.

RQ: Diffserv inter-BB 자원 예약·프로비저닝의 scalability 문제 (state / signaling / forwarding path / multiplexing gain) 를 어떻게 정량 분석 가능한 모형으로 해결하고, 실측 트래픽으로 검증 가능한가?
방법론: 아키텍처 설계, 네트워크 시뮬레이션 (analytical scalability + 실측 trace test-bed + dumbbell simulation)
데이터: NSF NMI ANI-0123939 grant. test-bed 10 router (Pentium III 997MHz Linux-2.4.7 + iproute2 + Diffserv kernel) × 30 source + 2 destination end host, 10Mbps 단방향 링크. CAIDA trace 150분 (2003.02.21, AS2641 최상위 + AS7377/AS1909/AS1668/AS1227/AS33 5 source), 20분 실험, reservation duration 평균 1분 exponential. dumbbell simulation 으로 state scalability 별도 검증, 호스트당 reservation 도착 Poisson rate 0.00001/s.
주요 발견: 1) BBRP signaling 부하: SIBBS 대비 52% 감소 (Section VI.B), aggregation level 증가 시 추가 감소; 2) trade-off: 12.5% over-provisioning; 3) state scalability: 100 source domain × 100 destination = SIBBS 10000 states vs BBRP 100 states (Section VI.D); 4) class-based traffic rate estimation: $R \geq m + Q^{-1}(l)\sigma$ 의 Gaussian CLT 근사가 Diffserv class 별 loss ratio 제약 $l$ 만족; 5) transit domain 에서는 measurement-based 가 19% over-reserved 자원으로 QoS 위반 가능 → transit 은 parameter-based, stub 은 measurement-based 구분 사용. multiplexing gain 은 transit 보다 stub 에서 큼.
시사점: BB 의 inter-domain reservation 을 individual pipe 가 아니라 destination region aggregation 으로 재정의하면 인터넷 scale (Internet 평균 AS path 4.9 hop) 에서 scalability 가 실제 작동. BGP-4 가 아닌 lightweight BB routing (BB-RIB: <destID, servID, nextBB, cost>) 으로 route flapping 도 완화 (existing reservation 영향 없음).

Diffserv 도메인 간 BBRP 의 BB 컴포넌트와 reservation·provisioning 운영 흐름.

요약

본 paper 는 Haci A. Mantar 의 박사 논문 정점 작업 (Haci A. Mantar 박사논문 “Scalable resource management framework for QoS-enabled multidomain networks”, Syracuse 2003, ref [3]) 으로 황준석 이 2저자, A Scalable and Efficient Inter-domain QoS Routing Architecture for Diffserv Networks 의 IM 2003 prototype 을 IEEE JSAC full journal 로 확장한 결정판이다. 출발 진단은 Diffserv + BB 가 next generation 인터넷의 QoS 표준 이 되려면 5 가지 미해결 이슈 — (1) dynamic network state 획득, (2) core router reservation 없는 정량 QoS, (3) 자기 도메인 너머 QoS·비용 정보, (4) 도메인 자원 효율 관리, (5) 이웃 BB 와 자원 협상 — 를 풀어야 한다는 점이다. 기존 pipe model (SIBBS, BGRP, TEQUILA, GlobalCenter, Khalil VPN, Okumus LSP) 은 source domain 에서 만 aggregation 하므로 transit 에서 state 수가 도메인 수 N 의 N² 로 폭발 — 인터넷 13,500 도메인 × 130,000 네트워크 에서 router 한계를 초과.

본 paper 의 핵심 design 은 BB 를 wholesale-retailer 패러다임으로 재정의하는 것이다. BB 가 provider 로부터 destination region + servID 단위로 자원을 사서 customer 에게 판매. 같은 <destID, servID> 인 incoming reservation 은 한 outgoing reservation 에 multiplexed. 4 핵심 컴포넌트: (1) BBRP (Inter-BB Resource Reservation and Provisioning Protocol) — SIBBS 의 RAR/RAA/CANCEL/CANCEL_ACK 메시지 재사용, (2) DPA (Dynamic Provisioning Algorithm) — 실제 traffic rate 모니터링 후 임계값 초과 시 BBRP trigger, (3) BB-RIB (Routing Information Base) — <destID, servID, nextBB, cost> 분산 라우팅 표, distance-vector flooding 으로 갱신, (4) RSC (Routing Setting Controller) — border router 설정. BB-RIB 핵심 design choice 는 existing reservation 은 갱신 안 됨 / future reservation 만 영향 으로 route flapping 완화.

운영은 2 단계로 분리: (a) Resource Reservation — BB 가 customer 자격으로 provider 와 협상, DPA 가 트리거, RAR → BB-RIB query → 최저 cost provider 선택 → 실패 시 다음 후보; (b) Resource Provisioning — BB 가 provider 자격으로 admission control, outgoing reservation 의 남은 자원으로 customer 요청 즉시 결정 (downstream BB signaling 불필요). 이 bilateral SLA + concatenation 구조로 multilateral SLA 의 복잡성 회피. Class-based rate estimation 은 Gaussian CLT 근사 — $R \geq m + Q^{-1}(l)\sigma$ , $\tau$ = delay bound 의 cushion 으로 measurement window 길이 결정. Stub 에서는 measurement-based, transit 에서는 parameter-based (peak rate) 적용 — 둘 모두 measurement-based 일 때 transit 의 19% over-reserved 자원이 QoS 위반 가능.

평가 결과는 인상적이다. 5-domain test-bed (CAIDA AS2641 + 5 source AS, Linux Pentium III router, 10Mbps 링크, 20분, 1분 평균 exponential reservation) 에서 BBRP 가 SIBBS 대비 (i) BB2↔BB1 signaling 메시지 수가 reservation 수의 일부에 불과, (ii) transit BB1↔BB4 signaling 부하 52% 감소, 자원 12.5% over-provisioning trade-off, (iii) 도착 path 가 길어질수록 (Internet 평균 4.9 AS hop) gain 증가, (iv) dumbbell simulation 에서 100 source × 100 destination 시 SIBBS 10,000 states vs BBRP 100 states. transit 의 statistical multiplexing gain 은 stub 보다 작음 — 이미 aggregated traffic 이라. 같은 시기 sibling An Implementation Study of a Dynamic Inter-Domain Bandwidth Management Platform in Diffserv Networks (NOMS 2004 의 implementation paper) 가 BBRP 의 IEEE/IFIP NOMS 발표 짝.

핵심 결과

측정	SIBBS (pipe)	BBRP	개선
transit signaling 부하 (Section VI.B)	100% (baseline)	48%	−52%
over-provisioning trade-off	0%	12.5%	(cost)
BB state 수 (100 src × 100 dst)	10,000 (O(N²))	100 (O(N×k))	99% 감소
forwarding path state	O(N²)	O(N)	1차 감소
BGP-4 의존	yes (BGP-4 + QoS extension)	no (lightweight BB-RIB)	route flapping 완화
inter-domain aggregation	source domain only	모든 domain	multiplexing gain ↑
transit measurement-based	(해당 없음)	19% over-reserve 시 QoS 위반 → parameter-based 사용 권고	(trade-off)

class-based rate estimation 의 핵심 결과: $R = m + Q^{-1}(l)\sigma$ 의 multiplier $Q^{-1}(l)$ 가 loss 제약 $l$ 별로 다른 추정률 산출 — class 1 (낮은 l) 은 보수적, class 3 (높은 l) 은 공격적, 적절히 설정하면 over-provisioning 과 over-estimation 양극 회피.

방법론 노트

핵심 분석 모형은 Gaussian CLT 근사를 사용한 class-based traffic rate 추정이다. 다수 reservation 이 한 queue 에 aggregated 될 때 aggregate rate 는 정규분포에 근사하며, sample window $T$ 의 mean $m$ 과 cumulative variance $\sigma^2$ 만으로 traffic 을 특징짓는다. class loss ratio 제약 $l$ 을 만족하려면 $\Pr(R(t) > R) \leq l$ 이 성립해야 하고, 이는 Gaussian approximation 으로

Q\!\left(\frac{R-m}{\sigma}\right) \leq l

가 되며, inverse transform 으로

R \geq m + Q^{-1}(l) \sigma

가 도출된다. admission control 의 충분조건은 new request 의 reservation rate $r^{\text{new}}$ 와 link capacity $C$ 에 대해

m + Q^{-1}(l)\sigma + r^{\text{new}} \leq C

다. window 길이 $T$ 는 delay bound $D$ 의 cushion 으로 설정 ( $T < D$ ). Identification 은 (i) stub vs transit 에서 estimation method (measurement-based / parameter-based) 분리, (ii) parameter-based 가 peak rate 만 사용해 deterministic 보장 강하지만 utilization 약, (iii) measurement-based 가 utilization 강하지만 transit 에서 QoS 위반 risk, (iv) Operation Region (high/low threshold) 의 width 가 signaling 부하·자원 utilization trade-off 의 control knob.

연구 계보

황준석 1기 bandwidth broker / QoS interconnection 라인의 마무리 정점 이자 Haci A. Mantar 박사 졸업 (Syracuse 2003) 의 결정판. 직접 predecessor 는 (1) QBone Signaling Design Team SIBBS (ref [1], 황준석 본인 참여), (2) Nichols·Jacobson·Zhang (RFC2638, 1999) Two-bit Diffserv Architecture — BB 개념 도입, (3) Mantar (PhD 2003, ref [3]) “Scalable resource management framework for QoS-enabled multidomain networks”, (4) Mantar·Hwang·Okumus·Chapin (SCI 2001, ref [4]) “Interdomain reservation via third agent”, (5) A Scalable and Efficient Inter-domain QoS Routing Architecture for Diffserv Networks (ref [5], IM 2003), (6) Okumus·Hwang·Mantar·Chapin (Globecom 2001, ref [6]) “Interdomain LSP setup using BMPs”, (7) Terzis·Wang·Ogawa·Zhang (Global Internet 1999, ref [7]) Two-Tier Resource Management, (8) Pan·Hahne·Schulzrinne (J. Commun. Networks 2000, ref [9]) BGRP, (9) Khalil et al. (ref [19]) BB for Diffserv VPN, (10) Chuah (UC Berkeley PhD 2001, ref [11]) Scalable framework for IP-network resource provisioning, (11) Black et al. (RFC2475, ref [12]) Diffserv architecture, (12) CAIDA 트래픽 trace (ref [26]). 같은 시기 sibling An Implementation Study of a Dynamic Inter-Domain Bandwidth Management Platform in Diffserv Networks (NOMS 2004 implementation 짝), A Scalable and Efficient Inter-domain QoS Routing Architecture for Diffserv Networks (IM 2003 RS prototype), Interprovider differentiated service interconnection management models in the Internet bandwidth commodity markets (BMP 최적화 모형), Cross-Network Open Provisioning Intelligent Network (COPIN) for Bandwidth Transaction Services in the Next Generation Internet (COPIN 원형) 와 함께 황준석 의 1기 BMP/BB 가족의 정점을 이룬다.

인접 그래프

1-hop 이웃 17개

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

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

이 문서를 가리키는 페이지

논문 (5)

인물 (1)

황준석