[세미나] KIDS

 

개요^#

 

1. Managing Dynamically extendable function^#

• 리눅스 네트워크 아키텍쳐는 매순간 변화 & 발전 중이다.
• 대부분 경우 이런 확장은 동적(Runtime)으로도 발생한다.
• ex)  네트워크  레이어, 전송 레이어, 패킷 필터
• 이런 확장을 관리 하기 위해서 우리에게 필요한것은 적용된 기능들을 감시할 적절한 인터페이스와 구조체이다.
• 아래의 함수들은 새 기능들을 커널에 등록할때 동작중인 기능들을 제거 할때 사용된다.

• register_functionality() : 새 기능을 추가
• unregister functionlity() : 기존 기능 빼기

위 함수 실행시 초기화 과정및 clean up단계 필요

ex) 해당 기능을 다른 곳에서 사용중인지 확인(Reference count == 0)후 unregistering

 

등록 작업 순서

 

• 새 기능 추가시 많은 설정 정보가 필요하다..이들을 모두를 파라미터로 넘기기에는 무리가 있으므로 [관리 구조체]를 생성후 사용한다.
  • 이러한 관리 구조체를 이용한 정보 넘기기 방식을 사용하면 등록후에 해당 기능과 파라미터에 접근할수 있다.
  • 관리 구조체 : 레지스터링시 필요한 파라미터 저장 (ex: net_device, packet_type)
    
    • 저장후 포인터를 registeration 함수에게 전달
    • 관리 구조체의 요소들은 작업에 따라 크게 2개로 구분
      
      • 설정 데이터 : 기능 추가 전에 정해 지고 난후 관리 구조체로 전달
      • Runtime variables : 기능 추가 전에는 정해지지 않음 , 기능 사용중에 요청함

 

2. Structure of the KIDS construction system^#

이장에서는 KIDS프레임 워크가 어떻게 리눅스에 구현되는지 살펴 보겠다.

 

• KIDS 는 Karlsruhe Implementation architecture of Differentiated Services의 약어이다.

• 구성 요소들은 Object-Oriented Concept의 특성을 가진다
• QoS 메커니즘을 네트워크 상에서 디자인, 평가, 사용을 목적으로 계발
• KIDS는 QoS 메커니즘의 구조및 상호 연동성을 설명한 축약 모델이다.
• 또한 여러 QoS 정책(Behavior)을 독립적으로 정의 할수도 있게 한다.
• 여러 플랫폼에 적용 가능 (Unix, OMNET++ 시뮬레이션 툴)

위의 특징들로 인하여 이미 개발된 많은 QoS 기술들과의 차이점을 지닌다.

 

2.1 Elementary QoS Components

• KIDS는 개별적인 QoS메커니즘에 구현 가능한 프레임 워크 생성시 유연성, 확장성, 모듈화 가능하도록 디자인 되었다.
  
  • 이는 QoS 메커니즘에 적용되는 컨포먼트들의 사용에 달려 있다.
• 컨포넌트들의 손쉬운 조합과 ensuring all potential degrees of freedom 이 KIDS의 KIDS 디자인의 가장 중요한 요소이다.
• KIDS는 일종의 레고 장남감과 비슷하다.
  
  • 이때 장난감 블록은 서로 다른 인터페이스를 가진 컨포넌트라고 볼수 있다.
  • 같은 인터페이스를 가진 컨포넌트들은 서로 연결되어 QoS메터니즘을 생성 할수 있다.

 

 

위 중 종류의 인터페이스 타입을 이용하여서 5개의 컨포넌트 클래스를 나눌수 있다. (QoS 메커니즘은 이런 클래스의 조합으로 이루어 진다)

• Operative components(BHVR) : 패킷 상에서 동작 한다. 패킷 수신후 정해진 알고리즘을 패킷에 적용시킨다.
  
  • Examples: Token Bucket, Shaper, Marker, Dropper, Classifier, Random Early Detection (RED)

 

