QoS Routing in the Internet Dept. of Computer Science Information Networking & Computing Lab. Gyung-Gui Moon 2019-05-06

Contents Background Framework for QoS-based Routing Interaction between QoSR and RSVP QoS Multicast Routing Summary 2019-05-06

Background 기존 라우팅과 QoS 라우팅을 간단하게 비교한다. 2019-05-06

Conventional Routing Destination oriented Always use minimum cost paths Optimize for a single arbitrary metric Focus on connectivity Support best-effort datagram service 단일 메트릭의 예: 홉 수, 지연, 링크 이용률 등 개개의 데이터그램을 전달하는 경로를 제공 2019-05-06

QoS-based Routing(QoSR) Find efficient paths for flows with satisfying specific QoS requirements Each flow defined as a sequence of packets that require special handling Need to be aware of network state Need to use the network efficiently IETF WG definition A routing mechanism under which paths for flows are determined based on some knowledge of resource availability in the network as well as the QoS requirements of flows -- A Framework for QoS-based Routing in the Internet QoS 라우팅을 통해 기대되는 효과는 사용자들에게 제공되는 서비스를 개선시킬 수 있다는 점과 전체 망 이용 효율을 개선시킬 수 있다는 점이다. 사용자들에게 제공되는 서비스 개선: Flow가 요구하는 QoS를 만족시키기 위해서는 망 자원 상태에 대한 정보가 필요 전체 망 이용 효율 개선: 망에 흐르는 flow 수, 망에서 사용 중인 대역폭 양 등이 효율 척도가 된다. 2019-05-06

Why Need QoSR? Bandwidth is abundant, no need for the extra complexity Proper network design will eliminate hot spots, no need for load sensitive routing Nevertheless not everywhere transient traffic/network capacity mismatch link failures 망 부하나 자원 상태를 고려하는 QoS 라우팅의 필요성 모든 망에 자원이 풍부하지 않다. 수요와 공급이 일치하지 않는 부분이 발생한다. 뛰어난 망 설계도 망의 일부가 고장을 일으킬 경우 원래의 기능을 하기 어렵다. 2019-05-06

QoSR Problems at a Glance Accurate network state information expensive to maintain Compute QoS paths satisfying multiple constraints intractable to solve How to find efficient paths in long-term view 정확한 망 자원 상태 정보를 유지하기 위해서는 상당한 비용이 수반 장기적인 안목에서 망 이용 효율을 높일 수 있는 경로 선택의 어려움 2019-05-06

Framework for QoSR IETF QoSR WG에서 작성한 프레임워크 문서 내용을 살펴본다. 2019-05-06

Standard Works on QoSR QoSR working group in IETF since 1997 Intradomain QoS routing based on OSPF Back to the framework document Work closely other routing protocol working group such as OSPF, IDR, BGP, and IDMR Close relationship with RSVP,IntServ, and ISSLL RFC 2386 (Aug. 6, 1998) -- A Framework for QoS-based Routing in the Internet 초기에는 OSPF 프로토콜을 확장해 QoS 라우팅을 지원하는 방법에 관한 연구가 주로 이루어졌다. 그러나 QoS 라우팅에서 해결해야 할 문제들이 많음을 인식하고 현재는 이러한 문제들과 접근 방안을 중심으로 한 프레임워크 문서 작성에 주력하고 있다. 라우팅 분야: OSPF, IDR, BGP, IDMR 트랜스포트 분야: RSVP, IntServ, ISSLL 2019-05-06

Framework for QoSR Philosophy Background Several Issues Best-effort and QoS-based routing QoS-based routing and resource reservation Several Issues Intradomain and interdomain routing requirements QoS-based multicast routing Related work Summary 인터넷 라우팅은 그 작업 계층에 따라 인트라도메인 라우팅과 인터도메인 라우팅으로 구분되어 연구와 구현이 이루어지고 있다. QoS 라우팅도 이와 동일한 방법으로 인트라도메인 영역과 인터도메인 영역을 구분해 연구하는 것이 필요함을 설명하고 있다. 멀티캐스트 flow를 지원하기 위한 QoS 라우팅 모델 설명 관련 연구로는 전화망과 ATM망에서 연구되고 있는 QoS 라우팅에 관한 내용을 설명하고 있다. 2019-05-06

