영향 반경
모든 링크와 모든 라우터를 한 번에 테스트하기, 그리고 그래프 이론이 그것을 13밀리초로 만드는 이유
Michel Wijnberg
“이걸 망가뜨리면 어떻게 될까?”는 하나의 대상에 관한 질문입니다. 아키텍트가 실제로 답을 필요로 하는 질문은 그 반대이고, 훨씬 어렵습니다.
이 네트워크에 있는 모든 것 가운데 어느 부분이 중요한가?
링크를 하나씩 클릭해서는 거기에 도달할 수 없습니다. 제 랩의 AS 200에는 링크 275개와 라우터 64대가 있습니다. 장애를 하나씩 손으로 테스트하면 실험이 339번이고, 토폴로지가 바뀔 때마다 다시 해야 합니다.
그래서 Osprey는 그것을 전부 한꺼번에 합니다. 그렇게 해서 얻는 것은 짧은 목록입니다. 고장 날 수 있는 339가지 가운데, 실제로 대가를 치르게 만들 몇 가지. 이것이 다음 분기로 잡아 두는 이중화 검토와, 변경을 승인하기 전에 돌려 보는 검토의 차이입니다.
모든 링크, 모든 라우터, 13밀리초
헤더를 읽어 보십시오. “1 with impact in 13ms”, 그 아래에는 무엇을 테스트했는지가 적혀 있습니다. “Links whose failure causes device isolation. Redundant links omitted.”
이 테넌트의 모든 링크가 평가되었습니다. 그중 정확히 하나, mia1-cr1 ↔ mia1-gw1만이 무언가를
고립시키고, 고립되는 것은 라우터 한 대, mia1-gw1입니다. 토글을 Node Failures로 바꾸면 답은
거울상입니다. 라우터 64대 중 정확히 한 대(mia1-cr1)가 정확히 다른 한 대를 떼어 놓습니다.
그것이 아키텍트가 원하는 결과입니다. 읽어야 할 275행짜리 목록이 아니라, 그중 274행은 증명 가능하게 시시하다는 진술 말입니다.
같은 약점을, 세 프로토콜을 통해 세 번 찾아내다
같은 사실의 구조적 관점은 자기 몫의 리포트에 살고 있습니다.
장비 64대, 분석된 링크 275개, 단절점 1개(mia1-cr1, 172.16.4.31)와 브리지 링크 1개. 단절점은
제거하면 연결 요소의 개수가 늘어나는 정점이고, “이 라우터가 죽으면 네트워크가 갈라진다”를 그래프 이론에서
부르는 이름입니다.
여기부터가 제가 계획하지 않았고 가장 마음에 드는 부분입니다. 같은 리포트를 나머지 두 테넌트에도 돌려 봤습니다.
| 테넌트 | IGP | 단절점 | 브리지 링크 |
|---|---|---|---|
| Harrier-Broadband | OSPFv2 | mia1-cr1 | mia1-cr1 ↔ mia1-gw1 |
| Kestrel-Dynamics | EIGRP | e-mia1-cr1 | e-mia1-cr1 ↔ e-mia1-gw1 |
| Merlin-Carrier | IS-IS | i-mia1-cr1 | i-mia1-cr1 ↔ i-mia1-gw1 |
통신사 세 곳. 서로 다른 IGP 세 종. 완전히 분리된 발견 경로 세 갈래. OSPF LSDB 워크, CISCO-EIGRP-MIB
네이버 테이블, IS-IS LSP. 그 각각에서 같은 구조적 약점이, 같은 자리에서 나왔습니다.
정직한 설명은 제가 랩을 템플릿으로 만들면서 마이애미에 싱글홈 게이트웨이를 세 번 줬다는 것입니다. 그런데
바로 그 점이 이것을 쓸모 있는 점검으로 만듭니다. 동일한 물리적 실수가 서로 무관한 세 프로토콜 모델을 통해
Osprey에 전달되었고, 같은 답 세 개를 냈습니다. 만약 IS-IS 토폴로지 추출에 버그가 있었다면, 불일치가 드러날
자리는 i-mia1-cr1이었을 것입니다.
도구가 알려 주기 전까지 저는 그것이 랩에 있는지 몰랐습니다. 몇 주 동안 거기 있었습니다. 바로 그런 것을 잡으려고 만든 랩 안에서요.
이 대목은 그래프 이론과 떼어 놓고 볼 만합니다. 이론 쪽이 평범한 절반이기 때문입니다. 단절점과 브리지는 교과서에 있고, 어떤 도구든 어떤 그림 위에서든 계산해 낼 수 있습니다. 그 답에 의미가 있는지를 결정하는 것은 정점과 간선이 무엇인가입니다. Osprey의 그래프는 누군가 관리해 온 도면이 아닙니다. 라우터 자신이 플러딩한 것으로부터 재구성된 것이고, 그래서 그 안의 브리지는 그림이 아니라 포워딩에 대한 진술입니다. 같은 알고리즘을 낡은 Visio 파일 위에서 돌리면 모양은 똑같이 나오고 진실은 하나도 남지 않습니다.
왜 답이 마우스를 놓기도 전에 나오는가
장애 시나리오 275개에 13밀리초가 걸린 것은 영리한 병렬화의 결과가 아닙니다. 그 일을 하지 않은 결과입니다.
제거하면 그래프를 끊어 놓는 링크는 브리지입니다. 어떤 사이클에도 놓여 있지 않은 간선이죠. Tarjan의 브리지 탐색 알고리즘은 깊이 우선 순회 한 번, O(V+E)로 그래프 전체의 브리지를 한꺼번에 찾아냅니다. 그리고 브리지가 아닌 링크는 무언가를 고립시키는 것이 애초에 불가능합니다. 정의상 사이클 위에 있으므로 돌아갈 길이 있기 때문입니다.
그래서 평가는 브리지를 먼저 찾고, 그것들만 시뮬레이션합니다.
// Precompute bridges in O(V+E). These are the only links that can
// cause unreachable devices when removed.
bridgeLinks := spf.FindBridges(baselineMerged)그다음 한 부류를 더 걷어냅니다. 라우터 두 대가 여러 개의 병렬 링크로 이어져 있다면, 그중 어느 것도 의미 있는 뜻에서의 브리지가 될 수 없습니다. 하나를 죽여도 나머지가 남기 때문입니다.
// Parallel links: if a device pair has multiple links, failing any one
// cannot disconnect them. Remove such links from the bridge set.링크 274개가 도달성 검사가 아니라 정리 하나로 제거됩니다. 시뮬레이션되는 것은 링크 하나입니다. 요령은 그게 전부이고, 마우스에서 손을 떼기도 전에 답이 도착하는 이유이기도 합니다. 이보다 100배 큰 네트워크에서도 여전히 순회 한 번에 검사 몇 개가 붙을 뿐입니다.
여기서 그래프 이론은 장식이 아닙니다. “돌려야 하는 리포트”와 “슬쩍 보면 되는 리포트”의 차이 그 자체입니다.
아무것도 치명적이지 않을 때 “치명적”이란 무엇인가
Critical Pairs 탭은 한 걸음 더 바깥의 질문에 답합니다. 어느 링크 두 개가, 각각은 단일 장애점이 아닌데, 함께 죽으면 치명적인가?
정말 고약한 부류의 위험입니다. 두 링크 모두 어떤 SPOF 리포트에도 나오지 않습니다. 각각만으로는 아무 일도 일어나지 않습니다. 둘 다 가져가면(같은 관로, 같은 카드, 같은 정비 시간) 네트워크가 갈라집니다.
그것들을 찾으려면 브리지가 아닌 모든 간선에 대해, 그것을 제거하고 남은 것에 브리지 탐색을 다시 돌려야 합니다. O(L·(V+E))이고, 이 리포트에서 가장 비싼 작업입니다.
세 테넌트 모두에서 답은 0이고, 패널은 그것을 말로 밝힙니다.
No critical link pairs detected — your topology has good redundancy.
계산에 실제 노력이 든 0은 긴 목록보다 값어치가 있습니다. 이 0이 말하는 것은, 이 네트워크에는 동시에 잃으면 분할이 일어나는 링크 쌍이 존재하지 않으며, 그것이 가정이 아니라 남김없이 확인되었다는 사실입니다.
영향 반경은 토폴로지만이 아닙니다
구조는 의존성의 한 종류입니다. 다른 종류는 도달성이고, 그 단위는 주소 공간입니다.
| 피어 AS | 피어 | 프리픽스 | IP 공간 | CIDR 환산 |
|---|---|---|---|---|
| 100 | 2 | 3 | 131,328 | /15 |
| 300 | 2 | 3 | 131,074 | /15 |
프리픽스 세 개는 별것 아닌 것처럼 들리지만, 131,328개 주소, /15에 해당하는 공간이 오직 AS 100을 통해서만 도달 가능하다고 표현하면 이야기가 달라집니다. 프리픽스 개수는 노출도의 대리 지표로는 형편없습니다(/15도 /32도 똑같이 “1”입니다). 그래서 리포트는 주소 공간으로 환산했다가 다시 CIDR 환산으로 되돌립니다. 그것이 아키텍트가 실제로 사고하는 단위이기 때문입니다.
그 옆에서 리포트는 각 크리티컬 링크 쌍을 그 구성원이 속한 SRLG 그룹과 교차시킵니다. 그래서 지도에서는 독립적으로 보이지만 관로를 공유하는 두 링크는 다중화가 아니라 상관된 것으로 보고됩니다.
이 대목에서, 당신이 발견하기보다 제가 먼저 말해 두고 싶은 빈틈으로 넘어갑니다.
정직하고 아직 끝나지 않은 부분
Osprey의 SRLG 지원은 한 방향만 빼고 모든 방향에서 완성되어 있습니다. 그룹을 정의하고, 링크를 붙이고, 그룹 전체를 하나의 시뮬레이션 변형으로 죽이고, 의존성 리포트에서 공유 위험 상관을 볼 수 있습니다. 할 수 없는 것은 그것을 발견하는 일입니다.
SRLG 테이블에 데이터를 공급하는 것이 아무것도 없습니다. 모든 그룹이 손으로 입력됩니다. Osprey는 IS-IS에서 본 RFC 5305 트래픽 엔지니어링 서브 TLV를 원시 바이트로 저장하지만 아직 SRLG 서브 TLV를 디코딩하지 않습니다. 그래서 이미 자기 IGP에서 공유 위험 그룹을 광고하고 있는 네트워크라도 아무 이득을 보지 못합니다.
소비자가 공급원보다 먼저 만들어졌습니다. 그것은 잘못된 순서이고, 로드맵에 올라 있으며, 그 일이 끝나기 전까지 이 기능의 정직한 설명은 “SRLG 발견”이 아니라 “당신이 알려 준 그룹에 기반한 SRLG 시뮬레이션”입니다.
평가 도중에 누군가 그것을 발견하게 하느니, 저는 이 문장을 쓰는 쪽을 택하겠습니다.
이것이 제가 가장 먼저 돌릴 리포트인 이유
내일 어떤 네트워크를 물려받는다면, 제가 가장 먼저 원할 것은 지도가 아닙니다. 세 질문에 대한 답입니다.
- 어떤 단일 장애가 실제로 무언가를 고립시키는가? (링크 하나. 라우터 하나.)
- 단일 장애 리포트에는 나오지 않지만 그렇게 되는 장애 쌍은 무엇인가? (없음: 가정이 아니라 검증됨.)
- 각 외부 의존성 뒤에는 얼마만큼의 주소 공간이 있는가? (피어 AS마다 /15.)
셋 다 이미 올바른 모델에서, 1초에 훨씬 못 미치는 시간에, 라우터를 건드리지 않고 계산할 수 있습니다. 모델을 먼저 제대로 만드는 데 네 편을 쓴 이유가 전부 여기에 있습니다. 정확한 모델은 제품이 아닙니다. 쓸모 있는 질문들이 그 위에서 돌아가는 바탕입니다.
다음 글: 이 글이 조용히 피해 간 숫자. 그 링크가 죽을 때 실제로 얼마만큼의 트래픽이 움직이는지, 그리고 왜 제 랩은 그것을 알려 줄 수 없는지. 측정할 수 없는 것을 추정하기.