• Queue Components(QUEUE) : 컴포넌트가 패킷을 큐에 넣거나 뺄때 사용되는 데이터 구조체
  
  • Examples: FIFO Queue, Earliest-Deadline-First-Queue

 

• Enqueuing Components (ENQ_BHVR) : 주어진 방법에 따라 패킷을 큐에 넣는다.
  
  • Examples: Head-Enqueue, Tail-Enqueue, EDF-Enqueue.

 

• Dequeuing components (DEQ_BHVR) : 주어진 방법에 따라 패킷을 큐에서 빼낸다. 이때 dequeue 요청은 메시지 input을 통해 수신후, 요청이 적절하다면 패킷은 패킷 output을 통해 이동하나.
  • Examples: Head-Dequeue, Tail-Dequeue

 

• Strategic components (DEQ_DISC) : 큐와 유연하게 연동될수 있는 정책(Strategic)을 구현하다.
  • Examples: Priority Queuing, Weighted Fair Queuing, Round Robin.

 

<Figure 22-2. Five different KIDS component classes.>

 

2.2 Hooks

 

 

 

3. Using the KIDS example to extend the linux network architecture

• 이전장에서는 KIDS 프레임워크의 구성에 대하여 설명 하였다.
• 이번장에서는 KIDS를 리눅스 커널에 구현함으로써 어떻게 기능 확장이 가능한지를 예시 삼아 설명 하도록 하겠다. (특히, 컴포넌트의 디자인및  관리
  
  • 컨포넌트를 어떻게 디자인 하는가?
  • 컨포넌트를 왜 디자인 하는가?
  • 컨포넌트를 Runtime시점에 어떻게 커널에게 연결(Introduce) 시키는가?
  • Hook를 서로다른 커널 인터페이스에게 구현하는가?
    
    • 이 말은 커널을 바꾸지 않고도 KIDS를 추가 할수 있다는 것이다.
  •  

 

3.1 Conponents and Their instances^#

• KIDS의 Conponent concept상 두 분류로 구성되어 있다.
  
  • Components
    
    • 특별 목적(Behavoir)를 하는 QoS메커니즘
    • Linux KIDS의 bhvr_type 구조체의 관리를 받음 (이 구조체 안에는 컴포넌트의 모든 속성이 들어 있음)
  • Component instances
    
    • 컴포넌트의 인스턴스가 필요시 생성
    • 이때문에 bhvr 타입의 구조체를 생성하여야 한다. (이 구조체 안에는component instance의 모든 속성이 들어 있음)
    • Instance는 component의 행동 양식(Behavior)를 저장, 따라서 컴포넌트의 bhvr_type구조체를 참조 하고있다.

 

1. struct bhvr_type
   {
      char              name[STRLEN];   //컴포넌트 이름 (ex: Token_Bucket)
      unsigned int      bhvr_class_id;  //컴포넌트의 클래스(ex: BHVR_ID, ENQ_BHVR_ID, DEQ_BHVR_ID, DEQ_DISC_ID, and QUEUE_ID)
      unsigned long     private_data_size; //각 컴포넌트 인스턴스의 bhvr 구조체에서 사용되는 private data 구조체의 크기 지정
      unsigned int      instances; //컴포넌트에서 생성된 인스턴스 관리 (ex : 0일 경우 컴포넌트가 커널에서 삭제 되었음을 의미)
      struct bhvr_type  *next; // bhvr_type_list의 해당하는 bhvr_type 구조체로의 링크
      int               (*func) (struct bhvr *, struct sk_buff *); //컴포넌트의 인스턴스에게 패킷 전달시 실행 되는 함수
      struct sk_buff*   (*deq_func) (struct bhvr *); // dequeuing & strategic 컴포넌트
2.                                                   // 구현된 메시지 인터페이스와 연관성 지님, 컴포넌트의 인스턴스가 패킷을 요청시 호출된다.
   
3.                                                   // 컴포넌트는 두개의 함수중 하나를 구현한다.(fucn = 패킷 인터페이스 인풋 소유, deq_func= 메시지 인터페이스소유)
4.    int               (*constructor) (struct bhvr *bhvr, char * data, int flag); //bhvr인스턴스가 초기화 되거나 설정이 변경시 호출
      int               (*destructor) (struct bhvr *bhvr); //bhvr 인스턴스 삭제시 호출
      struct bhvr*      (*get_bhvr) (struct bhvr *bhvr, char * port); //컴포넌트 인스턴스의 bhvr 구조체의 주소를 알아 오기위해 KIDS가 호출
      int               (*append_bhvr) (struct bhvr *new_bhvr, struct bhvr  *old_bhvr, char *port);
5.                                                                 // 아웃풋으로써 현재 컨포넌트 인스턴스(=old_bhvr)을 새 컨포넌트 인스턴스로 연결(=new_bhvr)
      int               (*proc) (struct bhvr *bhvr, char *ptr, int layer); //bhvr 컨포넌트 인스턴스의 정보 생성
   
6.                                                                         //대부분  proc 파일의 output이다
7.    int               (*get_config) (struct bhvr *bhvr, char *ptr);  // KIDS 설정신텍스에 맞추어서 bhvr 컨포넌트 인스턴스의 설정 정보를 ptr버퍼공간에 쓸때 호출
   };

 

 

1. struct bhvr

2. {

3.        char                   name[STRLEN];  //현 인스턴스의 이름 (ex : tb0, marker1)

4.        unsigned int           use_counter;  // 현 bhvr 구조체의 레퍼런스 횟수

5.        struct bhvr            *next_bhvr;   // bhvr_list에 있는 bhvr 데이터 구조체의 링크, 컴포넌트 탐색시 사용됨

6.        struct bhvr_type       *bhvr_type;   // bhvr_ype 구조체에 정의 되어 있는 컴포넌트 인스턴스의 특정 작업(behavior)의 주소

7.        char                   bhvr_data[0]; // private 정보를 위해 공간 확보용 (Place holder)

8. };

 

 

Using the token - Bucjet component as an example for a private data structure^#

• bhvr_data 구조체의 private 정보(bhvr_data)를 저장하고 있는건 중요하다.
• 특정 컨포넌트 인스턴스의 상태나 설정에 관련된 정보는 bhvr 구조체의 Private data 구조체 안에서 인스턴스 그 자체로써 관리 된다.

 

 

다음은 Token_Bucket 컨포넌트의 private data 구조체를 가르킨다.

1. struct tb_data
   {
      unsigned int     rate, bucket_size;
      unsigned long    token, packets_arvd, packets_in, packets_out;
      CPU_STAMP        last_arvl, cycles_per_byte;
      struct bhvr      *enough_token_bhvr;
      struct bhvr      *not_enough_token_bhvr;
      int              (*enough_token_func) (struct bhvr *, struct sk_buff *);
      int              (*not_enough_token_func) (struct bhvr *, struct sk_buff *);
   };

 

위의 Private data 구조체의 각 변수 들은 세개의 그룹으로 나누어 질수 있다.

1. 파라미터 & 변수 : 컨포넌트의 변수들은 컨포넌트에 구현된 알고리즘에 따라 각각 독립적이다. 이것때문에 변수들은 컨포넌트의 Private data 구조체로 관리 되어야 한다.
2. Func()함수나 deq_func()함수의 포인터 정보(function pointer)
3. bhvr_strucuture의 주소(reference)

Private information은 각 컨포넌트 output에 대하여 (2),(3)의 요소들을 관리 한다. 그이유는 아웃풋의 갯수 또한 각 컨포넌트마다 다르고, bhvr_type 구조체에 넣어서 관리 할수 없기 때문이다.

 

 

3.2 Registering and Managing Components^#

• bhvr_type_list : resistered componenrs 관리

 

[등록 작업] : QoS메커니즘을 적용시키기 위해 Linux KIDS를 사용하

1. 선행 작업 : 커널에게 어떤 component가 현재 사용 가능한지 알려 주어야 함
   
   • 이를 위해 Linux KIDS는 bhvr_type_list를 유지 하야 등록된 모든 컨포넌트를 관리
   •  bhvr_type_list는 vhbr_type 데이터 구조체에 각각 연결 되어 있다.
2.  등록 함수 호출 : register_bhvr_type함수를 이용하여서 bhvr_type구조체에 정의되어 있는 컴포넌트들을 등록
   
   • 이  말은 bhvr_type구조체가 bhvr_type_list에 들어 가게 되면, 그때부터 해당 컴포턴트를 커널을 인식할수 있고, 사용자는 해당 컴포넌트의 인스턴스를 생성할수 있다.

 

[해지 작업]

1. 해지 함수 호출 : unregister_bhv_type함수를 이용하여서 컴포넌트를 리스트에서 등록해지
   
   • 물론 등록 해지 전에는 해당 컴포넌트와 관련된 인스턴스 들이 남아 있으면 안된다.

 

 

3.3 Managing Component Instances^#

본장에서는 컨포넌트의 인스턴스 들을 어떻게 생성, 삭제, 링킹등의 관리를 하는지 살펴 보겠다.

 

 create_bhvr(type,name, data, id)

• 컴포넌트(name)의 인스턴스 생성시 사용
  
  • 해당 컴포넌트는 bhvr_type_list(등록된 컴포넌트 리스트)에 이미 존재 하여야 함

1. 새 컴포턴드 인스턴스를 위한 메모리 공간이 예약됨 (메모리 공간 = bhvr 구조체_모든 컴포넌트와 동일+private data 구조체_각 컴포넌트마다 다름 )
2. bhvr 구조체 초기화
3. 컴포넌트의 constructor 호출 (private date공간을 컴포넌트의 설정 파라미터로 채우기), 설정 파라미터들은 CREATE명령어를 통해 추출된후 데이터 캐릭터 스트링으로 전달된다. 한번 생성된 후에는 컴포턴트들은 다른 컨포넌트들과 연결되지 않는다.
4. bhvr_list에 등록된다.

 

remove_bhvr(name, force)

• name에 정의된 컴포넌트 인스터스를 삭제 하고 bhvr_list에서 제거 한다.
• force는 인스턴스의 user_counter가 무시 되어야 한다는 점을 알릴때 사용된다.
• 데이터 구조체가 release될때 컴포넌트의 destructor이 호출되어 자원을 release한다.

 

change_bhvr(name, data)

• runtime시의 컴포넌트 인스턴스의 private data를 바꾸는데 사용된다.
• INIT_BHVR플래그가 설정지 않는다
• Constructor는 파라미터에서 지정한 것들만 바꾼다, 그렇지 않을경우에는 모든 인스턴스 들이 초기화 된다.

 

3.4 Implementating Hooks^#

• Hooks는 기존의 프로토콜 인스턴스의 확장기능으로써 사용자가 쉽게 KIDS 프레임 워크의 규칙에 기반한 QoS컨포넌트들을 embed할수 있도록 한다.
• 중요한 요소중 하나는 hook를 통해 확장하고자 하는 위치 설정이다.(프로토콜 인스턴스의 프로세스 안에서)
  
  • 그 이유는 사용자는 항상 특정 양의 패킷들과 특정 위치를 지정하기 떄문이다.
    
    • ex) IP_FORWARD hook지점에서의 모든 패킷 포워딩 , IP_LOCAL_DELIVER hook지점에서의 IP인스턴스의 모든 패킷은 내부(locally)로 전달