Framework for QoSR Issues QoS determination and resource reservation Granularity of routing decision Metrics and path computation Administrative control Routing overheads Routing for multicast flows Scalability 사용할 수 있는 자원이 현재 얼만큼 있는지를 알아야 하는 문제 최종 목적지를 기준으로 한 라우팅이 아닌 flow를 기준으로 한 라우팅 다양한 메트릭을 만족시키는 경로를 선택하는 문제 전체 망 이용 효율을 높이기 위해 경로 선택을 제한하는 문제 계산, 통신, 저장 비용을 줄이는 문제 멀티캐스트 flow를 지원하기 위한 여러가지 문제 망 자원 정보를 합치는 과정에서 정확성 손실이 발생하기 때문에 규모 확장성을 얻기 위한 다른 방법이 필요 2019-05-06

Interaction between QoSR and RSVP QoSR과 RSVP 상호 의존 관계를 살펴보고 RSVP를 어떻게 QoSR과 연계 시킬 것인가에 관한 문제를 살펴본다. 2019-05-06

QoSR Operating Requirements QoSR operations Path determination Path management Requirements from definition QoS requirements of flows knowledge of resource availability in the network specific mechanism to identify flows with QoS requirements RSVP PATH messages serve as the trigger to the QoS routing. QoSR은 크게 경로를 결정하는 작업과 결정된 경로를 관리하는 작업으로 구성된다. Flow가 요구하는 QoS는 경로 결정 작업에 필요하고, 망 자원 가용 정보는 경로 결정 및 경로 관리 작업에 모두 필요하다. 우선 flow가 요구하는 QoS를 라우팅 프로토콜에 알려줄 방법이 필요하다. 이를 위해 RSVP를 이용한다. RSVP는 flow가 요구하는 QoS를 토대로 망 자원을 예약하는 프로토콜이다. 구체적으로 설명하면, RSVP flow QoS를 포함한 PATH 메시지를 라우팅 프로토콜에 전달해 새로운 경로를 결정할 수 있게 한다. 2019-05-06

RSVP Protocol operation flow The sender sends a PATH msg to receivers along the path selected by the routing protocol and path determination. The routers on the path receive the PATH msg and record the state of the path. Upon receiving the PATH msg, receivers send a RESV msg to the upstream next hop. Each router that received the RESV msg sets up to reserve network resources for the desired QoS. When the sender receives the RESV msg, the sender sends data packets. 2019-05-06

RSVP Operation Flow RESV 메시지는 필요에 따라 merge 작업을 거친다. 2019-05-06

QoSR and RSVP Cross dependent From QoSR to RSVP From RSVP to QoSR QoSR provides a path for RSVP to deliver PATH messages. From RSVP to QoSR RSVP provides QoS requirements using PATH messages for QoSR to determine a path. QoSR은 flow QoS를 만족할 경로를 제공 해줄 뿐 자원을 예약하지 않는다. RSVP는 flow QoS를 토대로 자원을 예약하지만 경로 결정을 하는 것은 아니다. 2019-05-06

QoSR Path Management Variations to affect QoS path network topology traffic QoS requirements network load QoSR path management recalculates, adjusts and maintains paths based on variations ensures such changes not reflected on existing paths avoids potential oscillations between paths 망에는 결정된 QoS 경로에 영향을 주는 요소들이 많다. QoSR 경로 관리는 여러 요소들의 변화에 따라 경로를 재계산, 조정, 유지하는 작업이다. 경로 관리 중 중요한 일은 이러한 변화가 기존 QoS 경로에 영향을 주지 않도록 하는 것이다. 2019-05-06

Oscillations between Paths Sample Topology 2019-05-06

Oscillations between Paths - 1st S - C - B - A - R0 1) RSVP 첫번째 PATH 메시지 flow QoS 9Mbps 2) QoSR 첫번째 경로 결정 --- 망 자원 상태 변화 3) 망 자원 상태 변화 때문에 다음번 refresh PATH 메시지 생성시 새로운 경로 요구 2019-05-06

Oscillations between Paths - 2nd S - F - E - D - A - R0 1) 두번째 경로 설정 --- 망 자원 상태 변화 2) 망 자원 상태 변화 때문에 다음번 refresh PATH 메시지 생성시 새로운 경로 요구 3) 첫번째 경로 설정 -- 망 자원 상태 변화 2019-05-06

Path Pinning Mechanism What is path pinning? An existing path will not be replaced by a better path unless the existing one is no longer usable. Requirements of path pinning mechanism state information associated with a QoS path to determines its current validity the resources already allocated to a flow on various links 기존 경로가 유효하다면 더 좋은 경로가 있어도 경로를 바꾸지 않게 하는 기법을 경로 고정 기법이라고 한다. 라우터가 어떤 flow를 흘려보내고 있다면 라우터는 flow가 얼만큼의 자원을 사용하고 있는지 알아야 한다. 결국, Flow별 자원 사용 정보는 flow가 흐르는 경로 위에 있는 라우터들은 알고 있어야 경로 고정을 할 수 있다. 2019-05-06

