Congestion in Data Networks

혼잡이란

• 혼잡은 네트워크를 통해 전송되는 패킷의 수가 네트워크가 패킷을 다룰 수 있는 용량에 도달하면 발생
• 혼잡 제어의 목적은 성능이 급격하게 떨어지는 레벨 이하로 패킷의 수를 유지하는 것
• 데이터 네트워크는 큐의 네트워크이다.
• 일반적으로 80% 이용률이 되면 문제가 생김
• 유한한 큐는 데이터를 잃어버릴 수 있다는 것을 의미

노드의 큐

• 각각의 링크는 최소 한쌍의 버퍼를 가짐
• 하나는 전송버퍼 하나는 수신버퍼

큐의 상호작용

• 뒤의 큐가 다 차면 앞의 노드가 보낼 수 없음

이상적인 네트워크 이용

실제 - 혼잡 제어 X

혼잡 제어의 매커니즘

• Backpressure
• Choke packet : 혼잡이 발생하면 choke packet을 source에 전송
• Implicit : 지연, 폐기, 간접적
• Explicit : 패킷에 혼잡이 발생한 것을 표시 이진수, 크레딧, 속도

Backpressure

• 하나의 노드에서 혼잡이 발생하면 다른 노드로부터의 패킷의 흐름을 늦추거나 멈출 수 있음
• back에서 source까지 전파됨
• connection oriented
• X.25
• ATM이나 frame relay에 사용되지 않음
• IP에 의해 개발됨

Choke Packet

• Control packet
• 혼잡이 일어난 노드에서 발생
• source노드 쪽으로 전송
• ICMP(Internet Control Message Protocol)에서 사용

Implicit Congestion Signaling

• 묵시적
• 혼잡이 발생하면 전송 지연이 늘어남, 버퍼가 꽉 차서 패킷 손실률이 높아짐
  • 혼잡이 발생했다고 인식
• Source가 혼잡을 감지하고 흐름을 줄임
• 각자의 end system이 결정하는 형태
• Connectionless 네트워크에서 적합
• Connection oriented네트워크에서도 사용

Explicit Congestion Signaling

• Backwards
  • source 쪽으로 알려줌
• forwards
  • destination 쪽으로 알려줌
• destination이 source에게 알려줌
• offered load : 재전송하는 것까지 고려한 실제 load

Explicit Signaling Categories

Binary

• 0,1 혼잡의 유무를 1비트로 나타냄
• 1이면 혼잡

Credit

• 크레딧 : 전송할 수 있는 패킷의 수를 나타냄

Rate

• 속도를 제한

Traffic Management

공평성

• 네트워크를 사용하는 많은 소스&데스티네이션 페어에게 공평한 기회를 제공

서비스의 품질

• 차등화된 서비스 제공

예약

• 네트워크를 예약해서 사용
• 사용자와 네트워크 사이의 트래픽 계약
• 예약된 것보다 더 많은 트래픽이 발생하면 폐기시키거나 마킹
• 망이 여유 있으면 수용해 줌

패킷 스위치 네트워크에서의 혼잡 제어

• 컨트롤 패킷을 발생시켜 일부 또는 모든 노드에 보냄
• 부가적인 트래픽이 생김 -> 망이 더 악화됨
• 라우팅 정보에 의존적 -> 너무 빨리 반응할 수 있음
• End to end probe packet을 사용 -> 오버헤드 발생
• 측정하기 위한 패킷
• 혼잡 정보를 패킷에 추가하여 전송 – 명시적 방법
• Backward, forward

ATM Traffic management

• 고속망, 작은 셀 크기, 제한된 오버헤드 비트 -> 처리시간이 짧음
• 개발 중임
• 기존 툴이 ATM에 부적절한 이유
  • 트래픽의 대부분이 흐름제어 대상이 되지 않음
  • 전파지연에 비해 전송시간이 줄어들어 피드백이 느림
  • 트래픽 패턴이 다양
  • 서비스 종류가 다양
  • 스위칭 속도도 빠르고 전송속도도 빠름 -> 휘발성이 높음