• 다른 인터페이스마다의 설정의 이점으로  리눅스네트워크 아키텍쳐는 프로토콜 인스턴스를 기능에 따라 확장할수 있도록 방법을 기본적으로 제공한다.
• 이러한 인터페이스들은 KIDS에서도 사용된다. 따라서 별도의 소스코드 수정 없이도 리눅스에 그대로 사용가능하다.
• IP인스턴스를 위한 hook는 넷필터 인터페이스에 기반을 두고 있다.
• Data-link 계층 hook는 트래픽 컨트롤 인터페이스에 기반을 두고 있다.

• 추가적인 hooks는 runtime일때라도 쉽게 통합될수있다.
  
  1. hook를 통합하기 위해서는 hook데이터 구조체에서 요구하는 관련 정보들을 저장
  2. register_hook()를 이용하여서 등록 한다.
• 확장하고자 하는 프로토콜 인스턴스 들은 함수 호출을 통하여 쉽게 확장 가능한다

 

 3.5 How a Component works^#

 

token_bucket_func()

1. int token_bucket_func(struct bhvr *tb_bhvr, struct sk_buff *skb)
   {
      struct tb_data  *data = (struct tb_data *) &(tb_bhvr->bhvr_data);
      CPU_STAMP       now;
   
      data->packets_arvd++;
      TAKE_TIME(now);
      /* calcs the tokens, that are produced since the last packet arrival */
      (unsigned long) data->token += (((unsigned long) (now - data->last_arvl)) /
                                           (unsigned long) data->cycles_per_byte);
      /* check, if the bucket is overflood */
      if (data->token > data->bucket_size)
         data->token = data->bucket_size;
      data->last_arvl = now;
      /* check, if there are enough tokens to send the packet */
      if (data->token < skb->len)
      {   /* not enough tokens -> out of profile */
          data->packets_out++;
          /* forward the packet to the next behavior (out-of-profile) */
          if ((data->not_enough_token_bhvr) && (data->not_enough_token_func))
             return data->not_enough_token_func(data->not_enough_token_bhvr, skb);
      }
      else
      {   /* enough tokens -> in profile */
          data->token -= skb->len;
          data->packets_in++;
          /* forward the packet to the next behavior (in-profile) */
          if ((data->enough_token_bhvr ) && (data->enough_token_func))
             return data->enough_token_func(data->enough_token_bhvr, skb);
      }
      return KIDS_ACCEPT; /* Do not discard packet, when no behavior is attached */
   }

 