QoSR Path Management Study Where should it be placed in? place path management in RSVP place path management in QoSR Research issues how to maintain and advertise the state information required for path management define how, when, and where path pinning and unpinning is to take place 2019-05-06

Related Work 1: QOSPF Quality of service extensions to OSPF(QOSPF) Z. Zhang, C. Sanchez, B. Salkewicz and E. Crawley Bay Networks, Inc. / Gigapacket Networks, Inc. Internet Draft, 1997 (2nd ver. Available) Retrofitting OSPF for QoSR Focus on unicast flow, partly multicast flow 2019-05-06

QOSPF Path Determination Network topology state information OSPF LSA(link state advertisement) flooding Network resource state information RES-LSA(link resource advertisement) flooding RRA(resource reservation advertisement) flooding Flow QoS requirements information TSpec of the RSVP PATH message Metrics enough bandwidth least delay OSPF에서는 링크 상태를 전파시키기 위해 LSA 패킷을 이용한다. QOSPF는 추가로 망 자원 상태를 전파시키기 위한 LSA 패킷을 가지고 있다. 이 LSA 패킷에 포함된 정보를 가지고 경로 결정 작업을 수행한다. 2019-05-06

QOSPF Path Management RES-LSA flooding RRA flooding Path pinning available link resources on a router RRA flooding existing link resource reservations used by a flow on a router flooding into all the routers in a routing area Path pinning set pin flag in RESV message and its corresponding RRA packet links with existing reservations for the flow preferred in running Dijkstra algorithm 특히 flow가 점유하고 있는 자원 정보를 포함한 RRA는 망 내부의 모든 라우터들에게 전파된다. 이런 망에 전파되는 자원 상태 정보를 가지고 경로 관리를 수행한다. 경로 고정은 RESV 메시지에 pin flag를 설정해 이루어진다. 그리고 고정된 경로는 경로 결정 과정에서 우선적으로 선택된다. 2019-05-06

QOSPF Comments RRA flooding not scalable Explicit routes to handle the scalability problems source routes pre-calculated and cached at the sources 소스 라우터가 경로를 결정하고 이 경로 위에 라우터들은 RRA 패킷을 망 전체가 아닌 소스 라우터에게만 전달한다. 2019-05-06

Related Work 2: PQC Path QoS collection for stable hop-by-hop QoSR Y. Goto, M. Ohta and K. Araki Kyushu University / Tokyo Institute of Technology Proceeding INET ‘97, 1997 Path QoS Collection(PQC) Focus on unicast flow, partly multicast flow 2019-05-06

PQC Operation Flow Each router Apply piggyback mechanism to RSVP receives generic link states by QoSLSAP receives information about resources used by the flow with RSVP PATH message corrects generic link states by QoSLSAP using information on PQC performs Dijkstra algorithm to decide the best path Apply piggyback mechanism to RSVP QoSLSAP는 QOSPF의 RES-LSA 역할을 담당한다. Flow가 사용하는 자원 정보는 flow가 흐르는 경로 위의 라우터들에게만 전달된다. 경로 결정은 자원 정보를 토대로 수정된 망 위에서 이루어진다. RSVP PATH 메시지에 정보를 얹어보내는 방식 2019-05-06

QOSPF vs. PQC Sample Topology 2019-05-06

QOSPF QoS Paths 1st Path (9Mbps) explicit pinning 2019-05-06 소스부터 차례로 hop-by-hop 라우팅이 이루어진다. 경로는 RESV 메시지가 거꾸로 올라오면서 고정된다. 2019-05-06

QOSPF QoS Paths 2nd Path (15Mbps) explicit unpinning 2019-05-06 2번째 경로도 같은 방법으로 결정된다. 동일한 소스로부터 나오는 flow이기 때문에 경로를 합치는 것을 고려해 볼 수 있다. 경로를 합치기 위해서는 2개의 RESV 메시지가 만나는 지점에서 이미 명시적으로 고정된 경로를 고정 해제하고 새로운 경로를 고정해야 하는지를 해결해야 한다. 따라서 여기에는 명시적으로 이런 중첩을 resolution 하는 메커니즘이 필요하게 된다. 2019-05-06

PQC QoS Paths 1st Path (9Mbps) implicit pinning 2019-05-06 경로는 수신자 라우터로부터 hop-by-hop 방식으로 결정된다. 경로 고정은 묵시적으로 이루어진다. 이것은 PQC를 통해 얻은 정보를 가지고 원래의 망 상태를 복원할 수 있고, 이 때문에 경로를 재계산해도 같은 경로가 묵시적으로 계속 선택되게 된다. (다음 페이지에 PQC 그림 추가) 2019-05-06