Latency/Speed Effects

• ATM은 155 Mbps가 일반적
• 지연이 오래 걸리면 망이 바쁜 것을 알 수 있음 -> 망의 상태를 반영하여 컨트롤 -> 느림
• 지연과 loss를 측정하는 시간 동안 7.2* 106 bits가 전송이 이루어짐 – 해결이 안 됨
• source에서 destination까지의 길이가 미국의 경우 전파 지연이 오래 걸림
• 네트워크를 traverse 하는 데 걸리는 시간은 전파 지연과 스위칭 지연에 의해 결정됨
• 전파 지연은 빛의 속도의 2/3
• 빛의 속도 3*10^5km/sec
• 유선에서 이뤄지는 전파지연은 2*10^5km/sec

Cell delay variation

• Cell delay는 source에서 destination까지 걸리는 절대 시간
• 지연은 망의 상태에 따라 다르므로 평균 지연 사용
• 서비스 품질 관점에서 variation중요
• Cell delay variation이 작을수록 품질이 좋음
• ATM에서 음성, 비디오, 데이터는 셀들의 연속임, 셀을 통해 전송됨
• 네트워크를 통해서의 지연은 상당히 작음
• 전송 속도는 일정해야 함
• 하지만 Variation이 존재
• 지연 셀이 상대적으로 작아야 함
• 일정한 전송속도를 가져야 함

Timing of CBR Cells

• Cell delay variation을 일정하게 유지하는 방법
• 버퍼링 기능
• 다운로드하는 속도가 일정하지 않음
• 셀을 일정한 시간 간격으로 발생(전송)
• 네트워크에서의 지연은 일정하지 않음
• 일정한 간격으로 display 되기 원함
• 첫 번째 셀이 전송되고 목적지에 도착하자마자 display 하지 않고 queueing
• 네트워크 상황에 따라 추가적인 지연을 조절
  • 일정한 간격 유지
• 셀이 너무 늦게 도착한 경우 -> 버림
• V를 크게 잡으면 문제 해결됨 but 오래 기다려야 하고, queue가 길어야 하므로 메모리가 많이 듦

Network Contribution to cell delay variation

• Cell delay variation를 발생시키는 요소
• 패킷 스위칭 네트워크는 queuing delay와 routing 결정 시간에 의해 생김
• ATM에서는 cell delay variation이 frame relay보다 적음
• frame relay는 end to end control이고 가변길이
• ATM은 end to end control이고 패킷 고정길이
• ATM 프로토콜은 처리 오버헤드를 최소화하도록 설계
• 처리량이 매우 높음
• 혼잡이 있을 때만 지연이 생김 -> 혼잡이 발생하지 않도록 load를 유지해야 함
• 혼잡이 발생할 것 같으면 받지 않아야 함 -> preventive control

Cell delay variation at the UNI

• 3가지 layer
  • Physical, ATM, ATM adaptation
• 다른 연결로부터 셀이 들어온다
• Operation and maintenance cell이 끼어들음
• 디지털 계층 프레임을 사용하면 physical layer에서 삽입됨
• 이러한 지연을 예측할 수 없음

Origins of Cell Delay Variation

• A는 x속도, B는 y속도
• Adaptation layer에서 48byte로 잘라서 header를 붙임
• ATM layer에서 header 붙음
• OAM cell은 네트워크에서 발생하는 셀 -> 랜덤 하게 발생함
• 일정한 간격으로 보내지지만 전해질 때는 일정하지 않음

Traffic Control and Congestion Control Function

• Long term : 긴 시간 한번 virtual path를 설정하면 오랫동안 사용
• Connection duration : connection admission control 망의 서비스를 받기 위해서는 사용자는 망에 신고하여 수용되면 서비스를 받을 수 있음
• round-trip propagation time : 왕복하는 동안 이루어지는 형태, Fast resource management가 traffic control 상황에서 이루어짐
• explicit forward congestion indication(EFCI), ABR flow control
• cell insertion time : 연결이 설정되고 나서 셀이 전송
• UPC (usage parameter control)
• Priority control
• Traffic shaping : 트래픽이 들어오는 모양을 바꾸는 것

