Grace

❗ network jitter를 해결하기 위한 DASH와 manifestfile

streaming 서비스에서는 네트워크 jitter(network delay)가 존재한다. 서버에서 영상을 받는 과정에서 딜레이가 발생할 수 밖에 없다. 딜레이를 방지하기 위해 버퍼링 시간을 가진다. 이것이 유튜브에서 영상을 클릭하는 순간 곧 바로 재생되는 것이 아니라 순간적으로 버퍼링이 걸리는 이유이다. 버퍼링은 버퍼를 채우는 과정이다. 클라이언트에서의 영상재생 속도보다 서버에서 받아오는 영상 데이터 량이 더 느리다면 영상이 끊기고 다시 버퍼링이 시작된다.

버퍼링이 길면 데이터를 많이 받은 후에 시작하는 것이기 때문에 영상시청 중간에 끊길 확률이 적다. 하지만 너무 길면 유저의 이탈률이 늘어날 것이다. 사람의 인내심과 영상이 끊기지 않은 정도 사이의 중용을 지켜야한다.

youtube ↔ client 통신은 에플리케이션간 통신으로 tcp 혹은 udp 에 의존한다.

udp를 쓰면 인코딩된 bps를 충족하는 속도로 server가 영상을 보낼 수 있지만 네트워크 상황을 고려하지 않기 때문에 네트워크 환경이 일정 수준 이하로 떨어지면 영상의 퀄리티에 심각한 피해가 생긴다. 그렇다고 tcp를 쓰자니 서버가 전송 속도를 조절할 수 없기에 원활한 서비스를 제공할 수 가 없다.

youtube에서 실제 사용하는 방식은 tcp를 사용하되 application layer에서 DASH라는 기술을 이용하는 방식이다. DASH는 Dynamic Adaptive Streaming Http의 약자로 네트워크에 적응하며 동적으로 http 스트리밍을 하는 방식이다. 이를 구현하기 위해 manifest file이 사용된다.

manifest이란?

영상이 업로드 될때, 영상전체가 올라가는 것이 아니라 256kb정도의 chanks로 분할되어서 저장된다. 또한 동일한 chanks에 대해서 여러개의 coding rate version이 생성된다.(128kbps, 256kbps, 512kbps, 1mbps, 2mbps, …) 유튜브에서 영상을 클릭하면 유튜브 서버는 클라이언트에게 manifestfile 을 넘겨준다. 그때 그때 네트워크 상황에 맞는 청크를 요청해서 가져온다. 이는 영상 중간에 화질 바뀌는 이유이다.

[manifestfile 예시]

❗ 서버 부화 방지와 통신속도 상향을 위한 CDN 분산저장(content delivery network)

manifestfile를 받아서 네트워크 환경에 따라 다른 버전의 chanks를 요청한다고 해도 많은 사용자가 서버 한곳에 몰리게 되면 과부화가 걸릴 수 밖에 없다. 이것을 해결하기 위해 전세계 CDN업체에 각 chanks를 분산저장하는 방식이 사용된다.

[구현원리]

manifestfile의 chanks URL의 ip를 알아내기 위해 cdn업체의 dns 서버에 접근하게 된다.(URL이 CDN 업체의 URL이기 때문이다.) 이때 요청자의 ip 주소를 기반으로 요청자의 위치와 가장 가까운 cdn 서버의 ip를 준다.

cdn위치는 사용자에게 가장 가까운 곳에 존재하는 것이 유리하다. 그래서 보통 access network(skt ,kt같은)의 내부 혹은 근처에 CDN이 즐비해 있다.

priority_queue를 사용한 dijkstra 알고리즘으로 접근했다.

4방향으로 탐색을 하면서 pq를 통해 최소경로을 탐색해준다.

#include <iostream>
#include <math.h>
#include <vector>
#include <queue>
#define INF 987654321
#define NODEN 126

using namespace std;

int a[NODEN][NODEN];
int dist[NODEN][NODEN];
int fdx[4] = {0, 0, 1, -1};
int fdy[4] = {1, -1, 0, 0};
int n;

void dijkstra(int sx, int sy){
    priority_queue<pair<int, pair<int,int>>> pq;
    pq.push({-a[sx][sy], {sx, sy}});
    dist[sx][sy] = a[sx][sy];
    
    while (!pq.empty())
    {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int w = -pq.top().first;
        pq.pop();

        if(w > dist[x][y]) continue;

        for (int i = 0; i < 4; i++){
            int dx = x + fdx[i];
            int dy = y + fdy[i];
            int dw = w + a[dx][dy];
            
            if (dx > 0 && dy > 0 && dx <= n && dy <= n)
            { 
                if (dist[dx][dy] > dw)
                {
                    dist[dx][dy] = dw;
                    pq.push({-dw, {dx, dy}});
                }
            }
        }
    }
}