PQC Information Flow 2019-05-06

PQC QoS Paths 2nd Path (15Mbps) implicit unpinning 2019-05-06 2번째 경로가 결정되는 과정에서 2개의 RESV 메시지가 만나게 되면 특별히 고정을 해제하기 위한 resolution(해결) 과정 없이 RESV 메시지 정보를 토대로 재계산을 수행한다. 재계산 결과 2개 RESV 요구 중 큰 쪽을 충족시키는 새로운 경로를 결정하게 된다. 결국 경로 고정과 마찬가지로 경로 고정 해제도 묵시적으로 이루어지는 것이다. 2019-05-06

PQC Comments PQC is more scalable than QOSPF. Not using RSVP reverse path mechanism PQC additive collection makes a difference between downstream and upstream routers. Carrying a lot of routing related information over RSVP messages increases overhead. 위 멀티캐스트 flow 예에서 다른 branch에 있는 라우터는 다른 branch 정보를 알 수 없다. 2019-05-06

Related Work 3: QoS-OSPF QoS routing mechanisms and OSPF extensions R. Guerin, S. Kamat, A. Orda, T. Przygienda and D. Williams IBM T. J. Watson Research Center / Bell Labs. Internet Draft, 1998 (4th ver. Available) Retrofitting OSPF for QoSR Focus on unicast flow 2019-05-06

QoS-OSPF Path Determination Each QoS capable router dedicates its resources to satisfy the flow QoS identifies and advertises the amount of its available resources Flow QoS requirements information TSpec of the RSVP PATH message Metrics enough bandwidth minimum hop Policy based approach 2019-05-06

QoS-OSPF Path Management Path pinned while it satisfies the flow QoS Extend RSVP for path pinning and unpinning Path pinned while processing PATH messages Path unpinned when corresponding path states are removed parameters received in PATH messages change local admission failure error after receiving a RESV message failure notification of a local link belonging to the path QOSPF에서 경로 고정은 RESV 메시지를 처리하는 과정에서 이루어지는 것에 비해 QoS-OSPF는 PATH 메시지를 처리하는 과정에서 이루어진다. 경로 고정과 고정 해제의 판단 기준은 flow QoS를 만족시킬 수 있느냐에 달려 있기 때문에 실제 flow QoS가 얻어지는 RESV 메시지 처리 과정에서 고정을 하는 것이 더 자연스럽다. (뒤에 수신자로부터 경로를 결정할 때는 더욱 당위성을 가진다.) 2019-05-06

QoS-OSPF Loop Handling Hop-by-hop processing QoS path introduces the possibility of loops When routers use inconsistent information to make QoS path determination Handle and prevent loop while processing PATH messages check change of PHOP value check change of TTL value 2019-05-06

QoS-OSPF Loop Detection Loop Detection by Checking PHOP Value Change 2019-05-06

QoS-OSPF Loop Detection Loop Detection by Checking TTL Value Change 2019-05-06

QoS-OSPF Comments Merge RSVP and QoS path management Explicitly define how, when, and where path pinning and unpinning is to take place Reduce path management overhead with QoSR Other research places path management in QoSR using RSVP as a proxy. Explicit path determination instead of hop-by-hop path determination RSVP 메시지 처리 과정에 경로 관리에 필요한 여러가지 정보와 규칙을 적용시켰다. Expicit 경로를 이용하는 것은 hop-by-hop 방식에서 발생하는 loop 문제를 제거하기 위해서이다. 2019-05-06

QoS Multicast Routing 2019-05-06

QoSR vs. RSVP RSVP designed to operate independent of the underlying routing scheme RSVP PATH messages establish the reverse path for RESV messages. Some QoSR computes a QoS path after receiver reservation. RSVP sender-directed signaling model is incompatible with receiver-directed QoSR scheme. RSVP는 라우팅 프로토콜에 목적지 주소만을 주고 PATH 메시지를 전달할 경로를 전달받는다. RESV 메시지는 이 경로를 따라 거꾸로 전달된다. 좀 더 정확한 flow QoS는 수신자가 정하는 것이기 때문에 QoSR은 수신자 자원 예약 후에 경로를 결정하게 된다. 다음 예를 통해서도 알 수 있듯이 RSVP의 역경로와 QoSR의 QoS 경로는 반드시 일치하지 않는다. 2019-05-06