Traffic management and congestion control techniques

• Virtual path를 사용하여 자원을 관리
• 연결 설정 관리
• UPC 모니터링
• 선택적인 셀 삭제
• 트래픽이 일시적으로 많이 몰리면 버퍼를 써서 순화시킴

Resource Management using virtual paths

• 같은 virtual path를 사용하면 품질이 비슷 (지연 비슷, cell loss확률도 비슷)
• 사용자와 사용자 연결
• 사용자와 네트워크 연결
• 네트워크와 네트워크 연결
• 품질에 관련된 파라미터
• Cell loss ratio : 낮아야 함
• Cell transfer delay : 낮아야 함
• Cell delay variation : 낮아야 함

Configuration of VCCs and VPCs

• 채널들이 모여서 virtual path가 됨
• Virtual path switch – 다수개의 virtual channel을 수용
• 같은 Virtual path는 퀄리티가 같고 source and destination이 같음
• Virtual path switch :
• semi-permanent switching

Allocation VCCs within VPC

• 하나의 VP가 다수의 VC를 가질 수 있음
• 하나의 Virutal path connection 안의 Virtual channel은 비슷한 네트워크 성능을 가짐
• 채널을 할당하는 방식
• Peak를 기반 – 장점 : 퀄리티가 확실히 보장, 채널의 이용률이 저조
• 통계적 다중화를 기반 – 평균값을 이용 이용률을 높일 수 있지만 퀄리티가 보장되지 않을 수 있음

Connection Admission control

• 협상 파라미터
• Peak cell rate(PCR)
• Cell delay variation(CDV)
• Sustainable cell rate(SCR) – 평균
• Burst tolerance – 이것이 크면 variation이 큼

Procedures Used to Set Values of Traffic Contract Parameters

• Explicitly specified parameters
• Implicitly specified parameters
• SVC switched virtual connection : signaling 의해서 설정됨
• PVC permanent virtual connection : network management system에서 이루어짐

Traffic Rate management

• 혼잡이 일어나면 일부 셀을 폐기시킴
• 폐기시키는 규칙
• Arbitrarily 임의적으로 source와 관련 없음
• End system이 빠를 속도로 전송할 수 있도록 제한하지 않음
• Committed information rate(CIR)
• Committed burst size
• cir보다 낮게 들어오면 모두 수용
• cir 넘는 것은 수용은 하되 넘친 것에 대해 마킹함
• 마킹한 것은 망이 바쁘지 않으면 서비스하고 아니면 폐기
• Excess를 넘기면 무조건 폐기 처분

Usage parameter control(UPC)

• 모니터링함 -계약한 대로 이행하고 있는지 확인
• 하나의 연결이 예약한 것보다 많이 들어오는 것을 막기 위해
• VCC, VPC에서 이루어짐
• Peak cell rate와 cell delay variation을 체크
• Sustainable cell rate와 burst tolerance을 체크

Cell rate algorithm

• 트래픽 흐름은 허용된 피크 치를 넘어가는지 확인
• Leaky bucket 알고리즘
• 수용된 셀을 허용
• 패킷이 전송되기 위해서는 토큰이 필요
• 토큰이 컨트롤
• 토큰을 발생하는 속도 중요
• 버킷의 사이즈 중요 - peak 치를 제어
• 토큰이 1초에 하나씩 발생
• 셀이 1초에 한 개씩 들어옴
• 입력이 들어오는 트래픽의 모양과 출력이 나가는 트래픽의 모양이 달라짐 -> 트래픽 shaping
• 트래픽 발생률을 바꿈으로 인풋의 비율도 바꿀 수 있음

Selective cell discard

• CLP(cell loss priority)에 의해 셀을 삭제
• CLP가 1이면 우선적으로 폐기
• CLP가 1이면 low priority
• 혼잡이 발생하면 폐기시킴
• CLP를 1로 할 수 있는 것
• 네트워크에서 UPC초과하면 1로 set
• Customer가 우선순위가 높은 것과 낮은 셀을 가짐
• User가 마킹을 보낼 수 있음
• 네트워크는 망이 바쁘면 CLP1인 경우 우선적으로 폐기함

