Artifact d037cafc583829644c3f85b739e27f3e44629405:
- File wiki/topology.md — part of check-in [385b2a8aa4] at 2019-03-09 12:11:20 on branch trunk — Markdown edits (user: bernd size: 2871)
0000: 23 20 54 6f 70 6f 6c 6f 67 79 0a 0a 6e 65 74 32 # Topology..net2 0010: 6f 20 61 73 73 75 6d 65 73 20 61 20 68 69 65 72 o assumes a hier 0020: 61 72 63 68 69 63 61 6c 20 74 6f 70 6f 6c 6f 67 archical topolog 0030: 79 2c 20 69 2e 65 2e 20 61 20 74 72 65 65 20 74 y, i.e. a tree t 0040: 6f 70 6f 6c 6f 67 79 2e 20 c2 a0 54 68 65 72 65 opology. There 0050: 20 6d 61 79 0a 62 65 20 6d 75 6c 74 69 70 6c 65 may.be multiple 0060: 20 70 61 74 68 73 20 72 65 61 63 68 69 6e 67 20 paths reaching 0070: 74 68 65 20 73 61 6d 65 20 64 65 73 74 69 6e 61 the same destina 0080: 74 69 6f 6e 2c 20 73 6f 20 74 68 69 73 20 64 6f tion, so this do 0090: 65 73 6e 27 74 20 65 78 63 6c 75 64 65 20 74 68 esn't exclude th 00a0: 61 74 0a 70 61 72 74 73 20 6f 66 20 74 68 65 20 at.parts of the 00b0: 74 72 65 65 20 61 72 65 20 61 63 74 75 61 6c 6c tree are actuall 00c0: 79 20 6d 65 73 68 20 6e 65 74 77 6f 72 6b 73 2e y mesh networks. 00d0: 20 c2 a0 54 68 69 73 20 72 65 66 6c 65 63 74 73 This reflects 00e0: 20 72 65 61 6c 69 74 79 20 69 6e 0a 74 68 65 20 reality in.the 00f0: 63 75 72 72 65 6e 74 20 49 6e 74 65 72 6e 65 74 current Internet 0100: 2c 20 61 6e 64 20 74 68 65 20 65 78 70 65 6e 73 , and the expens 0110: 69 76 65 20 6c 61 79 65 72 20 31 20 69 6e 66 72 ive layer 1 infr 0120: 61 73 74 72 75 63 74 75 72 65 20 69 73 6e 27 74 astructure isn't 0130: 20 6c 69 6b 65 6c 79 20 74 6f 0a 62 65 20 72 65 likely to.be re 0140: 70 6c 61 63 65 64 20 73 6f 6f 6e 2e 0a 0a 4d 6f placed soon...Mo 0150: 73 74 20 63 6f 6e 6e 65 63 74 69 6f 6e 73 20 73 st connections s 0160: 65 6e 64 20 61 20 6c 61 72 67 65 72 20 6e 75 6d end a larger num 0170: 62 65 72 20 6f 66 20 70 61 63 6b 65 74 73 2c 20 ber of packets, 0180: 73 6f 20 72 6f 75 74 69 6e 67 20 65 61 63 68 20 so routing each 0190: 70 61 63 6b 65 74 20 69 73 0a 77 61 73 74 65 66 packet is.wastef 01a0: 75 6c 2c 20 64 72 69 76 65 73 20 75 70 20 63 6f ul, drives up co 01b0: 73 74 73 20 61 6e 64 20 6c 6f 77 65 72 73 20 73 sts and lowers s 01c0: 70 65 65 64 2e 20 c2 a0 54 68 65 72 65 66 6f 72 peed. Therefor 01d0: 65 20 74 68 65 20 64 65 63 69 73 69 6f 6e 20 69 e the decision i 01e0: 73 20 74 6f 0a 73 77 69 74 63 68 20 70 61 63 6b s to.switch pack 01f0: 65 74 73 2c 20 61 6e 64 20 72 6f 75 74 65 20 63 ets, and route c 0200: 6f 6e 6e 65 63 74 69 6f 6e 73 20 e2 80 94 20 61 onnections — a 0210: 74 20 74 68 65 20 73 6f 75 72 63 65 2e 20 c2 a0 t the source. 0220: 49 20 63 61 6c 6c 20 74 68 69 73 0a 63 6f 6d 62 I call this.comb 0230: 69 6e 61 74 69 6f 6e 0a 0a 23 23 20 50 61 74 68 ination..## Path 0240: 20 53 77 69 74 63 68 69 6e 67 0a 0a 54 68 65 20 Switching..The 0250: 70 61 74 68 20 69 73 20 61 20 31 32 38 20 62 69 path is a 128 bi 0260: 74 20 66 69 65 6c 64 20 69 6e 20 74 68 65 20 70 t field in the p 0270: 61 63 6b 65 74 2c 20 74 68 65 20 73 77 69 74 63 acket, the switc 0280: 68 69 6e 67 20 61 6c 67 6f 72 69 74 68 6d 20 69 hing algorithm i 0290: 73 20 61 73 0a 66 6f 6c 6c 6f 77 73 3a 0a 0a 2a s as.follows:..* 02a0: 20 54 61 6b 65 20 74 68 65 20 66 69 72 73 74 20 Take the first 02b0: 5f 6e 5f 20 62 69 74 73 20 6f 66 20 74 68 65 20 _n_ bits of the 02c0: 70 61 74 68 20 66 69 65 6c 64 20 61 6e 64 20 75 path field and u 02d0: 73 65 20 74 68 6f 73 65 20 74 6f 20 73 65 6c 65 se those to sele 02e0: 63 74 0a 20 20 74 68 65 20 64 65 73 74 69 6e 61 ct. the destina 02f0: 74 69 6f 6e 0a 2a 20 53 68 69 66 74 20 74 68 65 tion.* Shift the 0300: 20 70 61 74 68 20 66 69 65 6c 64 20 62 79 20 5f path field by _ 0310: 6e 5f 20 62 69 74 73 20 74 6f 20 74 68 65 20 6c n_ bits to the l 0320: 65 66 74 0a 2a 20 49 6e 73 65 72 74 20 74 68 65 eft.* Insert the 0330: 20 62 69 74 2d 72 65 76 65 72 73 65 64 20 5f 6e bit-reversed _n 0340: 5f 20 62 69 74 20 73 6f 75 72 63 65 20 69 6e 74 _ bit source int 0350: 6f 20 74 68 65 20 72 65 61 72 20 65 6e 64 20 6f o the rear end o 0360: 66 20 74 68 65 0a 20 20 70 61 74 68 20 66 69 65 f the. path fie 0370: 6c 64 20 74 6f 20 6d 61 72 6b 20 74 68 65 20 77 ld to mark the w 0380: 61 79 20 62 61 63 6b 0a 0a 54 68 65 20 72 65 63 ay back..The rec 0390: 65 69 76 65 72 20 62 69 74 2d 72 65 76 65 72 73 eiver bit-revers 03a0: 65 73 20 74 68 65 20 65 6e 74 69 72 65 20 70 61 es the entire pa 03b0: 74 68 2c 20 61 6e 64 20 74 68 65 72 65 62 79 20 th, and thereby 03c0: 67 65 74 73 20 61 20 77 61 79 20 62 61 63 6b 20 gets a way back 03d0: 74 6f 0a 74 68 65 20 73 65 6e 64 65 72 2e 20 c2 to.the sender. 03e0: a0 54 68 69 73 20 6d 61 6b 65 73 20 73 70 6f 6f This makes spoo 03f0: 66 69 6e 67 20 69 6d 70 6f 73 73 69 62 6c 65 2c fing impossible, 0400: 20 61 6e 64 20 65 61 73 65 73 0a 5b 68 61 6e 64 and eases.[hand 0410: 6f 76 65 72 5d 28 68 61 6e 64 6f 76 65 72 2e 77 over](handover.w 0420: 69 6b 69 29 2c 20 61 73 20 6f 6e 6c 79 20 74 68 iki), as only th 0430: 65 20 64 65 76 69 63 65 20 74 68 61 74 0a 73 77 e device that.sw 0440: 69 74 63 68 65 73 20 6e 65 74 77 6f 72 6b 73 20 itches networks 0450: 6e 65 65 64 73 20 74 6f 20 63 61 6c 63 75 6c 61 needs to calcula 0460: 74 65 20 61 20 6e 65 77 20 70 61 74 68 3b 20 74 te a new path; t 0470: 68 65 20 72 65 63 65 69 76 65 72 20 77 69 6c 6c he receiver will 0480: 20 61 63 63 65 70 74 20 61 6e 79 0a 70 72 6f 70 accept any.prop 0490: 65 72 6c 79 20 61 75 74 68 65 6e 74 69 63 61 74 erly authenticat 04a0: 65 64 20 70 61 63 6b 65 74 20 61 6e 64 20 75 73 ed packet and us 04b0: 65 20 74 68 65 20 6e 65 77 20 70 61 74 68 20 74 e the new path t 04c0: 6f 20 73 65 6e 64 20 64 61 74 61 20 62 61 63 6b o send data back 04d0: 2e 0a 0a 23 23 20 50 61 63 6b 65 74 20 46 6f 72 ...## Packet For 04e0: 6d 61 74 0a 0a 50 61 63 6b 65 74 73 20 68 61 76 mat..Packets hav 04f0: 65 20 61 20 70 6f 77 65 72 2d 6f 66 2d 74 77 6f e a power-of-two 0500: 20 73 69 7a 65 20 66 72 6f 6d 20 36 34 20 62 79 size from 64 by 0510: 74 65 73 20 74 6f 20 32 4d 42 20 64 61 74 61 2e tes to 2MB data. 0520: 20 41 73 73 75 6d 69 6e 67 20 6e 65 74 77 6f 72 Assuming networ 0530: 6b 0a 73 70 65 65 64 20 74 6f 20 67 72 6f 77 20 k.speed to grow 0540: 62 79 20 61 20 66 61 63 74 6f 72 20 31 30 30 30 by a factor 1000 0550: 20 69 6e 20 32 30 20 79 65 61 72 73 2c 20 67 6f in 20 years, go 0560: 69 6e 67 20 66 72 6f 6d 20 61 20 6d 69 6c 6c 69 ing from a milli 0570: 6f 6e 20 31 6b 20 70 61 63 6b 65 74 73 20 6f 6e on 1k packets on 0580: 0a 61 20 31 30 47 62 20 45 74 68 65 72 6e 65 74 .a 10Gb Ethernet 0590: 20 6e 6f 77 20 74 6f 20 61 20 62 69 6c 6c 69 6f now to a billio 05a0: 6e 20 31 4d 20 70 61 63 6b 65 74 73 20 69 6e 20 n 1M packets in 05b0: 34 30 20 79 65 61 72 73 20 6d 65 61 6e 73 20 74 40 years means t 05c0: 68 69 73 20 68 61 73 20 65 6e 6f 75 67 68 0a 68 his has enough.h 05d0: 65 61 64 72 6f 6f 6d 20 66 6f 72 20 74 68 65 20 eadroom for the 05e0: 6e 65 78 74 20 34 30 20 79 65 61 72 73 2e 0a 0a next 40 years... 05f0: 54 68 65 20 70 61 63 6b 65 74 20 63 6f 6e 74 61 The packet conta 0600: 69 6e 73 20 74 68 65 73 65 20 65 6c 65 6d 65 6e ins these elemen 0610: 74 73 3a 0a 0a 31 2e 20 32 20 62 79 74 65 73 20 ts:..1. 2 bytes 0620: 66 6c 61 67 73 3a 20 32 20 62 69 74 73 20 51 6f flags: 2 bits Qo 0630: 53 20 28 30 30 20 68 69 67 68 65 73 74 20 74 6f S (00 highest to 0640: 20 31 31 20 6c 6f 77 65 73 74 29 2c 20 32 20 62 11 lowest), 2 b 0650: 69 74 73 0a 20 20 20 70 72 6f 74 6f 63 6f 6c 20 its. protocol 0660: 76 65 72 73 69 6f 6e 20 28 64 65 66 61 75 6c 74 version (default 0670: 20 69 73 20 6e 6f 77 20 30 31 29 2c 20 34 20 62 is now 01), 4 b 0680: 69 74 73 20 70 61 63 6b 65 74 20 73 69 7a 65 0a its packet size. 0690: 20 20 20 28 36 34 5c 2a 32 5e 5f 6e 5f 29 2c 20 (64\*2^_n_), 06a0: 32 20 62 69 74 20 73 77 69 74 63 68 20 66 6c 61 2 bit switch fla 06b0: 67 73 20 28 62 72 6f 61 64 63 61 73 74 2c 20 6d gs (broadcast, m 06c0: 75 6c 74 69 63 61 73 74 29 2c 20 33 20 62 69 74 ulticast), 3 bit 06d0: 73 0a 20 20 20 72 65 73 65 72 76 65 64 2c 20 33 s. reserved, 3 06e0: 20 62 69 74 73 20 66 6f 72 20 66 6c 6f 77 20 63 bits for flow c 06f0: 6f 6e 74 72 6f 6c 20 28 72 65 73 65 6e 64 2d 74 ontrol (resend-t 0700: 6f 67 67 6c 65 2c 20 62 75 72 73 74 2d 74 6f 67 oggle, burst-tog 0710: 67 6c 65 2c 0a 20 20 20 61 63 6b 2d 74 6f 67 67 gle,. ack-togg 0720: 6c 65 29 2e 0a 32 2e 20 31 36 20 62 79 74 65 73 le)..2. 16 bytes 0730: 20 70 61 74 68 20 28 72 6f 75 67 68 20 49 6e 74 path (rough Int 0740: 65 72 6e 65 74 20 31 2e 30 20 65 71 75 69 76 61 ernet 1.0 equiva 0750: 6c 65 6e 74 3a 20 e2 80 9c 61 64 64 72 65 73 73 lent: “address 0760: e2 80 9d 29 0a 33 2e 20 38 20 62 79 74 65 73 20 ”).3. 8 bytes 0770: 61 64 64 72 65 73 73 3a 20 74 68 69 73 20 69 73 address: this is 0780: 20 74 68 65 20 61 64 64 72 65 73 73 20 69 6e 20 the address in 0790: 74 68 65 20 64 65 73 74 69 6e 61 74 69 6f 6e 20 the destination 07a0: 62 75 66 66 65 72 20 77 68 65 72 65 20 74 68 65 buffer where the 07b0: 0a 20 20 20 70 61 63 6b 65 74 20 77 69 6c 6c 20 . packet will 07c0: 62 65 20 73 74 6f 72 65 64 20 28 72 6f 75 67 68 be stored (rough 07d0: 6c 79 20 65 71 75 69 76 61 6c 65 6e 74 20 74 6f ly equivalent to 07e0: 20 70 6f 72 74 2b 73 65 71 75 65 6e 63 65 20 6e port+sequence n 07f0: 75 6d 62 65 72 29 0a 34 2e 20 36 34 5c 2a 32 5e umber).4. 64\*2^ 0800: 5f 73 69 7a 65 5f 20 62 79 74 65 73 20 64 61 74 _size_ bytes dat 0810: 61 0a 35 2e 20 31 36 20 62 79 74 65 73 20 61 75 a.5. 16 bytes au 0820: 74 68 65 6e 74 69 63 61 74 69 6f 6e 20 64 61 74 thentication dat 0830: 61 20 28 6b 65 79 65 64 20 63 72 79 70 74 6f 67 a (keyed cryptog 0840: 72 61 70 68 69 63 20 63 68 65 63 6b 73 75 6d 29 raphic checksum) 0850: 0a 0a 54 68 65 20 e2 80 9c 61 62 73 74 72 61 63 ..The “abstrac 0860: 74 69 6f 6e e2 80 9d 20 61 74 20 70 61 63 6b 65 tion” at packe 0870: 74 20 6c 65 76 65 6c 20 69 73 20 73 68 61 72 65 t level is share 0880: 64 20 6d 65 6d 6f 72 79 3b 20 74 68 65 20 6d 6f d memory; the mo 0890: 64 65 6c 20 69 73 20 72 65 61 64 0a 6c 6f 63 61 del is read.loca 08a0: 6c 6c 79 20 61 6e 64 20 77 72 69 74 65 20 72 65 lly and write re 08b0: 6d 6f 74 65 6c 79 20 28 79 6f 75 20 63 61 6e 27 motely (you can' 08c0: 74 20 72 65 61 64 20 72 65 6d 6f 74 65 6c 79 2c t read remotely, 08d0: 20 79 6f 75 20 63 61 6e 20 61 73 6b 20 66 6f 72 you can ask for 08e0: 20 74 68 65 20 6f 74 68 65 72 0a 73 69 64 65 20 the other.side 08f0: 74 6f 20 73 65 6e 64 20 79 6f 75 20 70 61 63 6b to send you pack 0900: 65 74 73 29 2e 20 c2 a0 4f 66 20 63 6f 75 72 73 ets). Of cours 0910: 65 2c 20 74 68 65 20 61 64 64 72 65 73 73 65 73 e, the addresses 0920: 20 61 72 65 20 76 69 72 74 75 61 6c 2c 20 73 6f are virtual, so 0930: 20 79 6f 75 0a 63 61 6e 27 74 20 77 72 69 74 65 you.can't write 0940: 20 69 6e 74 6f 20 61 72 62 69 74 72 61 72 79 20 into arbitrary 0950: 6d 65 6d 6f 72 79 20 e2 80 94 20 6f 6e 6c 79 20 memory — only 0960: 69 6e 74 6f 20 74 68 65 20 62 75 66 66 65 72 73 into the buffers 0970: 20 70 72 6f 76 69 64 65 64 20 62 79 20 74 68 65 provided by the 0980: 20 6f 74 68 65 72 0a 73 69 64 65 2e 0a 0a 23 23 other.side...## 0990: 20 57 68 79 20 53 6f 75 72 63 65 20 52 6f 75 74 Why Source Rout 09a0: 69 6e 67 3f 0a 0a 54 68 65 72 65 20 61 72 65 20 ing?..There are 09b0: 74 68 72 65 65 20 70 6f 73 73 69 62 6c 65 20 73 three possible s 09c0: 63 68 65 6d 65 73 3a 0a 0a 31 2e 20 73 77 69 74 chemes:..1. swit 09d0: 63 68 65 64 20 63 69 72 63 75 69 74 20 28 50 4f ched circuit (PO 09e0: 54 53 2c 20 76 69 72 74 75 61 6c 3a 20 41 54 4d TS, virtual: ATM 09f0: 2c 20 4d 50 4c 53 29 0a 32 2e 20 75 6e 69 71 75 , MPLS).2. uniqu 0a00: 65 20 69 64 65 6e 74 69 66 69 65 72 20 28 49 50 e identifier (IP 0a10: 29 0a 33 2e 20 73 6f 75 72 63 65 20 72 6f 75 74 ).3. source rout 0a20: 69 6e 67 0a 0a 49 20 77 61 6e 74 20 74 6f 20 73 ing..I want to s 0a30: 65 70 61 72 61 74 65 20 63 6f 6d 70 75 74 65 72 eparate computer 0a40: 73 20 61 6e 64 20 6e 65 74 77 6f 72 6b 20 64 65 s and network de 0a50: 76 69 63 65 73 3b 20 73 6f 75 72 63 65 20 72 6f vices; source ro 0a60: 75 74 69 6e 67 20 61 6c 6c 6f 77 73 20 74 6f 0a uting allows to. 0a70: 75 73 65 20 73 69 6d 70 6c 65 2c 20 66 61 73 74 use simple, fast 0a80: 2c 20 73 74 61 74 65 6c 65 73 73 20 65 71 75 69 , stateless equi 0a90: 70 6d 65 6e 74 20 66 6f 72 20 73 77 69 74 63 68 pment for switch 0aa0: 69 6e 67 20 28 6f 72 20 61 74 20 6c 65 61 73 74 ing (or at least 0ab0: 20 65 71 75 69 70 6d 65 6e 74 20 77 69 74 68 0a equipment with. 0ac0: 61 20 73 6d 61 6c 6c 20 61 6d 6f 75 6e 74 20 6f a small amount o 0ad0: 66 20 73 74 61 74 65 3a 20 41 20 73 6d 61 6c 6c f state: A small 0ae0: 20 6d 61 70 70 69 6e 67 20 74 61 62 6c 65 20 69 mapping table i 0af0: 73 20 68 65 6c 70 66 75 6c 20 74 6f 20 67 69 76 s helpful to giv 0b00: 65 20 61 20 62 69 74 0a 61 6e 6f 6e 79 6d 69 74 e a bit.anonymit 0b10: 79 2c 20 62 79 20 72 65 67 75 6c 61 72 6c 79 20 y, by regularly 0b20: 63 68 61 6e 67 69 6e 67 20 74 68 65 20 6d 61 70 changing the map 0b30: 70 69 6e 67 29 2e 0a ping)..