• Token_Bucket 컨포넌트는 Operative 컨포넌트 클래스에 속한다.
  • 즉, 하나의 패킷 인풋과 n개의 패킷 아웃풋을 가지고 있어야 한다.
    • ex) 2개의 아웃풋 : confirm & non_confirm

• Token_Bucket 컨포넌트의 인스턴스가 패킷을 수신하게 되면 이와 연관된 func()핸들링 절차가 호출된다.
  
  • 얻게 되는 파라미터들로는 socket buffer, skb, 컨포넌트 인스턴스의 데이터를 가르키는 포인터 정보들이 있다.

 

[ 순서 ]

1. 처음에, 인스턴스의 private data의 포인터는 type cast를 가르키는 이 포인터 안에서만 가르키도록 되어 있다.
2. 함수가 완전히 reentrant되고 나면, 자신의 private data나 local 변수안에서만 작동하게 된다.
3. 이어서 token bucket 알고리즘에 따라 일련의 계산 작업이 수행된다.
4. 그리고 통계 변수의 정보들이 업데이트 된다.
   1. 이러한 계산의 결과 값은 아웃풋을 결론짓게 되고 이 값을 통해 socket buffer의 포워딩시 이용된다.
5. 만약 해당 아웃풋에 연관되는 인스턴스가 없을경우 함수는 KIDS_ACCEPT 결과값을 반환한다.
   
   1. 이 뜻은 패킷이 hook에게로 포워딩되어야 한다
6. counterpart부분은 KIDS_DROP이다.
   
   1. 이 부분은 hook에게 socket buffer을 드랍시키라고 한다.
7. 하지만 컴포넌트 인스턴스가 지정된 output(data-> ..._bhvr != NULL)을 따르게 된다면
   1. 인스턴스의 핸들링 절차(data->..._funv())가 호출된다.
   2. 그리고 나서 이어지는 인스턴스의 데이터에 대한 포인터가 이 핸들러의 루틴으로 전달 된다.
8. 이어지는 텀포넌트 인스터스의 반환값은 token-bucket 컨포넌트의 반환값으로 바로 사용되게 된다.