Traffic shaping

• Input이 들어오는 트래픽 패턴을 네트워크에 가해지는 트래픽 패턴과 다르게 하는 것
• 버퍼링을 통해
• UPC는 traffic policing으로 불림 – 트래픽 정리
• 급격히 변하는 트래픽 양을 완화시켜 줌
• Token bucket을 이용
• 급격한 변화를 완만하게 만듦

Token Bucket for traffic shaping

• 셀이 망에 들어오기 위해서는 토큰을 하나씩 달고 들어옴
• 버킷의 사이즈에 따라 들어갈 수 있는 양이 제한됨
• 들어오는 트래픽 형태와 나가는 트래픽 형태가 다름 – 완만해짐

GFR traffic management

Guaranteed frame rate(GFR) 은 LAN, ATM 인터페이스 하기 위해 사용

• 전송단위 프레임
• 단순함
• ATM네트워크에서 순한 요구조건이다
• end시스템은 policing이나 shaping을 하지 않음
• ATM adapter에 line rate로 전송할 수 있음
• 전송이 보장되지는 않음
• TCP
• Virtual channel단위로 이루어짐
• 최소 속도는 보장
• 혼잡이 발생하지 않으면 더 빠른 속도로 전송할 수 있음

GFR contract parameter

• Peak cell rate(PCR)
• Minimum cell rate(MCR)
• Maximum burst size(MBS)
• Maximum frame size(MFS)
• Cell delay variation tolerance(CDVT)

Components of GFR System Supporting rate guarantees

• UPC – service conformance mechanism
• F-GCRA (frame generic control rate algorithm) – QoS eligibility test mechanism
• Buffer management – 버퍼에 따라 공평하게 전송할 기회를 갖게 함
• Scheduler

Tagging and policing

• 초과된 것에 대해 태깅함 - CLP를 1로
• 보장되지 않는 것 우선순위가 낮은 것
• 태깅은 네트워크가 할 수도 있고 source가 할 수도 있음
• 네트워크는 CLP가 1인 셀을 폐기시킬 수 있음
• 셀 폐기가 policing 기능임

Buffer Management

• 버퍼가 많이 차 있으면 혼잡이 발생할 수 있다고 봄
• 버퍼가 많이 차면 폐기시켜야 함
• 공평성을 보장하기 위해 virtual channel 단위로 버퍼를 함
• Thresholds 값을 넘으면 바쁘다고 보고 셀을 폐기함

Scheduling

• Tagged와 untagged가 있음
• Untagged cell의 우선순위가 높음
• VC에 따라 다룸
• 공평성을 제공해야 함

GFC conformance definition

• 하나의 프레임에는 CLP값이 같아야 함
• 프레임에 있는 모든 셀은 같은 CLP를 가짐
• 셀의 전송 속도는 예약한 만큼 보장받음
• 프레임의 마지막 셀인지 or 셀의 카운트 값이 MFS(Maximum frame size) 보다 작은 지 확인
• MFS보다 작으면 수용해 줌
• 셀이 수용되면 전송이 보장되어야 함
• 모든 셀이 수용되면 프레임이 수용됨

GFR VC Frame categories

• Nonconforming frame
• 태그 되거나 폐기됨
• Conforming but ineligible frame
• Conforming and eligible frames
• 전송이 보장됨

QoS eligibility test

• 두 단계를 거쳐 이루어짐
• 계약한 대로 들어오고 있는지 체크
• 계약이 어겨지면 폐기되거나 태그 됨
• 태그 된 셀은 경우에 따라 전송이 이루어지고 망이 바쁘면 전송이 안됨
• 수용된 프레임은 각각의 virtual channel관점에서 협상한 값보다 적은 트래픽을 가짐
• Lower bound
• threshold보다 작은 값을 가지면 -> 계약한 것보다 적은 트래픽이 들어오는 경우
  • 전송이 항상 보장되어야 함