int main(){
    int t = 0;
    while (1)
    {
        t++;
        cin >> n;
        if(n==0)
            break;
        for (int i = 1; i <= n; i++)
        {
            for (int d,j = 1; j <= n; j++){
                cin >> d;
                a[i][j] = d;
            }
        }

        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= n; j++){
                dist[i][j] = INF;
            }
        }

        dijkstra(1, 1);

        printf("Problem %d: %d\n", t, dist[n][n]);
    }
}

recursion으로 접근한다.

BaseCase

1) n=1인 경우에는 각 케이스에 맞게 count를 1증가시키고 종료해준다.

RecursionCase

1) 모든 칸이 동일한 숫자로 채워져 있다면 해당 숫자에 맞게 count를 1증가시키고 종료해준다.

2) 그렇지 않다면 9개의 구역에 해당하는 recursion을 실행한다.

#include <iostream>
#include <math.h>

using namespace std;

int a[2200][2200] = {0,};
int count[3] = {0,};

void solve(int x, int y, int n){
    if(n==1){
        if(a[x][y] == -1)
            ::count[0]++;
        if(a[x][y] == 0)
            ::count[1]++;
        if(a[x][y] == 1)
            ::count[2]++;
        return;
    }

    int target = a[x][y];
    for (int i = x; i < x + n; i++)
    {
        for (int j = y; j < y + n; j++){
            if(target != a[i][j]){
                int d = n / 3;
                for (int c = 0; c < d * 3; c+=d){
                    for (int l = 0; l < d * 3; l += d)
                    {
                        int dx = x + c;
                        int dy = y + l;
                        solve(dx, dy, d);
                    }
                }
                return;
            }
        }
    }

    if(a[x][y] == -1)
        ::count[0]++;
    if(a[x][y] == 0)
        ::count[1]++;
    if(a[x][y] == 1)
        ::count[2]++;

    return;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    
    solve(0,0,n);

    for (int i = 0; i < 3; i++){
        cout << ::count[i] << "\n";
    }
}

0의 개수에 영향을 미치는 것은

1~n까지의 숫자 중에서,

각 숫자가 갖는 5와 2의 개수이다.

왜냐면 소수 5와 2가 곱해질때 만이 10이 만들어지기 때문이다.

따라서 각 숫자의 소인수 중 2와 5의 개수를 카운팅한다음

10이 얼마나 만들어 지는지를 찾는다. -> min(2의 개수, 5의 개수)

#include <iostream>
#include <math.h>

using namespace std;

int main(){
    int n;
    cin >> n;

    int a=0, b=0, count=0;
    for (int i = 1; i <= n; i++)
    {
        int num = i;
        while(num%5 == 0){
            num /= 5;
            a++;
        }
        while(num%2 == 0){
            num /= 2;
            b++;
        }
    }
    count = min(a, b);
    cout << count << "\n";
}

https://www.acmicpc.net/problem/11724

기본적인 BFS / DFS 문제이다.

BFS를 이용해 접근했다.

모든 노드에 대해 BFS를 시도하면서 이미 방문한 노드인 경우 건너뛰는 방식이다.

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int n, m;
int count = 0;
vector<int> a[1001];
int v[1001] = {
    0,
};

