home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1997 December / Internet_Info_CD-ROM_Walnut_Creek_December_1997.iso / drafts / draft_n_r / draft-panabaker-ip-vbi-01.txt < prev    next >
Text File  |  1997-10-14  |  38KB  |  871 lines
  1. INTERNET-DRAFT                                             R. Panabaker
  2. < draft-panabaker-ip-vbi-01.txt >                       Microsoft Corp.
  3. Obsoletes: NA                                                  C. Witty
  4. Category:                                          Newton Research Labs
  5.                                                              March 1997
  6.  
  7.  
  8.  
  9.      THE TRANSMISSION OF IP OVER THE VERTICAL BLANKING INTERVAL OF A
  10.                         TELEVISION SIGNAL
  11.  
  12.  
  13. 1. Status of this Memo
  14.  
  15. This document is an Internet-Draft.  Internet-Drafts are working 
  16. documents of the Internet Engineering Task Force (IETF), its areas, and 
  17. its working groups.  Note that other groups may also distribute working 
  18. documents as Internet-Drafts.
  19.  
  20. Internet-Drafts are draft documents valid for a maximum of six months 
  21. and may be updated, replaced, or obsoleted by other documents at any 
  22. time.  It is inappropriate to use Internet-Drafts as reference material 
  23. or to cite them other than as "work in progress."
  24.  
  25. To learn the current status of any Internet-Draft, please check the 
  26. "1id-abstracts.txt" listing contained in the Internet-Drafts Shadow 
  27. Directories on ftp.is.co.za (Africa), ftp.nordu.net (Europe), 
  28. munnari.oz.au (Pacific Rim), ds.internic.net (US East Coast), or 
  29. ftp.isi.deu (US West Coast).
  30.  
  31. 2. Abstract
  32.  
  33. This is an Internet-Draft, which describes a method for broadcasting 
  34. multicast IP data using the vertical blanking interval of a television 
  35. signal.  It includes a description for compressing multicast IP headers 
  36. on unidirectional networks, a framing protocol identical to SLIP, and a 
  37. forward error correction scheme for the NABTS standard.
  38.  
  39. Keywords: VBI, NTSC, broadcast, push, FEC, television, NABTS, IP
  40.  
  41. 3. Table of Contents
  42.  
  43. 1.    Status of this Memo . . . . . . . . . . . . . . . . . . . . . . 1
  44. 2.    Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . .1
  45. 3.    Table of Contents . . . . . . . . . . . . . . . . . . . . . . . 1
  46. 4.    Introduction . . . . . . . . . . . . . . . . . . . . . . . . . .2
  47. 5.    Proposed protocol stack . . . . . . . . . . . . . . . . . . . . 2
  48. 5.1.     VBI . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
  49. 5.2.     NABTS . . . . . . . . . . . . . . . . . . . . . . . . . . . .4
  50. 5.3.     FEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
  51. 5.4.     Framing . . . . . . . . . . . . . . . . . . . . . . . . . . .6
  52. 5.5.     IP compression . . . . . . . . . . . . . . . . . . . . . . . 6
  53. 6.    Addressing Considerations . . . . . . . . . . . . . . . . . . . 7
  54. 7.    Performance analysis . . . . . . . . . . . . . . . . . . . . . .7
  55.  
  56.  
  57. Panabaker                                                      [Page 1]
  58.  
  59. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  60.  
  61. 8.    Architecture . . . . . . . . . . . . . . . . . . . . . . . . . .8
  62. 9.    Scope of proposed protocols . . . . . . . . . . . . . . . . . . 8
  63. 10.   Security considerations . . . . . . . . . . . . . . . . . . . . 9
  64. 11.   Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . 9
  65. 12.   References . . . . . . . . . . . . . . . . . . . . . . . . . . .9
  66. 13.   Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
  67. 14.   Author's address and contacts . . . . . . . . . . . . . . . . .10
  68. 15.   Appendix:  Forward Error Correction Specification . . . . . . .11
  69. 15.1.    Mathematics used in the FEC . . . . . . . . . . . . . . . . 11
  70. 15.2.    Calculating FEC bytes . . . . . . . . . . . . . . . . . . . 12
  71. 15.3.    Correcting Errors . . . . . . . . . . . . . . . . . . . . . 12
  72. 15.4.    Correcting FEC Bundles . . . . . . . . . . . . . . . . . . .15
  73. 15.5.    Appendix References . . . . . . . . . . . . . . . . . . . . 15
  74.  
  75. 4. Introduction
  76.  
  77. This Internet-Draft proposes several protocols to be used in the 
  78. transmission of IP datagrams across the Vertical Blanking Interval 
  79. (VBI) of a television signal.  The VBI is an non-viewable portion of 
  80. the television signal that can be used to provide point-to-multipoint 
  81. IP data services which will relieve congestion and traffic in the 
  82. traditional Internet access networks.  Wherever possible these 
  83. protocols make use of existing RFC standards and non-standards.
  84.  
  85. Traditionally, point to point connections (TCP/IP) have been used even 
  86. for the transmission of broadcast type data.  Distribution of the same 
  87. content - news feeds, stock quotes, newsgroups, weather reports, and 
  88. the like - are typically sent repeatedly to individual clients rather 
  89. than being broadcast to the large number of users who want to receive 
  90. such data.
  91.  
  92. Today, multicast-IP is quickly becoming the preferred method of 
  93. distributing one-to-many data on Intranets and the Internet.  With the 
  94. coming availability of low cost PC hardware for receiving television 
  95. signals accompanied by broadcast data streams, it is imperative that a 
  96. standard be defined for the transmission of data over traditional 
  97. broadcast networks.  A lack of standards in this area as well as the 
  98. expense of hardware has, in the past, prevented traditional broadcast 
  99. networks from becoming effective deliverers of data to the home and 
  100. office.
  101. This document describes the transmission of multicast-IP using the 
  102. North American Basic Teletext Standard (NABTS), a recognized and 
  103. industry supported method of transporting data on the VBI.  This will 
  104. allow existing standards from the television and Internet communities 
  105. to provide inexpensive broadcast data services.  Additional protocols 
  106. will be used to do this including a serial stream framing protocol 
  107. similar to SLIP (RFC 1055 [Romkey 1988]) and a Van Jacobson style 
  108. compression technique  (RFC 1144) for unidirectional multicast UDP/IP 
  109. headers. 
  110.  
  111. I would like to acknowledge the tremendous assistance of Ken Birdwell, 
  112. Dave Feinleib and Brian Moran, of Microsoft Corp, and Carl Witty, of 
  113.  
  114.  
  115. Panabaker                                                      [Page 2]
  116.  
  117. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  118.  
  119. Newton Research Labs, in writing this document.  Many of the ideas 
  120. expressed within are the result of their efforts and insight in this 
  121. area.  Any of these ideas that prove misbegotten are the sole 
  122. responsibility of the author.
  123.  
  124. 5. Proposed protocol stack
  125.  
  126. The following protocol stack demonstrates the layers used in the 
  127. transmission of VBI data. Each layer has no knowledge of the data it 
  128. encapsulates and is therefore abstracted from the other layers.  At the 
  129. link layer, the NABTS protocol defines the modulation scheme used to 
  130. transport data on the VBI.  At the network layer IP handles the 
  131. movement of data to the appropriate computers and UDP, in the transport 
  132. layer, determines the flow of data to the appropriate processes and 
  133. applications.
  134.         +-----------+
  135.         |           |
  136.         |Application|
  137.         |           |
  138.         +-----------+
  139.         |           |  ) 
  140.         |    UDP    |   )
  141.         |           |   )
  142.         +-----------+   (-- multicast-IP
  143.         |           |   )
  144.         |    IP     |   )
  145.         |           |  )
  146.         +-----------+
  147.         |SLIP style |
  148.         |  encap-   |
  149.         | -sulation |
  150.         +-----------+
  151.         |           |
  152.         |   NABTS   |
  153.         | with FEC  |
  154.         +-----------+
  155.               |            The VBI of NTSC medium 
  156.               |            (cable, off-air, etc)
  157.               |--------<----<----<--------
  158.  
  159.  
  160. These protocols can be described in a bottom up component model as 
  161. follows:
  162.  
  163. NTSC signal --> NABTS --> FEC --> serial data stream --> Framing 
  164. protocol --> Van Jacobson style compressed UDP/IP headers --> 
  165. application data
  166.  
  167. This diagram can be read as follows: NTSC signals have NABTS packets 
  168. modulated onto them which contain a Forward Error Correction (FEC) 
  169. protocol.  The data contained in these sequential, ordered packets form 
  170. a serial data stream on which a framing protocol indicates the location 
  171.  
  172.  
  173. Panabaker                                                      [Page 3]
  174.  
  175. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  176.  
  177. of multicast-IP packets, with compressed headers, containing 
  178. application data. 
  179.  
  180. The structure of these components and protocols are described in 
  181. following subsections.
  182.  
  183. 5.1. VBI
  184.  
  185. An NTSC television frame is comprised of 2 fields of 262.5 horizontal 
  186. scan lines each.  The first 21 lines of each field are not part of the 
  187. visible picture and are collectively called the Vertical Blanking 
  188. Interval (VBI).  Of these 21 lines the first 9 are used while 
  189. repositioning the cathode ray to the top of the screen, but the 
  190. remaining lines are available for data transport.
  191.  
  192. Line 21 itself is reserved for the transport of closed captioning data.  
  193. There are therefore 11 possible VBI lines being broadcast 60 times a 
  194. second (each field 30 times a second), some or all of which could be 
  195. used for multicast IP transport.  It should be noted that some of these 
  196. lines are sometimes used for existing, proprietary, data and testing 
  197. services.  Multicast IP therefore becomes one more data service using a 
  198. subset or all of these lines.
  199.  
  200. 5.2. NABTS
  201.  
  202. The North American Basic Teletext Standard is defined in the 
  203. Electronics Industry Associations EIA-516.  It provides an industry-
  204. accepted method of modulating data onto the VBI of an NTSC signal.  
  205. This section describes the NABTS packet format as it is used for the 
  206. transport of multicast IP.  It should be noted that only a subset of 
  207. the NABTS standard is used, as is common practice in NABTS 
  208. implementations.  Further information concerning the NABTS standard and 
  209. its implementation can be found in EIA-516.
  210.  
  211. The NABTS packet is a 36-byte structure encoded onto one horizontal 
  212. scan line of an NTSC signal having the following structure:
  213.  
  214. {2 B clock sync}{1 B byte sync}{3 B packet group address}{1 B 
  215. continuity index}{1 B packet structure flags}{26 B data block}{2 B FEC 
  216. suffix}
  217.  
  218. The 2 byte Clock Synchronization and the 1 byte Byte Synchronization, 
  219. although not part of the NABTS packet, are located at the beginning of 
  220. every scan line containing a NABTS packet and are used to synchronize 
  221. the decoding sampling rate and byte timing.
  222.  
  223. The 3 byte Packet Group address field is Hamming encoded (as specified 
  224. in EIA-516, and provides 4 data bits per byte, and thus provides 4096 
  225. possible packet group addresses.  These addresses are used to 
  226. distinguish related services originating from the same source. This is 
  227. necessary for the receiver to determine which packets are related and 
  228. part of the same service.  NABTS packet group addresses therefore 
  229.  
  230.  
  231. Panabaker                                                      [Page 4]
  232.  
  233. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  234.  
  235. distinguish different data services, possibly inserted at different 
  236. points of the transmission system, and most likely totally unrelated.  
  237. Section 5 of this document discusses Packet Group Addresses in greater 
  238. detail.
  239.  
  240. The 1 byte Continuity Index field is a Hamming encoded byte, which is 
  241. incremented by one for each packet of a given Packet Group address.  
  242. The index number is determined by the packetÆs order in the FEC bundle 
  243. mentioned in the FEC section.  The first packet in the bundle has count 
  244. 0, and the two FEC only packets at the end have counts 14 and 15 
  245. respectively.  This allows the decoder to determine if packets have 
  246. been lost during transmission.
  247.  
  248. The Packet Structure field is also a Hamming encoded byte, which 
  249. contains information about the structure of the remaining portions of 
  250. the packet.  The most significant bit is always 0 in this 
  251. implementation.  The second significant bit specifies whether the Data 
  252. Block is full (0 indicates the data block is full of useful data, 1 
  253. indicates some or all of the data is filler data), and the least two 
  254. significant bits are used to indicate the length of the suffix on the 
  255. Data Block, in this implementation either 2 or 28 bytes.  This suffix 
  256. is used for the forward error correction described in the next section.
  257.  
  258. The Data Block field is 0 to 26 bytes of useful data.  Filler data is 
  259. indicated by a 0x15 followed by as many 0xEA as are needed to fill the 
  260. packet.  Sequential data blocks minus the filler data form an 
  261. asynchronous serial stream of data.
  262.  
  263. These NABTS packets are modulated onto the NTSC signal sequentially and 
  264. on any combination of lines.  Section 6 of this document discusses the 
  265. resulting bit rates and overheads associated with NABTS.
  266.  
  267. 5.3. FEC
  268.  
  269. Due to the unidirectional nature of VBI data transport, forward error 
  270. correction is needed to ensure the integrity of data at the receiver.  
  271. Any FEC could be used to this end.  The FEC for NABTS described in the 
  272. appendix of this document has been in use for a number of years, and 
  273. has proven popular with the broadcast industry.  It is capable of 
  274. correcting single byte errors and single and double byte erasures in 
  275. the data block and suffix of a NABTS packet. 
  276.  
  277. The FEC algorithm splits a serial stream of data into 364 byte 
  278. "bundles".  These are arranged as 14 packets of 26 bytes each.  A 
  279. function is applied to the 26 bytes of each packet to determine the two 
  280. suffix bytes for that, which (with the addition of a header) complete 
  281. the NABTS packet (8+26+2).
  282.  
  283. For every 14 packets in the bundle an additional 2 packets are appended 
  284. which contain only FEC data.  That is, they contain 28 bytes of FEC 
  285. data.  This data is obtained by first writing the packets into a table 
  286. of 16 rows and 28 columns.  The same expression as above can be used on 
  287.  
  288.  
  289. Panabaker                                                      [Page 5]
  290.  
  291. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  292.  
  293. the columns of the table with the suffix now represented by the bytes 
  294. at the base of the columns in rows 15 and 16.  With NABTS headers on 
  295. each of these rows, we now have a bundle of 16 NABTS packets ready for 
  296. sequential modulation onto lines of the NTSC signal.
  297.  
  298. At the receiving end of the network these formulae can be used to 
  299. verify the validity of the data with very high accuracy.  If single 
  300. byte errors or single and double byte erasures are found in any row or 
  301. column (including an entire packet lost) they can be corrected using 
  302. the algorithms found in the appendix.
  303.  
  304. 5.4. Framing
  305.  
  306. A framing protocol identical to SLIP is proposed for encapsulating IP 
  307. datagrams, thus abstracting this data from the lower protocol layers.  
  308. This protocol uses two special characters: END (0xc0) and ESC (0xdb).  
  309. To send a packet, the host will send the packet followed by the END 
  310. character.  If a data byte in the packet is the same code as END 
  311. character, a two byte sequence of ESC (0xdb) and 0xdc is sent instead.  
  312. If a data byte is the same code as ESC character, a two-byte sequence 
  313. of ESC (0xdb) and 0xdd is sent instead.  SLIP implementations are 
  314. widely available, see RFC 1055 [Romkey 1988] for more detail.   
  315.  
  316. +--------------+--+------------+--+--+---------+--+
  317. |IP packet     |c0| IP packet  |db|dd|         |c0|
  318. +--------------+--+------------+--+--+---------+--+
  319.                 END              ESC            END
  320.  
  321. 5.5.     IP compression
  322.  
  323. Finally we have the multicast IP packet (RFC 1112 [Deering 1989]).  Due 
  324. to the value of bandwidth, it is desirable to introduce as much 
  325. efficiency as possible.  One such efficiency is the compression of the 
  326. multicast UDP/IP header using a method similar to the TCP/IP header 
  327. compression as described by Van Jacobson (RFC 1144).  UDP/IP header 
  328. compression is not identical due to the limitation of unidirectional 
  329. transmission.
  330.  
  331. The following two packet formats are used in the following compression 
  332. scheme:
  333.  
  334. The first byte of all packets is the Compression Key.  It is a 1 byte 
  335. value, the first bit of which indicating if the header has been 
  336. compressed, and the remaining 7 bits indicating the compression group 
  337. it belongs to.
  338.  
  339. [0:1][Index:7][protocol:16][full headers:224][data][CRC:32]
  340.  
  341. [1:1][Index:7][compressed header:32][data][CRC:32]
  342.  
  343. If the high bit of the Compression Key is set to 0, no compression is 
  344. performed and the 2-byte protocol number (the same as 802.3 Ethernet) 
  345.  
  346.  
  347. Panabaker                                                      [Page 6]
  348.  
  349. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  350.  
  351. and the full header are sent. The client VBI interface should store the 
  352. protocol number and uncompressed header for future potential use.
  353.  
  354. If the high bit of the Compression Key is set to 1, the protocol number 
  355. is not sent, and a compressed version of that protocol's header is 
  356. sent.  The client VBI interface must then combine the compressed header
  357. with the stored uncompressed header and recreate a full packet.
  358.  
  359. As indicated, this compression scheme will support any packet protocol.  
  360. Currently, and for the purpose of this document, the only protocol 
  361. compression defined is for DoD IP, protocol number 0x0800.  When 
  362. uncompressed, the entire UDP/IP header is sent.  When compressed, only 
  363. the "IP identification" and the "fragment offset/flags" are sent.  The 
  364. client VBI interface should combine these with the previously saved 
  365. header. 
  366.  
  367. [0:1][Group:7][0x0800][IP header][UDP header]
  368. [1:1][Group:7][IP identification][fragment offset/flags]
  369.  
  370. A 32 bit CRC has also been added to the end of every packet to ensure 
  371. data integrity.  It is performed over the entire, uncompressed, IP 
  372. packet, and uses the same algorithm as the MPEG-2 transport stream 
  373. (ISO/IEC 13818-1).  The generator polynomial is:
  374.  
  375. 1 + D + D^2 + D^4 + D^5 + D^7 + D^8  D^10 + D^11 + D^12 + D^16 + D^22 + 
  376. D^23 + D^26 + D^32
  377.  
  378. As in the ISO/IEC 13818-1 specification, the initial state of the sum 
  379. is 0xFFFFFFFF.  This is not the same algorithm used by Ethernet.  
  380.  
  381. This CRC provides a final check for damaged datagrams, which spanned 
  382. FEC bundles or were not corrected properly by FEC.
  383.  
  384. 6. Addressing Considerations
  385.  
  386. The addressing of multicast IP packets should adhere to existing 
  387. standards in this area.  The inclusion of an appropriate source address 
  388. is needed to ensure the receiving client can distinguish between 
  389. sources and thus services.
  390.  
  391. NABTS packet addressing is not regulated or standardized and requires 
  392. care to ensure that unrelated services on the same channel are not 
  393. broadcasting with the same packet group address.  This could occur due 
  394. to multiple possible injection sites, including show production, 
  395. network redistribution, regional operator, and local operator.  
  396. Traditionally the marketplace has recognized this concern and made 
  397. amicable arrangements for the distribution of these addresses for each 
  398. channel.  
  399.  
  400. 7. Performance analysis
  401.  
  402. This section performs an analysis of the overheads associated with each 
  403.  
  404.  
  405. Panabaker                                                      [Page 7]
  406.  
  407. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  408.  
  409. of the protocols described above, and the resulting bit rates.
  410.  
  411. Every line of an NTSC picture is capable of carrying a 36-byte NABTS 
  412. packet (including sync bytes).  Every line is refreshed once every 
  413. 1/60th of a second, which results in a bit rate of 17,280 bps.  
  414.  
  415. The NABTS packet has 8 bytes of overhead on each 36 byte packet, or 
  416. 22.2% overhead.  FEC has 2 bytes on every packet plus 2 packets added 
  417. for every group of 14.  This brings the total overhead so far to 36.8%.    
  418.  
  419. The remaining data can now be treated as an asynchronous serial stream.  
  420. Assume an IP packet size of 350 bytes for the following calculations.  
  421.  
  422. The framing of IP packets adds 1.7% overhead to the data stream, or 
  423. 1.07% to the total overhead on all bits, assuming 2 escapes per packet.  
  424. This brings the running total to 37.9% overhead.
  425.  
  426. IP overhead is reduced with the use of header compression.  The 
  427. uncompressed version includes the compression index, protocol number, 
  428. the entire UDP/IP header, and CRC for a total of 34 bytes overhead.  
  429. The compressed version has only 9 bytes in its header.  Assuming we 
  430. only transmit the uncompressed packet once in every 10 packets, we get 
  431. an average header of only 11.5 bytes.  This adds an additional 2% 
  432. overhead on the total bits transmitted, bringing the total overhead to 
  433. 39.9%.
  434.  
  435. The theoretical throughput is therefore 17,280*(1-.399) or 10,380 bps 
  436. per line.  This is easily scalable to 115 Kbps for all 11 lines of the 
  437. VBI, or 2.7 Mbps for the entire screen.
  438.  
  439. 8. Architecture
  440.  
  441. The architecture that this document is addressing can be broken down 
  442. into 3 areas: insertion, distribution network, and receiving client.
  443.  
  444. The insertion of IP data onto the NTSC signal can occur at any part of 
  445. the delivery system.  A NABTS hardware encoder accepts a video signal 
  446. and an asynchronous serial stream of framed IP as inputs and packetizes 
  447. the data onto a selected set of lines using NABTS and an FEC.  This 
  448. composite signal is then modulated with other channels before being 
  449. broadcast onto the distribution network.  Operators further down the 
  450. distribution chain could then add their own data, to other unused 
  451. lines, as well.
  452.  
  453. The distribution networks include coax plant, off-air, and analog 
  454. satellite systems and are primarily unidirectional broadcast networks.  
  455. They must provide a signal to noise ratio which is sufficient for FEC 
  456. to recover any lost data for the broadcast of data to be effective.
  457.  
  458. The receiving client must be capable of tuning, NABTS waveform 
  459. sampling, filtering on NABTS group addresses, forward error correction, 
  460. unframing, verification of the CRC and decompressing the UDP/IP 
  461.  
  462.  
  463. Panabaker                                                      [Page 8]
  464.  
  465. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  466.  
  467. headers.  All of the above functions can be carried out in PC software 
  468. and inexpensive off-the-shelf hardware.
  469.  
  470. 9. Scope of proposed protocols
  471.  
  472. The protocols described in this document are for the purpose of 
  473. transmitting multicast IP packets.  However, their scope may be 
  474. extensible to other applications outside this area.  Many of the 
  475. protocols in this document could be implemented on any unidirectional 
  476. network.  NABTS is a standard used on NTSC signals and the FEC was 
  477. designed primarily for use with NABTS packet data.  However, the data 
  478. transported is simply an asynchronous serial stream, and is therefore 
  479. abstracted from the transport mechanism of these two protocols.
  480.  
  481. Many NABTS encoders work with PAL, SECAM, and NTSC-J video formats as 
  482. well.  This would require different waveform sampling and decoding on 
  483. the client, but would allow all 900+ million cable subscribers in the 
  484. world to receive IP over the VBI.  It should also be noted that NABTS 
  485. could be used in a full screen mode, in which all lines of the picture 
  486. frame were used for data transport.  There are obviously issues 
  487. concerning the logistics of this service, but the possibility exists, 
  488. and many VBI decoders support this functionality.
  489.  
  490. The unidirectional framing protocol provides encapsulation of multicast 
  491. IP datagrams on the serial stream, and the Van Jacobson style 
  492. compression of the UDP/IP headers reduces the overhead on transmission, 
  493. thus conserving bandwidth.  These two protocols could be widely used on 
  494. different unidirectional broadcast networks or modulation schemes to 
  495. efficiently transport any type of packet data.  In particular, new 
  496. versions of Internet protocols can be supported to provide a 
  497. standardized method of data transport.
  498.  
  499. 10. Security considerations
  500.  
  501. As with any broadcast network, there are security issues due to the 
  502. accessibility of data.  It is assumed that the responsibility for 
  503. securing data lies in the application layer protocol, which is beyond 
  504. the scope of this document.
  505.  
  506. 11. Conclusions
  507.  
  508. This document provides a method for broadcasting Internet data over a 
  509. television signal for reception by client computers.  With an 
  510. appropriate "push and filter" content model, this will become an 
  511. attractive method of providing data services to end users.  By using 
  512. existing standards and a layered protocol approach, this document has 
  513. also provided a model for data transmission on unidirectional and 
  514. broadcast networks.
  515.  
  516. 12. References
  517.  
  518. [1] Deering, S. E. 1989.  "Host Extensions for IP Multicasting," RFC 
  519. 1112, 17 pages (Aug.).
  520.  
  521. Panabaker                                                      [Page 9]
  522.  
  523. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  524.  
  525.  
  526. [2] EIA-516, "Joint EIA/CVCC Recommended Practice for Teletext: North 
  527. American Basic Teletext Specification (NABTS)" Washington: Electronic 
  528. Industries Association, c1988
  529.  
  530.  [3] Jack, Keith. "Video Demystified: A Handbook for the Digital 
  531. Engineer, Second Edition," San Diego: HighText Pub.  c1996.
  532.  
  533. [4] Jacobson, V.  1990a.  "Compressing TCP/IP Headers for Low-Speed 
  534. Serial Links," RFC 1144, 43 pages (Feb.).
  535.  
  536. [5] Norpak Corporation "TTX71x Programming Reference Manual", c1996, 
  537. Kanata, Ontario, Canada 
  538.  
  539. [6] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder 
  540. Software User's Manual." c1996, Kanata, Ontario, Canada
  541.  
  542. [7] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata, 
  543. Ontario, Canada
  544.  
  545. [8] Romkey, J. L.  1988.  "A Nonstandard for Transmission of IP 
  546. Datagrams Over Serial Lines: SLIP,"  RFC 1055, 6 pages (June).
  547.  
  548. [9] Stevens, W. Richard.  "TCP/IP Illustrated, Volume 1,: The 
  549. Protocols"  Reading:      Addison-Wesley Publishing Company, c1994.
  550.  
  551. 13. Acronyms
  552.  
  553. VBI            - Vertical Blanking Interval
  554. FEC            - Forward Error Correction
  555. NABTS          - North American Basic Teletext Standard
  556. NTSC           - National Television Standards Committee
  557. PAL            - Phase Alternation Line
  558. SECAM          - Sequentiel Couleur Avec Memoire (sequential color with 
  559. memory)
  560. NTSC-J         - Japanese flavor of NTSC
  561. RFC            - Request For Comments
  562. IP             - Internet Protocol
  563. UDP            - User Datagram Protocol
  564. TCP            - Transmission Control Protocol
  565. SLIP           - Serial Line Internet Protocol
  566.  
  567. 14. Author's address and contacts
  568.  
  569. Ruston Panabaker
  570. One Microsoft Way
  571. Redmond, WA
  572. 98052-6399
  573. email: BPCfeed@microsoft.com
  574.  
  575. Other contacts:
  576.  
  577.  
  578.  
  579. Panabaker                                                     [Page 10]
  580.  
  581. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  582.  
  583. Brian Moran
  584. One Microsoft Way
  585. Redmond, WA
  586. 98052-6399
  587. brianmo@microsoft.com
  588. T: (206) 936-4376
  589.  
  590. Dave Feinleib
  591. One Microsoft Way
  592. Redmond, WA
  593. 98052-6399
  594. davefe@microsoft.com
  595. T: (206) 703-5543
  596.  
  597. 15. Appendix:  Forward Error Correction Specification
  598.  
  599. This FEC is specified as used for the detection and correction of 
  600. errors incurred during transmission on the vertical blanking interval 
  601. in NABTS packets.  Carl Witty (< biblio >) wrote the original 
  602. specification, from which this appendix was written.  We begin with a 
  603. brief description of the mathematics used throughout this 
  604. specification.
  605.  
  606. 15.1. Mathematics used in the FEC
  607.  
  608. Galois fields form the basis for the FEC algorithm presented here.  
  609. Rather then explain these fields in general, a specific explanation is 
  610. given of the Galois field used in the FEC algorithm.
  611.  
  612. The Galois field used is GF(2^8).  This is a set of 256 elements, along 
  613. with the operations of "addition" and "multiplication" on these 
  614. elements.  Each element is represented by an 8 bit binary number. 
  615.  
  616.  The operation of "addition" with this Galois field is the XOR of two 
  617. elements.  Thus, the "sum" of 00011011 and 00000111 is 00011100.
  618.  
  619. Division of two elements is done using long division with subtraction 
  620. operations replaced by XOR.  For multiplication, standard long 
  621. multiplication is used but with the final addition stage replaced with 
  622. XOR.
  623.  
  624. All arithmetic in the following FEC is done modulo 100011101; for 
  625. instance, after you multiply two numbers, you replace the result with 
  626. its remainder when divided by 100011101.  There are 256 values in this 
  627. field (256 possible remainders), the 8-bit numbers.  It is very 
  628. important to remember that when we write A*B = C, we more accurately 
  629. imply modulo(A*B) = C.
  630.  
  631. These Galois elements have many properties in common with the real 
  632. numbers:
  633. - every nonzero x has an inverse x^-1 , such that x*x^-1=1
  634. - (xy)^-1 = x^-1 * y^-1
  635.  
  636.  
  637. Panabaker                                                     [Page 11]
  638.  
  639. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  640.  
  641. - x(yz) = (xy)z
  642. - x + (y + z) = (x +y) + z
  643. - xy = yx
  644. - x + y = y + x
  645. - (x + y)z = xz + yz
  646. - if xy = xz then x = 0 or y = z
  647. - if xy = 0 then x = 0 or y = 0
  648. - x^(a+b) = x^a * x^b (here a and b are standard numbers not in the 
  649. Galois field and a+b denotes standard addition)
  650.  
  651. There are also many properties which differ from the real numbers:
  652. - for every nonzero x, x^255 = 1 (this implies that x^254 = x^-1)
  653. - x + x = 0
  654.  
  655. 15.2. Calculating FEC bytes
  656.  
  657. The FEC algorithm splits a serial stream of data into 364 byte 
  658. "bundles".  These are arranged as 14 packets of 26 bytes each.  Across 
  659. each packet the following expression is determined for each of the two 
  660. suffix bytes, S0 and S1, which (with the addition of a header) complete 
  661. the NABTS packet (8+26+2):
  662.  
  663.         Sum, as i goes from 0-25, of   Ci,j * Di    =  Sj
  664.  
  665. Where, Ci,j is a tabulated coefficient, Di is the ith data byte of the 
  666. data block, and j can be 0 and 1.  The multiplications and additions in 
  667. this formula are done using Galois fields and modulo arithmetic as 
  668. explained above.
  669.  
  670. The tabulated coefficients are:
  671.  
  672. Ci,0 = {0x9d, 0x37, 0xe4, 0xcb, 0x7f, 0xab, 0x8d, 0xbb, 0xb1, 0x6a, 
  673. 0xde, 0x8a, 0x4a, 0x20, 0x98, 0x9d, 0xbb, 0x94, 0x3d, 0x38, 0xa6, 0xe9, 
  674. 0x42, 0xa0, 0xe2, 0x64, },
  675. and... 
  676. Ci,1 = {0x92, 0x97, 0xdd, 0xa0, 0x9a, 0x91, 0x0a, 0x50, 0x1d, 0x60, 
  677. 0xae, 0x20, 0x3d, 0x2c, 0x01, 0x0a, 0x40, 0xc8, 0xe5, 0xff, 0xf2, 0x68, 
  678. 0xc9, 0xa1, 0x63, 0x8d, }.
  679.  
  680. For every 14 packets in the bundle an additional 2 packets are appended 
  681. which contain only FEC data.  This data is obtained by first writing 
  682. the packets into a table of 16 rows and 28 columns.  The same formula 
  683. as above can be used on the columns of the table with S0 and S1 now 
  684. representing the byte at the base of the column in row 15 or 16 
  685. respectively. Therefore we calculate 
  686.  
  687.       Sum, as i goes from 0-13, of Ci,j * Di  =  Sj
  688.  
  689. for each column.  Where, Ci,j is a coefficient from the same table as 
  690. above, Di is the nth byte of the ith row, and j can be 0 and 1.
  691.  
  692. 15.3. Correcting Errors
  693.  
  694.  
  695. Panabaker                                                     [Page 12]
  696.  
  697. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  698.  
  699.  
  700. This section describes the procedure for detecting and correcting 
  701. errors using the FEC data calculated above.  Upon reception we begin by 
  702. arranging the packets in tabular form similar to that in the previous 
  703. section.  We form a column of 16 packets each containing 28 bytes 
  704. ofdata.  We will be detecting and correcting errors in these rows and 
  705. columns.
  706.  
  707. Since the horizontal and vertical FEC are the same (except for the 
  708. number of byes of data to be protected), the algorithms here will work 
  709. in both directions.  We will use k as the number of bytes of data to be 
  710. protected, so k is either 26 (for horizontal FEC) or 14 (for vertical 
  711. FEC).  The original, error-free bytes are D0, D1, ....Dk, Dk+1 (note 
  712. that the FEC bytes are included as Dk and Dk+1), and the received bytes 
  713. with possible errors are R0,....., Rk+1.
  714.  
  715. We know that if no errors occurred, we would have
  716.  
  717.        the sum, as i goes from 0 to k-1 of Ci,j * Ri = Rk+j,
  718.  
  719. for j=0,1.  In the Galois field this can be written as 
  720.  
  721. (the sum, as i goes from 0 to k-1 of Ci,j * Ri) + Rk+j = 0.      Eqn 1
  722.  
  723.  Conversely, if errors did occur, it is most likely that this equation 
  724. would not be true.  We can therefore assume that if Eqn 1 is satisfied, 
  725. no errors occurred.
  726.  
  727. 15.3.1. Detecting and correcting single-byte errors
  728.  
  729. When Eqn 1 is not satisfied there are one or more errors in the 
  730. protected bytes.  We will begin by looking at the effect of a single 
  731. byte error at position p.  There are two basic cases: p >= k and p < k.
  732.  
  733. The first case: If p >= k then there is an error in one of the two FEC 
  734. bytes.  This is indicated by Eqn 1 being satisfied when j = 0 or j = 1 
  735. but not both. 
  736.  
  737. The second case: If p < k then the error is not in the FEC bytes but in 
  738. the protected data.  In this case, Eqn 1 will not be satisfied for 
  739. either j = 0 or j = 1.  Instead we will get
  740.  
  741.   (the sum, as i goes from 0 to k-1 of Ci,j *Ri) + Rk+j = Ej      Eqn 2
  742.  
  743. where Ej = Ci,j * h, and h = Dp - Rp.  Thus as long as there is no q 
  744. (other then q=p) such that Cp,0 * Cp,1^-1 = Cq,0 * Cq,1^-1, we can 
  745. construct a function P(Cp,0 * Cp,1^-1) = p.  This condition is in fact 
  746. met by the coefficients chosen for Ci,j.
  747.  
  748. If p is found to be a valid number (less then k), we can subtract h 
  749. (where h = Ej * Cp,j^-1, and j = 0 or j = 1) from the value located at 
  750. p and the error is corrected.  This can be verified by using Eqn 1 on 
  751.  
  752.  
  753. Panabaker                                                     [Page 13]
  754.  
  755. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  756.  
  757. the new protected data block.  If p is not a valid number then we 
  758. assume there are at least two errors in the block.
  759.  
  760. It should be noted that by using any of the above corrections it is 
  761. possible to mistakenly turn a two-byte error into a three-byte error. 
  762.  
  763. 15.3.2. Correcting Single Byte Erasures
  764.  
  765. If we know where an error is in the protected block we can correct it 
  766. and still detect any other single byte error but not correct it.  We 
  767. might know the location of this erasure because a packet was lost 
  768. during transmission, and we are correcting the columns of our table.  
  769. Every column in this example will have an erasure at p, where p is the 
  770. lost packet row. 
  771.  
  772. First let's consider the case where p >= k, which means the erasure is 
  773. in the FEC.  We can use Eqn 1 to ensure the other FEC byte satisfies 
  774. the equation, and can therefore determine that the packet most likely 
  775. has no errors.  If it does not, we know there is at least one other 
  776. one-byte error and we cannot determine its location to fix it. 
  777.  
  778. The second possibility is that p<k, so the erasure is not in the FEC.  
  779. If Eqn 1 is satisfied for both j=0 and j=1 then we leave the erasure as 
  780. is, correct.  If Eqn 1 is satisfied by j=0 or j=1 but not both, then 
  781. there is an error we cannot correct.  If Eqn 1 is not satisfied by 
  782. either j=0 or j=1 and P(Cp,0/Cp,1) = p then we can correct the byte at 
  783. p by adding the result of (Ej * Cp,j^-1) for j=0 or j=1 (it shouldn't 
  784. matter which).
  785.  
  786. 15.3.3. Correcting Double-byte Erasures
  787.  
  788. In the case of a double byte erasure, we lose all error-detecting 
  789. capability.  Given the location of two erasures we can correct them 
  790. assuming all other bytes are correct.  There are three possible cases:
  791.  
  792. In the first case both erasures are in the FEC bytes.  In this case we 
  793. can use Eqn 1 to determine the correct value of Rk+j.
  794.  
  795. The second case has one erasure in the FEC, and another in the 
  796. protected block outside the FEC bytes at position p.  We can correct 
  797. the erasure at p as we would a single byte erasure by adding the 
  798. expression (Ej * Cp,j^-1), where Rk+j is not the erased FEC byte.  This 
  799. erasure in the FEC can now be corrected using Eqn 1 and solving for the 
  800. erased byte Dp.
  801.  
  802. In the third case, neither erasure is in the FEC bytes, so p < q <k.  
  803. This is the more difficult case.  Using our FEC algorithms developed 
  804. above we can write:
  805.  
  806. Ej   =  Cp,j (Dp + Rp) + Cq,j (Dq + Rq)
  807.  
  808. where j = 0 and j=1.  These two equations form a system of linear 
  809.  
  810.  
  811. Panabaker                                                     [Page 14]
  812.  
  813. < draft-panabaker-ip-vbi-00.txt >                            March 1997
  814.  
  815. equations.  Assuming Cp,j and Cq,j are non-zero (which they are in this 
  816. implementation), and Cp,0 * Cp,1^-1 does not equal Cq,0 * Cq,1^-1 
  817. (which is also true for all p < q < k), we can solve this system for Dp 
  818. and Dq.  
  819.  
  820. 15.4. Correcting FEC Bundles
  821.  
  822. We now have a set of tools for detecting and correcting errors in FEC 
  823. bundles.
  824.  
  825. 1) With no erasures, we can look at a row or column and say either: 
  826.         -  The FEC bytes match; there are probably no errors.
  827.         -  The FEC bytes fail to match in a way which could be 
  828.            caused by a single-byte error; in this case we can 
  829.            find the location and value of such an error.
  830.         -  The FEC bytes fail to match in a way which indicates
  831.            that there are at least two bytes of error.
  832.  
  833. 2) With one erasure, we can correct it and look at a line and say 
  834. either:
  835.         -  The FEC bytes now match; there are probably no other 
  836.            errors (beyond the erasure)
  837.         -  The FEC bytes don't match; there is at least one 
  838.            more error, which we cannot correct.
  839.  
  840. 3) With two erasures, we can correct the line so that the FEC bytes 
  841. match.  In this case, we have no error-detecting capability.
  842.  
  843. All of these tools can be used in an iterative manner on the rows and 
  844. columns of the FEC bundle to correct or detect errors. 
  845.  
  846. 15.5. Appendix References
  847.  
  848. [1] Norpak Corporation "TTX71x Programming Reference Manual", c1996, 
  849. Kanata, Ontario, Canada 
  850.  
  851. [2] Norpak Corporation, "TES3 EIA-516 NABTS Data Broadcast Encoder 
  852. Software User's Manual." c1996, Kanata, Ontario, Canada
  853.  
  854. [3] Norpak Corporation, "TES3/GES3 Hardware Manual" c1996, Kanata, 
  855. Ontario, Canada
  856.  
  857. [4] Pretzel, Oliver. ôCorrecting Codes and Finite Fields: Student 
  858. Edition" OUP, c1996
  859.  
  860. [5] Rorabaugh, C. Britton.  "Error Coding Cookbook" McGraw Hill, c1996
  861.  
  862. [6] Witty, Carl. 1997  Newton Research Labs, Seattle, WA
  863.  
  864.  
  865.  
  866.  
  867.  
  868.  
  869. Panabaker                                                     [Page 15]
  870.  
  871.