Reconciliation with RSVP QoSR determines a QoS path based on the sender traffic advertisement. Compatible with RSVP signaling model Limitation maximum reservation derived from sender advertisement homogeneous receiver reservations in multicast flows 이런 비호환성 문제를 해결하기 위해 관련 연구들에서는 RSVP로 하여금 목적지 주소 이외에 소스 트래픽 사양 정보를 PATH 메시지에 담아 라우팅 프로토콜에 전달하는 방식을 사용하고 있다. 이렇게 되면 라우팅 프로토콜이 RSVP에 돌려 주는 경로는 best-effort 경로가 아닌 QoS 경로가 된다. PATH 메시지에 담긴 소스 트래픽 사양은 flow가 요구하는 최대 QoS 정보이기 때문에 이를 기준으로 결정된 QoS 경로는 수신자가 요구하는 QoS보다 초과된 용량을 전달할 수 있는 경로가 된다. 멀티캐스트 flow 경우, 이 방식은 소스가 주는 정보로 QoS 경로를 결정하기 때문에 수신자의 이질성이 고려되지 않는다. 2019-05-06

Multicast Routing with RSVP RSVP reservation model multicast connection oriented receiver initiated heterogeneous reservation shared reservation Receiver-oriented QoS multicast routing model RSVP 예약 모델은 멀티캐스트에서 다수 수신자 위주 이질적인 자원 예약을 지원하는 것을 설계 원칙으로 하고 있다. RSVP 예약 모델의 설계 원칙과 호환되는 QoS 멀티캐스트 라우팅 모델을 연구하게 되었다. 2019-05-06

QoS Multicast Routing Model Sender delivers traffic advertisements via a best-effort multicast tree. Receivers generate resource reservation requests. Multicast routing scheme determines the QoS multicast tree with sufficient resource. Branches of a multicast delivery tree are built independently by various receivers. Incompatible with RSVP signaling model 소스가 전파하는 트래픽 사양 정보는 RSVP PATH 메시지 등을 이용할 수 있고, 수신자가 만드는 예약 요구는 RESV 메시지 등을 이용할 수 있다. QoS 멀티캐스트 트리의 각 branch는 수신자와 연결된 라우터들에 의해 개별적으로 구성된다. PATH 메시지가 전달된 경로로 반드시 RESV 메시지가 전달되지 않기 때문에, RSVP가 가정하고 있는 여러가지 프로토콜 symantic이 깨지게 된다. 2019-05-06

QoS Routing for Multicast Flow Existing QoS Multicast Tree Best-effort Multicast Tree 두번째 그림의 best-effort 멀티캐스트 트리는 소스 트래픽 사양 정보를 담고 있는 메시지가 전달되는 경로 2019-05-06

QoS Routing for Multicast Flow Resource Request of R4 New QoS Multicast Tree 2019-05-06

QoS M’cast Routing Issues Scalability reducing the overhead of discovering receivers reducing the overhead to control flow-specific state information Efficiency uncoordinated construction of various branches reducing the total resource allocated for a multicast flow 수신자 발견 오버헤드는 기존 멀티캐스트 라우팅에서도 필요한 사항 멀티캐스트 flow 경우에 각 라우터는 자신이 구성할 branch를 위해 다른 branch에서 이 flow가 얼만큼의 자원을 사용하고 있는지 알아야 한다. 또한, 이런 자원 사용 정보는 branch 위의 라우터들이 전파시켜야 한다. 이 정보의 전파 범위는 멀티캐스트 flow를 형성하는 구성원들에 대한 정보로부터 얻어지는 것이기 때문에 이들 정보에 대한 오버헤드도 고려해야 한다. Branch 형성이 개별적으로 이루어지기 때문에 효율적인 구성이 이루어지기 어렵다. 2019-05-06

QoS M’cast Routing Comments QoS multicast routing model utilizes separated, per-source delivery trees for routing flows. Possible utilization of shared, per-group delivery trees for routing flows How to compute and use such shared delivery trees How to limit flow-specific information in making multicast routing decisions How to manage several unicast paths to improve the efficiency QoS 멀티캐스트 라우팅에서 경로 고정 및 고정 해제는 어떻게 할 것인가? 이전 연구들에서 경로 고정 및 고정 해제는 RSVP 임시 상태 기법을 연장해 처리할 수 있었다. 그러나 RSVP 프로토콜 semantic을 깨트린 상황에서는 어떻게 할 것인가? 2019-05-06

Summary 2019-05-06

Summary Ongoing update of the framework for QoS-based routing in the Internet RFC 2386 released Aug. 6, 1998 More reconciliation between QoS-based routing and RSVP required Details of QoS multicast routing scheme required 2019-05-06

Any comments will be appreciated gmoon@brutus.snu.ac.kr 2019-05-06