void bfs(int start){
    if(v[start] == 1)
        return;

    queue<int> q;
    q.push(start);
    v[start] = 1;
    ::count++;

    while(!q.empty()){
        int x = q.front();
        q.pop();
        for (int i = 0; i < a[x].size(); i++){
            int y = a[x][i];
            if(v[y] == 0){
                v[y] = 1;
                q.push(y);
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for (int x,y,i = 0; i < m; i++){
        cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }
    for (int i = 1; i <= n; i++){
        bfs(i);
    }
    cout << ::count << "\n";
}

배열이나 set을 이용하여 문제를 해결할 수 있다.

주의해야할 사항은 시간초과와 메모리초과이다.

1. 시간초과

밑의 두가지 코드를 통해 해결한다.

ios_base::sync_with_stdio(false); // c의 stdio와 cpp의 iostream의 동기화를 해제해준다.

cin.tie(NULL); // 버퍼를 비워줌 cin와 cout을 독립적으로 만들어준다.

2. 메모리초과

결과값을 담아 마지막에 한번에 출력해주는 vector를 사용하면 메모리 초과가 난다. input stream / output stream은 별개이니 굳이 마지막에 모아서 결과를 출력하지 않아도 된다.

배열을 이용한 풀이

#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

vector<int> v(21); // index값 1-존재, 0-없음.

void init(){ // 1~20 초기화.
    for (int i = 1; i <= 20; i++){
        v[i] = 1;
    }
}

void arrEmpty(){
    for (int i = 1; i <= 20; i++){
        v[i] = 0;
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n,x;
    string type;
    cin >> n;

    for (int i = 0; i < n; i++)
    {
        cin >> type;
        if (type.compare("all") == 0) init();
        else if (type.compare("empty") == 0) arrEmpty();
        else{
            cin >> x;
            if (type.compare("add") == 0)
            {
                v[x] = 1;
            }
            if (type.compare("remove") == 0)
            {
                v[x] = 0;
            }
            if (type.compare("check") == 0)
            {
                v[x] == 1 ? cout << "1\n" : cout << "0\n";
            }
            if (type.compare("toggle") == 0)
            {
                v[x] == 1 ? v[x] = 0 : v[x] = 1;
            }
        }
    }
}

set을 이용한 풀이

#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

set<int> s;
set<int> init;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for (int i = 1; i <= 20; i++)
        init.insert(i);

    int n; cin >> n;
    string type;
    int x;

    for (int i = 0; i < n; i++)
    {
        cin >> type;
        if (type.compare("all") == 0)
        {
            s = init;
        }else if (type.compare("empty") == 0)
        {
            s = {};
        }else{
            cin >> x;
            if (type.compare("add") == 0)
            {
                s.insert(x);
            }
            if (type.compare("remove") == 0)
            {
                s.erase(x);
            }
            if (type.compare("check") == 0)
            {
                s.find(x)!=s.end() ? cout << "1\n" : cout << "0\n";
            }
            if (type.compare("toggle") == 0)
            {
                if(s.find(x)!=s.end()){ // 있는 경우 삭제
                    s.erase(s.find(x));
                }
                else
                { // 없는 경우 추가
                    s.insert(x);
                }
            }
        }
    }
}

liked layer에서 유선통신을 할 때는 csma / cd 프로토콜을 사용한다.

❗ wireless

유선 csma / cd를 그대로 사용할 경우 몇가지 문제점이 발생한다.

문제점 1.

유선통신에서는 csma / cd 사용하면 되지만 무선의 경우 거리에 따라서 주파수에 따라 전파가 도달가능한 범위가 다르기 때문에 노드들이 서로의 신호를 인지하지 못할 수 있다.

문제점 2.

collision detection이 불가능하다. 노드는 자신이 통신 중일때 전파 특성상 다른 노드의 신호를 인지할 수 없다.

이를 해결하기 위해 wifi는 CSMA / CA 라는 mac 프로토콜을 사용한다.

❗ wifi

• 기술적 명칭은 IEEE 802.11이다.
• wireless fidelity의 약자이다.
• ap가 초당 10~100회 정도로 주기적으로 boradcast를 하여 자신을 알린다.
• 유선 csma / cd에서는 노드들이 스스로 충돌감지를 할 수 있기 때문에 ack가 필요없지만 wifi에서는 충동감지가 불가능 하기때문에 ap의 ack가 따로 필요하다.
• csma / ca를 사용한다. (collision avoidance의 약자)

❗ CSMA/ CA 동작원리

csma / cd에서는 충돌 감지 후 곧 바로 통신을 중지하지만 와이파이는 충돌감지 자체가 불가능하기 때문에 충돌발생시 발생하는 손해가 유선에 비해 더욱 크다. 와이파이는 충돌감지를 위해 RTS(ready to send)와 CTS(clear to send)라는 control frame을 추가시켜서 통신을 진행하게 된다.

노드는 cast를 sence하고 있다가 일정시간 동안 조용할 경우 RTS라는 작은 크기의 프레임을 보낸다. RTS를 보내는 이유는 충돌 시 발생하는 손해가 크기 때문에 그 손해를 최소화하기 위함이다.

1. a와 b가 RTS경쟁을 하다가 RTS가 충돌날 경우 AP는 아무것도 듣지못하지만 피해는 크지않다.
2. a와 b는 exponential backoff을 가진 후 다시 rts를 보내게 된다.
3. RTS를 충돌 없이 정상적으로 받은 경우 ap는 a의 통신에 대한 cts를 뿌린다.
4. 그 후 A는 ap와 자유롭게 데이터 통신이 가능하게 된다.

rts와 cts에는 누가 얼마 동안에 어떤 채널을 사용한다는 정보가 담겨 있고 이를 받은 모든 반경의 노드들은 그 정보를 통해 특정 시간만큼 기다린다.

❗ CSMA/ CA 한계

하지만 CSMA/ CA 에도 결점이 존재한다.

다음과 같은 시나리오를 생각해보자.

1. ap가 A의 rts를 정상적으로 받은 후 cts를 보냈다.
2. cts를 보내는 중에 B가 ap에게 rts를 보내는 경우 B는 CTS를 정상적으로 받은 A가 통신중이라는 것을 알지 못한다.
3. 이때 a, ap는 정상통신이 가능하다고 예측을 하고 통신을 진행하지만 B는 그 사실을 알지 못한상태가 되어 a가 채널을 사용중에 있을 때 RTS를 보내 충돌이 발생되어 전송이 와해되게 된다.
4. ap에게 데이터에 대한 ack를 받지못한 a는 재전송을 위해 다시 Rts경쟁을 하게 된다.

서로 통신 반경이 다른 노드들간의 관계에 의해서, rts 혹은 cts가 미세한 시간차이로 인해 노이즈가 되어버리는 경우가 불가피 하다. 따라서 사람이 많을수록 충돌-지연-충돌-지연이 다수 발생하게 된다.

csma / ca는 재전송을 7번까지만 허용한다. 7번 이후에는 다음 프레임으로 넘어간다. 그렇다면 보내지 못한 데이터는 어떻게 되는가? tcp의 timer가 터지면 재전송을 위해 다시 내려오게 된다.

mac 프로토콜은 liked layer에서의 충돌 방지를 위한 프로토콜을 말한다.

❗ csma(carrier sence multiple access)

csma는 random access 방식을 사용한다. 다시말해 호스트는 자신이 원할때 마다 통신을 할 수 있다는 것을 의미한다.

기본적인 컨셉은 listen before send으로 carrier(데이터를 보낼 host)가 보내지 전에 우선석으로 sence(듣고)한 후 데이터를 보내는 방식이다.

하지만 propagation delay(빛의 속도, c)가 0이 아니기 때문에 boradcast 매체인 liked layer에서는 충돌이 발생할 수 밖에 없다. 즉 충돌은 나기마련이라는 것이 결론이다. 따라서 충돌을 방지할 수 있는 mac 프로토콜이 필요하다.

❗ csma / cd(carrier sence multiple access / collision detection)

그래서 등장한 것이 csma의 보완버전으로 충돌을 관리하는 mac 프로토콜이다.

작동원리

NIC가 충돌을 감지하면 그 순간 통신을 멈춘다. 그 후 일정시간을 기다린다. 이 과정을 binary exponential backoff이라고 한다. 0,1,2,…,2^m-1(m is count of collision) 중 랜덤으로 값을 선택하여 그 만큼의 딜레이를 갖는다. exponential한 값중에 랜덤하게 선택하기 때문에 충돌횟수가 늘어나면 더 오래기다릴 확률이 높아진다.

tcp의 congest control과 비슷한 원리인듯 하다. cast의 상황을 독립적으로 판단하고 적절히 양보하게 된다.

❗ 네트워크가 너무 느린데?!

가끔 많은 사람들이 같이 와이파이를 사용하는 경우에 우리가 체감적으로 네트워크가 느리다고 느끼는 것이 실제 네트워크가 느린것이 아니라 사람이 몰려서 backoff 시간이 늘어난다는 요인이 작용하기 때문이다.

❗ethernet minimum frame size

propagation delay가 빛의 속도이지만, csma / cd 만으로는 충돌이 발생했음에도 불구하고 충돌을 인식하지 못하는 아주 최악의 상황이 발생할 수 있다.

충동이 일어났음에도 인지하지 못하는 경우는 어떤 상황일까?

A와 B가 boradcast 매체의 host라고 가정하자.

1. A가 B에게 데이터를 보냈다.

2. A가 B에게 보낸 데이터가 B에게 도달하기 전에 B 또한 A에게 데이터를 보낸다.

3. 이때 B->A로 오는 와중에 A입장에서, A->B 데이터 전송이 끝난다면,

4. B->A데이터는 이미 노이즈 섞인 불완전한 데이터이지만

5. A는 자신이 통신을 모두 마친 후 아주 평안한 상태에서 받은 데이터이기 때문에 충돌이라는 것을 인지하지 못한다.

이처럼 충돌이 발생했음에도 불구해고 탐지하지 못하는 상황이 발생하는 것을 막기위해 최소전송단위시간이 존재한다. 찰나의 순간에 데이터를 같이 보내는 경우 그것을 인지하기 위해 일정크기 이상으로 데이터를 보내자는 약속이 있는 것이다. 이것이 바로 ethernet minimum frame size (64byte)이다. 만약 보내는 데이터가 64byte보다 작다면 padding 집어넣어서 64byte를 맞추어 보낸다.